Изменения

Положим, имеется конечное множество &Chi; <tex>X</tex> объектов (например, экспертных оценок или критериев) и ''<tex>m'' </tex> экспертов, пронумерованных индексами <tex>1,2... m</tex>. каждый ''Каждый <tex>i-</tex>й'' эксперт выставляет рейтинг, порождая порядок. Подобные тип задач в машинном обучении обозначается как ранжирование. <br \>'''Ранжирование''' (англ. ''learning to rank'') {{---}} особый тип задач [[Машинное обучение |машиного обучения ]], связанный с постороением некой ранжирующей модели по обучащей выборке. Отличие от классификации и регрессии состоит в том, что для обучающей выборки не заданы ответы, однако задано [[Отношение порядка |отношение порядка]] для пары объектов. Стоит отметить, что от отношения порядка на множестве объектов изменяется и подход к ранжированию.

 == Слабое ранжирование .Представления ===== Слабое Строгое слабое упорядовачивание ===

[[Бинарное отношение]] <tex><</tex> на множестве <tex>X x \times X</tex>, которое является [[Отношение порядка |частично упорядоченным]], называется '''слабым упорядочиванием''' (англ. ''weak ordering''), если оно обладает следующими свойствами:* [[Рефлексивное отношение|Иррефлексивность]] (англ. ''irreflexivity''): <tex>\forall a \in X:</tex> если <tex>a < b</tex>, то <tex>b < a</tex> - не выполняется.

Примечание: Строгое определение несравнимости: <tex>\forall a, b \in X:</tex>, если <tex>&not;b<a</tex> и <tex>&not;a<b</tex> и <tex>a\not=b</tex>, то <tex>a</tex> ~ <tex>\sim b</tex>.

* ПолноеСильное: <tex>\forall a, b \in X:</tex> <tex>a < b</tex> и <tex>b < a</tex>, те то есть если ~ пусто<tex>\emptyset</tex>.* Слабое<ref>[https://www.sciencedirect.com/science/article/pii/0012365X85900421 Interval graphs and interval orders]</ref>: <tex>\forall a, b, c \in X:</tex> если <tex>a~\sim b~\sim c</tex>, то <tex>a</tex>~<tex>\sim b</tex> и <tex>a=c</tex>.Можно заключить, что любое полное cильное упорядовачивание есть слабое. Отношение несравнимости является [[Отношение эквивалентности |отношением эквивалентности]] для всех своих разбиений на множестве <tex>X</tex>, что являются [[Упорядоченное множество |линейно упорядоченными]].  === Сильный подпорядок === {{Определение|definition='''Сильный подпорядок''' {{---}} такой подпорядок, на котором присутствует [[Отношение связности, компоненты связности |отношение связанности]].}}Сильный подпорядок <tex>\le \; \in X\times X</tex> обладает рядом следующих свойств:* [[Транзитивное отношение|Транзитивность]]: <tex>\forall a, b, c \in X:</tex> если <tex>a&le;b</tex> и <tex>b&le;c \Rightarrow a&le;c</tex>.* [[Отношение связности, компоненты связности |Связанности]]: <tex>\forall a, b \in X:</tex> выполнимо либо <tex>a&le;b</tex>, либо <tex>b&le;a</tex>.Если в любом сильном подпорядке <tex>\exists a,b : a&le;b</tex> и <tex>b&le;a</tex>, то на нем определено [[Отношение эквивалентности |отношение эквивалентности]]. Поскольку операция определена для всех элементов, такие подпорядки еще называют '''отношением предпочтения'''<ref>[https://eml.berkeley.edu/~webfac/saez/e131_s04/prefer.pdf Preference Relations, Social Decision Rules, Single-Peakedness, and Social Welfare Functions]</ref>. === Сравнения ========= Вещественная функция ======Удобство использования слабого ранжирования в том, что его элементы могут быть представлены единственным образом с помощью вещественных функций. Рассмотрим следующую теорему. {{Теорема|о слабом упорядочивании|statement=Для любого частичного упорядочивания <tex><\in X\times X</tex> '''слабое''' ''тогда и только тогда'', когда существует <tex><_t\in Y\times Y</tex> и отображение <tex> u: X \rightarrow Y :</tex> если <tex>a<b</tex>, то <tex>u(a) <_t u(b)</tex> и наоборот.}}Таким образом, чтобы имели место быть:* '''частичный подпорядок''': для <tex>a&le;b</tex> ''тогда и только тогда'', когда <tex>u(a)&le;u(b)</tex>.* '''эквивалентность''': для <tex>a \sim b</tex> ''тогда и только тогда'', когда <tex>u(a)=u(b)</tex>. ''Ограничения'': <br \>Лексикографические предпочтения. Ранжирующая функция может быть определена на любом конечном множестве, однако для случая лексикографического порядка функция не определена на <tex>R^n</tex>. <br \>[[Отображения |Инъективность]]. В случае, если бы <tex>u</tex> являлась бы инъективной функцией, то класс эквивалентности двух элементов множества <tex>Y</tex> мог бы переходить в более широкий соответствующий класс на множестве <tex>X</tex>. <br \>[[Отображения |Сюрьективность]]. Если на <tex>u</tex> вводятся ограничения, чтобы быть сюръективной функцией, то при отображении элементов некого класса на <tex>Y</tex> возможно соответствие ему меньшего или вовсе пустого класса на <tex>X</tex>. ====== Кусочная последовательность ======Для любого конечного множества <tex>X</tex>, на котором задано отношение слабого упорядовачивания и <tex>\exists u: X \rightarrow Y </tex>, может быть применимо моделирование с помощью кусочных последовательностей. Рассмотрим пример. Положим, что <center><tex>X=\{ a, b, c, d, e \}</tex></center><center><tex>u(a) = u(c) = 0, u(e) = 2, u(b) = u(d) = 5</tex> </center> Тогда слабое ранжирование <tex><</tex> представляется в виде следующего:<center><tex>\{ a, c \} \{ e \} \{ b, d \} </tex></center> == Частичное ранжирование =={{Определение|definition =[[Бинарное отношение]] <tex><</tex> на множестве <tex>X \times X</tex>, для некоторых элементов которого определена несравнимость <tex>\sim</tex>,называется '''частичным упорядочиванием''' (англ. ''semiorder''), если оно обладает следующими свойствами:* [[Рефлексивное отношение|Иррефлексивность]] (англ. ''irreflexivity''): <tex>\forall a \in X:</tex><tex>a \sim a</tex>.* [[Симметричное отношение|Ассиметричность]] (англ. ''asymmetry''): <tex>\forall a, b \in X:</tex> если <tex>a < b</tex>, то не <tex> b < a </tex>.* [[Транзитивное отношение|Транзитивность]] (англ. ''transitivity''): <tex>\forall a, b, c, d \in X:</tex> если <tex>a<b, \; b\sim c</tex> и <tex>c<d</tex>, то <tex>a<d</tex>.* Критерий сравнимости: <tex>\forall a, b, c, d \in X:</tex> если <tex>a<b</tex>, и <tex>b<c</tex>, то либо <tex>a<d</tex>, либо <tex>d<c</tex>. Примечание: не стоит путать последний критерий с слабым упорядочиванием, где отношение несравнимости транзитивно. Здесь же речь ведется о том, что среди <tex>a,b,c \;d</tex> должен быть хотя бы один элемент сравним c данным. }}=== Сравнения ========= Вещественная функция ======Частичное ранжирование поддается тому же функциональному подходу к сравнению за тем лишь исключением, что для численных значений объектов вводится некоторая погрешность <tex>\xi</tex>, внутри которой объекты считаются сравнимы, снаружи - нет. Зачастую такую погрешность выбирают нормированной к <tex>1</tex>.{{Теорема|о частичном упорядочивании|statement=Для любого конечного частичного упорядочиванием <tex><\in X\times X</tex> возможно определить такое <tex>\xi</tex> и функционал <tex> u: X \rightarrow Y :</tex> если <tex>a<b</tex>, то <tex>u(a) \le u(b) - \xi</tex> и наоборот.}}====== Интервальный метод ======Имея заданный функционал <tex> u: X \rightarrow Y :</tex> и <tex>\xi</tex> возможно использование интервального сравнения, а именно {{---}} объекты считаются сравнимы, если значения их оценок лежат в некотором интервале. Так, например, если <tex>a<b</tex>, то <tex>[u(a),u(b)-1]</tex>. ''Ограничения'': Если у данного частичного ранжирования существует несчетное множество строго упорядоченных объектов, то невозможно подобрать такую <tex>u</tex>. В противовес, любое конечное частичное ранжирование может быть описано с помощью <tex>u</tex>. == Сильное ранжирование =={{Определение|definition =[[Бинарное отношение]] <tex><</tex> на множестве <tex>X \times X</tex>, для некоторых элементов которого определена несравнимость <tex>\sim</tex>,называется '''сильным ранжированием''' (англ. ''total order''), если оно обладает следующими свойствами:* [[Рефлексивное отношение|Иррефлексивность]] (англ. ''irreflexivity''): <tex>\forall a \in X:</tex> <tex>a \sim a</tex>.* [[Симметричное отношение|Ассиметричность]] (англ. ''asymmetry''): <tex>\forall a, b \in X:</tex> если <tex>a < b</tex>, то не <tex> b < a </tex>.* [[Транзитивное отношение|Транзитивность]] (англ. ''transitivity''): <tex>\forall a, b, c, d \in X:</tex> если <tex>a<b, \; b\sim c</tex> и <tex>c<d</tex>, то <tex>a<d</tex>.* Критерий сравнимости: <tex>\forall a, b, c, d \in X:</tex> если <tex>a<b</tex>, и <tex>b<c</tex>, то либо <tex>a<d</tex>, либо <tex>d<c</tex>. * Трихотомия (англ. ''trichotomy''): <tex>\forall a, b \in X:</tex> <tex>x<y \vee y<x \vee x=y </tex> выполняется. }}Таким образом, сильное ранжирование {{---}} строгое слабое, для которого <tex>\sim \emptyset</tex>.=== Сравнения ========= Вещественная функция ======Сильное ранжирование сравнивается с помощью функционала <tex>u</tex>.{{Лемма|о сильном упорядочивании|statement=Для любого конечного сильного упорядочивания <tex>\le \in X\times X</tex> возможно определить такой функционал <tex> u: X \rightarrow Y :</tex> если <tex>a\le b</tex>, то <tex>u(a) \le u(b)</tex> и наоборот.}}====== Последовательность ======Для любого конечного множества <tex>X</tex>, на котором задано отношение сильного упорядочивания и <tex>\exists u: X \rightarrow Y </tex>, может быть применимо моделирование с помощью порождения последовательности значений элементов. Иными словами, задается новый функционал <tex> v: Y \rightarrow \mathbb{N} </tex>, что все оценки образуют последовательность.  ''Ограничения'': <tex>\; </tex>Как и для частичного, множество <tex>X</tex> должно быть конечно. == Supervised алгоритмы ранжирования ===== OC-SVM ===Ordinal Classification SVM {{---}} алгоритм поточечного ранжирования, рассматривающий каждый объект обособленно. В основе стоит использования идеи [[Метод опорных векторов (SVM) |метода опорных векторов]] о проведении разделяющей гиперплоскости над множеством оценок. ==== Постановка задачи ====Пусть имеется некое число градаций (оценок, предпочтений) <tex>K</tex>, тогда <tex>Y=\{1,2 ...K\}</tex> {{---}} ранжирующая функция с порогами <center> <tex>b_0=-\infty</tex>, <tex>b_1,b_2 ...b_{K-1} \in R, b_k=\infty:</tex></center> <center><tex>a(x)=y</tex>, если <tex>b_{y-1}<(w,x)\le b_y </tex> </center>Основное отличие от классического подхода в том, что на имеющееся <tex>K</tex> границ необходимо найти <tex>K-1</tex> зазоров. Иными словами, необходимо '''найти один направляющий вектор''' <tex>K-1</tex> числа гиперплоскостей. Исходим от предположения, что найдется такое направление, в котором объекты удовлетворительно отранжировались. Пример такого разделения для <tex>K=5</tex> представлен на [[Медиа:OC-svm.PNG|рисунке 1]].{|align="center" |-valign="top" |[[Файл:OC-svm.PNG|thumb|540px|Рис. 1. Направляющий вектор для <tex>K=5</tex>]] |} ==== Подход ====Поскольку теперь увеличилось число зазоров, классического значения штрафа <tex>\xi</tex> недостаточно {{---}} необходимы штрафы <tex>\xi^*_i</tex> и <tex>\xi_i</tex> для нарушение с левой и правой сторон соответственно <tex>i-</tex>ой границы. Ограничительное условие для такого случая состоит в том, что произвольный объект <tex>x_i</tex>, оказавшийся между разделяющими полосами, не должен выйти за их пределы ни слева, ни справа, что можно записать как:<center><tex>b_{y_i-1}+1-\xi^*_i \le \langle w_i,x_i\rangle \le b_{y_i}-1+\xi_i </tex></center> Для случая крайних границ, для объектов <tex>x_i : \hat{K}=1</tex> может существовать только нарушение слева от границы, когда для объектов <tex>x_i : \hat{K}=K</tex> {{---}} только справа от границы.Таким образом, задача может быть сформирована как задача минимизации с ограничениями:<center><tex> \begin{cases} \frac{1}{2}||w||^2 + C\sum_{i=1}^l(\xi^*_i[y_i \ne 1] + \xi_i[y_i \ne K]) \rightarrow \underset{w,b,\xi}{min} ; \\ b_{y_i-1}+1-\xi^*_i \le \langle w_i,x_i\rangle \le b_{y_i}-1+\xi_i ; \\ \xi^*_i \ge 0, \xi_i \ge 0 \end{cases} </tex></center> === Ranking SVM ===----Алгоритм для ''попарного подхода''<ref>[https://www.cs.cornell.edu/people/tj/publications/joachims_02c.pdf Optimizing Search Engines using Clickthrough Data]</ref> к ранжированию. Основное отличие от алгоритма SVM в том, что теперь объекты нумеруются попарно. ==== Постановка задачи ==== Считаем, что теперь решаем следующую оптимизационную задачу:<center><tex>Q(a) = \frac{1}{2}|w||^2 + C\sum_{i=1}^l(\mathbb{L}(a(x_j) - a(x_i)) \rightarrow \underset{a}{min}</tex>, где </center><center><tex>a(x) = \langle w,x\rangle </tex> {{---}} функция ранжирования,</center><center><tex>\mathbb{L}(M) = (1-M)_+ </tex> {{---}} функция потерь, </center><center><tex>M=Margin(i,j) = \langle w,x_j-x_i\rangle </tex> {{---}} отступ. </center> ==== Подход ====Поскольку теперь все операции выполяняются уже для пары объектов, то строгая система ограничений будет отличаться в соответствующих местах:<center><tex> \begin{cases} \frac{1}{2}||w||^2 + C\sum_{i=1}^l \xi_{ij} \rightarrow \underset{w,\xi}{min}; \\ \langle w,x_j-x_i\rangle \ge 1- \xi_{ij}, i\prec j ; \\ \xi_{ij} \ge 0, i\prec j \end{cases} </tex></center> === <nowiki>RankNet, LambdaRank</nowiki> ===----Данные алгоритмы применяются для списочного ранжирования, хотя по сути своей используют попарный подход, который был расширен до случая списка. [[Файл:LambdaRank.png|thumb|420px|Рис. 2. LambdaRank с разными функционалами]]==== Постановка задачи ==== Считаем, что у нас есть некий гладкий функционал качества, который необходимо оптимизировать:<center><tex>Q(a) = sum_{i\prec j}(\mathbb{L}(a(x_j) - a(x_i)) \rightarrow \underset{a}{min}</tex> </center>Конкретную функцию потерь в ''оригинальной работе''<ref>[https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/MSR-TR-2010-82.pdf From RankNet to LambdaRank to LambdaMART]</ref> выбирают как логистическую функцию потерь, те <center>при <tex>\mathbb{L}(M) =log(1+ e^{-\sigma M})</tex> и алгоритме <tex>a(x) = \langle w,x\rangle </tex>, где</center><tex>\sigma -</tex> масштабирующий параметр для пересчета значения отступа <tex>M</tex> в вероятностное значение. ==== Подход ==== Воспользовавшись методом стохастического градиентного спуска, выбираем на каждой <tex>i-</tex>ой итерации случайным образом запрос <tex>q \in Q</tex> и пару документов из запроса <tex> i\prec j </tex>, получаем итеративную формулу вычисления весов: <center><tex> w = w + \eta \frac{\sigma }{1 + e(\sigma \langle x_j - x_i,w\rangle)}\cdot (x_j - x_i) </tex></center>Чтобы перейти к использованию негладких функционалов MAP, NDCD, pFound необходимо домножить <tex>1 + e(\sigma \langle x_j - x_i,w\rangle)</tex> на изменение данного функционала при перестановке местами <tex>x_i</tex> и <tex>x_j</tex> в каждой итерации. Это означает, как изменится веса модели, если в задаче ранжирования поменять местами два документа. Результаты оценки алгоритма с разным функционалом представлены на [[Медиа:LambdaRank.png|рисунке 2]]. '''LambdaRank''' моделирует следующий итеративный процесс:<center><tex> w = w + \eta \frac{\sigma }{1 + e(\sigma \langle x_j - x_i,w\rangle)}\cdot |\Delta NDCD_{i,j}| \cdot (x_j - x_i) </tex></center>Оптмизируется тем самым по функционалу NDCD. === SoftRank ===----'''SoftRank''' {{---}} списочный метод ранжирования, который предполагает использовать ''сглаживание''<ref>[https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.469.3608&rep=rep1&type=pdf SoftRank: Optimizing Non-Smooth Rank Metrics]</ref> для возможности диффиренцирования значения сложной метрики. ==== Постановка задачи ==== Сперва необходимо перейти от поиска изначально детерминированного положения документа в отранижрованном порядке к случайной величине, распределенной по нормальному закону так, чтобы центр распределения лежал в предсказании функции ранжирования, как представлено на [[Медиа:SoftRank_F.png|рисунке 3]]. Величина дисперсии теперь также параметр модели:<center><tex> p(d_i)=\mathbb{N}(d_i|\overline{d_i}\cdot \sigma^2_{d_i}) = \mathbb{N}(d_i |a(w,x_i),\cdot \sigma^2_{d_i})</tex></center>{|align="center" |[[Файл:SoftRank_F.png|thumb|550px|Рис. 3. Сглаживание в SoftRank]] |}Возможно оценить вероятность того, что некий документ <tex>d_i-</tex>й окажется выше <tex>j-</tex>го. <center><tex>\pi_{i,j}\equiv P(d_i-d_j > 0) = \int\limits_0^\infty \mathbb{N}(d | \overline{d_i} - \overline{d_j}, 2 \sigma^2_{d_i})ds </tex></center> Теперь задача формулируется следующим образом: '''оценить вероятность''' того, что <tex>i-</tex>й документ окажется на позиции <tex>r</tex>. ==== Подход ====[[Файл:SR_pr.png|350px|thumb|Рис. 4. Рекурсивное вычисление вероятности]]Вычисления происходят рекурсивно для каждого <tex>j-</tex>го документа. <br /><tex>N=1</tex>. Оценить вероятность оказаться на <tex>r-</tex>м месте для <tex>1</tex> элемента: <br /><tex> p_j^1(r)=\delta (r)</tex> <br /><br /><tex>N=2</tex>. Тогда вероятность оказаться на <tex>1-</tex>м и <tex>2-</tex>м месте для двух документов: <br /><tex> p_j^2(0)=1 - \pi_{1,j}</tex> <br /><tex> p_j^2(1)=\pi_{1,j}</tex> <br /><br /><tex>N=3</tex>. Для выборки из <tex>3-</tex>х элементов, вероятность оказаться на первом месте: <br /><tex> p_j^3(1)=p_j^2(0)\cdot \pi_{2,j} + p_j^{i-1}(1)\cdot (1- \pi_{2,j}) </tex> <br />и т.д. <br />Графическая интерпритация вычислительного процесса представлена на [[Медиа:SR_pr.png|рисунке 4.]]   Чтобы использовать метрику NDCG '''необходимо''' учесть математическое ожидание ассесорской оценки <tex>M[D(r_j)]</tex>, что уже дает гладкий функционал:<center><tex>SoftNDCG=G_{max}^{-1}\cdot \sum_{i=1}^N g(l_i) \sum_{r=0}^{N-1}D(r_j)p_j(r)</tex></center>Данное выражения уже возможно оптимизировать градиентом:<center><tex>\Large {\frac{\delta \mathbb {G} }{\delta \overline{d_m}} =G_{max}^{-1}\cdot \sum_{i=1}^N g(l_i) \sum_{r=0}^{N-1}D(r_j)\frac{\delta p_j(r) }{\delta \overline{d_i} } } </tex></center><tex>\displaystyle {\frac{\delta p_j(r) }{\delta \overline{d_m} } }</tex> вычислятся через <tex>\displaystyle { \frac{\delta \pi_{i,j} }{\delta \overline{d_m}} }</tex>: <center><tex>\displaystyle { \frac{\delta \pi_{i,j} }{\delta \overline{d_m}} } = \begin{cases} \mathbb{N}(0 | \overline{d_m} - \overline{d_j}, 2 \sigma^2_{d_s}) \; m =i, m \ne j \\ \mathbb{N}(0 | \overline{d_i} - \overline{d_m}, 2 \sigma^2_{d_s}) \; m \ne i, m = j \\ 0 \; m \ne i, m \ne j \end{cases} </tex></center>

=== Сильное ранжирование Источники информации ==* [https://www.sciencedirect.com/science/article/pii/0898122196001022 A weak approach to group ranking ] * [https://users.metu.edu.tr/serge/courses/111-2011/textbook-math111.pdf How to prove it. A Structured Approach ]* [https://sphere.mail.ru/curriculum/program/discipline/102/ Инфопоиск от Mail.Group ]* [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) Курс лекций по машинному обучению] {{---}} Воронцов К.В.