Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: Many real-world machine learning applications encounter both labeled and unlabeled data. 
In such problems there may be a scarcity of high-quality labeled data, while large amounts of unlabeled or partially labeled data are available. 
Semi-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. 
Graph-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).
However, extending graph-based regularization to the problem of training trees in SSL tasks has received comparatively less attention. 

This 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. 
The algorithm alternates between a "label-step'' and a "tree-step'' until a stopping criterion such as maximum number of iterations or convergence is satisfied. 
In 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.
In 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. 

The 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.

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. 

However, 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.

Section 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. 


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.

Supplemental material, line 13: Should it say "$\mathbf{L}$ is positive" instead of "$\mathbf{J}$ is positive''?

Why 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?


limitations: The authors addressed the limitations and potential negative societal impact of the work.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strength: 
1. This paper studies semi-supervised version of decision tree learning problem, which has not been well-studied so far. 
2. 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. 

Weakness:
1. The main algorithm LapTAO is essentially applying ADMM with coordinate descent to the original problem (1). 
2. 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. 


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? 
2. Computation time should also be reported in the experiment section. 
limitations: 1. The main LapTAO algorithm has no theoretical analysis. 
2. 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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: ## Strengths:
The paper is well-written and easy to follow, the reformulation part is well-organized. Some model interpretability are provided, making the model more trustful.


## Weakness:
 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].  

2. 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. 

3. 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. 

[1]. https://openreview.net/forum?id=nHpzE7DqAnG

[2]. https://openreview.net/pdf?id=ebS5NUfoMKL


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
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 
strengths_and_weaknesses: Pros:
1. 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]
2. The paper is well motivated. The approach is reasonable and the math works out. 

Some improvements:
1. 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. 
2. 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. 

questions: Questions & Suggestions
1. 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. 
2. 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. 

This 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. 

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.
review_title: null

Meta-review: metareview: This paper extends graph-based semi-supervised learning to decision tree classifiers, where the optimization gets much more challenging.  The proposed solution reformulates the problem with a new auxiliary variable, which leads naturally to an iterative solution of alternating between 1) supervised learning on trees, and 2) label smoothing via a sparse linear systems.  High accuracy is favorable interpretability of the method are demonstrated in numerical experiments.   

All the reviewers, including myself, find the paper a solid contribution to the methodology and analysis. There are a few concerns such as computational complexity, and the rebuttal has done a good job addressing it (and other concerns).  These additional results and insights can be included in the final version of the paper.
confidence: Certain
Decision: Accept