44
правки
Изменения
Нет описания правки
<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>.
==Методы ранжирования==
Всего выделяют три подхода к решению задачи ранжирования: поточечный (англ. pointwise), попарный (англ. pairwise), списочный (англ. listwise). Выбор метода зависит от качества ранжирования на данных. Теоретически, списочный подход считается наилучшим, однако, например в Яндексе, лучше всего работает попарный подход.
===Поточечный подход===
<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>\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>.
Оказывается, что при выполнении градиентного спуска с помощью данных шагов оптимизируется nDCG. Существуют и другие подходы к оптимизации nDCG, однако в них предпринимается попытка работы с
функционалом, что гораздо сложнее.
== См. также ==
* [[Общие понятия|Общие понятия]]
* [[Стохастический градиентный спуск|Стохастический градиентный спуск]]
* [[Рекомендательные системы|Рекомендательные системы]]<sup>[на 17.03.19 не создан]</sup>
== Примечания ==
<references/>
== Источники информации ==
# [http://www.machinelearning.ru/wiki/images/8/89/Voron-ML-Ranking-slides.pdf?title=Rank Обучение ранжировнию] {{---}} статья на machinelearning.ru
# [httphttps://www.microsoftcoursera.comorg/enlecture/text-usretrieval/research/wplesson-6-1-learning-to-content/uploads/2016/02/MSRrank-TRpart-20101-82.pdf From RankNet mFYTD Learning to LambdaRankrank] {{---}} Christopher J.Cпрезентация на coursera. Burges From RankNet to LambdaRank to LambdaMART: An Overvieworg
# [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) Курс лекций по машинному обучению] {{---}} Воронцов К.В.
[[Категория: Машинное обучение]]
