Прогнозирование структуры и обучение

Сочетание прогностического моделирования с выводом структуры

Машинное обучение с учителем предполагает прогнозирование значения переменной result на основе некоторых входных данных. Как правило, результат является действительным или категоричным.

Структурированный прогноз обобщает это для прогнозирования результатов, которые либо имеют явную структуру, либо состоят из нескольких взаимодействующих скалярных результатов. Давайте посмотрим на примеры с явной структурой.

Структурированные результаты

Обычно это последовательности, деревья или графы. Мы увидим примеры каждого. Большинство из них взяты из [2].

Оптическое распознавание символов. Распознавайте слова на рукописном изображении. Слова — это структурированные результаты, состоящие из атомарных единиц, отдельных символов. (Структурированное) пространство результатов — это словарь всех слов. Он позволяет комбинировать информацию на уровне слов с распознаванием отдельных символов, тем самым повышая точность. Например, если первая буква выглядит как c, третья — как r, а вторая — как o или a, скорее всего, это слово автомобиль.

Синтаксический анализ НЛП. Прогнозирование дерева синтаксического анализа предложения, т. е. последовательности слов. Выходное пространство представляет собой множество всех деревьев синтаксического анализа.

Распознавание объектов: распознавание объектов на изображении или видео. Не индивидуально, а коллективно, как граф сцены. То есть как структурированный результат.

Предсказание структуры белка. Предскажите вторичную или третичную структуру белка по его последовательности.

Перевод фраз. Переведите английскую фразу на ее французский эквивалент.

Тегирование частей речи. Введите последовательность слов на языке (скажем, английском) и выведите последовательность POS-тегов слов (существительное, глагол, прилагательное и т. д.). Результат структурирован, потому что мы хотим вывести последовательность тегов POS. Теги, предсказанные для отдельных слов, взаимодействуют друг с другом, поэтому предсказание лучшего тега для каждого слова и простое их объединение не работают достаточно хорошо.

На пути к структурированному персептрону

Совместные функции объектов

Одна из ключевых идей заключается в объединенной функциональной функцииF(x, y), где x – ввод и y вывод. Рассмотрите POS-теги. Пока ограничимся тегированием одного слова, обозначим его x. Если мы считаем, что определенные аспекты x коррелируют с определенными аспектами y, мы можем отразить их в функциях. Ниже приведены некоторые примеры из [5].

Первая буква x заглавная, y = существительное
xоканчивается на ed, y= глагол

HMM, выраженные с помощью совместных функций

Следуя [6], это проще всего увидеть на примере. Учитывать

x   The   dog    ate    the   homework
y   Det → Noun → Verb → Det → Noun

Здесь → обозначает переход состояния в HMM. Совместная вероятность, факторизованная в соответствии с HMM, равна

P(x,y) = T(Det|Begin)*E(The|Det)*T(Noun|Det)*E(dog|Noun)*…

Здесь T(B|A) обозначает вероятность перехода из состояния A в состояние B в HMM, а E(B|A) обозначает вероятность выхода B из состояния A. Начало обозначает состояние, с которого HMM начинает вычислять P(x, y).

P(x, y) — это просто вероятность перехода в состояние Det из состояния Начало, затем испускание слова The из состояния Det, затем переход в состояние Noun из состояния Det , а затем выделяет слово dog из состояния Noun. И так далее.

Взятие журнала дает

log P(x,y) = log T(Det|Begin) + log E(The|Det) + log T(Noun|Det) + log E(dog|Noun) + …                                              (1)

Уравнение (1) можно переформулировать как

S(x, y) = w_{T, Begin, Det}*F_{T, Begin, Det}(Begin, y1) +
w_{E, Det, The}*F_{E, Det, The}(x1) + …                          (2)

где

S(x, y) равно log P(x, у), w_{T, Begin, Det} is log T(Det|Begin), F_{T, Begin, Det}(Begin, y1) равно 1, если y1 равно Det, и 0, если нет, w_{E, Det, The} is log E(The|Det), F_{E, Det, The}(x1, y1) равно 1, если x1 равно The и y1 равно Det, и 0, если нет

И так далее.

На первый взгляд кажется, что уравнение (2) — это просто более непрозрачный способ записи уравнения (1).

Однако это еще не все. Как оказалось, уравнение (2) легко преобразовать в функцию оценки, которая богаче, чем функция уравнения (1). Чтобы убедиться в этом, рассмотрим слово x3 = ate в нашем предложении. Член в уравнении (1), значение которого зависит от него, есть log E(ate|Verb), который в записи уравнения (2) равен

w_{E, Verb, ate}*F_{E, Verb, ate}(x3, y3)

А теперь представьте, что x3 заменяется другим словом, например жевал. Кроме того, предположим, что жевал не был замечен в нашем наборе данных. Итак, E(жеванный|Глагол) неизвестен.

Рассмотрите возможность добавления следующей функциональной функции F_{E, Verb, *ed}(x, y). У него есть обучаемый параметр w_{E, Verb, *ed} в паре с ним. F_{E, Verb, *ed}(x3, y3) равно 1, если x3 заканчивается с ed и y3 — это глагол, а в противном случае — 0.

Обратите внимание, что эта функция добавляется к нашей функции оценки. Итак, если бы жевал был замечен в тренировочном наборе, при оценке x = жевал, y = Глагол, появились бы две функции признаков. аддитивно

w_{E, Verb, chewed}*F_{E, Verb, chewed}(x, y)+
w_{E, Verb, *ed}*F_{E,Verb, *ed}(x, y)

В этом смысле есть некоторая избыточность. С другой стороны, F_{E, Verb, *ed} потенциально обобщает более широко, поскольку применимо к словам, которые не были замечены во время обучения, но оканчиваются на ed при произношении. из состояния Глагол.

Эффективный вывод

Как мы видели, возможности функции оценки с точки зрения того, какие функции она может поддерживать, важны. Что также важно, так это то, что мы можем эффективно делать выводы, используя функцию оценки. В наших условиях самым важным выводом является поиск y, который максимизирует S(x, y) для заданный x. В нашем рабочем примере это даст нам наилучшую последовательность тегов POS для заданной последовательности слов.

Эффективный вывод в HMM

Чтобы найти y, который максимизирует уравнение (1) для данного x, мы можем использовать специальную структуру HMM, чтобы заставить ее соблюдать принцип оптимальности : из оптимальных решений для небольших проблем мы можем выстроить оптимальные решения для более крупных.

Чтобы понять это более точно, давайте проиллюстрируем это на нашем примере с POS-тегами. Мы ищем оценку оптимальной последовательности тегов для Собака съела домашнее задание. Для каждого возможного тега tдля домашнего задания давайте найдем оценку оптимального решения для Собака съелапри добавленном ограничении, которое домашнее задание должно быть отправлено из t. Теперь у нас есть оптимальные оценки для нескольких подзадач, по одной на значение t. Мы умножаем каждую из этих оценок на вероятность получения домашнего задания от t. Каждая из полученных оценок оптимальна для всего предложения при добавленном ограничении, заключающемся в том, что домашнее задание выдается из t. Получение максимальной из этих оценок дает нам оптимальную оценку с удаленным ограничением.

То, что мы описали на интуитивном уровне в предыдущем абзаце, известно как алгоритм Витерби.

Эффективный вывод в более общем плане

Таким образом, уравнение (2) дает нам более богатую оценочную функцию, чем уравнение (1). А как насчет эффективности вывода? Мы ответим на этот вопрос косвенно, с точки зрения тематического исследования, в котором используется более богатая функция оценки, чем обычная HMM, при этом гарантируя, что вывод остается эффективным. Мы используем этот педагогический подход, потому что считаем, что «обеспечение эффективности вывода» лучше всего понять на реальном примере.

Теги для POS с расширенными функциями

Во-первых, мы начнем со всех основных функций HMM. В частности, те из уравнения (1), которые перевыражаются в обозначениях уравнения (2). К ним мы добавим дополнительные функции признаков с ограничением, что каждая из вновь добавленных функций применяется к одной паре (слово, состояние). Эти недавно добавленные можно рассматривать как расширенные версии функций излучения HMM.

Мы уже видели один, F_{E, Verb, *ed}(x, y). Это можно рассматривать как своего рода испускание: вероятность испускания слова, оканчивающегося на ed, из состояния Verb.

Читатель может догадаться, что это ограничение, которое недавно добавленные функции признаков накладывают на пару (слово, состояние), что позволит нам поддерживать эффективность вывода.

Давайте рассмотрим еще одну такую функцию: F_{E, Noun, first_letter_is_capitalized}(x, y). F_{E, существительное, first_letter_is_capitalized}(x, y) равно 1, если слово x начинается с заглавная буква и y — существительное, иначе 0. Чем поможет добавление этой функции?

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

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

Эффективность вывода

Поскольку каждая из недавно добавленных функций признаков применяется только к паре (слово, состояние), принцип оптимальности в нашем выводе остается в силе.

Чтобы убедиться в этом, давайте сначала рассмотрим наше объяснение эффективности логического вывода в HMM, которое мы дали на примере POS-тегов. Мы повторяем это ниже дословно.

Мы ищем оценку оптимальной последовательности тегов для Собака съела домашнее задание. Для каждого возможного тега tдля домашнего задания давайте найдем оценку оптимального решения для Собака съелапри добавленном ограничении, которое домашнее задание должно быть отправлено из t. Теперь у нас есть оптимальные оценки для нескольких подзадач, по одной на значение t. Мы умножаем каждую из этих оценок на вероятность получения домашнего задания от t. Каждая из полученных оценок оптимальна для всего предложения при добавленном ограничении, заключающемся в том, что домашнее задание выдается из t. Получение максимальной из этих оценок дает нам оптимальную оценку с удаленным ограничением.

Это объяснение остается в силе даже после добавления наших новых функциональных возможностей. В частности, из-за того ограничения, что недавно добавленная функция объекта применяется к паре (слово, состояние).

Можно несколько ослабить наши ограничения на новые функции признаков и при этом сохранить принцип оптимальности.

Автоматическое обнаружение новых функциональных возможностей

Ограничение функций признаков, которые применяются к парам (слово, состояние), полезно еще и с другой стороны. Мы можем автоматизировать обнаружение эффективных функций признаков этого типа с помощью обучения с учителем. Обучающий набор, который нам нужен для такого обнаружения, представляет собой набор пар (слово, POS-тег). слово вводится; POS-тег его этикетки. Метки могут быть шумными, а это означает, что тег слова не обязательно уникален. (Если бы метки были уникальными, сама проблема маркировки POS не нуждалась бы в структурированном предсказании.)

Из входного слова мы можем извлечь любые функции, которые, по нашему мнению, могут предсказать его метку. Например, заглавная ли первая буква, какие последние k буквы слова, для k = 1, 2, 3, … какие первые k буквы слова, для k = 1, 2, 3, …

Запустив алгоритм обучения с учителем на размеченном наборе данных для этой задачи, мы можем найти пары (f(x), y), которые сильно коррелированный. Здесь f(x) — это особый признак слова x. (Даже простой алгоритм обучения с учителем, который явно изучает P(y|f(x)) может Каждая такая пара (f(x), y) определяет нашу обнаруженную совместную функцию признаков.

Изучение весов функции оценки

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

Мы проиллюстрируем это на нашем рабочем примере POS-тегов. Допустим, у нас есть обучающий набор пар (слова, теги). Здесь words обозначает последовательность слов. Как в предложении, фразе или даже целом документе. Теги обозначают соответствующую последовательность тегов POS.

Ниже приведен пример пары в таком тренировочном наборе.

words The dog  ate  the homework
tags  Det Noun Verb Det Noun

Один из способов узнать веса — следовать подходу HMM. То есть выразить их вероятностно и оценить эти вероятности непосредственно по обучающей выборке.

Рассмотрим w_{E, Det, The}, которые мы выражаем как log E(The|Det). Величина E(The|Det) представляет собой вероятность испускания The из состояния Det. Это просто количество выделений слова The из состояния Det в обучающем наборе, деленное на общее количество выделений из состояния Det. Точно так же вес перехода w_{T, Det, Noun} равен log T(Noun|Det), где T — вероятность перехода в состояние Noun из состояния Det. Это просто количество переходов из состояния Det в состояние Noun, деленное на количество вхождений состояния Det в обучающем наборе.

Мы могли бы немного сгладить эти оценки, добавив псевдосчетчики. Идея состоит в том, чтобы покрыть события, которые никогда не встречались в обучающей выборке, с вероятностью чуть большей, чем 0.

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

Более сложный способ обучения включает в себя обучение на ошибках. Мы начинаем с начальной модели и итеративно улучшаем ее следующим образом.

— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — -

Представьте слова
Прогнозировать прогнозируемые теги из текущей модели
Настройте модель, чтобы прогнозируемые теги лучше согласовывались с (целевыми) тегами.

— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — -

Обучение, управляемое ошибками, также известное как дискриминационное обучение, потенциально позволяет создавать более точные модели, чем вышеупомянутое вероятностное обучение.

Шаг 2 может быть выполнен с использованием алгоритма Витерби.

Для объяснения шага 3, т. е. шага, на котором выполняется различительное обучение, будет удобна формальная нотация. При вводе слов пусть t_pred обозначает последовательность тегов, которую создает алгоритм Витерби применительно к текущей модели, а t_target обозначает теги, целевая последовательность тегов.

На данный момент в нашем запущенном примере функции функций имеют вид F_{T, curr_tag, next_tag}(t1, t2) или F_{E , слово, тег}(w, t). Здесь curr_tag, next_tag и tag обозначают определенные теги, word обозначает конкретное слово в словаре, w обозначает переменную слова, а t1 , t2 и t обозначают переменные тега.

Представляя дискриминативное обучение, мы будем выражать функции признаков следующим образом. Пусть F_i(w, t) обозначает i-ю функцию признаков. Здесь w — последовательность слов, а t — последовательность соответствующих тегов. Мы делаем это, чтобы выявить более общую природу этого различающего обучения (см. ниже). Как оказалось, это обозначение также является более кратким.

Для каждого i мы будем обновлять вес wi следующим образом:

wi += a*(Fi(w, t_target)-Fi(w, t_pred))                         (SP1

Здесь a — небольшая положительная константа, называемая скоростью обучения.

Уравнение (SP1) обновляет вес wi, чтобы попытаться заставить t_pred двигаться к t_target. Давайте проиллюстрируем это в конкретном сценарии в нашем рабочем примере. Скажем, для определенного j wj — это жевать, а tj_target — это глагол . Скажем, при выполнении алгоритма Витерби на w полная последовательность слов (из которых показано только wj) в текущей модели дает tj_pred для быть существительным.

Рассмотрим функцию признаков 2*F_{E, *ed, Verb}(w, t)-1. Его значение равно 1 для (жевал, глагол) и -1 для (жевал, существительное). Поэтому мы увеличим значение w_{E, *ed, Verb}. Это приведет к большему штрафу алгоритма Витерби, если он выведет какой-либо тег, кроме Verb, в качестве тега для этого вхождения chewed.

Сводка

В этом посте мы представили проблему прогнозирования структуры и обсудили распространенные варианты использования. Далее мы рассмотрели важную концепцию функций совместных признаков и то, как она обобщает ключевые вычисления в HMM. Далее мы рассмотрели, почему и как сделать эффективный вывод в HMM. Исходя из этого, мы приступили к обсуждению эффективного вывода в более общем контексте функций совместных признаков. Наконец, мы ввели дискриминационное обучение для обучения весов функций совместных признаков. Кульминацией этого стал структурированный персептрон: смесь эффективного вывода и различительного обучения в более общей настройке функций совместных признаков. Короче говоря, по сравнению с HMM мы получили более богатое представление (совместные функции признаков) и более точное обучение при сохранении эффективности вывода.

Дополнительная литература

Прогнозирование структуры и обучение

Сочетание прогностического моделирования с выводом структуры

Вопросы по теме