More efficient PAC-learning of DNF with membership queries under the uniform distribution

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

More efficient PAC-learning of DNF with membership queries under the uniform distribution

Full text

Pdf (1.14 MB)

Source

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

Santa Cruz, California, United States

Pages: 286 - 295

Year of Publication: 1999

ISBN:1-58113-167-4

Authors

Nader H. Bshouty	Dept. Computer Science, Technion, Haifa 32000, Israel
Jeffrey C. Jackson	Math. & Comp. Science Dept., Duquesne University, Pittsburgh, PA
Christino Tamon	Dept. Math & Comp. Science, Clarkson University, Potsdam, NY

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence
Univ. of California, : University of California at Santa Cruz

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 11, Citation Count: 11

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/307400.307472 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.

	A88	Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
	B92	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]
	BHL95	Avrim Blum , Lisa Hellerstein , Nick Littlestone, Learning in the presence of finitely or infinitely many irrelevant attributes, Journal of Computer and System Sciences, v.50 n.1, p.32-40, Feb. 1995 [doi>10.1006/jcss.1995.1004]
	BH96	Nader H. Bshouty , Lisa Hellerstein, Attribute-efficient learning in query and mistake-bound models, Proceedings of the ninth annual conference on Computational learning theory, p.235-243, June 28-July 01, 1996, Desenzano del Garda, Italy [doi>10.1145/238061.238108]
	DH94	A. Dhagat and L. Hellerstein. PAC Learning with Irrelevant Attributes. In Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, 64-74, 1994.
	D98	Peter Damaschke, Adaptive versus nonadaptive attribute-efficient learning, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.590-596, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276874]
	F90	Yoav Freund, Boosting a weak learning algorithm by majority, Proceedings of the third annual workshop on Computational learning theory, p.202-216, August 06-08, 1990, Rochester, New York, United States
	F93	Yoav Freund, An improved boosting algorithm and its implications on learning complexity, Proceedings of the fifth annual workshop on Computational learning theory, p.391-398, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130429]
	GL89	O. Goldreich , L. A. Levin, A hard-core predicate for all one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.25-32, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73010]
	H88	D. Haussler, Quantifying inductive bias: AI learning algorithms and Valiant's learning framework, Artificial Intelligence, v.36 n.2, p.177-221, September 1988 [doi>10.1016/0004-3702(88)90002-1]
	J97	Jeffrey C. Jackson, An efficient membership-query algorithm for learning DNF with respect to the uniform distribution, Journal of Computer and System Sciences, v.55 n.3, p.414-440, Dec. 1997 [doi>10.1006/jcss.1997.1533]
	K	A. Klivans. Personal communication.
	KM93	Eyal Kushilevitz , Yishay Mansour, Learning decision trees using the Fourier spectrum, SIAM Journal on Computing, v.22 n.6, p.1331-1348, Dec. 1993 [doi>10.1137/0222080]
	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]
	L93	L. Levin. Randomness and Non-determinism. Journal of Symbolic Logic, 58(3): 1102-1103, 1993.
	M92	Yishay Mansour, An O(nlog log n) learning algorithm for DNF under the uniform distribution, Proceedings of the fifth annual workshop on Computational learning theory, p.53-61, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130391]
	NN93	Joseph Naor , Moni Naor, Small-bias probability spaces: efficient constructions and applications, SIAM Journal on Computing, v.22 n.4, p.838-856, Aug. 1993 [doi>10.1137/0222053]
	UTW97	Ryuhei Uehara , Kensei Tsuchida , Ingo Wegener, Optimal Attribute-Efficient Learning of Disjunction, Parity and Threshold Functions, Proceedings of the Third European Conference on Computational Learning Theory, p.171-184, March 17-19, 1997
	V84	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]
	vL	J. H. Van Lint, Introduction to Coding Theory, Springer-Verlag New York, Inc., Secaucus, NJ, 1998

CITED BY 11

	Dmitry Gavinsky, Optimally-smooth adaptive boosting and application to agnostic learning, The Journal of Machine Learning Research, 4, p.101-117, 12/1/2003
	Elchanan Mossel , Ryan O'Donnell , Rocco P. Servedio, Learning juntas, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Adam R. Klivans , Rocco A. Servedio, Boosting and Hard-Core Set Construction, Machine Learning, v.51 n.3, p.217-238, June 2003
	Nader H. Bshouty , Dmitry Gavinsky, On boosting with polynomially bounded distributions, The Journal of Machine Learning Research, 3, 3/1/2003
	Adam R. Klivans , Ryan O'Donnell , Rocco A. Servedio, Learning intersections and thresholds of halfspaces, Journal of Computer and System Sciences, v.68 n.4, p.808-840, June 2004
	Rocco A. Servedio, On learning monotone DNF under product distributions, Information and Computation, v.193 n.1, p.57-74, 25 August 2004
	Elchanan Mossel , Ryan O'Donnell , Rocco A. Servedio, Learning functions of k relevant variables, Journal of Computer and System Sciences, v.69 n.3, p.421-434, November 2004
	Nader H. Bshouty , Elchanan Mossel , Ryan O'Donnell , Rocco A. Servedio, Learning DNF from random walks, Journal of Computer and System Sciences, v.71 n.3, p.250-265, October 2005
	Ariel Elbaz , Homin K. Lee , Rocco A. Servedio , Andrew Wan, Separating Models of Learning from Correlated and Uncorrelated Data, The Journal of Machine Learning Research, 8, p.277-290, 5/1/2007
	Dana Ron, Property Testing: A Learning Theory Perspective, Foundations and Trends® in Machine Learning, v.1 n.3, p.307-402, March 2008
	Vitaly Feldman, On The Power of Membership Queries in Agnostic Learning, The Journal of Machine Learning Research, 10, p.163-182, June 2009