Структурированная опорная векторная машина - Structured support vector machine

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

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

Обучение персонала

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

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

Функция выпуклая в ${ displaystyle { boldsymbol {w}}}$ потому что максимум набора аффинных функций выпуклый. Функция ${ displaystyle Delta: { 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}}$ - функция функции, извлекающая некоторый вектор признаков из заданного образца и метки. Дизайн этой функции во многом зависит от приложения.

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

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

Вывод

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

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

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

Разделение

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

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

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

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

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

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

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

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