Рейтинг SVM - Ranking SVM

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

Описание

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

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

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

Фон

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

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

Тау Кендалла

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

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

${\ Displaystyle \ тау (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 {array} {lcl} Precision = {\ left \ vert P_ {релевантно} \ cap P_ {извлечено} \ right \ vert \ over \ left \ vert P_ {извлечено} \ right \ vert}; \ \\\ Recall = {\ left \ vert P_ {соответствующий} \ cap P_ {извлеченный} \ right \ vert \ over \ left \ vert P_ {соответствующий} \ right \ vert}; \\\\ AveragePrecision = \ int _ { 0} ^ {1} {Prec (Вызов)} dRecall, \\\ end {array}}}$

где это из . ${\ displaystyle Prec (Отзыв)}$${\ 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 _ { я = 1} ^ {R} {\ sqrt {i}}) ^ {2}}$

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

Классификатор SVM

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

${\ displaystyle {\ begin {array} {lcl} \ mathrm {minim: \} V ({\ vec {w}}, {\ vec {\ xi}}) = {1 \ over 2} {\ vec {w }} \ cdot {\ vec {w}} + CF \ sum {\ xi _ {i} ^ {\ sigma}} \\ st \\ {\ begin {array} {lcl} \ sigma \ geqq 0; \\ \ forall y_ {i} ({\ vec {w}} {\ vec {x}} _ {i} + b) \ geqq 1- \ xi _ {i} ^ {\ sigma}; \ end {array}} \\\ mathrm {где, \} \\ {\ 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}}}$

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

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

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

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

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

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

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

Отрицательное значение можно выбрать в качестве функции потерь, чтобы минимизировать нижнюю границу средней точности${\ Displaystyle \ тау _ {П (е)}}$${\ displaystyle r_ {f (q)}}$ ${\ Displaystyle L_ {ожидаемый} = - \ tau _ {P (f)} = - \ int \ tau (r_ {f (q)}, r ^ {*}) dPr (q, r ^ {*})}$

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

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

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

${\ Displaystyle L_ {эмпирический} = - \ tau _ {S} (f) = - {1 \ over n} \ sum _ {i = 1} ^ {n} {\ tau (r_ {f (q_ {i}) )}, r_ {i} ^ {*})}}$

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

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

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

Функция сопоставления требуется для сопоставления каждого запроса и элемента базы данных с пространством функций. Затем каждой точке в пространстве признаков присваивается определенный ранг методом ранжирования. ${\ 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 {array} {lcl} \ mathrm {minim: \} V ({\ vec {w}}, {\ vec {\ xi}}) = {1 \ over 2} {\ vec {w }} \ cdot {\ vec {w}} + C_ {onstant} \ sum {\ xi _ {i, j, k}} \\ st \\ {\ 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 { где \} \ k \ in \ left \ {1,2, ... n \ right \}, \ i, j \ in \ left \ {1,2, ... \ right \}. \\\ конец {массив}} \ end {массив}}}$

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

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

Оптимальный вектор, полученный по обучающей выборке, равен ${\ 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 {minim: \} V ({\ vec {w}}, {\ vec {\ xi}}) = {1 \ over 2} {\ vec {w }} \ cdot {\ vec {w}} + C_ {ontant} \ sum {\ xi _ {i, j, k}} \\ st \\ {\ 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 { где \} \ k \ in \ left \ {1,2, ... n \ right \}, \ i, j \ in \ left \ {1,2, ... \ right \}. \\\ конец {массив}} \ end {массив}}}$

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

использованная литература