Рейтинг SVM

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

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

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

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

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

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

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

${\displaystyle \tau (r_{1},r_{2})={PQ \над P+Q}=1-{2Q \над P+Q}}$

где — число согласных пар, а — число несогласных пар (инверсий). Пара и является согласной, если и и согласуются в том, как они упорядочены и . Она является несогласной, если они не согласуются.${\displaystyle P}$${\displaystyle Q}$${\displaystyle d_{i}}$${\displaystyle d_{j}}$${\displaystyle r_{a}}$${\displaystyle r_{b}}$${\displaystyle d_{i}}$${\displaystyle d_{j}}$

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

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

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

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

где находится . ​${\displaystyle {\text{Prec}}({\text{Recall}})}$${\displaystyle {\text{Точность}}}$${\displaystyle {\text{Отзыв}}}$

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

${\displaystyle \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}}$

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

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

${\displaystyle {\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}}}$

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

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

где — коэффициенты, подлежащие определению.${\displaystyle \alpha _{i}}$

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

• Ожидаемая функция потерь ^[9]

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

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

где - статистическое распределение для определенного запроса .${\displaystyle Pr(q,r^{*})}$${\displaystyle r^{*}}$${\displaystyle q}$

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

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

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

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

Для сопоставления каждого запроса и элемента базы данных с пространством признаков требуется функция сопоставления ^{[10] [11]} . Затем каждая точка в пространстве признаков помечается определенным рангом с помощью метода ранжирования.${\displaystyle \Phi (q,d)}$

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

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

${\displaystyle {\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.

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

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

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

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

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

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

${\displaystyle {\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}}}$

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