72
правки
Изменения
м
== Порядки ==
→intro
При рассмотрении различных ситуаций, связанных с извлечением экспертных знаний, возникает потребность каким-либо упорядочить все множество оценок, затрагивая уже понятие группового ранжирования.
Положим, имеется конечное множество Χ <tex>X</tex> объектов (например, экспертных оценок или критериев) и <tex>m</tex> экспертов, пронумерованных индексами <tex>1,2... m</tex>. Каждый <tex>i-</tex>й эксперт выставляет рейтинг, порождая порядок.Подобные тип задач в машинном обучении обозначается как ранжирование. <br \>'''Ранжирование''' (англ. ''learning to rank'') {{---}} особый тип задач [[Машинное обучение |машиного обучения ]], связанный с постороением некой ранжирующей модели по обучащей выборке. Отличие от классификации и регрессии состоит в том, что для обучающей выборки не заданы ответы, однако задано [[Отношение порядка |отношение порядка]] для пары объектов. Стоит отметить, что от отношения порядка на множестве объектов изменяется и подход к ранжированию.
== Слабое ранжирование.Представления ==
* '''эквивалентность''': для <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> 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>.
== Сильное ранжирование ==
====== Последовательность ======
Для любого конечного множества <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"
Воспользовавшись методом стохастического градиентного спуска, выбираем на каждой <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''' {{---}} списочный метод ранжирования, который предполагает использовать ''сглаживание''<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"
<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.]]
