Oracles and queries that are sufficient for exact learning (extended abstract)

ABSTRACT

We show that the class of all circuits is exactly learnable in randomized expected polynomial-time using subset and superset queries. This is a consequence of the following result which we consider to be of independent interest: circuits are exactly learnable in randomized expected polynomial-time with equivalence queries and the aid of an NP-oracle. We also show that circuits are exactly learnable in deterministic polynomial-time with equivalence queries and a &Sgr;3p-oracle. The hypothesis class for the above learning algorithms is the class of circuits of larger—but polynomially related—size. Also, the algorithms can be adapted to learn the class of DNF formulas with hypothesis class consisting of depth-3 &Lgr;-V-&Lgr; formulas (by the work of Angluin, this is optimal in the sense that the hypothesis class cannot be reduced to depth-2 DNF formulas. We also investigate the power of an NP-oracle in the context of learning with membership queries. We show that there are deterministic learning algorithms that use membership queries and an NP-oracle to learn: monotone boolean functions in time polynomial in the DNF size and CNF size of the target formula; and the class of O(logn)-DNF ∩ O(logn)-CNF formulas in time polynomial in n. Finally, we show that, with an NP-oracle and membership queries, there is a randomized polynomial-time algorithm that learns any class that is learnable from membership queries with unlimited computational power.

REFERENCES

• A88: Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
• A90: Dana Angluin, Negative Results for Equivalence Queries, Machine Learning, v.5 n.2, p.121-150, Jun. 1990 [doi>10.1023/A:1022692615781]
• B89: Ravi Boppana. Amplification of Probabilistic Boolean Formulas. In Advances in Computing Research, 5:4, pages 27-45, 1989.
• B93: Nader Bshouty. Exact Learning via the Monotone Theory. In IEEE Foundations of Computer Science, pages 302-311, 1993.
• BC92: Nader Bshouty and Richard Cleve. On the Exact Learning of Formulas in Parallel. In Proceedings of the 33rd Symposium on Foundations of Computer Science, pages 513-522, 1992.
• G93: 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
• GRS93: Sally A. Goldman , Ronald L. Rivest , Robert E. Schapire, Learning binary relations and total orders, SIAM Journal on Computing, v.22 n.5, p.1006-1034, Oct. 1993 [doi>10.1137/0222062]
• JVV86: M R Jerrum , L G Valiant , V V Vazirani, Random generation of combinatorial structures from a uniform, Theoretical Computer Science, v.43 n.2-3, p.169-188, July 1986
• K93: 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]
• KM91: Eyal Kushilevitz , Yishay Mansour, Learning decision trees using the Fourier spectrum, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.455-464, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103466]
• L88: Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm, Machine Learning, v.2 n.4, p.285-318, April 1988 [doi>10.1023/A:1022869011914]
• MS56: E.F. Moore and C. Shannon. Reliable Circuits Using Less Reliable Relays. Y. Franklin Inst., 262, pages 191-208,281-297, 1956.
• PV88: Leonard Pitt , Leslie G. Valiant, Computational limitations on learning from examples, Journal of the ACM (JACM), v.35 n.4, p.965-984, Oct. 1988 [doi>10.1145/48014.63140]
• S83: Michael Sipser, A complexity theoretic approach to randomness, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.330-335, December 1983 [doi>10.1145/800061.808762]
• S85: Larry Stockmeyer. On Approximation Algorithms for #P. SIAM Journal on Computing, 14:4, pages 849-861, 1985.
• V84a: Leslie Valiant. Short Monotone Formulae for the Majority Function. J. Algorithms, 5, pages 363-366, 1984.
• V84b: 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.2 Modes of Computation
          Subjects: Relativized computation

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

General Terms:
Theory, Verification