Paper Info
Title
Learning languages from positive data and a finite number of queries
Abstract
A computational model for learning languages in the limit from full positive data and a bounded number of queries to the teacher (oracle) is introduced and explored. Equivalence, superset, and subset queries are considered (for the latter one we consider also a variant when the learner tests every conjecture, but the number of negative answers is uniformly bounded). If the answer is negative, the teacher may provide a counterexample. We consider several types of counterexamples: arbitrary, least counterexamples, the ones whose size is bounded by the size of positive data seen so far, and no counterexamples. A number of hierarchies based on the number of queries (answers) and types of answers/counterexamples is established. Capabilities of learning with different types of queries are compared. In most cases, one or two queries of one type can sometimes do more than any bounded number of queries of another type. Still, surprisingly, a finite number of subset queries is sufficient to simulate the same number of equivalence queries when behaviourally correct learners do not receive counterexamples and may have unbounded number of errors in almost all conjectures.
Year
DOI
Venue
2006
10.1016/j.ic.2005.09.001
Information & Computation
Keywords
Field
DocType
finite number,full positive data,subset query,bounded number,negative answer,different type,behaviourally correct learner,positive data,equivalence query,unbounded number,computer model
Discrete mathematics,Subset and superset,Finite set,Computer science,Oracle,Theoretical computer science,Equivalence (measure theory),Counterexample,Regular language,Hierarchy,Bounded function
Journal
Volume
Issue
ISSN
204
1
Information and Computation
ISBN
Citations 
PageRank 
3-540-24058-6
8
0.49
References 
Authors
27
2
Name
Order
Citations
PageRank
Sanjay Jain11647177.87
Efim Kinber242144.95