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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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