Parsowanie to proces analizowania ciągu słów w celu odkrycia jego struktury frazowej, zgodnie z zasadami gramatyki. Możemy myśleć o tym jako o poszukiwaniu prawidłowego drzewa parsowania, którego liście są słowami ciągu. Rysunek 24.4 pokazuje, że możemy zacząć od symbolu S i wyszukiwać z góry na dół lub możemy zacząć od słów i szukać od dołu do góry. Strategie analizy odgórnej lub oddolnej mogą być jednak nieefektywne, ponieważ mogą skończyć się powtarzaniem wysiłku w obszarach przestrzeni wyszukiwania, które prowadzą do ślepych zaułków. Rozważ następujące dwa zdania: Niech uczniowie z sekcji 2 Informatyki 101 przystąpią do egzaminu. Czy uczniowie z sekcji 2 Informatyki 101 przystąpili do egzaminu? Mimo że dzielą one pierwsze 10 słów, zdania te mają bardzo różne parsy, ponieważ pierwsze jest poleceniem, a drugie pytaniem. Algorytm analizujący od lewej do prawej musiałby odgadnąć, czy pierwsze słowo jest częścią polecenia, czy pytania, i nie będzie w stanie stwierdzić, czy odgadnięcie jest poprawne, aż do co najmniej jedenastego słowa, weź lub wzięcie. Jeśli algorytm odgadnie źle, będzie musiał cofnąć się do pierwszego słowa i ponownie przeanalizować całe zdanie pod inną interpretacją. Aby uniknąć tego źródła nieefektywności, możemy użyć programowania dynamicznego: za każdym razem, gdy analizujemy podciąg, przechowuj wyniki, abyśmy nie musieli ich później ponownie analizować. Na przykład, gdy odkryjemy, że „uczniowie z sekcji 2 Informatyki 101” to NP, możemy to zapisać w strukturze danych znanej jako wykres. Algorytm, który to robi, nazywa się parserem wykresu. Ponieważ mamy do czynienia z gramatykami bezkontekstowymi, każda fraza znaleziona w kontekście jednej gałęzi drzewa wyszukiwania może działać równie dobrze w każdej innej gałęzi drzewa wyszukiwania. Istnieje wiele rodzajów parserów wykresów; opisujemy probabilistyczną wersję algorytmu analizowania wykresów bottom-up, zwanego algorytmem CYK, na cześć jego wynalazców Ali Cocke, Daniela Youngera i Tadeo Kasami.
Algorytm CYK
Algorytm CYK wykorzystuje przestrzeń O(n2m) dla tablic P i T, gdzie n to liczba słów w zdaniu, a m to liczba nieterminalnych symboli w gramatyce i zajmuje czas O(n3m). Jeśli chcemy algorytmu, który gwarantuje działanie dla wszystkich możliwych gramatyk bezkontekstowych, nie możemy zrobić nic lepszego. Ale tak naprawdę chcemy parsować tylko języki naturalne, a nie wszystkie możliwe gramatyki. Języki naturalne ewoluowały, by być łatwym do zrozumienia w czasie rzeczywistym, aby nie być tak trudnym, jak to możliwe, więc wydaje się, że powinni być podatni na szybszy algorytm parsowania. Aby spróbować dostać się do O(n), możemy zastosować wyszukiwanie A w dość prosty sposób: każdy stan jest listą elementów (słów lub kategorii). Stan początkowy to lista słów, a stan docelowy to pojedyncza pozycja S. Koszt stanu jest odwrotnością jego prawdopodobieństwa, zgodnie z definicją dotychczas stosowanych reguł. Istnieją różne heurystyki pozwalające oszacować pozostałą odległość do cel; najlepsze obecnie stosowane heurystyki pochodzą z uczenia maszynowego zastosowanego do korpusu zdań. Dzięki algorytmowi A nie musimy przeszukiwać całej przestrzeni stanów i mamy gwarancję, że pierwsza znaleziona parsowanie będzie najbardziej prawdopodobna (przy założeniu dopuszczalnej heurystyki). Zwykle będzie to szybsze niż CYK, ale (w zależności od szczegółów gramatyki) nadal wolniejsze niż O(n). Podobnie jak w przypadku tagowania części mowy, możemy użyć wyszukiwania wiązki do parsowania, gdzie w dowolnym momencie bierzemy pod uwagę tylko b najbardziej prawdopodobnych parsów alternatywnych. Oznacza to, że nie mamy gwarancji, że znajdziemy parsowanie z najwyższym prawdopodobieństwem, ale (przy ostrożnej implementacji) parser może działać w czasie O(n) i nadal znajduje najlepszą parsowanie przez większość czasu. Parser przeszukiwania wiązki z b=1 nazywany jest parserem deterministycznym. Jednym z popularnych podejść deterministycznych jest parsowanie shift-reduce, w którym przechodzimy przez zdanie słowo po słowie, wybierając w każdym punkcie, czy przenieść słowo na stos składników, czy zredukować górny(e) składnik(i) na stosie zgodnie z regułą gramatyczną. Każdy styl parsowania ma swoich zwolenników w społeczności NLP. Nawet jeśli możliwe jest przekształcenie systemu redukcji zmian w PCFG (i odwrotnie), to po zastosowaniu uczenia maszynowego do problemu wprowadzenia gramatyki, indukcyjne nastawienie, a tym samym uogólnienia, które zrobi każdy system, będą inne.