PaperlayerView exact revision on arXiv

Source-linked AI summary

Neural Decision Trees

Randall Balestriero

arXiv:1702.07360v2stat.MLcs.LG

TL;DR

Decision trees partition inputs through splits, while neural models can learn more flexible boundaries; the paper combines these approaches in neural decision trees and hashing neural networks. Its toy classification examples report similar decision boundaries with fewer HNN parameters than an ANN, and the paper concludes that HNNs can represent unions of regions.

  • Problem

    Standard decision trees use axis-aligned or linear splits, while the paper seeks a differentiable framework for learning arbitrary decision boundaries with global optimization.

    Source: B. Univariate and Oblique Decision Trees · p. 2

  • Method

    The paper uses neural decision trees with learned sigmoid split probabilities and derives a hashing neural network from weight-shared units.

    Source: §II · p. 2, B. Model · p. 3

  • Results

    In the toy examples, similar decision boundaries required 13 parameters for the ANN and 9 for the HNN.

    Source: D. Toy Dataset · pp. 6–7

  • Takeaways & Limitations

    The authors conclude that representing unions of regions for classification or clustering reduces the need to fully linearize data and may reduce the required depth of deep architectures.

    Source: §V · p. 10

Abstract

from arXiv · show

In this paper we propose a synergistic melting of neural networks and decision trees (DT) we call neural decision trees (NDT). NDT is an architecture a la decision tree where each splitting node is an independent multilayer perceptron allowing oblique decision functions or arbritrary nonlinear decision function if more than one layer is used. This way, each MLP can be seen as a node of the tree. We then show that with the weight sharing asumption among those units, we end up with a Hashing Neural Network (HNN) which is a multilayer perceptron with sigmoid activation function for the last layer as opposed to the standard softmax. The output units then jointly represent the probability to be in a particular region. The proposed framework allows for global optimization as opposed to greedy in DT and differentiability w.r.t. all parameters and the input, allowing easy integration in any learnable pipeline, for example after CNNs for computer vision tasks. We also demonstrate the modeling power of HNN allowing to learn union of disjoint regions for final clustering or classification making it more general and powerful than standard softmax MLP requiring linear separability thus reducing the need on the inner layer to perform complex data transformations. We finally show experiments for supervised, semi-suppervised and unsupervised tasks and compare results with standard DTs and MLPs.

I. INTRODUCTION AND DECISION TREE REVIEW

Decision trees partition input space into regions whose number grows exponentially with tree depth, while standard univariate trees use sequential, axis-aligned tests. The paper motivates combining this partitioning with neural networks to learn more flexible decision boundaries through global optimization.

A. Motivations

  • Tree depth yields an exponentially growing number of input regions, supporting the use of tree partitions for complex discrimination.Source: A. Motivations · p. 1

B. Univariate and Oblique Decision Trees

II. NEURAL DECISION TREES

The paper introduces neural decision trees as softened trees whose splitting nodes can learn arbitrary decision surfaces. Their probabilistic splits connect the tree framework to locality-sensitive hashing, where a tree’s hash value is its reached leaf.

II. NEURAL DECISION TREES

  • A neural decision tree replaces hard splits with learned, differentiable decision surfaces and supports global optimization.Source: §II · p. 2

A. Locality Sensitive Hashing

B. Model

  • The model replaces an indicator split with a sigmoid whose output is interpreted as the probability that an input goes to a node’s left child.Source: B. Model · p. 2
  • Applying a general data transformation, such as an ANN, before the sigmoid permits arbitrary learned split functions.Source: B. Model · p. 3

C. Local and Global Loss

The local and global loss formulations adapt familiar tree split criteria to probabilistic routing. Global training weights leaf losses by the probability of reaching each leaf, allowing simultaneous optimization of all splits.

C. Local and Global Loss

  • Information gain selects splits that minimize the weighted sum of child entropies, favoring regions with concentrated class distributions.Source: C. Local and Global Loss · p. 3
  • Gini impurity is minimized at zero when each region contains only one class, and the node loss weights the impurity of its children.Source: C. Local and Global Loss · p. 3
  • For regression, variance reduction seeks splits that minimize within-region variance and can be weighted by each region’s probability.Source: C. Local and Global Loss · p. 3
  • Global training weights each leaf’s loss by its probability of being reached and optimizes all splitting nodes simultaneously.Source: C. Local and Global Loss · p. 4
  • The authors argue global optimization may be less prone to local optima because a nonoptimal split need not degrade all child performances.Source: C. Local and Global Loss · p. 4

A. Motivation

The paper recasts decision-tree paths as neural hashing outputs, allowing learned regions to support classification and regression. Its supervised loss aggregates uncertainty across regions, and the hashing layer can follow other neural layers.

A. Motivation

  • HNN generalizes neural decision trees by learning regions with low class uncertainty, allowing multiple regions per class and supervised, semi-supervised, or unsupervised learning.In the linear special case, the NDT is a sigmoid-output perceptron whose output chain corresponds to a tree path.Source: A. Motivation · p. 4

B. The Hashing Layer

  • The hashing layer outputs region-membership probabilities rather than class probabilities, with its neurons jointly encoding the path taken through a decision tree.A prediction policy can use the classes most represented in a region, and ambiguous regions can support different prediction choices.Source: B. The Hashing Layer · p. 4
  • At least log2(C) output neurons are required for C classes, while additional neurons allow different sub-regions to represent the same class.The passage motivates this flexibility for latent representations with more clusters than classes, including same-class clusters that are not neighbors.Source: 1) Supervised Case · p. 4

1) Supervised Case:

  • For supervised classification, the method assigns each chain a class distribution and minimizes a reach-probability-weighted sum of differentiable region uncertainties.The per-chain class distribution is a weighted mean of one-hot labels; classification losses can also use class weights for imbalanced data.Source: 1) Supervised Case · p. 5
  • For regression, the method defines local output variance and rewrites the overall loss using these local losses.The local losses need not be weighted by the probability of reaching each region.Source: 1) Supervised Case · p. 5
  • The hashing layer can follow dense, convolutional, or recurrent layers, so training can operate on learned representations through back-propagation.The passage cites Gardner and Dorling (1998), Krizhevsky et al. (2012), and Gers et al. (2000) for these layer types.Source: 1) Supervised Case · p. 5

2) Semi-Supervised Learning:

The paper describes an undeveloped semi-supervised hybrid loss and derives an unsupervised hashing objective based on reducing within-region variance. Unsupervised hashing can also use random hyperplanes in a locality-sensitive hashing framework.

2) Semi-Supervised Learning:

  • The semi-supervised extension combines discriminative loss for labeled examples with an unsupervised loss for labeled and unlabeled examples, but is not developed in the paper.The passage describes validation results for this hybrid loss as future work.Source: 2) Semi-Supervised Learning · p. 5

3) Unsupervised Case:

  • The unsupervised framework couples a deep autoencoder with an unsupervised hashing layer and can minimize intra-region variance to form clusters.The variance-based approach is described as similar to k-NN; the semi-supervised framework instead applies reconstruction loss to all inputs and hashing loss when labels are available.Source: 3) Unsupervised Case · p. 5
  • A random strategy can draw hyperplanes from a normal distribution to follow the locality-sensitive hashing framework.The passage compares this unlearned strategy with Extremely Randomized Trees.Source: 3) Unsupervised Case · p. 5

C. Training

The training discussion focuses on gradient-based iterative optimization and derives gradients for the Gini-impurity loss. It describes how parameter updates and hashing-layer derivatives are computed, with stochastic gradient descent as an option for large datasets.

1) Iterative Optimization Schemes:

  • Gradient-based methods optimize free parameters iteratively, with updates controlled by a learning rate and a regularization term.The paper focuses on gradient methods rather than genetic algorithms and notes that cross-validation or adaptive methods can select learning rates and regularizers.Source: 1) Iterative Optimization Schemes · p. 6
  • The hashing-layer weight derivative has shape (#out, #in), with each row combining an input—possibly an upper-layer output—with an activation and an indicator that determines the sign.The derivation is for the case where the loss is Gini impurity.Source: 1) Iterative Optimization Schemes · p. 6
  • The derivative of a region probability with respect to one output sums products of the other output neurons, with the varied neuron determining the sign.The derivation holds the other neurons fixed while varying the neuron under consideration.Source: 1) Iterative Optimization Schemes · p. 6
  • Stochastic gradient descent is an option for large training sets and is reported to improve convergence rate..Source: 1) Iterative Optimization Schemes · p. 6

2) Regularization Techniques:

The section describes dropout and noise-based regularization alongside a regularizer on how data are distributed across regions. The latter can encourage regions to be more equally likely.

2) Regularization Techniques:

  • Dropout deactivates neurons probabilistically to discourage co-adaptation, while Gaussian noise on neuron outputs is described as a way to make weights robust to noise.The passage distinguishes these motivations from simply avoiding overfitting and notes that overfitting can be useful with ensemble averaging.Source: 2) Regularization Techniques · p. 6
  • A regularizer on the data distribution across regions can make the regions more equally likely.Source: 2) Regularization Techniques · p. 6

D. Toy Dataset

On two nonlinear toy classification datasets, HNN represents decision boundaries with a small union of linear planes. The examples report similar boundaries with fewer parameters than an ANN and describe HNN’s learned regions and training behavior on two moons.

D. Toy Dataset

  • 13 parameters for ANN versus 9 for HNN yield similar decision boundaries, with HNN requiring only one layer.The paper presents the parameter reduction as an example of avoiding an unnecessarily flexible model.Source: D. Toy Dataset · p. 7

1) Two-moon Dataset:

  • On the two-moon dataset, a one-layer HNN with #out = 3 learns a nonlinear decision boundary made of 3 combined hyper-plans, similar in shape to the boundary learned by a 2 : 3 : 1 MLP.Source: 1) Two-moon Dataset · p. 7
  • The HNN tracks probabilities for eight two-moon regions during training; initially sparse regions can become preponderant, while useful regions can be disregarded.The figures show learned and final classification regions, alongside the evolution of region probabilities.Source: 1) Two-moon Dataset · p. 7, Figure 5 · p. 7, Figure 4 · p. 7
  • 50 iterations for HNN versus around 150 for ANN are reported for convergence on the two-moon dataset.The training plots show HNN error and regularization statistics and ANN error statistics.Source: 1) Two-moon Dataset · p. 7

2) Two-circle Dataset:

On the two-circle task, the paper compares HNN with an ANN and reports faster HNN convergence. Its four-neuron HNN example uses fewer parameters than the ANN, while the paper contrasts their modeling-capacity growth.

2) Two-circle Dataset:

  • The two-circle task separates concentric circles of different radii; the paper notes that changing variables to (r, θ) makes it linearly separable.The paper presents HNN and ANN decision boundaries for the task.Source: 2) Two-circle Dataset · p. 7, Figure 10 · p. 8, Figure 13 · p. 8
  • About 20 iterations for HNN versus a bit more than 300 for the neural network are reported for convergence on the two-circle dataset.The paper presents training-error plots for the HNN and ANN; the HNN plot also includes regularization errors.Source: 2) Two-circle Dataset · p. 8, Figure 12 · p. 8, Figure 15 · p. 8
  • On the two-circle dataset, a four-neuron HNN has 12 parameters versus 13 for the ANN; matching its modeling ability with an MLP requires minimum topology 2:4:1, containing 17 parameters.Results for the four-neuron HNN are presented in Fig. 16, Fig. 17 and Fig. 18.Source: 2) Two-circle Dataset · pp. 8–9

IV. FUTURE WORK

Future work considers alternative losses, ensemble strategies, and model averaging, while the conclusion presents a differentiable tree–neural-network framework and its potential for clustering and classification with disjoint regions.

IV. FUTURE WORK

  • Future work proposes studying how loss functions affect trained networks across training sets and fixed topologies, including standard networks and HNNs with #out = log2(n).The authors suggest this could lead to learning the loss function online.Source: §IV · p. 9
  • The authors propose bagging or boosting only the HNN hashing layer, so ensemble members share a latent space while acting on different parts of it.They also mention model averaging as a Bayesian alternative for accounting for uncertainty in model choice.Source: §IV · p. 9
  • A proposed Bayesian model-averaging framework could use a nonparametric probabilistic graphical model, with p(x|ANN) based on reconstruction error and p(ANN) on complexity or topology.Source: §IV · p. 9
  • The authors identify low correlation between outputs for different inputs as important; otherwise, the corresponding hyperplanes are scaled versions of one another.Source: §IV · p. 9

V. CONCLUSION

  • The conclusion combines decision-tree region partitioning with neural networks’ ability to learn arbitrary boundaries, using a global loss to train nodes simultaneously and addressing poor local optima in decision trees.The framework’s differentiability also supports integration into machine-learning pipelines.Source: §V · p. 9
  • The authors state that arbitrary unions of regions support per-class clustering without fully linearizing the dataset and may reduce deep architectures’ required depth.They also describe information-theoretic optimality as requiring log2(C) neurons for supervised problems, versus C for usual softmax layers.Source: §V · p. 10
Loading 1702.07360v2…