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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Приложения[править | править код]

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

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

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

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

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

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

Техники[править | править код]

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

Структурный перцептрон[править | править код]

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

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

Пусть будет вектором весов длины n
Для предопределённого числа итераций:
Для каждого экземпляра в тренировочном наборе с истинным выводом :
Делаем предсказание
Обновляем , от к : , является темпом обучения.

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

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

Примечания[править | править код]

Литература[править | править код]

Ссылки[править | править код]