Mutual Information 파헤치기

지난 글에 이어서 이번엔 Infromation Theory 중 Mutual Information(MI)에 대해 다룰 예정이다. 레퍼런스는 머피의 머신러닝 1 책의 6장과 CMI는 위키피디아를 참고했다. 

 

참고 : 위키피디아 https://en.wikipedia.org/wiki/Conditional_mutual_information

 

지난 글 : https://hi-lu.tistory.com/entry/%EC%97%94%ED%8A%B8%EB%A1%9C%ED%94%BC%EC%99%80-KL-Divergence

엔트로피와 KL Divergence

 

 

 

 

 

---

1. MI란

지난 글에서 KL-divergence는 p와 q가 얼마나 유사한지를 판단할 수 있는 척도였다. 0 일수록 유사하고 값이 클수록 유사하지 않음을 알 수 있었다. Mutual Information(MI)는 p와 q의 유사함보다는, 둘의 의존성에 대해 알 수 있다. 두 변수 x와 y의 MI는 I(x;y)로 나타내는데 이를 통해 x와 y가 얼마나 dependent 한 지를 구할 수 있다.

 

x와 y의 dependency를 보고 싶기 때문에 x과 y의 joint probability P(x,y)를 통해 P(x), P(y)와의 유사함을 나타내는 식을 그릴 수 있다. 유사성을 보기 위해서 우리는 KL Divergence를 이용할 수 있음을 알고 있다. 이번에도 적용해 보자. 

 

 

아래의 밴다이어그램을 통해 유사성을 보려면 p(x,y)가 p(x)p(y)와 멀어질수록 좋음을 알 수 있다.

x와 y가 dependent 할 수록 P(x,y)가 P(x)P(y)와 더욱 유사해질 것이다.  따라서 MI가 작을수록 x와 y는 independent하다. 

 

 

MI 해석 

아래 엔트로피에 대한 벤다이어그램을 봤을 때 X의 엔트로피와 Y의 엔트로피의 교집합이 MI에 해당하는 것을 알 수 있다. 

 

(지난 내용을 recap해보자. )

• Entropy H(X) =  - ∑p(x) log p(x)
• Joint Entropy H(X,Y) = - ∑ p(x,y) log p (x,y)
• Conditional Entropy H(X|Y) = H(X,Y) - H(Y)

 

 

위 그림에서 MI 수식을 유추할 수 있는데, MI는 Entropy(첫 번째 벤다이어그램) - Conditional Entropy(4번째 벤다이어그램)으로 볼 수 있다. I(X;Y) = H(X) + H(Y) - H(X,Y)임을 알 수 있다.  X와 Y는 각각 marginal distribution, x,y는 conditional이므로 marginal - conditional 로도 해석할 수 있다. 

Mutual Information 1

 

 

Normalized MI

지난 글에서 증명한 엔트로피의 성질에 따라 H(X,Y) = H(X|Y) + H(Y) = H(Y|X) + H(X)를 생각해 보면 식은 더 단순해진다. 

위 식을 봤을 때 알 수 있는 점은 I(X;Y)는 항상 H(X) 또는 H(Y)보다는 작을 것이란 거다. 즉 I(X;Y) <= min(H(X), H(Y))가 성립한다! 이렇기 때문에 만약 I(X;Y)를 0~ 1사이로 normalize 하고 싶다면 min(H(X),H(Y))로 나눠주면 되며, 이때는 Normalized Mutual Information(NMI)라고 쓴다. MI는 KL divergence 기반이기 때문에 어차피 0보다는 크다.

Normalized Mutual Information

 

만약 NMI(X;Y)가 1이고 min(H(X), H(Y)) = H(X)라면, H(X|Y) = 0을 의미한다. conditional entropy H(X|Y)가 0이란 뜻은 H(Y)가 H(X)에 무조건 속하는 상태로도 해석할 수 있다. 따라서 NMI값이 1이란 뜻은 두 변수 중 하나가 무조건 상대 엔트로피의 포함관계인 것이다.

 

2. conditional mutual information

 

[위키피디아] Conditional Mutual Information

 

이번엔 conditional MI를 통해 MI에도 chain rule이 적용됨을 보일 것이다. 아래와 같이 Z가 주어졌을 때의 X와 Y의 MI를 전개해 보자. 

우변을 풀어써보면 다음과 같다. 

 

 

식이 얼추 정리가 되었으니 log 를 풀어서 entropy H 형태로 정리해 보자. conditional prob들을 다 joint로 풀어냈다.(책과는 다르게 풀었다.)

 

이제 이 식을 MI 식으로 묶어볼 수 있다. 

 

따라서 I(X;Y|Z) = I(Y;X,Z) - I(Y;Z) 임을 보였다. 만약 위 식에서 H(y)가 아닌 H(x)를 더하고 뺐다면 식은 이렇게도 정리가 가능하다. 

이 식에서 Z에 Z1를, Y에 Z2를 각각 대입해 보면 chain rule이 성립하겠구나를 알 수 있다. 따라서 아래와 같이 Mutual Infromation에서 Chain rule을 구할 수 있다!

 

 

3. joint gaussian일 때 

이번엔 분포 x, y가 join gaussian distribution을 따른다고 가정해 본다. 그러면 두 분포의 gaussian은 아래와 같이 표현되는데, 이때 ρ는 둘의 상관계수다.

이때의 MI(x;y)를 구해보자. 먼저 평범한 1 dimension gaussian distribution x의 엔트로피 식은 다음과 같으며, u는 평균을 의미한다. 

 

이 식의 σ 자리에는 joint distribution의 분산이 자리하면 되기 때문에, det(∑)가 자리하게 된다. det(A) = ad- bc였음을 기억하면 X,Y의 joint entropy h(X,Y)는 아래와 같이 정리된다. 

I(X,Y) 는 H(X) + H(Y) - H(X,Y)였다. 각 자리에 대입해 보자. 

 

식이 정리가 됐다. 이로써 join gaussian distribution인 둘의 MI는 상관계수 ρ로 인해 정해짐을 알 수 있다. 이제 ρ자리에 1, -1, 0을 대입해 보며 MI가 어떻게 될지 보자.

• ρ = 1 :  I(X,Y)는 무한대로 가며 둘의 joint covariance(∑) 도 양수다. 이는 Y가 X에 대해 무한대로 정보를 갖고 있음을 뜻한다. 
• ρ = 0: I(X,Y)값이 log 1로 0이다. 즉 X, Y는 연관성이 전혀 없다. 
• ρ = -1 :  I(X,Y)는 무한대로 가는데 둘은 음의 상관성, X = -Y를 만족할 것이다.

 

4. MIC

x, y가  discrete 하지도, 그렇다고 gaussian 과 같이 해석가능한 continuous 분포도 아닌 real-valued data (continuous) 라면 NMI를 구하는 게 조금 까다롭다. 이럴 땐 continuous한 variable들을 구간별로 쪼개서 구할 수 있다. 각 구간별로 information 계수를 구한 후 이 구간들 중 가장 큰 값을 가진 계수를 택하는데 그래서 이름이 Maximal Information Coefficient(MIC)이다. 

 

식을 볼 때 G는 격자로 자른 구간을 의미한다. 구간들 각각 MI를 구하고, 그중 가장 큰 MI를 가진 구간의 MI를 MIC로 정의하고 있다. 

 

MIC 수식

 

 MI의 특징 상 MIC가 0이라면 x, y간 어떤 관계도 없음을(independent), 1이라면 noise-free한 관계를 가짐을 알 수 있다. 변수간 상관성을 보는 방법으로는 상관계수(Correlation Coefficient. corr)도 있다. MIC는 상관계수와 다르게 linear한 관계만을 보지도 않는다. 그렇기 때문에 corr을 구하는 대신 MIC를 보는 것이 유용할 때도 있다. 예를 들어 아래의 그림에서 E,F,G는 각각 2개의 변수에 대한 계수를 구한 지점이다. 각각 상관계수가 0에 가깝지만 MIC를 봤을 땐 0.5보다 크므로, 선형적인 상관성은 없을지 몰라도(corr = 0) 실제로는 상관성이 있다. 

 

5. data processing inequality

어떤 변수 X가 Y라는 함수를 통해 Z로 변환된다면(X -> Y -> Z), I(X;Y) >= I(X;Z)가 성립한다. 직관적으로 볼 때 X와 Y의 연관성이 X와 Z의 연관성보다는 높을 거라는 결론이 나올 수 있는데, 위 conditional mutual information 증명 과정에서 조금 변형하면 수식적으로도 증명할 수 있다. 

 

증명을 해보자면 다음과 같이 I(X;Y,Z) = I(X;Z) + I(X;Y|Z)를 도출할 수 있다. 

 

여기서 Z와 Y의 자리를 바꾸면 I(X;Y,Z) = I(X;Y) + I(X;Z|Y)도 성립한다.

 

X와 Z|Y는 직교한다고 가정했기 때문에 I(X; Z|Y) = 0일 것이고, I(X;Y|Z)는 항상 0보다 같거나 크기 때문에(KL divergence의 성질. 항상 0보다 크다.), I(X;Y) > I(X;Z)로 표현할 수 있게 된다! 

 

 

6. Fano's inequality

MI가 두 변수에 대한 상관성을 측정하기 때문에 feature selection에서도 유용하게 사용될 거다. 특정 피쳐 X와 클래스 라벨 Y 간의 상관성을 볼 때(이때 X가 예측한 Y는 Y^라고 하자), X와 Y의 상관성이 높은데 Y와  잘못 예측한 값과의 상관성은 더 높게 나오면 어떡할까?

 

다행히도 이런 일은 없다. 잘못 예측한 경우의 엔트로피가 항상 더 크기 때문인데,  이를 fano's inequality라고 한다. 지금부터는 이를 증명해 볼 것이다. 

전제 - 우선 에러 E는 실제 라벨 Y와 예측값 Y^이 다를 경우로, 이때의 확률을 Pe = P(Y != Y^)라고 나타내겠다. 에러가 날 확률의 minimum boundary를 H(Y|X) 통해 구해보자. (참고로 우리가 feature selection에서 높은지 알고 싶은 MI는 I(X;Y) =  H(Y) - H(Y|X) 로 표현할 수 있었기 때문에 H(Y|X)가 낮아질수록 I(X;Y)는 높아진다. )

 

 

1 - 첫 번째로는 H(Y|X)가 어떤 의미를 가지는지 알아보자.

먼저, 엔트로피는 항상 1보다 같거나 작기 때문에 H(Y|X) <= 1이 성립한다. 우변에 양수인 무언갈 더한다고 해도 부등호는 달라지지 않을 것이다. 그 무언가는 여기서 Pe log|Y|가 된다. (|Y|는 클래스라벨 종류 수를 의미한다.)

 

여기서 Pe에 대해 식을 정리해 보면 H(Y|X)에 따라 Pe의 최소 boundary가 지정됨을 알 수 있다. 따라서 H(Y|X)가 낮아질수록, 즉 I(X;Y)가 커질수록 에러 확률 Pe의 miminum도 낮아진다.

 

 

 

2 - 두 번째로는 H(Y|Y^) <= H(E) + Pe log|Y|임을 증명해 보자.  여기서는 H(Y2,Y1|Y0) = H(Y1|Y0) + H(Y2|Y1,Y0)인 chain rule을 사용한다. 

두 개를 더하면 H(Y|Y^) = H(E|Y^) + H(Y|E,Y^)를 도출할 수 있다. 여기서 H(Y|E,Y^)는 아래와 같이 상한선이 생긴다. 

이 H(Y|E,Y^)를 H(Y|Y^) = H(E|Y^) + H(Y|E,Y^)에 대입하면 아래와 같이 되는데, 그렇기 때문에 에러의 엔트로피가 X와 Y의 엔트로피보다 크다. 

 

3 - 마지막으로 data processing inequality로 인해  I(Y;Y^) <= I(Y;X)이다.(Y -> X -> Y^인 셈.)  H(Y|X) < H(Y|Y^)도 성립한다. 

이로써 Fano's inequality를 증명했다. 

 

 

 

 

---

오늘은 MI가 x, y의 dependence를 측정하는 방법론으로 KL divergence를 통해 수식이 생겨먹었다는 것을 알았다. 그리고 NMI, Conditional MI를 통한 chain rule, 두 변수가 joint gaussian distribution일 땐 어떻게 MI가 전개되고 해석할 수 있는지를 알아보았다. MI가 높으면 dependence가 높은 변수인 것이기 때문에, feature selection 시에도 MI가 높은 변수를 고르는 등 사용된다. 

 

 

지난 글부터 오늘 글을 통해 entropy - KL divergence - MI 까지 완전 정복해 보았다. (그리고 정말 새삼 책이 썩 친절하지는 않구나를 느꼈다..) 코로나에 걸려서 이번주는 스킵할 뻔했는데, 저번에 써둔 글이 있어 이번주도 이렇게 완료한다.