Redundancy of exchangeable estimators

Narayana P. Santhanam, Mokshay M. Madiman, Anand D. SarwateAllerton 2010 · DOI · OpenReview

TL;DR

This paper investigates the "redundancy" of Bayesian estimators for sequences with unknown, potentially infinite alphabets. The authors show that popular Bayesian methods like the Chinese Restaurant Process (CRP) and Pitman-Yor (PY) estimators are not "strongly universal" in this setting, meaning they don't perform optimally across all possible data distributions. However, they demonstrate that a mixture of CRP estimators can achieve "weak universality," offering a path towards more robust Bayesian inference in complex scenarios.

What Problem Does This Paper Address?

In many real-world applications, like language modeling or DNA analysis, we deal with sequences of data where the set of possible symbols (the alphabet) can be very large, even infinite, and often unknown beforehand. Estimating the underlying probability distribution of these sequences is crucial. Bayesian methods, which use prior beliefs to guide estimation, are a popular approach. However, a key question is how well these Bayesian estimators perform compared to an ideal, "universal" estimator that would work well regardless of the true underlying distribution.

This paper focuses on a specific measure of performance called "redundancy," which quantifies how much information is lost when using an estimator compared to the true distribution. The authors are interested in whether Bayesian estimators, particularly those based on exchangeable random partitions (like CRP and PY), can achieve "strong universality" – meaning they perform well across all possible distributions – or at least "weak universality" – performing well on average for any given distribution. They aim to understand the trade-offs and limitations of these Bayesian approaches from an information-theoretic perspective.

Methods

The paper frames the problem of estimating distributions over sequences with unknown alphabets within the context of universal compression. The core idea is to relate the performance of estimators to their "redundancy," which is a measure of how much extra information is needed to describe the data using the estimator compared to the true distribution.

Key techniques include:

  • Pattern-based representation: Instead of dealing with raw sequences, the authors work with "patterns" of sequences, which capture the relative order of appearance of symbols. This simplifies the problem by abstracting away the specific identities of the symbols.
  • Redundancy measures: They define and analyze two types of redundancy:
  • Worst-case redundancy: The maximum redundancy over all possible patterns for a given sequence length.
  • Average-case redundancy: The expected redundancy averaged over all possible sequences generated by a true distribution.
  • Exchangeable Random Partitions: The paper leverages concepts from exchangeable random partitions, specifically the Chinese Restaurant Process (CRP) and the Pitman-Yor (PY) process. These processes define priors over distributions on potentially infinite alphabets.
  • Mixture Estimators: To achieve weak universality, the authors construct a "mixture" of CRP estimators. This involves combining multiple CRP estimators, each tuned to different assumptions about the data, to create a more robust overall estimator.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and does not use specific datasets for evaluation.

Key Insights and Ideas

  • Bayesian estimators are not universally optimal: The paper's central finding is that standard Bayesian estimators like CRP and PY, while useful in practice, are not "strongly universal." This means they are tuned to specific types of data distributions and don't guarantee optimal performance across all possible distributions, especially when the alphabet size can be arbitrarily large.
  • Patterns simplify analysis: By focusing on "patterns" of sequences rather than the raw symbols, the authors can abstract away the complexity of unknown alphabets and analyze the core structure of the data.
  • Redundancy as a performance metric: Redundancy provides a principled information-theoretic way to measure the "frequentist" performance of Bayesian estimators, bridging the gap between Bayesian modeling and compression theory.
  • Weak universality is achievable: While strong universality is out of reach for these estimators, the paper shows that a carefully constructed mixture of CRP estimators can achieve "weak universality." This means the estimator performs well on average for any given data distribution, even if it's not optimal in the worst-case scenario.
  • Pitman-Yor offers some advantage: The Pitman-Yor estimator shows slightly better redundancy bounds than the CRP estimator when the number of distinct symbols is small, suggesting it might be more efficient in certain scenarios.

Key Results

  • CRP and PY are not strongly universal: The worst-case and average-case redundancies for CRP and PY estimators scale linearly with sequence length ($O(n)$) or worse ($\Omega(n \log n)$ for CRP in some cases), which is not sublinear and thus not strongly universal.
  • Pitman-Yor is better for small alphabets: For patterns with a number of distinct symbols $m$ that is small relative to the sequence length $n$ (e.g., $m = o(n)$), the Pitman-Yor estimator has a redundancy of $O(n)$, which is better than the $\Omega(n \log n)$ lower bound for CRPs.
  • Mixture of CRPs achieves weak universality: The paper constructs a mixture of CRP estimators that is weakly universal, meaning its average-case redundancy is $o(n)$ for any discrete i.i.d. process with finite entropy. This is a significant result, showing that a form of universal performance can be achieved by combining these Bayesian models.

Limitations and Future Work

  • Mixture estimator is not a single CRP/PY: The weakly universal estimator constructed is a mixture of CRP estimators, not a single CRP or PY estimator itself. This means it's not directly using a single Bayesian model but a combination.
  • Dependence on entropy and distinct symbols: The weak universality of the mixture estimator depends on the entropy of the source and the number of distinct symbols in the sample.
  • Predicting future performance: Predicting the performance of the mixture estimator for longer sequences (larger $N$) based on shorter samples (size $n$) is challenging, especially when the number of distinct symbols can grow unpredictably. The paper highlights an example where distinguishing between distributions is impossible with high probability even for large sample sizes.
  • Future work directions:
    • Investigating how to predict the number of distinct symbols in longer samples by imposing restrictions on the class of distributions.
  • Borrowing from "data-derived consistency formulations" to characterize when prediction of future symbol counts is possible.
  • Finding the unknown prior that corresponds to the near-optimal $O(n)$ redundancy estimator mentioned in the paper, which could lead to new classes of priors beyond Poisson-Dirichlet.

Summary updated

Abstract

Exchangeable random partition processes provide a framework for statistical inference in large alphabet scenarios from a Bayesian perspective. On the other hand, the notion of the pattern of a sequence provides a framework for data compression in large alphabet scenarios. Owing to the relationship between data compression and parameter estimation, both these approaches are related. Motivated by the possibilities of cross-fertilization, we examine the redundancy of Bayes estimators (specifically those that emerge from the “Chinese restaurant processes”) in the setting of unknown discrete alphabets from a universal compression point of view. In particular, we identify relations between alphabet sizes and sample sizes where the redundancy is small- and hence, characterize useful regimes for these estimators.
BibTeX
@inproceedings{santhanam2010redundancy,
  author = {Narayana P. Santhanam and Mokshay M. Madiman and Anand D. Sarwate},
  title = {{Redundancy of exchangeable estimators}},
  booktitle = {Allerton},
  year = {2010},
  doi = {10.1109/allerton.2010.5707041},
}
Figure