Дополнение к ранжированию — различия между версиями
(→Слабое ранжирование) |
(→RankNet, LambdaRank) |
||
(не показано 7 промежуточных версий этого же участника) | |||
Строка 5: | Строка 5: | ||
Положим, имеется конечное множество Χ объектов (например, экспертных оценок или критериев) и ''m'' экспертов, пронумерованных индексами 1,2... m. каждый ''i-й'' эксперт выставляет рейтинг, порождая порядок. | Положим, имеется конечное множество Χ объектов (например, экспертных оценок или критериев) и ''m'' экспертов, пронумерованных индексами 1,2... m. каждый ''i-й'' эксперт выставляет рейтинг, порождая порядок. | ||
− | == Слабое ранжирование == | + | == Слабое ранжирование.Представления == |
=== Слабое упорядовачивание === | === Слабое упорядовачивание === | ||
{{Определение | {{Определение | ||
Строка 14: | Строка 14: | ||
* [[Транзитивное отношение|Транзитивность]] (англ. ''transitivity''): <tex>\forall a, b, c \in X:</tex> если <tex>a<b</tex> и <tex>b<c</tex>, то <tex>a<c</tex>. | * [[Транзитивное отношение|Транзитивность]] (англ. ''transitivity''): <tex>\forall a, b, c \in X:</tex> если <tex>a<b</tex> и <tex>b<c</tex>, то <tex>a<c</tex>. | ||
* [[Транзитивное отношение|Транзитивность несравнимости]] (англ. ''transitivity of incomparability''): <tex>\forall a, b, d \in X:</tex> если <tex>a</tex> несравнимо с <tex>b</tex>, и <tex>b</tex> не сравнимо с <tex>d</tex>, то <tex>a</tex> несравнимо с <tex>d</tex>. | * [[Транзитивное отношение|Транзитивность несравнимости]] (англ. ''transitivity of incomparability''): <tex>\forall a, b, d \in X:</tex> если <tex>a</tex> несравнимо с <tex>b</tex>, и <tex>b</tex> не сравнимо с <tex>d</tex>, то <tex>a</tex> несравнимо с <tex>d</tex>. | ||
− | Примечание: Строгое определение несравнимости: <tex>\forall a, b \in X:</tex>, если <tex>¬b<a</tex> и <tex>¬a<b</tex> и <tex>a\not=b</tex>, то <tex>a | + | Примечание: Строгое определение несравнимости: <tex>\forall a, b \in X:</tex>, если <tex>¬b<a</tex> и <tex>¬a<b</tex> и <tex>a\not=b</tex>, то <tex>a\sim b</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 | + | * Слабое: <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>X</tex>, что являются [[Упорядоченное множество |линейно упорядоченными]]. | ||
− | === | + | === Сильный подпорядок === |
+ | {{Определение | ||
+ | |definition='''Сильный подпорядок''' {{---}} такой подпорядок, на котором присутствует [[Отношение связности, компоненты связности |отношение связанности]]. | ||
+ | }} | ||
+ | Сильный подпорядок <tex>≤ \in XxX</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>, то на нем определено [[Отношение эквивалентности |отношение эквивалентности]]. | ||
+ | Поскольку операция определена для всех элементов, такие подпорядки еще называют '''отношением предпочтения'''. | ||
+ | === Упорядоченное разбиение === | ||
+ | |||
+ | |||
+ | === Сравнения === | ||
+ | ====== '''Вещественная функция''' ====== | ||
+ | Удобство использования слабого ранжирования в том, что его элементы могут быть представленны единственным образом с помощью вещественных функций. Рассмотрим следующую теорему. | ||
+ | {{Теорема|о слабом упорядовачивании | ||
+ | |statement= | ||
+ | Для любого частичного упорядовачивания <tex><\in XxX</tex> '''слабое''' ''тогда и только тогда'', когда существует <tex><_t\in YxY</tex> и отображение <tex> u: X \rightarrow Y :</tex> если <tex>a<b</tex>, то <tex>u(a) <_t u(b)</tex> и наоборот. | ||
+ | }} | ||
+ | Таким образом, чтобы имели место быть: | ||
+ | * '''частичный подпорядок''': для <tex>a≤b</tex> ''тогда и только тогда'', когда <tex>u(a)≤u(b)</tex>. | ||
+ | * '''эквивалентность''': для <tex>a \sim b</tex> ''тогда и только тогда'', когда <tex>u(a)=u(b)</tex>. | ||
− | === | + | Ограничения: |
+ | :- Лексикографические предпочтения | ||
+ | Хоть и на любом конечном множестве может определена ранжирующая функция, однако для случая лексикографического порядка функция не определена на <tex>R^n</tex>. | ||
+ | :- [[Отображения |Инъективность]] | ||
+ | В случае, если бы <tex>u</tex> являлась бы инъективной функцей, что класс эквивалентности двух элементов множества <tex>Y</tex> мог бы переходить в более широкий соответсвий класс на множестве <tex>X</tex>. | ||
+ | :- [[Отображения |Сюрьективность]] | ||
+ | Если на <tex>u</tex> вводятся ограничения, чтобы быть сюръективной функцией, то при отображении элементов некого класса на <tex>Y</tex> возможно соответсвие ему меньшего или вовсе пустого класса на <tex>X</tex>. | ||
+ | |||
+ | ====== '''Кусочная последовательность''' ====== | ||
+ | Для любого конечного множества <tex>X</tex>, на котором задано отношение слабого упорядовачивания и <tex>\exists u: X \rightarrow Y </tex>, может быть применимо моделирование с помощью кусочных последовательностей. | ||
+ | Рассмотрим пример. Положим, что | ||
+ | <center><tex>X=\{ a, b, c, d, e \}</tex></center><center><tex>u(a) = u(c) = 0, u(e) = 2, u(b) = u(d) = 5</tex> </center> | ||
+ | Тогда слабое ранжирование <tex><</tex> представляется в виде следующего: | ||
+ | <center><tex>\{ a, c \} \{ e \} \{ b, d \} </tex></center> | ||
== Сильное ранжирование == | == Сильное ранжирование == | ||
+ | |||
+ | |||
+ | == 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> числа гиперплоскостей. Исходим от предположения, что найдется такое направление, в котором объекты удовлетворительно отранжировались. | ||
+ | {|align="center" | ||
+ | |-valign="top" | ||
+ | |[[Файл:OC-svm.PNG|thumb|540px|Направляющий вектор для K=5]] | ||
+ | |} | ||
+ | |||
+ | ==== Подход ==== | ||
+ | Поскольку теперь увеличилось число зазоров, классического значения штрафа <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 === | ||
+ | Алгоритм для попарного подхода к ранжированию. Основное отличие от алгоритма 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> | ||
+ | |||
+ | === RankNet, LambdaRank === | ||
+ | Данные алгоритмы применяются для списочного ранжирования, хотя по сути своей используют попарный подход, который был расширен до случая списка. | ||
+ | [[Файл:LambdaRank.png|thumb|420px|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>\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''' моделирует следующий итеративный процесс: | ||
+ | <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. | ||
+ | |||
+ | === AdaRank === | ||
+ | '''AdaRank''' {{---}} результат воплощения идеи о применении [[Бустинг, AdaBoost |бустинга]] для задачи [[Ранжирование |ранжирования]]. Как и прежде, отталкиваемся от предположения, что несколько сколь угодно лучших обычного гадания ранжирущих моделей могут дать ответ лучше, чем каждая из них. | ||
+ | |||
+ | ==== Подход ==== | ||
+ | Ключевая идея сохраняется: строим коммитет таким образом, чтобы он обращал свое внимание на неудачные результаты ранжирования прошлого коммитета: | ||
+ | |||
+ | |||
+ | |||
+ | Поскольку данный алгоритм, как и любой метод компоизиции, по сути своей является оберткой, чтобы построить коммитет, необходимо выбрать базовую модель и подобрать подходящую функцию потерь. В оригинальной работе AdaRank(ССЫЛКА) авторы строят коммитет как с [[Ранжирование |MAP]], так и с [[Ранжирование | DCG]]. Результаты сравнения производительностей отображены на соответсвующем рисунке. | ||
+ | ==== Псевдокод ==== | ||
+ | Работа алгоритма может быть представлена следующим образом: |
Версия 15:13, 9 апреля 2020
Содержание
Порядки
При рассмотрении различных ситуаций, связанных с извлечением экспертных знаний, возникает потребность каким-либо упорядочить все множество оценок, затрагивая уже понятие группового ранжирования. Положим, имеется конечное множество Χ объектов (например, экспертных оценок или критериев) и m экспертов, пронумерованных индексами 1,2... m. каждый i-й эксперт выставляет рейтинг, порождая порядок.
Слабое ранжирование.Представления
Слабое упорядовачивание
Определение: |
Бинарное отношение на множестве , которое является частично упорядоченным, называется слабым упорядочиванием (англ. weak ordering), если оно обладает следующими свойствами:
|
Рассмотрим случаи, определеяющее частичное упорядочение как:
- Сильное: и , те если ~ .
- Слабое: если , то и .
Можно заключить, что любое cильное упорядовачивание есть слабое. Отношение несравнимости является отношением эквивалентности для всех своих разбиений на множестве , что являются линейно упорядоченными.
Сильный подпорядок
Определение: |
Сильный подпорядок — такой подпорядок, на котором присутствует отношение связанности. |
Сильный подпорядок
обладает рядом следующих свойств:- Транзитивность: , если и .
- Связанности: выполнимо либо , либо .
Если в любом сильном подпорядке отношение эквивалентности. Поскольку операция определена для всех элементов, такие подпорядки еще называют отношением предпочтения.
и , то на нем определеноУпорядоченное разбиение
Сравнения
Вещественная функция
Удобство использования слабого ранжирования в том, что его элементы могут быть представленны единственным образом с помощью вещественных функций. Рассмотрим следующую теорему.
Теорема: |
Для любого частичного упорядовачивания слабое тогда и только тогда, когда существует и отображение если , то и наоборот. |
Таким образом, чтобы имели место быть:
- частичный подпорядок: для тогда и только тогда, когда .
- эквивалентность: для тогда и только тогда, когда .
Ограничения:
- - Лексикографические предпочтения
Хоть и на любом конечном множестве может определена ранжирующая функция, однако для случая лексикографического порядка функция не определена на
.
В случае, если быявлялась бы инъективной функцей, что класс эквивалентности двух элементов множества мог бы переходить в более широкий соответсвий класс на множестве .
Если навводятся ограничения, чтобы быть сюръективной функцией, то при отображении элементов некого класса на возможно соответсвие ему меньшего или вовсе пустого класса на .
Кусочная последовательность
Для любого конечного множества
, на котором задано отношение слабого упорядовачивания и , может быть применимо моделирование с помощью кусочных последовательностей. Рассмотрим пример. Положим, чтоТогда слабое ранжирование
представляется в виде следующего:
Сильное ранжирование
Supervised алгоритмы ранжирования
OC-SVM
Ordinal Classification SVM - алгоритм поточечного ранжирования, рассматривающий каждый объект обособленно. В основе стоит использования идеи метода опорных векторов о проведении разделяющей гиперплоскости над множеством оценок.
Постановка задачи
Пусть имеется некое число градаций (оценок, предпочтений) , тогда — ранжирующая функция с порогамиОсновное отличие от классического подхода в том, что на имеющееся
границ необходимо найти зазоров. Иными словами, необходимо найти один направляющий вектор числа гиперплоскостей. Исходим от предположения, что найдется такое направление, в котором объекты удовлетворительно отранжировались.Подход
Поскольку теперь увеличилось число зазоров, классического значения штрафа
недостаточно — необходимы штрафы и для нарушение с левой и правой сторон соответственно ой границы. Ограничительное условие для такого случая состоит в том, что произвольный объект , оказавшийся между разделяющими полосами, не должен выйти за их пределы ни слева, ни справа, что можно записать как:Для случая крайних границ, для объектов
может существовать только нарушение слева от границы, когда для объектов — только справа от границы. Таким образом, задача может быть сформирована как задача минимизации с ограничениями:Ranking SVM
Алгоритм для попарного подхода к ранжированию. Основное отличие от алгоритма SVM в том, что теперь объекты нумеруются попарно.
Постановка задачи
Считаем, что теперь решаем следующую оптимизационную задачу:
Подход
Поскольку теперь все операции выполяняются уже для пары объектов, то строгая система ограничений будет отличаться в соответствующих местах:
RankNet, LambdaRank
Данные алгоритмы применяются для списочного ранжирования, хотя по сути своей используют попарный подход, который был расширен до случая списка.
Постановка задачи
Считаем, что у нас есть некий гладкий функционал качества, который необходимо оптимизировать:
Конкретную функцию потерь в оригинальной работе выбирают как логистическую функцию потерь, те
масштабирующий параметр для пересчета значения отсупа в вероятностное значение.
Подход
Воспользовавшись методом стохастического градиентного спуска, выбираем на каждой
ой итерации случайным образом запрос и пару документов из запроса , получаем итеративную формулу вычисления весов:Чтобы перейти к использованию негладких функционалов MAP, NDCD, pFound необходимо домножить
на изменение данного функционала при перестановке местами и в каждой итерации. Это означает, как изменится веса модели, если в задаче ранжирования поменять местами два документа.LambdaRank моделирует следующий итеративный процесс:
Оптмизируется тем самым по функционалу NDCD.
AdaRank
AdaRank — результат воплощения идеи о применении бустинга для задачи ранжирования. Как и прежде, отталкиваемся от предположения, что несколько сколь угодно лучших обычного гадания ранжирущих моделей могут дать ответ лучше, чем каждая из них.
Подход
Ключевая идея сохраняется: строим коммитет таким образом, чтобы он обращал свое внимание на неудачные результаты ранжирования прошлого коммитета:
Поскольку данный алгоритм, как и любой метод компоизиции, по сути своей является оберткой, чтобы построить коммитет, необходимо выбрать базовую модель и подобрать подходящую функцию потерь. В оригинальной работе AdaRank(ССЫЛКА) авторы строят коммитет как с MAP, так и с DCG. Результаты сравнения производительностей отображены на соответсвующем рисунке.
Псевдокод
Работа алгоритма может быть представлена следующим образом: