Parsowanie języka naturalnego z użyciem pochodnych

W październiku zeszłego roku obroniłam swoją pracę magisterską z informatyki analitycznej, którą poświęciłam parsowaniu języka naturalnego z użyciem pochodnych. W pracy przedstawiłam propozycję nowej formalizacji dla gramatyk języków naturalnych, opartą na formalizmie DCG (Definite Clause Grammars), reprezentującym gramatyki za pomocą klauzul logiki pierwszego rzędu. Nowy sposób formalizacji, oparty na modyfikacji gramatyk bezkontekstowych poprzez dodanie unifikowalnych atrybutów, daje możliwość zastosowania parsowania przez obliczanie pochodnej języka. W pracy opisuję również aplikację tej metody oraz uzyskaną złożoność obliczeniową parsowania. Poniżej przedstawiam jej wybrane fragmenty. W kilku miejscach dla czytelności uprościłam i skróciłam zapis. Całość pracy (m.in. dokładne definicje, dowody twierdzeń, algorytm nullowalności oraz analiza złożoności) jest dostępna w systemie APD.

WSTĘP

Język naturalny pod wieloma względami różni się od języków formalnych. Przede wszystkim, jest żywym, abstrakcyjnym, ciągle zmieniającym się bytem, istniejącym w intersubiektywnej przestrzeni posługujących się nim użytkowników. Nie mamy dostępu do systemu jakim jest język, a jedynie do jego użycia w postaci licznych wypowiedzi. Jedynym, co możemy próbować uchwycić w matematycznym modelu, jest próba rekonstrukcji tego systemu odpowiadająca jego bardziej standardowemu użyciu. Wiąże się to jednak również z wieloma trudnościami.

Język naturalny, co w zwięzły sposób pokazuje w zebraniu wyników naukowych na temat jego złożoności Antonio Branco [Branco, 2018], nie jest regularny i nie jest bezkontekstowy. Jak zwraca uwagę autor, jedną ze ścieżek badań nad opracowaniem formalizacji języka naturalnego jest próba ujęcia jak najmniejszej ilości dodatkowych ponad-bezkontekstowych wymagań w celu otrzymania parsera o wciąż praktycznym czasie działania. Takie podejście doprowadziło na przykład do powstania szeroko wykorzystywanej gramatyki struktur frazowych.

W tej pracy poświęcimy uwagę rodzajowi gramatyk wykorzystywanemu do automatycznej analizy składnikowej języka polskiego w analizatorze Świgra 2 [Woliński, 2019] [Świdziński, 1992] - formalizmowi DCG (Definite Clause Grammars) [Pereira and Warren, 1980]. Jak zauważa Woliński, można na ten formalizm patrzeć jak na “gramatykę unifikacyjną rozszerzającą gramatyki bezkontekstowe”. Jednostkami nieterminalnymi są w niej termy z języka Prolog, a wystąpienie w różnych miejscach tej samej zmiennej wymusza konieczność unifikacji atrybutów, które są za jej pomocą reprezentowane. W języku fleksyjnym jakim jest język polski, pozwala to np. uchwycić warunek zgodności rodzaju, liczby i przypadku pomiędzy frazą przymiotnikową a rzeczownikową. Woliński wskazuje również na to, że formalizm DCG jest równoważny co do siły wyrazu maszynie Turinga, jednak w zastosowaniu dla typowych gramatyk języków naturalnych wielomianowy czas parsowania może zostać zachowany. W poniższej pracy zaprezentujemy formalizm podobny do gramatyk DCG i dający możliwość zastosowania parsowania przez obliczanie pochodnej języka. Zaaplikujemy te metodę oraz zastanowimy się nad złożonością problemu w tej wersji.

FORMALIZM DCG

Formalizm nazwany Definite Clause Grammars (DCG) został bardzo dobrze opisany w pracy porównującej go z przyrostowymi sieciami przejść [Pereira and Warren, 1980]. Autorzy tej pracy zwracają uwagę na to, że rozszerza on gramatyki bezkontekstowe w kilku ważnych dla języka naturalnego obszarach: pozwala na zależność od kontekstu, dopuszcza drzewa wywodu o dowolnej strukturze, które pomagają zapewnić odpowiednią reprezentację znaczenia parsowanego zdania i daje możliwość obsługi dodatkowych warunków. Osiągniecie tych własności jest możliwe dzięki reprezentacji gramatyki jako programu logicznego w języku Prolog. Wykonanie programu w Prologu zachowuje się bowiem w podobny sposób jak parser typu top-down.

W stronę nowego formalizmu

W DCG Prologowa unifikacja termów jest wykorzystywana w trzech celach: wyrażania zgodności cech elementów zdania, pilnowania pozycji w tekście za pomocą specjalnych znaczników oraz składania drzewa wywodu. W nowym formalizmie wykorzystamy jedynie pomysł reprezentowania w ten sposób warunków, które musza spełnić poszczególne wyrazy, aby mogły ze sobą współwystępować, co pozwala zwięźle opisać złożoność języków naturalnych. Nie będziemy wykorzystywać złożonych termów, które w DCG opisywały miedzy innymi drzewa parsowania, a jedynie stałe i zmienne. Do dwóch pozostałych zastosowań użyjemy rozwiązań z nowoczesnych i klasycznych parsersów bezkontekstowych - obliczania pochodnych gramatyk oraz zapisywania informacji pozwalających odzyskać wynik z programowania dynamicznego.

NOWY FORMALIZM DLA GRAMATYK JĘZYKÓW NATURALNYCH

Nowy formalizm proponowany w tej pracy przyjmuje następujące założenia:

• Przedstawiamy rozszerzenie gramatyk bezkontekstowych, takie, że każdy nieterminal może mieć dodatkowo zbiór argumentów pewnej arnosci (stałej dla danego nieterminala, ale być może różnej pomiędzy różnymi nieterminalami).

• Dodajemy możliwość wprowadzenia dodatkowych warunków do produkcji, które pomagają wyrazić obostrzenia, które nie są bezpośrednio częścią produkcji, ale nie wyróżniamy ich w definicji gramatyki.

• Wyrazy będące różnymi realizacjami tego samego leksemu (reprezentującymi jego różne dopuszczalne formy) są przypisane do tego samego terminala, ale maja różne atrybuty określające ich kategorie. Podstawowe kategorie gramatyczne do uwzględnienia jako atrybuty (w języku polskim):

– liczba (pojedyncza, mnoga)

– osoba (1-3)

– rodzaj (męski osobowy, męski żywotny nieosobowy, męski nieżywotny, żeński,

nijaki)

– przypadek (mianownik, dopełniacz, celownik, biernik, narzędnik, miejscownik, wołacz)

– czas (przeszły, teraźniejszy, przyszły)

– aspekt (dokonany, niedokonany)

– tryb (przypuszczający, rozkazujący, oznajmujący)

Dodatkowy atrybut: cześć mowy (czasownik, rzeczownik, przymiotnik, liczebnik, zaimek, przysłówek, przyimek, spójnik, wykrzyknik, partykuła). Do zapisu gramatyki być może istotne do uwzględnia w kontekście walencji (łączliwości elementów języka) będą również inne dodatkowe cechy pozwalające określić dopuszczalność występowania danego leksemu razem z innymi.

• W produkcjach gramatyki mówimy jednak tylko o jednym typie symboli - nieteminalach. W trakcie parsowania ”zapominamy” o leksemie związanym z danym terminalem i reprezentujemy go jako jego zestaw kategorii. Wszystkie leksemy o tym samym zestawie kategorii są zatem nierozróżnialne i reprezentowane jako jeden symbol. Wybór kategorii musi być dla danego języka odpowiednio dobrany, aby dało się na jego podstawie otrzymać wszystkie potrzebne informacje do zdefiniowania kontekstu, w którym mogą wystąpić jednostki terminalne.

• Będziemy mówić o języku pośrednim i pośrednich formach zdaniowych, złożonych z parametryzowanych nieterminali odpowiadających grupom leksemów. Ciągi wyrazów można w łatwy sposób przekształcić na odpowiadająca im reprezentacje uogólniona. Przekształcenie w druga stronę zwróci nam zbiór pasujących ciągów konkretnych wyrazów. Będziemy operować na kilku równoważnych wariantach definicji wywiedlności w gramatyce. Kolejno wzbogacając nasz formalizm o nowe elementy, takie jak kontekst z termami do unifikacji, będziemy zmierzać od wersji łatwiejszej dowodowo w kierunku wersji łatwiejszej do przekształcenia w praktyczny algorytm.

Definicja gramatyki

Podstawienia

Podstawieniem nazywamy ciąg przypisań (podstawień jednostkowych) oznaczajacych, że za zmienną v podstawiamy syntaktycznie stałą c. Aplikacja podstawienia oznacza złożenie aplikacji przypisań z podstawienia - przypisania są aplikowane kolejno od lewej do prawej. Podstawienie sigma jest bardziej szczegółowe od tau (a tau ogólniejsze od sigma), jeśli istnieje tau' 0 takie, że sigma można otrzymać jako złożenie tau z tau'. Podstawienia w naturalny sposób tworzą praporzadek.

Kompatybilność

Element x gramatyki jest kompatybilny z elementem y, jeśli dla każdego podstawienia sigma istnieje podstawienie tau takie, że tau(y) = sigma(x). Zauważmy, że kiedy x jest sztywny, tzn. nie zawiera zmiennych, wtedy sigma(x)=x dla każdego sigma. W takim razie wystarczy, aby istniało takie tau, że tau(y)=x. Realacja kompatybilności również tworzy praporząddek.

Aplikacja schematów produkcji

Schematy produkcji odpowiadają zwykłym produkcjom z gramatyki bezkontekstowej, z tą jednak istotną różnicą, że nie są one bezpośrednio regułami przepisywania nieterminali, a szablonami tworzenia takich reguł za pomoca dowolnego ich uszczegóławiania przy użyciu podstawienia stałych za wszystkie występujące w schemacie zmienne. 

Pochodna gramatyki

Do definicji pochodnej gramatyki i parsowania za pomocą pochodnych stosujemy analogiczne podejście jakie wykorzystano w pracy [Henriksen et al., 2019] do gramatyk bezkontekstowych.

Będziemy obliczać pochodną języka pośredniego ze względu na ”sztywny” nieterminal - parametryzowany stałymi. Będzie od odpowiadał pewnemu zestawowi kategorii charakteryzującemu dana grupę nierozróżnialnych syntaktycznie leksemów.

Pochodną języka po nieterminalu t nazywamy zbiór wszystkich takich ciągów x, że tx należy do L. Pochodna języka po ciągu nieterminalni jest natomiast złożeniem pochodnych po kolejnych jego elementach. Ciąg należy do języka L wtedy i tylko wtedy, gdy słowo puste należy do języka pochodnego do L, co jest kluczową obserwacją wykorzystywaną w parsowaniu przy użyciu pochodnych.

Zdefiniujmy następujące reguły przepisywania schematów produkcji gramatyki G do otrzymania gramatyki generującej pochodna języka L(G) po T~c. Nieterminalami w nowej gramatyce są zarówno wszystkie nieterminale z G, jak i ich warianty ”z pochodną”.

Reguła O kopiuje oryginalne produkcje, reguła T obsługuje schematy produkcji z nieterminalem, dla którego obliczamy pochodna, a reguła N z pozostałymi nieterminalami. Pochodna relacje generowania definiujemy analogicznie jak w przypadku oryginalnej relacji, ale na podstawie pochodnych schematów produkcji.

Generacja z kontekstem

Powyższe definicje zakładają, że od razu wiemy jakie finalne podstawienie stałych za zmienne chcemy zastosować. Jednak z punktu widzenia algorytmu obliczania pochodnej, bardziej praktycznie jest, jeśli pozwolimy na odroczenie tej decyzji i zamiast od razu stosować pełne podstawienie, zaaplikujemy tylko konieczne przypisania i zbierzemy ”na później” dodatkowe wymagania równoważności pomiędzy termami, które są wymagane przez skorzystanie ze schematu produkcji.

Rozszerzone pojęcie podstawień

W tej wersji pozwalamy na podstawianie za zmienne dowolnych termów, nie tylko stałych. Wszystkie definicje pozostają analogiczne, ale kolejność dokonywania przypisań jest jeszcze bardziej istotna: przykładowo (v1 -> v2, v2 -> v3)(v1) = v3, podczas gdy (v2 -> v3, v1 -> v2)(v1) = v2.

Kontekst

Sposród wszystkich możliwych podstawień będziemy potrzebowali wyróżnic te, które spełniają pewne dodatkowe wymagania, polegające na występowaniu równoważności pomiędzy termami. Zbiór takich wymagań nazwiemy kontekstem. Przypisania (a zatem i całe podstawienia) możemy w naturalny sposób aplikować również do kontekstów. Mówimy, że podstawienie spełnia kontekst, jeżeli po jego zaaplikowaniu do kontekstu wszystkie równoważności z kontekstu są spełnione, to znaczy pomiędzy termami t1, t2 tworzącymi lewa i prawa strone równoważnosci, po podstawieniu występuje syntaktyczna równość. Kontekst jest sprzeczny (lub nie jest spełnialny), jeżeli nie istnieje żadne podstawienie, które go spełnia.

Rozszerzone pojecie kompatybilnosci

Element x gramatyki jest kompatybilny z elementem y w kontekście (przy założeniach) Gamma, wtedy i tylko wtedy, gdy dla każdego podstawienia sigma spełniającego Gamma istnieje podstawienie tau, takie, że jego aplikacja do y bedzie równa x przekształconemu przez sigma.

Generacja jezyka pośredniego

Najpierw generujemy z S niekoniecznie sztywną formę zdaniowa, a następnie podstawiamy stałe za wystepujace w niej zmienne, pilnując jednak, aby podstawienie to spełniało warunki, które ”nagromadziliśmy” podczas generacji.

Kontekst uwzględniamy również w obliczaniu pochodnej gramatyki. 

W kierunku wersji algorytmicznej

Powyższe reguły umożliwiaja wyznaczenie gramatyki, która wywodzi słowo puste wtedy i tylko wtedy, gdy oryginalna gramatyka wywodzi jakąś formę zdaniowa. To jednak jeszcze nie pozwala uzyskać algorytmu parsowania, ponieważ mamy nieskończenie wiele możliwosci wyboru kontekstów gwarantujacych kompatybilność i nullowalność, a niekoniecznie spełnialnych.

Aby poradzić sobie z tym problemem w pracy zostaje wprowadzene pojęcie najsłabszego wymaganego kontekstu. Następnie pokazujemy, że kontekst generowany przez kompatybilnosc jest najsłabszym kontekstem gwarantujacym kompatybilność.

Unifikacja

Bazujemy na pomyśle przedstawionym w pracy [Martelli and Montanari, 1982], jednak w naszym algorytmie operujemy jedynie na stałych i zmiennych, a unifikujemy ze soba nie dwa termy, a cały zbiór warunków z kontekstu. Kontekst Gamma definiuje pewną relacje równoważności i to elementy klas tej relacji będziemy chcieli ze soba unifikować. Klasy tej relacji możemy reprezentować na przykład wykorzystując strukturę danych find-union. W ten sposób otrzymamy podział, dla którego tworzymy graf zależności. Jednak ponieważ nie operujemy na termach złożonych, a pomiędzy zmiennymi a stałymi nie występują żadne zależności, graf ten składa sie z samych wierzchołków izolowanych. W takim grafie nie może istnieć cykl, ale nie zawsze znajdziemy najbardziej ogólne podstawienie - może się okazać, że kontekst Gamma jest sprzeczny i zawiera w którejś z klas dwie różne stałe (w klasycznym pojeściu byłyby to funkcje zeroargumentowe). Zwracamy wtedy błąd. Jeśli natomiast w każdej klasie sa albo same zmienne, albo same wystąpienia tej samej stałej i zmienne, tworzymy najbardziej ogólne podstawienie w nastepujacy sposób:

• dla zbiorów z samymi zmiennymi vi1...vik dodajemy do podstawienia przypisania wszystkim zmiennym ze zbioru zmiennej o najniższym indeksie (poza przypisaniem jej do niej samej)

• dla zbiorów z wystąpieniami tej samej stałej c i zmiennymi vi1...vik dodajemy do podstawienia przypisania wszystkim zmiennym ze zbioru stałej c.

Pochodne wyższych rzędów i złożoność obliczeniowa

Jak zauważa w swojej pracy Henriksen [Henriksen et al., 2019] i co przenosi się na prezentowany tutaj formalizm, naiwne iterowanie obliczania pochodnej po kolejnych terminalach może prowadzić do wykładniczego rozmiaru gramatyki. Każda kolejna pochodna może bowiem prowadzić do przemnożenia liczby schematów produkcji o stałą (każdy z nieterminali parametryzowanych z prawej strony każdej produkcji może być nullowlany), co w rezultacie może doprowadzić do wykładniczego wzrostu rozmiaru wraz z długoscią n parsowanego zdania. Aby tego uniknąć, autorzy pracy proponują sprytniejsze obliczanie pochodnych wyższych rzędów.

Przykładowa gramatyka i słownik

Poniżej przedstawiono przykład, który ilustruje jak mogłaby wyglądać gramatyka i słownik dla języka polskiego. Dla uproszczenia przyjęto dwa rodzaje walencji dla czasowników: 0-argumentowe czasowniki nieprzechodnie i 1-argumentowe czasowniki przechodnie, dla których należy zdefiniować przypadek, który musi przyjąć argument. Dodano też określenie rodzaju dla czasowników, mimo, że w jezyku polskim ta kategoria wystepuje nie we wszystkich czasach i założono, że podmiot zdania musi wystąpić w mianowniku. Dla czytelności symbole nieterminalne zapisano z wielkich liter, argumenty nieterminali podano w nawiasach, zmienne zapisano bez cudzysłowia, a stałe w cudzysłowie.

Przez powyższą gramatykę i słownik są akceptowane na przykład nastepujace zdania: ”Janek czyta książkę o psach” oraz ”Mężczyzna spał”. Zwróćmy uwage na to, że wyrazy ”Janek” i ”mężczyzna” są nierozróżnialne po przekształceniu na zapis nieterminalowy. Nieterminalowej reprezentacji czasownika ”czyta” nie będziemy mogli zastosować w drugim schemacie produkcji, ponieważ stała ”przechodni” nie jest kompatybilna ze stałą ”nieprzechodni”. Analogicznie, reprezentacji czasownika ”spał” nie będziemy mogli użyć w schemacie trzecim, a będzie pasował do drugiego.

Do bardziej skomplikowanych przykładów, możemy wykorzystać również dodatkowe warunki, które w formalizmie DCG korzystajacym z Prologa były zapisywane jako osobne cele w nawiasach klamrowych. W naszym formalizmie możemy na nie przeznaczyć osobne nieterminale parametryzowne i dodać do gramatyki schematy produkcji prowadzące z akceptowanych kombinacji parametrów w epsilon. W ten sposób można wyrazić na przykład wymagania dotyczące występowania negacji.

Podsumowanie i kierunki rozwoju

Zaproponowaliśmy nowy formalizm dla gramatyk jezyków naturalnych, inspirowany formalizmem DCG (Definitive Clause Grammars), a pozwalający na aplikację metody parsowania przy użyciu pochodnych. Proponujemy nastepujace kierunki rozwoju:

• Zaproponowanie efektywnych struktur danych do przechowywania najsłabszego kontekstu wymaganego do kompatybilności i nullowalności.

• Zaproponowanie szybszego algorytmu na sprawdzanie nullowalności.

• Zapis całej gramatyki rzeczywistego jezyka naturalnego (np. języka polskiego poprzez przekształcenie pomysłów z pracy [Wolinski, 2019] na prezentowany formalizm).

• Implementacja parsera opartego o przedstawiony formalizm i sprawdzenie jego praktycznej złożoności na przykładowej gramatyce jezyka naturalnego.

Literatura

[Branco, 2018] Branco, A. (2018). Computational complexity of natural languages: A reasoned overview. In COLING2018, pages 10–19.

[Henriksen et al., 2019] Henriksen, I., Bilardi, G., and Pingali, K. (2019). Derivative grammars: A symbolic approach to parsing with derivatives. In Proceedings of the ACM on Programming Languages, volume 3. Association for Computing Machinery, New York, NY, United States.

[Martelli and Montanari, 1982] Martelli, A. and Montanari, U. (1982). An efficient unification algorithm. In ACM Transactions on Programming Languages and Systems, volume 2, page 258–282. Association for Computing Machinery, New York, NY, United States.

[Pereira and Warren, 1980] Pereira, F. C. N. and Warren, D. H. D. (1980). Definite clause grammars for language analysis - a survey of the formalism and a comparison with augmented transition networks. In Artificial Intelligence, volume 13, pages 231–278. North-Holland Publishing Company.

[Wolinski, 2019] Wolinski, M. (2019). Automatyczna analiza składnikowa jezyka polskiego. Wydawnictwa Uniwersytetu Warszawskiego.

[Swidzinski, 1992] Swidzinski, M. (1992). Gramatyka formalna jezyka polskiego. Wydawnictwa Uniwersytetu Warszawskiego.