Metoda postaci normalnej Chomsky'ego: implikacje wydajności parsera CYK?

Parsery wykresów mogą być implementowane w oparciu o normalną postać Chomsky'ego lub bezpośrednio w oparciu o reguły produkcji. Załóżmy na chwilę, że mamy parser wykresu CYK, który używa normalnej postaci Chomsky'ego. Binaryzacja nie jest jednoznacznie zdefiniowana. Czy wpływa to na wydajność analizy wykresu CYK. Czy można to wykorzystać do poprawy wydajności analizatora wykresów CYK?

Chociaż oczywistą odpowiedzią jest to, że podstawowa złożoność nie może się zmienić, mogą istnieć lepsze lub gorsze algorytmy do analizowania ciągów, które faktycznie napotkasz. Wydaje się jednak, że problemem jest mniejsza relatywna częstotliwość poszczególnych produkcji gramatycznych (pytania A, B i C w pytaniu), a bardziej kwestia niewykorzystanego ślepego zaułka ślepych zaułków, które może powodować jedna binaryzacja względem drugiej.

Przy odrobinie poszukiwań znalazłem Better Binaryization for CKY Parsing (Song, Ding i Lin, EMNLP 2008), który wydaje się definitywnie stwierdzić, że możesz wybrać „lepszą” lub „gorszą” binaryzację w stosunku do tak naprawdę oczekiwanych ciągów trzeba przeanalizować. Ich nazwa „ślepych zaułków”, które można by zminimalizować w praktyce, wydaje się być niekompletnym składnikiem , a dobry przykład znajduje się na pierwszej stronie.

W rzeczywistości normalna postać Chomsky'ego (CNF) nie musi uruchamiać CYK, a jedynie binaryzację. Binaryzacja jest niezbędna, aby zachować złożoność sześcienną parsowania, chociaż jest niezbędna tylko w odniesieniu do terminali innych niż terminale (NT). Ale jeśli masz reguły obejmujące tylko 2 nieterminale i niektóre terminale, algorytm CYK staje się bardziej skomplikowany w programowaniu i wyjaśnianiu.

Jak mówisz, istnieje wiele sposobów binaryzacji. Niektóre przyniosą mniejsze gramatyki niż inne. Na przykład

X -> B C D
Y -> B C E 

może być podzielony na binarne jako

X -> Z D
Y -> Z E
Z -> B C

oszczędzając w ten sposób jedną regułę przez faktoryzację, co może zaoszczędzić na obliczeniach i na wielkości wyniku.

Ale w przypadku innych reguł możesz chcieć wziąć pod uwagę koniec reguł, a nie początek.

Nie znam pracy Song, Ding i Lin , cytowanej w odpowiedzi Roba Simmonsa . Pomysł jest interesujący, ale zastanawiam się, jak skuteczny można go porównać z innymi sposobami optymalizacji obliczeń. Nie boję się tak bardzo.

Chodzi o to, że analiza problemów tylko w odniesieniu do czystego algorytmu CKY wydaje się nieco akademickim, ale kosztownym ćwiczeniem, ponieważ istnieją inne rodzaje optymalizacji, które mogą znacznie poprawić eliminację ślepych zaułków.

CYK jest tylko jedną z prostszych odmian w rodzinie algorytmów, które najwyraźniej są zbudowane na tym samym modelu programowania dynamicznego. Mówię najwyraźniej, ponieważ najprostsza wersja tych algorytmów nie jest znana jako programowanie dynamiczne, ale jako produkt krzyżowy. Jest to stara konstrukcja gramatyki CF G, która generuje przecięcie języka gramatyki CF F i języka regularnego FSA A., ze względu na Bar Hillela, Perlesa i Shamira (1961) , jak zauważył Lang w 1995 roku .

Wszystkie analizatory składni wykresów lub ogólne analizatory składni CF oparte na programowaniu dynamicznym mogą być postrzegane jako „zoptymalizowany” wariant tej konstrukcji obejmującej wiele produktów, przy czym optymalizacja jest wykorzystywana głównie w celu uniknięcia niepotrzebnych obliczeń analizatora składni. Ale problem jest subtelny jak unikanie niepotrzebnego obliczeń może spowodować powielenie użytecznych te, które mogą być gorsze.

Będąc oddolnym, algorytm CKY wytwarza bezużyteczne obliczenia parów cząstkowych, które nie mogą wywodzić się z aksjomatu gramatyki.

Algorytmy takie jak parser GLR (aby wymienić jeden z bardziej znanych, choć opublikowano wadliwą wersję), mają pewną wiedzę odgórną, która pozwoli uniknąć wielu takich bezużytecznych obliczeń, być może kosztem. Istnieje wiele innych wariantów o różnych zachowaniach w zakresie oszczędzania na niepotrzebnych obliczeniach.

Mając na uwadze te strategie optymalizacji, należy przeanalizować strategię binaryzacji. Jaki jest sens optymalizacji tego, co może być drobnym problemem, i zignoruj ​​bardziej zaawansowane techniki.

Optymalizacja procesu analizowania jest również ściśle związana z „jakością” uzyskanej struktury parsowania, która reprezentuje wszystkie możliwe parsowania, i jest często nazywana (wspólnym) parsowaniem lasu. Omawiam to w innej odpowiedzi .

Niektóre z tych zagadnień są omówione w literaturze. Na przykład Billot i Lang analizują niektóre aspekty binaryzacji w odniesieniu do strategii parsowania.