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

Babak Hosseini, Barbara Hammer

TL;DR

The authors introduce LMMK (Large-Margin Multiple Kernel learning), a framework that combines the "local neighborhood" philosophy of metric learning with the flexibility of Multiple Kernel Learning. By focusing on local class separation rather than global hyperplanes, LMMK achieves state-of-the-art accuracy in multi-class problems while simultaneously performing sparse feature selection for better interpretability.

What Problem Does This Paper Address?

Multiple Kernel Learning (MKL) is a powerful way to represent data by combining various "base kernels" (different ways of looking at the same data). However, the authors identify two major gaps in existing MKL research:

  1. The "Global" Trap: Most MKL algorithms (like those based on SVMs) try to find a single global hyperplane to separate classes. This fails when classes are non-linearly separable or consist of multiple sub-clusters (e.g., an XOR distribution).
  2. Binary Bias: Many high-performing MKL methods are designed for binary classification. Extending them to multi-class problems often results in fragmented feature embeddings that aren't cohesive across the entire dataset.

The challenge is to create a multi-class MKL framework that handles complex data distributions and identifies which specific features (or kernels) are actually driving the classification.

Methods

The core innovation is the integration of Large-Margin Nearest Neighbor (LMNN) principles into the MKL optimization process.

  • Local Metric Learning: Instead of a global separator, LMMK optimizes a diagonal Mahalanobis metric in the feature space. It uses a "pull and push" strategy: it pulls "target" neighbors (same class) closer together and pushes "impostor" neighbors (different classes) further away.
  • The LMMK Objective: The authors formulate an optimization problem that minimizes a loss function consisting of:
  • The distance to target neighbors.
  • A penalty for impostors that invade the local margin.
  • An $l_1$-regularization term (sparsity constraint) on the kernel weights ($\beta$).
  • Optimization via Linear Programming: By normalizing kernel matrices, the authors simplify the complex feature-space distances into a Non-negative Linear Programming (LP) problem. This makes the algorithm computationally efficient and guaranteed to converge to an optimal solution.

Datasets

The authors evaluated LMMK across two distinct scenarios:

  1. Representation Learning (Images):
    • Caltech-101: A classic benchmark with high inter-class variation.
  2. Pascal VOC 2007: A challenging 20-class object recognition dataset.
  3. Oxford Flowers17: 17 species of flowers with significant overlapping instances.
  4. Feature Selection (Multidimensional Time-Series - MTS):
    • PEMS: Daily traffic information (963 dimensions).
  5. AUSLAN: Australian sign language signs (95 classes).
  6. UTKinect: Human action recognition using Kinect skeleton sequences.

Key Insights and Ideas

  • Local vs. Global: The "aha moment" is that local separation is often more robust than global separation for real-world data. By focusing on small neighborhoods, LMMK can handle complex, non-convex class shapes that SVM-based MKL might struggle with.
  • Sparsity Equals Interpretability: By using $l_1$ regularization, the model doesn't just use a "bit of everything." It zeroes out irrelevant kernels. This tells researchers exactly which image descriptors (like SIFT vs. GIST) or which time-series dimensions are the most discriminative.
  • Kernel Normalization is Key: Normalizing the kernels allows the algorithm to bypass explicit (and often impossible) calculations in the high-dimensional feature space, turning a complex metric learning problem into a manageable Linear Program.

Key Results

LMMK consistently outperformed state-of-the-art MKL baselines (like MKL-TR and DMKL) across nearly all tests:

  • Accuracy Boost: On the Oxford Flowers17 dataset, LMMK achieved 93.8% accuracy, outperforming the best baseline (MKL-TR) by a significant 4.3% margin.
  • Superior Feature Selection: In the PEMS traffic dataset, LMMK reduced the feature set from 963 dimensions down to just 75 while maintaining a classification accuracy of 91.3% (the highest in the study).
  • Robustness to Training Size: On Caltech-101, LMMK showed a clear advantage as the number of training samples increased, reaching 88.6% accuracy with 30 samples per class.

Limitations and Future Work

  • Neighborhood Sensitivity: The algorithm relies on the $k$-nearest neighbor (kNN) structure. If the initial data distribution is so noisy that neighborhoods don't reflect class labels at all (very sparse training data), the "pull and push" mechanism becomes less effective.
  • Diagonal Constraint: The current model uses a diagonal matrix for the metric, which assumes kernels are independent. Future work could explore non-diagonal metrics to capture correlations between different kernels.
  • Scalability: While $O(N^2)$ is comparable to kernel computation, extremely large datasets might still require further optimization or stochastic approximation methods.

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},
}

Loading related content...

Figure