Automatic learning from positive data and negative counterexamples
The contribution discusses learnability in the limit of language classes from positive data and limited counterexamples. In their learning scenario the learner is presented with a stream of positive examples from the language that eventually presents every member of the language. At each step, the learner can return a hypothesis, which triggers a counterexample reply provided that the hypothesis contains an element that does not belong to the language to be learned. In this case the counterexample reply returns a member of the hypothesis language that is not a member of the language to be learned according to certain criteria (any, the least according to some total order, or some particularly small counterexample according to some size). In earlier work [the first author et al., J. Comput. Syst. Sci. 78, No. 6, 1910--1927 (2012; Zbl 1250.68137)] an automatic variant of this learning scenario without the counterexamples was introduced. In the automatic learnability the learner is restricted to be automatic, which means that its computed function is a regular relation (i.e., recognized by a finite automaton). Additionally, the authors also place memory restrictions on the learner. In the earlier work it was demonstrated that automatic learners are rather weak based on positive data alone. In the present work, this investigation is extended to the scenario that includes counterexamples. It is demonstrated that typically all automatic classes can be learned in this manner. The memory of the learner can even be restricted to the length of the longest datum seen so far without effect on the learnability. Only in the scenario in which the counterexample returned is bounded in size by the length of the longest datum seen so far a restricted learnability is observed. The authors present a characterization of the languages that can be successfully learned despite these severe restrictions. In conjunction with memory restrictions on the learner the situation becomes more involved and the authors also present results for these setups, which are still reasonably powerful. The paper is well written and should be generally understandable by anyone with a graduate level understanding of basic automata theory. The text is generally focussed on definitions and results, but motivation is provided in the text. Since most proofs are rather constructive in nature, additional examples are not much missed.
- Automatic learning from positive data and negative counterexamples
- Learning from Positive Data and Negative Counterexamples: A Survey
- Algorithmic Learning Theory
- Learning languages from positive data and negative counterexamples
- Learning languages from positive data and a limited number of short counterexamples
- A machine discovery from amino acid sequences by decision trees over regular patterns
- A theory of formal synthesis via inductive learning
- Analogical and inductive inference. International workshop AII '89, Reinhardsbrunn Castle, GDR, October 1-6, 1989. Proceedings
- Automatic functions, linear time and learning
- Automatic learning from positive data and negative counterexamples
- Characteristics of minimal effective programming systems
- Closed choice and a uniform low basis theorem
- Difficulties in Forcing Fairness of Polynomial Time Inductive Inference
- Distributional learning of parallel multiple context-free grammars
- Even linear simple matrix languages: formal language properties and grammatical inference.
- Finding patterns common to a set of strings
- scientific article; zbMATH DE number 3932417 (Why is no real title available?)
- scientific article; zbMATH DE number 3539202 (Why is no real title available?)
- scientific article; zbMATH DE number 408771 (Why is no real title available?)
- scientific article; zbMATH DE number 517033 (Why is no real title available?)
- scientific article; zbMATH DE number 1948150 (Why is no real title available?)
- scientific article; zbMATH DE number 2085171 (Why is no real title available?)
- scientific article; zbMATH DE number 806750 (Why is no real title available?)
- Independence Results for n-Ary Recursion Theorems
- Inductive inference of formal languages from positive data
- Iterative learning from positive data and negative counterexamples
- Language identification in the limit
- Language learning from texts: Mindchanges, limited memory and monotonicity
- Learnability of automatic classes
- Learning elementary formal systems
- Learning erasing pattern languages with queries
- Learning languages from positive data and negative counterexamples
- Learning recursive languages from good examples
- Learning regular languages from counterexamples
- Learning via queries in [+, <]
- Monotonic and non-monotonic inductive inference
- On automatic families
- On the impact of forgetting on learning machines
- Polynomial inference of universal automata from membership and equivalence queries
- Probabilistic computability and choice
- Queries and concept learning
- Relations between Gold-style learning and query learning
- Rich classes inferable from positive data: Length-bounded elementary formal systems
- Toward a mathematical theory of inductive inference
- Towards General Algorithms for Grammatical Inference
- One-shot learners using negative counterexamples and nearest positive examples
- Iterative learning from positive data and negative counterexamples
- Parallel learning of automatic classes of languages
- Learning from Positive Data and Negative Counterexamples: A Survey
- Iterative Learning from Positive Data and Counters
- Automatic learning from positive data and negative counterexamples
- Learners based on transducers
This page was built for publication: Automatic learning from positive data and negative counterexamples
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2013555)
