Research map / Learning theory and algorithms / Sample complexity
How Much is Unseen Depends Chiefly on Information About the Seen
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives an exact expression for the expected missing mass in terms of frequency-of-frequencies and uses a genetic algorithm to search over unbiased-ish representations, yielding distribution-specific estimators with lower MSE than Good-Turing.
Problem
Estimating the missing probability mass (mass of unseen classes/elements) from a random sample of a multinomial distribution; the Good-Turing estimator is biased and its MSE is not minimized for the specific distribution.
Approach
Exact identity expressing the expected total probability mass as an alternating sum of expected frequencies-of-frequencies (no Poisson approximation), which yields a large space of nearly unbiased estimator representations; a genetic algorithm searches this space for the representation minimizing an estimated MSE on the given sample.
Key results
- The evolved estimator has lower MSE than Good-Turing in over 93% of runs at n=2S, with MSE ratio 76-87% of Good-Turing on average across distributions (S=100).
- The minimal-bias estimator has bias that decays exponentially in n, far smaller than Good-Turing's bias across all six distributions.
- On the Shakespeare data, evolved MSE is 3.0e-3, 2.1e-3, 8.8e-4 vs Good-Turing 4.2e-3, 2.6e-3, 9.0e-4 for n=100, 200, 500.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the genetic algorithm to discover a distribution-specific missing-mass estimator instead of the Good-Turing estimator | Missing-mass estimation · Six multinomial distributions, S=100, n=S/2 to 2S | MSE: Avg. Ratio: 76% at n=S/2; 79% at n=S; 87% at n=2S; success rate 0.93 at n=S and n=2S | Helped |
| Use the minimal-bias estimator instead of Good-Turing | Missing-mass and total-mass estimation · Six multinomial distributions; missing mass as a function of n and total mass for k=0 to n=2000 | Bias: by thousands of orders of magnitude | Helped |
| Adapt an evolved estimator trained at sample size n to a larger sample | Evolved missing-mass estimator · Extended samples X^{cn}, c in {2, 5, 10} | MSE ratio to Good-Turing: 0.91 and 1.00 | Mixed |
| Apply an estimator discovered on one distribution to a different target distribution | Evolved missing-mass estimator · Cross-distribution evaluation | MSE: A12> 0.95 | Hurt |
| Use the evolved estimator rather than Good-Turing | Australian population-data-by-region missing-mass estimation, S=104, n=50 · Australian population-data-by-region | MSE: 25% of the MSE of GT | Helped |
| Use the evolved estimator rather than Good-Turing | Shakespeare missing-mass estimation, S=935 · Shakespeare, n = <100, 200, 500> | MSE: <3.0\!\times\!10^{-3}, 2.1\!\times\!10^{-3}, 8.8\!\times\!10^{-4}> vs <4.2\!\times\!10^{-3}, 2.6\!\times\!10^{-3}, 9.0\! | Helped |
| Use the minimal-bias estimator rather than Good-Turing | Missing-mass estimation for uniform distribution · Uniform, S=1000, n=2000 | Bias: (S-1)^{n-1}/S^n; (-1)^n/S^n | Helped |
| Use the minimal-bias estimator rather than Good-Turing | Missing-mass estimation · Uniform distribution, three sample sizes n | MSE | No clear effect |
Surprising findings
- The minimal-bias estimator has much higher variance, so its MSE is roughly equal to Good-Turing's; bias reduction alone does not reduce MSE.
- Estimators evolved on one distribution can perform poorly on another, with large variance increases.
Limitations
- MSE is estimated using a plug-in approximated distribution, so the fitness function is itself approximate and can overfit
- Adapted estimators to larger samples are not guaranteed to be MSE-optimal and degrade for the uniform distribution
- Quadratic programming alternative is O(n^4) per evaluation and impractical for large n
Experimental setup
Datasets: Australian population-data-by-region dataset Shakespeare dataset
Benchmarks: simulated multinomial distributions (S=100, 200) Australian population-data-by-region Shakespeare player frequency
Metrics: bias variance mean squared error Vargha-Delaney A12 success rate MSE ratio
Baselines: Good-Turing estimator minimal-bias estimator
Builds on: Good-Turing estimator Chao's species richness estimator Orlitsky et al. natural estimators
Closest papers by meaning
- Random features models: a way to study the success of naive imputation (ICML 2024 · similarity 0.83)
- Distribution Shift in Missing Data Imputation: A Risk-Based Perspective and Importance-Weighted Correction under MAR (NeurIPS 2026 · similarity 0.82)
- Naive Bayes Classifiers over Missing Data: Decision and Poisoning (ICML 2024 · similarity 0.82)
- Prediction models that learn to avoid missing values (ICML 2025 · similarity 0.82)
- Score Matching with Missing Data (ICML 2025 · similarity 0.82)
- What Does It Take to Build a Performant Selective Classifier? (NeurIPS 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.