Classification Using Information
Abstract
Smith and Wiehagen [9] introduced a model of classification that is similar to the Gold model of learning We would like to separate the computational limitations from the information-theoretic ones. To this end we study a model of learning originally due to Kelly [6] that has no computational limits; however, the objects that we will be concerned with are rather complex. Fix a set $\mathcal{A} \subseteq \left\{ {0,1} \right\}^\omega$ We will examine if a classifier (without computational limits) can classify a string $x \in \left\{ {0,1} \right\}^\omega$ with respect to A . We will be varying the amount of information the learner can access. To increase the models ability to access information, we will give it the ability to ask more powerful questions. To decrease the models ability to access information, we will bound the number of mindchanges it may make.
Cite
Text
Gasarch et al. "Classification Using Information." International Conference on Algorithmic Learning Theory, 1994. doi:10.1007/3-540-58520-6_72Markdown
[Gasarch et al. "Classification Using Information." International Conference on Algorithmic Learning Theory, 1994.](https://mlanthology.org/alt/1994/gasarch1994alt-classification/) doi:10.1007/3-540-58520-6_72BibTeX
@inproceedings{gasarch1994alt-classification,
title = {{Classification Using Information}},
author = {Gasarch, William I. and Pleszkoch, Mark G. and Velauthapillai, Mahendran},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {1994},
pages = {290-300},
doi = {10.1007/3-540-58520-6_72},
url = {https://mlanthology.org/alt/1994/gasarch1994alt-classification/}
}