Layer-Wise Relevance Propagation Based Sample Condensation for Kernel Machines

Daniel Winter, Ang Bian, Xiaoyi JiangCAIP 2021 · DOI

TL;DR

This paper introduces a novel method for "sample condensation" in kernel machines, significantly reducing the number of training samples needed for efficient inference without sacrificing classification performance. By leveraging Layer-wise Relevance Propagation (LRP) from explainable AI, they identify and retain the most "relevant" training samples, making kernel machines more scalable.

What Problem Does This Paper Address?

Kernel machines, like Support Vector Machines (SVMs), are powerful tools for classification and regression. However, their practical application is often hindered by the computational cost associated with large datasets. Specifically, training kernel machines requires storing the entire training set and computing a Gram matrix, which scales poorly with the number of samples ($O(n^3)$). While some methods like EigenPro offer speedups, the need to retain all training samples for prediction remains a bottleneck, especially when kernel computations are expensive. This paper addresses the challenge of reducing the training data size for kernel machines while preserving their predictive accuracy, aiming to make them more efficient for large-scale deployment.

Methods

The core of this paper's contribution lies in its novel approach to sample condensation for kernel machines. They leverage the interpretation of kernel machines as two-layer neural networks.

  • Neural Network Interpretation: Kernel machines are viewed as a network where input samples are connected to hidden layer neurons via a kernel function, and these hidden neurons are then connected to output neurons with learned weights.
  • Layer-wise Relevance Propagation (LRP): This explainable AI technique is adapted to measure the "relevance" or importance of each training sample. LRP propagates relevance scores backward from the output layer to the input layer, effectively quantifying how much each training sample contributes to the model's decision for a given test sample.
  • Relevance Estimation: The LRP method is applied to assign a relevance score to each training sample. This involves training a kernel machine on a subset of the data, then using a validation set to compute the relevance of all training samples. The relevance of a training sample $x_i$ to the output $f(z)$ on a validation sample $z$ is calculated using the kernel function and the learned weights. To get a general relevance score for $x_i$, these relevances are averaged over a validation set.
  • Decremental Strategy: Based on these relevance scores, a decremental strategy is employed. The training samples are sorted by their relevance, and the least relevant samples are iteratively removed. This process continues until a predefined accuracy threshold (controlled by a parameter $\mu$) is met. The algorithm iteratively retrains the kernel machine with the reduced set and re-evaluates relevances.

Datasets

The authors evaluated their approach on three widely used image classification datasets:

  • MNIST: A dataset of handwritten digits (28x28 grayscale images).
  • MNIST-Fashion: A dataset of clothing items (28x28 grayscale images), structured similarly to MNIST.
  • CIFAR-10: A dataset of 32x32 RGB images from ten object classes.

For their experiments, 90% of the training data was used for training the kernel machine, and the remaining 10% served as a validation set for relevance estimation.

Key Insights and Ideas

  • Explainable AI for Data Selection: The paper ingeniously applies explainable AI (LRP) not for understanding model behavior in general, but specifically for the task of selecting important data points. This is a novel application of LRP.
  • Relevance as a Proxy for Importance: The core idea is that samples deemed "relevant" by LRP are crucial for maintaining classification performance. This relevance measure effectively captures the discriminative power of individual training samples.
  • Decremental Condensation Works: The proposed decremental strategy, which iteratively removes the least relevant samples, proves effective in significantly reducing the dataset size while preserving accuracy.
  • CNN Feature Learning vs. Classification: The experiments suggest that while the feature learning part of a CNN benefits from a large training set, the final classification layers can perform well with a smaller, condensed set of representative samples. This highlights a potential for optimizing model deployment by condensing features rather than raw data.

Key Results

  • Substantial Sample Reduction: The approach demonstrated the ability to achieve substantial reductions in the number of training samples. For instance, on MNIST, they could retain only 5% of the original training samples while maintaining 99.9% of the original accuracy. For CIFAR-10, 43% of samples were sufficient to reach 99% accuracy.
  • Accuracy Preservation: The sample condensation method was shown to preserve classification accuracy effectively. In many cases, the accuracy of the condensed set was comparable to or even slightly better than randomly selected samples of the same size. For MNIST-Fashion, reducing samples even slightly increased accuracy.
  • Comparison to Random Selection: The paper includes comparisons with random sample selection, showing that the LRP-based method consistently outperforms random selection in terms of accuracy for a given number of selected samples, especially when the dataset is significantly reduced.
  • Runtime: While the paper doesn't focus on overall training time reduction (as it uses a CNN for feature extraction first), the condensation process itself is efficient. The runtime for the decremental approach on MNIST was reported as 7.9 hours for the two MNIST datasets and 11.6 hours for CIFAR-10, using specific hardware.

Limitations and Future Work

  • General Expressiveness: The authors acknowledge that achieving general higher expressiveness of the selected samples is not the primary goal, as the approach is tailored to kernel machines. They note that the selected samples do not necessarily exhibit higher expressiveness in general when used to train a CNN directly, except for the MNIST dataset where very few samples were selected.
  • Decremental Strategy: The paper mentions that the current decremental strategy is rather straightforward. They suggest that more sophisticated techniques, such as exploring sparse representations, could be investigated in the future for modeling sample importance.
  • Kernel Machine Specificity: While the method is designed for kernel machines, its application to CNN features suggests broader potential. Future work could explore its direct application to other types of models or further investigate its synergy with deep learning architectures.

Summary updated

BibTeX
@inproceedings{winter2021layer,
  author = {Daniel Winter and Ang Bian and Xiaoyi Jiang},
  title = {{Layer-Wise Relevance Propagation Based Sample Condensation for Kernel Machines}},
  booktitle = {CAIP},
  year = {2021},
  doi = {10.1007/978-3-030-89128-2\_47},
}
Figure