Two Variations of Inductive Inference of Languages from Positive Data
Takashi Tabe, 尚志 田部, Thomas Zeugmann · Kyushu University Institutional Repository (QIR) (Kyushu University) · 1995
The present paper deals with the learnabihty of indexed fammilies of uniformly recursive languages by single inductive inference machines (abbr.IIM) and teams of IIMs from positive and both positive and negative data.We study the learning power of single IIMs in dependence on the hypothesis space and the number of anomalies the synthesized language may have.Our results are fourfold.First, we show that allowing anomalies does not increase the learning power as long as inference from positive and negative data is considered.Second, we establish an infinite hierarchy in the number of allowed anomalies for learning from positive data.Third, we prove that every learnable indexed family $L$ may be even inferred with respect to the hypothesis space $\mathcal{L}$ itself.Fourth, we characterize learning with anomalies from positive data.Finally, we investigate the error correcting power of team learners, and relate the inference capabilities of teams in dependence on their size to one another.Again, an infinite hierarchy is established and the learnabihty is characterized in terms of recursively generable families of finite and non-empty sets.