cvpr cvpr2013 cvpr2013-39 cvpr2013-39-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Samuel Schulter, Paul Wohlhart, Christian Leistner, Amir Saffari, Peter M. Roth, Horst Bischof
Abstract: This paper introduces a novel classification method termed Alternating Decision Forests (ADFs), which formulates the training of Random Forests explicitly as a global loss minimization problem. During training, the losses are minimized via keeping an adaptive weight distribution over the training samples, similar to Boosting methods. In order to keep the method as flexible and general as possible, we adopt the principle of employing gradient descent in function space, which allows to minimize arbitrary losses. Contrary to Boosted Trees, in our method the loss minimization is an inherent part of the tree growing process, thus allowing to keep the benefits ofcommon Random Forests, such as, parallel processing. We derive the new classifier and give a discussion and evaluation on standard machine learning data sets. Furthermore, we show how ADFs can be easily integrated into an object detection application. Compared to both, standard Random Forests and Boosted Trees, ADFs give better performance in our experiments, while yielding more compact models in terms of tree depth.
[1] Y. Amit and D. Geman. Shape Quantization and Recognition with Randomized Trees. Neural Computation, 9(7): 1545– 1588, 1997. 1, 2, 6
[2] M. Andriluka, S. Roth, and B. Schiele. People-Trackingby-Detection and People-Detection-by-Tracking. In CVPR, 2008. 7
[3] G. Biau, L. Devroye, and G. Lugosi. Consistency of Random Forests and Other Averaging Classifiers. JMLR, 9(9):2015– 2033, 2008. 1
[4] C. M. Bishop. Pattern Recogntion and Machine Learning. Springer, 2007. 2
[5] L. Breiman. Random Forests. ML, 45(1):5–32, 2001. 1, 2, 4, 5, 6
[6] T. E. d. Campo, B. R. Babu, and M. Varma. Character Recognition in Natural Images. In VISAPP, 2009. 5
[7] R. Caruana, N. Karampatziakis, and A. Yessenalina. An em-
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19] pirical Evaluation of Supervised Learning in High Dimensions. In ICML, 2008. 1 O. Chapelle, B. Sch o¨lkopf, and A. Zien, editors. SemiSupervised Learning. MIT Press, 2006. 5 A. Criminsi and J. Shotton. Decision Forests for Computer Vision and Medical Image Analysis. Springer, 2013. 1 M. Everingham, L. Van Gool, C. K. I. Williams, J. Winn, and A. Zisserman. The Pascal Visual Object Classes (VOC) Challenge. IJCV, 88(2):303–338, 2010. 7 A. Frank and A. Asuncion. UCI Machine Learning Repository, 2010. University of California, Irvine, School of Information and Computer Sciences. Available online at http://archive.ics.uci.edu/ml. 5 Y. Freund and L. Mason. The Alternating Decision Tree Learning Algorithm. In ICML, 1999. 4 Y. Freund and R. E. Shapire. Experiments with a New Boosting Algorithm. In ICML, 1996. 3 Y. Freund and R. E. Shapire. A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting. Journal of Computer and System Sciences, 55(1): 119–139, 1997. 3 J. H. Friedman. Greedy Function Approximation: A Gradient Boosting Machine. The Annals of Statistics, 29(5): 1189– 1232, 2001. 2, 3 J. Gall and V. Lempitsky. Class-Specific Hough Forests for Object Detection. In CVPR, 2009. 1, 6, 7 T. Hastie, R. Tibshirani, and J. H. Friedman. The Elements of Statistical Learning. Springer, 2009. 3, 4, 5, 6, 7 J. J. Hull. A Database for Handwritten Text Recognition Research. PAMI, 16(5):550–554, 1994. 5 J. Jancsary, S. Nowozin, and C. Rother. Loss-Specific Train-
[20]
[21]
[22]
[23]
[24]
[25]
[26]
[27]
[28]
[29]
[30] ing of Non-Parametric Image Restoration Models: A New State of the Art. In ECCV, 2012. 5 P. Kontschieder, S. Rota Bul o`, A. Criminisi, P. Kohli, M. Pelillo, and H. Bischof. Context-Sensitive Decision Forests for Object Detection. In NIPS, 2012. 5 B. Leibe, N. Cornelis, K. Cornelis, and L. Van Gool. Dynamic 3D Scene Analysis from a Moving Vehicle. In CVPR, 2007. 7 C. Leistner, A. Saffari, and H. Bischof. Semi-Supervised Random Forests. In ICCV, 2009. 2 Y. Lin. A Note on Margin-based Loss Functions in Classification. Statistics & Probability Letters, 68(1):73–82, 2004. 2 H. Masnadi-Shirazi, V. Mahadevan, and N. Vasconcelos. On the design ofrobust classifiers for computer vision. In CVPR, 2010. 3, 5, 6 H. Masnadi-Shirazi and N. Vasconcelos. On the Design of Loss Functions for Classication: theory, robustness to outliers, and SavageBoost. In NIPS, 2008. 3, 5, 6 T. Mitchell. Machine Learning. Mcgraw-Hill Higher Education, 1997. 2 A. Montillo, J. Shotton, J. Winn, J. E. Iglesias, D. Metaxas, and A. Criminisi. Entangled Decision Forests and their Application for Semantic Segmentation of CT Images. In IPMI, 2011. 5 F. Moosmann, B. Triggs, and F. Jurie. Fast discriminative visual codebooks using randomized clustering forests. In NIPS, 2006. 1 R. E. Shapire. The Strength of Weak Learnability. ML, 5(2): 197–227, 1990. 3 J. Shotton, M. Johnson, and R. Cipolla. Semantic texton forests for image categorization and segmentation. In CVPR, 2008. 1 [3 1] H. Zou, J. Zhu, and T. Hastie. New multicategory boosting algorithms based on multicategory Fisher-consistent losses. Annals of Applied Statistics, 2(4): 1290–1306, 2008. 2 555 111533