On Learning Counting Functions with Queries
Abstract
We investigate the problem of learning disjunctions of counting functions, generalizations of parity and modulo functions, with equivalence and membership queries. We prove that, for any prime number p, the class of disjunctions of integer-weighted counting functions with modulus p over the domain Znq (or Zn) for any given integer q≥2, is polynomial time learnable using at most n+1 equivalence queries. The hypotheses issued by the learner are disjunctions of at most n counting functions with weights from Zp. In general a counting function may have a composite modulus. We prove that, for any given integer q≥2, over the domain Zn2, the class of read-once disjunctions of Boolean-weighted counting functions with modulus q is polynomial time learnable with only one equivalence query and O(nq) membership queries. And the class of disjunctions of loglogn Boolean-weighted counting functions with modulus q is polynomial time learnable.
Cite
Text
Chen and Homer. "On Learning Counting Functions with Queries." Annual Conference on Computational Learning Theory, 1994. doi:10.1145/180139.181116Markdown
[Chen and Homer. "On Learning Counting Functions with Queries." Annual Conference on Computational Learning Theory, 1994.](https://mlanthology.org/colt/1994/chen1994colt-learning/) doi:10.1145/180139.181116BibTeX
@inproceedings{chen1994colt-learning,
title = {{On Learning Counting Functions with Queries}},
author = {Chen, Zhixiang and Homer, Steven},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1994},
pages = {218-227},
doi = {10.1145/180139.181116},
url = {https://mlanthology.org/colt/1994/chen1994colt-learning/}
}