Дополнение к ранжированию — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (refs)
м (rollbackEdits.php mass rollback)
 
(не показано 12 промежуточных версий 2 участников)
Строка 1: Строка 1:
  
  
== Порядки ==
 
 
При рассмотрении различных ситуаций, связанных с извлечением экспертных знаний, возникает потребность каким-либо упорядочить все множество оценок, затрагивая уже понятие группового ранжирования.  
 
При рассмотрении различных ситуаций, связанных с извлечением экспертных знаний, возникает потребность каким-либо упорядочить все множество оценок, затрагивая уже понятие группового ранжирования.  
Положим, имеется конечное множество &Chi; объектов (например, экспертных оценок или критериев) и <tex>m</tex> экспертов, пронумерованных индексами <tex>1,2... m</tex>. Каждый <tex>i-</tex>й эксперт выставляет рейтинг, порождая порядок.
+
Положим, имеется конечное множество <tex>X</tex> объектов (например, экспертных оценок или критериев) и <tex>m</tex> экспертов, пронумерованных индексами <tex>1,2... m</tex>. Каждый <tex>i-</tex>й эксперт выставляет рейтинг, порождая порядок. Подобные тип задач в машинном обучении обозначается как ранжирование. <br \>
 +
'''Ранжирование''' (англ. ''learning to rank'') {{---}} особый тип задач [[Машинное обучение |машиного обучения ]], связанный с постороением некой ранжирующей модели по обучащей выборке. Отличие от классификации и регрессии состоит в том, что для обучающей выборки не заданы ответы, однако задано [[Отношение порядка |отношение порядка]] для пары объектов. Стоит отметить, что от отношения порядка на множестве объектов изменяется и подход к ранжированию.
 +
 
  
 
== Слабое ранжирование.Представления ==
 
== Слабое ранжирование.Представления ==
Строка 44: Строка 45:
 
* '''эквивалентность''': для <tex>a \sim b</tex> ''тогда и только тогда'', когда <tex>u(a)=u(b)</tex>.
 
* '''эквивалентность''': для <tex>a \sim b</tex> ''тогда и только тогда'', когда <tex>u(a)=u(b)</tex>.
  
''Ограничения'':
+
''Ограничения'': <br \>
:- Лексикографические предпочтения   
+
Лексикографические предпочтения. Ранжирующая функция может быть определена на любом конечном множестве, однако для случая лексикографического порядка функция не определена на <tex>R^n</tex>. <br \>
<tex>\; \;</tex> Хоть и на любом конечном множестве может определена ранжирующая функция, однако для случая лексикографического порядка функция не определена на <tex>R^n</tex>.  
+
[[Отображения |Инъективность]]. В случае, если бы <tex>u</tex> являлась бы инъективной функцией, то класс эквивалентности двух элементов множества <tex>Y</tex> мог бы переходить в более широкий соответствующий класс на множестве <tex>X</tex>. <br \>
:- [[Отображения |Инъективность]]   
+
[[Отображения |Сюрьективность]]. Если на <tex>u</tex> вводятся ограничения, чтобы быть сюръективной функцией, то при отображении элементов некого класса на <tex>Y</tex> возможно соответствие ему меньшего или вовсе пустого класса на <tex>X</tex>.
<tex>\; \;</tex>В случае, если бы <tex>u</tex> являлась бы инъективной функцией, что класс эквивалентности двух элементов множества <tex>Y</tex> мог бы переходить в более широкий соответствующий класс на множестве <tex>X</tex>.
 
:- [[Отображения |Сюрьективность]]
 
<tex>\; \;</tex>Если на <tex>u</tex> вводятся ограничения, чтобы быть сюръективной функцией, то при отображении элементов некого класса на <tex>Y</tex> возможно соответствие ему меньшего или вовсе пустого класса на <tex>X</tex>.
 
  
 
====== Кусочная последовательность ======
 
====== Кусочная последовательность ======
Строка 77: Строка 75:
 
}}
 
}}
 
====== Интервальный метод ======
 
====== Интервальный метод ======
Имея заданный функционал <tex> u: X \rightarrow Y :</tex> и <\xi> возможно использование интервального сравнения, а именно {{---}} объекты считаются сравнимы, если значения их оценок лежат в некотором интервале.  
+
Имея заданный функционал <tex> u: X \rightarrow Y :</tex> и <tex>\xi</tex> возможно использование интервального сравнения, а именно {{---}} объекты считаются сравнимы, если значения их оценок лежат в некотором интервале.  
 
Так, например, если <tex>a<b</tex>, то <tex>[u(a),u(b)-1]</tex>.
 
Так, например, если <tex>a<b</tex>, то <tex>[u(a),u(b)-1]</tex>.
  
 
''Ограничения'':
 
''Ограничения'':
 +
 
Если у данного частичного ранжирования существует несчетное множество строго упорядоченных объектов, то невозможно подобрать такую <tex>u</tex>. В противовес, любое конечное частичное ранжирование может быть описано с помощью <tex>u</tex>.
 
Если у данного частичного ранжирования существует несчетное множество строго упорядоченных объектов, то невозможно подобрать такую <tex>u</tex>. В противовес, любое конечное частичное ранжирование может быть описано с помощью <tex>u</tex>.
 
  
 
== Сильное ранжирование ==
 
== Сильное ранжирование ==
Строка 104: Строка 102:
 
====== Последовательность ======
 
====== Последовательность ======
 
Для любого конечного множества <tex>X</tex>, на котором задано отношение сильного упорядочивания и <tex>\exists u: X \rightarrow Y </tex>, может быть применимо моделирование с помощью порождения последовательности значений элементов.  
 
Для любого конечного множества <tex>X</tex>, на котором задано отношение сильного упорядочивания и <tex>\exists u: X \rightarrow Y </tex>, может быть применимо моделирование с помощью порождения последовательности значений элементов.  
Иными словами, задается новый функционал <tex> v: Y \rightarrow \mathbb{N} </tex>, что все оценки образуют последовательность.
+
Иными словами, задается новый функционал <tex> v: Y \rightarrow \mathbb{N} </tex>, что все оценки образуют последовательность.  
 +
 
 
''Ограничения'':
 
''Ограничения'':
  
<tex>\; </tex>Как и для частичного, оно должно быть конечно.
+
<tex>\; </tex>Как и для частичного, множество <tex>X</tex> должно быть конечно.
  
 
== Supervised алгоритмы ранжирования ==
 
== Supervised алгоритмы ранжирования ==
 
=== OC-SVM ===
 
=== OC-SVM ===
Ordinal Classification SVM - алгоритм поточечного ранжирования, рассматривающий каждый объект обособленно. В основе стоит использования идеи [[Метод опорных векторов (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>  
 
Пусть имеется некое число градаций (оценок, предпочтений) <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>
 
<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]].
+
Основное отличие от классического подхода в том, что на имеющееся <tex>K</tex> границ необходимо найти <tex>K-1</tex> зазоров. Иными словами, необходимо '''найти один направляющий вектор''' <tex>K-1</tex> числа гиперплоскостей. Исходим от предположения, что найдется такое направление, в котором объекты удовлетворительно отранжировались. Пример такого разделения для <tex>K=5</tex> представлен на [[Медиа:OC-svm.PNG|рисунке 1]].
 
{|align="center"
 
{|align="center"
 
  |-valign="top"
 
  |-valign="top"
Строка 159: Строка 158:
 
Воспользовавшись методом стохастического градиентного спуска, выбираем на каждой <tex>i-</tex>ой итерации случайным образом запрос <tex>q \in Q</tex> и пару документов из запроса <tex> i\prec j </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>
 
<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]].
+
Чтобы перейти к использованию негладких функционалов 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''' моделирует следующий итеративный процесс:
 
'''LambdaRank''' моделирует следующий итеративный процесс:
Строка 169: Строка 168:
 
'''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''' {{---}} списочный метод ранжирования, который предполагает использовать ''сглаживание''<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]]. Величина дисперсии теперь также параметр модели:
+
Сперва необходимо перейти от поиска изначально детерминированного положения документа в отранижрованном порядке к случайной величине, распределенной по нормальному закону так, чтобы центр распределения лежал в предсказании функции ранжирования, как представлено на [[Медиа: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>
 
<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"
 
{|align="center"
Строка 190: Строка 189:
 
<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 />
 
<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 />
 
и т.д. <br />
Графическая интерпритация вычислительного процесса представлена на [[Медиа:SR_pr.png|рис. 4.]]  
+
Графическая интерпритация вычислительного процесса представлена на [[Медиа:SR_pr.png|рисунке 4.]]  
  
  

Текущая версия на 19:26, 4 сентября 2022


При рассмотрении различных ситуаций, связанных с извлечением экспертных знаний, возникает потребность каким-либо упорядочить все множество оценок, затрагивая уже понятие группового ранжирования. Положим, имеется конечное множество [math]X[/math] объектов (например, экспертных оценок или критериев) и [math]m[/math] экспертов, пронумерованных индексами [math]1,2... m[/math]. Каждый [math]i-[/math]й эксперт выставляет рейтинг, порождая порядок. Подобные тип задач в машинном обучении обозначается как ранжирование.
Ранжирование (англ. learning to rank) — особый тип задач машиного обучения , связанный с постороением некой ранжирующей модели по обучащей выборке. Отличие от классификации и регрессии состоит в том, что для обучающей выборки не заданы ответы, однако задано отношение порядка для пары объектов. Стоит отметить, что от отношения порядка на множестве объектов изменяется и подход к ранжированию.


Слабое ранжирование.Представления

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

Определение:
Бинарное отношение [math]\lt [/math] на множестве [math]X\times X[/math], которое является частично упорядоченным, называется слабым упорядочиванием (англ. weak ordering), если оно обладает следующими свойствами:
  • Иррефлексивность (англ. irreflexivity): [math]\forall a \in X:[/math] [math]a \lt b[/math] - не выполняется.
  • Ассиметричность (англ. asymmetry): [math]\forall a, b \in X:[/math] если [math]a \lt b[/math], то не [math] b \lt a [/math].
  • Транзитивность (англ. transitivity): [math]\forall a, b, c \in X:[/math] если [math]a\lt b[/math] и [math]b\lt c[/math], то [math]a\lt c[/math].
  • Транзитивность несравнимости (англ. transitivity of incomparability): [math]\forall a, b, d \in X:[/math] если [math]a[/math] несравнимо с [math]b[/math], и [math]b[/math] не сравнимо с [math]d[/math], то [math]a[/math] несравнимо с [math]d[/math].
Примечание: Строгое определение несравнимости: [math]\forall a, b \in X:[/math], если [math]¬b\lt a[/math] и [math]¬a\lt b[/math] и [math]a\not=b[/math], то [math]a\sim b[/math].


Рассмотрим случаи, определеяющее частичное упорядочение как:

  • Сильное: [math]\forall a, b \in X:[/math] [math]a \lt b[/math] и [math]b \lt a[/math], то есть если ~ [math]\emptyset[/math].
  • Слабое[1]: [math]\forall a, b, c \in X:[/math] если [math]a\sim b\sim c[/math], то [math]a\sim b[/math] и [math]a=c[/math].

Можно заключить, что любое cильное упорядовачивание есть слабое. Отношение несравнимости является отношением эквивалентности для всех своих разбиений на множестве [math]X[/math], что являются линейно упорядоченными.

Сильный подпорядок

Определение:
Сильный подпорядок — такой подпорядок, на котором присутствует отношение связанности.

Сильный подпорядок [math]\le \; \in X\times X[/math] обладает рядом следующих свойств:

  • Транзитивность: [math]\forall a, b, c \in X:[/math] если [math]a≤b[/math] и [math]b≤c \Rightarrow a≤c[/math].
  • Связанности: [math]\forall a, b \in X:[/math] выполнимо либо [math]a≤b[/math], либо [math]b≤a[/math].

Если в любом сильном подпорядке [math]\exists a,b : a≤b[/math] и [math]b≤a[/math], то на нем определено отношение эквивалентности. Поскольку операция определена для всех элементов, такие подпорядки еще называют отношением предпочтения[2].

Сравнения

Вещественная функция

Удобство использования слабого ранжирования в том, что его элементы могут быть представлены единственным образом с помощью вещественных функций. Рассмотрим следующую теорему.

Теорема:
Для любого частичного упорядочивания [math]\lt \in X\times X[/math] слабое тогда и только тогда, когда существует [math]\lt _t\in Y\times Y[/math] и отображение [math] u: X \rightarrow Y :[/math] если [math]a\lt b[/math], то [math]u(a) \lt _t u(b)[/math] и наоборот.

Таким образом, чтобы имели место быть:

  • частичный подпорядок: для [math]a≤b[/math] тогда и только тогда, когда [math]u(a)≤u(b)[/math].
  • эквивалентность: для [math]a \sim b[/math] тогда и только тогда, когда [math]u(a)=u(b)[/math].

Ограничения:
Лексикографические предпочтения. Ранжирующая функция может быть определена на любом конечном множестве, однако для случая лексикографического порядка функция не определена на [math]R^n[/math].
Инъективность. В случае, если бы [math]u[/math] являлась бы инъективной функцией, то класс эквивалентности двух элементов множества [math]Y[/math] мог бы переходить в более широкий соответствующий класс на множестве [math]X[/math].
Сюрьективность. Если на [math]u[/math] вводятся ограничения, чтобы быть сюръективной функцией, то при отображении элементов некого класса на [math]Y[/math] возможно соответствие ему меньшего или вовсе пустого класса на [math]X[/math].

Кусочная последовательность

Для любого конечного множества [math]X[/math], на котором задано отношение слабого упорядовачивания и [math]\exists u: X \rightarrow Y [/math], может быть применимо моделирование с помощью кусочных последовательностей. Рассмотрим пример. Положим, что

[math]X=\{ a, b, c, d, e \}[/math]
[math]u(a) = u(c) = 0, u(e) = 2, u(b) = u(d) = 5[/math]

Тогда слабое ранжирование [math]\lt [/math] представляется в виде следующего:

[math]\{ a, c \} \{ e \} \{ b, d \} [/math]

Частичное ранжирование

Определение:
Бинарное отношение [math]\lt [/math] на множестве [math]X \times X[/math], для некоторых элементов которого определена несравнимость [math]\sim[/math],называется частичным упорядочиванием (англ. semiorder), если оно обладает следующими свойствами:
  • Иррефлексивность (англ. irreflexivity): [math]\forall a \in X:[/math][math]a \sim a[/math].
  • Ассиметричность (англ. asymmetry): [math]\forall a, b \in X:[/math] если [math]a \lt b[/math], то не [math] b \lt a [/math].
  • Транзитивность (англ. transitivity): [math]\forall a, b, c, d \in X:[/math] если [math]a\lt b, \; b\sim c[/math] и [math]c\lt d[/math], то [math]a\lt d[/math].
  • Критерий сравнимости: [math]\forall a, b, c, d \in X:[/math] если [math]a\lt b[/math], и [math]b\lt c[/math], то либо [math]a\lt d[/math], либо [math]d\lt c[/math].
Примечание: не стоит путать последний критерий с слабым упорядочиванием, где отношение несравнимости транзитивно. Здесь же речь ведется о том, что среди [math]a,b,c \;d[/math] должен быть хотя бы один элемент сравним c данным.

Сравнения

Вещественная функция

Частичное ранжирование поддается тому же функциональному подходу к сравнению за тем лишь исключением, что для численных значений объектов вводится некоторая погрешность [math]\xi[/math], внутри которой объекты считаются сравнимы, снаружи - нет. Зачастую такую погрешность выбирают нормированной к [math]1[/math].

Теорема:
Для любого конечного частичного упорядочиванием [math]\lt \in X\times X[/math] возможно определить такое [math]\xi[/math] и функционал [math] u: X \rightarrow Y :[/math] если [math]a\lt b[/math], то [math]u(a) \le u(b) - \xi[/math] и наоборот.
Интервальный метод

Имея заданный функционал [math] u: X \rightarrow Y :[/math] и [math]\xi[/math] возможно использование интервального сравнения, а именно — объекты считаются сравнимы, если значения их оценок лежат в некотором интервале. Так, например, если [math]a\lt b[/math], то [math][u(a),u(b)-1][/math].

Ограничения:

Если у данного частичного ранжирования существует несчетное множество строго упорядоченных объектов, то невозможно подобрать такую [math]u[/math]. В противовес, любое конечное частичное ранжирование может быть описано с помощью [math]u[/math].

Сильное ранжирование

Определение:
Бинарное отношение [math]\lt [/math] на множестве [math]X \times X[/math], для некоторых элементов которого определена несравнимость [math]\sim[/math],называется сильным ранжированием (англ. total order), если оно обладает следующими свойствами:
  • Иррефлексивность (англ. irreflexivity): [math]\forall a \in X:[/math] [math]a \sim a[/math].
  • Ассиметричность (англ. asymmetry): [math]\forall a, b \in X:[/math] если [math]a \lt b[/math], то не [math] b \lt a [/math].
  • Транзитивность (англ. transitivity): [math]\forall a, b, c, d \in X:[/math] если [math]a\lt b, \; b\sim c[/math] и [math]c\lt d[/math], то [math]a\lt d[/math].
  • Критерий сравнимости: [math]\forall a, b, c, d \in X:[/math] если [math]a\lt b[/math], и [math]b\lt c[/math], то либо [math]a\lt d[/math], либо [math]d\lt c[/math].
  • Трихотомия (англ. trichotomy): [math]\forall a, b \in X:[/math] [math]x\lt y \vee y\lt x \vee x=y [/math] выполняется.

Таким образом, сильное ранжирование — строгое слабое, для которого [math]\sim \emptyset[/math].

Сравнения

Вещественная функция

Сильное ранжирование сравнивается с помощью функционала [math]u[/math].

Лемма:
Для любого конечного сильного упорядочивания [math]\le \in X\times X[/math] возможно определить такой функционал [math] u: X \rightarrow Y :[/math] если [math]a\le b[/math], то [math]u(a) \le u(b)[/math] и наоборот.
Последовательность

Для любого конечного множества [math]X[/math], на котором задано отношение сильного упорядочивания и [math]\exists u: X \rightarrow Y [/math], может быть применимо моделирование с помощью порождения последовательности значений элементов. Иными словами, задается новый функционал [math] v: Y \rightarrow \mathbb{N} [/math], что все оценки образуют последовательность.

Ограничения:

[math]\; [/math]Как и для частичного, множество [math]X[/math] должно быть конечно.

Supervised алгоритмы ранжирования

OC-SVM

Ordinal Classification SVM — алгоритм поточечного ранжирования, рассматривающий каждый объект обособленно. В основе стоит использования идеи метода опорных векторов о проведении разделяющей гиперплоскости над множеством оценок.

Постановка задачи

Пусть имеется некое число градаций (оценок, предпочтений) [math]K[/math], тогда [math]Y=\{1,2 ...K\}[/math] — ранжирующая функция с порогами
[math]b_0=-\infty[/math], [math]b_1,b_2 ...b_{K-1} \in R, b_k=\infty:[/math]
[math]a(x)=y[/math], если [math]b_{y-1}\lt (w,x)\le b_y [/math]

Основное отличие от классического подхода в том, что на имеющееся [math]K[/math] границ необходимо найти [math]K-1[/math] зазоров. Иными словами, необходимо найти один направляющий вектор [math]K-1[/math] числа гиперплоскостей. Исходим от предположения, что найдется такое направление, в котором объекты удовлетворительно отранжировались. Пример такого разделения для [math]K=5[/math] представлен на рисунке 1.

Рис. 1. Направляющий вектор для [math]K=5[/math]

Подход

Поскольку теперь увеличилось число зазоров, классического значения штрафа [math]\xi[/math] недостаточно — необходимы штрафы [math]\xi^*_i[/math] и [math]\xi_i[/math] для нарушение с левой и правой сторон соответственно [math]i-[/math]ой границы. Ограничительное условие для такого случая состоит в том, что произвольный объект [math]x_i[/math], оказавшийся между разделяющими полосами, не должен выйти за их пределы ни слева, ни справа, что можно записать как:

[math]b_{y_i-1}+1-\xi^*_i \le \langle w_i,x_i\rangle \le b_{y_i}-1+\xi_i [/math]

Для случая крайних границ, для объектов [math]x_i : \hat{K}=1[/math] может существовать только нарушение слева от границы, когда для объектов [math]x_i : \hat{K}=K[/math] — только справа от границы. Таким образом, задача может быть сформирована как задача минимизации с ограничениями:

[math] \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} [/math]

Ranking SVM


Алгоритм для попарного подхода[3] к ранжированию. Основное отличие от алгоритма SVM в том, что теперь объекты нумеруются попарно.

Постановка задачи

Считаем, что теперь решаем следующую оптимизационную задачу:

[math]Q(a) = \frac{1}{2}|w||^2 + C\sum_{i=1}^l(\mathbb{L}(a(x_j) - a(x_i)) \rightarrow \underset{a}{min}[/math], где
[math]a(x) = \langle w,x\rangle [/math] — функция ранжирования,
[math]\mathbb{L}(M) = (1-M)_+ [/math] — функция потерь,
[math]M=Margin(i,j) = \langle w,x_j-x_i\rangle [/math] — отступ.

Подход

Поскольку теперь все операции выполяняются уже для пары объектов, то строгая система ограничений будет отличаться в соответствующих местах:

[math] \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} [/math]

RankNet, LambdaRank


Данные алгоритмы применяются для списочного ранжирования, хотя по сути своей используют попарный подход, который был расширен до случая списка.

Рис. 2. LambdaRank с разными функционалами

Постановка задачи

Считаем, что у нас есть некий гладкий функционал качества, который необходимо оптимизировать:

[math]Q(a) = sum_{i\prec j}(\mathbb{L}(a(x_j) - a(x_i)) \rightarrow \underset{a}{min}[/math]

Конкретную функцию потерь в оригинальной работе[4] выбирают как логистическую функцию потерь, те

при [math]\mathbb{L}(M) =log(1+ e^{-\sigma M})[/math] и алгоритме [math]a(x) = \langle w,x\rangle [/math], где

[math]\sigma -[/math] масштабирующий параметр для пересчета значения отступа [math]M[/math] в вероятностное значение.

Подход

Воспользовавшись методом стохастического градиентного спуска, выбираем на каждой [math]i-[/math]ой итерации случайным образом запрос [math]q \in Q[/math] и пару документов из запроса [math] i\prec j [/math], получаем итеративную формулу вычисления весов:

[math] w = w + \eta \frac{\sigma }{1 + e(\sigma \langle x_j - x_i,w\rangle)}\cdot (x_j - x_i) [/math]

Чтобы перейти к использованию негладких функционалов MAP, NDCD, pFound необходимо домножить [math]1 + e(\sigma \langle x_j - x_i,w\rangle)[/math] на изменение данного функционала при перестановке местами [math]x_i[/math] и [math]x_j[/math] в каждой итерации. Это означает, как изменится веса модели, если в задаче ранжирования поменять местами два документа. Результаты оценки алгоритма с разным функционалом представлены на рисунке 2.

LambdaRank моделирует следующий итеративный процесс:

[math] 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) [/math]

Оптмизируется тем самым по функционалу NDCD.

SoftRank


SoftRank — списочный метод ранжирования, который предполагает использовать сглаживание[5] для возможности диффиренцирования значения сложной метрики.

Постановка задачи

Сперва необходимо перейти от поиска изначально детерминированного положения документа в отранижрованном порядке к случайной величине, распределенной по нормальному закону так, чтобы центр распределения лежал в предсказании функции ранжирования, как представлено на рисунке 3. Величина дисперсии теперь также параметр модели:

[math] 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})[/math]
Рис. 3. Сглаживание в SoftRank

Возможно оценить вероятность того, что некий документ [math]d_i-[/math]й окажется выше [math]j-[/math]го.

[math]\pi_{i,j}\equiv P(d_i-d_j \gt 0) = \int\limits_0^\infty \mathbb{N}(d | \overline{d_i} - \overline{d_j}, 2 \sigma^2_{d_i})ds [/math]

Теперь задача формулируется следующим образом: оценить вероятность того, что [math]i-[/math]й документ окажется на позиции [math]r[/math].

Подход

Рис. 4. Рекурсивное вычисление вероятности

Вычисления происходят рекурсивно для каждого [math]j-[/math]го документа.
[math]N=1[/math]. Оценить вероятность оказаться на [math]r-[/math]м месте для [math]1[/math] элемента:
[math] p_j^1(r)=\delta (r)[/math]

[math]N=2[/math]. Тогда вероятность оказаться на [math]1-[/math]м и [math]2-[/math]м месте для двух документов:
[math] p_j^2(0)=1 - \pi_{1,j}[/math]
[math] p_j^2(1)=\pi_{1,j}[/math]

[math]N=3[/math]. Для выборки из [math]3-[/math]х элементов, вероятность оказаться на первом месте:
[math] p_j^3(1)=p_j^2(0)\cdot \pi_{2,j} + p_j^{i-1}(1)\cdot (1- \pi_{2,j}) [/math]
и т.д.
Графическая интерпритация вычислительного процесса представлена на рисунке 4.


Чтобы использовать метрику NDCG необходимо учесть математическое ожидание ассесорской оценки [math]M[D(r_j)][/math], что уже дает гладкий функционал:

[math]SoftNDCG=G_{max}^{-1}\cdot \sum_{i=1}^N g(l_i) \sum_{r=0}^{N-1}D(r_j)p_j(r)[/math]

Данное выражения уже возможно оптимизировать градиентом:

[math]\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} } } [/math]

[math]\displaystyle {\frac{\delta p_j(r) }{\delta \overline{d_m} } }[/math] вычислятся через [math]\displaystyle { \frac{\delta \pi_{i,j} }{\delta \overline{d_m}} }[/math]:

[math]\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} [/math]

Примечания

Источники информации