Grammatikinduktion (eller grammatisk inferens [1] ) är en maskininlärningsprocedur som återställer den formella grammatiken för ett språk baserat på en uppsättning observationer (exempel) med en känd tillhörighet till detta språk. Som ett resultat av proceduren byggs en modell av observerbara objekt i form av en uppsättning inferensregler eller genererande regler , en finit automat eller en automat av annan typ. Mer generellt är grammatisk slutledning ett av områdena för maskininlärning där exempelutrymmet består av diskreta kombinatoriska objekt som strängar, träd, grafer.
Grammatisk slutledning fokuserar ofta på problemet med att lära sig finita automater av olika typer (se artikeln Regular Language Induction för detaljer om dessa tillvägagångssätt), eftersom det har funnits effektiva algoritmer för att lösa detta problem sedan 1980-talet.
Sedan början av 2000-talet har dessa tillvägagångssätt utvidgats till uppgiften att sluta sig till sammanhangsfria grammatiker och rikare formalismer som flera sammanhangsfria grammatiker och parallella flera sammanhangsfria grammatiker. Andra klasser av grammatik för vilka grammatisk slutledning studerades studerades också för andra klasser av grammatik-kontextuell grammatik och mönsterspråk .
Den enklaste typen av inlärning är när inlärningsalgoritmen endast får en uppsättning exempel, och ibland motexempel, på orden i språket i fråga. Det finns andra inlärningsmodeller också. Ett av de ofta studerade alternativen är fallet när eleven kan fråga om ordets tillhörighet till språket, som till exempel i den exakta inlärningsmodellen eller den minimalt adekvata lärarmodellen som introducerats av Angluin [2] .
En mängd olika metoder för grammatisk slutledning har utvecklats. De två klassiska källorna är Fus artiklar från 1977 [3] och 1982 [4] . Duda, Hart och Stork [5] ägnade också ett litet avsnitt åt detta problem och citerar många källor. Den grundläggande trial and error-metoden de presenterade diskuteras nedan. För tillvägagångssätt för att underklassa vanliga språk , se i synnerhet Induction of Regular Languages . En nyare bok är de la Higueras (2010) [1] , som täcker teorin om grammatisk slutledning i vanliga språk och finita automater. D'Ulisia, Ferri och Grifoni [6] granskade forskning om inferensmetoder för naturliga språk.
Metoden som föreslås i avsnitt 8.7 i Dowd, Hart och Stork [5] föreslår sekventiell gissning av grammatiska regler och testning av dem mot positiva och negativa observationer. Regeluppsättningen utökas så att varje positivt exempel kan genereras, men om en given regeluppsättning genererar ett negativt exempel måste det kasseras. Detta speciella tillvägagångssätt kan beskrivas som "hypotestestning" och påminner något om versionsutrymmet Mitchells algoritm . Texten i artikeln av Dowd, Hart och Storck [5] ger ett enkelt exempel som illustrerar processen väl, men genomförbarheten av en sådan ostyrd trial and error-metod för större problem är tveksam.
Grammatisk slutledning med hjälp av evolutionära algoritmer är processen för evolution av representationen av målspråkets grammatik genom någon evolutionär process. Formell grammatik kan lätt representeras som träd av slutledningsregler som evolutionära operatorer kan tillämpas på. Algoritmer av detta slag har sitt ursprung i genetisk programmering , som pionjärer av John Koza . Andra tidiga arbeten på enkla formella språk använde en binär strängrepresentation av genetiska algoritmer, men den interna hierarkiska strukturen av grammatik som ligger till grund för språket Backus-Naur Augmented Form gör träd till ett mer flexibelt tillvägagångssätt.
Koza introducerade Lisp- program som träd. Han lyckades hitta analogier mellan genetiska operatörer och standardoperatörer på träd. Till exempel är subträdbyte likvärdigt med motsvarande process av genetisk korsning , där understrängar av den genetiska koden omvandlas till nästa generations individualitet. Giltighet mäts genom att utvärdera utgångskoden en Lisp - funktion . Liknande analogier mellan trädstrukturerna i Lisps representationer och trädrepresentationerna av grammatik gör tekniken att tillämpa genetisk programmering möjlig för grammatikinduktion.
När det gäller grammatikinduktion motsvarar överföringen av underträd utbyte av slutledningsregler, vilket gör det möjligt att analysera fraser för ett visst språk. Giltighetsoperatorn för en grammatik baseras på ett mått på hur väl den analyserar en grupp meningar från målspråket. I trädrepresentationen av grammatiken motsvarar terminalsymbolen för genereringsregeln ett blad av trädet. Dess överordnade nod matchar ett icke-terminalt tecken (som en substantivfras eller verbfras ) i regeluppsättningen. När allt kommer omkring kan rotnoden motsvara en sekvens av icke-terminaler.
Som alla giriga algoritmer fattar giriga slutledningsalgoritmer iterativt det beslut som verkar bäst i det skedet. Ett beslut förstås vanligtvis som att skapa en ny regel, ta bort en befintlig regel, välja en tillämplig regel, slå samman befintliga regler. Eftersom begreppen "scen" och "bäst" kan definieras på olika sätt har flera giriga slutledningsalgoritmer skapats.
Följande algoritmer för att generera kontextfria grammatiker fattar ett beslut efter att varje tecken läst:
Följande algoritmer för att generera sammanhangsfria grammatiker läser först hela teckensekvensen och börjar sedan fatta beslut:
Nyare tillvägagångssätt är baserade på distributivt lärande . Algoritmer som använder dessa tillvägagångssätt har använts för att lära ut sammanhangsfria grammatiker och något kontextkänsliga språk , och har visat sig vara korrekta och effektiva för stora underklasser av dessa grammatiker [7] [8]
Angluin definierade ett mönster som "en sträng av konstanta tecken från alfabetet Σ och variabla tecken från en disjunkt uppsättning". Språket för sådana mönster är uppsättningen av alla icke-tomma basexempel, det vill säga alla strängar som erhålls genom att på lämpligt sätt ersätta variabla tecken med icke-tomma strängar med konstanta tecken [not 1] . Ett mönster sägs vara beskrivande för en ändlig uppsättning strängar om dess språk är minimalt (med tanke på att mängden ingår) bland alla mönsterspråk, inklusive inmatningsuppsättningen.
Angluin har gett en polynomalgoritm för att beräkna, från en given ingångsuppsättning rader, alla beskrivande mönster från en enda variabel x[not 2] . För detta ändamål bygger hon en automat som representerar alla möjliga relevanta mönster. Genom att använda sofistikerade argument om ordlängder som bara beror på en enda variabel xkan antalet tillstånd reduceras avsevärt [9] .
Erlebach et al gav en effektivare version av Angluins mönsterinlärningsalgoritm, såväl som en parallell version av algoritmen [10] .
Arimura et al. har visat att en klass av språk som erhållits från en begränsad pool av prover kan tränas i polynomtid [11] .
Mönsterteori ( eng. mönsterteori ), formulerad av Ulf Grenander [12] , är en matematisk formalism för att beskriva kunskap om världen i form av mönster. Skillnaden mellan den föreslagna metoden för artificiell intelligens från andra är att den inte börjar med definitionen av algoritmer och maskiner för mönsterigenkänning och klassificering. Snarare föreskriver metoden en vokabulär för att formulera och skriva om mönster i exakt språk.
Utöver det nya algebraiska språket har ett nytt statistiskt tillvägagångssätt införts med syftet att:
Principerna för grammatikinduktion har tillämpats på andra aspekter av naturlig språkbehandling och (bland många andra uppgifter) på naturlig språkuppfattning [13] , exempelbaserad maskinöversättning [14] , morfemanalys och härledning av ortnamnens ursprung. Grammatikinduktion har också använts för förlustfri komprimering [15] och statistisk slutledning genom principerna för meddelanden med minsta längd och beskrivningar av minsta längd . Grammatikinduktion har också använts i vissa probabilistiska modeller för språkinlärning [16] .
| Maskininlärning och datautvinning | |
|---|---|
| Uppgifter | |
| Att lära sig med en lärare | |
| klusteranalys | |
| Dimensionalitetsreduktion | |
| Strukturell prognos | |
| Anomali upptäckt | |
| Grafisk probabilistiska modeller | |
| Neurala nätverk | |
| Förstärkningsinlärning |
|
| Teori | |
| Tidskrifter och konferenser |
|