Bayes Optimal Predictor

이곳에서는 Bayes optimal predictor에 대해 살펴본다.

자료 $(X, Y) \in X \times {0, 1}$ 가 확률분포 $D$ 를 따르고 $X$ 가 이산확률변수라 하자. 이때 $X, Y$ 의 함수 관계를 예측하는 문제를 고려하자. 이는 이진 분류 문제로 이때 최적해는 다음과 같은 함수임이 알려져 있다.

f_{D} (x) = {1 (P (Y = 1∣ X = x)) > 1/2 0 o t h er w i se

$f_{D}$ 가 최적해라는 것은 다른 함수 $g : X \to {0, 1}$ 에 대해 다음이 항상 성립한다는 것을 의미한다. (a.k.a. $L_{D} (f_{D}) \leq L_{D} (g)$ )

P (f_{D} (X) \neq = Y) \leq P (g (X) \neq = Y)

이와 같은 $f_{D}$ 를 Bayes optimal predictor 라고 한다. $f_{D}$ 의 정의는 다음과도 동치이다.

f_{D} (x) = argmax_{y} P (Y = y ∣ X = x)

Proof of Bayes Optimal Predictor’s Optimality

이곳에서는 $X$ 가 이산 확률 변수인 경우만을 증명한다.

일반성을 잃지 않고 $f_{D}$ 와 $g$ 가 단 하나의 지점 $x^{'}$ 에서만 다르다고 가정하고, 이때 $f_{D} (x^{'}) = 1, g (x^{'}) = 0$ 이라고 하자. 이제 다음이 성립한다. ( $g$ 에 대해서도 동일하게 성립한다.)

P (f_{D} (X) \neq = Y) = E_{X, Y} (I (f_{D} (X) \neq = Y)) = x, y \in X, Y \sum I (f_{D} (x) \neq = y) P (X = x, Y = y)

따라서 $f_{D}$ 와 $g$ 의 loss의 차이는 $x^{'}$ 의 지점에서 결정된다는 사실을 알 수 있다. 가정에 의해 그 값은 각각,

(F or f_{D}) P (X = x^{'}, Y = 0) v . s . P (X = x^{'}, Y = 0) (F or g)

과 같이 주어진다. 이제,

(F or f_{D}) P (Y = 0∣ X = x^{'}) P (X = x^{'}) v . s . P (Y = 1∣ X = x^{'}) P (X = x^{'}) (F or g)

이고 $f_{D}$ 는 항상 더 확률이 높은 쪽을 선택함으로 부등호는 아래와 같다.

(F or f_{D}) P (Y = 0∣ X = x^{'}) \leq P (Y = 1∣ X = x^{'}) (F or g)

따라서 우리는 $f_{D}$ 의 loss가 항상 $g$ 보다 작거나 같음을 알 수 있다. $□$

위의 기댓값 $E_{X, Y} (I (f_{D} (X) \neq = Y))$ 을 조건부 기댓값을 사용해 전개해도 같은 결과를 얻을 수 있다.

(1) Shai Shalev-Shwartz, Shai Ben-David, Understanding Machine Learning, 22-30pp.