5
$\begingroup$

I'm trying to use the notion of mutual information between continuous variables in a software. https://en.wikipedia.org/wiki/Mutual_information

The inputs of the algorithm would be two lists l1 and l2 of n real numbers and the output would be a real number m that represents the mutual information between the values in l1 and l2.

But I don't know how can I translate that formula in an algorithm. Can you help me?

Best regards.

$\endgroup$
  • 1
    $\begingroup$ Please be more specific. What is the input and output of the algorithm? $\endgroup$ – Stelios Aug 11 '17 at 21:11
  • $\begingroup$ I have provided a more detailed description of the inputs and output of the algorithm. $\endgroup$ – Juan Aug 11 '17 at 21:31
  • 1
    $\begingroup$ I am guessing the two lists of numbers represent (joint) realizations of two random variables and you want, based on these samples, to find an estimate of the mutual information. I am afraid there is no simple and accurate algorithm for this task. You could always employ the straightforward approach of estimating the joint pdf of the two variables (based on the histograms) and computing the mutual information by numerical integration. However, the resulting estimate will be biased, and typically unreliable. You will need to dig deep into advanced research papers on this topic. $\endgroup$ – Stelios Aug 11 '17 at 21:47
6
$\begingroup$

Estimating mutual information fast and accurately is non-trivial. I recommend using a library or you will have to look at the literature (e.g. see Kraskov et al, 2004, Estimating Mutual Information).


However, you can get an estimate naively as follows. You talk about two lists of values, $X$ and $Y$; hence, you can estimate the discrete rather than continuous mutual information: $$ I(X,Y) = \sum_{x\in X}\sum_{y\in Y} P(x,y) \log\left( \frac{P(x,y)}{P(x)\,P(y)} \right) $$ where $x\in X$ means $x$ runs over the range of $X$. The formula just requires that you know $P(x)$, $P(y)$, and $P(x,y)$, which you can estimate from your data (e.g. kernel density estimation, or fitting a Gaussian mixture model).

Maybe slightly better (and just as easy with libraries) is (1) determine the joint and marginal densities $P(x)$, $P(y)$, and $P(x,y)$ via density estimation (e.g. in Python, see scipy or sklearn) and (2) numerically integrate the resulting density functions (e.g. in scipy) using the continuous formula: $$ I(X,Y) = \int_{Y}\int_{X} P(x,y) \log\left( \frac{P(x,y)}{P(x)\,P(y)} \right)dx\,dy $$ so it boils down to running a density estimation algorithm, followed by a numerical integration algorithm.

You can also check out this question, which computes mutual information by density estimation (using histograms) first and then uses the representation of mutual information via Shannon Entropy, i.e. $$ I(X,Y) = H(X) - H(Y) - H(X,Y) $$ where $H$ is the information entropy, to finish the calculation instead.


(1/11/19) Since this has become of greater importance in certain fields (AI, data science, and machine learning, for example), I'll just mention some of the literature in those areas that uses/requires mutual information estimation.

For instance, infoGAN and HFVAE use Monte Carlo estimates of bounds of the information and/or entropy (also called variational information estimates). See also MINE and Deep InfoMax. Note that these methods (and the methods that cite or are cited by them) are often more concerned with optimizing mutual information, not just estimating it, which of course has different requirements.

$\endgroup$
  • $\begingroup$ Regarding the paper Kraskov et al, 2004, Estimating Mutual Information arxiv.org/pdf/cond-mat/0305641.pdf, I am puzzled over the motivation of using the $k$'th nearest neighbor point. Do you have any idea as to the motivation? $\endgroup$ – Hans Jan 11 at 9:46
  • $\begingroup$ Dear @Hans, would you mind posting as a new question and link back to it here? More people would see/help, it's more searchable/archivable, and it will be easier for you to add more details :) $\endgroup$ – user3658307 Jan 11 at 16:21
  • $\begingroup$ Good idea. :-) See math.stackexchange.com/q/3069744/64809. $\endgroup$ – Hans Jan 11 at 18:12
  • 1
    $\begingroup$ There are some great answers for the discrete case here: math.stackexchange.com/questions/604654/estimating-the-entropy $\endgroup$ – user3658307 Jul 15 at 2:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.