[인공지능 및 기계학습 개론] 2.4 Entropy and Information Gain

이번 포스팅에서는 Entropy와 Information Gain에 대해서 알아보도록 하겠습니다.

 

http://www.edwith.org/machinelearning1_17/lecture/10582

[LECTURE] 2.4. Entropy and Information Gain : edwith

 

---

Entropy는 Uncertainty를 계량화한 것이라 보시면 됩니다. 그래서 entropy가 클수록 더 큰 uncertainty를 갖는 것이라 해석을 할 수 있습니다. 불확실성에 대한 얘기를 하는 것이기 때문에 feature들이 deterministic한 대상이 아닌 random variable로서 간주됩니다. 이를 formulate하면 아래와 같습니다.: $$ H(X)\coloneqq -\sum_x P(X=x)\log_2 P(X=x) $$ 여기서 쓰이는 log의 밑은 2일때도 있고 e일 때도 있습니다. 이 식은 사실 $\log_2 X$의 minus expectation과 정확히 같은 식입니다.

 

다음으로 Conditional Entropy는 주어진 특정 feature variable에 대한 entropy를 측정하고 싶을 때 사용하는데, 정의는 아래와 같습니다.: $$ \begin{aligned} H(Y|X)&\coloneqq\sum_x P(X=x)H(Y|X=x) \\ &= \sum_x P(X=x)\cdot\bigg(-\sum_y P(Y=y|X=x)\log_2 P(Y=y|X=x)\bigg) \end{aligned} $$ 이 때 $$ P(Y=y|X=x)=\frac{P(X=x,Y=y)}{P(X=x)} $$ 라는 식과 $\log$의 성질을 이용하면 conditional entropy는 아래와 같이 정리가 가능합니다.: $$ \begin{aligned} H(Y|X)&=\sum_x P(X=x)\cdot\bigg(-\sum_y P(Y=y|X=x)\log_2 P(Y=y|X=x)\bigg) \\ &= \sum_x\sum_y P(X=x,Y=y)\log_2\frac{P(X=x)}{P(X=x,Y=y)}. \end{aligned} $$

 

---

 

이제 이전 포스팅에서 예로 들었던 신용평가 예를 다시 생각해 볼까요? 

 

 

$Y$를 instances의 positive/negative를 나타내는 class variable이라고 하면 $Y$의 entropy는 아래와 같이 쓰여지는데요.: $$ H(Y)=-\sum_{y\in\{+,-\}} P(Y=y)\log_2 P(Y=y) $$ 예를 들어 positive case의 경우 아래와 같이 계산이 가능합니다. $$ P(Y=+)=\frac{307}{307+383} $$ 즉, MLE로 구해지는 것이죠.

 

Entropy는 불확실성이기 때문에 가능한 한 낮출 수 있는 방향으로 생각하고 싶습니다. 이를 위해서는 $A1$과 $A9$이 각각 $Y$의 entropy에 얼마나 영향을 주는지 알 필요가 있는데, 이것이 바로 conditional entropy죠. Formula는 아래와 같습니다.: $$ \begin{aligned} &H(Y|A1)=\sum_{x\in\{a,b,?\}}\sum_{y\in\{+,-\}}P(A1=x,Y=y)\log_2\frac{P(A1=x)}{P(A1=x,Y=y)} \\ &H(Y|A9)=\sum_{x\in\{t,f\}}\sum_{y\in\{+,-\}}P(A9=x,Y=y)\log_2\frac{P(A9=x)}{P(A9=x,Y=y)} \end{aligned} $$ 이를 이용하여 Information Gain을 다음과 같이 정의합니다.: $$ IG(Y,Ai)\coloneqq H(Y)-H(Y|Ai) $$ 즉, $Ai$에 대한 information gain이 크다는 것은 $Ai$가 주어졌을 때의 $Y$의 entropy가 작을 때, 즉 $Ai$에 대한 불확실성이 줄어들었을 때 information gain이 큰 것입니다. 현재 예의 경우 $A9$이 각 선택지마다 positive/negative의 선호도가 확실하므로 이에 대한 entropy는 상대적으로 $A1$보단 작을 것이며, 따라서 $A9$의 information gain이 더 클 것을 알 수 있습니다.

 

---

 

이런 information gain을 이용한 decision tree 관련 algorithm이 여럿 있는데, 강의에서는 그 중 하나로 ID3를 예로 들었습니다. ID3에 대한 설명은 강의 내용만 듣고는 이해가 잘 되지 않아 따로 공부를 해봤는데, 간단한 알고리즘이었습니다. 직접 예를 만들어보고자 했으나 생각보다 시간이 오래 걸리는 것 같아, 제가 공부할 때 봤던 좋은 포스팅 하나를 공유합니다.

 

https://tyami.github.io/machine%20learning/decision-tree-2-ID3/

의사결정 나무 (Decision Tree) ID3 알고리즘 설명

 

Rule based model보다는 decision tree가 더 좋아보이는데, 그럼 이게 만능일까요? Decision tree의 node의 수가 많아지면 많아질수록 training dataset에 대한 설명력은 올라가게 되지만, 계속해서 늘리기만 하다보면 training dataset에 overfitting이 되는 문제가 발생하게 됩니다. 그래서 일정 수준까지는 test data에 대해서도 accuracy등의 평가지표가 상승하게 되지만, 그 이상으로 넘어가게 되면 training dataset에 overfitting하게 되어 되려 generalization error가 커지게 되는 것이죠. 

 

 

---

 

Overfitting 얘기가 나온김에 말하자면, 이런 learning process를 가지고 있는 모든 algorithm이 갖는 대표적인 숙명들은 아래와 같습니다.

• training dataset의 quality,
  • 특히 supervised learning의 경우에는 labeling의 power가 어마어마하고 (이 경우 domain knowledge가 절대적이고),
    
    
• model의 capacity와 topology,
  • deep learning의 경우 batch 크기나 channel size만 늘린다고 무조건 좋아지는 것은 아니고,
  • task에 맞는 적절한 topology를 찾아내는 것 또한 보통 일이 아닙니다.
  • training dataset이 충분히 풍부하지 않은데 model의 capacity가 그에 비해 지나치게 크다면 training set을 모두 외워버리겠죠. (overfitting 우려)
    
    
• hyperparameter의 적절한 선택,
  • 무한에 가까운 경우의 수를 모두 무지성으로 넣어볼 수는 없을 것입니다.
    
    
• computing power,
  • 아무리 좋은 결과가 보장되어 있다 하더라도 한 번 돌리는데 100년 걸린다고 하면 아무도 시도하지 않겠죠.

 

---

 

이렇게 이번 포스팅에서는 entropy에 대한 개념을 통해 간단한 decision tree algorithm을 살펴보았습니다. 이번 포스팅은 여기서 마치겠습니다.