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

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

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

Примером применения является проблема перевода предложения на естественном языке в синтаксическое представление, такое как дерево синтаксического анализа . Это можно рассматривать как проблему структурированного прогнозирования ^[2] , в которой структурированный выходной домен представляет собой набор всех возможных деревьев синтаксического анализа. Структурированное прогнозирование используется в самых разных областях, включая биоинформатику , обработку естественного языка (NLP), распознавание речи и компьютерное зрение .

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

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

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

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

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

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

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

1. Сначала определим функцию , которая сопоставляет обучающую выборку и прогнозируемый кандидат с вектором длины ( и может иметь любую структуру; зависит от проблемы, но должна быть фиксированной для каждой модели). Пусть будет функцией, которая генерирует прогнозируемые кандидаты.${\displaystyle \phi (x,y)}$${\displaystyle x}$${\displaystyle y}$${\displaystyle n}$${\displaystyle x}$${\displaystyle y}$${\displaystyle n}$${\displaystyle GEN}$
2. Затем:

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

Для заданного количества итераций:

Для каждого образца в обучающем наборе с истинным выходом :${\displaystyle x}$${\displaystyle t}$

Сделайте прогноз :${\displaystyle {\hat {y}}}$${\displaystyle {\hat {y}}={\operatorname {arg\,max} }\,\{y\in GEN(x)\}\,(w^{T},\phi (x,y))}$

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

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

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

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

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