How many queries are needed to learn?

ABSTRACT

We investigate the query complexity of exact learning in the membership and (proper) equivalence query model. We give a complete characterization of concept classes that are learnable with a polynomial number of polynomial sized queries in this model. We give applications of this characterization, including results on learning a natural subclass of DNF formulas, and on learning with membership queries alone. Query complexity has previously been used to prove lower bounds on the time complexity of exact learning. We show a new relationship between query complexity and time complexity in exact learning: If any “honest” class is exactly and properly learnable with polynomial query complexity, but not learnable in polynomial time, then P = NP. In particular, we show that an honest class is exactly polynomial-query learnable if and only if it is learnable using an oracle for &Ggr;p4.

REFERENCES

• 1: AIZENSTEIN, H., HELLERSTEIN, L., AND PITT, L. 1992. Read-thrice DNF is hard to learn with ~ membership and equivalence queries. In Proceedings of the 33rd Annual IEEE Symposium on the ~ Foundations of Computer Science. IEEE, New York, pp. 523-532.~
• 2: Dana Angluin, Learning regular sets from queries and counterexamples, Information and Computation, v.75 n.2, p.87-106, November 1, 1987 [doi>10.1016/0890-5401(87)90052-6]
• 3: Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
• 4: Dana Angluin, Negative Results for Equivalence Queries, Machine Learning, v.5 n.2, p.121-150, Jun. 1990 [doi>10.1023/A:1022692615781]
• 5: Dana Angluin , Michael Frazier , Leonard Pitt, Learning Conjunctions of Horn Clauses, Machine Learning, v.9 n.2-3, p.147-164, July 1992 [doi>10.1007/BF00992675]
• 6: 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]
• 7: Dana Angluin , Michael Kharitonov, When won't membership queries help?, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.444-454, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103420]
• 8: ANTHONY, M., BRIGHTWELL, G., AND SHAWE-TAYLOR, J. 1992. On specifying Boolean functions by ~ labelled examples. Tech. Rep. London School of Economics, London, U.K.
• 9: BIOCH, J., AND IBARAKI, t. 1993. Complexity of identification and dualization of positive boolean ~functions. Tech. Rep. RRR 25-93. Rutgers Center for Operations Research, Rutgers, N.J.
• 10: Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989 [doi>10.1145/76359.76371]
• 11: BREITBART, Y. 1992. Complexity of the calculation of predicates by finite automata. Ph.D. ~ dissertation. Technion, Haifa, Israel.
• 12: BSHOUTY, N. 1993. Exact learning via the monotone theory. In Proceedings of the 34th Annual ~ IEEE Symposium on the Foundations of Computer Science. IEEE, New York, 302-311.
• 13: Nader H. Bshouty , Richard Cleve , Sampath Kannan , Christino Tamon, Oracles and queries that are sufficient for exact learning (extended abstract), Proceedings of the seventh annual conference on Computational learning theory, p.130-139, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.181067]
• 14: ERD6S, P., AND SPENCER, J. 1974. Probabilistic Methods in Combinatotics. Probability and Mathe-matical Statistics A Series of Monographs and Textbooks. Academic Press, Orlando, Fla.
• 15: Ricard Gavaldà, On the power of equivalence queries, Proceedings of the first European conference on Computational learning theory, p.193-203, October 1994, Royal Holloway, Univ. of London, United Kingdom
• 16: Sally A. Goldman , Michael J. Kearns, On the complexity of teaching, Proceedings of the fourth annual workshop on Computational learning theory, p.303-314, August 05-07, 1991, Santa Cruz, California, United States
• 17: Thomas R. Hancock, Identifying μ-formula decision trees with queries, Proceedings of the third annual workshop on Computational learning theory, p.23-37, August 06-08, 1990, Rochester, New York, United States
• 18: Tibor Hegedűs, Generalized teaching dimensions and the query complexity of learning, Proceedings of the eighth annual conference on Computational learning theory, p.108-117, July 05-08, 1995, Santa Cruz, California, United States [doi>10.1145/225298.225311]
• 19: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 20: Jãnis Kaņeps , Rūsiņš Freivalds, Running time to recognize nonregular languages by 2-way probabilistic automata, Proceedings of the 18th international colloquium on Automata, languages and programming, p.174-185, June 1991, Madrid, Spain
• 21: Sampath K. Kannan, On the query complexity of learning, Proceedings of the sixth annual conference on Computational learning theory, p.58-66, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168312]
• 22: Richard M. Karp, Some Bounds on the Storage Requirements of Sequential Machines and Turing Machines, Journal of the ACM (JACM), v.14 n.3, p.478-489, July 1967 [doi>10.1145/321406.321410]
• 23: Eyal Kushilevitz , Yishay Mansour, Learning decision trees using the Fourier spectrum, SIAM Journal on Computing, v.22 n.6, p.1331-1348, Dec. 1993 [doi>10.1137/0222080]
• 24: MOSHKOV, M. 1983. Conditional tests. Prob. Kibern. (in Russian) 40, 131-170.
• 25: J. Naor , M. Naor, Small-bias probability spaces: efficient constructions and applications, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.213-223, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100244]
• 26: Krishnan Pillaipakkamnatt , Vijay Raghavan, On the limits of proper learnability of subclasses of DNF formulas, Proceedings of the seventh annual conference on Computational learning theory, p.118-129, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.181063]
• 27: R. L. Rivest , R. E. Schapire, Inference of finite automata using homing sequences, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.411-420, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73047]
• 28: Ayumi Shinohara , Satoru Miyano, Teachability in computational learning, New Generation Computing, v.8 n.4, p.337-347, 1991 [doi>10.1007/BF03037091]
• 29: STOCKMEYER, L. 1985. On approximation algorithms for #P. SIAMJ. Comput. 14, 849-861.
• 30: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Complexity hierarchies

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Relations between models
      F.1.2 Modes of Computation
          Subjects: Interactive and reactive computation; Relativized computation

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Concept learning; Induction

General Terms:
Algorithms, Design, Theory

Keywords:
certificates, equivalence queries, exact identification, membership queries, polynomial-query learning, polynomial-time hierarchy, polynomial-time learning, proper learning