Обсуждение:Практикум на ЭВМ (317)/2011-2012

Материал из MachineLearning.

(Различия между версиями)

Перейти к: навигация, поиск

Версия 20:13, 12 февраля 2012

Содержание

1 Реальная задача «Topical Classification of Biomedical Research Papers»

Реальная задача «Topical Classification of Biomedical Research Papers»

Очень неплохо, Пётр! Вы интенсивно собираете баллы первой части задания.

Только я не уверен, что можно выкладывать файл с данными... Не нарушаем ли мы этим какие-нибудь правила? Ведь для того, чтобы получить данные, надо зарегистрироваться (т.е. они изначально не хранятся в открытом доступе). Корректнее предоставить одногруппникам MATLAB-код для считывания данных (по крайней мере, я писал отдельный код).

Удачи! Приятно видеть "наших" в турнирной таблице! Дь-ов 22:22, 9 февраля 2012 (MSK)

Постановка, данные

Подробное описание задачи: [1].

Объект (журнальная статья) описывается 25640 признаками --- целые числа 0...1000. Каждый признак означает насколько сильно журнальная статья связана с медецинским термином. Признаковые описания разреженные: большая часть признаков у одного объекта равны 0, что означает что одна журнальная статья связана лишь с небольшим числом медецинских терминов.

Имеется 83 тематик (topics). По признаковому описанию журнальной статьи нужно сказать, к каким тематикам она относится. Выход классификатора: подмножество чисел 1..83.

Данные:

тренировочная выборка, 10'000 объектов, для каждого объекта список тематик, к которым он относится
тестовая выборка, 10'000 объектов

На сайте соревнования выложены текстовые файлы с матрицами объект-признак, после распаковки они весят под 500МБ и очень долго считываются в матлаб. Я сделал MAT-файл data.mat (ссылка в рассылке), в котором лежат sparse-матрицы (вид представления матриц в матлабе при котором запоминается список ненулевых элементов матрицы):

X, X_t — объект-признак для тренировочной и тестовой выборок;
Y — матрица правильных ответов для тренировочной выборки, размера 10'000x83, в каждой строке стоят единицы на месте столбцов с номерами выбраных тематик.

Матлаб функция, которая записывает результат классификации, представленный в виде матрицы Nx83 (как Y), в файл готовый для отправки в систему: [2].

Пример: решение, которое каждому объекту ставит в соответствие 5 наиболее часто встречаемых тематик

load('data.mat');
[~, idx] = sort(sum(Y), 'descend');     % после чего в idx номера тематик в порядке убывания их популярности
Y_t = sparse(size(X_t, 1), size(Y, 2)); % пустая матрица ответа
Y_t(:,idx(1:5)) = 1;                    % для каждого объекта выбираем 5 наиболее популярных тематик
sparse2labels(Y_t, 'majority.csv');

Peter Romov 16:15, 9 февраля 2012 (MSK)

Система оценки

Качество результата подсчитывается при помощи стандартной в Information Retrieval метрике: F-score.

Введем обозначения:

N — число документов
TrueTopics_i — множество верно предсказаных тематик для i-го документа
PredTopics_i — множество предсказанных тематик для i-го документа

Величины Precision и Recall для документа i:

$\text{Precision}_i = \frac{|\text{TrueTopics}_i \cap \text{PredTopics}_i|}{|\text{PredTopics}_i|}, \qquad \text{Recall}_i = \frac{|\text{TrueTopics}_i \cap \text{PredTopics}_i|}{|\text{TrueTopics}_i|}$
$\text{Fscore}_i = 2 \cdot \frac{\text{Precision}_i \cdot \text{Recall}_i}{\text{Precision}_i + \text{Recall}_i}, \qquad \text{AvgFscore} = \frac{1}{N} \sum_{i=1}^N \text{Fscore}_i$

Можно самому подсчитывать качество работы алгоритма на некоторой проверочной выборке, при условии что к ней есть правильные ответы (ground truth).

Обратите внимание: результат, которые выдает система он-лайн проверки подсчитывается на случайном подмножестве тестовой выборки, в 10 раз меньшем всей тестовой выборки.

Peter Romov 22:16, 9 февраля 2012 (MSK)

Пример matlab кода для вычисление F-меры:

function F=fscore(Y,A) 
%Y-predicted
%A-true
%Y and A are n x 83 matrices where n is the size of validation set
%Y(i,j)==1 if i document refers to j topic
N=size(Y,1);
Y=(Y==1)';
A=(A==1)';
c=(Y==1)&(A==1);
tp=sum(c);
p=tp./sum(Y==1);
r=tp./sum(A==1);
f=2*(p.*r)./(p+r); 
F=sum(f(~isnan(f)))/N;

Kondra 23:13, 12 февраля 2012 (MSK)

Эксперименты

Независимые классификаторы

Идея: свести задачу предсказания "подмножества" к задаче классификации на 2 класса.

Обучаем набор из 83 классификаторов для независимого решения по каждой тематике, каждый классификатор соответствует одной тематике и отвечает на вопрос "относится/не относится".

На некоторых объектах может получиться так, что ни один классификатор не дал положительного результата, но результат "пустое множество тематик" не допускается по правилам.

Эту проблему я решил эвристически: такие объекты привязываются к одной тематике, выбирается та тематика, чей классификатор дал наиболее близкое к положительному решающее значение, т.е. чей классификатор наименее уверенно ответил отрицательно на вопрос "относится ли объект к тематике?" Таких объектов в тестовой выборке оказалось 188 (линейные классификаторы). Peter Romov 21:28, 9 февраля 2012 (MSK)

Утверждение: признаков в 2.5 раз больше числа объектов ⇒ по отношению к одной тематике, обучающая выборка линейно разделима, очень уверенно разделима. Peter Romov 21:28, 9 февраля 2012 (MSK)

Классификатор	Результат (он-лайн)	Примечание
Линейные L2-reg L2-loss L1-reg L2-loss L2-reg L1-loss liblinear	0.393	Различные постановки задачи обучения дали одинаковые ответы (с точностью до выбора тематик), подбор коэффициента регуляризации бессмысленен (уверенная линейная разделимость). Что можно сделать: регулировать пороги решающих правил.

Предположение: другие классификаторы / методы, принимающие решения независимо, будут давать схожий результат; предположение независимости принадлежности статьи к разным тематикам очень наивно и нужно двигаться в сторону учета зависимостей между тематиками. Peter Romov 21:28, 9 февраля 2012 (MSK)

Классификация данных как текста (метрический алгоритм)

Идея: Считаем, что представленные величины являются просто количеством соответствующих терминов в тексте, так же используем независимые классификаторы по всем рубрикам.

Заменяем матрицу данных на классическую матрицу из весов $TF\times IDF$ :

$TF$ (term frequency — частота слова) — отношение числа вхождения некоторого слова к общему количеству слов документа. Таким образом, оценивается важность термина в пределах отдельного документа:

$tf_{ij}=\frac{t_i}{\sum_{l=1}^Tt_l}$

$IDF$ (inverse document frequency — обратная частота документа) — инверсия частоты, с которой некоторый термин встречается в документах коллекции. Учитывает тот факт, что если термин встречается во многих документах множества, то он не может являться существенным критерием принадлежности документа рубрике и наоборот:

$idf_i=log\frac{|D|}{n_i}$

После нормализации полученных весов строим т.н. «центроиды» — стандартизированные представители рубрик — просто среднее арифметическое векторов-представителей данной рубрики и запускаем простой метрический алгоритм для тестовой выборки — относим вектора к центроидам, которые ближе, чем некий порог, либо к минимально близкому из практических соображений.

Более подробно можно посмотреть, например, в дипломной работе.

Результат: Удалось достичь результата 0.306 с упущенной из виду нормировкой весов — итоговую функцию можно посмотреть здесь. (Вектора относятся к классам, центроиды которых удалены не более, чем на 0.8. Время построения матрицы весов — 25 минут, время классификации тестовой выборки — 2.5 часа на C2Dm/2.5GHz).

Пути улучшения: Попробовать другие метрики, модификации матрицы $TF\times IDF$ .

nizhibitsky 21:32, 12 февраля 2012 (MSK)

Идеи

Цепочка независимых классификаторов. Как использовать простую классификацию на два класса, но все таки учитывать зависимости между метками принадлежности тематикам? Например так: принимать решение по тематике 1 исключительно по признакам, решение по тематике 2 принимать по {признакам + принадлежности тематике 1}, ..., решение по тематике N принимать по {признакам + решениям о тематиках 1...N-1}. Т.е. образовать "цепочку" из классификаторов. Peter Romov 21:41, 9 февраля 2012 (MSK)

Разбиения. Зафиксировать несколько разбиений имеющейся обучающей выборки на тренировочную/тестовую, которую все будут использовать для оценки точности алгоритма. Это может быть полезно т.к.: 1) он-лайн система тестирования считает качество алгоритма на случайном подмножестве всей тестовой выборки (в правилах написано, что используется ≈10% объектов), т.е. оценка качества может быть неточной; 2) количество попыток отправить ответ на тестовой выборке ограничено 200 попытками, это много, но все же. Peter Romov 21:48, 9 февраля 2012 (MSK)

Случайное подмножество выбрали до начало конкурса — оно фиксировано для всех отправляющих. nizhibitsky 00:29, 10 февраля 2012 (MSK)

Терминология, нотация. «метками принадлежности тематикам»... придумать нормальную русскоязычную терминологию и договориться использовать ее, договориться о символьных обозначениях, например $x_i$ , y_j. Peter Romov 21:41, 9 февраля 2012 (MSK)

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5:%D0%9F%D1%80%D0%B0%D0%BA%D1%82%D0%B8%D0%BA%D1%83%D0%BC_%D0%BD%D0%B0_%D0%AD%D0%92%D0%9C_%28317%29/2011-2012»

Обсуждение:Практикум на ЭВМ (317)/2011-2012

Материал из MachineLearning.

Версия 20:13, 12 февраля 2012

Содержание

Реальная задача «Topical Classification of Biomedical Research Papers»

Постановка, данные

Система оценки

Эксперименты

Независимые классификаторы

Классификация данных как текста (метрический алгоритм)

Идеи

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты