Lower Bounds for the Complexity of Learning Half-Spaces with Membership Queries
Abstract
Exact learning of half-spaces over finite subsets of ℝ^n from membership queries is considered. We describe the minimum set of labelled examples separating the target concept from all the other ones of the concept class under consideration. For a domain consisting of all integer points of some polytope we give non-trivial lower bounds on the complexity of exact identification of half-spaces. These bounds are near to known upper bounds.
Cite
Text
Shevchenko and Zolotykh. "Lower Bounds for the Complexity of Learning Half-Spaces with Membership Queries." International Conference on Algorithmic Learning Theory, 1998. doi:10.1007/3-540-49730-7_5Markdown
[Shevchenko and Zolotykh. "Lower Bounds for the Complexity of Learning Half-Spaces with Membership Queries." International Conference on Algorithmic Learning Theory, 1998.](https://mlanthology.org/alt/1998/shevchenko1998alt-lower/) doi:10.1007/3-540-49730-7_5BibTeX
@inproceedings{shevchenko1998alt-lower,
title = {{Lower Bounds for the Complexity of Learning Half-Spaces with Membership Queries}},
author = {Shevchenko, Valery N. and Zolotykh, Nikolai Yu.},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {1998},
pages = {61-71},
doi = {10.1007/3-540-49730-7_5},
url = {https://mlanthology.org/alt/1998/shevchenko1998alt-lower/}
}