Incremental Sparse Bayesian Ordinal Regression

Chang Li, Maarten de Rijke

Abstract

Ordinal Regression (OR) aims to model the ordering information between different data categories, which is a crucial topic in multi-label learning. An important class of approaches to OR models the problem as a linear combination of basis functions that map features to a high dimensional non-linear space. However, most of the basis function-based algorithms are time consuming. We propose an incremental sparse Bayesian approach to OR tasks and introduce an algorithm to sequentially learn the relevant basis functions in the ordinal scenario. Our method, called Incremental Sparse Bayesian Ordinal Regression (ISBOR), automatically optimizes the hyper-parameters via the type-II maximum likelihood method. By exploiting fast marginal likelihood optimization, ISBOR can avoid big matrix inverses, which is the main bottleneck in applying basis function-based algorithms to OR tasks on large-scale datasets. We show that ISBOR can make accurate predictions with parsimonious basis functions while offering automatic estimates of the prediction uncertainty. Extensive experiments on synthetic and real word datasets demonstrate the efficiency and effectiveness of ISBOR compared to other basis function-based OR approaches.

Introduction

Ordinal Regression (OR) is the task of predicting labels that have a natural ordering, such as movie ratings or medical condition severity. Unlike standard classification, the relative distance and order between labels are significant. While basis function-based methods provide powerful non-linear modeling, they often face a major scalability wall. Traditional Bayesian methods, such as Gaussian Processes, typically scale at $O(N^3)$, making them unusable for large-scale datasets. Furthermore, many models lack sparsity, requiring the entire dataset to be kept in memory, and fast alternatives like Support Vector Machines (SVMs) often fail to provide probabilistic uncertainty estimates.

ISBOR addresses these limitations by combining the predictive power of Bayesian learning with the efficiency of incremental processing. By sequentially selecting only the most relevant data points (basis functions), it achieves state-of-the-art accuracy while being significantly faster and more memory-efficient than traditional batch-based methods.

Methodology

ISBOR is a threshold-based model that maps input features to a hidden score, which is then categorized into ordinal bins using learned thresholds.

Incremental Learning and Sparsity

Instead of processing all $N$ data points simultaneously, ISBOR utilizes a "fast marginal likelihood" strategy. It begins with a minimal subset of data and sequentially adds or removes basis functions based on their contribution to the model's evidence. This approach, combined with a zero-mean Gaussian prior and Gamma hyper-priors, acts as a form of regularization that forces the weights of irrelevant data points to zero, resulting in a highly sparse model.

Laplace Approximation and Log-Concavity

Since the true Bayesian posterior is mathematically intractable for this problem, ISBOR employs the Laplace method to approximate it with a Gaussian distribution. A critical property of the ISBOR framework is that the posterior distribution is log-concave. As shown in Figure 1, the log-posterior exhibits a concave shape, and its second derivative remains negative across the parameter space. This property ensures that optimization via Newton-Raphson updates will reliably converge to a global maximum, avoiding the local traps common in non-linear optimization.

The log-posterior and its first and second derivatives for different ordinal categories, illustrating the log-concavity essential for stable global optimization.

Experimental Evaluation

The authors evaluated ISBOR on a 2D synthetic dataset of 21,000 points and seven benchmark datasets, including Marketing, Census, CalHouse, and Computer, ranging from 400 to 22,500 samples.

Key Results

  • Accuracy: ISBOR achieves predictive accuracy comparable to (and sometimes better than) Support Vector Ordinal Regression (SVOR), a leading non-probabilistic benchmark.
  • Computational Speed: By moving to an incremental strategy, the complexity drops from $O(N^3)$ to approximately $O(N + M^3)$, where $M$ is the number of relevant samples. On a 10,000-sample synthetic test, ISBOR was roughly 10 times faster than its non-incremental counterpart.
  • Extreme Sparsity: ISBOR demonstrates remarkable efficiency in sample selection. For the Census dataset (~22,000 samples), ISBOR achieved its results using only 73 relevant samples, whereas SVM-based methods often require thousands of support vectors.

Conclusion and Future Work

ISBOR provides a scalable, sparse, and probabilistic solution for large-scale ordinal regression. By leveraging incremental learning and ensuring log-concavity, it overcomes the computational bottlenecks of traditional Bayesian methods while maintaining high accuracy and providing uncertainty estimates. Future work may involve adapting ISBOR for ranking tasks by incorporating pair-wise position information and exploring more advanced approximation techniques like Variational Bayes or Expectation Propagation for hyper-parameter tuning.

Summary updated

Abstract

Ordinal Regression (OR) aims to model the ordering information between different data categories, which is a crucial topic in multi-label learning. An important class of approaches to OR models the problem as a linear combination of basis functions that map features to a high dimensional non-linear space. However, most of the basis function-based algorithms are time consuming. We propose an incremental sparse Bayesian approach to OR tasks and introduce an algorithm to sequentially learn the relevant basis functions in the ordinal scenario. Our method, called Incremental Sparse Bayesian Ordinal Regression (ISBOR), automatically optimizes the hyper-parameters via the type-II maximum likelihood method. By exploiting fast marginal likelihood optimization, ISBOR can avoid big matrix inverses, which is the main bottleneck in applying basis function-based algorithms to OR tasks on large-scale datasets. We show that ISBOR can make accurate predictions with parsimonious basis functions while offering automatic estimates of the prediction uncertainty. Extensive experiments on synthetic and real word datasets demonstrate the efficiency and effectiveness of ISBOR compared to other basis function-based OR approaches.
BibTeX
@inproceedings{li2018incremental,
  author = {Chang Li and Maarten de Rijke},
  title = {{Incremental Sparse Bayesian Ordinal Regression}},
  booktitle = {Neural Networks},
  year = {2018},
  url = {https://openreview.net/forum?id=BgUdff6iiaE},
}
Figure