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

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

 

---

Course : Stanford CS229: Machine Learning Full Course taught by Andrew Ng | Autumn 2018

Course 소개 : CS229는 기계 학습과 통계적 패턴 인식에 대한 포괄적인 소개를 제공합니다. 지도 학습(생성적/판별적 학습, 모수/비모수 학습, 신경망, 서포트 벡터 머신); 비지도 학습(클러스터링, 차원 축소, 커널 메소드); 학습 이론(편향/분산 트레이드오프, 실용적인 조언); 강화 학습 및 적응 제어에 대한 강의를 다룹니다. 또한 기계 학습의 최근 응용에 대해 논의되며, 로봇 제어, 데이터 마이닝, 자율 항법, 생명 정보학, 음성 인식, 텍스트 및 웹 데이터 처리 등이 포함됩니다.

강의 제목 : Locally Weighted & Logistic Regression | Stanford CS229: Machine Learning - Lecture 3 (Autumn 2018)

강의 영상: https://youtu.be/nt63k3bfXS0?si=s_cCDW-JpxdF0yLy

강의 자료 (복원): 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

• Generative Learning Algorithms
  • Gaussian Discriminant Analysis (GDA)
  • Generative vs Discriminative comparison
  • Naive Bayes

Generative Learning Algorithms

decision boundary

위와 같이 두가지 클래스를 가지고 있는 dataset이 있을 때 Logistic regression과 같은 discriminative learning algorithm은 positive와 negative examples들을 나누는 직선인 decision boundary를 찾는다. 이것과 다르게 이런 seperation을 찾지않는, 저번 ㅏ강의에서 다룬 lieklihood를 최대화하지 않는 gernerative learning algorithm이라는 방법이 있다.

Discriminant learning algorithm

Generative learning algorithm은 두 클래스의 seperation을 찾는 대신 두 개의 클래스를 한번에 하나씩 확인한다. x를 악성 종양, o를 양성 종양이라고 했을 때 악성 종양이 어떻게 보이는지 분포에 대한 모델을 만들고 종양에 대한 분포도 악성 종양과 분리하여 모델을 만든다. 각 모델이 위의 그림과 같이 대충 타원형으로 나온다고 했을 때 새로운 데이터가 들어오면 그 데이터가 두 모델중 어느 모델에 더 가까운지 계산한다.

이것을 수식화하면 Discriminant learning algorithm은 $\large p(y|x)$을 학습하거나 x를 대응시키는 $h_{\theta}(x)$를 바로 학습한다. positive와 negative 클래스들을 판별하도록 학습한다. Generative learning algorithm은 주어진 class에서 특징들이 어떤지를 나타내는 $\large p(x|y)$를 학습한다. 위의 예시에서 양성일때 주어진 features $\large x$가 어떤 분포를 보이는지 학습하는 것이다. 그리고 class prior인 $\large p(y)$ 또한 학습한다. $\large p(x|y)$와 $\large p(y)$에 대한 모델이 만들어졌다면 이 두 값을 구할 수 있다. 새로운 데이터가 들어왔을 때 이 두 값과 Bayes rule을 이용하여 아래 값을 구한다.

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

$\large p(x)$ 값은 아래의 식으로 구할 수 있다.

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

Generative learning algorithms의 두가지 예제들을 다뤄볼것이다. 하나는 종양 분류와 같은 곳에 사용되는 continuous에 대한 것이고 하나는 이메일 스팸 분류와 같은 곳에 사용되는 discrete features에 대한 것이다.

Gaussian Discriminant Analysis (GDA)

$$
\begin{align}
& {\rm Suppose}\ x\in\mathbb{R}^{n}\quad({\rm drop}\ x_{0}=1\ {\rm convention}) \
& {\rm Assume}\ p(x|y)\ {\rm is \ Gaussian} \
\end{align}
$$

 

이 모델을 개발하기 위해 features $\large x$가 continuous value라고 가정(assume)한다 ($\large x\in\mathbb{R}^n$). $\large x_{0}=1$ convention을 제거하여 $\large x\in\mathbb{R}^{n+1}$가 아닌 $\large x\in\mathbb{R}^n$이다. GDA의 주요 assumption은 $\large P(x|y)$가 Gaussian 분포를 따른다. 다시말해 양성 종양의 모든 feature들이 Gaussian 분포를 따른다는 것이다.

Multivariate Gaussian

시작에 앞서 multivariate gaussian을 이해해야하는데 이것은 1-dimensional random variable의 Gaussian을 multiple dimensional random variable로 확장한 것이다.

$$
z\sim \mathcal{N}(\vec{\mu},\Sigma),\quad \vec{\mu}\in \mathbb{R}^{n},\quad \Sigma \in \mathbb{R}^{n\times n}
$$

$$
\begin{align}
& E[z] = \mu\
& Cov(z)=E[(z-\mu)(z-\mu)^{T}]=Ezz^T-(Ez)(Ez)^T\
& E[z] = Ez
\end{align}
$$

Gaussian의 probability density function은 아래와 같다.

$$
\large\begin{eqnarray}
p(z)=\frac{1}{(2\pi)^{\frac{n}{2}}|\Sigma|^{\frac{1}{2}}}exp\left(-\frac{1}{2}(z-\mu)^{T}\Sigma^{-1}(z-\mu)\right)
\end{eqnarray}
$$

GDA Model

GDA에선 $\large p(x|y)$의 모델이 필요하다. 따라서 $\large y=0$ 일때와 $\large y=1$일와의 모델을 각각 구해야한다.

$$
\begin{eqnarray}
p(x|y=0)=\frac{1}{(2\pi)^{\frac{n}{2}}|\Sigma|^{\frac{1}{2}}}exp\left(-\frac{1}{2}(x-\mu_{0})^{T}\Sigma^{-1}(x-\mu_{0})\right)
\end{eqnarray}
$$

 

$$
\begin{eqnarray}
p(x|y=1)=\frac{1}{(2\pi)^{\frac{n}{2}}|\Sigma|^{\frac{1}{2}}}exp\left(-\frac{1}{2}(x-\mu_{1})^{T}\Sigma^{-1}(x-\mu_{1})\right)
\end{eqnarray}
$$

위 모델에서 파라미터는 $\large \mu_{0},\ \mu_{1},\ \Sigma$ 이다. 두 클래스의 $\large \Sigma$를 각 각 구해도 되지만 보통 그러지 않는다. 따라서 positive와 negative 클래스가 같은 covariance matrix를 가지지만 다른 mean을 가지고 있다고 가정한다. $\large p(x|y)$에 대한 모델을 구했다면 $\large p(y)$에 대한 모델을 구해야한다. y는 Bernoulli random variable이다. 따라서 아래와 같이 쓸 수 있다.

$$
\large p(y)=\phi^{y}(1-\phi)^{1-y}\quad (p(y=1)=\phi)
$$

GDA 모델의 파라미터는 $\mu_{0},\ \mu_{1},\ \Sigma,\ \phi$ 4개이다.($\large \mu_{0},\ \mu_{1}\in \mathbb{R}^{n},\ \Sigma \in \mathbb{R}^{n\times n},\ \phi \in \mathbb{R}$) 이 파라미터들을 fitting 할 수 있다면 $\large p(x|y)$와 $\large p(y)$를 정의할 수 있다. 이 모델들로부터 얻은 값을 대입한다면 새로운 환자의 종양이 양성일 확률과 악성일 확률을 구할 수 있다.

Training set ${x_{(i)},\ y_{(i)} }$이 있다고 할 때 parameter를 fitting 하기 위해 joint likelihood를 최대화 할 것이다. 파라미터들의 likelihood는 아래와 같이 정의된다.

 

$$
\begin{align}
\large \mathcal{L}(\phi,\mu_{0},\mu_{1},\Sigma) & = \prod^{m}_{i=1}p(x^{(i)},y_{(i)};\phi,\mu_{0},\mu_{1},\Sigma)\\
&=\prod^{m}_{i=1}p(x^{(i)}|y^{(i)})p(y^{(i)})
\end{align}
$$

 

Discriminative learning algorithm과 비교했을 때 generative learning algorithm의 가장 큰 차이점은 최대화하는 cost function이 jointly likelihood라는 것이다. Discriminative learning algorithm에서는 conditional likelihood라고도 부르는 아래 식을 최대화한다.

$$
\mathcal{L}=\prod^{m}_{i=1}p(y^{(i)}|x^{(i)};\theta)
$$

Maximum Likelihood Estimation

MLE를 구하기 위해선 likelihood에 log를 취한 log likelihood를 각 파라미터에 대해 미분하여 그 값을 0이 되도록 하는 파라미터값을 구하면 된다. log likelihood는 아래와 같이 정의된다.

 

\begin{align}
\large \mathcal{l}(\phi,\mu_{0},\mu_{1},\Sigma) & = \log \prod^{m}_{i=1}p(x^{(i)},y_{(i)};\phi,\mu_{0},\mu_{1},\Sigma)\\
&=\log \prod^{m}_{i=1}p(x^{(i)}|y^{(i)})p(y^{(i)})
\end{align}

 

이 함수를 각 파라미터에 대해 미분한 뒤 미분값이 0이 되도록 하는 값을 구해보면 아래와 같다.

 

$$
\phi = \frac{\sum\limits^{m}_{i=1}y^{(i)}}{m}=\frac{\sum\limits^{m}_{i=1}1(y^{(i)}=1)}{m}
$$

$\large \phi$는 전체 dataset중 악성 종양($\large y^{(i)}=1)$을 가진 data의 비율이다.

$$
\large \mu_{0}= \frac{\sum\limits^{m}_{i=1}1(y^{(i)}=0)x^{(i)}}{\sum\limits^{m}_{i=1}1(y^{(i)}=0)}
$$

분자는 $\large y^{(i)}=0$인 example들의 feature 값의 합이고 분모는 $\large y^{(i)}=0$인 exmaple들의 개수이다. 따라서 $\large \mu_{0}$는 양성 종양을 가진 데이터들의 각 feature의 평균값이다.

$$
\large \mu_{1}= \frac{\sum\limits^{m}_{i=1}1(y^{(i)}=1)x^{(i)}}{\sum\limits^{m}_{i=1}1(y^{(i)}=1)}
$$

$\large \mu_{1}$도 $\large \mu_{0}$와 같은 방법으로 계산된다.

$$
\large \Sigma=\frac{1}{m}\sum\limits^{m}_{i=1}\left(x^{(i)}-\mu_{y^{(i)}}\right)\left(x^{(i)}-\mu_{y^{(i)}}\right)^{T}
$$

파라미터들을 모두 fitting했다면 아래의 시기으로 예측값을 구하면된다.

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

GDA Vs Logistic Regression

decision boundary

위 그림은 generative learning algorithm과 discriminative learning algorithm 두 방법으로 구한 decision boundary이다. 두 learning algorithm에서 decision boundary를 구한 방법이 다르기 때문에 다른 직선이 나오게 된다.
초록색 직선은 discriminative learning algorithm으로부터 구해진 decision boundary이다. 이 알고리즘은 임의의 직선으로 시작해 conditional likelihood에 대해 gradient ascent를 반복하여 최종 결과를 얻어낸다.
파란색 직선은 generative learning algorithm으로부터 구해진 decision boundary이다. positive와 negative example들에 대해 Gaussian을 fitting하고 Baye's rule을 통해 class label이 무엇인지 정한다. decision boundary의 오른쪽 위에 있는 점들은 positive에 더 가까운 점들이고 왼쪽 아래에 있는 점들은 negative에 더 가까운 점들이다. 두 클래스를 분리해서 gaussian을 fitting 했지만 같은 Sigma를 사용하기 때문에 완벽히 분리한 것은 아니다. 두 class에 대해 같은 sigma를 쓰는 이유는 decision boundary가 linear하게 나오기 때문이다. 다른 Sigma를 쓰게 된다면 decision boundary가 linear하게 나오지 않는다.

파라미터 $\large \mu_{0},\ \mu_{1},\ \Sigma,\ \phi$ 가 고정되어 있을 때 $\large p(y=1|x;phi,\mu_{0},\mu_{1},\Sigma)$를 $\large x$에 대한 함수로 plot 해보자. 이것은 baye's rule에 의해 $\large \frac{p(x|y=1;\mu_{1},\Sigma)p(y=1;\phi)}{p(x;\phi,\mu_{0},\mu_{1},\Sigma)}$와 같다. 파라미터가 고정되어 있기 때문에 Gaussian density를 계산하여 $\large p(x|y=1;\mu_{1},\Sigma)$값을 구할 수 있다. 분자 또한 비슷하게 계산할 수 있고 $\large p(y=1;\phi)=\phi$로 그 값을 알 수 있다. 따라서 모든 값을 숫자로 계산할 수 있다.

1-D

한 개의 feature만 가지고 있는 간단한 dataset이 있다면 위 사진처럼 $\large x$축 위에 표시할 수 있다. dataset의 각 클래스에 대해 Gaussian을 fitting한다면 아래와 같은 그림을 그릴 수 있다.

gaussian fitting

위의 Gaussian을 바탕으로 주어진 $\large x$의 클래스가 1일 확률을 그려보면 위의 그림처럼 나온다. 클래스가 1인 data들이 오른쪽에 분포되어 있기 때문에 왼쪽에서 오른쪽으로 갈 수록 클래스가 1일 확률이 증가한다. 두 Gaussian이 만나는 지점이 클래스가 0일 확률과 1일 확률이 정확히 50:50인 지점이다. 이 함수는 정확히 sigmoid와 같다. GDA와 logistic regression 모두 결국 $\large p(y=1|x)$를 계산하는데에 sigmoid function을 사용하거나 그 결과가 sigmoid funciton이 된다. 하지만 위의 plot에서 본 것 처럼 parameter를 어떻게 정하냐에 따라 결과가 달라진다.

Which One is Superior?

(Generative) GDA assumes

 

$$
\large
\begin{align}
& x|y=0 \sim \mathcal{N}(\mu_{0},\Sigma)\
& x|y=1 \sim \mathcal{N}(\mu_{1},\Sigma)\
& y\sim \mathcal{Ber}(\phi)
\end{align}
$$

 

(Discriminative) Logistic regression assumes

 

$$
\large
\begin{align}
&p(y=1|x)=\frac{1}{1+e^{-\theta^{T}x}}\
&x_{0}=1
\end{align}
$$

 

GDA의 assumption들은 Logistic regression의 assumption들인 $\large p(y=1|x)$가 logistic function이라는 것을 암시한다. 하지만 그 역은 성립하지 않는다. $\large p(y=1|x)$가 logistic function이더라도 $\large x|y$가 Gaussian이 아닐 수 있다. 이것은 GDA가 Logistic regression 보다 "stronger set of assumptions"을 만들고 Logistic regression은 GDA보다 “weaker set of assumptions"을 만든다는 것을 의미한다. 따라서 $\large x|y$가 실제로 Gaussian이라면 GDA가 logistic regression보다 우수하다. 하지만 $\large x|y$가 Gaussian이 아니여서 GDA의 assumption이서 틀렸다면 logistic regression이 더 우수할 것이다.
여기서 재밌는 사실이 있다. $\large x|y$가 Poisson 분포를 따라도 $\large p(y=1|x)$는 logistic function이다. $\large x|y$가 natural parameter에만 따르는 exponential families라면 $\large p(y=1|x)$는 logistic function이다. 이것은 data가 Gaussian인지 Poisson인지 또는 다른 Exponential families인지 몰라도 logistic regression을 사용하는것에 걱정하지 않아도 된다는 것이다. 하지만 만약 data가 Poisson인데 Gaussian으로 가정하여 GDA를 사용했다면 그 모델은 매우 빈약할 것이다.
logistic regression과 같이 weaker assumptions을 만든다면 알고리즘은 data가 Gaussian이고 아니고를 우연히 가정하는 것을 모델링하는 것에 대해 더욱 강력해질것이다. 반대로 data가 매우 적다면 많은 assumption들을 만드는 모델을 사용하는 것이 세상에 대한 더 많은 정보를 모델에게 알려주는 것이기 때문에 더 좋다. 데이터가 매우 많다면 세상에 대한 정보를 적게 줘도 알고리즘이 그것을 극복할 수 있다.

Naive Bayes

Naive Bayes는 generative learning algorithm의 한 종류로 spam email을 분류하는데 주로 사용된다. 스팸 메일을 분류할 때 feature vecotr $\large x$는 어떻게 표현해야할까? 이메일을 모두 수집한 뒤 가장 많이 등장하는 순으로 10,000개의 단어들을 추려 dictionary를 만든다. 이것을 이용하여 각 이메일에서 dictionary에 포함된 단어가 등장하는지에 대한 binary feature vector를 만들 수 있다.

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

Naive Bayes algorithm에서는 generative learning algorithm을 구축할 것이므로 $\large p(x|y), p(y)$을 모델링해야 한다. 하지만 $\large x$가 10000-dimensional binary vector이기 때문에 $\large x$로 $\large 2^{10000}$개의 값이 가능하다. 따라서 $\large p(x|y)$를 multinomial distributiond으로 모델링 하게되면 $\large 2^{10000}-1$개의 결과값과 parameter들이 나온다. 너무 많은 parameter들로 인해 추가적인 assumptions 없이는 모델링하는 것은 효과가 없다.

Naive Bayes algorithm에서는 $\large x_{i}$들이 주어진 $\large y$에 대해 conditionaly independent 하다고 가정한다.이 가정에 의해 아래의 식이 성립한다.

$$
\large
\begin{align}

 p(x_{1},\ \dots,\ x_{10000})&=p(x_{1}|y)p(x_{2}|x_{1},y)\cdots p(x_{10000}|\cdots)\\
&=p(x_{1}|y)p(x_2|y)\cdots p(x_{10000}|y)\\
&=\prod^{n}_{i=1}p(x_{i}|y)
\end{align}
$$

이 assumption은 conditional independece assumption이라고 불리고 Naive Bayes assumption이라고 불리기도 한다. 이것은 이메일에 ”aardvark“가 등장할 확률이 ”A"가 등장하는 것과 무관하다고 가정하는 것이다. 이 assumption은 사실인지 확실하지 않고 수학적으로 정확하지 않은 assumptions들 중 하나이다. 이 assumption이 수학적으로 사실이 아니지만 이 assumption을 사용할 수 없을 정도로 심각하지는 않을것이기 때문에 이 assumption을 사용한다.

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}
$$

$\large \phi_{j|y=1}$은 이메일이 spam일 때 단어 $\large j$가 등장할 확률을 의미하며 $\large \phi_{j|y=0}$은 이메일이 spam이 아닐 때 단어 $\large j$가 등장할 확률을 의미한다. $\large \phi_{y}$는 다음 이메일로 스팸을 받을 prior 확률을 의미한다.

Naive Bayes는 아래와 같은 Joint likelihood를 사용한다.

$$
\large \mathcal{L}(\phi_{y}, \phi_{j|y})=\prod^{m}_{i=1}p(x^{(i)},y^{(i)};\phi_{y},\phi_{j|y})
$$

위 식에 log를 취하고 미분하여 MLE를 구해보면 아래와 같은 결과를 얻을 수 있다.

$$
\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)} 



\end{align}
$$

$\large \phi_{y}$는 spam 이메일의 비율이고 $\large \phi_{j|y=1}$은 spam 이메일 중 단어 $\large j$를 포함할 비율이다.

이 알고리즘을 구현 했다면 spam을 상당히 잘 분류한다. 이 algorithm을 보완하는 방법을 다음 강의에서 다뤄볼 것이다. logistic regression을 이용하여 spam 분류를 했다면 항상 더 좋은 결과를 내놓을 것이지만 Naive Bayes algorithm은 매우 효율적인 알고리즘이다. counting 만으로 parameter들을 추정할 수 있고 많은 숫자들이 곱해질 뿐이지 iterative한 것이 없다. 따라서 매우 효율적으로 이 모델을 fitting 할 수 있고 새로운 데이터들이 생긴다면 그 데이터들로 모델을 업데이트 해주기만하면 된다. 이 algorithm의 가장 큰 문제점은 위의 식들 중 0이 등장했을 때 발생한다. 이것을 해결하는 방법인 Laplace moving에 대해 다음 강의에서 다뤄볼 것이다.