Wyrazowe modele języka, n-gramy i SRILM

Rozważmy pytanie: Gdzie znajdę salon optyczny? Gdyby jazgot hamującego tramwaju wybrzmiał wraz z ostatnim wyrazem, tak że nie usłyszelibyśmy go dokładnie, nie przeszkodziłoby to w rozstrzygnięciu czy przechodzień miał na myśli salon optyczny czy apteczny. Salon aptyczny bowiem na gruncie języka polskiego byłby (jest?) czymś egzotycznym.

Podobnie w zwrocie filtr|flirt do wody czy zdaniu ułomek|ułamek o zapisie (kreską pionową oznaczyłem alternatywę, podobnie jak robiliśmy to w przypadku wyrażeń regularnych).

Co musimy wiedzieć o polszczyźnie, żeby móc wybrać właściwą opcję? Spójrzmy na poniższe pary w języku gruzińskim:

• ????????????? ?????????,
• ????????????? ?????????.

Drugie słowo różni się w nich nieznacznie zapisem i wymową (kolejno k??mp?l?k?s? oraz k??mp?l?k?t??), natomiast tylko jedno z połączeń ma sens na gruncie języka.

Sprawdzając ile wyników wyszukiwania zwraca Google dla konkurencyjnych interpretacji bylibyśmy w stanie rozstrzygnąć, które z nich są bardziej prawdopodobne, niezależnie od tego czy znamy ich znaczenie:

…ale co zrobić, żeby ocenić poprawność całego zdania czy połączenia, które nie występuje w naszym korpusie? Możemy wszak stworzyć zarówno poprawne, jak i niepoprawne zdanie, którego nie znajdziemy ani w Google, ani w żadnym zbiorze tekstów którym dysponujemy.

Względnie: jak pozbyć się konieczności kosztownego (zasobowo) przetrzymywania ogromnego korpusu?

Pojęcie n-gramu

Mianem n-gramu określa się sekwencję następujących po sobie jednostek, takich jak słowa, fonemy, głoski, sylaby czy litery. W zależności od liczby elementów stosuję się też nazwy unigram (dla n-gramów jednoelementowych), bigram lub digram (dla sekwencji dwu elementów) i trigram (odnoszący się do ciągu trzech elementów).

Przeanalizujmy niewystępujące w Google, w chwili pisania tego tekstu, zdanie: Potężna burza łamie duże drzewa. Jeśli interesują nas słowa wyróżnić możemy:

• 5 unigramów (1-gramów), tj. potężna, burza, łamie, duże, drzewa;
• 4 bigramy (2-gramy), na które składają się potężna burza, burza łamie, łamie duże, duże drzewa;
• 3 trigramy (3-gramy), mianowicie potężna burza łamie, burza łamie duże, łamie duże drzewa.

Jak widać w każdym przypadku tworzenia n-gramów posługujemy się oknem o rozmiarze n elementów, które po prostu przesuwamy o jeden w prawo, np. w ostatnim przypadku:

1. Potężna burza łamie duże drzewa.
2. Potężna burza łamie duże drzewa.
3. Potężna burza łamie duże drzewa.

Od częstości do prawdopodobieństwa

Jeśli wiemy, że na danym przystanku zatrzymują się tramwaje o numerach 1 i 3, a drugi z nich jeździ cztery razy częściej niż pierwszy, to możemy oszacować, który pojawi się szybciej. Ponieważ na cztery przejazdy jedynka jeździ tylko raz, ocenialibyśmy prawdopodobieństwo jej pojawienia się jako pierwszej na 0,25.

Podobnie ze słowami ? wiedząc, że na milion słów w tekście polskim, wyraz krzesło pojawia się średnio czternaście razy, możemy wyrazić prawdopodobieństwo jego wylosowania z treści książki (lub użycia) jako 0,000014.

Z powodów, które zostaną zarysowane niżej, w zastosowaniach okołoinformatycznych stosuje się niekiedy pewne udziwnienie, mianowicie zamiast przedstawiać prawdopodobieństwo jako 0,000014, podajemy jego logarytm dziesiętny.

Jak doskonale wiemy logarytm dziesiętny informuje nas do jakiej potęgi należy podnieść liczbę 10, żeby otrzymać liczbę logarytmowaną (0,000014) i tutaj mielibyśmy prawdopodobieństwo zlogarytmowane (logprob, log probability) wynoszące -4.85, ponieważ log(0,000014) = -4.85.

Bigramowy model języka

Ostatnimi słowami Churchilla miały być: Już mnie to wszystko potwornie nudzi. Gdybyśmy 15 stycznia 1965 roku nie dosłyszeli ostatniego wyrazu, moglibyśmy stanąć przed problemem wyliczenia prawdopodobieństwa wielu różnych opcji zakończenia.

Prawdopodobieństwo użycia słowa nudzi moglibyśmy oszacować na tej samej zasadzie, jak zrobiliśmy to w przypadku krzesła wyżej i – wiedząc, że wspomniany czasownik występuje średnio 6 razy na milion wyrazów – orzec, że szansa, iż był ostatnim słowem brytyjskiego premiera wynosi 0,000006.

Nie wydaje się to jednak rozsądne, ponieważ nie interesuje nas prawdopodobieństwo słowa nudzi w losowym miejscu, ale prawdopodobieństwo wyrazu nudzi po ciągu Już mnie to wszystko potwornie…, co oznaczamy przez P(nudzi|Już mnie to wszystko potwornie).

Na potrzeby szacunków moglibyśmy przyjąć, że słowo zależne jest jedynie od poprzednika, tj. uprościć tę sytuację do P(nudzi|potwornie), lub od dwóch poprzedzających je słów i sprowadzić problem do P(nudzi|wszystko potwornie).

W bigramowym modelu języka mamy do czynienia z tym pierwszym założeniem, zaś wspomniane wyżej prawdopodobieństwo bigramu liczymy dzieląc liczbę jego wystąpień (w_n-1 ? w_n) przez liczbę wystąpień słowa, która w parze jest poprzednikiem (w_n-1), co wytłumaczyłem w prezentacji z innych zajęć, gdzie pojawiło się prawdopodobieństwo warunkowe. Spójrzmy na tabelę:

Prawdopodobieństwo istnienia zdania Potężna burza łamie duże drzewa wyliczylibyśmy jako iloczyn prawdopodobieństw dla wszystkich występujących w nim bigramów, czyli P(burza|potężna) ? P(łamie|burza) ? P(duże|łamie) ? P(drzewa|duże), tj.:

P(Potężna burza łamie duże drzewa) = 0,0141 ? 0,0008 ? 0,0019 ? 0,0007 = 1,5 ? 10^-11.

Dużo łatwiej nam i komputerowi byłoby podać wynik zlogarytmizowany, ponieważ log(x ? y) = log(x) + log(y). W celu wyliczenia logarytmu dziesiętnego tego prawdopodobieństwa moglibyśmy więc zsumować poszczególne logarytmy z ostatniej kolumny:

log(P(Potężna burza łamie duże drzewa)) = -1,8497 + -3,0965 + -2,7104 + -3,1612 = -10,8178.

Prawie to samo (ze względu na zaokrąglenia) oczywiście uzyskalibyśmy licząc log(1,5 ? 10^-11), ale sposób wyżej jest dużo łatwiejszy.

SRILM i jego podstawowe funkcje

W praktyce nie musimy niczego liczyć i istnieje szereg narzędzi pozwalających tworzyć n-gramowe modele wyrazowe, z których bodaj najpopularniejszym jest SRILM (The SRI Language Modeling Toolkit).

Na serwerze w pliku /data/wikisource_sample.txt znajduje się próbka tekstów dostępnych na stronie Wikiźródeł, która posłuży nam za korpus do zbudowania modelu n-gramowego języka polskiego. Załóżmy, że interesuje nas prosty, bigramowy model.

ngram-count

Pierwszy etap stanowi stworzenie statystyk interesujących nas n-gramów, tj. wylistowanie każdej pary występujących obok siebie słów wraz częstością, z jaką pojawiają się one w korpusie.

W pakiecie SLIRM służy do tego polecenie ngram-count, którego interesującymi nas opcjami są:

• -vocab, określająca plik tekstowy z naszym leksykonem, tj. słowoformami, które chcemy rejestrować; możemy na te potrzeby posłużyć się plikiem slowoformy.txt, który tworzyliśmy w jednym z poprzednich tekstów;
• -text, wskazująca nazwę pliku z naszym korpusem;
• -order, informująca do jakiego poziomu generujemy n-gramy, w tym przypadku będzie to 2, ponieważ interesują nas maksymalnie bigramy;
• -write, po której podajemy nazwę pliku wyjściowego;
• -unk, której efektem zastosowania będzie zastąpienie nieznanych słów (tj. niewystępujących w leksykonie, tzw. OOV od out-of-vocabulary words) umownym oznaczeniem <unk>.

Po przejściu do katalogu domowego, skopiujmy więc do niego korpus (linia 1.), utwórzmy plik ze słowoformami ze słownika gramatycznego (linia 2.), a następnie wygenerujmy plik n-gramy.counts opisanym wyżej poleceniem:

Zawartość pliku n-gramy.counts jest łatwa do przewidzenia, a jej wycinek przedstawia się następująco:

To samo polecenie, z nieco innymi opcjami ( -read określającą nazwę naszego pliku ze statystykami oraz -lm wskazującą nazwę pliku do zapisania modelu), posłuży nam do zbudowania modelu n-gramowego: ngram-count -vocab slowoformy.txt -read n-gramy.counts -order 2 -lm nasz-model.lm. Otrzymaliśmy plik, w którego wnętrzu odnajdziemy m.in. znane nam logproby:

ngram

Stwórzmy plik zawierający kilka testowych zdań komendą printf "kwitnie jak święte drzewo cedrowe\nmimo podobieństwo figi Pana jako" > testowe-zdania.txt. W testowe-zdania.txt mamy teraz dwa zdania, z których żadne nie wystąpiło w korpusie źródłowym, natomiast jedno z nich jest bardziej sensowne:

Do ich przetestowania posłuży nam, a jakże, polecenie ngram, konkretnie: ngram -ppl testowe-zdania.txt -lm nasz-model.lm -debug 2, którego efektem działania będzie wynik:

W podświetlonych liniach znajduje się logarytm z prawdopodobieństwa dwu podanych zdań. Jak widać, zgodnie z oczekiwaniami, otrzymaliśmy niższy wynik dla tego z nich, które było całkowicie nonsensowne.

Taki wynik jest ulgą, ponieważ korpus wykorzystany do stworzenia modelu był zanieczyszczony, nieznormalizowany i relatywnie niewielki.

Po co to komu?

Na wstępie rozdziału była mowa o wyimaginowanej sytuacji, która przypomina te z jakimi mierzy się podczas rozpoznawania mowy. System do tego przeznaczony zawierać może model akustyczny oraz model języka ? w takim przypadku zaszyta w nim będzie operacja zbliżona do:

arg max_{w1, w2, …, wn} {P(signal|w₁, w₂, …, w_n) ? P(w₁, w₂, …, w_n) }

Arg max przyporządkowuje funkcji wewnątrz znaków { oraz } zestaw takich argumentów, dla których osiąga ona maksimum ? w tym przypadku zwróci więc takie słowa w₁, w₂, …, w_n, dla których największy jest iloczyn prawdopodobieństwa modelu akustycznego (że dany sygnał był realizacją proponowanych słów) i n-gramowego modelu języka (że dana kombinacja słów mogła zaistnieć w języku). Osiągamy więc pewien kompromis, zwiększając poprawność rozpoznawania mowy.

Rozpoznawanie mowy to nie jedyne zastosowanie i podobnie możemy oceniać różne, możliwe warianty przekładu w tłumaczeniu maszynowym, sprawdzać czy doszło do plagiatu, dokonywać korekty pisowni, poprawiać wyniki uzyskane przez OCR czy wykrywać w jakim języku napisano tekst. Modele n-gramowe są też obficie stosowane w innych niż przetwarzaniem języka dziedzinach.