Mutual Information 추정하기

   mutual information 은 비선형 관계를 갖는 두 변수를 찾을 때 사용할 수 있는 값이다. 보통 선형이면 Pearson's Correlation 을 이용하는데 선형이 아닌 관계를 갖는 경우 mutual information 이 가장 잘 탐지할 수 있는 것으로 보인다. 이 글에선 mutual information 을 추정하기 위한 노력들을 살펴 본다. 실제 코드는 구현하지 않고 알려진 것을 사용한다^[각주:1]. 

   mutual information (MI) 는 continuous 에서 다음과 같이 정의된다. 

이것은 discrete 한 경우 다음과 같이 정의된다. 

문제는 많은 경우 실제로는 continuous이지만 우리가 실험적으로 얻은 값은 discrete 하다는 것이다. 그래서 continuous한 식을 그대로 사용하진 못하고 discrete 한 것으로 계산을 해야 하는데, 실험 데이터가 왠만큼 많지 않으면 계산에 큰 오차가 생긴다. 가장 단순한 방법은 x 와 y 구간을 적당히 나눠서(binning) 그 구간에 들어 간 데이터의 개수를 세어서 확률로 간주하는 것인데, 데이터가 10개 있을 때 구간을 10개로 나누면 데이터가 보통 1 개밖에 안 들어가게 되는데, 이것은 분명 10%의 확률이라고 하기엔 애매한 값이다. 더구나 x, y 모두 10개의 구간으로 나누면 총 100 개의 영역이 생기는 것이므로 이럴 경우 100개의 데이터가 있어도 확률이 0.01 혹은 0.00 혹은 0.02 에서 기껏해야 0.1 이 나올까 말까, 이런 식으로 실제 확률값과 계산된 확률값이 큰 차이를 가질 가능성이 높아 진다. 구간 수는 보통 데이터의 개수에 log2 를 취한 것 정도로 얘기되는데 구간 수야 어떻든 이렇게 binning 을 하는 방법은 오차가 크다. 

   그래서 위와 같은 문제를 조금이나마 극복하고자 나온 것이 k-nearest neighbor (KNN) 방법이다(참고자료 2번). 본 논문은 좀 어렵게 쓰여 있는데 - 수학적 개념이 설명 없이 자주 쓰인다 (spanning 된 space라던가...) - 간단한 아이디어는 각 데이터에 대해서 그 데이터에 몰려 있는 데이터들을 기준으로 확률을 계산해서 평균을 내는 방법이다. 이 저자의 페이지에 가면 소스 코드를 받아서 사용할 수 있다(MILCA 홈페이지). 대부분의 내용은 ICA 관련 내용인데 소스에 살펴 보면 MIxnyn.C 파일이 KNN 을 이용한 MI 이다. 소스는 C 로 되어 있고 별다른 라이브러리 없이 컴파일을 해서 사용할 수 있다. 이 방법을 구현하려 했는데, 굳이 있는 걸 구현할 필요는 없을듯 하여 지금 이 상태에서 글을 쓴다^[각주:2]. 확인해야 하는 경우가 많은 경우 system call 로 하지 않고, source code를 수정해서 library 로 만들어서 사용하면 좋으니 원 코드를 수정했다. vector 랑 pointer 둘 다 사용할 수 있도록 wrapper 를 만들어서 function 으로 호출할 수 있도록 수정했다. 

참고 자료

+1. Mutual Information between Discrete and Continuous Data Sets - Ross BC (2014) Mutual Information between Discrete and Continuous Data Sets. PLoS ONE 9(2): e87357. doi:10.1371/journal.pone.0087357

+2. Estimating mutual information - Phys. Rev. E 69, 066138 – Published 23 June 2004,  Alexander Kraskov, Harald Stögbauer, and Peter Grassberger

   source code 는 MILCA 홈페이지에 있다. 

+3. Mutual information algorithms - Mechanical Systems and Signal Processing Volume 24, Issue 8, November 2010, Pages 2947–2960

관련 자료

+1. Detecting Novel Associations in Large Data Sets - Science 16 December 2011, Vol. 334 no. 6062 pp. 1518-1524, DOI: 10.1126/science.1205438

   이 논문은 non-linear association 을 이루는 경우에 높은 값을 주는 새로운 수치인 MIC 에 관한 첫 논문이다. 정확한 값은 아니고 approximation 인데 저자들의 홈페이지에 java 실행 파일이 있으며 minepy 에 python 과 C/C++ 코드가 있다. 

+2. Equitability, mutual information, and the maximal information coefficient - Proc. Natl. Acad. Sci. USA 4 March 2014: 3354-3359.

   이 논문은 위의 Science 논문에서 제시하는 조건에 약간의 문제가 있으며 mutual information 자체만으로도 충분할 수 있다는 의견을 제시한다. 이 논문에서 independence test 로 사용할 수 있는 방법으로 equitability 를 확인했던 distance correlation 과 Hoeffding's D 가 나온 논문은 아래의 두 논문이다. KNN 으로 MI 를 추정한 논문은 위의 참고 자료의 Kraskov 논문이다. 

+3. Brownian distance covariance - Ann. Appl. Stat.,  Volume 3, Number 4 (2009), 1233-1830, Gábor J. Székely and Maria L. Rizzo

   distance correlation 에 관한 논문. 

+4. A Non-Parametric Test of Independence - Ann. Math. Statist., Volume 19, Number 4 (1948), 447-610, Wassily Hoeffding

   이 논문이 Hoeffding's D 에 관한 논문. 

1. 코드를 받아서 컴파일 및 실행이 되는 것을 확인한 후 한 고민은 이것을 내가 직접 구현을 할 것인가 말 것인가 였다. 보통은 원 알고리즘에 약간의 수정이 필요해서 내가 직접 구현했던 것인데 지금은 그렇지 않아서 그냥 있는 코드를 그대로 사용하기로 결론내렸다. [본문으로]
2. C/C++ 사용자들의 특성이지 않을까 하는데 - 아닌가? ㅋㅋ - 어지간해선 라이브러리를 쓰기보단 직접 구현한다. 이 경우도, 그래서, 구현을 할까말까, 고민했지, 컴파일이 된 걸 확인하고나서도. 우선은 있는 코드를 쓰지만 지금 생각하는 몇 가지 아이디어를 구현하다 필요하면 직접 구현에 들어 갈 생각이다, KNN 을 이용한 MI 도. [본문으로]