Estimating the Unseen: Improved Estimators for Entropy and other Properties
Recently, Valiant and Valiant [1,2] 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, this 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 our 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.
Summary: The paper introduces an algorithm for 
      estimating the histogram of distributions where the exact size of the 
      support is unknown. From the histogram, properties such as the size of the 
      support and the entropy of the distribution can be derived. As input, the 
      algorithm takes the fingerprint of an IID sample (i.e., how many elements 
      occur with frequency 1, 2, 3, ...). It then solves two linear programs to 
      find the “simplest plausible” histogram that would have generated the 
      fingerprint, where plausibility is based on the assumption that the 
      instance frequencies are Poisson distributed and close to their expected 
      values. In Theorem 1, the authors show their algorithm learns the entropy 
      of distributions over finite domains with arbitrary precision. Experiments 
      in Sec. 3 show clear improvements over state-of-the-art algorithms, and 
      the application to estimating the number of different words in 
      Shakespeare's Hamlet from a text subsample. 
      Significance/Originality: The paper builds on work by Valiant 
      and Valiant, so the idea is not entirely new. However, the original 
      algorithm is modified to a two-stage linear program (aiming to find the 
      simplest plausible histogram instead of the most plausible one), and 
      experimental results on simulated and real data are provided. In the 
      supplementary material, the authors show improvements of their two-stage 
      program over the original algorithm by Valiant and Valiant. A few more 
      details in the discussion of these results would be helpful to assess the 
      significance, e.g., are the “quirks” in the performance of the original 
      estimator due to fitting too large histograms? Clarity/Quality: 
      Overall, the presentation of the methodology and results is very 
      clear; the authors provide many examples which help to develop intuition. 
      Some of the settings in Algorithm 1 appear a bit ad-hoc: - the 
      criterion for distinguishing between “easy” and “hard” fingerprints (line 
      239) - the choice of 1/sqrt(1+Fi) to penalize the discrepancy between 
      empirical/fitted fingerprints The paper provides some motivation for 
      the choice of the penalizer but, still, there would be many other choices. 
      Do the authors have any insights (empirical/theoretical) why their choices 
      are preferable? Another fact which strikes me is that Theorem 1 
      doesn't make any assumption on the vectors x=x1,...,xL. This would mean 
      the estimator is consistent even if one chooses the singleton list x=1. Is 
      this correct? It would be surprising, because in this case the output of 
      the two linear programs would be somewhat “trivial”. In their rebuttal, 
      the authors pointed out that there was a misunderstanding and said they 
      would put explicit conditions on the density of the grid x1,...,xL into 
      the final version of the paper (which were included before in the 
      supplementary material).