Exploiting Random Walks for Learning
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 that this can be used to design on-line prediction algorithms. In particular, we present efficient algorithms for exactly identifying Boolean threshold functions, 2-term RSE, and 2-term-DNF, when the examples are generated by a random walk on 0,1n.
Cite
Text
Bartlett et al. "Exploiting Random Walks for Learning." Annual Conference on Computational Learning Theory, 1994. doi:10.1145/180139.181167Markdown
[Bartlett et al. "Exploiting Random Walks for Learning." Annual Conference on Computational Learning Theory, 1994.](https://mlanthology.org/colt/1994/bartlett1994colt-exploiting/) doi:10.1145/180139.181167BibTeX
@inproceedings{bartlett1994colt-exploiting,
title = {{Exploiting Random Walks for Learning}},
author = {Bartlett, Peter L. and Fischer, Paul and Höffgen, Klaus-Uwe},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1994},
pages = {318-327},
doi = {10.1145/180139.181167},
url = {https://mlanthology.org/colt/1994/bartlett1994colt-exploiting/}
}