A statistic to estimate the variance of the histogram-based mutual information estimator based on dependent pairs of observations

Abstract

In the case of two signals with independent pairs of observations (x_n,y_n) a statistic to estimate the variance of the histogram based mutual information estimator has been derived earlier. We present such a statistic for dependent pairs. To derive this statistic it is necessary to avail of a reliable statistic to estimate the variance of the sample mean in case of dependent observations. We derive and discuss this statistic and a statistic to estimate the variance of the mutual information estimator. These statistics are validated by simulations.

Zusammenfassung

Im Fall zweier Signale mit unabhängigen Paaren von Beobachtungen (x_n,y_n) wurde schon früher eine Statistik zur Schätzung der Varianz des histogramm-basierten Schätzers für die Transinformation (mutual information) abgeleitet. Wir stellen eine solche Statistik für abhängige Paare vor. Um diese Statistik abzuleiten, ist es erforderlich, auf eine zuverlässige Statistik zur Schätzung der Varianz des Mittelwertes für den Fall abhängiger Beobachtungen zurückzugreifen. Eine solche Statistik, sowie eine Statistik zur Schätzung der Varianz des Transinformations-Schätzers wird von uns abgeleitet und diskutiert. Die Statistiken werden durch Simulationsergebnisse bestätigt.

Résumé

Dans le cas de deux signaux avec des paires indépendantes d'observations (x_n,y_n), nous avons dérivé précédemment une statistique permettant d'estimer la variance de l'estimateur de l'information mutuelle basé sur l'histogramme. Nous présentons ici une telle statistique pour des paires dépendantes. Pour dériver cette statistique, il est nécessaire d'avoir une statistique fiable pour estimer la variance de la moyenne des échantillons dans le cas d'observations dépendantes. Nous dérivons et discutons cette statistique ainsi qu'une statistique pour estimer la variance de l'estimateur de l'information mutuelle. Ces statistiques sont validées par simulations.

Introduction

To estimate time-delays between recordings of electroencephalogram (EEG-) signals Mars and van Arragon introduced a method based on maximum mutual information [18]. Consider two stationary and ergodic stochastic processes x and y and the point measurements (samples) x_n=x(nΔt) and y_n=y(nΔt). To avoid confusion about the meaning of samples, which depend on the context (signal processing or statistics), we use the term point measurements instead. The mutual information $\text{I{}\text{x}{}_{\mathrm{n}}\text{;}\text{y}{}_{\mathrm{n+m}}\text{}}$, given an observed sequence of pairs of point measurements $\text{(}\text{x}{}_{\mathrm{n}}\text{,}\text{y}{}_{\mathrm{n}}\text{)}$ where 1⩽n⩽N, is estimated as a function of the lag m. Due to the stationarity of these processes this mutual information is independent of n. The lag for which the mutual information reaches a maximum is considered to be the delay of y with respect to x. Maximum mutual information is typically used in the alignment of 1D (time signals), 2D (images) or even 3D signals.

To validate the estimated lag, it is necessary to know the accuracy, e.g. the variance, of the mutual information estimates. In practical situations, e.g. the analysis of electroencephalogram (EEG-) signals, the estimation of this variance is complicated because in general the subsequent pairs of point measurements $\text{(}\text{x}{}_{\mathrm{n}}\text{,}\text{y}{}_{\mathrm{n+m}}\text{)}$ are not independent. Therefore, we need a statistic to estimate the variance of the mutual information estimator in case of dependent pairs of observations.

The concept of mutual information originates from the theory of communication. The mutual information measures the information of a random variable contained in another random variable. The definition of mutual information goes back to Shannon 28, 29, 30. The theory was extended and generalized by Gel'fand and Yaglom [6]. The mutual information of two discrete random variables x and y is defined by

$$\text{I{}\text{x}\text{;}\text{y}\text{}=}\text{∑}\text{i,j}\text{p}{}_{\mathrm{ij}}\text{log}\text{p}{}_{\mathrm{ij}}\text{p}{}_{\mathrm{<mtext>·</mtext><mtext>j</mtext>}}\text{p}{}_{\mathrm{<mtext>i</mtext><mtext>·</mtext>}}\text{,}$$

where $\text{p}{}_{\mathrm{ij}}\text{=}\text{Pr}\text{{}\text{x}\text{=X}{}_{\mathrm{i}}\text{,}\text{y}\text{=Y}{}_{\mathrm{j}}\text{}}$, p_·j=Pr{y=Y_j} and p_i·=Pr{x=X_i}. The outcomes X_i and Y_j are the possible (discrete) values of x and y, e.g. x∈{X₁,…,X_I} and y∈{Y₁,…,Y_J}. The mutual information between continuous random variables can be estimated by the same technique after quantization of the random variables. We assume base e for the logarithm, consequently the unit of measurement is nat; base 2 (bit) and base 10 (Hartley) can also be used. The mutual information measures the dependence of x and y; $\text{I{}\text{x}\text{;}\text{y}\text{}=0}$ if and only if x and y are independent, otherwise $\text{I{}\text{x}\text{;}\text{y}\text{}>0}$. The mutual information is independent of any transformation of the arguments having a unique inverse (bijection). The mutual information reaches a maximum if there is a bijective relation between x and y. We can express the mutual information using entropies:

$$\text{I{}\text{x}\text{;}\text{y}\text{}=H{}\text{x}\text{}+H{}\text{y}\text{}−H{}\text{x}\text{,}\text{y}\text{},}$$

where

$$\text{H{}\text{x}\text{}=}\text{∑}\text{i}\text{−p}{}_{\mathrm{<mtext>i</mtext><mtext>·</mtext>}}\text{log}\text{p}{}_{\mathrm{<mtext>i</mtext><mtext>·</mtext>}}\text{,}\text{H{}\text{x}\text{,}\text{y}\text{}=}\text{∑}\text{i,j}\text{−p}{}_{\mathrm{ij}}\text{log}\text{p}{}_{\mathrm{ij}}\text{.}$$

There exist essentially three different methods to estimate mutual information:

• histogram-based estimators 20, 21,

• kernel-based estimators 18, 22 and

• parametric methods.

For the application of parametric methods a model of the stochastic processes is necessary. Both the histogram- and the kernel-based estimator can be used as a general-purpose tool. Because of its relative simplicity the properties of the histogram-based estimator, such as bias, variance (for independent pairs of observations) and robustness, are fairly well known 20, 21. Within this article, we will construct a statistic to estimate the variance which can be applied to sequences of dependent pairs of observations. The kernel-based estimators have too many adjustable parameters such as the optimal kernel width and the optimal kernel form. Properties like bias and variance are still unknown. Especially in case of the iterative determination of the optimal kernel form as proposed by Mars and van Arragon [18] the method is computationally intensive.

Mutual information is often used to replace the correlation coefficient. The mutual information does not depend on a linear relation of x and y. The possible outcomes of these random variables do not need to be numerical or ordered (words in language processing). Due to these properties mutual information can be applied as a correlator in many areas where the correlation coefficient fails. To compare mutual information estimates amongst each other it is necessary to know whether differences are significant or whether they are caused by the bias of the statistic or statistical fluctuations.

The histogram-based statistic to estimate mutual information suffers from

• variance,

• bias caused by the finite number of observations,

• bias caused by quantization, and

• bias caused by the finite histogram.

The relative contribution of these causes depends on the application; especially it depends on the number of observations, the configuration of the histogram cells and the smoothness of the probability density function. The last two causes are independent of the number of observation and only relevant in case of continuous random variables. In case of independent pairs of observations these error causes were studied in earlier work 20, 21. Both the variance and the bias caused by the finite number of observations depend on the number of observed pairs and the dependencies amongst those pairs. An estimator for the variance in case of dependent pairs will be presented. An estimator for the bias due to the finite number of observations in case of dependent pairs of observations is unknown and is beyond the scope of this article. This bias will probably in first-order approximation only depend on the number of histogram cells and the interdependence of the pairs $\text{(}\text{x}{}_{\mathrm{n}}\text{,}\text{y}{}_{\mathrm{n}}\text{)}$ and not on the joint distribution of x_n and y_n.

Mutual information is used in several areas of science: language processing 4, 14, 15, speech processing [24], image processing 8, 16, 17, 25, 32, analyses of non-linear systems 10, 11, 13, time delay estimation 11, 18, 20, 21, neural networks 1, 2 and bio-medical applications [27].

InSection 2we develop the theory to estimate the variance of the mutual information estimator in case of dependent pairs. It is necessary to avail of a reliable estimator for variance of the sample mean in case of dependentpoint measurements of a stationary stochastic signal. In Section 3, we evaluate three methods to estimate this variance. Finally, we verify our theory by simulations inSection 4.