Изменения

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

<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>

<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>

=== Lambda Rank =Подход ====Поскольку теперь все операции выполяняются уже для пары объектов, то строгая система ограничений будет отличаться в соответствующих местах:<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 ===Данные алгоритмы применяются для списочного ранжирования, хотя по сути своей используют попарный подход, который был расширен до случая списка. ==== Постановка задачи ==== Считаем, что у нас есть некий гладкий функционал качества, который необходимо оптимизировать:<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]]. Результаты сравнения производительностей отображены на соответсвующем рисунке. ==== Псевдокод ====Работа алгоритма может быть представлена следующим образом: