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

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

(Различия между версиями)
Перейти к: навигация, поиск
м (Классификация данных как текста (метрический алгоритм))
(Постановка, данные)
Строка 58: Строка 58:
[[Участник:Peter Romov|Peter Romov]] 22:16, 9 февраля 2012 (MSK)
[[Участник:Peter Romov|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|Kondra]] 23:13, 12 февраля 2012 (MSK)
== Эксперименты ==
== Эксперименты ==

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

Содержание

Реальная задача «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 — число документов
  • TrueTopicsi — множество верно предсказаных тематик для i-го документа
  • PredTopicsi — множество предсказанных тематик для 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, yj. Peter Romov 21:41, 9 февраля 2012 (MSK)