On Learning Disjunctions of Zero-One Treshold Functions with Queries
Abstract
We investigate the learnability of the class κ-ZOTF_n of disjunctions of (at most) κk zero-one threshold functions with queries. We describe a poly ( n )-time algorithm that identifies any concept from 2-ZOTF_n with one proper equivalence query and O ( n ^2) membership queries, propose some techniques that work for larger κ in special cases and via a case analysis obtain an algorithm for learning 3-ZOTF_n with O (_n ^5) membership and proper equivalence queries. Then we prove non-learnability results via exhibiting bounds κ ( n ) for which polynomial time learnability of κ( n )-ZOTF_n with proper equivalence and membership queries becomes presumably intractable. Finally, we provide results on learning a single zero-one threshold function with queries: an efficient membership query algorithm for the case when the target has few relevant attributes, and a parallel algorithm that identifies a zero-one threshold function in constant time with O ( n ) membership queries.
Cite
Text
Hegedüs and Indyk. "On Learning Disjunctions of Zero-One Treshold Functions with Queries." International Conference on Algorithmic Learning Theory, 1997. doi:10.1007/3-540-63577-7_60Markdown
[Hegedüs and Indyk. "On Learning Disjunctions of Zero-One Treshold Functions with Queries." International Conference on Algorithmic Learning Theory, 1997.](https://mlanthology.org/alt/1997/hegedus1997alt-learning/) doi:10.1007/3-540-63577-7_60BibTeX
@inproceedings{hegedus1997alt-learning,
title = {{On Learning Disjunctions of Zero-One Treshold Functions with Queries}},
author = {Hegedüs, Tibor and Indyk, Piotr},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {1997},
pages = {446-460},
doi = {10.1007/3-540-63577-7_60},
url = {https://mlanthology.org/alt/1997/hegedus1997alt-learning/}
}