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

«МЕММ» перенаправляется сюда. О немецком лыжнике-двоеборце см. Сильвио Мемм .

В статистике модель Маркова с максимальной энтропией ( MEMM ) или условная модель Маркова ( CMM ) представляет собой графическую модель для маркировки последовательностей , которая сочетает в себе функции скрытых моделей Маркова (HMM) и моделей максимальной энтропии (MaxEnt). MEMM — это дискриминационная модель , которая расширяет стандартный классификатор максимальной энтропии , предполагая, что неизвестные значения, которые необходимо изучить, связаны в цепь Маркова, а не условно независимы друг от друга. MEMM находят применение в обработке естественного языка , в частности в маркировке частей речи. и извлечение информации .

Модель

Предположим, у нас есть последовательность наблюдений $O_{1},\dots ,O_{n}$ которые мы стремимся пометить ярлыками $S_{1},\dots ,S_{n}$которые максимизируют условную вероятность $P(S_{1},\dots ,S_{n}\mid O_{1},\dots ,O_{n})$. В MEMM эта вероятность учитывается в вероятностях марковского перехода, где вероятность перехода к определенной метке зависит только от наблюдения в этой позиции и метки предыдущей позиции. :

$P(S_{1},\dots ,S_{n}\mid O_{1},\dots ,O_{n})=\prod _{t=1}^{n}P(S_{t}\mid S_{t-1},O_{t}).$

Каждая из этих вероятностей перехода происходит из одного и того же общего распределения. $P(s\mid s',o)$. Для каждого возможного значения метки предыдущей метки $s'$, вероятность определенной метки $s$ моделируется так же, как классификатор максимальной энтропии :

$P(s\mid s',o)=P_{s'}(s\mid o)={\frac {1}{Z(o,s')}}\exp \left(\sum _{a}\lambda _{a}f_{a}(o,s)\right).$

Здесь $f_{a}(o,s)$ являются вещественными или категориальными функциями-функциями, и $Z(o,s')$ — это термин нормализации, гарантирующий, что сумма распределения равна единице. Эта форма распределения соответствует распределению вероятностей максимальной энтропии, удовлетворяющему ограничению, заключающемуся в том, что эмпирическое ожидание признака равно ожиданию данной модели:

$\operatorname {E} _{e}\left[f_{a}(o,s)\right]=\operatorname {E} _{p}\left[f_{a}(o,s)\right]\quad {\text{ for all }}a.$

Параметры $\lambda _{a}$ можно оценить с помощью обобщенного итеративного масштабирования . Кроме того, вариант алгоритма Баума-Уэлча , который используется для обучения HMM, может использоваться для оценки параметров, когда обучающие данные имеют неполные или отсутствующие метки .

Оптимальная последовательность состояний $S_{1},\dots ,S_{n}$ можно найти с помощью алгоритма Витерби, очень похожего на тот, который используется для HMM. Динамическая программа использует прямую вероятность:

$\alpha _{t+1}(s)=\sum _{s'\in S}\alpha _{t}(s')P_{s'}(s\mid o_{t+1}).$

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

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

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

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