Multi-View Randomized Kernel Classification via Nonconvex Optimization

Xiaojian Ding, Fan Yang

Abstract

This paper introduces RMKL (Multi-View Randomized Kernel Classification), a novel framework designed to address the diversity-accuracy tradeoff in Multiple Kernel Learning (MKL). By generating a pool of high-quality randomized kernels and selecting an optimal subset through nonconvex optimization, RMKL achieves state-of-the-art performance. The method transforms a difficult integer programming problem into a solvable semidefinite relaxation, demonstrating robustness across diverse datasets and various kernel-based classifiers.

Introduction

Multi-view data integration—combining information from sources like text, images, and audio—is a cornerstone of modern machine learning. Multiple Kernel Learning (MKL) is a primary technique for this, yet it often struggles with the balance between kernel accuracy and diversity. Traditional methods frequently overlook the importance of diversity, leading to redundant kernels that fail to improve generalization. Furthermore, standard kernels are highly sensitive to hyperparameter tuning, making the search for optimal parameters computationally expensive and prone to sub-optimal results.

Methods

The proposed RMKL framework operates in three distinct stages:

  1. Generating Randomized Kernels: Instead of manual tuning, random parameters are assigned to each input dimension. This creates a large pool of randomized kernels capable of capturing diverse characteristics of the data distribution.
  2. Measuring Quality: Each kernel is evaluated based on a "double-fault" diversity metric (how often two kernels fail on the same sample) and individual accuracy via $k$-fold cross-validation.
  3. Nonconvex Optimization: The selection of the optimal kernel subset is formulated as a nonconvex quadratic integer programming problem. This is efficiently solved by transforming it into a convex semidefinite programming (SDP) relaxation and applying a branch-and-bound (B&B) algorithm.

Results

RMKL was evaluated on eight benchmark datasets, including four multi-view datasets (e.g., 3Sources, MSRC-v1) and four single-view gene expression datasets (e.g., Armstrong, Chen). The results demonstrate that RMKL consistently achieves superior accuracy, outperforming ten state-of-the-art MKL methods.

Classification accuracy (ACC%) across eight benchmark datasets for various kernel-based classifiers.

As shown in Figure 1, the method is classifier-agnostic, providing performance gains not only for standard Support Vector Machines (SVM) but also for Least Squares SVM (LSSVM) and Least Squares Kernel Extreme Learning Machines (LSKELM).

Sensitivity analysis showing the impact of parameters C and m on classification accuracy across different models.

Sensitivity analysis (Figure 4) further reveals that RMKL is relatively robust to the choice of hyperparameters, such as the number of selected kernels ($m$) and the regularization parameter ($C$), facilitating its application in real-world scenarios.

Conclusion

RMKL provides a mathematically elegant solution to the MKL diversity-accuracy tradeoff. Its use of randomization reduces parameter sensitivity, while the optimization framework ensures a diverse and accurate kernel subset. While the computational complexity of solving SDPs remains a consideration for very large kernel pools, the current results establish RMKL as a robust and high-performing framework for multi-view learning. Future work will involve extending this approach to regression and clustering tasks.

Summary updated

Abstract

Multi kernel learning (MKL) is a representative supervised multi-view learning method widely applied in multi-modal and multi-view applications. MKL aims to classify data by integrating complementary information from predefined kernels. Although existing MKL methods achieve promising performance, they fail to consider the tradeoff between diversity and classification accuracy of kernels, preventing further improvement of classification performance. In this paper, we tackle this problem by generating a number of high-quality base learning kernels and selecting a kernel subset with maximum pairwise diversity and minimum generalization errors. We first formulate this idea as a nonconvex quadratic integer programming problem. Then we transform this nonconvex problem into a convex optimization problem and prove it is equivalent to a semidefinite relaxation problem, which a semidefinite-based branch-and-bound algorithm can quickly solve. Experimental results on the real-world datasets demonstrate the superiority of the proposed method. The results also show that our method works for the support vector machine (SVM) classifier and other state-of-the-art kernel classifiers.
BibTeX
@inproceedings{ding2024multi,
  author = {Xiaojian Ding and Fan Yang},
  title = {{Multi-View Randomized Kernel Classification via Nonconvex Optimization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i10.29064},
}
Figure