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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 7 промежуточных версий 3 участников)
Строка 1: Строка 1:
 +
'''Ранжирование''' (англ. ''learning to rank'') {{---}} это класс задач [[Общие понятия|машинного обучения с учителем]], заключающихся в автоматическом подборе ранжирующей модели по обучающей выборке, состоящей из множества списков и заданных частичных порядков на элементах внутри каждого списка. Частичный порядок обычно задаётся путём указания оценки для каждого элемента (например, «релевантен» или «не релевантен»). Цель ранжирующей модели — наилучшим образом приблизить и обобщить способ ранжирования в обучающей выборке на новые данные.
 +
 +
 
==Постановка задачи==
 
==Постановка задачи==
<tex>x_1 \ldots x_l</tex> выборка, состоящая из <tex>l</tex> элементов. Она состоит из объектов, имеющих признаковое описание, как и в задачах регрессии и классификации.
+
<tex>X</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>a : X \to \mathbb{R}</tex> такую, что: <tex> i \prec j \Rightarrow a(x_i) < a(x_j)</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>Q</tex> {{---}} множество запросов.
 +
 
 +
<tex>D_q \subseteq D</tex> {{---}} множество документов, найденных по запросу <tex>q</tex>.
 +
 
 +
<tex>X = Q \times D</tex> {{---}} объектами являются пары (запрос, документ): <tex>x \equiv (q, d), q \in Q, d \in D_q</tex>.
 +
 
 +
<tex>Y</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>d</tex>, упорядоченных с помощью функции ранжирования <tex>a(q, d)</tex>.
  
Ключевое отличие ранжирования заключается в целевой переменной. Если ранее в задачах обучения с учителем каждому объекту соответствовал свой ответ, то теперь ответы — это пары вида: <tex>\{ (i, j) : x_i \lt x_j\} </tex>. Набор таких пар и есть целевая переменная.
+
===Коллаборативная фильтрация===
 +
<tex>U</tex> {{---}} пользователи.
  
Основная задача – построить ранжирующую модель <tex>a(x)</tex>, такую, что: <tex>\{ x_i \lt x_j \Rightarrow a(x_i) \lt a(x_j) \}</tex>
+
<tex>I</tex> {{---}} предметы (фильмы, книги и т.д.).
  
Таким образом, по выходам необходимо восстановить порядок, а величина ответов не имеет значения. В этом
+
<tex>X = U \times I</tex> {{---}} объектами являются пары (пользователь, предмет).
заключается главное отличие ранжирования от остальных задач машинного обучения.
 
  
==Ранжирование поисковой выдачи==
+
''Правильный порядок'' определён между предметами, которые выбирал или рейтинговал один и тот же пользователь: <tex>(u, i) \prec (u, i') \Leftrightarrow y(u, i) < y(u, i')</tex>.
Классическим примером для задачи ранжирования считается ранжирование поисковой выдачи. Далее для понимания материала везде будет рассматриваться данный пример, но все рассуждения хорошо обобщаются и для других применений.
 
  
В качестве объектов выступают пары <tex>(запрос, документ)</tex>. Запрос – ключевые слова, введенные пользователем, документ – один из всех документов, имеющихся в поисковой выдаче: <tex>({запрос}, {документ}_1) \lt ({запрос}, {документ}_2) </tex>
+
Рекомендация пользователю <tex>u</tex> {{---}} это список предметов <tex>i</tex>, упорядоченный с помощью функции ранжирования <tex>a(u, i)</tex>.
  
 
==Метрики качества ранжирования==
 
==Метрики качества ранжирования==
 
===Точность ранжирования===
 
===Точность ранжирования===
 
В самой простой постановке задачи ранжирования целевая переменная принимает два значения, документ
 
В самой простой постановке задачи ранжирования целевая переменная принимает два значения, документ
либо релевантен запросу, либо нет:
+
либо релевантен запросу, либо нет:  
  
 
<tex>y(q, d) \in \{0, 1\}, </tex> где <tex>y</tex> – целевая переменная, <tex>q</tex> – запрос, <tex>d</tex> – документ.
 
<tex>y(q, d) \in \{0, 1\}, </tex> где <tex>y</tex> – целевая переменная, <tex>q</tex> – запрос, <tex>d</tex> – документ.
Строка 24: Строка 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>. Данная метрика определяется
 
как доля релевантных документов среди первых <tex>k</tex>, полученных с помощью модели:
 
как доля релевантных документов среди первых <tex>k</tex>, полученных с помощью модели:
  
<tex>Precision@k(q) = {{1}\over{k}} \sum_{i = 1}^{k} y(q, d_{q}^{(i)})</tex>
+
<tex>Precision@k(q) = {{1}\over{k}} \sum_{i = 1}^{k} y(q, d_{q}^{(i)})</tex>.
  
Это полезная метрика, потому что обычно важно иметь релевантные документы среди первых <tex>k</tex>. Однако
+
Однако у неё есть серьёзный недостаток: позиции релевантных документов никак не учитываются. Например, если
у неё есть серьёзный недостаток: позиции релевантных документов никак не учитываются. Например, если
 
 
при <tex>k = 10</tex> среди первых <tex>k</tex> документов есть <tex>5</tex> релевантных, то неважно, где они находятся: среди первых
 
при <tex>k = 10</tex> среди первых <tex>k</tex> документов есть <tex>5</tex> релевантных, то неважно, где они находятся: среди первых
 
или последних <tex>5</tex> документов. Обычно же хочется, чтобы релевантные документы располагались как можно
 
или последних <tex>5</tex> документов. Обычно же хочется, чтобы релевантные документы располагались как можно
 
выше.
 
выше.
  
Описанную проблему можно решить, модифицировав метрику, и определить среднюю точность (average
+
Описанную проблему можно решить, модифицировав метрику, и определить среднюю точность (англ. average
precision, <tex>AP</tex>). Данная метрика тоже измеряется на уровне <tex>k</tex> и вычисляется следующим образом:
+
precision). Данная метрика тоже измеряется на уровне <tex>k</tex> и вычисляется следующим образом:
  
<tex>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)})}}}</tex>
+
<tex>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)})}}}</tex>.
  
 
Данная величина уже зависит от порядка. Она достигает максимума, если все релевантные документы находятся вверху ранжированного списка. Если они смещаются ниже, значение метрики уменьшается.
 
Данная величина уже зависит от порядка. Она достигает максимума, если все релевантные документы находятся вверху ранжированного списка. Если они смещаются ниже, значение метрики уменьшается.
Строка 46: Строка 77:
 
И точность, и средняя точность вычисляются для конкретного запроса <tex>q</tex>. Если выборка большая и размечена для многих запросов, то значения метрик усредняются по всем запросам:
 
И точность, и средняя точность вычисляются для конкретного запроса <tex>q</tex>. Если выборка большая и размечена для многих запросов, то значения метрик усредняются по всем запросам:
  
<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===
 
Второй подход к измерению качества ранжирования — это метрика DCG (discounted cumulative gain). Она
 
используется в более сложной ситуации, когда оценки релевантности <tex>y</tex> могут быть вещественными:
 
  
<tex>y(q, d) \in \mathbb{R}</tex>
+
===Дисконтированный совокупный доход===
 +
Второй подход к измерению качества ранжирования — дисконтированный совокупный доход (англ. discounted cumulative gain) или DCG. Он
 +
используется в более сложной ситуации, когда оценки релевантности <tex>y</tex> могут быть вещественными: <tex>y(q, d) \in \mathbb{R}</tex>.
  
 
То есть для каждого документа теперь существует градация между релевантностью и нерелевантностью.
 
То есть для каждого документа теперь существует градация между релевантностью и нерелевантностью.
Остальные обозначения остаются теми же, что и для предыдущей метрики
+
Остальные обозначения остаются теми же, что и для предыдущей метрики. Формула для вычисления DCG:
  
Формула для вычисления DCG:
+
<tex>DCG@k(q)= \sum_{i = 1}^{k} {\large {{2^{y(q, d_{q}^{(i)})} - 1} \over {log(i+1)}}}</tex>.
 
 
<tex>DCG@k(q)= \sum_{i = 1}^{k} {\large {{2^{y(q, d_{q}^{(i)})} - 1} \over {log(i+1)}}}</tex>
 
  
 
Метрика — это сумма дробей. Чем более релевантен документ, тем больше числитель в дроби. Знаменатель
 
Метрика — это сумма дробей. Чем более релевантен документ, тем больше числитель в дроби. Знаменатель
Строка 66: Строка 93:
 
штраф будет маленьким. Таким образом, метрика DCG учитывает и релевантность, и позицию документа.
 
штраф будет маленьким. Таким образом, метрика DCG учитывает и релевантность, и позицию документа.
 
Она достигает максимума, если все релевантные документы находятся в топе списка, причём отсортированные
 
Она достигает максимума, если все релевантные документы находятся в топе списка, причём отсортированные
по значению <tex>y</tex>.
+
по значению <tex>y</tex>. Данную метрику принято нормировать:
 +
 
 +
<tex>nDCG@k(q) = {\large {DCG@k(q)} \over {{\large max DCG@k(q)}}}</tex>, где <tex>max DCG@k(q)</tex> — значение DCG при идеальном ранжировании. После нормировки метрика принимает
 +
значения от 0 до 1.
 +
 
 +
'''Пример вычисления DCG и nDCG:'''
 +
 
 +
Дано множество документов, где каждый документ оценивается от <tex>3</tex> до <tex>0</tex>, где <tex>3</tex> {{---}} очень релевантен, а <tex>0</tex> {{---}} не релевантен. Пусть таким множеством будет <tex>S = \{ D_1, D_2, D_3, D_4, D_5, D_6\}</tex>, где оценка релевантности по опросу пользователей задается(в том же порядке) множеством <tex>R = \{3, 2, 3, 0, 1, 2\}</tex>.
 +
 
 +
Тогда <tex>DCG@6 = \sum_{i = 1}^{6} {{rel_i} \over {log(i+1)}} = 3 + 1.262 + 1.5 + 0 + 0.387 + 0.712 = 6.861</tex>.
 +
 
 +
{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"
 +
|+
 +
|-align="center"
 +
! '''i''' || <tex>rel_i</tex> || <tex>log(i+1)</tex> || <tex>{rel_i}\over{log(i+1)}</tex>
 +
|-align="center"
 +
| <tex>1</tex> || <tex>3</tex> || <tex>1</tex> || <tex>3</tex>
 +
|-align="center"
 +
| <tex>2</tex> || <tex>2</tex> || <tex>1.585</tex> || <tex>1.262</tex>
 +
|-align="center"
 +
| <tex>3</tex> || <tex>3</tex> || <tex>2</tex> || <tex>1.5</tex>
 +
|-align="center"
 +
| <tex>4</tex> || <tex>0</tex> || <tex>2.322</tex> || <tex>0</tex>
 +
|-align="center"
 +
| <tex>5</tex> || <tex>1</tex> || <tex>2.585</tex> || <tex>0.387</tex>
 +
|-align="center"
 +
| <tex>6</tex> || <tex>2</tex> || <tex>2.807</tex> || <tex>0.712</tex>
 +
|}
  
Данную метрику принято нормировать:
+
Идеальный порядок оценок релевантности <tex>Ideal = \{3, 3, 2, 2, 1, 0\}</tex>. DCG для данного множества будет следующим: <tex>maxDCG@6 = \sum_{i = 1}^{6} {{rel_i} \over {log(i+1)}} = 3 + 1.893 + 1 + 0.861 + 0.387 + 0 = 7.141</tex>.
  
<tex>nDCG@k(q) = {\large {DCG@k(q)} \over {{\large max DCG@k(q)}}}</tex>
+
{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"
 +
|+
 +
|-align="center"
 +
! '''i''' || <tex>rel_i</tex> || <tex>log(i+1)</tex> || <tex>{rel_i}\over{log(i+1)}</tex>
 +
|-align="center"
 +
| <tex>1</tex> || <tex>3</tex> || <tex>1</tex> || <tex>3</tex>
 +
|-align="center"
 +
| <tex>2</tex> || <tex>3</tex> || <tex>1.585</tex> || <tex>1.893</tex>
 +
|-align="center"
 +
| <tex>3</tex> || <tex>2</tex> || <tex>2</tex> || <tex>1</tex>
 +
|-align="center"
 +
| <tex>4</tex> || <tex>2</tex> || <tex>2.322</tex> || <tex>0.861</tex>
 +
|-align="center"
 +
| <tex>5</tex> || <tex>1</tex> || <tex>2.585</tex> || <tex>0.387</tex>
 +
|-align="center"
 +
| <tex>6</tex> || <tex>0</tex> || <tex>2.807</tex> || <tex>0</tex>
 +
|}
  
где <tex>max DCG@k(q)</tex> — значение DCG при идеальном ранжировании. После нормировки метрика принимает
+
Итого <tex>nDCG@6 = {{DCG@6} \over {maxDCG@6}} = {{6.861} \over {7.141}} = 0.961</tex>.
значения от 0 до 1.
 
  
 
==Методы ранжирования==
 
==Методы ранжирования==
  
Всего выделяют три подхода к решению задачи ранжирования: pointwise (поточечный), pairwise (попарный), listwise (списочный). Далее будут приведены по одному методу из каждого подхода, чтобы можно было
+
Всего выделяют три подхода к решению задачи ранжирования: поточечный (англ. pointwise), попарный (англ. pairwise), списочный (англ. listwise). Выбор метода зависит от качества ранжирования данных. Теоретически, списочный подход считается наилучшим, однако, на практике, например в Яндексе, лучше всего работает попарный подход.
составить представления об их различиях и особенностях.
 
  
 
===Поточечный подход===
 
===Поточечный подход===
  
Самый простой подход — это поточечный. В нём игнорируется тот факт, что целевая переменная <tex>y(q, d) \in \mathbb{R}</tex>  задаётся на парах объектов, и оценка релевантности <tex>a(d, q)</tex> оценивается непосредственно для каждого объекта.
+
Самый простой подход — это поточечный. В нём игнорируется тот факт, что целевая переменная <tex>y(q, d) \in \mathbb{R}</tex>  задаётся на парах объектов, и оценка релевантности <tex>a(d, q)</tex> считается  для каждого объекта.
  
Если речь идёт о задаче ранжирования, то пусть асессор поставил какую-то оценку <tex>y</tex> каждой паре запрос, документ. Эта оценка и будет предсказываться. При этом никак не учитывается, что на самом деле
+
Если речь идёт о задаче ранжирования поисковой выдачи, то пусть асессор поставил какую-то оценку <tex>y</tex> каждой паре (запрос, документ). Эта оценка и будет предсказываться. При этом никак не учитывается, что нужно предсказать порядок объектов, а не оценки. Этот подход является простым в том смысле, что в нём
нужно предсказать порядок объектов, а не оценки. Этот подход является простым в том смысле, что в нём
 
 
используются уже известные методы. Например, можно предсказывать оценки с использованием линейной
 
используются уже известные методы. Например, можно предсказывать оценки с использованием линейной
 
регрессии и квадратичной ошибки:
 
регрессии и квадратичной ошибки:
Строка 96: Строка 163:
 
===Попарный подход===
 
===Попарный подход===
  
В попарном подходе используются знания об устройстве целевой переменной. Модель строится минимизацией количества дефектных пар, то есть таких, в которых моделью был предсказан неправильный порядок:
+
В попарном подходе используются знания об устройстве целевой переменной. Модель строится сведением к минимуму количества дефектных пар, то есть таких, в которых моделью был предсказан неправильный порядок:
  
 
<tex>\sum_{x_i < x_j} [a(x_j) - a(x_i) < 0] \rightarrow min</tex>
 
<tex>\sum_{x_i < x_j} [a(x_j) - a(x_i) < 0] \rightarrow min</tex>
  
К сожалению, этот функционал дискретный (в него входят индикаторы), поэтому не получится минимизировать непосредственно его. Однако можно действовать так же, как и с классификаторами: оценить функционал
+
К сожалению, этот функционал дискретный (в него входят индикаторы), поэтому невозможно его минимизировать. Однако можно действовать так же, как и с классификаторами: оценить функционал
 
сверху.
 
сверху.
  
Строка 108: Строка 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. Затем можно решать задачу, например, с помощью [[Стохастический градиентный спуск|стохастического градиентного спуска]].
  
===Listwise-подход===
+
===Списочный подход===
  
 
В методе RankNet шаг стохастического градиентного спуска для линейной модели выглядит следующим
 
В методе RankNet шаг стохастического градиентного спуска для линейной модели выглядит следующим
Строка 117: Строка 184:
 
<tex>\omega := \omega + \eta {{\large 1} \over {\large 1 + exp(\langle \omega, x_j - x_i \rangle)}} (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)</tex>
  
Это не очень сложная формула, она зависит от одной пары объектов. Возникает вопрос, можно ли модифицировать данный метод (а именно формулу шага) так, чтобы минимизировался не исходный функционал,
+
Заметим, что данная формула зависит от одной пары объектов, а также не учитываются зависимости между различными парами. Возникает вопрос, можно ли модифицировать данный метод (а именно формулу шага) так, чтобы минимизировался не исходный функционал, оценивающий долю дефектных пар, а DCG.
оценивающий долю дефектных пар, а DCG.
 
  
Ответ на этот вопрос положительный. Можно домножить градиент исходного функционала на то, насколько изменится nDCG, если поменять местами <tex>x_i</tex> и <tex>x_j</tex> :
+
Действительно, можно домножить градиент исходного функционала на то, насколько изменится nDCG, если поменять местами <tex>x_i</tex> и <tex>x_j</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>
 
<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>
  
Оказывается, что при выполнении градиентного спуска с помощью данных шагов оптимизируется NDCG.
+
Данный метод называется 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, однако в них предпринимается попытка работы с
функционалом, что гораздо сложнее. Выше описан самый простой подход, он называется LambdaRank.
+
функционалом, что гораздо сложнее.
 +
 
 +
== См. также ==
 +
* [[Общие понятия|Общие понятия]]
 +
* [[Стохастический градиентный спуск|Стохастический градиентный спуск]]
 +
* [[Рекомендательные системы|Рекомендательные системы]]<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
 +
# [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) Курс лекций по машинному обучению] {{---}} Воронцов К.В.
 +
 
[[Категория: Машинное обучение]]
 
[[Категория: Машинное обучение]]

Текущая версия на 19:27, 4 сентября 2022

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