Структурированная машина опорных векторов — это алгоритм машинного обучения , который обобщает классификатор машины опорных векторов (SVM). В то время как классификатор SVM поддерживает бинарную классификацию , многоклассовую классификацию и регрессию , структурированная SVM позволяет обучать классификатор для общих структурированных выходных меток .
Например, экземпляром образца может быть предложение на естественном языке, а выходной меткой — аннотированное дерево разбора . Обучение классификатора состоит из показа пар правильных образцов и выходных меток. После обучения структурированная модель SVM позволяет предсказать для новых экземпляров образца соответствующую выходную метку; то есть, учитывая предложение на естественном языке, классификатор может создать наиболее вероятное дерево разбора.
Для набора обучающих примеров из пространства выборки и пространства меток структурированный SVM минимизирует следующую регуляризованную функцию риска.
Функция выпукла в , поскольку максимум набора аффинных функций является выпуклым. Функция измеряет расстояние в пространстве меток и является произвольной функцией (не обязательно метрикой ) , удовлетворяющей и . Функция является функцией признаков, извлекающей некоторый вектор признаков из заданного образца и метки. Конструкция этой функции во многом зависит от приложения.
Поскольку регуляризованная функция риска выше недифференцируема, ее часто переформулируют в терминах квадратичной программы , вводя одну переменную-слэк для каждого образца, каждая из которых представляет значение максимума. Стандартная структурированная первичная формулировка SVM имеет следующий вид.
Во время тестирования известен только образец , и функция прогнозирования сопоставляет его с предсказанной меткой из пространства меток . Для структурированных SVM, учитывая вектор, полученный в результате обучения, функция прогнозирования следующая.
Таким образом, максимизатор над пространством меток является предсказанной меткой. Решение для этого максимизатора является так называемой проблемой вывода и похоже на создание максимального апостериорного (MAP) предсказания в вероятностных моделях. В зависимости от структуры функции , решение для максимизатора может быть сложной задачей.
Вышеуказанная квадратичная программа включает в себя очень большое, возможно бесконечное число ограничений линейных неравенств. В общем случае число неравенств слишком велико, чтобы оптимизировать его явно. Вместо этого проблема решается с помощью отложенной генерации ограничений, где используется только конечное и малое подмножество ограничений. Оптимизация по подмножеству ограничений увеличивает допустимый набор и даст решение, которое обеспечивает нижнюю границу цели. Чтобы проверить, нарушает ли решение ограничения полного набора неравенств, необходимо решить задачу разделения. Поскольку неравенства разлагаются по образцам, для каждого образца необходимо решить следующую задачу.
Правосторонняя цель, которую необходимо максимизировать, состоит из константы и члена, зависящего от оптимизируемых переменных, а именно . Если достигнутая правая цель меньше или равна нулю, то для этого образца не существует нарушенных ограничений. Если она строго больше нуля, то было выявлено наиболее нарушенное ограничение по отношению к этому образцу. Проблема увеличивается на это ограничение и решается. Процесс продолжается до тех пор, пока не будут выявлены нарушенные неравенства.
Если из приведенной выше задачи отбросить константы, то получим следующую задачу, требующую решения.
Эта проблема очень похожа на проблему вывода. Единственное отличие — добавление термина . Чаще всего он выбирается таким образом, чтобы имел естественное разложение в пространстве меток. В этом случае влияние может быть закодировано в проблему вывода, и решение для наиболее нарушающего ограничения эквивалентно решению проблемы вывода.
