Analiza składniowa (lingwistyka komputerowa)

Analiza składniowa to automatyczna analiza struktury składniowej języka naturalnego, w szczególności relacji składniowych (w gramatyce zależności ) i rozpiętości etykietowania składowych (w gramatyce okręgowej ). Jest to motywowane problemem niejednoznaczności strukturalnej w języku naturalnym: zdaniu można przypisać wiele analiz gramatycznych, więc potrzebna jest pewna wiedza wykraczająca poza reguły gramatyki obliczeniowej, aby określić, która analiza jest zamierzona. Analiza składniowa jest jednym z ważnych zadań w lingwistyce komputerowej i przetwarzanie języka naturalnego i jest przedmiotem badań od połowy XX wieku wraz z pojawieniem się komputerów.

Różne teorie gramatyki proponują różne formalizmy do opisu składniowej struktury zdań. Dla celów obliczeniowych formalizmy te można pogrupować w gramatyki okręgowe i gramatyki zależności . Parsery dla obu klas wymagają różnych typów algorytmów, a podejścia do tych dwóch problemów przybrały różne formy. Tworzenie banków drzew z adnotacjami ludzkimi przy użyciu różnych formalizmów (np. uniwersalnych zależności ) przebiegało równolegle z rozwojem nowych algorytmów i metod analizy składniowej.

Oznaczanie części mowy (które rozwiązuje pewne niejasności semantyczne) jest powiązanym problemem i często warunkiem wstępnym lub podproblemem analizy składniowej. Analizy składniowe mogą być wykorzystywane do ekstrakcji informacji (np. analizowanie zdarzeń, etykietowanie ról semantycznych, etykietowanie jednostek) i mogą być dalej wykorzystywane do wydobywania formalnych reprezentacji semantycznych .

Parsowanie okręgów wyborczych

Analizowanie okręgów wyborczych obejmuje analizowanie zgodnie z formalizmami gramatycznymi okręgów wyborczych, takimi jak minimalizm lub formalizm Penn Treebank . Oznacza to co najmniej stwierdzenie, które przęsła są składowymi (np. [The man] is here. ) i jakiego rodzaju są to składowe (np. [The man] jest frazą rzeczownikową) na podstawie gramatyki bezkontekstowej (CFG), który koduje zasady tworzenia i łączenia składników.

Algorytmy generalnie wymagają konwersji CFG do postaci normalnej Chomsky'ego (z dwojgiem dzieci na składnik), co można zrobić bez utraty jakichkolwiek informacji o drzewie lub zmniejszania ekspresji przy użyciu algorytmu opisanego po raz pierwszy przez Hopcrofta i Ullmana w 1979 roku.

CKY

Najpopularniejszym algorytmem analizowania okręgów wyborczych jest algorytm Cocke – Kasami – Younger (CKY), który jest algorytmem programowania dynamicznego, który konstruuje analizę składniową w najgorszym przypadku $prawo | \ prawo)}$ ${\ Displaystyle {\ mathcal {O }} \ lewo (n ^ {3} \ cdot \ lewo |$ $\$ czas, w zdaniu słów i ${\ displaystyle \ lewo | G \ prawo |}$ to rozmiar CFG podany w postaci normalnej Chomsky'ego .

Biorąc pod uwagę problem niejednoznaczności (np. niejednoznaczności przyimka-dołączenia w języku angielskim) prowadzącej do wielu akceptowalnych analiz, konieczna jest umiejętność oceny prawdopodobieństwa analiz, aby wybrać najbardziej prawdopodobną. Jednym ze sposobów na to jest użycie probabilistycznej gramatyki bezkontekstowej (PCFG), która ma prawdopodobieństwo każdej reguły okręgu wyborczego, oraz zmodyfikowanie CKY w celu maksymalizacji prawdopodobieństw podczas analizy oddolnej.

Kolejną modyfikacją jest leksykalny PCFG, który przypisuje głowę każdemu składnikowi i koduje regułę dla każdego leksemu w tym gnieździe. Tak więc, gdy PCFG może mieć regułę „NP → DT NN” (wyrażenie rzeczownikowe jest wyznacznikiem i rzeczownikiem), podczas gdy zleksykalizowany PCFG będzie miał konkretnie reguły, takie jak „NP (pies) → DT NN (pies)” lub „NP (osoba)” itd. W praktyce prowadzi to do pewnych ulepszeń wydajności.

Nowsza praca polega na neuronowej ocenie prawdopodobieństwa rozpiętości (która może uwzględniać kontekst w przeciwieństwie do (P)CFG) w celu zasilania CKY, na przykład za pomocą powtarzającej się sieci neuronowej lub transformatora na podstawie osadzania słów .

W 2022 roku Nikita Kitaev i in. wprowadził parser przyrostowy, który najpierw uczy się dyskretnych etykiet (z ustalonego słownictwa) dla każdego tokena wejściowego, biorąc pod uwagę tylko kontekst po lewej stronie, które są wtedy jedynymi danymi wejściowymi do parsera wykresów CKY z prawdopodobieństwami obliczonymi przy użyciu wyuczonego skalera zakresu neuronowego. Podejście to jest nie tylko motywowane językowo, ale także konkurencyjne w stosunku do poprzednich podejść do analizowania okręgów wyborczych. Ich praca zdobyła nagrodę za najlepszy artykuł na ACL 2022 .

Oparte na przejściach

Po sukcesie $na$ przejściach dla gramatyk zależności rozpoczęto prace nad dostosowaniem podejścia do analizowania Pierwszą taką pracę wykonali Kenji Sagae i Alon Lavie w 2005 roku, która opierała się na klasyfikatorze opartym na funkcjach, aby zachłannie podejmować decyzje dotyczące przejścia. Po tym nastąpiła praca Yue Zhanga i Stephena Clarka w 2009 roku, która dodała przeszukiwanie wiązki do dekodera, aby wykonać bardziej globalnie optymalne analizy. Pierwszym parserem z tej rodziny, który przewyższył parser oparty na wykresach, był parser autorstwa Muhua Zhu i in. w 2013 r., który zajął się problemem różnic długości różnych sekwencji przejściowych ze względu na jednoargumentowe reguły okręgów wyborczych (nieistniejący problem przy analizowaniu zależności) poprzez dodanie operacji wypełniania.

Należy zauważyć, że parsowanie oparte na przejściach może być czysto zachłanne (tj. wybieranie najlepszej opcji na każdym etapie budowania drzewa, co prowadzi do potencjalnie nieoptymalnych lub źle uformowanych drzew) lub używać wyszukiwania wiązek w celu zwiększenia wydajności bez poświęcania wydajności .

Sekwencja do sekwencji

Oriol Vinyals et al. w 2015 r. W tym podejściu parsowanie składników jest modelowane jak tłumaczenie maszynowe : zadaniem jest konwersja sekwencji do sekwencji ze zdania na analizę składniową, w oryginalnym artykule przy użyciu głębokiego LSTM z mechanizmem uwagi . Złote drzewa treningowe muszą być linearyzowane dla tego rodzaju modelu, ale konwersja nie powoduje utraty żadnych informacji. To działa w ${\ Displaystyle O (n)}$ z dekoderem wyszukiwania wiązek o szerokości 10 (ale nie znaleźli większych korzyści z większego rozmiaru wiązki, a nawet ograniczenie go do zachłannego dekodowania działa dobrze) i osiąga konkurencyjną wydajność dzięki tradycyjnym algorytmom do analizy bezkontekstowej, takiej jak CKY.

Analiza zależności

Analizowanie zależności jest analizowaniem zgodnie z formalizmem gramatyki zależności, takim jak Universal Dependencies (który jest również projektem tworzącym wielojęzyczne banki drzew zależności). Oznacza to przypisanie głowy (lub wielu głów w niektórych formalizmach, takich jak rozszerzone zależności, np. w przypadku koordynacji ) do każdego tokena i odpowiedniej relacji zależności dla każdej krawędzi, ostatecznie konstruując drzewo lub wykres dla całego zdania.

Istnieją zasadniczo trzy nowoczesne paradygmaty modelowania analizowania zależności: oparte na przejściach, oparte na gramatyce i oparte na wykresach.

Oparte na przejściach

Wiele nowoczesnych podejść do analizowania drzewa zależności wykorzystuje analizę opartą na przejściach (podstawowa forma tego jest czasami nazywana arc-standard ), jak sformułował Joakim Nivre w 2003 r., Która rozciąga się na parsowanie z redukcją przesunięć poprzez utrzymywanie działającego stosu tokenów i decydowanie z trzech operacji dla następnego napotkanego żetonu:

LeftArc (obecny token jest dzieckiem wierzchołka stosu, nie jest dodawany do stosu)
RightArc (obecny token jest rodzicem wierzchołka stosu, zastępuje górę)
Shift (dodaj bieżący token do stosu)

Algorytm można sformułować jako porównanie dwóch górnych żetonów stosu (po dodaniu kolejnego żetonu do stosu) lub górnego żetonu na stosie i następnego żetonu w zdaniu.

Dane treningowe dla takiego algorytmu są tworzone za pomocą wyroczni , która konstruuje sekwencję przejść z drzewek złota, które są następnie podawane do klasyfikatora. Klasyfikator uczy się, która z trzech operacji jest optymalna, biorąc pod uwagę bieżący stan stosu, bufora i bieżącego tokena. Nowoczesne metody wykorzystują klasyfikator neuronowy, który jest wyszkolony w zakresie osadzania słów , poczynając od pracy Danqi Chen i Christophera Manninga w 2014 r. W przeszłości powszechne były również klasyfikatory oparte na cechach, z cechami wybieranymi ze znaczników części mowy, pozycji zdania , informacje morfologiczne itp.

Jest to $jest$ algorytm, więc nie gwarantuje najlepszej możliwej analizy ani nawet koniecznie poprawnej analizy, Niekoniecznie jest również tak, że określone drzewo będzie miało tylko jedną sekwencję prawidłowych przejść, które mogą do niego dotrzeć, więc dynamiczna wyrocznia (która może pozwalać na wielokrotny wybór operacji) zwiększy wydajność.

Modyfikacją tego jest parsowanie arc-eager , które dodaje kolejną operację: Zmniejsz (usuń górny żeton ze stosu). W praktyce skutkuje to wcześniejszym powstawaniem łuku.

Wszystkie one obsługują jak dotąd tylko drzewa rzutowe , w których krawędzie nie przecinają się, biorąc pod uwagę kolejność tokenów ze zdania. W przypadku drzew nierzutowych Nivre w 2009 r. zmodyfikował parsowanie oparte na przejściach w standardzie łuku, aby dodać operację Zamień (zamień dwa górne tokeny na stosie, zakładając formułę, w której następny token jest zawsze dodawany do stosu jako pierwszy). Zwiększa to czas działania do $, ale praktycznie$ prawie liniowego

Oparte na gramatyce

Podejście do programowania dynamicznego oparte na wykresach do projekcyjnej analizy zależności zostało zaproponowane przez Michaela Collinsa w 1996 r. I dodatkowo zoptymalizowane przez Jasona Eisnera w tym samym roku. Jest to adaptacja CKY (wcześniej wspomnianego do analizowania okręgów wyborczych) do zależności nagłówkowych, z korzyścią polegającą na tym, że jedyną zmianą w stosunku do analizowania okręgów wyborczych jest to, że każdy składnik jest kierowany przez jeden z jego węzłów potomnych. W ten sposób można po prostu określić, które dziecko zapewnia nagłówek dla każdej reguły okręgu wyborczego w gramatyce (np. NP jest na czele swojego dziecka N), aby przejść od analizy CKY okręgu do analizy zależności CKY.

Oryginalna adaptacja McDonalda miała czas działania , a optymalizacje $\ Displaystyle O (n$ dynamicznego Eisnera skróciły czas działania do $3$ . Eisner zasugerował w swoim artykule trzy różne metody punktacji do obliczania prawdopodobieństw rozpiętości.

Oparte na wykresach

Wyczerpujące wyszukiwanie możliwych $^$ w drzewie zależności, z cofaniem się w przypadku utworzenia źle sformułowanego drzewa, daje linię bazową ${3})}$ $\ Displaystyle O (n$ środowisko wykonawcze do analizowania zależności na podstawie wykresów. Podejście to zostało po raz pierwszy formalnie opisane przez Michaela A. Covingtona w 2001 roku, ale twierdził, że jest to „algorytm znany w jakiejś formie od lat 60. XX wieku”.

Problem parsowania można również modelować jako znalezienie arborescencji o maksymalnym prawdopodobieństwie na wykresie wszystkich możliwych krawędzi zależności, a następnie wybranie etykiet zależności dla znalezionych krawędzi w drzewie. Mając to na uwadze, możemy zastosować rozszerzenie algorytmu Chu-Liu/Edmondsa o punktację krawędzi i punktację etykiet. Algorytm ten został po raz pierwszy opisany przez Ryana McDonalda, Fernando Pereirę , Kirila Ribarova i Jana Hajiča. w 2005 r. Może obsługiwać drzewa nierzutowe, w przeciwieństwie do parsera opartego na standardach łukowych i CKY. Tak jak poprzednio, osoby oceniające mogą być neuronowe (wyszkolone w zakresie osadzania słów) lub oparte na funkcjach. Działa $z$ _

Ocena

Wydajność analizatorów składniowych jest mierzona przy użyciu standardowych metryk oceny. Zarówno podejście do analizowania okręgów wyborczych, jak i zależności można ocenić pod kątem stosunku dokładnych dopasowań (procent zdań, które zostały doskonale przeanalizowane), a precyzja , przypomnienie i wynik F1 obliczone na podstawie poprawnych przypisań okręgów wyborczych lub zależności w analizie składniowej w stosunku do tej liczby w analizie referencyjnej i/lub hipotezy. Te ostatnie są również znane jako metryki PARSEVAL.

Analizę zależności można również ocenić za pomocą oceny załączników . Wynik przywiązania bez etykiety (UAS) to odsetek tokenów z prawidłowo przypisanymi główkami, podczas gdy wynik przywiązania z etykietą (LAS) to odsetek tokenów z prawidłowo przypisanymi główkami i etykietami relacji zależności.

Konwersja między parsami

Biorąc pod uwagę, że wiele prac nad angielską analizą składniową zależało od Penn Treebank , który wykorzystywał formalizm okręgów wyborczych, wiele prac nad analizą zależności opracowało sposoby deterministycznej konwersji formalizmu Penn na składnię zależności, aby użyć jej jako danych treningowych. Jednym z głównych algorytmów konwersji był Penn2Malt, który ponownie zaimplementował poprzednie prace nad problemem.

Praca w kierunku konwersji zależności na okręg wyborczy korzysta z szybszego czasu działania algorytmów analizowania zależności. Jednym podejściem jest użycie ograniczonego parsowania CKY $wykonywania$ , które w oczywisty sposób naruszają strukturę analizy zależności, a tym samym . Innym podejściem jest wytrenowanie klasyfikatora, aby znalazł uporządkowanie dla wszystkich elementów zależnych każdego tokena, co skutkuje strukturą izomorficzną z parsowaniem elektoratu.

Dalsza lektura

Jurajski, Dan; Martin, James H. (2021). Przetwarzanie mowy i języka (3 wyd.) . Źródło 22 października 2021 r .

Analiza zależności

Kübler, Sandra; McDonald, Ryan; Nivre, Joakim (2009). Graeme Hirst (red.). Analiza zależności . Wykłady syntetyczne na temat technologii języka ludzkiego . Morgana i Claypoola.