10. Generalization and Regularization

Training vs Test Errors

Regression problem에서는 일반적으로 loss function을 MSE로 잡는다.

$$J(\theta) = \frac{1}{N}\sum_{i = 1}^N(y^{(i)}-h_\theta(x^{(i)}))^2$$

하지만 test error는 위 방식과는 다름

$$L(\theta) = E_{(x, y) \sim \mathcal D}[(y-h_\theta(x))^2]$$

where a test sample $(x, y)$ is sampled from the so called test distribution $D$.

Overfitting and Underfitting

Training error와 test error와의 차이를 Generalization gap 라고 부른다.

Overfitting

Training example을 잘 예측하지만, test example을 잘 예측하지 못하는 것

→ 즉, Generalization이 잘 안된 것

Underfitting

Training error가 상대적으로 크기 때문에 test error도 큰 상황

→ 즉, 학습이 제대로 진행되지 않은 것으로 이해할 수 있다.

Bias and Variance

일반적으로 training example은 ground truth으로부터 noise를 살짝 가지고 있다고 가정한다.

💡

해당 error는 Normal distribution을 따른다고 가정한다.

궁극적인 목표는 $h^*$를 예측하는 것인데, 문제가 되는 지점은 test example의 경우에는 noise가 얼마나 되는지에 대해서 예측하기가 힘들다는 것이다.

Bias is the error that occurs due to the model not being able to capture the underlying relationship between the features and the target variable. Variance is the error that occurs due to the model being too sensitive to small changes in the training data.

• Bias: A model that predicts the same value for all data points is said to have high bias. This can happen if the model is too simple and cannot capture the underlying relationship between the features and the target variable.

• Variance: A model that performs well on the training data but poorly on new data is said to have high variance. This can happen if the model is too complex and is overfitting the training data.

What is “Bias”?

오른쪽에서 볼 수 있는 것처럼 데이터의 크기가 늘어나도 잘 학습되지 않는다.

→ linear model임을 가정함으로써 발생하는 문제이다.

즉 underfitting 문제는 데이터의 크기를 늘리거나 noise를 줄이는 것으로 해결할 수 없다.

💡

Informally, the bias of a model can be defined by the test error even if we were to fit it to a very large training dataset. 잘못된 가정을 했을 때 발생하는 오차이다. 높은 편향값은 알고리즘이 데이터의 특징과 결과물과의 적절한 관계를 놓치게 만드는 과소적합(underfitting) 문제를 발생 시킨다. 즉 엄청나게 데이터를 많이 주어도 나타나게 되는 test error이다.

💡

다른 측면으로 bias 크다는 것은 model에 대한 강한 가정을 하고 있다는 측면으로 해석할 수도 있다.

What is “Variance”?

이 경우에는 데이터의 크기가 클수록 해결됨

만약 데이터의 양이 적은 경우 overfitting될 가능성이 높음

💡

Informally, the variance of the model can be characterized by the amount of variations across models learnt on multiple different training dataset

💡

The spurious patterns are specific to the randomness of the noise. 만약 high variance를 가지는 model은 큰 noise까지 모델링에 포함시키는 과적합(overfitting) 문제를 발생시킨다.

앞서 언급한 것처럼 높은 variance 문제는 많은 양의 data를 주게 되면 거의 해결할 수 있게 된다.

Bias-Variance Trade off

만약 모델이 너무 simple하고 너무 적은 parameter를 가진다면, large bias 를 가지고 small variance 를 가질 가능성이 높다. 즉 underfitting 문제를 겪게 될 가능성이 있다.

반대로 모델이 너무 복잡하고 너무 많은 parameter를 가진다면, large variance 를 가지고 small bias 를 가질 가능성이 높다. 즉 overfitting 문제를 겪게될 가능성이 높다.

만약 모델이 너무 simple하다면 large bias (but small variance)

→ 이 경우에는 일반적으로 underfitting 문제를 겪음

만약 모델이 너무 복잡하다면 large variance (but small bias)

💡

중요한 점은 x축이 model complexity라는 것이다.

Parametric density estimation perspective

$\hat \theta$ : estimator of $\theta$

$$\mathbb E [(\hat \theta-\theta)^2] = \mathbb E[\hat \theta^2 - 2\hat\theta\theta + \theta^2] \\ = \mathbb E[\hat \theta^2] - 2\theta\mathbb E[\hat \theta]+ \theta^2 \\ = \mathbb E^2[\hat\theta] - 2\theta\mathbb E[\hat \theta] + \theta^2 + \mathbb E[\theta^2] - \mathbb E^2[\hat\theta] \\ = (\mathbb E[\hat \theta] - \theta)^2 + \mathbb E[\hat\theta^2] - \mathbb E^2[\hat\theta]$$

이때 $(\mathbb E[\hat \theta] - \theta)^2$ 는 $\text{bias}^2$이고, $\mathbb E[\hat\theta^2] - \mathbb E^2[\hat\theta]$ 는 $\text{variance}$이다.

💡

MSE of $\hat \theta$는 Bias-Variance Trade-off와 관련되어 있다.

Regression perspective

The MSE of the model $h_S$ which is trained on $D = \{(x^{(i)}, y^{(i)})\}$ is defined by

$$\text{MSE}(x) = \mathbb E_{D, \xi}[(y - h_S(x))^2]$$

💡

$\xi$ 는 일종의 관측 상에서 발생하는 error를 의미한다고 생각해주면 된다. 또한 $h^*$는 true distribution이다.

$$\mathbb E[(y - h_S(x))^2] = \mathbb E[(h^*(x) + \xi - h_S(x))^2] \\ = \mathbb E[\xi^2] + \mathbb E[2\xi(h^*(x) - h_S(x))] + \mathbb E[(h^*(x) - h_S(x))^2] \text{ (by linearity)} \\ = \mathbb E[\xi^2] + 2\mathbb E[\xi] \mathbb E[(h^*(x) - h_S(x))] + \mathbb E[(h^*(x) - h_S(x))^2] \text{ (by independence)} \\ =\mathbb E[\xi^2] + \mathbb E[(h^*(x) - h_S(x))^2] \text{ (by }\mathbb E[\xi] = 0) \\ = \mathbb E[\xi^2] + (h^*(x)-\mathbb E[h_S(x)])^2 + \mathbb E[(h_S(x) - \mathbb E[h_S(x)])^2]$$

이때 $(h^*(x)-\mathbb E[h_S(x)])^2$는 $\text{bias}^2$이고, $\mathbb E[(h_S(x) - \mathbb E[h_S(x)])^2]$는 $\text{variance}$이다.

💡

$\mathbb E[\xi^2]$ : unavoidable

이때 bias는 data의 부족 때문이 아니라, family of model이 적절하게 $h^*$를 근사하지 못했기 떄문이다. 마찬가지로 variance는 해당 함수들의 분포가 얼마나 $h^*$로부터 멀어져있는지를 보는 것이다.

💡

일종의 보고 있는 공간이 함수공간이라고 생각해주면 쉽게 이해할 수 있다.

Generalization

Definition

Generalization refers to model’s capability to adapt properly to new/unseen data

💡

앞서 살펴본 것처럼 overfitting이나 underfitting이 발생한 경우에는 generalization이 잘 진행되지 않았다고 생각할 수 있다. 추가적으로 overfitting 문제의 경우 regularization을 취해주게 되면 학습이 안정적으로 진행되는 효과를 가져올 수 있다.

Evaluation of Generalization power

Hold-out method

전제 : 주어진 데이터가 2개의 독립적인 set으로 partition된다.

1. Training set

2. Test set

💡

즉 training data와 test data가 동일한 distribution을 가진다.

만약 Test set이 편향되어있는 경우, 문제가 발생할 수 있다.

→ 그래서 Random sample strategy를 사용

→ 위와 같은 작업을 k번 수행하고, 평균을 처리해서 위 문제를 alleviate시킴.

K-fold cross validation

1. 전체 데이터를 k개의 크기가 거의 유사한 mutually-exclusive subset으로 나눈다.

2. 각각 한번씩 해당 subset을 testset으로 사용해서 test error를 확인한다.

3. 1~2 과정을 총 k번 반복한다.

💡

이러한 방법은 data set의 크기가 작을 때 유용하다.

Nested cross validation

Hyper-parameter를 조정해야할 경우에 사용하는 방법

→ 어떤 hyper-parameter를 설정할 것인지에 대한 기준을 제공하는 역할을 수행

→ 그래서 등장한 set이 validation

1. 총 Dataset을 k개의 subset으로 나눈다.

2. 각 subset을 한번 씩 test set으로 설정한다.

3. 나머지 k - 1개를 번갈아가면서 validation set으로 취급한다.

4. 총 k번 1~3과정을 반복한다.

💡

일종의 k-fold cross validation에 validation을 넣은 느낌이다. 왜냐하면 K-fold cross validation의 경우에는 model 선택 위한 validation set이 존재하지 않기때문이다.

Train/Validation/Test Splitting

만약 데이터가 큰 경우에는 Nested cross validation이 너무 많은 시간이 걸린다는 단점이 존재하는데, 이 때문에 그냥 단순하게 하자는 것.

Regularization

앞서 살펴본 것처럼 bias-variance trade off가 존재하기에 model complexity를 적절하게 설정하는 것이 중요하다.

💡

Model의 complexity는 단순히 parameter의 개수로 추정할 수 있다.

즉 parameter가 너무 커지게 되면 overfitting문제가 발생하기 때문에 이에 대한 penalty를 regularization 으로 주겠다는 것

💡

Regularization controls the model complexity and prevents overfitting

$$J_\lambda(\theta) = J(\theta) + \lambda R(\theta) \\ J_\lambda(\theta) : \text{Regularized loss} \\ R(\theta) : \text{Regularizer}$$

$l_o, l_1, l_2$ Regularization

$l_2$ regularization이 대표적으로 사용되는 것이다.

$$R(\theta) = \frac{1}{2}\|\theta\|_2^2$$

Regularized loss에 대해서 Gradient descent를 하는 것은 standard gradient descent에 weight decay 과정을 하는 것으로 이해할 수 있다. ($(1-\eta\lambda)\theta$로 작아지게 된다.)

$$\theta \leftarrow \theta - \eta\nabla_\lambda(\theta) \\ = \theta - \eta(\lambda \theta + \nabla J(\theta)) \\ = (1-\eta\lambda)\theta - \eta\nabla J(\theta)$$

$l_0$는 미분이 불가능하다는 측면때문에 gradient descent를 할 때는 잘 사용하지 않는다.

💡

모델이 sparse(희소)하다는 것은 모델의 파라미터 중에서 많은 부분이 0으로 되어 있는 상태를 의미합니다. 즉, 모델의 파라미터 값 중에서 0에 가까운 작은 값들이 많아지는 것을 말합니다. 즉 모델이 지나치게 complex해지는 것을 억제하는 역할을 수행하게 된다.