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.

REFERENCES

• A: Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
• AHK: Dana Angluin , Lisa Hellerstein , Marek Karpinski, Learning read-once formulas with queries, Journal of the ACM (JACM), v.40 n.1, p.185-210, Jan. 1993 [doi>10.1145/138027.138061]
• BR: Avrim Blum , Steven Rudich, Fast learning of k-term DNF formulas with queries, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.382-389, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129748]
• BCJ: Avrim Blum , Prasad Chalasani , Jeffrey Jackson, On learning embedded symmetric concepts, Proceedings of the sixth annual conference on Computational learning theory, p.337-346, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168367]
• BS: Avrim Blum , Mona Singh, Learning functions of k terms, Proceedings of the third annual workshop on Computational learning theory, p.144-153, August 06-08, 1990, Rochester, New York, United States
• BGHM: Nader H. Bshouty , Sally A. Goldman , Thomas R. Hancock , Sleiman Matar, Asking questions to minimize errors, Proceedings of the sixth annual conference on Computational learning theory, p.41-50, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168310]
• BHH: Nader H. Bshouty , Thomas R. Hancock , Lisa Hellerstein, Learning Boolean read-once formulas with arbitrary symmetric and constant fan-in gates, Proceedings of the fifth annual workshop on Computational learning theory, p.1-15, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130386]
• FS: Paul Fischer , Hans Ulrich Simon, On learning ring-sum-expansions, SIAM Journal on Computing, v.21 n.1, p.181-192, Feb. 1992 [doi>10.1137/0221014]
• HH: Thomas Hancock , Lisa Hellerstein, Learning read-once formulas over fields and extended bases, Proceedings of the fourth annual workshop on Computational learning theory, p.326-336, August 05-07, 1991, Santa Cruz, California, United States
• HSW: David Helmbold , Robert Sloan , Manfred K. Warmuth, Learning integer lattices, SIAM Journal on Computing, v.21 n.2, p.240-266, April 1992 [doi>10.1137/0221019]
• J: J. Jackson, Personal communications.
• S: R. Schapire, Personal communications.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Algorithms, Theory, Verification