Ранжирование — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 7: Строка 7:
 
<tex>X^l = \{x_1, \ldots, x_l\}</tex> {{---}} обучающая выборка.
 
<tex>X^l = \{x_1, \ldots, x_l\}</tex> {{---}} обучающая выборка.
  
<tex>i \prec j</tex> {{---}} правильный частичный порядок на парах <tex>(i, j) \in \{1, \ldots, l\}^2</tex>. "Правильность" зависит от постановки задачи, а именно запись <tex>i \prec j</tex> может означать, что объект <tex>i</tex> имеет ранг выше, чем объект <tex>j</tex>, так и наоборот.  
+
<tex>i \prec j</tex> {{---}} правильный [[Отношение порядка|частичный порядок]] на парах <tex>(i, j) \in \{1, \ldots, l\}^2</tex>. "Правильность" зависит от постановки задачи, а именно запись <tex>i \prec j</tex> может означать, что объект <tex>i</tex> имеет ранг выше, чем объект <tex>j</tex>, так и наоборот.  
  
 
'''Задача:'''
 
'''Задача:'''
Строка 17: Строка 17:
 
<tex>a(x; w) = \langle x, w \rangle</tex>, где <tex>x \mapsto (f_1(x), \ldots, f_n(x)) \in \mathbb{R}^n</tex> {{---}} вектор признаков объекта <tex>x</tex>.
 
<tex>a(x; w) = \langle x, w \rangle</tex>, где <tex>x \mapsto (f_1(x), \ldots, f_n(x)) \in \mathbb{R}^n</tex> {{---}} вектор признаков объекта <tex>x</tex>.
  
==Примеры приложения==
+
==Примеры==
 
===Задача ранжирования поисковой выдачи===
 
===Задача ранжирования поисковой выдачи===
 
<tex>D</tex> {{---}} коллекция текстовых документов.
 
<tex>D</tex> {{---}} коллекция текстовых документов.
Строка 29: Строка 29:
 
<tex>Y</tex> {{---}} упорядоченное множество рейтингов.
 
<tex>Y</tex> {{---}} упорядоченное множество рейтингов.
  
<tex>y: X \to Y</tex> {{---}} оценки релевантности, поставленные асессорами(экспертами): чем выше оценка <tex>y(q, d)</tex>, тем релевантнее документ <tex>d</tex> по запросу <tex>q</tex>.
+
<tex>y: X \to Y</tex> {{---}} оценки релевантности, поставленные асессорами (экспертами): чем выше оценка <tex>y(q, d)</tex>, тем релевантнее документ <tex>d</tex> по запросу <tex>q</tex>.
  
 
''Правильный порядок'' определен только между документами, найденными по одному и тому же запросу <tex>q</tex>: <tex> (q, d) \prec (q, d') \Leftrightarrow y(q, d) < y(q, d')</tex>.
 
''Правильный порядок'' определен только между документами, найденными по одному и тому же запросу <tex>q</tex>: <tex> (q, d) \prec (q, d') \Leftrightarrow y(q, d) < y(q, d')</tex>.
 +
 +
Релевантные ответы запросу <tex>q</tex> {{---}} это список документов <tex>d</tex>, упорядоченных с помощью функции ранжирования <tex>a(q, d)</tex>.
  
 
===Коллаборативная фильтрация===
 
===Коллаборативная фильтрация===
Строка 54: Строка 56:
 
релевантности документ для запроса <tex>q</tex>.
 
релевантности документ для запроса <tex>q</tex>.
  
После того как введены обозначения, можно задать простейшую метрику ранжирования. Это <tex>Precision@k</tex>,
+
После того как введены обозначения можно задать простейшую метрику ранжирования. Это <tex>Precision@k</tex>,
 
точность среди первых <tex>k</tex> документов (<tex>k</tex> — параметр метрики). Если ранжируется поисковая выдача, и на
 
точность среди первых <tex>k</tex> документов (<tex>k</tex> — параметр метрики). Если ранжируется поисковая выдача, и на
 
первой странице показываются 10 документов, то разумно выбирать <tex>k = 10</tex>. Данная метрика определяется
 
первой странице показываются 10 документов, то разумно выбирать <tex>k = 10</tex>. Данная метрика определяется
Строка 77: Строка 79:
 
<tex>MAP@k = {{1}\over{|Q|}} \sum_{q \in Q} AP@k(q)</tex>.
 
<tex>MAP@k = {{1}\over{|Q|}} \sum_{q \in Q} AP@k(q)</tex>.
  
===DCG===
+
===Дисконтированный совокупный доход===
 
Второй подход к измерению качества ранжирования — дисконтированный совокупный доход (англ. discounted cumulative gain) или DCG. Он
 
Второй подход к измерению качества ранжирования — дисконтированный совокупный доход (англ. discounted cumulative gain) или DCG. Он
 
используется в более сложной ситуации, когда оценки релевантности <tex>y</tex> могут быть вещественными: <tex>y(q, d) \in \mathbb{R}</tex>.
 
используется в более сложной ситуации, когда оценки релевантности <tex>y</tex> могут быть вещественными: <tex>y(q, d) \in \mathbb{R}</tex>.
Строка 144: Строка 146:
 
==Методы ранжирования==
 
==Методы ранжирования==
  
Всего выделяют три подхода к решению задачи ранжирования: поточечный (англ. pointwise), попарный (англ. pairwise), списочный (англ. listwise).  
+
Всего выделяют три подхода к решению задачи ранжирования: поточечный (англ. pointwise), попарный (англ. pairwise), списочный (англ. listwise). Выбор метода зависит от качества ранжирования на данных. Теоретически, списочный подход считается наилучшим, однако, например в Яндексе, лучше всего работает попарный подход.
  
 
===Поточечный подход===
 
===Поточечный подход===
Строка 173: Строка 175:
 
<tex>\sum_{x_i < x_j} L(a(x_j) - a(x_i)) \rightarrow min</tex>
 
<tex>\sum_{x_i < x_j} L(a(x_j) - a(x_i)) \rightarrow min</tex>
  
Если использовать функцию как в логистической регрессии <tex>L(M) = log(1 + e^{−M})</tex>, то полученный метод называется RankNet. Затем можно решать задачу, например, с помощью стохастического градиентного спуска.
+
Если использовать функцию как в логистической регрессии <tex>L(M) = log(1 + e^{−M})</tex>, то полученный метод называется RankNet. Затем можно решать задачу, например, с помощью [[Стохастический градиентный спуск|стохастического градиентного спуска]].
  
 
===Списочный подход===
 
===Списочный подход===
Строка 188: Строка 190:
 
<tex>\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)</tex>
 
<tex>\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)</tex>
  
Данный метод называется LambdaRank.  
+
Данный метод называется LambdaRank<ref>[https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/MSR-TR-2010-82.pdf From RankNet to LambdaRank {{---}} Christopher J.C. Burges]</ref>.  
  
 
Оказывается, что при выполнении градиентного спуска с помощью данных шагов оптимизируется nDCG. Существуют и другие подходы к оптимизации nDCG, однако в них предпринимается попытка работы с
 
Оказывается, что при выполнении градиентного спуска с помощью данных шагов оптимизируется nDCG. Существуют и другие подходы к оптимизации nDCG, однако в них предпринимается попытка работы с
 
функционалом, что гораздо сложнее.  
 
функционалом, что гораздо сложнее.  
 +
 +
== См. также ==
 +
* [[Общие понятия|Общие понятия]]
 +
* [[Стохастический градиентный спуск|Стохастический градиентный спуск]]
 +
* [[Рекомендательные системы|Рекомендательные системы]]<sup>[на 17.03.19 не создан]</sup>
 +
 +
== Примечания ==
 +
<references/>
  
 
== Источники информации ==
 
== Источники информации ==
 
# [http://www.machinelearning.ru/wiki/images/8/89/Voron-ML-Ranking-slides.pdf?title=Rank Обучение ранжировнию] {{---}} статья на machinelearning.ru
 
# [http://www.machinelearning.ru/wiki/images/8/89/Voron-ML-Ranking-slides.pdf?title=Rank Обучение ранжировнию] {{---}} статья на machinelearning.ru
# [http://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/MSR-TR-2010-82.pdf From RankNet to LambdaRank] {{---}} Christopher J.C. Burges From RankNet to LambdaRank to LambdaMART: An Overview
+
# [https://www.coursera.org/lecture/text-retrieval/lesson-6-1-learning-to-rank-part-1-mFYTD Learning to rank] {{---}} презентация на coursera.org
 
# [http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%BD%D0%BE%D0%B5_%D0%BE%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_(%D0%BA%D1%83%D1%80%D1%81_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B9%2C_%D0%9A.%D0%92.%D0%92%D0%BE%D1%80%D0%BE%D0%BD%D1%86%D0%BE%D0%B2) Курс лекций по машинному обучению] {{---}} Воронцов К.В.
 
# [http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%BD%D0%BE%D0%B5_%D0%BE%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_(%D0%BA%D1%83%D1%80%D1%81_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B9%2C_%D0%9A.%D0%92.%D0%92%D0%BE%D1%80%D0%BE%D0%BD%D1%86%D0%BE%D0%B2) Курс лекций по машинному обучению] {{---}} Воронцов К.В.
  
 
[[Категория: Машинное обучение]]
 
[[Категория: Машинное обучение]]

Версия 14:05, 17 марта 2019

Ранжирование (англ. 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]q[/math] — это список документов [math]d[/math], упорядоченных с помощью функции ранжирования [math]a(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].

Дисконтированный совокупный доход

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

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

См. также

Примечания

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

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