nips nips2013 nips2013-82 knowledge-graph by maker-knowledge-mining

82 nips-2013-Decision Jungles: Compact and Rich Models for Classification

Source: pdf

Author: Jamie Shotton, Toby Sharp, Pushmeet Kohli, Sebastian Nowozin, John Winn, Antonio Criminisi

Abstract: Randomized decision trees and forests have a rich history in machine learning and have seen considerable success in application, perhaps particularly so for computer vision. However, they face a fundamental limitation: given enough data, the number of nodes in decision trees will grow exponentially with depth. For certain applications, for example on mobile or embedded processors, memory is a limited resource, and so the exponential growth of trees limits their depth, and thus their potential accuracy. This paper proposes decision jungles, revisiting the idea of ensembles of rooted decision directed acyclic graphs (DAGs), and shows these to be compact and powerful discriminative models for classiﬁcation. Unlike conventional decision trees that only allow one path to every node, a DAG in a decision jungle allows multiple paths from the root to each leaf. We present and compare two new node merging algorithms that jointly optimize both the features and the structure of the DAGs efﬁciently. During training, node splitting and node merging are driven by the minimization of exactly the same objective function, here the weighted sum of entropies at the leaves. Results on varied datasets show that, compared to decision forests and several other baselines, decision jungles require dramatically less memory while considerably improving generalization. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 However, they face a fundamental limitation: given enough data, the number of nodes in decision trees will grow exponentially with depth. [sent-2, score-0.719]

2 For certain applications, for example on mobile or embedded processors, memory is a limited resource, and so the exponential growth of trees limits their depth, and thus their potential accuracy. [sent-3, score-0.4]

3 This paper proposes decision jungles, revisiting the idea of ensembles of rooted decision directed acyclic graphs (DAGs), and shows these to be compact and powerful discriminative models for classiﬁcation. [sent-4, score-0.614]

4 Unlike conventional decision trees that only allow one path to every node, a DAG in a decision jungle allows multiple paths from the root to each leaf. [sent-5, score-0.909]

5 During training, node splitting and node merging are driven by the minimization of exactly the same objective function, here the weighted sum of entropies at the leaves. [sent-7, score-0.355]

6 Results on varied datasets show that, compared to decision forests and several other baselines, decision jungles require dramatically less memory while considerably improving generalization. [sent-8, score-1.079]

7 1 Introduction Decision trees have a long history in machine learning and were one of the ﬁrst models proposed for inductive learning [14]. [sent-9, score-0.322]

8 Although trees allow making predictions efﬁciently, learning the optimal decision tree is an NP-hard problem [15]. [sent-13, score-0.63]

9 In his seminal work, Quinlan proposed efﬁcient approximate methods for learning decision trees [27, 28]. [sent-14, score-0.543]

10 Some researchers have argued that learning optimal decision trees could be harmful as it may lead to overﬁtting [21]. [sent-15, score-0.543]

11 A prior over the space of trees and their parameters induces a posterior distribution, which can be used, for example, to marginalize over all tree models. [sent-22, score-0.409]

12 There are similarities between the idea of randomly drawing multiple trees via a Bayesian procedure and construction of random tree ensembles (forests) using bagging, a method shown to be effective in many applications [1, 5, 9]. [sent-23, score-0.475]

13 1 While the above-mentioned methods can reduce overﬁtting, decision trees face a fundamental limitation: their exponential growth with depth. [sent-25, score-0.581]

14 For large datasets where deep trees have been shown to be more accurate than large ensembles (e. [sent-26, score-0.388]

15 In this paper, we investigate the use of randomized ensembles of rooted decision directed acyclic graphs (DAGs) as a means to obtain compact and yet accurate classiﬁers. [sent-29, score-0.413]

16 Building on the information gain measure commonly used for training decision trees, we propose an objective that is deﬁned jointly over the features of the split nodes and the structure of the DAG. [sent-32, score-0.59]

17 Both methods alternate between optimizing the split functions at the nodes of the DAG and optimizing the placement of the branches emanating from the parent nodes. [sent-34, score-0.413]

18 We evaluate jungles on a number of challenging labelling problems. [sent-36, score-0.391]

19 Our experiments below quantify a substantially reduced memory footprint for decision jungles compared to standard decision forests and several baselines. [sent-37, score-1.164]

20 The use of rooted decision DAGs (‘DAGs’ for short) has been explored by a number of papers in the literature. [sent-40, score-0.307]

21 It has also been shown that DAGs lead to accurate predictions while having lower model complexity, subtree replication, and training data fragmentation compared to decision trees. [sent-43, score-0.262]

22 Oliveira [23] used local search method for constructing DAGs in which tree nodes are removed or merged together based on similarity of the underlying sub-graphs and the corresponding message length reduction. [sent-48, score-0.44]

23 Chou [8] investigated a k-means clustering for learning decision trees and DAGs (similar ‘ClusterSearch’ below), though did not jointly optimize the features with the DAG structure. [sent-50, score-0.589]

24 In this paper we show how jungles, ensembles of DAGs, optimized so as to reduce a well deﬁned objective function, can produce results which are superior to those of analogous decision tree ensembles, both in terms of model compactness as well as generalization. [sent-53, score-0.413]

25 2 Forests and Jungles Before delving into the details of our method for learning decision jungles, we ﬁrst brieﬂy discuss how decision trees and forests are used for classiﬁcation problems and how they relate to jungles. [sent-58, score-0.952]

26 A binary decision tree is composed of a set of nodes each with an in-degree of 1, except the root node. [sent-60, score-0.51]

27 The out-degree for every internal (split) node of the tree is 2 and for the leaf nodes is 0. [sent-61, score-0.388]

28 Each split node contains a binary split function (‘feature’) which decides whether an 2 grass csg cow 0 csg csg grass 1 2 sheep csg (a) … csg 3 csg 4 csg 5 (b) Training patches Figure 1: Motivation and notation. [sent-62, score-1.204]

29 (a) An example use of a rooted decision DAG for classifying image patches as belonging to grass, cow or sheep classes. [sent-63, score-0.44]

30 Using DAGs instead of trees reduces the number of nodes and can result in better generalization. [sent-64, score-0.48]

31 For example, differently coloured patches of grass (yellow and green) are merged together into node 4, because of similar class statistics. [sent-65, score-0.41]

32 Prediction in binary decision trees involves every input starting at the root and moving down as dictated by the split functions encountered at the split nodes. [sent-70, score-0.757]

33 Rooted binary DAGs have a different architecture compared to decision trees and were introduced by Platt et al. [sent-74, score-0.565]

34 More speciﬁcally a rooted binary DAG has: (i) one root node, with in-degree 0; (ii) multiple split nodes, with in-degree ≥ 1 and out-degree 2; (iii) multiple leaf nodes, with in-degree ≥ 1 and out-degree 0. [sent-76, score-0.268]

35 In fact, the leaf nodes are not necessarily pure; And each leaf remains associated with an empirical class distribution. [sent-78, score-0.264]

36 We explain the relationship between decision trees and decision DAGs using the image classiﬁcation task illustrated in Fig. [sent-80, score-0.783]

37 Since patches corresponding to different classes may have different average intensity, the root node may decide to split them according to this feature. [sent-84, score-0.27]

38 Similarly, the two child nodes may decide to split the patches further based on their chromaticity. [sent-85, score-0.346]

39 However, if we detect that two such nodes are associated with similar class distributions (peaked around grass in this case) and merge them, then we get a single node with training examples from both grass types. [sent-87, score-0.439]

40 3 Learning Decision Jungles We train each rooted decision DAG in a jungle independently, though there is scope for merging across DAGs as future work. [sent-90, score-0.525]

41 This is done by minimizing an objective function deﬁned over the predictions made by the child nodes emanating from the nodes whose split features are being learned. [sent-93, score-0.559]

42 Consider the set of nodes at two consecutive levels of the decision DAG (as shown in Fig. [sent-94, score-0.379]

43 This set consist of the set of parent nodes Np and a set of child nodes Nc . [sent-96, score-0.422]

44 Let θi denote the parameters of the split feature function f for parent node i ∈ Np , and Si denote the set of labelled training instances (x, y) that reach node i. [sent-99, score-0.415]

45 Given θi and Si , we can compute the set of instances L from node i that travel through its left and right branches as Si (θi ) = {(x, y) ∈ Si | f (θi , x) ≤ 0} 1 Jointly training all levels of the tree simultaneously remains an expensive operation [15]. [sent-100, score-0.274]

46 We use li ∈ Nc to denote the current assignment of the left outwards edge from parent node i ∈ Np to a child node, and similarly ri ∈ Nc for the right outward edge. [sent-102, score-0.28]

47 We can now formulate the problem of learning the parameters of the decision DAG as a joint minimization of the objective over the split parameters {θi } and the child assignments {li }, {ri }. [sent-109, score-0.419]

48 Note that if the number of child nodes M is equal to twice the number of parent nodes i. [sent-114, score-0.422]

49 M = 2|Np |, then the DAG becomes a tree and we can optimize the parameters of the different nodes independently, as done in standard decision tree training, to achieve optimal results. [sent-116, score-0.571]

50 We found that a greedy initialization of LSearch (allocating splits to the most energetic parent nodes ﬁrst) resulted in a lower objective after optimization than a random initialization. [sent-126, score-0.298]

51 First, 2|Np | temporary child nodes are built via conventional tree-based, training-objective minimization procedures. [sent-130, score-0.283]

52 4 Experiments and results This section compares testing accuracy and computational performance of our decision jungles with state-of-the-art forests of binary decision trees and their variants on several classiﬁcation problems. [sent-133, score-1.418]

53 1 Classiﬁcation Tasks and Datasets We focus on semantic image segmentation (pixel-wise classiﬁcation) tasks, where decision forests have proven very successful [9, 19, 29]. [sent-135, score-0.544]

54 Following [29], 3 trees or DAGs are used unless otherwise speciﬁed. [sent-138, score-0.322]

55 We train each of 3 trees or DAGs in the ensemble on a separate 1000 training images using every pixel. [sent-143, score-0.448]

56 We train on all 715 labelled images, seeding our feature generator differently for each of 3 trees or DAGs in the ensemble. [sent-146, score-0.377]

57 2 Baseline Algorithms We compare our decision jungles with several tree-based alternatives, listed below. [sent-163, score-0.612]

58 As a ﬁrst variant on forests, we train binary decision trees with an enforced maximum width M at each level, and thus a reduced memory footprint. [sent-167, score-0.693]

59 This is useful to tease out whether the improved generalization of jungles is due more to the reduced model complexity or to the node merging. [sent-168, score-0.54]

60 Training a tree with ﬁxed width is achieved by ranking the leaf nodes i at each level by decreasing value of E(Si ) and then greedily splitting only the M/2 nodes with highest value of the objective. [sent-169, score-0.515]

61 1 0 1 10 100 1000 10000 100000 1000000 Total number of nodes (c) Test segmentation accuracy 0. [sent-183, score-0.327]

62 8 Kinect dataset Test segmentation accuracy Test segmentation accuracy 0. [sent-213, score-0.37]

63 (a, b, c) Segmentation accuracy as a function of the total number of nodes in the ensemble (i. [sent-223, score-0.27]

64 3 The leaf nodes that are not split are discarded from further consideration. [sent-230, score-0.296]

65 Current leaf nodes are ranked by the reduction in the objective that would be achieved by splitting them. [sent-233, score-0.267]

66 At each iteration, the top M nodes are split, optimal splits computed and the new children added into the priority queue. [sent-234, score-0.257]

67 This baseline is identical to the baseline 2 above, except that nodes that are not split at a particular iteration are part of the ranking at subsequent iterations. [sent-235, score-0.385]

68 This can be seen as a form of tree pruning [13], and in the limit, will result in standard binary decision trees. [sent-236, score-0.348]

69 As shown later, the trees at intermediate iterations can give surprisingly good generalization. [sent-237, score-0.322]

70 One of our two main hypotheses is that jungles can reduce the amount of memory used compared to forests. [sent-241, score-0.449]

71 To investigate this we compared jungles to the baseline forests on three different datasets. [sent-242, score-0.65]

72 Note that the jungles of merged DAGs achieve the same accuracy as the baselines with substantially fewer total nodes. [sent-245, score-0.682]

73 2, the jungle requires around 3000 nodes whereas the standard forest require around 22000 nodes. [sent-247, score-0.303]

74 For example, the forest of 3 trees occupied 80MB on the Kinect dataset vs. [sent-249, score-0.409]

75 On the Faces dataset the forest of 3 trees occupied 7. [sent-251, score-0.409]

76 Firstly, observe how all tree-based baselines saturate and in some cases start to overﬁt as the trees become larger. [sent-256, score-0.345]

77 This is a common effect with deep trees and small ensembles. [sent-257, score-0.34]

78 3 In other words, baseline 1 optimizes the most energetic nodes, whereas baseline 2 optimizes all nodes and takes only the splits that most reduce the objective. [sent-259, score-0.348]

79 8 Kinect dataset Test segmentation accuracy Kinect dataset Test segmentation accuracy Test segmentation accuracy 0. [sent-272, score-0.571]

80 feature evaluations / pixel (c) 1 10 100 1000 10000 100000 1000000 Total number of nodes Figure 3: (a, b) Effect of ensemble size on test accuracy. [sent-282, score-0.311]

81 (a) plots accuracy against the total number of nodes in the ensemble, whereas (b) plots accuracy against the maximum number of computations required at test time. [sent-283, score-0.299]

82 For a ﬁxed ensemble size jungles of DAGs achieve consistently better generalization than conventional forests. [sent-284, score-0.515]

83 Interestingly, the width-limited tree-based baselines perform substantially better than the standard tree training algorithm, and in particular the priority scheduling appears to work very well, though still inferior to our DAG model. [sent-289, score-0.264]

84 We do not expect the reduction in memory given by merging to come for free: there is likely to be a cost in terms of the number of nodes evaluated for any individual test example. [sent-293, score-0.349]

85 For example, training 3 trees for Kinect took 32mins vs. [sent-299, score-0.363]

86 Note from (a) that in all cases, a jungle of DAGs uses substantially less memory than a standard forest for the same accuracy, and also that the merging consistently increases generalization. [sent-304, score-0.321]

87 The merged DAGs consistently outperform the standard trees both in terms of memory consumption and generalization, for all settings of M evaluated. [sent-327, score-0.61]

88 On the Kinect data, forests of 9 trees are compared to jungles of 9 DAGs. [sent-332, score-0.901]

89 The jungles appear to give smoother segmentations than the standard forests, perhaps more so than the quantitative results would suggest. [sent-333, score-0.409]

90 On the Faces data, small forests of 3 trees are compared to jungles of 3 DAGs, with each model containing only 48k nodes in total. [sent-334, score-1.059]

91 A few example results on the Kinect body parts and face segmentation tasks, comparing standard trees and merged DAGs with the same number of nodes. [sent-339, score-0.669]

92 1 0 4 10 2 10 Total number of nodes 4 10 6 10 Total number of nodes Figure 5: UCI classiﬁcation results for two data sets, MNIST-60k and Poker, eight trees or DAGs per ensemble. [sent-358, score-0.638]

93 The MNIST result is typical in that the accuracy improvements of DAGs over trees is small but achieved at a smaller number of nodes (memory). [sent-359, score-0.533]

94 The largest improvements for DAGs over trees is reported for the largest dataset (Poker). [sent-362, score-0.354]

95 5 Conclusion This paper has presented decision jungles as ensembles of rooted decision DAGs. [sent-363, score-0.985]

96 Our evaluation on a number of diverse and challenging classiﬁcation tasks has shown jungles to improve both memory efﬁciency and generalization for several tasks compared to conventional decision forests and their variants. [sent-366, score-0.959]

97 We believe that decision jungles can be extended to regression tasks. [sent-367, score-0.612]

98 We also plan to investigate multiply rooted trees and merging between DAGs within a jungle. [sent-368, score-0.506]

99 Using the minimum description length principle to infer reduced ordered decision graphs. [sent-530, score-0.244]

100 Reducing decision trees ensemble size using parallel decision DAGs. [sent-543, score-0.823]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('dags', 0.558), ('jungles', 0.391), ('trees', 0.322), ('decision', 0.221), ('merged', 0.195), ('forests', 0.188), ('dag', 0.171), ('nodes', 0.158), ('kinect', 0.121), ('segmentation', 0.116), ('lsearch', 0.108), ('merging', 0.098), ('csg', 0.094), ('jungle', 0.094), ('node', 0.09), ('tree', 0.087), ('nc', 0.086), ('rooted', 0.086), ('split', 0.085), ('np', 0.078), ('priority', 0.075), ('grass', 0.075), ('scheduled', 0.071), ('baseline', 0.071), ('clustersearch', 0.067), ('ensembles', 0.066), ('classi', 0.063), ('ensemble', 0.059), ('memory', 0.058), ('uci', 0.056), ('poker', 0.054), ('child', 0.053), ('parent', 0.053), ('leaf', 0.053), ('accuracy', 0.053), ('patches', 0.05), ('ri', 0.049), ('emanating', 0.048), ('branching', 0.044), ('intl', 0.044), ('training', 0.041), ('si', 0.04), ('objective', 0.039), ('faces', 0.038), ('generalization', 0.036), ('li', 0.035), ('test', 0.035), ('depth', 0.034), ('multiclass', 0.034), ('evaluations', 0.034), ('forest', 0.033), ('criminisi', 0.033), ('sheep', 0.033), ('dataset', 0.032), ('cow', 0.031), ('shotton', 0.031), ('labelled', 0.029), ('branches', 0.029), ('conventional', 0.029), ('jointly', 0.028), ('sj', 0.028), ('instances', 0.027), ('train', 0.026), ('kohli', 0.025), ('pixel', 0.025), ('splits', 0.024), ('yellow', 0.024), ('footprint', 0.024), ('energetic', 0.024), ('oliveira', 0.024), ('classes', 0.023), ('cation', 0.023), ('reduced', 0.023), ('baselines', 0.023), ('occupied', 0.022), ('breiman', 0.022), ('temporary', 0.022), ('root', 0.022), ('binary', 0.022), ('greedily', 0.021), ('width', 0.021), ('minimization', 0.021), ('jaccard', 0.021), ('cristianini', 0.021), ('pami', 0.02), ('lk', 0.02), ('acyclic', 0.02), ('growth', 0.02), ('optimizing', 0.02), ('randomized', 0.02), ('substantially', 0.02), ('image', 0.019), ('schedule', 0.019), ('tasks', 0.018), ('features', 0.018), ('effect', 0.018), ('face', 0.018), ('standard', 0.018), ('consumption', 0.017), ('splitting', 0.017)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999982 82 nips-2013-Decision Jungles: Compact and Rich Models for Classification

Author: Jamie Shotton, Toby Sharp, Pushmeet Kohli, Sebastian Nowozin, John Winn, Antonio Criminisi

2 0.1634362 340 nips-2013-Understanding variable importances in forests of randomized trees

Author: Gilles Louppe, Louis Wehenkel, Antonio Sutera, Pierre Geurts

Abstract: Despite growing interest and practical use in various scientiﬁc areas, variable importances derived from tree-based ensemble methods are not well understood from a theoretical point of view. In this work we characterize the Mean Decrease Impurity (MDI) variable importances as measured by an ensemble of totally randomized trees in asymptotic sample and ensemble size conditions. We derive a three-level decomposition of the information jointly provided by all input variables about the output in terms of i) the MDI importance of each input variable, ii) the degree of interaction of a given input variable with the other input variables, iii) the different interaction terms of a given degree. We then show that this MDI importance of a variable is equal to zero if and only if the variable is irrelevant and that the MDI importance of a relevant variable is invariant with respect to the removal or the addition of irrelevant variables. We illustrate these properties on a simple example and discuss how they may change in the case of non-totally randomized trees such as Random Forests and Extra-Trees. 1 Motivation An important task in many scientiﬁc ﬁelds is the prediction of a response variable based on a set of predictor variables. In many situations though, the aim is not only to make the most accurate predictions of the response but also to identify which predictor variables are the most important to make these predictions, e.g. in order to understand the underlying process. Because of their applicability to a wide range of problems and their capability to both build accurate models and, at the same time, to provide variable importance measures, Random Forests (Breiman, 2001) and variants such as Extra-Trees (Geurts et al., 2006) have become a major data analysis tool used with success in various scientiﬁc areas. Despite their extensive use in applied research, only a couple of works have studied the theoretical properties and statistical mechanisms of these algorithms. Zhao (2000), Breiman (2004), Biau et al. (2008); Biau (2012), Meinshausen (2006) and Lin and Jeon (2006) investigated simpliﬁed to very realistic variants of these algorithms and proved the consistency of those variants. Little is known however regarding the variable importances computed by Random Forests like algorithms, and – as far as we know – the work of Ishwaran (2007) is indeed the only theoretical study of tree-based variable importance measures. In this work, we aim at ﬁlling this gap and present a theoretical analysis of the Mean Decrease Impurity importance derived from ensembles of randomized trees. The rest of the paper is organized as follows: in section 2, we provide the background about ensembles of randomized trees and recall how variable importances can be derived from them; in section 3, we then derive a characterization in asymptotic conditions and show how variable importances derived from totally randomized trees offer a three-level decomposition of the information jointly contained in the input variables about the output; section 4 shows that this characterization only depends on the relevant variables and section 5 1 discusses theses ideas in the context of variants closer to the Random Forest algorithm; section 6 then illustrates all these ideas on an artiﬁcial problem; ﬁnally, section 7 includes our conclusions and proposes directions of future works. 2 Background In this section, we ﬁrst describe decision trees, as well as forests of randomized trees. Then, we describe the two major variable importances measures derived from them – including the Mean Decrease Impurity (MDI) importance that we will study in the subsequent sections. 2.1 Single classiﬁcation and regression trees and random forests A binary classiﬁcation (resp. regression) tree (Breiman et al., 1984) is an input-output model represented by a tree structure T , from a random input vector (X1 , ..., Xp ) taking its values in X1 × ... × Xp = X to a random output variable Y ∈ Y . Any node t in the tree represents a subset of the space X , with the root node being X itself. Internal nodes t are labeled with a binary test (or split) st = (Xm < c) dividing their subset in two subsets1 corresponding to their two children tL and tR , while the terminal nodes (or leaves) are labeled with a best guess value of the output ˆ variable2 . The predicted output Y for a new instance is the label of the leaf reached by the instance when it is propagated through the tree. A tree is built from a learning sample of size N drawn from P (X1 , ..., Xp , Y ) using a recursive procedure which identiﬁes at each node t the split st = s∗ for which the partition of the Nt node samples into tL and tR maximizes the decrease ∆i(s, t) = i(t) − pL i(tL ) − pR i(tR ) (1) of some impurity measure i(t) (e.g., the Gini index, the Shannon entropy, or the variance of Y ), and where pL = NtL /Nt and pR = NtR /Nt . The construction of the tree stops , e.g., when nodes become pure in terms of Y or when all variables Xi are locally constant. Single trees typically suffer from high variance, which makes them not competitive in terms of accuracy. A very efﬁcient and simple way to address this ﬂaw is to use them in the context of randomization-based ensemble methods. Speciﬁcally, the core principle is to introduce random perturbations into the learning procedure in order to produce several different decision trees from a single learning set and to use some aggregation technique to combine the predictions of all these trees. In Bagging (Breiman, 1996), trees are built on random bootstrap copies of the original data, hence producing different decision trees. In Random Forests (Breiman, 2001), Bagging is extended and combined with a randomization of the input variables that are used when considering candidate variables to split internal nodes t. In particular, instead of looking for the best split s∗ among all variables, the Random Forest algorithm selects, at each node, a random subset of K variables and then determines the best split over these latter variables only. 2.2 Variable importances In the context of ensembles of randomized trees, Breiman (2001, 2002) proposed to evaluate the importance of a variable Xm for predicting Y by adding up the weighted impurity decreases p(t)∆i(st , t) for all nodes t where Xm is used, averaged over all NT trees in the forest: Imp(Xm ) = 1 NT p(t)∆i(st , t) T (2) t∈T :v(st )=Xm and where p(t) is the proportion Nt /N of samples reaching t and v(st ) is the variable used in split st . When using the Gini index as impurity function, this measure is known as the Gini importance or Mean Decrease Gini. However, since it can be deﬁned for any impurity measure i(t), we will refer to Equation 2 as the Mean Decrease Impurity importance (MDI), no matter the impurity measure i(t). We will characterize and derive results for this measure in the rest of this text. 1 More generally, splits are deﬁned by a (not necessarily binary) partition of the range Xm of possible values of a single variable Xm . 2 e.g. determined as the majority class j(t) (resp., the average value y (t)) within the subset of the leaf t. ¯ 2 In addition to MDI, Breiman (2001, 2002) also proposed to evaluate the importance of a variable Xm by measuring the Mean Decrease Accuracy (MDA) of the forest when the values of Xm are randomly permuted in the out-of-bag samples. For that reason, this latter measure is also known as the permutation importance. Thanks to popular machine learning softwares (Breiman, 2002; Liaw and Wiener, 2002; Pedregosa et al., 2011), both of these variable importance measures have shown their practical utility in an increasing number of experimental studies. Little is known however regarding their inner workings. Strobl et al. (2007) compare both MDI and MDA and show experimentally that the former is biased towards some predictor variables. As explained by White and Liu (1994) in case of single decision trees, this bias stems from an unfair advantage given by the usual impurity functions i(t) towards predictors with a large number of values. Strobl et al. (2008) later showed that MDA is biased as well, and that it overestimates the importance of correlated variables – although this effect was not conﬁrmed in a later experimental study by Genuer et al. (2010). From a theoretical point of view, Ishwaran (2007) provides a detailed theoretical development of a simpliﬁed version of MDA, giving key insights for the understanding of the actual MDA. 3 Variable importances derived from totally randomized tree ensembles Let us now consider the MDI importance as deﬁned by Equation 2, and let us assume a set V = {X1 , ..., Xp } of categorical input variables and a categorical output Y . For the sake of simplicity we will use the Shannon entropy as impurity measure, and focus on totally randomized trees; later on we will discuss other impurity measures and tree construction algorithms. Given a training sample L of N joint observations of X1 , ..., Xp , Y independently drawn from the joint distribution P (X1 , ..., Xp , Y ), let us assume that we infer from it an inﬁnitely large ensemble of totally randomized and fully developed trees. In this setting, a totally randomized and fully developed tree is deﬁned as a decision tree in which each node t is partitioned using a variable Xi picked uniformly at random among those not yet used at the parent nodes of t, and where each t is split into |Xi | sub-trees, i.e., one for each possible value of Xi , and where the recursive construction process halts only when all p variables have been used along the current branch. Hence, in such a tree, leaves are all at the same depth p, and the set of leaves of a fully developed tree is in bijection with the set X of all possible joint conﬁgurations of the p input variables. For example, if the input variables are all binary, the resulting tree will have exactly 2p leaves. Theorem 1. The MDI importance of Xm ∈ V for Y as computed with an inﬁnite ensemble of fully developed totally randomized trees and an inﬁnitely large training sample is: p−1 Imp(Xm ) = k=0 1 1 k Cp p − k I(Xm ; Y |B), (3) B∈Pk (V −m ) where V −m denotes the subset V \ {Xm }, Pk (V −m ) is the set of subsets of V −m of cardinality k, and I(Xm ; Y |B) is the conditional mutual information of Xm and Y given the variables in B. Proof. See Appendix B. Theorem 2. For any ensemble of fully developed trees in asymptotic learning sample size conditions (e.g., in the same conditions as those of Theorem 1), we have that p Imp(Xm ) = I(X1 , . . . , Xp ; Y ). (4) m=1 Proof. See Appendix C. Together, theorems 1 and 2 show that variable importances derived from totally randomized trees in asymptotic conditions provide a three-level decomposition of the information I(X1 , . . . , Xp ; Y ) contained in the set of input variables about the output variable. The ﬁrst level is a decomposition among input variables (see Equation 4 of Theorem 2), the second level is a decomposition along the 3 degrees k of interaction terms of a variable with the other ones (see the outer sum in Equation 3 of Theorem 1), and the third level is a decomposition along the combinations B of interaction terms of ﬁxed size k of possible interacting variables (see the inner sum in Equation 3). We observe that the decomposition includes, for each variable, each and every interaction term of each and every degree weighted in a fashion resulting only from the combinatorics of possible interaction terms. In particular, since all I(Xm ; Y |B) terms are at most equal to H(Y ), the prior entropy of Y , the p terms of the outer sum of Equation 3 are each upper bounded by 1 1 1 1 1 H(Y ) = k C k H(Y ) = H(Y ). k Cp p − k Cp p − k p−1 p −m B∈Pk (V ) As such, the second level decomposition resulting from totally randomized trees makes the p sub1 1 importance terms C k p−k B∈Pk (V −m ) I(Xm ; Y |B) to equally contribute (at most) to the total p importance, even though they each include a combinatorially different number of terms. 4 Importances of relevant and irrelevant variables Following Kohavi and John (1997), let us deﬁne as relevant to Y with respect to V a variable Xm for which there exists at least one subset B ⊆ V (possibly empty) such that I(Xm ; Y |B) > 0.3 Thus we deﬁne as irrelevant to Y with respect to V a variable Xi for which, for all B ⊆ V , I(Xi ; Y |B) = 0. Remark that if Xi is irrelevant to Y with respect to V , then by deﬁnition it is also irrelevant to Y with respect to any subset of V . Theorem 3. Xi ∈ V is irrelevant to Y with respect to V if and only if its inﬁnite sample size importance as computed with an inﬁnite ensemble of fully developed totally randomized trees built on V for Y is 0. Proof. See Appendix D. Lemma 4. Let Xi ∈ V be an irrelevant variable for Y with respect to V . The inﬁnite sample size / importance of Xm ∈ V as computed with an inﬁnite ensemble of fully developed totally randomized trees built on V for Y is the same as the importance derived when using V ∪ {Xi } to build the ensemble of trees for Y . Proof. See Appendix E. Theorem 5. Let VR ⊆ V be the subset of all variables in V that are relevant to Y with respect to V . The inﬁnite sample size importance of any variable Xm ∈ VR as computed with an inﬁnite ensemble of fully developed totally randomized trees built on VR for Y is the same as its importance computed in the same conditions by using all variables in V . That is: p−1 Imp(Xm ) = k=0 r−1 = l=0 1 1 k Cp p − k 1 1 l Cr r − l I(Xm ; Y |B) B∈Pk (V −m ) (5) I(Xm ; Y |B) −m B∈Pl (VR ) where r is the number of relevant variables in VR . Proof. See Appendix F. Theorems 3 and 5 show that the importances computed with an ensemble of totally randomized trees depends only on the relevant variables. Irrelevant variables have a zero importance and do not affect the importance of relevant variables. Practically, we believe that such properties are desirable conditions for a sound criterion assessing the importance of a variable. Indeed, noise should not be credited of any importance and should not make any other variable more (or less) important. 3 Among the relevant variables, we have the marginally relevant ones, for which I(Xm ; Y ) > 0, the strongly relevant ones, for which I(Xm ; Y |V −m ) > 0, and the weakly relevant variables, which are relevant but not strongly relevant. 4 5 Random Forest variants In this section, we consider and discuss variable importances as computed with other types of ensembles of randomized trees. We ﬁrst show how our results extend to any other impurity measure, and then analyze importances computed by depth-pruned ensemble of randomized trees and those computed by randomized trees built on random subspaces of ﬁxed size. Finally, we discuss the case of non-totally randomized trees. 5.1 Generalization to other impurity measures Although our characterization in sections 3 and 4 uses Shannon entropy as the impurity measure, we show in Appendix I that theorems 1, 3 and 5 hold for other impurity measures, simply substituting conditional mutual information for conditional impurity reduction in the different formulas and in the deﬁnition of irrelevant variables. In particular, our results thus hold for the Gini index in classiﬁcation and can be extended to regression problems using variance as the impurity measure. 5.2 Pruning and random subspaces In sections 3 and 4, we considered totally randomized trees that were fully developed, i.e. until all p variables were used within each branch. When totally randomized trees are developed only up to some smaller depth q ≤ p, we show in Proposition 6 that the variable importances as computed by these trees is limited to the q ﬁrst terms of Equation 3. We then show in Proposition 7 that these latter importances are actually the same as when each tree of the ensemble is fully developed over a random subspace (Ho, 1998) of q variables drawn prior to its construction. Proposition 6. The importance of Xm ∈ V for Y as computed with an inﬁnite ensemble of pruned totally randomized trees built up to depth q ≤ p and an inﬁnitely large training sample is: q−1 Imp(Xm ) = k=0 1 1 k p−k Cp I(Xm ; Y |B) (6) B∈Pk (V −m ) Proof. See Appendix G. Proposition 7. The importance of Xm ∈ V for Y as computed with an inﬁnite ensemble of pruned totally randomized trees built up to depth q ≤ p and an inﬁnitely large training sample is identical to the importance as computed for Y with an inﬁnite ensemble of fully developed totally randomized trees built on random subspaces of q variables drawn from V . Proof. See Appendix H. As long as q ≥ r (where r denotes the number of relevant variables in V ), it can easily be shown that all relevant variables will still obtain a strictly positive importance, which will however differ in general from the importances computed by fully grown totally randomized trees built over all variables. Also, each irrelevant variable of course keeps an importance equal to zero, which means that, in asymptotic conditions, these pruning and random subspace methods would still allow us identify the relevant variables, as long as we have a good upper bound q on r. 5.3 Non-totally randomized trees In our analysis in the previous sections, trees are built totally at random and hence do not directly relate to those built in Random Forests (Breiman, 2001) or in Extra-Trees (Geurts et al., 2006). To better understand the importances as computed by those algorithms, let us consider a close variant of totally randomized trees: at each node t, let us instead draw uniformly at random 1 ≤ K ≤ p variables and let us choose the one that maximizes ∆i(t). Notice that, for K = 1, this procedure amounts to building ensembles of totally randomized trees as deﬁned before, while, for K = p, it amounts to building classical single trees in a deterministic way. First, the importance of Xm ∈ V as computed with an inﬁnite ensemble of such randomized trees is not the same as Equation 3. For K > 1, masking effects indeed appear: at t, some variables are 5 never selected because there always is some other variable for which ∆i(t) is larger. Such effects tend to pull the best variables at the top of the trees and to push the others at the leaves. As a result, the importance of a variable no longer decomposes into a sum including all I(Xm ; Y |B) terms. The importance of the best variables decomposes into a sum of their mutual information alone or conditioned only with the best others – but not conditioned with all variables since they no longer ever appear at the bottom of trees. By contrast, the importance of the least promising variables now decomposes into a sum of their mutual information conditioned only with all variables – but not alone or conditioned with a couple of others since they no longer ever appear at the top of trees. In other words, because of the guided structure of the trees, the importance of Xm now takes into account only some of the conditioning sets B, which may over- or underestimate its overall relevance. To make things clearer, let us consider a simple example. Let X1 perfectly explains Y and let X2 be a slightly noisy copy of X1 (i.e., I(X1 ; Y ) ≈ I(X2 ; Y ), I(X1 ; Y |X2 ) = and I(X2 ; Y |X1 ) = 0). Using totally randomized trees, the importances of X1 and X2 are nearly equal – the importance of X1 being slightly higher than the importance of X2 : 1 1 1 Imp(X1 ) = I(X1 ; Y ) + I(X1 ; Y |X2 ) = I(X1 ; Y ) + 2 2 2 2 1 1 1 Imp(X2 ) = I(X2 ; Y ) + I(X2 ; Y |X1 ) = I(X2 ; Y ) + 0 2 2 2 In non-totally randomized trees, for K = 2, X1 is always selected at the root node and X2 is always used in its children. Also, since X1 perfectly explains Y , all its children are pure and the reduction of entropy when splitting on X2 is null. As a result, ImpK=2 (X1 ) = I(X1 ; Y ) and ImpK=2 (X2 ) = I(X2 ; Y |X1 ) = 0. Masking effects are here clearly visible: the true importance of X2 is masked by X1 as if X2 were irrelevant, while it is only a bit less informative than X1 . As a direct consequence of the example above, for K > 1, it is no longer true that a variable is irrelevant if and only if its importance is zero. In the same way, it can also be shown that the importances become dependent on the number of irrelevant variables. Let us indeed consider the following counter-example: let us add in the previous example an irrelevant variable Xi with respect to {X1 , X2 } and let us keep K = 2. The probability of selecting X2 at the root node now becomes positive, which means that ImpK=2 (X2 ) now includes I(X2 ; Y ) > 0 and is therefore strictly larger than the importance computed before. For K ﬁxed, adding irrelevant variables dampens masking effects, which thereby makes importances indirectly dependent on the number of irrelevant variables. In conclusion, the importances as computed with totally randomized trees exhibit properties that do not possess, by extension, neither random forests nor extra-trees. With totally randomized trees, the importance of Xm only depends on the relevant variables and is 0 if and only if Xm is irrelevant. As we have shown, it may no longer be the case for K > 1. Asymptotically, the use of totally randomized trees for assessing the importance of a variable may therefore be more appropriate. In a ﬁnite setting (i.e., a limited number of samples and a limited number of trees), guiding the choice of the splitting variables remains however a sound strategy. In such a case, I(Xm ; Y |B) cannot be measured neither for all Xm nor for all B. It is therefore pragmatic to promote those that look the most promising – even if the resulting importances may be biased. 6 Illustration on a digit recognition problem In this section, we consider the digit recognition problem of (Breiman et al., 1984) for illustrating variable importances as computed with totally randomized trees. We verify that they match with our theoretical developments and that they decompose as foretold. We also compare these importances with those computed by an ensemble of non-totally randomized trees, as discussed in section 5.3, for increasing values of K. Let us consider a seven-segment indicator displaying numerals using horizontal and vertical lights in on-off combinations, as illustrated in Figure 1. Let Y be a random variable taking its value in {0, 1, ..., 9} with equal probability and let X1 , ..., X7 be binary variables whose values are each determined univocally given the corresponding value of Y in Table 1. Since Table 1 perfectly deﬁnes the data distribution, and given the small dimensionality of the problem, it is practicable to directly apply Equation 3 to compute variable importances. To verify our 6 X1 X2 y 0 1 2 3 4 5 6 7 8 9 X3 X4 X5 X6 X7 Eqn. 3 0.412 0.581 0.531 0.542 0.656 0.225 0.372 3.321 K=1 0.414 0.583 0.532 0.543 0.658 0.221 0.368 3.321 x2 1 0 0 0 1 1 1 0 1 1 x3 1 1 1 1 1 0 0 1 1 1 x4 0 0 1 1 1 1 1 0 1 1 x5 1 0 1 0 0 0 1 0 1 0 x6 1 1 0 1 1 1 1 1 1 1 x7 1 0 1 1 0 1 1 0 1 1 Table 1: Values of Y, X1 , ..., X7 Figure 1: 7-segment display X1 X2 X3 X4 X5 X6 X7 x1 1 0 1 1 0 1 1 1 1 1 K=2 0.362 0.663 0.512 0.525 0.731 0.140 0.385 3.321 K=3 0.327 0.715 0.496 0.484 0.778 0.126 0.392 3.321 K=4 0.309 0.757 0.489 0.445 0.810 0.122 0.387 3.321 K=5 0.304 0.787 0.483 0.414 0.827 0.122 0.382 3.321 K=6 0.305 0.801 0.475 0.409 0.831 0.121 0.375 3.321 K=7 0.306 0.799 0.475 0.412 0.835 0.120 0.372 3.321 Table 2: Variable importances as computed with an ensemble of randomized trees, for increasing values of K. Importances at K = 1 follow their theoretical values, as predicted by Equation 3 in Theorem 1. However, as K increases, importances diverge due to masking effects. In accordance with Theorem 2, their sum is also always equal to I(X1 , . . . , X7 ; Y ) = H(Y ) = log2 (10) = 3.321 since inputs allow to perfectly predict the output. theoretical developments, we then compare in Table 2 variable importances as computed by Equation 3 and those yielded by an ensemble of 10000 totally randomized trees (K = 1). Note that given the known structure of the problem, building trees on a sample of ﬁnite size that perfectly follows the data distribution amounts to building them on a sample of inﬁnite size. At best, trees can thus be built on a 10-sample dataset, containing exactly one sample for each of the equiprobable outcomes of Y . As the table illustrates, the importances yielded by totally randomized trees match those computed by Equation 3, which conﬁrms Theorem 1. Small differences stem from the fact that a ﬁnite number of trees were built in our simulations, but those discrepancies should disappear as the size of the ensemble grows towards inﬁnity. It also shows that importances indeed add up to I(X1 , ...X7 ; Y ), which conﬁrms Theorem 2. Regarding the actual importances, they indicate that X5 is stronger than all others, followed – in that order – by X2 , X4 and X3 which also show large importances. X1 , X7 and X6 appear to be the less informative. The table also reports importances for increasing values of K. As discussed before, we see that a large value of K yields importances that can be either overestimated (e.g., at K = 7, the importances of X2 and X5 are larger than at K = 1) or underestimated due to masking effects (e.g., at K = 7, the importances of X1 , X3 , X4 and X6 are smaller than at K = 1, as if they were less important). It can also be observed that masking effects may even induce changes in the variable rankings (e.g., compare the rankings at K = 1 and at K = 7), which thus conﬁrms that importances are differently affected. To better understand why a variable is important, it is also insightful to look at its decomposition into its p sub-importances terms, as shown in Figure 2. Each row in the plots of the ﬁgure corresponds to one the p = 7 variables and each column to a size k of conditioning sets. As such, the value at row m and column k corresponds the importance of Xm when conditioned with k other variables 1 1 (e.g., to the term C k p−k B∈Pk (V −m ) I(Xm ; Y |B) in Equation 3 in the case of totally randomized p trees). In the left plot, for K = 1, the ﬁgure ﬁrst illustrates how importances yielded by totally randomized trees decomposes along the degrees k of interactions terms. We can observe that they each equally contribute (at most) the total importance of a variable. The plot also illustrates why X5 is important: it is informative either alone or conditioned with any combination of the other variables (all of its terms are signiﬁcantly larger than 0). By contrast, it also clearly shows why 7 K=1 0.5 K=7 X1 X1 X2 X3 X4 X4 X5 X5 X6 X6 X7 0.375 X2 X3 X7 0 1 2 3 4 5 6 0.25 0.125 0 1 2 3 4 5 6 0.0 Figure 2: Decomposition of variable importances along the degrees k of interactions of one variable with the other ones. At K = 1, all I(Xm ; Y |B) are accounted for in the total importance, while at K = 7 only some of them are taken into account due to masking effects. X6 is not important: neither alone nor combined with others X6 seems to be very informative (all of its terms are close to 0). More interestingly, this ﬁgure also highlights redundancies: X7 is informative alone or conditioned with a couple of others (the ﬁrst terms are signiﬁcantly larger than 0), but becomes uninformative when conditioned with many others (the last terms are closer to 0). The right plot, for K = 7, illustrates the decomposition of importances when variables are chosen in a deterministic way. The ﬁrst thing to notice is masking effects. Some of the I(Xm ; Y |B) terms are indeed clearly never encountered and their contribution is therefore reduced to 0 in the total importance. For instance, for k = 0, the sub-importances of X2 and X5 are positive, while all others are null, which means that only those two variables are ever selected at the root node, hence masking the others. As a consequence, this also means that the importances of the remaining variables is biased and that it actually only accounts of their relevance when conditioned to X2 or X5 , but not of their relevance in other contexts. At k = 0, masking effects also amplify the contribution of I(X2 ; Y ) (resp. I(X5 ; Y )) since X2 (resp. X5 ) appears more frequently at the root node than in totally randomized trees. In addition, because nodes become pure before reaching depth p, conditioning sets of size k ≥ 4 are never actually encountered, which means that we can no longer know whether variables are still informative when conditioned to many others. All in all, this ﬁgure thus indeed conﬁrms that importances as computed with non-totally randomized trees take into account only some of the conditioning sets B, hence biasing the measured importances. 7 Conclusions In this work, we made a ﬁrst step towards understanding variable importances as computed with a forest of randomized trees. In particular, we derived a theoretical characterization of the Mean Decrease Impurity importances as computed by totally randomized trees in asymptotic conditions. We showed that they offer a three-level decomposition of the information jointly provided by all input variables about the output (Section 3). We then demonstrated (Section 4) that MDI importances as computed by totally randomized trees exhibit desirable properties for assessing the relevance of a variable: it is equal to zero if and only if the variable is irrelevant and it depends only on the relevant variables. We discussed the case of Random Forests and Extra-Trees (Section 5) and ﬁnally illustrated our developments on an artiﬁcial but insightful example (Section 6). There remain several limitations to our framework that we would like address in the future. First, our results should be adapted to binary splits as used within an actual Random Forest-like algorithm. In this setting, any node t is split in only two subsets, which means that any variable may then appear one or several times within a branch, and thus should make variable importances now dependent on the cardinalities of the input variables. In the same direction, our framework should also be extended to the case of continuous variables. Finally, results presented in this work are valid in an asymptotic setting only. An important direction of future work includes the characterization of the distribution of variable importances in a ﬁnite setting. Acknowledgements. Gilles Louppe is a research fellow of the FNRS (Belgium) and acknowledges its ﬁnancial support. This work is supported by PASCAL2 and the IUAP DYSCO, initiated by the Belgian State, Science Policy Ofﬁce. 8 References Biau, G. (2012). Analysis of a random forests model. The Journal of Machine Learning Research, 98888:1063–1095. Biau, G., Devroye, L., and Lugosi, G. (2008). Consistency of random forests and other averaging classiﬁers. The Journal of Machine Learning Research, 9:2015–2033. Breiman, L. (1996). Bagging predictors. Machine learning, 24(2):123–140. Breiman, L. (2001). Random forests. Machine learning, 45(1):5–32. Breiman, L. (2002). Manual on setting up, using, and understanding random forests v3. 1. Statistics Department University of California Berkeley, CA, USA. Breiman, L. (2004). Consistency for a simple model of random forests. Technical report, UC Berkeley. Breiman, L., Friedman, J. H., Olshen, R. A., and Stone, C. J. (1984). Classiﬁcation and regression trees. Genuer, R., Poggi, J.-M., and Tuleau-Malot, C. (2010). Variable selection using random forests. Pattern Recognition Letters, 31(14):2225–2236. Geurts, P., Ernst, D., and Wehenkel, L. (2006). Extremely randomized trees. Machine Learning, 63(1):3–42. Ho, T. (1998). The random subspace method for constructing decision forests. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 20(8):832–844. Ishwaran, H. (2007). Variable importance in binary regression trees and forests. Electronic Journal of Statistics, 1:519–537. Kohavi, R. and John, G. H. (1997). Wrappers for feature subset selection. Artiﬁcial intelligence, 97(1):273–324. Liaw, A. and Wiener, M. (2002). Classiﬁcation and regression by randomforest. R news, 2(3):18–22. Lin, Y. and Jeon, Y. (2006). Random forests and adaptive nearest neighbors. Journal of the American Statistical Association, 101(474):578–590. Meinshausen, N. (2006). Quantile regression forests. The Journal of Machine Learning Research, 7:983–999. Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., et al. (2011). Scikit-learn: Machine learning in python. The Journal of Machine Learning Research, 12:2825–2830. Strobl, C., Boulesteix, A.-L., Kneib, T., Augustin, T., and Zeileis, A. (2008). Conditional variable importance for random forests. BMC bioinformatics, 9(1):307. Strobl, C., Boulesteix, A.-L., Zeileis, A., and Hothorn, T. (2007). Bias in random forest variable importance measures: Illustrations, sources and a solution. BMC bioinformatics, 8(1):25. White, A. P. and Liu, W. Z. (1994). Technical note: Bias in information-based measures in decision tree induction. Machine Learning, 15(3):321–329. Zhao, G. (2000). A new perspective on classiﬁcation. PhD thesis, Utah State University, Department of Mathematics and Statistics. 9

3 0.11447948 211 nips-2013-Non-Linear Domain Adaptation with Boosting

Author: Carlos J. Becker, Christos M. Christoudias, Pascal Fua

Abstract: A common assumption in machine vision is that the training and test samples are drawn from the same distribution. However, there are many problems when this assumption is grossly violated, as in bio-medical applications where different acquisitions can generate drastic variations in the appearance of the data due to changing experimental conditions. This problem is accentuated with 3D data, for which annotation is very time-consuming, limiting the amount of data that can be labeled in new acquisitions for training. In this paper we present a multitask learning algorithm for domain adaptation based on boosting. Unlike previous approaches that learn task-speciﬁc decision boundaries, our method learns a single decision boundary in a shared feature space, common to all tasks. We use the boosting-trick to learn a non-linear mapping of the observations in each task, with no need for speciﬁc a-priori knowledge of its global analytical form. This yields a more parameter-free domain adaptation approach that successfully leverages learning on new tasks where labeled data is scarce. We evaluate our approach on two challenging bio-medical datasets and achieve a signiﬁcant improvement over the state of the art. 1

4 0.11024979 32 nips-2013-Aggregating Optimistic Planning Trees for Solving Markov Decision Processes

Author: Gunnar Kedenburg, Raphael Fonteneau, Remi Munos

Abstract: This paper addresses the problem of online planning in Markov decision processes using a randomized simulator, under a budget constraint. We propose a new algorithm which is based on the construction of a forest of planning trees, where each tree corresponds to a random realization of the stochastic environment. The trees are constructed using a “safe” optimistic planning strategy combining the optimistic principle (in order to explore the most promising part of the search space ﬁrst) with a safety principle (which guarantees a certain amount of uniform exploration). In the decision-making step of the algorithm, the individual trees are aggregated and an immediate action is recommended. We provide a ﬁnite-sample analysis and discuss the trade-off between the principles of optimism and safety. We also report numerical results on a benchmark problem. Our algorithm performs as well as state-of-the-art optimistic planning algorithms, and better than a related algorithm which additionally assumes the knowledge of all transition distributions. 1

5 0.10978558 93 nips-2013-Discriminative Transfer Learning with Tree-based Priors

Author: Nitish Srivastava, Ruslan Salakhutdinov

Abstract: High capacity classiﬁers, such as deep neural networks, often struggle on classes that have very few training examples. We propose a method for improving classiﬁcation performance for such classes by discovering similar classes and transferring knowledge among them. Our method learns to organize the classes into a tree hierarchy. This tree structure imposes a prior over the classiﬁer’s parameters. We show that the performance of deep neural networks can be improved by applying these priors to the weights in the last layer. Our method combines the strength of discriminatively trained deep neural networks, which typically require large amounts of training data, with tree-based priors, making deep neural networks work well on infrequent classes as well. We also propose an algorithm for learning the underlying tree structure. Starting from an initial pre-speciﬁed tree, this algorithm modiﬁes the tree to make it more pertinent to the task being solved, for example, removing semantic relationships in favour of visual ones for an image classiﬁcation task. Our method achieves state-of-the-art classiﬁcation results on the CIFAR-100 image data set and the MIR Flickr image-text data set. 1

6 0.10361787 355 nips-2013-Which Space Partitioning Tree to Use for Search?

7 0.1004365 216 nips-2013-On Flat versus Hierarchical Classification in Large-Scale Taxonomies

8 0.096100286 151 nips-2013-Learning Chordal Markov Networks by Constraint Satisfaction

9 0.095573984 349 nips-2013-Visual Concept Learning: Combining Machine Vision and Bayesian Generalization on Concept Hierarchies

10 0.08803051 289 nips-2013-Scalable kernels for graphs with continuous attributes

11 0.086488806 318 nips-2013-Structured Learning via Logistic Regression

12 0.080228552 176 nips-2013-Linear decision rule as aspiration for simple decision heuristics

13 0.069483273 47 nips-2013-Bayesian Hierarchical Community Discovery

14 0.066936463 111 nips-2013-Estimation, Optimization, and Parallelism when Data is Sparse

15 0.066735953 58 nips-2013-Binary to Bushy: Bayesian Hierarchical Clustering with the Beta Coalescent

16 0.062862433 154 nips-2013-Learning Gaussian Graphical Models with Observed or Latent FVSs

17 0.061541602 288 nips-2013-Scalable Influence Estimation in Continuous-Time Diffusion Networks

18 0.061524432 5 nips-2013-A Deep Architecture for Matching Short Texts

19 0.059695907 291 nips-2013-Sensor Selection in High-Dimensional Gaussian Trees with Nuisances

20 0.055193111 359 nips-2013-Σ-Optimality for Active Learning on Gaussian Random Fields

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.136), (1, 0.023), (2, -0.087), (3, -0.045), (4, 0.117), (5, 0.026), (6, 0.016), (7, -0.05), (8, -0.021), (9, 0.048), (10, -0.025), (11, -0.062), (12, 0.159), (13, -0.032), (14, 0.007), (15, -0.005), (16, 0.005), (17, 0.079), (18, 0.022), (19, -0.049), (20, 0.115), (21, 0.145), (22, -0.001), (23, 0.02), (24, 0.051), (25, 0.053), (26, 0.073), (27, -0.049), (28, 0.058), (29, -0.044), (30, -0.019), (31, 0.092), (32, -0.084), (33, -0.028), (34, 0.127), (35, 0.107), (36, 0.019), (37, -0.025), (38, 0.021), (39, -0.076), (40, -0.116), (41, 0.004), (42, -0.043), (43, 0.046), (44, 0.041), (45, 0.047), (46, -0.08), (47, -0.031), (48, 0.004), (49, 0.012)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.96155363 82 nips-2013-Decision Jungles: Compact and Rich Models for Classification

Author: Jamie Shotton, Toby Sharp, Pushmeet Kohli, Sebastian Nowozin, John Winn, Antonio Criminisi

2 0.76584959 340 nips-2013-Understanding variable importances in forests of randomized trees

Author: Gilles Louppe, Louis Wehenkel, Antonio Sutera, Pierre Geurts

3 0.70777428 93 nips-2013-Discriminative Transfer Learning with Tree-based Priors

Author: Nitish Srivastava, Ruslan Salakhutdinov

4 0.65047002 47 nips-2013-Bayesian Hierarchical Community Discovery

Author: Charles Blundell, Yee Whye Teh

Abstract: We propose an efﬁcient Bayesian nonparametric model for discovering hierarchical community structure in social networks. Our model is a tree-structured mixture of potentially exponentially many stochastic blockmodels. We describe a family of greedy agglomerative model selection algorithms that take just one pass through the data to learn a fully probabilistic, hierarchical community model. In the worst case, Our algorithms scale quadratically in the number of vertices of the network, but independent of the number of nested communities. In practice, the run time of our algorithms are two orders of magnitude faster than the Inﬁnite Relational Model, achieving comparable or better accuracy. 1

5 0.64842612 151 nips-2013-Learning Chordal Markov Networks by Constraint Satisfaction

Author: Jukka Corander, Tomi Janhunen, Jussi Rintanen, Henrik Nyman, Johan Pensar

Abstract: We investigate the problem of learning the structure of a Markov network from data. It is shown that the structure of such networks can be described in terms of constraints which enables the use of existing solver technology with optimization capabilities to compute optimal networks starting from initial scores computed from the data. To achieve efﬁcient encodings, we develop a novel characterization of Markov network structure using a balancing condition on the separators between cliques forming the network. The resulting translations into propositional satisﬁability and its extensions such as maximum satisﬁability, satisﬁability modulo theories, and answer set programming, enable us to prove optimal certain networks which have been previously found by stochastic search. 1

6 0.62015998 58 nips-2013-Binary to Bushy: Bayesian Hierarchical Clustering with the Beta Coalescent

7 0.61828125 216 nips-2013-On Flat versus Hierarchical Classification in Large-Scale Taxonomies

8 0.6146248 355 nips-2013-Which Space Partitioning Tree to Use for Search?

9 0.54324102 90 nips-2013-Direct 0-1 Loss Minimization and Margin Maximization with Boosting

10 0.52968419 211 nips-2013-Non-Linear Domain Adaptation with Boosting

11 0.50830418 318 nips-2013-Structured Learning via Logistic Regression

12 0.49940625 32 nips-2013-Aggregating Optimistic Planning Trees for Solving Markov Decision Processes

13 0.48818427 176 nips-2013-Linear decision rule as aspiration for simple decision heuristics

14 0.48444548 154 nips-2013-Learning Gaussian Graphical Models with Observed or Latent FVSs

15 0.46816447 349 nips-2013-Visual Concept Learning: Combining Machine Vision and Bayesian Generalization on Concept Hierarchies

16 0.45920032 275 nips-2013-Reservoir Boosting : Between Online and Offline Ensemble Learning

17 0.45474133 291 nips-2013-Sensor Selection in High-Dimensional Gaussian Trees with Nuisances

18 0.44670132 289 nips-2013-Scalable kernels for graphs with continuous attributes

19 0.43548098 343 nips-2013-Unsupervised Structure Learning of Stochastic And-Or Grammars

20 0.41932723 19 nips-2013-Accelerated Mini-Batch Stochastic Dual Coordinate Ascent

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(16, 0.065), (33, 0.128), (34, 0.088), (41, 0.016), (46, 0.011), (49, 0.017), (56, 0.087), (70, 0.042), (84, 0.221), (85, 0.047), (89, 0.035), (93, 0.12), (99, 0.015)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.8170349 82 nips-2013-Decision Jungles: Compact and Rich Models for Classification

Author: Jamie Shotton, Toby Sharp, Pushmeet Kohli, Sebastian Nowozin, John Winn, Antonio Criminisi

2 0.77692765 178 nips-2013-Locally Adaptive Bayesian Multivariate Time Series

Author: Daniele Durante, Bruno Scarpa, David Dunson

Abstract: In modeling multivariate time series, it is important to allow time-varying smoothness in the mean and covariance process. In particular, there may be certain time intervals exhibiting rapid changes and others in which changes are slow. If such locally adaptive smoothness is not accounted for, one can obtain misleading inferences and predictions, with over-smoothing across erratic time intervals and under-smoothing across times exhibiting slow variation. This can lead to miscalibration of predictive intervals, which can be substantially too narrow or wide depending on the time. We propose a continuous multivariate stochastic process for time series having locally varying smoothness in both the mean and covariance matrix. This process is constructed utilizing latent dictionary functions in time, which are given nested Gaussian process priors and linearly related to the observed data through a sparse mapping. Using a differential equation representation, we bypass usual computational bottlenecks in obtaining MCMC and online algorithms for approximate Bayesian inference. The performance is assessed in simulations and illustrated in a ﬁnancial application. 1 1.1

3 0.69456875 146 nips-2013-Large Scale Distributed Sparse Precision Estimation

Author: Huahua Wang, Arindam Banerjee, Cho-Jui Hsieh, Pradeep Ravikumar, Inderjit Dhillon

Abstract: We consider the problem of sparse precision matrix estimation in high dimensions using the CLIME estimator, which has several desirable theoretical properties. We present an inexact alternating direction method of multiplier (ADMM) algorithm for CLIME, and establish rates of convergence for both the objective and optimality conditions. Further, we develop a large scale distributed framework for the computations, which scales to millions of dimensions and trillions of parameters, using hundreds of cores. The proposed framework solves CLIME in columnblocks and only involves elementwise operations and parallel matrix multiplications. We evaluate our algorithm on both shared-memory and distributed-memory architectures, which can use block cyclic distribution of data and parameters to achieve load balance and improve the efﬁciency in the use of memory hierarchies. Experimental results show that our algorithm is substantially more scalable than state-of-the-art methods and scales almost linearly with the number of cores. 1

4 0.6918546 215 nips-2013-On Decomposing the Proximal Map

Author: Yao-Liang Yu

Abstract: The proximal map is the key step in gradient-type algorithms, which have become prevalent in large-scale high-dimensional problems. For simple functions this proximal map is available in closed-form while for more complicated functions it can become highly nontrivial. Motivated by the need of combining regularizers to simultaneously induce different types of structures, this paper initiates a systematic investigation of when the proximal map of a sum of functions decomposes into the composition of the proximal maps of the individual summands. We not only unify a few known results scattered in the literature but also discover several new decompositions obtained almost effortlessly from our theory. 1

5 0.68503112 99 nips-2013-Dropout Training as Adaptive Regularization

Author: Stefan Wager, Sida Wang, Percy Liang

Abstract: Dropout and other feature noising schemes control overﬁtting by artiﬁcially corrupting the training data. For generalized linear models, dropout performs a form of adaptive regularization. Using this viewpoint, we show that the dropout regularizer is ﬁrst-order equivalent to an L2 regularizer applied after scaling the features by an estimate of the inverse diagonal Fisher information matrix. We also establish a connection to AdaGrad, an online learning algorithm, and ﬁnd that a close relative of AdaGrad operates by repeatedly solving linear dropout-regularized problems. By casting dropout as regularization, we develop a natural semi-supervised algorithm that uses unlabeled data to create a better adaptive regularizer. We apply this idea to document classiﬁcation tasks, and show that it consistently boosts the performance of dropout training, improving on state-of-the-art results on the IMDB reviews dataset. 1

6 0.6826601 65 nips-2013-Compressive Feature Learning

7 0.67779475 172 nips-2013-Learning word embeddings efficiently with noise-contrastive estimation

8 0.67588538 251 nips-2013-Predicting Parameters in Deep Learning

9 0.67503148 211 nips-2013-Non-Linear Domain Adaptation with Boosting

10 0.67164427 5 nips-2013-A Deep Architecture for Matching Short Texts

11 0.66894913 179 nips-2013-Low-Rank Matrix and Tensor Completion via Adaptive Sampling

12 0.66714901 30 nips-2013-Adaptive dropout for training deep neural networks

13 0.66484523 94 nips-2013-Distributed $k$-means and $k$-median Clustering on General Topologies

14 0.66463649 45 nips-2013-BIG & QUIC: Sparse Inverse Covariance Estimation for a Million Variables

15 0.6618073 201 nips-2013-Multi-Task Bayesian Optimization

16 0.66173512 22 nips-2013-Action is in the Eye of the Beholder: Eye-gaze Driven Model for Spatio-Temporal Action Localization

17 0.66038704 339 nips-2013-Understanding Dropout

18 0.66008246 12 nips-2013-A Novel Two-Step Method for Cross Language Representation Learning

19 0.65805346 340 nips-2013-Understanding variable importances in forests of randomized trees

20 0.6571483 114 nips-2013-Extracting regions of interest from biological images with convolutional sparse block coding