Memory-Effcient Orthogonal Least Squares Kernel Density Estimation using Enhanced Empirical Cumulative Distribution Functions

Martin Schafföner, Edin Andelic, Marcel Katz, Sven E. Krüger, Andreas WendemuthAISTATS 2007

Abstract

Kernel Density Estimation (KDE) is a vital tool for distribution modeling, yet it often suffers from high computational costs or excessive memory requirements. This paper introduces OROLS (Order-Recursive Orthogonal Least Squares), a memory-efficient algorithm for sparse KDE. By treating density estimation as a regression problem on the Empirical Cumulative Distribution Function (ECDF) and utilizing "thin" matrix updates, OROLS achieves state-of-the-art accuracy with significantly lower memory overhead and fewer model parameters than existing methods like $\epsilon$-SVD.

Introduction

Practitioners using KDE typically face a trade-off between the accuracy of dense models like Parzen Windows and the efficiency of sparse models like Gaussian Mixture Models (GMMs) or $\epsilon$-SVD. Dense models require every training sample for inference, while existing sparse models often rely on complex optimization or memory-intensive Gram matrices that scale quadratically ($O(N^2)$) with the number of samples. This paper addresses these limitations by proposing a recursive approach that minimizes memory usage while maintaining high sparsity.

Methodology

The proposed approach rests on two primary innovations: the OROLS algorithm and an enhanced ECDF sampling technique.

OROLS Algorithm

Instead of the standard approach of computing a full orthogonal decomposition of the kernel matrix, OROLS employs an order-recursive strategy. It updates the orthogonal decomposition matrices and the pseudo-inverse of the Gram matrix "on the fly" during the greedy selection of kernel centers. This "thin update" strategy allows the construction of a sparse model without ever storing the entire $N \times N$ matrix, reducing memory requirements from $O(SN + N^2)$ to approximately $O(3Sm + m^2/2)$, where $m \ll N$ is the number of selected centers.

Enhanced ECDF Sampling

Reframing density estimation as a regression on the ECDF requires evaluating the fit at specific points. "Naive" sampling at training data points often fails in multi-dimensional spaces as it misses the "staircase" jumps of the distribution. The authors implement an output-sensitive algorithm to identify additional "jump points," providing a richer target for regression.

Figure 1: Illustration of the Enhanced ECDF sampling strategy identifying jump points and regions in a 2D space.

Experimental Evaluation

The algorithm was tested on three benchmarks:

  1. Artificial 2D-Problem: A mixture of Gaussian and exponential distributions.
  2. Ripley Data Set: A classic 2D two-class classification problem (125 training samples).
  3. Thyroid Data Set (UCI): A 5-dimensional real-world dataset (140 training samples).

Key Results

OROLS demonstrated superior performance in both sparsity and accuracy across the test sets.

Sparsity and Accuracy on Ripley

On the Ripley dataset, OROLS with enhanced ECDF sampling achieved a lower error rate (8.5%) compared to $\epsilon$-SVD (9.8%). Crucially, it achieved this with far greater efficiency, using only 14 centers (7 per class) compared to the 128 centers required by $\epsilon$-SVD.

Figure 5: Performance comparison on the Ripley dataset. OROLS (Enhanced) achieves the best balance of low error and high sparsity (# centers).

High-Dimensional Performance

On the 5D Thyroid dataset, OROLS consistently outperformed $\epsilon$-SVD across various sampling densities. It produced more accurate models while requiring less than one-third of the samples used by other sparse methods.

Conclusion and Future Work

While OROLS significantly improves memory efficiency and sparsity, the "Curse of Dimensionality" remains a challenge for ECDF sampling. In 5D, the number of jump points can grow combinatorially, necessitating random sub-sampling. Future research will focus on scaling the algorithm to even higher dimensions and larger datasets, such as high-dimensional speech feature vectors.

Summary updated

BibTeX
@article{schaffoner2007memory,
  author = {Martin Schafföner and Edin Andelic and Marcel Katz and Sven E. Krüger and Andreas Wendemuth},
  title = {{Memory-Effcient Orthogonal Least Squares Kernel Density Estimation using Enhanced Empirical Cumulative Distribution Functions}},
  journal = {AISTATS},
  year = {2007},
}
Figure