Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/39338
Title: Ordinal mind change complexity of language identification
Authors: Ambainis, A.
Jain, S. 
Sharma, A.
Keywords: Inductive inference
Mind change complexity
Ordinals
Issue Date: 1999
Source: Ambainis, A.,Jain, S.,Sharma, A. (1999). Ordinal mind change complexity of language identification. Theoretical Computer Science 220 (2) : 323-343. ScholarBank@NUS Repository.
Abstract: The approach of ordinal mind change complexity, introduced by Freivalds and Smith, uses (notations for) constructive ordinals to bound the number of mind changes made by a learning machine. This approach provides a measure of the extent to which a learning machine has to keep revising its estimate of the number of mind changes it will make before converging to a correct hypothesis for languages in the class being learned. Recently, this notion, which also yields a measure for the difficulty of learning a class of languages, has been used to analyze the learnability of rich concept classes. The present paper further investigates the utility of ordinal mind change complexity, It is shown that for identification from both positive and negative data and n ≥ 1, the ordinal mind change complexity of the class of languages formed by unions of up to n + 1 pattern languages is only ω x o notn(n) (where notn(n) is a notation for n, ω is a notation for the least limit ordinal and x o represents ordinal multiplication). This result nicely extends an observation of Lange and Zeugmann that pattern languages can be identified from both positive and negative data with 0 mind changes. Existence of an ordinal mind change bound for a class of learnable languages can be seen as an indication of its learning "tractability". Conditions are investigated under which a class has an ordinal mind change bound for identification from positive data. It is shown that an indexed family of languages has an ordinal mind change bound if it has finite elasticity and can be identified by a conservative machine. It is also shown that the requirement of conservative identification can be sacrificed for the purely topological requirement of M-finite thickness. Interaction between identification by monotonic strategies and existence of ordinal mind change bound is also investigated. © 1999 Elsevier Science B.V. All rights reserved.
Source Title: Theoretical Computer Science
URI: http://scholarbank.nus.edu.sg/handle/10635/39338
ISSN: 03043975
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

47
checked on Jan 21, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.