Рейтинг СВМ

В машинном обучении ранжирующая SVM — это вариант машинного алгоритма опорных векторов , который используется для решения определенных ранжирования задач (посредством обучения ранжированию ). Алгоритм ранжирования SVM был опубликован Торстеном Йоахимсом в 2002 году. Первоначальной целью алгоритма было повышение производительности поисковой системы в Интернете . Однако было обнаружено, что ранжирование SVM также можно использовать для решения других задач, таких как Rank SIFT .

Описание

Алгоритм ранжирования SVM — это обучающаяся функция поиска, которая использует методы парного ранжирования для адаптивной сортировки результатов в зависимости от того, насколько они «релевантны» для конкретного запроса. Функция ранжирования SVM использует функцию сопоставления для описания соответствия между поисковым запросом и характеристиками каждого из возможных результатов. Эта функция сопоставления проецирует каждую пару данных (например, поисковый запрос и выбранную веб-страницу) в пространство объектов. Эти функции объединяются с соответствующими данными о кликах (которые могут служить показателем того, насколько релевантна страница для конкретного запроса), а затем могут использоваться в качестве обучающих данных для алгоритма ранжирования SVM.

Обычно ранжирование SVM включает в себя три этапа периода обучения:

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

Фон

Метод ранжирования

Предполагать $\mathbb {C}$ представляет собой набор данных, содержащий $N$ элементы $c_{i}$. $r$ это метод ранжирования, применяемый к $\mathbb {C}$. Затем тот $r$ в $\mathbb {C}$ может быть представлен как $N\times N$ двоичная матрица. Если ранг $c_{i}$ выше ранга $c_{j}$, то есть $r\ c_{i}<r\ c_{j}$, соответствующая позиция этой матрицы устанавливается на значение «1». В противном случае элементу в этой позиции будет присвоено значение «0».

тау Кендалла

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

Предполагать $r_{1}$ и $r_{2}$ два метода ранжирования применяются к набору данных $\mathbb {C}$, Тау Кендалла между $r_{1}$ и $r_{2}$ можно представить следующим образом:

$\tau (r_{1},r_{2})={P-Q \over P+Q}=1-{2Q \over P+Q}$

где $P$ количество согласованных пар и $Q$ – количество несогласованных пар (инверсий). Пара $d_{i}$ и $d_{j}$ согласовано, если оба $r_{a}$ и $r_{b}$ согласен в том, как они заказывают $d_{i}$ и $d_{j}$ . Это противоречит, если они не согласны.

Качество поиска информации

Качество поиска информации обычно оценивается по следующим трем показателям:

1. Точность
2. Отзывать
3. Средняя точность

Для конкретного запроса к базе данных пусть $P_{relevant}$ быть набором соответствующих информационных элементов в базе данных и $P_{retrieved}$ быть набором извлеченных информационных элементов. Тогда приведенные выше три измерения можно представить следующим образом:

${\begin{aligned}&{\text{precision}}={\frac {\left|P_{\text{relevant}}\cap P_{\text{retrieved}}\right|}{\left|P_{\text{retrieved}}\right|}};\\[6pt]&{\text{recall}}={\frac {\left|P_{\text{relevant}}\cap P_{\text{retrieved}}\right|}{\left|P_{\text{relevant}}\right|}};\\[6pt]&{\text{average precision}}=\int _{0}^{1}{\text{Prec}}({\text{recall}})\,d{\text{recall}},\\\end{aligned}}$

где ${\text{Prec}}({\text{Recall}})$ это ${\text{Precision}}$ из ${\text{Recall}}$.

Позволять $r^{*}$ и $r_{f(q)}$ — ожидаемый и предлагаемый методы ранжирования базы данных соответственно, нижняя граница средней точности метода. $r_{f(q)}$ можно представить следующим образом:

$\operatorname {AvgPrec} (r_{f(q)})\geqq {1 \over R}\left[Q+{\binom {R+1}{2}}\right]^{-1}\left(\sum _{i=1}^{R}{\sqrt {i}}\right)^{2}$

где $Q$ – количество различных элементов в верхних треугольных частях матриц $r^{*}$ и $r_{f(q)}$ и $R$ — количество соответствующих элементов в наборе данных.

классификатор СВМ

Предполагать $({\vec {x}}_{i},y_{i})$ — это элемент набора обучающих данных, где ${\vec {x}}_{i}$ вектор признаков и $y_{i}$ это метка (которая классифицирует категорию ${\vec {x}}_{i}$). Типичный классификатор SVM для такого набора данных можно определить как решение следующей задачи оптимизации.

${\begin{aligned}&{\text{minimize }}V({\vec {w}},{\vec {\xi }})={1 \over 2}{\vec {w}}\cdot {\vec {w}}+CF\sum \xi _{i}^{\sigma }\\[6pt]&{\text{subject to}}\\[6pt]&{\begin{array}{l}\sigma \geqq 0;\\\forall y_{i}({\vec {w}}{\vec {x}}_{i}+b)\geqq 1-\xi _{i}^{\sigma };\end{array}}\\[6pt]&\mathrm {where} \\[6pt]&{\begin{array}{l}b{\text{ is a scalar;}}\\\forall y_{i}\in \left\{-1,1\right\};\\\forall \xi _{i}\geqq 0;\\\end{array}}\end{aligned}}$

Решение вышеуказанной задачи оптимизации можно представить как линейную комбинацию векторов признаков. $x_{i}$с.

${\vec {w}}^{*}=\sum _{i}\alpha _{i}y_{i}x_{i}$

где $\alpha _{i}$ – коэффициенты, которые необходимо определить.

Ранжирование алгоритма SVM

Функция потерь

Позволять $\tau _{P(f)}$ быть тау Кендалла между ожидаемым методом ранжирования $r^{*}$ и предлагаемый метод $r_{f(q)}$, можно доказать, что максимизация $\tau _{P(f)}$ помогает минимизировать нижнюю границу средней точности $r_{f(q)}$.

• Функция ожидаемых потерь

Отрицательный $\tau _{P(f)}$ может быть выбрана в качестве функции потерь , чтобы минимизировать нижнюю границу средней точности $r_{f(q)}$

$L_{\text{expected}}=-\tau _{P(f)}=-\int \tau (r_{f(q)},r^{*})\,dPr(q,r^{*})$

где $Pr(q,r^{*})$ это статистическое распределение $r^{*}$ на определенный запрос $q$.

• Эмпирическая функция потерь

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

$L_{\text{empirical}}=-\tau _{S}(f)=-{1 \over n}\sum _{i=1}^{n}\tau (r_{f(q_{i})},r_{i}^{*})$

Сбор данных обучения

$n$ Запросы iid применяются к базе данных, и каждый запрос соответствует методу ранжирования. Набор обучающих данных имеет $n$ элементы. Каждый элемент содержит запрос и соответствующий метод ранжирования.

Пространство функций

Маркированные точки в пространстве объектов

Функция сопоставления $\Phi (q,d)$ требуется для сопоставления каждого запроса и элемента базы данных с пространством объектов. Затем каждой точке пространства признаков присваивается определенный ранг с помощью метода ранжирования.

Проблема оптимизации

Точки, сгенерированные обучающими данными, находятся в пространстве признаков, которое также несет информацию о ранге (метки). Эти помеченные точки можно использовать для поиска границы (классификатора), определяющей их порядок. В линейном случае такой границей (классификатором) является вектор.

Предполагать $c_{i}$ и $c_{j}$ являются двумя элементами в базе данных и обозначают $(c_{i},c_{j})\in r$ если ранг $c_{i}$ выше, чем $c_{j}$ в определенном методе ранжирования $r$. Пусть вектор ${\vec {w}}$ быть кандидатом в линейный классификатор в пространстве признаков. Тогда проблема ранжирования может быть преобразована в следующую проблему классификации SVM. Обратите внимание, что один метод ранжирования соответствует одному запросу.

${\begin{aligned}&{\text{minimize }}V({\vec {w}},{\vec {\xi }})={1 \over 2}{\vec {w}}\cdot {\vec {w}}+{\text{constant}}\cdot \sum \xi _{i,j,k}\\[6pt]&{\text{subject to}}\\[6pt]&{\begin{array}{l}\forall \xi _{i,j,k}\geqq 0\\\forall (c_{i},c_{j})\in r_{k}^{*}\\{\vec {w}}(\Phi (q_{1},c_{i})-\Phi (q_{1},c_{j}))\geqq 1-\xi _{i,j,1};\\\,\,\,\vdots \\{\vec {w}}(\Phi (q_{n},c_{i})-\Phi (q_{n},c_{j}))\geqq 1-\xi _{i,j,n};\\{\text{where }}k\in \left\{1,2,\ldots ,n\right\},\ i,j\in \left\{1,2,\ldots \right\}.\end{array}}\end{aligned}}$

Вышеупомянутая задача оптимизации идентична классической задаче классификации SVM, поэтому этот алгоритм называется Ranking-SVM.

W-кандидат

Не лучший кандидат

Функция поиска

Оптимальный вектор ${\vec {w}}^{*}$ полученный по обучающей выборке, равен

${\vec {w}}^{*}=\sum \alpha _{k,\ell }^{*}\Phi (q_{k},c_{i})$

Таким образом, поисковая функция может быть сформирована на основе такого оптимального классификатора.
Для нового запроса $q$, функция поиска сначала проецирует все элементы базы данных в пространство признаков. Затем он упорядочивает эти характерные точки по значениям их внутренних произведений с оптимальным вектором. А ранг каждой характерной точки — это ранг соответствующего элемента базы данных для запроса. $q$.

Применение ранжирования SVM

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

1. Запрос.
2. Текущий рейтинг результатов поиска
3. Результаты поиска, на которые нажал пользователь

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

${\begin{aligned}&{\text{minimize }}V({\vec {w}},{\vec {\xi }})={1 \over 2}{\vec {w}}\cdot {\vec {w}}+{\text{constant}}\cdot \sum \xi _{i,j,k}\\[6pt]&{\text{subject to}}\\[6pt]&{\begin{array}{l}\forall \xi _{i,j,k}\geqq 0\\\forall (c_{i},c_{j})\in r_{k}'\\{\vec {w}}(\Phi (q_{1},c_{i})-\Phi (q_{1},c_{j}))\geqq 1-\xi _{i,j,1};\\\,\,\,\vdots \\{\vec {w}}(\Phi (q_{n},c_{i})-\Phi (q_{n},c_{j}))\geqq 1-\xi _{i,j,n};\\{\text{where }}\ k\in \left\{1,2,\ldots ,n\right\},\ i,j\in \left\{1,2,\ldots \right\}.\end{array}}\end{aligned}}$

Метод $r'$ не предоставляет информацию о ранжировании всего набора данных, это подмножество метода полного ранжирования. Таким образом, условие задачи оптимизации становится более мягким по сравнению с исходным Ranking-SVM.