cvpr cvpr2013 cvpr2013-390 cvpr2013-390-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Xiao Liu, Mingli Song, Dacheng Tao, Zicheng Liu, Luming Zhang, Chun Chen, Jiajun Bu
Abstract: Node splitting is an important issue in Random Forest but robust splitting requires a large number of training samples. Existing solutions fail to properly partition the feature space if there are insufficient training data. In this paper, we present semi-supervised splitting to overcome this limitation by splitting nodes with the guidance of both labeled and unlabeled data. In particular, we derive a nonparametric algorithm to obtain an accurate quality measure of splitting by incorporating abundant unlabeled data. To avoid the curse of dimensionality, we project the data points from the original high-dimensional feature space onto a low-dimensional subspace before estimation. A unified optimization framework is proposed to select a coupled pair of subspace and separating hyperplane such that the smoothness of the subspace and the quality of the splitting are guaranteed simultaneously. The proposed algorithm is compared with state-of-the-art supervised and semi-supervised algorithms for typical computer vision applications such as object categorization and image segmen- tation. Experimental results on publicly available datasets demonstrate the superiority of our method.
[1] R. Achanta, A. Shaji, K. Smith, A. Luchi, P. Fua, and S. S ¨푢sstrunk. Slic superpixels compared to state-of-the-art superpixel methods. IEEE Trans. Pattern Anal. Mach. Intell., 34:2274–2282, 2012.
[2] M. Belkin, P. Niyogi, and V. Sindhwani. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. JMLR, 7:2399–2434, Dec. 2006.
[3] L. Breiman. Out-of-bag estimates. Technical report, 1966.
[4] L. Breiman. Random forests. Machine Learning, 45:5–32, 2001.
[5] L. Breiman, J. Friedman, R. Olshen, and C. Stone. Classification and regression trees. CA: Wadsworth Int., Belmont, 1984.
[6] C.-C. Chang and C.-J. Lin. Libsvm: a library for support vector machines. ACM Trans. Intell. Syst. Tech., 2, 2011.
[7] O. Chapelle, B. Sch 표¨lkopf, and A. Zien. Semi-supervised Learning. The MIT Press, Cambridge, Massachusetts, Lodon, England, 2006.
[8] A. Criminisi. Microsoft research cambridge object recognition image dataset. version 1.0, 2004.
[9] R. Duda and P. Hart. Pattern Classification and scene analysis. Wiley-Interscience, 1973.
[10] P. Geurts, D. Ernst, and L. Wehenkel. Extremely randomized trees. Machine Learning, 63:3–42, 2006.
[11] T. Ho. The random subspace method for constructing decision forests. IEEE Trans. Pattern Anal. Mach. Intell., 20:832–844, Aug. 1998.
[12] L. Hyafil and R. Rivest. Constructing optimal binary decision trees is NP-complete. Information Processing Letters, 5: 11–17, 1976.
[13] T. Joachims. Transductive inference for text classification using support vector machines. Proc. ICML, pages 200–209, 1999.
[14] C. Leistner, A. Saffari, J. Santner, and H. Bischof. Semisupervised random forests. Proc. ICCV, pages 506–5 13, Sept. 2009.
[15] F.-F. Li, R. Fergus, and P. Perona. Learning generative visual models from few training examples: an incremental bayesian approach tested on 101 objct categories. Proc. CVPR Workshop on Generative-Model Based Vision, 2004.
[16] H. Payne and W. Meisel. An algorithm for constructing optimal binary decision trees. IEEE Trans. Comput., C-26:905– 516, Sept. 1977.
[17] J. Quinlan. Induction of decision trees. Mach. Learn. , 1:81– 106, Mar. 1986.
[18] J. Quinlan. C4.5: Programs for machine learning. Morgan Kaufmann Publishers, 1993.
[19] E. Rounds. A combined non-parametric approach to feature selection and binary decision tree design. Pattern Recognition, 12:313–317, 1980.
[20] B. Silverman. Density Estimation for Statistics and Data Analysis. Chapman and Hall/CRC, Apr. 1986.
[21] C. Suen and Q. Wang. ISOETRP - an interactive clustering
[22]
[23]
[24]
[25]
[26] algorithm with new objectives. Pattern Recognition, 17:21 1– 219, 1984. C. Wu, D. Landgrebe, and P. Swain. The decision tree approach to classification. School Elec. Eng., Purdue Univ., Lafayette, IN, Rep. RE-EE 75-17, 1975. J. Yang, K. Yu, Y. Gong, and T. Huang. Linear spatial pyramid matching using sparse coding for image classification. Proc. CVPR, pages 1794–1801, 2009. Y. Yang, F. Nie, D. Xu, J. Luo, Y. Zhuang, and Y. Pan. A multimedia retrieval framework based on semi-supervised ranking and relevance feedback. IEEE Trans. Pattern Anal. Mach. Intell., 34:723–742, 2012. L. Zhang, M. Song, Z. Liu, X. Liu, J. Bu, and C. Chen. Probabilistic graphlet cut: Exploiting spatial structure cue for weakly supervised image segmentation. Proc. CVPR, 2013. T. Zhang and F. Oles. A probability analysis on the value of unlabeled data for classification problems. Proc. ICML, pages 1191–1 198, 2000. 444999779