High-Dimensional Density Ratio Estimation with Extensions to Approximate Likelihood Computation

Rafael Izbicki, Ann B. Lee, Chad SchaferAISTATS 2014 · OpenReview

Estimating the ratio between two probability densities—$\beta(\mathbf{x}) = f(\mathbf{x})/g(\mathbf{x})$—is a fundamental task in machine learning. It’s the engine behind transfer learning, novelty detection, and correcting selection bias. However, when your data lives in high-dimensional space (like images or complex sensor data), traditional methods hit a wall known as the "curse of dimensionality."

In this paper, Rafael Izbicki and colleagues from Carnegie Mellon University introduce a nonparametric "spectral series" approach that bypasses the need for lossy dimension reduction by adapting to the intrinsic geometry of the data.

TL;DR

The authors propose a new method for density ratio estimation that expands the ratio into a series of eigenfunctions derived from the data itself. By using these data-driven basis functions, the model naturally adapts to low-dimensional structures (like manifolds) hidden in high-dimensional spaces, outperforming standard techniques in both density ratio estimation and likelihood-free inference.

What Problem Does This Paper Address?

Most density ratio estimators struggle when the input $\mathbf{x}$ is high-dimensional. To cope, researchers usually perform an explicit dimension reduction step (like PCA) before estimation. The problem? This often throws away the very information needed to distinguish between the two distributions.

Furthermore, the authors tackle the "likelihood-free inference" problem. In many scientific fields (like astronomy or genetics), we have complex simulators that can generate data, but we don't have an analytical formula for the likelihood function $f(\mathbf{x}|\theta)$. Estimating this likelihood is essentially a density ratio problem, and doing it accurately in high dimensions is notoriously difficult.

Methods

The core innovation is the Spectral Series Estimator. Instead of using a fixed basis (like a standard Fourier series), the authors use a kernel-based operator to find eigenfunctions $\{\psi_j\}$ that are orthonormal with respect to one of the distributions ($G$).

  1. Basis Construction: They compute the top $J$ eigenvectors of a Gram matrix based on a sample from $G$. These functions act as a "Fourier-like" basis that is custom-fit to the geometry of the data (e.g., if the data lies on a spiral, the basis functions follow that spiral).
  2. Expansion: They expand the ratio $\beta(\mathbf{x})$ as a linear combination of these eigenfunctions.
  3. Coefficient Estimation: Because of the orthogonality property, the coefficients $\beta_j$ can be estimated simply by averaging the eigenfunctions over the samples from the other distribution ($F$).
  4. Likelihood Extension: For likelihood estimation, they use a tensor product basis. They create one basis for the data space $\mathbf{x}$ and another for the parameter space $\theta$, allowing them to estimate $L(\mathbf{x}; \theta)$ as a ratio of the conditional density to the marginal density.

Datasets

The authors evaluated their method on a mix of synthetic "manifold" data and high-dimensional image data:

  • Spiral (2D): Data lying on a 1D spiral.
  • Klein Bottle (4D): Data lying on a 2D surface embedded in 4D.
  • Transformed Images (400D): $20 \times 20$ pixel images of a tiger, rotated and translated.
  • Binary Edges (400D): $20 \times 20$ images of edges with varying rotations and displacements.
  • Simulated Galaxy Images (400D): Realistic, noisy galaxy images used for astronomical shear estimation.
  • SDSS Data: Real-world astronomical data from the Sloan Digital Sky Survey used for photometric redshift prediction.

Key Insights and Ideas

  • Geometry Matters: Traditional methods treat all dimensions equally. The spectral approach recognizes that high-dimensional data often has a much lower "intrinsic" dimensionality. By using eigenfunctions of a kernel operator, the estimator "travels" along the data manifold.
  • Orthogonality is a Superpower: By ensuring the basis is orthonormal with respect to the "denominator" distribution $G$, the math simplifies significantly. Estimating coefficients becomes a simple empirical average, making the implementation fast and stable.
  • No More PCA Pre-processing: Unlike other methods that require PCA to reduce dimensions first, this method uses the kernel to capture the structure implicitly. In the galaxy image experiments, the spectral method outperformed "PCA + Least Squares" because it didn't discard subtle but important features during a separate reduction step.

Key Results

  • Superior Performance in High-D: In the 400-dimensional image experiments (Tiger, Edges, Galaxies), the Series estimator consistently achieved the lowest $L^2$ loss compared to Kernel Density Estimation (KDE) and Least Squares (LS) methods.
  • Likelihood Recovery: In the galaxy simulation, the spectral series estimator was the only one that accurately recovered the "True" likelihood surface for parameters like orientation and axis ratio, even with noisy, low-resolution images.
  • Redshift Prediction: On real SDSS data, the method provided better "importance weights" for correcting selection bias, leading to more accurate galaxy redshift predictions than standard astronomical k-nearest neighbor (KNN) approaches.

Limitations and Future Work

  • Kernel Selection: The performance still depends on the choice of the kernel (e.g., the Gaussian kernel bandwidth). While the authors use cross-validation, choosing the "right" kernel for very complex data remains an art.
  • Computational Scaling: While the Nyström extension helps, calculating the eigendecomposition of a large Gram matrix can be computationally expensive for massive datasets. The authors suggest parallelization and more advanced matrix decomposition techniques as future directions.
  • Positivity Constraint: The series expansion doesn't inherently guarantee that the estimated ratio is positive (though they use a simple truncation $(\cdot)_+$ to handle this). More sophisticated ways to enforce positivity could improve results.

Summary updated

Abstract

The ratio between two probability density functions is an important component of various tasks, including selection bias correction, novelty detection and classification. Recently, several estimators of this ratio have been proposed. Most of these methods fail if the sample space is high-dimensional, and hence require a dimension reduction step, the result of which can be a significant loss of information. Here we propose a simple-to-implement, fully nonparametric density ratio estimator that expands the ratio in terms of the eigenfunctions of a kernel-based operator; these functions reflect the underlying geometry of the data (e.g., submanifold structure), often leading to better estimates without an explicit dimension reduction step. We show how our general framework can be extended to address another important problem, the estimation of a likelihood function in situations where that function cannot be well-approximated by an analytical form. One is often faced with this situation when performing statistical inference with data from the sciences, due the complexity of the data and of the processes that generated those data. We emphasize applications where using existing likelihood-free methods of inference would be challenging due to the high dimensionality of the sample space, but where our spectral series method yields a reasonable estimate of the likelihood function. We provide theoretical guarantees and illustrate the effectiveness of our proposed method with numerical experiments.
BibTeX
@inproceedings{izbicki2014high,
  author = {Rafael Izbicki and Ann B. Lee and Chad Schafer},
  title = {{High-Dimensional Density Ratio Estimation with Extensions to Approximate Likelihood Computation}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2014},
  url = {https://openreview.net/forum?id=qK31fz3DoR},
}
Figure