cvpr cvpr2013 cvpr2013-390 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.
Reference: text
sentIndex sentText sentNum sentScore
1 com♮ Abstract Node splitting is an important issue in Random Forest but robust splitting requires a large number of training samples. [sent-6, score-1.011]
2 In this paper, we present semi-supervised splitting to overcome this limitation by splitting nodes with the guidance of both labeled and unlabeled data. [sent-8, score-1.444]
3 In particular, we derive a nonparametric algorithm to obtain an accurate quality measure of splitting by incorporating abundant unlabeled data. [sent-9, score-1.016]
4 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. [sent-10, score-0.286]
5 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. [sent-11, score-1.333]
6 Because labeling training samples is very time consuming, only a small size of labeled training set is given in some tasks, which usually leads to an obvious performance drop. [sent-17, score-0.354]
7 Thus, sometimes the insufficiency of labeled data is a severe challenging issue in the construction of RF. [sent-18, score-0.271]
8 A popular solution to overcome this problem is to introduce abundant unlabeled data to guide the learning, which is known as semi-supervised learning (SSL). [sent-19, score-0.523]
9 The only existing representative attempt is the Deterministic Annealing based Semi-Supervised Random Forests (DAS-RF) [14], which treated the unlabeled data as additional variables for margin maximization between different classes. [sent-21, score-0.374]
10 Hence, it is desirable to find a method that allows RF to utilize the unlabeled data without losing its flexibility. [sent-25, score-0.307]
11 In this paper, by analyzing the construction of an RF using a small size of labeled training dataset, we find that the performance bottleneck is located in the node splitting. [sent-26, score-0.363]
12 From this insight, we tackle the aforementioned problem by introducing abundant unlabeled data to guide the splitting. [sent-27, score-0.498]
13 Based on kernel density estimation and the law of total probability, we derive a nonparametric algorithm to utilize abundant unlabeled data to obtain an accurate quality measure for node splitting. [sent-28, score-0.859]
14 In particular, to avoid the curse of dimensionality, the data points are projected from the original high-dimensional feature space onto a low-dimensional subspace before estimating the categorical distributions. [sent-29, score-0.344]
15 Finally, a unified optimization framework is proposed to select a coupled pair of subspace and separating hyperplane for each node such that the smoothness of the subspace and the quality of the splitting are guaranteed simultaneously. [sent-30, score-1.445]
16 Our contribution is three-fold: ∙ We experimentally show that node splitting quality is tWhee performance blyot sthleonwec tkh faotr n constructing R quFa wlitityh a small size labeled training set. [sent-31, score-0.878]
17 ∙ We show that partitioning an arbitrary feature space 444999002 ∙ with a hyperplane can be treated as projecting the data points from the original high-dimensional space onto the one-dimensional subspace that is perpendicular to the separating hyperplane. [sent-32, score-0.685]
18 Thus a unified optimization framework is presented to choose a coupled pair of subspace and hyperplane such that the subspace is smooth and the hyperplane can effectively partition the feature space. [sent-33, score-1.039]
19 We present an efficient nonparametric estimationbWaesed p semi-supervised splitting mareatmhoedtr itoc c oesntsitmrauctito Rn-F. [sent-34, score-0.517]
20 Related Work Node splitting is the key issue of tree-based classifiers. [sent-36, score-0.481]
21 [22] suggested a histogram-based splitting criterion for decision design. [sent-43, score-0.621]
22 Rounds [19] proposed Komogorov-Smirnov (K-S) distance and test as the splitting criterion. [sent-47, score-0.481]
23 [21] proposed an entropy-based splitting criterion for decision tree construction. [sent-53, score-0.704]
24 However, since the feature points are usually in high-dimensional space, one may have to face the curse of dimensionality to directly use the unlabeled data for estimation and thus there is insufficient number of observations to obtain a good estimation. [sent-58, score-0.446]
25 A classification margin for both unlabeled and labeled data is defined and maximized through global optimization. [sent-61, score-0.567]
26 The second family assumes that the high-dimensional data roughly lie on a low-dimensional manifold such that the unlabeled data can be efficiently used to infer the structure of the manifold without being troubled by the curse of dimensionality. [sent-63, score-0.445]
27 Both of the above two families predict the labels of unlabeled data as additional optimization variables, while the proposed method follows another line, i. [sent-65, score-0.307]
28 Pre-analysis The lack of training data influences RF construction in two ways: 1) the depth of the forest is limited and 2) the best splitting may not be chosen. [sent-69, score-0.685]
29 Two RFs were constructed for comparison: the first RF was constructed conventionally only using a very small size labeled training set which may lead to bad splitting. [sent-72, score-0.361]
30 We constructed both RFs with 100 trees and used the popular entropy gain maximization criterion for splitting. [sent-74, score-0.337]
31 From the comparisons above, it is obvious that the splitting quality is the performance bottleneck ofRF construction when the size of the training set is small. [sent-77, score-0.682]
32 For this reason, it is necessary to focus our effort on the node splitting strategies for RF construction. [sent-78, score-0.593]
33 i sI tt hise eprsotimbabatieldit by calculating tchlaes sr a 푘tio g itvheant class gets votes from the leaves in the 푖푡ℎ tree 푘 푝푖(푘∣푥) =∑푗퐾푙=푖,푘1푙푖,푗, (2) where 푙푖,푘 is the number of le∑aves in the 푖푡ℎ tree that vote for class The overall decision function of RF is defined as 푘. [sent-95, score-0.263]
34 An oblique linear split is expressed as a function of the hyperplane 푊 푥 = 휃, (4) where 푊 ∈ ℛ푀 and 휃 ∈ ℛ are the parameters. [sent-100, score-0.398]
35 Given the data falling into a node and a candidate hyperplane, a quality measure needs to be defined such that one can search for the best hyperplane to maximize the splitting quality. [sent-103, score-1.016]
36 There are four common criteria to evaluate the splitting quality, i. [sent-104, score-0.543]
37 , information gain [17], normalized information gain [18], Gini index [5], and Bayesian classification error [9]. [sent-106, score-0.282]
38 (5) Since both 푝(푥) and 푝(푘∣푥) are unknown, finite labeled samples are hus 푝ed(푥 to) amndake 푝 t푘he∣푥 e)st airmea utnioknn 푝푘=∑∣푖푅=1∣1푤푅푖푖∑∣=푅1∣푝(푘∣푥푅푖)푤푅푖, (6) where 푤푅푖 is the ∑푖푡ℎ sample falling into a node 푅 and 푤푅푖 is its weight. [sent-109, score-0.352]
39 (7) The problem with the fully supervised splitting is that, although the distribution 푝(푘∣푥푅푖 ) is given by the labeled sample, hth teh sparse blaubtieolend 푝 d(a푘∣ta푥 cannot give a good approximation of the marginal distribution which may lead to a worse choice of the separating hyperplane. [sent-111, score-0.836]
40 If only given few labeled samples, for example, one would choose to partition the two-dimensional space with the hyperplane shown in Figure 2(a). [sent-112, score-0.525]
41 In contrast, given more data, a better splitting can be found, as shown in Figure 2(b). [sent-114, score-0.481]
42 The red triangles and the blue circles are labeled samples of two classes while the black squares are unlabeled data. [sent-116, score-0.495]
43 If only given a small number of labeled data, one may partition the feature space with the hyperplane shown in (a). [sent-117, score-0.525]
44 When given more labeled data, one could find a better splitting strategy as in (b). [sent-118, score-0.627]
45 Even the abundant data are unlabeled one can still choose the appropriate separating hyperplane as in (c) by combining the law of total probability and the kernel-based density estimation. [sent-119, score-1.096]
46 We carry out the kernel-based density estimation in a one-dimensional subspace of the original feature space. [sent-121, score-0.264]
47 Unfortunately, the insufficiency of labeled training data usually leads to a sparse distribution and a bad approximation like Figure 2(a). [sent-123, score-0.34]
48 Our solution to overcome the this 444999224 limitation is to introduce abundant unlabeled samples to estimate 푝푘. [sent-124, score-0.567]
49 A new problem to arise is that the pos- teriori distribution ˆ푝(푘∣푥푅푖 ) of unlabeled data is unknown. [sent-127, score-0.338]
50 (9) For 푝(푥푅푖 ∣푘), we apply ∑a kernel-based density estimation with Gau∣s푘s)ia,n w keer anpepll [y20 a] 퐾ℎ(푢) = ℎ−푑(2휋)−푑/2exp{−2ℎ12푢푇푢}, (10) where ℎ is the bandwidth to be determined and 푑 is the data dimension. [sent-129, score-0.24]
51 We then have the following estimation for an unlabeled sample 푝(푥푅푖∣푘) =푛1푘푦∑푗=푘퐾ℎ(푥푅푖− 푥푗), where 푛푘 (11) is the number of samples that are labeled 푘. [sent-130, score-0.529]
52 Since the true density 푝(푥∣푘) is unknown, we adopt the commonly e u tsreude rud elen-soitf-yth 푝u(m푥b∣푘 [)2 i0s] uton replace the unknown true density by a reference density 푞(푥), e. [sent-136, score-0.276]
53 (14) Figure 2(c) shows a case where, by combining the law of total probability and the kernel-based density estimation, the appropriate separating hyperplane with abundant unla- beled data can be chosen. [sent-143, score-0.848]
54 Since the feature points are usually in very highdimensional space, directly estimating the densities is still not a good idea, not only because of the intractable time complexity but also because there are insufficient labeled samples to make a good estimation in the high-dimensional space. [sent-144, score-0.274]
55 Note that another way of looking at the hyperplane partition is that the original data are projected onto the one-dimensional subspace that is perpendicular to the separating hyperplane. [sent-146, score-0.746]
56 In particular, by using a hyperplane 푊 ⋅ 푥 = 휃 to partition the feature space, nthge a algorithm nmea 푊kes ⋅ a projection wartiithti othne t projection function 푧 =푊 ⋅ 푥. [sent-147, score-0.379]
57 Thus, the labels of both labeled and unlabeled data distribute smoothly along the subspace. [sent-149, score-0.453]
58 (17) We want to search for a coupled pair of subspace and separating hyperplane such that the smoothness of the subspace and the quality of the splitting are guaranteed simultaneously. [sent-152, score-1.305]
59 An alternative optimization strategy is adopted to couple the two procedures by iterating the following two updating steps: ∙ Project the data onto the given subspace and estimate tPhreo categorical adi osnttroib uthtieon g. [sent-153, score-0.299]
60 i 444999335 ∙ Search for a separating hyperplane according to the quality measure. [sent-154, score-0.485]
61 Output: The parameters of the chosen hyperplane 푊푅 and 휃푅. [sent-160, score-0.318]
62 2: Search for a hyperplane with parameters 푊0 and 휃0 that maximize the quality measure considering only labeled data. [sent-162, score-0.517]
63 6: Project all the samples onto the subspace that is perpendicular to the separating hyperplane: 푧 = 푊푡 ⋅ 푥. [sent-165, score-0.409]
64 7: for each labeled samples 푥푖 ∈ 푋푙 do 8: Use the given label as posterior distribution 푝(푘∣푧푖) = [푦푖 = 푘]. [sent-166, score-0.244]
65 9: en푝d( f푘o∣r푧 10: for each unlabeled samples 푥푖 ∈ 푋푢 do 11: Calculate 푝(푘∣푧푖) with the ke∈rn 푋el-based density esCtimalacutiloant. [sent-167, score-0.441]
66 14: Choose the hyperplane parameters 푊푡 and 휃푡 that maximize the quality measure. [sent-169, score-0.371]
67 15: until the chosen separating hyperplane is stable or the algorithm reaches enough iterations. [sent-170, score-0.432]
68 Random Forest Construction Based on Semi-supervised Splitting In the RF construction stage, an individual training set for each tree is generated from the original training set using bootstrap aggregation. [sent-174, score-0.295]
69 The samples which are not chosen for training are called Out-Of-Bag (OOB) samples of the tree and can be used for calculating the Out-Of-BagError (OOBE), which is an unbiased estimation of the generalization error. [sent-175, score-0.325]
70 To overcome the limitation of ‘airbag’ algorithm, we propose to independently compare the OOBE of single decision trees in the supervised and semi-supervised models. [sent-181, score-0.246]
71 In each model, we use a set of labeled bootstrap data to construct the supervised decision tree and use the same set oflabeled data and a set of unlabeled bootstrap data to construct the semi-supervised tree. [sent-182, score-0.832]
72 2: for the 푖푡ℎ decision tree in 퐹 do 3: Generate a new labeled set 푋푙푖 and a new unlabeled set 푋푢푖 using the bootstrap aggregation. [sent-189, score-0.666]
73 Experiment and Analysis We compared the proposed semi-supervised splitting with different splitting criteria on typical machine learning tasks. [sent-199, score-1.024]
74 We show that by introducing abundant unlabeled data, obvious accuracy improvement can be achieved. [sent-200, score-0.489]
75 We also applied the proposed semi-supervised splitting RF for object categorization and image segmentation. [sent-201, score-0.531]
76 Data Classification To quantitatively evaluate the improvement over the traditional splitting criteria, we test our method on the Satimage and Pendigits datasets. [sent-205, score-0.516]
77 The Satimage dataset has 4435 training samples and 2000 testing samples while the Pendigits dataset has 7494 training samples and 3498 testing samples. [sent-206, score-0.299]
78 We implement Breiman’s Random Forests [4] with the four different splitting criteria, i. [sent-207, score-0.481]
79 The proposed semi-supervised splitting was applied to the four criteria. [sent-211, score-0.481]
80 For each dataset, we randomly chose a part of the training data as the labeled data and left the remainder as unlabeled data. [sent-212, score-0.527]
81 0 while the weights of the unlabeled samples were set through cross-validation. [sent-217, score-0.349]
82 We built the RF with 100 trees and 10 hyperplanes were randomly generated as candidates in the internal node of RF. [sent-218, score-0.268]
83 The classification accuracy of Random Forests with traditional splitting criteria (dashed lines) and the proposed semisupervised splitting (solid lines). [sent-230, score-1.088]
84 We also compared the proposed semi-supervised splitting RF with the state-of-the-art semi-supervised and supervised classifiers: RF [4], TSVM [13], SVM [6] and DASRF [14]. [sent-232, score-0.514]
85 s Feo 1llo5 images per category as mtheen lta sbeetulepd, training data and 15 images as the unlabeled training data. [sent-254, score-0.405]
86 Normalized information gain is used as the splitting criterion to construct the RF. [sent-264, score-0.635]
87 5 percent over the SVM, by introducing abundant unlabeled data. [sent-271, score-0.474]
88 Image Segmentation We applied the proposed semi-supervised splitting RF for the task of image segmentation in the 9-class MSRC 444999557 dataset. [sent-274, score-0.481]
89 We randomly chose 150 images as the labeled training data and 150 images as the unlabeled training data from a total of 480 images, leaving the remainder as the testing data. [sent-276, score-0.576]
90 During splitting, 10 hyperplanes were randomly generated as candidates and the hyperplane that maximized the information gain was chosen. [sent-281, score-0.531]
91 0 and set the weight of an unlabeled superpixel at 0. [sent-283, score-0.318]
92 We show the segmentation results of the proposed semi-supervised splitting RF in Figure 5. [sent-289, score-0.481]
93 Conclusion and Future Work In this paper, we introduced a semi-supervised splitting method that uses abundant unlabeled data to guide the node splitting of random forests. [sent-296, score-1.572]
94 We derived a nonparametric algorithm to estimate the categorical distributions of the internal nodes such that an accurate quality measure of splitting can be obtained. [sent-297, score-0.677]
95 Our method can be combined with many popular splitting criteria, and the experimental results show that it brings obvious performance improvements to all of them. [sent-298, score-0.524]
96 A unified splitting framework that can handle both labeled and unlabeled data would be the extension. [sent-300, score-0.962]
97 Information Gain: The information gain is defined as the subtraction of entropies before and after splitting △퐻(푅,푊,휃) = 퐻(푅)−∣∣푅푅푙∣∣퐻(푅푙)−∣∣푅푅푟∣∣퐻(푅푟), (18) where 푅 is an internal node, 푅푙 and 푅푟 are its left and right child respectively. [sent-305, score-0.641]
98 Normalized Information Gain: The normalized entropy gain is defined as the quotient of the information gain and a normalized factor △푁(푅,푊,휃) =−(∣푅∣푅푙∣∣lo△g퐻∣∣푅푅(푙∣푅∣+,푊∣∣푅푅,푟휃∣∣)log∣∣푅푅푟∣∣). [sent-307, score-0.26]
99 Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. [sent-334, score-0.428]
100 A probability analysis on the value of unlabeled data for classification problems. [sent-500, score-0.376]
wordName wordTfidf (topN-words)
[('splitting', 0.481), ('rf', 0.335), ('hyperplane', 0.318), ('unlabeled', 0.282), ('oobe', 0.198), ('abundant', 0.164), ('pendigits', 0.149), ('satimage', 0.149), ('labeled', 0.146), ('subspace', 0.138), ('separating', 0.114), ('node', 0.112), ('gain', 0.111), ('gini', 0.105), ('decision', 0.097), ('density', 0.092), ('ssl', 0.092), ('bandwidth', 0.089), ('tree', 0.083), ('curse', 0.078), ('rfs', 0.077), ('airbag', 0.074), ('breiman', 0.074), ('forest', 0.074), ('samples', 0.067), ('criteria', 0.062), ('trees', 0.062), ('law', 0.061), ('partition', 0.061), ('bootstrap', 0.058), ('categorical', 0.058), ('maximized', 0.057), ('construction', 0.056), ('quality', 0.053), ('amise', 0.05), ('hyafil', 0.05), ('suen', 0.05), ('categorization', 0.05), ('training', 0.049), ('internal', 0.049), ('perpendicular', 0.045), ('hyperplanes', 0.045), ('onto', 0.045), ('bad', 0.045), ('constructed', 0.044), ('qualifying', 0.044), ('insufficiency', 0.044), ('payne', 0.044), ('tsvm', 0.044), ('obvious', 0.043), ('criterion', 0.043), ('oblique', 0.041), ('impurity', 0.041), ('probability', 0.04), ('split', 0.039), ('maximization', 0.039), ('truths', 0.038), ('entropy', 0.038), ('coupled', 0.038), ('bayesian', 0.037), ('constructing', 0.037), ('nonparametric', 0.036), ('superpixel', 0.036), ('traditional', 0.035), ('family', 0.035), ('beled', 0.034), ('estimation', 0.034), ('procedures', 0.033), ('conventionally', 0.033), ('supervised', 0.033), ('annealing', 0.032), ('posteriors', 0.032), ('distribution', 0.031), ('forests', 0.031), ('index', 0.031), ('msrc', 0.03), ('classification', 0.029), ('song', 0.029), ('limitation', 0.029), ('slic', 0.028), ('transductive', 0.028), ('unified', 0.028), ('margin', 0.028), ('percent', 0.028), ('crf', 0.028), ('insufficient', 0.027), ('falling', 0.027), ('bu', 0.027), ('guide', 0.027), ('deterministic', 0.026), ('iws', 0.026), ('leistner', 0.026), ('unbiased', 0.025), ('heavily', 0.025), ('smoothness', 0.025), ('appendix', 0.025), ('overcome', 0.025), ('data', 0.025), ('microsoft', 0.025), ('tao', 0.024)]
simIndex simValue paperId paperTitle
same-paper 1 1.0000006 390 cvpr-2013-Semi-supervised Node Splitting for Random Forest Construction
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.
2 0.2232164 36 cvpr-2013-Adding Unlabeled Samples to Categories by Learned Attributes
Author: Jonghyun Choi, Mohammad Rastegari, Ali Farhadi, Larry S. Davis
Abstract: We propose a method to expand the visual coverage of training sets that consist of a small number of labeled examples using learned attributes. Our optimization formulation discovers category specific attributes as well as the images that have high confidence in terms of the attributes. In addition, we propose a method to stably capture example-specific attributes for a small sized training set. Our method adds images to a category from a large unlabeled image pool, and leads to significant improvement in category recognition accuracy evaluated on a large-scale dataset, ImageNet.
3 0.18430254 34 cvpr-2013-Adaptive Active Learning for Image Classification
Author: Xin Li, Yuhong Guo
Abstract: Recently active learning has attracted a lot of attention in computer vision field, as it is time and cost consuming to prepare a good set of labeled images for vision data analysis. Most existing active learning approaches employed in computer vision adopt most uncertainty measures as instance selection criteria. Although most uncertainty query selection strategies are very effective in many circumstances, they fail to take information in the large amount of unlabeled instances into account and are prone to querying outliers. In this paper, we present a novel adaptive active learning approach that combines an information density measure and a most uncertainty measure together to select critical instances to label for image classifications. Our experiments on two essential tasks of computer vision, object recognition and scene recognition, demonstrate the efficacy of the proposed approach.
4 0.16655618 387 cvpr-2013-Semi-supervised Domain Adaptation with Instance Constraints
Author: Jeff Donahue, Judy Hoffman, Erik Rodner, Kate Saenko, Trevor Darrell
Abstract: Most successful object classification and detection methods rely on classifiers trained on large labeled datasets. However, for domains where labels are limited, simply borrowing labeled data from existing datasets can hurt performance, a phenomenon known as “dataset bias.” We propose a general framework for adapting classifiers from “borrowed” data to the target domain using a combination of available labeled and unlabeled examples. Specifically, we show that imposing smoothness constraints on the classifier scores over the unlabeled data can lead to improved adaptation results. Such constraints are often available in the form of instance correspondences, e.g. when the same object or individual is observed simultaneously from multiple views, or tracked between video frames. In these cases, the object labels are unknown but can be constrained to be the same or similar. We propose techniques that build on existing domain adaptation methods by explicitly modeling these relationships, and demonstrate empirically that they improve recognition accuracy in two scenarios, multicategory image classification and object detection in video.
5 0.1621009 39 cvpr-2013-Alternating Decision Forests
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.
6 0.14558104 340 cvpr-2013-Probabilistic Label Trees for Efficient Large Scale Image Classification
7 0.098220505 459 cvpr-2013-Watching Unlabeled Video Helps Learn New Human Actions from Very Few Labeled Snapshots
8 0.097953975 193 cvpr-2013-Graph Transduction Learning with Connectivity Constraints with Application to Multiple Foreground Cosegmentation
9 0.096138276 442 cvpr-2013-Transfer Sparse Coding for Robust Image Representation
10 0.093453452 380 cvpr-2013-Scene Coordinate Regression Forests for Camera Relocalization in RGB-D Images
11 0.093265839 186 cvpr-2013-GeoF: Geodesic Forests for Learning Coupled Predictors
12 0.09056481 405 cvpr-2013-Sparse Subspace Denoising for Image Manifolds
13 0.089865282 268 cvpr-2013-Leveraging Structure from Motion to Learn Discriminative Codebooks for Scalable Landmark Classification
14 0.085508816 180 cvpr-2013-Fully-Connected CRFs with Non-Parametric Pairwise Potential
15 0.085113853 140 cvpr-2013-Efficient Color Boundary Detection with Color-Opponent Mechanisms
16 0.084055461 389 cvpr-2013-Semi-supervised Learning with Constraints for Person Identification in Multimedia Data
17 0.082672775 135 cvpr-2013-Discriminative Subspace Clustering
18 0.080788888 98 cvpr-2013-Cross-View Action Recognition via a Continuous Virtual Path
19 0.077930316 167 cvpr-2013-Fast Multiple-Part Based Object Detection Using KD-Ferns
20 0.073572107 249 cvpr-2013-Learning Compact Binary Codes for Visual Tracking
topicId topicWeight
[(0, 0.173), (1, -0.041), (2, -0.035), (3, 0.013), (4, 0.082), (5, 0.026), (6, -0.037), (7, -0.009), (8, -0.027), (9, -0.006), (10, 0.034), (11, -0.001), (12, -0.059), (13, -0.022), (14, -0.113), (15, -0.009), (16, -0.098), (17, -0.143), (18, -0.031), (19, -0.043), (20, -0.027), (21, -0.054), (22, -0.102), (23, -0.016), (24, 0.025), (25, 0.083), (26, 0.029), (27, -0.009), (28, 0.0), (29, 0.031), (30, -0.202), (31, 0.13), (32, -0.062), (33, 0.027), (34, 0.052), (35, 0.047), (36, -0.077), (37, -0.149), (38, 0.054), (39, -0.088), (40, -0.11), (41, 0.083), (42, -0.007), (43, 0.077), (44, 0.091), (45, 0.072), (46, -0.11), (47, -0.053), (48, -0.043), (49, 0.036)]
simIndex simValue paperId paperTitle
same-paper 1 0.95881826 390 cvpr-2013-Semi-supervised Node Splitting for Random Forest Construction
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.
2 0.75106084 34 cvpr-2013-Adaptive Active Learning for Image Classification
Author: Xin Li, Yuhong Guo
Abstract: Recently active learning has attracted a lot of attention in computer vision field, as it is time and cost consuming to prepare a good set of labeled images for vision data analysis. Most existing active learning approaches employed in computer vision adopt most uncertainty measures as instance selection criteria. Although most uncertainty query selection strategies are very effective in many circumstances, they fail to take information in the large amount of unlabeled instances into account and are prone to querying outliers. In this paper, we present a novel adaptive active learning approach that combines an information density measure and a most uncertainty measure together to select critical instances to label for image classifications. Our experiments on two essential tasks of computer vision, object recognition and scene recognition, demonstrate the efficacy of the proposed approach.
3 0.71827644 39 cvpr-2013-Alternating Decision Forests
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.
4 0.71283245 340 cvpr-2013-Probabilistic Label Trees for Efficient Large Scale Image Classification
Author: Baoyuan Liu, Fereshteh Sadeghi, Marshall Tappen, Ohad Shamir, Ce Liu
Abstract: Large-scale recognition problems with thousands of classes pose a particular challenge because applying the classifier requires more computation as the number of classes grows. The label tree model integrates classification with the traversal of the tree so that complexity grows logarithmically. In this paper, we show how the parameters of the label tree can be found using maximum likelihood estimation. This new probabilistic learning technique produces a label tree with significantly improved recognition accuracy.
5 0.62151784 261 cvpr-2013-Learning by Associating Ambiguously Labeled Images
Author: Zinan Zeng, Shijie Xiao, Kui Jia, Tsung-Han Chan, Shenghua Gao, Dong Xu, Yi Ma
Abstract: We study in this paper the problem of learning classifiers from ambiguously labeled images. For instance, in the collection of new images, each image contains some samples of interest (e.g., human faces), and its associated caption has labels with the true ones included, while the samplelabel association is unknown. The task is to learn classifiers from these ambiguously labeled images and generalize to new images. An essential consideration here is how to make use of the information embedded in the relations between samples and labels, both within each image and across the image set. To this end, we propose a novel framework to address this problem. Our framework is motivated by the observation that samples from the same class repetitively appear in the collection of ambiguously labeled training images, while they are just ambiguously labeled in each image. If we can identify samples of the same class from each image and associate them across the image set, the matrix formed by the samples from the same class would be ideally low-rank. By leveraging such a low-rank assump- tion, we can simultaneously optimize a partial permutation matrix (PPM) for each image, which is formulated in order to exploit all information between samples and labels in a principled way. The obtained PPMs can be readily used to assign labels to samples in training images, and then a standard SVM classifier can be trained and used for unseen data. Experiments on benchmark datasets show the effectiveness of our proposed method.
6 0.60336721 36 cvpr-2013-Adding Unlabeled Samples to Categories by Learned Attributes
7 0.59586412 442 cvpr-2013-Transfer Sparse Coding for Robust Image Representation
8 0.58064443 320 cvpr-2013-Optimizing 1-Nearest Prototype Classifiers
9 0.5560438 168 cvpr-2013-Fast Object Detection with Entropy-Driven Evaluation
10 0.55253595 193 cvpr-2013-Graph Transduction Learning with Connectivity Constraints with Application to Multiple Foreground Cosegmentation
11 0.55051666 239 cvpr-2013-Kernel Null Space Methods for Novelty Detection
12 0.53900868 403 cvpr-2013-Sparse Output Coding for Large-Scale Visual Recognition
13 0.52554315 186 cvpr-2013-GeoF: Geodesic Forests for Learning Coupled Predictors
14 0.51861531 389 cvpr-2013-Semi-supervised Learning with Constraints for Person Identification in Multimedia Data
15 0.51539916 15 cvpr-2013-A Lazy Man's Approach to Benchmarking: Semisupervised Classifier Evaluation and Recalibration
17 0.48047286 179 cvpr-2013-From N to N+1: Multiclass Transfer Incremental Learning
18 0.46306705 134 cvpr-2013-Discriminative Sub-categorization
19 0.46266586 268 cvpr-2013-Leveraging Structure from Motion to Learn Discriminative Codebooks for Scalable Landmark Classification
20 0.45370042 417 cvpr-2013-Subcategory-Aware Object Classification
topicId topicWeight
[(10, 0.143), (16, 0.014), (18, 0.16), (26, 0.045), (33, 0.311), (67, 0.068), (69, 0.051), (87, 0.123)]
simIndex simValue paperId paperTitle
1 0.95056933 369 cvpr-2013-Rotation, Scaling and Deformation Invariant Scattering for Texture Discrimination
Author: Laurent Sifre, Stéphane Mallat
Abstract: An affine invariant representation is constructed with a cascade of invariants, which preserves information for classification. A joint translation and rotation invariant representation of image patches is calculated with a scattering transform. It is implemented with a deep convolution network, which computes successive wavelet transforms and modulus non-linearities. Invariants to scaling, shearing and small deformations are calculated with linear operators in the scattering domain. State-of-the-art classification results are obtained over texture databases with uncontrolled viewing conditions.
2 0.94233412 452 cvpr-2013-Vantage Feature Frames for Fine-Grained Categorization
Author: Asma Rejeb Sfar, Nozha Boujemaa, Donald Geman
Abstract: We study fine-grained categorization, the task of distinguishing among (sub)categories of the same generic object class (e.g., birds), focusing on determining botanical species (leaves and orchids) from scanned images. The strategy is to focus attention around several vantage points, which is the approach taken by botanists, but using features dedicated to the individual categories. Our implementation of the strategy is based on vantage feature frames, a novel object representation consisting of two components: a set of coordinate systems centered at the most discriminating local viewpoints for the generic object class and a set of category-dependentfeatures computed in these frames. The features are pooled over frames to build the classifier. Categorization then proceeds from coarse-grained (finding the frames) to fine-grained (finding the category), and hence the vantage feature frames must be both detectable and discriminating. The proposed method outperforms state-of-the art algorithms, in particular those using more distributed representations, on standard databases of leaves.
3 0.91423291 365 cvpr-2013-Robust Real-Time Tracking of Multiple Objects by Volumetric Mass Densities
Author: Horst Possegger, Sabine Sternig, Thomas Mauthner, Peter M. Roth, Horst Bischof
Abstract: Combining foreground images from multiple views by projecting them onto a common ground-plane has been recently applied within many multi-object tracking approaches. These planar projections introduce severe artifacts and constrain most approaches to objects moving on a common 2D ground-plane. To overcome these limitations, we introduce the concept of an occupancy volume exploiting the full geometry and the objects ’ center of mass and develop an efficient algorithm for 3D object tracking. Individual objects are tracked using the local mass density scores within a particle filter based approach, constrained by a Voronoi partitioning between nearby trackers. Our method benefits from the geometric knowledge given by the occupancy volume to robustly extract features and train classifiers on-demand, when volumetric information becomes unreliable. We evaluate our approach on several challenging real-world scenarios including the public APIDIS dataset. Experimental evaluations demonstrate significant improvements compared to state-of-theart methods, while achieving real-time performance. – –
same-paper 4 0.91234398 390 cvpr-2013-Semi-supervised Node Splitting for Random Forest Construction
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.
5 0.91198051 248 cvpr-2013-Learning Collections of Part Models for Object Recognition
Author: Ian Endres, Kevin J. Shih, Johnston Jiaa, Derek Hoiem
Abstract: We propose a method to learn a diverse collection of discriminative parts from object bounding box annotations. Part detectors can be trained and applied individually, which simplifies learning and extension to new features or categories. We apply the parts to object category detection, pooling part detections within bottom-up proposed regions and using a boosted classifier with proposed sigmoid weak learners for scoring. On PASCAL VOC 2010, we evaluate the part detectors ’ ability to discriminate and localize annotated keypoints. Our detection system is competitive with the best-existing systems, outperforming other HOG-based detectors on the more deformable categories.
6 0.91145122 305 cvpr-2013-Non-parametric Filtering for Geometric Detail Extraction and Material Representation
7 0.90858775 98 cvpr-2013-Cross-View Action Recognition via a Continuous Virtual Path
8 0.90803379 242 cvpr-2013-Label Propagation from ImageNet to 3D Point Clouds
9 0.90686285 71 cvpr-2013-Boundary Cues for 3D Object Shape Recovery
10 0.90432912 143 cvpr-2013-Efficient Large-Scale Structured Learning
11 0.90422779 408 cvpr-2013-Spatiotemporal Deformable Part Models for Action Detection
12 0.90384358 147 cvpr-2013-Ensemble Learning for Confidence Measures in Stereo Vision
13 0.90362978 227 cvpr-2013-Intrinsic Scene Properties from a Single RGB-D Image
15 0.90347463 14 cvpr-2013-A Joint Model for 2D and 3D Pose Estimation from a Single Image
16 0.90330923 225 cvpr-2013-Integrating Grammar and Segmentation for Human Pose Estimation
17 0.90284538 222 cvpr-2013-Incorporating User Interaction and Topological Constraints within Contour Completion via Discrete Calculus
18 0.90282255 446 cvpr-2013-Understanding Indoor Scenes Using 3D Geometric Phrases
19 0.90259051 256 cvpr-2013-Learning Structured Hough Voting for Joint Object Detection and Occlusion Reasoning
20 0.90239894 298 cvpr-2013-Multi-scale Curve Detection on Surfaces