Länk grammatik

Länk Grammar parser
Utvecklare	OpenCog
Initial release	oktober 1991 ; 31 år sedan
Stabil frisättning	5.8.1 / 8 januari 2021 ; för 2 år sedan
Förvar	github .com /opencog /länk-grammar ;
Skrivet i	C++ ; ursprungligen C
Operativ system	Cross-plattform
Plattform	GNU
Typ	NLP
Licens	LGPLv2
Hemsida	www .abisource .com /projects /link-grammar /

Länkgrammatik (LG) är en syntaxteori av Davy Temperley och Daniel Sleator som bygger relationer mellan ordpar snarare än att konstruera beståndsdelar i en frasstrukturhierarki . Länkgrammatik liknar beroendegrammatik , men beroendegrammatik inkluderar ett huvudberoende förhållande, medan Linkgrammatik gör det huvudberoende förhållandet valfritt (länkar behöver inte ange riktning). Colored Multiplanar Link Grammar (CMLG) är en förlängning av LG som tillåter korsning av relationer mellan ordpar. Relationen mellan ord indikeras med länktyper , vilket gör länkgrammatiken nära besläktad med vissa kategorigrammatiker .

Till exempel, i ett ämne-verb-objekt- språk som engelska, skulle verbet titta åt vänster för att bilda en ämneslänk och åt höger för att bilda en objektlänk. Substantiv skulle titta åt höger för att komplettera ämneslänken, eller vänster för att komplettera objektlänken.

I ett subjekt–objekt–verb- språk som persiska skulle verbet titta åt vänster för att bilda en objektlänk och en mer avlägsen vänster för att bilda en subjektlänk. Substantiv ser till höger för både ämnes- och objektlänkar.

Översikt

Länkgrammatik förbinder orden i en mening med länkar, liknande formen som en catena . Till skillnad från catena eller en traditionell beroendegrammatik är markeringen av det huvudberoende förhållandet valfritt för de flesta språk, och blir obligatoriskt endast på språk med fritt ordföljd ( som turkiska , finska , ungerska , litauiska ). Det vill säga på engelska är förhållandet subjekt-verb "uppenbart", i och med att subjektet nästan alltid står till vänster om verbet, och därför behöver ingen specifik indikation på beroende göras. I fallet med subjekt-verbinversion används en distinkt länktyp. För fria ordordningsspråk kan detta inte längre hålla, och en länk mellan subjekt och verb måste innehålla en explicit riktningspil för att indikera vilket av de två orden som är vilket.

Länkgrammatik skiljer sig också från traditionella beroendegrammatik genom att tillåta cykliska relationer mellan ord. Således kan det till exempel finnas länkar som anger både huvudverbet i en mening, meningens huvudsubjekt, såväl som en länk mellan subjektet och verbet. Dessa tre länkar bildar alltså en cykel (en triangel, i detta fall). Cykler är användbara för att begränsa vad som annars skulle kunna vara tvetydiga analyser; cykler hjälper till att "strama upp" uppsättningen av tillåtna analys av en mening.

Till exempel i analysen

+---->WV--->+ +--Wd--+-Ss-+--Pa--+ | | | | VÄNSTER-VÄGG han springer fort

VÄNSTER VÄGG indikerar meningens början, eller rotnoden. Den riktade WV- länken (med pilar) pekar på meningens huvudverb; det är länken Wall-Verb. Wd-länken (ritad här utan pilar) indikerar meningens huvudsubstantiv (subjektet). Länktypen Wd indikerar både att den ansluter till väggen (W) och att meningen är en deklarativ mening (undertypen med gemener "d"). Ss - länken indikerar förhållandet subjekt-verb; de gemena "s" som indikerar att motivet är singular. Observera att WV, Wd och Ss länkar för en cykel. Pa-länken kopplar verbet till ett komplement; det gemena "a" anger att det är ett predikativt adjektiv i detta fall.

Parsningsalgoritm

Parsning utförs i analogi med att sätta ihop ett pussel (som representerar den analyserade meningen) från pusselbitar (som representerar enskilda ord). Ett språk representeras med hjälp av en ordbok eller lexis , som består av ord och den uppsättning tillåtna "pusselformer" som varje ord kan ha. Formen indikeras av en "kontakt", som är en länktyp, och en riktningsvisare + eller - som indikerar höger eller vänster. Således kan till exempel ett transitivt verb ha kopplingarna S- & O+ som indikerar att verbet kan bilda en Subjekt (" S ")-koppling till vänster (" -" ) och en objektkoppling (" O ") till höger ( " + "). På liknande sätt kan ett vanligt substantiv ha kopplingarna D- & S+ vilket indikerar att det kan ansluta till en bestämningsfaktor till vänster (" D- ") och fungera som subjekt, när det kopplas till ett verb till höger (" S+ "). Handlingen med att analysera är sedan att identifiera att S+ -anslutningen kan ansluta till S- anslutaren och bilda en " S "-länk mellan de två orden. Parsningen slutförs när alla kontakter har anslutits.

Ett givet ord kan ha dussintals eller till och med hundratals tillåtna pusselformer (som kallas "disjunkter"): till exempel kan många verb vara valfritt transitiva, vilket gör O+-kopplingen valfri ; sådana verb kan också ta adverbial modifierare ( E- anslutningar) som i sig är valfria. Mer komplexa verb kan ha ytterligare kopplingar för indirekta objekt, eller för partiklar eller prepositioner . Således innebär en del av analysen också att välja en enda unik disjunkt för ett ord; den sista analysen måste uppfylla (ansluta) alla anslutningar för den disjuncten.

Beroende

Anslutningsdon kan också inkludera huvudberoende indikatorer h och d . I det här fallet får en kontakt som innehåller en huvudindikator endast anslutas till en kontakt som innehåller den beroende indikatorn (eller till en kontakt utan några hd-indikatorer på den). När dessa indikatorer används är länken dekorerad med pilar för att indikera länkens riktning.

En nyligen genomförd tillägg förenklar specifikationen av kopplingar för språk som har få eller inga begränsningar för ordföljd, som litauiska . Det finns också tillägg för att göra det enklare att stödja språk med konkatenativa morfologier .

Planhet

Parsningsalgoritmen kräver också att den slutliga grafen är en plan graf , dvs att inga länkar korsar. Denna begränsning är baserad på empiriska psykolingvistiska bevis för att beroendelänkar verkligen inte korsas för de flesta språk, i nästan alla situationer. Det finns sällsynta undantag, t.ex. på finska och även på engelska; de kan analyseras med länkgrammatik endast genom att introducera mer komplexa och selektiva kopplingstyper för att fånga dessa situationer.

Kostnader och urval

Anslutningar kan ha en valfri flyttalskostnadsmärkning , så att vissa är "billigare" att använda än andra, vilket ger företräde åt vissa analyser framför andra. Det vill säga den totala kostnaden för analys är summan av de individuella kostnaderna för de anslutningar som användes; den billigaste analysen indikerar den mest sannolika analysen. Detta används för att analysera flera tvetydiga analyser. Det faktum att kostnaderna är lokala för kontakterna och inte är en global egenskap hos algoritmen gör dem i huvudsak Markovian till sin natur.

Tilldelningen av en log-sannolikhet till länkar tillåter länkgrammatik att implementera det semantiska urvalet av predikat-argument-relationer. Det vill säga att vissa konstruktioner, även om de är syntaktiskt giltiga, är extremt osannolika. På detta sätt förkroppsligar länkgrammatik några av idéerna som finns i operatorgrammatik .

Eftersom kostnaderna är additiva, beter de sig som sannolikhetens logaritm (eftersom log-sannolikheter är additiva), eller på motsvarande sätt, ungefär som entropin ( eftersom entropier är additiva). Detta gör Link Grammar kompatibel med maskininlärningstekniker som dolda Markov-modeller och Viterbi-algoritmen , eftersom länkkostnaderna motsvarar länkvikterna i Markov-nätverk eller Bayesiska nätverk .

Typteori

Länkgrammatiklänktyperna kan förstås vara typerna i betydelsen typteori . I själva verket kan länkgrammatiken användas för att modellera det interna språket för vissa (icke-symmetriska) kompakta slutna kategorier , till exempel förgruppsgrammatik . I denna mening verkar Link Grammar vara isomorf eller homomorf för vissa kategorigrammatiker . Således kan t.ex. i en kategoriserad grammatik substantivfrasen " the bad boy " skrivas som

{{\text{the}} \atop {\text{NP/N,}}}{{\text{dålig}} \atop {\text{ N/N,}}}{{\text{pojke}} \top {\text{N}}}

medan motsvarande disjunkter i Link Grammar skulle vara

den: D+; dåligt: A+; pojke: D- & A-;

Sammandragningsreglerna (inferensregler) för Lambek-kalkylen kan mappas till anslutningen av kopplingar i Link Grammar. Riktningsindikatorerna + och - motsvarar snedstrecket framåt och bakåt i den kategoriska grammatiken. Slutligen kan enbokstavsnamnen A och D förstås som etiketter eller "lättlästa" mnemoniska namn för de ganska mer utförliga typerna NP/N , etc.

Den primära skillnaden här är då att de kategoriska grammatikerna har två typkonstruktorer , snedstrecket framåt och bakåt, som kan användas för att skapa nya typer (som NP/N ) från bastyper (som NP och N ). Länkgrammatik utelämnar användningen av typkonstruktörer, utan väljer istället att definiera en mycket större uppsättning bastyper med kompakta, lätta att komma ihåg minnesminnen.

Exempel

Exempel 1

En grundläggande regelfil för ett SVO-språk kan se ut så här:

<determiner><i>D+;</i> <b>D+;</b><noun-subject> <i>{D−} & S+;</i> <b>{D−} & S+;</b><noun-object> <i>{D−} & O−;</i> <b>{D−} & O−;</b><verb> <i>S− & {O+};</i> <b>S− & {O+};</b>

Således skulle den engelska meningen "The boy painted a picture" se ut som:

+-----O-----+ +-D-+--S--+ +--D--+ | | | | | Pojken målade en bild

Liknande tolkningar gäller för kinesiska.

Exempel 2

Omvänt kan en regelfil för ett SOV-språk med nullsubjekt bestå av följande länkar:

<noun-subject><i>S+;</i> <b>S+;</b><noun-object> <i>O+;</i> <b>O+;</b><verb> <i>{O−} & {S−};</i> <b>{O−} & {S−};</b>

Och en enkel persisk mening, man nAn xordam (من نان خوردم) "Jag åt bröd" skulle se ut så här:

+-----S-----+ | +--O--+ | | | man nAn xordam

VSO-order kan också tas emot, till exempel för arabiska.

Exempel 3 (morfologi)

I många språk med en konkatenativ morfologi spelar stammen ingen grammatisk roll; grammatiken bestäms av suffixen. ryska kan alltså meningen 'вверху плыли редкие облачка' ha tolkningen:

+------------Wd------------+--------------------SIp-------- -------+ | +-------EI------+ +--------Api-------+ | | +--LLCZD-+ +-LLAQZ+ +--LLCAO-+ | | | | | | | | VÄNSTER VÄGG вверху.e плы.= =ли.vnndpp ре.= =дкие.api облачк.= =а.ndnpi

De nedsänkta, såsom '.vnndpp', används för att indikera den grammatiska kategorin. De primära länkarna: Wd, EI, SIp och Api kopplar samman suffixen, eftersom i princip andra stammar skulle kunna förekomma här, utan att ändra meningens struktur. Api-länken indikerar adjektivet; SIp betecknar subjekt-verb inversion; EI är en modifierare. Wd-länken används för att indikera huvudsubstantivet; huvudverbet anges inte i denna mening. LLXXX-länkarna tjänar endast till att fästa stammar till suffix.

Exempel 4 (fonologi)

Länkgrammatiken kan också indikera fonologisk överensstämmelse mellan angränsande ord. Till exempel:

+---------Ost--------+ +------>WV------>+ +------Ds**x-- ---+ +----Wd---+-Ss*b-+ +--PHv-+----A----+ | | | | | | LEFT-WALL that.jp är.v ett abstrakt.ett koncept.n

Här används kopplingen 'PH' för att begränsa de bestämningsfaktorer som kan visas före ordet 'abstrakt'. Det blockerar effektivt (gör det dyrt) att använda bestämningsfaktorn 'a' i denna mening, medan länken till 'an' blir billig. De andra länkarna är ungefär som i tidigare exempel: S betecknar subjekt, O betecknar objekt, D betecknar bestämmare. 'WV'-länken anger huvudverbet och 'W'-länken anger huvudsubstantivet. De gemena bokstäverna som följer länktyperna med versaler tjänar till att förfina typen; så till exempel kan Ds bara ansluta till ett singular substantiv; Ss endast till ett singulart subjekt, Os till ett singularobjekt. Det gemena v i PHv betecknar 'vokal'; det gemena d i Wd betecknar en deklarativ mening.

Exempel 5 - vietnamesiska

Den vietnamesiska meningen "Bữa tiệc hôm qua là một thành công lớn" - "Festen i går var en stor framgång" kan tolkas på följande sätt:

Genomföranden

Länk grammatik syntax parser är ett bibliotek för naturlig språkbehandling skrivet i C . Den är tillgänglig under LGPL-licensen . Parsern är ett pågående projekt. De senaste versionerna inkluderar förbättrad meningstäckning, stöd för ryska, persiska och arabiska språk, prototyper för tyska, hebreiska, litauiska, vietnamesiska och turkiska, och programmerings-API:er för Python , Java , Common LISP , AutoIt och OCaml , med bindningar från tredje part för Perl , Ruby och JavaScript node.js .

Ett aktuellt stort företag är ett projekt för att lära sig grammatik och morfologi för nya språk, med hjälp av oövervakade inlärningsalgoritmer.

Länkparserprogrammet tillsammans med regler och ordlistor för engelska kan hittas i vanliga Linux-distributioner , t.ex. som ett Debianpaket , även om många av dessa är föråldrade årtal.

Ansökningar

AbiWord kontrollerar grammatik med Link Grammar

AbiWord , en gratis ordbehandlare , använder Link Grammar för direkt grammatikkontroll. Ord som inte kan länkas någonstans är understrukna med grönt.

Den semantiska relationsextraktorn RelEx, skiktad ovanpå Link Grammar-biblioteket, genererar en beroendegrammatikutdata genom att explicit de semantiska relationerna mellan ord i en mening. Dess utdata kan klassificeras som på en nivå mellan den för SSyntR och DSyntR of Meaning-Text Theory . Den tillhandahåller också inramning/jordning, anafora-upplösning , identifiering av huvudord, lexikal chunking , ordstyrd identifiering och taggning, inklusive taggning av entitet, datum, pengar, kön, etc.. Den innehåller ett kompatibilitetsläge för att generera beroendeutdata som är kompatibelt med Stanford-parsern och Penn Treebank -kompatibel POS-taggning .

Link Grammar har också använts för informationsextraktion av biomedicinska texter och händelser som beskrivs i nyhetsartiklar, samt experimentella maskinöversättningssystem från engelska till tyska, turkiska, indonesiska. och farsi.

Länkordboken för länkgrammatik används för att generera och verifiera den syntaktiska korrektheten hos tre olika system för att skapa naturliga språk : NLGen, NLGen2 och mikroplanerare/surrealistiskt. Det används också som en del av NLP-pipelinen i OpenCog AI-projektet.

Anteckningar

Vidare läsning

Scholia har en ämnesprofil för Link grammatik .

Schneider, Gerold (1998). "En språklig jämförelse valkrets, beroende och länkgrammatik" (PDF) . Magisteruppsats, universitetet i Zürich . Hämtad 2007-12-26 . {{ citera journal }} : Citera journal kräver |journal= ( hjälp )
Daniel Sleator & Davy Temperley (1993). "Parsing English with a Link Grammar" (PDF) . Tredje internationella workshopen om analysteknik .
Dennis Grinberg; John Lafferty; Daniel Sleator (september 1995). "En robust analysalgoritm för länkgrammatik" (PDF) . Proceedings of the Fourth International Workshop on Parsing Technologies . arXiv : cmp-lg/9508003 . Bibcode : 1995cmp.lg....8003G .

externa länkar

Den ursprungliga Link Grammar-hemsidan (som har ersatts av det nuvarande projektet .)
- Engelsk onlinedemonstration (för en äldre, inaktuell version; många buggar har åtgärdats sedan denna version.)
BioLG , en modifiering av Link Grammar Parser anpassad för den biomedicinska domänen (många, men inte alla, BioLG-förbättringar har visats tillbaka till huvudlänkgrammatikdistributionen).
Analysera meningar med Link Grammar and Python av Jeff Elmore på PyCon 2012

Språktillägg