A General Dimension for Approximately Learning Boolean Functions
Abstract
We extend the notion of general dimension, a combinatorial characterization of learning complexity for arbitrary query protocols, to encompass approximate learning. This immediately yields a characterization of the learning complexity in the statistical query model. As a further application, we consider approximate learning of DNF formulas and we derive close upper and lower bounds on the number of statistical queries needed. In particular, we show that with respect to the uniform distribution, and for any constant error parameter ∈ lt; 1/2, the number of statistical queries needed to approximately learn DNF formulas (over n variables and s terms) with tolerance τ = Θ(1/s) is n Θ^(log s).
Cite
Text
Köbler and Lindner. "A General Dimension for Approximately Learning Boolean Functions." International Conference on Algorithmic Learning Theory, 2002. doi:10.1007/3-540-36169-3_13Markdown
[Köbler and Lindner. "A General Dimension for Approximately Learning Boolean Functions." International Conference on Algorithmic Learning Theory, 2002.](https://mlanthology.org/alt/2002/kobler2002alt-general/) doi:10.1007/3-540-36169-3_13BibTeX
@inproceedings{kobler2002alt-general,
title = {{A General Dimension for Approximately Learning Boolean Functions}},
author = {Köbler, Johannes and Lindner, Wolfgang},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2002},
pages = {139-148},
doi = {10.1007/3-540-36169-3_13},
url = {https://mlanthology.org/alt/2002/kobler2002alt-general/}
}