1632
правки
Изменения
м
Это не очень сложная Заметим, что данная формула, она зависит от одной пары объектов, а также не учитываются зависимости между различными парами. Возникает вопрос, можно ли модифицировать данный метод (а именно формулу шага) так, чтобы минимизировался не исходный функционал,оценивающий долю дефектных пар, а DCG.
Ответ на этот вопрос положительный. Можно Действительно, можно домножить градиент исходного функционала на то, насколько изменится nDCG, если поменять местами <tex>x_i</tex> и <tex>x_j</tex> :
Оказывается, что при выполнении градиентного спуска с помощью данных шагов оптимизируется NDCGДанный метод называется LambdaRank<ref>[https://www.Это эмпирический факт, и он не доказанmicrosoft. Но на практике NDCG действительно улучшается при решениизадачи данным методомcom/en-us/research/wp-content/uploads/2016/02/MSR-TR-2010-82.pdf From RankNet to LambdaRank {{---}} Christopher J.C. Burges]</ref>.
rollbackEdits.php mass rollback
<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>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>.
{| 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>nDCG@6 = {{DCG@6} \over {maxDCG@6}} = {{6.861} \over {7.141}} = 0.961</tex>.
==Методы ранжирования==
Всего выделяют три подхода к решению задачи ранжирования: поточечный (англ. 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>
Оказывается, что при выполнении градиентного спуска с помощью данных шагов оптимизируется 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
# [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) Курс лекций по машинному обучению] {{---}} Воронцов К.В.
[[Категория: Машинное обучение]]
