Model Markowa o maksymalnej entropii

W statystyce model Markowa o maksymalnej entropii ( MEMM ) lub warunkowy model Markowa ( CMM ) to graficzny model do etykietowania sekwencji , który łączy cechy ukrytych modeli Markowa (HMM) i modeli maksymalnej entropii (MaxEnt). MEMM to model dyskryminacyjny , który rozszerza standardowy klasyfikator maksymalnej entropii , zakładając, że nieznane wartości do nauczenia są połączone w łańcuch Markowa zamiast być warunkowo niezależnymi od siebie. MEMM znajdują zastosowanie w przetwarzaniu języka naturalnego , w szczególności w znakowaniu części mowy i ekstrakcji informacji .

Model

$, że$ mamy sekwencję obserwacji $S_ { 1},\dots ,S_{n}}$ oznaczyć etykietami które maksymalizują prawdopodobieństwo warunkowe ${\ Displaystyle P (S_ {1}, \ kropki, S_ {n} \ środkowy O_ {1}, \ kropki, O_ {n})}$ . W MEMM prawdopodobieństwo to jest uwzględniane w prawdopodobieństwach przejścia Markowa, gdzie prawdopodobieństwo przejścia do określonej etykiety zależy tylko od obserwacji w tej pozycji i etykiety poprzedniej pozycji [ ^{potrzebne źródło ]} :

{\ Displaystyle P (S_ {1}, \ kropki, S_ {n} \ środkowy O_ {1}, \ kropki, O_ {n}) = \ prod _ {t = 1} ^ {n} P (S_ {t }\mid S_{t-1},O_{t}).}

Każde z tych prawdopodobieństw przejścia pochodzi z tego samego ogólnego rozkładu ${\ Displaystyle P (s \ mid s', o)$ } Dla każdej możliwej wartości etykiety poprzedniej etykiety $displaystyle$ określonej etykiety $s'}$ w taki sam sposób, jak klasyfikator maksymalnej entropii : s ′ {\

{\ Displaystyle P (s \ mid s', o) = P_ {s'} (s \ mid o) = {\ Frac {1} {Z (o, s')}} \ exp \ lewo (\ suma _ {a}\lambda _{a}f_{a}(o,s)\right).}

Tutaj $, s$ mają wartość rzeczywistą lub kategoryczną i $)}$ $(o,$ jest terminem normalizacyjnym zapewniającym, że rozkład sumuje się do jednego. Ta postać rozkładu odpowiada rozkładowi prawdopodobieństwa maksymalnej entropii spełniającemu ograniczenie, że empiryczne oczekiwanie dla cechy jest równe oczekiwaniu danego modelu:

{\ Displaystyle \ nazwa operatora {E} _ {e} \ lewo [f_ {a} (o, s) \ prawej] = \ nazwa operatora {E} _ {p} \ lewo [f_ {a} (o, s) \ po prawej]\quad {\text{dla wszystkich}}a.}

Parametry $uogólnionego$ oszacować za pomocą iteracyjnego . Ponadto wariant algorytmu Bauma-Welcha , który jest używany do szkolenia HMM, może być użyty do oszacowania parametrów, gdy dane szkoleniowe mają niekompletne lub brakujące etykiety .

Optymalną sekwencję stanów można znaleźć $.$ pomocą bardzo algorytmu do Program dynamiczny wykorzystuje prawdopodobieństwo do przodu:

{\ Displaystyle \ alfa _ {t + 1} (s) = \ suma _ {s '\ w S} \ alfa _ {t} (s') P_ {s'} (s \ mid o_ {t + 1} ).}

Mocne i słabe strony

Zaletą MEMM zamiast HMM do znakowania sekwencji jest to, że oferują większą swobodę w wyborze cech reprezentujących obserwacje. W sytuacjach związanych ze znakowaniem sekwencji przydatne jest wykorzystanie wiedzy dziedzinowej do projektowania funkcji specjalnego przeznaczenia. W oryginalnym artykule wprowadzającym MEMM autorzy piszą, że „próbując wyodrębnić wcześniej niewidoczne nazwy firm z artykułu w wiadomościach, tożsamość samego słowa nie jest zbyt przewidywalna; jednak wiedząc, że słowo jest pisane wielką literą, jest to rzeczownik, że jest używany w apozytywie i że pojawia się w górnej części artykułu, wszystko byłoby dość przewidywalne (w połączeniu z kontekstem zapewnianym przez strukturę przejścia stanu). Przydatne funkcje znakowania sekwencji, takie jak te, często nie są niezależne. Modele maksymalnej entropii nie zakładają niezależności między cechami, ale generatywne modele obserwacji stosowane w HMM tak. Dlatego MEMM pozwalają użytkownikowi określić wiele skorelowanych, ale informacyjnych funkcji.

Kolejną zaletą MEMM w porównaniu z HMM i warunkowymi polami losowymi (CRF) jest to, że szkolenie może być znacznie bardziej wydajne. W HMM i CRF należy użyć jakiejś wersji algorytmu forward-backward jako wewnętrznej pętli w szkoleniu ^{[ potrzebne źródło ]} . Jednak w MEMM oszacowanie parametrów rozkładów maksymalnej entropii używanych do prawdopodobieństw przejścia można przeprowadzić dla każdego rozkładu przejścia osobno.

Wadą MEMM jest to, że potencjalnie cierpią z powodu „problemu odchylenia etykiety”, w którym stany z rozkładami przejścia o niskiej entropii „skutecznie ignorują ich obserwacje”. Warunkowe pola losowe zostały zaprojektowane w celu przezwyciężenia tej słabości, która została już rozpoznana w kontekście modeli Markowa opartych na sieciach neuronowych na początku lat 90. Innym źródłem błędu etykiety jest to, że uczenie zawsze odbywa się w odniesieniu do znanych poprzednich tagów, więc model ma problemy w czasie testu, gdy poprzedni tag jest niepewny.