[PML intro] Ch6 Information Theory (Sec.6.3 Mutual Information - 8)

지난 포스팅의 [PML intro] Ch6 Information Theory (Sec.6.3 Mutual Information - 7)에서는 충분통계량 (Sufficient Statistics)에 대해서 설명하였습니다. 오늘은 Fano의 부등식 (Fano's Inequality)에 알아보도록 하겠습니다. 

 

특징 선택에서 흔히 쓰이는 방법 중 하나는 입력 특징 $X_{d}$ 중에서 응답변수 (예측) $Y$와의 상호정보량 $\mathbb{I}(X; Y)$가 큰 것들을 고르는 것입니다. 이번 포스팅에서는 이러한 직관적인 이해를 보다 엄밀하게 증명해보는 시간을 가져보겠습니다. 이 과정에서 쓰이는 것이 바로 Fano의 부등식 (Fano's Inequality)으로 어떤 분류 방법을 쓰든 오분류 확률을 "특징 $X$와 예측 $Y$ 사이의 상호정보량"으로 하한 (bound)할 수 있게 됩니다. 

 

정리1. Fano의 부등식 (Fano's Inequality)

Y \rightarrow X \rightarrow \hat{Y}$가 마르코프 체인을 이루는 특징 $X$와 예측 $Y$ 사이의 추정기 $\hat{Y} = f(X)$를 고려하자.여기서 $E = \{ \hat{Y} \neq Y \}$를 오류가 발생한 사건인 오류 사건 그리고 $P_{e} = P(Y \neq \hat{Y})$를 오류 확률이라고 하자. 그러면 다음과 같은 부등식을 얻을 수 있다. 

 

$$\mathbb{H}(Y \mid X) \le \mathbb{H}(Y \mid \hat{Y}) \le \mathbb{H}(E) + P_{e} \log |\mathcal{Y}|$$

 

이때, $\mathbb{H}(E) \ge 1$이기 때문에 다음과 같은 부등식으로 약화시켜서 쓸 수 있다. 

 

$$1 + P_{e} \log |\mathcal{Y}| \ge \mathbb{H} (Y \mid X)$$

 

따라서 최종적으로 다음과 같은 부등식을 얻을 수 있다. 

 

$$P_{e} \ge \frac{\mathbb{H}(Y \mid X) - 1}{\log |\mathcal{Y}|}$$

 

즉, $\mathbb{H}(Y \mid X)$를 최소화하면 이는 $\mathbb{I}(X ; Y)$를 최대화하는 것과 동치이며 오류 확률 $P_{e}$의 하한도 함께 낮아지게 된다. 

 

Proof

엔트로피의 체인 룰을 쓰면 다음과 같이 두 가지 다른 표현을 얻을 수 있습니다. 

 

$$\begin{cases} \mathbb{H}(E, Y \mid \hat{Y} ) &= \mathbb{H}(Y \mid \hat{Y}) + \mathbb{H} (E \mid Y, \hat{Y}) \\ \mathbb{H}(E, Y \mid \hat{Y}) &= \mathbb{H}(E \mid \hat{Y}) + \mathbb{H}(Y \mid E, \hat{Y}) \end{cases}$$

 

이때, $Y$와 $\hat{Y}$이 결정된다면 오류 사건 $E$은 결정되버리기 때문에 불확실성이 0이 되므로 $\mathbb{H}(E \mid Y, \hat{Y}) = 0$이 됩니다. 

 

이번에는 두 번째 식의 두번째 항 $\mathbb{H}(Y \mid E, \hat{Y})$을 보도록 하겠습니다. 

 

$$\mathbb{H}(Y \mid E, \hat{Y}) = P(E = 0)\mathbb{H}(Y \mid \hat{Y}, E = 0) + P(E = 1)\mathbb{H}(Y \mid \hat{Y}, E = 1)$$

 

여기서 $E = 0$이라면 $\hat{Y} = Y$이므로 $\mathbb{H}(Y \mid \hat{Y}, E = 0) = 0$이 이 됩니다. 또한, $E = 1$ 이라면 최악의 경우 $|\mathcal{Y}|$개 중 하나가 될 수 있으므로 $\mathbb{H}(Y \mid \hat{Y}, E = 1) \le \log |\mathcal{Y}|$가 되어 다음과 같이 식을 전개 할 수 있습니다. 

 

$$\mathbb{H}(Y \mid E, \hat{Y}) \le (1 - P_{e}) \cdot 0 + P_{e} \log |\mathcal{Y}|$$

 

결과적으로 기존 식을 다음과 같이 변형할 수 있습니다. 

 

$$\begin{align} \mathbb{H}(Y \mid \hat{Y}) &\le \mathbb{H}(E \mid \hat{Y}) + \mathbb{H}(Y \mid E, \hat{Y}) \le \mathbb{H}(E) + P_{e} \log |\mathcal{Y}| \end{align}$$

 

마지막으로 데이터 처리 부등식에 의해 $\mathbb{I}(Y; \hat{Y}) \le \mathbb{I}(Y; X)$이므로 $\mathbb{H}(Y \mid X) \le \mathbb{H}(Y \mid \hat{Y})$가 되어 Fano의 부등식이 성립하게 됩니다.