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

Ранжирование (англ. learning to rank) — это класс задач машинного обучения с учителем, заключающихся в автоматическом подборе ранжирующей модели по обучающей выборке, состоящей из множества списков и заданных частичных порядков на элементах внутри каждого списка. Частичный порядок обычно задаётся путём указания оценки для каждого элемента (например, «релевантен» или «не релевантен»). Цель ранжирующей модели — наилучшим образом приблизить и обобщить способ ранжирования в обучающей выборке на новые данные.

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

[math]X[/math] — множество объектов.

[math]X^l = \{x_1, \ldots, x_l\}[/math] — обучающая выборка.

[math]i \prec j[/math] — правильный частичный порядок на парах [math](i, j) \in \{1, \ldots, l\}^2[/math]. "Правильность" зависит от постановки задачи, а именно запись [math]i \prec j[/math] может означать, что объект [math]i[/math] имеет ранг выше, чем объект [math]j[/math], так и наоборот.

Задача:

Построить ранжирующую функцию [math]a : X \to \mathbb{R}[/math] такую, что: [math] i \prec j \Rightarrow a(x_i) \lt a(x_j)[/math].

Линейная модель ранжирования:

[math]a(x; w) = \langle x, w \rangle[/math], где [math]x \mapsto (f_1(x), \ldots, f_n(x)) \in \mathbb{R}^n[/math] — вектор признаков объекта [math]x[/math].

Примеры приложения

Задача ранжирования поисковой выдачи

[math]D[/math] — коллекция текстовых документов.

[math]Q[/math] — множество запросов.

[math]D_q \subseteq D[/math] — множество документов, найденных по запросу [math]q[/math].

[math]X = Q \times D[/math] — объектами являются пары (запрос, документ): [math]x \equiv (q, d), q \in Q, d \in D_q[/math].

[math]Y[/math] — упорядоченное множество рейтингов.

[math]y: X \to Y[/math] — оценки релевантности, поставленные асессорами(экспертами): чем выше оценка [math]y(q, d)[/math], тем релевантнее документ [math]d[/math] по запросу [math]q[/math].

Правильный порядок определен только между документами, найденными по одному и тому же запросу [math]q[/math]: [math] (q, d) \prec (q, d') \Leftrightarrow y(q, d) \lt y(q, d')[/math].

Коллаборативная фильтрация

[math]U[/math] — пользователи.

[math]I[/math] — предметы (фильмы, книги и т.д.).

[math]X = U \times I[/math] — объектами являются пары (пользователь, предмет).

Правильный порядок определён между предметами, которые выбирал или рейтинговал один и тот же пользователь: [math](u, i) \prec (u, i') \Leftrightarrow y(u, i) \lt y(u, i')[/math].

Рекомендация пользователю [math]u[/math] — это список предметов [math]i[/math], упорядоченный с помощью функции ранжирования [math]a(u, i)[/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 = 10[/math] среди первых [math]k[/math] документов есть [math]5[/math] релевантных, то неважно, где они находятся: среди первых или последних [math]5[/math] документов. Обычно же хочется, чтобы релевантные документы располагались как можно выше.

Описанную проблему можно решить, модифицировав метрику, и определить среднюю точность (англ. average precision). Данная метрика тоже измеряется на уровне [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

Второй подход к измерению качества ранжирования — дисконтированный совокупный доход (англ. discounted cumulative gain) или DCG. Она используется в более сложной ситуации, когда оценки релевантности [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.

Пример вычисления DCG и nDCG:

Дано множество документов, где каждый документ оценивается от [math]3[/math] до [math]0[/math], где [math]3[/math] — очень релевантен, а [math]0[/math] — не релевантен. Пусть таким множеством будет [math]S = \{ D_1, D_2, D_3, D_4, D_5, D_6\}[/math], где оценка релевантности по опросу пользователей задается(в том же порядке) множеством [math]R = \{3, 2, 3, 0, 1, 2\}[/math].

Тогда [math]DCG@6 = \sum_{i = 1}^{6} {{rel_i} \over {log(i+1)}} = 3 + 1.262 + 1.5 + 0 + 0.387 + 0.712 = 6.861[/math]

i	[math]rel_i[/math]	[math]log(i+1)[/math]	[math]{rel_i}\over{log(i+1)}[/math]
[math]1[/math]	[math]3[/math]	[math]1[/math]	[math]3[/math]
[math]2[/math]	[math]2[/math]	[math]1.585[/math]	[math]1.262[/math]
[math]3[/math]	[math]3[/math]	[math]2[/math]	[math]1.5[/math]
[math]4[/math]	[math]0[/math]	[math]2.322[/math]	[math]0[/math]
[math]5[/math]	[math]1[/math]	[math]2.585[/math]	[math]0.387[/math]
[math]6[/math]	[math]2[/math]	[math]2.807[/math]	[math]0.712[/math]

Идеальный порядок оценок релевантности [math]Ideal = \{3, 3, 2, 2, 1, 0\}[/math]. DCG для данного множества будет следующим: [math]maxDCG@6 = \sum_{i = 1}^{6} {{rel_i} \over {log(i+1)}} = 3 + 1.893 + 1 + 0.861 + 0.387 + 0 = 7.141[/math].

i	[math]rel_i[/math]	[math]log(i+1)[/math]	[math]{rel_i}\over{log(i+1)}[/math]
[math]1[/math]	[math]3[/math]	[math]1[/math]	[math]3[/math]
[math]2[/math]	[math]3[/math]	[math]1.585[/math]	[math]1.893[/math]
[math]3[/math]	[math]2[/math]	[math]2[/math]	[math]1[/math]
[math]4[/math]	[math]2[/math]	[math]2.322[/math]	[math]0.861[/math]
[math]5[/math]	[math]1[/math]	[math]2.585[/math]	[math]0.387[/math]
[math]6[/math]	[math]0[/math]	[math]2.807[/math]	[math]0[/math]

Итого [math]nDCG@6 = {{DCG@6} \over {maxDCG@6}} = {{6.861} \over {7.141}} = 0.961[/math].

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

Всего выделяют три подхода к решению задачи ранжирования: поточечный (англ. 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. Курс лекций по машинному обучению — Воронцов К.В.