Semi-Supervised Learning with Decision Trees: Graph Laplacian Tree Alternating Optimization
Authors: Arman Zharmagambetov
Miguel A. Carreira-Perpinan
Venue: NeurIPS 2022 Accept (2022)
Keywords: semi-supervised learning
decision trees
alternating optimization
graph prior
interpretability

Abstract: Semi-supervised learning seeks to learn a machine learning model when only a small amount of the available data is labeled. The most widespread approach uses a graph prior, which encourages similar instances to have similar predictions. This has been very successful with models ranging from kernel machines to neural networks, but has remained inapplicable to decision trees, for which the optimization problem is much harder. We solve this based on a reformulation of the problem which requires iteratively solving two simpler problems: a supervised tree learning problem, which can be solved by the Tree Alternating Optimization algorithm; and a label smoothing problem, which can be solved through a sparse linear system. The algorithm is scalable and highly effective even with very few labeled instances, and makes it possible to learn accurate, interpretable models based on decision trees in such situations.

Semi-Supervised Learning with Decision Trees: Graph Laplacian Tree Alternating Optimization
Arman Zharmagambetoy Dept. of Computer Science and Engineering University of California, Merced azcharmagaabettovvcuuerrrro edu
Miguel Á. Carreira-Perpinán Dept. of Computer Science and Engineering University California, Merced mcarreiira-perpinnnnccceeettt edu
Abstract
Semi-supervised learning seeks to learn a machine learning model when only a small amount of the available data is labeled. The most widespread approach uses a graph prior, which encourages similar instances to have similar predictions. This has been very successful with models ranging from kernel machines neural net- works, but has remained inapplicable to decision trees, for which the optimization problem is much harder. We solve this based on a reformulation of the problem which requires iteratively solving two simpler problems: supervised tree learn- ing problem, which can be solved by the Tree Alternating Optimization algorithm; and label smoothing problem, which can be solved through sparse linear sys- tem. The algorithm scalable and highly effective even with very few labeled instances, and makes it possible to learn accurate, interpretable models based on decision trees in such situations.
Introduction
Semi-supervised learning (SSL.) is an important subfield of machine learning which has received lot of attention in recent years given today's growing amount of data and widespread deployment of machine learning systems. One of the major reasons is that SSL is applicable when labels are scarce. This is in contrast to the traditional fully supervised learning, which requires access to large amount of high-quality labeled data. However, obtaining such samples is often costly, time-consuming and sometimes
impractical. Therefore, SSL methods have received much praise in the machine learning literature (40) and they are widely used in many applications. A common strategy in SSL is to assume that similar instances have similar predictions, which is commonly incorporated into an objective as a graph prior (e.g. graph Laplacian).
In this paper, study the problem of training decision tree model by leveraging small percentage of labeled data and a much larger sample of unlabeled data. Why trees? First, trees are considered to be interpretable models, since the prediction is obtained by routing an input along unique root- to-leaf path, which can reformulated as if-then rules. Second, they are widely used in a wide spectrum of applications, such as data mining (30). computer vision [13]. finance, etc. They are typically employed as base learners in an ensemble (e.g. bagging [3] or boosting (15)). However, they used standalone predictors well. For instance, recent algorithmic advances in training non non-greedy trees have shown that oblique trees can perform competitively well in number of tasks
and strike good balance between accuracy and interpretability 6 5. 16
18
34 36).
However, like many non-linear methods, decision trees are well known to overfit for small-sized (labeled) data, which is the case in SSL. As an illustration, consider fig. [ that shows a synthetic binary classification problem 2D. An oblique tree achieves certain good performance when is provided the entire population of labeled data. But the enror significantly increases if tree is trained on six labeled instances only (plot 3). Whereas the benefit is evident when we provide all
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

ground truth error: 0.0%
all data
tree labeled data error: 23.46%
LapTAO (ours) error: 8.78%
error: 4.5%
0
0
-1
Binary classification on 2D. Plot 1 shows the original data and corresponding class labels. Cross markers (x, six in total) indicate the labeled points that provide to any given SSL algorithm. "TTre on all data" shows the decision boundary obtained by using all available labeled data, whereas plot 3 uses only six labeled points to train tree. Plot 4 shows the result of our SSL framework. All trees are oblique of depth A ==
Figure I:
data (six labeled and the rest are unlabeled) and properly optimize tree within SSL framework. In our proposed approach, we first state the objective, which consists of a supervised loss (for the labeled data only) and graph Laplacian regularization (also known as manifold regularization (2)). The resulting optimization problem is long considered to be hard to solve since trees define a non- differentiable, non-convex mapping. By reformulating the problem as constrained optimization, we derive an efficient and scalable iterative algorithm (section which requires solving two simpler problems at each step: a sparse linear system and a supervised tree learning problem. For the latter, we use the Tree Alternating Optimization algorithm [6. S]. which is crucial for the success of our approach (section 3.I. Moreover, for a special case where the tree structure as well as the parameters in each decision node (not leaves) are fixed, we derive the exact solution given by another linear system (section (.3) Experimental results (section 4 show the algorithm able to learn accurate and interpretable decision trees even with very few labeled instances.
2 Related work
Although the literature on this topic is immense (see [40 291),, incorporating decision trees into SSL has received almost no attention. One possible explanation is the difficulty of the optimization prob- lem. Most SSL methods are based on adding graph prior (or similarity matrix) as regularization
to exploit the geometry of the underlying data distribution 22. 39
42 Minimizing an objective
with such regularization is non-trivial when we have decision trees as a predictive model.
That said, several attempts have been made to apply SSL for trees. Levatić et al. [23] modify a splitting criterion for recursive tree induction by taking into account unlabeled data. That is, a splitting score for each [feature, threshold] pair consists of two parts: the traditional purity score (e.g. Gini index) for labeled data and a "clustering" score for all available data. Tanha al. [27] apply self-training framework [33] to train classification trees with labeled and unlabeled data. Note that self-training is generic framework that can be applied with any classifier which predicts class probabilities, It trains a classifier iteratively where the first iteration includes only labeled data. After that, uses model predictions and adds the most confidently predicted instances enrich the amount of supervision. Another direct approach is to apply label smoothing technique [41] to propagate label information to all data and then fit a tree. This method has been recently reused within the graph neural networks framework to train boosted trees [12 21).. Finally, Kemp et al. [22] proposed a Bayesian approach where unlabeled data assist in inferring a latent tree structure from distribution over trees. The limitations of this approach are that it covers classification tasks only, and it uses Markov Chain Monte Carlo to sample from the distribution over trees, which leads to scalability issues.
Unlike all these methods, we attempt to directly minimize a regularized SSL objective (with graph prior) over the parameters of decision tree. The method is applicable to both regression and

---

classification problems, and can train trees of arbitrary type (i.e., axis-aligned, oblique, etc.). In fact, our optimization framework is generally applicable to any type of predictive functions, not just trees.
3 LapTAO: semi-supervised learning framework for decision trees
We are given the dataset D = =D; UD, where Dj {xn: Vo C R x R is the labeled portion of the data, with I points, and D. = (xn | C R is the unlabeled portion, with N points. Then our goal is to minimize the following regularized objective:
F(()
Σ (T(x;; 3) - yn)) + n=1
2 +7
Σ 7L,M7:1
Wnm (T(x,; 2) T(xm: 0)) (1)
Here, Wnm are the weights in the affinity (similarity) matrix based on a graph on all the data points
D. usually nearest- graph; T: RR" R is the tree predictive mapping. with parameters @ = (0; bodes: of-) is regularization penalty, such as |I-II; and y.a are regularization hyperparam- eters. Rather than using greedy recursive partitioning procedure (such as CART [4] C5.0 (26)), which does not optimize any loss function, we consider 7 as a parametric model with trainable weights in each node (like fixing neural net architecture and optimizing over its parameters). If T was differentiable, one could optimize (I via gradient- based methods, as can be done for neural nets [3]] Similarly, the solution relatively straightforward However, solving problem ( is non-trivial with a tree which defines a non-differentiable and non- convex mapping. Instead, we apply the method of auxiliary coordinates g 91, generic method for optimizing nested systems.
obtain if problem ①I convex [2].
We proceed follows by reformulating problem ① in equivalent form (similar to that in 7 36 17 for dimensionality reduction and clustering). Introduce a new auxiliary variable žn E R for each training instance and consider the constrained problem:
min A
Σ (En vn) n=1
+ Φ ()) +Y
Wam (En 2m)²
(2)
7,m=1
in Txx;; 4 I,...,,. N.
Obviously, by putting the constraints 3 back into eq. 2 we end up with the same objective as in ①. so these problems are equivalent. Let us denote y [y1 V2...... 31, O...... R the augmented ground truth vector, i.e,, we put zeros in the unlabeled portion of the data. Similarly, introduce a diagonal matrix J diag(1,.... 1, 0)
NNN with the first diagonal entries equal to and the rest to 0. Also, let the graph Laplacian be L. = D W with a diagonal matrix D NxN (the degree matrix) having entries dnn = Σ Wnm. and let W (Wmm) N be the affinity matrix. Finally, call z = [a1..... =x] and t(X; θ) = [7(x;; θ) i)...................... T.....,,TNNNN, ((xx; O))T.
where (x1, ........ ..... XN). Then we can rewrite eq. (2) as follows:
min (z y) (z y) (( zzz s.t. z))
(4)
x
Now we solve this using the augmented Lagrangian method (25]. This defines a new, unconstrained optimization problem:
min (z - J (z y) + (x)+)((0)))))))) + x Lz X² (x) - ((x;)) (5) 2
where E RN are the estimates of the Lagrange multipliers. Optimizing this for each μ > produces sequence of (Z (X; Q)) and, as + oc, gradually force the minimizer to be in the feasible set of the constrained problem. Finally, in order to minimize (5) over z and t(x; θ) for fixed μ. we apply alternating optimization over and O
Label-step (optimizing over z given fixed t(X; O)). The objective in eq. tion and minimizer is obtained by solving the linear system:
5 is a quadratic func-
min (z y) (z y) + x L z X (z t(x: +)) + /1|2 2|
(6)
1 ト
Az = Jy t θ
3

---

where A = = μi L is positive definite matrix. Moreover, A is a sparse matrix if the graph Laplacian L sparse, which is the case in practice we construct W by using a nearest neighbors graph. This allows us to solve large scale linear system in an efficient way (e.g. by caching a matrix factorization or using the conjugate gradient method). Intuitively, the label-step can be interpreted as approximating the labels (for D.,) using the graph Laplacian and predictions obtained from the current tree (i.e., label smoothing).
Tree-step (optimizing over θ given fixed z). Problem (5) reduces to regression fit of a tree:
min
t(X;
0)1 + (( - (= t(X; +
min 0
2 2μ -tx)
2
+ (+))
- 2μ as "ground-truth" labels (not yn. which is not defined for Du anyway). We solve this problem using the Tree Alternating Optimization (TAO) algorithm, which we describe in section [3.1 below. Intuitively, this step can be understood as fitting tree with the current estimates of the labels.
Note that here we use (z
Finally, the step over Lagrange multipliers is done by the update À + A 102 t(x: In summary, our algorithm alternates between solving a linear system and training a tree. After each trabel, we increase the penalty parameter Jr, we update À and we keep iterating until approximate convergence or other stopping criterion (e.g. maximum number of iterations reached). We call our algorithm LapTAO and provide detailed pseudocode in the suppl. mat.
Initialization for LapTAO To start our iterative algorithm, we need to obtain initial solutions (Zo. to) for eq. ( when μ - 0+. This is straightforward to achieve for zo, as it involves solving the same linear system as in eq. (6) but with non-parametric smoothing of the labels obtained by propagating (diffusing) the
0 and À = O: (J + >L)z = Jy. This can
be considered ground- ground-truth labels over all points (labeled and unlabeled) through the graph Laplacian. Although these smoothed labels are not optimal in problem (,, which requires optimizing them jointly with the tree, they do provide a good initialization, and it is convenient to solve the linear system exactly for / O. After that, requires an initial tree (see section [.I]), which we obtain by generating a complete tree of depth A (a hyperparameter) with a Gaussian random weight vector at each decision node.
fit
using Zo as ground-truth labels (tree-step)- Note that TAO
Hyperparameters of LapTAO The hyperparameters are r for the graph prior and (sparsity) and A (depth) for the tree. They can be selected by cross-validation.
Extension to multioutput regression and classification We can extend LapTAO for multiple outputs in a straightforward way: the label-step solves the linear system (6) for each dimension separately and the tree-step applies TAO as usual, as it can handle a vector-valued output. For classification, we use a one-hot encoding of the labels and consider the problem as regression task, as is commonly done in the decision tree literature [9] (especially for boosted trees). It is possible to extend our framework for other losses (c.g. hinge, logistic) that may work better for classification. This requires certain changes in the label-step and we will explore in our future works.
Extension to models other than trees Although our focus in this paper decision trees, the semi-supervised learning optimization algorithm we propose is perfectly general. The model (T(x; +)) appears in the algorithm in the tree-step, with the form of a regression problem hav- ing the smoothed labels as ground-truth. Obviously, we can use other regression models, such as random forests, gradient boosted trees, neural networks, etc. The motivation use our approach was the fact that trees are not differentiable, so one cannot optimize problem ①[ by gradient-based methods. But our approach has another, computational advantage: by separating terms through the auxiliary variables z, the quadratic-cost term is confined to the label-step. For large datasets, this is a sparse linear system, for which efficient algorithms exist. Hence, the complexity associated with the model (tree) is linear on the dataset size (in the tree-step). This is much faster than having to deal directly with the quadratic term and the model, as in eq. ①. whether for trees or other models.
3.1 Overview of the tree alternating optimization (TAO) algorithm
Potentially, one could apply any tree fitting algorithm to solve the tree-step in LapTAO, such as CART 4). C5.0 26). OC1 (24]. etc. (we do show such results in the suppl. mat.). But there

---

are several important considerations. Firstly, from an optimization point of view, it is known that alternating optimization most effective when the step over each block (ideally) exact. This is computationally achievable for the label-step, which involves a linear system. However, training tree optimally even in the simplest case (axes-aligned with binary inputs and output) NP-hard [20]. Therefore, we need an approximate but good solution. Most traditional tree learning algorithms, based on greedy recursive partitioning (such as CART), are highly suboptimal [19] and do not even consider any specific loss function over trees. In contrast, the Tree Alternating Optimization (TAO) algorithm [6. [S] fits decision trees by monotonically decreasing a well-definet and very general loss function and regularization over a well-defined parametric space of trees, given initial tree structure and parameter values. This makes also possible to use warm-start in the tree-step. i... to continue improving the tree from the previous cerration-wicee greedy recursive partitioning cannot do, as it constructs a new tree from scratch every time. Warm-start is essential to speed up the optimization and to achieve stability in the results (CART-type algorithms are notoriously unstable in that small changes in the training set can result in drastically different tree structures and parameters (19)). A further, important advantage of TAO is that it can learn trees of quite general types, such as oblique trees (see section 3.2), which are far more powerful that the traditional axes- aligned trees.
TAO has been shown to find much better trees under a variety of losses, regularization and types of tree, well as forests, and scales well to large datasets, e.g. [37 34 provide a summary of TAO for completeness; more details can be found in
38
35
16,
Id). Below
TAO considers decision tree parametric model with given structure and trainable parameters in each node ( = {0.) modes), and it optimizes an objective consisting of a loss and a regularization term, such as that in eq. 7 TAO requires the loss to be sum individual points, so it cannot handle eq- (., which includes pairwise distances. However, our reformulation of the problem allows us to apply TAO since the minimization in eq. is now in the desirable form.
6
5
34).
TAO takes as input an initial tree, for example a complete tree of depth A with random weights at each node, tree created by another algorithm. It uses separability condition to decompose the loss function non-descendant w.r.t. each other and can be trained independently (and in parallel). Then, TAO uses an alternating optimization scheme such as the following: 1) pick all nodes at a certain depth and fix all remaining nodes (i.e., we consider them as function with constant parameters); 2) optimize each node at that depth efficiently by solving a reduced problem (see below); 3) repeat this for all depths. One pass through all nodes is TAO iteration, and keep iterating until convergence occurs or until we reach a maximum number of iterations (see pseudocode in the suppl. mat.). Optimizing a single node (decision node or leaf) over its parameters can be shown to be equivalent to a simpler, reduced problem operating only on those training points which currently reach i (denoted as reduced sel R.). The solution of the reduced problem depends on the type of node:
Z over subsets of non-descendant nodes. For instance, all nodes at the same depth are
Decision node. With binary trees, this involves solving certain binary classification problem. Given the reduced set R2, we pass each input (xn: yn) E R, to both children of i and calculate the error (elen, <x induced by each child (note that all descendant nodes and their parameters are fixed). Next, assign a pseudolabel In E {11,1} depending on which child brings the lower error (either left right). Each pscudolabel comes with the weight |e] - -e right since the error made for each instance is different. Solve a weighted 0/1 loss binary classification on (Xn: }.
Leaf. The actual prediction of tree occurs in its leaves; the decision nodes are just responsible for routing a point to the corresponding leaf. Therefore, the optimization problem for leaf is equivalent to the original problem 7 but on its reduced set. Its solution depends on what type of leaf model we use. With constant label, it is the average of the response values (y,,) in that leaf. With linear leaves, the solution is to fit a linear regressor on R, (possibly with regularization).
3.2 Sparse oblique decision trees
The TAO algorithm is applicable to a large spectrum of decision tree types. Here we pick sparse oblique tree with constant leaves as our main model. Each decision node i makes a hyperplane- based split: go to the left child if w x < Who, else go the right one. Therefore, the decision node reduced problem (which is NP-hard) is approximated by fitting logistic regression. Additionally, we apply an l penalty as regularization term Φi-) to encourage sparsity. We use LIBLINEAR [14] to fit this model. As for the leaves, we take the average of the response values (y) in that leaf.
5

---

The motivation behind choosing sparse oblique trees is twofold. First, traditional axis axis-aligned trees are very restrictive since each split uses a single feature, which neglects interactions or correlations between features. Indeed, empirical results show oblique trees achieve far better performance [38]. Besides, thanks to the sparsity, only few features are active at each split, and nodes the initial tree can become redundant and be pruned if their weight w, becomes zero G This, together with the fact that oblique trees typically have small depth, makes the final model more interpretable.
3.3 Special case: exact solution when the tree structure fixed
Problem (I) is hard to solve over the entire space of decision trees, but we can obtain an exact solution if the structure and decision node parameters are fixed, since then the problem reduces to solving linear system. In this case, the only parameters to optimize are in the leaves. Assuming each leaf outputs constant value, we can reformulate the tree prediction as sum of basis functions T(x)= De C; b; (x), where m is the number of leaves, C E R is leaf i's label and b;(-) {0, } only x ends up in leaf Now we can rewrite ① as the following minimization problem over the parameters of all the leaves c (el,...,,m.)
m
m
F(c) Σ
Σ
ci bx(xxx)
V/
+
Σ 7,m=1
Wrem
Σ 1=1
Gi (b:(xx)) - bo(xm))
(8)
(Bc- - y- (Bc - y)
LBC
where B (bx(x,)) RNxx can be precomputed since we fix the tree structure and parameters in all decision nodes. Minimizing this over с yields the following linear system:
Ac = By By
(10)
where A = B + B'LB a matrix of m x m. This is very fast to solve since oblique trees quite shallow, the number of leaves is not large (at most 1 000 in experiments). Once LapTAO finished, we apply the above procedure as a post-processing to the final tree.
3.4 Computational complexity of LapTAO
At the top level, LapTAO runs fixed number of iterations (depending on the schedule, typically less than 20). Each iteration has to solve (approximately) two subproblems:
Label-step: this is large, sparse linear system of N x N (where N is the sample size). We solve it approximately with conjugate gradients (CG), initialized by the previous iterate (warm-start). Each CG iteration is (NN)) where 1: is the average number of neighbors in the graph, and just few CG iterations. The total runtime of the label step is less than 30 seconds in the largest experiment we conducted (IM points). Convergence can be further improved via preconditioning (e.g. Jacobi). We can also solve the linear system exactly in O(N²) by caching its SVD, as noted in the suppl. mat. (section 3), but this is only convenient if N is few thousands most.
fitting an oblique tree with TAO the N training points. Each iteration of TAO updates each decision node and leaf node. For each leaf, we compute the average the labels of its reduced set (training points reaching it), so this is O(N) over all the leaves. For each decision node, we train a logistic regression on its reduced set. Assuming logistic regression is linear on the sample size and dimensionality, this is O(N D)) total for all the decision nodes the same depth, although with a larger constant factor in the big-O notation than for the leaves. Hence, processing all the decision nodes in the tree is O D(AND) D)) equivalently, running A logistic regressions on the whole training set. See more details in [6 [] A critical computational advantage of TAO is due to the fact that each node (decision leaf node) only handles the points in its reduced set. Therefore, TAO itself can be parallelized depthwise. In summary, the overall runtime of TAO is O) per TAO iteration. We run 10 TAO iterations in our experiments.
Tree-step:
Since the tree-step dominates the label-step, in terms of runtime our algorithm is almost like se- quentially training decision trees (as in boosting). Additionally, each tree-step can be parallelized. Further acceleration can be done using GPUs. This is possible with GPU-friendly inplementations of logistic regression, and also because oblique trees involve scalar products (unlike axis-aligned trees).

---

Finally, this computational cost should also include computing the nearest- neighbr graph and its affinity matrix W. This is indeed a large cost, and it affects all semi-supervised learning methods based on the graph Laplacian. A naive implementation requires O(DN2) to calculate the distance vector for each point and determine the nearest neighbors. For large datasets, one usually uses approximate nearest neighbors (e.g. via Locality Sensitive Hashing or other techniques Пi).
In terms of storage, besides the tree T, we need store the auxiliary variables (predieted labels) for the entire training set, which are N scalars for ID regression or binary classification.
4 Experiments
This section shows our experimental findings. We demonstrate that the proposed method domi- nates over other semi-supervised learning frameworks in accuracy and approaches fully supervised baseline with far less amount of labeled data. This is true with practically no exceptions against baseline tree-based models where accuracy margin is often quite large. As for the other methods (non tree-based), we either outperform them or achieve similar error, which makes LapTAO a strong competitor. To show that, we consider several regression and classification benchmarks of varying sizes and across different domains. We were able to run our algorithm on dataset with up I million instances on a regular PC, which shows its scalability. Moreover, using fashion-mnist as an example, we demonstrate that the final model, shallow oblique tree with sparse parameter vector in each node, provides insights into how it achieves a prediction allowing model interpretability.
4.1 Experimental setup
We compare our proposed approach (LapTAO) with the following baselines: 1) oblique-al all fits an oblique tree with full supervision, this shows the theoretical maximum performance we can achieve; 2) oblique-lbl is the oblique trees trained on labeled portion of data Dj (this completely discards large portion of unlabeled data); 3) Self-training (axis-self, oblique-self) is iterative procedure that uses the model predictions to enlarge the portion of labeled data (see section [2] for details and references), we closely follow the implementation by Yarowsky [33]; here, "axis" means traditional axis-aligned trees; 4) Laplacian SVM is a seminal work by Belkin et al. [2) which has similar prob- lem formulation as in eq. ① but for SVM. Additionally, the suppl. mat. include the comparison with semi-supervised classification trees by Levatić et al. (233 and EBBS by Chen et al. [12). Regarding hyperparameters, given the fixed cross- valsdaaaiittion set (1% of train data), we explored as best as we could all important hyperparameters for all methods (see details in the suppl. mat.). These include: controlling tree depth (A), confidence threshold for self-training, a and C values for LapS etc. It worth to mention that the hyperparameter settings suggested by authors or their default values work best in most cases.
We use TAO to train oblique trees and CART to train axis-aligned trees. For all methods that use TAO, we set the total number of TAO iterations 15. The depth A as well as the regularization parameter a are tuned via cross-validation. As for the settings that are specific to LapTAO,, we proceed as follows. To construct the graph Laplacian, we use the Gaussian affinities with k-nearest neighbors and perplexity parameter I. tuned for each dataset. The linear system in the label-step solved either using direct methods (less than 20k dimensions) or Conjugate Gradient method for large scale problems. We use 7 0.1 in all experiments. As for the main loop of the augmented Lagrangian, we iterate 20 times starting from small value for foo = 0.001 multiplied by 1.5 after each iteration. The remaining details as well as dataset descriptions can be found in the suppl. mat.
4.2 Main results
Fig. 2 summarizes the main results which are the trade-off plots of test error versus the percentage of labeled data on two regression and classification tasks. Intuitively, the error should go down monotonically as we increase the amount of supervision which is clearly the case in all figures. According to our findings, KNN and "axis- self" show the worst results in almost all benchmarks. The only case when KNN performed reasonably good was on MNIST, which is known to work well with "template classifiers" (e.g. RBF network, kernel SVM. KNN, etc.). Even in that case it has a large error gap with respect to LapTAO. The poor performance of the "axis-self" can be explained by suboptimality of greedily grown trees [19] and suboptimality of the self-training approach, which is mostly based on heuristics. Next, oblique trees trained on supervised data only ("oblique-IbI")
7

---

Regression
Classification
cpu act 28,,
year 1ea__pred(0.5M,900.1
mnist(70k,784,1))
Susy(IM,18.2)
ablique
LapTAAOouns)
E Eiss(MEB (MSE)
oblique-seif
30
35
aaxis self
obliqe-lll Ibl
(%)
E (
28
30
KNN-Ibl
15
10
10
20
10
20
0.2 0.6 1.6
3 5 10
0.07
0.1
03 0.5 0.8
% of labeled data
% of labeled data
% of labeled data
% of labeled data
Figure 2: Results on regression [year_pred, epu_act) and classiiication(mmiss,, susy) tasks. Numbers in brackets report the training size, number of features and output dimension (or number of classes). x-axis shows the percentage of labeled data provided to the algorithm and andy-am y-axis shows the test error. Baselines: oblique-all fully supervised baseline (i.e., trains an oblique tree on 100% of labeled data); *-lbl uses D, only train the corresponding model; *-self is an iterative self-training approach (see section 2 and
leads to the significant drop in accuracy (magenta vs black lines). This shows that relying only on labeled data is not enough to achieve a decent performance. Incorporating oblique tree into self- training framework brings certain benefits ("oblique-self"), notably for classification tasks (green dashed vs solid lines). Finally, LapTAO consistently improves over all other SSL methods, often by considerable margin. For instance, in case of 3% in cpu act and 1 1% in MNIST, the difference the error with the second best SSL approach is several orders of magnitude. It shows acceptable results even in extreme label scarcity scenarios, c.g. when we provide < 0.5% of labeled data on year pred quickly: for MNIST,
and susy. Moreover, LapTAA approaches the fully supervised baseline we can achieve the same ~ 5% test error as "oblique-all all" using only 20% of labeled training points.
Comparison with Laplacian SVM LapSVM is a natu- ral baseline to compare with since it uses the same prob- lem formulation as in eq. ① but for the support vector machines. However, we were not able to include it to the previous comparison (in fig. 22 due to implementation is- sues: 1) it is impractical 30k instances as it requires computing the inverse of the modified dense Gram matrix on the entire dataset 2) can handle classification task only. Therefore, we pick the subset of Rashion-MNISS (3 classes: "shirt", "bag" and "ankle boot")) resulting in 18k training points. To make the comparison as fair as possible, both of the al- gorithms use the same graph Laplacian matrix and we en- force the same penalty on (? 0.1). For LapSVM, we use the rbf kernel with 5 and the hyperparameter for LIBSVM [1]
LapTAO LapSVM
apply it for problems beyond
(%)
2-
0.6 0.8 1
5
10
20 100
% of labeled data
Figure 3: Comparison against LapSVM on Fashion-MNIST (3 classes: "shirt", "bag" and "ankle boot").
is set to C = 100.
The results are illustrated in fig. 3 It is worth to mention that similar the original MNIST. "template classifiers", such as kernel SVM, show quite good performance on this task which makes LapSVM a strong baseline [32]. On top of that, the problem formulation in eq. ① is still convex for SVM and can be efficiently solved, whereas we are dealing with much harder problem for oblique trees. Therefore, it is nice to see that LapTAAO performs similarly (but slightly worse) up to some point. However, it is surprising to see that the error gap between our approach and LapSVM narrows as we introduce more label scarcity and eventually we start to outperform when % of labeled data 3%. From that point on, the table turns to the side of LapTAO and the difference becomes more and more noticeable (especially for 0.6%). One possible explanation for this behavior is the overfitting issue on small datasets, which
'One could approximate the inverse by Nyström (or other) method but this beyond the scope of this paper.

---

Table 1: Training runtime for different semi-supervised learning algorithms (in seconds).
Dataset Method
LapTAO
oblique-sel self
axis-self
SSCT
eput_act
1072s 11027s
934s
238
936s
mnist susy
9572s
514s
15932s
24578s
17873s
816s
>Id
known problem for kernel SVM, whereas sparse oblique trees are shown to be relatively robust to that (8).
Training time Table I reports the training time for different baseline methods. Overall, LapTAO algorithm for the largest experiment we performed (on susy) took less than 7 hours and around hours for the moderate dataset size (mnist). This is comparable to the self-training baseline (i.e., oblique-self) but Lap produces far better trees in terms of accuracy. Please note that we ran code regular PC (Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz, 32GB RAM), with little parallel processing and using unoptimized Python implementation. Therefore, the training runtime for LapTAO can be significantly improved. We did not use any GPUs.
4.3 Model interpretability
Model explainability and interprctability is a topic of renewed interest due to the widespread usage of machine learning and the risks associated with privacy, algorithmic bias, etc. In order to trust and rely on such automated systems, it crucial to understand how they achieve a certain prediction. In contrast to "black box" models, decision trees are long considered as interpretable models due to the hierarchical structure. This allows to transform the model prediction as "if-then" rules extracted from root-to- leaf path. Specifically for oblique trees, each logical clause takes the following form: go to left child if w x < wo. else go to right. This makes the interpretation a little harder since we need look linear combination of features at each split. However, in case, add & penalty which encourages parameter vector at each node to be sparse, i.e., only few features participate in decision making.
In this section, we argue that the oblique trees trained using LapTAO strike a good trade-off between accuracy and interpretabiliity which is controlled via hyperparameter the same subset of Fashion-MNIS: as in section [42] and train a sparse oblique tree using LapTAA (10% of training data are labeled). By decreasing the value of a enforce more sparsity resulting into shallower and more interpretable trees (since complexity decreases). However, we sacrifice the performance since the error goes up.
To illustrate this, we use
Fig. 4 shows the results for a and a = 10, more results can be found the suppl. mat. For simplicity, let us focus on the bottom tree (a 10). Clearly, each leaf contains instances of nearly the same class since the average image looks like a representative "template" from the corresponding class. As for the decision node, consider the root (node #1). All "Boot" images sent to the right child of the root. Also, it easy to notice that such images do not contain any pixels in the top-left quadrant of the image. Therefore, the weight vector at the root has negative (blue) values in the corresponding elements and we know that negative values are responsible for sending an instance to sent to the left.
the left. In other words, all images that have something in the top-left quadrant Therefore, boots will end up in the right child. Similarly, node #2 sends most of the images that have M-shaped stroke in the top-center part (e.g. large bags, shirts with collar) the left child. Following the same logic, we can obtain meaningful insights for each decision node. Also note that all nodes have majority of values equal to zero (thanks to the sparsity) which makes the interpretation easier.
5 Conclusion
semi-supervised learning is most commonly formulated with a graph-based regularization term, which encourages the labels of nearby (similar) points to be similar. This has been very successful with models such as neural nets and kernel machines, but until now it remained an open problem with decision trees, which define a nondifferentiable function. We have shown how to reformulate the problem in a way that is amenable to iterative optimization. By introducing auxiliary variables, we isolate the difficult part (the tree optimization). and all the algorithm needs to do to fit a regression tree in alternation with solving sparse linear system that smoothes the predicted labels. The tree

---

19191
(325)
(197))
(000))
teg 2011
(5844)
Abic
Figure 4:
Some the oblique trees obtained from LapTAO on Fashion-MNIST. Both figures use 10% of labeled data, but they differ in regularization penalty (a) on the tree: (top) a with Evst = 2.1% and (bottom) a = 10 with Exst = 3.9%. At each decision node, we illustrate the weight vector of dimension 784 reshaped into 28 28 square where each value colored according to their sign and magnitude (positive, negative and zero values are blue, red, and white, respectively). At each leaf, we show the class label, the total number of training points in that leaf (in brackets), and the average of input images in that leaf (as a greyscale image).
fitting can be done reliably and efficiently using the Tree Alternating Optimizing (TAO) algorithm, which also allows results demonstrate that the algorithm can train accurate and interpretable decision trees even in extreme label scarcity situations. Our framework can be generalized other machine learning models, such as ensembles of trees, which will be the future direction of our work.
more powerful trees, such sparse oblique trees. Our experimental
Acknowledgments and Disclosure of Funding
Work partially supported by NSF awards IIS-1423515 and IIS- LIS-2007 147.
10

---

References
[1] A. Andoni and P. Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Comm. ACM, 51(1):117-122, Jan. 2008.
[2] M. Belkin, P. Niyogi, and V. Sindhwani. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. Machine Learning Research, 7:2399-2434, Nov. 2006.
[3] L. Breiman. Random forests. Machine Learning, 45(1):5-32, Oct. 2001.
[4] L. J. Breiman, J. H. Friedman, R. A. Olshen, and J. Stone. Classification and Regression Trees. Wadsworth, Belmont, Calif., 1984.
[5] M. Á. Carreira-Perpinaal The Tree Alternating Optimization (TAO) algorithm: A new way to learn decision trees and tree-based models. arXiv, 2022.
[6] M. A. Carreira-Perpiñal and P. Tavallali. Alternttngg optimization of decision trees, with appli- cation to learning sparse oblique trees. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances Neural Information Processing Systems (NEURIPS), volume 31, pages 1211-1221 MIT Press, Cambridge, MA, 2018.
[7] M. Á. Carreira- Pereira-errpinnn and M. Vladymyrov. fast, universal algorithm to learn parametric nonlinear embeddings. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems (NIPS), volume 28, pages 253-
261. MIT Press, Cambridge, MA, 2015.
[8] M. Á. Parreira-Perpinán and W. Wang. Distributed optimization of deeply nested systems. ar arXiv:1212..999 Dec. 24 2012.
[9] M. Á. Carreira- and W. Wang. Distributed optimization of deeply nested systems. In Kaski and Corander, editors, Proc. of the 17th Int. Conf. Artificial Intelligence and Statistics (AISTATS 2014), pages 10-19, Reykjavik, Iceland, Apr. 22-25 2014.
[10] M. Á. Carreira-Perpine and A. Zharmagambetov. Ensembles of bagged TAO trees consis- tently improve over random forests, AdaBoost and gradient boosting. In Proc. of the 2020 ACM-IMS Foundations of Data Science Conference (FODS 2020), pages 35 46, Seattle, WA, Oct. 19-20 2020.
[11] C.-C. Chang and C.-J. Lin. LIBSVM: A library for support vector machines. ACM Trans. Intelligent Systems and Technology, 2(3):27, Apr. 2011.
[12] J. Chen, J. Muelerr, V. N. loannidis, S. Adeshina, Y. Wang. T. Goldstein, and D. Wipf. Does your graph need confidence boost? convergent boosted smoothing graphs with tabular node features. In K. Chaudhuri, S. Jegelka, L. Song, C. Szepesvari, G. Niu, and S. Sabato, editors, Proc. of the 39th Inf. Conf. Machine Learning (ICMI, 2022), Baltimore, JDly 17- 23 2022.
[13] A. Criminisi J. Shotton. Decision Forests for Computer Vision and Medical Image Analysis. Advances in Computer Vision and Pattern Recognition. Springer-Verlag. 2013.
[14] R.-E. Fan, K.-W. Chang, C.-J. Hsieh, X.R.. Wang, and C.-J. Lin. LIBLINEAR: A library for large linear classification. J. Machine Learning Research, 9:1871-1874, Aug. 2008
[15] J. H. Friedman. Greedy function approximation: A gradient boosting machine. Annals of Statistics, ((55):189-1220) 2001.
[16] M. Gabidolla and M. Á. Carreira-Perpinan. Pushing the envelope of gradient boosting forests via globally oblique trees. In Proc. of the 2022 IEEE Computer Society Conf. Com- puter Vision and Pattern Recognition (CVPR'22), New Orleans, LA, June 19-24 2022.
[17] M. Gabidolla and M. Á. Carreira- Periia--Prrpnnn.. Optimal interpretable clustering using oblique decision trees. Proc. of the 28th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining (SIGKDD 2022), pages 400-410, Washington, DC, Aug. 14-18 2022.

---

[18] S. S. Hada, M. Á. Carreira-Perpiñáne and A. Zharmagambetov. Sparse oblique decision trees: tool understand and manipulate neural net features. Data Mining and Knowledge Discov- ery, 2022. To appear.
[19] J. Hastie, R. J. Tibshirani, and J. H. Friedman. The Elements of Statistical Learnin- Data Mining, Inference and Prediction. Springer Series in Statistics. Springer- Verlag, second edition, 2009.
[20] L. Hyafil and R. L. Rivest. Constructing optimal binary decision trees is NP-complete. Infor- mation Processing Letters, 5(1):15-17, May 1976.
[21] S. Ivanov and L. Prokhorenkova. Boost then convolve: Gradient boosting meets graph neu- ral networks. In Proc. of the 9th Int. Conf. Learning Representations (ICLR 2021), Online, Apr. 25-29 2021.
[22] C. Kemp, I. L. Griffiths, S. Stromsten, and J. B. Tenenbaum. Semi-supervised learning with trees. In Thrun et al. [28]. pages 257-264.
[23] J. Levatić, M. Ceci, D. Kocev, and S. Džeroski. Semi-supervised classification trees. J. Intelli- gent Information Systems, 49:461-486, 2017.
[24] K. Murthy, S. Kasif, S. Salzberg, and R. Beigel. OC1: A randomized algorithm for building oblique decision trees. In Proc. of the 11th AAAI Conference Artificial Intelligence (AAAI 1993), pages 322-327, Washington, DC, July 11-15 1993.
[25] J. Nocedal and S. J. Wright. Numerical Optimization. Springer Series in Operations Research and Financial Engineering. Springer- Verlag, New York, second edition, 2006.
[26] J. R. Quinlan. C4.5: Programs for Machine Learning. Morgan Kaufmann, 1993.
[27] Tanha, M. van Someren, and H. Afsarmanesh. Semi-supervised self-training for decision tree classifiers. Int. J. Machine Learning and Cybernetics, 8:355-370, 2017.
[28] S. Thrun, L. K. Saul, and B. Schölkopf, editors. Advances in Neural Information Processing Systems (NIPS), volume 16, 2004. MIT Press, Cambridge, MA.
[29] J. E. van Engelen and H. H. Hoos. A survey on semi supervisd learning. Machine Learning, 109:373 2020.
[30] A. Verikas, A. Gelzinis, and M. Bacauskiene. Mining data with random forests: A survey and results of new tests. Pattern Recognition, 44(2)330-334,,201
[31] J. Weston, F. Ratle, and R. Collobert. Deep learning via semi-supervised embedding. In A. McCallum and S. Roweis, editors, Proc. the 25th Int. Conf. Machine Learning (ICML (08), pages 1168-11 1175.115. Helsinki, Finland, July 5-9 2008
[32] H. Xiao, K. Rasul, and R. Vollgraf. MASSI: novel image dataset for benchmarking machine learning algorithms. arXiv:1708.0774477 Sept. 15 2017.
[33] D. Yarowsky. Unsupervised word sense disambiguation rivaling supervised methods. In Proc. 33rd Annual Meeting of the Association for Computational Linguisties (ACI. 1995), pages 189- 196, 1995.
[34] A. Zharmagambetov and M. Á. Carreira-Perpiñánn Smaller, more accurate regression forests using tree alternating optimization. In H. Daumé III and A. Singh, editors, Proc. of the 37th Int. Conf. Machine Learning (ICMI. 2020), pages 11398-11408, Online, July 13-18 2020.
[35] A. Zharmagambetov and M. Á. Carreira-Perpinan. Learning tree of neural nets. In Proc. of the IEEE Int. Conf. Acoustics, Speech and Sig. Proc. (ICASSP'21). pages 3140-3144, Toronto, Canada, June 6-11 2021.
[36] A. Zharmagambetov and M. Á. Carreira-Perpinaar Learning interpretable, tree-based projec- tion mappings for nonlinear embeddings. In Proc. of the 25th Ini. Conf. Artificial Intelligence and Statistics (AISTATS 2022), pages 9550-9570, Online, Mar. 28-30 2022.
12

---

[37] A. Zharmagambetov, M. Gabidolla, and M. Á. Carreira-Perpiñäae Softmax tree: An accurate, fast classifier when the number of classes is large. In M.-F. Moens, X. Huang, L. Specia, and S. W.-t. Yih, editors, Proc. Conf. Empirical Methods in Natural Language Processing (EMNLP 202 ), pages 10730-10745, Online, 2021.
[38] A. Zharmagambetov, S. S. Hada, M. Gabidolla, and M. Á. Carreira-Perpiñánn Non-greedy algorithms for decision tree optimization: An experimental comparison. In Int. J. Conf. Neural Networks (IJCNN'2/) /), Virtual event, July 18-22 2021.
[39] D. Zhou, O. Bousquet, T. N. L. Weston, and B. Schölkopf. Learning with local and global consistency. Thrun et al. [28). pages 321-328.
[40] X. Zhu. Semi-supervised learning literature survey. Technical Report TR-1530, Dept. of Computer Science, University of Wisconsin-Madison July 19 2008
[41] X. Zhu and Z. Ghahramani. Learning from labeled and unlabeled data with label propaga- tion. Technical Report CMU-CALD-022 -2-1--0--10, School of Computer Science, Carnegie-Mellon University, June 2002.
[42] X. Zhu, Z. Ghahramani, and Lafferty. Semi-supervised learning using Gaussian fields and harmonic functions. In T. Fawcett and N. Mishra, editors, Proc. of the 20th Int. Conf. Machine Learning (ICML 03), pages 912-919, Washington, DC, Aug. 21-24 2003.

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See section
(c) Did you discuss any potential negative societal impacts of your work? [No] Our work on optimization and efficiently training of machine learning models. We anticipate no impact beyond that of the models themselves.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] see section and the suppl. mat.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [No]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Section and in the suppl. mat.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [No]
(c) Did you include any assets either in the supplemental material or URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you'l re using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "l9WTFGknNYF", "reviewer": "Reviewer_dfEo", "summary": "This paper introduces a bi-level optimization method for semi-supervised learning tasks, which iteratively solves a supervised tree learning problem and label smoothing problem. The experimental results demonstrate that LapTAO can achieve accurate and interpretable in label scarcity situations.", "questions": "1. Can author provide more details about Graph Laplacian matrix construction? The paper only mentioned Gaussian affinities with k-nearest neighbors, it clusters all available feature vectors?", "limitations": "no potential negative societal impact ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths:\nThe paper is well-written and easy to follow, the reformulation part is well-organized. Some model interpretability are provided, making the model more trustful.\n\n\n## Weakness:\n 1. The framework is not novel to me, [1] also introduces a bi-level optimization method, incorporating label smoothing into decision tree. The author may conduct more literature reviews and comparison with existing methods although [1] and [2] are from Graph Neural Networks (GNNs) community. But most node classification problems in GNNs are semi-supervised learning problem. The paper may have broader impact if the author consider more tasks or datasets from [1] and [2].  \n\n2. About model complexity or training time, the author should provide more comparison with other baselines (especially for strong baseline **oblique–self**, the performance is close to LapTAO in Figure 2 ). The author roughly described the complexity and rarely mentioned other baseline's training time. \n\n3. About experimental results, Figure 2 may not be compelling for me, since only LapTAO introduces graph Laplacian matrix and other baselines don't consider graph structure. The gap between LapTAO and other competitors is probably caused by introducing graph information. LapTAO and LapSVM is a fair comparison for me since both methods start from graph Laplacian matrix and the gap between these two methods is narrowed compared with Figure 2. The author may need to carefully conduct a fair baseline comparison or justify why there is a gap between LapTAO with other baselines in Figure 2. \n\n[1]. https://openreview.net/forum?id=nHpzE7DqAnG\n\n[2]. https://openreview.net/pdf?id=ebS5NUfoMKL\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Zt6D9XSpTum", "reviewer": "Reviewer_bXo9", "summary": "This paper studies the semi-supervised decision tree learning problem. By introducing additional variables $z$, the original problem can be reformulated and solved iteratively as two simpler problems: a label smoothing problem, which can be solved through a sparse linear system, and a supervised tree learning problem, which was solved by the Tree Alternating Optimization algorithm in this paper. The numerical experiments demonstrate that the proposed method in this paper is able to achieve high testing accuracy and good interpretability.", "questions": "1. Since TAO method in \"tree-step\" requires solving the logistic regression on the whole training set over all branch nodes for multiple iterations, for large dataset it can be very time consuming. For that reason, I do not expect the LapTAO algorithm can be run for too many iterations within a particular time limit. My question is, have the authors tried to use other more efficient algorithms (can be greedy) to fit the tree? \n2. Computation time should also be reported in the experiment section. ", "limitations": "1. The main LapTAO algorithm has no theoretical analysis. \n2. The selection of benchmark methods in the experiment part is not representative and seems very random. For example, the authors do not have to compare with KNN or any other axis-parallel decision tree, instead, the authors should focus on comparing the performance of LapTAO with the application of other semi-supervised learning algorithm on decision tree (e.g., SSCT in the supplementary materials). Similarly, the authors can implement experiments on the extension of LapTAO to other models, and compare with the successful semi-supervised learning algorithms of those models. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \n1. This paper studies semi-supervised version of decision tree learning problem, which has not been well-studied so far. \n2. The algorithm LapTAO introduced in this paper can be easily extended to classification and multioutput regression problems, and can even be extended to other models with little modification. \n\nWeakness:\n1. The main algorithm LapTAO is essentially applying ADMM with coordinate descent to the original problem (1). \n2. The choice of using TAO method for \"Tree-step\" does not quite make sense to me, this seems arbitrary and the reason is not fully justified. There are many other efficient algorithms for training optimal decision tree, with or without regularization term. \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "SG2RJ6199SM", "reviewer": "Reviewer_e5V7", "summary": "Many real-world machine learning applications encounter both labeled and unlabeled data. \nIn such problems there may be a scarcity of high-quality labeled data, while large amounts of unlabeled or partially labeled data are available. \nSemi-supervised learning (SSL) involves the task of training machine learning models on such datasets to obtain more accurate predictions than models trained on labeled data alone. \nGraph-based methods for regularization have been demonstrated to provide efficient methods for  SSL problems, including the popular Laplacian regularized least squares and Laplacian support vector machines (LapSVM).\nHowever, extending graph-based regularization to the problem of training trees in SSL tasks has received comparatively less attention. \n\nThis paper proposes an algorithm for training decision trees in SSL problems. The proposed approach combines ideas from manifold regularization, sparse regularization, and tree optimization to obtain a sample efficient algorithm for training sparse decision trees. \nThe algorithm alternates between a \"label-step'' and a \"tree-step'' until a stopping criterion such as maximum number of iterations or convergence is satisfied. \nIn the label-step the augmented Lagrangian method is applied, yielding an unconstrained optimization problem whose solution yields an updated approximation of the labels based on the current (fixed) tree.\nIn the tree-step, tree alternating optimization (TAO) is applied to update the parameters of the decision tree to fit the current estimates of the labels. \n\nThe authors apply the resulting LapTAO (for Laplacian TAO) algorithm to the training of oblique decision trees in a variety of tasks. The results show that oblique trees trained with LapTAO obtain smaller MSE on the test set and testing error compared to a variety of alternative approaches for training axis-aligned and oblique trees in SSL, as well as KNN on the labeled data alone. The authors also demonstrate LapTAO yields similar performance to LapSVM on the Fashion-MNIST problem given greater than 3% of training data, while outperforming that method by considerable margin when trained with less than 3% labeled data. Finally, the authors display a visualization of the sparse parameter vectors obtained by the algorithm in the Fashion-MNIST case to demonstrate the interpretability of the resulting oblique decision tree.\n", "questions": "Line 330: in the description of Figure 4 it says \"$\\alpha = 1$ and $\\alpha=0.1$'', should the second value be $\\alpha=10$? Same also on line 331, see the caption of Figure 4.\n\nSupplemental material, line 13: Should it say \"$\\mathbf{L}$ is positive\" instead of \"$\\mathbf{J}$ is positive''?\n\nWhy was only 1 iteration used in most of the experiments, as described in the caption of the pseudocode in Figure 1 of the supplemental material? Were other values tried?\n\n", "limitations": "The authors addressed the limitations and potential negative societal impact of the work. ", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written, and the proposed approach is interesting and novel. The derivations are simple and straightforward, and the presentation and length of the paper are good. In particular, Section 3 of the paper is easy to follow and the authors provide ample discussion on initialization, extension of LapTAO to classification and multioutput regression problems, and extension of the general proposed alternating approach to other models such as neural networks. The experiments also provide many comparisons to other approaches, demonstrating the LapTAO algorithm achieves higher accuracy over other approaches for SSL, with a focus on tree-based methods in particular but also including LapSVM, on a variety of tasks. SSL is an important problem relevant to many application areas and decision trees are also an important direction of active research. \n\nHowever, the paper lacks somewhat in the depth of the experimental validation of the claims of the improved performance over other approaches for SSL and in discussion of computational complexity of the approach in large scale machine learning tasks. The experiment results presented are for the MNIST, susy, cpuact, year\\_pred, and fashion-MNIST datasets. As the authors describe, the largest experiment was conducted on a CPU and took less than 24 hours. It would be interesting to see how the LapTAO method performs on some larger scale benchmark prediction tasks where GPUs are necessary, in particular with regard to the computational complexity relative to other popular approaches. It would also be interesting to see further comparisons on the proposed regularization approach with different types of trees, for example using this formulation with axis-aligned trees and CART.\n\nSection 4.3 on model interpretability displays visualizations of the weights of the nodes of some oblique trees trained with LapTAO on the Fashion-MNIST dataset. While sometimes it appears clear from the displayed weights why the model takes one branch over another (e.g. in the case of the boot from node 1 of the $\\alpha=10$ case of Figure 4), other times it is not so clear. It would be interesting to see a comparison with models trained without the $\\ell_1$ term, i.e. $\\alpha = 0$. Overall, the discussion on model interpretability and sparsity could be improved. \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "MAGrmfww_C7", "reviewer": "Reviewer_sdWW", "summary": "This work proposes an approach to do semi-supervised learning with decision trees. Their approach splits the objective function into a sparse linear system and a decision tree optimization part. They use alternating optimizations to learn the parameters and minimize the objective function. The linear part is solved analytically. An approximate solution for the tree optimization is obtained using a previously developed TAO method. The authors demonstrate the effectiveness of their method for the SSL tasks on different regression/classification tasks and also analyze the interpretability of their model. ", "questions": "Questions & Suggestions\n1. In the Fig. 1 example, can you also provide any statistical guarantees? For instance, running with different number of parameters, different initializations, tree sizes etc. for LapTAO and other methods. I suspect that with the choice of labels for this 2D data, the classifier can easily choose any of the decision boundaries in the right 2 plots. I will definitely appreciate adding the statistical significance along with the error percentages. \n2. Theoretical guarantees: Any ideas of deriving the convergence rate for the alternating optimization? I understand that the tree optimization is NP-Hard but having a probabilistic error term will be very helpful to understand the limitations of this approach. \n\nThis is a good direction to explore further. I would like to know the authors views on the above points and their approach to handling them. \n", "limitations": "I request the authors to show results which highlight the limitations of their model. It will be great to get an idea of the size and types of data for which one can opt their method over other SOTA. ", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n1. A well thought off application of the Alternating Optimization technique. Since, the TAO algorithm cannot directly optimize the Eq.(1), the reformulation is a neat way of circumventing this problem. [Lines 158-159]\n2. The paper is well motivated. The approach is reasonable and the math works out. \n\nSome improvements:\n1. Results on larger datasets: Will be interesting to see the results on larger image datasets. I am curious on how the affinity matrix will be designed. Will you take a subset of images which is defined by a batch size? In that case the affinity matrix will need to be recalculated and then the algorithm will be slower. Please share your thoughts and maybe some best practices that you recommend. \n2. Comparison with deep learning based approaches: I understand that interpretability is also one aspect to compare. Visualizing the CNN filters for instance in Fig. 4. Also, I would like to see a comparison with SOTA DL methods, that will give the readers an idea about the limitations. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept