Leaf-Smoothed Hierarchical Softmax for Ordinal Prediction

Wesley Tansey, Karl Pichotta, James G. Scott

Introduction

Predicting discrete values with a natural ordering—known as ordinal labels—is a fundamental task in deep learning. From determining pixel intensities in image generation to modeling waveforms in audio synthesis, the ability to respect the underlying structure of the label space is crucial. Traditional approaches typically rely on either flat multinomial models (standard Softmax) or parametric mixture models (like Gaussian Mixture Models). However, both have significant drawbacks: multinomial models ignore label proximity, requiring vast amounts of data to learn smooth distributions, while mixture models are often too rigid to capture complex real-world data distributions, such as those with sharp boundary spikes.

The LSHS Architecture

To bridge the gap between flexibility and efficiency, researchers have introduced Leaf-Smoothed Hierarchical Softmax (LSHS). This method combines a tree-based probability structure with a graph-based smoothing regularizer.

The core of the architecture is a Dyadic Decomposition. Instead of a flat output layer, LSHS organizes labels into a balanced binary tree. Calculating the probability of a specific label involves traversing the path from the root to the leaf, reducing computational complexity to $O(\log n)$. This structure is particularly effective for high-dimensional labels, as it can alternate dimensions at different levels of the tree.

Hierarchical decomposition of ordinal labels showing potential tree bias at major splits.

However, hierarchical trees introduce a specific pathology known as "tree bias." As seen in the figure above, neighboring labels (like 3 and 4) may reside on opposite sides of a major tree split. Without intervention, the model might treat these adjacent values as entirely unrelated, leading to discontinuities in the predicted distribution.

Overcoming Tree Bias with Smoothing

LSHS addresses tree bias by incorporating Graph-Based Trend Filtering. By treating the output labels as nodes in a graph (a lattice where neighbors are connected), the model gains spatial awareness. This filtering acts as a regularizer during training, forcing the model to ensure that the predicted probabilities of neighboring labels remain similar.

This approach allows the model to "borrow statistical strength" from nearby values. To maintain the efficiency of the tree structure, the authors utilize Local Smoothing, applying the regularizer only to a small neighborhood around the target label. This ensures that the model remains fast while benefiting from the accuracy of a smoothed distribution.

Performance and Sample Efficiency

The authors evaluated LSHS across synthetic benchmarks, UCI repository datasets, and complex generative tasks like WaveNet audio synthesis. A key finding is the model's exceptional sample efficiency, particularly in low-to-mid sample size regimes.

Comparison of TV Error across different sample sizes for GMM and Edge-Biased distributions.

As illustrated in the comparative analysis above, LSHS (purple line) consistently achieves lower Total Variation (TV) error than standard multinomial or mixture-based methods. In the "Edge-Biased" distribution—designed to mimic the boundary spikes common in image data—LSHS was uniquely capable of capturing both the smooth central modes and the sharp spikes at the boundaries.

Key Results and Insights

  • Error Reduction: LSHS reduced prediction error by nearly half on several real-world datasets compared to popular baselines.
  • WaveNet Integration: When integrated into WaveNet for audio tasks, LSHS outperformed the original multinomial model in most resolution settings, demonstrating its scalability to high-dimensional generative tasks.
  • Consistency: Unlike GMMs, which often suffer from model misspecification, LSHS provided a high-fidelity fit across all tested scenarios, from simple synthetic tests to complex multi-speaker speech databases.

Conclusion and Future Work

LSHS represents a significant step forward for ordinal prediction, offering a model that is both flexible and sample-efficient. By "healing" the boundaries of hierarchical trees through trend filtering, it provides a robust solution for tasks where data is scarce or distributions are complex.

Future research may focus on overcoming the current dimensionality limits, as the $O(n)$ output node requirement can become a memory bottleneck beyond four dimensions. One promising direction is the integration of LSHS into autoregressive models like MADE, potentially allowing for even higher-dimensional discrete distribution modeling.

Summary updated

Abstract

We propose a new approach to conditional probability estimation for ordinal labels. First, we present a specialized hierarchical softmax variant inspired by k-d trees that leverages the inherent spatial structure of (potentially-multivariate) ordinal labels. We then adapt ideas from signal processing on noisy graphs to develop a novel regularizer for such hierarchical softmax models. Both our tree structure and regularizer independently boost the sample efficiency of a deep learning model across a series of simulation studies. Furthermore, the combination of these two techniques produces additive gains and the model does not suffer from the pathologies of other approaches in the literature. We validate our approach empirically on a suite of real-world datasets, in some cases reducing the error by nearly half in comparison to other popular methods in the literature. Our results demonstrate that our method is a powerful new modeling technique for conditional probability estimation of ordinal labels, especially in the low-to-mid sample size regimes such as those often found in biological and other physical sciences.
BibTeX
@inproceedings{tansey2018leaf,
  author = {Wesley Tansey and Karl Pichotta and James G. Scott},
  title = {{Leaf-Smoothed Hierarchical Softmax for Ordinal Prediction}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.11754},
}
Figure