From On-Line to Batch Learning
Abstract
We contrast on-line and batch settings for concept learning, and describe an on-line learning model in which no probabilistic assumptions are made. We briefly mention some of our recent results pertaining to on-line learning algorithms developed using this model. We then turn to the main topic, which is an analysis of a conversion to improve the performance of on-line learning algorithms in a batch setting. For the batch setting we use the PAC-learning model. The conversion is straightforward, consisting of running the given on-line algorithm, collecting the hypotheses it uses for making predictions, and then choosing the hypothesis among them that does the best in a subsequent hypothesis testing phase. We have developed an analysis, using a version of Chernoff bounds applied to supermartingales, that shows that for some target classes the converted algorithm will be asymptotically optimal.
Cite
Text
Littlestone. "From On-Line to Batch Learning." Annual Conference on Computational Learning Theory, 1989. doi:10.1016/B978-0-08-094829-4.50022-2Markdown
[Littlestone. "From On-Line to Batch Learning." Annual Conference on Computational Learning Theory, 1989.](https://mlanthology.org/colt/1989/littlestone1989colt-line/) doi:10.1016/B978-0-08-094829-4.50022-2BibTeX
@inproceedings{littlestone1989colt-line,
title = {{From On-Line to Batch Learning}},
author = {Littlestone, Nick},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1989},
pages = {269-284},
doi = {10.1016/B978-0-08-094829-4.50022-2},
url = {https://mlanthology.org/colt/1989/littlestone1989colt-line/}
}