On-Line Learning with an Oblivious Environment and the Power of Randomization

Abstract

A new model for on-line learning is introduced. In this model the environment is assumed to be oblivious to the learner: it supplies an arbitrary (not necessarily random) sequence of examples for the target concept which does not depend on the sequence of hypotheses of the learner. This model provides a framework for the design and analysis of on-line learning algorithms which acquire information not just from counterexamples, but also from examples which support their current hypotheses. It is shown that for various concept classes C an arbitrary target concept from C can be learned in this model by a randomized learning algorithm (which uses only hypotheses from C) with substantially fewer prediction errors than in the previously considered models for on-line learning. In particular any target-setting of weights and thresholds in a feed forward neural net can be learned by a randomized learning algorithm in this model with an expected number of prediction errors that is polynomial in the number of units of the neural net. We also show that these positive results for randomized learning algorithms remain valid if the environment is only weakly oblivious, i.e. if the environment can let its choice of examples depend on earlier reactions of the learner, but is not able to predict future moves of the learner.