Изменения

<tex>X</tex> {{---}} множество объектов. <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 \to \mathbb{R}</tex> такую, что: <tex> i \prec j \Rightarrow a(x_i) < a(x_j)</tex>.

Ключевое отличие '''Линейная модель ранжирования заключается в целевой переменной. Если ранее в задачах обучения с учителем каждому объекту соответствовал свой ответ, то теперь ответы — это пары вида: <tex>\{ (i, j) : x_i \lt x_j\} </tex>. Набор таких пар и есть целевая переменная.'''

Основная задача – построить ранжирующую модель <tex>a(x; w)= \langle x, w \rangle</tex>, такую, что: где <tex>x \{ x_i \lt x_j \Rightarrow amapsto (f_1(x_ix) , \lt aldots, f_n(x_jx) ) \in \mathbb{R}^n</tex> {{---}} вектор признаков объекта <tex>x</tex>.

Таким образом, по выходам необходимо восстановить порядок, а величина ответов не имеет значения. В этом==Примеры приложения==заключается главное отличие ===Задача ранжирования от остальных задач машинного обученияпоисковой выдачи===<tex>D</tex> {{---}} коллекция текстовых документов.

==Ранжирование поисковой выдачи==Классическим примером для задачи ранжирования считается ранжирование поисковой выдачи. Далее для понимания материала везде будет рассматриваться данный пример, но все рассуждения хорошо обобщаются и для других применений<tex>Q</tex> {{---}} множество запросов.

В качестве объектов выступают пары <tex>D_q \subseteq D</tex> {{---}} множество документов, найденных по запросу <tex>q</tex>. <tex>X = Q \times D</tex> {{---}} объектами являются пары (запрос, документ): <tex>x \equiv (q, d), q \in Q, d \in D_q</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>U</tex> {запрос{---}} пользователи. <tex>I</tex> {{---}}предметы (фильмы, книги и т.д.). <tex>X = U \times I</tex> {{документ---}}_1объектами являются пары (пользователь, предмет). ''Правильный порядок'' определён между предметами, которые выбирал или рейтинговал один и тот же пользователь: <tex>(u, i) \lt prec (u, i') \Leftrightarrow y(u, i) < y(u, i')</tex>. Рекомендация пользователю <tex>u</tex> {{запрос---}}это список предметов <tex>i</tex>, {документ}_2упорядоченный с помощью функции ранжирования <tex>a(u, i) </tex>.

либо релевантен запросу, либо нет:

<tex>Precision@k(q) = {{1}\over{k}} \sum_{i = 1}^{k} y(q, d_{q}^{(i)})</tex>.

Это полезная метрика, потому что обычно важно иметь релевантные документы среди первых <tex>k</tex>. Однакоу неё есть серьёзный недостаток: позиции релевантных документов никак не учитываются. Например, если

Описанную проблему можно решить, модифицировав метрику, и определить среднюю точность (англ. averageprecision, <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 дисконтированный совокупный доход (англ. discounted cumulative gain)или DCG. Онаиспользуется в более сложной ситуации, когда оценки релевантности <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>.

по значению <tex>y</tex>. Данную метрику принято нормировать: <tex>nDCG@k(q) = {\large {DCG@k(q)} \over {{\large max DCG@k(q)}}}</tex>

<tex>nDCG@k(q) = {\large {DCG@k(q)} \over {{\large max DCG@k(q)}}}</tex>, где <tex>max DCG@k(q)</tex> — значение DCG при идеальном ранжировании. После нормировки метрика принимает