1632
правки
Изменения
м
== Порядки ==
<!-- ====== Интервальный метод ======Имея заданный функционал <tex> u: X \rightarrow Y :</tex> и <tex>\xi</tex> возможно использование интервального сравнения, а именно {{---}} объекты считаются сравнимы, если значения их оценок лежат в некоторой окрестностинекотором интервале. Так, например, если <tex>a<b</tex>, то <tex>[u(a),u(b)--1]</tex>. ''Ограничения'':
rollbackEdits.php mass rollback
При рассмотрении различных ситуаций, связанных с извлечением экспертных знаний, возникает потребность каким-либо упорядочить все множество оценок, затрагивая уже понятие группового ранжирования.
Положим, имеется конечное множество Χ <tex>X</tex> объектов (например, экспертных оценок или критериев) и <tex>m</tex> экспертов, пронумерованных индексами <tex>1,2... m</tex>. Каждый <tex>i-</tex>й эксперт выставляет рейтинг, порождая порядок.Подобные тип задач в машинном обучении обозначается как ранжирование. <br \>'''Ранжирование''' (англ. ''learning to rank'') {{---}} особый тип задач [[Машинное обучение |машиного обучения ]], связанный с постороением некой ранжирующей модели по обучащей выборке. Отличие от классификации и регрессии состоит в том, что для обучающей выборки не заданы ответы, однако задано [[Отношение порядка |отношение порядка]] для пары объектов. Стоит отметить, что от отношения порядка на множестве объектов изменяется и подход к ранжированию.
== Слабое ранжирование.Представления ==
Рассмотрим случаи, определеяющее частичное упорядочение как:
* Сильное: <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>, что являются [[Упорядоченное множество |линейно упорядоченными]].
* [[Отношение связности, компоненты связности |Связанности]]: <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>.
=== Сравнения ===
====== '''Вещественная функция''' ======
Удобство использования слабого ранжирования в том, что его элементы могут быть представлены единственным образом с помощью вещественных функций. Рассмотрим следующую теорему.
{{Теорема|о слабом упорядочивании
* '''эквивалентность''': для <tex>a \sim b</tex> ''тогда и только тогда'', когда <tex>u(a)=u(b)</tex>.
''Ограничения'':<br \>:- Лексикографические предпочтения . <tex>\; \;</tex> Хоть и Ранжирующая функция может быть определена на любом конечном множестве может определена ранжирующая функция, однако для случая лексикографического порядка функция не определена на <tex>R^n</tex>. <br \>:- [[Отображения |Инъективность]] . <tex>\; \;</tex>В случае, если бы <tex>u</tex> являлась бы инъективной функцией, что то класс эквивалентности двух элементов множества <tex>Y</tex> мог бы переходить в более широкий соответствующий класс на множестве <tex>X</tex>.<br \>:- [[Отображения |Сюрьективность]] <tex>\; \;</tex>. Если на <tex>u</tex> вводятся ограничения, чтобы быть сюръективной функцией, то при отображении элементов некого класса на <tex>Y</tex> возможно соответствие ему меньшего или вовсе пустого класса на <tex>X</tex>.
====== '''Кусочная последовательность''' ======
Для любого конечного множества <tex>X</tex>, на котором задано отношение слабого упорядовачивания и <tex>\exists u: X \rightarrow Y </tex>, может быть применимо моделирование с помощью кусочных последовательностей.
Рассмотрим пример. Положим, что
}}
=== Сравнения ===
====== '''Вещественная функция''' ======
Частичное ранжирование поддается тому же функциональному подходу к сравнению за тем лишь исключением, что для численных значений объектов вводится некоторая погрешность <tex>\xi</tex>, внутри которой объекты считаются сравнимы, снаружи - нет. Зачастую такую погрешность выбирают нормированной к <tex>1</tex>.
{{Теорема|о частичном упорядочивании
Для любого конечного частичного упорядочиванием <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</tex>. В противовес, любое конечное частичное ранжирование может быть описано с помощью <tex>u</tex>.
Таким образом, сильное ранжирование {{---}} строгое слабое, для которого <tex>\sim \emptyset</tex>.
=== Сравнения ===
====== '''Вещественная функция''' ======
Сильное ранжирование сравнивается с помощью функционала <tex>u</tex>.
{{Лемма|о сильном упорядочивании
Для любого конечного сильного упорядочивания <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>]]
|}
=== Ranking SVM ===
----
Алгоритм для ''попарного подхода ''<ref>[https://www.cs.cornell.edu/people/tj/publications/joachims_02c.pdf Optimizing Search Engines using Clickthrough Data]</ref> к ранжированию. Основное отличие от алгоритма SVM в том, что теперь объекты нумеруются попарно.
==== Постановка задачи ====
</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''' моделирует следующий итеративный процесс:
=== 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>го.
==== Подход ====
[[Файл: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.]]
\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) Курс лекций по машинному обучению] {{---}} Воронцов К.В.
