Learning read-once formulas with queries

ABSTRACT

A read-once formula is a Boolean formula in which each variable occurs, at most, once. Such formulas are also called &mgr;-formulas or Boolean trees. This paper treats the problem of exactly identifying an unknown read-once formula using specific kinds of queries. The main results are a polynomial-time algorithm for exact identification of monotone read-once formulas using only membership queries, and a polynomial-time algorithm for exact identification of general read-once formulas using equivalence and membership queries (a protocol based on the notion of a minimally adequate teacher [1]). The results of the authors improve on Valiant's previous results for read-once formulas [26]. It is also shown, that no polynomial-time algorithm using only membership queries or only equivalence queries can exactly identify all read-once formulas.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	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]
	2	Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
	3	~ANGLUm, D. Using queries to identify /z-formulas. Tech. rcp. YALE/DCS/RR-694. Yale ~Univ., New Haven, Conn., 1989.
	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	~ANGLUIN, D., FRAZIER, M., AND PITT, L. Learning conjunctions of Horn clauses. In Proceed- ~ings o)' tile 31st Annual Symposium on Foundations of Computer Sctetzce. IEEE Computer ~Society Press, New York, 1990, pp. 186-192.
	6	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]
	7	~ANGLUIN, D. AND VALIANT, L. Fast probabilistic algorithms for Hamiltonian circuits and ~matchings. J. Compttt. Syst. Sci. J8 (1979), 155-193.
	8	Avrim Blum , Lisa Hellerstein , Nick Littlestone, Learning in the presence of finitely or infinitely many irrelevant attributes, Proceedings of the fourth annual workshop on Computational learning theory, p.157-166, August 05-07, 1991, Santa Cruz, California, United States
	9	Dima Yu Grigoriev , Marek Karpinski , Michael F. Singer, Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields, SIAM Journal on Computing, v.19 n.6, p.1059-1063, Dec. 1990 [doi>10.1137/0219073]
	10	~HANCOCK, T. Identifying /z-decision trees and /z-formulas with constrained instance queries. ~Manuscript, Harvard University, Cambridge, Mass., 1989.
	11	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
	12	Thomas R. Hancock, Learning 2u DNF formulas and ku decision trees, Proceedings of the fourth annual workshop on Computational learning theory, p.199-212, August 05-07, 1991, Santa Cruz, California, United States
	13	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
	14	Lisa Hellerstein , Richard M. Karp, On characterizing and learning some classes of read-once functions, 1989
	15	L. Hellerstein , Marek Karpinski, Learning read-once formulas using membership queries, Proceedings of the second annual workshop on Computational learning theory, p.146-161, December 1989, Santa Cruz, California, United States
	16	M. Karchmer , N. Linial , I. Newman , M. Saks , A. Wigderson, Combinatorial characterization of read-once formulae, Discrete Mathematics, v.114 n.1-3, p.275-282, April 28, 1993 [doi>10.1016/0012-365X(93)90372-Z]
	17	R M Karp , E Upfal , A Wigderson, Are search and decision programs computationally equivalent?, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.464-475, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22197]
	18	Michael J. Kearns, Computational Complexity of Machine Learning, MIT Press, Cambridge, MA, 1990
	19	M. Kearns , M. Li , L. Pitt , L. Valiant, On the learnability of Boolean formulae, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.285-295, January 1987, New York, New York, United States [doi>10.1145/28395.28426]
	20	M. Kearns , L. G. Valiant, Crytographic limitations on learning Boolean formulae and finite automata, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.433-444, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73049]
	21	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]
	22	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]
	23	Leonard Pitt , Manfred K. Warmuth, Prediction-preserving reducibility, Journal of Computer and System Sciences, v.41 n.3, p.430-467, Dec. 1990 [doi>10.1016/0022-0000(90)90028-J]
	24	Vijay Raghavan , Stephen R. Schach, Learning switch configurations, Proceedings of the third annual workshop on Computational learning theory, p.38-51, August 06-08, 1990, Rochester, New York, United States
	25	Yasubumi Sakakibara, Learning context-free grammars from structural data in polynomial time, Theoretical Computer Science, v.76 n.2-3, p.223-242, Nov. 21, 1990 [doi>10.1016/0304-3975(90)90017-C]
	26	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]