ℓ q -Norm Sample-Adaptive Multiple Kernel Learning

Qiang Wang, Xinwang Liu, Jiaqing Xu

Abstract

Traditional Multiple Kernel Learning (MKL) algorithms apply a fixed set of kernel weights across all data samples. This "one-size-fits-all" approach fails to account for sample-specific variations. This paper introduces ℓ<sub>q</sub>-norm Sample-Adaptive Multiple Kernel Learning (ℓ<sub>q</sub>-SAMKL), which allows for sample-specific kernel selection. By extending the framework to arbitrary ℓ<sub>q</sub>-norms (q ≥ 1) and deriving a closed-form solution for kernel weights, the authors provide a robust and flexible method for complex classification tasks.

Introduction

Multiple Kernel Learning (MKL) is a powerful technique for integrating diverse data representations—such as color, texture, and deep features—into a single predictive model. However, standard MKL assumes that the optimal combination of these features is uniform across the entire dataset. In reality, a specific feature might be highly informative for one image but noisy for another. Sample-Adaptive MKL (SAMKL) addresses this by allowing kernel weights to vary per sample. This paper generalizes SAMKL to the ℓ<sub>q</sub>-norm, offering greater flexibility than previous ℓ<sub>1</sub>-norm restricted versions.

The Challenge of Global Kernel Weights

In traditional MKL, a single set of weights is learned for a pre-specified group of base kernels. This approach is often suboptimal because data is frequently "irregularly corrupted" or contains heterogeneous feature distributions. For instance, in image classification, occlusion or lighting changes might render certain descriptors (like SIFT) less reliable for specific samples while deep features remain robust. Previous attempts at SAMKL were limited by the ℓ<sub>1</sub>-norm, which forces extreme sparsity, and suffered from computationally expensive optimization routines.

Proposed ℓ<sub>q</sub>-SAMKL Framework

The authors propose a framework that adaptively switches kernels on or off for each individual sample. By generalizing to the ℓ<sub>q</sub>-norm, the model can range from sparse selection to collaborative combinations, depending on the application requirements.

The proposed framework for image classification using ℓ<sub>q</sub>-norm SAMKL.

The framework involves three main stages:

  1. Feature Extraction: Combining traditional computer vision features (HOG, SIFT, LBP) with deep learning features (ResNet, VGG).
  2. Preprocessing: Normalizing features and constructing kernel matrices.
  3. MKL Decision: Applying the ℓ<sub>q</sub>-SAMKL algorithm to determine sample-specific weights and maximize the classification margin.

Efficient Optimization via Cutting Planes

To make ℓ<sub>q</sub>-SAMKL practical, the authors introduced two major technical improvements:

  • Closed-Form Solution: Leveraging the equivalence between MKL and group-lasso, they derived a mathematical shortcut to calculate kernel weights directly, bypassing the need for slow external optimization software.
  • 1-Slack Cutting Plane Method: They implemented a "1-slack" cutting plane algorithm to solve the margin maximization problem. This approach is more stable and efficient than traditional coordinate descent methods, adding only one constraint per iteration and ensuring monotonic convergence.

Experimental Evaluation

The method was tested on protein subcellular localization datasets (psortPos, plant) and various image classification benchmarks (Caltech256, Birds200, STL-10, Cifar-100, Vgg Pets).

Key findings include:

  • Improved Accuracy: ℓ<sub>q</sub>-SAMKL consistently outperformed standard MKL baselines and the original ℓ<sub>1</sub>-SAMKL.
  • Hybrid Feature Synergy: The results confirmed that while deep features are dominant, their combination with traditional features via adaptive MKL yields superior performance.
  • Computational Efficiency: The 1-slack formulation demonstrated linear scaling in computation time relative to the number of iterations, making it suitable for larger datasets.

Conclusion

The ℓ<sub>q</sub>-SAMKL framework provides a flexible and efficient solution for sample-adaptive learning. By allowing the model to ignore irrelevant or noisy kernels on a per-sample basis, it achieves higher robustness and accuracy in complex classification tasks. Future work will explore extending this adaptive approach to regression and clustering problems.

Summary updated

Abstract

Existing multiple kernel learning (MKL) algorithms indiscriminately apply the same set of kernel combination weights to all samples by pre-specifying a group of base kernels. Sample-adaptive MKL learning (SAMKL) overcomes this limitation by adaptively switching on/off the base kernels with respect to each sample. However, it restricts to solving MKL problems with pre-specified kernels. And, the formulation of existing SAMKL falls to an ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> -norm MKL which is not flexible. To allow for robust kernel mixtures that generalize well in practical applications, we extend SAMKL to the arbitrary norm and apply it to image classification. In this paper, we formulate a closed-form solution for optimizing the kernel weights based on the equivalence between group-lasso and MKL, and derive an efficient ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</sub> -norm (q ≥ 1 and denoting the ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</sub> -norm of kernel weights) SAMKL algorithm. The cutting plane method is used to solve this margin maximization problem. Besides, we propose a framework for solving MKL problems in image classification. Experimental results on multiple data sets show the promising performance of the proposed solution compared with other competitive methods.
BibTeX
@inproceedings{wang2020l,
  author = {Qiang Wang and Xinwang Liu and Jiaqing Xu},
  title = {{ℓ<sub> <i>q</i> </sub>-Norm Sample-Adaptive Multiple Kernel Learning}},
  booktitle = {IEEE Access},
  year = {2020},
  doi = {10.1109/access.2020.2974903},
}
Figure