72
правки
Изменения
→OC-SVM
== Supervised алгоритмы ранжирования ==
=== OC-SVM ===
Ordinal Classification SVM - алгоритм поточечного ранжирования, рассматривающий каждый объект обособленно. В основе стоит использования идеи метода опорных векторов о проведении разделяющей гиперплоскости над множеством оценок.
==== Постановка задачи ====
Пусть имеется некое число градаций (оценок, предпочтений) <tex>K</tex>, тогда <tex>Y=\{1,2 ...K\}</tex> {{---}} ранжирующая функция с порогами <center> <tex>b_0=-\inf</tex>, <tex>b_1,b_2 ...b_(K-1) \in R, b_k=\inf:</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"
|[[Файл:Example_4.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} 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>
