uncategorized

Learning_Theory

Learning Theory

Andrew ng lecture note 를 공부하며 정리한 자료입니다

1. Bias / Variance tradeoff

선형 회귀에서 데이터에 해당 하는 모델을 simple($y=\theta_0 + \theta_1 x$)하게 혹은 complex($y=\theta_0 + \theta_1 x + \cdots + \theta_4 x^4$)하게 만들수 있다.

4차 함수가 아무리 $y$(price) 예측을 잘한다고 할지라도, 새로운 데이터가 들어왔을때에는 정확하게 예측하기는 어렵다. 즉 학습 데이터로 학습한 complex 모델은 다른 데이터(집)에 대해서는 일반화 되지 않은것이라고 할수 있다. generalization error란 반드시 트레이닝 데이터로 나온 error를 측정하는게 아닌 새로운 테스트 데이터가 들어왔을때의 error를 나타낸다.

가장 왼쪽에 있는 모델과 오른쪽에 있는 모델 모두 generalization error가 높다. 하지만 두 모델의 error가 높은 이유는 다르다.
먼저 왼쪽 모델을 보면 만약 $(x, y)$ 데이터가 서로 linear 관계가 아니라면 아무리 많은 데이터로 학습을 시켜도 정확하게 예측하기란 쉽지가 않다. 이런 경우 모델의 편향(bias)이 크다고 한다 또는 underfit 되었다고 한다.

오른쪽 모델인 경우 보통 학습 데이터가 적을때 $(x,y)$ 데이터 상관관계를 폭넓게 반영하지 못하는 경우이다. 이러한 경우 모델의 분산(variance)이 크다고 하고 overfit 되었다고 한다.

bias, variance 서로 상충관계(trade off) 이다.
simple 한 모델이라면 bias는 크고 variance는 작다. 반면에 complex 모델이라면 bias는 작지만 variance는 매욱 크게 된다.

2. Preliminaries

여기에서는 다음 3가지의 질문을 정의할것이다.
첫째, bias variance tradeoff를 formal하게 할수 있을까?
둘째, generalization error를 training error로 관계지을수 있을까?
셋째, 학습 알고리즘이 잘 학습되고 있는지 증명할수 있는 조건들이 있는가?

위 질문에 답하기 위해 두개의 보조 정리를 애기해보자

  1. Union bound

$k$개의 모든 사건이 서로 독립적이지 않는 사건 $A_1, A_2, \ldots, A_k$이 있다고 한다면 다음 식이 성립된다.

증명은 하지 않겠지만 직관적으로 이해해 보면 사건 간의 교집합이 존재할수 있기 때문에 각각의 사건의 확률의 합은 모든 사건 합의 확률보다는 크다는 것을 알수 있다.

  1. Hoeffding inequality

서로 동일한 베르누이 분포에서 나온 독립적인 확률 변수(iid) $Z_1, Z_2, \ldots, Z_m$가 있다고 하자.

$P(Z_i=1)=\phi$, $P(Z_i=0)=1-\phi$ 라고 표기하고, 확률변수의 평균은 $\widehat \phi = \frac{1}{m}\sum_{i=1}^m Z_i$ 라고 정의 하고, $\gamma > 0$ 보다 크다고 고정한다.

learning theory에서는 $Chernoff bound$라고 하는 식은 다음과 같다.

식이 복잡해 볼수 있지만, 크게 어렵지 않다. 식을 직관적으로 이해해 보면, 만약 데이터의 갯수가 많으면 즉 $m$이 커지면 커질수록 확률변수의 평균($\widehat \phi$)과 측정값($\phi$)의 차이가 클 확률이 줄어든다는 것이다.

이해를 좀더 쉽게 하기 위해서 label $y \in \{0,1\}$ binary classification을 생각해 보자. 학습데이터 $S$는 $D$ 라는 특정 확률분포에서 $m$개 샘플되었다고 해보자. $S = \{ (x^{(i)}, y^{(i)});i = 1,\ldots,m \}$
다음과 같이 training error는 hypothesis $h$에 대해서 다음과 같이 쓸수 있다.

training error가 아닌 우리가 알고 싶은 generalization error는 다음과 같이 나타낼수 있다.

분포 $D$에서 랜덤하게 나온 sample $(x^{(i)}, y^{(i)})$ 을 $h$가 잘못 분류한것을 나타낸다. 다시한번 언급하자면 training data는 분포 $D$에서 샘플링 된다는 것을 가정하는 것이다.

그럼 hypothesis $h_\theta (x) =1\{\theta^T x \geq 0\}$의 파라미터 $\theta$를 찾으려는 식을 알아보자.

식을 이해해보면, 즉 학습데이터에 대한 에러를 가장 줄이는 $\widehat \theta$를 찾는 것이다

조금 더 깊게 들어가 우리는 hypothesis class $\mathcal{H}$를 정의할것이다. linear classification에서의 $\mathcal{H}$는 다음과 같이 쓸수 있다.

$\mathcal{X}$ input domain 들마다의 classifier 집합이다.

hypothesis $h$는 모든 classifier hypothesis 집합 $\mathcal{H}$ 속에서 가장 학습 데이터에 대한 오류가 작은 것이 $\widehat h$가 될것이다.

3. The case of finite $\mathcal{H}$

유한개의 hypothesis 들의 집합 $\mathcal{H}=\{h_1, h_2, \ldots, h_k\}$ 로 정의할수 있고, $\mathcal{X}$ input data에 대해 $\{0,1\}$로 mapping 해주는 함수가 $k$개의 있는 것과 같다.

여기서 우리는 두가지를 확인해야 한다.
첫번째, 모든 h에 대해서 $\widehat \epsilon (h)$는 $\epsilon(h)$가 될수 있다.
두번째, 여기서 나온 error는 $\widehat h$의 generalization error의 상한선(upper bound)이 된다.

$h_i \in \mathcal{H}$를 하나 선택한다. 그리고 베르누이 확률변수($Z$)를 하나 정의한다. $Z$ 는 분포 $\mathcal{D}$에서 샘플된 데이터$(x,y)\sim \mathcal{D}$를 $h_i$가 잘못 분류한 경우를 말한다. $Z=1\{h_i(x) \neq y\}$ 학습 데이터는 동일한 분포 $\mathcal{D}$에서 샘플 되었기 때문에 $Z$와 $Z_i$도 같은 분포에서 나온 확률 변수 임을 알수 있다.

hypothesis의 학습데이터 오류는 확률변수 $Z$의 평균임을 알수 있다.

$\widehat \epsilon (h_i)$는 $m$개의 확률변수 $Z_j \sim Bern\left(\phi = \epsilon (h_i)\right)$의 평균이다. 여기에서
Hoeffding inequality 공식을 적용해보자.

식을 이해해 보면 hypothesis $h_i$의 학습데이터에 대한 오류가 generalization error 와 비슷해지는 확률은 데이터의 갯수($m$)이 많아지면 많아질수록 높아지게 된다. 우리는 더 나아가 $h_i$하나의 hypothesis 뿐만 아니라 모든 hypothesis($h \in \mathcal{H}$)에도 적용 되는지 알아보자. 문제를 풀기 위해 $\mid \epsilon (h_i) - \widehat \epsilon (h_i) \mid > \gamma$를 하나의 사건 $A_i$로 표기하도록 하자.

위에서 보았던 union bound 정리를 이용해 다음과 같이 정리할수 있다.

양변을 1에서 빼주면 다음과 같이 써줄수 있다.

위 식을 직관적으로 이해하면, $1-2k \exp \left( -2 \gamma^2 m\right)$ 이상의 확률로 $\widehat \epsilon (h_i)$는 $\epsilon (h_i)$의 $\gamma$ 범위 안에 있다. 이것을 uniform convergence 라고 부른다

Notation

  • $\lnot$ : not 이라는 의미입니다.

여기에서 관심있는 값은 $m$, $\gamma$, 에러의 확률이다.

$\delta$ = $2k \exp \left( -2 \gamma^2 m\right) > 0$이라고 fix하고, $\gamma$도 특정한 값으로 fix 하면 데이터의 갯수 $m$는 얼마나 필요한지 확인힐수 있다.

만약 데이터의 갯수($m$)가 위와 같이 충분히 있으면, 모든 $h \in \mathcal{H}$ 에 대해서 $\mid \epsilon (h_i) - \widehat \epsilon (h_i) \mid \leq \gamma$ 일 확률은 최소 $1-\delta$가 된다. 마찬가지로, 모든 $h \in \mathcal{H}$ 에 대해서 $\mid \epsilon (h_i) - \widehat \epsilon (h_i) \mid > \gamma$ 일 확률은 최대 $\delta$가 된다. 이러한 확률 bound는 우리가 얼마만큼의 데이터가 필요로 하는지 알수 있게 된다. 또한 $m$은 $\log k$에 영향을 많이 받는다. 여기서 $k$는 hypothesis의 갯수이다.

이번에는 $m$과 $\theta$를 고정하고 $\gamma$를 유도하면 다음과 같다.

모든 $h \in \mathcal{H}$ 에 대해서

generalization error를 최소화하는 hypothesis $h$는 다음과 같이 정의할수 있다 $h^* = argmin_{h \in \mathcal{H}} \epsilon (h)$ 즉 우리가 찾는 best model이 되는 것이다.

위 식을 조금 더 이해하기 쉽게 notation을 다시한번 정리해보자.

Notation

  • $\widehat h$ : training error를 가장 최소화 하는 hypothesis, $\widehat h = argmin_{h \in \mathcal{H}} \widehat \epsilon (h)$

  • $\widehat \epsilon(\widehat h)$ : hypothesis $\widehat h$의 training error

  • $\epsilon(\widehat h)$ : hypothesis $\widehat h$의 generalization error

위 식에 대해서 순서대로 설명을 해보자면, 1번식 같은 경우는 $\widehat h$의 generalization error는 training error 보다 $\gamma$ 만큼 크다는 것이다. 2번식은 $\widehat h$의 training error보다 $h^{star}$의 training error 가 더 크다는 것이다. $\widehat h, h^{star}$의 정의를 잘 생각해보면 이해할수 있을것이다. 3번식은 $h^{star}$의 generalization error 보다 training error가 $\gamma$ 만큼 더 크다는 뜻이다.

이제 다음과 같은 이론 공식을 유도할수 있다.
$\mid \mathcal{H} \mid$ = $k$, $m, \delta$를 고정한다.

최소 $1 - \delta$의 확률로

$\gamma = \sqrt{\frac{1}{2m} \log \frac{2k}{\delta}}$

$min_{h \in \mathcal{H}} \epsilon (h)=\epsilon ( h^{*})$

위 식에서 trade off 관계를 확인 할수 있다. 만약 hypothesis의 차수를 늘려주게 되면 generalization error ($\epsilon ( h^{*})$) 는 줄어 들것이다. 하지만 hypothesis의 갯수(k)는 늘어가게 되어서 결국 이 것은 bias는 줄어들게 되지만 variance는 커지게 된다. 반대로 hypothesis의 차수가 줄어들면 generalization error는 커지게 되지만 그만큰 hypothesis의 갯수는 줄어들게 되어서 bias /variance 의 tradeoff 관계가 나타나게 된다.

Share