Absent Multiple Kernel Learning

Xinwang Liu, Lei Wang, Jianping Yin, Yong Dou, Jian Zhang

Abstract

Multiple Kernel Learning (MKL) is a powerful paradigm for combining information from diverse data sources. However, real-world applications often suffer from missing data channels, a problem typically addressed through unreliable imputation techniques. This paper introduces Absent Multiple Kernel Learning (AMKL), a framework that avoids imputation by defining sample-specific margins based solely on observed data. We reformulate this approach into a convex optimization problem (C-AMKL), ensuring global optimality. Experimental results across multiple benchmarks, including protein localization and object recognition, demonstrate that AMKL significantly outperforms traditional methods, particularly in highly sparse scenarios with missing ratios up to 90%.

Introduction

In fields such as bioinformatics and medical imaging, data is frequently collected from multiple "channels" or views (e.g., genetic markers, blood tests, and various scan types). While Multiple Kernel Learning (MKL) excels at integrating these channels, it conventionally assumes complete data for every sample. In practice, missing channels are common due to technical failures or logistical constraints.

Traditional solutions rely on "imputation"—filling missing values with zeros, means, or predicted values. However, as the "missing ratio" increases, these guesses introduce significant noise, leading to a sharp decline in model performance. AMKL addresses this by adapting the model to the available data rather than forcing the data to fit a complete-case model.

Methodology: The AMKL Framework

The core innovation of AMKL is the shift from a global margin to a sample-based margin.

1. Sample-Based Margin

Instead of projecting all samples into a unified high-dimensional space, AMKL calculates the margin for each individual sample only within the "relevant space" defined by the channels actually present for that sample. This ensures that the classifier's confidence is grounded in observed evidence rather than imputed noise.

2. Convex Reformulation (C-AMKL)

The initial "min-max" objective for maximizing these sample-based margins results in a non-convex optimization problem. To make this computationally tractable, the authors leverage the Representer Theorem to derive a convex reformulation. This C-AMKL formulation guarantees a single global optimum, allowing for reliable solutions using standard convex optimization tools like CVX.

Experimental Evaluation

The researchers evaluated AMKL against several baselines, including Zero-Filling (ZF-MKL) and Mean-Filling (MF-MKL), across five benchmark datasets: psortPos, psortNeg, Plant, Protein Fold Prediction, and Caltech101. Robustness was tested by artificially removing channels at missing ratios ranging from 0% (complete data) to 90% (highly sparse data).

Results and Discussion

AMKL demonstrates remarkable stability and superiority as data becomes sparser.

Performance comparison on the psortPos dataset across various binary tasks and averaged results. C-AMKL (red) consistently maintains higher F1 scores as the missing ratio increases.

Superiority at High Sparsity

As shown in Figure 1, while imputation-based methods like ZF-MKL and MF-MKL experience a performance "cliff" beyond a 50% missing ratio, C-AMKL maintains high F1 scores. On the psortPos Class 3 vs. Class 4 task, C-AMKL improved performance by over 18% compared to the next best method at a 90% missing ratio.

Performance comparison on the psortNeg dataset. Similar to psortPos, C-AMKL exhibits superior robustness to missing data compared to baseline methods.

Consistency and Stability

Across all datasets, including psortNeg (Figure 2), AMKL showed significantly lower variance in performance. On the Caltech101 dataset, AMKL achieved a nearly 19% improvement over the second-best method at 90% sparsity, highlighting its effectiveness in complex image recognition tasks.

Conclusion

Absent Multiple Kernel Learning provides a mathematically rigorous alternative to data imputation. By acknowledging the absence of data and optimizing margins in the relevant observed space, AMKL offers a robust solution for real-world multi-view learning. Future work will focus on improving computational efficiency for large-scale datasets and incorporating "radius information" to further refine the model's accuracy.

Summary updated

Abstract

Multiple kernel learning (MKL) optimally combines the multiple channels of each sample to improve classification performance. However, existing MKL algorithms cannot effectively handle the situation where some channels are missing, which is common in practical applications. This paper proposes an absent MKL (AMKL) algorithm to address this issue. Different from existing approaches where missing channels are firstly imputed and then a standard MKL algorithm is deployed on the imputed data, our algorithm directly classifies each sample with its observed channels. In specific, we define a margin for each sample in its own relevant space, which corresponds to the observed channels of that sample. The proposed AMKL algorithm then maximizes the minimum of all sample-based margins, and this leads to a difficult optimization problem. We show that this problem can be reformulated as a convex one by applying the representer theorem. This makes it readily be solved via existing convex optimization packages. Extensive experiments are conducted on five MKL benchmark data sets to compare the proposed algorithm with existing imputation-based methods. As observed, our algorithm achieves superior performance and the improvement is more significant with the increasing missing ratio.
BibTeX
@inproceedings{liu2015absent,
  author = {Xinwang Liu and Lei Wang and Jianping Yin and Yong Dou and Jian Zhang},
  title = {{Absent Multiple Kernel Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2015},
  doi = {10.1609/aaai.v29i1.9545},
}
Figure