Структурированный прогноз - Structured prediction

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

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

Приложения

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

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

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

Этот	DT
является	ВБЗ
а	DT
отмечен	JJ
приговор	NN
.	.

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

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

Методы

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

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

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

Один из самых простых способов понять алгоритмы общего структурированного предсказания - это структурированный перцептрон Коллинз.^[3]Этот алгоритм сочетает в себе перцептрон алгоритм обучения линейные классификаторы с алгоритмом вывода (классически Алгоритм Витерби при использовании с данными последовательности), и абстрактно его можно описать следующим образом. Сначала определите «функцию совместной функции» Φ (Икс, y), который отображает обучающую выборку Икс и предсказание кандидата y к вектору длины п (Икс и y может иметь любую структуру; п зависит от проблемы, но требует исправления для каждой модели). Пусть GEN будет функцией, которая генерирует прогнозы кандидатов. Потом:

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

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

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

Сделать прогноз ${\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 более ${\displaystyle {GEN}({x})}$ будет выполняться с использованием такого алгоритма, как Витерби, или такого алгоритма, как максимальная сумма, а не исчерпывающий поиск через экспоненциально большой набор кандидатов.

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

Рекомендации

1. Гекхан Бакир, Бен Таскар, Томас Хофманн, Бернхард Шёлкопф, Алекс Смола и SVN Вишванатан (2007), Прогнозирование структурированных данных, MIT Press.
2. Лафферти, Дж., Маккаллум, А., Перейра, Ф. (2001). «Условные случайные поля: вероятностные модели для сегментации и маркировки данных последовательности» (PDF). Proc. 18-я международная конф. по машинному обучению. С. 282–289.
3. Коллинз, Майкл (2002). Дискриминационные методы обучения скрытых марковских моделей: теория и эксперименты с алгоритмами персептрона (PDF). Proc. ЕМНЛП. 10.

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

внешняя ссылка

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