1632
правки
Изменения
м
== Порядки ==
rollbackEdits.php mass rollback
При рассмотрении различных ситуаций, связанных с извлечением экспертных знаний, возникает потребность каким-либо упорядочить все множество оценок, затрагивая уже понятие группового ранжирования.
Положим, имеется конечное множество Χ <tex>X</tex> объектов (например, экспертных оценок или критериев) и ''<tex>m'' </tex> экспертов, пронумерованных индексами <tex>1,2... m</tex>. каждый ''Каждый <tex>i-</tex>й'' эксперт выставляет рейтинг, порождая порядок. Подобные тип задач в машинном обучении обозначается как ранжирование. <br \>'''Ранжирование''' (англ. ''learning to rank'') {{---}} особый тип задач [[Машинное обучение |машиного обучения ]], связанный с постороением некой ранжирующей модели по обучащей выборке. Отличие от классификации и регрессии состоит в том, что для обучающей выборки не заданы ответы, однако задано [[Отношение порядка |отношение порядка]] для пары объектов. Стоит отметить, что от отношения порядка на множестве объектов изменяется и подход к ранжированию.
== Слабое ранжирование.Представления ==
=== Слабое Строгое слабое упорядовачивание ===
{{Определение
|definition =
[[Бинарное отношение]] <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> - не выполняется.
* [[Симметричное отношение|Ассиметричность]] (англ. ''asymmetry''): <tex>\forall a, b \in X:</tex> если <tex>a < b</tex>, то не <tex> b < a </tex>.
* [[Транзитивное отношение|Транзитивность]] (англ. ''transitivity''): <tex>\forall a, b, c \in X:</tex> если <tex>a<b</tex> и <tex>b<c</tex>, то <tex>a<c</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\sim b</tex> и <tex>a=c</tex>.
Можно заключить, что любое cильное упорядовачивание есть слабое.
Отношение несравнимости является [[Отношение эквивалентности |отношением эквивалентности]] для всех своих разбиений на множестве <tex>X</tex>, что являются [[Упорядоченное множество |линейно упорядоченными]].
=== Сильный подпорядок ===
|definition='''Сильный подпорядок''' {{---}} такой подпорядок, на котором присутствует [[Отношение связности, компоненты связности |отношение связанности]].
}}
Сильный подпорядок <tex>&\le\; \in XxXX\times X</tex> обладает рядом следующих свойств:* [[Транзитивное отношение|Транзитивность]]: <tex>\forall a, b, c \in X:</tex>, если <tex>a≤b</tex> и <tex>b≤c \Rightarrow a≤c</tex>.* [[Отношение связности, компоненты связности |Связанности]]: <tex>\forall a, b \in X:</tex>выполнимо либо <tex>a≤b</tex>, либо <tex>b≤a</tex>.
Если в любом сильном подпорядке <tex>\exists a,b : a≤b</tex> и <tex>b≤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 XxXX\times X</tex> '''слабое''' ''тогда и только тогда'', когда существует <tex><_t\in YxYY\times Y</tex> и отображение <tex> u: X \rightarrow Y :</tex> если <tex>a<b</tex>, то <tex>u(a) <_t 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>\{ 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>
== Примечания ==
<references/>
== Источники информации ==
* [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) Курс лекций по машинному обучению] {{---}} Воронцов К.В.
