Подробное объяснение принципа LTR-сортировки алгоритма LambdaRank

Алгоритм сортировки

1. Введение

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

Традиционный метод сортировки, основанный на комбинации стратегий вручную, может сыграть свою роль, когда объем данных невелик. Этот подход становится все более сложным по мере увеличения объема интернет-данных. Поэтому более естественным решением является разработка алгоритма ранжирования в поисковых системах, основанного на машинном обучении. Этот алгоритм часто называют Learning to Rank (LTR).

В алгоритме LTR LambdaMART[1]Это наиболее часто используемый алгоритм Listwise, который используется в основных поисковых системах. Из его названия можно понять, что он состоит из лямбда и MART, где MART (дерево множественной аддитивной регрессии) представляет базовую модель обучения, а лямбда представляет градиент, используемый в процессе решения MART.

Почему LambdaMART хорошо подходит для сценариев сортировки? Это в основном выигрывает от использования лямбда-градиентов. Но изначально Lambda была предложена в модели LambdaRank, а модель LambdaRank была усовершенствована на основе модели RankNet.

Далее мы узнаем больше об алгоритме LambdaMART от MART и Lambda.

2. Алгоритм МАРТ

Говоря о MART (дерево множественной аддитивной регрессии), вы можете быть относительно незнакомы. Но когда дело доходит до GBDG (Gradient Boosting Decision Tree), многие люди знакомы с ним. Да, MART — это, по сути, градиентное дерево решений GBDT. Итак, мы можем легко узнать некоторые характеристики MART:

  • Прогнозировать результаты на основе нескольких деревьев решений;
  • Результаты накладываются между деревьями решений с помощью аддитивной модели;
  • Каждое дерево решений является улучшением недостатков предыдущего дерева решений.

По сути, MART — это фреймворк алгоритма, основанный на идее Boosting. Он улучшает возможности новой модели за счет непрерывного повторения слабой модели и, наконец, получает суперпозицию всех моделей, которая служит достаточно сильной моделью, чтобы предсказать истинное значение. Подробнее об алгоритме MART см. в [8], который здесь подробно описываться не будет.

Итак, как в LambdaMART определяется функция потерь MART? Здесь мы должны понять историю эволюции Lambda.

3.Lambda

Lambda впервые появился на основе алгоритма LambdaRank, а алгоритм LambdaRank был улучшен на основе алгоритма RankNet. Чтобы лучше понять алгоритм сортировки, давайте сначала разберемся с алгоритмом RankNet.

2.1RankNet

Мы знаем, что при сортировке обычно используемые оценочные показатели NDCG, MAP и ERR являются невыводимыми, то есть невозможно получить градиент, что приводит к невозможности использования алгоритма градиентного спуска для решения задачи сортировки. RankNet[2]Гениальным способом задача сортировки, которая не может быть решена с помощью градиентного спуска, оптимизируется как функция кросс-энтропийных потерь от вероятности, которая затем может быть решена с помощью алгоритма градиентного спуска.

Давайте посмотрим, как RankNet оптимизирует проблему ранжирования. Цель обучения RankNet — получить модельss, вход - это документxx, результатом является оценка для этого документа:s=f(x;W)s = f(x;W)вWWмодель представленияssнабор параметров.

есть модельssПосле этого для документацииxix_{i}иxjx_{j}, мы можем получить счет соответственноsis_{i}иsjs_{j}:si=f(xi;W),sj=f(xj;W)s_{i} = f(x_{i};W),s_{j} = f(x_{j};W)

Отличительной чертой RankNet является то, что он связывает баллы между документами с порядком документов через отношение частичного порядка, а затем вычисляет вероятность. В частности, помнитеPijP_{ij}Представляет документxix_{i}Рейтингxjx_{j}Тогда предыдущая вероятность:

Pij=P(xi⊳xj)=exp⁡(о⋅(si−sj))1+exp⁡(о⋅(si−sj))=11+exp⁡(−о⋅(si−sj))P_{ij} = P(x_i \rhd x_j) = \frac{\exp\bigl(\sigma\cdot(s_i - s_j)\bigr)}{1 + \exp\bigl(\sigma\cdot(s_i - s_j)\bigr)} = \frac{1}{1 + \exp\bigl(-\sigma\cdot(s_i - s_j)\bigr)}

Как видите, RankNet использует сигмовидную функцию для преобразования вероятности ранжирования, что по сути является логистической регрессией! здесьо\sigmaОн влияет на форму сигмовидной функции, что мало влияет на конечный результат, для упрощения описания он будет использован позже.о\sigma=1.

В практических приложениях документxix_{i}Рейтингxjx_{j}Мы знаем реальную вероятность заранее, которая записана здесь какPˉij\bar{P}_{ij}. Мы согласны, что еслиxix_{i}Рейтингxjx_{j}доPˉij\bar{P}_{ij}1, иначе 0.

Тогда по модельной вероятностиPijP_{ij}и истинная вероятностьPˉij\bar{P}_{ij}, используя кросс-энтропию для измерения того, насколько хорошо модель сортирует документы.xix_{i}иxjx_{j}Полученная функция потерь:

Lij=−Pˉijlog⁡Pij−(1−Pˉij)log⁡(1−Pij)=12(1−Sij)⋅(si−sj)+log⁡{1+exp⁡(−(si−sj))}\begin{aligned} L_{ij} & {}= -\bar{P}_{ij}\log P_{ij} - (1 - \bar{P}_{ij})\log (1 - P_{ij})\\ & {}= \frac12 (1 - S_{ij})\cdot(s_i - s_j) + \log\Bigl\{1 + \exp\bigl(-(s_i - s_j)\bigr)\Bigr\} \end{aligned}

В приведенной выше формуле мы использовали обозначениеSijS_{ij}, который представляет документxix_{i}иxjx_{j}Истинное отношение порядка:

Sij={1,xiСравниватьxjболее актуальный0,xiСравниватьxjтакая же корреляция−1,xjСравниватьxiболее актуальныйS_{ij}=\left\{ \begin{aligned} 1 &, x_{i} более коррелирован, чем x_{j}\\ 0 &, x_{i} так же коррелирован, как x_{j}\\ -1 & , x_{j} более релевантен, чем x_{i}\end{aligned} \right.

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

L=∑(i,j)еDLijL = \sum_{(i, j) \in D}L_{ij}

здесь,DDПредставляет коллекцию всех пар документов в запросе.

Целью обучения RankNet является решение моделиssпараметрыWW, которое можно решить градиентным спуском:wk→wk−н∂L∂wkw_k \to w_k - \eta\frac{\partial L}{\partial w_k}

2.2LambdaRank

RankNet избегает прямой оптимизации показателей оценки в рейтинге и решает связанную с этим проблему порядка в рейтинге абстрактно с помощью вероятностной модели. Однако при практическом применении возникают некоторые проблемы, так как оптимизация оценочных показателей не проводится.

как показано на рисунке[4], каждая строка представляет собой документ, синий цвет представляет связанные документы, а серый цвет представляет собой нерелевантные документы, и документы на переднем плане будут отображаться для пользователя в первую очередь. Поскольку RankNet заботится только о порядке между двумя документами и игнорирует конкретную информацию о порядке документов, сталкиваясь с ситуацией слева, предполагая, что значение потери равно 13 в это время, RankNet уменьшает связанные документы в первую очередь на 3 позиции, а предпоследний связанный документ перемещается вверх на 5 позиций, уменьшая значение потерь до 11. Тем не менее, пользователи обычно уделяют больше внимания порядку первых k результатов, и пользователям не нравится понижать связанные документы в верхних результатах в процессе оптимизации.

Черная стрелка в левой части правого изображения на рисунке 1 указывает направление упорядочения и силу RankNet в следующем раунде, но что действительно нужно пользователям, так это направление и сила, представленные красной стрелкой справа, то есть улучшение позиции в рейтинге связанных документов, которые больше озабочены передним положением.

Таким образом, оценочный индекс NDCG в рейтинге может лучше отражать потенциальную потребность пользователя в релевантности. Возникает вопрос: можно ли определить градиент по индикатору NDCG?

LambdaRank[3]На этой идее основано то, что Lambda относится к красной стрелке, которая представляет направление и силу следующей итерационной оптимизации, то есть градиента.

Давайте посмотрим, как LambdaRank определяет градиент с помощью метрики NDCG. Во-первых, для градиента RankNet у нас есть следующий вывод:

∂L∂wk=∑(i,j)еP∂Lij∂wk=∑(i,j)еP∂Lij∂si∂si∂wk+∂Lij∂sj∂sj∂wk,\frac{\partial L}{\partial w_k} = \sum_{(i, j) \in P}\frac{\partial L_{ij}}{\partial w_k} = \sum_{(i, j) \in P} \frac{\partial L_{ij}}{\partial s_i}\frac{\partial s_i}{\partial w_k} + \frac{\partial L_{ij}}{\partial s_j}\frac{\partial s_j}{\partial w_k},

Далее можно заметить, что модельssВывод имеет следующую симметрию:

∂Lij∂si=∂{12(1−Sij)(si−sj)+log⁡{1+exp⁡(−(si−sj))}}∂si=12(1−Sij)−11+exp⁡(si−sj)=[12(1−Sij)−11+exp⁡(si−sj)]=−∂Lij∂sj.\begin{aligned} \frac{\partial L_{ij}}{\partial s_i} & {} = \frac{\partial \biggl\{\frac12 (1 - S_{ij})(s_i - s_j) + \log\Bigl\{1 + \exp\bigl(-(s_i - s_j)\bigr)\Bigr\}\biggr\}}{\partial s_i}\\ & {}= \frac12 (1 - S_{ij}) - \frac{1}{1 + \exp\bigl(s_i - s_j\bigr)} \\ & {}= \Biggl[\frac12(1 - S_{ij}) - \frac{1}{1 + \exp\bigl(s_i - s_j\bigr)}\Biggr] \\ & {}= -\frac{\partial L_{ij}}{\partial s_j}. \end{aligned}

Поэтому LambdaRank имеет следующую документацию поxix_iиxjx_jОпределение лямбда:

λij=∂Lij∂si=−∂Lij∂sj,\lambda_{ij}= \frac{\partial L_{ij}}{\partial s_i} = -\frac{\partial L_{ij}}{\partial s_j},

Сначала рассмотрим упорядоченные пары(i,j)(i, j), так что естьSij=1S_{ij} = 1, поэтому приведенную выше формулу можно еще упростить:

λij=−11+exp⁡(si−sj)\lambda_{ij}= - \frac{1}{1 + \exp\bigl(s_i - s_j\bigr)}

Пока вы можете получить любой документxix_iЗначение лямбда:

λi=∑(i,j)еIλij−∑(j,i)еIλij\lambda_{i} = \sum_{(i, j) \in I}\lambda_{ij} - \sum_{(j, i) \in I}\lambda_{ij}

формулаIIпара документов (xix_i,xjx_j), где документыxix_iРейтингxjx_jспереди, т.е. более актуально.

Чтобы усилить важность порядка до и после сортировки, LambdaRank дополнительно вводит индекс оценки Z (например, NDCG) в Lambda и изменяет индекс оценки, вызванный обменом позициями двух документов.∣ΔZij∣\lvert\Delta Z_{ij}\rvertкак один из факторов:

λij=−11+exp⁡(si−sj)⋅∣ΔZij∣\lambda_{ij} = - \frac{1}{1 + \exp\bigl(s_i - s_j\bigr)} \cdot \lvert\Delta Z_{ij}\rvert

Лямбда может быть понята таким образом, Лямбда количественно определяет направление и силу, с которой сортируемый документ должен быть скорректирован на следующей итерации.

Можно видеть, что LambdaRank не решает проблему ранжирования, явно определяя функцию потерь и затем находя градиент, но анализирует физический смысл градиента, требуемого задачей ранжирования, и непосредственно определяет градиент.Функция потерь LambdaRank может выводится в обратном порядке:Lij=log⁡{1+exp⁡(si−sj)}⋅∣ΔZij∣L_{ij} = \log\Bigl\{1 + \exp\bigl(s_i - s_j\bigr)\Bigr\}\cdot\lvert\Delta Z_{ij}\rvert

2.3LambdaMART

После понимания определений Lambda и MART понять LambdaMART несложно. Результат модели LambdaMART состоит из множества деревьев решений с помощью идеи повышения, Подходящей целью каждого дерева является градиент функции потерь, и градиент здесь рассчитывается методом лямбда.

Ниже приведены конкретные шаги алгоритма Lambda.[5]:

Параметры алгоритма: количество деревьев решений M, количество листовых узлов L и скорость обучения.н\eta.

  1. Изначально модель дерева решений отсутствует, поэтому каждый документ имеет оценку модели 0.
  2. Для обучения каждого дерева алгоритм будет проходить пары документов с разными метками в наборе обучающих данных и находить изменения индекса, вызванные обменом позициями пар документов с разными метками.∣ΔZij∣\lvert\Delta Z_{ij}\rvertа такжеλij\lambda_{ij}, а затем получить значение Lambda каждого документаλi\lambda_{i}.
  3. рассчитать каждыйλi\lambda_{i}производная отwiw_{i}, который используется для определения значения конечного узла на следующем шаге Ньютона.
  4. со всеми документамиλ\lambdaОбучите дерево решений как метку, обратите внимание здесьλ\lambdaявляется подходящей целью дерева решений. Ключом к построению дерева решений является то, как определить разделяемый узел. LambdaMART использует самый наивный метод наименьших квадратов, который заключается в минимизации суммы квадратов ошибок для разделения узлов: то есть для выбранного признака выберите значение val, все образцы val к правому дочернему узлу. Затем вычислите сумму квадратов ошибок лямбда для левого и правого узлов соответственно и сложите их вместе как стоимость этого разделения, а затем выберите наименьшую стоимость (feature, val) в качестве текущей точки разделения и, наконец, сгенерируйте листовой узел с номером L дерева решений.
  5. Для сгенерированного выше дерева решений шаг Ньютона используется для вычисления значения каждого конечного узла, то есть выходное значение конечного узла вычисляется для набора документов, попадающих в листовой узел.
  6. Обновите модель, добавьте текущее изученное дерево решений в существующую модель и используйте скорость обучения v для регуляризации.

3. Резюме

LambdaMART — это алгоритм LTR типа Listwise, который основан на идее Lambda и алгоритме MART и преобразует проблему ранжирования результатов поисковой системы в проблему дерева решений регрессии. LambdaMART имеет множество преимуществ, некоторые из них перечислены ниже.[7]:

  • Решайте проблему сортировки напрямую, вместо использования методов классификации или регрессии;
  • Он может преобразовывать невыводимые индикаторы оценки, такие как NDCG, в производную функцию потерь, которая имеет четкий физический смысл;
  • Продолжить обучение можно на базе существующих моделей;
  • На каждой итерации для градиентного спуска выбирается признак с наибольшим усилением, поэтому можно изучить комбинацию различных признаков и отразить важность признака (выбор признака);
  • Нечувствительны к количественному соотношению положительных и отрицательных примеров.

использованная литература

Категории