Learnability with Restricted Focus of Attention Guarantees Noise-Tolerance
Abstract
We consider the question of learning in the presence of classification noise. More specifically, we address the issue of identifying conditions that, once a learning algorithm meets them, it can be transformed into a noise-tolerant algorithm. While the question of whether every PAC learning algorithm can be made noise-tolerant is still open, the bottom line of this work, loosely stated, is that any restriction on the amount of data an algorithm is allowed to retrieve from its input samples, suffices to render the existence of a noise-tolerant variant that is efficient whenever the original algorithm is. The result is obtained by proving that such a restricted learning is equivalent to learning from statistical queries, and by applying Kearns transformation from statistical learning into noise-tolerant learning.
Cite
Text
Ben-David and Dichterman. "Learnability with Restricted Focus of Attention Guarantees Noise-Tolerance." International Conference on Algorithmic Learning Theory, 1994. doi:10.1007/3-540-58520-6_68Markdown
[Ben-David and Dichterman. "Learnability with Restricted Focus of Attention Guarantees Noise-Tolerance." International Conference on Algorithmic Learning Theory, 1994.](https://mlanthology.org/alt/1994/bendavid1994alt-learnability/) doi:10.1007/3-540-58520-6_68BibTeX
@inproceedings{bendavid1994alt-learnability,
title = {{Learnability with Restricted Focus of Attention Guarantees Noise-Tolerance}},
author = {Ben-David, Shai and Dichterman, Eli},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {1994},
pages = {248-259},
doi = {10.1007/3-540-58520-6_68},
url = {https://mlanthology.org/alt/1994/bendavid1994alt-learnability/}
}