On the boosting ability of top-down decision tree learning algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the boosting ability of top-down decision tree learning algorithms

Full text

Pdf (1.14 MB)

Source

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

Philadelphia, Pennsylvania, United States

Pages: 459 - 468

Year of Publication: 1996

ISBN:0-89791-785-5

Authors

Michael Kearns	AT&T Research
Yishay Mansour	Tel-Aviv 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): 48, Citation Count: 17

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/237814.237994 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	In Machine Learning: Proceedings of the International Conference. Morgan Kaufmann, 1982-1995.
	2	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 [doi>10.1145/195058.195147]
	3	L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. Classification and Regression Trees. Wadsworth International Group, 1984.
	4	N. H. Bshouty , Y. Mansour, Simple learning algorithms for decision trees and multivariate polynomials, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.304, October 23-25, 1995
	5	N. H. Bshouty. Exact learning via the monotone theory. In Proceedings of the 34th IEEE Symposium on the Foundations of Computer Science, pages 302-311. IEEE Computer Society Press, Los Alamitos, CA, 1993.
	6	Wray Buntine , Tim Niblett, A Further Comparison of Splitting Rules for Decision-Tree Induction, Machine Learning, v.8 n.1, p.75-85, Jan. 1992 [doi>10.1023/A:1022686419106]
	7	T. Dietterich, M. Keams, and Y. Mansour. Applying the weak learning framework to understand and improve C4.5. Unpublished manuscript, 1996.
	8	Y. Freund and R. Schapire. Some experiments with a new boosting algorithm. Unpublished manuscript, 1996.
	9	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]
	10	Yoav Freund , Robert E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Proceedings of the Second European Conference on Computational Learning Theory, p.23-37, March 13-15, 1995
	11	J. Jackson. An efficient membership query algorithm for learning DNF with respect to the uniform distribution. In Proceedings of the 35th IEEE Symposium on the Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 1994.
	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	Eyal Kushilevitz , Yishay Mansour, Learning decision trees using the Fourier spectrum, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.455-464, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103466]
	14	John Mingers, An Empirical Comparison of Selection Measures for Decision-Tree Induction, Machine Learning, v.3 n.4, p.319-342, March 1989 [doi>10.1023/A:1022645801436]
	15	J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
	16	Robert E. Schapire, The Strength of Weak Learnability, Machine Learning, v.5 n.2, p.197-227, Jun. 1990 [doi>10.1023/A:1022648800760]
	17	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]

CITED BY 17

	Robert E. Schapire , Yoram Singer, Improved boosting algorithms using confidence-rated predictions, Proceedings of the eleventh annual conference on Computational learning theory, p.80-91, July 24-26, 1998, Madison, Wisconsin, United States
	Robert E. Schapire , Yoram Singer, Improved Boosting Algorithms Using Confidence-rated Predictions, Machine Learning, v.37 n.3, p.297-336, Dec. 1999
	Eiji Takimotoa , Akira Maruokaa , Volodya Vovk, Predicting nearly as well as the best pruning of a decision tree through dynamic programming scheme, Theoretical Computer Science, v.261 n.1, p.179-209, 06/17/2001
	Ron Meir , Gunnar Rätsch, An introduction to boosting and leveraging, Advanced lectures on machine learning, Springer-Verlag New York, Inc., New York, NY, 2003
	Erin L. Allwein , Robert E. Schapire , Yoram Singer, Reducing multiclass to binary: a unifying approach for margin classifiers, The Journal of Machine Learning Research, 1, p.113-141, 9/1/2001
	R. Servedio, PAC Analogues of Perceptron and Winnow Via Boosting the Margin, Machine Learning, v.47 n.2-3, p.133-151, May-June 2002
	Shie Mannor , Ron Meir, On the Existence of Linear Weak Learners and Applications to Boosting, Machine Learning, v.48 n.1-3, p.219-251, 2002
	Leonard A. Breslow , David W. Aha, Simplifying decision trees: A survey, The Knowledge Engineering Review, v.12 n.1, p.1-40, January 1997
	Pierre-Alain Laur , Richard Nock , Jean-Emile Symphor , Pascal Poncelet, Mining evolving data streams for frequent patterns, Pattern Recognition, v.40 n.2, p.492-503, February, 2007
	Michael Lindenbaum , Shai Ben-David, VC-Dimension Analysis of Object Recognition Tasks, Journal of Mathematical Imaging and Vision, v.10 n.1, p.27-49, Jan. 1999
	György Turán, Remarks on computational learning theory, Annals of Mathematics and Artificial Intelligence, v.28 n.1-4, p.43-45, 2000
	Sreerama K. Murthy, Automatic Construction of Decision Trees from Data: A Multi-Disciplinary Survey, Data Mining and Knowledge Discovery, v.2 n.4, p.345-389, December 1998
	David G. T. Denison, Boosting with Bayesian stumps, Statistics and Computing, v.11 n.2, p.171-178, April 2001
	Adam Tauman Kalai , Yishay Mansour , Elad Verbin, On agnostic boosting and parity learning, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Sivan Sabato , Shai Shalev-Shwartz, Ranking Categorical Features Using Generalization Properties, The Journal of Machine Learning Research, 9, p.1083-1114, 6/1/2008
	Wei Fan, On the optimality of probability estimation by random decision trees, Proceedings of the 19th national conference on Artifical intelligence, p.336-341, July 25-29, 2004, San Jose, California
	Charles Elkan, The foundations of cost-sensitive learning, Proceedings of the 17th international joint conference on Artificial intelligence, p.973-978, August 04-10, 2001, Seattle, WA, USA