Рейтинг SVM - Ranking SVM

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

Описание

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

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

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

Фон

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

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

Кендаллс Тау ^[3][4]

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

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

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

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

Качество поиска информации ^[5][6][7]

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

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

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

${\displaystyle {\begin{array}{lcl}Precision={\left\vert P_{relevant}\cap P_{retrieved}\right\vert \over \left\vert P_{retrieved}\right\vert };\\\\Recall={\left\vert P_{relevant}\cap P_{retrieved}\right\vert \over \left\vert P_{relevant}\right\vert };\\\\AveragePrecision=\int _{0}^{1}{Prec(Recall)}dRecall,\\\end{array}}}$

куда ${\displaystyle Prec(Recall)}$ это ${\displaystyle Precision}$ из ${\displaystyle Recall}$.

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

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

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

Классификатор SVM ^[8]

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

${\displaystyle {\begin{array}{lcl}\mathrm {minimize:\ } V({\vec {w}},{\vec {\xi }})={1 \over 2}{\vec {w}}\cdot {\vec {w}}+CF\sum {\xi _{i}^{\sigma }}\\s.t.\\{\begin{array}{lcl}\sigma \geqq 0;\\\forall y_{i}({\vec {w}}{\vec {x}}_{i}+b)\geqq 1-\xi _{i}^{\sigma };\end{array}}\\\mathrm {where,\ } \\{\begin{array}{lcl}b\mathrm {\ is\ a\ scalar;} \\\forall y_{i}\in \left\{-1,1\right\};\\\forall \xi _{i}\geqq 0;\\\end{array}}\end{array}}}$

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

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

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

Алгоритм ранжирования SVM

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

Позволять ${\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_{expected}=-\tau _{P(f)}=-\int \tau (r_{f(q)},r^{*})dPr(q,r^{*})}$

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

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

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

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

Сбор обучающих данных

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

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

Помеченные точки в пространстве функций

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

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

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

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

${\displaystyle {\begin{array}{lcl}\mathrm {minimize:\ } V({\vec {w}},{\vec {\xi }})={1 \over 2}{\vec {w}}\cdot {\vec {w}}+C_{onstant}\sum {\xi _{i,j,k}}\\s.t.\\{\begin{array}{lcl}\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};\\...\\{\vec {w}}(\Phi (q_{n},c_{i})-\Phi (q_{n},c_{j}))\geqq 1-\xi _{i,j,n};\\\mathrm {where\ } \ k\in \left\{1,2,...n\right\},\ i,j\in \left\{1,2,...\right\}.\\\end{array}}\end{array}}}$

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

Кандидат W

Не w кандидат

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

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

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

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

Применение рейтингового SVM

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

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

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

${\displaystyle {\begin{array}{lcl}\mathrm {minimize:\ } V({\vec {w}},{\vec {\xi }})={1 \over 2}{\vec {w}}\cdot {\vec {w}}+C_{ontant}\sum {\xi _{i,j,k}}\\s.t.\\{\begin{array}{lcl}\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};\\...\\{\vec {w}}(\Phi (q_{n},c_{i})-\Phi (q_{n},c_{j}))\geqq 1-\xi _{i,j,n};\\\mathrm {where\ } \ k\in \left\{1,2,...n\right\},\ i,j\in \left\{1,2,...\right\}.\\\end{array}}\end{array}}}$

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

Рекомендации

1. Йоахимс, Т. (2002), «Оптимизация поисковых систем с использованием данных перехода по ссылкам», Труды конференции ACM по обнаружению знаний и интеллектуальному анализу данных.
2. Бинг Ли; Жун Сяо; Чживэй Ли; Руй Кай; Бао-Лян Лу; Лэй Чжан; «Rank-SIFT: обучение ранжированию повторяемых местных достопримечательностей», Компьютерное зрение и распознавание образов (CVPR), 2011 г.
3. М.Кемены. Методы ранговой корреляции, Хафнер, 1955 г.
4. А. Муд, Ф. Грейбилл, Д. Боуз. Введение в теорию статистики. Макгроу-Хилл, 3-е издание, 1974 г.
5. Дж. Кемени и Л. Снелл. Математические модели в социальных науках. Джинн и Ко. 1962 г.
6. Ю. Яо. Измерение эффективности поиска на основе предпочтений пользователей в отношении документов. Журнал Американского общества информационных наук, 46 (2): 133-145, 1995.
7. Р.Баеза-Йетс и Б. Рибейро-Нето. Современный информационный поиск. Эддисон-Уэсли-Лонгман, Харлоу, Великобритания, май 1999 г.
8. К. Кортес и В. Н. Вапник. Сети опорных векторов. Журнал машинного обучения, 20: 273-297, 1995.
9. В.Вапник. Статистическая теория обучения. ВИЛИ, Чичестер, Великобритания, 1998 г.
10. Н.Фур. Оптимальные полиномиальные функции поиска, основанные на принципе вероятностного ранжирования. ACM TRANSACTIONS в информационных системах, 7 (3): 183-204
11. Н.Фур, С. Хартманн, Г. Люстиг, М. Швантнер, К. Церас и Г. Кнорц. Air / x - основанная на правилах многоступенчатая система индексации для больших предметных областей. В РИАО, 1991 г.