Robust learning with infinite additional information

AbstractThe present work investigates Gold-style algorithmic learning from input–output examples where the learner has access to oracles as additional information. This access is required to be robust in the sense that a single learning algorithm has to succeed with every oracle which meets a given specification. The first main result considers oracles of the same Turing degree: Robust learning with any oracle from a given degree does not achieve more than learning without any additional information. The further work considers learning from function oracles which describe the whole class of functions to be learned in one of the following five ways: as a list of all functions in this class, a predictor for this class, a one-sided classifier accepting just the functions in this class, an identifier for the class or a martingale succeeding on this class. It is shown that for learning in the limit (Ex), lists are the most powerful additional information, the powers of predictors and classifiers are incomparable and identifiers and martingales are of no help at all. Similar results are obtained for the criteria of predicting the next value, finite, Popperian and finite Popperian learning. Lists are omniscient for the criterion of predicting the next value and also identifiers are helpful at this criterion. So it turns out that algorithms to predict the next value can much better exploit robustly oracles than algorithms which give explanations (Ex-learning). For Ex-learning none of these five types of help is omniscient, that is, some classes cannot be Ex-learned with any of these types of additional information. The class REC of all recursive functions is Ex-learnable with the help of a list, a predictor or a classifier