Title: On Learning Counting Functions With Queries
Author: Zhixiang Chen and Steven Homer
Date: February 1994
Abstract:
We investigate the problem of learning disjunctions of counting
functions, which are general cases 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 $Z^{n}_{q}$ (or $Z^{n}$)
for any given integer $q \ge 2$ is polynomial time learnable using at
most $n+1$ equivalence queries, where the hypotheses issued by the
learner are disjunctions of at most $n$ counting functions with
weights from $Z_{p}$. The result is obtained through learning linear
systems over an arbitrary field. In general a counting function may
have a composite modulus. We prove that, for any given integer $q \ge
2$, over the domain $Z_{2}^{n}$, the class of read-once disjunctions
of Boolean-weighted counting functions with modulus $q$ is polynomial
time learnable with only one equivalence query, and the class of
disjunctions of $\log \log n$ Boolean-weighted counting functions with
modulus $q$ is polynomial time learnable.tions, which are general
cases Finally, we present an algorithm for learning graph-based
counting functions.ies.