$\vec X$의 받침을 $\vec\xX$, $Y$의 받침을 $D := \{1,\ldots,m\}$라 하고 $f:\vec\xX \to D$를 임의의 분류기(classifier)라고 하자. $f^*$를 베이즈 분류기라고 하면, 즉 \begin{equation} f^*(\vec x) = j, \text{ where } j = \mathrm{argmax}_k\mysepp P\mysep[\mysep Y = k \mybar \vec X = \vec x\mysepp] \end{equation} 로 두면 \begin{equation} P[f(\vec X)\ne Y\mysepp] \ge P[f^*(\vec X)\ne Y\mysepp] \label{eq:bayesproof1} \end{equation} 가 성립한다는 것이 [정리 7.21]의 내용이다.
이 웹문서는 이 정리의 증명에서 사용한 보조정리(lemma) 2개를 증명한다.
증명을 쉽게 하기 위하여 $\vec X$는 이산형인 것을 가정한다. 하지만 여기서 제시하는 증명에서 $\sum$을 $\int$로 바꿔주기만 하면 $\vec X$가 연속형인 경우에 대한 증명으로 변환됨을 말해 둔다.
\eqref{eq:bayesproof1}을 보이기 위하여는 다음의 \eqref{eq:bayesproof2}를 보이면 충분하다. \begin{equation} (\forall \vec x\in \vec \xX )\quad P[f(\vec X)\ne Y\mybar \vec X=\vecx\mysep] \ge P[f^*(\vec X)\ne Y\mybar \vec X=\vecx\mysep] \label{eq:bayesproof2} \end{equation}
(보조정리 1의 증명).$\;$ 먼저 알아야 할 것은 확률변수 $X$의 받침을 $\xX$라 하고, 함수 $g_1:\xX\to\rR$, $g_2:\xX\to\rR$가 $(\forall x\in\xX)\bigl(g_1(x) \ge g_2(x)\bigr)$를 만족하면 \begin{equation} \eE_X[g_1(X)] \ge \eE_X[g_2(X)] \label{eq:lem11} \end{equation} 라는 사실이다. $X$의 확률함수를 $h$로 두면, \eqref{eq:lem11}의 좌변에서 우변을 뺀 것은
\begin{align*} & \sum_{x\in X} g_1(x)h(x) - \sum_{x\in X} g_2(x)h(x) = \sum_{x\in X} (g_1(x) - g_2(x))h(x) \ge 0 \end{align*}가 성립한다. $(\forall x)(h(x) \ge 0)$이므로 그러하다.
그러므로 이제 다음의 등식이 성립함을 보이면 보조정리 1이 증명된다. 단, 여기서 $f$는 임의의 분류기를 뜻하므로 $f$ 자리에 $\hat f$를 대신 넣어도 이 등식은 성립한다.
\begin{equation} P[f(\vec X)\ne Y] = \eE_{\vec X}\Bigl[P[f(\vec X)\ne Y \mybar \vec X = \vec x]\Bigr] \label{eq:lem12} \end{equation}\eqref{eq:lem12}의 증명은 실은 이 식에 등장하는 기호들의 정확한 정의만 알고 있으면 아주 쉽다.
먼저 \eqref{eq:lem12}의 좌변은, 결합확률분포 $(\vec X, Y)$의 확률함수를 $h(\vec x,y)$로 두면 $\sum_{f(\vec x)\ne y} h(\vec x, y)$로 나타낼 수 있으며, 이는 다시 \begin{align*} & R := \{(\vec x, y)\in\xX\times D\} \st f(\vec x) \ne y \} \\ & R_{\vec x} = \{ y \in D \st (\exists \vec x)(f(\vec x)\ne y)\} \end{align*} 로 두었을 때 다음과 같다. 아래의 식에서 $h_{\vec X}(\vec x) = \sum_y h(\vec x,y)$는 주변확률함수이다.
\begin{align*} P[f(\vec X)\ne Y] &= \textstyle \sum_{f(\vec x)\ne y} h(\vec x, y) = \sum_{(\vec x, y)\in R} h(\vec x, y) = \sum_{\vec x \in \xX}\sum_{y\in R_{\vec x}}h(\vec x, y) \\ &= \sum_{\vec x \in \xX}\sum_{y\in R_{\vec x}} \frac{h(\vec x, y)}{h_{\vec X}(\vec x)} \cdot h_{\vec X}(\vec x) = \sum_{\vec x \in \xX}h_{\vec X}(\vec x)\sum_{y\in R_{\vec x}}P[f(\vec x)\ne y \mybar \vec X = \vec x] \\ &= \eE_{\vec X}\Bigl[P[f(\vec X)\ne Y \mybar \vec X = \vec x]\Bigr] \end{align*} 이것으로써 \eqref{eq:lem12}를 보였고 보조정리 1의 증명은 완료되었다. $\;\checkmark$모든 $\vec x \in \vec \xX$와 $j_1, j_2 \in D$에 대해서 사건 $f(X) = j_1$과 $Y = j_2$는 $\vec X = \vec x$에 대하여 조건부 독립이다. 즉 다음의 식이 성립한다. (일반적으로 $\vec X$와 $Y$가 독립이 아님에도 불구하고 이러하다.)
\begin{equation} P[f(\vec X) = j_1,\; Y = j_2 \mybar \vec X = \vec x] = P[f(\vec X) = j_1\mybar \vec X = \vec x] \times P[Y = j_2 \mybar \vec X = \vec x] \end{equation}(보조정리 2의 증명).$\;$ [연습문제 4.13].(4),(5)에서 $P(A) = 1$ 또는 $P(A) = 0$이면 $A$는 모든 사건과 독립임을 보였는데, 이것의 증명과 거의 같은 방법으로 $P(A\mybar B)=1$ 또는 $P(A\mybar B)=0$이면 $A$는 모든 사건과 '$B$에 관하여 조건부 독립'임을 보일 수 있다.
$\vec X = \vec x \in \vec \xX$일 때 $f(\vec x) := j \in D$로 두면, $j=j_1$이거나 혹은 $j\ne j_1$이며 $P[f(\vec X) = j_1 \mybar \vec X = \vec x]$은 $j=j_1$일 때는 1이고 $j\ne j_1$일 때는 0이다. 따라서 어떤 경우든지 사건 $f(\vec X) = j_1$은 사건 $Y = j_2$와 '사건 $\vec X = \vec x$에 대해서 조건부 독립'일 수밖에 없다. $\;\checkmark$
[홈으로]