Name
Abstract | ||
|---|---|---|
We investigate a new paradigm in the context of learning in the limit, namely, learning correction grammars for classes of r.e. languages. Knowing a lan- guage may feature a representation of the target language in terms of two sets of rules (two grammars). The second grammar is used to make corrections to the rst grammar. Such a pair of grammars can be seen as a single description of (or grammar for) the language. We call such grammars correction grammars. Correction grammars capture 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 even in the TxtBc-model (where the learner is allowed to converge to innitely many syntactically distinct but correct conjectures in the limit). For each n 0, 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 trans- nite, using the idea of counting-down from notations for transnite constructive ordinals. This transnite extension can also be conceptualized as being about learn- ing Ershov-descriptions for r.e. langauges. Foru a notation in Kleene's general system (O;<o) of ordinal 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. lan- guages that can be TxtEx-learned by conjecturing v-correction grammars but not by conjecturing u-correction grammars. Surprisingly, we show that | above \!-many" corrections | it is not possible to strengthen the hierarchy: TxtEx-learningu-correction grammars of classes of r.e. lan- |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-72927-3_16 | Journal of Symbolic Logic |
Keywords | Field | DocType |
single correct correction grammar,n correction,ordinary grammar,u-correction grammar,correction grammar,v-correction grammar,w-correction grammar,u o v,similar learning advantage,grammars correction grammar | Tree-adjoining grammar,Context-sensitive grammar,Context-free grammar,L-attributed grammar,Definite clause grammar,Computer science,Indexed grammar,Phrase structure grammar,Artificial intelligence,Ambiguous grammar,Machine learning | Conference |
Volume | Issue | ISSN |
74 | 2 | 0302-9743 |
Citations | PageRank | References |
2 | 0.40 | 21 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lorenzo Carlucci | 1 | 66 | 8.56 |
| John Case | 2 | 239 | 21.40 |
| Sanjay Jain | 3 | 1647 | 177.87 |