Indukce gramatiky (neboli gramatická inference [1] ) je procedura strojového učení , která obnovuje formální gramatiku jazyka na základě souboru pozorování (příkladů) se známou příslušností k tomuto jazyku. Výsledkem procedury je sestavení modelu pozorovatelných objektů ve formě sady inferenčních pravidel nebo generujících pravidel , konečného automatu nebo automatu jiného typu. Obecněji je gramatické vyvozování jednou z oblastí strojového učení, ve kterém se příkladový prostor skládá z diskrétních kombinatorických objektů, jako jsou řetězce, stromy, grafy.
Gramatický závěr se často zaměřuje na problém učení konečných automatů různých typů (viz článek Regular Language Induction pro podrobnosti o těchto přístupech), protože od 80. let existují účinné algoritmy pro řešení tohoto problému.
Od počátku roku 2000 byly tyto přístupy rozšířeny na úkol odvodit bezkontextové gramatiky a bohatší formalismy, jako jsou vícenásobné bezkontextové gramatiky a paralelní vícenásobné bezkontextové gramatiky. Jiné třídy gramatik , pro které byla studována gramatická inference , byly také studovány pro další třídy gramatik -- kontextové gramatiky a vzorové jazyky .
Nejjednodušším druhem učení je, když algoritmus učení přijímá pouze sadu příkladů a někdy i protipříklady slov daného jazyka. Existují i jiné modely učení. Jednou z často zkoumaných alternativ je případ, kdy se žák může ptát na příslušnost slova k jazyku, jako například v exaktním modelu učení nebo minimálně adekvátním modelu učitele, který zavedl Angluin [2] .
Byla vyvinuta široká škála metod pro gramatické vyvozování. Dva klasické zdroje jsou Fuovy práce z roku 1977 [3] a 1982 [4] . Duda, Hart a Stork [5] také věnovali malou část tomuto problému a citují mnoho zdrojů. Základní metoda pokusu a omylu, kterou představili, je diskutována níže. Pro přístupy k podtřídění regulárních jazyků , zejména viz Induction of Regular Languages . Novější knihou je de la Higuera's (2010) [1] , která se zabývá teorií gramatické inference v regulárních jazycích a konečných automatech. D'Ulisia, Ferri a Grifoni [6] zhodnotili výzkum inferenčních metod pro přirozené jazyky.
Metoda navržená v sekci 8.7 Dowd, Hart a Stork [5] navrhuje postupné hádání gramatických pravidel a jejich testování proti pozitivním a negativním pozorováním. Sada pravidel je rozšířena tak, aby bylo možné vygenerovat každý pozitivní příklad, ale pokud daná sada pravidel vygeneruje negativní příklad, musí být zrušena. Tento konkrétní přístup lze popsat jako „testování hypotéz“ a je poněkud podobný Mitchellovu algoritmu . Text článku Dowda, Harta a Storcka [5] uvádí jednoduchý příklad, který proces dobře ilustruje, ale proveditelnost takového neřízeného přístupu pokusů a omylů u větších problémů je sporná.
Gramatické vyvozování pomocí evolučních algoritmů je proces evoluce reprezentace gramatiky cílového jazyka prostřednictvím nějakého evolučního procesu. Formální gramatiky lze snadno reprezentovat jako stromy inferenčních pravidel, na které lze aplikovat evoluční operátory. Algoritmy tohoto druhu mají svůj původ v genetickém programování , jehož průkopníkem byl John Koza . Jiné rané práce na jednoduchých formálních jazycích používaly binární řetězcovou reprezentaci genetických algoritmů, ale vnitřní hierarchická struktura gramatik, která je základem jazyka Backus-Naur Augmented Form , činí stromy flexibilnějším přístupem.
Koza představil Lisp programy jako stromy. Podařilo se mu najít analogie mezi genetickými operátory ke standardním operátorům na stromech. Například záměna podstromů je ekvivalentní odpovídajícímu procesu genetického křížení , kde jsou podřetězce genetického kódu převedeny na individualitu další generace. Platnost se měří vyhodnocením výstupního kódu Lisp . Podobné analogie mezi stromovými strukturami Lispových reprezentací a stromovými reprezentacemi gramatik umožňují techniku použití genetického programování pro indukci gramatiky.
V případě indukce gramatiky přenos podstromů odpovídá výměně inferenčních pravidel, což umožňuje analyzovat fráze určitého jazyka. Operátor platnosti pro gramatiku je založen na určité míře toho, jak dobře analyzuje určitou skupinu vět z cílového jazyka. Ve stromové reprezentaci gramatiky odpovídá koncový symbol generujícího pravidla listu stromu. Jeho nadřazený uzel se shoduje s neterminálním znakem (jako je fráze podstatného jména nebo fráze slovesa ) v sadě pravidel. Koneckonců, kořenový uzel může odpovídat posloupnosti neterminálů.
Stejně jako všechny chamtivé algoritmy , i chamtivé inferenční algoritmy opakovaně přijímají rozhodnutí, které se v dané fázi jeví jako nejlepší. Rozhodnutí je obvykle chápáno jako vytvoření nového pravidla, smazání existujícího pravidla, výběr použitelného pravidla, sloučení existujících pravidel. Protože pojmy „stage“ a „best“ mohou být definovány různými způsoby, bylo vytvořeno několik chamtivých inferenčních algoritmů.
Následující algoritmy pro generování bezkontextových gramatik se rozhodují po přečtení každého znaku:
Následující algoritmy pro generování bezkontextových gramatik nejprve přečtou celou sekvenci znaků a poté začnou rozhodovat:
Novější přístupy jsou založeny na distributivním učení . Algoritmy využívající tyto přístupy byly aplikovány na výuku bezkontextových gramatik a mírně kontextově citlivých jazyků a ukázalo se, že jsou správné a efektivní pro velké podtřídy těchto gramatik [7] [8]
Angluin definoval vzor jako „řetězec konstantních znaků z abecedy Σ a proměnných znaků z disjunktní množiny“. Jazykem takových vzorů je množina všech neprázdných základních příkladů, tedy všech řetězců získaných vhodným nahrazením proměnných znaků neprázdnými řetězci konstantních znaků [poznámka 1] . O vzoru se říká , že je popisný pro konečnou množinu řetězců, pokud je jeho jazyk minimální (vzhledem k zahrnutí množiny) mezi všemi jazyky vzorů, včetně vstupní množiny.
Angluin dal polynomiální algoritmus pro výpočet všech popisných vzorů z jedné proměnné z dané vstupní sady řádků x[poznámka 2] . Za tímto účelem sestaví automat představující všechny možné relevantní vzory. Pomocí sofistikovaných argumentů o délkách slov, které závisí pouze na jedné proměnné x, lze počet stavů výrazně snížit [9] .
Erlebach et al poskytli efektivnější verzi Angluinova algoritmu pro učení vzorů a také paralelní verzi algoritmu [10] .
Arimura et al. ukázali, že třídu jazyků získanou z omezeného souboru vzorků lze trénovat v polynomiálním čase [11] .
Teorie vzorů ( angl. pattern theory ), formulovaná Ulfem Grenanderem [12] , je matematický formalismus pro popis znalostí o světě ve formě vzorů. Rozdíl navrhovaného přístupu k umělé inteligenci od ostatních spočívá v tom, že nezačíná definicí algoritmů a strojů pro rozpoznávání a klasifikaci vzorů. Metoda spíše předepisuje slovní zásobu pro formulování a přepisování vzorů v přesném jazyce.
Kromě nového algebraického jazyka byl zaveden nový statistický přístup s cílem:
Principy indukce gramatiky byly aplikovány na další aspekty zpracování přirozeného jazyka a (mezi mnoha jinými úkoly) na percepci přirozeného jazyka [13] , strojový překlad založený na příkladech [14] , analýzu morfémů a odvozování původ místních jmen. Gramatická indukce byla také použita pro bezeztrátovou kompresi [15] a statistické vyvozování prostřednictvím principů minimální délky zpráv a popisů minimální délky . Indukce gramatiky byla také použita v některých pravděpodobnostních modelech osvojování jazyka [16] .
| Strojové učení a dolování dat | |
|---|---|
| Úkoly | |
| Učení s učitelem | |
| shluková analýza | |
| Redukce rozměrů | |
| Strukturální prognózy | |
| Detekce anomálií | |
| Grafové pravděpodobnostní modely | |
| Neuronové sítě | |
| Posílení učení |
|
| Teorie | |
| Časopisy a konference |
|