# Can the MIC algorithm for detecting non-linear correlations be explained intuitively?

More recently, I read two articles. Speed's article is about the history of the correlation, and the article by Reshef, et al. is about a new method called maximal information coefficient (MIC). I need your help to understand the MIC method to estimate non-linear correlations between variables.

Moreover, instructions for MIC's use in R can be found on the author's website (under Downloads):

I hope this will be a good platform to discuss and understand this method. My interest is in the intuition behind this method and how it can be extended in the way the author said:

...we need extensions of $$\text{MIC}(X,Y)$$ to $$\text{MIC}(X,Y|Z)$$. We will want to know how much data are needed to get stable estimates of MIC, how susceptible it is to outliers, what three- or higher-dimensional relationships it will miss, and more. MIC is a great step forward, but there are many more steps to take.

Citations
Speed, T. (2011). A Correlation for the 21st Century. Science, 334(6062), 1502–1503.

Reshef, D. N., et al. (2011). Detecting Novel Associations in Large Data Sets. Science, 334(6062), 1518–1524.

• The discussion will be hindered by the fact that the article in Science is not open access. Commented Dec 20, 2011 at 9:16
• Here is a copy of the paper liberated by one of the authors.
– user88
Commented Dec 20, 2011 at 12:03
• In short, MIC is an excavation of old idea of "plot-all-scatterplots-and-peak-those-with-biggest-white-area", so it mainly produces false positives, has an unreal complexity of $O(M^2)$ (which authors hide behind test-only-some-randomly-selected-pairs heuristic) and by-design misses all three- and more- variable interactions.
– user88
Commented Dec 20, 2011 at 12:12
• mbq: Thanks, Could you please elaborate more your answer? mpiktas: More specially, I am interested to understand the algorithm MIC, intuitively. Commented Dec 20, 2011 at 13:06
• For technical details on the MIC, the Supporting Online Material is more informative than the article itself. Commented Dec 20, 2011 at 13:51

Is it not telling that this was published in a non-statistical journal whose statistical peer review we are unsure of? This problem was solved by Hoeffding in 1948 (Annals of Mathematical Statistics 19:546) who developed a straightforward algorithm requiring no binning nor multiple steps. Hoeffding's work was not even referenced in the Science article. This has been in the R hoeffd function in the Hmisc package for many years. Here's an example (type example(hoeffd) in R):

# Hoeffding's test can detect even one-to-many dependency
set.seed(1)
x <- seq(-10,10,length=200)
y <- x*sign(runif(200,-1,1))
plot(x,y)  # an X
hoeffd(x,y)  # also accepts a numeric matrix

D
x    y
x 1.00 0.06
y 0.06 1.00

n= 200

P
x  y
x     0   # P-value is very small
y  0


hoeffd uses a fairly efficient Fortran implementation of Hoeffding's method. The basic idea of his test is to consider the difference between joint ranks of X and Y and the product of the marginal rank of X and the marginal rank of Y, suitably scaled.

# Update

I have since been corresponding with the authors (who are very nice by the way, and are open to other ideas and are continuing to research their methods). They originally had the Hoeffding reference in their manuscript but cut it (with regrets, now) for lack of space. While Hoeffding's $D$ test seems to perform well for detecting dependence in their examples, it does not provide an index that meets their criteria of ordering degrees of dependence the way the human eye is able to.

In an upcoming release of the R Hmisc package I've added two additional outputs related to $D$, namely the mean and max $|F(x,y) - G(x)H(y)|$ which are useful measures of dependence. However these measures, like $D$, do not have the property that the creators of MIC were seeking.

• (+1) Hoeffding's paper is available online. Commented Dec 23, 2011 at 17:04
• Nice find. Might be worth a short note to Science comparing Hoeffding's performance with theirs. It is a pity that many good studies (in many fields) from the 50's were forgotten over the years. Commented Dec 24, 2011 at 20:26
• Frank Harrell, I wish I could up-vote this twice. Reporting on the correspondence is just classy. Commented Mar 22, 2022 at 17:32
• @r.e.s. The link you gave appears to be dead now. Commented Mar 22, 2022 at 17:55
• @DifferentialCovariance Hoeffding's paper can still be downloaded here. (I don't know why the old link expired.) Commented Mar 22, 2022 at 19:39

The MIC method is based on mutual information (MI), which quantifies the dependence between the joint distribution of $$X$$ and $$Y$$ and what the joint distribution would be if $$X$$ and $$Y$$ were independent (see, e.g., the Wikipedia entry). Mathematically, MI is defined as $$MI=H(X)+H(Y)-H(X,Y)$$ where $$H(X)=-\sum_i p(z_i)\log p(z_i)$$ is the entropy of a single variable and $$H(X,Y)=-\sum_{i,j} p(x_i,y_j)\log p(x_i,y_j)$$ is the joint entropy of two variables.

The authors' main idea is to discretize the data onto many different two-dimensional grids and calculate normalized scores that represents the mutual information of the two variables on each grid. The scores are normalized to ensure a fair comparison between different grids and vary between 0 (uncorrelated) and 1 (high correlations).

MIC is defined as the highest score obtained and is an indication of how strongly the two variables are correlated. In fact, the authors claim that for noiseless functional relationships MIC values are comparable to the coefficient of determination ($$R^2$$).

I found two good articles explaining more clearly the idea of MIC. In particular the blog post "large-scale data exploration, MIC-style", and Gelman's blog post "Mr. Pearson, meet Mr. Mandelbrot: Detecting Novel Associations in Large Data Sets".

As I understood from these reads is that you can zoom in to different complexities and scales of relationships between two variables by exploring different combinations of grids; these grids are used to split the 2 dimensional space into cells. By choosing the grid that holds the most information on how the cells partition the space you are choosing the MIC.

I would like to ask @mbq if he could expand what he called "plot-all-scatterplots-and-peak-those-with-biggest-white-area" and unreal complexity of $$O(M^2)$$.

• I worry about any statistical method that uses binning. Commented Dec 24, 2011 at 13:49
• @FrankHarrell Can you provide references or some intuition which detail why binning is bad? Intuitively, I can see that you are essentially throwing away information due to binning, but there must be more reasons why? Commented Sep 30, 2016 at 19:41
• There are too many references to know where to start. No statistical method based on binning ultimately survives. Arbitrariness is one of many problems. Commented Sep 30, 2016 at 19:51
• @FrankHarrell Appreciate the comment. Reason I asked for references is I am a PhD student, and am studying dependence and multivariate dependence concepts right now, and would love to read these papers and cite them in my own works in the future. If you could mention one or two prominent ones, I am sure I can find the remaining ones you are mentioning. I'll also do some digging and post references here if I find good ones. Commented Sep 30, 2016 at 19:59
• Start with citeulike.org/user/harrelfe/article/13265458 then see other information about dichotomization at biostat.mc.vanderbilt.edu/CatContinuous. For a general dependence measure not requiring any binning don't miss citeulike.org/user/harrelfe/article/13264312 Commented Oct 1, 2016 at 12:42