A nyelvtani indukció (vagy grammatikai következtetés [1] ) egy olyan gépi tanulási eljárás, amely megfigyelések (példák) halmaza alapján állítja vissza egy nyelv formális nyelvtanát egy ismert ehhez a nyelvhez tartozóval. Az eljárás eredményeként megfigyelhető objektumok modellje épül fel következtetési szabályok halmaza vagy generáló szabályok , véges automata vagy más típusú automata formájában. Általánosabban, a grammatikai következtetés a gépi tanulás egyik olyan területe, ahol a példatér diszkrét kombinatorikus objektumokból áll, mint például karakterláncok, fák, gráfok.
A nyelvtani következtetés gyakran a különböző típusú véges automaták tanulásának problémájára összpontosít (a megközelítések részleteit lásd a Regular Language Induction cikkben ), mivel az 1980-as évek óta léteznek hatékony algoritmusok a probléma megoldására.
A 2000-es évek eleje óta ezeket a megközelítéseket kiterjesztették a kontextusmentes nyelvtanok és gazdagabb formalizmusok, például a többszörös kontextusmentes nyelvtanok és a párhuzamos többszörös kontextusmentes nyelvtanok következtetésére. A nyelvtani következtetések más osztályait is tanulmányozták más nyelvtani osztályokhoz – kontextuális nyelvtanokhoz és mintanyelvekhez .
A tanulás legegyszerűbb fajtája az, amikor a tanulási algoritmus csak egy sor példát, néha pedig ellenpéldákat kap a szóban forgó nyelv szavaira. Vannak más tanulási modellek is. Az egyik gyakran vizsgált alternatíva az az eset, amikor a tanuló rákérdezhet a szó nyelvhez való tartozására, mint például az egzakt tanulási modellben vagy az Angluin által bevezetett minimálisan adekvát tanári modellben [2] .
A nyelvtani következtetésre sokféle módszert fejlesztettek ki. A két klasszikus forrás Fu 1977-es [3] és 1982 -es [4] cikkei . Duda, Hart és Stork [5] is szentelt egy kis részt ennek a problémának, és számos forrást idéz. Az alábbiakban ismertetjük az általuk bemutatott alapvető próba és hiba módszert. A reguláris nyelvek alosztályozásának megközelítéseiért lásd : Reguláris nyelvek indukciója . Egy újabb könyv de la Higuera (2010) [1] , amely a reguláris nyelvek és véges automaták grammatikai következtetéseinek elméletét fedi le. D'Ulisia, Ferri és Grifoni [6] áttekintette a természetes nyelvekre vonatkozó következtetési módszerekkel kapcsolatos kutatásokat.
A Dowd, Hart és Stork [5] 8.7. szakaszában javasolt módszer a nyelvtani szabályok szekvenciális kitalálását és tesztelését javasolja a pozitív és negatív megfigyelések alapján. A szabálykészlet kibővül, így minden pozitív példa generálható, de ha egy adott szabálykészlet negatív példát generál, akkor azt el kell vetni. Ez a sajátos megközelítés "hipotézis tesztelésnek" nevezhető, és némileg hasonlít a verziótér Mitchell algoritmusához . Dowd, Hart és Storck cikkének [5] szövege egy egyszerű példát ad, amely jól szemlélteti a folyamatot, de az ilyen irányítatlan próbálkozás és hiba megközelítés megvalósíthatósága nagyobb problémák esetén megkérdőjelezhető.
Az evolúciós algoritmusok segítségével történő grammatikai következtetés az a folyamat, amely során a célnyelv nyelvtanának reprezentációja valamilyen evolúciós folyamaton keresztül fejlődik. A formális nyelvtanok könnyen ábrázolhatók következtetési szabályok fájaként , amelyekre evolúciós operátorokat lehet alkalmazni. Az ilyen típusú algoritmusok a genetikai programozásból származnak , amelynek úttörője John Koza volt . Az egyszerű formális nyelveken végzett más korai munkák a genetikai algoritmusok bináris karakterlánc-reprezentációját használták, de a nyelvtanok belső hierarchikus struktúrája, amely a Backus-Naur kiterjesztett formanyelv alapja , rugalmasabb megközelítést tesz lehetővé a fák számára.
Koza fákként mutatta be a Lisp programokat. Sikerült analógiákat találnia a genetikai operátorok és a fák standard operátorai között. Például a részfa cseréje egyenértékű a megfelelő genetikai keresztezési folyamattal , ahol a genetikai kód részsztringjei a következő generáció egyéniségévé alakulnak. egy Lisp függvény kimeneti kódjának kiértékelésével mérjük . A Lisp-féle reprezentációk fastruktúrái és a nyelvtanok faábrázolásai közötti hasonló analógiák lehetővé teszik a genetikai programozás alkalmazásának technikáját a nyelvtani indukcióhoz.
Nyelvtani indukció esetén a részfák átvitele megfelel a következtetési szabályok cseréjének, ami lehetővé teszi egy bizonyos nyelv frázisainak elemzését. A nyelvtan érvényességi operátora azon alapul, hogy mennyire jól értelmezi a célnyelv bizonyos mondatcsoportjait. A nyelvtan faábrázolásában a generáló szabály terminális szimbóluma a fa levelének felel meg. Szülőcsomópontja megegyezik egy nem terminális karakterrel (például főnévi kifejezéssel vagy igei kifejezéssel ) a szabálykészletben. Végül is a gyökércsomópont megfelelhet nem terminálisok sorozatának.
Mint minden mohó algoritmus , a mohó következtetési algoritmusok is iteratív módon hozzák meg azt a döntést, amely abban a szakaszban a legjobbnak tűnik. Döntés alatt általában új szabály létrehozását, meglévő szabály törlését, alkalmazandó szabály kiválasztását, meglévő szabályok összevonását értjük. Mivel a "színpad" és a "legjobb" fogalmak különbözőképpen definiálhatók, számos mohó következtetési algoritmust hoztak létre.
A kontextusmentes nyelvtanok létrehozására szolgáló alábbi algoritmusok minden karakter beolvasása után döntenek:
A következő algoritmusok a környezetmentes nyelvtanok generálására először beolvassák a teljes karaktersorozatot, majd elkezdenek döntéseket hozni:
Az újabb megközelítések a disztributív tanuláson alapulnak . Az ezeket a megközelítéseket használó algoritmusokat kontextusmentes nyelvtanok és enyhén kontextusérzékeny nyelvek tanítására alkalmazták , és helyesnek és hatékonynak bizonyultak e nyelvtanok nagy alosztályaiban [7] [8]
Angluin a mintát a következőképpen definiálta : "az Σ ábécé állandó karakterei és egy diszjunkt halmaz változó karakterei ". Az ilyen minták nyelve az összes nem üres alappélda halmaza, vagyis minden olyan karakterlánc, amelyet úgy kapunk, hogy a változó karaktereket megfelelően helyettesítjük állandó karakterekből álló nem üres karakterláncokkal [1. megjegyzés] . Egy mintát akkor mondunk leírónak egy véges karakterlánchalmazt, ha a nyelve minimális (adott halmazba foglalva) az összes mintanyelv között, beleértve a bemeneti halmazt is.
Angluin adott egy polinomiális algoritmust , amely egy adott bemeneti sorkészletből az összes leíró mintát egyetlen változóból számítja ki x[2. megjegyzés] . Ebből a célból egy automatát épít, amely az összes lehetséges releváns mintát reprezentálja. A szóhosszúságra vonatkozó kifinomult argumentumokkal, amelyek csak egyetlen változótól függenek x, az állapotok száma jelentősen csökkenthető [9] .
Erlebach és munkatársai megadták az Angluin-féle minta-tanuló algoritmus egy hatékonyabb változatát, valamint az algoritmus párhuzamos változatát [10] .
Arimura és munkatársai kimutatták, hogy a korlátozott mintákból nyert nyelvek egy osztálya polinomiális időben tanítható [11] .
( eng. pattern theory ) , amelyet Ulf Grenander [12] fogalmazott meg , egy matematikai formalizmus a világgal kapcsolatos ismeretek minták formájában történő leírására. A mesterséges intelligencia javasolt megközelítésének különbsége atöbbitől az, hogy nem a mintafelismerésre és osztályozásra szolgáló algoritmusok és gépek meghatározásával kezdődik. A módszer inkább egy szókincset ír elő a minták pontos nyelvezetű megfogalmazásához és átírásához.
Az új algebrai nyelv mellett egy új statisztikai megközelítést vezettek be, amelynek célja:
A nyelvtani indukció elveit alkalmazták a természetes nyelvi feldolgozás más aspektusaiban , és (sok más feladat mellett) a természetes nyelvészlelésben [13] , a példaalapú gépi fordításban [14] , a morfémaelemzésben és a helynevek eredete. A nyelvtani indukciót veszteségmentes tömörítésre [15] és statisztikai következtetésekre is használták a minimális hosszúságú üzenetek és a minimális hosszúságú leírások elvein keresztül . A nyelvtani indukciót a nyelvelsajátítás néhány valószínűségi modelljében is alkalmazták [16] .
| Gépi tanulás és adatbányászat | |
|---|---|
| Feladatok | |
| Tanulás tanárral | |
| klaszteranalízis | |
| Dimenziócsökkentés | |
| Strukturális előrejelzés | |
| Anomália észlelése | |
| Grafikon valószínűségi modellek | |
| Neurális hálózatok | |
| Megerősítő tanulás |
|
| Elmélet | |
| Folyóiratok és konferenciák |
|