Learning in the presence of malicious errors

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Learning in the presence of malicious errors

Full text

Pdf (1.41 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twentieth annual ACM symposium on Theory of computing table of contents

Chicago, Illinois, United States

Pages: 267 - 280

Year of Publication: 1988

ISBN:0-89791-264-0

Authors

Michael Kearns	Harvard University
Ming Li	Harvard University

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 55, Citation Count: 18

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions 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/62212.62238 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.

	AL86	Anghin, D., P. Laird, "Identifying kCNF formulas from noisy examples", Technical report YALEU/DCS/TR-478, Yale University, 1986.
	BEHW86	A Blumer , A Ehrenfeucht , D Haussler , M Warmuth, Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.273-282, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12158]
	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]
	C79	Chvatal, V., "A greedy keuristic for the set covering problem", Math. Op. Res., 4(3), 1979.
	EHKV87	Ehrenfeucht, A., D. Haussler, M. Kearns, L. Valiant, "A general lower bound on the number of examples needed for learning", Technical report UCSC- CRL-87-26, U.C. Santa Cruz, 1987.
	J74	Johnson, D., "Approximation algorithms for combinatorial problems", Journal o{ Computer and Systems Sciences, 9, 1974.
	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]
	L75	Lovazz, b., "On the ratio of optimal integral and fractional covers", Discrete Math, 13, 1975.
	N69	Nigmatullin, R., "The hstcst descent method for covering problems" (in Russian), Proceedings o! a Symposium on Question8 o! Precision and Efficiency o! Computer Algorithms, Kiev, 1969.
	R87	Rivest, R., "Le~g decision lists", Machine Learning, to appear.
	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]
	V85	Valiant, L., "Learning disjunctions of conjunctions'', 9th International Joint Con}erence on Artificial Intelligence, 1985.

CITED BY 18

	Roni Khardon , Dan Roth, Learning to reason, Journal of the ACM (JACM), v.44 n.5, p.697-725, Sept. 1997
	Avrim Blum , Prasad Chalasani, Learning switching concepts, Proceedings of the fifth annual workshop on Computational learning theory, p.231-242, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
	Dana Ron , Ronitt Rubinfeld, Learning fallible finite state automata, Proceedings of the sixth annual conference on Computational learning theory, p.218-227, July 26-28, 1993, Santa Cruz, California, United States
	Shai Ben-David , Eli Dichterman, Learning with restricted focus of attention, Proceedings of the sixth annual conference on Computational learning theory, p.287-296, July 26-28, 1993, Santa Cruz, California, United States
	Peter Auer, On-line learning of rectangles in noisy environments, Proceedings of the sixth annual conference on Computational learning theory, p.253-261, July 26-28, 1993, Santa Cruz, California, United States
	Michael Kearns, Efficient noise-tolerant learning from statistical queries, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.392-401, May 16-18, 1993, San Diego, California, United States
	Scott Evan Decatur, Statistical queries and faulty PAC oracles, Proceedings of the sixth annual conference on Computational learning theory, p.262-268, July 26-28, 1993, Santa Cruz, California, United States
	Javed A. Aslam , Scott E. Decatur, Specification and simulation of statistical query algorithms for efficiency and noise tolerance, Proceedings of the eighth annual conference on Computational learning theory, p.437-446, July 05-08, 1995, Santa Cruz, California, United States
	B. K. Natarajan, Occam's razor for functions, Proceedings of the sixth annual conference on Computational learning theory, p.370-376, July 26-28, 1993, Santa Cruz, California, United States
	Michele Flammini , Alberto Marchetti-Spaccamela , Luděk Kučera, Learning DNF formulae under classes of probability distributions, Proceedings of the fifth annual workshop on Computational learning theory, p.85-92, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
	Michael J. Kearns , Robert E. Schapire , Linda M. Sellie, Toward efficient agnostic learning, Proceedings of the fifth annual workshop on Computational learning theory, p.341-352, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
	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
	Javed A. Aslam , Aditi Dhagat, Searching in the presence of linearly bounded errors, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.486-493, May 05-08, 1991, New Orleans, Louisiana, United States
	S. Muthukrishnan, On optimal strategies for searching in presence of errors, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.680-689, January 23-25, 1994, Arlington, Virginia, United States
	Jyrki Kivinen , Heikki Mannila , Esko Ukkonen, Learning hierarchical rule sets, Proceedings of the fifth annual workshop on Computational learning theory, p.37-44, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
	Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989
	Yasubumi Sakakibara , Rani Siromoney, A noise model on learning sets of strings, Proceedings of the fifth annual workshop on Computational learning theory, p.295-302, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
	Michael O'Mahony , Neil Hurley , Nicholas Kushmerick , Guénolé Silvestre, Collaborative recommendation: A robustness analysis, ACM Transactions on Internet Technology (TOIT), v.4 n.4, p.344-377, November 2004