Изменения

Перейти к: навигация, поиск

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

24 байта убрано, 15 март
Нет описания правки
===DCG===
Второй подход к измерению качества ранжирования — дисконтированный совокупный доход (англ. discounted cumulative gain) или DCG. ОнаОн
используется в более сложной ситуации, когда оценки релевантности <tex>y</tex> могут быть вещественными: <tex>y(q, d) \in \mathbb{R}</tex>.
Дано множество документов, где каждый документ оценивается от <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"
===Поточечный подход===
Самый простой подход — это поточечный. В нём игнорируется тот факт, что целевая переменная <tex>y(q, d) \in \mathbb{R}</tex> задаётся на парах объектов, и оценка релевантности <tex>a(d, q)</tex> оценивается непосредственно считается для каждого объекта.
Если речь идёт о задаче ранжированияпоисковой выдачи, то пусть асессор поставил какую-то оценку <tex>y</tex> каждой паре (запрос, документ). Эта оценка и будет предсказываться. При этом никак не учитывается, что на самом деленужно предсказать порядок объектов, а не оценки. Этот подход является простым в том смысле, что в нём
используются уже известные методы. Например, можно предсказывать оценки с использованием линейной
регрессии и квадратичной ошибки:
===Попарный подход===
В попарном подходе используются знания об устройстве целевой переменной. Модель строится минимизацией сведением к минимуму количества дефектных пар, то есть таких, в которых моделью был предсказан неправильный порядок:
<tex>\sum_{x_i < x_j} [a(x_j) - a(x_i) < 0] \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 действительно улучшается при решениизадачи данным методомДанный метод называется LambdaRank.
Оказывается, что при выполнении градиентного спуска с помощью данных шагов оптимизируется nDCG. Существуют и другие подходы к оптимизации nDCG, однако в них предпринимается попытка работы сфункционалом, что гораздо сложнее. Выше описан самый простой подход, он называется LambdaRank.
== Источники информации ==
# [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
# [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) Курс лекций по машинному обучению] {{---}} Воронцов К.В.
 
[[Категория: Машинное обучение]]
44
правки

Навигация