Asking questions to minimize errors

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Asking questions to minimize errors

Full text

Pdf (1.14 MB)

Source

Annual Workshop on Computational Learning Theory archive
Proceedings of the sixth annual conference on Computational learning theory table of contents

Santa Cruz, California, United States

Pages: 41 - 50

Year of Publication: 1993

ISBN:0-89791-611-5

Authors

Nader H. Bshouty
Sally A. Goldman
Thomas R. Hancock
Sleiman Matar

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 12, Citation Count: 9

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/168304.168310 What is a DOI?

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.

	AFP90	Dana Angluin, Michael Frazier, and Leonard Pitt. Learning conjunctions of horn clauses. In 31st Annual Symposium on Foundations of Computer Science, pages 186-192, October 1990.
	AFP92	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]
	AHK89	Dana Angluin , Lisa Hellerstein , Marek Karpinski, Learning Read-Once Formulas with Queries, University of California at Berkeley, Berkeley, CA, 1989
	Ang87a	Dana Angluin. Learning k-term DNF formulas using queries and counterexamples. Technical Report YALEU/DCS/RR-559, Yale University, August 1987.
	Ang87b	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]
	Aug88	Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
	Ang90	Dana Angluin, Negative Results for Equivalence Queries, Machine Learning, v.5 n.2, p.121-150, Jun. 1990 [doi>10.1023/A:1022692615781]
	AP91	Howard Aizenstein , Leonard Pitt, Exact learning of read-twice DNF formulas (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.170-179, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185366]
	AP92	Howard Aizenstein , Leonard Pitt, Exact learning of read-k disjoint DNF and not-so-disjoint DNF, Proceedings of the fifth annual workshop on Computational learning theory, p.71-76, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130393]
	BC92	Nader H. B~houty and Richard Cleve. On the exact learning of formulas in parallel. In 33rd Annual Symposium on Foundations of Computer Science, pages 1-15, October 1992.
	BF72	Ian Barzdin and Rasi!~ Freivald. On the prediction of general recursive functions. Sovset Mathematics Doklady, 13:1224-1228, 1972.
	BGHM93	Nader H. Bshouty, Sally A. Goldman, Thomas R. Hancock, and Sleiman Matar. Asking questions to minimize errors. Technical Report WUCS-93-23, Washington University, Department of Computer Science, 1993.
	BHH92a	Nader H. Bshouty , Thomas R. Hancock , Lisa Hellerstein, Learning arithmetic read-once formulas, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.370-381, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129747]
	BHH92b	Nader H. Bshouty , Thomas R. Hancock , Lisa Hellerstein, Learning Boolean read-once formulas with arbitrary symmetric and constant fan-in gates, Proceedings of the fifth annual workshop on Computational learning theory, p.1-15, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130386]
	BHHK91	Nader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein, and Marek Karpinski. Learning Boolean read-once formulas with arbitrary symmetric and constant fan-in gates. Technical Report TR-92-020, International Computer Science Institute, 1991.
	BR92	Avrim Blum , Steven Rudich, Fast learning of k-term DNF formulas with queries, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.382-389, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129748]
	Bsh93	Nader H. Bshouty. Exact learning. Unpubhshed manuscript, 1993.
	Han91	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
	HKLW88	David Haussler , Michael Kearns , Nick Littlestone , Manfred K. Warmuth, Equivalence of models for polynomial learnability, Proceedings of the first annual workshop on Computational learning theory, p.42-55, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
	Lit88	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]
	MT92	Wolfgang Maass , György Turán, Lower Bound Methods and Separation Results for On-Line Learning Models, Machine Learning, v.9 n.2-3, p.107-145, July 1992 [doi>10.1007/BF00992674]
	NN90	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]
	RS89	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]
	RS90	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
	Val84	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]

CITED BY 9

	José L. Balcázar , Josep Díaz , Ricard Gavaldà , Osamu Watanabe, An optimal parallel algorithm for learning DFA, Proceedings of the seventh annual conference on Computational learning theory, p.208-217, July 12-15, 1994, New Brunswick, New Jersey, United States
	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
	Nader H. Bshouty , Zhixiang Chen , Scott E. Decatur , Steven Homer, On the learnability of Zn-DNF formulas (extended abstract), Proceedings of the eighth annual conference on Computational learning theory, p.198-205, July 05-08, 1995, Santa Cruz, California, United States
	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
	Zhixiang Chen , Steven Homer, On learning counting functions with queries, Proceedings of the seventh annual conference on Computational learning theory, p.218-227, July 12-15, 1994, New Brunswick, New Jersey, United States
	Henning Fernau, Even linear simple matrix languages: formal language properties and grammatical inference, Theoretical Computer Science, v.289 n.1, p.425-456, 23 October 2002
	Peter Auer , Philip M. Long, Simulating access to hidden information while learning, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.263-272, May 23-25, 1994, Montreal, Quebec, Canada
	Nader H. Bshouty, Exact Learning of Formulas in Parallel, Machine Learning, v.26 n.1, p.25-41, Jan. 1997
	Judy Goldsmith , Robert H. Sloan , Balázs Szörényi , György Turán, Theory revision with queries: horn, read-once, and parity formulas, Artificial Intelligence, v.156 n.2, p.139-176, July 2004