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

Структурирован опорные векторы машина является машинным обучением алгоритма , который обобщает Опорно-Vector Machine (SVM) классификатор. В то время как классификатор 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}}}$

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

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

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

Вывод

Во время тестирования известен только образец , и функция прогнозирования сопоставляет его с прогнозируемой меткой из пространства меток . Для структурированных 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 \ 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