Search papers, labs, and topics across Lattice.
This paper introduces a new Bayesian estimator for probability estimation over large alphabets, characterized by its simplicity and efficiency. The method involves multiplying independent uniform draws from the probability simplex and renormalizing, with depth as the sole structural parameter, which eliminates the need for tuning. Remarkably, the estimator demonstrates competitive performance against established methods like Good-Turing across various benchmarks, while also providing explicit expressions for regret that reveal scaling laws related to data and alphabet size.
A new Bayesian estimator achieves competitive performance with established methods while being remarkably simple and tuneless, revealing critical scaling laws in data discovery.
Probability estimation over large alphabets under log loss is a well-studied problem, with celebrated methods such as the Good-Turing estimator. We introduce and study a new Bayesian estimator with four notable properties. First, its construction is exceptionally simple: multiply independent uniform draws from the probability simplex coordinate-wise and renormalize. Depth is the only structural parameter, and averaging over depths eliminates the need to tune it. Second, the regret of the resulting mixture, the excess code length it pays relative to a code that knows the source, admits an explicit and efficiently computable expression. Third, despite its simplicity and lack of tuned constants, the estimator is competitive across a diverse set of synthetic and real-text benchmarks with substantially more specialized methods, including Good-Turing. Fourth, the tractability of its regret allows us to identify scaling laws in data, alphabet size, and depth. For Zipf targets with exponent above one, the regret has a simple reading as long as the sample reveals only a small fraction of the alphabet. It closely matches the description length of the set of discovered symbols, at one bit of code per bit of description, plus a further cost per symbol. The data exponent is therefore the rate at which new symbols are discovered.
