Online Learning, Overfitting and Black Swan Paradox

Online Learning

Machine learning에는 크게 batch learning과 online learning이 존재한다.

만약 데이터 1000만 개가 존재할 때 batch learning은 이를 한 번에 넣어서 학습을 진행하는 반면, online learning은 1~5000, 5001 ~ 10000 이런 식으로 나누어 학습을 진행한다.

online learning에서 고려해야하는 점은 항상 결과가 같은지 다른지 이다.

batch learning의 posteior는 위에서 정의한 수식과 같다. 하지만 online learning의 경우에는 약간의 차이가 있다. 데이터가 $D_{a}, D_{b}$로 나뉘었다고 가정을 하면 posterior는 아래 수식으로 표현된다.

$$ p(\theta \mid D_{a}, D_{b}) \propto p(D_{b} \mid \theta)p(\theta \mid D_{a}) \\ \propto \text{Bin}(N_{1}^{b} \mid \theta, N_{1}^{b} +N_{0}^{b})\text{Beta}(\theta \mid N_{1}^{a} +a , N_{0}^{a} + b) \\ \propto\text{Beta}(\theta \mid N_{1}^{a}+N_{1}^{b}+a, N_{0}^{a}+N_{0}^{b}+b) $$

Posterior Mean and Mode

Beta Binomail model의 properties를 알아보기 위해 이전에 설명했던 Beta 분포를 소개할 때 알아보았던 mean과 mode를 사용한다.

식은 다음과 같다.

$$\text{mean}=\frac{a}{a+b}, \ \text{mode}=\frac{a-1}{a+b-2},\ \text{var}=\frac{ab}{(a+b)^2(a+b+1)} $$

이를 Beta binomail에 적용하게 되면, posterior가 $\text{Beta}(\theta|N_1+a,N_0+b)$ 이므로 MAP estimate를 다음과 같이 구할 수 있다.

$$ \hat\theta_{MAP}=\frac{a+N_1-1}{a+b+N-2}$$

mode는 모든 구간에 대한 최대 빈도수를 의미하기 때문에 이를 적용한다. 여기서 coin toss의 예시를 적용해보면 분모 term은 total이고, 분자 term은 head에 해당하는 counts를 의미한다고 생각하면 된다.

만약 uniform prior를 사용한다면 $a= b=1$이므로, MAP estimate는 다음 수식과 같은 empirical fraction of heads인 MLE로 감소한다.

$$ \hat\theta_{MLE}=\frac{N_1}{N} $$

위 수식은 직관적으로 이해가 되지만, 아래 수식의 likelihood function을 maximize 하기 위해 식을 도출 할 수도 있다.

$$ p(\mathcal D|\theta)=\theta^{N_1}(1-\theta)^{N_0} $$

반대로 posterior mean은 다음과 같이 구할 수 있다.

$$ \bar\theta=\frac{a+N_1}{a+b+N} $$

이러한 mode와 mean의 차이는 나중에 중요하게 다룰 것이다.

$a_{0} = a+b$는 strength를 제어하는 prior의 샘플 크기이고, prior mean을 $m_{1} = \frac{a}{a_{0}}$라고 생각해보자. 그러면 다음 수식에 의해 posterior mean을 구할 수 있다.

$$ \mathbb E(\theta|\mathcal D)=\frac{\alpha_0m_1+N_1}{N+\alpha_0}=\frac{\alpha_0}{N+\alpha_0}m_1+\frac{N}{N+\alpha_0}\frac{N_1}{N}=\lambda m_1+(1-\lambda)\hat\theta_{MLE} $$

여기서 $\lambda=\frac{\alpha_0}{N+\alpha_0}$는 posterior equivalent size에 대한 prior의 비율이고, 일종의 가중치라고 생각하면 된다. 따라서 prior가 약할수록 $\lambda$가 작아지고, posterior mean이 MLE에 가까워지는 것을 알 수 있다.

마찬가지로, posterior mode는 prior mode와 MLE의 convex combination이며, MLE로 수렴한다.

 

Posterior Variance

mean과 mode는 point estimation을 진행하지만, 이에 대해 어느 정도 신뢰도를 갖는지를 아는 것이 유용하다. posterior의 variance는 이것을 측정하는 방법 중 하나이다.

Beta posterior의 variance는 다음과 같이 주어진다.

$$ \text{var}[\theta|\mathcal D]=\frac{(a+N_1)(b+N_0)}{(a+N_1+b+N_0)^2(a+N_1+b+N_0+1)} $$

$N=N_1+N_0\gg a,b$ 인 경우, 복잡한 위 식을 다음과 같이 근사할 수 있다.

$$ \text{var}[\theta|\mathcal D]\approx\frac{N_1N_0}{NNN}=\frac{\hat\theta(1-\hat\theta)}{N},\text{where }\hat\theta\text{ is the MLE} $$

따라서 이를 활용해 posterior standard deviatation를 쉽게 구할 수 있다.

$$ \sigma=\sqrt{\text{var}[\theta|\mathcal D]}\approx\sqrt{\frac{\hat\theta(1-\hat\theta)}{N}} $$

우리의 estimate의 error는 standard deviation을 이용한다. $N$이 커지면 표준 편차는 작아지고, 반대로 작아지면 표준 편차는 커진다. $\theta$가 극단적으로 1이라고 하면 0이되고, 0인 경우도 마찬가지이다.

$\theta$가 0.5일 때 최대화되며, 이는 coin toss를 예를 들어, coin이 공정하다고 하는 확신하는 것보다 편향되어 있다고 확신하는 것이 더 쉽다는 의미이다.

Posterior predictive distribution

지금까지는 unknown parameter의 추론에 초점을 맞춰 살펴보았다. 이제 미래의 관측이 가능한 데이터에 대한 prediction에 대해 알아보자.

$\text{Beta}(a, b)$ posterior에 따른 single future trail에서 Head의 확률에 대해 예측한다고 가정하자.

이를 다음과 같이 표현할 수 있다.

$$ p(\tilde x=1|\mathcal D)=\int_0^1p(x=1|\theta)p(\theta|\mathcal D)d\theta\\ =\int_0^1\theta\ \text{Beta}(\theta|a,b)d\theta=\mathbb E[\theta|\mathcal D]=\frac{a}{a+b} $$

이를 통해 알 수 있는 사실은 다음 시도에서 Head가 나올 확률은 $\frac{a}{a+b}$를 따른다는 것이며, 따라서 posterior predictive distribution의 mean이 posterior mean parameter를 삽입하는 것과 동등하다는 것을 알 수 있다.

$$ p(\tilde x|\mathcal D)=\text{Ber}(\tilde x|\mathbb E[\theta|\mathcal D]) $$

여기서 베르누이 분포에 대한 수식은 다음과 같다.

$$ \text{Ber}(x|\theta)\triangleq\theta^{\mathbb{I}(x=1)}(1-\theta)^{\mathbb{I}(x=0)},\theta=\frac{a}{a+b} $$

Overfitting and Black Swan Paradox

데이터가 불충분한 경우에는 어떻게 될까? posterior mean paramter를 삽입하는 대신 MLE를 직접 plug-in 한다고 가정해보자. 식은 아래와 같이 정의된다.

$$p(\tilde x|\mathcal D)\approx\text{Ber}(\tilde x|\hat\theta_{MLE}=\frac{N_1}{N}) $$

이러한 approximation은 sample size가 작은 경우 결과가 좋지 않다. 예를 들어 $N=3$ 의 시도를 통해 연속적으로 tail을 봤다고 하자. 이때 MLE는 $\hat\theta=0/3=0$으로, 결과적으로 MLE로 추론된 확률에 대해 구하면 뒷 면만 나올 것이라고 할 수 있다. 이러한 문제를 zero count problem 또는 sparse data problem이라고 부르고, 소량의 데이터에서 counts를 추정할 때 자주 발생하는 문제이다.

이를 또한 Black swan paradox라고도 부른다.

이러한 문제를 해결하기 위한 간단한 Bayesian solution을 도출해보자. 이를 위해 MLE를 사용하는 것이 아닌 posterior estimate를 사용하자. posterior를 사용한다는 것은 prior를 구하겠다는 의미이고, 이를 위해 uniform prior를 사용할 것이기 때문에 $a=b=1$이 된다. 이러한 경우 posterior mean $\bar\theta=\frac{a+N_1}{a+b+N}$에 plug-in 하면 Laplace’s rule of succession이 성립한다.

$$ p(\tilde x=1|\mathcal D)=\frac{N_1+1}{N_1+N_0+2} $$

위 식에서 $+1, +2$ 가 없다면 $\frac{N_1}{N_1+N_0}=\frac{N_1}{N}$으로 $\hat\theta_{MLE}$와 같아진다. 즉 empirical counts에 1을 더한 것이라고 볼 수 있다. $+1, +2$를 통해 smooth를 해줄 수 있다. 이를 Add-one smoothing이라고 부른다.

MAP parameter를 plug-in하면 $\hat\theta_{MAP}=\frac{N_1+a-1}{N+a+b-2}$이므로, smoothing effect가 없다. 이때 mode는 $a=b=1$ 일 경우 $\hat\theta_\text{MLE}$가 된다. 즉, add-one-smoothing을 uniform prior를 가정하여 MAP에 적용하면, MLE가 되기 때문에 smoothing effect를 기대할 수 없으며, black swan paradox가 발생할 수 있다.