On learning visual concepts and DNF formulae

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On learning visual concepts and DNF formulae

Full text

Pdf (881 KB)

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: 317 - 326

Year of Publication: 1993

ISBN:0-89791-611-5

Authors

Eyal Kushilevitz
Dan Roth

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): 8, Citation Count: 6

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.168362 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	D. Angluin, M. Frazier, and L. Pitt. Learning conjunction of Horn' clauses. In Proceedings of the IEEE Syrup. on Foundation of Computer Science, number 31, pages 186-192, 1990.
	AHP92	H. Aizenstein, L. Hellerstein, and L. Pitt. Read-thrice DNF is hard to learn with membership and equivalence queries. In Proceedings of the IEEE Symp. on Foundation of Computer Science, number 33, pages 523- 532, Pittsburgh, Pennsylvania, 1992.
	Ang80	Dana Angluin. Finding patterns common to a set of strings. Journal of Computer and System Sciences, 21(1):46-62, August 1980.
	Ang92	Dana Angluin, Computational learning theory: survey and selected bibliography, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.351-369, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129746]
	BEHW87	Alselm Blumer , Andrzej Ehrenfeucht , David Haussler , Manfred K. Warmuth, Occam's razor, Information Processing Letters, v.24 n.6, p.377-380, 6 April 1987 [doi>10.1016/0020-0190(87)90114-1]
	Blu92	Avrim Blum, Learning Boolean Functions in an Infinite Attribute Space, Machine Learning, v.9 n.4, p.373-386, Oct. 1992 [doi>10.1023/A:1022653502461]
	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]
	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
	Jer91	M. Jerrum.Simple translationinvariant concepts are hard to learn. Technical Report CSR-12-91, University of Edinburgh, Department of Computer Science, 1991.
	KLPV87	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]
	KP89	Michael Kearns , Leonard Pitt, A polynomial-time algorithm for learning k-variable pattern languages from examples, Proceedings of the second annual workshop on Computational learning theory, p.57-71, December 1989, Santa Cruz, California, 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]
	Lit89	N. Littlestone, Mistake bounds and logarithmic linear-threshold learning algorithms, University of California at Santa Cruz, Santa Cruz, CA, 1990
	Riv87	Ronald L. Rivest, Learning Decision Lists, Machine Learning, v.2 n.3, p.229-246, November 1987 [doi>10.1023/A:1022607331053]
	Sch90	Robert E. Schapire, Pattern languages are not learnable, Proceedings of the third annual workshop on Computational learning theory, p.122-129, August 06-08, 1990, Rochester, New York, United States
	Shv90	H. Shvayster, Learnable and Nonlearnable Visual Concepts, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.5, p.459-466, May 1990 [doi>10.1109/34.55105]
	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]
	Val85	L.G. Valiant. Learning disjunctions of conjunctions. In Proceedings of the International Joint Conference of Artificial Intelligence, pages 560-566. Morgan Kaufmann, August 1985.

CITED BY 6

	Adam R. Klivans , Rocco Servedio, Learning DNF in time, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.258-265, July 2001, Hersonissos, Greece
	Nader H. Bshouty , Jeffrey C. Jackson, Learning DNF over the uniform distribution using a quantum example oracle, Proceedings of the eighth annual conference on Computational learning theory, p.118-127, July 05-08, 1995, Santa Cruz, California, United States
	Avrim Blum , Roni Khardon , Eyal Kushilevitz , Leonard Pitt , Dan Roth, On learning Read-k-Satisfy-j DNF, Proceedings of the seventh annual conference on Computational learning theory, p.110-117, July 12-15, 1994, New Brunswick, New Jersey, United States
	Adam R. Klivans , Rocco A. Servedio, Learning DNF in time 2^{õ(n^1/3)}, Journal of Computer and System Sciences, v.68 n.2, p.303-318, March 2004
	Avrim Blum , Merrick Furst , Jeffrey Jackson , Michael Kearns , Yishay Mansour , Steven Rudich, Weakly learning DNF and characterizing statistical query learning using Fourier analysis, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.253-262, May 23-25, 1994, Montreal, Quebec, Canada
	Dan Roth, Learning to reason the non monotonic case, Proceedings of the 14th international joint conference on Artificial intelligence, p.1178-1184, August 20-25, 1995, Montreal, Quebec, Canada