Exploiting Random Walks for Learning

Peter Bartlett, Paul Fischer, K.-U. Hoeffgen

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    In this paper we consider an approach to passive learning. In contrast to the classical PAC model we do not assume that the examples are independently drawn according to an underlying distribution, but that they are generated by a time-driven process. We define deterministic and probabilistic learning models of this sort and investigate the relationships between them and with other models. The fact that successive examples are related can often be used to gain additional information similar to the information gained by membership queries. We show how this can be used to design on-line prediction algorithms. In particular, we present efficient algorithms for exactly identifying Boolean threshold functions and 2-term RSE, and for learning 2-term-DNF, when the examples are generated by a random walk on {0, 1}n.
    Original languageEnglish
    JournalInformation and Computation
    Volume176
    Issue number2
    Pages (from-to)121-135
    ISSN0890-5401
    DOIs
    Publication statusPublished - 2002

    Fingerprint

    Dive into the research topics of 'Exploiting Random Walks for Learning'. Together they form a unique fingerprint.

    Cite this