Stanford CS229: Machine Learning | Lecture 8 강의 정리

Stanford에서 2018년 가을학기에 열린 Andrew Ng 교수의 CS229 머신러닝 강의의 대부분의 내용을 번역 정리한 글입니다.

---

Course : Stanford CS229: Machine Learning Full Course taught by Andrew Ng | Autumn 2018
Course 소개 : CS229는 기계 학습과 통계적 패턴 인식에 대한 포괄적인 소개를 제공합니다. 지도 학습(생성적/판별적 학습, 모수/비모수 학습, 신경망, 서포트 벡터 머신); 비지도 학습(클러스터링, 차원 축소, 커널 메소드); 학습 이론(편향/분산 트레이드오프, 실용적인 조언); 강화 학습 및 적응 제어에 대한 강의를 다룹니다. 또한 기계 학습의 최근 응용에 대해 논의되며, 로봇 제어, 데이터 마이닝, 자율 항법, 생명 정보학, 음성 인식, 텍스트 및 웹 데이터 처리 등이 포함됩니다.
강의 제목 : Lecture 8 - Data Splits, Models & Cross-Validation | Stanford CS229: Machine Learning (Autumn 2018)
강의 영상: https://youtu.be/rjbkWSTjHzM?si=VfAnr0G8RF8VnSGv
강의 자료 (복원): https://github.com/maxim5/cs229-2018-autumn
강의 syllabus : http://cs229.stanford.edu/syllabus-autumn2018.html
강의를 듣기 전에 알고 있어야 하는 내용
선형대수학 : https://cs229.stanford.edu/notes2022fall/cs229-linear_algebra_review.pdf
확률이론 : https://cs229.stanford.edu/notes2022fall/cs229-probability_review.pdf

---

Outline

• Bias/Variance
• Regularization
• Train/dev/test splits
• Model selection & cross validatoin

Bias/Variance

cs229

가로축이 크기이고 세로축이 가격인 집 가격 예측 문제에 대한 dataset이 있다고 하자. 이것을 직선으로 fitting해도 나쁘지 않아 보인다.

cs229

dataset이 위로 올라가다가 살짝 휘어져 내려오는 것처럼 보여 quadratic model로 fitting 하면 조금 더 좋을 것이다.

cs229

또는 더 높은 차수의 다항식으로 fitting 할 수 있다. 6개의 example들이 있기 때문에 5차 다항식으로 fitting을 한다면 모든 example들을 완벽히 통과할 것이다. 하지만 이것은 좋은 모델로 보이지는 않는다.

cs229

위 세가지 모델중에 가운데에 있는 2차 함수 모델이 가장 좋기 때문에 “just right"이라고 한다.

왼쪽에 있는 예시는 data에 underfit 되어 있다. data에 분명히 보이는 trend를 포착하지 못하고 있다. 우리는 이 algorithm이 high bias를 가지고 다고 한다. 이것은 이 알고리즘이 데이터가 linear 할 것이라는 매우 강한 선입관을 가지고 있다는 것을 의미하고 이것은 사실이 아니다.

오른쪽의 예시는 데이터에 overfit 되어 있고 high variance를 가지고 있다. high variance는 만약 저 6개의 example들을 다른 사람이 수집했다면 다른 example 집합일 것이고 알고리즘은 완전히 다른 함수로 fitting 할것이기 때문에 predictions이 very high variance를 가질 것이라는 직관에서 나온다. 친구가 random noise 때문에 조금이라도 다른 example들을 고른다면 알고리즘은 5차 다항식을 fitting 하고 완전히 다른 결과가 나온다. 따라서 우리는 이 알고리즘이 매우 높은 variance를 가지고 있다고 말하고 이 알고리즘이 만드는 predictions에는 많은 variability가 있다.

모델을 학습시킬 때 그 모델은 절대 처음부터 작동하지 않는다. learning algorithm을 발전시킬 때 이 알고리즘의 문제가 high bias인지 high variacne인지, underfitting 인지 overfitting인지 이해하려고 해야하고 이 insight를 이용하여 어떻게 알고리즘을 발전시킬지 결정해야한다.

bias와 variance문제는 classification에서도 유효하다. binary classification problem에 대해서 이야기해보자.

logistic regression model을 fitting 한다면 직선이 data에 fitting 된다. 이건 좋은 결과가 아니다. $\large x_{1}, x_{2}$가 아닌 $\large x_{1}^{2}, x_{1}x_{2}$와 같은몇 개의 non-linear feature들을 사용하거나 kernel을 사용하여 SVM을 사용할 수 있다. 만약 너무 많은 feature들을 사용한다면 학습 알고리즘은 아래와 같이 매우 복잡한 decision boundary를 fitting 할 것이다.

cs229

이것은 training set에 완벽한 퍼포먼스를 보여주지만 overfitting 되었다.

cs229

따라서 위의 그림처럼 이 사이에서 data에 더 잘 fitting 되는 적당한 곳을 골라야한다.

많은 feature들을 가진 모델을 학습시키는 GPU computing ability의 에러에서, 그 중 하나는 SVM을 충분한 고차원의 feature space에서 사용하거나 logistic regression에 충분한 feature들을 더하는 것처럼 충분히 큰 모델을 만드는 것은 자주 data에 overfitting 된다. overfitting을 방지하는 가장 효율적인 방법 중 하나는 regularization이다.

Regularization

Adding Penalty on the Norm of Parameters

Regularization은 설명하는데 오래걸리지 않고 기가 막힐 정도로 단순하지만 Andrew Ng 교수가 가장 자주 사용하는 테크닉중 하나이다.

$$
\large
\min_{\theta}\frac{1}{2}\sum\limits^{m}_{i=1}\rVert y^{(i)}-\theta^T x^{(i)}\lVert^{2}
$$

위 식은 linear regression의 optimization objective이다. linear regression에 egularization을 추가하고 싶다면 위 식에 $\large \theta$의 norm과 관련된 추가적인 항만 더해주면 된다.

$$
\large
\min_{\theta}\frac{1}{2}\sum\limits^{m}_{i=1}\rVert y^{(i)}-\theta^T x^{(i)}\lVert^{2}+\frac{\lambda}{2}\rVert\theta\lVert^{2}
$$

이것을 linear regression의 cost function으로 사용하고 $\theta$를 더 작게 만들도록하는 incentive term을 추가한다. $\large \frac{\lambda}{2}\rVert\theta\lVert^{2}$을 regularization term이라고 하고 파라미터 $\theta$가 너무 커지는 것을 방지해 학습 알고리즘이 data에 overfitting 되는 것을 더 어렵게 한다. $\lambda$가 0이라면 아무 regularization도 사용하지 않는 것이기 때문에 overfitting 될 것이고, $\lambda$가 너무 크다면 모든 파라미터들을 0과 가까워지도록 강요하는 것이기 때문에 매우 간단한 함수가 되어 underfitting이 될 것이다.

더욱 일반적으로 logistic regression의 optimization object가 아래와 같을 때

$$
\large
\arg\max_{\theta}\sum\limits^{n}_{i=1}\log p(y^{(i)}|x^{(i)};\theta)
$$

regularization을 추가한다면 아래와 같은 식이 된다. 처음에 다룬 linear regression은 최소화하는 문제이기 때문에 regularization term을 더해줬지만 이번 경우에선 최대화하는 문제이기 때문에 regularization term을 빼준다.

$$
\large
\arg\max_{\theta}\sum\limits^{n}_{i=1}\log p(y^{(i)}|x^{(i)};\theta)-\frac{\lambda}{2}\rVert\theta\lVert^{2}
$$

이것은 generalized linear model family에서의 argmax가 될 수 있다. regularization term을 빼주면서 logistic regression과 같은 classification 알고리즘을 regulaize 할 수 있게 해준다.

SVM이 infinite dimensional feature space를 사용하면서 너무 나쁘게 overfitting 되지 않는 이유는 SVM의 optimization objective가 $\large \min\rVert w\lVert^{2}$가 $\large \min \frac{\lambda}{2}\rVert\theta\lVert^{2}$과 같은 역할을 해 $\large w$가 너무 커지는 것을 방지하기 때문이다.

Text Calssification

Naive Bayes의 text classification 알고리즘에 대해 이야기했었다. 만약 100개의 example들이 있고 10000차원의 feature를 가지고 있을 때 이 데이터에 logistic regression을 fitting 한다면 아마 overfitting 될 것이다. Logistic regression을 regularization과 함께 사용한다면 이것은 text classification에 매우 좋은 알고리즘이며 classification 정확도에서 Naive Bayes보다 대개 좋은 성능을 보인다. Logistic regression의 'rule of thumb'중 하나는 regularization을 하지 않으려면 example들의 수가 최소 fueatre의 수 만큼 있어야 좋은 성능을 보인다는 것이다. 그 이유는parameter를 고를 때 좋은 선택을 하기 위해선 충분한 정보가 있어야 하기 때문이다. regularization을 사용한다면 100개 뿐인 적은 example들로도 10000개의 parameter를 fitting 할 수 있다.

regularizatoin term으로 $\sum\limits_{j} \lambda_{j}\theta_{j}^{2}$가 아닌 $\large\lambda\rVert\theta\lVert^{2}$를 사용하는 이유는 parameter의 수가 많아질 때 $\lambda$의 수도 많아지기 때문에 이것을 각각 선택하는 것은 어렵기 때문이다.

MLE Vs MAP

지금까지 parameters의 norm의 패널티를 더해 기계적으로 regularization을 구현했다. 다른 방법으로도 regularization을 생각할 수 있다. linear regression에 대해 이야기 할 때 squared error를 최소화 하는 것과 Exponential familly로 Gaussian distribution을 사용한 generlized lnear model의 Maximum Likelihood Estimation(MLE)에 대해 이야기 했었다. 여기서 방금 본 정규화 알고리즘에 대해 취할 수 있는 비슷한 관점이 있다. training set이 $\large S={x^{(i)},y^{(i)}}^{m}_{i=1}$라고 할 때 주어진 training set에서 가장 likeli한 $\theta$값을 찾아야 한다. bayes rule에 의해 $p(\theta|S)$는 아래와 같다.

$$
\large
\begin{align}
p(\theta|S)&=\frac{p(S|\theta)p(\theta)}{p(S)}\
\arg \max_{\theta}p(\theta|S)&=\arg\max_{\theta}p(S|\theta)p(\theta)
\end{align}
$$

만약 Logistic regression을 사용한다면 아래식처럼 쓸 수 있다.

$$
\large
\arg\max_{\theta}\left(\prod^{m}_{i=1}p(y^{(i)}|x^{(i)},\theta)\right)p(\theta)
$$

여기서 $\theta$가 평균이 0이고 분산이 $\tau^{2}I$를 따르는 Gaussian이라고 가정한다.

$$
\large
p(\theta) \sim \mathcal{N}(0,\tau^{2}I)
$$

즉 $p(\theta)$는 아래와 같다.

$$
\large
p(\theta)=\frac{1}{\sqrt{2\pi}(\tau^{2}I)^{\frac{1}{2}}}\exp\left(-\frac{1}{2}\theta^{T}(\tau^{2}I)^{-1}\theta\right)
$$

$p(\theta)$를 위 식에 대입하여 최댓값을 계산하면 우리가 방금 발견한 regularization 테크닉과 일치하게 된다.

Frequentist Vs Bayesian

우리가 지금까지 해왔던 모든 것에서 frequentist(빈도주의)적으로 해석했었다. 통계학의 주요 학파는 Frequentist와 Bayesian으로 나뉜다. Frequentist 학파가 찾고 싶은 $\theta$는 어떤 데이터가 있을 때 이 데이터를 가능한 likeli하도록 만드는 MLE(maximum likelihood estimator) $\large \theta=\arg\max_{\theta}p(S|\theta)$이다. 그리고 이것을 세상에 알려지지 않은 $\theta$의 true 값이라고 생각한다. 따라서 어떤 $\theta$의 ture 값이 데이터를 만들고 이 ture parameter를 추정하는 것이 목표이다.

Bayesian 학파에서는 알려지지 않은 $\theta$가 있다고 말하지만 data를 보기 전에 target이 어떻게 만들어졌는지에 대한 사전 믿음이 있고 이것은 확률분포로 포착된다. 이것은 $\large p(\theta)$라고 쓰고 Gaussian prior라고 부른다. Gaussian prior는 상당히 논리적이다. data를 보기 전에 $\theta$의 평균을 0이라고 하는 것은 $\theta$가 양수인지 음수인지 모르기 때문이다. 이것이 맞는지에 대해 논쟁을 할 순 있지만 이것이 완전히 터무니없는 것은 아니다. Bayesian 관점에서 우리의 목표는 data를 보고 나서 가장 likeli한 $\theta$의 값을 찾는 것이다.

$$
\large
\max_{\theta}p(\theta|S)
$$이것을 MAP(maximum a posteriori) estimation이라고 부르고 $\large \theta=\arg \max_{\theta}p(\theta|S)$는 MAP estimator이다. MAP estimator는 data를 보고 $\theta$의 Bayesian posterior distribution을 계싼해 가장 likeli 한 값을 고르는 것이다. Gaussian prior 대신 Laplace prior 같은 다른 prior를 대입하여 다른 MAP를 유도할 수 있다.

이 둘을 non-regularization vs regularization으로 볼 수 있다. MLE는 regularization의 기원이고 MAP는 reaularization을 추가한 것이다. Frequentist도 regularization을 사용할 수 있지만 Bayesian prior를 정의하려고 하지는 않는다. Frequentist들도 regularization을 추리하지만 이것은 Bayesian prior에서 유도된 것이 아닌 그들이 발명한 알고리즘의 일부라고 말한다.

Model Complexity

다항식의 차수와 같은 model complexity에 따른 error 차트를 그려보면 아래와 같다.

regularization을 하지 않았을 때 2차, 3차 4차와 같이 model complexity를 증가시키면 training error가 감소한다. 하지만 알고리즘의 generalized error는 감소하다가 증가하기 시작한다. test set을 분리하여 알고리즘이 보지 못한 이 데이터로 classifier를 평가하면 알고리즘이 다른 새로운 data set에 얼마나 일반화 되었는지 측정할 수 있다. 선형 함수로 fitting을 하면 underfitting이 되고 5차 다항식으로 fitting하면 overfitting되고 이 둘 사이가 “just right”이 된다.

cs229

이것은 regularization에도 적용된다.feature가 10,000개 이고 training example들이 매우 적은 상황에서 linear regrssion을 적용시키면 $\lambda$가 매우 크다면 ($\lambda=10^{100}$) underfitting이 된다. $\lambda$가 0이여서 regularization을 허용하지 않는다면 overffiting이 될 것이고 underfitting과 overfitting이 균형을 이루는 너무 크지도 작지도 않는 중간의 값이 있을 것이다. 이 중간 지점을 찾는 몇개의 기계적 절차에 대해 이야기해보자.

Model Selection

Simple Cross Validation

주어진 data set을 train, dev, test의 부분집합들로 나눈다. 10,000개의 example들이 있고 이것들로 model selection을 수행한다고 하자. 예를 들어 다항식의 차수를 고르거나 $\large \lambda$나 $\large \tau$를 고르거나 SVM에서 얼마나 완벽히 training example들을 분류할 것 인지를 나타내는 $\large C$를 고르는 것이다. 여기서 어떤 선택을 하든 bias-variance trade-off를 가지고 있다.
model selection을 위해 아래 작업을 수행한다.

• training data $\large S$를 이것의 부분집합인 $\large S_{train},\ S_{dev},\ S_{test}$로 나눈다. (dev는 development의 약자이다.)
• 다항식의 차수를 옵션으로 한 각 모델을 $\large S_{train}$으로 학습시켜 hypothesis $\large h_{i}$를 얻는다.
• $\large S_{dev}$를 이용하여 error를 측정해 가장 낮은 에러를 갖는 모델을 고른다.
• 여기서 $\large S_{train}$을 이용하여 error를 측정하면 항상 가장 복잡한(가장 overfitting 된) 모델을 고를것이기 때문에 이것을 사용하면 안된다.
• 학습하는 동안 보지 못한 분리된 development set을 이용하여 모델의 error를 계산해서 overfit도 underfit도 아닌 모델을 고르려고 하는 것이다.
• (선택) : $\large S_{test}$를 이용하여 알고리즘의 error를 이용하여 report(paper)를 작성한다.
• 논문을 작성할 때 dev set에서 계산한 error를 결과로 작성하는 것은 유효하지 않다. 모델을 고르는 위 과정에서 알고리즘이 이미 dev set에 최적화 되어 있기 때문이다.
• 논문을 작성할 때 good hygiene을 고려하고 싶다면 모델을 개발하는 동안 test set을 완벽히 분리하여 어느 방법으로든 보지 않고 error를 계산하는 것이다. $\large S_{test}$에 의한 error가 모델을 결정하는데 반영되면 안된다.
• 데이터가 적고 학술 논문을 쓰지 않은 상황에서는 test set을 나누지 않아도 된다. 학술 논문에 test set을 사용하지 않고 dev set만 사용한다면 많은 클레임들을 만들게 될것이기 때문에 절대 해서는 안된다.

과거에는 60:20:20의 비율로 부분집합을 나누기도 했지만 현재에는 거대한 양의 데이터를 처리할 일이 많기 때문에 퍼센트로 dev set과 test set을 나누지 않는다. 예를 들어 천만개의 exmaple들이 있을 때 classifier의 성능을 측정하는데 2백만개의 example들이 정말 필요한가에 대해 생각해야한다. 모델 사이의 1~2%의 성능을 비교하는덴 1000개의 example들로도 충분하다. 따라서 example 수가 많을 때에는 얼마나 자세하게 성능을 비교하고 싶은지에 따라 그 수에 맞게 dev set과 test set으로 나누면 된다. $S_{dev}$를 이용하여 error를 비교하는 과정을 (Simple) Hold-out cross validation이라고 하고 development set은 cross validation set이라고 부른다.

K-fold Cross Validation

우리는 언제는지 작은 datasets을 가질 수 있다. 이번엔 분리된 test set이 있다고 가정하고 test set에 대한 고려를 하지 않을 것이다. 100개의 example들을 가지고 있다고 하자. 만약 이것을 70개의 training set과 30개의 dev set으로 나누려고 한다면 100개의 example들이 아닌 70개의 example들로 알고리즘을 학습시켜야한다. dataset이 작은 경우 이것을 얻기 위해 많은 비용이 필요한 상황일 것인데 model selection을 위해 100개의 example들 중 70개의 example들만 사용한다는 것은 많은 비용을 내고 수집한 많은 data를 낭비하는 것으로 보인다. 또한 30개의 example들로 모델을 평가하기도 너무 적어보인다.

약간의 데이터 낭비 없이 Model selection을 하는 방법에 대해서 이야기 해 볼 것이다. k-fold cross validation이라고 불리는 이 절차는 작은 data set을 가지고 있을 때만 사용해야하고 simple cross validation과 대비된다.

training set $\large S$가 100개의 example들이 있다면 이것을 $\large k$개의 조각으로 나눈다. 보통 $\large k=10$을 사용한다. $\large k=5$로 예시를 들면 $\large S$를 각 각 20개의 example들을 가지고 있는 5개의 서로 다른 부분집합으로 나눈다.

For i=1,...,k
train (fit prameters) on k-1 pieces
test on rmaining 1 pieces
Average

 

k-Fold

k-1개의 조각들로 학습을 한 뒤 나머지 하나로 평가를 진행한다. 이 때 매번 다른 test 조각을 사용하여 k번을 반복한 뒤 이때 계산된 error의 평균을 구한다.

만약 다항식의 차수를 고르고 싶다면 위 절차를 각 차수마다 반복하여 error의 평균이 가장 작은 차수를 선택한다.

For d=1,...,5 (degree of polynomial){
For i=1,...,k
train (fit prameters) on k-1 pieces
test on rmaining 1 pieces
Average
}

(선택) 이 이후 100%의 모든 data를 사용하여 선택된 모델을 다시 학습시킨다.

이 방법의 장점은 30% data를 dev set을 위해 버리는 것이 아닌 각 반복에서 $\large \frac{1}{k}$의 example들만 data만 버려진다는 것이다. 보통 $\large k=10$을 사용하는데 각 반복에 10%의 데이터만 dev set을 위해 버려진다.

simple cross validation 와 비교했을 때 data를 매우 효율적으로 사용한다는 장점이 있지만 k번 모델을 학습 해야하기 때문에 계산이 매우 비싸다는 단점이 있다. 하지만 data의 수가 매우 적은 경우 계산 시간을 고려하지 않아도 되기 때문에 더 좋은 방법이다.

Leave-one-out Validation

data가 더 적은 경우 leave-one-out validation이라고 부르는 k-fold cross validation의 극단적인 버전을 사용한다. $\large k=m$으로 data의 수 만큼 조각을 나눈다. 만약 data가 20개가 있다면 19개로 model을 학습하고 나머지 하나로 평가를 한다. 이 과정을 20개의 data에 대해 반복하여 평균을 낸다. 이 방법의 큰 단점은 data의 개수 $\large m$ 만큼 반복 해야 하기 때문에 계산적으로 매우 비싸다는 것이다. 따라서 $m$이 매우 작은 상황이 아니면 절대 사용해서는 안된다. Andrew ng 교수는 $m$이 100보다 작은 상황이 아니면 쓰지 않는다고 한다.

Feature Selection

가끔 많은 feature들을 가지고 있을 때가 있다. text calssification에서는 10,000개의 단어에 대응하는 10,000개의 feature들을 가지고 있다. 하지만 우리는 이것들 중 많은 feature들이 중요하지 않다는 것을 짐작하고 있을 것이다. feaure가 많을 때 overfitting을 줄이는 한 가지 방법은 feature의 가장 중요한 작은 부분집합을 찾는 것이다. 따라서 feature selection은 model selection의 특별한 경우이다.

Forward Search

$\mathcal{F}$를 feature의 공집합 으로 시작해서 $\mathcal{F}=\emptyset$ 아래 과정을 반복한다.

1. 각 feature $i$를 $\mathcal{F}$에 추가하여 어떤 하나의 feature가 추가되었을 때 dev set performance가 가장 개선되는지 확인한다.
2. 그 feature를 $\mathcal{F}$에 추가한다.
   위 방법으로 Greedy하게 feature들을 추가한다. 공집합에서 시작해서 한 번에 하나의 feature씩 추가하는 방법이다. 반대로 모든 feature 집합에서 하나씩 제거하는 backward search 방법도 있다. forward search는 계산적으로 비싸지만 feature 집합을 줄이는데 도움을 줄 수 있다.