A method for speeding up feature extraction based on KPCA

Yong Xu, Yong Xu 0001, David Zhang, Fengxi Song, Jing-Yu Yang, Zhong Jing, Miao LiNeurocomputing 2007 · DOI

TL;DR

This paper introduces Improved Kernel Principal Component Analysis (IKPCA), a novel method to significantly speed up feature extraction in Kernel PCA (KPCA) without sacrificing classification accuracy. By approximating feature extractors as linear combinations of a subset of "important" training samples (nodes), IKPCA drastically reduces the computational cost of feature extraction, making it more feasible for large-scale real-world applications.

What Problem Does This Paper Address?

Kernel Principal Component Analysis (KPCA) is a powerful technique for nonlinear feature extraction. However, its efficiency is inversely proportional to the size of the training dataset. Specifically, to extract features for a single sample, KPCA requires calculating kernel functions between that sample and all training samples. This becomes computationally prohibitive for datasets with a large number of training samples, rendering KPCA inefficient or even infeasible in many practical scenarios. Existing methods to accelerate kernel methods often lack theoretical grounding or don't align with the core principles of KPCA.

Methods

The paper proposes an Improved KPCA (IKPCA) method. The core idea is to approximate the feature extractors (which are typically eigenvectors of the kernel matrix) as linear combinations of a smaller set of "nodes." These nodes are selected from the training samples based on their contribution to the expansion of the feature extractors.

The process involves:

  1. Node Determination: A novel algorithm is presented to select these "important" training samples as nodes. This algorithm iteratively identifies nodes by assessing which samples, when used as a basis for expansion, lead to the largest eigenvalues in a modified eigenvalue equation. The selection process aims to maximize a sum of eigenvalues, reflecting a good approximation of the feature extractors.
  2. Feature Extraction: Once the nodes are determined, feature extraction for a new sample is performed by calculating kernel functions only between the new sample and these selected nodes, rather than all training samples. This significantly reduces the number of kernel computations.

The authors emphasize that IKPCA remains methodologically consistent with the PCA framework, unlike some other kernel acceleration methods. If the number of nodes equals the number of training samples, IKPCA reduces to standard KPCA.

Datasets

The paper evaluates IKPCA on four benchmark datasets:

  • Splice: A dataset with 60 dimensions.
  • Diabetes
  • Banana
  • Cancer

For each dataset, experiments were conducted using subsets of training samples (e.g., 100, 90, 80, 70 features extractors for Splice; 100, 90, 80, 70 for Diabetes and Banana; 70, 60, 50, 40 for Cancer). The Gaussian kernel was used, with the parameter $\sigma^2$ set to the square of the Frobenius norm of the correlation matrix of the first training subset. A nearest neighbor classifier was used for evaluation.

Key Insights and Ideas

  • The "Important" Sample Hypothesis: The fundamental insight is that not all training samples contribute equally to the expansion of feature extractors in feature space. By identifying and using a subset of "important" samples (nodes), we can achieve a good approximation of KPCA with significantly reduced computation.
  • Methodological Consistency: IKPCA's strength lies in its adherence to the PCA methodology, ensuring that the derived features are theoretically sound and directly related to the principal components in the kernel space. This distinguishes it from methods that might rely on different theoretical underpinnings.
  • Trade-off Between Node Selection and Feature Extraction Speed: While the node selection process itself can be time-consuming, the subsequent feature extraction for new samples is dramatically faster. This trade-off is highly beneficial for applications where feature extraction is performed repeatedly on large datasets.
  • Accuracy Preservation: A key finding is that IKPCA achieves classification accuracy comparable to standard KPCA, demonstrating that the speedup does not come at the cost of performance.

Key Results

  • Significant Speedup: Experimental results show that IKPCA drastically reduces feature extraction time compared to KPCA. For instance, on the "Splice" dataset with 100 features extractors, KPCA's feature extraction time was 2130 seconds, while IKPCA achieved it in 813 seconds (with $t=0.25$). Similar substantial reductions were observed across all datasets and configurations.
  • Comparable Classification Accuracy: IKPCA generally achieved classification error rates very close to, and sometimes better than, KPCA. For the "Splice" dataset, IKPCA classified more accurately. For "Banana," the accuracy was slightly lower but still competitive.
  • Node Selection Parameter 't': The parameter 't' (related to the proportion of training samples used for node selection) influences both speed and accuracy. The paper explores various values of 't' to demonstrate this trade-off.

Limitations and Future Work

  • Node Selection Time: The authors acknowledge that the node selection procedure itself can be time-consuming. While the subsequent feature extraction is faster, the initial setup cost is a limitation.
  • Empirical Determination of 's': The number of nodes ('s') or the parameter 't' is often determined empirically or through a classification procedure. The paper suggests that classification accuracy can help guide this decision, but a more formal method for optimal 's' determination could be a future direction.
  • Comparison with Other Methods: While the paper contrasts IKPCA with some existing methods, a more comprehensive comparison with a broader range of state-of-the-art acceleration techniques could further highlight its advantages.

Summary updated

BibTeX
@article{xu2007method,
  author = {Yong Xu and Yong Xu and David Zhang and Fengxi Song and Jing-Yu Yang and Zhong Jing and Miao Li},
  title = {{A method for speeding up feature extraction based on KPCA}},
  journal = {Neurocomputing},
  year = {2007},
  doi = {10.1016/j.neucom.2006.09.005},
}
Figure