• View
• Edit
• History
• Print

Gramatyki

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

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

1.  Analiza morfologiczna (Computational Morphology, word tagging)

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.

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

2.  Parsowanie gramatyk 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.

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.

2.1  Praser CFG: algorytm Earleya.

Zacznijmy od parsowania pełnego CFG: Functional Pearls: Functional Chart Parsing of Context Free Grammars by Peter LjunglĂśf.

2.2  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.

2.3  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”.)

2.4  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).
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:

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.

2.5  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 2006 http://dev.openwengo.com/trac/openwengo/trac.cgi/wiki/CodeCampWengoPhoneNaturalLanguage — projekt zakończony fiaskiem).

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):

 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. 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] .

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ą.)

3.  Formalizmy lingwistyczne używane w NLP

Introduction to LFG and HPSG by Ananda Lima.

3.1  Gramatyki transformacyjne

Gramatyki transformacyjne (“szkoła Chomskiego”).

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

Government & Binding Theory

An Introduction to Government & Binding

3.2  Lexical Functional Grammar (LFG)

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

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

3.3  Head-driven Phrase Structure Grammar (HPSG)

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).

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

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

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

3.4  (Lexicalized) Tree Adjoining Grammar (TAG, xTAG)

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

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

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ć. 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.

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/

4.  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.

4.1  Struktura (drzewa) rozbioru

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.

4.2  Constraint Programming

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

5.  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, 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), ten rozdział przedstawia ogĂłlnie parsowanie probabilistyczne (bez odniesień do CCG).

5.1  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

6.  Od składni do semantyki

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

Part II: Semantic Interpretation / Chapter 8 : Semantics and Logical Form, Chapter 9 : Linking Syntax and Semantics

6.1  Gramatyki Montague’a

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

6.2  Underspecification

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

6.3  Przetwarzanie dyskursu

Discourse Representation Theory