Структурированная машина опорных векторов

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

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

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

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

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

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

${\displaystyle {\begin{array}{cl}{\underset {{\boldsymbol {w}},{\boldsymbol {\xi }}}{\min }}&\|{\boldsymbol {w}}\|^{2}+C\sum _{i=1}^{n}\xi _{i}\\{\textrm {st}}&\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{массив}}}$

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

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

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

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

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

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

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

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

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

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