Approximating entropy from sublinear samples

ABSTRACT

We consider the problem of approximating the entropy of a discrete distribution P on a domain of size q, given access to n independent samples from the distribution. It is known that n ≥ q is necessary, in general, for a good additive estimate of the entropy. A problem of multiplicative entropy estimate was recently addressed by Batu, Dasgupta, Kumar, and Rubinfeld. They show that n = qα suffices for a factor-α approximation, α > 1.

We introduce a new parameter of a distribution--its effective alphabet size qef(P). This is a more intrinsic property of the distribution depending only on its entropy moments. We show qef ≤ Õ(q). When the distribution P is essentially concentrated on a small part of the domain qef ≪ q. We strengthen the result of Batu et al. by showing it holds with qef replacing q.

This has several implications. In particular the rate of convergence of the maximum-likelihood entropy estimator (the empirical entropy) for both finite and infinite alphabets is shown to be dictated by the effective alphabet size of the distribution. Several new, and some known, facts about this estimator follow easily.

Our main result is algorithmic. Though the effective alphabet size is, in general, an unknown parameter of the distribution, we give an efficient procedure, with access to the alphabet size only, that achieves a factor-α approximation of the entropy with n = Õ (exp {α ^1/4 · log^3/4 q · log^1/4 qef}). Assuming (for instance) log qef ≪ log q this is smaller than any power of q. Taking α → 1 leads in this case to efficient additive estimates for the entropy as well. In particular, this result shows that for many natural scenarios, a tight estimation of the entorpy may be achieved using a sub-linear sample.

Several extensions of the results above are discussed.

REFERENCES

• 1: András Antos , Ioannis Kontoyiannis, Convergence properties of functional estimates for discrete distributions, Random Structures & Algorithms, v.19 n.3-4, p.163-193, October-December 2001 [doi>10.1002/rsa.10019]
• 2: Tuǧkan Batu , Sanjoy Dasgupta , Ravi Kumar , Ronitt Rubinfeld, The complexity of approximating entropy, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510005]
• 3: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 4: B. Efron and C. Stein. The jackknife estimate of variance. Ann. Stat., 9(3):586--596, 1981.
• 5: P. Grassberger. Entropy estimates from insufficient samplings, E-print physics/0307138, July 2003.
• 6: C. Haixiao, S. R. Kulkarni, and S. Verdu. Universal entropy estimation via block sorting. IEEE Transactions on Information Theory, 50, July, 2004.
• 7: C. McDiarmid. Surveys in Combinatorics, chapter On the method of bounded differences, pages 148--188. Cambridge University Press, 1989.
• 8: G. Miller. Information theory in Psychology, chapter II-B: Note on the bias of information estimates, pages 95--100. Glencoe IL: Free Press, 1955.
• 9: I. Nemenman, W. Bialek, and R. de Ruyter van Steveninck. Entropy and information in neural spike trains: Progress on the sampling problem. Phys. Rev. E, 69, 2004.
• 10: Liam Paninski, Estimation of entropy and mutual information, Neural Computation, v.15 n.6, p.1191-1253, June 2003 [doi>10.1162/089976603321780272]
• 11: L. Paninski. Estimating entropy on m bins given fewer than m samples. IEEE Transactions on Information Theory, 50, 2004.
• 12: S. Strong, R. Koberle, R. de Ruyter van Steveninck, and W. Bialek. Entropy and information in neural spike trains. Phys. Rev. Let., 80(1), 1998.
• 13: A. Wyner and D. Foster. On the lower limits of entropy estimation. Submitted to IEEE Transactions on Information Theory.
• 14: M. Brautbar and A. Samorodnitsky. Approximating the entropy of large alphabets. Technical report, ECCC, 084, 2005.