Estimating the Entropy of Binary Time Series: Methodology, Some Theory and a Simulation Study

Entropy - Tập 10 Số 2 - Trang 71-99
Yun Gao1, Ioannis Kontoyiannis2, Elie Bienenstock3
1Knight Equity Markets, L.P., Jersey City, NJ 07310, USA
2Department of informatics, Athens University of Economics and Business, Athens 10434, Greece
3Division of Applied Mathematics and Department of Neuroscience, Brown University, Providence, RI 02912, USA

Tóm tắt

Partly motivated by entropy-estimation problems in neuroscience, we present a detailed and extensive comparison between some of the most popular and effective entropy estimation methods used in practice: The plug-in method, four different estimators based on the Lempel-Ziv (LZ) family of data compression algorithms, an estimator based on the Context-Tree Weighting (CTW) method, and the renewal entropy estimator. METHODOLOGY: Three new entropy estimators are introduced; two new LZ-based estimators, and the “renewal entropy estimator,” which is tailored to data generated by a binary renewal process. For two of the four LZ-based estimators, a bootstrap procedure is described for evaluating their standard error, and a practical rule of thumb is heuristically derived for selecting the values of their parameters in practice. THEORY: We prove that, unlike their earlier versions, the two new LZ-based estimators are universally consistent, that is, they converge to the entropy rate for every finite-valued, stationary and ergodic process. An effective method is derived for the accurate approximation of the entropy rate of a finite-state hidden Markov model (HMM) with known distribution. Heuristic calculations are presented and approximate formulas are derived for evaluating the bias and the standard error of each estimator. SIMULATION: All estimators are applied to a wide range of data generated by numerous different processes with varying degrees of dependence and memory. The main conclusions drawn from these experiments include: (i) For all estimators considered, the main source of error is the bias. (ii) The CTW method is repeatedly and consistently seen to provide the most accurate results. (iii) The performance of the LZ-based estimators is often comparable to that of the plug-in method. (iv) The main drawback of the plug-in method is its computational inefficiency; with small word-lengths it fails to detect longer-range structure in the data, and with longer word-lengths the empirical distribution is severely undersampled, leading to large biases.

Từ khóa


Tài liệu tham khảo

Quastler, H. (1955). Information theory in psychology, Free Press.

Basharin, 1959, On a statistical estimate for the entropy of a sequence of independent random variables, Theor. Probability Appl., 4, 333, 10.1137/1104033

Grassberger, 1989, Estimating the information content of symbol sequences and efficient codes, IEEE Trans. Inform. Theory, 35, 669, 10.1109/18.30993

Shields, 1992, Entropy and prefixes, Ann. Probab., 20, 403, 10.1214/aop/1176989934

Kelly, F.P. (1994). Proba-bility Statistics and Optimization, Wiley.

Treves, 1995, The upward bias in measures of information derived from limited data samples, Neural Comput., 7, 399, 10.1162/neco.1995.7.2.399

Grassberger, 1996, Entropy estimation of symbol sequences, Chaos, 6, 414, 10.1063/1.166191

Kontoyiannis, I. (The complexity and entropy of literary styles, 1996). The complexity and entropy of literary styles, [Available from pages.cs.aueb.gr/users/yiannisk/].

Kontoyiannis, 1998, Nonparametric entropy estimation for stationary processes and random fields, with applications to English text, IEEE Trans. Inform. Theory, 44, 1319, 10.1109/18.669425

Darbellay, 1999, Estimation of the information by an adaptive partitioning of the observation space, IEEE Trans. Inform. Theory, 45, 1315, 10.1109/18.761290

Victor, 2000, Asymptotic Bias in Information Estimates and the Exponential (Bell) Polynomials, Neural Comput., 12, 2797, 10.1162/089976600300014728

Antos, 2001, Convergence properties of functional estimates for discrete distributions, Random Structures & Algorithms, 19, 163, 10.1002/rsa.10019

Paninski, 2003, Estimation of entropy and mutual information, Neural Comput., 15, 1191, 10.1162/089976603321780272

Cai, 2004, Universal entropy estimation via block sorting, IEEE Trans. Inform. Theory, 50, 1551, 10.1109/TIT.2004.830771

Brown, 1992, An estimate of an upper bound for the Entropy of English, Computational Linguistics, 18, 31

Chen, S., and Reif, J. (, 1993). Using difficulty of prediction to decrease computation: Fast sort, priority queue and convex hull on entropy bounded inputs. 34th Symposium on Foundations of Computer Science, Los Alamitos, California.

(, 1995). On the entropy of DNA: Algorithms and measurements based on memory and rapid convergence. Proceedings of the 1995 Sympos. on Discrete Algorithms.

Stevens, C., and Zador, A. (NIPS, 1995). Information through a Spiking Neuron, NIPS.

Teahan, W., and Cleary, J. (, 1996). The entropy of English using PPM-based models. Proc. Data Compression Conf. – DCC 96, Los Alamitos, California.

Strong, 1998, Entropy and Information in Neural Spike Trains, Phys. Rev. Lett., 80, 197, 10.1103/PhysRevLett.80.197

Suzuki, 1999, Information entropy of humpback whale song, The Journal of the Acoustical Society of America, 105, 1048, 10.1121/1.424990

Loewenstern, 1999, Significantly Lower Entropy Estimates for Natural DNA Sequences, Journal of Computational Biology, 6, 125, 10.1089/cmb.1999.6.125

Levene, 2000, Computing the entropy of user navigation in the web, International Journal of Information Technology and Decision Making, 2, 459, 10.1142/S0219622003000768

Reinagel, 2000, Information theory in the brain, Current Biology, 10, 542, 10.1016/S0960-9822(00)00609-6

London, 2002, The information efficacy of a synapse, Nature Neurosci., 5, 332, 10.1038/nn826

Bhumbra, 2004, Measuring spike coding in the rat supraoptic nucleus, The Journal of Physiology, 555, 281, 10.1113/jphysiol.2003.053264

Nemenman, W., Bialek, W., and de Ruyter van Steveninck, R. (2004). Entropy and information in neural spike trains: Progress on the sampling problem. Physical Review E, 056111.

Warland, 1997, Decoding visual infomation from a population of retinal ganglion cells, J. of Neurophysiology, 78, 2336, 10.1152/jn.1997.78.5.2336

Kennel, M., and Mees, A. (2002). Context-tree modeling of observed symbolic dynamics. Physical Review E, 66.

Wajnryb, 2004, Estimating the entropy rate of spike trains via Lempel-Ziv complexity, Neural Computation, 16, 717, 10.1162/089976604322860677

Shlens, 2007, Estimating information rates with confidence intervals in neural spike trains, Neural Comput., 19, 1683, 10.1162/neco.2007.19.7.1683

Gao, Y., Kontoyiannis, I., and Bienenstock, E. (, 2003). Lempel-Ziv and CTW entropy estimators for spike trains. Estimation of entropy Workshop, Neural Information Processing Systems Conference (NIPS), Vancouver, BC, Canada.

Gao, Y. (2004). Division of Applied Mathematics. [Ph.D. thesis, Brown University].

Gao, Y., Kontoyiannis, I., and Bienenstock, E. (2006). IEEE Int. Symp. on Inform. Theory.

Rieke, F., Warland, D., de Ruyter van Steveninck, R., and Bialek, W. (1999). Spikes, MIT Press. Exploring the neural code, Computational Neuroscience.

Ziv, 1977, A universal algorithm for sequential data compression, IEEE Trans. Inform. Theory, 23, 337, 10.1109/TIT.1977.1055714

Ziv, 1978, Compression of individual sequences by variable rate coding, IEEE Trans. Inform. Theory, 24, 530, 10.1109/TIT.1978.1055934

Willems, 1995, Context tree weighting: Basic properties, IEEE Trans. Inform. Theory, 41, 653, 10.1109/18.382012

Willems, 1996, Context weighting for general finite-context sources, IEEE Trans. Inform. Theory, 42, 1514, 10.1109/18.532891

Willems, 1998, The context-tree weighting method: Extensions, IEEE Trans. Inform. Theory, 44, 792, 10.1109/18.661523

Cover, T., and Thomas, J. (1991). Elements of Information Theory, J. Wiley.

Shields, P. (1996). The ergodic theory of discrete sample paths, American Mathematical Society.

Paninski, 2004, Estimating entropy on m bins given fewer than m samples, IEEE Trans. Inform. Theory, 50, 2200, 10.1109/TIT.2004.833360

Wyner, 1989, Some asymptotic properties of the entropy of a stationary ergodic data source with applications to data compression, IEEE Trans. Inform. Theory, 35, 1250, 10.1109/18.45281

Ornstein, 1993, Entropy and data compression schemes, IEEE Trans. Inform. Theory, 39, 78, 10.1109/18.179344

Pittel, 1985, Asymptotical growth of a class of random trees, Ann. Probab., 13, 414, 10.1214/aop/1176993000

Szpankowski, 1993, Asymptotic properties of data compression and suffix trees, IEEE Trans. Inform. Theory, 39, 1647, 10.1109/18.259648

Wyner, 1995, Improved redundancy of a version of the Lempel-Ziv algorithm, IEEE Trans. Inform. Theory, 35, 723, 10.1109/18.382018

Szpankowski, 1993, A generalized suffix tree and its (un)expected asymptotic behaviors, SIAM J. Comput., 22, 1176, 10.1137/0222070

Wyner, 1998, On the role of pattern matching in information theory. (Information theory: 1948–1998), IEEE Trans. Inform. Theory, 44, 2045, 10.1109/18.720530

Politis, 1994, The stationary bootstrap, J. Amer. Statist. Assoc., 89, 1303, 10.1080/01621459.1994.10476870

Barron, A. (1985). [Ph.D. thesis, Dept. of Electrical Engineering, Stanford University].

Kieffer, 1991, Sample converses in source coding theory, IEEE Trans. Inform. Theory, 37, 263, 10.1109/18.75241

Rissanen, J. (1989). Stochastic Complexity in Statistical Inquiry, World Scientific.

Yushkevich, 1953, On limit theorems connected with the concept of the entropy of Markov chains, Uspehi Mat. Nauk, 8, 177

Ibragimov, 1962, Some limit theorems for stationary processes, Theory Probab. Appl., 7, 349, 10.1137/1107036

Kontoyiannis, 1997, Second-order noiseless source coding theorems, IEEE Trans. Inform. Theory, 43, 1339, 10.1109/18.605604

Volf, P., and Willems, F. (, 1995). On the context tree maximizing algorithm. Proc. of the IEEE International Symposium on Inform. Theory, Whistler, Canada.

Ephraim, 2002, Hidden Markov processes, IEEE Trans. Inform. Theory, 48, 1518, 10.1109/TIT.2002.1003838

Jacquet, P., Seroussi, G., and Szpankowski, W. (, 2004). On the entropy of a hidden Markov process. Proc. Data Compression Conf. – DCC 2004, Snowbird, UT.

Papangelou, 1978, On the entropy rate of stationary point processes and its discrete approximation, Z. Wahrsch. Verw. Gebiete, 44, 191, 10.1007/BF00534210

Thông tin
Thông tin xuất bản

Entropy

Tập 10 Số 2

71-99

Thông tin tác giả