Lisa Hellerstein
Vijay Raghavan
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 Γp4.
- 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.~Google Scholar
- ANGLUIN, D. 1987. Learning regular sets from queries and counterexamples. Inf. Comput. 75, ~87-106. Google Scholar
- ANGLUIN, D. 1988. Queries and concept learning. Mach. Learn. 2, 319-342. Google Scholar
- ANGLUIN, D. 1990. Negative results for equivalence queries. Mach. Learn. 5, 121-150. Google Scholar
- ANGLUIN, D., FRAZIER, M., AND PITt, L. 1992. Learning conjunctions of Horn clauses. Mach. ~ Learn. 9, 147-164. Google Scholar
- ANGLUIN, D., HELLERSTEIN, L., AND KARPINSKI, M. 1993. Learning read-once formulas with ~ queries. J. ACM 40, 1 (Jan.), 185-210. Google Scholar
- ANGLUIN, D., AND KHARITONOV, M. 1991. When won't membership queries help? In Proceedings ~ of the 23rd ACM Symposium on Theory of Computing (New Orleans, La., May 6-8). ACM, New ~ York, pp. 444-454. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- BLUMER, A., EHRENFEUCHT, A., HAUSSLER, D., AND WARMUTH, M.K. 1989. Learnability and the ~ Vapnik-Chervonenkis dimension. J. ACM 36, 4 (Oct.), 929-965. Google Scholar
- BREITBART, Y. 1992. Complexity of the calculation of predicates by finite automata. Ph.D. ~ dissertation. Technion, Haifa, Israel.Google Scholar
- 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.Google Scholar
- BSHOUTY, N., CLEVE, R., KANNAN, S., AND TAMON, C. 1994. Oracles and queries that are sufficient ~ for exact learning. In Proceedings of the 7th Annual ACM Conference on Computational Learning ~ Theory (New Brunswick, N.J., June 12-15). ACM, New York, pp. 130-136). Google Scholar
- 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.Google Scholar
- GAVALDX, R. 1993. On the Power of Equivalence Queries. In Proceedings of EUROCOLT 93, ~ 193-203. Google Scholar
- GOLDMAN, S., AND KEARNS, M. 1991. On the complexity of teaching. In Proceedings of the 4th ~ Annual Workshop on Computational Learning Theory. 303-314. Google Scholar
- HANCOCK, T. 1990. Identifying /x-formula decision trees with queries. In Proceedings of the 3rd ~ Annual Workshop on Computational Learning Theory. pp. 23-37. Google Scholar
- HEGED/JS, T. 1995. Generalized teaching dimensions and the query complexity of learning. In ~ Proceedings of the 8th Annual ACM Conference on Computational Learning Theory (Santa Cruz, ~ Calif., July 5-8). ACM, New York, pp. 108-117. Google Scholar
- HOPCROFT, J., AND ULLMAN, J. 1979. Introduction to Automata Theory, Languages and Computa- ~ tion. Addison-Wesley. Google Scholar
- KANEPS, r., AND FREIVALDS, R. 1991. Running time to recognize nonregular languages by 2-way ~ probabilistic finite automata. In Lecture Notes in Computer Science, vol. 510. Springer-Verlag, New ~ York, pp. 355-361. Google Scholar
- KANNAN, S. 1993. On the query complexity of learning. In Proceedings of the 6th Annual ACM ~ Conference on Computational Learning Theory Google Scholar
- KARP, R. 1967. Some bounds on the storage requirements of sequential machines and Turing ~ machines. J. ACM 14, 3 (July) 478-489. Google Scholar
- KUSHILEVITZ, E., AND MANSOUR, Y. 1993. Learning decision trees using the Fourier spectrum. ~ SIAMJ. Comput. 22, 6, 1331-1348. Google Scholar
- MOSHKOV, M. 1983. Conditional tests. Prob. Kibern. (in Russian) 40, 131-170.Google Scholar
- NAOR, J., AND NAOR, M. 1990. Small-bias probability spaces: Efficient constructions and applica- ~ tions. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (Baltimore, Md., ~ May 12-14). ACM, New York, pp. 213-223. Google Scholar
- PILLAIPAKKAMNATT, K., AND RAGHAVAN, V. 1994. On the limits of proper learnability of sub- ~ classes of DNF formulas. In Proceedings of the 7th Annual ACM Conference on Computational ~ Learning Theory (New Brunswick, N.J., June 12-15). ACM, New York, pp. 118-129. Google Scholar
- RIVEST, R., AND SCHAPIRE, R. 1989. Inference of finite automata using homing sequences. In ~ Proceedings of the 21st Annual ACM Symposium on Theory of Computing (Seattle, Wash., May ~ 15-17). ACM, New York, pp. 411-420. Google Scholar
- SHINOHARA, A., AND MIYANO, S. 1991. Teachability in computational learning. New Gem Comput. ~ 8, 337-347. Google Scholar
- STOCKMEYER, L. 1985. On approximation algorithms for #P. SIAMJ. Comput. 14, 849-861.Google Scholar
- VALIANT, L. 1984. A theory of the learnable. Commun. ACM 27, 11 (Nov.), 1134-1142. Google Scholar
Index Terms
- How many queries are needed to learn?
Recommendations
Learning read-once formulas with queries
A read-once formula is a Boolean formula in which each variable occurs, at most, once. Such formulas are also called μ-formulas or Boolean trees. This paper treats the problem of exactly identifying an unknown read-once formula using specific kinds of ...
Hardness of approximate two-level logic minimization and PAC learning with membership queries
STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of ComputingProducing a small DNF expression consistent with given data is a classical problem in computer science that occurs in a number of forms and has numerous applications. We consider two standard variants of this problem. The first one is two-level logic ...
On the complexity of learning from counterexamples and membership queries
SFCS '90: Proceedings of the 31st Annual Symposium on Foundations of Computer ScienceIt is shown that for any concept class C the number of equivalence and membership queries that are needed to learn C is bounded from below by Omega (VC-dimension(C)). Furthermore, it is shown that the required number of equivalence and membership ...
Comments