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

TitleOn-Line Learning with an Oblivious Environment and the Power of Randomization
Publication TypeTechnical Report
Year of Publication1991
AuthorsMaass, W.
Other Numbers633
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 counter examples, but also from examples which "support" their current hypothesis. 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 Angluin's classical model for on-line learning with an adaptive worst-case environment. 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.For comparison we also examine the power of randomization for Angluin's model for learning with an adaptive environment.

URLhttp://www.icsi.berkeley.edu/pubs/techreports/tr-91-003.pdf
Bibliographic Notes

ICSI Technical Report TR-91-003

Abbreviated Authors

W. Maass

ICSI Publication Type

Technical Report