Gramatyki

[Na marginesie: słÄ‚Å‚w węzeł i wierzchołek używam zamiennie (tzn. używam pierwszego bo jest krÄ‚Å‚tsze).]

RozbiÄ‚Å‚r zdania nie musi zatrzymywać się na poziomie słowa: dzięki automatycznemu podziałowi słowa na morfemy możemy zmniejszyć wielkość słownika, a nawet radzić sobie z nieznanymi słowami. Dla przykładu, system konwersacyjny może swobodnie zapytać użytkownika o znaczenie wyrazu, kiedy jego rola gramatyczna jest dzięki analizie w pełni określona i znane są wzorce odmiany.

OgÄ‚Å‚lnie o parsowaniu: Parsing Techniques - A Practical Guide. Istotne hasła: metoda CYK, chart parsing, parsowanie top-down vs. bottom-up, Earley parser, metody LR.

Functional Pearls: Functional Chart Parsing of Context Free Grammars by Peter LjunglĂśf.

Inkrementacyjna unifikacja (inkrementacyjne rozstrzyganie więzÄ‚Å‚w)

Drzewa dowodÄ‚Å‚w (proof trees) jako drzewa rozbioru dla gramatyk unifikacyjnych, zobacz Logic, Programming and Prolog (2ed) rozdz. 3.6. Oczywiście chcemy możliwie szybko odcinać błędne ścieżki wyprowadzeń, dlatego (jak w Prologu), od razu propagujemy rozwiązania generowanych rÄ‚Å‚wnań. “Funkcję obliczeń” R wyznacza nam algorytm chart-parsera. (Rozdział 3.6 książki o Prologu mÄ‚Å‚wi tylko o doklejaniu płytkich drzew odpowiadających produkcjom, u nas krawędzi z kropką na samym początku, ale idea przenosi się na doklejanie głębszych drzew. Pełne gramatyki unifikacyjne są opisane w rozdziale o “Definite Clause Grammars”.)

1. Dzielimy gramatykę na reguły leksykalne/słownikowe i pozostałe. Reguły leksykalne to te, ktÄ‚Å‚rych prawa strona rozpoczyna się od terminala (często będzie to tylko terminal). Tylko nieleksykalne reguły wstawiamy jako “pętelki” w każdą pozycję charta, reguły leksykalne grupujemy w słownik ze słÄ‚Å‚w w zbiÄ‚Å‚r reguł, i dla każdego słowa wstawiamy do charta przeskakujące to słowo krawędzie.
2. Samo wstawianie “pętelek” do charta możemy potraktować leniwie: zgromadzić reguły nieleksykalne w słownik indeksowany (np.) przez część mowy (lub nazwę frazy) i w momencie wybierania z charta krawędzi do przedłużenia, dorzucić krawędzie odpowiadające regułom ze słownika dla potrzebnej części mowy. W ten sposÄ‚Å‚b nie przeglądamy za każdym razem wszystkich reguł (nieleksykalnych).
3. Można pokusić się o bardziej skomplikowane optymalizacje. Można badać klasy leksykalne (np. verb = transitive verb + intransitive verb), ktÄ‚Å‚rych derywacje z danej reguły wymagają / nie dopuszczają (tzn. klasy słÄ‚Å‚w, ktÄ‚Å‚re muszą / nie mogą się pojawić we frazie, ktÄ‚Å‚rej wyprowadzenia korzeniem jest dana reguła). Można skompilować gramatykę do bardziej wydajnej postaci (bardziej podobnej do postaci Greibach), ale w czasie parsowania rekonstruować drzewo rozbioru względem oryginalnej gramatyki.

Pomysły na tłumaczenie błędÄ‚Å‚w gramatycznych

Jeśli zdanie jest niepoprawne gramatycznie, to parsing kończy się bez krawędzi obejmujących całe zdanie. Szukamy (dynamicznie) ciągÄ‚Å‚w krawędzi dających minimalne pokrycie rozłączne zdania (tzn. minimalną ilość krawędzi, po ktÄ‚Å‚rych można przeskoczyć z początku na koniec). Budujemy nowy chart, tylko z krawędzi z tych ciągÄ‚Å‚w. Do standardowych reguł chart-parsera dodajemy następujące reguły obsługi błędÄ‚Å‚w:

Nasyć chart przy pomocy poszerzonego zbioru reguł (poszerz odpowiednio używany algorytm parsowania). ZwrÄ‚Å‚ć użytkownikowi drzewa rozbioru odpowiadające krawędziom obejmującym całe zdanie wyprowadzone z minimalną ilością zastosowań reguł obsługi błędÄ‚Å‚w, razem z zapamiętanymi komentarzami.

Obecny Speagram: trochę ogÄ‚Å‚lniejsze gramatyki struktur frazowych

Po lewej stronie produkcji, wstawiamy term A opisujący własności drzewa rozbioru z korzeniem wyprowadzonym z tej produkcji, zależne od własności poddrzew. Po prawej stronie produkcji, zamiast nieterminali wstawiamy term A_i opisujący interesujące nas własności, oraz relację R_i, w ktÄ‚Å‚rej term B opisujący potencjalne poddrzewo rozbioru ma być względem termu A_i. Trzy rodzaje relacji wydają się rozsądne, w żargonie językÄ‚Å‚w programowania nazywają się one: “pozycja inwariantna” (=), “pozycja kowariantna” (<), “pozycja kontrawariantna” (>). Budując drzewo rozbioru zdania pilnujemy niesprzeczności wymagań. Przykłady (italiką oznaczone są terminale, a znakiem zapytania zmienne w termach własności, tzn. w typach):

z przedchodniości, ta produkcja jest rÄ‚Å‚wnoważna następującym:

Konstrukcja z językÄ‚Å‚w programowania. let X be Y oznacza, że X oblicza się do Y. Żeby to było dopuszczalne, Yki muszą być Xami, tzn. typ Yka musi być podtypem Xa.

Przymiotnik opisujący frazę rzeczownikową może mieć typ ogÄ‚Å‚lniejszy niż ta fraza, na przykład może być rodzaju męskiego gender=m, ktÄ‚Å‚ry jest nadtypem rodzajÄ‚Å‚w m1, m2 i m3.

Są dwie możliwe interpretacje etykiet brakujących w opisie: sensowna formalnie interpretacja abstrakcyjna oraz praktyczna interpretacja polimorficzna. Interpretacja abstrakcyjna pod niewyspecyfikowane wartości etykiet podstawia Top, a interpretacja polimorficzna ignoruje etykiety nie występujące jednocześnie po obu stronach porÄ‚Å‚wnania. W interpretacji abstrakcyjnej NP[number=singular] oznacza zbiÄ‚Å‚r wszystkich fraz rzeczownikowych w liczbie pojedynczej ( NP[gender=masculie, number=singular] jest ściśle konkretniejszy od tego typu), a w interpretacji polimorficznej NP[number=singular] oznacza pewną frazę rzeczownikową w liczbie pojedynczej ( NP[gender=masculie, number=singular] jest i konkretniejszy i ogÄ‚Å‚lniejszy od tego typu). Interpretacja polimorficzna okazuje się być wygodniejsza przy pisaniu gramatyk, It doesn’t work in theory, but it works in practice… (Obecnie mamy w Speagramie interpretację polimorficzną.)

HPSG przypisuje frazom — począwszy od słÄ‚Å‚w po całe zdania — struktury atrybutowe (feature-structures) zawierające bardzo bogatą informację: fono/morfologiczną, syntaktyczną i semantyczną. HPSG składa się ze słownika, zawierającego struktury atrybutowe dla poszczegÄ‚Å‚lnych słÄ‚Å‚w języka, oraz bardzo niewielu schematÄ‚Å‚w reguł. Do HPSG można stosować chart-parsery: wypełnia się chart przez struktury atrybutowe słÄ‚Å‚w zdania i następnie stosuje schematy reguł do konstrukcji/przekształcania krawędzi charta. Od “zwykłych” gramatyk unifikacyjnych (tzn. CFG + struktury atrybutowe) HPSG rÄ‚Å‚żni się więc tym, że produkcje nie są dane jawnie, tylko wydobywane ze struktur atrybutowych przez schematy reguł.

HPSG jest niederywacyjna (deklaratywna): zupełnie nieistotne jest, w jaki sposÄ‚Å‚b skonstruowaliśmy strukturę atrybutową dla zdania, ta struktura zawiera całą potrzebną informację, oraz nietransformacyjna: struktury atrybutowe nie są modyfikowane, tylko łączone w większe struktury przez unifikację. Dlatego HPSG można też parsować “czysto więzowo” tak jak gramatyki zależności (dependency grammars).

Atrybutowe leksykalne TAGs (strona głÄ‚Å‚wna projektu xTAG)

Gramatyki kategorialne są rÄ‚Å‚wnież formalizmem leksykalnym. Ze słowami związane są kategorie (typy), ktÄ‚Å‚re ilustrują sposÄ‚Å‚b, w jaki słowa i frazy łączą się (kombinują) ze sobą tworząc większe frazy. Reguły zwykłych gramatyk kategorialnych (CG, rÄ‚Å‚wnoważnych CFG) to:

Wielomodalne CCG mają annotacje na ukośnikach mÄ‚Å‚wiące, ktÄ‚Å‚re reguły można do danej kategorii złożonej stosować. Kategorie mogą być indeksowane strukturami atrybutowymi, ktÄ‚Å‚re są unifikowane pomiędzy kategoriami, ktÄ‚Å‚re ze sobą kombinują (tzn. unifikowane są struktury atrybutowe ktÄ‚Å‚re stałyby przy wystąpieniach Y w powyższych regułach); wynikowe podstawienie jest stosowane do wszystkich struktur w danej derywacji. Całe kategorie też mogą być zmiennymi.

Do parsowania CCG używa się chart-parserÄ‚Å‚w, każdej spośrÄ‚Å‚d powyższych reguł odpowiada reguła dodawania krawędzi do charta.

Parsowanie dla gramatyk struktur frazowych istotnie wykorzystuje kolejność węzłÄ‚Å‚w drzewa. Nie jest to korzystne w przypadku językÄ‚Å‚w o zdaniach ze swobodnym szykiem. Szyk wyrazÄ‚Å‚w nie musi być istotnym elementem składni: możemy rozpatrywać przynależność do języka modulo permutacja słÄ‚Å‚w zdania. Aby parsować z pominięciem szyku, należy znaleźć jakiś odpowiednik programowania dynamicznego, ktÄ‚Å‚ry pozwoli inkrementacyjnie budować drzewo rozbioru. OgÄ‚Å‚lnych metod rozwiązywania problemÄ‚Å‚w o naturze kombinatorycznej dostarcza programowanie więzÄ‚Å‚w. Pierwszym językiem programowania więzÄ‚Å‚w był Prolog, ale obecne języki / techniki programowania więzÄ‚Å‚w są skuteczniejsze, zaopatrzone w bogatsze logiki i wydajniejsze mechanizmy (dziedziny). Jak widzieliśmy już wcześniej, parsery gramatyk unifikacyjnych budują drzewo obliczeń (gramatyki potraktowanej jako) program w Prologu, przycięte przez algorytm dynamiczny wiążący porządek (liniowy) węzłÄ‚Å‚w drzewa z porządkiem słÄ‚Å‚w zdania. Nasz obecny pomysł na parsowanie, to pominięcie “przycinania z zewnątrz”, ale wykorzystanie wspÄ‚Å‚łczesnych technik programowania więzÄ‚Å‚w.

Aby zaprogramować całe parsowanie jako problem rozwiązywania więzÄ‚Å‚w, potrzebujemy reprezentować dowolne drzewo rozbioru w dziedzinie więzÄ‚Å‚w, ktÄ‚Å‚rej używamy. Reprezentować dowolne drzewo o liściach będących słowami ustalonego zdania jest trudno — jest ich nieskończenie wiele. Musimy więc ograniczyć ilość węzłÄ‚Å‚w wewnętrznych nie posiadających rozgałęzień. Najprościej jest wykluczyć takie węzły. Zauważmy, że wtedy węzłÄ‚Å‚w wewnętrznych jest o jeden mniej niż liści, możemy więc każdemu węzłowi wewnętrznemu przyporządkować liść. Miło byłoby, gdyby sama gramatyka z każdym węzłem drzewa rozbioru wiązała liść-terminal-słowo zdania. Okazuje się, że takie gramatyki są naturalne, pracował nad nimi m.in. Lucien Tesniere, głÄ‚Å‚wną pracę “Elements de syntaxe structurale” wydał w 1959, więc rÄ‚Å‚wnolegle z pracami Chomsky’ego.

Samemu rozwiązywaniu więzÄ‚Å‚w jest wszystko jedno, jaką strukturę narzucimy na graf, więc możemy “zrelaksować” prototypowy warunek, żeby strukturą rozbioru było drzewo. Spotkałem się z formalizmami, w ktÄ‚Å‚rych wymaga się, żeby to był graf acykliczny (DAG). Praktyczne wydaje się zezwolenie na cykle, może ograniczone do klik, np. żeby wyrażać związki koordynacji (tzn. konstrukcje złożone wspÄ‚Å‚łrzędnie, np. “A i B”), z ktÄ‚Å‚rymi “dependency grammars” mają pewne problemy.

Kompletny tutorial implementacji parsera dla “dependency grammar” na bazie programowania więzÄ‚Å‚w: http://citeseer.ist.psu.edu/duchier00constraint.html.

• dezambiguacji na rÄ‚Å‚żnych poziomach rozbioru zdania, włączając niepewność co do użytych słÄ‚Å‚w,
• przyspieszania parsowania, m.in. poprzez “beam search” (pomijanie mniej prawdopodobnych wariantÄ‚Å‚w)

Data and models for statistical parsing with Combinatory Categorial Grammar, Chapter 4. A brief introduction to statistical parsing (faktycznie strony 121–152 wersji jednostronnej), ten rozdział przedstawia ogÄ‚Å‚lnie parsowanie probabilistyczne (bez odniesień do CCG).

• Harry Bunt and Reinhard Muskens, Computational Semantics
• Allen 1995 : Natural Language Understanding /

[Na marginesie: słÃ³w węzeł i wierzchołek używam zamiennie (tzn. używam pierwszego bo jest krótsze).]

Rozbiór zdania nie musi zatrzymywać się na poziomie słowa: dzięki automatycznemu podziałowi słowa na morfemy możemy zmniejszyć wielkość słownika, a nawet radzić sobie z nieznanymi słowami. Dla przykładu, system konwersacyjny może swobodnie zapytać użytkownika o znaczenie wyrazu, kiedy jego rola gramatyczna jest dzięki analizie w pełni określona i znane są wzorce odmiany.

Ogólnie o parsowaniu: Parsing Techniques - A Practical Guide. Istotne hasła: metoda CYK, chart parsing, parsowanie top-down vs. bottom-up, Earley parser, metody LR.

Functional Pearls: Functional Chart Parsing of Context Free Grammars by Peter Ljunglöf.

Inkrementacyjna unifikacja (inkrementacyjne rozstrzyganie więzów)

Drzewa dowodów (proof trees) jako drzewa rozbioru dla gramatyk unifikacyjnych, zobacz Logic, Programming and Prolog (2ed) rozdz. 3.6. Oczywiście chcemy możliwie szybko odcinać błędne ścieżki wyprowadzeń, dlatego (jak w Prologu), od razu propagujemy rozwiązania generowanych równań. “Funkcję obliczeń” R wyznacza nam algorytm chart-parsera. (Rozdział 3.6 książki o Prologu mówi tylko o doklejaniu płytkich drzew odpowiadających produkcjom, u nas krawędzi z kropką na samym początku, ale idea przenosi się na doklejanie głębszych drzew. Pełne gramatyki unifikacyjne są opisane w rozdziale o “Definite Clause Grammars”.)

1. Dzielimy gramatykę na reguły leksykalne/słownikowe i pozostałe. Reguły leksykalne to te, których prawa strona rozpoczyna się od terminala (często będzie to tylko terminal). Tylko nieleksykalne reguły wstawiamy jako “pętelki” w każdą pozycję charta, reguły leksykalne grupujemy w słownik ze słÃ³w w zbiór reguł, i dla każdego słowa wstawiamy do charta przeskakujące to słowo krawędzie.
2. Samo wstawianie “pętelek” do charta możemy potraktować leniwie: zgromadzić reguły nieleksykalne w słownik indeksowany (np.) przez część mowy (lub nazwę frazy) i w momencie wybierania z charta krawędzi do przedłużenia, dorzucić krawędzie odpowiadające regułom ze słownika dla potrzebnej części mowy. W ten sposób nie przeglądamy za każdym razem wszystkich reguł (nieleksykalnych).
3. Można pokusić się o bardziej skomplikowane optymalizacje. Można badać klasy leksykalne (np. verb = transitive verb + intransitive verb), których derywacje z danej reguły wymagają / nie dopuszczają (tzn. klasy słÃ³w, które muszą / nie mogą się pojawić we frazie, której wyprowadzenia korzeniem jest dana reguła). Można skompilować gramatykę do bardziej wydajnej postaci (bardziej podobnej do postaci Greibach), ale w czasie parsowania rekonstruować drzewo rozbioru względem oryginalnej gramatyki.

Pomysły na tłumaczenie błędów gramatycznych

Jeśli zdanie jest niepoprawne gramatycznie, to parsing kończy się bez krawędzi obejmujących całe zdanie. Szukamy (dynamicznie) ciągów krawędzi dających minimalne pokrycie rozłączne zdania (tzn. minimalną ilość krawędzi, po których można przeskoczyć z początku na koniec). Budujemy nowy chart, tylko z krawędzi z tych ciągów. Do standardowych reguł chart-parsera dodajemy następujące reguły obsługi błędów:

Nasyć chart przy pomocy poszerzonego zbioru reguł (poszerz odpowiednio używany algorytm parsowania). Zwróć użytkownikowi drzewa rozbioru odpowiadające krawędziom obejmującym całe zdanie wyprowadzone z minimalną ilością zastosowań reguł obsługi błędów, razem z zapamiętanymi komentarzami.

Obecny Speagram: trochę ogólniejsze gramatyki struktur frazowych

Po lewej stronie produkcji, wstawiamy term A opisujący własności drzewa rozbioru z korzeniem wyprowadzonym z tej produkcji, zależne od własności poddrzew. Po prawej stronie produkcji, zamiast nieterminali wstawiamy term A_i opisujący interesujące nas własności, oraz relację R_i, w której term B opisujący potencjalne poddrzewo rozbioru ma być względem termu A_i. Trzy rodzaje relacji wydają się rozsądne, w żargonie języków programowania nazywają się one: “pozycja inwariantna” (=), “pozycja kowariantna” (<), “pozycja kontrawariantna” (>). Budując drzewo rozbioru zdania pilnujemy niesprzeczności wymagań. Przykłady (italiką oznaczone są terminale, a znakiem zapytania zmienne w termach własności, tzn. w typach):

z przedchodniości, ta produkcja jest równoważna następującym:

Konstrukcja z języków programowania. let X be Y oznacza, że X oblicza się do Y. Żeby to było dopuszczalne, Yki muszą być Xami, tzn. typ Yka musi być podtypem Xa.

Przymiotnik opisujący frazę rzeczownikową może mieć typ ogólniejszy niż ta fraza, na przykład może być rodzaju męskiego gender=m, który jest nadtypem rodzajów m1, m2 i m3.

Są dwie możliwe interpretacje etykiet brakujących w opisie: sensowna formalnie interpretacja abstrakcyjna oraz praktyczna interpretacja polimorficzna. Interpretacja abstrakcyjna pod niewyspecyfikowane wartości etykiet podstawia Top, a interpretacja polimorficzna ignoruje etykiety nie występujące jednocześnie po obu stronach porównania. W interpretacji abstrakcyjnej NP[number=singular] oznacza zbiór wszystkich fraz rzeczownikowych w liczbie pojedynczej ( NP[gender=masculie, number=singular] jest ściśle konkretniejszy od tego typu), a w interpretacji polimorficznej NP[number=singular] oznacza pewną frazę rzeczownikową w liczbie pojedynczej ( NP[gender=masculie, number=singular] jest i konkretniejszy i ogólniejszy od tego typu). Interpretacja polimorficzna okazuje się być wygodniejsza przy pisaniu gramatyk, It doesn’t work in theory, but it works in practice… (Obecnie mamy w Speagramie interpretację polimorficzną.)

Government & Binding Theory

An Introduction to Government & Binding

HPSG przypisuje frazom — począwszy od słÃ³w po całe zdania — struktury atrybutowe (feature-structures) zawierające bardzo bogatą informację: fono/morfologiczną, syntaktyczną i semantyczną. HPSG składa się ze słownika, zawierającego struktury atrybutowe dla poszczególnych słÃ³w języka, oraz bardzo niewielu schematów reguł. Do HPSG można stosować chart-parsery: wypełnia się chart przez struktury atrybutowe słÃ³w zdania i następnie stosuje schematy reguł do konstrukcji/przekształcania krawędzi charta. Od “zwykłych” gramatyk unifikacyjnych (tzn. CFG + struktury atrybutowe) HPSG różni się więc tym, że produkcje nie są dane jawnie, tylko wydobywane ze struktur atrybutowych przez schematy reguł.

HPSG jest niederywacyjna (deklaratywna): zupełnie nieistotne jest, w jaki sposób skonstruowaliśmy strukturę atrybutową dla zdania, ta struktura zawiera całą potrzebną informację, oraz nietransformacyjna: struktury atrybutowe nie są modyfikowane, tylko łączone w większe struktury przez unifikację. Dlatego HPSG można też parsować “czysto więzowo” tak jak gramatyki zależności (dependency grammars).

Atrybutowe leksykalne TAGs (strona głÃ³wna projektu xTAG)

Gramatyki kategorialne są również formalizmem leksykalnym. Ze słowami związane są kategorie (typy), które ilustrują sposób, w jaki słowa i frazy łączą się (kombinują) ze sobą tworząc większe frazy. Reguły zwykłych gramatyk kategorialnych (CG, równoważnych CFG) to:

Wielomodalne CCG mają annotacje na ukośnikach mówiące, które reguły można do danej kategorii złożonej stosować. Kategorie mogą być indeksowane strukturami atrybutowymi, które są unifikowane pomiędzy kategoriami, które ze sobą kombinują (tzn. unifikowane są struktury atrybutowe które stałyby przy wystąpieniach Y w powyższych regułach); wynikowe podstawienie jest stosowane do wszystkich struktur w danej derywacji. Całe kategorie też mogą być zmiennymi.

Do parsowania CCG używa się chart-parserów, każdej spośród powyższych reguł odpowiada reguła dodawania krawędzi do charta.

Parsowanie dla gramatyk struktur frazowych istotnie wykorzystuje kolejność węzłÃ³w drzewa. Nie jest to korzystne w przypadku języków o zdaniach ze swobodnym szykiem. Szyk wyrazów nie musi być istotnym elementem składni: możemy rozpatrywać przynależność do języka modulo permutacja słÃ³w zdania. Aby parsować z pominięciem szyku, należy znaleźć jakiś odpowiednik programowania dynamicznego, który pozwoli inkrementacyjnie budować drzewo rozbioru. Ogólnych metod rozwiązywania problemów o naturze kombinatorycznej dostarcza programowanie więzów. Pierwszym językiem programowania więzów był Prolog, ale obecne języki / techniki programowania więzów są skuteczniejsze, zaopatrzone w bogatsze logiki i wydajniejsze mechanizmy (dziedziny). Jak widzieliśmy już wcześniej, parsery gramatyk unifikacyjnych budują drzewo obliczeń (gramatyki potraktowanej jako) program w Prologu, przycięte przez algorytm dynamiczny wiążący porządek (liniowy) węzłÃ³w drzewa z porządkiem słÃ³w zdania. Nasz obecny pomysł na parsowanie, to pominięcie “przycinania z zewnątrz”, ale wykorzystanie współczesnych technik programowania więzów.

Aby zaprogramować całe parsowanie jako problem rozwiązywania więzów, potrzebujemy reprezentować dowolne drzewo rozbioru w dziedzinie więzów, której używamy. Reprezentować dowolne drzewo o liściach będących słowami ustalonego zdania jest trudno — jest ich nieskończenie wiele. Musimy więc ograniczyć ilość węzłÃ³w wewnętrznych nie posiadających rozgałęzień. Najprościej jest wykluczyć takie węzły. Zauważmy, że wtedy węzłÃ³w wewnętrznych jest o jeden mniej niż liści, możemy więc każdemu węzłowi wewnętrznemu przyporządkować liść. Miło byłoby, gdyby sama gramatyka z każdym węzłem drzewa rozbioru wiązała liść-terminal-słowo zdania. Okazuje się, że takie gramatyki są naturalne, pracował nad nimi m.in. Lucien Tesniere, głÃ³wną pracę “Elements de syntaxe structurale” wydał w 1959, więc równolegle z pracami Chomsky’ego.

Samemu rozwiązywaniu więzów jest wszystko jedno, jaką strukturę narzucimy na graf, więc możemy “zrelaksować” prototypowy warunek, żeby strukturą rozbioru było drzewo. Spotkałem się z formalizmami, w których wymaga się, żeby to był graf acykliczny (DAG). Praktyczne wydaje się zezwolenie na cykle, może ograniczone do klik, np. żeby wyrażać związki koordynacji (tzn. konstrukcje złożone współrzędnie, np. “A i B”), z którymi “dependency grammars” mają pewne problemy.

Kompletny tutorial implementacji parsera dla “dependency grammar” na bazie programowania więzów: http://citeseer.ist.psu.edu/duchier00constraint.html.

• dezambiguacji na różnych poziomach rozbioru zdania, włączając niepewność co do użytych słÃ³w,
• przyspieszania parsowania, m.in. poprzez “beam search” (pomijanie mniej prawdopodobnych wariantów)

Data and models for statistical parsing with Combinatory Categorial Grammar, Chapter 4. A brief introduction to statistical parsing (faktycznie strony 121–152 wersji jednostronnej), ten rozdział przedstawia ogólnie parsowanie probabilistyczne (bez odniesień do CCG).

Formalizmy lingwistyczne używane w NLP

Gramatyki zależności (dependency grammars)

Struktura (drzewa) rozbioru

Analiza morfologiczna (Computational Morphology, word tagging)

Parsowanie gramatyk struktur frazowych

Praser CFG: algorytm Earleya.

Parsery “shift-reduce” w kontekście NLP

Inkrementacyjna unifikacja (inkrementacyjne rozstrzyganie więzów)

Usprawnianie chart-parsera

Pomysły na optymalizację

Pomysły na tłumaczenie błędów gramatycznych

Obecny Speagram: trochę ogólniejsze gramatyki struktur frazowych

Nieterminale to typy, ale typy mogą posiadać bogatą strukturę.

Etykiety i cechy. Interpretacja brakujących etykiet.

Formalizmy lingwistyczne używane w NLP

Gramatyki transformacyjne

Lexical Functional Grammar (LFG)

Head-driven Phrase Structure Grammar (HPSG)

(Lexicalized) Tree Adjoining Grammar (TAG, xTAG)

Unification Categorial Grammar, Combinatory Categorial Grammar (UCG, CCG)

Gramatyki zależności (dependency grammars)

Struktura (drzewa) rozbioru

Constraint Programming

Gramatyki probabilistyczne, parsowanie probabilistyczne

Parsery probabilistyczne z modelowaniem zależności w strukturze predykatowo-argumentowej

Od składni do semantyki

Gramatyki Montague’a

Underspecification

Przetwarzanie dyskursu

Discourse Representation Theory

(:toc:)

Ogólnie o parsowaniu: Parsing Techniques - A Practical Guide. Istotne hasła: metoda CYK, chart parsing, parsowanie top-down vs. bottom-up, Earley parser, metody LR.

1. Parsery probabilistyczne z modelowaniem zależności w strukturze predykatowo-argumentowej

Parsery probabilistyczne z modelowaniem zależności w strukturze predykatowo-argumentowej

Data and models for statistical parsing with Combinatory Categorial Grammar, Chapter 4. A brief introduction to statistical parsing (faktycznie strony 121–152 wersji jednostronnej), ten rozdział przedstawia ogólnie parsowanie probabilistyczne (bez odniesień do CCG).

Parsery probabilistyczne z modelowaniem zależności w strukturze predykatowo-argumentowej

Koncepcja zaczerpnięta z “dependency grammars” pozwala na optymalniejsze posługiwanie się gramatykami probabilistycznymi. Parsing with generative models of predicate-argument structure

• przyspieszania parsowania, m.in. poprzez “beam search” (pomijanie mniej prawdopodobnych wariantów)

Allen 1995: Natural Language Understanding / Chapter 7 - Ambiguity Resolution: Statistical Methods / 7.4 Obtaining Lexical Probabilities, 7.5 Probabilistic Context-Free Grammars, 7.6 Best-First Parsing, 7.7 A Simple Context-Dependent Best-First Parser

Data and models for statistical parsing with Combinatory Categorial Grammar, Chapter 4. A brief introduction to statistical parsing (faktycznie strony 121–152 wersji jednostronnej).

1. Parsery “shift-reduce” w kontekście NLP.
2. Inkrementacyjna unifikacja (inkrementacyjne rozstrzyganie więzów)
3. Usprawnianie chart-parsera
   1. Pomysły na optymalizację
   2. Pomysły na tłumaczenie błędów gramatycznych
4. Obecny Speagram: trochę ogólniejsze gramatyki struktur frazowych
   1. Nieterminale to typy, ale typy mogą posiadać bogatą strukturę.
   2. Etykiety i cechy. Interpretacja brakujących etykiet.

Zacznijmy od parsowania pełnego CFG:

Parsery “shift-reduce” w kontekście NLP

Allen 1995 : Natural Language Understanding / Chapter 6: Toward Efficient Parsing

Dla gramatyk CCG: Incremental natural language understanding with combinatory categorial grammar.

Inkrementacyjna unifikacja (inkrementacyjne rozstrzyganie więzów)

Usprawnianie chart-parsera

Pomysły na optymalizację

Pomysły na tłumaczenie błędów gramatycznych

Obecny Speagram: trochę ogólniejsze gramatyki struktur frazowych

Nieterminale to typy, ale typy mogą posiadać bogatą strukturę.

Etykiety i cechy. Interpretacja brakujących etykiet.

Allen 1995 : Natural Language Understanding / Part II: Semantic Interpretation / Chapter 8 : Semantics and Logical Form, Chapter 9 : Linking Syntax and Semantics

Wielomodalne CCG mają annotacje na ukośnikach mówiące, które reguły można do danej kategorii złożonej stosować. Kategorie mogą być indeksowane strukturami atrybutowymi, które są unifikowane pomiędzy kategoriami, które ze sobą kombinują (tzn. unifikowane są struktury atrybutowe które stałyby przy wystąpieniach Y w powyższych regułach); wynikowe podstawienie jest stosowane do wszystkich struktur w danej derywacji. Całe kategorie też mogą być zmiennymi.

1. Gramatyki probabilistyczne, parsowanie probabilistyczne
2. Od składni do semantyki
   1. Gramatyki Montague’a
   2. Underspecification
   3. Przetwarzanie dyskursu
      1. Discourse Representation Theory

Gramatyki kategorialne są również formalizmem leksykalnym. Ze słowami związane są kategorie (typy), które ilustrują sposób, w jaki słowa i frazy łączą się (kombinują) ze sobą tworząc większe frazy. Reguły zwykłych gramatyk kategorialnych (CG, równoważnych CFG) to:

1. (X / Y) Y ==> X (aplikacja)
2. Y (X \ Y) ==> X

Kombinatoryczne gramatyki kategorialne (o mocy “mildly context sensitive”) mają dodatkowo reguły

1. (X / Y) (Y / Z) ==> X / Z (złożenie)
2. (X \ Y) (Y \ Z) ==> X \ Z
3. X ==> T / (T \ X) (podniesienie typu)
4. (X / Y) (Y \ Z) ==> X \ Z (złożenie krzyżowe)
5. (Y / Z) (X \ Y) ==> X / Z

Wielomodalne CCG mają annotacje na ukośnikach mówiące, które reguły można do danej kategorii złożonej stosować.

Do parsowania CCG używa się chart-parserów, każdej spośród powyższych reguł odpowiada reguła dodawania krawędzi do charta.

Gramatyki probabilistyczne, parsowanie probabilistyczne

Są użyteczne m.in. dla:

• dezambiguacji na różnych poziomach rozbioru zdania, włączając niepewność co do użytych słów,
• przyspieszania parsowania, poprzez “beam search” (pomijanie mniej prawdopodobnych wariantów)

Od składni do semantyki

Gramatyki Montague’a

Underspecification

Przetwarzanie dyskursu

Discourse Representation Theory

Speagram to jednocześnie język programowania oraz dynamiczny (programowalny) parser. (Uwagi dotyczą wersji SVN http://svn.sourceforge.net/viewvc/speagram/trunk/speagram/, intensywnie rozwijanej od sierpnia do października 2006 http://dev.openwengo.com/trac/openwengo/trac.cgi/wiki/CodeCampWengoPhoneNaturalLanguage — projekt zakończony fiaskiem).

Obecny Speagram: trochę ogólniejsze gramatyki struktur frazowych

Speagram to jednocześnie język programowania oraz dynamiczny (programowalny) parser. (Uwagi dotyczą wersji SVN http://svn.sourceforge.net/viewvc/speagram/trunk/speagram/, intensywnie rozwijanej od sierpnia do października b.r. http://dev.openwengo.com/trac/openwengo/trac.cgi/wiki/CodeCampWengoPhoneNaturalLanguage — projekt zakończony fiaskiem).

HPSG jest niederywacyjna (deklaratywna): zupełnie nieistotne jest, w jaki sposób skonstruowaliśmy strukturę atrybutową dla zdania, ta struktura zawiera całą potrzebną informację, oraz nietransformacyjna: struktury atrybutowe nie są modyfikowane, tylko łączone w większe struktury przez unifikację. Dlatego HPSG można też parsować “czysto więzowo” tak jak gramatyki zależności (dependency grammars).

HPSG jest niederywacyjna: zupełnie nieistotne jest, w jaki sposób skonstruowaliśmy strukturę atrybutową dla zdania, ta struktura zawiera całą potrzebną informację. Dlatego HPSG można też parsować “czysto więzowo” tak jak gramatyki zależności (dependency grammars).

HPSG przypisuje frazom — począwszy od słów po całe zdania — struktury atrybutowe (feature-structures) zawierające bardzo bogatą informację: fono/morfologiczną, syntaktyczną i semantyczną. HPSG składa się ze słownika, zawierającego struktury atrybutowe dla poszczególnych słów języka, oraz bardzo niewielu schematów reguł. Do HPSG można stosować chart-parsery: wypełnia się chart przez struktury atrybutowe słów zdania i następnie stosuje schematy reguł do konstrukcji/przekształcania krawędzi charta. Od “zwykłych” gramatyk unifikacyjnych (tzn. CFG + struktury atrybutowe) HPSG różni się więc tym, że produkcje nie są dane jawnie, tylko wydobywane ze struktur atrybutowych przez schematy reguł.

Ważne miejsce: http://hpsg.stanford.edu/

Kurs LFG i HPSG: http://www.cl.uni-bremen.de/~stefan/Lehre/Konstanz2001/ (slajdy dla HPSG)

Strona domowa LFG (m. in. wprowadzenie do LFG)

1. Unification Categorial Grammar, Combinatory Categorial Grammar (UCG, CCG)

Strona domowa LFG

Unification Categorial Grammar, Combinatory Categorial Grammar (UCG, CCG)

Atrybutowe leksykalne TAGs (strona główna projektu xTAG)

Publikacje dot. CCG: http://groups.inf.ed.ac.uk/ccg/publications.html (m. in. wprowadzenie do CCG).

Multi-modalne CCG: http://www.dfki.de/~gj/lectures/050404-08.fi.helsinki.kit/

http://www.cis.upenn.edu/~xtag/

http://www.dfki.de/~gj/lectures/050404-08.fi.helsinki.kit/ http://groups.inf.ed.ac.uk/ccg/publications.html

1. Parsowanie gramatyk struktur frazowych
   1. Praser CFG: algorytm Earleya.
   2. Inkrementacyjna unifikacja (inkrementacyjne rozstrzyganie więzów)
   3. Usprawnianie chart-parsera
      1. Pomysły na optymalizację
      2. Pomysły na tłumaczenie błędów gramatycznych
   4. Obecny Speagram: trochę ogólniejsze gramatyki struktur frazowych
      1. Nieterminale to typy, ale typy mogą posiadać bogatą strukturę.
      2. Etykiety i cechy. Interpretacja brakujących etykiet.
2. Formalizmy lingwistyczne używane w NLP
   1. Gramatyki transformacyjne
   2. Lexical Functional Grammar (LFG)
   3. Head-driven Phrase Structure Grammar (HPSG)
   4. (Lexicalized) Tree Adjoining Grammar (TAG, xTAG)
   5. Unificational Categorial Grammar, Combinatory Categorial Grammar (UCG, CCG)
3. Gramatyki zależności (dependency grammars)
   1. Struktura (drzewa) rozbioru
   2. Constraint Programming
4. Od składni do semantyki
   1. Gramatyki Montague’a
   2. Underspecification
   3. Przetwarzanie dyskursu
      1. Discourse Representation Theory

Parsowanie gramatyk struktur frazowych

Praser CFG: algorytm Earleya.

Inkrementacyjna unifikacja (inkrementacyjne rozstrzyganie więzów)

Usprawnianie chart-parsera

Pomysły na optymalizację

Pomysły na tłumaczenie błędów gramatycznych

Obecny Speagram: trochę ogólniejsze gramatyki struktur frazowych

Nieterminale to typy, ale typy mogą posiadać bogatą strukturę.

Etykiety i cechy. Interpretacja brakujących etykiet.

Formalizmy lingwistyczne używane w NLP

Gramatyki transformacyjne

Lexical Functional Grammar (LFG)

Head-driven Phrase Structure Grammar (HPSG)

(Lexicalized) Tree Adjoining Grammar (TAG, xTAG)

Unificational Categorial Grammar, Combinatory Categorial Grammar (UCG, CCG)

Gramatyki zależności (dependency grammars)

Struktura (drzewa) rozbioru

Constraint Programming

Od składni do semantyki

Gramatyki Montague’a

Underspecification

Przetwarzanie dyskursu

Discourse Representation Theory

1. Można pokusić się o bardziej skomplikowane optymalizacje. Można badać klasy leksykalne (np. verb = transitive verb + intransitive verb), których derywacje z danej reguły wymagają / nie dopuszczają (tzn. klasy słów, które muszą / nie mogą się pojawić we frazie, której wyprowadzenia korzeniem jest dana reguła). Można skompilować gramatykę do bardziej wydajnej postaci (bardziej podobnej do postaci Greibach), ale w czasie parsowania rekonstruować drzewo rozbioru względem oryginalnej gramatyki.

Jeśli zdanie jest niepoprawne gramatycznie, to parsing kończy się bez krawędzi obejmujących całe zdanie. Szukamy (dynamicznie) ciągów krawędzi dających minimalne pokrycie rozłączne zdania (tzn. minimalną ilość krawędzi, po których można przeskoczyć z początku na koniec). Budujemy nowy chart, tylko z krawędzi z tych ciągów. Do standardowych reguł chart-parsera dodajemy następujące reguły obsługi błędów:

1. Underspecification
2. Przetwarzanie dyskursu
   1. Discourse Representation Theory

Underspecification

http://www.coli.uni-saarland.de/courses/underspecification-06/page.php?id=schedule

Przetwarzanie dyskursu

Discourse Representation Theory

1. Gramatyki transformacyjne
2. Lexical Functional Grammar (LFG)
3. Head-driven Phrase Structure Grammar (HPSG)

Gramatyki transformacyjne

Gramatyki transformacyjne (“szkoła Chomskiego”).

http://www.ling.upenn.edu/~beatrice/syntax-textbook/index.html

Lexical Functional Grammar (LFG)

http://emsah.uq.edu.au/linguistics/Working%20Papers/ananda_ling/LFG_Summary.htm

Head-driven Phrase Structure Grammar (HPSG)

http://emsah.uq.edu.au/linguistics/Working%20Papers/ananda_ling/HPSG_Summary.htm

Introduction to LFG and HPSG by Ananda Lima.

1. Formalizmy lingwistyczne używane w NLP
   1. Lexical Functional Grammar (LFG)
   2. Head-driven Phrase Structure Grammar (HPSG)

Formalizmy lingwistyczne używane w NLP

Lexical Functional Grammar (LFG)

Head-driven Phrase Structure Grammar (HPSG)

1. Head-driven Phrase Structure Grammars

Drzewa dowodów (proof trees) jako drzewa rozbioru dla gramatyk unifikacyjnych, zobacz Logic, Programming and Prolog (2ed) rozdz. 3.6. Oczywiście chcemy możliwie szybko odcinać błędne ścieżki wyprowadzeń, dlatego (jak w Prologu), od razu propagujemy rozwiązania generowanych równań. “Funkcję obliczeń” R wyznacza nam algorytm chart-parsera. (Rozdział 3.6 książki o Prologu mówi tylko o doklejaniu płytkich drzew odpowiadających produkcjom, u nas krawędzi z kropką na samym początku, ale idea przenosi się na doklejanie głębszych drzew. Pełne gramatyki unifikacyjne są opisane w rozdziale o “Definite Clause Grammars”.)

1. Można pokusić się o bardziej skomplikowane optymalizacje. Można badać klasy leksykalne (np. verb = transitive verb + intransitive verb), których derywacje z danej reguły wymagają / nie dopuszczają. Można skompilować gramatykę do bardziej wydajnej postaci (bardziej podobnej do postaci Greibach), ale w czasie parsowania rekonstruować drzewo rozbioru względem oryginalnej gramatyki.

Jeśli zdanie jest niepoprawne gramatycznie, to parsing kończy się bez krawędzi obejmujących całe zdanie. Szukamy (dynamicznie) ciągów krawędzi dających minimalne pokrycie rozłączne zdania. Budujemy nowy chart, tylko z krawędzi z tych ciągów. Do standardowych reguł chart-parsera dodajemy następujące reguły obsługi błędów:

błąd typu

poszerz krawędź o przyległą zupełną krawędź (z kropką na końcu), odpowiednio przesuwając kropkę lewej krawędzi, bez sprawdzania zgodności nieterminali, np. krawędzie [i -> j] A => B.CD, [j -> k] E => FG., dodaj [i -> k] A => BC.D, zapamiętaj “błąd typu: oczekiwane C, znaleziono E”

wtrącenie

wydłuż krawędź do końca przyległej zupełnej krawędzi, bez przesuwania kropki, np. krawędzie [i -> j] A => B.CD, [j -> k] E => FG., dodaj [i -> k] A => B.CD, zapamiętaj “wtrącenie: nieoczekiwane E”

opuszczenie

przesuń kropkę bez wydłużania krawędzi, np. krawędź [i -> j] A => B.CD, dodaj [i -> j] A => BC.D, zapamiętaj “opuszczenie: pominięto C”

Nasyć chart przy pomocy poszerzonego zbioru reguł (poszerz odpowiednio używany algorytm parsowania). Zwróć użytkownikowi drzewa rozbioru odpowiadające krawędziom obejmującym całe zdanie wyprowadzone z minimalną ilością zastosowań reguł obsługi błędów, razem z zapamiętanymi komentarzami.

Head-driven Phrase Structure Grammars

1. Usprawnianie chart-parsera
   1. Pomysły na optymalizację
   2. Pomysły na tłumaczenie błędów gramatycznych

Usprawnianie chart-parsera

Pomysły na optymalizację

Dla ustalenia uwagi udoskonalamy algorytm Earleya: bottom-up left-to-right

1. Dzielimy gramatykę na reguły leksykalne/słownikowe i pozostałe. Reguły leksykalne to te, których prawa strona rozpoczyna się od terminala (często będzie to tylko terminal). Tylko nieleksykalne reguły wstawiamy jako “pętelki” w każdą pozycję charta, reguły leksykalne grupujemy w słownik ze słów w zbiór reguł, i dla każdego słowa wstawiamy do charta przeskakujące to słowo krawędzie.
2. Samo wstawianie “pętelek” do charta możemy potraktować leniwie: zgromadzić reguły nieleksykalne w słownik indeksowany (np.) przez część mowy (lub nazwę frazy) i w momencie wybierania z charta krawędzi do przedłużenia, dorzucić krawędzie odpowiadające regułom ze słownika dla potrzebnej części mowy. W ten sposób nie przeglądamy za każdym razem wszystkich reguł (nieleksykalnych).

Pomysły na tłumaczenie błędów gramatycznych

Uwaga: notatki są w trakcie opracowywania i mogą zawierać poważne błędy.

Drzewa dowodów (proof trees) jako drzewa rozbioru dla gramatyk unifikacyjnych, zobacz Logic, Programming and Prolog (2ed) rozdz. 3.6. Oczywiście chcemy możliwie szybko odcinać błędne ścieżki wyprowadzeń, dlatego (jak w Prologu), od razu propagujemy rozwiązania generowanych równań. “Funkcję obliczeń” R wyznacza nam algorytm chart-parsera. (Rozdział 3.6 książki o Prologu mówi tylko o doklejaniu płytkich drzew odpowiadających produkcjom, u nas krawędzi z kropką na samym początku, ale idea przenosi się na doklejanie głębszych drzew.)

Rozbiór zdania nie musi zatrzymywać się na poziomie słowa: dzięki automatycznemu podziałowi słowa na morfemy możemy zmniejszyć wielkość słownika, a nawet radzić sobie z nieznanymi słowami. Dla przykładu, system konwersacyjny może swobodnie zapytać użytkownika o znaczenie wyrazu, kiedy jego rola gramatyczna jest dzięki analizie w pełni określona i znane są wzorce odmiany.

1. Constraint Programming

1. Nieterminale to typy, ale typy mogą posiadać bogatą strukturę.

1. Analiza morfologiczna (Computational Morphology, word tagging)
2. Gramatyki struktur frazowych
   1. Parsowanie
      1. Praser CFG: algorytm Earleya.
      2. Inkrementacyjna unifikacja (inkrementacyjne rozstrzyganie więzów)
      3. Pomysły na optymalizację parsera
   2. Obecny Speagram: trochę ogólniejsze gramatyki struktur frazowych
      1. [[#p221 | Nieterminale to typy, ale typy mogą posiadać bogatą strukturę.]
      2. Etykiety i cechy. Interpretacja brakujących etykiet.
3. Gramatyki zależności (dependency grammars)
   1. Struktura (drzewa) rozbioru
   2. Constraint Programming
4. Od składni do semantyki
   1. Gramatyki Montague’a

Analiza morfologiczna (Computational Morphology, word tagging)

Gramatyki struktur frazowych

Parsowanie

Praser CFG: algorytm Earleya.

Inkrementacyjna unifikacja (inkrementacyjne rozstrzyganie więzów)

Pomysły na optymalizację parsera

Obecny Speagram: trochę ogólniejsze gramatyki struktur frazowych

Speagram to jednocześnie język programowania oraz dynamiczny (programowalny) parser.

Nieterminale to typy, ale typy mogą posiadać bogatą strukturę.

Po lewej stronie produkcji, wstawiamy term A opisujący własności drzewa rozbioru z korzeniem wyprowadzonym z tej produkcji, zależne od własności poddrzew. Po prawej stronie produkcji, zamiast nieterminali wstawiamy term A_i opisujący interesujące nas własności, oraz relację R_i, w której term B opisujący potencjalne poddrzewo rozbioru ma być względem termu A_i. Trzy rodzaje relacji wydają się rozsądne, w żargonie języków programowania nazywają się one: “pozycja inwariantna” (=), “pozycja kowariantna” (<), “pozycja kontrawariantna” (>). Budując drzewo rozbioru zdania pilnujemy niesprzeczności wymagań. Przykłady (italiką oznaczone są terminale, a znakiem zapytania zmienne w termach własności, tzn. w typach):

Etykiety i cechy. Interpretacja brakujących etykiet.

Gramatyki zależności (dependency grammars)

Struktura (drzewa) rozbioru

Constraint Programming

Od składni do semantyki

Gramatyki Montague’a

http://www-personal.umich.edu/~akao/MontagueGrammar.pdf

Constraint Programming

Kompletny tutorial implementacji parsera dla “dependency grammar” na bazie programowania więzów: http://citeseer.ist.psu.edu/duchier00constraint.html.

Struktura (drzewa) rozbioru

Samemu rozwiązywaniu więzów jest wszystko jedno, jaką strukturę narzucimy na graf, więc możemy “zrelaksować” prototypowy warunek, żeby strukturą rozbioru było drzewo. Spotkałem się z formalizmami, w których wymaga się, żeby to był graf acykliczny (DAG). Praktyczne wydaje się zezwolenie na cykle, może ograniczone do klik, np. żeby wyrażać związki koordynacji (tzn. konstrukcje złożone współrzędnie, np. “A i B”), z którymi “dependency grammars” mają pewne problemy.

[Na marginesie: słów węzeł i wierzchołek używam zamiennie (tzn. używam pierwszego bo jest krótsze).]

Aby zaprogramować całe parsowanie jako problem rozwiązywania więzów, potrzebujemy reprezentować dowolne drzewo rozbioru w dziedzinie więzów, której używamy. Reprezentować dowolne drzewo o liściach będących słowami ustalonego zdania jest trudno — jest ich nieskończenie wiele. Musimy więc ograniczyć ilość węzłów wewnętrznych nie posiadających rozgałęzień. Najprościej jest wykluczyć takie węzły. Zauważmy, że wtedy węzłów wewnętrznych jest o jeden mniej niż liści, możemy więc każdemu węzłowi wewnętrznemu przyporządkować liść. Miło byłoby, gdyby sama gramatyka z każdym węzłem drzewa rozbioru wiązała liść-terminal-słowo zdania. Okazuje się, że takie gramatyki są naturalne, pracował nad nimi m.in. Lucien Tesniere, główną pracę “Elements de syntaxe structurale” wydał w 1959, więc równolegle z pracami Chomsky’ego.

Struktura drzewa rozbioru

Aby zaprogramować całe parsowanie jako problem rozwiązywania więzów, potrzebujemy reprezentować drzewo rozbioru w dziedzinie więzów, której używamy.

Gramatyki zależności (dependency grammars)

Parsowanie dla gramatyk struktur frazowych istotnie wykorzystuje kolejność węzłów drzewa. Nie jest to korzystne w przypadku języków o zdaniach ze swobodnym szykiem. Szyk wyrazów nie musi być istotnym elementem składni: możemy rozpatrywać przynależność do języka modulo permutacja słów zdania. Aby parsować z pominięciem szyku, należy znaleźć jakiś odpowiednik programowania dynamicznego, który pozwoli inkrementacyjnie budować drzewo rozbioru. Ogólnych metod rozwiązywania problemów o naturze kombinatorycznej dostarcza programowanie więzów. Pierwszym językiem programowania więzów był Prolog, ale obecne języki / techniki programowania więzów są skuteczniejsze, zaopatrzone w bogatsze logiki i wydajniejsze mechanizmy (dziedziny). Jak widzieliśmy już wcześniej, parsery gramatyk unifikacyjnych budują drzewo obliczeń (gramatyki potraktowanej jako) program w Prologu, przycięte przez algorytm dynamiczny wiążący porządek (liniowy) węzłów drzewa z porządkiem słów zdania. Nasz obecny pomysł na parsowanie, to pominięcie “przycinania z zewnątrz”, ale wykorzystanie współczesnych technik programowania więzów.

Są dwie możliwe interpretacje etykiet brakujących w opisie: sensowna formalnie interpretacja abstrakcyjna oraz praktyczna interpretacja polimorficzna. Interpretacja abstrakcyjna pod niewyspecyfikowane wartości etykiet podstawia Top, a interpretacja polimorficzna ignoruje etykiety nie występujące jednocześnie po obu stronach porównania. W interpretacji abstrakcyjnej NP[number=singular] oznacza zbiór wszystkich fraz rzeczownikowych w liczbie pojedynczej ( NP[gender=masculie, number=singular] jest ściśle konkretniejszy od tego typu), a w interpretacji polimorficznej NP[number=singular] oznacza pewną frazę rzeczownikową w liczbie pojedynczej ( NP[gender=masculie, number=singular] jest i konkretniejszy i ogólniejszy od tego typu). Interpretacja polimorficzna okazuje się być wygodniejsza przy pisaniu gramatyk, It doesn’t work in theory, but it works in practice… (Obecnie mamy w Speagramie interpretację polimorficzną.)

W Speagramie typy (czyli cechy) są symbolami lub odwzorowaniami z etykiet w typy. Mamy też domyślne etykiety symboli: jeśli domyślną etykietą symbolu NP jest POS a domyślną etykietą symbolu masculine jest gender, to NP[gender=masculine, number=?n] = [POS=NP, gender=?g, number=?n] = masculine[POS=NP, number=?n] .

W Speagramie typy (czyli cechy) są symbolami lub odwzorowaniami z etykiet w typy. Mamy też domyślne etykiety symboli: jeśli domyślną etykietą symbolu NP jest cat a domyślną etykietą symbolu masculine jest gender, to NP[gender=masculine, number=?n] = [cat=NP, gender=?g, number=?n] = masculine[cat=NP, number=?n] .

Są dwie możliwe interpretacje etykiet brakujących w opisie: sensowna formalnie interpretacja abstrakcyjna oraz praktyczna interpretacja polimorficzna. Interpretacja abstrakcyjna pod niewyspecyfikowane wartości etykiet podstawia Top, a interpretacja polimorficzna ignoruje etykiety nie występujące jednocześnie po obu stronach porównania. W interpretacji abstrakcyjnej NP[number=singular] oznacza zbiór wszystkich fraz rzeczownikowych w liczbie pojedynczej ( NP[gender=masculie, number=singular] jest ściśle konkretniejszy od tego typu), a w interpretacji polimorficznej NP[number=singular] oznacza pewną frazę rzeczownikową w liczbie pojedynczej ( NP[gender=masculie, number=singular] jest i konkretniejszy i ogólniejszy od tego typu). Interpretacja polimorficzna okazuje się być wygodniejsza przy pisaniu gramatyk, It doesn’t work in theory, but it works in practice… (Obecnie mamy w Speagramie interpretację polimorficzną, uzyskałem ją z abstrakcyjnej przez wycięcie fragmentów kodu.)

Gramatyki struktur frazowych

Mam na myśli gramatyki bazujące na CFG lub na gramatykach kategorialnych, wspierane przez więzy wyrażające ograniczenia składniowe i semantyczne. Często są one nazywane gramatykami unifikacyjnymi lub atrybutowymi.

Obecny Speagram: trochę ogólniejsze gramatyki struktur frazowych

Speagram to jednocześnie język programowania oraz dynamiczny (programowalny) parser.

Praser CFG: algorytm Earleya.

Zacznijmy od parsowania CFG: Functional Pearls: Functional Chart Parsing of Context Free Grammars by Peter Ljunglöf.

Nieterminale to typy, ale typy mogą posiadać bogatą strukturę.

Następnie dodajemy atrybuty: po lewej stronie produkcji, wstawiamy term A opisujący własności drzewa rozbioru z korzeniem wyprowadzonym z tej produkcji, zależne od własności poddrzew. Po prawej stronie produkcji, zamiast nieterminali wstawiamy term A_i opisujący interesujące nas własności, oraz relację R_i, w której term B opisujący potencjalne poddrzewo rozbioru ma być względem termu A_i. Trzy rodzaje relacji wydają się rozsądne, w żargonie języków programowania nazywają się one: “pozycja inwariantna” (=), “pozycja kowariantna” (<), “pozycja kontrawariantna” (>). Budując drzewo rozbioru zdania pilnujemy niesprzeczności wymagań. Przykłady (italiką oznaczone są terminale, a znakiem zapytania zmienne w termach własności, tzn. w typach):

 rewrite_rule ← let (> ?a) be (< ?a)

z przedchodniości, ta produkcja jest równoważna następującym:

 rewrite_rule ← let (> ?a) be (= ?a)
 rewrite_rule ← let (= ?a) be (< ?a)

Konstrukcja z języków programowania. let X be Y oznacza, że X oblicza się do Y. Żeby to było dopuszczalne, Yki muszą być Xami, tzn. typ Yka musi być podtypem Xa.

 NP[gender=?g, number=?n] ← (> ADJ[gender=?g, number=?n]) (= NP[gender=?g, number=?n])
 NP[gender=?g, number=?n] ← (= N[gender=?g, number=?n])

Przymiotnik opisujący frazę rzeczownikową może mieć typ ogólniejszy niż ta fraza, na przykład może być rodzaju męskiego gender=m, który jest nadtypem rodzajów m1, m2 i m3.

Etykiety i cechy. Interpretacja brakujących etykiet.

W Speagramie typy (czyli cechy) są symbolami lub odwzorowaniami z etykiet w typy. Tzn. jeśli domyślną etykietą symbolu NP jest cat, to NP[gender=?g, number=?n] = [cat=NP, gender=?g, number=?n].

Analiza morfologiczna (Computational Morphology, word tagging)

Rozbiór zdania nie musi zatrzymywać się na poziomie słowa: automatycznemu podziałowi słowa na morfemy możemy zmniejszyć wielkość słownika, a nawet radzić sobie z nieznanymi słowami. Dla przykładu, system konwersacyjny może swobodnie zapytać użytkownika o znaczenie wyrazu, kiedy jego rola gramatyczna jest dzięki analizie w pełni określona i znane są wzorce odmiany.

Jedno z zadań polegało na zapoznaniu się z gramatykami (czyli.. słownikami) programu sprawdzającego pisownię ispell: http://ficus-www.cs.ucla.edu/geoff/ispell.html, http://ispell-pl.sourceforge.net/.

Wydajne techniki analizy morfologicznej w OCamlu: http://pauillac.inria.fr/~huet/PUBLIC/tagger.pdf