Improved lower bounds for learning from noisy examples

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Improved lower bounds for learning from noisy examples: an information-theoretic approach

Full text

Pdf (1.72 MB)

Source

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

Madison, Wisconsin, United States

Pages: 104 - 115

Year of Publication: 1998

ISBN:1-58113-057-0

Authors

Claudio Gentile	DSI, Universita' di Milano, Via Comelico 39, 20135 Milano, Italy
David P. Helmbold	Computer Science Department, University of California, 95064 Santa Cruz

Sponsors

University of Wisconsin : University of Wisconsin
UC @ Santa Cruz : UC @ Santa Cruz
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): 5, Downloads (12 Months): 29, Citation Count: 1

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

	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	Dana Angluin , Mārtiņš Kriķis , Robert H. Sloan , György Turán, Malicious Omissions and Errors in Answers to Membership Queries, Machine Learning, v.28 n.2-3, p.211-255, Aug./Sept. 1997 [doi>10.1023/A:1007311411259]
	4	Dana Angluin , Philip Laird, Learning From Noisy Examples, Machine Learning, v.2 n.4, p.343-370, April 1988 [doi>10.1023/A:1022873112823]
	5	B. Apolloni , C. Gentile, Sample size lower bounds in PAC learning by algorithmic complexity theory, Theoretical Computer Science, v.209 n.1-2, p.141-162, Dec. 6, 1998 [doi>10.1016/S0304-3975(97)00102-3]
	6	Javed A. Aslam , Scott E. Decatur, On the sample complexity of noise-tolerant learning, Information Processing Letters, v.57 n.4, p.189-195, Feb. 26, 1996 [doi>10.1016/0020-0190(96)00006-3]
	7	Peter L. Bartlett, Learning with a slowly changing distribution, Proceedings of the fifth annual workshop on Computational learning theory, p.243-252, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130412]
	8	P. Bartlett, D. Helmbold, manuscript, 1996.
	9	Rakesh D. Barve , Philip M. Long, On the complexity of learning from drifting distributions, Information and Computation, v.138 n.2, p.170-193, Nov. 1, 1997 [doi>10.1006/inco.1997.2656]
	10	Gyora M. Benedek , Alon Itai, Learnability with respect to fixed distributions, Theoretical Computer Science, v.86 n.2, p.377-389, Sept. 2, 1991 [doi>10.1016/0304-3975(91)90026-X]
	11	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 [doi>10.1145/76359.76371]
	12	N. Cesa-Bianchi, E. Dichterman, P. Fischer, E. Shamir, H.U. Simon, "Sample-efficient Strategies for Learning in the Presence of Noise", eCOLT Tech. Rep. 97- 003, WWW.' http://ecolt.informatik, uni-dortmund, de/. Preliminary versions in 28th STOC, 1996 and 3rd EuroCOLT, 1997
	13	Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
	14	R.L. Dobrushin, "General formulation of Shannon's main theorem in information theory", Uspelchi Mat. Nauk, vol. 14, pp. 3-104, 1959; translated in Amer. Math. Soc. Translations, Ser. 2, vol. 33, pp. 323-438, 1963.
	15	R.M. Dudley, A Course on Empirical Processes. Lecture Notes in Mathematics, vol. 1097, Spfinger-Vefiag, Berlin/New York, 1984.
	16	Andrzej Ehrenfeucht , David Haussler, A general lower bound on the number of examples needed for learning, Information and Computation, v.82 n.3, p.247-261, Sep. 1989 [doi>10.1016/0890-5401(89)90002-3]
	17	Bonnie Eisenberg , Ronald L. Rivest, On the sample complexity of pac-learning using random and chosen examples, Proceedings of the third annual workshop on Computational learning theory, p.154-162, August 06-08, 1990, Rochester, New York, United States
	18	C. Gentile, "A note on sample size lower bounds for PAC-leaming", manuscript, 1997.
	19	D. Haussler, A. Barron, "How well do Bayes methods work for on-line prediction of {-1 ,+ 1 } values'?.", in Proc. of the 3rd NEC Symposium on Computation and Cognition, 1992, pp. 74-100.
	20	David Haussler , Michael Kearns , Robert E. Schapire, Bounds on the Sample Complexity of Bayesian Learning Using Information Theory and the VC Dimension, Machine Learning, v.14 n.1, p.83-113, Jan. 1994 [doi>10.1023/A:1022698821832]
	21	D. Haussler , N. Littlestone , M. K. Warmuth, Predicting {0, 1}-functions on randomly drawn points, Information and Computation, v.115 n.2, p.248-292, Dec. 1994 [doi>10.1006/inco.1994.1097]
	22	D. Haussler, M. Opper, "Mutual Information, Metric Entropy, and Cumulative Relative Entropy Risk", Annals of Statistics, 1997. To appear.
	23	D. Helmbold, N. Littlestone, P. Long, "Apple Tasting'', manuscript 1997. An extended abstract appeared in Proc. of the 33rd Symposium on the Foundations of Comp. Sci., 1992, pp.493-502.
	24	S. Ihara, Information theory for continuous systems. River Edge, NJ: World Scientific, 1993.
	25	Michael Kearns , Ming Li, Learning in the presence of malicious errors, SIAM Journal on Computing, v.22 n.4, p.807-837, Aug. 1993 [doi>10.1137/0222052]
	26	A.N. Kolmogorov, V.M. Tihomirov, "e-entropy and ecapacity of sets in functional spaces", Amer. Math. Soc. Translations (Ser. 2), vol. 17, pp. 277-364, 1961.
	27	Philip D. Laird, Learning from good and bad data, Kluwer Academic Publishers, Norwell, MA, 1988
	28	W. Maass, G. Turfin, "On the complexity of learning from counterexamples and membership queries", in Proc. of the 31th Symposium on the Foundations of Comp. Sci., 1990, pp. 203-210.
	29	Yasubumi Sakakibara, On learning from queries and counterexamples in the presence of noise, Information Processing Letters, v.37 n.5, p.279-284, March 14, 1991 [doi>10.1016/0020-0190(91)90220-C]
	30	Hans Ulrich Simon, General bounds on the number of examples needed for learning probabilistic concepts, Journal of Computer and System Sciences, v.52 n.2, p.239-254, April 1996 [doi>10.1006/jcss.1996.0019]
	31	Robert H. Sloan, Four types of noise in data for PAC learning, Information Processing Letters, v.54 n.3, p.157-162, May 12, 1995 [doi>10.1016/0020-0190(95)00016-6]
	32	George Shackelford , Dennis Volper, Learning k-DNF with noise in the attributes, Proceedings of the first annual workshop on Computational learning theory, p.97-103, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
	33	György Turán, Lower bounds for PAC learning with queries, Proceedings of the sixth annual conference on Computational learning theory, p.384-391, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168382]
	34	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]
	35	Vladimir Vapnik, Estimation of Dependences Based on Empirical Data: Springer Series in Statistics (Springer Series in Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 1982
	36	Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
	37	B. Yu, "Lower Bounds on Expected Redundancy for Nonparametric Classes", IEEE Trans. on Inf. Th., vol. 42, no. 1, pp. 272-275, 1996.