Multiscale likelihood analysis and complexity penalized estimation

Eric D. Kolaczyk, Robert D. NowakarXiv 2004 · DOI · arXiv

TL;DR

This paper introduces a "Multiresolution Analysis (MRA) for likelihoods," providing a unified mathematical framework to apply wavelet-style multiscale analysis to non-Gaussian data. By factoring likelihood functions into localized components, the authors develop estimators for Poisson and multinomial data that are as adaptive and near-optimal as classical wavelet denoising is for Gaussian signals.

What Problem Does This Paper Address?

In the 1990s, wavelet-based methods revolutionized signal processing because they could efficiently handle "inhomogeneous" objects—signals with sharp spikes or varying smoothness. However, most of that success was built on the Gaussian "signal-plus-noise" model.

When researchers tried to apply wavelets to other common data types—like Poisson counts in medical imaging or multinomial categories in remote sensing—they hit a wall. Simply applying a standard wavelet transform to this data often leads to mathematically "messy" expressions that are hard to interpret and computationally expensive. The authors tackle this by asking: Can we build a multiscale structure directly into the likelihood function itself, rather than just transforming the data?

Methods

The authors propose a set of four conditions (labeled A through D) that allow a likelihood function to be factored into a product of conditional densities. This is essentially a "probabilistic wavelet transform."

Key components include:

  • Likelihood Factorization: They show that for certain distributions, the total likelihood can be broken down into a product of terms representing information at different scales and positions.
  • Complexity Penalized Estimation: They define estimators that minimize a cost function: Total Cost = -log(Likelihood) + 2 * Penalty. The penalty is proportional to the number of "nontrivial" multiscale coefficients used, effectively encouraging "sparse" models that don't overfit.
  • Three Estimator Types:
    1. Thresholding (T): Similar to wavelet hard-thresholding.
  • Recursive Dyadic Partitioning (RDP): A multiscale approach similar to a restricted version of the CART (Classification and Regression Trees) algorithm.
  • Recursive Partitioning (RP): A more flexible, generalized version of RDP.
  • Algorithms: They provide efficient ways to compute these: $O(N)$ for thresholding and RDP, and $O(N^3)$ for general recursive partitioning.

Datasets

This is a theoretical and methodological paper. It does not use specific real-world empirical datasets for benchmarking. Instead, it evaluates the proposed methods using:

  • Mathematical Models: Canonical models for Gaussian (continuous), Poisson (count), and Multinomial (categorical) data.
  • Function Spaces: Theoretical "smoothness classes" like Bounded Variation (BV) and Besov spaces, which are standard benchmarks for proving how well an estimator performs across different types of signals.

Key Insights and Ideas

  • The Unified Framework: The most powerful insight is that the same mathematical "machinery" can handle continuous, count, and categorical data. The "detail" captured by a wavelet coefficient in a Gaussian model is mirrored by a "ratio" of counts in a Poisson or Multinomial model.
  • Homogeneity as Sparsity: In standard wavelets, a smooth signal results in many zero coefficients (sparsity). In this framework, a smooth signal results in multiscale ratios that match the "default" proportions of the bins, allowing the penalty term to "kill" unnecessary complexity.
  • Hellinger Distance: The authors use the squared Hellinger distance as a loss function. This choice is crucial because it provides a common "yardstick" to measure error across different probability families, enabling a unified proof of optimality.

Key Results

  • Minimax Near-Optimality: The authors prove that their estimators are "near-optimal" in a minimax sense. This means that for a wide range of possible signals, no other estimator can perform significantly better.
  • Risk Bounds: For signals of Bounded Variation, the risk (error) for the thresholding and RP estimators is bounded by $O((\log N/N)^{2/3})$.
  • Adaptivity: The estimators are "adaptive," meaning they automatically perform well regardless of the underlying smoothness of the signal, without the researcher needing to tune parameters for a specific smoothness level beforehand.

Limitations and Future Work

  • Haar-only Basis: The current framework is essentially an "unbalanced Haar" approach. It works best for piecewise-constant signals. Extending this to "smoother" wavelets (like Daubechies wavelets) to better estimate very smooth functions is noted as a "much more difficult problem."
  • Independence Assumptions: The framework relies on certain independence conditions (like L-independence) to allow for clean factorization. Relaxing these conditions to handle more complex, correlated data structures remains an open question.
  • Computational Scaling: While $O(N)$ is great, the $O(N^3)$ complexity for general recursive partitioning might become a bottleneck for extremely large multi-dimensional datasets (like high-res 3D video).

Summary updated

Abstract

We describe here a framework for a certain class of multiscale likelihood factorizations wherein, in analogy to a wavelet decomposition of an L^2 function, a given likelihood function has an alternative representation as a product of conditional densities reflecting information in both the data and the parameter vector localized in position and scale. The framework is developed as a set of sufficient conditions for the existence of such factorizations, formulated in analogy to those underlying a standard multiresolution analysis for wavelets, and hence can be viewed as a multiresolution analysis for likelihoods. We then consider the use of these factorizations in the task of nonparametric, complexity penalized likelihood estimation. We study the risk properties of certain thresholding and partitioning estimators, and demonstrate their adaptivity and near-optimality, in a minimax sense over a broad range of function spaces, based on squared Hellinger distance as a loss function. In particular, our results provide an illustration of how properties of classical wavelet-based estimators can be obtained in a single, unified framework that includes models for continuous, count and categorical data types.
BibTeX
@misc{kolaczyk2004multiscale,
  author = {Eric D. Kolaczyk and Robert D. Nowak},
  title = {{Multiscale likelihood analysis and complexity penalized estimation}},
  year = {2004},
  eprint = {math/0406424},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/math/0406424},
}
Figure