Boosting in the presence of noise

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Boosting in the presence of noise

Full text

Pdf (273 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-fifth annual ACM symposium on Theory of computing table of contents

San Diego, CA, USA

SESSION: Session 4B table of contents

Pages: 195 - 205

Year of Publication: 2003

ISBN:1-58113-674-9

Authors

Adam Kalai	M.I.T., Cambridge, MA
Rocco A. Servedio	Columbia University, New York, NY

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 29, Citation Count: 3

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

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/780542.780573 What is a DOI?

ABSTRACT

Boosting algorithms are procedures that "boost" low accuracy weak learning algorithms to achieve arbitrarily high accuracy. Over the past decade boosting has been widely used in practice and has become a major research topic in computational learning theory. In this paper we study boosting in the presence of random classification noise, giving both positive and negative results.We show that a modified version of a boosting algorithm due to Mansour and McAllester [14] can achieve accuracy arbitrarily close to the noise rate. We also give a matching lower bound by showing that no efficient black-box boosting algorithm can boost accuracy beyond the noise rate (assuming that one-way functions exist). Finally, we consider a variant of the standard scenario for boosting in which the "weak learner" satisfies a slightly stronger condition than the usual weak learning guarantee. We give an efficient algorithm in this framework which can boost to arbitrarily high accuracy in the presence of classification noise.

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	Javed A. Aslam , Scott E. Decatur, Specification and simulation of statistical query algorithms for efficiency and noise tolerance, Journal of Computer and System Sciences, v.56 n.2, p.191-208, April 1998 [doi>10.1006/jcss.1997.1558 ]
	2	A. Blum, A. Frieze, R. Kannan, and S. Vempala. A polynomial time algorithm for learning noisy linear threshold functions. Algorithmica, 22(1/2):35--52, 1997.
	3	Thomas G. Dietterich, An Experimental Comparison of Three Methods for Constructing Ensembles of Decision Trees: Bagging, Boosting, and Randomization, Machine Learning, v.40 n.2, p.139-157, Aug. 2000 [doi>10.1023/A:1007607513941 ]
	4	J. Friedman, T. Hastie, and R. Tibshirani. Additive logistic regression: A statistical view of boosting. The Annals of Statistics, 28:337 -- 374, 2000.
	5	Yoav Freund, Boosting a weak learning algorithm by majority, Information and Computation, v.121 n.2, p.256-285, Sept. 1995 [doi>10.1006/inco.1995.1136 ]
	6	Yoav Freund , Robert E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences, v.55 n.1, p.119-139, Aug. 1997 [doi>10.1006/jcss.1997.1504 ]
	7	Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
	8	Johan HÅstad , Russell Impagliazzo , Leonid A. Levin , Michael Luby, A Pseudorandom Generator from any One-way Function, SIAM Journal on Computing, v.28 n.4, p.1364-1396, Aug. 1999 [doi>10.1137/S0097539793244708]
	9	A. Kalai and R. Servedio. On the boosting ability of oblivious decision graphs. Unpublished manuscript, 2003.
	10	Michael Kearns, Efficient noise-tolerant learning from statistical queries, Journal of the ACM (JACM), v.45 n.6, p.983-1006, Nov. 1998 [doi>10.1145/293347.293351]
	11	Michael Kearns , Yishay Mansour, On the boosting ability of top-down decision tree learning algorithms, Journal of Computer and System Sciences, v.58 n.1, p.109-128, Feb. 1999 [doi>10.1006/jcss.1997.1543 ]
	12	Michael Kearns , Leslie Valiant, Cryptographic limitations on learning Boolean formulae and finite automata, Journal of the ACM (JACM), v.41 n.1, p.67-95, Jan. 1994 [doi>10.1145/174644.174647]
	13	Michael J. Kearns , Umesh V. Vazirani, An introduction to computational learning theory, MIT Press, Cambridge, MA, 1994
	14	Y. Mansour and D. McAllester. Boosting using branching programs. Journal of Computer and System Sciences, 64(1):103--112, 2002.
	15	Robert E. Schapire, The Strength of Weak Learnability, Machine Learning, v.5 n.2, p.197-227, Jun. 1990 [doi>10.1023/A:1022648800760]
	16	Robert E. Schapire, Theoretical Views of Boosting and Applications, Proceedings of the 10th International Conference on Algorithmic Learning Theory, p.13-25, December 06-08, 1999

CITED BY 3

	Alina Beygelzimer , Varsha Dani , Tom Hayes , John Langford , Bianca Zadrozny, Error limiting reductions between classification tasks, Proceedings of the 22nd international conference on Machine learning, p.49-56, August 07-11, 2005, Bonn, Germany
	Takafumi Kanamori , Takashi Takenouchi , Shinto Eguchi , Noboru Murata, Robust Loss Functions for Boosting, Neural Computation, v.19 n.8, p.2183-2244, August 2007
	Navin Goyal , Michael Saks, Rounds vs queries trade-off in noisy computation, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia