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

Версия 19:10, 21 февраля 2012

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

Итак, результат 0.482 можно получить простой MATLAB-программой (всего 940 байт с комментариями!), используя лишь стандартные функции size, sparse, bsxfun, full и т.д. На стареньком ноутбуке все вычисления (кроме загрузки данных) занимают 1 минуту. Дь-ов 16:32, 13 февраля 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:

Можно самому подсчитывать качество работы алгоритма на некоторой проверочной выборке, при условии что к ней есть правильные ответы (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)

Тестирование

Тестировать лучше на своей машине. Для этого можно разбивать множество объектов на два случайных подмножества: обучение и контроль. А затем проводить серию обучение/тестирование на нескольких случайных разбиениях.

matlab код функции разбивающей данные на два случайных подмножества:

function [X,Y,Xt,Yt]=splitData(S,y,n)
 %S-матрица объект-признак
 %y-матрица ответов
 %n-желаемый размер первого множества
 [m,~]=size(S);
 idx=randperm(m);
 X=S(idx(1:n),:);
 Y=y(idx(1:n),:);
 Xt=S(idx((n+1):end),:);
 Yt=y(idx((n+1):end),:);

Тестировать можно так:

function [favg,f]=test(S,y,n,m)
 %S-матрица объект-признак
 %y-матрица ответов
 %n-количество серий
 %m-желаемый размер контрольного множества
 %favg-усредненная f-мера по серии тестов
 %f-массив f-мер
 f=zeros(n,1);
 for i=1:n
     [X,Y,Xt,Yt]=splitData(S,y,m);
     model=train(Xt,Yt);
     label=classify(X,model);
     f(i)=fscore(label,Y); 
 end
 favg=sum(f)/n;

Разница между оценкой, полученной данным способом, и оценкой с сайта не превосходила .

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

Я думаю стоит зафиксировать разбиения и выложить его сюда, чтобы мы могли честно сравнивать результат. Peter Romov 09:24, 13 февраля 2012 (MSK)

Вывод результата

Код программы создания файла, готового к отправке на сайт

function MakeSubmit(Y_p,filename)
%Y_p - ответы классификатора
%filename - имя для файла с ответами
fid=fopen(filename,'w');
for i=1:size(Y_p,1)
    I=find(Y_p(i,:));
    if size(I,2)>0 
        fprintf(fid,'%d',I(1));
    else
        fprintf(fid,'44'); %44 - самая встречаемая рубрика
    end
    fprintf(fid,',%d',I(2:end));
    fprintf(fid,char(10));
end
fclose(fid);

Ildar 21:20, 14 февраля 2012 (MSK)

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

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

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

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

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

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

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

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

Замечание: после нормировки данных, произошло улучшение(результат 0.437). До этого было 0.4 и на некоторых признаках свм не сходился, теперь на любом признаке сходится за 10-15 итераций. Kondra 23:24, 15 февраля 2012 (MSK)

Не ясно, что значит свм не сходился. За сколько итераций сходимость не была достигнута? Каким методом оптимизировался функционал? Какое значение С? (как правило, чем выше С, тем больше нужно итераций) Peter Romov 01:27, 20 февраля 2012 (MSK)

Замечание: Если использовать нормировку по максимуму, то можно добиться результата 0.471. Andrew Ostapets 23:14, 18 февраля 2012 (MSK)

Замечание: Если использовать нормировку по максимуму, то можно добиться результата 0.509. nizhibitsky 16:39, 19 февраля 2012 (MSK)

Вывод: Если использовать линейные классификаторы, принимающие решения независимо, то можно получить достаточно высокий результат.

Идея: Попробовать различные преобразования признаков, и уже на них запускать линейные классификаторы. Andrew Ostapets 9:31, 19 февраля 2012 (MSK)

Идея: Для каждого класса подбирать свой оптимальный линейный классификатор. nizhibitsky 20:57, 19 февраля 2012 (MSK)

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

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

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

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

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

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

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

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

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

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

Можно попробовать использовать косинусную меру. Kondra 19:41, 15 февраля 2012 (MSK)

Эксперименты с метрическим алгоритмом

Получен результат 0.369. Описание: tf*idf, нормализация. В качестве ответа берется ближайший сосед по косинусной мере. Улучшения: оптимизировать число соседей. Kondra 23:57, 15 февраля 2012 (MSK)

Подбор числа соседей(пока что несколько вариантов вручную) привел к результату 0.462. Планирую сделать автоматический перебор. Ответ считается где-то за 16 секунд.(Core i7 3.40GHz) Kondra 23:40, 16 февраля 2012 (MSK)

Сделал автоподбор k, существенного улучшения от 0.46 нету. Попробую некоторые вариации tf*idf и нормировок. Kondra 20:55, 17 февраля 2012 (MSK)

Идея: попробовать SVD. Kondra 13:54, 18 февраля 2012 (MSK)

Выделение частичной иерархии

Идея: Наилучшим продолжением идеи Евгения Зака о поиске «часто вместе встречающихся» рубрик будет вычисление поддержки — ничто иное как условная вероятность совместной встречи категорий.

Реализация: Составляем матрицу условных вероятностей, например, так:

sup = zeros(83,83);
for i=1:83
    for j=1:83
        if sum(y(:,j)>0.5)~=0 && i~=j
            sup(i,j) = sum(y(:,i)>0.5&y(:,j)>0.5)/sum(y(:,j)>0.5);
        end
    end
end

Здесь - вероятность наличия рубрики при наличии рубрики (я не уверен в каноничности порядка индексов — гугл не признается, как же правильно записывается support).

Промежуточные результаты: Например, можно посмотреть максимально вероятную рубрику-пару для данной, и упорядочить по этой максимальной вероятности:

Вывод. Скорее всего, рубрика 50 является «хирургией» для «переломов» 46 (не наоборот!).

nizhibitsky 13:04, 13 февраля 2012 (MSK)

Метод ближайшего соседа

Функция, считающая расстояние в метрике Евклида. На входе: матрица X, размерность D*N, D - размерность вектора, N - количество векторов. Матрица Y, размерность D*P, D - размерность вектора, P - количество векторов.

На выходе: матрица D размера N*P, где в D(n,p) представлен !!!квадрат!!! евклидового расстояния между X(:,n) и Y(:,p).

function d = cvEucdist(X, Y)
if ~exist('Y', 'var') || isempty(Y)
    %% Y = zeros(size(X, 1), 1);
    U = ones(size(X, 1), 1);
    d = abs(X'.^2*U).'; return;
end
V = ~isnan(X); X(~V) = 0; % V = ones(D, N); 
U = ~isnan(Y); Y(~U) = 0; % U = ones(D, P); 
d = abs(X'.^2*U - 2*X'*Y + V'*Y.^2);

Ekaterina 22:50, 15 февраля 2012 (MSK)

Екатерина, код — это ok. Но здесь наиболее важно писать результат эксперимента, хотя бы он-лайн, или можно на кросс-валидации. Peter Romov 23:44, 15 февраля 2012 (MSK)

Нормировка исходных данных и линейные классификаторы

Как уже писалось ранее, в этой задачи независимые линейные классификаторы позволяют получать высокий результат. Только для этого нужно хорошо настроить классификаторы.

Для улучшения результатов проводится нормировка исходных данных.Все нормировки проводятся по столбцам(можно проводить нормировки и по строкам, но конечные результаты оказываются практически одинаковы). Было испытано 4 различных вида нормировок:

1) По сумме всех значений столбца.

2) По максимальному значению столбца.

3) По среднему значению столбца.

4) По среднему значению ненулевых элементов столбца.

В итоге, самый низкий результат получался при использовании 3-ей нормировки(максимум,который удалось достичь - 0.43). 1-ая и 2-ая нормировки, в итоге, показали примерно одинаковые результаты(максимальное значение в районе 0.49). И самый лучший результат удалось достичь при использовании 4-ой нормировки - 0.513.

После нормировки, необходимо настроить линейные классификаторы. Для настройки применяется кросс-валидация - выборка несколько раз разбивается на две подвыборки: обучающую и контрольную. Алгоритм настраивается по обучающей подвыборке, затем классифицируются объекты контрольной и подсчитывается F-score. Каждому набору параметров ставится в соответстие среднее по всем разбиениям величина F-score на контрольных подвыборках. В итоге, выбирается набор параметров с наилучшей средней оценкой.

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

Если для некоторого документа классификаторы не выдали ни одного ответа, то в этом случае выдается 5 самых популярных рубрик в тренировочной выборке.

Такой алгоритм получил результат 0.513, и вполне вероятно, что его можно еще улучшить)

Andrew Ostapets 20:50, 19 февраля 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)

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

• Зависимость рубрик. Идея такова: раз это реальные медицинские статьи, то рубрики, к которым они принадлежат, могут быть зависимы (например, статья из рубрики «переломы рук» точно принадлежит рубрике «хирургия»). Для того, чтобы проверить эту гипотезу я посмотрел сколько раз какие две рубрики встречаются вместе для всех статей. и получил следующие результаты (более подробно(а именно таблицу пар) напишу 13 вечером, а то спать хочется=)):

1)Из 3403 возможных пар рубрик 2377(69,9 %) пар хотя бы раз встречаются вместе;

2)Среди количества одновременных встреч: минимальное 0, максимальное 1278 раз, среднее 27,68 раз. Количеств, больших среднего: 1130(23,8 %).

Отсюда мысль: если статья принадлежит рубрике A, и есть рубрика B, такая что А и В вместе встречаются очень часто(скажем чаще, чем пороговое k), то наша статья принадлежит и рубрике В. E_zak 03:13, 13 февраля 2012 (MSK)

• Классификация one-vs-one. То есть отделение каждой пары классов друг от друга. Здесь уже нужно n*(n-1)/2 классификаторов. Kondra 23:52, 15 февраля 2012 (MSK)

• Комбинирование результатов алгоритмов. Идея: построить N классификаторов, которые имеют различную природу. В тренировочной выборке на каждый объект приходится чуть менее 4 тем. Настроить классификаторы так, чтобы для каждого объекта они выдавали немного завышенное число тематик. Скажем, порядка 8 тем. В итоге, оставить для каждого объекта только тебе темы, которые выдали хотя бы N/2 классификаторов. Andrew Ostapets 0:44, 19 февраля 2012 (MSK)

• Вычисление оценок. Идея: поскольку матрица сильно разрежена, а признаковое пространство нашей задачи устроено таким образом, что по отдельности признаки неинформативны, но представительные наборы из 2-3 признаков могут обладать хорошей информативностью, то можно попробовать алгоритм КОРА (Вапник или Воронцов). Про формулы оценок принадлежности к классам нормально есть в нашей методичке (или лекции АМА).Матрица бинаризуется по правилу ноль-не-ноль. Выборку по классам можно делить один против всех (получаем 83 независимых алгоритма). Самостоятельно такое решение вряд ли сможет дать хорошие результаты, но в качестве дополнительных признаков в SVM, или внутри Committee Boosting (Воронцов) может оказаться весьма полезным. О результатах экспериментов позже. Berezin 22:09, 21 февраля 2012 (MSK)

Инструменты

LIBLINEAR

LIBLINEAR — библиотека с алгоритмами линейной классификации. Отличается тем, что может работать с очень большими матрицами объект-признак достаточно быстро, может справляться с разреженными матрицами объект-признак, которые в полном объеме не помещаются в память.

Подготовка к использованию с MATLAB. Нужно скачать архив, распаковать его, пользователям не-windows прочитать README и собрать MEX-файлы. Затем в матлабе нужно добавить путь к каталогу с MEX-файлами библиотеки (у пользователей windows это подкаталог liblinear/windows), после чего должны появиться функции train и predict, если их вызвать без параметров, они покажут справочную информацию.

addpath c:/.../liblinear/windows
>> train
Usage: model = train(training_label_vector, training_instance_matrix, 'liblinear_options', 'col');
liblinear_options:
...
>> predict
Usage: [predicted_label, accuracy, decision_values/prob_estimates] = predict(testing_label_vector, testing_instance_matrix, model, 'liblinear_options','col')
liblinear_options:

Обучение модели. Пример: натренируем классификатор, отличающий документы относящиеся к категории 1 от всех остальных.

>> model = train( full(Y(:,1)), X, '-s 3 -c 100 -B 1' )

Функция имеет параметр -v N, который позволяет провести N-fold скользящий контроль, в таком режиме train выдает не модель, а точность классификации на скользящем контроле — это может помочь при настройке параметров.

Классификация. Функции классификации обязательно нужно передавать правильные метки для объектов для того чтобы она посчитала точность классификации, если правильных ответов нет (вы считаете результат на тестовой выборке — нужно сделать вектор из нулей).

>> Y_p(:,1) = predict(zeros(size(X,1), 1), X, model)
>> Y_p(:,1) = predict(full(Y(:,k)), X, model)
Accuracy = 99.36% (9936/10000)

Peter Romov 11:43, 13 февраля 2012 (MSK)
Проблема у пользователей MSVS
Если после установки библиотеки функции train и predict не вызываются, значит нужно собрать библиотеку вручную.
Делается это просто:

• Делаем текущей папкой c:/.../liblinear/matlab
• Выполняем команду make
• Выполняем команду addpath('c:/.../liblinear/matlab');

Ildar 21:34, 14 февраля 2012 (MSK)

R

Для установки языка R (для реализации Random Forest) http://cran.gis-lab.info/

Random Forest http://cran.r-project.org/web/packages/randomForest/index.html

Пособие (минимальное и не факт, что адекваное, по R) http://en.wikibooks.org/wiki/R_Programming

Ekaterina 15:11, 13 февраля 2012 (MSK)

Random Forest для MATLAB

http://code.google.com/p/randomforest-matlab/

Peter Romov 01:30, 20 февраля 2012 (MSK)