Estimating the Unseen: Improved Estimators for Entropy and other Properties

Paul Valiant, Gregory ValiantNeurIPS 2013 · OpenReview

This paper presents a breakthrough in statistical estimation, addressing a fundamental challenge in data science: how to accurately describe a population when you have only observed a tiny, biased fraction of it. Authored by Gregory Valiant and Paul Valiant, the research provides a theoretically optimal and practically superior method for estimating distributional properties—like entropy and the number of unique elements—using "sublinear" samples.

The Challenge of Sublinear Sampling

Imagine a linguist trying to estimate the total vocabulary of a language based on a single book, or a geneticist hunting for rare mutations in a small population sample. In these scenarios, the sample size is vastly smaller than the total number of possible outcomes. Many items will appear only once, and a massive portion of the underlying distribution will remain entirely unseen.

Standard "plug-in" estimators, which assume the sample perfectly represents the whole, fail miserably in these conditions. They consistently underestimate entropy and the number of distinct elements because they are "blind" to what they haven't observed. While existing tools like the Good-Turing frequency estimator can calculate the total probability mass of unseen items, they cannot reveal the distribution or "shape" of those items. This paper fills that critical gap.

Methodology: Reconstructing the Unseen

The core innovation is a two-step approach utilizing Linear Programming (LP) to characterize the unobserved portion of a distribution.

  1. The Fingerprint: Instead of tracking specific labels (e.g., the specific word "apple"), the algorithm analyzes the fingerprint of the sample—a histogram of frequencies. It asks questions like, "How many unique items appeared exactly once? How many appeared twice?"
  2. Linear Programming (LP):
    • LP 1 (Plausibility): The method searches for a "plausible" hidden distribution that, if sampled, would likely produce the exact fingerprint observed. It does this by minimizing the discrepancy between the expected fingerprint of a candidate distribution and the actual observed data.
  3. LP 2 (Simplicity/Occam’s Razor): Among all plausible distributions, the algorithm selects the "simplest" one—specifically, the one with the smallest support size. This acts as a powerful regularizer, preventing the model from inventing unnecessary complexity to explain random noise in the sample.
  4. Hybrid Approach: Finally, the algorithm splits the data. It relies on standard empirical estimates for "easy" items (those that appear frequently) and deploys the LP approach for "hard" items (rare or unseen ones).

Experimental Results

The authors evaluated their "Unseen" estimator against several benchmarks, including the Naive estimator, Miller-Madow, Jackknife, the Coverage Adjusted Estimator (CAE), and Paninski’s Best Upper Bound (BUB).

Synthetic Benchmarks

The method was tested on six different types of synthetic distributions, including Uniform, Zipf (power-law), and Geometric distributions, with support sizes ($n$) ranging from 1,000 to 100,000.

RMSE across synthetic distributions

In almost every synthetic test, the Unseen estimator demonstrated significantly lower Root Mean Squared Error (RMSE) than all other estimators. Its performance advantage became especially pronounced as the sample size grew toward the theoretical $O(n/\log n)$ threshold.

The Hamlet Test

To test the estimator on real-world data, the authors used fragments of Shakespeare’s Hamlet to estimate the total number of distinct words in the entire play.

Estimating Hamlet's vocabulary

Using only a 10% fragment of the text, the Unseen estimator predicted the total vocabulary (4,268 words) with remarkable accuracy. It converged on the true value much faster and more reliably than the CAE and Naive estimators.

Distinguishing Distributions

The authors also extended the method to estimate the $L_1$ distance (statistical distance) between two distributions. They successfully distinguished between identical and different distributions even when the samples were so small that they shared almost no overlapping elements.

Key Insights and Limitations

The success of the Unseen estimator relies on a few core theoretical insights:

  • Characterizing the Shape: You do not need to know what the unseen elements are to accurately estimate how many there are and how they are distributed.
  • Sublinear Scaling: The paper proves that for a distribution with $n$ elements, a sample size of only $O(n / \log n)$ is required for an accurate estimate, a massive improvement over the $O(n)$ samples traditionally deemed necessary.
  • Symmetry: The method works for "symmetric" properties—metrics that don't change if you swap element labels (like entropy). This allows the algorithm to discard labels entirely and work solely with the fingerprint.

Limitations: While highly accurate, the method is more computationally intensive than simple plug-in formulas due to the reliance on Linear Programming. Additionally, the theoretical guarantees assume independent draws. In real-world sequential data (like the words in Hamlet), elements are often correlated, which can introduce a slight negative bias. Future work may explore models that account for these temporal or contextual dependencies, as well as methods for automating the probability "mesh" selection used in the LP for highly skewed distributions.

Summary updated

Abstract

Recently, [Valiant and Valiant] showed that a class of distributional properties, which includes such practically relevant properties as entropy, the number of distinct elements, and distance metrics between pairs of distributions, can be estimated given a SUBLINEAR sized sample. Specifically, given a sample consisting of independent draws from any distribution over at most n distinct elements, these properties can be estimated accurately using a sample of size O(n / log n). We propose a novel modification of this approach and show: 1) theoretically, our estimator is optimal (to constant factors, over worst-case instances), and 2) in practice, it performs exceptionally well for a variety of estimation tasks, on a variety of natural distributions, for a wide range of parameters. Perhaps unsurprisingly, the key step in this approach is to first use the sample to characterize the unseen" portion of the distribution. This goes beyond such tools as the Good-Turing frequency estimation scheme, which estimates the total probability mass of the unobserved portion of the distribution: we seek to estimate the "shape"of the unobserved portion of the distribution. This approach is robust, general, and theoretically principled; we expect that it may be fruitfully used as a component within larger machine learning and data analysis systems. "
BibTeX
@inproceedings{valiant2013estimating,
  author = {Paul Valiant and Gregory Valiant},
  title = {{Estimating the Unseen: Improved Estimators for Entropy and other Properties}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2013},
  url = {https://openreview.net/forum?id=B1-n1ObdbS},
}
Figure