Large-Scale Kernel-Based Feature Extraction via Low-Rank Subspace Tracking on a Budget

Fatemeh Sheikholeslami, Dimitris Berberidis, Georgios B. GiannakisIEEE TSP 2018 · OpenReview

TL;DR

This paper introduces a novel online algorithm for kernel-based feature extraction that efficiently tracks low-rank nonlinear subspaces. This approach significantly reduces computational and memory demands, making powerful kernel methods practical for large-scale, dynamic datasets.

What Problem Does This Paper Address?

Kernel-based methods are powerful for learning complex, nonlinear patterns but suffer from prohibitive computational and memory costs as datasets grow. Specifically, forming and storing the kernel matrix scales quadratically with the number of data points ($N^2$), and subsequent computations can be cubic ($N^3$). This "big data" challenge limits their applicability. Existing methods for reducing this complexity often rely on approximations that may not be data-driven or suitable for online, streaming scenarios where data arrives sequentially. This paper aims to bridge this gap by developing an efficient, online, and budget-constrained method for kernel-based feature extraction.

Methods

The core of the proposed method is a generative model that approximates high-dimensional (potentially infinite) features by projecting them onto a low-rank nonlinear subspace. This allows for a kernel function approximation. The authors develop both offline and online solvers for learning this subspace.

  • Low-Rank Subspace Approximation: The key idea is to model the data $x_i$ as a linear combination of a low-rank matrix $L$ and projected features $q_i$, with added noise: $x_i \approx Lq_i + v_i$. This is extended to the lifted feature space using a "virtual" subspace $\tilde{L}$, leading to a kernel approximation $\kappa(x_i, x_j) \approx \tilde{q}_i^T \tilde{q}_j$.
  • Batch Solver (BKFE): An iterative, bi-convex optimization approach is proposed to find the optimal subspace factor $A$ and projected features $q_i$.
  • Online Solvers (Parametric & Nonparametric): To handle streaming data, stochastic gradient descent (SGD) is employed.
  • Parametric Tracker (Algorithm 2): Updates the subspace factor $A$ while keeping its size fixed.
  • Nonparametric Tracker (Algorithm 3): Updates $A$ where its size can grow with the data, offering a more flexible approach.
  • Budgeted Feature Extraction (OKFEB): To manage memory and computational constraints, a "budget" ($B$) is imposed on the number of stored "online support vectors" (OSVs).
  • Censoring: Uninformative data points (those that don't significantly change the subspace) are discarded.
  • Budget Maintenance: When the OSV set exceeds the budget, a greedy removal strategy (minimum distortion or recency-aware) is used to discard less important OSVs.

Datasets

The paper evaluates its methods on:

  • Synthetic Datasets:
    • A dataset for testing batch and online feature extraction, generated from two equiprobable classes of 3D data vectors on spheres of different radii.
  • A dataset for dynamic subspace tracking, generated from two different manifolds (sphere and spheroid) to simulate changes in the underlying data distribution.
  • Real-World Datasets:
    • PAMAP2: A dataset for physical activity tracking, containing measurements from inertial sensors worn by subjects.
  • Adult, CADATA, Slice, Year: Standard datasets used for evaluating kernel-based classification and regression tasks.

Key Insights and Ideas

  • Low-Rank Subspace as a Feature Extractor: The core insight is that a low-rank approximation of the lifted feature space can effectively capture the essential nonlinear structure of the data, acting as a powerful feature extractor.
  • Online Tracking for Dynamic Data: The proposed online algorithms are crucial for handling data streams and dynamically changing data distributions, which are common in real-world applications.
  • Budgeting for Scalability: The introduction of a budget for storing online support vectors is a key innovation for making kernel methods practical on large datasets, balancing accuracy with computational feasibility.
  • Censoring Uninformative Data: Discarding data points that don't contribute significantly to subspace learning is an efficient way to manage computational load and memory.
  • Unified Framework: The paper presents a unified framework that can handle both static and dynamic data, and can be adapted for classification, regression, and feature extraction tasks.

Key Results

  • Efficiency: The proposed online budgeted method (OKFEB) achieves performance comparable to batch methods but with significantly lower computational complexity (e.g., $O(Nr^3 + NDr)$ vs. $O(N^2r)$ per iteration for batch).
  • Accuracy: OKFEB demonstrates competitive accuracy in kernel approximation, classification, and regression tasks, often outperforming existing Nystrom-based methods, especially on dynamic datasets.
  • Dynamic Subspace Tracking: The method successfully tracks changes in the underlying data manifold, as evidenced by the rise in LS error when the manifold shifts in synthetic data experiments.
  • Budget Impact: The budget parameter $B$ significantly impacts performance, with a sweet spot often found around $B \approx 1.5r$ to $5r$. Restrictive budgets can lead to performance comparable to more complex methods, highlighting the effectiveness of the greedy maintenance strategy.
  • Kernel Mismatch: OKFEB shows lower average kernel mismatch compared to KPCA and other Nystrom variations on dynamic datasets.

Limitations and Future Work

  • Parameter Tuning: The performance of the algorithms is sensitive to parameter choices, such as the regularization parameter $\lambda$, the step sizes ($\mu_{n,L}, \mu_{n,A}$), the budget $B$, and the censoring threshold $\epsilon$. Cross-validation or adaptive methods might be needed for optimal settings.
  • Kernel Choice: While the paper uses Gaussian and polynomial kernels, the effectiveness of the approach might depend on the choice of kernel and its suitability for the data.
  • Theoretical Guarantees: While convergence is proven for the proposed algorithms, the theoretical analysis often relies on assumptions like i.i.d. data and bounded iterates, which might not always hold in practice.
  • Future Work: The authors suggest exploring data-driven multi-kernel approaches and further investigating adaptive parameter selection strategies. The framework's applicability to other machine learning tasks beyond classification and regression could also be explored.

Summary updated

BibTeX
@article{sheikholeslami2018large,
  author = {Fatemeh Sheikholeslami and Dimitris Berberidis and Georgios B. Giannakis},
  title = {{Large-Scale Kernel-Based Feature Extraction via Low-Rank Subspace Tracking on a Budget}},
  journal = {IEEE Trans. Signal Process.},
  year = {2018},
  url = {https://openreview.net/forum?id=p7Najc-dWmH},
}
Figure