Изменения
Нет описания правки
precision, <tex>AP</tex>). Данная метрика тоже измеряется на уровне <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>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>
То есть для каждого документа теперь существует градация между релевантностью и нерелевантностью.
Остальные обозначения остаются теми же, что и для предыдущей метрики
Формула для вычисления DCG:
<tex>DCG@k(q)= \sum_{i = 1}^{k} {\large {{2^{y(q, d_{q}^{(i)})} - 1} \over {log(i+1)}}}</tex>
Метрика — это сумма дробей. Чем более релевантен документ, тем больше числитель в дроби. Знаменатель
зависит от позиции документа, он штрафует за то, где находится документ. Если документ очень релевантен,
но занимает низкую позицию, то штраф будет большим, если документ релевантен и находится вверху списка,
штраф будет маленьким. Таким образом, метрика DCG учитывает и релевантность, и позицию документа.
Она достигает максимума, если все релевантные документы находятся в топе списка, причём отсортированные
по значению <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.
==Методы ранжирования==
Всего выделяют три подхода к решению задачи ранжирования: pointwise (поточечный), pairwise (попарный), listwise (списочный). Далее будут приведены по одному методу из каждого подхода, чтобы можно было
составить представления об их различиях и особенностях.
===Поточечный подход===
Самый простой подход — это поточечный. В нём игнорируется тот факт, что целевая переменная <tex>y(q, d) \in \mathbb{R}</tex> задаётся на парах объектов, и оценка релевантности <tex>a(d, q)</tex> оценивается непосредственно для каждого объекта.
Если речь идёт о задаче ранжирования, то пусть асессор поставил какую-то оценку <tex>y</tex> каждой паре запрос, документ. Эта оценка и будет предсказываться. При этом никак не учитывается, что на самом деле
нужно предсказать порядок объектов, а не оценки. Этот подход является простым в том смысле, что в нём
используются уже известные методы. Например, можно предсказывать оценки с использованием линейной
регрессии и квадратичной ошибки:
<tex>\sum_{i = 1}^{l} (a(q_i, d_i) - y(q_i, d_i))^2 \rightarrow min</tex>
Известно, как решать такую задачу, и таким образом будет получена релевантность. Далее по выходам модели
можно ранжировать объекты.
===Попарный подход===
В попарном подходе используются знания об устройстве целевой переменной. Модель строится минимизацией количества дефектных пар, то есть таких, в которых моделью был предсказан неправильный порядок:
<tex>\sum_{x_i < x_j} [a(x_j) - a(x_i) < 0] \rightarrow min</tex>
К сожалению, этот функционал дискретный (в него входят индикаторы), поэтому не получится минимизировать непосредственно его. Однако можно действовать так же, как и с классификаторами: оценить функционал
сверху.
Можно считать, что разница между объектами <tex>a(x_j) − a(x_i)</tex> — это отступ <tex>M</tex>, и задать некоторую гладкую
функцию <tex>L(M)</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. Затем можно решать задачу, например, с помощью стохастического градиентного спуска.
===Listwise-подход===
В методе RankNet шаг стохастического градиентного спуска для линейной модели выглядит следующим
образом:
<tex>\omega := \omega + \eta {{\large 1} \over {\large 1 + exp(\langle \omega, x_j - x_i \rangle)}} (x_j - x_i)</tex>
Это не очень сложная формула, она зависит от одной пары объектов. Возникает вопрос, можно ли модифицировать данный метод (а именно формулу шага) так, чтобы минимизировался не исходный функционал,
оценивающий долю дефектных пар, а DCG.
Ответ на этот вопрос положительный. Можно домножить градиент исходного функционала на то, насколько изменится 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>
Оказывается, что при выполнении градиентного спуска с помощью данных шагов оптимизируется NDCG.
Это эмпирический факт, и он не доказан. Но на практике NDCG действительно улучшается при решении
задачи данным методом.
Существуют и другие подходы к оптимизации nDCG, однако в них предпринимается попытка работы с
функционалом, что гораздо сложнее. Выше описан самый простой подход, он называется LambdaRank.
== Источники информации ==
# [http://www.machinelearning.ru/wiki/images/8/89/Voron-ML-Ranking-slides.pdf?title=Rank Обучение ранжировнию] {{---}} статья на machinelearning.ru
# [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) Курс лекций по машинному обучению] {{---}} Воронцов К.В.
[[Категория: Машинное обучение]]
