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

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

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

Приложения

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

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

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

Этот	ДТ
является	ВБЗ
а	ДТ
отмеченный	Джей-Джей
предложение	НН
.	.

Основная задача этой проблемы — устранить двусмысленность : слово «предложение» также может быть глаголом в английском языке, а также «помечено».

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

Техники

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

• Условное случайное поле
• Машина структурированных опорных векторов
• Структурированные 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 , а не исчерпывающего поиска среди экспоненциально большого набора кандидатов.

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

Ссылки

• Ной Смит, Прогнозирование лингвистической структуры , 2011.
• Майкл Коллинз, Дискриминационные методы обучения для скрытых марковских моделей , 2002.

Внешние ссылки

• Реализация структурированного персептрона Коллинза