[Chapter2] Training versus Testing - (1)

2.1 Theory of Generalization

 학습에 사용되지 않은 데이터(out-of-sample)에 대한 error ( $E_{out}$ )는  학습된 모델을 새로운 데이터에 적용했을 때, 얼마나 잘 일반화(generalize)할 수 있는가를 나타낸다. $E_{out}$은 input space $\chi$ 전체에 걸쳐 영향을 받는다.(학습에 사용된 입력으로 모델이 훈련되고 결정된다. 그리고 학습에 사용된 데이터로는 generalization을 측정할 수 없다.) $E_{out}$을 추론할 때는 학습에 사용되지 않은 데이터 샘플을 사용해야 한다. 

 이와 달리 $E_{in}$은 학습에 사용된 데이터(in-sample)에 대한 error를 나타내고, 모델이 주어진 데이터에 대한 학습이 얼마나 잘 되었는지를 의미한다. 

 Generalization error.

 $E_{in}$을 보고  $E_{out}$으로 항상 generalize되는건 아니다. Hoeffding Inequality는 generalization error를 확률을 사용해 bound를 두는 방법을 보여준다,

$$\mathbb{P}[|E_{in}(g) - E_{out}(g) > \epsilon] \leq 2Me^{-2\epsilon^2 N},  \epsilon > 0 \tag{2.1}$$

 Pick a tolerance lever $\delta$, for example $\delta = 0.05$, and assert with probability at least $1-\delta$ that

$$E_{out}(g) \leq E_{in}(g) + \sqrt{\frac{1}{2N}ln \frac{2M}{\delta}} \tag{2.2}$$.

 위와 같은 부등식을 generalization bound 으로 부르기도 하는데, 왜냐하면 $E_{out}$에 대한 bound를 $E_{in}$으로 나타내기 때문이다. Hoeffding Inequality가 위의 generalization bound를 내포하는걸 보기 위해, 식 (2.1)로부터 (2.2)를 다음 과정을 거쳐 유도할 수 있다. 식 (2.1)로부터, $|E_{out}(g) - E_{in}(g)| \leq \epsilon$일 확률은 $1-2Me^{-2N\epsilon^2}$가 된다. 이 확률은 $E_{out} \leq E_{in} + \epsilon$의 경우를 내포하고, $\epsilon = \sqrt{\frac{1}{2N} ln \frac{2M}{\delta}}$로 두었을 때, $\delta = 2Me^{-2N\epsilon^2}$를 나타낼 수 있다.

 분명히 해야 할 점은 $E_{out} \geq E_{in} - \epsilon$의 경우도 내포하고 있다. This is important for learning, but in a more subtle way. 우리가 알고 싶은건 1) hypothesis $g$(training error가 가장 적은 모델)가 계속해서 새로운 데이터도 잘 설명할 수 있는가( $E_{out} \geq E_{in} + \epsilon$ ), 2) 다른 hypothesis와 비교해 최고의 hypothesis를 선택했는가( $E_{out}(g)$보다 더 나은 $E_{out}(h)$이 있는가, $h$는 $h \in H$ )이다. Hypothesis 집합에서 우리가 선택한 $g$를 제외한 나머지 집합의 원소 h에 대해 $E_{out}(h) \geq E_{in}(h) - \epsilon$가 된다면, $g$가 가장 best라고 말할 수 있다. h인 경우 $E_{in}$보다 $E_{out}$이 커지게 되고, $g$인 경우는 $E_{out}$과 비교해서 $E_{in}$이 $\epsilon$만큼 조금 더 크다.

 Error bound $\sqrt{\frac{1}{2N}ln \frac{2M}{\delta}}$는$M$에 dependent하다. 여기서 $M$은 hypothesis set $H$의 size를 의미하고, 만약 $H$가 infinite set이라면, bound 역시 무한으로 커지게 되고 이럴 경우 bound가 지닌 의미를 상실한다. 불행하게도, perceptron을 포함한 대부분 학습 모델은 infinite $H$를 가진다. 

 따라서 모델의 generalization을 연구할 때, $H$가 infinite일 경우에 적용할 방법을 고안해야 한다. $M$을 무언가 finite로 바꾸기 위해 $M$을 어떻게 얻었는지 다시 볼 필요가 있다. ( we got the M factor in the first place was by taking the disjunction of events )

$"|E_{in}(h_1) - E_{out}(h_1)| > \epsilon" \mathbf{or}$

$"|E_{in}(h_2) - E_{out}(h_2)| > \epsilon" \mathbf{or}$

$ \vdots $

$"|E_{in}(h_M) - E_{out}(h_M)| > \epsilon" \tag{2.3}$

 식 (2.3)을 통해 $|E_{in}(g) - E_{out}(g)| > \epsilon$인 경우를 항상 포함하는걸 보장하는데, 왜냐하면 $g$는 hypothesis 집합 $H$에 포함되기 때문이다. 그러고 나서 union bound를 통해 확률을 over-estimated했다. $B_m$을 

$|E_{in}(h_M) - E_{out}(h_M)| > \epsilon$에 해당되는 경우라고 가정하자. 이렇게 했을 때 식 (2.3)을 아래와 같이 작성할 수 있다. 

$\mathbb{P}[B_1 \; \mathbf{or}\; B_2\; \mathbf{or} \dots\; B_M] \leq \mathbb{P}[B_1] + \mathbb{P}[B_2] + \dots + \mathbb{P}[B_M]$

 만약 $B_1, B_2, \dots\; , B_M$의 event가 많이 겹치는 경우인 아래의 그림을 생각해보자.

 여기서 각각의 원은 hypothesis로 보면 되고, 면적은 hypothesis에 대한 확률을 의미한다. 여기서 $B_1, B_2, B_3$ 전체의 확률은 각각의 확률보다 조금 낮을 뿐, 각각의 확률을 더할 경우 부등호는 참(true)이지만 매우 강하게 overestimating한 값이 되버린다. 

 event "$|E_{in}(h_m) - E_{out}(h_m)| > \epsilon,\;m=1, \dots M$"은 종종 strongly overlapping된다. 만약 $h_1$과 $h_2$가 서로 비슷하다면, 두 개의 event "$|E_{in}(h_1) - E_{out}(h_1)| > \epsilon$"과 "$|E_{in}(h_2) - E_{out}(h_2)| > \epsilon$"는 대부분의 dataset에서 일치할 것이다. 만약 perceptron모델에서 weight값을 조금씩 변화시키는 것으로 instance를 만든다면, 무한의 weight vector $W$를 만들 수 있지만 대부분 비슷한 결과를 보일 것이다. 

 generalization을 표현할 때 이러한 접근법보다는, 만약 다른 hypotheses에 대해 overlap을 적절히 측정할 수 있다면 무한의 hypotheses의 개수 M을 대체할 유한의 값을 고안할 수 있을 것이다.  그리고 $E_{out}$에 가까이 가는 $E_{in}$의 조건 역시 발견할 수 있을 것이다.