Learning counting functions with queries

✍ Scribed by Zhixiang Chen; Steven Homer

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 1022 KB
• Volume: 180
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(96)00144-2

✦ Synopsis

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: (or Z") for any given integer q > 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,. In general, a counting function may have a composite modulus. We prove that, for any given integer q > 2, over the domain Zl, 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.