Tworzenie modelu maksymalnej entropii Markowa na podstawie istniejącego klasyfikatora maksymalnego entropii z wieloma wejściami

Intryguje mnie koncepcja modelu Maksymalnej Entropii Markowa (MEMM) i zastanawiam się nad użyciem go do taggera części mowy (POS). W tej chwili używam konwencjonalnego klasyfikatora Maximum Entropy (ME) do oznaczania każdego słowa. Wykorzystuje szereg funkcji, w tym dwa poprzednie tagi.

MEMM używają algorytmu Viterbi do znalezienia optymalnej ścieżki w łańcuchu Markowa (tj. Do znalezienia pełnego optymalnego zestawu znaczników dla zdania, a nie indywidualnych optymalnych dla każdego słowa). Czytając o tym, wydaje się, że ma cudowną elegancję i prostotę. Jednak każdy etap opiera się tylko na „wynikach” poprzedniego etapu (tj. Zgodnie z łańcuchem Markowa).

Jednak mój model ME wykorzystuje poprzednie dwa etapy (tj. Tagi dla poprzednich dwóch słów). Wygląda na to, że mam dwa możliwe podejścia:

• Podobnie jak w przypadku tradycyjnej implementacji Viterbi, użyj zestawu ścieżek przechowywanych zgodnie z jednym (poprzednim) etapem. Mój klasyfikator ME użyłby tego i „zamrożonego” etapu wcześniej (zamrożonego na rozważanej ścieżce) do wytworzenia funkcji przenoszenia.

• Albo piszę algorytm, aby śledzić dwa etapy. Jest to bardziej skomplikowane i nie byłoby już prawdziwym modelem Markowa, ponieważ każda funkcja przenoszenia (tj. Z modelu ME) zależałaby od dwóch poprzednich etapów, a nie jednego etapu.

Uderza mnie, że sekunda będzie dokładniejsza, choć będzie bardziej skomplikowana.

Nie znalazłem jeszcze żadnych przykładów tego podczas przeszukiwania literatury. Czy próbowano? Czy podejście dwustopniowe poprawiło ogólną dokładność?

(To naprawdę prawdziwe pytanie, przed którym stoję, a uruchomienie witryny ML StackExchange było właściwie idealne: wykonałem kilka dni czytania książek i badań online i miałem zacząć wdrażanie. Oto moje wyniki. Chociaż nie są rygorystyczne, myślę, że odpowiadają na moje pytanie. Pozostawię pytanie otwarte na razie, na wypadek, gdyby ktoś miał jakiś użyteczny wkład, spróbował czegoś podobnego lub miał jakieś przydatne odniesienia).

Okej, w ciągu ostatnich kilku dni zakodowałem to. Kod nie jest zbyt wydajny - dużo tworzenia i kopiowania kolekcji, ale celem ćwiczenia było sprawdzenie, czy zadziała i jak dobrze działa.

Losowo dzielę moje dane na dwie listy: dane treningowe i dane testowe. Korzystam z danych testowych za pomocą tradycyjnego tagera POS Maximum Entropy; i mój nowy tagger MEMM. Dlatego widzą te same dane testowe, co pozwala na bezpośrednie porównania - ze względu na losowość wybranych danych, widzę pewne różnice między testami (zwykle około 0,2-0,4%).

Pierwszy test wykorzystuje tagger MEMM z jednym etapem (tj. Prawdziwy łańcuch Markowa). To konsekwentnie działało lepiej niż prosty tagger ME o około 0,1-0,25%.

Następnie wypróbowałem podejście dwustopniowe, które wydaje się bardziej poprawne. Jednak wyniki były jeszcze bardziej marginalne. Często wyniki byłyby identyczne, czasami byłyby nieco gorsze, ale prawdopodobnie w większości przypadków były nieco lepsze (więc +/- 0,05%).

Tagger MEMM działa wolno. Okej, nie zastosowałem żadnych optymalizacji, ale etap 1 (prawdziwy łańcuch Markowa) jest N razy wolniejszy (gdzie N = liczba etykiet), ponieważ jest to liczba ścieżek, które są przenoszone między każdym krokiem. Implementacja 2-etapowa jest wolniejsza od N * N (z powodu większej liczby przesłanych ścieżek). Chociaż optymalizacje mogą poprawić sytuację, I jest to prawdopodobnie zbyt wolne dla większości praktycznych zastosowań.

Próbuję zastosować dolną granicę prawdopodobieństwa do ścieżek. To znaczy. ścieżki Viterbi są przycinane podczas każdej iteracji, a wszystkie ścieżki poniżej pewnego prawdopodobieństwa (obecnie Log (całkowita ścieżka P) <- 20,0) są przycinane. Działa to nieco szybciej, ale pozostaje pytanie, czy warto. Myślę, że prawdopodobnie nie jest.

Dlaczego nie widzimy żadnej poprawy? Myślę, że wynika to przede wszystkim ze sposobu, w jaki zachowują się tagi POS i modelu Maximum Entropy. Chociaż model ma funkcje oparte na dwóch poprzednich znacznikach, bezpośredni poprzedni znacznik jest znacznie ważniejszy w porównaniu z poprzednim. Intuicyjnie miałoby to sens dla języka angielskiego (np. Po przymiotniku zwykle występuje rzeczownik lub inny przymiotnik, ale tak naprawdę to nie zależy od tego, co było przed przymiotnikiem).