Ранжирование

Постановка задачи

[math]x_1 \ldots x_l[/math] – выборка, состоящая из [math]l[/math] элементов. Она состоит из объектов, имеющих признаковое описание, как и в задачах регрессии и классификации.

Ключевое отличие ранжирования заключается в целевой переменной. Если ранее в задачах обучения с учителем каждому объекту соответствовал свой ответ, то теперь ответы — это пары вида: [math]\{ (i, j) : x_i \lt x_j\} [/math]. Набор таких пар и есть целевая переменная.

Основная задача – построить ранжирующую модель [math]a(x)[/math], такую, что: [math]\{ x_i \lt x_j \Rightarrow a(x_i) \lt a(x_j) \}[/math]

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

Ранжирование поисковой выдачи

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

В качестве объектов выступают пары [math](запрос, документ)[/math]. Запрос – ключевые слова, введенные пользователем, документ – один из всех документов, имеющихся в поисковой выдаче: [math]({запрос}, {документ}_1) \lt ({запрос}, {документ}_2) [/math]

Метрики качества ранжирования

Точность ранжирования

В самой простой постановке задачи ранжирования целевая переменная принимает два значения, документ либо релевантен запросу, либо нет:

[math]y(q, d) \in \{0, 1\}, [/math] где [math]y[/math] – целевая переменная, [math]q[/math] – запрос, [math]d[/math] – документ.

Пусть также есть некоторая модель [math]a(q, d)[/math], оценивающая релевантность документа запросу. По значениям, полученным с помощью этой модели, можно отранжировать документы. [math]d^{(i)}_{q}[/math] будет обозначать [math]i[/math]-й по релевантности документ для запроса [math]q[/math].

После того как введены обозначения, можно задать простейшую метрику ранжирования. Это [math]Precision@k[/math], точность среди первых [math]k[/math] документов ([math]k[/math] — параметр метрики). Если ранжируется поисковая выдача, и на первой странице показываются 10 документов, то разумно выбирать [math]k = 10[/math]. Данная метрика определяется как доля релевантных документов среди первых [math]k[/math], полученных с помощью модели:

[math]Precision@k(q) = {{1}\over{k}} \sum_{i = 1}^{k} y(q, d_{q}^{(i)})[/math]

Это полезная метрика, потому что обычно важно иметь релевантные документы среди первых [math]k[/math]. Однако у неё есть серьёзный недостаток: позиции релевантных документов никак не учитываются. Например, если при [math]k = 10[/math] среди первых [math]k[/math] документов есть [math]5[/math] релевантных, то неважно, где они находятся: среди первых или последних [math]5[/math] документов. Обычно же хочется, чтобы релевантные документы располагались как можно выше.

Описанную проблему можно решить, модифицировав метрику, и определить среднюю точность (average precision, [math]AP[/math]). Данная метрика тоже измеряется на уровне [math]k[/math] и вычисляется следующим образом:

[math]AP@k(q) = {\large {{\sum_{i = 1}^{k} y(q, d_{q}^{(i)}) Precision@i(q)}\over{\sum_{i = 1}^{k} y(q, d_{q}^{(i)})}}}[/math]

Данная величина уже зависит от порядка. Она достигает максимума, если все релевантные документы находятся вверху ранжированного списка. Если они смещаются ниже, значение метрики уменьшается.

И точность, и средняя точность вычисляются для конкретного запроса [math]q[/math]. Если выборка большая и размечена для многих запросов, то значения метрик усредняются по всем запросам:

[math]MAP@k = {{1}\over{|Q|}} \sum_{q \in Q} AP@k(q)[/math]

DCG

Второй подход к измерению качества ранжирования — это метрика DCG (discounted cumulative gain). Она используется в более сложной ситуации, когда оценки релевантности [math]y[/math] могут быть вещественными:

[math]y(q, d) \in \mathbb{R}[/math]

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

Формула для вычисления DCG:

[math]DCG@k(q)= \sum_{i = 1}^{k} {\large {{2^{y(q, d_{q}^{(i)})} - 1} \over {log(i+1)}}}[/math]

Метрика — это сумма дробей. Чем более релевантен документ, тем больше числитель в дроби. Знаменатель зависит от позиции документа, он штрафует за то, где находится документ. Если документ очень релевантен, но занимает низкую позицию, то штраф будет большим, если документ релевантен и находится вверху списка, штраф будет маленьким. Таким образом, метрика DCG учитывает и релевантность, и позицию документа. Она достигает максимума, если все релевантные документы находятся в топе списка, причём отсортированные по значению [math]y[/math].

Данную метрику принято нормировать:

[math]nDCG@k(q) = {\large {DCG@k(q)} \over {{\large max DCG@k(q)}}}[/math]

где [math]max DCG@k(q)[/math] — значение DCG при идеальном ранжировании. После нормировки метрика принимает значения от 0 до 1.

Методы ранжирования

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

Поточечный подход

Самый простой подход — это поточечный. В нём игнорируется тот факт, что целевая переменная [math]y(q, d) \in \mathbb{R}[/math] задаётся на парах объектов, и оценка релевантности [math]a(d, q)[/math] оценивается непосредственно для каждого объекта.

Если речь идёт о задаче ранжирования, то пусть асессор поставил какую-то оценку [math]y[/math] каждой паре запрос, документ. Эта оценка и будет предсказываться. При этом никак не учитывается, что на самом деле нужно предсказать порядок объектов, а не оценки. Этот подход является простым в том смысле, что в нём используются уже известные методы. Например, можно предсказывать оценки с использованием линейной регрессии и квадратичной ошибки:

[math]\sum_{i = 1}^{l} (a(q_i, d_i) - y(q_i, d_i))^2 \rightarrow min[/math]

Известно, как решать такую задачу, и таким образом будет получена релевантность. Далее по выходам модели можно ранжировать объекты.

Попарный подход

В попарном подходе используются знания об устройстве целевой переменной. Модель строится минимизацией количества дефектных пар, то есть таких, в которых моделью был предсказан неправильный порядок:

[math]\sum_{x_i \lt x_j} [a(x_j) - a(x_i) \lt 0] \rightarrow min[/math]

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

Можно считать, что разница между объектами [math]a(x_j) − a(x_i)[/math] — это отступ [math]M[/math], и задать некоторую гладкую функцию [math]L(M)[/math]:

[math]\sum_{x_i \lt x_j} L(a(x_j) - a(x_i)) \rightarrow min[/math]

Если использовать функцию как в логистической регрессии [math]L(M) = log(1 + e^{−M})[/math], то полученный метод называется RankNet. Затем можно решать задачу, например, с помощью стохастического градиентного спуска.

Listwise-подход

В методе RankNet шаг стохастического градиентного спуска для линейной модели выглядит следующим образом:

[math]\omega := \omega + \eta {{\large 1} \over {\large 1 + exp(\langle \omega, x_j - x_i \rangle)}} (x_j - x_i)[/math]

Это не очень сложная формула, она зависит от одной пары объектов. Возникает вопрос, можно ли модифицировать данный метод (а именно формулу шага) так, чтобы минимизировался не исходный функционал, оценивающий долю дефектных пар, а DCG.

Ответ на этот вопрос положительный. Можно домножить градиент исходного функционала на то, насколько изменится nDCG, если поменять местами [math]x_i[/math] и [math]x_j[/math] :

[math]\omega := \omega + \eta {{\large 1} \over {\large 1 + exp(\langle \omega, x_j - x_i \rangle)}} (x_j - x_i) |\Delta nDCG_{ij}| (x_j - x_i)[/math]

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

Существуют и другие подходы к оптимизации nDCG, однако в них предпринимается попытка работы с функционалом, что гораздо сложнее. Выше описан самый простой подход, он называется LambdaRank.

Источники информации

1. Обучение ранжировнию — статья на machinelearning.ru
2. Курс лекций по машинному обучению — Воронцов К.В.