1.Information Theory
    (=
Shannon's Information Theory)
정보량에 대해 기술하기 위한 이론으로 엔트로피를 핵심 개념으로 사용하며, 기계학습을 비롯해 셀 수없이 방대한 분야에서 활용되고 있다.

Shannon's Bits : Information 의 양을 나타내기 위해 샤논은 bit를 다음과 같이 사용하였다.

Shannon은 정보량을 다음과 같이 정의하였다.
확률 p인 사건의 정보량 = 1/p 를 나타내는데 필요한 bit의 개수 = log_2(1/p)

그래서 정보량이 log_2(1/p)인 것이다.
이에 따라 확률이 낮은 사건일수록 그값을 표현하는 데 bit가 더 많이 필요하다.


http://en.wikipedia.org/wiki/Information_theory

http://www.science4all.org/le-nguyen-hoang/shannons-information-theory/


Entropy

엔트로피는 정보량의 평균이다. (엔트로피를 다르게 해석하면, 어떤 X가 가진 정보의 희소성에 대한 측정값이다. )

우선 정보량의 정의는 다음과 같다.

이 정보량은 낮은 확률의 사건이 일어날 수록 깜짝 놀랄만한 정보를 담고 있다는 가정으로 정의된것이다. 예를 들어 로또에 맞을 확률이 약 800만분의 1인데, 내 옆사람이 갑자기 당첨되었다면? 이는 정말 놀라울만한 정보가 아닐 수 없을 것이다.
다시 말해 만약 모든 숫자가 1만 나오던 어떤 신호에서, 갑자기 2인 신호가 딱 한 번 나타나면 이것 역시 매우 놀라운 사건으로, 아주 큰 정보량을 갖는다.

그런데 이러한 의미의 정보량을 단순히 확률의 역수로 정의하지 않고, log2를 취하는 이유는 1/p(x) (깜짝 놀라는 정도)를 나타내는데 필요한 비트의 숫자를 표현하기 위해서이다. 그래서 log2를 취하는 것이다.

다른 의미로는 정보량과 p(x)와의 곱을 통해 평균을 취하기 위해서라고도 볼 수 있는데, 단순히 역수만 취하면 항상 p(x) * 1/p(x) = 1 밖에 얻을 수가 없다. 따라서 유의미한 계산을 하기 위해 Log를 씌운다고도 볼 수 있다.(Log는 단조 증가 함수로 취해도 대소 비교 순서를 잃지 않는다.)

그래서 엔트로피란 바로 이 정보량에 확률을 곱하고 더하여, 정보량의 평균을 계산한 것이다.


이것을 또 다시 설명하자면, 어떤 확률 분포 p(x)에서 일어날 수 있는 모든 사건들의 정보량에 평균을 구한 것이다. 즉 확률 분포 p(x) 자체가 가지고 있는 정보의 량을 측정한 것이다.

예를 들어, 앞 뒷면이 각각 50% 확률로 나오는 동전은 한 쪽면이 일그러져서 확률이 8:2인 동전보다 엔트로피가 보다 더 크다. 즉 8:2 인 동전은 거의 앞면 위주로 등장할 것을 뻔히 알고 있기 때문에 평균적인 사건의 정보량이 작은 것이다. ( 물론 20% 확률로 뒷면이 나올 경우 그 사건의 정보량은 매우 크지만, 전체 사건의 평균을 구하면 더 작게 된다. )

이는 실제로 엔트로피의 수식에 확률을 넣어서 계산해봄으로써도 알 수가 있다.
5:5 의 경우 엔트로피는 -{ 0.5 * -1 + 0.5 * -1 } = 1 이고, 
8:2 의 경우 엔트로피는 -{ 0.8 * -0.322 + 0.2 * -2.322 } = 0.722 이다

만약 앞면만 100% 확률로 나오는 동전이라면? 정보량은 0이 된다. 따라서 동전던지기의 경우에는 앞,뒤면이 나올 확률이 uniform 분포인 (1/2로 같은 확률)동전의 엔트로피가 가장 크다. 

이를 그래프로 그리면 다음과 같은 그래프를 얻을 수가 있다.



https://upload.wikimedia.org/wikipedia/commons/thumb/2/22/Binary_entropy_plot.svg/300px-Binary_entropy_plot.svg.png


그러면 여기서 더 나아가, 엔트로피를 불확실성(uncertainty)과도 같은 개념이라고 인식할 수 있다. 즉, 예측 불가능한 불확실성이 높을 수록 정보의 양이 더 많고, 그러므로 엔트로피는 더 커진다.

http://ko.wikipedia.org/wiki/정보_엔트로피


또한 이 엔트로피 정의가 편리한 것은 아래와 같은 이유도 있다.

"p 가 0이면, p*logp도 0이다"
In what follows, an expression of the form 
p log p is considered by convention to be equal to zero whenever p = 0. This is justified because  for any logarithmic base.

https://en.wikipedia.org/wiki/Information_theory

이 속성의 편리함은 뒤에 나올 CrossEntropy와 KL Divergence에서 보다 자세히 설명한다.



열역학에서의 Entropy와의 관계

열역학에서의 Entropy와 정보이론에서의 Entropy 정의는 매우 흡사하다.(볼츠만 상수값이 곱해진 차이) 그리고 해석적으로 둘사이에는 불확실성이라는 공통된 개념을 가지고 있다.

즉 Entropy는 확률 분포 p 에 담긴 불확실성을 나타내는 지표로, 이 값이 클 수록 방향성과 규칙성이 없는 chaos가 됨을 뜻한다. 다시말해 이것이 크다는 것은 아무것도 예측 불가능한 카오스 상태이고, 예측가능한 세계, 지능적인 행위는 이 엔트로피가 매우 낮은 경우에 해당한다.

https://ko.wikipedia.org/wiki/%EC%A0%95%EB%B3%B4_%EC%97%94%ED%8A%B8%EB%A1%9C%ED%94%BC#.EC.97.B4.EC.97.AD.ED.95.99.EC.A0.81_.EC.97.94.ED.8A.B8.EB.A1.9C.ED.94.BC.EC.99.80.EC.9D.98_.EA.B4.80.EA.B3.84



Joint Entropy

확률 p(x)와 확률 p(y)가 동시에 일어날 확률을 p(x, y) 즉 교집합의 확률로 확장하는 것처럼, Entropy에 대해서도 동일하게 확장을 한 것을 의미한다.

따라서 Joint Entropy는 p(x, y)에 대한 엔트로피, 즉 교집합의 엔트로피라고 말할 수 있다. 예를 들면, x는 동전의 사건이고 y가 주사위의 사건라면 동전과 주사위를 동시에 던지는 사건에 대한 엔트로피를 구한 것이다.

Joint Entropy의 정의는 다음과 같다.

단순히 엔트로피의 정의에서 2개의 사건에 대한 확률로 확장한 것이다. 그래서 만약 x와 y가 서로 독립이라면, H(x, y) = H(x) + H(y)가 된다.



Conditional Entropy
Conditional Entropy는 조건부 확률 p(x | y)의 개념을 Entropy로도 확장하여 적용한 것이라고 볼 수 있다. 즉 Y라는 사건이 일어났을 떄, X의 불확실성을 측정한 것이다. 즉 conditioned 정보량에 대한 평균이다.

아래 수식의 가장 첫 번째 줄이 Conditional Entropy에 대한 정의이고, 그 뒤로 나오는 수식은 이것을 변형시켜서 Joint Entropy - Entropy 형태로 변형 가능한 것을 보인 것이다.


그런데 이 수식을 자세히 보면 Joint Entropy와 정의가 매우 흡사하단 것을 알 수 있다. 다만 정보량이 logP(x,y)에서 logP(x | y)로 바뀐 것이 유일한 차이이다.

결국 이를 해석하면 X,Y의 교집합의 정보량에서 Y의 정보량을 뺀 것이 된다.


한가지 주의할 점은 y conditioning을 정보량에 대해서만 해야지, 평균을 내는 확률 p(x, y)에 대해서 하지 않는 다는 것이다. 만약 양쪽다 y로 conditioning을 하게되면 이는 그냥 p(x | y)에 대한 Entropy이지, X의 Y에 대한 Conditional Entropy가 아니다. 

이렇게 이상하게 되는 이유는 Conditional Entropy의 정의가 p(x|y)에 대한 정보량의 평균을, 다시 y로 평균내도록 되어있기 때문이다. 아래의 수식을 보면 좀더 이해가 잘 것이다.
H(X|Y)=\mathbb {E} _{Y}[H(X|y)]=-\sum _{y\in Y}p(y)\sum _{x\in X}p(x|y)\log p(x|y)=-\sum _{x,y}p(x,y)\log {\frac {p(x,y)}{p(y)}}.



Mutual Information
Mutual Information은 Conditional Entropy의 정의에서 p(x)로 정보량을 한번 더 나눈 차이가 있다. 기본적으로 정보 이론에서 정의된 여러가지 metric들은 아주 미세한 수식의 차이로 다른 정보를 측정할 수가 있다. 

그 중에서도 Mutual Information은 X와 Y가 서로 독립인지 아닌지에 대한 정도를 정보량으로 측정한 것이다. 

다음 수식에서 첫줄은 Mutual Information에 대한 정의이다. 그리고 Mutual Information은 보통 I 라는 문자를 쓴다. 그 이유는 아마도 Mutual Information에서는 Entropy와 달리 음수 부호가 앞에서 빠지기 때문이 아닐까 싶다.

먼저 첫째 수식을 잘 보면 평균낼 정보량 부분이 x와 y가 서로 독립이면 0이 된다.(분자 분모가 약분되어 1이 되므로) 반면에 서로 종속인 정도가 심하면 값이 커지게 된다.
즉 Mutual Information은 X, Y 변수가 서로에 의해서 영향받는 정도를 정보량으로 측정한 것이다.

그리고 나머지는 다양한 수식 전개 방법을 통해 서로 동치인 Mutual Information을 증명한 것이다.



2.Distance Metric of PDF

지금까지 배운 방법들이 정보량을 측정하는 것 혹은 독립과 종속의 정도를 측정하는 것이었다면, 지금부터는 두 확률분포 사이의 거리를 측정하는 방법에 대해서 다루어본다.

Cross Entropy

먼저 Joint Entropy와 자주 헷갈릴 수 있는 개념으로 크로스 엔트로피가 존재한다. Joint Entropy는 하나의 확률 분포 p에 대해서 X와 Y 두개의 사건이 갖는 정보량으로 정의된 반면, 크로스 엔트로피는 두개의 확률 분포 p와 q에 대해 하나의 사건 X가 갖는 정보량으로 정의된다.

즉 서로 다른 두 확률 분포에 대해, 같은 사건이 가지는 정보량을 계산한 것이다. 그래서 두 가지 확률 사이의 정보량이라는 의미에서 크로스라는 말이 들어갔다.


두 확률 분포 p, q 사이에 존재하는 정보량을 계산하는 방법. 정확히는 q에 대한 정보량을 p에 대해서 평균낸 것이다. 이때 머신러닝에서는 p는 underlying true 확률 분포를 사용하고, q는 model의 예측 확률 분포를 사용한다. 그리고 이 크로스 엔트로피를 Loss로 정의해서 minimize하는 방식으로 클래시피케이션 알고리즘을 학습하는 경우가 많다. 

그런데 이러한 방식의 원리를 제대로 이해하기 위해서는 다음에 나오는 KL Divergence를 이해하고 이를 사용해서 해석해야만 한다.


https://en.wikipedia.org/wiki/Cross_entropy


* 2-Class classification의 supervised learning에서의 CrossEntropy


여기서 잠시 아까 위에 나왔던 이 문장의 편리함을 짚고 넘어가자.

"p 가 0이면, p*logp도 0이다"

이 속성으로 때문에 항상 deep learning을 학습할 때, p는 true 확률 분포, q는 모델의 예측 확률분포를 사용하게 된다. p의 true 분포의 경우 2 class인 경우에 보통 정답이 1, 오답이 0으로 주어지게 된다. 정답인 경우는 p(y)값이 1이므로 별문제없이 수식을 계산할 수 있고, 오답이 0인 경우에도 0*log0 = 0 이라는 편리함 덕분에 해당 항이 사라지면서 쉽게 계산이 가능하다.

그런데 만약 p가 모델의 예측분포이고, q가 true 확률 분포라면 이러한 계산이 불가능해진다. 모델의 예측확률은 보통 정확하게 0이나 1이 나오는게 아니고 0~1 사이의 어떤 실수값이 계산되기 때문에(특히 학습 초반에는 0.5 근처의 값이 나옴), 0.5 * log 0 같은 값을 계산해야하는 상황이 발생한다. 이 값은 -무한대이기 때문에 학습이 불가능한 loss가 된다. 따라서 항상 CrossEntropy를 쓸 때는 p가 true 분포, q가 모델의 분포인 것이다.


KL Divergence(=relative entropy, information gain)

KL Divergence(줄여서 D_KL)는 두 확률 분포 p, q 간의 거리를 측정하는 방법이다. (거리에 대한 측정을 의미하기 때문에 음수 부호는 빠진다. 또한 조건부 확률에서 처럼, p||q 이면 q가 분모에 위치한다.)

위 수식을 잘 이해해보면, p(x)와 q(x)의 값이 항상 같을 경우, 정보량에 해당하는 부분은 항상 값이 1이 된다. 이 값이 1이되면 D_KL값은 항상 0이 되고, 두 분포간의 거리가 0인 것을 의미한다.

이를 다시 해석하면 KL Divergence는 (마치 importance sampling에서처럼) p(x)와 q(x)의 세로 길이비를 log scale에서 측정한 다음 평균(또는 적분)낸 것이라고 볼 수 있다. 그리고 D_KL은 분자분모가 바뀜에 따라 거리 측정 값이 변하므로 symmetric하지가 않다.



그런데 이때 수식을 잘 변형하면 다음과 같이 Cross Entropy를 D_KL을 이용해서 표현 가능해진다.


즉 CrossEntropy는 사실 D_KL 과 Entropy를 더해서 두 분포의 차이를 측정한 것이다!



즉 p,q의 크로스엔트로피에서 p의 엔트로피를 뺀 값.

D 는 두 확률 분포 p,q가 같을 때 0이 된다. (이는 jensen's 부등식으로 증명가능하다.)
즉 D 값이 클 수록 두 확률 분포

KL Divergence는 p,q사이의 차이를 나타내는 수치


http://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence


CrossEntropy Minimization의 원리

인데 이때 H(p)는 항상 상수이다.(p가 underlying true 분포이므로) 따라서 이를 최소화시키는 것은 D_KL값을 최소화하는 것이 되고, 이는 우리가 예측한 모델의 분포q와 p가 동일해지기를 바라는 것이다.

https://en.wikipedia.org/wiki/Cross_entropy#Cross-entropy_minimization


그런데 뉴럴넷에서 D_KL을 안쓰고, CrossEntropy를 쓰는 이유는 

위의 수식에서 H(p, q)는 계산이 쉽지만, D_KL 또는 H(p)를 계산하는 것은 어렵기 때문이다.(수식적으로)


- 뉴럴 넷에서의 Softmax, Cross-entropy

뉴럴 넷에서 3클래스 이상인 멀티클래스 문제에서는 softmax 를 사용해야한다. output 3개의 노드를 logistic regression 으로 각 클래스가 맞을 확률을 나타내는 것 보다, softmax 를 사용해 셋중에 오직 하나의 노드만을 가리키도록 제한을 두는 것이 더 강한 조건이며, 클래시피케이션에 더 적합하기 때문이다.

logistic regression 으로 각 클래스를 가리키면 이론상 모두 다 1,1,1 로 나타나는 경우도 가능한 반면 softmax는 반드시셋을 다합쳐서 1인, 확률로써 나타내야한다. 따라서 멀티클래스의 문제 세팅에는 softmax가 훨씬 더 잘 맞고 성능도 더 잘나온다.



Binary class에서 ouput 뉴런에 사용하는 logistic regression을 multi class에서는 softmax로 바꾸고
[ yk=시그모이드(WK) ---> yk=exp(z)/sum(expZ) ] 
Loss function LSE를 cross-entropy로 바꾸면
[ Error = 1/2 sum{yk-tk}^2 ---> Error = -P(t)*logQ(y)]
위 두식을 이용해 Error함수를 W로미분한 백프로퍼게이션 식이 서로 동일하다.


(수식 전개는 PRML 205쪽과 242쪽 참고)


이 때 Loss function은 [softmax일 경우 cross entropy]를 사용한다. 그러면 [logistic regression에서 Least Sqaured Error]을 사용한것과 동일한 백프로퍼게이션 식이 계산된다.

멀티클래스에서는 Loss function 이 cross entropy이고, 바이너리클래스에서는 least squared error이다.


# 뉴럴넷에서 Softmax output node를 사용하는 경우 쓰이는 Loss인 CrossEntropy는 다음과 같이 해석한다.

D는 minibatch 사이즈를 의미하고, k는 클래스의 개수를 의미한다.
P(Td=k) 는 데이터의 y 레이블을 의미한다. y 레이블은 보통 one-hot-coding의 형태로 K dimensional vector 중 1개의 값만 1이고 나머진 0으로 주어진다.
Q(Od=k) 는 [0,1]사이의 값으로 뉴럴 넷의 K번째 output 노드가 정답으로 켜질 확률을 추론한 값이다.

이 값을 잘 분석해 보면 결국 이렇게 분석된다.


P(Td=k) 값은 오직 데이터의 레이블이 K일 때에만 1의 값을 갖고, 그이외에 경우에는 무조건 0의 값만을 갖는다. 즉 위의 수식에서 오직 정답에 해당하는 logP(Od=k) 값만 살아남고, 나머지는 다 0으로 사라지는 것이다.

그러므로 이는 [정답을 예측한 노드의 logP(Od=k)] 값을 최대화시키는 방향으로 학습이 이뤄지는 것이다.. 즉 그냥 단순히 정답 레이블의 output node 값이 100%의 확률이 되도록 하는 objective function이다.

* 이때 CrossEntorpy = -log(모델이 정답 레이블을 예측한 확률의 합, P(y=K|x)) 이므로, 
는 Likelihood = P(y=K|x)의 정의에 따라 완벽하게 NNL(Negative Log Likelihood)과 동치가 된다.
즉 Softmax의 Loss function = 
NLL = CrossEntropy

http://en.wikipedia.org/wiki/Jensen's_inequality



Total Variation


https://en.wikipedia.org/wiki/Total_variation


Jenson Shannon Divergence


https://en.wikipedia.org/wiki/Jensen%E2%80%93Shannon_divergence


Wasserstein Distance


https://en.wikipedia.org/wiki/Wasserstein_metric



by 곽동현 이스텔리앙 2014.09.29 23:00
  • 윤영근 2017.05.26 12:06 ADDR EDIT/DEL REPLY

    유익한 글 잘 학습하고 갑니다. 덕분에 쉽게 이해했습니다. 감사합니다.