Czym są n-gramy i do czego służą?

Dowiesz się jak użyć n-gramów w swoim projekcie i jak ulepszyć nawigację po nim. W tym artykule opiszemy też jeden z mechanizmów, na których oparty jest Korektor Tekstu.

• 1. Czym jest n-gram?
• 2. Rozkład zdań na n-gramy
• 3. Czy długość ma znaczenie?
• 4. Podstawy obliczania prawdopodobieństwa
• 5. Które zdanie jest bardziej prawdopodobne?
• 6. Zastosowania w biznesie

1. Czym jest n-gram?

W swojej budownie to nic innego jak tylko N kolejnych wyrazów wyjętych z jakiegoś zdania, lub tekstu. Takie pary służą potem do analizy lub podpowiedzi użytkownikowi 'co może mieć na myśli'.

Często z n-gramem połączona jest też liczba jego wystąpień w korpusie. Dzięki temu można m.in. wyliczać prawdopodobieństwa i wykrywać wyrazy niepasujące do kontekstu.

N-gram o długości 1 zwany jest inaczej unigramem, 2 - bigramem, a 3 - trigramem. Skrócone formy zapisu mogą mieć też postać 1-gram, 2-gram itp. Nie ma jednej poprawnej formy, więc w praktyce można spotkać się z każdą z nich.

2. Rozkład zdań na n-gramy

Tworzenie n-gramu jest niczym innym jak zwykłym podzieleniem napisu na pojedyncze słowa, a następnie pogrupowanie ich w pary, albo trójki.

Dla zdania „Kasia ma kota i dużego pieska.” n-gramy o długości 3 będą wyglądać następująco:

• kasia ma kota
• ma kota i
• kota i dużego
• i dużego pieska
• dużego pieska .

Jak można zauważyć imię Kasia zostało zapisane małą literą - to nie pomyłka. W praktyce, aby uniknąć powtórzeń wszystko zapisywane jest małymi literami, bo przecież KAsia KaSiA i kasIA to te same wyrazy, i nie chcemy zliczać ich niezależnie od siebie. Ale jak ze wszystkim, tak i tu trzeba dobrać techniki pasujące do naszych założeń, bo może zależy nam, aby rozróżniać wielkości liter.

Inne przykłady ujednolicania:

• powielone przecinki są traktowane jako jeden np. zaraz to zrobię,, tylko pójdę do sklepu
• każdy znak ' " ` „ ” jest zamieniany na pojedynczy apostrof (i analogicznie cała rodzina nawiasów oraz myślników)

3. Czy długość ma znaczenie?

Jak to w życiu bywa, nic nie jest czarno-białe i od każdej reguły znajdzie się sto wyjątków. Nie inaczej jest w tym przypadku.

Od strony teoretycznej zależy nam, aby kolekcjonować jak najdłuższe ciągi wyrazów ze względu na prostą zależność - im dłuższy ciąg, tym szerszy kontekst wypowiedzi on ze sobą niesie. Niestety w praktyce dla języka polskiego stworzenie znormalizowanego i wiarygodnego korpusu 6-cio, albo 7-gramowego ociera się o niewykonalność z powodu niewystarczającej bazy, z której taki korpus może zostać wygenerowany.

Oczywiście nawet dla najmniejszej lektury można wygenerować jej reprezentację w postaci nawet i 10-gramu. Natomiast taki korpus będzie zawierał gigantyczną liczbę braków przez co jego użyteczność poza statystykami dla tej konkretnej książki będzie bliska zeru.

Na szczęście są sposoby jak można z tą przypadłością żyć i posiadając jedynie 3-gramową bazę można wyliczyć prawdopodobieństwo dla np. 10-wyrazowego zdania.

4. Podstawy obliczania prawdopodobieństwa

Zakładając, że chcemy obliczyć jak bardzo prawdopodobne jest zdanie składające się ze słów A B C D. Wtedy ogólny wzór na wyliczenie tego jest następujący:

I nie przejmuj się, wygląda to na bardziej tajemnicze, niż jest w praktyce. Rozpisując wzór w przypadku 2-gramowego korpusu, będzie wyglądał on już o wiele przystępniej:

P(A) * P(B|A) * P(C|B) * P(D|C)

Dużą literą P oznacza się funkcję obliczającą prawdopodobieństwo (ang. probability). Natomiast zapis P(X|Y) odnosi się do wyliczania prawdopodobieństwa wystąpienia wyrazu Xpod warunkiem wcześniejszego wystąpienia wyrazu Y.

Zatem całość sprowadza się do przemnożenia następujących prawdopodobieństw:

Zostało nam już tylko odszyfrowanie zapisów P(A) oraz P(B|A).

P(A) oznacza count(A) / liczba wszystkich słów, czyli liczba wystąpień słowa A dzielona jest przez liczbę wszystkich słów jakie mamy zgromadzone w słowniku.

P(B|A) natomiast oznacza count(A B) / count(B), czyli zwyczajnie liczba wystąpień 2-gramu AB dzielona jest przez liczbę wystąpień samego słowa B.

Na koniec trzeba tylko wszystko przez siebie przemnożyć i dostaniemy liczbę między 0 a 1, i to ona będzie naszym prawdopodobieństwem.

5. Które zdanie jest bardziej prawdopodobne?

Gdy już wiesz jakie są podstawowe wzory, to pewnie interesuje Cię jak sprawdzić, które zdanie jest bardziej prawdopodobne, lub jakie jest najbardziej prawdopodobne następne słowo.

Będziemy tutaj korzystać ze wzorów omówionych w poprzednim punkcie i porównamy na początku, które zdanie ma większą szansę na wystąpienie:

1. tomek ma dom
2. tomek ma mieszkanie

Całość sprowadzi się do wyliczenia P(tomek ma dom) i P(tomek ma mieszkanie), a następnie porównania ich ze sobą i wybrania większej liczby. Załóżmy zatem na początku, że w naszym korpusie mamy następujące wartości:

Jak łatwo zauważyć wersja z domem jest o ok. 37% bardziej popularna w naszym przykładowym korpusie. Co na pierwszy rzut oka nie było aż tak oczywiste. Chociaż patrząc na same liczby już można było zauważyć przewagę słowa dom nad mieszkaniem.

6. Zastosowania w biznesie

Jeśli prowadzisz stronę internetową (np. sklep) to pewnie chcesz, żeby klient po wpisaniu skrzynka meka i tak otrzymał listę z produktami pomimo błędnego zapytania.

W takim przypadku wystarczy, że sprawdzisz listę najbardziej prawdopodobnych słów, które występują po słowie skrzynka, a następnie wybierzesz te najbardziej pasujące do Twojej oferty.

Na tym nie koniec, możliwe zastosowania zależą od efektu jaki chcesz uzyskać, a to tylko jedne z nich:

• dopełnianie brakujących słów
• korekta językowa
• sortowanie podpowiedzi według szansy ich wystąpienia