Analiza jzyka naturalnego

Artykuy o tej samej nazwie mona znale w artykule Analizator .

W jzyku komputerowym lub NLP The parsowanie ( skadniowym parsowania ) odnosi si do zautomatyzowanego procesu analizy acucha sów - reprezentowanie fraz - w celu uzyskania zaleno pomidzy wspóistniejc poprzez te sowa z drzewa skadni . Rozpoczynajc od zwykego tekstu, ten ostatni musia zosta wczeniej podzielony na jednostki leksykalne ( tokenizacja ). Zazwyczaj analiza leksykalna ( lematyzacja , analiza morfosyntaktyczna ...) jest wykonywana przed waciw analiz skadni, w celu zidentyfikowania jednostek leksykalnych i ich waciwoci. Wynik analizy jest zwykle uywany jako podstawa w analizie semantycznej , konstruowaniu reprezentacji znaczenia tekstu lub bezporednio w zastosowaniach, takich jak korekta gramatyczna .

W przypadku systemu odpowiadania na pytania lub wyszukiwania informacji trudno byoby na przykad poprawnie odpowiedzie na pytanie jakie prace pisali francuskojzyczni autorzy przed 1900 rokiem. Bez rozpoznawania tematu utwory , poniewa w szczególnoci naley rozumie, e uytkownik chce mie list dzie, a nie list autorów.

Proces analizy moe opiera si na gramatyce formalnej i / lub wykorzystywa metody statystyczne .

Historyczny

Parsowanie siga pocztków bada NLP, poniewa jeden z pierwszych algorytmów analizy zosta wprowadzony przez Victora Yngve w 1955 roku, jeszcze przed opracowaniem teorii jzyka formalnego przez Noama Chomsky'ego w 1956 roku. Dlatego tworzone parsery bd oparte na gramatykach formalnych, szczególnie tych wywoywanych poza kontekstem lub typu 2 . Midzy innymi, John Cocke wynalaz w 1960 roku algorytm programowania dynamicznego, który nastpnie zosta sformalizowany przez T. Kasami (1965) i DH Younger (1967): synny algorytm CKY , analizujcy sekwencj w czasie szeciennym z wykorzystaniem gramatyki Form normalnych autorstwa Chomsky'ego . Ta ostatnia jest typu mieszanego, to znaczy czcego strategie oddolne i odgórne, indywidualnie mniej efektywne.

Równoczenie w latach 60. pojawio si kilka innych formalizmów powiconych analizie skadniowej, w tym gramatyki zalenoci inspirowane Lucienem Tesnièreem (1959) i sformalizowane przede wszystkim przez Davida Haysa (1960). Wkrótce po N. Chomsky, John Backus (1959) i Peter Naur (1960) niezalenie wymylili gramatyk bezkontekstow w swoim opisie jzyka ALGOL , dajc pocztek synnej formie Backus-Naur . W 1968 roku Jay Earley wynalaz pierwszy algorytm analizy w czasie szeciennym dla wszystkich gramatyk bezkontekstowych (niekoniecznie w normalnej formie). W tym samym czasie R. Kaplan i M. Kay uogólnili algorytm CKY na wszystkie gramatyki bezkontekstowe, aby uczyni go parserem wykresów , uywajc grafu. Wród algorytmów podobnych do dwóch poprzednich moemy równie przytoczy parser lewego rogu , w odniesieniu do pierwszego symbolu prawej czci reguy produkcyjnej.

W latach siedemdziesitych i osiemdziesitych XX wieku opracowano wiele innych formalizmów, w tym sieci rozszerzonych przej (ATN) i gramatyki unifikacyjne (gramatyki oparte na ograniczeniach ). Przedstawienie w zalenociach tego ostatniego pierwotnie zaproponowa H. Maruyama. W latach 90. rozwój skupia si gównie na metodach statystycznych, w tym znaczcych pracach nad probabilistycznymi gramatykami bezkontekstowymi (PCFG) - jednym z najbardziej wpywowych modeli analizy statystycznej, która opiera si na gramatyce formalnej - w tym gównymi problemami s ignorancja informacji semantycznej i hipoteza niezalenoci strukturalnego przywizania fraz. Niektóre nowsze podejcia umoliwiy popraw saboci PCFG, midzy innymi poprzez leksykalizacj gramatyki lub uycie bardziej precyzyjnego zestawu symboli nieterminalnych. Po stronie reprezentacji w zalenociach pierwszy wpywajcy algorytm stochastyczny zosta zaproponowany przez Jasona Eisnera.

W przypadku metod, które nie wymagaj interwencji gramatyki, modele s bezporednio indukowane z danych opatrzonych adnotacjami ( korpus ), co uatwia przenoszenie systemów do nowych jzyków lub dziedzin. Chocia ta ostatnia moliwo jest obecnie wykorzystywana gównie, metody oparte na gramatykach s nadal stosowane, gdy nie ma wystarczajcej iloci danych z adnotacjami, niezbdnych do dziaania metod nadzorowanych. Na marginesie naley zauway, e gramatyk mona bardzo dobrze wyodrbni z danych jzykowych; metody oparte na gramatyce ( analiza oparta na gramatyce ) i metody oparte na danych ( analiza oparta na danych ) nie wykluczaj si wzajemnie. Proponowana kategoryzacja statystycznych metod analizy jest szeroko stosowana w dziedzinie NLP.

Trudnoci

Parsowanie jest zadaniem nietrywialnym, gównie ze wzgldu na nieodczn niejednoznaczno jzyka i jego rónorodno. O stwierdzeniu mówi si, e jest niejednoznaczne, jeli mona z nim skojarzy kilka struktur jzykowych.

Oto kilka przykadów niejednoznacznoci strukturalnych :

John zobaczy mczyzn na wzgórzu przez teleskop

W tym zdaniu przywizanie przyimkowego wyraenia jest niejednoznaczne i nie wiadomo, czy John uy teleskopu, aby zobaczy czowieka, czy te John zobaczy samego czowieka za pomoc teleskopu.

- Do kogo obiecae napisa "

Poprzednie pytanie mona sparafrazowa na dwa sposoby: Do kogo obiecae napisa. Lub Do kogo obiecae napisa "; nie wiadomo, czy dana osoba napisze do kogo, czy te obiecaa komu napisa (co).

Zwizek z analiz jzyka formalnego

Nawet jeli cel analizy deterministycznego jzyka formalnego (np. Jzyka programowania ) jest identyczny z celem analizy jzyka naturalnego, w drugim przypadku zadanie to jest znacznie trudniejsze.

Po pierwsze, zdolno generacyjna gramatyki - jej moc - jest znacznie mniejsza w przypadku jzyków komputerowych, poniewa musz one by cile jednoznaczne i szybko analizowalne (std gramatyka jest ograniczona). Dla porównania, gramatyka przeznaczona dla jzyka naturalnego musi na przykad umoliwia wyraanie zalenoci midzy wyrazami, które s daleko od siebie; jest zatem bardziej zoony.

Po drugie, poniewa jzyk naturalny cierpi z powodu niejednoznacznoci strukturalnej, na kadym etapie analizy moe mie zastosowanie kilka regu gramatycznych. Tak wic zdanie takie jak Jan widzia czowieka [na wzgórzu] [z teleskopem] [w towarzystwie jego córki] [] spowoduje, e liczba jego moliwych analiz wzronie wykadniczo wraz z liczb dodanych skadników. . Nawiasem mówic, jest to jeden z powodów, dla których opracowano metody statystyczne.

Ostatnia zauwaalna rónica dotyczy wanoci sekwencji wejciowej: jzyk programowania ma skoczon liczb prawidowych konstrukcji, podczas gdy w przypadku jzyka naturalnego jest on nieograniczony . Dlatego w przypadku NLP istnieje niemono wykonania analizy, bd, który niekoniecznie wynika z nieodpowiedniej gramatyki, ale prawdopodobnie z bdu gramatycznego, literówki, nieznanego sowa itp.

Oprócz tych karykaturalnych podobiestw istnieje wiele innych, takich jak cise rozgraniczenie zda (zda, bloków) i sów w przypadku jzyków formalnych z dobrze zdefiniowanymi znakami.

Metody klasyczne

Metody czysto gramatyczne

Wikszo pierwszych systemów analizowania opiera si wycznie na swobodnej gramatyce kontekstu ( gramatyka bezkontekstowa ) w celu wygenerowania prawidowych struktur skadniowych, chocia ten rodzaj gramatyki nie jest wystarczajcy do wygenerowania jzyka naturalnego jako caoci. Razem konieczne jest posiadanie algorytmu, który dyktuje, w jaki sposób te struktury bd wydajnie wytwarzane. W tym kontekcie szeroko stosowany jest algorytm programowania dynamicznego CKY , w którym podproblemy - utrzymywane w tablicy - s reprezentowane przez czciowe drzewa skadniowe zakorzenione w frazach zdania wejciowego. Dziki niezalenoci od kontekstu gramatyki moliwe jest ponowne wykorzystanie podstruktury w kolejnych, wymagajcych tego derywacji, umoliwiajc programowanie dynamiczne. Algorytmy konkurujce z CKY to analiza Earleya i wykresu .

Metody wspomagane statystykami

Problem z algorytmami asymilowanymi do CKY polega na ich niezdolnoci do rozwizywania niejednoznacznoci strukturalnych (patrz rozdzia   trudnoci  ), chocia mona je wykry. Aby przezwyciy ten brak, konieczne jest dodanie do modelu komponentu statystycznego; jeli kadej regule towarzyszy prawdopodobiestwo , w przypadku niejasnoci wystarczy wybra t o najwikszym prawdopodobiestwie. Jako taki, najczciej uywanym formalizmem jest probabilistyczna gramatyka bezkontekstowa (PCFG). Istnieje probabilistyczna wersja algorytmu CKY, opisana przede wszystkim przez H. Neya. Dokadne wnioskowanie wymaga czasu w , gdzie jest liczba regu gramatycznych. ${\ Displaystyle {\ mathcal {O}} (n ^ {3} \ cdot | R |)}$${\ displaystyle | R |}$

Jednak model PCFG ma stosunkowo ograniczone moliwoci osigania doskonaych wyników, poniewa narzuca silne zaoenia niezalenoci. Gównym problemem jest to, e prawdopodobiestwo konkretnej reguy jest niezalene od kontekstu, w którym zostaa stworzona; na przykad prawdopodobiestwo, e fraza rzeczownikowa zostanie przeduona do zaimka (reguy ) pozostaje stae, e fraza ta znajduje si na pozycji podmiotu lub dopenienia, podczas gdy pierwsza moliwo jest znacznie czstsza w niektórych jzykach. Z drugiej strony, jeli dwie róne struktury uywaj dokadnie tych samych regu, uzyskaj to samo prawdopodobiestwo; jednak dla tego samego zdania (a wic tych samych regu) czsto istnieje struktura, która jest preferowana wzgldem innej (gdy istnieje kilka moliwoci), czego nie przekazuje formalizm PCFG. ${\ displaystyle {\ text {NP}} \ longrightarrow {\ text {Pron}}}$

Zaproponowano kilka modeli w celu rozwizania wyej wymienionych problemów. Jednym z najbardziej wpywowych jest ten autorstwa Michaela Collinsa , zwany LPCFG lub czasem kierowany gow , polegajcy na leksykalizacji gramatyki poprzez wybór elementu dominujcego ( reguy gównej ) dla kadej reguy gramatyki. W ten sposób kady wze macierzysty drzewa skadni jest sparametryzowany sowem w zdaniu; na przykad regua dla PCFG moe sta si, jeli pies jest czci zdania, które ma by analizowane. Zgodnie z nadrzdn przesank tej reguy rodzic dziedziczy sowo pies. ${\ Displaystyle [{\ tekst {NP}} \ longrightarrow {\ tekst {DT}} \ quad {\ tekst {NN}}]}$${\ Displaystyle [{\ tekst {NP (pies)}} \ longrightarrow {\ tekst {DT ()}} \ quad \ mathbf {NN} {\ tekst {(pies)}}]}$${\ displaystyle {\ text {NN}}}$${\ displaystyle {\ text {NP}}}$

Adnotacja nieterminalnych wzów PCFG, znana jako adnotacja nadrzdna , równie bya bardzo skuteczna w analizie komponentów, poniewa dokadno systemów wykorzystujcych t technik jest podobna do tych opartych na LPCFG, ale jest mniej zoona. Taka adnotacja moe by na przykad, jeli tworzy przyimek. ${\ Displaystyle [{\ tekst {NP}} ^ {\ tekst {PP}} \ longrightarrow {\ tekst {DT}} \ quad {\ tekst {NN}}]}$${\ displaystyle {\ text {NP}}}$

Innym rozwizaniem braku strukturalnej wraliwoci PCFG jest analiza zorientowana na dane (DOP) opracowana przez Remko Scha i Rens Bod. Zasad jest analiza zda poprzez czenie fragmentów analiz zda, których struktura jest znana, np. Pochodzcych z korpusu.

Istniej dwie klasy modeli probabilistycznych: te znane jako generatywne , takie jak LPCFG, oraz te znane jako modele dyskryminujce (  wicej szczegóów znajduje si w sekcji   modele analizy statystycznej ).

metody statystyczne

Korzyci ze statystyk

W klasycznym podejciu analiza zdania moe spowodowa powstanie milionów moliwych drzew skadniowych ze wzgldu na duy rozmiar gramatyki i niemono wybrania tego, które najlepiej odzwierciedla struktur danego zdania. Jeli do tej gramatyki zostan dodane ograniczenia w celu ograniczenia liczby moliwych analiz, cz analizowanych zda moe utraci odpowiedni struktur. Podejcie statystyczne ma t zalet, e toleruje miliony analiz, a jednoczenie daje moliwo wybrania najlepszej w rozsdnym czasie; w zwizku z tym czsto konieczne jest zmniejszenie przestrzeni poszukiwa w trakcie caego procesu analizy, eliminujc najwczeniej mao prawdopodobne analizy czciowe.

W dzisiejszych czasach gramatyki (same w sobie) s ju prawie nie uywane, a podejcia w dziedzinie NLP opieraj si gównie na technikach uczenia maszynowego .

Co wicej, formalizacja zjawisk jzykowych jest pracochonna, a techniki statystyczne przyniosy ogromn korzy w postaci wydobywania wiedzy jzykowej bezporednio z (rzeczywistych) próbek danych. A jeli budowa korpusu ( banku drzewa ) jest bardziej mudna ni budowa gramatyki, ta pierwsza ma t zalet, e mona j ponownie wykorzysta w innych systemach (w tym w analizatorach morfosyntaktycznych), co czciowo tumaczy brak zainteresowania gramatykami. Ponadto dane niejawnie zawieraj statystyki, a ocena systemu jest atwa. Zwró uwag, e gramatyk mona bardzo dobrze wyodrbni z danych jzykowych; Metody oparte na gramatyce ( analiza oparta na gramatyce ) i metody oparte na danych ( analiza oparta na danych ) - dzi w wikszoci - nie wykluczaj si zatem wzajemnie.

Chocia do ujednoznacznienia - w razie potrzeby - procesu analizy stosuje si techniki statystyczne, bardzo rzadko mona zbada ca przestrze poszukiwa i konieczne jest jej ograniczenie ze wzgldu na efektywno.

Modele analizy statystycznej

Moemy przedstawi parser za pomoc funkcji , gdzie jest zbiorem moliwych danych wejciowych, wiedzc, e reprezentuje sekwencj wejciow , i jest zbiorem dopuszczalnych reprezentacji skadniowych. Naley zauway, e charakter reprezentacji analizy jest specyficzny dla zastosowanej teorii, podobnie jak jej kryterium dopuszczalnoci. ${\ displaystyle f: {\ mathcal {X}} \ do {\ mathcal {Y}}}$${\ displaystyle {\ mathcal {X}}}$${\ displaystyle {\ boldsymbol {x}} \ in {\ mathcal {X}}}$${\ Displaystyle {\ boldsymbol {x}} = (t_ {0}, t_ {1}, \ kropki, t_ {n})}$${\ displaystyle {\ mathcal {Y}}}$${\ displaystyle {\ boldsymbol {y}} \ in {\ mathcal {y}}}$

Koncepcyjnie model analizy mona podzieli na dwie czci:

1. generatywnej komponent , który pasuje do wpisu do zbioru analiz kandydujcych , w zwizku ;${\ displaystyle \ mathrm {GEN}}$${\ displaystyle {\ boldsymbol {x}}}$${\ Displaystyle \ {{\ boldsymbol {y}} _ {1}, {\ boldsymbol {y}} _ {2}, \ kropki, {\ boldsymbol {y}} _ {| {\ mathcal {Y}} | } \}}$${\ Displaystyle \ mathrm {GEN} ({\ boldsymbol {x}}) \ subseteq {\ mathcal {Y}}, {\ boldsymbol {x}} \ in {\ mathcal {X}}}$
2. komponent oceniajcy , klasyfikujcy analizy kandydatów zgodnie z przypisan punktacj liczbow .${\ displaystyle \ mathrm {EVAL}}$${\ Displaystyle \ mathrm {EVAL} ({\ boldsymbol {r}}) \ w \ mathbb {R}, {\ boldsymbol {r}} \ w \ mathrm {GEN} ({\ boldsymbol {x}})}$

Oba skadniki maj zwykle parametrów, których wartoci zostan oszacowane statystycznie, poczwszy od analizy danych reprezentatywnych, zwany zestaw szkole , w celu zapewnienia dobrego estymatora z korespondentem. Jest to modelowy etap uczenia si , który moe by nadzorowany lub nienadzorowany (czasami czciowo nadzorowany ); uczenie nadzorowane wymaga, aby dane zawieray prawidow analiz. Caa trudno tego kroku polega zatem na poprawnym wykorzystaniu czciowego dowodu - zawartego w danych - w celu stworzenia rozkadu prawdopodobiestwa, który jak najbliej odzwierciedla rzeczywisto. Z funkcji wywnioskowanej w momencie uczenia si modelu drugi krok polega na sprawnym uporzdkowaniu analiz kandydatów dla danego (niepublikowanego) zdania wejciowego: na tym polega problem wnioskowania . Te ostatnie mog by dokadne lub przyblione, w zalenoci od gwarancji, jakie daje zastosowany algorytm. ${\ displaystyle f ({\ boldsymbol {x}} _ {i})}$${\ displaystyle {\ boldsymbol {y}} _ {i}}$${\ displaystyle f}$

Czsto konieczne jest znalezienie sprawiedliwego kompromisu midzy zoonoci modelu a brakiem dokadnoci generowanych rozwiza. Na marginesie zwró uwag na fakt, e zbiór jest prawdopodobnie bardzo duy, a kady z nich jest przedmiotem o bogatej strukturze wewntrznej; to odkrycie kontrastuje z prostym problemem klasyfikacyjnym, który byby znacznie mniejszy. Systemy wykorzystujce algorytm uczenia nadzorowanego s znacznie bardziej powszechne, poniewa s znacznie bardziej wydajne. ${\ Displaystyle \ mathrm {GEN} ({\ boldsymbol {x}})}$${\ Displaystyle {\ boldsymbol {y}} _ {i} \ w \ mathrm {GEN} ({\ boldsymbol {x}})}$${\ Displaystyle \ mathrm {GEN} ({\ boldsymbol {x}})}$

Ponadto w uczeniu maszynowym przeciwstawiaj si dwie due klasy modeli, niekoniecznie powizane z wymienionymi wczeniej komponentami generatywnymi i ewaluacyjnymi: pierwsza moliwo, zwana generatywn , polega na postrzeganiu procesu analizy jako systemu przepisywania probabilistycznego, gdzie celem polega na wytworzeniu jednej (lub wicej) konstrukcji zgodnie z danym wejciem; na kadym etapie naley wybiera najlepsz (-e) alternatyw (-y) w celu uzyskania najbardziej prawdopodobnej struktury na koniec analizy. Tutaj celem jest maksymalizacja wspólnego prawdopodobiestwo , cokolwiek i , poprzez modelowanie i , a nastpnie przez ponowne czenie ich z reguy Bayesa (przypadek PCFGs). Druga moliwo, zwana dyskryminacj , polega na postrzeganiu gramatyki jako zbioru ogranicze dotyczcych prawidowych struktur, a sekwencji wejciowej jako ograniczenia pozycji sów; analiza musi nastpnie rozwiza te ograniczenia, a nastpnie wybra najbardziej prawdopodobn struktur skadniow sporód tych, które najlepiej speniaj ograniczenia. W tym przypadku próbujemy modelowa prawdopodobiestwo warunkowe bezporednio na podstawie danych. Ponownie, te dwa podejcia mona czy sekwencyjnie ( ponowne klasyfikowanie ). ${\ Displaystyle P ({\ boldsymbol {x}}, {\ boldsymbol {y}})}$${\ displaystyle {\ boldsymbol {x}} \ in {\ mathcal {X}}}$${\ displaystyle {\ boldsymbol {y}} \ in {\ mathcal {y}}}$${\ Displaystyle P ({\ boldsymbol {x}} | {\ boldsymbol {y}})}$${\ Displaystyle P ({\ boldsymbol {y}})}$${\ Displaystyle P ({\ boldsymbol {y}} | {\ boldsymbol {x}})}$

Modele generatywne

Wyprowadzenie struktury syntaktycznej jest modelowane przez proces stochastyczny, w którym kady krok zaley od wydarze, które miay miejsce w przeszoci (historyczne). Ogólna forma takich modeli, o której pocztkowo wspomnia G. Leech, jest nastpujca:

$${\ Displaystyle {\ boldsymbol {y}} = {\ duy \ langle} d_ {1}, d_ {2}, \ kropki, d_ {m} {\ duy \ rangle}}$$

$${\ Displaystyle P {\ duy (} {\ boldsymbol {y}} {\ duy)} = \ prod _ {i = 1} ^ {m} P {\ duy (} d_ {i} | \ Phi (d_ { 1}, \ dots, d_ {i-1}) {\ big)}}$$

gdzie funkcja okrela, które wydarzenia historyczne s brane pod uwag. Chocia jest to czsto zdarza si, skadnik generatywne jest ukadem wyprowadze, która nie zawsze ograniczane poprzez formalne gramatyki (model Parser IDP przykad). Oceny dokonuje si zgodnie z prawdopodobiestwem cznym, rozoonym na prawdopodobiestwa warunkowe. Naley zauway, e jest to zredukowane do, poniewa dla danej struktury prawdopodobiestwo jest równe si jest jedynym zdaniem odpowiadajcym tej strukturze; dlatego te, jeli si odrodzi , lub we wszystkich innych przypadkach. ${\ displaystyle \ Phi}$${\ Displaystyle \ mathrm {GEN} ({\ boldsymbol {x}})}$${\ Displaystyle \ mathrm {EVAL} ({\ boldsymbol {y}})}$${\ Displaystyle P ({\ boldsymbol {x}}, {\ boldsymbol {y}})}$${\ Displaystyle P ({\ boldsymbol {y}})}$${\ Displaystyle P ({\ boldsymbol {x}} | {\ boldsymbol {y}})}$${\ displaystyle 1}$${\ displaystyle {\ boldsymbol {x}}}$${\ Displaystyle P ({\ boldsymbol {x}}, {\ boldsymbol {y}}) = P ({\ boldsymbol {y}})}$${\ displaystyle {\ boldsymbol {y}}}$${\ displaystyle {\ boldsymbol {x}}}$${\ Displaystyle P ({\ boldsymbol {x}}, {\ boldsymbol {y}}) = 0}$

Modele generatywne narzucaj sztywne zaoenia dotyczce niezalenoci, co wpywa na ujednoznacznienie (zwykle PCFG). Jednak adaptacja tych zaoe daje bardziej zoone modele i dokadne wnioskowanie nie jest ju moliwe (patrz take sekcja   metody wspomagane przez statystyki  ). Zasadniczo ten rodzaj modelu musi przewidywa nastpne sowo w miar postpu analizy, co wymaga globalnej normalizacji w caym sownictwie i czsto wikszego klastra (jeli istnieje), aby mona byo wypróbowa du liczb struktur na cz zdania zawierajca przewidywane sowo. Ponadto uczenie modeli generatywnych dy przez wikszo czasu do maksymalizacji wspólnego prawdopodobiestwa nakadów i wyników zbioru uczcego; jednak celem analizy jest maksymalizacja precyzji modelu dla zda niepublikowanych. Z tych powodów coraz czciej stosuje si modele dyskryminacyjne.

Lokalnie dyskryminujce modele

Celem tych modeli jest maksymalizacja prawdopodobiestwa decyzji lokalnych , majc nadziej na osignicie najlepszego globalnego rozwizania dziki sukcesji optymalnych (lokalnych) decyzji, takich jak modele generatywne oparte na historii:

$${\ Displaystyle {\ boldsymbol {y}} = {\ duy \ langle} d_ {1}, d_ {2}, \ kropki, d_ {m} {\ duy \ rangle}}$$

$${\ Displaystyle P {\ duy (} {\ boldsymbol {y}} | {\ boldsymbol {x}} {\ duy)} = \ prod _ {i = 1} ^ {m} P {\ duy (} d_ { i} | \ Phi (d_ {1}, \ dots, d_ {i-1}, {\ boldsymbol {x}}) {\ big)}}$$

Tutaj funkcja reprezentuje dowolne waciwoci / cechy w zalenoci od historii podjtych decyzji

i danych wejciowych  ; innymi sowy, definiujemy klas równowanoci dla dowolnej kombinacji historii i wpisu. Stosujc metody prognozowania danych wejciowych, niektórzy analizatorzy podchodz do analizy deterministycznej (predykcyjnej). W przypadku tego typu modelu komponent generatywny skada si z procesu przyrostowego (np. Automatu), natomiast komponent oceniajcy musi by w stanie przypisa wynik danej decyzji lokalnej i poczy te wyniki w oceny globalne, oceniajc pen sekwencj przej. . ${\ displaystyle \ Phi}$${\ displaystyle \ langle d_ {1}, \ kropki, d_ {i-1} \ rangle}$${\ displaystyle {\ boldsymbol {x}}}$${\ Displaystyle \ mathrm {GEN} ({\ boldsymbol {x}})}$${\ Displaystyle \ mathrm {EVAL} ({\ boldsymbol {y}})}$

Czasami ten typ modelu jest nazywany generatywnym, poniewa obejmuje zaoenia niezalenoci, takie jak modele prawdziwie generatywne - modelujce wspólne prawdopodobiestwo - ale na lokalnych decyzjach , a nie na decyzjach globalnych. Podejcie lokalne ma t zalet, e faworyzuje rozwaanie cech charakterystycznych przydatnych do ujednoznaczniania, gównego problemu prawdziwych modeli generatywnych. Ta kategoria modeli umoliwia uzyskanie analizatorów znacznie szybciej ni te oparte na modelach generatywnych (np. Rzdu 35x).

Modele dyskryminacyjne

Ta klasa modeli zazwyczaj definiuje funkcj oceny jako iloczyn wektora cech (cech) i wektora wag : ${\ Displaystyle \ mathbf {f} ({\ boldsymbol {x}}, {\ boldsymbol {y}}) = \ langle f_ {1} ({\ boldsymbol {x}}, {\ boldsymbol {y}}), \ dots, f_ {m.} ({\ boldsymbol {x}}, {\ boldsymbol {y}}) \ rangle \ in \ mathbb {R} ^ {m}}$${\ displaystyle {\ boldsymbol {w}} = \ langle w_ {1}, \ kropki, w_ {m} \ rangle \ in \ mathbb {R} ^ {m}}$

$${\ Displaystyle S ({\ boldsymbol {x}}, {\ boldsymbol {r}}) \; = \; \ mathbf {f} ({\ boldsymbol {x}}, {\ boldsymbol {y}}) \ cdot {\ boldsymbol {w}} \; = \; \ sum _ {k = 1} ^ {m} f_ {k} ({\ boldsymbol {x}}, {\ boldsymbol {y}}) \ cdot w_ {k }}$$

gdzie kada reprezentuje cech i , a kada okrela ilociowo znaczenie cechy dla optymalnej analizy. Jeli ta waga jest ujemna, charakterystyka suy do analizy, podczas gdy w przeciwnym razie cecha pozytywnie wpywa na optymaln analiz. Charakter cech

nie jest ograniczony; jedynym ograniczeniem jest moliwo ich kodowania w postaci cyfrowej. Mona na przykad wykorzysta punktacj dostarczon przez inny analizator jako cech lub uwzgldni obecno / brak podstruktury. ${\ displaystyle f_ {k} ({\ boldsymbol {x}}, {\ boldsymbol {y}}): {\ mathcal {X}} \ razy {\ mathcal {Y}} \ do \ mathbb {R}}$${\ displaystyle {\ boldsymbol {x}}}$${\ displaystyle {\ boldsymbol {y}}}$${\ displaystyle w_ {k} \ in \ mathbb {R}}$${\ displaystyle f_ {k}}$

Dlatego prawdziwie rozróniajcy model definiuje unikalny wynik ogólnej struktury analizy. Zalet jest moliwo obserwowania globalnych waciwoci struktur skadniowych oraz uwzgldniania (dodawania) nowych ogranicze bez zmiany wyprowadzenia modelu. W przypadku tej klasy komponent generatywny jest do zmienny w rónych systemach, podczas gdy komponent oceny jest ustalany przez liniow kombinacj waonych charakterystyk, nie ograniczonych przez aden proces, i których wagi s ustalane przez rozróniajcy model uczenia si. ${\ Displaystyle \ mathrm {GEN} ({\ boldsymbol {x}})}$${\ Displaystyle \ mathrm {EVAL} ({\ boldsymbol {y}})}$

Wad tego typu modelu jest konieczno ponownej analizy zestawu uczcego w kadej iteracji, co w naturalny sposób wymaga duej iloci zasobów. Niektóre podejcia, znane jako reranking , byy zadowolone z uywania tego rodzaju modelu tylko dla podzbioru samego siebie uzyskanego za pomoc modelu generatywnego. Jednak najlepsza analiza niekoniecznie znajduje si w tym drugim podzbiorze, co sprawia, e nie jest to idealna technika. Niemniej jednak problemy z wydajnoci s mniej widoczne w analizie zalenoci ni w przypadku skadników i s czsto uywane w pierwszym przypadku, gdy dokadne wnioskowanie jest moliwe nawet w okrelonych warunkach (patrz sekcja  

Metody oparte na wykresach  ). ${\ Displaystyle \ mathrm {GEN} ({\ boldsymbol {x}})}$

Paradygmaty analizy

Obecnie najpopularniejsz reprezentacj struktur skadniowych jest ta w zalenociach , ze wzgldu na dobry kompromis midzy wyrazistoci / wydajnoci oferowanych algorytmów, a wydajnoci uzyskiwan dla szerokiej gamy jzyków. W przypadku tej reprezentacji bardzo czsto stosowane s lokalnie dyskryminujce lub dyskryminujce modele probabilistyczne, w przeciwiestwie do reprezentacji w skadnikach , dla których modele generatywne s bardziej konkurencyjne. Warto jednak zauway, e niektóre najnowsze systemy ^{(na przykad )} , szczególnie wydajne, opieraj si na skadaniu modeli rónych typów (technika montau lub kombinacja systemów ).

Przykad struktury zalenoci dla zdania Mam brzowego psa.

Zdecydowan wikszo modeli analizy zalenoci statystycznych mona podzieli na dwie rodziny:

• Sposoby oparte na przejciach ( transformacji opartej ) oparte s na automat skoczony stan umoliwiajcy generowanie struktury skadniowej z danego zdaniu. W trakcie analizy wyuczony model powinien by w stanie przewidzie nastpne przejcie na podstawie historii przej, tak aby mona byo znale optymaln sekwencj przej prowadzc do jak najlepszej analizy zdania.
• Metody oparte na grafach definiuj wszechwiat analiz kandydatów dla danego zdania. Uczenie si sprowadza si do stworzenia modelu zdolnego do oceny tych analiz kandydatów jako caoci; proces analizy musi znale struktur, na przykad jej najwyszy wynik, odpowiadajc zdaniu wejciowemu.

W pierwszym przypadku strategia polega na znalezieniu najlepszego rozwizania lokalnego ( chciwo ), w drugim przypadku rozumowanie przybiera pozór wyczerpujcego poszukiwania . Ponadto pierwsza metoda jest czasami nazywana analizowaniem z redukcj przesunicia i nosi nazw algorytmu

analizowania uywanego w wielu implementacjach. Jest to bardzo popularna metoda ze wzgldu na doskona wydajno: zoono typowego algorytmu parsowania jest liniowa (w stosunku do liczby sów w zdaniu wejciowym). Jeli chodzi o drug metod, czasami znajduje si j pod nazw maksymalnego parsowania drzewa rozpinajcego ( MST ), co odpowiada nazwie algorytmu uywanego przez system, który wprowadzi t technik. W 2015 roku Jinho Choi i wsp. szczegóowo przeanalizowa wydajno dziesiciu analizatorów zalenoci konkurencyjnych i wykorzysta róne metryki.

Metody oparte na przejciach

Modele oparte na przejciach s lokalnie dyskryminujcymi modelami z dyskryminacyjnym uczeniem si, w tym sensie, e tylko oszacowanie kocowej analizy jest wyodrbniane z rozkadu probabilistycznego, na przykad przy uyciu powierzchni decyzyjnej. W przeciwiestwie do modeli warunkowych, w których caa gsto

prawdopodobiestwa warunkowego byaby zoptymalizowana. Przyjmujc funkcj oceny, która przypisuje punktacj moliwym przejciom wedug wzorca, reprezentowanego przez wektor , a take sposób oceny penej sekwencji przej, analiza sprowadza si do znalezienia sekwencji o najwyszym wyniku. W zwizku z tym wikszo systemów implementuje wyszukiwanie wizki. ${\ displaystyle {\ boldsymbol {y}}}$ ${\ Displaystyle P ({\ boldsymbol {y}} | {\ boldsymbol {x}})}$${\ Displaystyle S (\ Phi (\ mathbf {c}), d)}$${\ displaystyle d}$${\ Displaystyle \ Phi (\ mathbf {c})}$

Bardzo popularn metod analizy struktur zalenoci jest wykorzystanie klasyfikatora (trenowanego na korpusie) w celu przewidzenia nastpnej akcji wykonywanej przez deterministyczny algorytm analizy. Podejcie to jest czasami nazywane pseudo-deterministycznym w odniesieniu do deterministycznych algorytmów analizy stosowanych w gramatykach jednoznacznych ( jzyki formalne ). W omawianym przypadku przestrze poszukiwa jest z natury rzeczy ograniczona metod algorytmu, poniewa jedno wybrane dziaanie pociga za sob porzucenie wszystkich innych; z powodu tego zachannego podejcia przycinanie jest zatem bardzo agresywne. Ta sia jest równie wad, poniewa wczesny zy wybór moe negatywnie wpyn na ostateczn analiz.

System analizy oparty na klasyfikatorach skada si z trzech podstawowych skadników:

• algorytm analizy syntaktycznej, który ustala analiz przez kolejne czynnoci elementarne (poprzez system przej );
• model umoliwiajcy opisanie dowolnego stanu analizatora (konfiguracji ukadu przej) za pomoc wektora charakterystyk;
• klasyfikator, który przeksztaca stan w postaci wektora charakterystyk w dziaanie algorytmu analitycznego.

Podejcie to zostao zapocztkowane przez T. Kudo i Y. Matsumoto, którzy zaproponowali implementacj sprzon z klasyfikatorem typu maszyny wektorów nonych do analizy nieoznakowanych zalenoci jzyka japoskiego. Korzystajc z algorytmu Joakima Nivre'a, pomys zosta nastpnie iteracyjnie rozszerzony na zalenoci oznaczone jako szwedzki, nastpnie angielski, a nastpnie 19 jzyków, zanim zosta zoptymalizowany w celu utworzenia oprogramowania MaltParser . Pierwsze algorytmy ograniczaj si do struktur rzutowych , ale midzy innymi G. Attardi zaproponowa algorytm rozszerzony na podzbiór struktur nie projekcyjnych. W zwizku z tym J. Nivre oferuje wersj online zmiany kolejnoci swojego systemu przej, podczas gdy inne podejcia obejmuj dekompozycj na (pod) drzewa zalenoci planarnych i analiz kadego planu oddzielnie ( parsowanie mltiplanar ). Inne rozwizanie polega na przetwarzaniu danych przed / po (tzw. Pseudo-projektowaniu ).

Gówne problemy tego paradygmatu to wraliwo na bdy wyszukiwania i propagacja bdów w wyniku procesu przyrostowego jeden do jednego. Próbujc poprawi dokadno, zachowujc jednoczenie bardzo wydajn analiz, pojawio si kilka technik. Niektórzy zagodzili cile deterministyczny proces - utrzymywanie najlepszych analiz K ( wyszukiwanie wizki ) - czasami kojarzony ze szkoleniem jako ustrukturyzowan prognoz, podczas gdy inni porzucili czysto sekwencyjn analiz od lewej do prawej (

atwe pierwsze analizowanie ), poniewa wizka wyszukiwanie znacznie spowalnia parsowanie. W tym samym celu J. Nivre eksperymentowa z uyciem dynamicznej wyroczni - zarówno niedeterministycznej, jak i kompletnej (w przeciwiestwie do zwykych statycznych wyroczni) - w swoim systemie przej dnych uku . Jednak te wyrocznie powoduj wielk zoono, gdy s uywane z ogólnymi systemami (nie ograniczajc si do struktur projekcyjnych) i nie zawsze jest moliwe ich wyprowadzenie. Z tego powodu M. Straka i in. wprowadzili now klas wyroczni zwanych wyroczniami opartymi na wyszukiwaniu , która jest przyblieniem dynamicznych wyroczni.

W praktyce modele probabilistyczne s definiowane dla kadego dziaania algorytmu analizy, zgodnie z jego aktualnym kontekstem; jednak modele oparte na historii dziaa (lub przej) musz radzi sobie z nieograniczon iloci informacji, co uniemoliwia modelowanie probabilistyczne. Ten problem zazwyczaj rozwizuje si, ograniczajc histori do skoczonego zestawu cech. W tym miejscu najwiksza trudno polega na wyborze reprezentacji tej historii, czyli jej przegldzie, na podstawie którego mona waciwie oszacowa prawdopodobiestwo kolejnego dziaania. Poniewa prawdopodobiestwo to jest niezalene od jakichkolwiek informacji o historii, które nie s zawarte w jego przegldzie, na jako analizy mog mie duy wpyw wybrane cechy.

Badania w zakresie analizy statystycznej rozpoczto w poowie lat 90. i przez wiele lat skupiay si gównie na modelach liniowych. W takich modelach punktacja przypisana analizie jest obliczana na podstawie kombinacji cech strukturalnych lub cech morfologicznych - których reprezentacja jest naturalnie rzadka - zwizanych z dan struktur. Wymaga to jednak rcznego wyboru, prawdopodobnie mudnego, kombinacji cech, które maj by uwzgldnione w ocenie, przed uyciem algorytmu uczcego si. Dlatego dostosowanie tych modeli do nowych jzyków lub nowych dziedzin jest trudne i kosztowne; ponadto zapomnienie o wanej charakterystyce moe mie bardzo negatywny wpyw na precyzj (problem niekompletnoci). Ponadto analizatorzy spdzaj wikszo czasu na wyodrbnianiu cech, a nie samej analizie. Wszystkie te powody zmotywoway rozwój modeli nieliniowych , zdolnych do automatycznego wywoywania odpowiedniej kombinacji cech predykcyjnych; w takich przypadkach sztuczna sie neuronowa zajmuje drugie miejsce lub w wikszoci zastpuje klasyfikator liniowy . W przypadku wikszoci modeli konieczne jest jednak zapewnienie im niewielkiej liczby (ok. 1020) prostych charakterystyk dynamicznych (tj. Nieskadanych). Podejcie to zostao zapocztkowane przez Jamesa Hendersona na pocztku XXI wieku, a nastpnie pogbione w 2007 r. Za pomoc analizatora opartego na czysto generatywnym modelu probabilistycznym i wyposaonego w ISBN ( przyrostowa sigmoidalna sie przekona ) do wyodrbniania charakterystyk, bardzo zblionych do `` dynamicznego modelu

bayesowskiego ''. sie . Zalet tej techniki jest uzyskanie gstej reprezentacji sów (tj. Osadzanie sów ), znaczników morfosyntaktycznych i innych cech jzykowych; ta ostatnia reprezentacja (o mniejszym wymiarze) przenosi na przykad pojcie podobiestwa midzy sowami w cigej przestrzeni wymiarowej lub nawet ca histori analizy, gdy sie jest powtarzalna. Krótko mówic, gste reprezentacje korzystaj z duej zdolnoci do generalizacji. ${\ displaystyle m}$

Modele dynamicznych (niezalenych) charakterystyk, o których mowa w poprzednim akapicie, wybieraj elementy jzykowe (sowa, etykiety zalenoci itp.), Których wektory reprezentacji ( osadzenia ) s czsto czone na wejciu sieci neuronowej. Jeli liczba funkcji moe si zmienia, potrzebny jest jaki sposób na utrzymanie wektorów o staym rozmiarze, poniewa dane wejciowe do sieci maj stay rozmiar. Mona na przykad przeprowadzi urednienie wektorów (reprezentacja przez cigy zbiór sów lub CBOW).

Obecnie ekstrakcji funkcja jest wykonywana z sieci o rónej zoonoci, w której skad LSTM jednostek na przykad (uoone sieci LSTM dwukierunkowy LSTM, etc.), ISBN lub za pomoc sieci, bez nawrotów., Podobnie jak w pierwszej warstwy wielo warstwowy perceptron . Niektóre podejcia (zwane opartymi na znakach ) ucz si nawet przedstawia sowa z pojedynczych znaków, na przykad SyntaxNet ( ^druga wersja) i LSTM-Parser.

Jeli chodzi o sam klasyfikator, to czsto jest to ustrukturyzowany perceptron, taki jak proponowany przez Google system SyntaxNet ( Parsey's Cousins ), którego poprawiony system ( ParseySaurus ) jest obecnie jednym z najbardziej precyzyjnych. Te ostatnie systemy s pocztkowo opiera si na Stanford Parser opracowany przez Danqi Chen i Christophera Manninga w 2014 roku, ale integrowa gboki sieci neuronowej (i róne funkcje aktywacji) szkolenia zorganizowanego, nie wspominajc o model probabilistyczny z globalnej normalizacji. Lub z samo- normalizacja. Jednak najnowoczeniejsze systemy, takie jak LSTM-Parser lub DINN, niekoniecznie musz ucieka si do gbokiej sieci i na przykad wykorzystuj warstw softmax jako klasyfikator (przewidywanie elementarnych dziaa analizy).

Metody oparte na grafach

Modele analityczne oparte na wykresach s modelami dyskryminujcymi (patrz sekcja   modele analizy statystycznej  ). Zalet struktur w zalenociach w porównaniu do struktur w skadnikach jest dostosowanie tego typu podejcia do dokadnego wnioskowania. Rzeczywicie, szeroko rozpowszechnione podejcie, pocztkowo zaproponowane przez Ryana McDonalda i wsp. polega na znalezieniu drzewa opinajcego o maksymalnej wadze na penym wykresie . Zauwa, e w tych warunkach komponent nie jest modelowany przez system autonomiczny, ale przez waciwo

teorii grafów . Jednak dokadne wnioskowanie zakada ograniczenie zakresu cech do podgrafów; w zwizku z tym opracowano inne techniki aproksymacyjne. W porównaniu z modelami opartymi na przejciach zalet tego typu modelu jest obserwacja - w teorii - waciwoci caej struktury globalnej i / lub nieograniczonego zdania wejciowego, podczas gdy waciwoci s ograniczone do strukturalnego kontekstu lokalnego z pierwsz kategori . ${\ Displaystyle \ mathrm {GEN} ({\ boldsymbol {x}})}$

W praktyce tylko modele traktujce punktacj kadego uku z osobna - nazywane ^1. rzdu lub podzielone na czynniki uku - s rozwizywane w sposób dokadny w rozsdnym czasie, poniewa najmniejszy wzrost tych modeli generuje problem NP-trudny . To zakada, e kada relacja zalenoci jest niezalena od pozostaych, co jest dalekie od prawdy z jzykowego punktu widzenia. Jednak niektóre systemy 1 ^st rzdu s bardzo konkurencyjne pod wzgldem dokadnoci, tak po prostu T. i C. Manning Dozat mechanizm oparty opieki gboko biaffine . Zdecydowana wikszo systemów ^pierwszego rzdu opiera si albo na algorytmie Eisnera, albo na chciwym algorytmie Chu-Liu-Edmondsa (CLE). Pierwszy to algorytm programowania dynamicznego wywodzcy si z CKY, który w zwizku z tym znajduje tylko struktury rzutowe, podczas gdy drugi znajduje drzewo rozpinajce o maksymalnej masie i dlatego jest równie zdolny do zwrócenia nieprzewidywalnego drzewa zalenoci.

Aby przewidzie popraw wydajnoci przy zachowaniu algorytmu wielomianowego czasu, niektóre podejcia rozszerzyy wykres algorytmu Eisnera, dodajc czynnik kwadratowy do zoonoci z kadym wzrostem w kolejnoci modelu. Badania w tym kierunku s mniej wicej zgodne z modelami ^czwartego rzdu (zoono czasowa ). Nowsze strategie - i odpowiednio 200x i 5x szybciej ni dokadny model trzeciego

^rzdu - baday przycinanie przestrzeni poszukiwa za pomoc algorytmu Vine parse ^{( )} lub utrzymywanie zbioru alternatyw zintegrowanych z algorytmem Eisnera (duch przycinanie kostka ), midzy innymi. Te przyblione pozwalaj znacznie obniy koszty analizy, przy jednoczesnym zachowaniu dokadnoci przy dokadnych modeli 3 ^rd lub 4 ^th zamówienia! ${\ Displaystyle {\ mathcal {O}} (n ^ {5})}$

Jeli chodzi o modele wyszego rzdu zdolne do tworzenia wszelkiego rodzaju drzew zalenoci (w tym drzew nie projekcyjnych), z koniecznoci przechodz one przez przyblienie, albo przez dekodowanie, albo przez przestrze poszukiwa. Pierwsza opcja obejmuje systemy uwzgldniajce przetwarzanie kocowe na kocu algorytmu Eisnera lub CLE, który odpowiednio przestawia uki lub czy najlepsze drzewa rozpinajce. Inne opieraj si na zasadzie podwójnego rozkadu, cigej relaksacji itp. Druga kategoria obejmuje procesy uwzgldniajce tylko niewielk cz zbioru drzew zalenoci nie projekcyjnych, poniewa niektóre struktury s jzykowo nieprawdopodobne i próba ich wytworzenia jest cakowicie bezuyteczna (te ostatnie nazywane s strukturami agodnie nieprojektywnymi ) . Podjto jednak mniej udane eksperymenty z integeryczn optymalizacj liniow (ILP).

Wszystkie te systemy wykorzystuj algorytm uczenia si, taki jak strukturalny perceptron, MIRA (rozszerzenie tego ostatniego), klasyfikator maksymalnej entropii (MaxEnt) itp. Wikszo systemów omówionych w tej sekcji wybiera charakterystyk kadego podgrafu (np. uku) przy uyciu wczeniej ustalonych modeli (rzadka reprezentacja). Jednak niektóre najnowsze techniki wykorzystuj sie neuronow do wyodrbniania cech: propagacja w przód lub rekurencja  ; ponadto wynik nie jest ju obliczany liniowo, ale w szczególnoci przez wielowarstwowy perceptron , czasami zwizany z transformacj dwuliniow.

Zoono analizy zalenoci

Oto przegld czasowej zoonoci algorytmów analizowania struktur zalenoci. Odróniamy te, które mog wytwarza tylko struktury rzutowe od ogólnych algorytmów, ale bierzemy pod uwag tylko dokadne wersje (z wyczeniem przyblie).

	Proj.	Non-proj.
Analiza oparta na przejciach	${\ Displaystyle {\ mathcal {O}} (n)}$	${\ Displaystyle {\ mathcal {O}} (n ^ {2})}$ ${\ Displaystyle {\ mathcal {O}} (n)}$ w praktyce
Analiza w oparciu o wykresy - 1. rzdu	${\ Displaystyle {\ mathcal {O}} (n ^ {3})}$	${\ Displaystyle {\ mathcal {O}} (n ^ {2})}$
Analiza oparta na wykresach - n - ty rzd (n> 1)	FP ...	Kompletny FNP

Ocena analizy

Kady system analizowania musi zosta oceniony, aby zmierzy jego wydajno. Osiga si to poprzez wykonanie procedury analizy na zbiorze danych testowych, innym ni zbiór uczcy (jeli istnieje) i ogólnie znacznie mniejszym. Struktury utworzone przez parser zostan porównane ze strukturami referencyjnymi ( parsami zotego standardu ), uwaanymi za najlepsze analizy - które s opatrzone adnotacjami przez lingwistów. Zwykle stosowane miary to precyzja i przypominanie , czsto poczone w jeden wynik zwany wynikiem F , odpowiadajcy redniej harmonicznej precyzji ( ) i przypominania ( ): ${\ textstyle P}$${\ textstyle R}$

$${\ Displaystyle F_ {1} = {\ Frac {(2PR)} {(P + R)}}}$$

Najprostsz metod jest policzenie liczby zda, dla których utworzona struktura jest identyczna ze struktur odniesienia ( dopasowanie cise ). Jest to niezwykle trudny test w tym sensie, e pojedynczy bd w etykiecie ma taki sam wpyw, jak cakowicie bdna analiza; dlatego raczej preferowane s metryki oparte na czciowym dopasowaniu, którego szczegóowo jest dokadniejsza.

Od struktur do czci skadowych

Powszechnie stosowanymi pomiarami s pomiary zwizane z metrykami PARSEVAL, zliczajce liczb skadników, które odpowiadaj tym obecnym w strukturze odniesienia.

Od konstrukcji po budynki gospodarcze

W odniesieniu do struktur zalenoci, powszechnie stosowan miar jest ocena przywizania , która okrela odsetek sów poprawnie powizanych z waciwym rodzicem w porównaniu z odniesieniem. Istnieje kilka odmian:

• Wynik przywizania bez etykiety (UAS): zwizek jest uwaany za prawidowy, jeli dziecko jest spokrewnione z oczekiwanym rodzicem.
• Oznaczona ocena przywizania (LAS): zwizek jest uwaany za prawidowy, jeli dziecko jest spokrewnione z oczekiwanym rodzicem, a typ relacji jest wiernie odtworzony.
• Wynik dokadnoci etykiety (LS): badamy tylko etykiet relacji, bez uwzgldnienia rodzica.

Poniewa kada jednostka leksykalna ma dokadnie jednego rodzica, do okrelenia dokadnoci wystarczy tylko jedna miara. Na poziomie korpusu wynik globalny mona obliczy w skali sowa ( mikrorednia ), czyli bez uwzgldnienia zdania, do którego sowo naley, lub w skali zdania ( rednia makro ) , biorc redni z wyników kadego z nich.

Uwagi i odniesienia

1. Zwykle zalenoci krzyowych (lub nie projekcyjnych) - wystpujcych w niektórych jzykach - nie mona uzyska za pomoc gramatyki typu 2 . Jzyk naturalny jest zatem typem 1 ( kontekstualnym ), niemniej jednak bardzo zblionym do typu 2.
2. drzewa zalenoci formalnie jest prosty, poczony i oznaczony acykliczny skierowane wykres, skadajcy si z jednego pierwiastka, wyposaony w liniowo wzgldem pierwszestwa w zestawie wierzchoków (kolejno sowo).${\ displaystyle V}$
3. Odpowiada to czeniu elementów jzykowych (sów ...), a nastpnie wyszukiwaniu w strukturze danych zawierajcej kilka milionów elementów.
4. Wszystkie poprzednie systemy wykorzystuj lokaln normalizacj , znacznie mniej skomplikowan do oblicze. Niemoliwe jest równie obliczenie globalnie znormalizowanych prawdopodobiestw w rozsdnym czasie; w zwizku z tym systemy te wymagaj przyblienia.

Odnoniki bibliograficzne

1. Jacqueline Léon , Historia automatyzacji nauk o jzyku , ENS Éditions, wyd.  "Jzyki",27 marca 2015 r, 218  s. ( ISBN  978-2-84788-680-1 , DOI  10.4000 / books.enseditions.3733 , czytaj online )
2. Tadao Kasami, Efektywny algorytm rozpoznawania i skadni jzyków bezkontekstowych, Raport techniczny AFCLR-65-758 , Air Force Cambridge Research Laboratory, 1965
3. DH Younger, Rozpoznawanie jzyków bezkontekstowych w czasie n ³  , Informacje i kontrola , t.   10 N ^O   2, 1967, str.   189-208.
4. Jay Earley skutecznego kontekstu wolne algorytm analizy skadni, w: Communications of the ACM 13 (2) , str. 94-102,170
5. Ronald M. Kaplan, typowego procesora skadniowej, w: Natural Language Processing pod re. R. Rustin, Algorithmics Press, s. 193-241,1973
6. Martin Kay, Algorithm Schemata and Data Structures in Syntactic Processing, raport CSL - 8012 , Xerox PARC, 1980
7. Alan Demers, Generalized Left Corner Parsing, W: Proceedings of the 4th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages , ACM, str. 170-182,1977
8. Hiroshi Maruyama, Strukturalne ujednoznacznienie z propagacj ogranicze, W: Proceedings of the 28th Meeting of the Association for Computational Linguistics , Association for Computational Linguistics, s. 31-38, 1990
9. T. L. Booth i RA Thompson, Applying Probability Measures to Abstract Languages, In: IEEE Transactions on Computers 22.5 , s. 442-450,1973
10. Eugene Charniak, Analiza statystyczna z gramatyk bezkontekstow i statystyk sów, w: Proceedings of 14th National Conference on Artificial Intelligence , Association for Computational Linguistics, s. 598-603, 1997
11. Dan Klein i Christopher D. Manning, Accurate unllexicalized parsing, w: Proceedings of the 41st Annual Meeting on Association for Computational Linguistics , Association for Computational Linguistics., 2003
12. Jason M. Eisner, Three New Probabilistic Models for Dependency Parsing: An Exploration, W: Proceedings of the 16th International Conference on Computational Linguistics, Association for Computational Linguistics, s. 340-345, 1996
13. Joakim Nivre, Analiza statystyczna, W: Podrcznik przetwarzania jzyka naturalnego , Pod re. autorzy: Nitin Indurkhya i Fred J. Damerau, 2. miejsce, Chapman & Hall / CRC, rozdz. 11, s. 237-266, 2010
14. Kenneth Church i Ramesh Patil, Radzenie sobie z niejednoznacznoci skadniow lub jak umieci blok w pudeku na stole, Comput. Jzykoznawca. 8,3-4,139-149,1982
15. H. Ney, Analiza dynamicznego programowania dla gramatyki bezkontekstowej w cigym rozpoznawaniu mowy, I EEE Transactions on Signal Processing, 39 (2) , 336340, 1991.
16. (w) Michael Collins , "  Head-Driven Statistical Models for Natural Language Parsing  " , Computational Linguistics , vol.  29 N ^O  4,1 ^st grudzie 2003, s.  589637 ( ISSN  0891-2017 , DOI  10.1162 / 089120103322753356 , czytaj online )
17. (w) Dan Klein i Christopher D. Manning ,   Dokadne unleksykalizowane analizowanie   , Materiay z 41. dorocznego spotkania Stowarzyszenia Lingwistyki Obliczeniowej , Stowarzyszenia Lingwistyki Obliczeniowej,07 lipca 2003, s.  423430 ( DOI  10.3115 / 1075096.1075150 , czytaj online )
18. (w) Slav Petrov , Leon Barrett , Romain Thibaux i Dan Klein , "  Learning Accurate, Compact, and interpretable Tree Annotation  " , Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics ,2006( czytaj online )
19. R. Bod, Wzbogacanie lingwistyki o statystyki: modele wydajnoci jzyka naturalnego, praca doktorska , Uniwersytet w Amsterdamie, Amsterdam, Holandia, 1995.
20. R. Bod, R. Scha i K. Sima'an (red.), Data-Oriented Parsing, CSLI Publications , Stanford, CA., 2003. ( Czytaj online )
21. (in) Michael Collins i Terry Koo ,   dyskryminacyjne Reranking for Natural Language Parsing   , Lingwistyka komputerowa , tom.  31, n ^o  1,Marzec 2005, s.  2570 ( ISSN  0891-2017 i 1530-9312 , DOI  10.1162 / 0891201053630273 , czytaj online , dostp 11 czerwca 2018 )
22. (w) Geoffrey N. Leech , Statystycznie sterowane komputerowe gramatyki jzyka angielskiego: podejcie IBM / Lancaster , Rodopi,1993( ISBN  90-5183-478-0 )
23. (en) Ivan Titov i James Henderson ,   A latent variable model for generative dependency parsing   , Proceedings of the 10th International Conference on Parsing Technologies , Association for Computational Linguistics,23 czerwca 2007, s.  144-155 ( ISBN  9781932432909 , czyt. Online , dostp 12 czerwca 2018 r. )
24. (en) Michael Collins ,   Discriminative Reranking for Natural Language Parsing   , Proceedings of the Seventeenth International Conference on Machine Learning , Morgan Kaufmann Publishers Inc.,29 czerwca 2000, s.  175-182 ( ISBN  1558607072 , czytaj online )
25. (w) Michael Collins i Nigel Duffy , "  Nowe algorytmy rankingowe do analizowania i znakowania: jdra nad strukturami dyskretnymi i gosowany perceptron  " , Proceedings of the 40th Annual Meeting on Association for Computational Linguistics , Association for Computational Linguistics,6 lipca 2002, s.  263270 ( DOI  10.3115 / 1073083.1073128 , czytaj online )
26. Haim Gaifman, Systemy zalenoci i systemy struktury fraz, In: Informacja i kontrola 8.3 , s. 304-337, 1965
27. (en) Michael A. Covington,   A Fundamental Algorithm for Dependency Parsing   , Proceedings of the 39th Annual ACM Southeast Conference ,2001, s.  95-102
28. (w) Sabine Buchholz i Erwin Marsi ,   CoNLL-X Shared Task to wielojzyczna analiza zalenoci   , International Journal of Web Engineering and Technology - IJWET ,1 ^st stycze 2006( DOI  10.3115 / 1596276.1596305 , czytaj online , dostp 12 czerwca 2018 )
29. (w) J. NIVRE, J. Hall, S. Kübler, R. McDonald, J. Nilsson, S. Riedel, D. Yuret,   The CoNLL 2007 Shared Task Dependency Parsing my   , Proceedings of the Task CoNLL Shared Session EMNLP-CoNLL 2007 ,2007, s.  915-932
30. (w) Tianze Shi , Felix G. Wu , Xilun Chen i Yao Cheng ,   Combining Global Models for Parsing Universal Dependencies   , Proceedings of the CoNLL 2017 Shared Task: Multilingual Text Parsing from Raw to Universal Dependencies , Association for Computational Linguistics, Oprócz tego musisz wiedzie o tym wicej.2017, s.  3139 ( DOI  10.18653 / v1 / K17-3003 , czytaj online )
31. (w) Anders Björkelund Agnieszka Falenska , Xiang Yu i Jonas Kuhn ,   IMS at the CoNLL 2017 UD Shared Task: CRFs and Perceptrons Meet Neural Networks   , Proceedings of the CoNLL 2017 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies , Stowarzyszenie Lingwistyki Obliczeniowej,2017, s.  4051 ( DOI  10.18653 / v1 / K17-3004 , czytaj online )
32. (w) Joakim NIVRE i Ryan McDonald ,   Integrating Graph-Based and Transition-Based Dependency Parsers   , Proceedings of ACL-08: HLT ,2008( czytaj online )
33. (w) Ryan Mcdonald , "  Charakteryzowanie bdów modeli analizy zalenoci opartych na danych  " , PRZEBIEG KONFERENCJI NA TEMAT METOD EMPIRYCZNYCH W PRZETWARZANIU JZYKA NATURALNEGO I NAUKA JZYKA NATURALNEGO ,2007( czytaj online , sprawdzono 11 czerwca 2018 r. )
34. Joakim Nivre, An Efficient Algorithm for Projective Dependency Parsing, In: Proceedings of the 8th International Workshop on Parsing Technologies (IWPT) , 2003
35. (en) Ryan McDonald Fernando Pereira , Kiril Ribarov i Jan Haji ,   Non-rzutowa zaleno parsowania przy uyciu obejmujce algorytmy drzewo   , Proceedings of the Conference on Human Language Technology i empiryczne metody w Natural Language Processing , Stowarzyszenie dla lingwistyki komputerowej,6 padziernika 2005, s.  523-530 ( DOI  10.3115 / 1220575.1220641 , odczyt online , dostp: 6 czerwca 2018 )
36. (w) Jinho D. Choi , Joel Tetreault i Amanda Stent ,   It Depends: Dependency Parser A Compare Using Web-Based Evaluation Tool   , Proceedings of the 53rd Annual Meeting of the Computational Linguistics and the 7th International Joint Conference on Przetwarzanie jzyka naturalnego (tom 1: dugie artykuy) , Stowarzyszenie Lingwistyki Obliczeniowej, t.  1,2015, s.  387396 ( DOI  10.3115 / v1 / P15-1038 , czytaj online )
37. Tony Jebara, Discriminative, Generative and Imitation Learning, praca doktorska , Massachusetts Institute of Technology, 212 s., 2002.
38. (w) Joakim NIVRE , "  Algorytmy dla deterministycznego analizowania zalenoci przyrostowych  " , Lingwistyka obliczeniowa , tom.  34, n ^o  4,grudzie 2008, s.  513553 ( ISSN  0891-2017 i 1530-9312 , DOI  10.1162 / coli.07-056-r1-07-027 , odczyt online , dostp 6 czerwca 2018 r. )
39. (w) Taku Kudo i Yuji Matsumoto , "  Japoska analiza struktury zalenoci jest oparta na maszynach wektorów nonych  " , Proceedings of the 2000 Joint Conference on SIGDAT Empirical Methods in Natural Language Processing and Very Large Corpora , Association for Computational Linguistics,7 padziernika 2000, s.  1825 ( DOI  10.3115 / 1117794.1117797 , czytaj online , dostp: 6 czerwca 2018 )
40. (w) Joakim NIVRE Johan Hall , Jens Nilsson i Gülen Eryiit ,   Labeled pseudo-projective dependency parsing with support vector machines   , Proceedings of the Tenth Conference on Computational Natural Language Learning , Association for Computational Linguistics,8 czerwca 2006, s.  221225
41. J. Nivre, J. Hall, J. Nilsson, A. Chanev, G. Eryigit, S. Kübler, S. Marinov i E. Marsi, MaltParser: A language-Independent system for data-based dependency parsing, Inynieria jzyka naturalnego , 13, 95-135, 2007.
42. Giuseppe Attardi, Experiments with a wielojzyczny non-projective dependency parser, In Proceedings of the Tenth Conference on Computational Natural Language Learning (CoNLL-X '06). Stowarzyszenie Lingwistyki Obliczeniowej, Stroudsburg, PA, USA, 166-170, 2006.
43. (in) Joakim NIVRE ,   Incremental Non-Projective Dependency Parsing.  » , Materiay konferencji pónocnoamerykaskiego oddziau Stowarzyszenia Lingwistyki Obliczeniowej ,1 ^st stycze 2007, s.  396-403
44. Joakim Nivre, Non-projective dependency parsing in oczekiwany czas liniowy. In Proceedings of the Joint Conference of the 47th Annual Meeting of ACL and the 4th International Joint Conference on the Natural Language Processing of the AFNLP: Volume 1 - Volume 1 (ACL '09), Association for Computational Linguistics, Stroudsburg, PA, USA, 351-359, 2009.
45. Carlos Gómez-Rodríguez i Joakim Nivre, Parser oparty na przejciach dla 2-planarnych struktur zalenoci. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics (ACL '10), Association for Computational Linguistics, Stroudsburg, PA, USA, 1492-1501, 2010.
46. (w) Joakim NIVRE i Jens Nilsson , "  Pseudo-projective dependency parsing  " , Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics , Association for Computational Linguistics,25 czerwca 2005, s.  99106 ( DOI  10.3115 / 1219840.1219853 , czytaj online , dostp 12 czerwca 2018 )
47. Richard Johansson i Pierre Nugues, Investigating multilingual dependency parsing, In Proceedings of the Tenth Conference on Computational Natural Language Learning (CoNLL-X '06), Association for Computational Linguistics, Stroudsburg, PA, USA, 206-210, 2006.
48. (w) Yue Zhang i Stephen Clark , "  Opowie o dwóch parserach: Badanie i czenie analizy zalenoci opartej na grafach i przejciach przy uyciu wyszukiwania wizki  " , W PROCEDURACH EMNLP-08 ,2008
49. Yoav Goldberg i Michael Elhadad, Efektywny algorytm dla atwego pierwszego bezkierunkowego analizowania zalenoci, In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics (HLT '10), Association for Computational Linguistics, Stroudsburg, PA, USA, 742-750, 2010.
50. Yoav Goldberg, Joakim Nivre, A Dynamic Oracle for Arc-Eager Dependency Parsing, 2012
51. Milan Straka, Jan Haji, Jana Strakova i Jan jr. Haji, Parsing Universal Dependency Treebanks using Neural Networks and Search-Based Oracle, 2015.
52. (w) Yue Zhang i Joakim NIVRE ,   Transition-based Dependency Parsing with Rich Features Non-local   , Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics ,2011
53. Danqi Chen i Christopher Manning ,   szybkie i dokadne Zaleno parsera wykorzystujce sieci neuronowe  , Proceedings of 2014 Konferencji empirycznych metod w Natural Language Processing (EMNLP) , Association for Computational Linguistics,2014( DOI  10.3115 / v1 / d14-1082 , czytaj online )
54. (w) Bernd Bohnet , "  Bardzo wysoka dokadno i szybkie analizowanie zalenoci nie jest sprzecznoci  " , Proceedings of the 23rd International Conference on Computational Linguistics , Association for Computational Linguistics,23 sierpnia 2010, s.  8997
55. (w) James Henderson ,   Inducing history reprezentations szeroki zasig dla analizy statystycznej   , Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology , Association for Computational Linguistics,27 maja 2003, s.  2431 ( DOI  10.3115 / 1073445.1073459 , czytaj online , dostp: 6 czerwca 2018 )
56. (w) James Henderson ,   dyskryminacyjne szkolenie analizatora statystycznego sieci neuronowej   , Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics , Association for Computational Linguistics,21 lipca 2004, s.  95 ( DOI  10.3115 / 1218955.1218968 , czytaj online , dostp: 6 czerwca 2018 )
57. (w) T Mikolov , W. T- Yih i G Zweig , "  Lingwistyczne regularnoci w cigych reprezentacjach wyrazów w przestrzeni  " , Proceedings of NAACL-HLT ,1 ^st stycze 2013, s.  746751 ( czytaj online )
58. (w) Tomas Mikolov Kai Chen , Greg Corrado i Jeffrey Dean ,   Efficient Estimation of Word Vector Representations in Space   , arXiv: 1301.3781 [cs] ,16 stycznia 2013( czytaj online )
59. (w) Chris Dyer , Miguel Ballesteros , Wang Ling i Austin Matthews ,   Transition-Based Dependency Parsing Stack with Long Short-Term Memory   , arXiv: 1505.08075 [cs] ,29 maja 2015( czytaj online )
60. (en) Eliyahu Kiperwasser i Yoav Goldberg ,   Simple and Accurate Dependency Parsing Using Bidirectional LSTM Feature Representations   , arXiv: 1603.04351 [cs] ,14 marca 2016 r( czytaj online )
61. Majid Yazdani i James Henderson, Przyrostowy powtarzajcy si analizator zalenoci sieci neuronowej ze szkoleniem dyskryminacyjnym opartym na wyszukiwaniu, w: Proceedings of the 19th Conference on Computational Language Learning , Pekin, Chiny, 2015, s. 142-152.
62. (en) Daniel Andor , Chris Alberti , David Weiss i Aliaksei Severyn ,   Globally Normalized Transition-Based Neural Networks   , Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) , Stowarzyszenie Lingwistyki Obliczeniowej,2016( DOI  10.18653 / v1 / p16-1231 , czytaj online )
63. (en) "  Uaktualnienie do SyntaxNet, nowe modele i konkurs analizowania  " ,15 marca 2017 r
64. (en) Miguel Ballesteros , Chris Dyer i Noah A. Smith ,   Improved Transition-based Parsing by Modeling Characters zamiast Words with LSTMs   , Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing , Association for Computational Jzykoznawstwo,2015( DOI  10.18653 / v1 / d15-1041 , czytaj online )
65. (in) Ryan McDonald i Fernando Pereira ,   Online Learning of Approximate Dependency Parsing Algorithms   , IN PROC. AECL ,2006, s.  8188
66. (en) Ryan McDonald i Giorgio Satta ,   On the complexity of non-projective data-based dependency parsing   , Proceedings of the 10th International Conference on Parsing Technologies , Association for Computational Linguistics,23 czerwca 2007, s.  121132 ( ISBN  9781932432909 , czytaj online )
67. (en) Timothy Dozat i Christopher D. Manning ,   Deep Biaffine Attention for Neural Dependency Parsing   , arXiv: 1611.01734 [cs] ,6 listopada 2016 r( czytaj online )
68. (w) Jason M. Eisner , "  Three new probabilistic models for dependency parsing: an exploration  " , Proceedings of the 16th Conference on Computational Linguistics , Association for Computational Linguistics,5 sierpnia 1996, s.  340345 ( DOI  10.3115 / 992628.992688 , czytaj online )
69. Jack Edmonds, Optimum Branchings, w: J. Res. Nat. Rzep. Normy 71B.4 , s. 233-240,1967.
70. (en) Xavier Carreras ,   Experiments with a Higher-Order Projective Dependency Parser   , Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL) ,2007( czytaj online )
71. (w) Terry Koo i Michael Collins ,   Efektywne analizatory zalenoci trzeciego rzdu.  » , Materiay z 48. dorocznego spotkania Stowarzyszenia Lingwistyki Komputerowej ,22 grudnia 2010, s.  111 ( czytaj online )
72. (w) Xuezhe My and Hai Zhao ,   Fourth-Order Dependency Parsing   , Proceedings of COLING 2012 ,1 ^st grudzie 2012, s.  785796 ( czytaj online )
73. (w) Markus Dreyer , David A. Smith i Noah A. Smith ,   Analiza winoroli i zmiana kolejnoci minimalnego ryzyka dla szybkoci i precyzji   , Materiay z dziesitej konferencji na temat komputerowego uczenia si jzyka naturalnego , Stowarzyszenie Lingwistyki Obliczeniowej,8 czerwca 2006, s.  201205 ( czytaj online )
74. (w) Alexander M. Rush i Slav Petrov , "  Przycinanie winoroli dla efektywnej zalenoci parsowania wieloprzebiegowego  " , Materiay z konferencji z 2012 r. Pónocnoamerykaskiego oddziau Stowarzyszenia Lingwistyki Obliczeniowej , Stowarzyszenie Lingwistyki Obliczeniowej,3 czerwca 2012, s.  498507 ( ISBN  9781937284206 , czytaj online )
75. (w) Mark Hopkins i Greg Langmead ,   Przycinanie kostek jako przeszukiwanie heurystyczne   , Materiay z konferencji z 2009 r. Na temat metod empirycznych w przetwarzaniu jzyka naturalnego , Stowarzyszenie Lingwistyki Obliczeniowej,6 sierpnia 2009, s.  6271 ( ISBN  9781932432596 , czytaj online )
76. (w) Hao Zhang i Ryan McDonald ,   Generalized Higher-Order Dependency Parsing with Cube Pruning   , Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning ,2012( czytaj online )
77. (w) Keith Hall ,   K-best Spanning Tree Parsing   , Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics ,2007( czytaj online )
78. (w) Terry Koo , Alexander M. Rush , Michael Collins i Tommi Jaakkola , "  Dual decomposition for parsing with non-projective head automat  " , Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing , Association for Computational Linguistics,9 padziernika 2010, s.  1288-1298 ( czytaj online )
79. (w) Andre FT Martins , Noah A. Smith , Pedro MQ Aguiar i AT Mário Figueiredo ,   Dual decomposition with overlapping Many components   , Proceedings of the Conference on Empirical Methods in Natural Language Processing , Association for Computational Linguistics,27 lipca 2011, s.  238249 ( ISBN  9781937284114 , czytaj online )
80. (w) André Martins , Miguel Almeida i Noah A Smith ,   Turning on the Turbo Fast Third-Order Non-Projective Turbo Parsers   , Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics , vol.  2,1 ^st sierpie 2013, s.  617622 ( czytaj online )
81. (w) Sebastian Riedel , David Smith i Andrew Mccallum ,   Parse, price and cut: delayed column and row generation for graph based parsers   , Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning , Oprócz tego musisz wiedzie o tym wicej.12 lipca 2012, s.  732743 ( czytaj online )
82. (w) Carlos Gomez-Rodriguez , John Carroll i David Weir , "  Dependency parsing schemata and lekko non-projective dependency parsing  " , Computational Linguistics , vol.  37, n ^o  3,1 ^st wrzesie 2011, s.  541586 ( ISSN  0891-2017 , DOI  10.1162 / COLI_a_00060 , czytaj online )
83. (w) Emily Pitler , Sampath Kannan and Mitchell Marcus ,   Dynamic Programming for Higher Order Parsing of Gap Minding Trees   , Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning ,2012( czytaj online )
84. (w) Emily Pitler , Sampath Kannan i Mitchell Marcus ,   Finding Optimal 1-Endpoint-Crossing Trees   , Transactions of the Association of Computational Linguistics , vol.  1,2013( czytaj online )
85. (w) Emily Pitler , "  A Crossing-Sensitive Third-Order factorization for Dependency Parsing  " , Transactions of the Association of Computational Linguistics , vol.  2 n ^o  1,2014( czytaj online )
86. (w) Andre FT Martins , Noah A. Smith i Eric P. Xing ,   Concise integer linear Programulation formulations for dependency parsing   , Proceedings of the Joint Conference of the 47th Annual Meeting of ACL oraz 4th International Joint Conference on Natural Przetwarzanie jzykowe AFNLP , Stowarzyszenie Lingwistyki Obliczeniowej,2 sierpnia 2009, s.  342350 ( ISBN  9781932432459 , czytaj online )
87. (w) Koby Crammer i Yoram Singer ,   ultrakonserwatywne algorytmy online dla problemów wieloklasowych   , The Journal of Machine Learning Research , vol.  3,1 ^st marca 2003, s.  951991 ( ISSN  1532-4435 , DOI  10.1162 / jmlr.2003.3.4-5.951 , czytaj online )
88. (en) Wenzhe Pei , Tao Ge i Baobao Chang ,   An Effective Neural Network Model for Graph-based Dependency Parsing   , Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics oraz 7th International Joint Conference on Natural Przetwarzanie jzyka (tom 1: dugie artykuy) , Stowarzyszenie Lingwistyki Obliczeniowej, t.  1,2015, s.  313322 ( DOI  10.3115 / v1 / P15-1031 , czytaj online )
89. CJ van Rijsbergen, Pobieranie informacji , Butterworths, 1975.
90. (w) S. Abney , S. Flickenger , C. Gdaniec i C. Grishman ,   Procedura ilociowego porównywania skadniowego pokrycia gramatyki angielskiej   , Materiay warsztatowe to Speech and Natural Language Association for Computational Linguistics,19 lutego 1991, s.  306311 ( DOI  10.3115 / 112405.112467 , czytaj online )
91. R. Grishman, C. Macleod i J. Sterling, Evaluating parsing strategy using standardized parse files, In Proceedings of the Third Conference on Applied Natural Language Processing (ANLP) , Trento, Wochy, str. 156-161,1992.
92. (w) Sabine Buchholz i Erwin Marsi ,   CoNLL-X Shared task is multilingual dependency parsing   , Proceedings of the Tenth Conference on Computational Natural Language Learning (CoNLL-X) , Association for Computational Linguistics,8 czerwca 2006, s.  149-164 ( DOI  10.3115 / 1596276.1596305 , odczyt online , dostp: 11 czerwca 2018 )

Zobacz te

Bibliografia

• Daniel Jurafsky i James H. Martin, Speech and Language Processing (2. wydanie), Prentice Hall,16 maja 2008, 1024 s. 
• Nitin Indurkhya i Fred J. Damerau (red.), Handbook of Natural Language Processing (2. wydanie), Chapman & Hall,22 lutego 2010, 702 pkt.
• AV Aho i JD Ullman, Teoria analizy, tumaczenia i kompilacji , tom. 1. Prentice Hall, 1972.
• Christophe Moor, Multilingual Dependency Parsing from Raw Text to Universal Dependencies: The CLCL entry , praca magisterska, University of Geneva, 2018.

Powizane artykuy

• Automatyczne przetwarzanie jzyka naturalnego
• Analiza semantyczna
• Analiza leksykalna
• Rozbiór gramatyczny zdania
• Drzewo skadni
• Gramatyka bezkontekstowa
• Gramatyka zalenoci
• Algorytm Cocke-Younger-Kasami
• Analiza Earley
• Programowanie dynamiczne
• Klasyfikator liniowy
• Wielowarstwowy perceptron
• Sztuczna sie neuronowa

Linki zewntrzne

• Parser skadowych historycznych

Collinsa oparty na leksykalizowanych probabilistycznych gramatykach bezkontekstowych

Parser zalenoci statystycznych

MaltParser oparty na przejciach (zaimplementowany w Javie)

Graficzny analizator zalenoci

MSTParser (Java)

Analizator zalenoci

IDP oparty na przejciach i generatywnym modelu probabilistycznym, integrujcy rekurencyjn sie neuronow (C)

Stanford Parser najnowszy analizator zalenoci oparty na przejciach i integracji sieci neuronowej