PROFILPELAJAR.COM

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

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

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

Приложения

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

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

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

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

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

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

Техники

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

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

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

Определяем «совместную функцию признаков» Φ(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, а не полного перебора по экспоненциально большому множеству кандидатов.