174
правки
Изменения
м
Это не очень сложная Заметим, что данная формула, она зависит от одной пары объектов, а также не учитываются зависимости между различными парами. Возникает вопрос, можно ли модифицировать данный метод (а именно формулу шага) так, чтобы минимизировался не исходный функционал,оценивающий долю дефектных пар, а DCG.
Ответ на этот вопрос положительный. Можно Действительно, можно домножить градиент исходного функционала на то, насколько изменится nDCG, если поменять местами <tex>x_i</tex> и <tex>x_j</tex> :
Существуют и другие подходы к оптимизации nDCG, однако в них предпринимается попытка работы с== Примечания ==функционалом, что гораздо сложнее. Выше описан самый простой подход, он называется LambdaRank.<references/>
→Методы ранжирования
<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; 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>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>q</tex>.
После того как введены обозначения, можно задать простейшую метрику ранжирования. Это <tex>Precision@k</tex>,
точность среди первых <tex>k</tex> документов (<tex>k</tex> — параметр метрики). Если ранжируется поисковая выдача, и на
первой странице показываются 10 документов, то разумно выбирать <tex>k = 10</tex>. Данная метрика определяется
<tex>MAP@k = {{1}\over{|Q|}} \sum_{q \in Q} AP@k(q)</tex>.
===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"
==Методы ранжирования==
Всего выделяют три подхода к решению задачи ранжирования: поточечный (англ. pointwise), попарный (англ. pairwise), списочный (англ. listwise). Выбор метода зависит от качества ранжирования данных. Теоретически, списочный подход считается наилучшим, однако, на практике, например в Яндексе, лучше всего работает попарный подход.
===Поточечный подход===
Самый простой подход — это поточечный. В нём игнорируется тот факт, что целевая переменная <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>\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>
<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<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>. Оказывается, что при выполнении градиентного спуска с помощью данных шагов оптимизируется NDCGnDCG.Существуют и другие подходы к оптимизации nDCG, однако в них предпринимается попытка работы сЭто эмпирический фактфункционалом, и он не доказанчто гораздо сложнее. == См. Но также ==* [[Общие понятия|Общие понятия]]* [[Стохастический градиентный спуск|Стохастический градиентный спуск]]* [[Рекомендательные системы|Рекомендательные системы]]<sup>[на практике NDCG действительно улучшается при решениизадачи данным методом17.03.19 не создан]</sup>
== Источники информации ==
# [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) Курс лекций по машинному обучению] {{---}} Воронцов К.В.
[[Категория: Машинное обучение]]
