Learning Boolean Halfspaces with Small Weights from Membership Queries
Abstract
We consider the problem of proper learning a Boolean Halfspace with integer weights 0,1,…, t from membership queries only. The best known algorithm for this problem is an adaptive algorithm that asks $n^{O(t^5)}$ membership queries where the best lower bound for the number of membership queries is n ^ t [4]. In this paper we close this gap and give an adaptive proper learning algorithm with two rounds that asks n ^ O ( t ) membership queries. We also give a non-adaptive proper learning algorithm that asks $n^{O(t^3)}$ membership queries.
Cite
Text
Abasi et al. "Learning Boolean Halfspaces with Small Weights from Membership Queries." International Conference on Algorithmic Learning Theory, 2014. doi:10.1007/978-3-319-11662-4_8Markdown
[Abasi et al. "Learning Boolean Halfspaces with Small Weights from Membership Queries." International Conference on Algorithmic Learning Theory, 2014.](https://mlanthology.org/alt/2014/abasi2014alt-learning/) doi:10.1007/978-3-319-11662-4_8BibTeX
@inproceedings{abasi2014alt-learning,
title = {{Learning Boolean Halfspaces with Small Weights from Membership Queries}},
author = {Abasi, Hasan and Abdi, Ali Z. and Bshouty, Nader H.},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2014},
pages = {96-110},
doi = {10.1007/978-3-319-11662-4_8},
url = {https://mlanthology.org/alt/2014/abasi2014alt-learning/}
}