Emacs Artificial General Intelligence Algorithmic Game Theory: Prediction Markets (po polsku) Systemy Inteligentnych Agentów
|
NLP.Gramatyki HistoryHide minor edits - Show changes to output May 06, 2007, at 03:29 AM
by - semantics
Changed lines 3-4 from:
''[Na marginesie: sł to:
''[Na marginesie: słÄ‚Å‚w'' '''węzeł''' ''i'' '''wierzchołek''' ''używam zamiennie (tzn. używam pierwszego bo jest krÄ‚Å‚tsze).]'' Changed lines 8-9 from:
to:
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. Changed lines 17-18 from:
to:
OgÄ‚Å‚lnie o parsowaniu: [[http://www.cs.vu.nl/~dick/PTAPG.html | Parsing Techniques - A Practical Guide]]. Istotne hasła: metoda CYK, chart parsing, parsowanie top-down vs. bottom-up, Earley parser, metody LR. Changed lines 21-22 from:
[[http://www.cs.chalmers.se/~peb/pubs/p04-chart-pearl.pdf | Functional Pearls: Functional Chart Parsing of Context Free Grammars]] by Peter to:
[[http://www.cs.chalmers.se/~peb/pubs/p04-chart-pearl.pdf | Functional Pearls: Functional Chart Parsing of Context Free Grammars]] by Peter LjunglĂśf. Changed lines 28-30 from:
!!! [[#unif]] Inkrementacyjna unifikacja (inkrementacyjne rozstrzyganie wię Drzewa to:
!!! [[#unif]] Inkrementacyjna unifikacja (inkrementacyjne rozstrzyganie więzÄ‚Å‚w) Drzewa dowodÄ‚Å‚w (proof trees) jako drzewa rozbioru dla gramatyk unifikacyjnych, zobacz [[http://www.ida.liu.se/~ulfni/lpp/ | 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".) Changed lines 36-44 from:
# Dzielimy gramatykę na reguły leksykalne/słownikowe i pozostałe. Reguły leksykalne to te, # 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 # Można pokusić się o bardziej skomplikowane optymalizacje. Można badać klasy leksykalne (np. verb = transitive verb + intransitive verb), !!!! [[#errdesc]] Pomysły na tłumaczenie błę Jeśli zdanie jest niepoprawne gramatycznie, to parsing kończy się bez krawędzi obejmujących całe zdanie. Szukamy (dynamicznie) cią to:
# 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. # 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). # 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. !!!! [[#errdesc]] 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: Changed lines 51-53 from:
Nasyć chart przy pomocy poszerzonego zbioru reguł (poszerz odpowiednio używany algorytm parsowania). !!! [[#speagram]] Obecny [[http://svn.sourceforge.net/viewvc/speagram/trunk/speagram/ | Speagram]]: trochę to:
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. !!! [[#speagram]] Obecny [[http://svn.sourceforge.net/viewvc/speagram/trunk/speagram/ | Speagram]]: trochę ogÄ‚Å‚lniejsze gramatyki struktur frazowych Changed lines 57-58 from:
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 to:
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): Changed lines 61-62 from:
z przedchodniości, ta produkcja jest to:
z przedchodniości, ta produkcja jest rÄ‚Å‚wnoważna następującym: Changed lines 66-67 from:
Konstrukcja z ję to:
Konstrukcja z językÄ‚Å‚w programowania. [@ let X be Y @] oznacza, że @@X@@ oblicza się do @@Y@@. Żeby to było dopuszczalne, @@Y@@ki muszą być @@X@@ami, tzn. typ @@Y@@ka musi być podtypem @@X@@a. Changed lines 71-73 from:
Przymiotnik opisujący frazę rzeczownikową może mieć typ to:
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@@. Changed lines 77-78 from:
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 to:
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ą.) Changed lines 97-100 from:
HPSG przypisuje frazom -- począwszy od sł HPSG jest niederywacyjna (deklaratywna): zupełnie nieistotne jest, w jaki to:
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 ([[#p4 | dependency grammars]]). Changed lines 108-109 from:
[[http://www.cis.upenn.edu/~xtag/tech-report/node5.html | Atrybutowe leksykalne TAGs]] ([[http://www.cis.upenn.edu/~xtag/ | strona gł to:
[[http://www.cis.upenn.edu/~xtag/tech-report/node5.html | Atrybutowe leksykalne TAGs]] ([[http://www.cis.upenn.edu/~xtag/ | strona głÄ‚Å‚wna projektu xTAG]]) Changed lines 111-112 from:
Gramatyki kategorialne są to:
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: Changed lines 129-132 from:
Wielomodalne CCG mają annotacje na ukośnikach Do parsowania CCG używa się chart- 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. Changed lines 138-139 from:
Parsowanie dla gramatyk struktur frazowych istotnie wykorzystuje kolejność węzł to:
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. Changed lines 141-144 from:
Aby zaprogramować całe parsowanie jako problem rozwiązywania wię Samemu rozwiązywaniu wię to:
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. Changed lines 146-147 from:
Kompletny tutorial implementacji parsera dla "dependency grammar" na bazie programowania wię to:
Kompletny tutorial implementacji parsera dla "dependency grammar" na bazie programowania więzÄ‚Å‚w: [[http://citeseer.ist.psu.edu/duchier00constraint.html]]. Changed lines 151-154 from:
* dezambiguacji na * przyspieszania parsowania, m.in. poprzez "beam search" (pomijanie mniej prawdopodobnych to:
* 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) Changed lines 158-159 from:
[[http://www.ircs.upenn.edu/~juliahr/Dissertation/index.html | 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 to:
[[http://www.ircs.upenn.edu/~juliahr/Dissertation/index.html | 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). Changed lines 167-168 from:
[[http://www.uni-giessen.de/~g91062/Seminare/gk-cl/Allen95/al1995co.htm | Allen 1995 : Natural Language Understanding]] / to:
* [[http://let.uvt.nl/general/people/rmuskens/pubs/comput.pdf | Harry Bunt and Reinhard Muskens, ''Computational Semantics'']] * [[http://www.uni-giessen.de/~g91062/Seminare/gk-cl/Allen95/al1995co.htm | Allen 1995 : Natural Language Understanding]] / April 27, 2007, at 02:30 PM
by - GB
Changed lines 3-4 from:
''[Na marginesie: sł to:
''[Na marginesie: słÃ³w'' '''węzeł''' ''i'' '''wierzchołek''' ''używam zamiennie (tzn. używam pierwszego bo jest krótsze).]'' Changed lines 8-9 from:
to:
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. Changed lines 17-18 from:
to:
Ogólnie o parsowaniu: [[http://www.cs.vu.nl/~dick/PTAPG.html | Parsing Techniques - A Practical Guide]]. Istotne hasła: metoda CYK, chart parsing, parsowanie top-down vs. bottom-up, Earley parser, metody LR. Changed lines 21-22 from:
[[http://www.cs.chalmers.se/~peb/pubs/p04-chart-pearl.pdf | Functional Pearls: Functional Chart Parsing of Context Free Grammars]] by Peter to:
[[http://www.cs.chalmers.se/~peb/pubs/p04-chart-pearl.pdf | Functional Pearls: Functional Chart Parsing of Context Free Grammars]] by Peter Ljunglöf. Changed lines 28-30 from:
!!! [[#unif]] Inkrementacyjna unifikacja (inkrementacyjne rozstrzyganie wię Drzewa to:
!!! [[#unif]] Inkrementacyjna unifikacja (inkrementacyjne rozstrzyganie więzów) Drzewa dowodów (proof trees) jako drzewa rozbioru dla gramatyk unifikacyjnych, zobacz [[http://www.ida.liu.se/~ulfni/lpp/ | 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".) Changed lines 36-44 from:
# Dzielimy gramatykę na reguły leksykalne/słownikowe i pozostałe. Reguły leksykalne to te, # 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 # Można pokusić się o bardziej skomplikowane optymalizacje. Można badać klasy leksykalne (np. verb = transitive verb + intransitive verb), !!!! [[#errdesc]] Pomysły na tłumaczenie błę Jeśli zdanie jest niepoprawne gramatycznie, to parsing kończy się bez krawędzi obejmujących całe zdanie. Szukamy (dynamicznie) cią to:
# 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. # 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). # 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. !!!! [[#errdesc]] 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: Changed lines 51-53 from:
Nasyć chart przy pomocy poszerzonego zbioru reguł (poszerz odpowiednio używany algorytm parsowania). !!! [[#speagram]] Obecny [[http://svn.sourceforge.net/viewvc/speagram/trunk/speagram/ | Speagram]]: trochę to:
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. !!! [[#speagram]] Obecny [[http://svn.sourceforge.net/viewvc/speagram/trunk/speagram/ | Speagram]]: trochę ogólniejsze gramatyki struktur frazowych Changed lines 57-58 from:
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 to:
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): Changed lines 61-62 from:
z przedchodniości, ta produkcja jest to:
z przedchodniości, ta produkcja jest równoważna następującym: Changed lines 66-67 from:
Konstrukcja z ję to:
Konstrukcja z języków programowania. [@ let X be Y @] oznacza, że @@X@@ oblicza się do @@Y@@. Żeby to było dopuszczalne, @@Y@@ki muszą być @@X@@ami, tzn. typ @@Y@@ka musi być podtypem @@X@@a. Changed lines 71-73 from:
Przymiotnik opisujący frazę rzeczownikową może mieć typ to:
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@@. Changed lines 77-78 from:
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 to:
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ą.) Added lines 87-90:
!!!! Government & Binding Theory [[http://www.ifi.unizh.ch/CL/gschneid/dreitaegig.pdf | An Introduction to Government & Binding]] Changed lines 97-100 from:
HPSG przypisuje frazom -- począwszy od sł HPSG jest niederywacyjna (deklaratywna): zupełnie nieistotne jest, w jaki to:
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 ([[#p4 | dependency grammars]]). Changed lines 108-109 from:
[[http://www.cis.upenn.edu/~xtag/tech-report/node5.html | Atrybutowe leksykalne TAGs]] ([[http://www.cis.upenn.edu/~xtag/ | strona gł to:
[[http://www.cis.upenn.edu/~xtag/tech-report/node5.html | Atrybutowe leksykalne TAGs]] ([[http://www.cis.upenn.edu/~xtag/ | strona głÃ³wna projektu xTAG]]) Changed lines 111-112 from:
Gramatyki kategorialne są to:
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: Changed lines 129-132 from:
Wielomodalne CCG mają annotacje na ukośnikach Do parsowania CCG używa się chart- 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. Changed lines 138-139 from:
Parsowanie dla gramatyk struktur frazowych istotnie wykorzystuje kolejność węzł to:
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. Changed lines 141-144 from:
Aby zaprogramować całe parsowanie jako problem rozwiązywania wię Samemu rozwiązywaniu wię to:
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. Changed lines 146-147 from:
Kompletny tutorial implementacji parsera dla "dependency grammar" na bazie programowania wię to:
Kompletny tutorial implementacji parsera dla "dependency grammar" na bazie programowania więzów: [[http://citeseer.ist.psu.edu/duchier00constraint.html]]. Changed lines 151-154 from:
* dezambiguacji na * przyspieszania parsowania, m.in. poprzez "beam search" (pomijanie mniej prawdopodobnych to:
* 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) Changed lines 158-159 from:
[[http://www.ircs.upenn.edu/~juliahr/Dissertation/index.html | 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 to:
[[http://www.ircs.upenn.edu/~juliahr/Dissertation/index.html | 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). Changed line 79 from:
!! Formalizmy lingwistyczne używane w NLP to:
!! [[#ling]] Formalizmy lingwistyczne używane w NLP Changed line 133 from:
!! Gramatyki zależności (dependency grammars) to:
!! [[#depgram]] Gramatyki zależności (dependency grammars) Changed line 136 from:
!!! Struktura (drzewa) rozbioru to:
!!! [[#deptree]] Struktura (drzewa) rozbioru Changed line 7 from:
!! [[# to:
!! [[#morf]] Analiza morfologiczna (Computational Morphology, word tagging) Changed line 14 from:
!! [[# to:
!! [[#pars]] Parsowanie gramatyk struktur frazowych Changed line 19 from:
!!! [[# to:
!!! [[#cfg]] Praser CFG: algorytm Earleya. Changed line 23 from:
!!! [[# to:
!!! [[#lr]] Parsery "shift-reduce" w kontekście NLP Changed line 28 from:
!!! [[# to:
!!! [[#unif]] Inkrementacyjna unifikacja (inkrementacyjne rozstrzyganie więzów) Changed lines 31-33 from:
!!! [[# !!!! [[# to:
!!! [[#chart]] Usprawnianie chart-parsera !!!! [[#chartopt]] Pomysły na optymalizację Changed line 42 from:
!!!! [[# to:
!!!! [[#errdesc]] Pomysły na tłumaczenie błędów gramatycznych Changed line 53 from:
!!! [[# to:
!!! [[#speagram]] Obecny [[http://svn.sourceforge.net/viewvc/speagram/trunk/speagram/ | Speagram]]: trochę ogólniejsze gramatyki struktur frazowych Changed line 56 from:
!!!! to:
!!!! Nieterminale to typy, ale typy mogą posiadać bogatą strukturę. Changed line 74 from:
!!!! to:
!!!! Etykiety i cechy. Interpretacja brakujących etykiet. Changed line 79 from:
!! to:
!! Formalizmy lingwistyczne używane w NLP Changed line 82 from:
!!! [[# to:
!!! [[#transf]] Gramatyki transformacyjne Changed line 87 from:
!!! [[# to:
!!! [[#lfg]] Lexical Functional Grammar (LFG) Changed line 92 from:
!!! [[# to:
!!! [[#hpsg]] Head-driven Phrase Structure Grammar (HPSG) Changed line 103 from:
!!! [[# to:
!!! [[#xtag]] (Lexicalized) Tree Adjoining Grammar (TAG, xTAG) Changed line 106 from:
!!! [[# to:
!!! [[#ccg]] Unification Categorial Grammar, Combinatory Categorial Grammar (UCG, CCG) Changed line 133 from:
!! to:
!! Gramatyki zależności (dependency grammars) Changed line 136 from:
!!! to:
!!! Struktura (drzewa) rozbioru Changed line 141 from:
!!! [[# to:
!!! [[#constr]] Constraint Programming Changed line 144 from:
!! [[# to:
!! [[#prob]] Gramatyki probabilistyczne, parsowanie probabilistyczne Changed lines 156-157 from:
!!! [[# to:
!!! [[#probdep]] Parsery probabilistyczne z modelowaniem zależności w strukturze predykatowo-argumentowej Changed lines 161-162 from:
!! [[# to:
!! [[#sem]] Od składni do semantyki Changed line 167 from:
!!! [[# to:
!!! [[#montag]] Gramatyki Montague'a Changed line 170 from:
!!! [[# to:
!!! [[#underspec]] Underspecification Changed lines 173-175 from:
!!! [[# !!!! [[# to:
!!! [[#disc]] Przetwarzanie dyskursu !!!! [[#drt]] Discourse Representation Theory Deleted lines 2-29:
# [[#p2 | Parsowanie gramatyk struktur frazowych]] ## [[#p21 | Praser CFG: algorytm Earleya.]] ## [[#p22 | Parsery "shift-reduce" w kontekście NLP.]] ## [[#p23 | Inkrementacyjna unifikacja (inkrementacyjne rozstrzyganie więzów)]] ## [[#p24 | Usprawnianie chart-parsera]] ### [[#p241 | Pomysły na optymalizację]] ### [[#p242 | Pomysły na tłumaczenie błędów gramatycznych]] ## [[#p25 | Obecny Speagram: trochę ogólniejsze gramatyki struktur frazowych]] ### [[#p251 | Nieterminale to typy, ale typy mogą posiadać bogatą strukturę.]] ### [[#p252 | Etykiety i cechy. Interpretacja brakujących etykiet.]] # [[#p3 | Formalizmy lingwistyczne używane w NLP]] ## [[#p31 | Gramatyki transformacyjne]] ## [[#p32 | Lexical Functional Grammar (LFG)]] ## [[#p33 | Head-driven Phrase Structure Grammar (HPSG)]] ## [[#p34 | (Lexicalized) Tree Adjoining Grammar (TAG, xTAG)]] ## [[#p35 | Unification Categorial Grammar, Combinatory Categorial Grammar (UCG, CCG)]] # [[#p4 | Gramatyki zależności (dependency grammars)]] ## [[#p41 | Struktura (drzewa) rozbioru]] ## [[#p42 | Constraint Programming]] # [[#p5 | Gramatyki probabilistyczne, parsowanie probabilistyczne]] ## [[#p51 | Parsery probabilistyczne z modelowaniem zależności w strukturze predykatowo-argumentowej]] # [[#p6 | Od składni do semantyki]] ## [[#p61 | Gramatyki Montague'a]] ## [[#p62 | Underspecification]] ## [[#p63 | Przetwarzanie dyskursu]] ### [[#p631 | Discourse Representation Theory]] Added lines 43-44:
Ogólnie o parsowaniu: [[http://www.cs.vu.nl/~dick/PTAPG.html | Parsing Techniques - A Practical Guide]]. Istotne hasła: metoda CYK, chart parsing, parsowanie top-down vs. bottom-up, Earley parser, metody LR. Added line 22:
## [[#p51 | Parsery probabilistyczne z modelowaniem zależności w strukturze predykatowo-argumentowej]] Changed lines 180-181 from:
!!! Parsery probabilistyczne z modelowaniem zależności w strukturze predykatowo-argumentowej to:
!!! [[#p51]] Parsery probabilistyczne z modelowaniem zależności w strukturze predykatowo-argumentowej Changed lines 177-178 from:
[[http://www.ircs.upenn.edu/~juliahr/Dissertation/index.html | Data and models for statistical parsing with Combinatory Categorial Grammar]], Chapter 4. A brief introduction to statistical parsing (faktycznie strony 121-152 wersji jednostronnej). to:
[[http://www.ircs.upenn.edu/~juliahr/Dissertation/index.html | 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 [[#p4 | "dependency grammars"]] pozwala na optymalniejsze posługiwanie się gramatykami probabilistycznymi. [[http://www.ircs.upenn.edu/~juliahr/Papers/ACL2003/HockenmaierACL2003.pdf | Parsing with generative models of predicate-argument structure]] Added line 185:
Changed lines 172-173 from:
* przyspieszania parsowania, poprzez "beam search" (pomijanie mniej prawdopodobnych wariantów) to:
* przyspieszania parsowania, m.in. poprzez "beam search" (pomijanie mniej prawdopodobnych wariantów) [[http://www.uni-giessen.de/~g91062/Seminare/gk-cl/Allen95/al1995co.htm | Allen 1995: Natural Language Understanding]] / [[http://www.uni-giessen.de/~g91062/Seminare/gk-cl/Allen95/al199507.htm | Chapter 7 - Ambiguity Resolution: Statistical Methods]] / [[http://www.uni-giessen.de/~g91062/Seminare/gk-cl/Allen95/al199507.htm#chap7_4 | 7.4 Obtaining Lexical Probabilities]], [[http://www.uni-giessen.de/~g91062/Seminare/gk-cl/Allen95/al199507.htm#chap7_5 | 7.5 Probabilistic Context-Free Grammars]], [[http://www.uni-giessen.de/~g91062/Seminare/gk-cl/Allen95/al199507.htm#chap7_6 | 7.6 Best-First Parsing]], [[http://www.uni-giessen.de/~g91062/Seminare/gk-cl/Allen95/al199507.htm#chap7_7 | 7.7 A Simple Context-Dependent Best-First Parser]] [[http://www.ircs.upenn.edu/~juliahr/Dissertation/index.html | Data and models for statistical parsing with Combinatory Categorial Grammar]], Chapter 4. A brief introduction to statistical parsing (faktycznie strony 121-152 wersji jednostronnej). Changed lines 4-10 from:
## [[#p22 | ## [[#p23 | ### [[#p231 | Pomys ### [[# to:
## [[#p22 | Parsery "shift-reduce" w kontekście NLP.]] ## [[#p23 | Inkrementacyjna unifikacja (inkrementacyjne rozstrzyganie więzów)]] ## [[#p24 | Usprawnianie chart-parsera]] ### [[#p241 | Pomysły na optymalizację]] ### [[#p242 | Pomysły na tłumaczenie błędów gramatycznych]] ## [[#p25 | Obecny Speagram: trochę ogólniejsze gramatyki struktur frazowych]] ### [[#p251 | Nieterminale to typy, ale typy mogą posiadać bogatą strukturę.]] ### [[#p252 | Etykiety i cechy. Interpretacja brakujących etykiet.]] Changed line 43 from:
Zacznijmy od parsowania CFG: to:
Zacznijmy od parsowania pełnego CFG: Changed lines 46-51 from:
!!! [[#p22]] Inkrementacyjna unifikacja (inkrementacyjne rozstrzyganie więzów) to:
!!! [[#p22]] Parsery "shift-reduce" w kontekście NLP [[http://www.uni-giessen.de/~g91062/Seminare/gk-cl/Allen95/al1995co.htm | Allen 1995 : Natural Language Understanding]] / [[http://www.uni-giessen.de/~g91062/Seminare/gk-cl/Allen95/al199506.htm | Chapter 6: Toward Efficient Parsing]] Dla gramatyk CCG: [[http://homepages.inf.ed.ac.uk/s9764747/PAPERS/McConvilleMScThesis.pdf | Incremental natural language understanding with combinatory categorial grammar]]. !!! [[#p23]] Inkrementacyjna unifikacja (inkrementacyjne rozstrzyganie więzów) Changed lines 54-56 from:
!!! [[# !!!! [[# to:
!!! [[#p24]] Usprawnianie chart-parsera !!!! [[#p241]] Pomysły na optymalizację Changed line 65 from:
!!!! [[# to:
!!!! [[#p242]] Pomysły na tłumaczenie błędów gramatycznych Changed line 76 from:
!!! [[# to:
!!! [[#p25]] Obecny [[http://svn.sourceforge.net/viewvc/speagram/trunk/speagram/ | Speagram]]: trochę ogólniejsze gramatyki struktur frazowych Changed line 79 from:
!!!! [[# to:
!!!! [[#p251]] Nieterminale to typy, ale typy mogą posiadać bogatą strukturę. Changed line 97 from:
!!!! [[# to:
!!!! [[#p252]] Etykiety i cechy. Interpretacja brakujących etykiet. Changed lines 175-178 from:
to:
[[http://www.uni-giessen.de/~g91062/Seminare/gk-cl/Allen95/al1995co.htm | Allen 1995 : Natural Language Understanding]] / [[http://www.uni-giessen.de/~g91062/Seminare/gk-cl/Allen95/al95p2.htm | Part II: Semantic Interpretation]] / [[http://www.uni-giessen.de/~g91062/Seminare/gk-cl/Allen95/al199508.htm | Chapter 8 : Semantics and Logical Form]], [[http://www.uni-giessen.de/~g91062/Seminare/gk-cl/Allen95/al199509.htm | Chapter 9 : Linking Syntax and Semantics]] Changed lines 142-143 from:
Wielomodalne CCG mają annotacje na ukośnikach mówiące, które reguły można do danej kategorii złożonej stosować. 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. Changed lines 20-25 from:
# [[#p5 | # ## [[# ## to:
# [[#p5 | Gramatyki probabilistyczne, parsowanie probabilistyczne]] # [[#p6 | Od składni do semantyki]] ## [[#p61 | Gramatyki Montague'a]] ## [[#p62 | Underspecification]] ## [[#p63 | Przetwarzanie dyskursu]] ### [[#p631 | Discourse Representation Theory]] Added lines 124-145:
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: # [@ (X / Y) Y ==> X @] (aplikacja) # [@ Y (X \ Y) ==> X @] Kombinatoryczne gramatyki kategorialne (o mocy "mildly context sensitive") mają dodatkowo reguły # [@ (X / Y) (Y / Z) ==> X / Z @] (złożenie) # [@ (X \ Y) (Y \ Z) ==> X \ Z @] # [@ X ==> T / (T \ X) @] (podniesienie typu) # [@ (X / Y) (Y \ Z) ==> X \ Z @] (złożenie krzyżowe) # [@ (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. Changed lines 161-163 from:
!! [[#p5]] !!! [[ to:
!! [[#p5]] 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) !! [[#p6]] Od składni do semantyki !!! [[#p61]] Gramatyki Montague'a Changed line 173 from:
!!! [[# to:
!!! [[#p62]] Underspecification Changed lines 176-178 from:
!!! [[# !!!! [[# to:
!!! [[#p63]] Przetwarzanie dyskursu !!!! [[#p631]] Discourse Representation Theory Changed lines 70-71 from:
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 to:
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). Changed lines 69-71 from:
!!! [[#p24]] Obecny Speagram to:
!!! [[#p24]] Obecny [[http://svn.sourceforge.net/viewvc/speagram/trunk/speagram/ | 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). Changed lines 111-112 from:
HPSG jest niederywacyjna to:
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 ([[#p4 | dependency grammars]]). Added lines 111-112:
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 ([[#p4 | dependency grammars]]). Added lines 109-114:
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/]] ([[http://www.cl.uni-bremen.de/~stefan/PS/konstanz2001-slides.pdf | slajdy dla HPSG]]) Changed lines 104-105 from:
[[http://www.essex.ac.uk/linguistics/LFG/ | Strona domowa LFG]] to:
[[http://www.essex.ac.uk/linguistics/LFG/ | Strona domowa LFG]] (m. in. [[http://users.ox.ac.uk/~cpgl0015/lfg.pdf | wprowadzenie do LFG]]) Changed line 16 from:
## [[#p35 | to:
## [[#p35 | Unification Categorial Grammar, Combinatory Categorial Grammar (UCG, CCG)]] Added lines 104-105:
[[http://www.essex.ac.uk/linguistics/LFG/ | Strona domowa LFG]] Changed line 114 from:
!!! [[#p35]] to:
!!! [[#p35]] Unification Categorial Grammar, Combinatory Categorial Grammar (UCG, CCG) Changed lines 110-111 from:
[[http://www.cis.upenn.edu/~xtag/ to:
[[http://www.cis.upenn.edu/~xtag/tech-report/node5.html | Atrybutowe leksykalne TAGs]] ([[http://www.cis.upenn.edu/~xtag/ | strona główna projektu xTAG]]) Changed lines 113-115 from:
to:
Publikacje dot. CCG: [[http://groups.inf.ed.ac.uk/ccg/publications.html]] (m. in. [[ftp://ftp.cogsci.ed.ac.uk/pub/steedman/ccg/manifesto.pdf | wprowadzenie do CCG]]). Multi-modalne CCG: [[http://www.dfki.de/~gj/lectures/050404-08.fi.helsinki.kit/]] Changed lines 110-111 from:
to:
[[http://www.cis.upenn.edu/~xtag/]] Changed lines 113-114 from:
to:
[[http://www.dfki.de/~gj/lectures/050404-08.fi.helsinki.kit/]] [[http://groups.inf.ed.ac.uk/ccg/publications.html]] Changed lines 2-24 from:
# [[#p2 | ## [[#p21 | ## ### [[# ### # ## ## [[#p23 | Formalizmy lingwistyczne u& ### [[#p231 | Gramatyki transformacyjne ## # # [[# # ## [[# # [[# ## [[# ## [[#p42 | Underspecification]] ## [[#p43 | Przetwarzanie dyskursu]] ### [[#p431 to:
# [[#p2 | Parsowanie gramatyk struktur frazowych]] ## [[#p21 | Praser CFG: algorytm Earleya.]] ## [[#p22 | Inkrementacyjna unifikacja (inkrementacyjne rozstrzyganie więzów)]] ## [[#p23 | Usprawnianie chart-parsera]] ### [[#p231 | Pomysły na optymalizację]] ### [[#p232 | Pomysły na tłumaczenie błędów gramatycznych]] ## [[#p24 | Obecny Speagram: trochę ogólniejsze gramatyki struktur frazowych]] ### [[#p241 | Nieterminale to typy, ale typy mogą posiadać bogatą strukturę.]] ### [[#p242 | Etykiety i cechy. Interpretacja brakujących etykiet.]] # [[#p3 | Formalizmy lingwistyczne używane w NLP]] ## [[#p31 | Gramatyki transformacyjne]] ## [[#p32 | Lexical Functional Grammar (LFG)]] ## [[#p33 | Head-driven Phrase Structure Grammar (HPSG)]] ## [[#p34 | (Lexicalized) Tree Adjoining Grammar (TAG, xTAG)]] ## [[#p35 | Unificational Categorial Grammar, Combinatory Categorial Grammar (UCG, CCG)]] # [[#p4 | Gramatyki zależności (dependency grammars)]] ## [[#p41 | Struktura (drzewa) rozbioru]] ## [[#p42 | Constraint Programming]] # [[#p5 | Od składni do semantyki]] ## [[#p51 | Gramatyki Montague'a]] ## [[#p52 | Underspecification]] ## [[#p53 | Przetwarzanie dyskursu]] ### [[#p531 | Discourse Representation Theory]] Changed line 37 from:
!! [[#p2]] to:
!! [[#p2]] Parsowanie gramatyk struktur frazowych Changed lines 40-42 from:
!!! [[#p21 !!!! [[#p211 to:
!!! [[#p21]] Praser CFG: algorytm Earleya. Changed line 44 from:
!!! to:
!!! [[#p22]] Inkrementacyjna unifikacja (inkrementacyjne rozstrzyganie więzów) Changed lines 47-49 from:
!!! !!!! to:
!!! [[#p23]] Usprawnianie chart-parsera !!!! [[#p231]] Pomysły na optymalizację Changed line 58 from:
!!!! to:
!!!! [[#p232]] Pomysły na tłumaczenie błędów gramatycznych Changed line 69 from:
!!! [[# to:
!!! [[#p24]] Obecny Speagram: trochę ogólniejsze gramatyki struktur frazowych Changed line 72 from:
!!!! [[# to:
!!!! [[#p241]] Nieterminale to typy, ale typy mogą posiadać bogatą strukturę. Changed line 90 from:
!!!! [[# to:
!!!! [[#p242]] Etykiety i cechy. Interpretacja brakujących etykiet. Changed line 95 from:
!! to:
!! [[#p3]] Formalizmy lingwistyczne używane w NLP Changed line 98 from:
!!! to:
!!! [[#p31]] Gramatyki transformacyjne Changed line 103 from:
!!! to:
!!! [[#p32]] Lexical Functional Grammar (LFG) Changed line 106 from:
!!! to:
!!! [[#p33]] Head-driven Phrase Structure Grammar (HPSG) Changed lines 109-114 from:
!! [[# to:
!!! [[#p34]] (Lexicalized) Tree Adjoining Grammar (TAG, xTAG) !!! [[#p35]] Unificational Categorial Grammar, Combinatory Categorial Grammar (UCG, CCG) !! [[#p4]] Gramatyki zależności (dependency grammars) Changed line 117 from:
!!! [[# to:
!!! [[#p41]] Struktura (drzewa) rozbioru Changed line 122 from:
!!! [[# to:
!!! [[#p42]] Constraint Programming Changed lines 125-127 from:
!! [[# !!! [[# to:
!! [[#p5]] Od składni do semantyki !!! [[#p51]] Gramatyki Montague'a Changed line 130 from:
!!! [[# to:
!!! [[#p52]] Underspecification Changed lines 133-135 from:
!!! [[# !!!! [[# to:
!!! [[#p53]] Przetwarzanie dyskursu !!!! [[#p531]] Discourse Representation Theory Changed lines 57-58 from:
# 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. to:
# 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. Changed lines 60-61 from:
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: to:
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: Changed lines 21-24 from:
to:
## [[#p42 | Underspecification]] ## [[#p43 | Przetwarzanie dyskursu]] ### [[#p431 | Discourse Representation Theory]] Added lines 125-131:
!!! [[#p42]] Underspecification [[http://www.coli.uni-saarland.de/courses/underspecification-06/page.php?id=schedule]] !!! [[#p43]] Przetwarzanie dyskursu !!!! [[#p431]] Discourse Representation Theory Changed lines 13-14 from:
### [[#p231 | ### [[#p232 | Head-driven Phrase Structure Grammar (HPSG)]] to:
### [[#p231 | Gramatyki transformacyjne]] ### [[#p232 | Lexical Functional Grammar (LFG)]] ### [[#p233 | Head-driven Phrase Structure Grammar (HPSG)]] Changed lines 96-99 from:
!!!! [[#p231]] !!!! to:
!!!! [[#p231]] Gramatyki transformacyjne Gramatyki transformacyjne ("szkoła Chomskiego"). [[http://www.ling.upenn.edu/~beatrice/syntax-textbook/index.html]] !!!! [[#p232]] Lexical Functional Grammar (LFG) [[http://emsah.uq.edu.au/linguistics/Working%20Papers/ananda_ling/LFG_Summary.htm]] !!!! [[#p233]] Head-driven Phrase Structure Grammar (HPSG) [[http://emsah.uq.edu.au/linguistics/Working%20Papers/ananda_ling/HPSG_Summary.htm]] Changed lines 93-94 from:
to:
[[http://emsah.uq.edu.au/linguistics/Working%20Papers/ananda_ling/ | Introduction to LFG and HPSG]] by Ananda Lima. Changed lines 12-14 from:
## [[#p23 | to:
## [[#p23 | Formalizmy lingwistyczne używane w NLP]] ### [[#p231 | Lexical Functional Grammar (LFG)]] ### [[#p232 | Head-driven Phrase Structure Grammar (HPSG)]] Changed lines 92-93 from:
!!! [[#p23]] to:
!!! [[#p23]] Formalizmy lingwistyczne używane w NLP !!!! [[#p231]] Lexical Functional Grammar (LFG) !!!![[#p232]] Head-driven Phrase Structure Grammar (HPSG) Added line 12:
## [[#p23 | Head-driven Phrase Structure Grammars]] Changed lines 40-41 from:
Drzewa dowodów (proof trees) jako drzewa rozbioru dla gramatyk unifikacyjnych, zobacz [[http://www.ida.liu.se/~ulfni/lpp/ | 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.) to:
Drzewa dowodów (proof trees) jako drzewa rozbioru dla gramatyk unifikacyjnych, zobacz [[http://www.ida.liu.se/~ulfni/lpp/ | 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".) Added lines 51-52:
# 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. Changed lines 54-63 from:
to:
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. Added lines 90-91:
!!! [[#p23]] Head-driven Phrase Structure Grammars Changed lines 6-8 from:
### [[#p213 | to:
### [[#p213 | Usprawnianie chart-parsera]] #### [[#p2131 | Pomysły na optymalizację]] #### [[#p2132 | Pomysły na tłumaczenie błędów gramatycznych]] Changed lines 41-42 from:
!!!! [[#p213]] to:
!!!! [[#p213]] Usprawnianie chart-parsera !!!!! [[#p2131]] Pomysły na optymalizację Dla ustalenia uwagi udoskonalamy algorytm Earleya: bottom-up left-to-right # 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. # 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). !!!!! [[#p2132]] Pomysły na tłumaczenie błędów gramatycznych Added lines 18-19:
''Uwaga: notatki są w trakcie opracowywania i mogą zawierać poważne błędy.'' Changed lines 37-38 from:
to:
Drzewa dowodów (proof trees) jako drzewa rozbioru dla gramatyk unifikacyjnych, zobacz [[http://www.ida.liu.se/~ulfni/lpp/ | 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.) Changed lines 19-20 from:
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. to:
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. Changed line 12 from:
## [[#p32 to:
## [[#p32 | Constraint Programming]] Changed line 8 from:
### [[#p221 | Nieterminale to typy, ale typy mogą posiadać bogatą strukturę.] to:
### [[#p221 | Nieterminale to typy, ale typy mogą posiadać bogatą strukturę.]] Added lines 1-15:
# [[#p1 | Analiza morfologiczna (Computational Morphology, word tagging) ]] # [[#p2 | Gramatyki struktur frazowych]] ## [[#p21 | Parsowanie]] ### [[#p211 | Praser CFG: algorytm Earleya.]] ### [[#p212 | Inkrementacyjna unifikacja (inkrementacyjne rozstrzyganie więzów)]] ### [[#p213 | Pomysły na optymalizację parsera]] ## [[#p22 | Obecny Speagram: trochę ogólniejsze gramatyki struktur frazowych]] ### [[#p221 | Nieterminale to typy, ale typy mogą posiadać bogatą strukturę.] ### [[#p222 | Etykiety i cechy. Interpretacja brakujących etykiet.]] # [[#p3 | Gramatyki zależności (dependency grammars)]] ## [[#p31 | Struktura (drzewa) rozbioru]] ## [[#p32]] Constraint Programming # [[#p4 | Od składni do semantyki]] ## [[#p41 | Gramatyki Montague'a]] Changed line 18 from:
!! Analiza morfologiczna (Computational Morphology, word tagging) to:
!! [[#p1]] Analiza morfologiczna (Computational Morphology, word tagging) Changed line 25 from:
!! Gramatyki struktur frazowych to:
!! [[#p2]] Gramatyki struktur frazowych Changed lines 28-31 from:
!!! Speagram to jednocześnie język programowania oraz dynamiczny (programowalny) parser. !!!! to:
!!! [[#p21]] Parsowanie !!!! [[#p211]] Praser CFG: algorytm Earleya. Changed lines 34-36 from:
!!!! Następnie dodajemy atrybuty: po to:
!!!! [[#p212]] Inkrementacyjna unifikacja (inkrementacyjne rozstrzyganie więzów) !!!! [[#p213]] Pomysły na optymalizację parsera !!! [[#p22]] Obecny Speagram: trochę ogólniejsze gramatyki struktur frazowych Speagram to jednocześnie język programowania oraz dynamiczny (programowalny) parser. !!!! [[#p221]] 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): Changed line 59 from:
!!!! Etykiety i cechy. Interpretacja brakujących etykiet. to:
!!!! [[#p222]] Etykiety i cechy. Interpretacja brakujących etykiet. Changed line 64 from:
!! Gramatyki zależności (dependency grammars) to:
!! [[#p3]] Gramatyki zależności (dependency grammars) Changed line 67 from:
!!! Struktura (drzewa) rozbioru to:
!!! [[#p31]] Struktura (drzewa) rozbioru Changed line 72 from:
!!! Constraint Programming to:
!!! [[#p32]] Constraint Programming Added lines 74-78:
!! [[#p4]] Od składni do semantyki !!! [[#p41]] Gramatyki Montague'a [[http://www-personal.umich.edu/~akao/MontagueGrammar.pdf]] Added lines 50-52:
!!! Constraint Programming Kompletny tutorial implementacji parsera dla "dependency grammar" na bazie programowania więzów: [[http://citeseer.ist.psu.edu/duchier00constraint.html]]. Changed line 46 from:
!!! Struktura drzewa rozbioru to:
!!! Struktura (drzewa) rozbioru Added line 49:
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. Added lines 1-2:
''[Na marginesie: słów'' '''węzeł''' ''i'' '''wierzchołek''' ''używam zamiennie (tzn. używam pierwszego bo jest krótsze).]'' Changed lines 47-48 from:
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. to:
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. Added lines 43-45:
!!! 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. Added lines 41-42:
!! 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. Changed lines 39-40 from:
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ą to:
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ą.) Changed lines 37-38 from:
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 @@ to:
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] @]. Changed lines 37-40 from:
W Speagramie typy (czyli cechy) są symbolami lub odwzorowaniami z etykiet w typy. to:
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.) Changed lines 8-37 from:
to:
!! 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: [[http://www.cs.chalmers.se/~peb/pubs/p04-chart-pearl.pdf | 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, @@Y@@ki muszą być @@X@@ami, tzn. typ @@Y@@ka musi być podtypem @@X@@a. 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]@]. Added lines 1-8:
!! 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]] !! |