Совместный выбор объектов и признаков в задачах многоклассовой классификации коллекции документов

Полный текст

Введение В работе рассматривается задача многоклассовой классификации документов [1-2]. Документами являются ответы поисковой машины на запросы пользователей. В качестве меток классов используется линейно-упорядоченный набор, отражающий степень релевантности документа запросу. Требуется каждому документу поставить в соответствие число, характеризующее его релевантность запросу. Одними из методов, с помощью которых решают эту задачу являются SVM-регрессия [3] и случайные леса [4]. В данной работе для решения задачи классификации используется многоклассовая логистическая регрессия [5]. Для ранжирования документов по релевантности внутри классов и оценки параметров регрессии предлагается модификация многоклассовой логистической регрессии. В вычислительном эксперименте представлены результаты работы предложенных алгоритмов на данных поисковой выдачи Яндекса [6]. В качестве базового алгоритма, с которым происходит сравнение, используется многоклассовая модификация SVM [7]. Для оценки качества используется Discounted Cumulative Gain [8]. Каждый документ исследуемой коллекции [6] описан 245 признаками. Обучающая выборка содержит почти 105 документов. Поэтому необходимо произвести отбор объектов и признаков. Задача отбора признаков и объектов решается предложенным в работе алгоритмом. В качестве альтернативного решения используется генетический алгоритм [9-10]. Размер и состав наборов признаков, отобранных обоими алгоритмами, сравниваются. Постановка задачи Пусть нам заданы выборка D = {(х,.,^.)}, матрица признаков в которой X = [x^...,x^]TeR^n; N - число записей данных; n - число признаков, и вектор ответов У = 1>ц- • -Ovf; yt G Y с N0, где Y - линейноупорядоченное конечное множество, состоящее более чем из одного элемента. Для определения принадлежности объектов x классам у используется модель многоклассовой логистической регрессии - параметрическая функция /:(©,x)->j>e7, (1) отображающая пару «параметры, объект» в метку класса у из множества Y. Для оценки адекватности модели задачи используется функция качества S(@, Х,А,В), где © - набор параметров модели; X - набор индексов некоторого множества объектов; А - набор индексов используемых признаков; В - набор индексов, используемых при обучении объектов. А Поиск оптимального набора параметров 0 осуществляется следующим образом: 0 = argminQ(0,B,A,B), (2) 0eRX где L - размерность пространства параметров модели. Задачу поиска оптимальных наборов объектов и признаков {Xy}JeA; {*,},*'е В сформулируем в виде (А,В) = argmin Q(&, S, В, А). (3) A=J,Bd Требуется по обучающей выборке оценить параметры © модели, чтобы затем классифицировать объекты в предположении, что из исходного множества признаков - столбцов матрицы X = [Xiv>Xn] и исходного множества объектов отобраны некоторые подмножества признаков {Ху},у € А и объек- «Инфокоммуникационные технологии» Том 12, № 1, 2014 48 Адуенко А. А., Стрижов В.В. I А I ^ тов, оптимальных согласно (3), | А |= п ^п, | В |= < N. Параметр © находится путем максимизации качества модели 6(0,X,А,В) на обучающей выборке S. Задача нахождения оптимального набора объектов и признаков решается в работе с помощью предложенного шагового алгоритма и с помощью генетического алгоритма. Алгоритм многоклассовой логистической регрессии Сопоставим каждому классу Ск,к = 1, ...К весовой вектор w^. е R”, где n - число признаков . Тогда для объекта Хг- вероятность попасть в класс Ск в модели логистической регрессии равна Ул ехр ак К ХехРа/ /=1 и с учетом (8) получим дУя даj ехр ак 8ai /=1 ехр а* ХехР ai \i=i . ' к Л2 ХехРа/ V /=1 У&1и ~УлУг да\ (8) Р(Ск |ж() = expw*x,. -,i е I. (4) j=i ^expwjx,. Введем для обозначение yik. Для каждого объекта хг,/е1 введем целевой вектор ti, где к е [0, 1] есть принадлежность объекта хг классу Ск. В нашем случае на обучающей выборке считаем tik = 1, если объект Хг. лежит в классе Ск, иначе tik = 0. Обозначим целевую матрицу, составленную из tik Т = [fft]. Запишем функцию правдоподобия выборки, используя (4): N К N К Р(т|wls...,wr)=ПГИС* Iх<)'*ПГЬ* (5) 1=1 к=\ i=l к=1 Запишем отрицательный логарифм функции правдоподобия (5) и поставим задачу его минимизации: £(w„...,wr) К N к=1 i=l min (6) ¥i.....w* Для нахождения минимума функции (6) рассчитаем ее градиент и гессиан. Введем обозначение ак = w^x;. Рассчитаем да\ dyik сначала dw. и да) dal к - dw, (7) где - элемент единичной матрицы. Запишем yik через {а)}^=1 следующим образом: Таким образом Из (7) и (9) получаем ОУа _дУ1к 8aJ dw j да\ dWj то есть dyik dw j y*(!» -yvW Искомый градиент имеет вид Vw£(wi,.-,wj = N К 1 дУп ik _ (9) (10) = -ZZ/л я™ ин yik 5wj N К j = “ZS* -Угк (jkj - Уу )Xi = i=l k=1 У ik N N К N (11) i=1 i=l k=1 i=l Из выражений для градиента (11) и (10) для подматрицы размера LxL гессиана Н получаем Vw Vw £К,...^) = 'к -j ( N = v_ Л Ч 1=1 (12) XX'Vw, У у ^Уу V)к - yik • 1=1 1=1 «Инфокоммуникационные технологии» Том 12, № 1, 2014 Адуенко А. А., Стрижов В.В. 49 Гессиан H есть матрица размера LKxLK вида Н ГНп ... Н1К' Если бы H была положительно определенной матрицей, то для нахождения оптимального вектора весов можно было бы воспользоваться методом Ньютона-Рафсона: "t+l-W -ccH'VE,а >0. w (13) Однако из (12) получаем, что в каждой строке матрицы H сумма равна нулю, то есть матрица H вырождена и метод Ньютона-Рафсона не применим. Поэтому в работе используются методы безусловной минимизации первого порядка. Определив векторы по формуле (4), найдем для каждого объекта Х(- вероятности ты . Класс С „ к которому будет отнесен объект X., найдем из условия k* = argmaxP(Ct | х,.). (14) к=\,..^К Заметим, что алгоритм многоклассовой логистической регрессии, описанный выше, классифицирует объекты и потому не подразумевает сравнения объектов внутри классов (объекты из разных классов сравнимы, так как метки классов линейно-упорядочены). Это ведет к неустойчивой и часто неправильной классификации объектов, у которых несколько классов близки к выполнению (14). Поэтому далее откажемся от требования, что yt принадлежит конечному линейно-упорядоченному множеству Y, заменив его на требование принадлежности значения у. отрезку [С^С^-], считая классы линейно-упорядоченными. Тогда рассматриваемая задача перестанет быть задачей классификации, а становится задачей регрессии на отрезок. Для ее решения можно использовать полученное ранее решение задачи классификации. С учетом линейной упорядоченности меток классов в качестве оценки у. рассмотрим (15) k=1 Алгоритмы отбора объектов и признаков Рассмотрим пошаговый алгоритм совместного отбора объектов и признаков. Вернемся к задаче отбора признаков (3). Предложим алгоритм, позволяющий отбирать не только признаки, но и объекты. В частном случае этого алгоритма, когда отбор объектов не производится, он переходит в алгоритм отбора признаков. Будем пошагово отбирать объекты и признаки для модели многоклассовой логистической регрессии. Отбор признаков будем проводить из всего множества признаков. Для отбора объектов введем два множества В, и В2. Из Вj происходит отбор множества Вх ^ Вх объектов, которые и будут объектами, по которым будет происходить минимизация (6) и нахождение векторов весов wlv. .,W*. По множеству В2 происходит контроль, и решение о добавлении или удалении объектов и признаков будет приниматься по изменению значения оптимизируемой функции Е( wlv..,wj именно на множестве В2. Различие множеств Во и Д позволит избежать минимизации Е(Wj,...jW^) исключительно за счет уменьшения размеров множества Д1. Приведем описание алгоритма. Алгоритм на входе имеет шесть параметров: А» 4’ U2; Dx и D2, смысл которых разъясняется ниже. На начальном этапе задаем множество объектов модели Y cz Хх и множество признаков модели А = {1}: где 1 соответствует постоянному признаку. Пусть на очередном шаге значение функции потерь на множестве Х2 равно E. Затем в имеющуюся модель по очереди добавляем признаки f.e J. Для полученных моделей Y = Y,Aj = A'U {_/} считаем значение функции потерь Е на множестве X2. Находим J = argmine,. (16) Вычислим значение критерия г = (Е - Е ») /е. /j ж_ _ .* в модель, в противном случае фиксируем признак f * и пробуем в новую модель добавить еще один признак - если общее число добавляемых признаков не превышает Dx. Критерий добавления остается прежним: г> щ, но Г рассчитывается уже при добавлении в модель полученного на очередном шаге набора признаков. Затем пытаемся добавить новый объект в модель аналогично добавлению признака, с той разницей, что для принятия решения о добавлении объекта используется параметр и2, а число добавляемых объектов не превышает D2. После этого осуществляем поочередно удаление признаков и удаление объектов из модели по «Инфокоммуникационные технологии» Том 12, № 1, 2014 50 Адуенко А. А., Стрижов В.В. аналогичному правилу. С той разницей, что при удалении признаков г рассчитывается по фор * муле r = (E-E^)/EJ , где j определяется из условия (16) при Aj = А\{у'}. Максимальное число удаляемых признаков также равно Dx. Удаление происходит, если г <1Х. По аналогии с удалением признаков происходит удаление объектов - с той лишь разницей, что удаление происходит, если г<12, а максимальное число удаляемых объектов равно D2. Чтобы алгоритм останавливался, требуется наложить условия 11<г1 и 12< г2 на значения параметров. Если на очередной итерации не происходит добавление или удаление признаков или объектов, то алгоритм останавливается. Опишем генетический алгоритм отбора признаков. Рассмотрим обучающую выборку S и поставим задачу отбора множества признаков {3C;}Je А , используемых в логистической регрессии: [A,{wI9...,w^}] = = argmin £(w,.....w,). (17) {wj.....w jr }eR^, Ac J Опишем итеративный алгоритм, который применялся для решения задачи отбора признаков (17). Будем характеризовать набор индексов использующихся признаков А вектором Ь из 0 и 1 размерности | J |= п . Пусть перед г-ой итерацией алгоритма есть некоторый набор векторов V = {Ь15.где v=\V\. Каждому вектору Ь- из V сопоставим число minA=A(b.),{w1.....WA:}eRlAl . .,W^) . Исключим из набора V долю а векторов с наибольшими значениями £г и заменим их дубликатами векторов с долей (X с наименьшими значениями е;. Затем разобьем векторы на пары .UJ новые векторы bi - (b^, и Функционал качества многоклассовой классификации Рассмотрим функционал качества Q2 оценки качества решения задачи. Рассмотрим произвольный запрос (Jj , где Q - множество всех запросов, и соответствующие ему документы и оценки их релевантности = {xi,yj},i е I .. Здесь \. задает набор индексов документов, соответствующих запросу qj. Для каждого qj отсортируем документы внутри Q по убыванию их оценок релевантности у, получим множество D.J. При этом документы хг,Ху с одинаковыми оценками релевантности у. = у располагаются в порядке убывания их реальных релевантностей yt и yj. Обозначим ind(x.) - номер документа х;. в I. В качестве функционала качества будем использовать DCG, усредненный по запросам: 1 161 -YdCG„ \Q\P J где |ni' Jind(xp (18) (19) i=\ l0g2i + l Последняя сумма берется по элементам {Xpj),},/ e \j. Проанализируем функционал качества DCG.Рассмотрим произвольный запрос q и два документа Xj и х2, относящихся к этому запросу. Предположим, что К = 5 и для СХ,...С5 вычислены следующие вероятности Р{Ск | х,), Р{Ск | х2); к = 1,... 5 по формуле (4) - см. таблицу 1.Оба вектора Xj и х2 в соответствии с (14) будут отнесены к классу С2 . Однако (если v нечетно, то один вектор вектор х2 следует ранжировать выше, чем может остаться без пары). Внутри каждой пары проведем операцию скрещивания, которая заменяет пару векторов на некоторую другую пару векторов. Правила этой замены будут описаны ниже. Затем с каждым из получившихся векторов с вероятностью p происходит мутация, то есть случайный бит b меняется на противоположный. Опишем операцию скрещивания. Рассмотрим пару векторов: bi={b[,...bln) ; Ь . = ф(,...bJn)T. Сгенерируем случайное натуральное число z el, ...п. Тог -да результатом операции скрещивания, примененной к векторам Ьг и , будут Ч ’ так как для х2 вероятности попасть во все классы выше С2 не ниже, чем для Xj, а вероятность попасть в класс С4 выше. Это находит отражение и в функционале (19), так как если у2 > ух, а у2 = ух, то значение DCGq для запроса q будет ниже, чем если бы было выполнено у2 "> уv С этой трудностью справляется предложенная модификация алгоритма многоклассовой логистической регрессии. Например, для указанных векторов х, и х2 в соответствии с (15) 1,8 = у2 > ух = 1,05 . Предположение о том, что модификация логистической регрессии будет лучше в терминах функционала «Инфокоммуникационные технологии» Том 12, № 1, 2014 Адуенко А. А., Стрижов В.В. 51 качества Q2 (19), чем исходный алгоритм логистической регрессии, подтверждается экспериментальным путем. Таблица 1. Вероятности классов (пример) Класс xi Х2 С,= 0 0,3 0,05 С2= 1 0,.5 0,5 С3= 2 0,.1 од с4 = з 0,05 0,3 С5 = 4 0,05 0,05 Вычислительный эксперимент Цель вычислительного эксперимента сравнить работу базового алгоритма SVM и предложенного в работе алгоритма. Алгоритмы сравнивались на реальных данных Яндекса [6], а также на синтетической выборке объектов трех классов, обладающей свойством линейной разделимости. В качестве синтетической выборки была взята линейно разделимая выборка объектов, принадлежащих трем классам. В выборке было 2700 объектов, по 900 объектов каждого класса (см. рис. 1). Рис. 1. Синтетическая выборка, три класса описаны точками в пространстве двух признаков В вычислительном эксперименте строилась зависимость функционала качества Q2 (19) от числа элементов в обучающей выборке. Разбиение на обучающую и тестовую выборки осуществлялось случайно. Для каждого размера обучающей выборки проводилось 10 экспериментов. Полученные значения Q2 усреднялись. На рис. 2 приведена зависимость функционала качества Q2 на обучении и тесте в зависимости от размеров обучающей выборки. В терминах функционала Q2 предложенный алгоритм оказывается более предпочтительным, поскольку в отличие от SVM при размере выборки в 700 элементов значение Q2 и на обучении, и на контроле равно максимально возможному. Более того, для нахождения весов признаков с помощью алгоритма SVM необходимо решить задачу минимизации для двойственных переменных, количество которых равно числу объектов в обучении, что при большой обучающей выборке весьма затратно. Рис. 2. Зависимость функционала Q2 от размера обучающей выборки: а) для базового алгоритма; б) для предложенного алгоритма Оптимизация же функции E(wv...,WK) в логистической регрессии происходит в пространстве заметно меньшей размерности d = Кт . Для демонстрации работы пошагового алгоритма отбора объектов и признаков к рассматриваемой синтетической выборке было добавлено 10 шумовых признаков. В качестве множества Bj был взят случайный набор из 150 объектов, по 50 объектов каждого класса. В качестве множества В2 был взят случайный набор из 1000 объектов выборки. «Инфокоммуникационные технологии» Том 12, № 1, 2014 52 Адуенко А.А., Стрижов В.В. Использовались следующие параметры алгоритма: Dx= D2=2 ; Ix=12=Q\ rx = r2 = 0,04. Сравнивались два алгоритма: отбор только объектов и отбор объектов и признаков. В обоих случаях все шумовые признаки были отфильтрованы. При отборе и объектов, и признаков было отобрано 97 из 150 объектов. Число ошибок классификации на всей выборке в случае с отбором только объектов составило 32, для алгоритма отбора и объектов, и признаков - 13. Полученные результаты говорят о применимости приведенного алгоритма совместного отбора объектов и признаков для задач, где число объектов не слишком велико. Реальные данные представляют собой выборку объемом 97290 объектов, которые относятся к пяти линейно-упорядоченным классам {0; 1; 2; 3; 4}. Объекты представляют собой выдачи Яндекса на поисковые запросы. Все признаки нормированы на отрезок [0; 1], номера классов соответствуют релевантности полученной выдачи соответствующему запросу. Общее число признаков равно 245. Таблица 2. Сравнение логистической регрессии и базового алгоритма SVM Алгоритм Значение Q2 SVM 3,520 Логистическая регрессия 3,639 Подготовка данных. Особенностью представленной выборки является малое число объектов классов 3 и 4, менее 3% объектов каждого из классов и наличие почти постоянных признаков. Для устранения мультиколлинеарности воспользуемся методом главных компонент [11]. В данной работе были взяты 63 главные компоненты из условия XIХ^ > Р = 3 -10“3, где Хтах - максимальное собственное число матрицы ХТХ; X -собственное число, соответствующее рассматриваемой главной компоненте. Кроме того, с учетом малого числа объектов классов 3 и 4 обучающая выборка была дополнительно сбалансирована и содержала примерно одинаковое количество объектов из каждого класса. Сравнение логистической регрессии и SVM. Приведем значения функционала Q2 при классификации объектов с помощью многоклассовой логистической регрессии и с помощью базового алгоритма SVM (см. таблицу 2). Алгоритм логистической регрессии оказывается более предпочтительным в терминах функционала Q2 (18). Рис. 3. Зависимость доли объектов, обладающих рассматриваемым признаком, от номера итерации Рис. 4. Зависимость минимального значения функции потерь от номера итерации Номер сегмента Рис. 5. Распределение признаков по частоте встречаемости в наборе «Инфокоммуникационные технологии» Том 12, № 1, 2014 Адуенко А. А., Стрижов В.В. 53 Отбор объектов и признаков. В рассматриваемой задаче отбор объектов в силу их большого числа затратен, а потому не проводился. Проводился лишь отбор признаков. Наборы признаков, отбираемые двумя предложенными в работе алгоритмами, заметно пересекаются, однако при рассматривавшихся параметрах алгоритма шагового отбора он отбирает меньше признаков. Число отобранных признаков и качество классификации в терминах 02 (19) приведено в таблице 3. Для генетического алгоритма графики зависимости доли объектов с наличием признака в множестве V приведены на рис. 3. Кривая зависимости минимального на V значения функции потерь E (6) от номера итерации показана на рис. 4. Распределение признаков по доли объектов, им обладающих, после 50 итераций генетического алгоритма иллюстрирует рис. 5. Далее по отобранным наборам признаков решалась задача нахождения векторов весов wiv-jwjf в соответствии с (6).Затем применялась предложенная модификация алгоритма логистической регрессии. Результаты. Таблица 2 демонстрирует полученные результаты в терминах Q2 (18). Достигнутое значение 02 = 4 ,058 превосходит результат базового уровня, полученный Яндексом [6]. Это позволяет говорить о применимости предложенного алгоритма для ранжирования документов. Для сравнения качества с существующими алгоритмами был использован пакет SVMlight в режиме построения регрессии. Полученное значение функционала качества DCG равно 4,234 при обучении по всей обучающей выборке. Это на 4,5% выше, чем получено предложенным алгоритмом, потому предложенный алгоритм можно, по-видимому, улучшить еще. Таблица 3. Сравнение качества Q2 для двух алгоритмов отбора признаков Алгоритм Число при Q2 для лог. Q2 для моотбора знаков регрессии диф. лог. регрессии Пошаговый 12 3,612 4,028 Г енетический 18 3,639 4,058 Заключение В данной работе рассматривалась задача ранжирования коллекции документов поисковой выдачи. Для ее решения предложен алгоритм многоклассовой логистической регрессии. Представлена его модификация, которая по результатам вычислительного эксперимента значительно улучшает качество ранжирования в терминах функционала DCG. Также рассмотрен алгоритм пошагового отбора объектов и признаков. По качеству ранжирования на отобранных признаках он не уступает рассматривавшемуся в работе генетическому алгоритму.

Об авторах

Александр Александрович Адуенко

Московский физико-технический институт

Email: aduenko1@gmail.com
студент

Вадим Викторович Стрижов

Вычислительный центр РАН

Email: strijov@ccas.ru
к.ф.-м.н., доцент, научный сотрудник

Список литературы

Дополнительные файлы