Noisy inference and oracles

The present paper deals with several variants of inductive inference from noisy data. The notion of noise is based on the idea that the learner recieves a sequence of data elements such that each correct element appears infinitely often and each incorrect element appears at most finitely often. The main result is that the concept of learning in the limit from noisy informant has the same power as finite learning using a K-oracle from noise-free informant. The analog equality for text fails in general and holds only in one direction in the case of learning uniformly recursive families. Furthermore, learnability from noisy informant or text in presence of using oracles is investigated. It is shown that partial identification of all r. e. sets can also cope with noisy informant and text.

Authors

• Frank Stephan

Keywords

No keywords are indexed for this paper.