Gaussian models (MVN, QDA, LDA)
Gaussian models
Multivariate Gaussian 또는 MVN (Multivariate Normal)은 연속적인 데이터에 대한 joint probability density function에서 사용하며, D 차원의 MVN에 대한 PDF는 다음과 같이 정의한다.
$$ \mathcal N(x|{\mu,\Sigma})\triangleq\frac{1}{(2\pi)^{D/2}|\Sigma|^{1/2}}\exp\left[-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu)\right] $$
exponential 안 수식은 featrue $x$와 mean vector $\mu$ 사이의 차이를 나타내는 mahalanobis distance로, $\Sigma$에 대해 eigen decomposition을 수행함으로써 이를 더 잘 이해할 수 있다.
$\Sigma=U\Lambda U^T$ 로 쓸 수 있고, 여기서 $U$는 $U^{T}U = I$를 만족하는 eigenvector의 orthonormal matrix이다.
($U^{T} = U^{-1}$ 를 만족한다.)
$\Lambda$ 는 eigen value의 diagonal matrix이다.
$\Sigma$를 eigen decomposition을 하게 되면 다음의 식을 얻을 수 있다.
$$ \mathbf\Sigma^{-1}=U^{-T}\Lambda^{-1}U^{-1}={U\Lambda}^{-1}U^T=\sum_{i=1}^D\frac{1}{\lambda_i}u_iu_i^T $$
여기서 $u_{i}$는 $i$ 번째 eigen vector를 포함하고 있는 $U$ 의 $i$ 번째 column vector 이다.
정리하자면 $\Sigma^{-1}$ 를 eigen decomposition 하여, orthonormal matrix $U$ 와 diagonal matrix $\Lambda$ 로 분리할 수 있고, orthonormal vector의 combination으로 표현할 수 있다.
위 수식에서 $\lambda_{i}$ 의 값은 diagonal matrix $\Lambda$ 에 대한 element라고 생각할 수 있다.
따라서 Mahalanoabis distance를 다음과 같이 쓸 수 있다.
$$ (x-\mu)^T\mathbf\Sigma^{-1}(x-\mu)=(x-\mu)^T\left(\sum_{i=1}^D\frac{1}{\lambda_i}u_iu_i^T\right)(x-\mu)\\ =\sum_{i=1}^D\frac{1}{\lambda_i}(x-\mu)^Tu_iu_i^T(x-\mu)=\sum_{i=1}^D\frac{y_i^2}{\lambda_i} $$
$$ \text{where }y_i\triangleq u_i^T(x-\mu) $$
Mahalanoabis distance를 이해하기 위해, 아래 2차원 타원에 대한 방정식을 생각하면
$$ \frac{y^2_1}{\lambda_1}+\frac{y^2_2}{\lambda_2}=1 $$
$D=2$인 형태인 것을 알 수 있다.
위 plot처럼 표현할 수 있고, 주 축은 $\lambda$ 값이 더 큰 것이 된다.
타원의 반지름의 길이는 $\sqrt{\lambda_{1}}$ 가 되고, eigen vector $\mu$ 는 타원의 방향을 나타낸다.
MLE for MVN
이제는 MLE를 사용하여 MVN의 parameter를 추정하는 방법에 대해 알아보자.
MLE를 사용한다는 것은 MVN의 중요한 term인 mean과 covariance를 구하겠다는 의미로, 이를 위해 중요한 이론을 알아야 한다.
만약 $N$개의 $i.i.d.$인 $x_{i} \sim N(\mu, \Sigma)$가 주어 진다면 MLE의 parameter는 다음과 같이 정의된다.
$$ \hat{\mu}{mle}=\frac{1}{N}\sum{i=1}^Nx_i\triangleq\overline{x} \\ \hat{\Sigma}{mle}=\frac{1}{N}\sum{i=1}^N(x_i-\overline{x})(x_i-\overline{x})^T=\frac{1}{N}\left(\sum_{i=1}^Nx_ix_i^T\right)-\overline{x}\ \overline{x}^T $$
이를 단변량의 경우면 식은 다음과 같이 표현할 수 있다.
$$ \hat\mu=\frac{1}{N}\sum_i x_i=\overline x \\ \hat\sigma^2=\frac{1}{N}\sum_i(x_i-\overline x)^2=\left(\frac{1}{N}\sum_i x_i^2\right)-(\overline x)^2 $$
Gaussian Discriminant Analysis
모델을 이용해서 sample을 분리하는 것이다.
앞서 Generative model에 대해 다뤘었는데, 이는 다음과 같이 정의했다.
$$ p(y=c|{x},\theta)= \frac{p(y=c|\theta)p(x|y=c,\theta)}{\sum_{c'}p(y=c'|\theta)p(x|y=c',\theta)} $$
베이즈를 이용해 위와 같이 쓸 수 있고, 분자를 가우시안을 이용해서 likelihood를 정의할 수 있다.
$$ p(x|y=c,\theta)=\mathcal N(x|\mu_c,\mathbf\Sigma_c) $$
이를 Gaussian discriminant analysis라고 한다.
만약 $\Sigma_{c}$가 diagonal이면 naive Bayes와 동일하다.
이를 이용하여 classification 하고 싶은 것은 class label을 예측하는 것으로, argmax를 해서 로그를 취해 수식을 변경하면 된다.
$$ \hat y(x)=argmax_c[\log p(y=c|\pi)+\log p(x|\theta_c)] $$
결국 위 수식은 prior term과 likelihood term으로 구성된 다는 것을 알 수 있다.
또한 Mahalanoabis distance를 이용하여 $x$ 에서 각 class의 중심인 $\mu_{c}$ 까지의 거리를 측정할 수 있다.
이를 nearest centroid classifier로 생각할 수 있다.
Example
예를 들어 남성과 여성의 키와 체중을 나타낸 2차원 데이터가 있다고 하자.
각 feature가 correlation을 형성하는 것을 알 수 있고, 각 class의 ellipse는 probability mass의 95%를 포함한다.
class에 대한 uniform prior가 있는 경우 다음과 같이 Mahalanoabis distance를 이용하여 새로운 test vector를 분류할 수 있다.
$$ \hat y(x)=argmin_c(x-\mu_c)^T\mathbf\Sigma_c^{-1}(x-\mu_c) $$
QDA (Quadratic Discriminant Analysis)
QDA에서는 prior가 uniform 하지 않고, 각각이 다른 경우에 대해 다룬다.
즉 class에 대한 prior까지 고려한 것이 QDA이다. 이를 위해서는 posterior over class label을 구해야 한다.
class label에 대한 posterior는 다음의 수식을 통해 구할 수 있다.
$$ p(y=c|x,\theta)=\frac{\pi_c|2\pi\mathbf\Sigma_c|^{-\frac{1}{2}}\exp\left[-\frac{1}{2}(x-\mu_c)^T\mathbf\Sigma_c^{-1}(x-\mu_c)\right]} {\sum_{c'}\pi_{c'}|2\pi\Sigma_{c'}|^{-\frac{1}{2}}\exp\left[-\frac{1}{2}(x-\mu_{c'})^T\mathbf\Sigma_{c'}^{-1}(x-\mu_{c'})\right]} $$
위 수식에 대해 threshold를 지정하면 $x$ 에 대한 quadratic function이 생성된다.
그 결과를 QDA라고 한다.
위 그림에서는 2D에서 decision boundary가 어떻게 보이는 지에 예를 보여준다.
LDA (Linear Discriminant Analysis)
covariance matrix들이 class 간 서로 공유되는 특별한 경우를 고려해 보자. 즉 아래의 수식을 따른다고 하자.
$$ \Sigma_{c} = \Sigma $$
모든 class에 대해 covariance matrix가 동일한 경우로, 이러한 assumption을 적용하여 QDA를 다음과 같이 분자만 고려하여 proportion 한 형태로 쓸 수 있다.
$$ p(y=c|x,\theta)\propto\pi_c\exp\left[ \mu_c^T\Sigma^{-1}x-\frac{1}{2} x^T\Sigma^{-1}x-\frac{1}{2}\mu_c^T\Sigma^{-1}\mu_c\right]\\ =\exp\left[ \mu_c^T\Sigma^{-1}x-\frac{1}{2}\mu_c^T\Sigma^{-1}\mu_c+\log\pi_c \right]\exp\left[-\frac{1}{2}{x}^T\Sigma^{-1}x\right] $$
위 수식을 살펴보면 첫 번째 $\text{exp}$ term의 2, 3번 째 수식은 bias이고, 2번째 $\text{exp}$ term은 quadratic term이다.
quadratic term은 모든 covariance matrix가 동일하기 때문에, $c$와 독립이 되어 분자, 분모에서 상쇄된다.
따라서 첫 번째 $\text{exp}$ term 만 고려하면 되고, 이는 $x$ 에 대한 linear function 형태이기 때문에, LDA라고 부를 수 있다.
만약 위 수식의 공통 인자들을 아래와 같이 정의한다면 다음과 같이 쓸 수 있다.
$$ \gamma_c=-\frac{1}{2}\mu_c^T\Sigma^{-1}\mu_c+\log\pi_c \\ \beta_c=\Sigma^{-1}\mu_c $$
$$ p(y=c|x,\theta) \frac{\exp\left[{\beta_c^T{x}+\gamma_c}\right]}{\sum_{c'}\exp\left[{\beta_{c'}^T{x}+\gamma_{c'}}\right]}=\mathcal{S}(\eta)_c $$
위 수식과 같이 softmax 함수로 정의가 된다. softmax의 수식은 다음과 같다.
$$ \mathcal{S}(\eta)c=\frac{e^{\eta_c}}{\sum{c'=1}^Ce^{\eta_{c'}}} $$
softmax function은 max function과 비슷한 역할을 진행한다. 이를 확인하기 위해 $\eta_{c}$를 temperature라고 불리는 상수 $T$ 로 나누어보자.
$$ \mathcal{S}(\eta/T)c=\frac{e^{\eta_c/T}}{\sum{c'=1}^Ce^{\eta_{c'}/T}} $$
그리고 $T$ → $0$ 인 경우를 보자.
$$ \mathcal{S}(\eta/T)c=\begin{cases} &1.0\quad\text{if }c=argmax{c'}\eta_{c'}\\ &0.0\quad\text{otherwise} \end{cases} $$
반대로 $T$ → $infin$ 의 경우는 다음과 같이 된다.
$$ \mathcal{S}(\eta/T)_c= \text{uniform} $$
즉, 저온에서 distribution은 본질적으로 가장 가능성 있는 상태에서 모든 시간을 소비하지만, 고온에서는 모든 상태를 균일하게 유지한다.
T가 커지면 uniform의 특성을 보이는 것을 확인할 수 있고, 작으면 spike 한 모습을 볼 수 있다.
이렇게 LDA의 simplified form이 softmax function 또는 botzmann distribution 형태라는 것에 대해 알아보았다.
더욱 심플한 linear form으로 표현하기 위해 $\log$ 까지 취하면 $\text{exp}$ term까지 상쇄할 수 있다.
이는 각 covariance matrix $\Sigma_{c} = \Sigma$라는 조건이 있어야 한다.
이러한 테크닉을 linear discriminant analysis 또는 LDA라고 하고, 다음과 같이 식을 유도할 수 있다.
$$ p(y=c|{x},\theta)=p(y=c'|{x},\theta)\\ \beta_c^T{x}+\gamma_c=\beta_{c'}^T{x}+\gamma_{c'}\\ {x}^T(\beta_{c'}-\beta)=\gamma_{c'}-\gamma_c $$
위 plot은 class가 2개, 3개인 경우에 대해 LDA를 적용했을 때 linear decision boundary가 형성되는 것을 보여 준다.