Semi-Supervised Learning with Decision Trees: Graph Laplacian Tree Alternating Optimization

Arman Zharmagambetov, Miguel Á. Carreira-PerpiñánNeurIPS 2022 · OpenReview

TL;DR

LapTAO (Graph Laplacian Tree Alternating Optimization) is a novel framework that brings the power of graph-based semi-supervised learning (SSL) to decision trees. By decoupling the optimization into two alternating steps—label smoothing via a linear system and tree fitting via the TAO algorithm—LapTAO allows researchers to train accurate, interpretable models even when labeled data is extremely scarce.

The Challenge of Semi-Supervised Trees

Semi-supervised learning is essential when labeled data is expensive or difficult to obtain, but unlabeled data is abundant. The most successful SSL approaches use a graph prior (like the Graph Laplacian), which operates on the assumption that if two data points are similar in feature space, they should have similar labels.

While this graph-based approach works beautifully for differentiable models like neural networks or kernel machines, it has historically been inapplicable to decision trees. Decision trees are optimization nightmares: they are non-differentiable, non-convex, and define a discrete mapping. Consequently, most existing "SSL trees" rely on heuristics like self-training or modified splitting criteria, which often fail to minimize a global objective.

As shown below, a standard tree trained on just a few labeled points overfits wildly, whereas the LapTAO approach successfully recovers the underlying data distribution.

Comparison of decision boundaries on a synthetic 2D problem. LapTAO (right) recovers the ground truth much better than a tree trained only on labeled data (middle-right).

The LapTAO Method

To solve this, the authors propose a formulation that adds a Graph Laplacian regularization term to the standard supervised loss. They tackle the resulting complex optimization using the Method of Auxiliary Coordinates (MAC). This introduces a "proxy label" ($z_n$) for every single data point, whether initially labeled or unlabeled.

This clever reformulation breaks the hard problem into two simpler, alternating steps:

  1. The Label-step: This step solves a sparse linear system to perform "label diffusion." It spreads information from the few labeled points to the unlabeled ones, guided by the current tree's predictions.
  2. The Tree-step: This step fits a decision tree to the newly updated proxy labels. Crucially, the authors use the Tree Alternating Optimization (TAO) algorithm instead of traditional greedy algorithms like CART. TAO allows for "warm-starting" (improving the tree from the previous iteration) and can optimize specific loss functions over complex "oblique" trees (where splits are hyperplanes rather than just axis-aligned).

Key Insights

  • Decoupling is Key: By separating the "graph smoothing" from the "tree fitting," the authors bypass the non-differentiability of the tree. The graph logic stays in the linear system, and the tree logic stays in the TAO step.
  • Beyond Axis-Aligned Splits: The use of sparse oblique trees is a major advantage. These trees use a linear combination of a few features at each node, making them much more powerful than standard trees while remaining interpretable.
  • Efficiency and Scalability: Unlike many graph-based methods (like LapSVM) that require inverting large dense matrices, the Label-step in LapTAO involves a sparse linear system that can be solved efficiently with conjugate gradients.

Key Results

The authors evaluated LapTAO on several standard benchmarks across regression (cpu_act, year_pred) and classification (MNIST, SUSY, and Fashion-MNIST). They demonstrated impressive scalability, successfully running the algorithm on a dataset with 1 million instances on a standard consumer PC.

LapTAO consistently outperformed other SSL baselines, such as self-training and trees trained only on labeled data.

Test error vs. percentage of labeled data for various datasets. LapTAO (red line) consistently achieves lower error than baselines, especially in low-label regimes.
  • Accuracy: In many cases, LapTAO achieved a test error with only 1-3% of labeled data that other methods couldn't match even with significantly more supervision. For example, on MNIST, LapTAO reaches ~5% error using only a fraction of the labeled data required by a fully supervised tree.
  • Comparison to SVMs: LapTAO performs similarly to Laplacian SVMs on image datasets like Fashion-MNIST, but it scales much better to large datasets where the dense matrix operations of SVMs become computationally impractical.

Limitations and Future Work

  • Graph Construction: The method's success depends heavily on the quality of the initial affinity graph. Constructing this graph for very high-dimensional data remains a computational bottleneck.
  • Loss Functions: The current Label-step is optimized for squared loss. While this works for classification via one-hot encoding, exploring other losses (like hinge or logistic) directly in the Label-step could yield even better results.
  • Ensembles: While this paper focuses on standalone trees to preserve interpretability, the framework could naturally be extended to ensembles like Random Forests or Gradient Boosted Trees for even higher predictive performance.

Summary updated

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.
BibTeX
@inproceedings{zharmagambetov2022semi,
  author = {Arman Zharmagambetov and Miguel Á. Carreira-Perpiñán},
  title = {{Semi-Supervised Learning with Decision Trees: Graph Laplacian Tree Alternating Optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=uWujtTgaukO},
}
Figure