Автор:Майкл Коллинз

Ссылка на документ

Тегирование последовательностей является фундаментальной задачей НЛП. Например, маркировка частей речи и распознавание именованных объектов — это проблемы маркировки последовательностей, которые являются важными проблемами сами по себе, а также важными промежуточными этапами в конвейерах для решения более сложных задач, таких как синтаксический анализ и извлечение отношений. Примерно в то время, когда была написана эта статья (например, до того, как LSTM и встраивания с пропуском граммов правили землей), преобладающий подход к маркировке последовательностей заключался в том, чтобы вручную спроектировать большое количество функций и использовать их для обучения какой-либо модели с максимальной энтропией (например, логистическая регрессия)[1] или условное случайное поле (CRF)[2]. В этой статье Майкл Коллинз представляет удивительно эффективный метод обучения таких моделей тегов на основе признаков с использованием алгоритма персептрона.

Ключевое наблюдение заключается в следующем. Предположим, у нас есть набор данных, состоящий из последовательностей входных данных x=[x⁽¹⁾,…,x⁽ᴺ⁾]вместе с соответствующими тегами t=[t⁽¹⁾,…,t ⁽ᴺ⁾]. Один из самых простых способов моделирования совместной вероятности этих последовательностей — с помощью триграммы Скрытая марковская модель (СММ):

Где первый альфа-термин — это вероятность текущего тега с учетом двух предыдущих тегов, а второй альфа-член — это вероятность текущего слова с учетом текущего тега. Обычный способ оценки этих параметров — подсчет относительной частоты триграмм тегов и пар слово-тег в нашем наборе данных.

Коллинз отмечает, что существует альтернативный способ получения этих оценок с использованием алгоритма персептрона. Для каждой итерации алгоритма мы начинаем с использования алгоритма Витерби для декодирования наилучшей возможной последовательности тегов z=[z⁽¹⁾,…,z⁽ᴺ⁾]для каждой наблюдаемой последовательности xв рамках текущей модели. Затем мы обновляем наши параметры, сравнивая количество раз, когда триграмма тега/пара слово-тег встречается в истинной последовательности тегов t, с количеством раз, когда она встречается в прогнозируемой последовательности тегов z:

(Примечание: правило обновления для другого альфа-члена определяется аналогично)

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

Интересно, что этот подход можно применять для оценки параметров более сложных моделей, таких как модель максимальной энтропии на основе признаков (например, логистическая регрессия):

где мы используем h⁽ⁱ⁾ для обозначения всех контекстуальных переменных (например, двух предыдущих тегов, а также наблюдаемых слов), а ϕ для обозначения функций . Алгоритм персептрона работает почти точно так же. Каждая итерация снова состоит из использования Витерби для декодирования предсказанной последовательности тегов, а затем обновления параметров путем сравнения различий между истинной и предсказанной последовательностями. Единственное изменение, которое нам нужно сделать, — это сравнивать функции вместо подсчета пар триграмма/слово-тег. Это:

где Φ — просто сумма ϕ по всей последовательности (например, если ϕ — индикаторная функция, измеряющая, был ли предыдущий тег СУЩЕСТВИТЕЛЬНЫМ, то Φ подсчитывает, сколько раз этот тег происходит в последовательности). Кроме того, Коллинз отмечает, что на практике этот подход работает лучше, если обновление усредняется по нескольким примерам из набора данных.

В оставшейся части статьи приводятся теоремы, доказывающие, что эта идея действительно работает, и описываются результаты экспериментов по двум задачам: маркировка частей речи и разбиение именных фраз на фрагменты. По сравнению с моделью с максимальной энтропией, обученной с использованием стандартного подхода, показано, что модель на основе персептрона:

  1. Сходится быстрее (стандартный подход требует до 100 итераций обучения).
  2. Имеет более низкий уровень ошибок для точности тегов POS (абсолютное снижение ~ 0,5%) и более высокие баллы F1 (абсолютное увеличение ~ 1,0) при условии, что используется вышеупомянутый прием усреднения обновлений.

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

Ссылки

[1] Ратнапарки, Адвайт. «Модель максимальной энтропии для маркировки частей речи». Конференция по эмпирическим методам обработки естественного языка. 1996.

[2] Лафферти, Джон, Эндрю МакКаллум и Фернандо С.Н. Перейра. «Условные случайные поля: вероятностные модели для сегментации и маркировки данных последовательности». (2001).