이전에는 Gini 불순물에 대해 논의했다. 엔트로피 불순도 (Entropy Impurity) 또한 결정 트리가 사용하는 분할 기준 중 하나이다. 이 불순도를 더 잘 이해하기 위해 Log likelihood와 KL divergence의 관점에서 해석하여 보자.
Log likelihood와 KL divergence는 머신러닝에 있어 굉장히 중요하고 유용한 개념들이다. 너무 많은 수학적 세부 사항으로 들어가지 않고, 얕게나마 기본 개념을 이해하려고 노력해 보자. 이들을 정의하고 간단히 설명한 다음 이 두 개념을 사용하여 엔트로피 불순도 공식을 유도해 보겠다.
[엔트로피 불순도 공식]
주어진 노드 $m$ 에 대한 엔트로피 불순도의 공식은 다음과 같다:
$$ – \sum_{j=1}^{J} \frac{c_j}{n_m} \log \Big( \frac{c_j}{n_m} \Big) $$
$ c_j = $ 현재 노드의 클래스 $j$에 해당하는 데이터의 개채(행)의 수
$ n_m =$ 현재 노드의 총 행 수
$ J =$ 총 클래스 수
아래는 파이썬 패키지 Sklearn의 결정 트리 소스코드에서 엔트로프 불순도를 계산하는 부분의 의역이다. 실제 코드와 거의 동일하다.
entropy = 0
for c in range(n_classes):
count_k = sum_total[c]
# number of instances that corresponds to class c in current node
count_k /= n_node_samples
# n_node_samples = the number of samples in the current node
entropy -= count_k * log(count_k)
return entropy
proxy_impurity_improvement = (- weighted_n_right * impurity_right
- weighted_n_left * impurity_left)결정 트리 노드는 proxy_impurity_improvement의 최대 지점에서 Split한다. 다시 말해, 엔트로피 불순도 측정값이 작을수록 좋다.
[Non Parametric Log Likelihood로 부터의 동기부여]
Likelihood는 무엇인가? Likelihood는 본질적으로 이벤트-확률 맵핑 함수가 주어졌을 때 특정 이벤트의 관측 확률이다.
$$ Pr(\text{관측} ; \text{맵핑 함수}) $$
매핑 함수가 Parametric 모델이고 이 모델이 고정된 $ \theta $로 완전히 정의될 수 있는 경우 다음과 같이 나타낼 수 있다.
$$ L(\theta | \text{관측}) = Pr(\text{관측} ; \theta) $$
각각의 관측 이벤트가 independent하면, product rule에 의해 N개의 이벤트 관측은 다음과 같이 쓸 수 있다 :
$$ L = \prod_{i=1}^{N} Pr(관측_i; \theta) $$
수학을 쉽게 풀이하기 위해, 보통 log likelihood를 사용한다.
$$ l = \log(L) = \sum_{i=1}^{N} \log \Big( Pr(관측_i; \theta) \Big)$$
맵핑 함수는 꼭 parametric 모델일 필요는 없다. 임의의 함수 h 일 수도 있다. $h(X) = Pr(y=j|X)$라고 가정해보자.
그리고 이 함수의 estimator를 $ \hat{h} $이라고 하자. 그러면 다음과 같이 나타낼 수 있다.
$$ l = \sum_{i=1}^{N} \log \Big( Pr(y=j | X_i, \hat{h}) \Big) $$
$$ = \sum_{i=1}^{N} \log \hat{h}_{y_i}(X_i)$$
$$= \sum_{i=1}^{N} (\textbf{y}_i)^\intercal \log \hat{h}(X_i) $$
$$ = \sum_{i=1}^{N} \sum_{j=1}^{J} y_{ij} \log \hat{h}_j(X_i)$$
따라서 위 양을 극대화하거나 그의 음수를 최소화해야 한다:
$$ – \sum_{i=1}^{N} \sum_{j=1}^{J} y_{ij} \log \hat{h}_j(X_i)$$
[DL divergence로 부터의 동기부여]
엔트로피란 무엇일까? 엔트로피 $ H (p) $는 확률 $p$에 대해 최적화된 코드를 사용하는 평균 메시지의 길이이다. 그게 도대체 무슨 뜻인가?
간단한 예시를 들어 보자. “dog”, “cat”및 “horse”라는 단어로 구성된 메시지를 보내려 한다고 가정해 보자. 각 단어는 비트로 인코딩된다. (예 : “dog”= 0, “cat”= 10, “horse”= 111). 여기서 인코딩을 통해 통신 비용을 최대한 낮게 해야 한다. 통신을 저렴하게 하기 위해 짧은 비트로 대부분의 횟수를 전달하는 단어를 인코딩해야 한다. 단어의 빈도가 낮을수록 비교적 긴 비트 인코딩을 할 수 있다. (예: “dog”가 100번 통신될 때 “horse”가 2번만 통신된다면 “dog”를 0으로 인코딩 하고 “horse”를 111로 인코딩해야 전달해야 하는 비트의 총수를 최소화할 수 있기 때문이다.)
메시지를 유일하게 디코딩할 수 있게 만들기 위해서는 (이 주제에 대해 별도의 블로그를 작성할 예정이다) $ p $의 확률을 가진 단어의 가장 효율적인 비트 길이는 $ \log_2 \big( \frac {1} {p} \big) $이라는 걸 수학적으로 증명할 수 있다.
$ p $의 엔트로피는 다음과 같이 정의된다:
$$H(p) = \sum_{x \in \text{words}} p(x) \log_2 \big( \frac{1}{p(x)} \big) = -\sum_{x \in \text{words}} p(x) \log_2 p(x) $$
이 (증명 되지 않은) 명제를 통해 이것이 확률 $p$에 대해 가장 최적화된 인코딩을 사용했을 때의 평균 메시지 길이라는 것을 알 수 있다.
그러면 크로스 엔트로피란 무엇일까? $ p $에 대한 $ q $의 크로스 엔트로피($ H_p (q) $)는 $ p $에 최적화 된 비트 인코딩을 사용하여 $ q $의 확률로 배분된 메시지를 통신 전달 할 때의 평균 메시지 비트 길이이다. 그게 무슨 뜻 일까?
우리가 $ p $ 용으로 설계된 비트 인코딩을 사용하고 있기 때문에 해당 비트 인코딩을 사용하면 $ q $분포의 단어를 의사소통하는 데 효율적이지 않다. 직관적으로, 이 비효율은 두 분포 사이의 차이가 클 경우 더 크다.
$ p $에 대한 $ q $의 크로스 엔트로피는 다음과 같이 정의한다.
$$H_p(q) = \sum_{x \in \text{words}} q(x) \log_2 \big( \frac{1}{p(x)} \big) = – \sum_{x \in \text{words}} q(x) \log_2 p(x) $$
우리는 이 공식을 $ p $를 위해 설계된 코드 길이 $ \log_2 \big (\frac {1} {p (x)} \big) $가 $ q $의 분포도를 따라 전달될 때의 평균 비트 길이로 해석 할 수 있다. 따라서 이 평균 비트 길이는 $ q $의 엔트로피보다 길다: ($q$와 $p$의 분포가 다르다는 가정하에)
$$ H(q) < H_p(q)$$
마지막으로 KL Divergence란 무엇인가? $ p $에 대한 $ q $의 이른바 Kullback-Leibler Divergence는 엔트로피와 크로스 엔트로피의 효율성의 불일치를 측정 한 것이다.
$$D_{KL}(q || p) = H_p(q) – H(q) = \sum_{x \in \text{words}} q(x) \log \Big( \frac{q(x)}{p(x)} \Big)$$
즉, $ p $에 대한 $ q $의 KL Divergence는 다른 분포 $ p $를 사용하여 $ q $를 전달했을 때의 효율성의 손실 측정값이다. 그리고 우리는 이것을 두 분포 $ p $와 $ q $ 사이의 차이를 측정하는 것으로 해석할 수 있다.
위의 논의를 통해 엄밀히 말하면 교차 엔트로피는 손실 함수가 아니라는 것을 알 수 있다. 메시지의 평균 길이는 비트 단위이다. 반면에 KL Divergence는 손실로 해석 될 수 있다. 그러나 실제 practice에서는 “크로스 엔트로피 손실”을 최적화한다. 그 이유는 실제로, $ q $는 ground of truth이고 $ p $는 머신러닝 모델을 통해 예측 된 분포이다. 따라서 $ q $의 엔트로피는 KL Divergence에서 일정하므로, 사실상 크로스 엔트로피 “손실”를 최적화 하는 것과 동일한 결과를 가져온다.
따라서 KL Divergence의 관점에서 다음 손실 함수에 대해 최적화 (최소화)하는 것이 옳다.
$$ -\sum_{i=1}^{N} \sum_{j=1}^{J} y_{ij} \log \hat{h}_j(X_i)$$
여기서 우리는 Log likelihood에서와 같이 $ \textbf {y} _i $ 백터를 indicator 벡터가 아니라 모든 확률 가중치가 하나의 값에 집중되는 확률 분포로 해석하고 있다.
[증명]
이제 왜 다음 표현을 최소화 해야 하는지 적어도 2개의 관점을 통해 동기 부여를 했다:
$$-\sum_{i=1}^{N} \sum_{j=1}^{J} y_{ij} \log \hat{h}_j(X_i)$$
그러면 위의 양을 최소화함으로써 엔트로피 불순도에 도달 할 수 있음을 증명해 보자:
$$ – \sum_{j=1}^{J} \frac{c_j}{n_m} \log \Big( \frac{c_j}{n_m} \Big) $$
이전 결정 트리 블로그에서했던 것처럼, 현재 노드 내의 모든 샘플에 각 클래스에 대해 상수 근사를 내기 때문에 estimator의 샘플 인덱스를 무시할 수 있다.
$$-\sum_{i=1}^{N} \sum_{j=1}^{J} y_{ij} \log \hat{h}_j$$
$$ = – \sum_{j=1}^{J} \frac{c_j}{N} \log (\hat{h}_j) $$
$ c_j $는 response value가 클래스 $ j $에 해당하는 학습 데이터 행의 총 수이다.
우리는 또한 다음과 같은 제약이있다 :
$$ \sum_{j=1}^{J} \hat{h}_j = 1$$
따라서 다음과 같은 Lagrangian 함수를 만들 수 있다 :
$$ L = -\sum_{j=1}^{J} \frac{c_j}{N} \log ( \hat{h}_j ) + \lambda \big( \sum_{j=1}^{J} \hat{h}_j -1 \big) $$
그럼 Lagrangian 함수를 풀어보자:
$$\frac{\partial{L}}{\partial{\hat{h}_j}} = – \frac{1}{\hat{h}_j} \frac{c_j}{N} + \lambda = 0$$
$$ \implies \hat{h}_j = \frac{c_j}{N \lambda} $$
$$\frac{\partial{L}}{\partial{\lambda}} = \sum_{j=1}^{J} \hat{h}_j – 1 = 0$$
$$\implies \lambda = 1$$
따라서 우리는 원했던 결과를 도출할 수 있다:
$$ – \sum_{j=1}^{J} \frac{c_j}{N} \log \Big( \frac{c_j}{N} \Big) $$