Large-Margin Multiple Kernel Learning for Discriminative Features Selection and Representation Learning

Babak Hosseini, Barbara Hammer

Abstract

Multiple kernel learning (MKL) algorithms combine different base kernels to obtain a more efficient representation in the feature space. Focusing on discriminative tasks, MKL has been used successfully for feature selection and finding the significant modalities of the data. In such applications, each base kernel represents one dimension of the data or is derived from one specific descriptor. Therefore, MKL finds an optimal weighting scheme for the given kernels to increase the classification accuracy. Nevertheless, the majority of the works in this area focus on only binary classification problems or aim for linear separation of the classes in the kernel space, which are not realistic assumptions for many real-world problems. In this paper, we propose a novel multi-class MKL framework which improves the state-of-the-art by enhancing the local separation of the classes in the feature space. Besides, by using a sparsity term, our large-margin multiple kernel algorithm (LMMK) performs discriminative feature selection by aiming to employ a small subset of the base kernels. Based on our empirical evaluations on different real-world datasets, LMMK provides a competitive classification accuracy compared with the state-of-the-art algorithms in MKL. Additionally, it learns a sparse set of non-zero kernel weights which leads to a more interpretable feature selection and representation learning.

Introduction

Multiple Kernel Learning (MKL) provides a flexible framework for data representation by combining various "base kernels," each potentially capturing different modalities or descriptors of the data. Despite its success, traditional MKL often relies on finding a global hyperplane for class separation, typically within a Support Vector Machine (SVM) framework. This "global" approach can struggle with complex data distributions where classes are non-linearly separable or composed of multiple sub-clusters. Furthermore, many existing MKL methods are optimized for binary classification, making their extension to multi-class scenarios less effective.

To address these challenges, we introduce LMMK (Large-Margin Multiple Kernel learning). LMMK shifts the focus from global separation to local neighborhood structures, leveraging the principles of metric learning to handle complex multi-class distributions while simultaneously performing sparse feature selection.

Methods

The core of LMMK is the integration of Large-Margin Nearest Neighbor (LMNN) principles into the MKL optimization process. Unlike global separators, LMMK optimizes a local metric in the feature space using a "pull and push" strategy.

The LMNN "pull and push" strategy used in LMMK to enhance local class separation by pulling target neighbors closer and pushing impostors away.

As illustrated in the figure above, the algorithm identifies "target" neighbors (samples of the same class) and "impostor" neighbors (samples of different classes). The objective function is designed to:

  1. Minimize the distance between a sample and its target neighbors.
  2. Penalize impostors that enter the local margin surrounding the sample.
  3. Enforce sparsity on the kernel weights ($\beta$) using an $l_1$-regularization term.

By normalizing the base kernel matrices, the complex feature-space distance optimization is transformed into a Non-negative Linear Programming (LP) problem. This ensures computational efficiency and guarantees convergence to an optimal set of kernel weights.

Experimental Results

The LMMK framework was evaluated on several benchmark datasets for both representation learning (e.g., Caltech-101, Oxford Flowers17) and feature selection in multidimensional time-series (e.g., PEMS traffic data, AUSLAN sign language).

Classification Performance

LMMK consistently outperformed state-of-the-art MKL baselines. For instance, on the Oxford Flowers17 dataset, LMMK achieved an accuracy of 93.8%, a significant improvement over the 89.5% achieved by the MKL-TR baseline. On the Caltech-101 dataset, LMMK's performance scaled effectively with the number of training samples, as shown in the table below.

Comparison of LMMK against state-of-the-art methods on the Caltech-101 dataset across different training sample sizes ($N_{tr}$).

Feature Selection and Sparsity

A key advantage of LMMK is its ability to perform sparse feature selection. In the PEMS traffic dataset, which contains 963 dimensions, LMMK successfully reduced the feature set to just 75 dimensions while maintaining a state-of-the-art classification accuracy of 91.3%. This sparsity not only improves computational efficiency but also provides interpretability by identifying the most discriminative kernels or descriptors.

Conclusion

LMMK offers a robust multi-class MKL framework that excels by focusing on local class separation. By combining the strengths of LMNN with sparse kernel learning, it achieves high accuracy and provides interpretable feature selection. While the method is sensitive to the initial neighborhood structure and currently assumes a diagonal metric, it represents a significant step forward in making MKL more applicable to complex, real-world multi-class problems.

Summary updated

Abstract

Multiple kernel learning (MKL) algorithms combine different base kernels to obtain a more efficient representation in the feature space. Focusing on discriminative tasks, MKL has been used successfully for feature selection and finding the significant modalities of the data. In such applications, each base kernel represents one dimension of the data or is derived from one specific descriptor. Therefore, MKL finds an optimal weighting scheme for the given kernels to increase the classification accuracy. Nevertheless, the majority of the works in this area focus on only binary classification problems or aim for linear separation of the classes in the kernel space, which are not realistic assumptions for many real-world problems. In this paper, we propose a novel multi-class MKL framework which improves the state-of-the-art by enhancing the local separation of the classes in the feature space. Besides, by using a sparsity term, our large-margin multiple kernel algorithm (LMMK) performs discriminative feature selection by aiming to employ a small subset of the base kernels. Based on our empirical evaluations on different real-world datasets, LMMK provides a competitive classification accuracy compared with the state-of-the-art algorithms in MKL. Additionally, it learns a sparse set of non-zero kernel weights which leads to a more interpretable feature selection and representation learning.
BibTeX
@inproceedings{hosseini2019large,
  author = {Babak Hosseini and Barbara Hammer},
  title = {{Large-Margin Multiple Kernel Learning for Discriminative Features Selection and Representation Learning}},
  booktitle = {IJCNN},
  year = {2019},
  url = {https://openreview.net/forum?id=MKcspSxgS5},
}
Figure