N-gram
Jak działa
1. Tokenizacja korpusu na jednostki (słowa, znaki, subwords). 2. Dodanie znaczników początku i końca zdania (<s>, </s>). 3. Zliczenie wszystkich n-gramów i (n−1)-gramów w korpusie. 4. Estymacja prawdopodobieństw warunkowych metodą największej wiarygodności: P(w_i | w_{i−n+1}...w_{i−1}) = count(w_{i−n+1}...w_i) / count(w_{i−n+1}...w_{i−1}). 5. Wygładzanie (Laplace, Good-Turing, Katz back-off, Kneser-Ney) w celu nadania niezerowej masy prawdopodobieństwa n-gramom niewidzianym w korpusie. 6. Podczas inferencji prawdopodobieństwo zdania jest iloczynem prawdopodobieństw warunkowych kolejnych n-gramów, zwykle obliczane w przestrzeni log do uniknięcia underflow. Ewaluacja: perplexity (im niższe, tym lepiej).
Rozwiązany problem
Bezpośrednie modelowanie pełnego rozkładu prawdopodobieństwa nad sekwencjami języka jest niewykonalne — liczba możliwych sekwencji rośnie wykładniczo z długością. N-gram radzi sobie z tym przez założenie Markowa: tylko n−1 ostatnich tokenów ma znaczenie, dzięki czemu model ma skończoną, oszacowywalną liczbę parametrów.
Komponenty
Struktura przechowująca count(w_{i−n+1}...w_i) dla każdego n-gramu obserwowanego w korpusie treningowym; zwykle implementowana jako trie, hash-table lub baza danych klucz-wartość.
Komponent obliczający P(w_i | w_{i−n+1}...w_{i−1}) z surowych zliczeń, zwykle MLE: count(n-gram) / count(prefix).
Algorytm redystrybucji masy prawdopodobieństwa do n-gramów niewidzianych w treningu. Standardowe metody: Laplace (add-one), Good-Turing, Katz back-off, interpolated Kneser-Ney, modified Kneser-Ney.
Mechanizm cofania się do n-gramów niższego rzędu (np. trigram → bigram → unigram), gdy n-gram wyższego rzędu nie został zaobserwowany lub ma niskie zliczenie.
Implementacja
Każdy n-gram niewidziany w treningu dostaje P=0, co powoduje, że całe zdanie ma P=0 i log P=−∞. Wygładzanie jest obowiązkowe.
Mnożenie wielu małych prawdopodobieństw szybko trafia w dolny zakres float; wyniki tracą precyzję lub stają się 0.
Bez znaczników początku/końca zdania nie da się policzyć P(pierwszego słowa) ani P(zakończenia).
Pełna tablica 5-gramów na korpusie internetowym może mieć setki GB. Bez pruningu i kompresji model jest nieużywalny.
N-gram z założenia ignoruje cokolwiek dalej niż n−1 tokenów wstecz. Składnia, koreferencja i kontekst dyskursu są poza zasięgiem modelu.
Ewolucja
W "A Mathematical Theory of Communication" Shannon analizuje statystykę języka angielskiego za pomocą n-gramów znakowych i słownych, traktując język jako proces stochastyczny rzędu n−1 (Markov).
Klasyczny eksperyment szacowania entropii języka angielskiego przy użyciu n-gramów; pokazuje, że ludzie potrafią przewidywać kolejne litery lepiej niż n-gramy niskiego rzędu.
Grupa Frederick Jelineka w IBM Research wprowadza trigramowe modele języka do dużych systemów rozpoznawania mowy, ustanawiając paradygmat noisy channel.
Slava Katz publikuje schemat back-off do estymacji prawdopodobieństw rzadkich n-gramów — standard branżowy przez dwie dekady.
Reinhard Kneser i Hermann Ney wprowadzają wygładzanie oparte na liczbie unikalnych kontekstów. Modified Kneser-Ney (Chen & Goodman 1998) pozostaje najlepszą metodą wygładzania dla n-gramów słownych.
Google udostępnia korpus 5-gramów zliczonych z 1 tryliona słów internetu. Brants et al. pokazują "Large Language Models in Machine Translation": prosty stupid back-off na ogromnych danych dorównuje wyrafinowanym metodom.
Kenneth Heafield publikuje KenLM, otwartą bibliotekę modeli n-gramowych z modified Kneser-Ney, standard de facto dla SMT (Moses) i baseline'ów.
Mikolov et al. (RNN LM) i word2vec pokazują, że gęste reprezentacje wektorowe rozwiązują problem data sparsity n-gramów; era statystycznego LM zaczyna się kończyć w produkcji.
Hiperparametry (konfigurowalne osie)
Rząd modelu, czyli długość n-gramu. Typowe wartości: 1 (unigram), 2 (bigram), 3 (trigram), 4–5 dla dużych korpusów.
Metoda wygładzania prawdopodobieństw dla n-gramów niewidzianych. Wybór tej metody jest często ważniejszy niż wybór n.
Jednostka n-gramu: znak, słowo, sylaba, subword, fonem, base pair.
Rozmiar słownika |V|. Wyznacza maksymalną liczbę unikalnych unigramów i decyduje o eksplozji parametrów.
Złożoność obliczeniowa
Złożoność czasowa: O(N) trening; O(1) lookup (amortyzowany hash) na n-gram podczas inferencji. Złożoność przestrzenna: O(|V|^n) w pesymistycznym przypadku; O(min(N, |V|^n)) w praktyce.
Wąskie gardło obliczeniowe
Liczba możliwych n-gramów rośnie jak |V|^n. Dla |V|=50 000 i n=5 daje to 3.1×10^23 możliwych 5-gramów; ogromna większość nigdy się nie pojawia, ale przechowywanie zaobserwowanych zliczeń wymaga wielogigabajtowych struktur (Google 5-gram: 1 TB nieskompresowany).
Paradygmat wykonania
Tylko jedna ścieżka w tablicy zliczeń jest dotykana per zapytanie — bardzo rzadka aktywacja parametrów.
Równoległość
Zliczanie n-gramów jest trywialnie równoległe (MapReduce); inferencja każdego n-gramu jest niezależna.
Wymagania sprzętowe
Modele n-gramowe to głównie wyszukiwanie w tablicach hash/trie — operacje pamięciowo-zorientowane, świetnie dopasowane do CPU z dużym cache i szybką pamięcią.
Brak zależności od mnożenia macierzy — działa wszędzie, włącznie z urządzeniami wbudowanymi.
GPU nie daje praktycznie żadnego przyspieszenia dla n-gramów — to nie jest workload macierzowy.