Improved boosting algorithms using confidence-rated predictions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Improved boosting algorithms using confidence-rated predictions

Full text

Pdf (1.59 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: 80 - 91

Year of Publication: 1998

ISBN:1-58113-057-0

Authors

Robert E. Schapire	AT&T Labs, 180 Park Avenue, Florham Park, NJ
Yoram Singer	AT&T Labs, 180 Park Avenue, Florham Park, NJ

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): 3, Downloads (12 Months): 59, Citation Count: 46

Additional Information:

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/279943.279960 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	Peter L. Bartlett. The sample complexity of pattem classification with neural networks: the size of the weights is more important than the size of the network. IEEE Transactions on Information Theory, 1998 (to appeaD.
	2	Eric Bauer and Ron Kohavi. An empirical comparison of voting classification algorithms: Bagging, boosting, and variants. Unpublished manuscript, 1997.
	3	Eric B. Baum , David Haussler, What size net gives valid generalization?, Neural Computation, v.1 n.1, p.151-160, Spring 1990 [doi>10.1162/neco.1989.1.1.151]
	4	Avfim Blum. Empirical support for winnow and weightedmajority based algorithms: results on a calendar scheduling domain. In Proceedings of the Twelfth International Conj'krence on Machine Learning, pages 64-72, 1995.
	5	Leo Breiman. Aming classifiers. Annals of Statistics, to appear.
	6	Thomas G. Dietterich. An experimental comparison of three methods for constructing ensembles of decision trees: Bagging, boosting, and randomization, llnpublished manuscript, 1998.
	7	Thomas G. Dietterich and Ghulum Bakiri. Solving multiclass learning problems via error-cmrecting output codes. Journal of Artificial Intelligence Research, 2:263-286, January 1995.
	8	Hams Dmckerand Cofinna Cortes. Boosting decision trees. In Advances in Neural Information Processing Systems 8, pages 479-485, 1996.
	9	Yoav Freund and Robert E. Schapire. F, xpefiments with a new boosting algorithm. In Machine Learning: Proceedings of the Thirteenth International Conference, pages 148-156, 1996.
	10	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]
	11	Yoav Freund , Robert E. Schapire , Yoram Singer , Manfred K. Warmuth, Using and combining predictors that specialize, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.334-343, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258616]
	12	David Haussler, Decision theoretic generalizations of the PAC model for neural net and other learning applications, Information and Computation, v.100 n.1, p.78-150, Sept. 1992 [doi>10.1016/0890-5401(92)90010-D]
	13	David Haussler , Philip M. Long, A generalization of Sauer's lemma, Journal of Combinatorial Theory Series A, v.71 n.2, p.219-240, Aug. 1995 [doi>10.1016/0097-3165(95)90001-2]
	14	Michael Kearns , Yishay Mansour, On the boosting ability of top-down decision tree learning algorithms, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.459-468, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237994]
	15	Richard Maclin and David Opitz. An empirical evaluation of bagging and boosting. In Proceedings of the Fourteenth National Conference on Artificial Intelligence, pages 546- 551, 1997.
	16	Dragos D. Margineantu , Thomas G. Dietterich, Pruning Adaptive Boosting, Proceedings of the Fourteenth International Conference on Machine Learning, p.211-218, July 08-12, 1997
	17	C. J. Merz and P. M. Murphy. UCI repository of machine leaming Databases,1998. http://www.ics .uci.edu/,,mtleam/MLRe pository.html.
	18	J. R. Quinlan. Bagging, boosting, and C4.5. In Proceedings of the Thirteenth National Conference on Artificial Intelligence, pages 725-730, 1996.
	19	Robert E. Schapire, Using output codes to boost multiclass learning problems, Proceedings of the Fourteenth International Conference on Machine Learning, p.313-321, July 08-12, 1997
	20	Robert E. Schapire, Yoav Freund, Peter Bartlett, and Wee Sun Lee. Boosting the margin: A new explanation for the effectiveness of voting methods. Annals of Statistics, to appear.
	21	Robert E. Schapire and Yoram Singer. BoosTexter: A system for multiclass multi-label text categorization. Unpublished manuscript, 1998.
	22	Holger Schwenk , Yoshua Bengio, Training methods for adaptive boosting of neural networks, Proceedings of the 1997 conference on Advances in neural information processing systems 10, p.647-653, July 1998, Denver, Colorado, United States

CITED BY 46

	Wei Fan , Salvatore J. Stolfo , Junxin Zhang, The application of AdaBoost for distributed, scalable and on-line learning, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.362-366, August 15-18, 1999, San Diego, California, United States
	Stan Z. Li , ZhenQiu Zhang, FloatBoost Learning and Statistical Face Detection, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.9, p.1112-1123, September 2004
	Robert E. Schapire, Drifting games, Proceedings of the twelfth annual conference on Computational learning theory, p.114-124, July 07-09, 1999, Santa Cruz, California, United States
	Masayuki Nakamura , Hiroki Nomiya , Kuniaki Uehara, Improvement of Boosting Algorithm by Modifying the Weighting Rule, Annals of Mathematics and Artificial Intelligence, v.41 n.1, p.95-109, May 2004
	Yoav Freund, An adaptive version of the boost by majority algorithm, Proceedings of the twelfth annual conference on Computational learning theory, p.102-113, July 07-09, 1999, Santa Cruz, California, United States
	John C. Henderson , Eric Brill, Bagging and boosting a treebank parser, Proceedings of the first conference on North American chapter of the Association for Computational Linguistics, p.34-41, April 29-May 04, 2000, Seattle, Washington
	Philip K. Chan , Wei Fan , Andreas L. Prodromidis , Salvatore J. Stolfo, Distributed Data Mining in Credit Card Fraud Detection, IEEE Intelligent Systems, v.14 n.6, p.67-74, November 1999
	Yushi Jing , Vladimir Pavlović , James M. Rehg, Efficient discriminative learning of Bayesian network classifier via boosted augmented naive Bayes, Proceedings of the 22nd international conference on Machine learning, p.369-376, August 07-11, 2005, Bonn, Germany
	Juan J. Rodríguez , Carlos J. Alonso, Interval and dynamic time warping-based decision trees, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus
	Eiji Takimoto , Akira Maruoka, Top-down decision tree learning as information based boosting, Theoretical Computer Science, v.292 n.2, p.447-464, 27 January 2003
	Venkatesan Guruswami , Amit Sahai, Multiclass learning, boosting, and error-correcting codes, Proceedings of the twelfth annual conference on Computational learning theory, p.145-155, July 07-09, 1999, Santa Cruz, California, United States
	Massimiliano Ciaramita, Boosting automatic lexical acquisition with morphological information, Proceedings of the ACL-02 workshop on Unsupervised lexical acquisition, p.17-25, July 12-12, 2002, Philadelphia, Pennsylvania
	David G. T. Denison, Boosting with Bayesian stumps, Statistics and Computing, v.11 n.2, p.171-178, April 2001
	Min-Ling Zhang , Zhi-Hua Zhou, ML-KNN: A lazy learning approach to multi-label learning, Pattern Recognition, v.40 n.7, p.2038-2048, July, 2007
	Eugene Charniak , Mark Johnson, Edit detection and parsing for transcribed speech, Second meeting of the North American Chapter of the Association for Computational Linguistics on Language technologies 2001, p.1-9, June 01-07, 2001, Pittsburgh, Pennsylvania
	Marc Sebban , Richard Nock , Stéphane Lallich, Stopping criterion for boosting based data reduction techniques: from binary to multiclass problem, The Journal of Machine Learning Research, 3, 3/1/2003
	Anthony Tomasic , Isaac Simmons , John Zimmerman, Learning information intent via observation, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada
	Kingshy Goh , Beitao Li , Edward Y. Chang, Semantics and feature discovery via confidence-based ensemble, ACM Transactions on Multimedia Computing, Communications, and Applications (TOMCCAP), v.1 n.2, p.168-189, May 2005
	Juan J. Rodríguez , Carlos J. Alonso , Henrik Boström, Boosting interval based literals, Intelligent Data Analysis, v.5 n.3, p.245-262, August 2001
	Tamás Horváth , Susanne Hoche , Stefan Wrobel, Effective rule induction from labeled graphs, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France
	Beitao Li , Kingshy Goh, Confidence-based dynamic ensemble for image annotation and semantics discovery, Proceedings of the eleventh ACM international conference on Multimedia, November 02-08, 2003, Berkeley, CA, USA
	M. Di Marzio , C. C. Taylor, Kernel density classification and boosting: an L2 analysis, Statistics and Computing, v.15 n.2, p.113-123, April 2005
	Richard Nock, Complexity in the case against accuracy estimation, Theoretical Computer Science, v.301 n.1-3, p.143-165, 14 May 2003
	John Lafferty, Additive models, boosting, and inference for generalized divergences, Proceedings of the twelfth annual conference on Computational learning theory, p.125-133, July 07-09, 1999, Santa Cruz, California, United States
	King-Shy Goh , Edward Y. Chang , Beitao Li, Using One-Class and Two-Class SVMs for Multiclass Image Annotation, IEEE Transactions on Knowledge and Data Engineering, v.17 n.10, p.1333-1346, October 2005
	Gerard Escudero , Lluís Màrquez , German Rigau, An empirical study of the domain dependence of supervised word sense disambiguation systems, Proceedings of the 2000 Joint SIGDAT conference on Empirical methods in natural language processing and very large corpora: held in conjunction with the 38th Annual Meeting of the Association for Computational Linguistics, p.172-180, October 07-08, 2000, Hong Kong
	Koby Crammer , Ofer Dekel , Joseph Keshet , Shai Shalev-Shwartz , Yoram Singer, Online Passive-Aggressive Algorithms, The Journal of Machine Learning Research, 7, p.551-585, 12/1/2006
	James Bergstra , Norman Casagrande , Dumitru Erhan , Douglas Eck , Balázs Kégl, Aggregate features and ADABOOST for music classification, Machine Learning, v.65 n.2-3, p.473-484, December 2006
	Adam R. Klivans , Rocco A. Servedio, Boosting and Hard-Core Set Construction, Machine Learning, v.51 n.3, p.217-238, June 2003
	Gunnar Rätsch , Sebastian Mika , Bernhard Schölkopf , Klaus-Robert Müller, Constructing Boosting Algorithms from SVMs: An Application to One-Class Classification, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.9, p.1184-1199, September 2002
	Nicola Giusti , Francesco Masulli , Alessandro Sperduti, Theoretical and Experimental Analysis of a Two-Stage System for Classification, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.7, p.893-904, July 2002
	Juan J. Rodríguez , Jesús Maudes, Boosting recombined weak classifiers, Pattern Recognition Letters, v.29 n.8, p.1049-1059, June, 2008
	Jyrki Kivinen , Manfred K. Warmuth, Boosting as entropy projection, Proceedings of the twelfth annual conference on Computational learning theory, p.134-144, July 07-09, 1999, Santa Cruz, California, United States
	Rens Bod, What is the minimal set of fragments that achieves maximal parse accuracy?, Proceedings of the 39th Annual Meeting on Association for Computational Linguistics, p.66-73, July 06-11, 2001, Toulouse, France
	Min-Ling Zhang, Ml-rbf: RBF Neural Networks for Multi-Label Learning, Neural Processing Letters, v.29 n.2, p.61-74, April 2009
	Tina Eliassi-Rad , Jude Shavlik, A System for Building Intelligent Agents that Learn to Retrieve and Extract Information, User Modeling and User-Adapted Interaction, v.13 n.1-2, p.35-88, February -May 2003
	Ron Bekkerman , Ran El-Yaniv , Naftali Tishby , Yoad Winter, Distributional word clusters vs. words for text categorization, The Journal of Machine Learning Research, 3, 3/1/2003
	Holger Schwenk , Yoshua Bengio, Boosting Neural Networks, Neural Computation, v.12 n.8, p.1869-1887, August 2000
	Ilkka Autio, Using natural class hierarchies in multi-class visual classification, Pattern Recognition, v.39 n.7, p.1290-1299, July, 2006
	Robert E. Schapire , Yoram Singer, BoosTexter: A Boosting-based Systemfor Text Categorization, Machine Learning, v.39 n.2-3, p.135-168, May-June 2000
	Tina Eliassi-Rad , Jude Shavlik, Intelligent Web agents that learn to retrieve and extract information, Intelligent exploration of the web, Physica-Verlag GmbH, Heidelberg, Germany, 2003
	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
	Nada Lavrač , Branko Kavšek , Peter Flach , Ljupčo Todorovski, Subgroup Discovery with CN2-SD, The Journal of Machine Learning Research, 5, p.153-188, 12/1/2004
	G. Rätsch , T. Onoda , K.-R. Müller, Soft Margins for AdaBoost, Machine Learning, v.42 n.3, p.287-320, March 2001
	Rens Bod, Do all fragments count?, Natural Language Engineering, v.9 n.4, p.307-323, December 2003
	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