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

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

Модель [ править ]

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

${\ displaystyle 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}).}$

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

${\displaystyle 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).}$

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

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

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

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

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

Сильные и слабые стороны [ править ]

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

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

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

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