Структурное прогнозирование

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

Аналогично широко используемым техникам обучения с учителем, модели структурного прогнозирования обучаются с помощью наблюдаемых данных, где истинное предсказанное значение используется для пересмотра параметров модели. Из-за возможной сложности модели и взаимосвязи предсказанных переменных, процесс предсказания с использованием обучения модели часто вычислительно невыполним, вследствие этого используются приближённые выводы.

Для оценки структурного коэффициента применяется косвенный МНК.

Приложения

Например, задачу перевода предложения естественного языка в синтаксическое представление, такое как дерево синтаксического разбора, можно рассматривать как задачу структурного прогнозирования , в которой структурная область вывода является множеством всех возможных деревьев разбора. Структурное прогнозирование также используется в широкой области приложений, включая биоинформатику, обработку естественного языка, распознавание речи и компьютерное зрение.

Пример: разметка последовательностей

Разметка последовательностей — это класс задач, широко распространённых в обработке естественного языка, где входными данными часто являются последовательности (например, предложения в тексте). В некоторых версиях возникает необходимость разметки последовательностей, например в разметке частей речи и распознавании именованных сущностей. В частеречной разметке, например, каждое слово в последовательности должно получить «ярлык» (класс метки), который выражает «тип» слова:

This	ДТ
is	ГЛ
a	ДТ
tagged	ИП
sentence	ИС
.	.

Основной целью этой задачи является правильное определение понятия (элемента последовательности) при наличии нескольких подходящих для него значений: существительное "sentence" ( рус. «предложение») в английском языке может быть также глаголом; чтобы облегчить определение части речи слову можно присвоить соответствующий «ярлык».

На первый взгляд, описанная выше задача может быть решена посредством простой классификации индивидуальных элементов, однако этот подход не учитывает эмпирический факт: ярлыки не возникают независимо. Наоборот, каждый ярлык показывает сильную условную зависимость от ярлыка предыдущих слов. То есть от того, какая метка стоит, например, у слова "sentence" — глагол или прилагательное — зависят метки других слов в предложении. Этот факт может быть использован в моделях, которые предсказывают всю последовательность ярлыков для предложения, таких как скрытая марковская модель или условное случайное поле. Для моделей, использующих индивидуальные ярлыки, например алгоритм Витерби, такой способ не подходит.

Техники

Графовые вероятностные модели образуют большой класс моделей структурного прогнозирования. В частности, популярны байесовские сети и случайные поля. Другие алгоритмы и модели для структурного прогнозирования включают индуктивное логическое программирование, рассуждения на основе прецедентов, структурные методы опорных векторов, логико-марковские сети и ограниченные условные модели. Основные техники:

• Условное случайное поле
• Структурный метод опорных векторов
• Структурный метод k-ближайших соседей
• Рекуррентная нейронная сеть, в частности, нейронная сеть Элмана

Структурный перцептрон

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

Определяем «совместную функцию признаков» Φ(x, y), которая отображает тренировочный элемент x и предсказанного кандидата y в вектор длины n. При этом x и y могут иметь любую структуру, а значение n зависит от задачи, но фиксировано для каждой модели. Пусть GEN будет функцией, которая генерирует кандидата в предсказатели. Тогда:

Пусть $w$ будет вектором весов длины n

Для предопределённого числа итераций:

Для каждого экземпляра $x$ в тренировочном наборе с истинным выводом $t$:

Делаем предсказание ${\hat {y}}={\operatorname {arg\,max} }\,\{{y}\in {GEN}({x})\}\,({w}^{T}\,\phi ({x},{y}))$

Обновляем $w$, от ${\hat {y}}$ к $t$: ${w}={w}+{c}(-\phi ({x},{\hat {y}})+\phi ({x},{t}))$, $c$ является темпом обучения.

На практике, нахождение Argmax на ${GEN}({x})$ может быть осуществлено с помощью алгоритма, такого как алгоритм Витерби или алгоритм max-sum, а не полного перебора по экспоненциально большому множеству кандидатов.

Идея обучения похожа на перцептрон с множеством классов.

Литература

• Gökhan BakIr, Ben Taskar, Thomas Hofmann, Bernhard Schölkopf, Alex Smola, S.V.N. Vishwanathan. Predicting Structured Data. — MIT Press, 2007.
• Lafferty J., McCallum A., Pereira F. Conditional random fields: Probabilistic models for segmenting and labeling sequence data // Proc. 18th International Conf. on Machine Learning. — 2001. Архивная копия от 7 июня 2013 на Wayback Machine
• Michael Collins. Discriminative training methods for hidden Markov models: Theory and experiments with perceptron algorithms // Proc. EMNLP. — 2002. — Т. 10. Архивная копия от 8 декабря 2006 на Wayback Machine
• Noah Smith, Linguistic Structure Prediction, 2011.

Ссылки

• Implementation of Collins structured perceptron