Kieliopin induktio (tai kieliopin päättely [1] ) on koneoppimismenettely , joka palauttaa kielen muodollisen kieliopin havaintojen (esimerkkien) joukon perusteella, jossa on tähän kieleen kuuluva tunnetusti. Toimenpiteen tuloksena rakennetaan malli havaittavista objekteista päättelysääntöjoukon tai generointisäännön muodossa , äärellisen automaatin tai muun tyyppisen automaatin muodossa. Yleisemmin kieliopillinen päättely on yksi koneoppimisen alueista, jossa esimerkkiavaruus koostuu diskreeteistä kombinatorisista objekteista, kuten merkkijonoista, puista, kaavioista.
Kielioppipäätelmissä keskitytään usein erityyppisten äärellisten automaattien oppimisen ongelmaan (katso artikkelista Regular Language Induction saadaksesi lisätietoja näistä lähestymistavoista), koska tämän ongelman ratkaisemiseen on ollut tehokkaita algoritmeja 1980-luvulta lähtien.
2000-luvun alusta lähtien näitä lähestymistapoja on laajennettu päättelemään yhteydettömiä kielioppeja ja rikkaampia formalismeja, kuten useita yhteydettömiä kielioppeja ja rinnakkaisia useita yhteydettömiä kielioppeja. Muita kielioppiluokkia, joiden kielioppia tutkittiin, tutkittiin myös muille kielioppiluokille - kontekstuaalisia kielioppeja ja mallikieliä .
Yksinkertaisin oppimisen muoto on, kun oppimisalgoritmi vastaanottaa vain joukon esimerkkejä ja joskus vastaesimerkkejä kyseisen kielen sanoista. On myös muita oppimismalleja. Yksi usein tutkituista vaihtoehdoista on tapaus, jossa oppija voi kysyä sanan kuuluvuudesta kieleen, kuten esimerkiksi tarkassa oppimismallissa tai Angluinin esittämässä minimaalisesti riittävässä opettajamallissa [2] .
Kieliopin päättelyyn on kehitetty monenlaisia menetelmiä. Kaksi klassista lähdettä ovat Fu 1977 [3] ja 1982 [4] paperit . Duda, Hart ja Stork [5] omistivat myös pienen osan tälle ongelmalle ja lainaavat monia lähteitä. Niiden esittämää perusyritys- ja erehdysmenetelmää käsitellään alla. Erityisesti säännöllisten kielten alaluokituksen lähestymistapoja varten katso Säännöllisten kielten induktio . Uudempi kirja on de la Higueran (2010) [1] , joka kattaa kieliopillisen päättelyn teorian säännöllisissä kielissä ja äärellisissä automaateissa. D'Ulisia, Ferri ja Grifoni [6] tarkastelivat luonnollisten kielten päättelymenetelmiä koskevaa tutkimusta.
Dowdin, Hartin ja Storkin [5] luvussa 8.7 ehdotettu menetelmä ehdottaa kielioppisääntöjen peräkkäistä arvausta ja niiden testaamista positiivisten ja negatiivisten havaintojen suhteen. Sääntöjoukkoa laajennetaan siten, että jokainen positiivinen esimerkki voidaan luoda, mutta jos tietty sääntöjoukko luo negatiivisen esimerkin, se on hylättävä. Tätä erityistä lähestymistapaa voidaan kuvata "hypoteesitestaukseksi" ja se on jossain määrin samanlainen kuin versioavaruuden Mitchellin algoritmi . Dowdin, Hartin ja Storckin artikkelin teksti [5] antaa yksinkertaisen esimerkin, joka havainnollistaa prosessia hyvin, mutta tällaisen ohjaamattoman yrityksen ja erehdyksen toteutettavuus suurempiin ongelmiin on kyseenalainen.
Evoluutioalgoritmien avulla tehtävä kielioppi on kohdekielen kieliopin esityksen evoluutioprosessi jonkin evoluutioprosessin kautta. Muodolliset kieliopit voidaan helposti esittää päättelysääntöjen puina , joihin voidaan soveltaa evolutionaarisia operaattoreita. Tämän tyyppiset algoritmit juontavat juurensa geneettisestä ohjelmoinnista , jonka edelläkävijä oli John Koza . Muissa varhaisissa yksinkertaisia muodollisia kieliä koskevissa töissä käytettiin geneettisten algoritmien binäärimerkkijonoesitystä, mutta Backus-Naur Augmented Form -kielen taustalla oleva kielioppien sisäinen hierarkkinen rakenne tekee puista joustavamman lähestymistavan.
Koza esitteli Lisp- ohjelmat puita. Hän onnistui löytämään analogioita geneettisten operaattoreiden ja tavallisten puiden operaattorien joukosta. Esimerkiksi alipuiden vaihto vastaa vastaavaa geneettisen risteytyksen prosessia , jossa geneettisen koodin osajonot muunnetaan seuraavan sukupolven yksilöllisyydeksi. Kelvollisuus mitataan arvioimalla funktion lähtökoodia . Samanlaiset analogiat Lispin esitysten puurakenteiden ja kielioppien puuesitysten välillä tekevät geneettisen ohjelmoinnin soveltamistekniikan mahdolliseksi kieliopin induktiossa.
Kieliopin induktion tapauksessa alipuiden siirto vastaa päättelysääntöjen vaihtoa, mikä mahdollistaa tietyn kielen lauseiden jäsentämisen. Kieliopin kelpoisuusoperaattori perustuu johonkin mittaan siitä, kuinka hyvin se jäsentää jonkin lauseryhmän kohdekielestä. Kieliopin puuesityksessä generointisäännön päätesymboli vastaa puun lehteä. Sen pääsolmu vastaa sääntöjoukon muuta kuin päätemerkkiä (kuten substantiivilausetta tai verbilausetta ). Loppujen lopuksi juurisolmu voi vastata ei-terminaalien sarjaa.
Kuten kaikki ahneet algoritmit , ahneet päättelyalgoritmit tekevät iteratiivisesti päätöksen, joka näyttää parhaimmalta siinä vaiheessa. Päätös ymmärretään yleensä uuden säännön luomiseksi, olemassa olevan säännön poistamiseksi, sovellettavan säännön valitsemiseksi, olemassa olevien sääntöjen yhdistämiseksi. Koska käsitteet "vaihe" ja "paras" voidaan määritellä eri tavoin, on luotu useita ahneita päättelyalgoritmeja.
Seuraavat algoritmit yhteydettömän kieliopin luomiseksi tekevät päätöksen jokaisen luetun merkin jälkeen:
Seuraavat algoritmit yhteydettömän kieliopin luomiseksi lukevat ensin koko merkkisarjan ja alkavat sitten tehdä päätöksiä:
Uudemmat lähestymistavat perustuvat distributiiviseen oppimiseen . Näitä lähestymistapoja käyttäviä algoritmeja on sovellettu yhteydettömien kielioppien ja hieman kontekstiherkkien kielten opettamiseen , ja ne on osoittautunut oikeiksi ja tehokkaiksi näiden kielioppien suurille alaluokille [7] [8]
Angluin määritteli kuvion "aakkoston Σ vakiomerkkien ja epäyhtenäisen joukon muuttuvien merkkien merkkijonoksi". Tällaisten mallien kieli on joukko ei-tyhjiä kantaesimerkkejä, eli kaikki merkkijonot, jotka on saatu korvaamalla muuttujan merkit asianmukaisesti ei-tyhjillä vakiomerkkien merkkijonoilla [huomautus 1] . Kuvion sanotaan kuvaavan äärellistä merkkijonojoukkoa, jos sen kieli on minimaalinen (jossa on mukana) kaikkien kuviokielten joukossa, mukaan lukien syöttöjoukko.
Angluin on antanut polynomialgoritmin laskea annetusta rivien joukosta kaikki kuvaavat kuviot yhdestä muuttujasta x[huomautus 2] . Tätä tarkoitusta varten hän rakentaa automaatin, joka edustaa kaikkia mahdollisia relevantteja kuvioita. Käyttämällä kehittyneitä argumentteja sanojen pituuksista, jotka riippuvat vain yhdestä muuttujasta x, tilojen määrää voidaan vähentää merkittävästi [9] .
Erlebach ym. antoivat tehokkaamman version Angluinin mallioppimisalgoritmista sekä rinnakkaisversion algoritmista [10] .
Arimura ym. ovat osoittaneet, että rajoitetusta näytejoukosta saatuja kieliä voidaan opettaa polynomiajassa [11] .
Ulf Grenanderin [12] muotoilema kuvioteoria ( eng. pattern theory ) , on matemaattinen formalismi maailmaa koskevan tiedon kuvaamiseksi kuvioiden muodossa. Tekoälyn ehdotetun lähestymistavan eromuihin verrattuna on se, että se ei ala hahmontunnistuksen ja luokituksen algoritmien ja koneiden määrittelystä. Pikemminkin menetelmä määrää sanaston kuvioiden muotoilua ja uudelleenkirjoittamista varten tarkalla kielellä.
Uuden algebrallisen kielen lisäksi on otettu käyttöön uusi tilastollinen lähestymistapa, jonka tavoitteena on:
Kieliopin induktion periaatteita on sovellettu muihin luonnollisen kielen käsittelyn näkökohtiin ja (monien muiden tehtävien ohella) luonnollisen kielen havaitsemiseen [13] , esimerkkipohjaiseen konekäännökseen [14] , morfeemianalyysiin ja kielen johtamiseen. paikannimien alkuperä. Kieliopin induktiota on käytetty myös häviöttömään pakkaamiseen [15] ja tilastolliseen päättelyyn minimipituusviestien ja minimipituuskuvausten periaatteiden kautta . Kieliopin induktiota on käytetty myös joissakin todennäköisyyspohjaisissa kielen hankinnan malleissa [16] .
| Koneoppiminen ja tiedon louhinta | |
|---|---|
| Tehtävät | |
| Opettajan kanssa oppimista | |
| ryhmäanalyysi | |
| Mittasuhteiden vähentäminen | |
| Rakenteellinen ennustaminen | |
| Anomalian havaitseminen | |
| Piirrä todennäköisyysmallit | |
| Neuroverkot | |
| Vahvistusoppiminen |
|
| Teoria | |
| Lehdet ja konferenssit |
|