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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Сильное ранжирование)
м (rollbackEdits.php mass rollback)
 
(не показано 25 промежуточных версий 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'') {{---}} особый тип задач [[Машинное обучение |машиного обучения ]], связанный с постороением некой ранжирующей модели по обучащей выборке. Отличие от классификации и регрессии состоит в том, что для обучающей выборки не заданы ответы, однако задано [[Отношение порядка |отношение порядка]] для пары объектов. Стоит отметить, что от отношения порядка на множестве объектов изменяется и подход к ранжированию.
 +
 
  
 
== Слабое ранжирование.Представления ==
 
== Слабое ранжирование.Представления ==
Строка 19: Строка 20:
 
Рассмотрим случаи, определеяющее частичное упорядочение как:
 
Рассмотрим случаи, определеяющее частичное упорядочение как:
 
* Сильное: <tex>\forall a, b \in X:</tex> <tex>a < b</tex> и <tex>b < a</tex>, то есть если ~ <tex>\emptyset</tex>.
 
* Сильное: <tex>\forall a, b \in X:</tex> <tex>a < b</tex> и <tex>b < a</tex>, то есть если ~ <tex>\emptyset</tex>.
* Слабое: <tex>\forall a, b, c \in X:</tex> если <tex>a\sim b\sim c</tex>, то <tex>a\sim b</tex> и <tex>a=c</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ильное упорядовачивание есть слабое.  
 
Можно заключить, что любое cильное упорядовачивание есть слабое.  
 
Отношение несравнимости является [[Отношение эквивалентности |отношением эквивалентности]] для всех своих разбиений на множестве <tex>X</tex>, что являются [[Упорядоченное множество |линейно упорядоченными]].
 
Отношение несравнимости является [[Отношение эквивалентности |отношением эквивалентности]] для всех своих разбиений на множестве <tex>X</tex>, что являются [[Упорядоченное множество |линейно упорядоченными]].
Строка 31: Строка 32:
 
* [[Отношение связности, компоненты связности |Связанности]]: <tex>\forall a, b \in X:</tex> выполнимо либо <tex>a&le;b</tex>, либо <tex>b&le;a</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>, то на нем определено [[Отношение эквивалентности |отношение эквивалентности]].  
 
Если в любом сильном подпорядке <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>.
  
 
=== Сравнения  ===
 
=== Сравнения  ===
====== '''Вещественная функция''' ======
+
====== Вещественная функция ======
 
Удобство использования слабого ранжирования в том, что его элементы могут быть представлены единственным образом с помощью вещественных функций. Рассмотрим следующую теорему.  
 
Удобство использования слабого ранжирования в том, что его элементы могут быть представлены единственным образом с помощью вещественных функций. Рассмотрим следующую теорему.  
 
{{Теорема|о слабом упорядочивании
 
{{Теорема|о слабом упорядочивании
Строка 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>.
 
  
====== '''Кусочная последовательность''' ======
+
====== Кусочная последовательность ======
 
Для любого конечного множества <tex>X</tex>, на котором задано отношение слабого упорядовачивания и <tex>\exists u: X \rightarrow Y </tex>, может быть применимо моделирование с помощью кусочных последовательностей.  
 
Для любого конечного множества <tex>X</tex>, на котором задано отношение слабого упорядовачивания и <tex>\exists u: X \rightarrow Y </tex>, может быть применимо моделирование с помощью кусочных последовательностей.  
 
Рассмотрим пример. Положим, что  
 
Рассмотрим пример. Положим, что  
Строка 70: Строка 68:
 
}}
 
}}
 
=== Сравнения ===
 
=== Сравнения ===
====== '''Вещественная функция''' ======
+
====== Вещественная функция ======
 
Частичное ранжирование поддается тому же функциональному подходу к сравнению за тем лишь исключением, что для численных значений объектов вводится некоторая погрешность <tex>\xi</tex>, внутри которой объекты считаются сравнимы, снаружи - нет. Зачастую такую погрешность выбирают нормированной к <tex>1</tex>.
 
Частичное ранжирование поддается тому же функциональному подходу к сравнению за тем лишь исключением, что для численных значений объектов вводится некоторая погрешность <tex>\xi</tex>, внутри которой объекты считаются сравнимы, снаружи - нет. Зачастую такую погрешность выбирают нормированной к <tex>1</tex>.
 
{{Теорема|о частичном упорядочивании
 
{{Теорема|о частичном упорядочивании
Строка 76: Строка 74:
 
Для любого конечного частичного упорядочиванием <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><\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> и наоборот.
 
}}
 
}}
<!-- Имея заданный функционал и <\xi> возможно использование интервального сравнения, а именно {{---}} объекты считаются сравнимы, если значения их оценок лежат в некоторой окрестности. -->
+
====== Интервальный метод ======
Ограничения:
+
Имея заданный функционал <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>u</tex>. В противовес, любое конечное частичное ранжирование может быть описано с помощью <tex>u</tex>.
  
Строка 92: Строка 94:
 
Таким образом, сильное ранжирование {{---}} строгое слабое, для которого <tex>\sim \emptyset</tex>.
 
Таким образом, сильное ранжирование {{---}} строгое слабое, для которого <tex>\sim \emptyset</tex>.
 
=== Сравнения ===
 
=== Сравнения ===
====== '''Вещественная функция''' ======
+
====== Вещественная функция ======
 
Сильное ранжирование сравнивается с помощью функционала <tex>u</tex>.
 
Сильное ранжирование сравнивается с помощью функционала <tex>u</tex>.
 
{{Лемма|о сильном упорядочивании
 
{{Лемма|о сильном упорядочивании
Строка 98: Строка 100:
 
Для любого конечного сильного упорядочивания <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>\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>\; </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</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"
  |[[Файл:OC-svm.PNG|thumb|540px|Направляющий вектор для K=5]]
+
  |[[Файл:OC-svm.PNG|thumb|540px|Рис. 1. Направляющий вектор для <tex>K=5</tex>]]
 
  |}
 
  |}
  
Строка 124: Строка 130:
 
=== Ranking SVM ===
 
=== Ranking SVM ===
 
----
 
----
Алгоритм для попарного подхода к ранжированию. Основное отличие от алгоритма SVM в том, что теперь объекты нумеруются попарно.
+
Алгоритм для ''попарного подхода''<ref>[https://www.cs.cornell.edu/people/tj/publications/joachims_02c.pdf Optimizing Search Engines using Clickthrough Data]</ref> к ранжированию. Основное отличие от алгоритма SVM в том, что теперь объекты нумеруются попарно.
  
 
==== Постановка задачи ====  
 
==== Постановка задачи ====  
Строка 138: Строка 144:
 
</center>
 
</center>
  
=== RankNet, LambdaRank ===
+
=== <nowiki>RankNet, LambdaRank</nowiki> ===
 
----
 
----
 
Данные алгоритмы применяются для списочного ранжирования, хотя по сути своей используют попарный подход, который был расширен до случая списка.  
 
Данные алгоритмы применяются для списочного ранжирования, хотя по сути своей используют попарный подход, который был расширен до случая списка.  
[[Файл:LambdaRank.png|thumb|420px|LambdaRank с разными функционалами]]
+
[[Файл: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>
 
<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>
+
<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>\sigma -</tex> масштабирующий параметр для пересчета значения отступа <tex>M</tex> в вероятностное значение.
  
 
==== Подход ====  
 
==== Подход ====  
 
Воспользовавшись методом стохастического градиентного спуска, выбираем на каждой <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> в каждой итерации. Это означает, как изменится веса модели, если в задаче ранжирования поменять местами два документа.
+
Чтобы перейти к использованию негладких функционалов 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''' моделирует следующий итеративный процесс:
Строка 160: Строка 166:
 
=== SoftRank ===
 
=== SoftRank ===
 
----
 
----
'''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>
 
<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"
  |[[Файл:SoftRank_F.png|thumb|550px|Сглаживание в SoftRank]]
+
  |[[Файл:SoftRank_F.png|thumb|550px|Рис. 3. Сглаживание в SoftRank]]
 
  |}
 
  |}
 
Возможно оценить вероятность того, что некий документ <tex>d_i-</tex>й окажется выше <tex>j-</tex>го.  
 
Возможно оценить вероятность того, что некий документ <tex>d_i-</tex>й окажется выше <tex>j-</tex>го.  
Строка 173: Строка 179:
  
 
==== Подход ====
 
==== Подход ====
[[Файл:SR_pr.png|350px|thumb|Рекурсивное вычисление]]
+
[[Файл:SR_pr.png|350px|thumb|Рис. 4. Рекурсивное вычисление вероятности]]
 
Вычисления происходят рекурсивно для каждого <tex>j-</tex>го документа.  <br />
 
Вычисления происходят рекурсивно для каждого <tex>j-</tex>го документа.  <br />
<tex>N=1</tex>. Оценить вероятность оказаться на r-м месте для 1 элемента:  <br />
+
<tex>N=1</tex>. Оценить вероятность оказаться на <tex>r-</tex>м месте для <tex>1</tex> элемента:  <br />
 
<tex> p_j^1(r)=\delta (r)</tex> <br /><br />
 
<tex> p_j^1(r)=\delta (r)</tex> <br /><br />
<tex>N=2</tex>. Тогда оказаться на 1-м и 2-м месте для двух документов:  <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(0)=1 - \pi_{1,j}</tex> <br />
 
<tex> p_j^2(1)=\pi_{1,j}</tex> <br /><br />
 
<tex> p_j^2(1)=\pi_{1,j}</tex> <br /><br />
<tex>N=3</tex>. Для выборки из 3-х элементов, вероятность оказаться на первом месте: <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 />
 
<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.]]
  
  
Строка 194: Строка 201:
 
       \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  
 
       \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>
 
         \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) Курс лекций по машинному обучению] {{---}} Воронцов К.В.

Текущая версия на 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]

Примечания

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