WikiDer > Марковская модель максимальной энтропии

Maximum-entropy Markov model

В статистика, а марковская модель с максимальной энтропией (MEMM), или же условная марковская модель (CMM), это графическая модель за маркировка последовательности который сочетает в себе черты скрытые марковские модели (HMMs) и максимальная энтропия (MaxEnt) модели. MEMM - это дискриминационная модель что расширяет стандарт классификатор максимальной энтропии предполагая, что неизвестные значения, которые должны быть изучены, связаны в Цепь Маркова а не быть условно независимый друг друга. MEMM находят применение в обработка естественного языкаособенно в теги части речи[1] и извлечение информации.[2]

Модель

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

Каждая из этих вероятностей перехода происходит от одного и того же общего распределения . Для каждого возможного значения метки предыдущей метки , вероятность определенной метки моделируется так же, как и классификатор максимальной энтропии:[3]

Здесь являются вещественными или категориальными функциями-функциями, и является нормировочным членом, гарантирующим, что сумма распределения равна единице. Эта форма распределения соответствует распределение вероятностей максимальной энтропии удовлетворение ограничению, что эмпирическое ожидание для характеристики равно ожидаемому для данной модели:

Параметры можно оценить с помощью обобщенное итеративное масштабирование.[4] Кроме того, вариант Алгоритм Баума – Велча, который используется для обучения HMM, может использоваться для оценки параметров, когда обучающие данные неполные или отсутствующие ярлыки.[2]

Оптимальная последовательность состояний можно найти с помощью очень похожего Алгоритм Витерби к тому, который используется для HMM. В динамической программе используется прямая вероятность:

Сильные и слабые стороны

Преимущество MEMM перед HMM для маркировки последовательностей состоит в том, что они предлагают большую свободу в выборе функций для представления наблюдений. В ситуациях с тегами последовательности полезно использовать знания предметной области для разработки специальных функций. В оригинальной статье, представляющей MEMM, авторы пишут, что «при попытке извлечь ранее невидимые названия компаний из статьи в ленте новостей, идентичность слова сама по себе не очень предсказуема; однако, зная, что слово пишется с заглавной буквы, то есть существительное, то, что он используется в аппозитиве, и что он появляется в верхней части статьи, вполне предсказуемо (в сочетании с контекстом, обеспечиваемым структурой перехода между состояниями) ".[2] Такие полезные функции маркировки последовательностей, как эти, часто не являются независимыми. Модели максимальной энтропии не предполагают независимости между функциями, в отличие от моделей генеративного наблюдения, используемых в HMM.[2] Следовательно, MEMM позволяют пользователю указать множество коррелированных, но информативных функций.

Еще одно преимущество MEMM перед HMM и условные случайные поля (CRF) заключается в том, что обучение может быть значительно более эффективным. В HMM и CRF необходимо использовать некоторую версию вперед-назад алгоритм как внутренний цикл обучения[нужна цитата]. Однако в MEMM оценка параметров распределений максимальной энтропии, используемых для вероятностей переходов, может выполняться отдельно для каждого распределения переходов.

Недостатком MEMM является то, что они потенциально страдают от «проблемы смещения меток», когда состояния с низкоэнтропийными переходными распределениями «эффективно игнорируют свои наблюдения». Условные случайные поля были разработаны для преодоления этой слабости,[5]которые уже были признаны в контексте марковских моделей на основе нейронных сетей в начале 1990-х годов.[5][6]Еще один источник систематической ошибки меток заключается в том, что обучение всегда выполняется в отношении известных предыдущих тегов, поэтому модель испытывает трудности во время тестирования, когда есть неопределенность в предыдущем теге.

Рекомендации

  1. ^ Тутанова, Кристина; Мэннинг, Кристофер Д. (2000). «Обогащение источников знаний, используемых в тегах части речи с максимальной энтропией». Proc. J. SIGDAT Conf. по эмпирическим методам в НЛП и очень больших корпусах (EMNLP / VLC-2000). С. 63–70.
  2. ^ а б c d Маккаллум, Эндрю; Фрайтаг, Дэйн; Перейра, Фернандо (2000). «Марковские модели с максимальной энтропией для извлечения и сегментации информации» (PDF). Proc. ICML 2000. С. 591–598.
  3. ^ Бергер А.Л., Пьетра В.Дж. и Пьетра, S.A.D. (1996). «Максимально энтропийный подход к обработке естественного языка». Компьютерная лингвистика. MIT Press. 22 (1): 39–71.CS1 maint: несколько имен: список авторов (связь)
  4. ^ Дэрроч, Дж. И Рэтклифф Д. (1972). «Обобщенное итерационное масштабирование для лог-линейных моделей». Анналы математической статистики. Институт математической статистики. 43 (5): 1470–1480. Дои:10.1214 / aoms / 1177692379.
  5. ^ а б Лафферти, Джон; Маккаллум, Эндрю; Перейра, Фернандо (2001). «Условные случайные поля: вероятностные модели для сегментации и маркировки данных последовательности». Proc. ICML 2001.
  6. ^ Леон Ботту (1991). Une Approche théorique de l'Apprentissage Connexionniste: Applications à la Reconnaissance de la Parole (Кандидат наук.). Université de Paris XI.