A nyelvtan indukciós (grammar induction) tanulása annak feladata, hogy adatokból nyelvtant tanuljunk. Nyilvánvaló, hogy meg kell kísérelni, hiszen bebizonyosodott, hogy nagyon nehéz egy nyelvtant kézzel elkészíteni, és az interneten mintaként használható kijelentések milliárdjai állnak ingyenesen rendelkezésre. Ez egy nehéz feladat, mivel a lehetséges nyelvtanok tere végtelen, és azért is, mivel annak ellenőrzése, hogy egy adott nyelvtan generálja-e a mondatok egy adott halmazát, számításigényes feladat.

Egy érdekes modell a SEQUITUR-rendszer (Nevill-Manning és Witten, 1997). Nincs szüksége más bemenetre, csak egy szövegre (amit nem szükséges előzetesen mondatokra bontani). Egy nagyon specializált formátumú nyelvtant állít elő: egy olyan nyelvtant, amely csak egy karakterfüzért generál, nevezetesen az eredeti szöveget. Másképp tekintve a SEQUITUR épp csak arra elegendő nyelvtant tanul, hogy a szöveget elemezze. Íme, itt van az a zárójelezés, amit egy nagyobb, híreket tartalmazó szövegben levő mondatra felfedezett:

[Most Labour] [sentiment [[would still] [favor the] abolition]] [[of [the House]] [of Lords]]

Helyesen választott ki olyan összetevőket, mint például az „of the House of Lords” PP, bár a tradicionális elemzéssel ellentétesen dolgozik akkor például, amikor a „the”-t a megelőző igével és nem a követő főnévvel csoportosítja.

A SEQUITUR azon az ötleten alapszik, hogy egy jó nyelvtan egyben tömör is. A következő két kényszer betartása a legfontosabb: (1) Egymást követő szimbólumok egyetlen párja sem szerepelhet egynél többször a nyelvtanban. Ha az A B szimbólumpár több szabály jobb oldalán is szerepel, akkor ki kell cserélnünk a párt egy új, nem záró szimbólummal, amit C-nek nevezünk, és egy új szabályt kell bevezetnünk, miszerint C → A B. (2) Minden szabályt legalább kétszer kell használni. Ha egy C nem záró, csak egyszer szerepel a nyelvtanban, akkor törölnünk kell a C-re vonatkozó szabályt, és fel kell cserélnünk egyetlen előfordulását a szabály jobb oldalával. Ezt a két kényszert egy mohó keresés alkalmazza, amely a beérkező szöveget balról jobbra végignézi, menet közben inkrementálisan építi a nyelvtant, és alkalmazza a kényszereket, amint lehetséges. A 22.22. ábra mutatja az algoritmus működését az „abcdbcabcd” szövegen. Az algoritmus egy optimálisan tömör nyelvtant határoz meg a szöveghez.

A következő fejezetben további nyelvtant tanuló algoritmusokat is látni fogunk, amelyek valószínűségi alapú, környezetfüggetlen nyelvtanokkal működnek. Most azonban egy olyan nyelvtan tanulásának problémáját vizsgáljuk meg, amelyet szemantikával terjesztettünk ki. Mivel egy kiterjesztett nyelvtan egyben Horn-klóz logikai program is, ezért az induktív logikai programozás technikái megfelelők lesznek. A CHILL (Zelle és Mooney, 1996) egy induktív logikai programozás (ILP), amely példákból megtanul egy nyelvtant és egy arra specializált elemzőt. A célterület természetes nyelvű adatbázis-lekérdezések. A tanító példák szófüzérek, és a nekik megfelelő lekérdezések párjait tartalmazzák – például:

What is the capital of the state with the largest population?

Answer(c, Capital(s, c) ∧ Largest(p, State(s) ∧ Population(s, p)))

A CHILL feladata, hogy megtanuljon egy Parse(words, query) predikátumot, amely konzisztens a példákkal, és remélhetőleg más példákra is jól általánosít. Az ILP közvetlen alkalmazása ezen predikátum megtanulására gyenge teljesítményt hoz: a kikövetkeztetett elemző csak körülbelül 20%-os pontosságú. Szerencsére az ILP tanuló algoritmusok fejleszthetők tudás bevitelével. Ebben az esetben a Parse predikátum nagy részét logikai programként definiálták, és a CHILL feladatát a vezérlő szabályok kikövetkeztetésére redukálták, amelyek segítik az elemzőt a különböző elemzések közötti választásban. Ezzel a hozzáadott háttértudással a CHILL 70–85% közötti pontosságot ér el különböző adatbázis-lekérdezési feladatokon.

22.22. ábra - Az „abcdbcabcd” bemeneti szöveget elemző nyelvtant tartalmazó Sequitur-rendszer futási lépései. Egy S-re vonatkozó szabályból indulunk ki, és ezen szabály végéhez sorban minden egyes szimbólumot hozzáadunk. Miután a hatodik szimbólumot is hozzáadtuk, megkapjuk egy ismétlődő pár első előfordulását: bc. Ezért a bc mindkét előfordulását lecseréljük egy új nem záróra, A-ra, és egy új szabályt veszünk fel: A → bc. Miután három újabb szimbólumot hozzáraktunk a bemenethez, a kilencedik a bc egy újabb ismétlését eredményezi, így újra A-val helyettesítjük. Ez az aA két előfordulásához vezet, ezért egy új nem záróval, B-vel helyettesítjük. Miután a tizedik, utolsó szimbólumot is hozzáraktuk, Bd két előfordulását kapjuk, ezért lecseréljük őket egy új nem záróval, C-vel. De B immár csak egyszer szerepel, a C szabály jobb oldalán, ezért B-t a neki megfelelő bővítéssel, aA-val cseréljük le.