1. Обзор существующих алгоритмов машинного обучения для задачи ранжирования
В своей статье «Learning to Rank for Information Retrieval»[4] Тай-Ян Лю из Microsoft Research Asia провёл анализ по существующим на тот момент (2009 год) алгоритмам машинного обучения для задач ранжирования и привёл для них классификацию по их входным данным и функциям потерь из трёх типов: поточечный подход, попарный подход и посписочныйподход.
1.1. Поточечный подход
Поточечный подход в своей целевой функции рассматривает каждый элемент обучающей выборки отдельно, как это делается во многих других задачах машинного обучения. То есть алгоритмы поточечного подхода тренируют классификацию или регрессию для предсказывания по каждому отдельному элементу, насколько он релевантен для данного запроса. Далее список элементов сортируется по их полученным оценкам релевантности, и на выходе выдает ранжированные по запросу элементы.
Для поточечного подхода могут применяться любые алгоритмы машинного обучения для регрессии или классификации практически без модификаций. Неудивительно, что одними из первых алгоритмов обучения ранжированию являются поточечные методы. Например, алгоритм OPRF[5] появился ещё в 1989 году. В нём используется полиномиальная регрессия: каждая пара запрос-документ представляется в векторном виде, а полиномиальная функция подбирается так, что она даёт оценку вероятности релевантности запросу документа с минимальной квадратичной ошибкой. Следующий алгоритм SLR[6], представленный в 1992 году, уже использует многоэтапную логистическую регрессию – каждый раз уменьшая выборку элементов по установленному порогу. Более современным поточечным алгоритмом (2007 год) является McRank[7], являющийся улучшением другого попарного метода – LambdaRank (описан в главе 1.3.2). Основан
алгоритм на множественной порядковой классификации, которая обучается при помощи дерева градиентного бустинга.
Несмотря на разнообразие и относительную легкость алгоритмов, которые можно применить в поточечном методе, его недостаток состоит в том, что каждый элемент рассматривается независимо от других элементов, входящих в окончательный список. И следующий метод – попарный – пытается решить данное упущение, сравнивая сразу пару элементов.
1.2. Попарный подход
В попарном подходе в целевой функции сразу рассматривается пара элементов, которую нужно разместить в оптимальном порядке, соответствующим их релевантности запросу. Задача обучения ранжированию тут состоит в том, чтобы уменьшить количество инверсий в таких парах, то есть уменьшить количество выходных пар, которые не соответствуют действительному порядку.
Существует огромное количество алгоритмов попарного метода ранжирования. Большинство из них основаны на попарной классификации или регрессии. Например, есть целая группа алгоритмов попарного подхода – RankNet (2005), LambdaRank (2006) и LambdaMART (2008) [2] [3], которые были разработаны Крисом Бёрджесом и его коллегами из Microsoft Research. Исходный RankNet использовал в своей основе нейронную сеть, обучаемую стохастическим градиентным спуском, однако позже команда разработчиков заметила, что градиент не просто помогает правильно модель обучить, так же он может указывать, в каком направлении нужно сдвигать документ в списке, к тому же, в этот раз они использовали другую метрику – nDCG (normalized discounted cumulative gain). LambdaMART является уже гибридом LambdaRank и MART, Multiple Additive Regression Tree. От первого алгоритма осталась функция потерь, от второго – способ решения поставленной задачи, то есть деревья градиентного бустинга, что увеличило скорость и точность в сравнении сLambdaRank.
Также в попарном подходе обучения ранжированию представлены алгоритмы, в основе своей использующие метод опорных векторов – RankSVM и IR-SVM[8]. Второй алгоритм является улучшением первого за счёт изменения функции потерь линейного SVM, чтобы в ней также учитывались такие факторы, как требования к высокой точности ранжирования для самых верхних документов в поисковой выдаче и возможность малого количества релевантных документов на запрос.
Попарный подход работает лучше, чем поточечный за счёт того, что упорядочивание документов ближе к истинной природе ранжирования, то есть определения порядка релевантных документов, чем предсказывание независимой от других элементов оценки конкретного элемента выборки. Однако всё так же имеется ограничение, которое заключается в рассмотрении одновременно только двух элемента, поэтому результат во многом может зависеть от разбиения на пары. Следующий подход – посписочный – уже рассматривает все элементы в группе.
1.3. Посписочные методы
Посписочный подход уже рассматривает целую группу элементов и пытается предсказать релевантный порядок расположения элемента в этой группе, согласно запросу. Для решения такой задачи есть два типа методов:
1. Оптимизация метрик поиска информаций, как, например, DCG (discounted cumulative gain). Такой метод используется в SoftRank[9] и AdaRank[10].
2. Минимизация специфичнойдля конкретной задачи целевой функции, основанной на понимании особенных свойств ранжирования в данной ситуации. Например, в ListNet[11] и вListMLE[12].
2. Теоретические основы алгоритмов ранжированиятекстов
2.1. Предобработка входныхданных
Перед тем, как приступить к обучению ранжированию, стоит определиться с форматом и обработкой входных данных. Ни один из выбранных алгоритмов машинного обучения – ни нейронная сеть в виде многослойного персептрона, ни метод опорных векторов – не способны принимать в качестве входных данных обычный текст, для них нужно некое числовое представление данных. Так как задача эта распространённая, то для векторизации текста можно воспользоваться уже существующей моделью word embedding. В данной работе была выбрана разработанная в 2013 году в компании Google Томасом Миколовым модель Word2Vec[13], которая, обрабатывая корпус текстов и основываясь на статистике совместного появления разных слов, представляет вектора в виде слов.
К тому же, ещё в оригинальной статье отмечаются интересные свойства составленных нейронной сетью векторов слов: в векторах отражаются семантические связи слов, которые можно продемонстрировать с помощью линейных преобразований. К примеру, если к вектору слова
«King» прибавить «Woman» и вычесть «Man», то в результате будет вектор, близкий к слову «Queen» [13].
Для обучения модели Word2Vec используются два разных подхода: Continuous Bag of Words (CBOW, «мешок слов») и Skip-gram. У каждого подхода есть свои особенности, например, если описать кратко, то в CBOW обучение основывается на предсказывании окружающего контекста по слову, Skip-gram же работает наоборот – предсказывает слово по контексту (модели их обучения отражены на рисунке 1).
Рисунок 1 – Архитектура CBOW и Skip-gram
Однако встаёт вопрос, какой из этих алгоритмов справляется лучше со своей задачей? Во второй оригинальной статье [14] приводится следующая таблица сравнения (таблица 1):
Таблица 1 – Сравнение разных моделей на одинаковых выборках
Model Architecture Semantic-Syntatic Word Relationship
test set MSR Word Relatedness Test Set
Semantic
Accuracy [%] Syntatic Accuracy
[%]
RNNLM 9 36 35
NNLM 23 53 47
CBOW 24 64 61
Skip-gram 55 59 56
Алгоритмы, предложенные в статье, сравнивались по двум факторам: точность семантических отношений и точность грамматический (синтетических) отношений. В приведённой таблице 1 точность по первому показателю лучше у подхода Skip-gram, а синтетическая точность выше у
«мешка слов». В данной работе стояла задача скорее оценить семантическую близость документов к запросам, поэтому для обучения была выбрана модель Skip-gram.
Теперь более подробно про обучение Skip-gram модели, главная задача которой найти такое векторное представление слова, по которому можно максимально точно предсказать окружающий контекст. На вход поступает последовательность слов , тогда задача состоит в максимизации функции вида:
1)
где – размер обучающей выборки.
Как определить условную вероятность в данном случае? Для этого в «классическом» алгоритме используется обычная функцияsoftmax:
? 2)
Но она вычислительно сложная, что будет влиять на время обучения, поэтому в обучении используется более вычислительно эффективная аппроксимация softmax’а – иерархический softmax (рисунок 2):
Рисунок 2 – Иерархический Softmax
Теперь для получения вычисления вероятности вместо W выходных узлов нейронной сети модели Word2Vec оценивается только log2(W) узлов [14], и это даёт большое преимущество. В иерархическом softmax’е для этой
цели строится дерево Хаффмана, где каждый лист – это слово (см. рисунок 2).
Тогда вычисление вероятности сводится к формуле:
([ ( )]
)3)
где , ch – левый дочерний узел, а L(w) – длина пути до слова. То есть искомая вероятность – это произведение всех
шагов с вероятностью пойти по левому ребру равной ( ) и по
правому – ( ).
Итак, для преобработки текста для задач обучения ранжированию в данной работе в качестве модели для получения векторов слов, учитывая все перечисленные преимущество, можно использовать Skip-gram модель Word2Vec с иерархическим Softmax.
2.2. Нейронные сети
В попарном подходе задача заключается в определении ранга относительно друг друга двух элементов выборки. Сводится эта задача или к регрессии, или к бинарной классификации, и с обоими типами задач прекрасно справляются нейронные сети. В данной работе задача ранжирования сводилась к задаче бинарной классификации, где класс (или 0, или 1) означал отсутствие или наличие инверсии. Инверсия в рамках попарного подхода обучения ранжированию – это неправильный порядок расположения в паре, то есть если на первом месте стоит элемент наименее релевантный запросу, то это свидетельствует о наличии инверсии.
В данной работе в качестве нейронной сети использовался многослойный персептрон для бинарной классификации с двумя выходами. На вход персептрон подавались три элемента – запрос + первый текст + второй текст.
Многослойный персептрон – модель искусственной нейронной сети прямого распространения. Существует три различных типа нейронов в персептроне: узлы входного слоя (сенсорные), узлы скрытых слоев (ассоциативные) и узлы выходного слоя (реагирующие). Многослойный персептрон можно представить в виде направленного ацикличного взвешенного графа, где каждый узел связан с узлами последующего слоя ребрами с установленными весами, при этом узлы одного слоя не связаны между собой (рисунок 3).
Рисунок 3 – Схема многослойного персептрона
Количество нейронов во входном слое устанавливаются количеством компонент в векторе входных данных, а количество выходных узлов зависят от условий поставленной задачи. Оптимальное количество скрытых слоев и количества их нейронов решаются в ходе экспериментов с моделью, однако обычно в качестве начального приближения можно взять один промежуточный слой, а число элементов в нем положить равным полусумме числа входных и выходных элементов [15].
На вход нейрона каждого слоя поступает вектор по ребрам с весами . Нейрон после получения вектора (сигнала) суммирует все входные значения, умножая на соответствующие веса, и прибавляет смещение. Полученное значение передают в качестве параметра некой функции и результат уже передаётся дальше по рёбрам (рисунок 4). Такая функция называется функцией активации.
Рисунок 4 – Схема искусственного нейрона
Чаще всего в качестве функции активации берётся гладкая (т.е. всюду дифференцируемая) и монотонно возрастающая функция, есть разные типы функций, выбирают их в зависимости от задачи:
1. В некоторых задачах используется линейная функция, то есть совершается линейной преобразования над комбинацией входа нейрона. Есть, например, линейные функции с насыщением (шаговая). Примером такой функции является:
{4)
2. Существуют также пороговая функция активации, также известная, как функция Хевисайда. В этом случае пока комбинация входных сигналов не будет больше определенного порога T, выходной равняется нулю, в обратном случае – единице.
{
3. Одной из популярных функций активаций является ReLU («выпрямитель») – пороговый переход внуле.
6)
4. Есть целый класс сигмоидальных функций активации – гладкие монотонно возрастающие функции, графики которых имеют вид буквы «S» (рисунок 5).
Рисунок 5 – Семейство сигмоидальных функций
В это семейство функций активаций входят, например, логистическая функция (7) и гиперболический тангенс (8).
7)
8)
Однако более популярна логистическая функция, так как одним из её преимуществ является простота её производной.
9)
Также одним из преимуществ является её способность лучше усиливать слабые сигналы, но при этом не допускать перенасыщение от сильных сигналов [16] (рисунок 6).
Рисунок 6 – График логистической функции
Для обучения многослойного персептрона используются разные алгоритмы обучения. Одним из самых распространённых является алгоритм обратного распространения ошибки, где для минимизации целевой функции
используютсяразличныеметодыоптимизации,например,градиентный
спуск. Назван этот алгоритм в связи с тем, что после прямого прогона по модели нейронной сети её выходные значения сравниваются с тем, что нужно получить, вычисляется ошибка (некая разница), а далее эта ошибка используется в вычислении ошибок на предыдущихслоях.
Целевая функция (функция ошибки) зависит от поставленной задачи. Однако для задачи классификации такой функцией является квадратичная функция ошибок:
10)
где – выходы нейронной сети с матрицей весов W, а – правильный вектор классов, соответствующие входным данным
.
Тогда вычисляется её градиент по весам для минимизации этой функции, то есть вычисляется частная производная функции ошибки по весам, используется при этом правила дифференцирования сложной функции. Производная целевой функции по весам последнего слоя:
· 11)
где ? – линейнаякомбинация входов,–
значение функции активации нейронов. Тогда:
·
· 12)
13)
14)
Длявычисленияградиентафункцииошибкидлявесовкаждого скрытого слоя используется ошибка следующего слоя (рисунок 7). Для этого
обозначим ошибку одного нейрона выходного слоя .
Рисунок 7 – Обратное распространение ошибки
Таким образом, ошибка k-ого нейрона скрытого слоя зависит от ошибок всех нейронов последующего слоя с весами .
Тогда:
15)
Теперь можно вычислить новые веса по полученному градиенту по формуле:
,
16)
Однако существуют и другие алгоритмы оптимизации целевой функции для обучения нейронной сети, один из них – итерационный метод, относящий к классу квазиньютоновских методов, BFGS, названный так в честь своих создателей Бройдена, Флетчера, Гольдфарба и Шанно. Его, например, используют при обучении рекурентных нейронных сетей [17] и просто для оптимизации работы нейронных сетей [18][19].
