AbstractWe 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 class 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 an ``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 learnable if and only iff it is learnable using an oracle for Sigma^p_4.
The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.
Categories and Subject Descriptors: F.1.1 [Computation by Abstract Devices]: Models of Computation -- relations among models; F.1.2 [Computation by Abstract Devices]: Modes of Computation -- relativized computation, interactive computation; F.1.3 [Computation by Abstract Devices]: Complexity Classes -- complexity hierarchies; I.2.6 [Artificial Intelligence]: Learning -- concept learning, induction
General Terms: Algorithms, Design, Theory
Additional Key Words and Phrases: Certificates, equivalence queries, exact identification, membership queries, polynomial-time hierarchy, polynomial-time learning, polynomial-query learning, proper learning
Selected papers that cite this one
- Aaron Feigelson and Lisa Hellerstein. Conjunctions of unate DNF formulas: Learning and structure. Information and Computation, 140(2):203-228, 1 February 1998.
Selected references
- Howard Aizenstein, Lisa Hellerstein, and Leonard Pitt. Read-thrice DNF is hard to learn with membership and equivalence queries. In 33rd Annual Symposium on Foundations of Computer Science, pages 523-532, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.
- Dana Angluin. Learning regular sets from queries and counterexamples. Information and Computation, 75(2):87-106, November 1987.
- Dana Angluin, Michael Frazier, and Leonard Pitt. Learning conjunctions of Horn clauses (extended abstract). In 31st Annual Symposium on Foundations of Computer Science, volume I, pages 186-192, St. Louis, Missouri, 22-24 October 1990. IEEE.
- Dana Angluin, Lisa Hellerstein, and Marek Karpinski. Learning read-once formulas with queries. Journal of the ACM, 40(1):185-210, January 1993.
- Dana Angluin and Michael Kharitonov. When won't membership queries help? (extended abstract). In Proceedings of the Twenty Third Annual ACM Symposium on Theory of Computing, pages 444-454, New Orleans, Louisiana, 6-8 May 1991.
- Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. Journal of the ACM, 36(4):929-965, October 1989.
- Nader H. Bshouty. Exact learning Boolean functsion via the monotone theory. Information and Computation, 123(1):146-153, 15 November 1995.
- Richard M. Karp. Some bounds on the storage requirements of sequential machines and Turing machines. Journal of the ACM, 14(3):478-489, July 1967.
- Eyal Kushilevitz and Yishay Mansour. Learning decision trees using the Fourier spectrum. SIAM Journal on Computing, 22(6):1331-1348, December 1993.
- Joseph Naor and Moni Naor. Small-bias probability spaces: Efficient constructions and applications. In Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, pages 213-223, Baltimore, Maryland, 14-16 May 1990.
- Ronald L. Rivest and Robert E. Schapire. Inference of finite automata using homing sequences (extended abstract). In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 411-420, Seattle, Washington, 15-17 May 1989.
- Larry Stockmeyer. On approximation algorithms for #P. SIAM Journal on Computing, 14(4):849-861, November 1985.
- Leslie G. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134-1142, November 1984.