Nonparametric Online Machine Learning with Kernels

Khanh NguyenIJCAI 2017 · DOI

TL;DR

This paper tackles the challenge of selecting optimal hyperparameters for kernel-based and max-margin machine learning models, especially in the demanding context of online learning. By framing these methods within a Bayesian inference framework, the authors propose a principled way to learn hyperparameters, avoiding computationally expensive grid searches and paving the way for more efficient and scalable machine learning.

What Problem Does This Paper Address?

Kernel methods and max-margin algorithms are powerful tools for building machine learning models with excellent generalization capabilities. They work by mapping data into a higher-dimensional space where linear models can capture complex, non-linear relationships. However, a significant hurdle in using these methods is "model selection" – determining the best hyperparameters that control the model's complexity and performance. This problem becomes particularly acute in "online learning," where data arrives sequentially and the optimal hyperparameters can change over time. Traditional methods like grid search, which exhaustively try different hyperparameter combinations, are computationally prohibitive, especially when dealing with many hyperparameters or large datasets. This paper aims to provide a more efficient and principled solution to this model selection problem, particularly for online learning scenarios.

Methods

The core contribution of this paper is the application of Bayesian inference to the problem of hyperparameter learning in kernel-based and max-margin models. Instead of treating hyperparameters as fixed values to be tuned through brute-force search, the authors propose to model them as latent variables within a graphical model. This allows them to use Bayesian inference techniques, such as Markov Chain Monte Carlo (MCMC) or variational inference, to learn the most likely hyperparameter values.

Specifically, the paper discusses two main approaches:

  • Multiple Kernel Learning (MKL) with Bayesian Inference: For MKL, where multiple kernels are combined linearly, the authors propose a Bayesian approach that avoids the need for grid search to tune kernel combination weights and other hyperparameters. They construct a graphical model and use data augmentation to make the posterior inference tractable. This approach also helps in avoiding complex regularization terms like the group norm L2,1.
  • Multi-Hyperplane Machine with Bayesian Inference: For multi-hyperplane machines, which aim to improve scalability by learning hyperplanes in the input space, the authors plan to use Bayesian inference to address model selection. This is presented as a future direction, building upon their work to incorporate sparsity-inducing norms.

Datasets

The paper mentions validation on "several benchmark datasets" for both batch and online settings. Specific dataset names are not detailed in the provided text.

Key Insights and Ideas

  • Bayesian Inference as a Solution to Model Selection: The paper highlights that Bayesian inference offers a principled and computationally efficient alternative to grid search for hyperparameter tuning in kernel methods.
  • Unified Framework for Kernel Methods: By viewing max-margin and kernel methods through a Bayesian lens, the authors create a more unified theoretical framework that can handle model selection naturally.
  • Enabling Online Learning: The proposed Bayesian approach is particularly well-suited for online learning, where hyperparameters can drift, and the system needs to adapt continuously without expensive re-tuning.
  • Avoiding Computational Bottlenecks: The methods presented aim to significantly reduce the computational cost associated with hyperparameter tuning, making complex kernel models more practical for large-scale and streaming data.

Key Results

The paper states that their proposed methods can learn hyperparameters in a principled way, eliminating the need for expensive grid searches. They report gaining a "significant computational speedup" compared to state-of-the-art baselines in both batch and online settings. The methods are also designed to be scalable and ready for online learning.

Limitations and Future Work

  • Model Selection in Semi-Supervised Learning: The authors identify semi-supervised learning (where training data includes both labeled and unlabeled examples) as a key area for future work, aiming to extend their Bayesian inference approach to this setting.
  • Multi-Hyperplane Machine Hyperparameter Tuning: While the paper discusses addressing sparsity in multi-hyperplane machines, the full application of Bayesian inference for hyperparameter tuning in this specific context is presented as a future step.
  • Tractability of Posterior Inference: The paper acknowledges that posterior inference can be intractable and proposes data augmentation as a technique to overcome this. The effectiveness and scalability of this augmentation technique in various scenarios might be a point of further investigation.

Summary updated

BibTeX
@inproceedings{nguyen2017nonparametric,
  author = {Khanh Nguyen},
  title = {{Nonparametric Online Machine Learning with Kernels}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/758},
}
Figure