Learning Correction Grammars

dc.contributor.authorCARLUCCI, Lorenzoen_US
dc.contributor.authorCASE, Johnen_US
dc.contributor.authorJAIN, Sanjayen_US
dc.date.accessioned2006-12-18T03:22:00Zen_US
dc.date.accessioned2017-01-23T06:59:54Z
dc.date.available2006-12-18T03:22:00Zen_US
dc.date.available2017-01-23T06:59:54Z
dc.date.issued2006-12-18T03:22:00Zen_US
dc.description.abstractWe investigate a new paradigm in the context of learning in the limit, namely, learning correction grammars for classes of r.e. languages. Knowing a language may feature a representation of the target language in terms of two sets of rules (two grammars). The second grammar is used to edit errors of (make corrections to) the first grammar. Such a pair of two grammars can be seen as a single description of (or grammar for) the language. We call such grammars correction grammars. Correction grammars can be thought of as capturing the observable fact that people do correct their linguistic utterances during their usual linguistic activities. Is the need for self-corrections implied by using correction grammars instead of normal grammars compensated by a learning advantage? We show that learning correction grammars for classes of r.e. languages in the TxtEx-model (i.e., converging to a single correct correction grammar in the limit) is sometimes more powerful than learning ordinary grammars in the TxtBc-model (where the learner is allowed to converge to infinitely many syntactically distinct but correct conjectures in the limit). For each n, there is a similar learning advantage, again in learning correction grammars for classes of r.e. languages, but where we compare learning correction grammars that make n+1 corrections to those that make $n$ corrections. The concept of a correction grammar can be extended into the constructive transfinite by employing the idea of counting-down from notations for transfinite constructive ordinals. For u a notation in Kleene's system (O,<_o) of notations for constructive ordinals, we introduce the concept of an u-correction grammar, where u is used to bound the number of corrections that the grammar is allowed to make. We prove a general hierarchy result: if u and v are notations for constructive ordinals such that u <_o v, then there are classes of r.e. languages that can be TxtEx-learned by conjecturing v-correction grammars but not by conjecturing u-correction grammars. Surprisingly, we show that --- above omega-many corrections --- it is not possible to strengthen the hierarchy: TxtEx-learning u-correction grammars of classes of r.e. languages, where u is a notation in O for any ordinal, can be simulated by TxtBc-learning w-correction grammars, where w is any notation for the smallest infinite ordinal omega.en_US
dc.format.extent685253 bytesen_US
dc.format.mimetypeapplication/pdfen_US
dc.identifier.urihttps://dl.comp.nus.edu.sg/xmlui/handle/1900.100/2307en_US
dc.language.isoenen_US
dc.relation.ispartofseriesTR12/06en_US
dc.titleLearning Correction Grammarsen_US
dc.typeTechnical Reporten_US
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
TR12-06.pdf
Size:
669.19 KB
Format:
Adobe Portable Document Format
Description:
License bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
license.txt
Size:
1.53 KB
Format:
Plain Text
Description: