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

Ранжирование (англ. 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. Затем можно решать задачу, например, с помощью стохастического градиентного спуска.

Списочный подход

В методе 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]

Данный метод называется LambdaRank.

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

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

1. Обучение ранжировнию — статья на machinelearning.ru
2. From RankNet to LambdaRank — Christopher J.C. Burges From RankNet to LambdaRank to LambdaMART: An Overview
3. Курс лекций по машинному обучению — Воронцов К.В.