Raport z projektu zaliczeniowego, Sztuczna Inteligencja '07

Rozpoznawanie zniekształconego słowa w zdaniu

Jakub Michaliszyn
Uniwersytet Wrocławski
10 czerwca 2006

Zadanie

Dane: Zdanie, w którym jedno ze słów jest zastąpione wyrażeniem regularnym.
Zadanie: Wyznaczyć najbardziej prawdopodobne w kontekście tego zdania słowo, które pasuje do zadanego wyrażenia regularnego.

Przykładowe zastosowania

• Wybór właściwego słowa podczas pisania smsa z użyciem słownika T9 - w tym celu uruchamiamy algorytm dla kolejnych wpisywanych słów
• Korekta błędów ortograficznych - np. możemy napisać "A n[uó]ż się uda" i sprawdzić, która forma w tym kontekście jest bardziej prawdopodobna
• Wybór właściwego słowa przez program do rozpoznawania tekstu pisanego - podobnie jak w przypadku smsów, algorytm może być uruchamiany dla kolejnych wczytywanych słów
• Odzyskiwanie sensu wulgaryzmów - często w tekstach pisanych słowa wulgarne są "gwiazdkowane", np. "poj***ny". Program komunikujący się z użytkownikiem w niektórych sytuacjach powinien wiedzieć, jakie dokładnie słowo zostało wykropkowane, np. zdanie "jesteś z******* botem" może być zarówno pozytywne, jak i negatywne.
• Drobne wsparcie do różnych łamigłówek, np. krzyżówek: jeśli mamy hasło "ogoniasty płaz" oraz litery "...a.a..ra" to można mieć nadzieję, że słowo "salamandra" w kontekście "ogoniastego płazu" pojawia się częściej, niż np. "ambasadora"

Opis metody

Wprowadzenie

Rozważany problem jest mocno zbliżony do problemu dezambiguacji semantycznej, opisanej w [1]. Podobieństwo wynika z tego, że jeśli będziemy traktować wyrażenie regularne jako zadane słowo, a pasujące doń wyrazy jako domniemane znaczenia tego słowa, to problem wyboru odpowiedniego słowa sprowadza się do wyboru odpowiedniego znaczenia. Zatem do rozwiązania mojego problemu wykorzystałem wiedzę, jaką specjaliści z NLP już zgromadzili, uzupełniając znane algorytmy własnymi pomysłami

Problem dezambiguacji może być rozwiązany na kilka sposobów, ale większość wymaga pewnej wiedzy o języku (np. słownika morfosyntaktycznego, tezaurusa) i przez to nie może być łatwo przeniesiona na rozważany wariant problemu. Uniwersalną metodą jest wyliczanie wartości ze wzoru wynikającego (przy pewnych założeniach) ze wzoru Bayesa, opisanego niżej.

Metoda Bayesa - wprowadzenie teoretyczne

Zauważmy, że interesuje nas wybór takiego słowa, które jest najbardziej prawdopodobne w swoim kontekście, czyli obliczenie argmax_w(P(w|k))., gdzie k jest kontekstem, a w przebiega wszystkie pasujące słowa. Z definicji prawdopodobieństwa warunkowego mamy P(w|k) = P(k|w)P(w)/P(k), zatem argmax_w(P(w|k)) = argmax_w(P(k|w)*P(w)). Załóżmy teraz, że k = {k₁,k₂, ..., k_s} (zatem tracimy informację o tym, w jakiej kolejności były słowa - później tę informację będziemy starali się uwzględnić). Naiwne założenie Bayesowskie wygląda następująco:

P(k|w)=P(k₁|w)*P(k₂|w)*...*P(k_s|w) zatem zakładamy, że wystąpienia poszczególnych słów w zdaniu są niezależne. Z definicji prawdopodobieństwa warunkowego mamy P(k_i|w) = P(k i w)/P(w) Zatem otrzymujemy ostatecznie:
argmax_w(P(w|k))=argmax_w(P(w)*P(k₁|w)*P(k₂|w)*...*P(k_s|w)) Z powodu tego, że prawdopodobieństwa mogą być bardzo małe, na ich wartości nakłada się logarytm:
argmax_w(P(w|k))=argmax_w(log (P(w)) + log(P(k₁|w)) + ... + log (P(k_s|w))) Dla uniknięcia wartości zerowych stosuje się wygłazdanie prawdopodobieństw. Wyprowadzenie nieco bardziej ogólnego wzoru można znaleźć w [2].

Ograniczanie słownika

Główną przeszkodą przy implementowaniu algorytmu było to, że, w odróżnieniu od zwykłej dezambiguacji, mój zbiór "znaczeń" słowa może być duży, a nawet potencjalnie nieskończony (np. dla wyrażenia .*). Z punktu widzenia samego algorytmu ten problem został ominięty - aplikacja po prostu przyjmuje jako parametr funkcję, która zwraca odpowiedni zbiór słów na podstawie wyrażenia regularnego i kontekstu. Najprostsza funkcja może zwracać wszystkie słowa ze słownika pasujące do wyrażenia, bardziej złożone funkcje mogą korzystać z kontekstu słowa oraz z częstości wystąpień słowa w korpusie. Bardziej szczegółowe omówienie zaimplementowanych funkcji jest w dziale "Uwagi implementacyjne".

Główna pętla algorytmu

W swojej zasadniczej części algorytm przegląda pliki, traktując ich kolejne linie jako konteksty językowe - to mogą być zdania, akapity, wpisy słownikowe, bigramy itp. Niech LSK oznacza liczbę słów kontekstu wejściowego, a LPS oznacza liczbę pasujących słów, zwróconych przez funkcję omawianą w poprzednim podpunkcie. Algorytm wypełnia tablicę macierz[LSK+1][LPS+1] tak, że dla i<LSK i j<LPS w pole macierz[i][j] jest wstawiana liczba wystąpień i-tego słowa z kontekstu wejściowego w jednym językowym wraz z j-tym słowem. Ponadto macierz[LSK][i] zawiera liczbę kontekstów językowych, w których wystąpiło i-te proponowane słowo, a macierz[i][LPS] zawiera liczbę kontekstów językowych, w których wystąpiło i-te słowo z kontekstu wejściowego. Wpis macierz[LSK][LPS] zawiera liczbę wszystkich kontekstów językowych wczytanych przez program przy generowaniu macierzy.

Obliczanie wyników

Po przygotowaniu takiej macierzy algorytm powierza zadanie zwrócenia wyniku drugiej funkcji podanej jako parametr wywołania i kończy wynik. W najprostszej wersji ta funkcja podstawia po prostu odpowiednie liczby do wzoru Bayesa, a w bardziej skomplikowanej różnym czynnikom są przypisywane dodatkowo odpowiednie wagi.

Wykorzystane źródła

Do generowania kontekstów językowych wykorzystałem darmowe materiały dostępne w internecie, w szczególności konkordacje , korpus frekwencyjny oraz słownik słów do gry literaki dostępny na stronie kurnik.pl. Do testów wykorzystałem również stosunkowo mały zbiór bigramów, przygotowany jako jedno z zadań z NLP w minionym semestrze na podstawie bardzo ograniczonego korpusu IPAN ze strony korpus.pl. Do testów zostały wykorzystane losowe strony Wikipedii oraz teksty znalezione w darmowej wersji korpusu PWN . Alternatywne źródła mogą być podawane jako argument w linii poleceń.

Uwagi implementacyjne

Rozwiązanei zostało zaimplementowane w OCamlu. Szczegóły dotyczące kompilacji znajdują się w nagłówku pliku si.ml. Skompilowany program można wywoływać z następuacymi parametrami:
si [-h1 liczba] [-plik1 nazwa] [-h2 liczba] [-w0] [-t] [-k nazwa]* [nazwa_pliku_wejsciowego]
gdzie:

• -h1 n oznacza, że zostanie użyta n-ta funkcja heurystyczna do wyborów słów ze słownika (domyślnie 0)
• -plik1 nazwa określa plik, z którego będzie korzystać powyższa funkcja (domyślnie sl-kon.txt)
• -h2 n oznacza, że zostanie użyta n-ta funkcja heurystyczna do przetwarzania wyników (domyślnie 0)
• -w0 ogranicza liczbę wypisywanych komunikatów do minimum
• -t sprawia, że program po zakończeniu wypisze czas wykonania
• -k nazwa określa nazwę pliku, który zostanie wykorzystany do obliczania zależności. Można podać dowolnie wiele plików po kolejnych znacznikach -k. Domyślna lista plików to ("a-publi.txt", "b-prasa.txt", "c-popul.txt", "d-proza.txt", "e-dramat.txt", "bigramy.txt", "kon2.txt")

Wpisanie si --help wyświetla pomoc. Jeśli nie zostanie podana nazwa pliku wejściowego, program poprosi o wpisanie zdania z klawiatury. Zdanie wejściowe powinno zawierać jedynie litery i spacje z wyjątkiem wyrażenia regularnego, poprzedzonego znakiem "#".

Dostępne są następujące funkcje heurystyczne wybierające słowa ze słownika:

• 0 - funkcja przyjmuje jako parametr plik z listą słów i wybiera wszystkie pasujące
• 1 - funkcja przyjmuje jako parametr plik z parami słowo liczba wystąpień (jedna para przedzielona spacją w każdej linii), ale działa tak, jak poprzednia funkcja
• 2 - funkcja przyjmuje jako parametr plik z parami jak wyżej i zwraca najwyżej t najczęściej występujących słów (gdzie t jest stałą równą 20)
• 3 - funkcja przyjmuje jako parametr plik z listą słów i zwraca liczbę pasujących słów jako jedyny element tablicy pasujących słów (to się przyda do testów)

Natomiast dostępne funkcje obliczające wyniki są następujące:

• 0 - funkcja, która oblicza wynik wg zmodyfikowanego wzoru, przypisując większe wagi słowom będącym bliżej wzorca
• 1 - funkcja, która oblicza wynik dokładnie wg udowodnionego wcześniej wzoru
• 2 - funkcja obliczająca wyniki wg wzoru log (P(w)) + log(P(k₁ i w)/P(k₁)) + ... + log (P(k_s i w)/P(k_s)). Ten wzór nie ma żadnego teoretycznego uzasadnienia, a intuicja jest taka, że premiuje się te słowa z kontekstu, które występują rzadziej.
• 3 - funkcja sumująca liczbę wspólnych wystąpień danego słowa i słów z kontekstu
• 4 - funkcja obliczająca wyniki wg wzoru log(P(k₁|w)) + ... + log (P(k_s|w)), czyli mniej zależna od liczby wystąpień słowa w korpusie.
• 5 - funkcja dodatkowo premiująca rzadkie wyrazy, wg wzoru log(P(k₁ i w)/(P(k₁)*P(w))) + ... + log (P(k_s i w)/(P(k_s)*P(w)))
• 6 - funkcja wypisująca całą macierz obliczoną przez program

Program zasadniczo nie obsługuje polskich znaków - po uruchomieniu będzie się starał je usunąć, co uda mu się pod warunkiem, że kodowanie pliku wejściowego będzie identyczne z kodowaniem w pliku plfonts.

Aplikacja wymaga, by pliki podane jako korpus zawierały kolejne konteksty w postaci wyrazów oddzielonych spacją, jeden kontekst w jednej linii, bez polskich znaków. Dodatkowo do aplikacji zostały dołączone dwa programy: tworz_slownik.ml, który z danego korpusu tworzy słownik (opcjonalnie z informacją o częstotliwościach słów) oraz sms.ml, który "psuje" podane zdanie na jeden z kilku sposobów. Szczegóły dotyczące tych programów znajdują się w nagłówkach kodów źródłowych.

Przykładowe testy

Przykładowe sesje

Na początek dwa przykłady pokazujące, że wybór słowa rzeczywiście zależy od kontekstu:

Sesja 1.

• si
• Podaj zdanie (bez znakow interpunkcjyjnych i polskich liter), w ktorym dokladnie jeden z wyrazow jest poprzedzony znakiem # i zapisany w postaci wyrazenia regularnego:
• W sadzie rosna jablka #gr.*ki oraz sliwki

• gruszki: 49.13
  grzegorzki: 47.26
  grodkowski: 44.46
  grzegorzewski: 44.25
  grzechotki: 16.83
  grochowski: 16.36
  groszkowski: 16.33
  grodzicki: 16.14
  grafiki: 15.64
  grodecki: 14.99
  grupki: 14.99
  gronowski: 14.85
  grabowki: 14.51
  groszki: 14.27
  grotowski: 14.27
  grzybki: 12.95
  gromadki: 12.83
  grudki: 12.68
  gromadzki: 12.68
  grzadki: 12.05
  grecki: 11.69
  grabowski: 10.38
  grzybowski: 0.72
  grodzienski: 0.48
  gromyki: 0.24
  grocholski: 0.00

Sesja 2.

• si
• Podaj zdanie (bez znakow interpunkcjyjnych i polskich liter), w ktorym dokladnie jeden z wyrazow jest poprzedzony znakiem # i zapisany w postaci wyrazenia regularnego:
• komputer moze sluzyc do tworzenia roznorakiej #gr.*ki na przyklad rysunkow czy fotomontarzy zdjec

• grafiki: 306.71
  grabowski: 275.81
  grzadki: 268.72
  gruszki: 223.26
  grzegorzki: 196.91
  grzybki: 187.87
  grecki: 185.53
  gromadzki: 182.62
  gromadki: 182.29
  groszki: 177.45
  grodzienski: 152.40
  grotowski: 145.92
  grupki: 135.65
  grodecki: 121.14
  grzybowski: 107.21
  grodzicki: 106.06
  grabowki: 105.48
  grocholski: 105.48
  grudki: 103.03
  grzechotki: 48.02
  grzegorzewski: 5.65
  groszkowski: 5.65
  grochowski: 4.50
  grodkowski: 4.50
  gromyki: 4.50
  gronowski: 0.00

Teraz przykład wykorzystania programu do rozstrzygania wątpliwości ortograficznych

Sesja 3.

• si
• Podaj zdanie (bez znakow interpunkcjyjnych i polskich liter), w ktorym dokladnie jeden z wyrazow jest poprzedzony znakiem # i zapisany w postaci wyrazenia regularnego:
• nasi podopieczni wyjechali nad #mo[zr]*e na 2 tygodnie

• morze: 19.66
  moze: 0.00

Najczęstsze słowo:

Sesja 4.

• si -h1 2 -h2 1
• Podaj zdanie (bez znakow interpunkcjyjnych i polskich liter), w ktorym dokladnie jeden z wyrazow jest poprzedzony znakiem # i zapisany w postaci wyrazenia regularnego:
• #.*

• w: 1.03
  i: 0.94
  sie: 0.87
  na: 0.79
  nie: 0.78
  z: 0.71
  to: 0.59
  do: 0.58
  ze: 0.56
  a: 0.37
  o: 0.32
  jest: 0.29
  jak: 0.24
  co: 0.16
  ale: 0.11
  tak: 0.10
  po: 0.07
  od: 0.03
  tym: 0.01
  juz: 0.00

Sesja 5.

Teraz test, który miał pokazać, z czym najczęściej występuje słowo "lubi". Uwydatnie on jedną z wad algorytmu - jeśli słowo z konteksty może być wynikiem, to jest ono wysoko punktowane.

• si -h2 3
• Podaj zdanie (bez znakow interpunkcjyjnych i polskich liter), w ktorym dokladnie jeden z wyrazow jest poprzedzony znakiem # i zapisany w postaci wyrazenia regularnego:
• #.* lubi

• lubi: 343.00
  nie: 139.00
  sie: 100.00
  to: 87.00
  a: 86.00
  ze: 74.00
  z: 67.00
  na: 60.00
  tak: 57.00
  i: 52.00
  bo: 49.00
  jak: 46.00
  ona: 42.00
  ale: 39.00
  ja: 39.00
  on: 39.00
  o: 37.00
  ma: 33.00
  pan: 32.00
  co: 32.00
  mnie: 30.00
  tylko: 30.00
  pani: 29.00
  w: 29.00
  bardzo: 28.00
  mu: 26.00
  go: 24.00
  nawet: 21.00
  (...)

Sesja 6.

Przykład na użycie parametrów -w0 i -t

• S:\programy\si>si -h1 1 -h2 5 -w0 -t
• Podaj zdanie (bez znakow interpunkcjyjnych i polskich liter), w ktorym dokladnie jeden z wyrazow jest poprzedzony znakiem # i zapisany w postaci wyrazenia regularnego:
• wyjatkowo ladna #[pgqd][oa].*[oa].*a spowodowala ze wielu wroclawian zdecydowalo sie na wyjazd poza miasto

• pogoda 6.906

Sesja 7.

Przykład literacki

• si
• Podaj zdanie (bez znakow interpunkcjyjnych i polskich liter), w ktorym dokladnie jeden z wyrazow jest poprzedzony znakiem # i zapisany w postaci wyrazenia regularnego:
• jestem pierwszy jestem w tyle nieomylny choc sie myle jestem sedzia i sadzonym winnym i uniewinnionym chociaz teraz jestem wrogiem #przy.* tez byc moge jestem zwrotka i refrenem wychowaniem szkola genem

• przy: 1589.17
  przyszedl: 1472.89
  przyjdzie: 1446.18
  przyklad: 1440.19
  przyjac: 1421.82
  przyszlo: 1386.26
  przyszlosci: 1345.25
  przyszedlem: 1320.79
  przynajmniej: 1290.12
  przyszli: 1287.89
  przypomnial: 1282.47
  przypomina: 1269.30
  przyjaciol: 1263.16
  przyczyna: 1260.09
  przyszlosc: 1225.99
  przysiegam: 1211.42
  przyjechal: 1179.14
  przyczyny: 1161.39
  przykro: 1146.12
  przypadku: 1129.84
  przyniesc: 1122.65
  przygotowany: 1119.51
  przynosi: 1118.41
  przyda: 1112.21
  przygotowuje: 1108.89
  przyznam: 1107.65
  przychodza: 1090.60
  przypadkowo: 1070.09
  przyjemnosci: 1064.90
  przypuszczam: 1003.22
  przyjemnosc: 997.22
  przypadkiem: 989.55
  przypominac: 980.18
  przyjsc: 960.51
  przyjacielu: 956.58
  przyjecie: 947.51
  przyszlym: 943.31
  przyjdziesz: 941.75
  przypada: 940.78
  przypomnialem: 940.04
  przyjaciele: 930.11
  przypadkow: 928.47
  przypomniala: 924.93
  przychodze: 923.60
  przyjde: 923.16
  przyjecia: 916.25
  przywiazuje: 908.14
  przyjacielem: 903.43
  przyznac: 899.69
  przygod: 897.09
  przyniose: 893.02
  przyjechalem: 889.90
  przypomniec: 866.76
  przyjaciolka: 864.03
  przystapie: 862.85

Duże testy

Do przeprowadzenia testów stworzyłem specjalny program, który "losowo" psuje podane zdanie, a konkretnie zamienia losowo wybrane słowo z podanego zdania na wyrażenie regularne według wybranego schematu - od zamiany słowa na format smsowy (np. kot -> [jkl][mno][tuv]) przez zamianę poszczególnych liter na "." do zamiany słowa na .*. Do testów użyłem zdań z różnych źródeł - stron korpus.pwn.pl, gazeta.pl, wikipedia.org (losowe strony), google.pl i tej dokumentacji. Wyniki obliczałem wywołując program dla kolejnych plików wejściowych w pętli. Szczegółowe wyniki dostępne są w załączonym pliku, natomiast statystyczne wyniki pokazuje poniższa tabelka:

Wyniki	h2 = 0	h2 = 1	h2 = 2	h2 = 3	h2 = 4	h2 = 5	Suma
h1 = 0	60,6%	58,6%	59,6%	54,5%	57,6%	55,6%	57,8%
h1 = 2	57,6%	57,6%	58,6%	55,6%	54,5%	54,5%	56,4%
h1 = 3	33,48%
Suma*	59,1%	58,1%	59,1%	55,1%	56,1%	55,1%	57,1%

* - z pominięciem h1 = 3

Wynik dla h1=3 odzwierciedla skuteczność, jaką byśmy uzyskali, gdybyśmy po prostu losowali słowo. Wyniki są do siebie bardzo zbliżone, co wynika po części z faktu, że w wielu przypadkach program znajdował w słowniku co najwyżej jedno pasujące słowo w słowniku, przez co wybór funkcji nie miał znaczenia. Statystyka, która nie uwzględnia tych sytuacji, jest nieco bardziej zróżnicowana:

Wyniki	h2 = 0	h2 = 1	h2 = 2	h2 = 3	h2 = 4	h2 = 5	Suma
h1 = 0	50%	47,1%	48,6%	41,4%	45,7%	42,9%	46%
h1 = 2	45,7%	45,7%	47,1%	42,9%	41,4%	41,4%	44%
h1 = 3	11,64%
Suma*	48,3%	46,4%	47,8%	42,2%	43,6%	42,2%	45%

* - z pominięciem h1 = 3

Warto również wspomnieć, że średni czas obliczania przy użyciu funkcji h1 oznaczonej numerem 0 wyniósł 7,5 sekundy, natomiast dla funkcji oznaczonej liczbą 2 - 3,7 sekundy. Po odrzuceniu testów z oczywistą odpowiedzią mamy odpowiednio 10,5 sekundy oraz 5,1 sekundy.

Wnioski i propozycje rozszerzeń

Otrzymana przeze mnie skuteczność w najlepszym przypadku rzędu 60% nie wygląda imponująco. Jednakże nawet dla człowieka problem odzyskania utraconego słowa nie zawsze jest łatwy do rozwiązania, np. w teście "wyznaczyc najbardziej prawdopodobne w kontekscie tego zdania slowo ktore pasuje do #.* wyrazenia regularnego " można wymyślić bardzo wiele pasujących słów (zadanego, badanego, danego, bieżącego, wybranego, ustalonego itd.). Testy pokazują, że obliczanie wyników zgodnie ze wzorem Bayesa jest dużo lepsze, niż naiwne sumowanie wspólnych wystąpień, natomiast najlepsze wyniki uzyskuje się premiując dodatkowo wyrazy bliskie wyrażeniu regularnemu.

Znaczącą poprawę funkcjonalności aplikacji można by uzyskać przez dodanie do niej sprawdzania poprawności gramatycznej, jednakże wymaga to zdobycia pełnego opisu języka. Ma to też tę wadę, że program straci przez to uniwersalność - obecnie zmiana języka wymaga jedynie wymiany używanych plików słownika oraz korpusu. Zauważmy ponadto, że sprawdzanie poprawności gramatycznej można zaszyć w każdej z funkcji heurystycznych. Znaczną poprawę powinno przynieść użycie większego korpusu, jednakże takie korpusy nie są darmowe. Gdyby jednak program miał przetwarzać korpusy o rozmiarze rzędu 1 GB, to konieczne byłoby stworzenie odpowiedniego indeksu odwróconego w celu szybkiego przeszukiwania danych.

Literatura

1. Word sense disambiguation, Wikipedia angielska.
2. Naive Bayes classifier, Wikipedia angielska.