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

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

---

Course : Stanford CS229: Machine Learning Full Course taught by Andrew Ng | Autumn 2018
Course 소개 : CS229는 기계 학습과 통계적 패턴 인식에 대한 포괄적인 소개를 제공합니다. 지도 학습(생성적/판별적 학습, 모수/비모수 학습, 신경망, 서포트 벡터 머신); 비지도 학습(클러스터링, 차원 축소, 커널 메소드); 학습 이론(편향/분산 트레이드오프, 실용적인 조언); 강화 학습 및 적응 제어에 대한 강의를 다룹니다. 또한 기계 학습의 최근 응용에 대해 논의되며, 로봇 제어, 데이터 마이닝, 자율 항법, 생명 정보학, 음성 인식, 텍스트 및 웹 데이터 처리 등이 포함됩니다.
강의 제목 : Lecture 6 - Support Vector Machines | Stanford CS229: Machine Learning Andrew Ng (Autumn 2018)
강의 영상: https://youtu.be/lDwow4aOrtg?si=6KL7pjZOm9i7swPg
강의 자료 (복원): 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

• Naive Bayes
  • Laplace smoothing
  • Event models
• comments on apply ML
• SVM Intro

Naive Bayes

Recap

Generative model

$$
\large
\begin{align}
& x \in \{0,1\}^{n},\quad n=10000\\
&x_{j}=1({\rm word\ j\ appears\ in\ email})
\end{align}
$$

 

$\large x_{j}$는 단어 $\large j$가 메일에 나타나는지를 의미한다. generative model를 만들기 위해선 $\large p(x|y)$과 $\large p(y)$가 필요하다. Naive Bayes에서는 $\large p(x|y)$가 주어진 class에서 개별 feautre들의 조건부 확률의 곱인 $\large \prod^{n}_{j=1}p(x_j|y)$으로 모델링 된다.

Naive Bayes 모델의 parameter는 아래와 같다.

 

$$
\large
\begin{align}
&\phi_{j|y=1}=p(x_{j}=1|y=1)\\
&\phi_{j|y=0}=p(x_{j}=1|y=0)\\
&\phi_{y}=p(y=1)
\end{align}
$$

 

각 parameter들을 maximum likelihood estmates로 이끌어내면 다음과 같이 구해진다.

 

$$
\large
\begin{align}
&\phi_{y} =\frac{\sum\limits^{m}_{i=1}1(y^{(i)}=1)}{m} \\
&\phi_{j|y=1} = \frac{\sum\limits^{m}_{i=1}1(x^{(i)}=1,y^{(i)}=1)}{\sum\limits^{m}_{i=1}1(y^{(i)}=1)}\\
&\phi_{j|y=0} = \frac{\sum\limits^{m}_{i=1}1(x^{(i)}=1,y^{(i)}=0)}{\sum\limits^{m}_{i=1}1(y^{(i)}=0)}
\end{align}
$$

 

예측을 할 때 아래의 식으로 확률을 구한다.

 

$$
\large p(y=1|x)=\frac{p(x|y=1)p(y=1)}{p(x|y=1)p(y=1)+p(x|y=0)p(y=0)}
$$

 

이 알고리즘은 거의 작동하지만 무너지는 때가 있다, “NIPS"(Neural Information Processing Systems, 머신러닝 컨퍼런스)라는 단어가 사전의 10000개의 단어중 6017번째에 있다고 했을 때 친구로부터 ”NIPS 컨퍼런스에 논문을 제출할거야?“라는 메일을 받았다. 하지만 지금까지 받은 메일중 ”NIPS"라는 단어를 포함한 메일이 없고 parameter의 MLE를 구하면 $\large \phi_{j|y=1}=p(x_{6017}|y=1)=\frac{0}{\#\{y=1\}},\ \phi_{j|y=0}=p(x_{6017}|y=0)=\frac{0}{\#\{y=0\}}$  이 된다. 아직 본 적이 없다고해서 확률이 0이라고 하는것은 통계적으로 좋은 생각은 아니다. 이것이 Naive Bayes algorithm을 무너지게 한다.

$\large p(x|y=1)= \prod^{n}{j=1}p(x_j|y=1)$ 이고 $\large p(x{6017}|y=1)$이 0이기 때문에 $\large p(x|y=1)=0$이 된다. 같은 이유로 $\large p(x|y=0)=0$이다. 따라서 "NIPS"라는 단어가 친구로부터 온 메일에 처음 포함되어 있었다면 이것이 스팸일 확률 $\large p(y=1|x) = \frac{0}{0+0}$이 되어 분모가 $\large 0$이 되는 오류가 발생한다.

Laplace Smoothing

Laplace smoothing은 위에서 언급한 문제점을 해결할 수 있는 방법이다. Laplace smoothing은 각 경우의 수에 1을 더해주는 것이다. 예를 들어 클래스가 1인 data를 하나도 보지 못했더라도 한 개를 본 것으로 하고, 3개를 봤다면 4개를 본 것으로 한다. 이것으로 확률이 0이 되는 것을 방지하여 더욱 의미있는 확률을 얻을 수 있게 된다. 일반화 하면 $\large x\in{1,\cdots,k}$ 일때 $\large P(x=j)=\frac{\sum^{m})_{j=1}1(x^{(i)}=j)+1}{m+k}$로 추정한다.

Naive Bayes에서는 $\large \phi_{j|y=0}$의 MLE를 Laplace smoothing을 사용하여 분자에 1, 분모에 2를 더해 구한다. 이것은 추정한 확률이 정확히 1이나 0이 될 수 없으며 $\large \frac{0}{0}$이 되지 않음을 의미한다.

 

$$
\large \phi_{j|y=0} = \frac{\sum\limits^{m}_{i=1}1(x^{(i)}=1,y^{(i)}=0)+1}{\sum\limits^{m}_{i=1}1(y^{(i)}=0)+2}
$$

Event Model

text classification의 특정한 문제를 다룰 때 더 좋은 Naive Bayes의 변형이다. “Desk! Buy Desks now!"라는 매우 스팸스러운 이메일을 받았다고 할 때 우리가 지금까지 다루었던 기존의 Naive Bayes에서는 $\large x$를 아래처럼 표현한다.

$$
\large
x= \begin{bmatrix}0 \\ 0 \\ \vdots \\ 1 \\  \vdots \\  1 \\ \vdots \\  1 \end{bmatrix}\ \begin{matrix} a \\ aardvark \\ \vdots \\ buy \\ \vdots  \\ desks \\ \vdots \\ now\end{matrix} \ \begin{matrix} 1st \\ 2nd \\ \vdots \\ 800th \\ \vdots  \\ 1600th \\ \vdots \\ 6200th \end{matrix}
$$

이 경우 'Desks“가 두번 나왔지만 $\large x_{j}\in{0,1}$이기 때문에 약간의 정보 손실이 발생하게 된다. text data는 매우 짧거나 매우 길수도 있다는 특징이 있다. 위와 같이 data를 표현하면 길이와 무관하게 항상 같은 길이로 feature vector를 mapping하게 된다. 예전엔 위 표현은 Multivariate Bernoulli event model이라고 부르기도 했다.

Multinomial event model이라는 text data에만 해당되는 새로운 representation이 있다.

$$
x=\begin{bmatrix} 1600 \ 800 \ 1600 \ 6200 \end{bmatrix} \in \mathbb{R}^{n_{i}}\quad x_{j}\in{1,\cdots,10000}\quad n_{i}={\rm length\ of\ email\ i}
$$

항상 10000-dimensional feature vector를 사용했었지만 이번엔 4-dimensional feature vector를 사용한다. 이메일이 길면 feature vector도 길고 eamil이 짧으면 feature vector도 짧다.

이 새로운 모델을 사용하여 generative model를 만들것이다.

 

$$
\large
\begin{align}
p(x,y)&=p(x|y)p(y) \\
&=\prod^{n}_{j=1}p(x_{j}|y)p(y)

\end{align}
$$

 

이것은 저번 강의에서 Naive Bayes에 대해 처음 다뤘을 때 보았던 식과 외적으로 동일하지만 $\large n$과 $\large x_{j}$가 의미하는 것이 다르다. $\large n$은 10000이 아닌 email의 길이이고 $\large p(x_{j}|y)$는 binary나 Bernoulli probability가 아닌 multinomial probability이다. 이 모델의 parameter는 $\large \phi_{j}=p(y=1)$, $\large \phi_{k|y=0}=p(x_{j}=k|y=0)$, $\large \phi_{k|y=1}=p(x_{j}=k|y=1)$이다. $\large \phi_{k|y=0}$는 j번째 단어가 k일 확률이다. 이것은 j에 의존하지 않다는 것을 암시한다. 모든 위치에서 단어 k가 등장할 확률은 모두 같다고 가정한다. $\large \phi_{k|y=0}$의 MLE는 아래와 같다.

$$
\large
\begin{align}
\phi_{k|y=0} =\frac{\sum\limits_{i=1}^{m}\left(1{y^{(i)}=0}\sum\limits_{j=1}^{n_{i}}1{x_{j}^{(i)}=k}\right)}{\sum\limits_{i=1}^{m}1{y^{(i)}=0}n_{i}}
\end{align}
$$

분모는 학습 데이터셋에 있는 스팸이 아닌 모든 메일들의 단어수를 더한 것이고 분자는 스팸이 아닌 모든 메일들에서 k가 등장하는 수를 더한 것이다. 여기에 Laplace smoothing을 적용하기 위해 분자에 1을 더해준다.

$$
\large
\begin{align}
\phi_{k|y=0} =\frac{\sum\limits_{i=1}^{m}\left(1{y^{(i)}=0}\sum\limits_{j=1}^{n_{i}}1{x_{j}^{(i)}=k}\right)+1}{\sum\limits_{i=1}^{m}1{y^{(i)}=0}n_{i}+10000}
\end{align}
$$

분모에는 10000을 더해주는데 이것은 k가 될 수 있는 값 즉, $\large x_{j}$가 될 수 있는 값이 10000개이기 때문이다. dictionary에 없는 단어를 처리하는 방법으로 두가지 방법을 선택할 수 있다. 첫번째는 그냥 버리는 것이고 두번째는 "UNK"(unkown) token등 특별한 token을 만들어 처리하는 것이다.

Naive Bayes algorithm은 다른 learning algorithm에 비해 경쟁적이지 않다. 대부분의 문제들이 logistic regression으로 푸는 것이 더 효율적이다. 하지만 Naive Bayes의 장점은 계산적으로 효율적이고 비교적 빨리 구현할 수 있다. 반복적인 gradient descent 같은 것도 안해도 되고 코드 몇줄이면 바로 구현할 수 있다. (GDA도). "quick and dirty"하게 모델을 만들어야할 때 의미있게 사용된다.

Support Vector Machine

support vector machine

위와 같은 dataset이 있다고 할 때 우리는 오른쪽의 non-linear decision boundary를 찾아야한다. Support Vector Machine은 아주 non-linear한 decision boundary를 찾도록 도와준다. 지금까지 다룬 Logistic regression과 GDA는 linear한 직선 decision boundary를 찾아낸다. Logisitc regression에 non-linearlity를 적용시키는 방법은 $\large x_{1},\ x_{2}$를 $\large \phi(x)= \begin{bmatrix} x_{1} \ x_{2}\ x_{1}^{2}\ x_{2}^{2}\ x_{1}x_{2} \end{bmatrix}$
등의 high dimensional feature vector로 mapping하는 것이다. 증가된 feature들에 logistic regression을 적용시키면 non-linear한 decision boundary를 얻을 수 있다. $\large \phi(x)$로 mapping 하였다면 decision boundary가 타원형으로 얻어진다. 하지만 우리가 얻고 싶은 decision boundary는 타원보다 조금 더 복잡하게 생겼고 이런 decision boundary를 얻기 위해 feature를 고르는 것은 매우 어렵다.

Support Vector Machine은 $\large x_{1},\ x_{2}$를 input으로 받아 고차원의 feature set으로 mapping 시켜 linear classifier를 적용시킨다. 이것은 logistic regerssion과 비슷하지만 아주 non-linear한 dicision boundary를 학습시키는 자세한 방법은 다르다. 오늘날에 Support Vector Machine을 사용하는 이유는 이것이 비교적 turn-key algorithm이기 때문이다. “turn-key”는 만지작거릴 parameter가 많이 없다는 것을 의미한다. logistic regression이나 linear regression은 learning rate를 tuning 해야한다. 여러가지 값들을 시도해야하고 그 값이 결과를 망치지 않길 기도해야한다. Support Vector Machine은 neural network만큼 효과적이지 않지만 열쇠를 돌리기만 하면 작동하는 (turn key) 대단한 특징이 있다.

Optimal Margin Classifier

SVM을 정의하기 위해선 두가지 margin에 대해 정의해야한다.

Functional Margin

functional margin

classifier의 functional margin은 비공식적으로 얼마나 자신있고 정확하게 example들을 분류하는지를 의미한다. 예를 들어 $\large h_{\theta}=g(\theta^{T}x)\quad g={\rm sigmoid}$이고 $\large \theta^{T}x\geq0$일때 1, 아닐때 0을 예측한다고 할 때 $\large y^{(i)}$가 1이라면 $\large \theta^{T}x^{(i)}$의 값이 0보다 많이 커야 $\large h_{\theta}$의 값이 1에 가까워진다. $\large y^{(i)}=1$일때 $\large h_{\theta}$가 1과 가까워질수록 더욱 정확하고 자신있는 예측값이다. 이런 경우 large functional margin이라고 한다.

Geometric Margin

위와 같이 example들을 분리했다고 할때 초록색 선과 빨간색 선 모두 posivite와 negetive를 분리했지만 초록샌 선이 빨간색 선보다 더 잘 분리한 것 처럼 보인다. 이것은 빨간색 선이 training exmple들과 가까이 있고 초록색 선은 더 멀리 떨어져 있기 때문이다. training example들과 decision boundar 사이의 물리적으로 간격을 geometric margin이라고 한다. SVM이 기본적인 기능이 Optimal margin classier이고 이것은 geometric margin을 maximize 하도록 최적화 하는 것이다.

Formalize

Functional Margin

$(\large x^{(i)}, y^{(i)})$에 대한 hyperplane의 functional margin은 $\large (w,b)$로 정의된다.

$$
\large \hat{\gamma}^{(i)}=y^{(i)}\left(w^{T}x^{(i)}+b\right)
$$

• 만약 $\large y^{(i)}=1$이라면 $\large w^{T}x^{(i)}+b\gg0$ 이길 원한다.
• 만약 $\large y^{(i)}=-1$이라면 $\large w^{T}x^{(i)}+b\ll0$ 이길 원한다.
• $\large \hat{\gamma}^{(i)}$는 이 둘의 곱이기 때문에 이것을 정리하면 $\large \hat{\gamma}^{(i)}\gg0$이길 원한다.
• $\large \hat{\gamma}^{(i)}>0$라는 것은 $\large h(x^{(i)})=y^{(i)}$라는 것을 의미한다.

training set 전체에 대한 functional margin은 각 example의 functional margin의 최솟값(worst)으로 정의된다.

$$
\large \hat{\gamma}=\min_{i}\hat{\gamma}^{(i)}
$$

funcitonal margin은 $\large w,\ b$에 상수를 곱하는 cheating으로 쉽게 늘릴 수 있다. $\large h_{w,b}$는 $\large w^{T}x^{(i)}+b$ 값이 아닌 부호에만 의미가 있기 때문에 의미있는 변화는 일어나지 않는다. 이런 cheating을 방지하기 위해 $\large w,b$의 길이를 1로 만들어주는 normalizing을 해준다. 이것은 calssification의 결과에 주지 않는 parameter의 크기만 바꿔주는 작업이다.

Geometric Margin

geometric margin

$\large (w,b)$에 의해 정의된 linear classifier $\large w^{T}x+b$가 있을 때 위쪽은 $\large y^{(i)}=1$로 예측하고 아래쪽은 $\large y^{(i)}=0$로 예측한다. 여기서 해야할 것은 geometric margin이 되는 직선까지의 거리를 정의해야한다. $(\large x^{(i)}, y^{(i)})$에 대한 hyperplane의 geometric margin은 아래와 같이 정의된다.

$$
\large
\gamma^{(i)}=\frac{y^{(i)}\left(w^{T}x^{(i)}+b\right)}{\rVert w \lVert}
$$

이것은 example과 decision boundary 사이의 Euclidean distance이다. 분자는 functional margin과 같기 때문에 이를 이용해 정의할 수 있다.

$$
\large
\gamma^{(i)}=\frac{\hat{\gamma}^{(i)}}{\lVert w \rVert}
$$

training set 전체에 대한 geometric margin은 각 example의 geometric margin의 최솟값(worst)으로 정의된다.

$$
\large \gamma=\min_{i}\gamma^{(i)}
$$

Conclusion

따라서 Optimal margin classifier는 $\large \gamma$를 maximize하는 $\large w,\ b$를 고른다.

$$
\large
\begin{align}
\max_{\gamma,w,b} & \quad \gamma\
s.t.&\quad \frac{y^{(i)}\left(w^{T}x^{(i)}+b\right)}{\lVert w\rVert}\geq \gamma,\quad i=1,\dots,m
\end{align}
$$

이것은 convex optimization problem이 아니기 때문에 gradient descent로 풀기 어렵다. convex optimization problem으로 바꿔주기 위해 lecture note에 있는 몇가지 단계를 거치면 위 식은 아래의 식과 같은 의미를 같게 된다.

$$
\large
\begin{align}
\min_{w,b} &\quad \frac{1}{2}\lVert w\rVert^2\
s.t&\quad y^{(i)}\left(w^{T}x^{(i)}+b\right)\geq 1
\end{align}
$$

(이 부분 자막 오역)