Машина структурированных опорных векторов

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

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

Обучение

Для набора $n$ обучающие экземпляры $({\boldsymbol {x}}_{i},y_{i})\in {\mathcal {X}}\times {\mathcal {Y}}$, $i=1,\dots ,n$ из выборочного пространства ${\mathcal {X}}$ и место для метки ${\mathcal {Y}}$, структурированная SVM минимизирует следующую регуляризованную функцию риска.

${\underset {\boldsymbol {w}}{\min }}\quad \|{\boldsymbol {w}}\|^{2}+C\sum _{i=1}^{n}{\underset {y\in {\mathcal {Y}}}{\max }}\left(0,\Delta (y_{i},y)+\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y)\rangle -\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y_{i})\rangle \right)$

Функция выпукла по ${\boldsymbol {w}}$ поскольку максимум множества аффинных функций выпуклый. Функция $\Delta :{\mathcal {Y}}\times {\mathcal {Y}}\to \mathbb {R} _{+}$ измеряет расстояние в пространстве меток и является произвольной функцией (не обязательно метрикой ) , удовлетворяющей $\Delta (y,z)\geq 0$ и $\Delta (y,y)=0\;\;\forall y,z\in {\mathcal {Y}}$. Функция $\Psi :{\mathcal {X}}\times {\mathcal {Y}}\to \mathbb {R} ^{d}$ — это функция признака, извлекающая некоторый вектор признаков из заданного образца и метки. Конструкция этой функции во многом зависит от приложения.

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

${\begin{array}{cl}{\underset {{\boldsymbol {w}},{\boldsymbol {\xi }}}{\min }}&\|{\boldsymbol {w}}\|^{2}+C\sum _{i=1}^{n}\xi _{i}\\{\textrm {s.t.}}&\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y_{i})\rangle -\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y)\rangle +\xi _{i}\geq \Delta (y_{i},y),\qquad i=1,\dots ,n,\quad \forall y\in {\mathcal {Y}}\end{array}}$

Вывод

Во время тестирования только образец ${\boldsymbol {x}}\in {\mathcal {X}}$ известна, а функция прогнозирования $f:{\mathcal {X}}\to {\mathcal {Y}}$ сопоставляет его с предсказанной меткой из пространства меток ${\mathcal {Y}}$. Для структурированных SVM, учитывая вектор ${\boldsymbol {w}}$ полученная в результате обучения, функция прогнозирования имеет следующий вид.

$f({\boldsymbol {x}})={\underset {y\in {\mathcal {Y}}}{\textrm {argmax}}}\quad \langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}},y)\rangle$

Следовательно, максимизатор пространства меток является прогнозируемой меткой. Решением этого максимайзера является так называемая проблема вывода, похожая на максимальное апостериорное предсказание (MAP) в вероятностных моделях. В зависимости от структуры функции $\Psi$, решение максимизатора может оказаться сложной задачей.

Разделение

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

$y_{n}^{*}={\underset {y\in {\mathcal {Y}}}{\textrm {argmax}}}\left(\Delta (y_{i},y)+\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y)\rangle -\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y_{i})\rangle -\xi _{i}\right)$

Правая цель, которую необходимо максимизировать, состоит из постоянной $-\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y_{i})\rangle -\xi _{i}$ и член, зависящий от оптимизируемых переменных, а именно $\Delta (y_{i},y)+\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y)\rangle$. Если достигнутая цель правой части меньше или равна нулю, то для этой выборки не существует нарушенных ограничений. Если оно строго больше нуля, то обнаружено наиболее нарушенное ограничение по отношению к этой выборке. Проблема расширяется из-за этого ограничения и решается. Процесс продолжается до тех пор, пока не будет выявлено ни одного нарушенного неравенства.

Если из приведенной выше задачи исключить константы, мы получим следующую задачу, которую необходимо решить.

$y_{i}^{*}={\underset {y\in {\mathcal {Y}}}{\textrm {argmax}}}\left(\Delta (y_{i},y)+\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y)\rangle \right)$

Эта проблема очень похожа на проблему вывода. Единственное отличие заключается в добавлении термина $\Delta (y_{i},y)$. Чаще всего его выбирают таким, чтобы он имел естественную декомпозицию в пространстве меток. В этом случае влияние $\Delta$ может быть закодировано в задаче вывода, и решение наиболее нарушающего ограничения эквивалентно решению задачи вывода.

Ссылки

• Иоаннис Цочантаридис, Торстен Йоахимс , Томас Хофманн и Ясемин Алтун (2005), Методы с большой маржой для структурированных и взаимозависимых выходных переменных , JMLR, Vol. 6, страницы 1453–1484.
• Томас Финли и Торстен Йоахимс (2008), Обучение структурных SVM, когда точный вывод неразрешим , ICML 2008.
• Сунита Сараваги и Рахул Гупта (2008), Точное обучение максимальной марже для структурированных выходных пространств , ICML 2008.
• Гекхан Бакир, Бен Таскар, Томас Хофманн, Бернхард Шёлкопф, Алекс Смола и СВН Вишванатан (2007), Прогнозирование структурированных данных , MIT Press.
• Войтех Франк и Богдан Савчинский. Дискриминационное обучение классификаторов максимальной суммы , Журнал исследований машинного обучения, 9 (январь): 67–104, 2008, Microtome Publishing.
• Кевин Мерфи [1] Машинное обучение, MIT Press