We are considering publishing the workshop proceedings, and we welcome inquries from potential contributors, even if they did not present at the workshop.

Organizers:

• William Bialek, Department of Physics, Princeton University.
• Ilya Nemenman, Kavli Institute for Theoretical Physics, University of California at Santa Barbara (contact organizer).

Summary: This was the original workshop proposal and the schedule.

Workshop speakers: Ilya Nemenman (UCSB), Liam Paninski (NYU), Jose Costa (Ann Arbor), Ronitt Rubinfeld (NEC Labs America), Jonathan Victor (Cornell), William Bialek (Princeton), Jon Shlens (UCSD), Yun Gao (Brown), Pamela Reinagel (UCSD), Gal Chechik (Stanford).

More information about the talks:

Ilya Nemenman. Entropy estimation: A general overview.

Abstract: I will introduce the problem of entropy and mutual information estimation for continuous and discrete variables and give a brief classification of different approaches to the problem, emphasizing their similarities rather than differences. I will spend time on "negative results" that seem to hopelessly limit any successes we might have with this problem, and then I will point out some cases where these bounds are violated. Understanding these cases may bring some hope back, and it will lead me to making suggestions about the properties that entropy and mutual information estimators must posses in various regimes (oversampled, undersampled, and extremely undersampled).

Liam Paninski. Estimating entropy on m bins given fewer than m samples.

The body of work related to this presentation is collected here.

Abstract: I'll discuss the simplest possible entropy estimation problem: estimating the Shannon entropy of an i.i.d. random variable which is known to take values on just a finite number (m) of discrete points. I'll try to answer the following questions: 1) what this (apparently) simple problem has to do with the much more difficult problem of estimating the mutual information between two arbitrary i.i.d. random vectors; 2) why the obvious approach (and a couple not-so-obvious) approaches to solving this problem can fail, especially when m is large compared to N, the number of observed samples; 3) how we can estimate the entropy even when this "data fraction" N/m approaches zero in a certain sense.

The last case in particular is somewhat counterintuitive: it means we can learn the entropy of a distribution without ever needing to learn the distribution itself. It is interesting to note that the Shannon entropy is special in this regard; for example, the closely related Renyi entropies do not share this property.

Jose Costa. Applications of entropic graphs in nonparametric estimation.

Abstract: The study of classical optimization problems over the past 50 years has lead to the characterization of the asymptotic behavior of many minimal graphs such as minimal spanning trees, k-nearest neighbor graphs or minimal matching graphs among others. When the vertices of these graphs are taken as random vectors lying in a feature space, this characterization has an important information theoretic entropy interpretation. In particular, under broad conditions, the appropriately normalized length functional of these graphs converges a.s. (in the number of feature vectors) to the Renyi entropy of the underlying multivariate density. This result motivates the use of such entropic graphs as consistent nonparametric estimators of entropy that bypass the need to estimate multivariate densities with all its inherent complications.

We will discuss applications of entropic graph methods to entropy and divergence estimation, and nonlinear dimensionality reduction in the manifold learning problem.

Ronitt Rubinfeld. The complexity of approximating the entropy.

Abstract: We consider the problem of approximating the entropy of a discrete distribution over a domain of size n. For a given multiplicative approximation parameter gamma > 1, we wish to determine how many samples are required to gamma-approximate the entropy, where the sample complexity is measured in terms of n and gamma. Our main interest is in worst case bounds which make minimal assumptions on the distributions.

We consider the above problem under several models. For example, if the distribution is given explicitly as an array where the ith location is the probability of the ith element, then linear time in n is both necessary and sufficient for approximating the entropy.

A more commonly studied model is when the algorithm is given access only to independent samples from the distribution. In this model, we show that a gamma-multiplicative approximation to the entropy can be obtained for a large class of distributions with a number of samples that is *sublinear* in the size of the domain. In particular, our algorithm uses O(n^{(1+\eta)/gamma^2} \polylog n) time for distributions with entropy Omega(gamma/eta), where eta is an arbitrarily small positive constant. We show that one cannot get a multiplicative approximation to the entropy in general in this model in any amount of time. Even for the class of distributions to which our upper bound applies, we obtain a lower bound of Omega(n^{max(1/(2gamma^2),2/(5gamma^2-2))}) samples.

We also consider a hybrid model in which the distribution is available both as an explicit array and as a black-box. In this model, significantly more efficient algorithms can be achieved: a gamma-multiplicative approximation to the entropy can be obtained in O({gamma^2 log^2{n}} / {h^2 (gamma-1)^2}) time for distributions with entropy Omega(h); for this class of distributions, we show a lower bound of Omega(\frac{\log n}{h(\gamma^2-1)}).

Finally, we consider two special families of distributions: those for which the probability of an element decreases monotonically in the label of the element, and those that are uniform over a subset of the domain. In each case, we give more efficient algorithms for approximating the entropy. In the former case, we give algorithms whose sample complexities are polylogarithmic in n.

Suggested references:

• T Batu, S Dasgupta, R Kumar, and R Rubinfeld, The complexity of approximating the entropy.
• T Batu, L Fortnow, R Rubinfeld, W Smith, and P White, Testing that distributions are close.
• T Batu, E Fischer, L Fortnow, R Kumar, R Rubinfeld, and P White, Testing random variables for independence and identity.

Jonathan Victor. Metric-space approach to information calculations, with application to single-neuron and multineuronal coding in primary visual cortex. (Warning: 1.1MB file.)

The body of work about this method and the applications is collected here. The relevant publications are:

• JD Victor and K Purpura. Metric-space analysis of spike trains: theory, algorithms, and application. Network 8, 127-164, 1997.
• DS Reich, F Mechler, and JD Victor, J.D. Independent and redundant information in nearby cortical neurons. Science 294, 2566-2568, 2001.
• F Mechler, DS Reich, and JD Victor. Detection and discrimination of relative spatial phase by V1 neurons. J. Neurosci. 22, 6129-6157, 2002.
• JD Victor. Binless strategies for estimation of information from neural data. Phys. Rev. E. 66, 51903, 2002.
• D Aronov, DS Reich, F Mechler, and JD Victor. Neural coding of spatial phase in V1 of the macaque monkey. J. Neurophysiol. 89, 3304-3327, 2003.

William Bialek. Entropy and information in spike trains: Why are we interested and where do we stand?

Abstract: I'll give a brief review of why the technical problem of entropy estimation is important for understanding the neural code, and then proceed to an inevitably biased summary of the current state of the field (hopefully others in the room can correct the worst of the biases). I'll emphasize that there are corners of the problem where there is (almost) no technical problem because sample sizes really are large compared with the number of possible responses; these examples are interesting in their own right and also provide benchmarks. On the other hand, for many interesting questions about the neural code, we won't get answers unless we make progress on the entropy estimation problem far from the well sampled regime. Shifting to theory, I'll argue that the origin of the systematic errors in entropy estimation is understandable in Bayesian terms as a problem of phase space: with many seemingly reasonable priors on the space of probability distributions, the overwhelming majority of these distributions have almost the same entropy, and hence it takes very large sample sizes for estimates to cross from being prior-dominated to being data-dominated; because this effect can lead either to under- or to over estimates of the entropy, this perspective is different from the usual one in which we imagine that entropy is underestimated in small samples because we haven't seen all the possibilities. These observations suggest that much of the problem would be cured if we could construct priors on the space of probability distributions which are at least approximately flat in entropy. My colleagues and I have constructed one such prior that is relatively easy to work with, and I'll present evidence that this leads to entropy estimates that are nearly unbiased both in model problems and in the analysis of real data. It is worth emphasizing that this approach (as, we expect, any successful approach) produces reliable entropy estimates despite considerable uncertainty about the precise shape of the underlying probability distribution.

Jon Shlens. Estimating Entropy Rates and Information Rates in Retinal Spike Trains. (Warning: 5.3MB file.)

Publications referenced in this presentation are collected here.

Abstract: Direct estimates of entropy and information in finite data sets generally suffer from bias, which can be particularly severe when analyzing real spike trains at high temporal resolution. Two opposing biases result from (1) temporal dependencies and (2) undersampled probability distributions. These biases significantly complicate the selection of word length - the free but critical parameter in conventional entropy rate calculations.

We propose a new approach to estimating entropy and mutual information rates that substantially alleviates this problem. The approach derives from the perspective that choosing an estimate of entropy rate effectively involves selecting the appropriate model complexity for a finite data set and is best solved under the guiding principle of Minimum Description Length (Rissanen, 1989).

Following this principle we select an appropriate weighting of probabilistic models using a method from compression, "Context Tree Weighting" (Willems et al, 1995, Kennel & Mees 2002, London et al, 2002). We model a spike train (or any symbol stream) as a weighting of finite-order, discrete Markov processes. We use Bayesian estimators of entropy (Wolpert & Wolf 1995) on this weighting of probabilistic models to directly estimate the entropy rate. We do not estimate just a single number (a point estimate of the statistic). Rather, using Monte Carlo techniques we sample the likelihood that a model could generate some range of entropy rates; this provides Bayesian confidence intervals on our estimate.

Using simulations with known entropy rates, we have tested the performance of this estimator and compared the convergence and consistency of this estimator to several other methods (e.g. "direct method", string-matching, Lempel-Ziv compression, "straight" context tree weighting compression, etc). Finally, we have begun testing these methods on spike trains from primate retinal ganglion cells to perform a temporal precision analysis (Reinagel & Reid, 2000).

Yun Gao. Lempel-Ziv and CTW Entropy Estimators for Spike Trains.

Abstract: We consider the problem of evaluating the performance of Lempel-Ziv-type estimators on neural spike train data. We consider two families of entropy estimators based on the Lempel-Ziv data compression algorithm, and we study their theoretical properties and their performance on estimating the information content of spike trains. The first estimator is a known, widely used technique, and the second one is a new estimator, which we prove can be applied to a broader range of experimental data. Their major advantages are that: 1) They make minimal assumptions on the nature of the data distribution; 2) They naturally take into account finer dependence structure arising from long-range dependence; and 3) Their parameters can be adjusted so as to balance the bias-variance trade-off. We prove that the second estimator is "universal" (i.e., it is strongly consistent on all stationary and ergodic processes), and we examine the convergence rate (in term of bias and variance) for both algorithms. Furthermore, we introduce a new nonparametric variance estimation method, based on the stationary bootstrap. We report the performances of these entropy estimators on the spike trains of 29 neurons recorded simultaneously for a one-hour period from the primary motor and dorsal premotor cortices of a quietly seated monkey not engaged in a behavior, as well as on various types of simulated data. The results show that the main drawback of these methods is their slow convergence rate.

Pamela Reinagel. Application of some entropy estimation methods to large experimental data sets from LGN neurons.

Abstract: To appear.

Gal Chechik. Information bearing elements and redundancy reduction in the auditory pathway.

Abstract: Estimating the information that neurons convey about stimuli, depends in practice on finding good statistics of the spike trains. These allow to reduce the spike train dimensionality while preserving the structures that carry information, thus approximating the statistical notion of sufficient statistics. Here we report a comparison of four decoding methods (Victor's Binless estimation, Panzeri's 2nd order expansion, Treves' decoding scheme and the Direct method) in two preparations: responses of auditory cortical neurons of ferrets to broadband noises and of cats to bird chirps. To decrease estimation bias and variance, our method involves a step of reducing the dimensionality of the joint distribution matrices while preserving the mutual information of the variables. In these preparations, the direct method was found to be the most accurate information estimator, as judged by comparisons with exact information calculations on non homogeneous Poissons that simulate our data. Interestingly, we find that in both stations essentially all information is captured by a pair of reduced statistics: the spike count and burst latency.

Using these methods, we also quantified changes in coding by small sets of neurons along the ascending processing hierarchy. Comparing recordings from three stations in the auditory pathway (inferior colliculus (IC), auditory thalamus (MGB) and auditory cortex (A1)), we observe a process of redundancy reduction: A1 neurons conveyed half the information about stimulus identity than IC neurons did, but were significantly less redundant. IC neurons conveyed an order of magnitude more information about the spectro temporal structure of sounds than AI neurons. These findings suggest that A1 extracts high-level independent components of the natural sensory stimuli.