Alternating Optimization of Decision Trees, with Application to Learning Sparse Oblique Trees
Learning a decision tree from data is a difficult optimization problem. The most widespread algorithm in practice, dating to the 1980s, is based on a greedy growth of the tree structure by recursively splitting nodes, and possibly pruning back the final tree. The parameters (decision function) of an internal node are approximately estimated by minimizing an impurity measure. We give an algorithm that, given an input tree (its structure and the parameter values at its nodes), produces a new tree with the same or smaller structure but new parameter values that provably lower or leave unchanged the misclassification error. This can be applied to both axis-aligned and oblique trees and our experiments show it consistently outperforms various other algorithms while being highly scalable to large datasets and trees. Further, the same algorithm can handle a sparsity penalty, so it can learn sparse oblique trees, having a structure that is a subset of the original tree and few nonzero parameters. This combines the best of axis-aligned and oblique trees: flexibility to model correlated data, low generalization error, fast inference and interpretable nodes that involve only a few features in their decision.
I am satisfied with the authors' response, the new experiments make a good addition and improve the paper. Thus I maintain my score and reommend accepting this work. ----- This paper presents an improvement scheme for (binary) decision trees, which takes a given tree (e.g., output of the CART algorithm) and iteratively refines it using an alternating misclassification error minimization scheme that optimizes over subsets of the tree nodes while keeping the rest fixed. The proposed method can handle both axis-aligned trees (single-feature decision nodes) as well as oblique trees (with decision hyperplanes), and in the latter case, incorporate sparsity-promoting penalties in order to obtain more interpretable oblique trees where each decision node involves a few features only. The TAO (tree alternating optimization) algorithm exploits natural separability of classification paths to define its subproblems, and although no substantial theoretical guarantees are provided for successful improvement, numerical experiments validate the approach and demonstrate that the overall classification accuracy can be improved significantly by running TAO on given trees. Based on my detailed reading (see comments below), I recommend accepting this submission.  The main strength of the paper is the relatively versatile algorithmic scheme to refine decision trees that at least works well in practice, although unfortunately no strong theoretical results have been proven yet. The separability of misclassification errors over tree nodes is not a deep result, but is used cleverly to define error-minimization subproblems involving only parameters of disjoint subsets of the tree nodes that can be (approximately) solved efficiently when the remaining parameters are kept fixed, thus enabling the use of alternating optimization to improve the overall tree. All in all, the paper is well-written and the problems under consideration are well-motivated.  A weak spot of the present work is the lack of theoretical understanding of the proposed method; however, as the tackled problems are NP-hard and inherently discrete (w.r.t. the tree structure/design itself), it is difficult to analyze something like approximation properties of alternating minimization schemes that are more commonly employed in continuous problems, and in light of the convincing numerical results, I do not think this is a big problem (but it should certainly be on the agenda for future research). Moving on, I would like to see some aspects clarified:  1. At some points (particularly, in the abstract), it sounds like TAO is a stand-alone algorithm to learn decision trees that „outperforms various other algorithms“ – this is misleading, as TAO requires a tree as input and cannot start from scratch by itself. Thus, please rephrase to more accurately emphasize that TAO can (significantly) improve the classification accuracy for given decision trees, and particularly given its short runtime, suggests itself as a kind of postprocessing routine for whatever method may be used to obtain a tree in the first place.  2. I would have liked to see experiments combining TAO with the MIP approaches (OCT for axis-aligned, and OCT-H for oblique trees) by Bertsimas & Dunn (cf. suppl. mat.). Specifically, what are the improvements achievable by running TAO on the trees produced by these methods, and vice versa, what may be gained by providing TAO-trees (e.g., obtained by refining CART trees) to the MIP solver as initial solutions? However, I am not sure if the OCT code is accessible, so the authors may not be able to conduct such experiments in the short time until their response is due; but perhaps this is something to consider in the future.  3. There is some lack of (notational) clarity or imprecise wording that I would like to see resolved: a) top of p. 2, in „Finding an optimal decision tree is NP-complete [...]“ – only decision problems can be contained in NP (and thus, be NP-complete if they are at the same time NP-hard), not optimization problems. So, here, it should say „... is NP-hard ...“. b) p. 2, 2nd bullet: „...tends to get stuck in poor local optima...“ (I suggest inserting „local“ to be entirely clear here) c) p. 3, 2nd paragraph: „(multilinear) linear programming“ – unclear, what „multilinear“ is to mean here; please clarify. Also, in that paragraph, the papers cited w.r.t. the claim that the „linear program is so large that the procedure is only practical for very small trees“ are over 20 years old – are you sure that this statement still holds true, given the immense progress in LP-solvers over the past two decades? It would be nice to see a more recent reference for this claim, or else a remark on own computational experience in that regard. Finally, I don't quite see why the Norouzi et al. method should not be applicable to axis-aligned trees – are they not special cases of oblique trees (with unit vectors as decision hyperplanes)? Could you please clarify why it is supposedly not applicable? (Also, starting here, you talk about „induced trees“ several times, but never clearly say what „induced“ means, so maybe define that explicitly at first occurrence.) d) p. 3, 3rd par. and 2nd bullet: Early on (on p. 1), you state the node decision question in oblique trees as strict hyperplane-inequalities, and on p. 3 write that Bertsimas & Dunn „...smooth the strict inequalities ... by adding a small constant value to one side, which can alter the solution“ – does that really matter/is this even necessary? After all, as you yourself do later on p. 3, the decision question could simply be „flipped“ so as to work with non-strict inequalities. So, please, clarify if this makes any differences and if not, make the exposition of these aspects a bit clearer and more consistent. e) In Eq. (2) should be a minimization problem (and is indeed referred to as an optimization problem later on), but the „min“ is missing. f) Thm. 3.1 and its proof: The functional $\mathcal{L}_i(\theta_i)$ should be explicitly given somewhere, preferably in the theorem or else in its proof. (Gathering what it should look like from the present description only, I believe it would be $\mathcal{L}_i(\theta_i) = \sum_{n\in\mathcal{S}_i} L(y_n, T(x_n,\{ \theta_i : i\in\mathcal{S}_i \} )$ – is that correct?) Also, the word „constant“ is a bit misleading, although it becomes clear what is meant; if possible, perhaps clarify further. g) p. 4, 4th par.: Could you please elaborate a bit what you mean by „... a smaller tree that … probably generalizes better“ ? h) p. 4, „Optimizing (2) over a leaf“: Perhaps clarify the „majority vote“ (I take this to mean you pick the most-occurring label from training points routed to this leaf?). Also, what is „otherwise“ here – are the classifiers at leaves not defined to be labels...? i) p. 4, last par.: „...misclassification loss for a subset $\mathcal{C}_i$ ...“ – should it not be $\mathcal{S}_i$ here? Also, „...optimizing (2) where the misclassification error is summed over the whole training set is equivalent to optimizing it over the subset of training points $\mathcal{S}_i that reach node $i$.“ – and then summing the subset-errors over all $i$ ? (Else, I don't see this.) Please elaborate/be a bit clearer here. j) p. 5, 1st par.: So, is $\mathcal{C}_i$ a subset of $\mathcal{S}_i$ ? Perhaps include this relation at first occurrence of $\mathcal{C}_i$ to make it clear. k) p. 5, regarding „Sparse oblique trees“ – What about working with L0 directly rather than resorting to L1 as a sparsity proxy? (Naturally, this yields NP-hard problems again, but there are efficient iterative schemes that may work well in practice.) I don't expect the authors to work out the whole thing based on exact (L0-) sparsity measures, but I would like to see a brief discussion of this aspect at this point. l) In the suppl. mat., Fig. 2: The legend is sticking out – perhaps it could just be moved into the „empty“ part of Fig. 2 at the bottom right?  Finally, there are several typos, so please proof-read again and fix what you find (out of space to list all I found, but e.g.: "vs"/"vs.","eq."/"Eq.","fig./Fig.","inputed").