[ML] 11. Dimensionality Reduction


## Intro

주어지는 data에 항상 feature, label이 정확하게 매칭되지는 않는다. 이럴 경우 우리는 각 data에 대한 label과 주어진 data와 label을 잘 설명할 수 있는 probability distribution을 모두 구해야 한다. 여기서 label과 probability distribution을 동시에 구하기 위해서는 어떻게 해야할지에 대한 방법 중에서 대표적인 EM Algorithm에 대해서 살펴보도록 하겠다.

## Problem

여태까지 우리가 살펴봤던 supervised learning에서는 학습(learning) 시에는 feature와 label이 모두 동시에 주어지고, 예측/추론(inference)을 수행할 때에는 feature만 존재하는 data가 주어졌다. 따라서, 학습 시에 feature 정보들을 특정 pattern에 녹여냈을 때, label값을 얻는지를 확인할 수 있었다. 하지만, label이 주어지지 않은 data를 학습시킬 때에는 어떻게 해야할까? 우리는 label이 있어야 해당 data가 가진 실제 결과값을 알고 probability distribution을 얼마나 수정할지를 알 수 있었다. 하지만, 이 값을 모르니 probability distribution을 만들 수 없다. 정확한 probability distribution이 있다면, 반대로 label을 생성하는 것도 가능할 것이다. 하지만, 우리는 아무것도 알 수 없다.

이렇게 답답한 상황에서 우리는 다음과 같은 아이디어를 발상해낼 수 있다. 만약, 대략적인 label을 안다면, 이것을 이용해서 최적의 확률 분포를 찾고, 이 확률 분포에 맞는 label을 다시 생성하고 이를 기반으로 다시 확률 분포를 찾는다면 어떨까? 이렇게 반복하면 꽤나 그럴싸한 분포를 만들 수 있지 않을까? 이 과정을 예를 들자면, 다음과 같다.

각 기 다른 나라(label)의 동전 3종류(500원, 100cent, 100엔)를 구분하고 싶다고 하자. 이때, 알 수 있는 정보는 무게(feature) 밖에 없다고 가정하겠다. 이때 우리는 어떻게 구분할 수 있을까? 우리가 길 거리에서 무작위로 동전을 수집했다고 하자. 각 동전은 흠집도 있을 것이고 공장마다 조금씩 무게가 차이있을 수 있다. 그 결과 다음과 같은 분포가 나왔다고 하자.

![ml-em-algorithm-1](/images/ml-em-algorithm-1.jpg)

그래서 우리는 확률 분포가 아마 Gaussian distribution이라고 생각할 것이다. 따라서, 임의의 Gaussian Distribution을 따르는 세 개의 분포를 아래와 같이 가정해보는 것이다.

![ml-em-algorithm-2](/images/ml-em-algorithm-2.jpg)

그렇다면, 우리는 이 분포에 따라 가장 적절한 label을 생성할 수 있다. 아래와 같이 생성할 수 있다.

![ml-em-algorithm-3](/images/ml-em-algorithm-3.jpg)

그러면 결과적으로 우리는 다음과 같은 label된 data를 갖게 되는 것이다.

![ml-em-algorithm-4](/images/ml-em-algorithm-4.jpg)

이렇게 labeling data를 이용해서 우리는 더 효과적인 확률 분포 변수를 찾아보면 아래와 같이 이전과는 사뭇 다른 분포를 가진다는 것을 알 수 있다.

![ml-em-algorithm-5](/images/ml-em-algorithm-5.jpg)

결과적으로 해당 분포가 이전에 임의로 추정했던 분포보다 더 적절하다는 것을 알 수 있다. 이 과정을 계속해서 반복하면 어떻게 될까?

![ml-em-algorithm-6](/images/ml-em-algorithm-6.jpg)

반복을 통해서 우리는 그럴싸한 확률분포를 습득했다. 대략 머릿속으로는 그럴 수 있을 것 같다는 생각이 들 것이다. 그렇다면, 이것이 어떻게 가능하며 수학적으로 표현이 가능할까? 이를 이제부터 자세히 알아보도록 하겠다.

## Base Knowledge

본론으로 들어가기에 앞 서 우리는 두 가지 정의를 알아야 EM Algorithm을 증명하고 설명할 수 있다.

1. Jensen’s Inequality
2. Gibb's Inequality

이 두 가지를 모두 안다면 바로 다음으로 넘어가는 것이 좋다. 하지만, 알지 못한다면 이 정의에 대해서 먼저 알아보고 가도록 하자.

### Jensen’s Inequality

일반적으로 우리는 다음 성질을 만족하는 집합을 Convex set이라고 한다.

$$
\lambda x + (1-\lambda)y \in C,\quad \forall x, y \in C \text{ and } \forall\lambda\in[0,1]
$$

즉, 집합에서 random으로 고른 두 수 사이의 수도 집합에 포함되는 집합이라는 것이다. convex set이라고 불리는 이유는 결국 이러한 집합을 2, 3 차원상에 그려보면 볼록하게 튀어나오는 형태라는 것을 알 수 있기 때문이다.

또한, 아래와 같은 조건을 만족하는 함수(f)를 Convex function이라고 한다.

$$
f(\lambda x + (1-\lambda)y) \leq \lambda f(x) + (1-\lambda)f(y),\quad \forall x,y \in C(\text{Convex set}) \text{ and } \forall\lambda \in [0,1]
$$

아래로 볼록한 함수에서는 위와 같은 과정이 너무나 당연하게도 성립한다. 사잇값의 함수값보다 함수값의 사잇값이 더 크기 때문이다.

![ml-convex-function](/images/ml-convex-function.jpg)

반대로 concave(위로 볼록) 함수인 경우에는 반대로 다음과 같이 정의된다.

$$
f(\lambda x + (1-\lambda)y) \geq \lambda f(x) + (1-\lambda)f(y),\quad \forall x,y \in C(\text{Convex set}) \text{ and } \forall\lambda \in [0,1]
$$

여기서 Jensen's Inequality는 다음과 같은 수식이 convex에서 성립한다는 것이다.

$$
E[f(X)] \geq f(E[X])
$$

convex function에서는 어찌보면 당연해보인다. 그렇지만 이는 EM Algorithm에서 토대로 사용되는 아이디어이기 때문에 반드시 기억하자. 반대로 Concave function인 경우에는 다음과 같다.

$$
E[f(X)] \leq f(E[X])
$$

### Gibb's Inequality

KL divergence 식에 Jensen's Inequality를 적용하여 KL divergence가 항상 0보다 크거나 같고, KL divergence가 0이 되기 위해서는 두 확률분포가 같아야 한다는 것을 증명한 것이다.

이에 대한 증명을 간단하게 하면 다음과 같다.

$$
\begin{align*}
KL(p||q) &= \sum_{i}{p_{i}\log\frac{p_{i}}{q_{i}}} \\
&= -\sum_{i}p_{i}\log{\frac{q_{i}}{p_{i}}} \\
&= E_{p}[-\log{\frac{q_{i}}{p_{i}}}] \geq -\log{E_{p}[\frac{q_{i}}{p_{i}}]}\, (\because \text{Jensen's Inequality}) \\
&= -\log{\sum_{i}p_{i}\frac{q_{i}}{p_{i}}} = -\log{1} = 0\\
\therefore KL(p||q) &\geq 0
\end{align*}
$$

## EM Algorithm

우리는 parametric estimation 방법을 사용하기 위해서 다음과 같은 Likelihood를 계산했다.

$$
\begin{align*}
\mathcal{L}(\theta) &= \log p(D| \theta) \\
\mathcal{L}(\theta) &= \log \prod_{x\in D} p(x| \theta) \\
&= \sum_{x\in D} \log{p(x|\theta)}
\end{align*}
$$

그렇지만 우리가 이 값을 구하는 것이 어렵다는 것을 위에서 제시했다. 따라서, 이를 다음과 같이 바꿔서 풀어보자는 것이다.

$$
\begin{align*}
\mathcal{L}(\theta) &= \sum_{x\in D} \log{p(x|\theta)} \\
&= \sum_{x\in D} \log{\int_{z \in K}p(x, z|\theta)} dz
\end{align*}
$$

이렇게 바꾸게 된다고 무슨 이득이 있을까? 단순히 식이 더 복잡해보인다. 하지만, 이 식을 다음과 같이 바꿀 수 있다.

$$
\begin{align*}
\mathcal{L}(\theta) &= \sum_{x\in D} \log{p(x|\theta)} \\
&= \sum_{x\in D} \log{\int_{z \in K} p(x, z|\theta)} dz \\
&= \sum_{x\in D} \log{\int_{z \in K} p(x, z|\theta) \frac{p(z|x, \theta^{\prime})}{p(z| x, \theta^{\prime})} dz} \\
&= \sum_{x\in D} \log{\int_{z \in K} p(z|x, \theta^{\prime}) \frac{p(x, z|\theta)}{p(z| x, \theta^{\prime})} dz} \\
&= \sum_{x\in D} \log{E_{z|x, \theta^{\prime}}{[\frac{p(x, z|\theta)}{p(z| x, \theta^{\prime})}]}} \geq \sum_{x\in D} E_{z|x, \theta^{\prime}}{[\log{\frac{p(x, z|\theta)}{p(z| x, \theta^{\prime})}}]}\,(\because \text{Jensen's Inequality}) = \mathcal{F}(p_{z|x, \theta^{\prime}}, \theta)
\end{align*}
$$

이를 통해서 우리는 아래와 같은 과정을 수행해볼 수 있다.

$$
\begin{align*}
\mathcal{L}(\theta) - \mathcal{F}(p_{z|x, \theta^{\prime}}, \theta) &= \sum_{x\in D} \log{p(x|\theta)} - \sum_{x\in D}\{\int_{z|x, \theta^{\prime}}{p(z|x,\theta^{\prime})\log{\frac{p(x, z|\theta)}{p(z| x, \theta^{\prime})}}}\} \\
&= \sum_{x\in D} \log{p(x|\theta)} - \sum_{x\in D}\{\int_{z|x, \theta^{\prime}}{p(z|x,\theta^{\prime})\log{\frac{p(z|x, \theta)p(x|\theta)}{p(z| x, \theta^{\prime})}}}\} \\
&= \sum_{x\in D} \log{p(x|\theta)} - \sum_{x\in D}\{\int_{z|x, \theta^{\prime}}{p(z|x,\theta^{\prime})\log{p(x|\theta)}} + \int_{z|x, \theta^{\prime}}{p(z|x,\theta^{\prime})\log{\frac{p(z|x, \theta)}{p(z| x, \theta^{\prime})}}}\} \\
&= \sum_{x\in D}\{\int_{z|x, \theta^{\prime}}{p(z|x,\theta^{\prime})\log{\frac{p(z|x, \theta^{\prime})}{p(z| x, \theta)}}}\} \\
&= \sum_{x\in D}{KL(p_{z|x, \theta^{\prime}}, p_{z|x, \theta})}
\end{align*}
$$

우리가 원하는 것은 결국 해당 값의 minization이다. 따라서, 우리는 모든 $x$에 대해서 KL-divergence의 최솟값을 구해야 한다(모든 사건은 독립이기 때문이다). KL-divergence는 0과 같거나 큰 수이고, KL-divergence는 $p_{z|x, \theta^{\prime}} = p_{z|x, \theta}$일 때, 0이므로 이를 만족할 수 있는 값을 찾는 것이 중요하다.

따라서, 우리는 다음과 같은 insight를 얻을 수 있다.

1. $\mathcal{F}(p_{z|x, \theta^{(t-1)}}, \theta^{(t)}) \leq \mathcal{L}(\theta^{(t)})$ 아래 식에 의해서 이를 증명할 수 있다.  
   $\mathcal{F}(p_{z|x, \theta}, \theta^{(t)}) \leq \mathcal{L}(\theta^{(t)}) (\because \text{Jensen's Inequality})$
2. $\mathcal{L}(\theta^{(t)}) = \mathcal{F}(p_{z|x, \theta^{(t)}}, \theta^{(t)})$ 바로 위에서 살펴보았 듯이 $p_{z|x, \theta^{\prime}} = p_{z|x, \theta}$일 때, 등식이 성립한다. (Gibb's Inequality)
3. $\mathcal{F}(p_{z|x, \theta^{(t)}}, \theta^{(t)}) \leq \mathcal{F}(p_{z|x, \theta^{(t)}}, \theta^{(t+1)})$  
   여기서 $\theta^{(t+1)}$은 다음과 같이 구할 수 있다.  
   $\theta^{(t+1)} = \argmax_{\theta}{\mathcal{F}(p_{z|x, \theta^{(t)}}, \theta)}$
4. $\mathcal{F}(p_{z|x, \theta^{(t)}}, \theta^{(t+1)}) \leq \mathcal{L}(\theta^{(t+1)})$  
   이는 1번과 동일한 식이다.
5. $\mathcal{L}(\theta^{(t)}) \leq \mathcal{L}(\theta^{(t+1)})$

결론적으로, 5번에 의해서 우리는 매단계가 이전보다 같거나 크다는 것을 알 수 있다. 또한, 각 단계를 차례대로 설명한다면 다음과 같다.

1. 이전 확률과 현재 parameter의 추정치를 이용해서 구한 $\mathcal{F}(p_{z|x, \theta^{(t-1)}}, \theta^{(t)})$는 $\theta^{(t)}) \leq \mathcal{L}(\theta^{(t)})$보다 작다는 것을 Jensen's Inequality에 의해서 알 수 있다.
2. 우리는 이제 $\mathcal{F}(p_{z|x, \theta}, \theta^{(t)})$를 최대화하기 위해서 $p_{z|x, \theta}$를 $p_{z|x, \theta^{(t)}}$로 업데이트 한다. 그렇다면, 이 결과는 앞 서 보았듯이 이 값은 $\mathcal{L}(\theta^{(t)})$와 동일한 결과를 갖는다.
3. 여기서 우리가 얻은 $ \mathcal{F}(p_{z|x, \theta^{(t)}}, \theta)$를 최대화할 수 있는 $\theta^{(t+1)}$를 구한다면, 이는 당연하게도 $\mathcal{F}(p_{z|x, \theta^{(t)}}, \theta^{(t)})$ 보다 크다.
4. 이렇게 얻은 새로운 parameter에 의한 결과는 역시 당연하게도 1번과 같은 결론에 도달하게 된다.
5. 결국 우리는 1~4번 까지의 과정을 거치면서 $\mathcal{L}(\theta)$를 계속해서 증가시킬 수 있다.

결국 우리가 해야할 것은 다음값을 매차시마다 구하는 것이다.

$$
\theta^{(t+1)} = \argmax_{\theta}{\mathcal{F}(p_{z|x, \theta^{(t)}}, \theta)}
$$

이를 위해서 먼저 우리는 $\mathcal{F}(p_{z|x, \theta^{(t)}}, \theta)$의 식을 좀 더 정리해볼 것이다.

$$
\begin{align*}
\mathcal{F}(p_{z|x, \theta^{\prime}}, \theta) &= \sum_{x\in D} E_{z|x, \theta^{\prime}}{[\log{\frac{p(x, z|\theta)}{p(z| x, \theta^{\prime})}}]} \\
&= \sum_{x\in D}\{\int_{z|x, \theta^{\prime}}{p(z|x,\theta^{\prime})\log{\frac{p(x, z|\theta)}{p(z| x, \theta^{\prime})}}}\}\\
&= \sum_{x\in D}\{\int_{z|x, \theta^{\prime}}{p(z|x,\theta^{\prime})\log{p(x, z|\theta)}} + \int_{z|x, \theta^{\prime}}{p(z|x, \theta^{\prime})}{\log{\frac{1}{p(z|x, \theta^{\prime})}}}\} \\
&= \sum_{x\in D}\{\int_{z|x, \theta^{\prime}}{p(z|x,\theta^{\prime})\log{p(x, z|\theta)}} + H(p_{z|x,\theta^{\prime}})\}
\end{align*}
$$

위 식에서 우리는 $\argmax_{\theta}{\mathcal{F}(p_{z|x, \theta^{(t)}}, \theta)}$를 구하기 위한 과정에서 $H(p_{z|x,\theta^{\prime}})$는 필요없다는 것을 알 수 있다.

$$
\begin{align*}
\mathcal{Q}(\theta; \theta^{\prime}) &= \mathcal{F}(p_{z|x, \theta^{(t)}}, \theta) - H(p_{z|x,\theta^{\prime}}) \\
&= \sum_{x\in D}\{\int_{z|x, \theta^{\prime}}{p(z|x,\theta^{\prime})\log{p(x, z|\theta)}}\} \\
&= \sum_{x\in D}\{ E_{z|x, \theta^{\prime}}[\log{p(x, z|\theta)}] \}
\end{align*}
$$

그 결과 우리는 다음과 같은 결론을 내릴 수 있다.

$$
\begin{align*}
\theta^{(t+1)} &= \argmax_{\theta} \mathcal{Q}(\theta; \theta^{(t)}) \\
&= \argmax_{\theta} \sum_{x\in D}\{ E_{z|x, \theta^{(t)}}[\log{p(x, z|\theta)}] \}
\end{align*}
$$

따라서, 우리는 이를 효과적으로 구하기 위해서 EM Algorithm을 다음과 같이 정의하고, 단계에 따라 수행한다.

1. Expectation Step  
   앞에서 제시한 $\mathcal{Q}(\theta; \theta^{(t)})$의 식을 구하는 단계이다. 즉, 변수를 $\theta$ 외에는 모두 없애는 단계이다. Expectation 단계라고 부르는 이유는 $\mathcal{Q}(\theta; \theta^{(t)})$가 $\sum_{x\in D}\{ E_{z|x, \theta^{\prime}}[\log{p(x, z|\theta)}] \}$와 같이 Expectation의 합의 형태로 표현되기 때문이다.  
   이를 좀 더 쉽게 표현하자면 다음과 같이 말할 수도 있다. 이전 parameter $\theta^{(t)}$가 주어졌을 때, 각 데이터에 대한 latent variable $z$의 확률을 구하는 것이다. 즉, $p(z|x, \theta^{(t)})$를 구하는 것이다.
2. Maximization Step  
   이제 앞 서 구한 $\mathcal{Q}(\theta; \theta^{(t)})$를 $\theta$에 대해 최대화하여, $\theta^{(t+1)}$를 구하는 단계이다.

이것이 EM Algorithm의 본질이다.

그래서 앞 선 Clustering에서 살펴보았던 것처럼 EM Algorithm을 다음과 같이 정의할 수도 있는 것이다.

1. 초기 parameter $\theta^{(0)}$를 설정한다.  
2. 이를 기반으로 data가 해당 분포에서 $z$일 확률을 구한다.
3. 구한 확률을 바탕으로 해당 확률과 data를 잘 표현할 수 있는 새로운 parameter $\theta^{(t+1)}$를 구한다.
4. 2, 3번 과정을 parameter가 일정 수준에 수렴할 때까지 반복한다.

## Reference

- Tumbnail : Photo by [Markus Winkler](https://unsplash.com/@markuswinkler?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText) on [Unsplash](https://unsplash.com/@markuswinkler?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText)


[ML] 10. EM Algorithm

## Intro

이전까지의 Posting에서는 Supervised Learning 즉, 이미 Labeling이 완료된 데이터에 의한 Learning을 중점적으로 다루었다. 지금부터는 Unsupervised Learning에 대해서 조금 더 살펴보도록 하겠다. 대표적인 Unsupervised Learning은 Clustering, Feature Selection(or Dimensionality Reduction), Generative Model 등이 존재한다. 이들에 대해서 차근차근 살펴보도록 하고, 해당 Posting에서는 가장 대표적이라고 할 수 있는 Clustering을 먼저 살펴보면서 Unsupervised Learning에 대한 계략적인 이해를 해보도록 하겠다.

## Clustering

Clustering은 unlabeled data를 data간 유사성 또는 거리 지표 등을 활용하여 미리 지정한 수 만큼의 partitioning하는 작업을 의미한다. 즉, 우리가 학습을 진행함에 있어 data는 label이 존재하지 않기 때문에 우리는 data간의 관계에서 정보를 추출해서 이를 분류해내는 것이 목표인 것이다.

이를 수행하기 위한 방법은 크게 두 가지로 나눌 수 있다.

1. **Non-Parametric Approach** 
 이름 그대로 확률적 분포를 가정한 후, Parameter를 찾아가는 방식이 아닌 직관적인 방법(Huristic Approach)을 활용하는 방법이다. 그렇기에 확률적인 해석이 뒷받침되기 보다는 Algorithm을 통해서 이를 설명한다. 대표적인 방법이 K-Means Clustering이다.
2. **Parametric Approach** 
 확률적 분포를 가정한 후, Parameter를 찾아가는 방식으로, 대표적인 방법이 Gaussian 분포를 가정하고 찾아나가는 Gaussian Mixture Model(GMM, or MoG, Mixture of Gaussian)이 있다.

따라서, Clustering을 대표하는 K-means Clustering과 GMM을 각 각 살펴보도록 하겠다.

### K-Means Clustering

K-Means Clustering은 K개의 평균값을 통한 Clustering으로 해석하면 의미 파악이 쉽다. 즉, K개의 Partition을 만들기 위해서 K개의 평균값을 찾아 이를 기반으로 더 가까운 평균값에 속하는 Partition에 data를 분배하는 방식이다.

그렇다면, 우리가 구해야할 값은 각 data가 어느 Partition에 속하는지에 대한 정보($\bold{r}\leftarrow\text{one hot vector}$)와 각 Partition의 평균값($\mu$)이다. 즉, K-means Clustering에서는 기존 data들을 통해서 K개의 평균값(K-means)을 찾아서(**Learning**) 이후에 추가로 들어올 data에 대해서도 똑값은 K-means를 통해서 Partition을 찾을 수 있다(**Inference**).또는 모든 data를 저장해두었다가 K-means를 다시 계산하는 방법도 있다(Online K-means).

그렇다면, $\boldsymbol{\mu}(=\{\mu_{1}, \mu_{2}, \cdots, \mu_{K}\})$와 $\bold{R}$(모든 data의 $\bold{r}$로 이루어진 Matrix)을 어떻게 구할 수 있을까? 이에 대한 해답은 다음과 같은 Cost Function을 제시하는 것으로 해결할 수 있다.

$$
\mathcal{L} = \min_{\boldsymbol{\mu}}\min_{\bold{R}} \sum_{i \in \{1,2, \cdots, N\}}\sum_{k \in \{1, 2, \cdots, K\}}\bold{R}_{ik}||x_{i} - \mu_{k}||^{2}
$$

현재 data의 point로 부터 가장 가까운 평균을 선택하는 경우를 최대화해야 해당 값이 가장 작아질 수 있다는 것을 알 수 있다. 즉, 여기서는 평균과의 거리를 유사성의 지표로 사용한 것이다. 여기서는 Euclidean distance(L2-norm)를 사용했지만, Manhatan distance(L1-norm)을 활용할 수도 있고 아예 다른 지표를 활용할 수도 있다. 중요한 것은 Cost Function이 아래와 같은 form을 가진다는 것이다.

$$
\mathcal{L} = \min_{\boldsymbol{\mu}}\min_{\bold{R}} \sum_{i \in \{1,2, \cdots, N\}}\sum_{k \in \{1, 2, \cdots, K\}}\bold{R}_{ik}\times(\text{Similarity measure})
$$

그렇다면, 실제로 위에서 제시한 Cost Function을 활용하여 어떻게 $\boldsymbol{\mu}$와 $\bold{R}$을 구할 수 있을까? minimize하고자하는 요소가 두 개이기 때문에 미분을 하기도 다소 난해하다. 따라서, 여기서는 EM Algorithm이라는 방식을 제시한다. 이에 대해서는 다음 Posting에 대해서 자세히 다루겠지만, 간단히 설명하자면 하나의 Variable을 Random하게 지정하고, 다른 Variable의 최적값을 구한 후 이를 다시 대입하고 반대 Variable을 최적값으로 구하기를 반복하면서 더 이상 Variable이 유의미하게 변경되지 않을 때까지 반복해서 구한 값이 최적값과 근사한다는 점을 활용한 Algorithm이다. 지금은 다소 엉뚱할 수 있지만, 지금은 해당 방법을 사용하도록 하겠다. 증명이 궁금하다면, 해당 Posting([🔗 [ML] 10. EM Algorithm](/posts/ml-em-algorithm))을 참고하자.

따라서, 우리가 수행할 과정은 다음과 같다.

1. $\boldsymbol{\mu}$를 랜덤하게 초기화한다.
2. Assignment step: $\boldsymbol{\mu}$가 주어졌을 때, $\bold{R}$을 구한다. 
 $$
 R_{ik} = \begin{cases}
 1 & \text{if}\quad k = \argmin_{k}||x_{i} - \mu_{k}||^{2} \\
 0 & \text{otherwise}
 \end{cases}
 $$
3. Update step: $\bold{R}$이 주어졌을 때, $\boldsymbol{\mu}$를 구한다. 
 우리가 분류한 $R$을 활용하여 각 k에 속하는 data의 평균을 통해서 $\boldsymbol{\mu}$를 구한다.
 $$
 \mu_{k} = \frac{\sum_{i=1}^{N}R_{ik}x_{i}}{\sum_{i=1}^{N}R_{ik}}
 $$
4. 특정값으로 $\boldsymbol{\mu}$가 수렴할 때까지 2번, 3번 과정을 반복한다.

아래는 이 과정을 그림을 통해서 표현한 것이다.

![ml-clustering-1](/images/ml-clustering-1.jpg)

K-means 방식은 위와 같은 Iteration 절차를 많이 수행하지 않아도 몇번의 수행만으로 수렴한다는 것을 관측할 수 있다. 또한, Assignment 시에는 $O(KND)$의 시간이 소모되고, Update 시에는 $O(N)$ 만큼의 시간이 소모되기 때문에 무겁지 않고, 굉장히 간단하다는 장점을 갖고 있다. 하지만, 이 방법은 Global Optimal을 찾을 것이라는 확신을 줄 수 없다. 그렇기에 초기값을 어떻게 잡느냐에 따라서 결과가 크게 변할 수도 있다. 뿐만 아니라, outlier data에 대해서도 굉장히 민감하게 반응한다는 단점이 있다. 예를 들어, 아래 사진에서 왼쪽보다 오른쪽이 더 성공적인 Clustering이라고 말할 수 있을 것이다.

![ml-clustering-2](/images/ml-clustering-2.jpg)

이를 해결하기 위한 방법으로 다음과 같은 방법들이 제시되었다.

1. **K-means++**: 초기값을 잘 설정하기 위한 방법으로, 초기값을 잘 설정하면 수렴하는 속도가 빨라지고, Global Optimal에 수렴할 가능성이 높아진다.
2. **K-mendoids**: K-means에서는 중심점을 data의 평균으로 설정했지만, K-mendoids에서는 중심점을 data의 중간값으로 설정한다. 이렇게 하면 outlier에 민감하지 않게 된다.

> **Soft K-means**

마지막으로 K-means Clustering에서 확률적인 접근을 시도한 방법 또한 소개하겠다. 앞 서 본 (Hard)K-means에서는 $\bold{R}_{ik}$를 0 또는 1로 보았다. 하지만, 이를 확률적으로 표현하는 것에 대해서 생각해 볼 수 있다. 즉, 다음과 같이 soft-max function을 활용한다면 표현이 가능할 것이다.

$$
\bold{R}_{ik} = \frac{\exp(-\beta||x_{i}-\mu_{k}||^{2})}{\sum_{l \in {1, 2, \cdots, K}} \exp(-\beta||x_{i}-\mu_{l}||^{2})}
$$

이렇게 확률적으로 표현하게 되면, 우리는 추가적인 정보를 활용할 수 있다. 대표적으로 특정 Cluster로 해당 확률이 편향되어 있을 수록 더 좋은 분류일 것이라는 사전 지식(Prior)을 활용할 수 있다. 따라서, 우리는 다음과 같이 Cost Function을 변경할 수 있다.

$$
\mathcal{L} = \min_{\boldsymbol{\mu}}\min_{\bold{R}} \sum_{i \in \{1,2, \cdots, N\}}\sum_{k \in \{1, 2, \cdots, K\}}\bold{R}_{ik}||x_{i} - \mu_{k}||^{2} - \frac{1}{\beta}\sum_{i \in \{1,2, \cdots, N\}}\sum_{k \in \{1, 2, \cdots, K\}}\bold{R}_{ik}\log\bold{R}_{ik}
$$

뒷 부분에 새로 추가된 $-\frac{1}{\beta}\sum_{i \in \{1,2, \cdots, N\}}\sum_{k \in \{1, 2, \cdots, K\}}\bold{R}_{ik}\log\bold{R}_{ik}$는 $R_{ik}$가 확률이 되었기 때문에 사실상 Entropy를 의미한다. Entropy는 균형잡힌 분포일 수록 커지고, skew된 경우에는 작아지기 때문에 적절한 지표라고 할 수 있다. $\beta$는 이러한 prior를 얼마나 사용할지에 대한 hyperparameter이다. $\beta$가 클 수록 사실상 Hard K-means와 동일한 결과를 얻게 되고, $\beta$가 작을 수록 Entropy를 더 중요시하는 결과를 얻게 된다.

### Gaussian Mixture Model

Gaussian Mixture Model, 일명 GMM은 Finite Mixture Model의 일종이다. Finite Mixture Model은 우리가 추정하고자 하는 확률 분포가 다양한 확률 분포 몇 개의 조합으로 이루어진 분포라고 가정하고, 해당 확률 분포의 Parameter를 학습(Learning) 단계에서 찾아내고, 이를 이용해서 새로운 data에 대해서 추정(Inference)하는 방식이다.

$$
p(x) = \sum_{k \in \{1, 2, \cdots, K\}}p(x, z=k) = \sum_{k \in \{1, 2, \cdots, K\}}p(x|z=k)p(z=k) = \sum_{k \in \{1, 2, \cdots, K\}}p_{k}(x)p(z=k)
$$

여기서 $z$는 관측할 수 없는 latent(hidden) variable로 data가 몇 번째 확률 분포에 속할 것인지를 의미한다. 따라서, $p(z=k)$ k번째 분포에 속할 확률이라고 볼 수 있다. 대게 이것이 어느정도로 확률 분포를 섞는지를 의미하기 때문에 mixing parameter라고도 부른다.

이에 따라 GMM은 각 $p_{k}(x)$가 Gaussian Distribution이라고 가정하는 Finite Mixture Model인 것이다.

![ml-gmm-graphical-form](/images/ml-gmm-graphical-form.jpg)

그렇다면, 우리는 다음과 같이 Graphical Model 형태로 Finite Mixture Model을 생성할 수 있다. 여기서 $\pi,\, \mu,\, \Sigma$는 Parameter를 의미한다.

- $\pi_{k} = p(z = k)$
- $\mu_{k} = E[x|z=k]$ 즉, Gaussian의 기댓값을 의미한다.
- $\Sigma_{k} = Cov[x|z=k]$ 즉, Gaussian의 분산을 의미한다.

이를 통해서 우리는 위에서 제시한 확률을 다음과 같이 재정의할 수 있다. (Joint Probability를 Bayesian Network로 푼 식이다. 모르겠다면, [🔗 [ML] 8. Graphical Model](/posts/ml-graphical-model#Graphical-Model)에서 Bayesian Network를 다시 살펴보고 오자.)

$$
\begin{align*}
p(x) &= \sum_{k \in \{1, 2, \cdots, K\}}p(x, z=k) \\
&= \sum_{k \in \{1, 2, \cdots, K\}}p(z=k| \pi_{k})p(x|z=k, \mu_{k}, \Sigma_{k}) \\
&= \sum_{k \in \{1, 2, \cdots, K\}}\pi_{k}\mathcal{N}(x|\mu_{k}, \Sigma_{k})
\end{align*}
$$

여기서 우리가 실제로 추측(Inference)을 할 때에는 $p(z|x)$가 필요하다. 이는 우리가 posterior를 활용해서 구할 수 있다.

$$
\begin{align*}
\hat{k} &=\argmax_{k}p(z=k|x) \\
&= \argmax_{k}\frac{p(x|z=k)p(z=k)}{p(x)} \\
&= \argmax_{k}p(x|z=k)p(z=k)\\
&= \argmax_{k}\pi_{k}\mathcal{N}(x|\mu_{k}, \Sigma_{k})
\end{align*}
$$

학습(Learning)을 할 때에는 결국 $\pi,\, \mu,\, \Sigma$ 이 세 개의 parameter 값을 찾는 것이 중요하다. 이것은 우리가 Parametric Estimation에서 줄기차게 했던 MLE를 이용하면 된다. 이를 위한 Likelihood는 다음과 같다.

$$
\begin{align*}
\mathcal{L}(\pi,\, \mu,\, \Sigma) &= \log{p(\mathcal{D} | \pi,\, \mu,\, \Sigma)} \\
&= \log{\prod_{i=1}^{N}{p(x_{i} | \pi,\, \mu,\, \Sigma)}} \\
&= \sum_{i=1}^{N}{\log{p(x_{i}| \pi,\, \mu,\, \Sigma)}} \\
&= \sum_{i=1}^{N}{\log{\sum_{k=1}^{K}{\pi_{k}\mathcal{N}(x_{i}|\mu_{k}, \Sigma_{k})}}}
\end{align*}
$$

하지만, 이것을 단순한 Optimization Technique으로는 풀 수 없다. 왜냐하면, 단순한 미분으로 각 parameter를 구할 수 없기 때문이다. 따라서, EM Algorithm을 이용해서 풀어야 한다. (이것은 [🔗 [ML] 10. EM Algorithm](/posts/ml-em-algorithm)에서 다룬다.)

따라서, 아래 그림과 같이 임의의 $\pi,\, \mu,\, \Sigma$를 가정한 상태에서 data에 알맞는 최적의 Cluster set을 구하고, data에 cluster가 label된 상태에서 최적의 $\pi,\, \mu,\, \Sigma$를 구하는 과정을 반복하는 것이다.

![ml-gmm-1](/images/ml-gmm-1.jpg)

그렇다면, 이를 실제로 어떻게 하는지를 알아보도록 하겠다. 하지만, 그냥 모든 Gaussian 형태를 위한 방법을 사용하면 다소 식이 복잡해지기 때문에 isotropic Gaussian(모든 방향에서 분산이 동일한 Gaussian)을 가정으로 하겠다.

또한, 다음과 같은 요소를 추가로 정의하자.

1. $z_{i} \in \{1, 2, \cdots, K\}$ : $i$번째 data가 속하는 cluster의 index 
 $z_{ik} = \begin{cases} 1 & \text{if } z_{i} = k \\ 0 & \text{otherwise} \end{cases}$
2. $\theta_{k} = (\pi_{k},\, \mu_{k},\, \Sigma_{k})$ : $k$번째 cluster를 위한 parameter의 집합 
 $\theta = (\pi,\, \mu,\, \Sigma)$ : parameter의 집합 

앞 서 말한 바와 같이 이제 우리는 $\theta$를 구하는 과정에서 $z_{i}$에 해당하는 정보도 알고 있다. 따라서, Likelihood 식도 변형되어야 한다.

$$
\begin{align*}
\mathcal{L}(\theta) &= \log{p(\mathcal{D} | \theta)} \\
&\geq \log{p(X, Z | \theta)} \\
&= \sum_{i=1}^{N}{\log{p(x_{i}, z_{i}| \theta)}} \\
&= \sum_{i=1}^{N}{\log{p(z_{i} | \theta) \times p(x_{i}| z_{i}, \theta)}} \\
&= \sum_{i=1}^{N}{\log{(\prod_{k=1}^{K}{\pi_{k}^{z_{ik}}} \times \prod_{k=1}^{K}{\mathcal{N}(x_{i}|\mu_{k}, \Sigma I)^{z_{ik}}})}} \\
&= \sum_{i=1}^{N}{\sum_{k=1}^{K}\log{({\pi_{k}}{\mathcal{N}(x_{i}|\mu_{k}, \Sigma I)})^{z_{ik}}}} \\
&= \sum_{i=1}^{N}{\sum_{k=1}^{K}z_{ik}\log{({\pi_{k}}{\mathcal{N}(x_{i}|\mu_{k}, \Sigma I)})}} \\
\end{align*}
$$

이에 따라서 우리는 EM Algorithm의 $\mathcal{Q}$를 다음과 같이 구할 수 있다.

$$
\begin{align*}
\mathcal{Q}(\theta; \theta^{\prime}) &= \sum_{i=1}^{N}E_{z_{i}|x_{i}, \theta^{\prime}}[\log p(x_{i}, z_{i} | \theta)] \\
&= \sum_{i=1}^{N}E_{z_{i}|x_{i}, \theta^{\prime}}[\sum_{k=1}^{K}z_{ik}\log{({\pi_{k}}{\mathcal{N}(x_{i}|\mu_{k}, \Sigma I)})}] (\because \text{위의 식에서 3번째 줄을 참고})\\
&= \sum_{i=1}^{N}\sum_{k=1}^{K}E_{z_{i}|x_{i}, \theta^{\prime}}[z_{ik}\log{({\pi_{k}}{\mathcal{N}(x_{i}|\mu_{k}, \Sigma I)})}] \\
&= \sum_{i=1}^{N}\sum_{k=1}^{K}E_{z_{i}|x_{i}, \theta^{\prime}}[z_{ik}\log{({\pi_{k}}{\mathcal{N}(x_{i}|\mu_{k}, \Sigma I)})}] \\
&= \sum_{i=1}^{N}\sum_{k=1}^{K}E_{z_{i}|x_{i}, \theta^{\prime}}[z_{ik}]\log{({\pi_{k}}{\mathcal{N}(x_{i}|\mu_{k}, \Sigma I)})} \\
\end{align*}
$$

따라서, 우리는 각 step을 다음과 같이 정의할 수 있다.

- **E-step** 
 $\mathcal{Q}$에서 parameter($\pi,\, \mu,\, \Sigma$)를 제외하고, 아직 미지수로 남아있는 값은 $E_{z_{i}|x_{i}, \theta^{\prime}}[z_{ik}]$이다. 즉, 이 값만 구하면 $\mathcal{Q}$를 구했다고 할 수 있다. 
 $$
 \begin{align*}
 E_{z_{i}|x_{i}, \theta^{\prime}}[z_{ik}] &= \sum_{k=1}^{K}{z_{ik}p(z_{i} = k | x_{i}, \theta^{\prime})} \\
 &= p(z_{i} = k^{*} | x_{i}, \theta^{\prime}) = r_{ik^{*}}
 \end{align*}
 $$ 
 결국 우리가 해당 단계에서 구할 것은 관측 가능한 data와 이전 parameter가 주어졌을 때, 속하게 되는 cluster에서의 확률을 구하는 것이다. 이것을 모든 data에 대해서 구하면, $\mathcal{Q}$에서 parameter를 제외한 모든 부분을 구할 수 있다. 따라서, 식을 좀 더 정리하면 다음과 같은 결론을 얻을 수 있다.
 $$
 \begin{align*}
 E_{z_{i}|x_{i}, \theta^{\prime}}[z_{ik}] = r_{ik^{*}} &= \frac{p(x_{i}, z_{i}=k^{*} | \theta^{\prime})}{p(x_{i}|\theta^{\prime})} \\
 &= \frac{\pi_{k^{*}}^{\prime}{\mathcal{N}(x_{i}|\mu_{k^{*}}^{\prime}, \Sigma_{k^{*}}^{\prime} I)}}{\sum_{l=1}^{K}{\pi_{l}{\mathcal{N}(x_{i}|z_{i} = l, \mu_{l}, \Sigma_{l} I)}}}
 \end{align*}
 $$ 
 
- **M-step** 
 결론적으로 우리는 다음과 같은 $\mathcal{Q}$와 constraint를 얻었다. 
 $$
 \begin{align*}
 \text{maximize}&\quad \mathcal{Q}(\theta; \theta^{\prime}) = \sum_{i=1}^{N}\sum_{k=1}^{K}r_{ik}\log{({\pi_{k}}{\mathcal{N}(x_{i}|\mu_{k}, \Sigma I)})} \\
 \text{subject to}&\quad \sum_{k=1}^{K}{\pi_{k}} = 1
 \end{align*}
 $$ 
 이제 우리는 이를 Optimization 방식을 활용하여 풀기만 하면 끝이다. ([🔗 참고(Base Knowledge)](/posts/ml-base-knowledge)) 
 $$
 \begin{align*}
 \mu_{k} &= \frac{\sum_{i=1}^{N}{r_{ik}x_{i}}}{\sum_{i=1}^{N}{r_{ik}}} \\
 \Sigma_{k} &= \frac{\sum_{i=1}^{N}{r_{ik}||x_{i} - \mu_{k}||^{2}}}{\sum_{i=1}^{N}{r_{ik}}} \\
 \pi_{k} &= \frac{1}{N}\sum_{i=1}^{N}{r_{ik}}
 \end{align*}
 $$

---

마지막으로 짚고 넘어갈 것은, 바로 K-means Clustering은 사실 GMM의 하나의 special case라는 것이다. 만약, 우리가 $\pi_{k},\, \Sigma_{k}$를 모두 같은 값으로 설정하면, $\pi_{k} = \frac{1}{K}$이고 $\Sigma_{k} = \Sigma$가 된다고 하자. 이때 EM algorithm을 살펴보면 다음과 같다.

- **E-step** 
 $$
 r_{ik} = \begin{cases} 1 & k = \argmax_{l\in \{1, 2, \cdots, K\}} p(x_{i}|z_{i} = l, \mu_{l}, \Sigma) \\ 0 & \text{otherwise} \end{cases}
 $$ 
 이는 사실상 K-means Clustering에서 중심과의 거리를 통해서 구했던 것과 매우 유사한 식이다.
- **M-step** 
 $$
 \begin{align*}
 \mu_{k} &= \frac{\sum_{i=1}^{N}{r_{ik}x_{i}}}{\sum_{i=1}^{N}{r_{ik}}} \\
 \pi_{k} &= \frac{1}{N}\sum_{i=1}^{N}{r_{ik}}
 \end{align*}
 $$ 
 $\pi_{k}$가 추가되기는 했지만, $\mu_{k}$를 구하는 식은 완전 동일하다.

## Reference

- Tumbnail : Photo by [Markus Winkler](https://unsplash.com/@markuswinkler?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText) on [Unsplash](https://unsplash.com/@markuswinkler?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText)

[ML] 9. Clustering

[ML] 8. Graphical Model

## Intro

여태까지 ML을 수행할 수 있는 여러 가지 방법론을 살펴보았다. 그렇다면, 어떤 Model을 선택하고, 학습과 추정을 해야할지 결정해야 한다. 따라서, 여기서는 어떤 것이 좋은 Model이고, 각 Model 간에 어떻게 비교를 수행할 것인지 그리고 더 나아가 Model을 혼합하는 방법에 대해서 알아볼 것이다.

## What is Good Model?

우리가 사람 image를 입력받아서 긴 머리를 가진 사람인지 여부를 판단하는 classifier를 만든다고 하자. 이때 어떤 Model이 좋은 Model이 될 수 있을까?

가장 쉽게 생각할 수 있는 Model은 Fully Connected Neural Network(FCNN)를 구성하는 것이다. 이를 위해서 Image의 각 pixel을 일렬로 줄 세워 입력할 수 밖에 없다. 하지만, 이는 pixel들 간의 인접 관계를 사용할 수 없게 한다는 단점 때문에 높은 성능을 내기가 어려웠다. 따라서, 이를 극복하기 위헤서 제시된 방법이 Convolutional Neural Network(CNN)를 사용하는 것이다. 이는 FCNN을 적용하기 이전에 Image에 Filter를 적용하여 특정 구간을 대표하는 값을 뽑아내서 더 효율적인 학습을 하는 것을 목표로 한다.(물론 더 자세히 다루면 Pooling Layer 등 더 자세한 설명이 필요하지만, 여기서는 자세히 다루지 않는다. 해당 글을 참고하도록 하자. [🔗 CNN(Convolutional Neural Networks) 쉽게 이해하기](https://halfundecided.medium.com/%EB%94%A5%EB%9F%AC%EB%8B%9D-%EB%A8%B8%EC%8B%A0%EB%9F%AC%EB%8B%9D-cnn-convolutional-neural-networks-%EC%89%BD%EA%B2%8C-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0-836869f88375))

우리의 뇌에서도 Image를 인식하고 처리하기 위해서, color와 motion 그리고 윤곽 등을 따로 따로 처리한다고 한다. 즉, CNN은 이러한 Domain Knowledge를 활용한 훌륭한 예시 중 하나라고 할 수 있다. 즉, 여기서 말하고자 하는 바는 결국 모든 환경에서 최고의 성능을 보여줄 수 있는 Model은 없다는 것이며, Good Model은 우리가 하고자 하는 일에 따라서 Domain Knowledge를 충실하게 활용하여 최고의 성능을 낼 수 있는 Model이라고 할 수 있다.

```plaintext
 🤔 Data Augmentation
 
 Domain Knowledge를 활용하여 Model의 성능을 높일 수 있는 방법은 
 단순히 Model 자체를 바꾸는 것 뿐만 아니라 Domain Knowledge를 바탕으로 
 Data를 추가적으로 더 만들어내는 방법이 있다. 이러한 방법을 
 Data Augmentation이라고 한다.

 Image data 같은 경우에는 원본 Image를 약간 회전시키거나 확대하거나 
 Noise를 주는 등의 작업을 하여 전체 데이터의 크기를 늘릴 수 있다.

Text 같은 경우에는 동의어를 활용하여 문장 데이터의 크기를 효과적으로
늘리는 것도 가능하다.
```

![ml-data-augmentation](/images/ml-data-augmentation.png)

## Comparison between Models

여기서 만약 우리가 얻을 수 있는 Model의 종류가 다양하다면 이들을 어떻게 비교하여 하나의 Model을 선택할 수 있을까? 이 역시 중요한 문제이다.

사실 우리가 학습했던 data를 그대로 평가할 때 사용하는 것은 굉장히 불공평하다고 할 수 있다. 우리가 만들고자 하는 Model은 일반적으로 어느 상황에 두어도 그리고 안본 data일지라도 올바르게 분류하기를 원한다. 즉, 우리의 Model이 **Generalization**을 수행할 수 있기를 바란다.

이러한 Model의 **Generalization** 성능을 측정하기 위해서 자주 사용되는 것이 Dataset을 Train과 Test set으로 나누는 것이다. 하지만, 이것도 부족할 때가 있다. 특정 Model이 특정 Train set에서만 성능이 높을 수도 있기 때문이다. 따라서, 우리는 **Cross Validation**이라는 방식을 도입한다. 이는 우리가 가진 dataset을 골고루 test와 train set으로 활용하는 방법이다. 즉, 여러 번의 training을 수행하며, test를 수행하기를 반복하는 것이다. 그리고, 이를 평균을 내서 전체적인 Model 성능을 평가하는 방법이다.

![ml-k-fold-cross-validation](/images/ml-k-fold-cross-validation.png)

위와 같이 공평하게 k개로 나누는 방식을 k fold cross validation이라고 하며, 해당 예시는 $k=4$인 경우이다. 즉, 위와 같이 Validation을 하기 위해서는 Model의 수가 $N$개라고 할 때, 총 $N \times k$번의 Training과 Evaluation이 필요하다.

하지만, 여기서 또 간과한 사실은 hyperparameter가 각 model마다 큰 영향을 미친다는 사실이다. 즉, Hyper Parameter를 정하는 과정 역시 필요한데, 이는 각 각의 Model 내부에서 어떤 Hyper Parameter를 사용할지에 대한 합의가 필요한 것이다. 이를 확인하기 위해서 어쩔 수 없이 우리는 Training과 Evaluation을 수행해야 하며, 이를 위한 data를 별도로 분리해야 한다. 따라서, 우리가 가지는 dataset을 다음과 같이 세개로 나누어야 한다는 것이다.

![ml-dataset](/images/ml-dataset.png)

여기서 더 정당하게 하고 싶다면, 아래와 같은 과정을 반복해야 한다.

![ml-nested-cross-validation](/images/ml-nested-cross-validation.png)

하지만, 이는 굉장히 비용이 커질 수 있다. validation set을 고를 때, $k^{\prime}$개가 필요하다고 한다면, 우리는 $N \times k^{\prime} \times k$번의 Training과 Evaluation이 필요한 것이다. 굉장히 비용이 커지기 때문에 대게 validation set까지 cross validation하는 nested cross validation은 상황에 따라 사용되기도 하고, 사용되지 않기도 한다.

## Combining Simple Models

좋은 Model을 만들 수 있는 방법 중에서 가장 쉽게 생각할 수 있는 것 중에 하나가 여러 개의 Model을 활용하는 방법이다. 쉽게 집단 지성을 활용한다고 볼 수 있다. 이러한 방식을 **Ensemble**(앙상블)이라고 부르고, 이를 활용할 수 있는 방법은 여러 가지가 있다.

1. 서로 다른 여러 개의 Model, 또는 Hyperparameter만을 변경하거나 또는 feature를 다르게 변형하여 Model을 여러 개 생성하고 평균 또는 최댓값을 취하는 방법 (**Voting**)
2. 여러 개의 Model을 혼합하지만, 각 단계에 따라서 Model을 선택하는 방법 (**Stacking**)
3. dataset을 여러 번 sampling하여 각 각의 Model을 만들고, 각 Model의 결과를 평균 또는 최댓값을 취하는 방법 (**Bagging**, **Pasting**)
4. 이전과는 달리 앞 서 진행한 Model의 결과를 반영하여 다음 Model에 적용하기를 반복하며, 여러 Model을 제작하고 취합하는 방법 (**Boosting**)

크게는 이렇게 3가지로 나눌 수 있다. 여기서 각각을 자세히 다루지는 않고, **Boosting** 방식 중에서도 많이 사용되는 방법 중에 하나인 **AdaBoost**에 대해서 좀 더 자세히 다뤄보도록 하겠다.

### AdaBoost

Adaptive Boosting의 약자인 AdaBoost는 이름에서 볼 수 있듯이 반복적인 작업을 통해서 최종 Model의 성능을 높이는 것을 목표로 한다. 우선 Boosting 방법 자체가 동시에 Model을 학습시키는 것이 아니고, 순차적으로 학습시키면서 성능을 높이는 방법이다. 그렇다면, 우리가 이전 Model들의 학습 과정에서 다음 Model에게 넘겨줄 수 있는 특별한 정보는 무엇일까? 이는 바로 자신들이 잘못 분류한 데이터에 대한 정보이다. 자신들이 잘못 분류한 data들에게 더 높은 가중치를 부여하도록 하여 다음 Model에서는 이를 중심적으로 분류할 수 있도록 하는 방식으로 최종 Model의 성능을 높여보자는 것이 Idea이다.

그렇다면, 이것이 어떻게 가능할까? 매우 간단한 이진 분류기를 기반으로 이를 설명하도록 하겠다. 우리가 만약 특정 임계값($\theta_{t}$)보다 작으면 -1, 그렇지 않으면 1이라고 분류하는 아주 간단한 분류기(weak classifier, decision stump)를 가지고 있다고 하자.

$$
f_{t}(x) = \begin{cases} -1 & \text{if } x < \theta_{t} \\ 1 & \text{otherwise} \end{cases}
$$

이제 우리는 이 간단한 분류기 T개를 합쳐서 복잡한 분류 문제를 해결할 분류기를 제작할 것이다. 이 때, 각 분류기는 다음과 같은 가중치($\alpha_{t}$)를 가지게 된다.

$$
\begin{align*}
\text{output} = \text{sign}(F_{T}(x)) \\
F_{T}(x) = \sum_{t=1}^{T} \alpha_{t} f_{t}(x)
\end{align*}
$$

그렇다면, 우리는 위 식에서 어떻게 하면, 현명하게 $\theta_{t}, \alpha_{t}$를 결정할 수 있을까? 이에 대한 해답으로 **AdaBoost**는 이전 $F_{t-1}$에 의해 발생한 **error**에 집중한다.

우선 $F_{t}$의 Error($E(F_{t})$)를 아래와 같다고 하자.

$$
E(F_{t}) = \sum_{i=1}^{N} \exp(-y^{(i)}F_{t}(x^{(i)}))
$$

즉, 예측이 맞다면 error는 $1 \over e$, 틀리다면 $e$만큼 error가 증가한다. 
여기서 우리는 현재 학습할 Model 이전까지의 Model의 하나의 데이터에 대한 Error를 $\gamma_{t}^{(i)}$라고 정의해보자.

$$
\gamma_{t}^{(i)} = \exp(-y^{(i)}F_{t-1}(x^{(i)})),\quad \gamma_{1}^{(i)} = 1
$$

다시 한 번 $\gamma_{t}^{(i)}$의 의미를 정의하면, 간단하게 이전까지의 Model의 합으로 만든 Model이 잘 분류했다면, $e$ 그렇지 않다면, $1 \over e$가 된다.

그렇다면, 계속해서 Error 식을 정리해보자.

$$
\begin{align*}
E(F_{t}) &= \sum_{i=1}^{N}\{\exp(-y^{(i)}F_{t-1}(x^{(i)})) \times \exp(-y^{(i)}\alpha_{t}f_{t}(x^{(i)}))\} \\
&= \sum_{i=1}^{N} \gamma_{t}^{(i)} \exp(-y^{(i)}\alpha_{t}f_{t}(x^{(i)})) \\
&= \sum_{i:y^{(i)}=f_{t}(x^{(i)})}\gamma_{t}^{(i)}\exp(-\alpha_{t}) + \sum_{i:y^{(i)}\neq f_{t}(x^{(i)})}\gamma_{t}^{(i)}\exp(\alpha_{t}) \\
&= \sum_{i=1}^{N}\gamma_{t}^{(i)}\exp(-\alpha_{t}) + \sum_{i:y^{(i)}\neq f_{t}(x^{(i)})}\gamma_{t}^{(i)}(\exp(\alpha_{t})-\exp(-\alpha_{t})) \\
&= \exp(-\alpha_{t})\sum_{i=1}^{N}\gamma_{t}^{(i)} + (\exp(\alpha_{t})-\exp(-\alpha_{t}))\sum_{i:y^{(i)}\neq f_{t}(x^{(i)})}\gamma_{t}^{(i)}
\end{align*}
$$

여기서 Error를 가장 작게 할 수 있는 $\theta_{t}, \alpha_{t}$를 찾기 위한 방법은 각 각 다음과 같다.

1. 식에서 $\theta_{t}$가 바꿀 수 있는 것은 $f_{t}$밖에 없다. 즉 $\sum_{i:y^{(i)}\neq f_{t}(x^{(i)})}\gamma_{t}^{(i)}$를 조정하는 것이다. 
 즉, $\gamma_{t}^{(i)}$는 이전 분류기($F_{t-1}$)가 잘 분류했다면 $e$, 그렇지 않다면 $1 \over e$가 되는데, 이들의 합이 최소가 되도록 하는 임계값 $\theta_{t}$를 찾는 것이다. 
 즉, 기존 분류기가 잘못 분류한 data에 대해서 더 중점적으로 분류할 수 있도록 가중치를 부여하여 다시 분류한다는 것이다.
2. Error를 $\alpha_{t}$에 대한 미분을 하여, 0이 되도록 하는 $\alpha_{t}$를 찾으면 된다. 이 과정은 다음과 같다.

$$
\alpha_{t} = \frac{1}{2}\ln\frac{1-\varepsilon_{t}}{\varepsilon_{t}},\quad \varepsilon_{t} = \frac{\sum_{i:y^{(i)}\neq f_{t}(x^{(i)})}\gamma_{t}^{(i)}}{\sum_{i}^{N}\gamma_{t}^{(i)}}
$$

여기서 $\varepsilon_{t}$를 자세히 보면, 분모는 decision stump의 최대 Error이고 분자는 현재 decision stump의 Error를 의미한다. 이것이 직접적으로 $\alpha_{t}$에 영향을 미치는 것이다.

따라서 이르 조금 더 정리하자면 다음과 같다.

1. $\varepsilon_{t} \gt \frac{1}{2} \rArr \alpha_{t} \lt 0$ 
 $\varepsilon_{t} \gt \frac{1}{2}$라는 것은 사실 $f_{t}$의 성능이 선택지 두 개지 하나를 Random하게 고르는 경우의 확률 $\frac{1}{2}$보다 못하다는 것이다. 이 경우에 $\alpha_{t}$를 음수로 설정하여 적용하는 것이 반대로 확률을 적용하는 것이고, 이것이 전체 성능을 높일 수 있기에 타당하다.
2. $\varepsilon_{t} = \frac{1}{2} \rArr \alpha_{t} = 0$ 
 만약, 성능이 딱 $\frac{1}{2}$라면, 더 이상 개선의 여지가 없어진다. 즉, $\alpha_{t}$를 0으로 설정하여 적용하게 되면, $F_{t}=F_{t-1}$이 된다. 즉, 더 이상의 Model 중첩은 무의미하다는 것을 의미하므로 해당 단계에 도달하면 학습을 중단한다.
3. $0 \lt \varepsilon_{t} \lt \frac{1}{2} \rArr \alpha_{t} \gt 0$ 
 일반적인 경우로, 새롭게 만든 분류기가 기존 분류기($F_{t-1}$)를 보완할 만큼 잘 예측을 하고 있기에 $\alpha_{t}$를 양수로 설정하여 적용한다.
4. $\varepsilon_{t} \rarr 0 \rArr \alpha \rarr \infin$ 
 $\varepsilon_{t}$가 0에 가까워지면, 즉, $f_{t}$가 모든 data를 정확하게 분류한다면, 사실상 기존 분류기들은 더 이상 의미가 없다. 하나의 $decision stump$로 완벽하게 분류되는 문제였기 때문이다. 즉, $F_{t} = f_{t}$가 된다.

### Decision Tree

앞 선 **AdaBoost**에서는 Decision Stump를 다루었지만, 더 다양한 분류기를 이용해서 Decision Tree를 구성하는 것도 가능하다. 실제 Stacking 또는 Bagging 등의 작업을 할 때에는 단순한 Decision Stump의 합 같은 형태가 아니라 Tree형태로 구성되는 경우가 많다(Decision을 할 때마다 가지치기를 하며 나뉘는 형태). 그리고 실제로도 이 형태가 인간의 사고 과정도 매우 유사하다. 따라서, 대게의 경우 성능도 좋은 뿐만 아니라 직관적이기 때문에 이러한 방식을 사용해서 여러 Model을 혼합하는 경우도 있다. 이 안에서 Decision을 수행할 때 복잡한 Deep Learning을 수행할 수도 있고, 단순하게 Decision Stump를 사용할 수도 있는 것이다.

![ml-decision-tree](/images/ml-decision-tree.png)

그렇다면, 이러한 Decision Tree를 어떻게 학습하는 게 좋을지를 조금만 살펴보도록 하겠다. 가정을 하나 해보자. 우리가 분류하고자 하는 Category가 10개이고, feature가 100개이다. 이때, 어떤 Feature를 이용한 어떤 Model을 사용한 것을 우선으로 적용해야할까? 이것이 사실 가장 중요한 문제이다. 이를 해결하기 위해서 여러 알고리즘(ID3, CART, 등)이 제시되었다. 하지만, 결국 핵심은 각 각의 단계에서 데이터를 가장 적절하게 나누는 것이 중요한 것이다. 따라서, Model(f)에 대해서 **얻을 수 있는 정보의 양**(**IG**, Information Gain)이 많을 수록 좋은 Model이라고 칭하는 것이다. 이를 식으로 표현하면 다음과 같다.

$$
IG(\mathcal{D}, f) = I(\mathcal{D}) - \sum_{j=1}^{J} \frac{D_{j}}{D}I(\mathcal{D}_{j})
$$

여기서, 또 그렇다면, I는 무엇인지 궁금할 수 있다. 이는 Impurity(정보의 혼탁도)를 의미하며, 이를 표현하는 지표는 아래와 같은 것들이 있다.

1. Gini Impurity
2. Entropy
3. Classification Error

위 중에서 우리가 [🔗 ML Base Knowledge(Information Theory)](/posts/ml-base-knowledge#Information-Theory)에서 다루었던 **Entropy**에 기반한 방법이 가장 즐겨서 사용되어진다.

즉, Entropy에 기반한 설명을 하자면, 우리는 IG(정보 획득량)를 최대화하기 위한 선택을 하게 되면, 해당 결정의 Child들은 적은 Entropy를 가지게 되고 이 과정을 반복해 나가면서 최적화를 수행하는 것이다.

즉, Decision Tree를 생성할 때에는 여러 가지 feature와 Model을 적용하며 각 Model이 가지는 IG를 기반으로 하여 Tree의 Root에서부터 Model을 선택하며 내려오는 것이다.

## Cutting down a Compex Model

또한, 좋은 Model을 만들기 위해서 아이러니하게도 일부 정보를 삭제하는 것이 도움이 될 때가 있다. 대게 Deep Learning 환경에서 많이 발생하는 경우인데, **over fitting**으로 인한 문제를 해결하기 위해서 일부 edge를 제거하는 **dropout**을 수행한다. 이러한 방법은 **over fitting**을 방지할 뿐만 아니라 학습의 속도 역시 개선할 수 있기 때문에 자주 사용되어진다. 실제로 model의 성능이 증가할 수 있는지에 대해 다룬 논문이 별도로 있으니 참고할 수 있다면 해보도록 하자. 만약 시간이 된다면 이에 대해서도 다룰 수 있도록 하겠다.

- Frankle, Jonathan, and Michael Carbin. "The lottery ticket hypothesis: Finding sparse, trainable neural networks." ICRL 2019

## Reference

- Tumbnail : Photo by [Markus Winkler](https://unsplash.com/@markuswinkler?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText) on [Unsplash](https://unsplash.com/@markuswinkler?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText)
- [🔗 CNN(Convolutional Neural Networks) 쉽게 이해하기](https://halfundecided.medium.com/%EB%94%A5%EB%9F%AC%EB%8B%9D-%EB%A8%B8%EC%8B%A0%EB%9F%AC%EB%8B%9D-cnn-convolutional-neural-networks-%EC%89%BD%EA%B2%8C-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0-836869f88375)

[ML] 7. Model Selection

[NLP] 8. Language Parsing

## Intro

해당 Posting에서는 Maximum Entropy를 이용하여 최적의 parameter를 찾아나가는 Machine Learning 접근법에 기반한 NLP 방식을 제안한다. 이를 위해서 NL를 수학적인 형태로 변형하기 위한 기술 중 하나인 word2vec에 대한 설명도 같이 진행한다.

## MaxEnt Model

Maximum Entropy Model(MEM)의 약자로, 이것의 의미는 주어진 dataset을 표현할 수 있는 가장 적절한 분포는 Prior Knowledge를 만족하는 분포들 중에서 가장 높은 Entropy를 가지는 분포라는 것이다. 

이는 다음과 같은 관측에 의해서 정의된 것이다.

1. 다양한 물리현상들은 시간이 지남에 따라 Entropy를 최대화하려는 방향으로 이동하려는 경향이 있다.
2. 더 적은 수의 논리로 설명이 가능한 경우, 많은 수의 논리를 세우지 말라 (오컴의 면도날)

다소 억지같아 보이는 논리일지라도 후에 가서 살펴보면, Machine Learning의 Logistic Regression에 연결되는 것을 볼 수 있다. 우선은 이 정도 논리로 사용하겠다는 정도로 이해해보자.

따라서, 우리가 풀어야할 식은 다음과 같다.

$$
\begin{align*}
 \text{maximize} \quad & H(p) = - \sum_{i=1}^{N}p_i\log p_i &\\
 \text{subject to} \quad & p_i \geq 0, & i = 1, ..., N \\
 & \sum_{i=1}^{N}p_i = 1 &\\
 & \text{Other Prior Knowledge}
\end{align*}
$$

이를 이용해서 문제를 세 개 정도 풀어보면 감이 잡을 수 있는데 한 번 따라와보도록 하자.

### Example

> **1. 주사위 던지기**

1부터 6까지의 눈이 있는 주사위가 있다고 할 때, 주사위의 각 눈이 나올 확률을 알고 싶다고 하자. 이때 우리는 간단하게 $1\over6$이라고 말할 것이다. 이것도 Maximum Entropy에 기반한 추론 방법 중에 하나라고 할 수 있다. 다음 식을 보자.

$$
\begin{align*}
 \text{maximize} \quad & H(p) = - \sum_{i=1}^{N}p_i\log p_i &\\
 \text{subject to} \quad & p_i \geq 0, & i = 1, ..., N \\
 & \sum_{i=1}^{N}p_i = 1 &
\end{align*}
$$

정말 아무런 정보가 없을 때에는 위의 식을 Lagrangian을 쓰지 않고도 uniform distribution이라는 것을 알 수 있다. 이는 [🔗 [ML] Base Information Theory](/posts/ml-base-knowledge#Information-Theory)에서 살펴보았었다.

그렇다면, 좀 더 복잡한 경우를 고려해보자. 아래는 Duke University ECE587 수업 PPT의 예제이다.

> **2. 평균이 주어졌을 때의 추론**

우리가 만약 평균 데이터를 알고 있다면, 이를 Maximum Entropy로 어떻게 추정할 수 있는지를 살펴볼 것이다. 아래는 어느 fastfood점의 메뉴라고 하자.

| Item | Price | Calories |
| :------ | :---- | :------- |
| Burger | $1 | 1000 |
| Chicken | $2 | 600 |
| Fish | $3 | 400 |
| Tofu | $8 | 200 |

그리고 특정 학생이 이 가게에서 하루에 하나씩 먹는다고 할 때, 평균 소비 가격이 $2.5라고 하자. 그렇다면, 이 학생이 가장 많이 먹는 메뉴는 무엇일지를 추론해보는 것이다. 
즉, 이를 식으로 정리하면 다음과 같다.

$$
\begin{align*}
 \text{maximize} \quad & H(p) = - \sum_{i=1}^{N}p_i\log p_i &\\
 \text{subject to} \quad & p_i \geq 0, & i = 1, ..., N \\
 & \sum_{i=1}^{N}p_i = 1 &\\
 & E[\text{price}] = 2.5 &
\end{align*}
$$

이를 Lagrangian 방식을 이용해서 표현하면 다음과 같이 나타낼 수 있다.

$$
\mathcal{L} = - \sum_{i}^{N}p_{i}\log{p_{i}} + \lambda_{0}(\sum_{i=1}^{N}p_{i} - 1) + \lambda_{1}(\sum_{i=1}^{N}\text{price}_{i}\times{p_{i}} -2.5)
$$

위 식을 각 각의 $p_{i}$에 대해서 미분하면 다음과 같다.

$$
{\partial \mathcal{L}\over\partial p_{i}} = -\log{p_{i}} -1 + \lambda_{0} + \lambda_{1}\times\text{price}_{i}
$$

따라서, $p_{i}$는 다음과 같다.

$$
\begin{align*}
0 &= -\log{p_{i}} -1 + \lambda_{0} + \lambda_{1}\times\text{price}_{i} \\
\log{p_{i}} &= \lambda_{0} + \lambda_{1}\times\text{price}_{i} - 1 \\
p_{i} &= e^{\lambda_{0} + \lambda_{1}\times\text{price}_{i} - 1}
\end{align*}
$$

여기서 나오는 모든 식과 제한 조건을 정리하면 다음과 같다.

- $p(Burger) = e^{\lambda_{0} + \lambda_{1} - 1}$, $p(Chicken) = e^{\lambda_{0} + 2\lambda_{1} - 1}$, $p(Fish) = e^{\lambda_{0} + 3\lambda_{1} - 1}$, $p(Tofu) = e^{\lambda_{0} + 8\lambda_{1} - 1}$
- $p(Burger) + p(Chicken) + p(Fish) + p(Tofu) = 1$
- $p(Burger) + 2p(Chicken) + 3p(Fish) + 8p(Tofu) = 2.5$

위의 식을 연립해서 풀면, $\lambda_{0} = 1.2371$, $\lambda_{1}=0.2586$이고, 전체 확률은 다음과 같다.

| Item | p |
| :------ | :----- |
| Burger | 0.3546 |
| Chicken | 0.2964 |
| Fish | 0.2478 |
| Tofu | 0.1011 |

> **3. 주사위의 눈의 합**

1번에서 보았던 주사위를 n개 던져서 나온 눈의 합을 알 때, 주사위의 비율을 추정한다고 해보자.

이때 우리는 다음과 같은 변수를 정의할 수 있다.

- 주사위의 갯수 : $n$
- i개의 눈을 가진 주사위의 갯수 : $n_{i}$
- 전체 눈의 수의 합 : $n\alpha$
- 추가되는 Prior Knowledge : $\sum_{i=1}^{6}{i n_{i}} = n\alpha$

이를 Maximum Entropy를 이용해서 풀게 되면 다음과 같은 결론을 얻을 수 있다.

$$
p_{i} = {e^{\lambda_{i}}\over{\sum_{i=1}^{6}{e^{\lambda_{i}}}}}
$$

## Generalization

Maximum Entropy를 위의 식을 통해서 구하는 것도 문제는 없지만 우리는 좀 더 일반화된 식을 원한다. 따라서, 이를 표현하기 위해서 다음과 같은 상황을 고려해보는 것이다. 우리가 마지막 보았던 예시가 사실은 우리가 하고자 하는 과정을 대표하는 하나의 예시이다. 우리가 가진 사전 지식은 이전에 관측한 데이터와 이것의 class이다. 따라서, 우리는 관측 결과의 가짓수(class)가 $K$개이고, 데이터의 input과 결과를 $(X, Y)$ 쌍이 라고 할 때, 특정 input data($X_{i}$)가 class k일 확률은 다음과 같이 표현할 수 있다.

$$
p(Y_{i} = k) = {e^{w^{\top}_{k}X_{i}}\over{\sum_{k^{\prime}=1}^{K}{e^{w_{k^{\prime}}^{\top}X_{i}}}}}
$$

여기서 가장 중요한 Point가 발견된다. 바로 이 식이 **softmax** 함수라는 것이다. 즉, Maximum Entropy를 통한 classification의 의미는 사실상 multinomial logistic regression의 다른 이름일 뿐이다. (logistic regression에 대한 내용은 [🔗 [ML] 3. Logistic Regression](/posts/ml-logistic-regression)에서 다루었다.)

따라서, 여기서는 별도로 Modeling, Estimation, Smoothing 절차를 다루지 않는다. machine learning의 방법과 동일하기 때문이다.

## Features

NL의 가장 큰 특징은 data가 sparse하다는 것이다. domain마다 사용되는 언어와 빈도가 너무나 천차만별이기 때문에 sparse 현상이 필연적으로 발생한다. 이를 극복하기 위해서 대게의 data는 domain 별로 따로따로 수집하는 것이 일반적이다. 또한, data에서 올바른 feature를 추출하는 것이 굉장히 중요하다. 
이를 위해 NL에서 전통적으로 쓰던 방식은 대소문자 여부, 억양 표기, 품사, 문장구조, 뜻 등을 단어에 미리 적용하기도 하여 이를 이용하는 방법도 있다. 그런데 이러한 품사, 뜻 등을 찾아내는 과정도 Statistical Inference가 필요하다. 따라서, 앞으로 chapter에서는 품사와 문장구조 뜻을 정의하기 위한 기술들과 이를 어떻게 찾을 수 있는지를 알아볼 것이다.

또한, Word자체를 Vector로 치환하여 사용하는 Word2Vec방식에 대해서도 살펴보도록 하겠다.

## Reference

- Tumbnail : Photo by [David Ballew](https://unsplash.com/@daveballew?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText) on [Unsplash](https://unsplash.com/@daveballew?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText)
- Maximum Entropy 자료 참고, <https://www2.isye.gatech.edu/~yxie77/ece587/Lecture11.pdf>

[NLP] 7. MaxEnt

## Intro

이전까지 특정 word를 기반으로 하여 modeling을 수행하는 방법을 알아보았다. 하지만, 우리가 특정 word의 sequence를 통해서 각 word에 대한 classification을 한 번에 하고 싶은 경우는 어떻게 할까?(예를 들어, 각 단어의 품사를 지정하는 일) 일반적으로 각 단어가 특정 해당 class일 확률로 구하는 방법이 일반적일 것이다. 하지만, 문맥을 고려하여 확률을 구할 방법은 없을까? 그 방법은 바로 bigram을 이용하면 될 것이다. 그렇다면, 사실 우리가 사용하는 문맥이 단어 자체보다는 이전 class가 더 영향이 크다면, 이는 어떻게 해야할까? 이를 위한 해결책이 HMM이다. NLP 뿐만 아니라 여러 분야에서 넓게 사용되고 있지만, 여기서는 NLP 분야에서 어떻게 이를 사용하는지를 알아볼 것이다.

## Markov Model

HMM을 알아보기전에 Markov Model을 알아야 한다. 이는 특정 sequence의 확률을 추정하는 방법이다. 즉 우리에게 state sequence ($S= {s_{0}, s_{1}, ..., s_{N}}$)가 주어질 때, 각 state에서 다음 state로 전이(이동)할 확률을 이용해서 state sequence의 확률을 구하는 방법이다.

![nlp-markov-model-1](/images/nlp-markov-model-1.jpg)

위의 그림이 state 각 각에서 다음 state로 전이할 확률을 나타낸 것이라면, 우리는 아래 그림과 같은 그림으로 sequence의 확률을 추론할 수 있는 것이다.

![nlp-markov-model-2](/images/nlp-markov-model-2.jpg)

따라서, 위의 그림에서 우리가 만약 $(s_{0}, s_{1}, s_{0}, s_{2})$으로 이루어진 sequence의 확률을 얻기를 바란다면, 그 확률은 아래와 같아진다.
$$
\begin{align*}
p(s_{0}, s_{1}, s_{0}, s_{2}) &= p(s_{0}| \text{start}) \times p(s_{1}|s_{0}) \times p(s_{0}|s_{1}) \times p(s_{2}|s_{1}) \times p(end|s_{2}) \\
&= \pi_{0} \times p_{01} \times p_{10} \times p_{12} \times 1
\end{align*}
$$

이를 잘 살펴보니 bigram에서의 Likelihood를 구하는 공식과 똑같다. 즉, state 각 각을 word라고 본다면, Markov Model을 통해서 구할 수 있는 확률은 bigram의 Likelihood인 것이다.

그리고 이를 일반화하면 다음과 같다.

$$
p(seq) = \prod_{i=1}^{N}p(seq_{i}|seq_{i-1})
$$

그런데, 여기서 n이 3 이상인 ngram을 적용하고 싶다면, 각 state를 n-1 gram으로 설정하면 된다.

$$
\begin{align*}
X_{i} &= (Q_{i-1}, Q_{i}) \text{라면, }\\
P(X_{i} | X_{i-1}) &= P(Q_{i-1}, Q_{i} | Q_{i-2}, Q_{i-1}) \\
&= P(Q_{i} | Q_{i-2}, Q_{i-1})
\end{align*}
$$

따라서, trigram을 적용해보면 아래와 같다.

$$
\begin{align*}
p((start, w_{0}), (w_{0}, w_{1}), (w_{1}, w_{0}), (w_{0}, w_{2})) &= p(w_{0}| \text{start}, \text{start}) \times p(w_{1}|\text{start}, w_{0}) \times p(w_{0}|w_{0}, w_{1}) \times p(w_{2}|w_{1}, w_{0}) \times p(end|w_{0}, w_{2}) \\
&= \pi_{0} \times p_{01} \times p_{10} \times p_{12} \times 1
\end{align*}
$$

## Hidden Markov Model

Hidden Markov Model은 state를 하나 더 만든다는 것이 핵심이다. 그래서, 우리가 직접 관측하는 state(**observed state**)와 직접적으로 관측하지 않지만, 관측한 state들에 의존하는 state(**hidden state**) 총 두 개의 state를 사용한다. 일반적인 예시가 text가 입력되었을 때 우리는 각 단어를 observed state라고 한다면, 각 단어의 품사를 hidden state라고 정의할 수 있다.

![nlp-markov-model-3](/images/nlp-markov-model-3.jpg)

위의 예시는 우리가 관측하는 데이터($O$)가 3개의 state를 가지고, 이 사건에 의존적인 또 다른 사건($H$)이 3개의 state를 가지는 경우이다. 이를 이용해서 기존 Markov Model보다 복잡한 작업을 수행하는 것이 가능하다.

### Estimation

우리가 할 수 있는 작업은 크게 두 가지이다. 일반적인 Markov Model에서 할 수 있던 방식이 **Trellis** 방식이고, 또 다른 방식이 **Viterbi** 방식이다.

1. $(o_{0}, o_{1}, o_{0}, o_{2})$의 확률이 궁금할 때(**Trellis**)
2. $(o_{0}, o_{1}, o_{0}, o_{2})$가 주어질 때, 이것의 hidden state의 sequence 중 가장 유력한 sequence를 찾고자할 때(**Viterbi**)

위의 경우를 각각 풀어보도록 하자.

> **1. Trellis**

우리가 직접 관측한 데이터의 sequence 자체의 확률이 궁금할 때이다. 따라서, 이에 대한 분석은 $(o_{0}, o_{1}, o_{0}, o_{2})$의 확률을 분석해보면서 설명하겠다.

$$
\begin{align*}
p(o_{0}, o_{1}, o_{0}, o_{2}) &= p(o_{0}, o_{1}, o_{0}) \times p(o_{2} | o_{0}, o_{1}, o_{0}) \\
&= p(o_{0}, o_{1}, o_{0}) \times \{p(o_{2} | h_{0})p(h_{0} | o_{0}, o_{1}, o_{0}) + p(o_{2} | h_{1})p(h_{1} | o_{0}, o_{1}, o_{0}) + p(o_{2} | h_{2})p(h_{2} | o_{0}, o_{1}, o_{0})\} \\
&= p(o_{0}, o_{1}, o_{0}) \times \sum_{i=0}^{2}{p(o_{2} | h_{i})p(h_{i} | o_{0}, o_{1}, o_{0}) } \\
&= p(o_{0}, o_{1}) \times \sum_{i=0}^{2}{p(o_{0} | h_{i})p(h_{i} | o_{0}, o_{1}) } \times \sum_{i=0}^{2}{p(o_{2} | h_{i})p(h_{i} | o_{0}, o_{1}, o_{0}) } \\
&= p(o_{0}) \times \sum_{i=0}^{2}{p(o_{1} | h_{i})p(h_{i} | o_{0}) } \times \sum_{i=0}^{2}{p(o_{0} | h_{i})p(h_{i} | o_{0}, o_{1}) } \times \sum_{i=0}^{2}{p(o_{2} | h_{i})p(h_{i} | o_{0}, o_{1}, o_{0}) } \\
&= \sum_{i=0}^{2}p(o_{0}|h_{i})p(h_{i}|start) \times \sum_{i=0}^{2}{p(o_{1} | h_{i})p(h_{i} | o_{0}) } \times \sum_{i=0}^{2}{p(o_{0} | h_{i})p(h_{i} | o_{0}, o_{1}) } \times \sum_{i=0}^{2}{p(o_{2} | h_{i})p(h_{i} | o_{0}, o_{1}, o_{0}) }
\end{align*}
$$

이를 그림으로 표현하면 다음과 같다.

![nlp-hidden-markov-model-1](/images/nlp-hidden-markov-model-1.jpg)

또한, 이 식을 다음과 같이 축소가 가능하다.

$$
\begin{align*}
 &\sum_{i=0}^{2}p(o_{0}|h_{i})p(h_{i}|start) \times \sum_{i=0}^{2}{p(o_{1} | h_{i})p(h_{i} | o_{0}) } \times \sum_{i=0}^{2}{p(o_{0} | h_{i})p(h_{i} | o_{0}, o_{1}) } \times \sum_{i=0}^{2}{p(o_{2} | h_{i})p(h_{i} | o_{0}, o_{1}, o_{0}) } \\
 =& \sum_{i=0}^{2}\alpha_{0 i} \times \sum_{i=0}^{2}{p(o_{1} | h_{i})p(h_{i} | o_{0}) } \times \sum_{i=0}^{2}{p(o_{0} | h_{i})p(h_{i} | o_{0}, o_{1}) } \times \sum_{i=0}^{2}{p(o_{2} | h_{i})p(h_{i} | o_{0}, o_{1}, o_{0}) } \\
 =& \sum_{i=0}^{2}{\alpha_{1 i} } \times \sum_{i=0}^{2}{p(o_{0} | h_{i})p(h_{i} | o_{0}, o_{1}) } \times \sum_{i=0}^{2}{p(o_{2} | h_{i})p(h_{i} | o_{0}, o_{1}, o_{0}) } \\
 =& \sum_{i=0}^{2}{\alpha_{2 i} } \times \sum_{i=0}^{2}{p(o_{2} | h_{i})p(h_{i} | o_{0}, o_{1}, o_{0}) } \\
 =& \sum_{i=0}^{2}{\alpha_{3 i} }
\end{align*}
$$

우리는 이를 통해서, Markov Model의 특징을 하나 배울 수 있다. 그것은 바로 복잡한 sequence 전체의 확률에서 벗어나서 바로 직전의 확률값만 으로 다음 확률을 추론할 수 있다는 것이다. 이것이 Markov Chain이라는 이론이고, 이를 이용했기 때문에 Markov Model라고 부르는 것이기도 하다.

따라서, $\alpha$는 다음과 같이 정의할 수 있다.

$$
\alpha(t, i) = \sum_{k=1}^{N}{\alpha(t-1, k)p(h_{i}|h_{k})p(o = s_{t}|h_{i})} \quad (s_{t} = \text{input으로 들어온 sequence의 t번째 값})
$$

또, 이를 반대로 할 경우에는 다음과 같은 식을 얻을 수 있다.

![nlp-hidden-markov-model-2](/images/nlp-hidden-markov-model-2.jpg)

$$
\begin{align*}
 &\sum_{i=0}^{2}p(o_{0}|h_{i})p(h_{i}|start) \times \sum_{i=0}^{2}{p(o_{1} | h_{i})p(h_{i} | o_{0}) } \times \sum_{i=0}^{2}{p(o_{0} | h_{i})p(h_{i} | o_{0}, o_{1}) } \times \sum_{i=0}^{2}{p(o_{2} | h_{i})p(h_{i} | o_{0}, o_{1}, o_{0}) } \\
 =& \sum_{i=0}^{2}p(o_{0}|h_{i})p(h_{i}|start) \times \sum_{i=0}^{2}{p(o_{1} | h_{i})p(h_{i} | o_{0}) } \times \sum_{i=0}^{2}{p(o_{0} | h_{i})p(h_{i} | o_{0}, o_{1}) } \times \sum_{i=0}^{2}{\beta_{3i}} \\
 =& \sum_{i=0}^{2}p(o_{0}|h_{i})p(h_{i}|start) \times \sum_{i=0}^{2}{p(o_{1} | h_{i})p(h_{i} | o_{0}) } \times \sum_{i=0}^{2}{\beta_{2i}} \\
 =& \sum_{i=0}^{2}p(o_{0}|h_{i})p(h_{i}|start) \times \sum_{i=0}^{2}{\beta_{1i}} \\
 =& \sum_{i=0}^{2}{\beta_{0i}} \\
\end{align*}
$$

$$
\beta(t, i) = \sum_{k=1}^{N}{\beta(t+1, k)p(h_{k}|h_{i})p(o = s_{t}|h_{i})} \quad (s_{t} = \text{input으로 들어온 sequence의 t번째 값})
$$

위의 처럼 앞에서부터 풀이를 해나가면서, $\alpha$의 합으로 끝이 나도록 푸는 방법을 forwarding 방식이라하고, 반대로 뒤에서부터 풀이하면서 $\beta$의 합으로 푸는 방법을 backwarding 방식이라고 한다. 사실 이 경우는 HMM이 굳이 아니더라도, MM으로 구할 수 있으니 굳이 필요는 없다. 하지만, 이것은 후에 modeling 단계에서 사용하기 때문에 알아두어야 한다.

> **2. Viterbi**

이는 observed state의 sequence에 의해서 파생되는 가장 적절한 hidden sequence를 구하는 것이 목표이다. 이를 통해서 할 수 있는 대표적인 것이 sequence classification이다.

그렇다면 가장 유력한 hidden state의 sequence를 $\hat{s}^{(H)}$라고 하자. 이는 다음과 같다.

$$
\begin{align*}
\hat{s}^{(H)} &= \argmax_{s^{(H)} \in S^{(H)}}P(s^{(H)}|s^{(O)}) \\
&= \argmax_{s^{(H)} \in S^{(H)}}P(s^{(O)}|s^{(H)})P(s^{(H)}) \\
&= \argmax_{{h_{1}, h_{2}, ..., h_{N}} \in S^{(H)}}\underbrace{P(o_{1}, o_{2}, ... , o_{N}|h_{1}, h_{2}, ... , h_{N})}_{\text{Markov Model}}\underbrace{P(h_{1}, h_{2}, ... , h_{N})}_{\text{Markov Model}} \\
&= \argmax_{{h_{1}, h_{2}, ..., h_{N}} \in S^{(H)}}\prod_{i=1}^{N}p(o_{i}|h_{i})p(h_{i}|h_{i-1})
\end{align*}
$$

![nlp-hidden-markov-model-3](/images/nlp-hidden-markov-model-3.jpg)

즉, 각 layer에서 단 하나의 가장 큰 output만 살아남을 수 있게 되는 것이다. 이 과정이 사실상 HMM의 본질적인 목표이다. sequence를 입력해서 sequence 형태의 classification 결과를 얻는 것이다.

### Modeling

여태까지 HMM을 활용하여 sequential class를 어떻게 estimation 하는지 알아보았다. 그렇다면, 이제는 이를 위해서 사용되는 확률값을 구해야한다. 필요한 확률값은 다음과 같다.

- $p(h_{i}|h_{i-1})$ : Hidden State에서 Hidden State로 넘어가기 위한 확률이다.
- $p(o_{i}|h_{i})$ : 방출 확률로 특정 Hidden State에서 다음 State의 Observed State로 넘어가는 방법이다.
- $\pi_{i}$

Trelli 방식에서 만들었던, $\alpha$와 $\beta$의 의미를 이해해야 한다. 각 각은 해당 과정까지 오면서 누적해온 확률이라고 할 수 있다. 그리고, 우리가 원하는 것은 입력으로 주어진 데이터를 잘 반영할 수 있는 확률 값을 찾는 것이다. 그렇다면, 우리가 생각할 수 있는 방법은 평균을 활용하는 것이다. 이를 구하는 과정을 먼저 살펴보자.

$$
\begin{align*}
 c(i, j, k) &= h_{i}\text{에서 } h_{j}\text{로 넘어가고, } o_{k}\text{가 관측될 확률의 합} \\
 &= \sum_{t=2}^{T} \alpha(t-1, i)p(h_{j}|h_{i})p(o_{k}|h_{j}) \beta(t, j) \\
 \\
 c(i,j) &= h_{i}\text{에서 } h_{j}\text{로 넘어갈 확률의 합} \\
 &= \sum_{k=1}^{K}\sum_{t=2}^{T}{\alpha(t-1, i)p(h_{j}|h_{i})p(o_{k}|h_{j}) \beta(t, j)} \\
 \\
 c(i) &= h_{i}\text{에서 상태를 변경하는 확률의 합} \\
 &= \sum_{j=1}^{N}\sum_{k=1}^{K}\sum_{t=2}^{T}{\alpha(t-1, i)p(h_{j}|h_{i})p(o_{k}|h_{j}) \beta(t, j)} \\
\end{align*}
$$

위의 값을 통해서 우리는 우리가 가지고 있던 확률을 업데이트할 수 있다.

$$
\begin{align*}
p(h_{j}|h_{i}) &= {c(i,j)\over c(i)} \\
p(o_{k}|h_{i}) &= {c(i,j,k)\over c(i,j)}
\end{align*}
$$

즉, 우리는 다음 과정을 수행하여 Modeling을 수행할 수 있는 것이다.

1. 초기값 ($p(h_{i}|h_{i-1})$, $p(o_{i}|h_{i})$, $\pi_{i}$)을 초기화 한다. 
2. Trelli를 통해서 $\alpha$, $\beta$를 계산한다.
3. $p(h_{i}|h_{i-1})$, $p(o_{i}|h_{i})$를 업데이트 한다. 
 ($pi_{i}$같은 경우는 발생 빈도로 업데이트 한다.)
4. 임계치에 도달할 때까지 2,3번을 반복한다.

이 과정을 대게 10번 정도만 하면 수렴하게 되고, 이를 확률로 사용하는 것이다.

## Reference

- Tumbnail : Photo by [David Ballew](https://unsplash.com/@daveballew?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText) on [Unsplash](https://unsplash.com/@daveballew?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText)

[NLP] 6. Hidden Markov Model

## Intro

Naive Bayes Model은 가장 쉽게 Classification을 수행할 수 있는 Model이지만, 성능이 다른 Model에 비해 뛰어나지는 않다. 그럼에도 Naive Bayes는 가장 기본이 되는 Model이기에 비교 대상으로 많이 사용되고, Classification의 insight를 키우는데 많은 도움을 줄 수 있다. 여기서는, 전반적인 개념과 이를 직접 Spam Filtering에서 어떻게 사용하는지 살펴본다.

## Naive Bayes Model

특정 class에서 해당 데이터가 얼마나 자주 발생되는지와 실제로 해당 class의 빈도를 활용하여, classification을 수행하는 것이다. 우선 이를 수식적으로 표현하기 위해서 다음 변수들을 먼저 정의해보자.

- **documents($D$)**: 여러 개의 Document를 의미하며, 하나의 Document는 대게 여러 개의 words를 포함한다. 각 document는 $d_{i} \in D$의 형태로 표현한다.
- **classes($C$)**: class는 두 개 이상을 가진다. 각 클래스는 $c_{i} \in C$의 형태로 표현된다.
- **labeled dataset**: 이는 (document($d_{i}$), class($c_{i}$))가 하나씩 mapping된 형태로 존재한다. 우리가 가지는 dataset으로 학습, 평가 시에 사용한다. 대게 평가에 사용되는 데이터는 학습 시에 사용하는 것을 금지하기 때문에 별도로 분리하여 사용한다.
- **word($w$)**: 하나의 word를 의미하며 NLP 학습 시에 사용하는 가장 작은 단위이다. 대게 document 하나에 있는 단어의 수는 N으로 표기하고, unique한 단어의 수는 V(size of vocabulary)로 표시한다.

따라서, 우리가 찾고자 하는 가장 높은 확률을 가진 class는 다음을 통해서 구할 수 있다.

$$
\begin{align*}
c_{MAP} &= \argmax_{c \in C}{P(c|d)} \\
&= \argmax_{c \in C}{p(d|c)p(c)\over p(d)} \\
&= \argmax_{c \in C}{p(d|c)p(c)} \\
&= \argmax_{c \in C}{p(w_{1}, w_{2}, ... , w_{N} | c)p(c)} \\
&= \argmax_{c \in C}{\prod_{i=1}^{N}p(w_{i}|c)p(c)} \\
&= \argmax_{c \in C}{\log(\prod_{i=1}^{N}p(w_{i}|c)p(c))} \\
&= \argmax_{c \in C}{\sum_{i=1}^{N}\log p(w_{i}|c) + \log{p(c)}} \\
\end{align*}
$$

여기서 우리가 language model을 무엇으로 정했는지가 중요하다. 위에서는 uni-gram이라고 가정해서 풀이했지만, bi-gram인 경우 document의 형태가 $d={(w_{1}, w_{2}), (w_{2}, w_{3}), ... , (w_{N-1}, w_{N})}$이다. 따라서, 전체적인 크기와 vocabulary자체도 바뀌게 된다.

즉, 우리는 train set을 통해서 vocabulary를 완성한다. 그리고, 각 word의 count 및 필요에 따라 필요한 word sequence의 count를 수집하여 $p(w_i)$를 구한 후 위에 방법을 통해서 특정 class를 추측할 수 있는 것이다.

이제 구체적인 Naive Bayes의 동작 절차는 Spam Filtering이라는 Case Study를 통해서 자세히 살펴보도록 하자.

## Case Study. Spam Filtering

초기 NLP가 가장 많이 사용되었던 예시 중에 하나이다. 여러 개의 메일에 spam인지 ham인지를 labeling한 데이터를 갖고 후에 input으로 mail 데이터가 들어왔을 때, 이를 filtering하는 것이다. 위에서 살펴보았던 확률을 그대로 적용하면 된다. 예측에 필요한 확률을 습득하고, 예측하는 방법과 이를 평가하는 방법의 순으로 설명하겠다.

### 0. Preprocessing

사실 mail data의 형태가 이상할 수도 있다. Subject부터 시작하여 날짜 데이터 그리고 특수 문자 등이 존재할 수 있는데, 이를 먼저 처리해서 후에 있을 Modeling 단계에서 잘 사용할 수 있도록 형태를 변형해주어야 한다.

[🔗 이전 Posting(Text Processing)](/posts/nlp-text-processing)에서 배웠던 기술들을 활용하여 이를 해결할 수 있다.

대표적으로 해줄 수 있는 작업들은 다음과 같다.

1. 대소문자 통일
2. alphabet이 하나라도 들어있지 않은 데이터는 삭제
3. date, 참조 등을 의미하는 데이터 삭제

### 1. Modeling

Parameter Estimation / Learning / Modeling 등으로 불리는 단계이다. 일단 우리는 train set으로부터 우리가 원하는 확률을 추출해야 한다. 그 전에 우리가 어떤 language model을 이용할지 선택해야 한다. 먼저 uni-gram인 경우에는 다음과 같은 방법으로 train set이 정의된다.
$$
\text{TrainSet} = {(d_{1}, c_{1}), (d_{2}, c_{2}), ..., (d_{N}, c_{N})}
$$
$$
d_{i} = \begin{cases}
 {w_{1}, w_{2}, ... , w_{M_{i}}} \quad&\text{unigram} \\
 {(<s>, w_{1}), (w_{1}, w_{2}), ... , (w_{M_{i}}, </s>)} \qquad&\text{bigram}
\end{cases}
$$

이제 우리가 원하는 parameter, 즉 확률은 다음과 같은 데이터이다.

> **unigram**

$$
\begin{align*}
p(w_{i}|c_{j}) &= {\text{count}(w_{i}, c_{j}) \over \sum_{w \in V} \text{count}(w, c_{j})} \\
p(c_{j}) &= {\sum_{i = 1}^{N}{1[c_{i} = c_{j}]} \over N}
\end{align*}
$$

> **bigram**

$$
\begin{align*}
p(w_{i}|w_{i-1},c_{j}) &= {\text{count}((w_{i-1}, w_{i}), c_{j}) \over \sum_{(w^{(1)}, w^{(2)}) \in V} \text{count}((w^{(1)}, w^{(2)}), c_{j})} \\
p(c_{j}) &= {\sum_{i = 1}^{N}{1[c_{i} = c_{j}]} \over N}
\end{align*}
$$

여기서 우리는 반드시 Smoothing을 해주어야 한다. 왜냐하면, spam mail에서 안 본 단어가 나올 가능성이 너무나 높기 때문이다. 따라서, 실제 $p(w_{i}|c_{j})$는 아래와 같이 변경된다. (간단한 예시를 들기 위해서 Add-1 방식을 사용했다. - 해당 내용이 기억이 나지 않는다면, [🔗 이전 포스팅](/posts/nlp-language-modeling)을 다시 보고 오자.)

$$
p(w_{i}|c_{j}) = {\text{count}(w_{i}, c_{j}) + 1 \over \sum_{w \in V} \text{count}(w, c_{j}) + |V|}
$$

주의할 점은 다시 한 번 강조하지만, $V$는 후에 Estimation에서 input으로 사용하는 단일 document까지 포함한 Vocabulary이다.

### 2. Estimation

이제 우리가 얻은 parameter를 이용해서 실제 input data에 대한 estimation을 수행할 수 있다.

이 경우 다음과 같은 과정을 수행할 수 있다.

$$
\hat{c} = \argmax_{c \in C} p(c)\prod_{w \in d_{\text{input}}}p(w|c)
$$

물론 어떤 n-gram을 쓰냐에 따라 $d_{\text{input}}$도 형태가 달라질 것이다.

### 3. Evaluation

이제 평가를 수행할 것이다. 평가는 우리가 알아봤던 Accuracy와 F1 Score를 추출할 수 있다. Binary Classification이기 때문에 쉽게 구할 수 있을 것이다.

| prediction\answer | True | False |
| :---------------- | :------------------------------------------------------------------------- | :------------------------------------------------------------------------ |
| Positive | $\sum_{(d, c) \in D_{\text{test}}} 1[\hat{c}_{d} = c, c = \text{spam}]$ | $\sum_{(d, c) \in D_{\text{test}}} 1[\hat{c}_{d} \neq c, c = \text{ham}]$ |
| Negative | $\sum_{(d, c) \in D_{\text{test}}} 1[\hat{c}_{d} \neq c, c = \text{spam}]$ | $\sum_{(d, c) \in D_{\text{test}}} 1[\hat{c}_{d} = c, c = \text{ham}]$ |

## Reference

- Tumbnail : Photo by [David Ballew](https://unsplash.com/@daveballew?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText) on [Unsplash](https://unsplash.com/@daveballew?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText)

[NLP] 5. Naive Bayes

## Intro

이전 Posting에서는 sentence의 적절성을 확인한다든지 다음 단어를 유추한다든지 오타를 정정하는 등에 필요한 기본적인 Language Modeling 방식을 살펴보았다. 이번에는 실제로 가장 많이 사용되는 예제인 Classification을 Language Model을 이용하여 어떻게 구현하는지를 다룬다.

## Classification

Classification은 input이 들어왔을 때, 이를 알맞은 분류로 나누는 것이 목표이다. 단순히 Rule에 기반하여 이를 수행할 수도 있지만, Statistic한 Language Modeling을 이용하면, 더 정확도가 높은 분류를 수행할 수 있다. 결국 Statistic Prediction을 수행하기 위해서 우리는 3개(Estimation, Modeling, Evaluation)를 중점적으로 봐야 하는 것은 Classification도 동일하다. 따라서, 이에 대해서 살펴볼 것이고, 그 전에 먼저 Classification Model 의 종류를 살펴보도록 하겠다.

## Generative Model vs Discriminative Model

Classification에서 이용되는 Model을 크게 두가지로 나눌 수 있는데 이에 대해서 먼저 알아보도록 하자.

1. **Generative Model(생성 Model)**
 1. Naive Bayes
 2. Hidden Markov Model(HMM)
2. **Discriminative Model(판별 Model)**
 1. Logistic Regression
 2. K Nearest Neighbors
 3. Support Vector Machine
 4. Maximum Entropy Model(MaxEnt)
 5. Neural Network(Deep Learning)

두 Model의 가장 큰 차이점은 추론의 과정이다. 우리가 원하는 데이터 $P(\text{class}=c | \text{input} = \text{data})$(특정 data가 주어졌을 때, 각 class의 속할 확률)를 얻는 과정이 서로 다르다.

**첫 번째**로, $P(\text{class}=c, \text{input} = \text{data})$일 확률을 구하여 **간접적**으로 구하는 방법이다.

$$
\begin{align*}
P(\text{class}=c | \text{input} = \text{data}) &= {{P(\text{class}=c, \text{input} = \text{data})}\over{P(\text{input} = \text{data})}} \\
&\propto {P(\text{class}=c, \text{input} = \text{data})}
\end{align*}
$$

이런 식으로 생성하여 추론하는 방식을 Generative Model이라고 한다. 이 방식은 결국 Conditional Probability를 추론하기 위해서 Joint Probability를 이용하는 방식이기 때문에 어느정도 한계가 존재한다는 점을 유의하자.

**두 번째**로는, $P(\text{class}=c | \text{input} = \text{data})$를 **직접적**으로 구하는 방법이 있다. 이를 위해서, 마친 Conditional Probability를 구한 것과 유사한 효과를 내는 **Discriminant Function(판별 함수)**이라는 특별한 함수를 input에 적용하는 방법이다. 이 함수 중에서 가장 대표적인 것이 Softmax function이다. 우리가 만약 input을 softmax function에 입력하게 되면, 이 값은 [0, 1] 사이의 값으로 표현된다. 이를 통해서 우리는 해당 input이 class인 경우 1에 가깝게, 그렇지 않은 경우 0에 가깝게 표현하여 여러 데이터에 적용하면, class의 inpuut에 따른 분포 양상을 확인할 수 있다. 그리고, 이 분포 양상을 확률로 즉각적으로 표현할 수 있기 때문에 softmax function을 취한 결과가 $P(\text{class}=c | \text{input} = \text{data})$과 비례한다는 결론을 낼 수 있다. 자세한 설명이 필요하다면, [🔗 Logistic Regression](/posts/ml-logistic-regression#Logistic-Regression)을 참고하도록 하자. 이러한 방식을 우리는 Discriminative Model이라고 한다.

위에서 제시한 방법들 중 대표적인 방법들은 별도의 Posting을 통해서 정리하였다. 해당 링크를 참조하여 확인해보도록 하자.

- **Generative Model(생성 Model)**
 - [🔗 Naive Bayes](/posts/nlp-naive-bayes)
 - [🔗 Hidden Markov Model(HMM)](/posts/nlp-hmm)
- **Discriminative Model(판별 Model)**
 - [🔗 Maximum Entropy Model(MaxEnt)](/posts/nlp-maxent)
 - [🔗 Logistic Regression](/posts/ml-logistic-regression)

## Estimation

어떤 Model을 선택했다고 하더라도 결국 우리가 Class를 결정하는 과정을 동일하다. 위의 과정을 통해서 어찌되었든 다음 값을 찾으면 된다.

$$
\begin{align*}
c^{\prime} &= \argmax_{c \in C}{P(\text{class}=c | \text{input} = \text{data})}
\end{align*}
$$

## Modeling

Model을 만드는 과정, 즉 학습하는 과정은 결국 Model의 구현마다 천차 만별이다. Naive Bayes는 단순하게 data의 word와 count를 활용하고, HMM은 EM algorithm을 활용하며, Linear Regression은 Gradient Descent를 활용한다. 따라서, 여기서는 자세히 다루지 않고 위에서 제시한 링크를 따라가서 각 Model마다의 학습법을 확인해보도록 하자.

## Evaluation

Classification의 성능을 평가하는 것 역시 중요한 일이다. 가장 쉬운 Binary Classification부터 알아보자.

binary classificaiton의 결과는 아래와 같이 4개 중 하나로 결정된다.

| prediction\answer | True | False |
| :---------------- | :------------- | :------------- |
| Positive | true positive | false positive |
| Negative | false negative | true negative |

이를 쉽게 이해할려면, 병(코로나)의 양성/음성 판정이 row에 해당하고, 실제 병의 여부를 column으로 생각하면 쉽다. 또한, 각 cell의 값이 헷갈릴 수 있는데, 우리가 원하는 것이 예측의 정확도를 확인하는 것이기 때문에 예측 결과는 그대로 보여주면서, 이것이 틀렸는지 맞았는지를 앞에 true/false로 표현했다고 생각하면 쉽다.

classification의 성능을 측정하는 지표는 대표적으로 4 가지가 있다.

1. **Accuracy(정확도)** 
 가장 쉽게 그리고 일반적으로 생각하는 지표다. 위의 표에서는 전체 경우의 수를 더하여 옳게 예측한 것(true postive, true negative)의 합을 나누는 것이다.
 $tp + fn \over tp + fp + fn + tn$ 
 하지만, 이 방식은 한계가 있다. 바로, 데이터가 한쪽으로 치우쳐져있을 때이다. 예를 들어, 우리가 진짜를 진짜라고 맞출확률은 높지만, 가짜를 가짜라고 맞출 확률이 낮다고 할 때, 이를 제대로 반영하기가 어렵다. 그런데 데이터에서 진짜가 가짜보다 압도적으로 많을 경우 정확도는 좋은 지표로 쓰기 어렵다는 것이다.
2. **Precision(정밀도, 정답률)** 
 쉽게 정답 자체를 맞힐 확률입니다. 
 $tp \over tp + fn$
3. **Recall(재현율)** 
 예측이 맞을 확률을 의미합니다. 
 $tp \over tp + fp$
4. **F1 Score** 
 좀 더 세분화된 평가지표이다. 조화 평균에 기반하여 모델의 성능을 정확하게 평가할 때 사용한다. 
 ${2\over{{1\over\text{Precision}} + {1\over\text{Recall}}}} = 2 \times {\text{Precision} \times \text{Recall} \over \text{Precision} + \text{Recall}}$

여기까지 봤으면, 슬슬 multi class의 경우에는 어떻게 해야할지 궁금할 것이다. 대게 두 가지 방법을 통해서 수행할 수 있다.

> **1. Micro Average**

전체 class를 하나의 binary table로 합치는 것이다. 즉, 클래스가 A, B, C 3개가 있다면, 각 클래스 별로 예측 성공도를 binary로 표시하고, 이를 하나의 테이블로 합치는 것이다. 그 후에는 binary에서 계산하는 식을 그대로사용할 수 있다. 

> **2. Macro Average**

multi class의 경우에도 별로 다를 것은 없다. 단지 Precision과 Recall 그리고 Accuracy가 어떻게 바뀌는지만 알면 쉽게 이해할 수 있을 것이다. 

| prediction\answer | c1 | c2 | c3 | c4 |
| :---------------- | :------------ | :------------ | :------------ | :------------ |
| c1 | true positive | x | x | x |
| c2 | x | true positive | x | x |
| c3 | x | x | true positive | x |
| c4 | x | x | x | true positive |

- Precision: $c_{ii} \over \sum_{j}c_{ij}$
- Recall: $c_{ii} \over \sum_{j}c_{ji}$
- Accuracy: $c_{ii} \over \sum_{i}\sum_{j}c_{ij}$

## Reference

- Tumbnail : Photo by [David Ballew](https://unsplash.com/@daveballew?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText) on [Unsplash](https://unsplash.com/@daveballew?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText)

[NLP] 4. Classification

[NLP] 3. Language Modeling

## Intro

우리는 Linear Regression, Logistic Regression, SVM을 거치며 data로 부터 유의미한 pattern을 발견하는 과정을 알아보았다. 이 과정은 우리에게 명확한 식 하나를 제시하였고, 모든 과정을 우리가 제어할 수 있게 하였다. 하지만, 실제 데이터를 우리가 모두 명확하게 이해할 수 있는 형태로 분류할 수 있는 것인지는 의문이 들 수 있다. 그렇다면, 우리가 이해하지는 못하지만, 알아서 최적의 결과를 가져오게 할 수 있는 방법이 있을까? 이런 마법같은 일에 대한 아이디어를 제시하는 것이 Neural Network이다.
대게 알지 못하지만 input이 들어왔을 때, 이를 처리해서 output을 전달하는 시스템을 우리의 신체에서 찾게 된다. 바로 우리 몸을 이루는 신경망이다. 예시로 우리는 눈을 통해 빛이라는 input을 받으면, 우리 눈과 뇌에서 무슨 일이 발생하는지는 모르지만 결과적으로 우리는 물체를 볼 수 있다. 이 과정을 추측의 과정에 도입하면 어떻게 될까?

## Perceptron

Perception(인지 능력) + Neuron(신경 세포)의 합성어이다. 중고등학교 생명 수업을 들었다면, 우리의 모든 신경은 뉴런이라는 단위 세포로 이루어진다는 것을 배웠을 것이다. 즉, 우리의 신경 세포를 컴퓨터 공학에서 활용하기 위해서, 수학적으로 변환한 것이다. 형태를 먼저 살펴보자.

$$
y = sign(\bold{w}^{\top}\bold{x} + b)
$$

![nn-perceptron-1](/images/nn-perceptron-1.jpg)

대단한 것을 기대했다면 실망하겠지만, simple한 것이 최고라는 연구의 진리에 따라서 위의 식은 꽤나 합리적이다. 우리가 Linear Regression과 Logistic Regression을 배웠으니 알 것이다. 이는 사실 Linear Regression을 이용해서 우리가 Classification을 수행할 때 사용했던 식이다. 즉, perceptron 하나는 input을 선형으로 구분할 수 있도록 하는 decision boundary를 찾는 것과 같다.

> **Optimization**

그렇다면, 해당 perceptron을 통해서 모든 데이터를 구분하기 위해서는 다음을 만족하는 $\bold{w}$를 찾아야 한다.

$$
y_{n} =
\begin{cases}
1 &\text{ if } \bold{x}_{n} \in \mathcal{C}_{1} \\
-1 &\text{ if } \bold{x}_{n} \in \mathcal{C}_{2} \\
\end{cases}
$$
$$
y_{n}\bold{w}^{\top}\bold{x}_{n} \gt 0, \forall n
$$

결국 Loss 함수는 perceptron의 잘못된 classification 결과를 최소화하는 것이다.

$$
\mathcal{J}(\bold{w}) = - \sum_{n \in \mathcal{M}(\bold{w})}{y_{n}\bold{w}^{\top}\bold{x}_{n}} \quad( \mathcal{M}(\bold{w}) = \{ n : y_{n}\bold{w}^{\top}\bold{x}_{n} \} )
$$
$$
\nabla_{\bold{w}}\mathcal{J}(\bold{w}) = - \sum_{n \in \mathcal{M}(\bold{w})}{y_{n}\bold{x}_{n}}
$$

따라서, 우리가 사용할 수 있는 Gradient Descent식은 다음과 같다.

$$
\bold{w}_{t+1} = \bold{w}_{t} + \alpha\sum_{n \in \mathcal{M}(\bold{w})}{y_{n}\bold{x}_{n}}
$$

간단한 예시로 AND, OR Gate를 percentron을 통해 표현해보자.

![nn-and-gate](/images/nn-and-gate.jpg)
![nn-or-gate](/images/nn-or-gate.jpg)

하지만, 우리가 다루는 데이터는 항상 완벽하게 선으로 나뉘어지지는 않는다. 하나의 perceptron으로는 아래의 XOR조차도 구분해낼 수 없다.

![nn-multi-line-example](/images/nn-multi-line-example.jpg)

## Multilayer Perceptron

위의 문제를 해결하기 위해서 나온 것이 perceptron을 다층으로 쌓아서 해결하는 방법이다. 이제는 하나의 신경세포였던 perceptron을 진짜 신경망처럼 연결해보자는 것이다.

먼저 추상적인 예시를 생각해보자. 우리가 XOR Gate를 만들기 위해서는 어떤 Gate를 결합해야할까?

$$
a \oplus b = ab + \bar{a}\bar{b}
$$

우리는 AND Gate 2개 연산을 수행하고, 해당 결과값을 이용해서 OR Gate 연산을 수행하면 XOR Gate를 표현할 수 있다는 것을 알고 있다. 그렇다면, 각 Gate는 우리가 perceptron으로 나타낼 수 있었는데 그냥 이것을 gate로 표현하듯이 똑같이 나타내면 풀 수 있지 않을까?

그래서 직접 수행해보면 다음과 같은 값을 구할 수 있다.

![nn-xor-gate](/images/nn-xor-gate.jpg)

```plaintext
 🤔 Insight

 위의 과정을 보다보면 놀라운 것을 하나 발견할 수 있다. 바로 왼 쪽 그림의 변화이다. 
 첫번째, 두 개의 perceptron을 통해서 만들어진 output이 이루는 결과값의 형태로 feature를 변환하면, 
 하나의 perceptron으로 decision boundary를 그릴 수 있다는 것이다. 
 이는 마치 이전 linear regression에서 배웠던 basis function(ϕ)이 했던 역할이다.

 그렇다면, 이를 더욱 확장해보자. 
 만약 해당 Layer가 더 깊어진다고 해도, 출력 직전의 layer는 단순히 이전 모든 layer는 입력 데이터를 가공해서
feature를 변환하는 하나의 basis function(ϕ)를 취한 것으로 이해할 수 있다.
```

결론적으로 우리는 더 복잡하고, 어려운 문제의 경우에도 더 깊게 신경망을 구성하면 결국은 문제를 풀 수 있다는 것이다.

> **Universal Approximation Theorem**

위와 같은 깊은 신경망 구조를 이용하자는 주장도 있지만, 이와 유사하게 넓은 신경망을 쓰자는 주장도 존재했다. 

![nn-universal-approx-theorem-1](/images/nn-universal-approx-theorem-1.jpg)

만약, 우리가 하나의 Layer와 output에서 최종 output perceptron만 갖고 처리를 한다면, 결국 여러 perceptron의 weighted 합으로 볼 수 있다. 그 경우 우리는 계단 함수의 weighted 합으로 생각할 수 있는데 perceptron이 많아질 수록 촘촘해지며 정답과 유사한 추론이 가능해진다.(마치 적분의 개념과 유사하다. 물론 이는 추상적인 설명이기 때문에 실제로는 계단함수의 합이기 때문에 좀 다르다.)

![nn-universal-approx-theorem-2](/images/nn-universal-approx-theorem-2.jpg)

위의 그림을 보면 이해할 수 있다. 하지만, 이 방식은 결국 모든 함수 형태를 기억하는 것이다.(**memorizer**) 이것은 input data가 많아질 수록 복잡도가 급격하게 증가하기 때문에 학습과 예측과정에 굉장히 많은 시간을 소모한다.

> **Multilayer Optimization(Backpropagation)**

그렇다면, 넓은 신경망이 한계가 있으니 선택지는 input과 output 사이의 layer(**hidden layer**)의 갯수를 늘려서 깊은 신경망을 만드는 것이다. 하지만, 우리가 사용하고 있는 perceptron은 sign함수로 감싸져있기 때문에 미분 시에 기울기가 0이라는 문제를 갖는다. 또한, 그렇다고 정답의 갯수를 이용하기에는 각 perceptron의 영향을 전달하기에 부족하다는 것이 명확하다. 따라서, 우리는 perceptron에 있는 정답을 판별하는 함수 sign을 다른 함수로 대체하기로 한다.

![nn-perceptron-2](/images/nn-perceptron-2.jpg)

여기서 이 함수를 우리는 **activation function**이라고 부르고 대표적으로는 같은 종류가 있다.

- **sigmoid** 
 우리가 가장 쉽게 생각할 수 있는 함수이다. logistic regression에서 사용해본만큼 기울기값을 효과적으로 가질 수 있다.
- **tanh** 
 sigmod와 굉장히 유사한 함수이다. 따라서, 비슷한 용도로 사용될 수 있다.
- **ReLU** 
 출력 시점에서는 사용하지 않지만, 각 각의 hidden layer에서 이를 사용하는 경우가 많다. 왜냐하면, sigmoid 함수는 출력값의 형태가 [0, 1], tanh는 [-1, 1]이기 때문에 반복해서 적용하면, gradient가 사라지는 현상이 발생할 수 있다. 따라서, 기울기를 있는 그대로 적용할 수 있는 이러한 형태를 출력 이전에는 많이 사용한다.
- **Leaky ReLU** 
 ReLU가 음수값을 완전히 무시하는데 Leaky ReLU는 이러한 데이터가 조금이라도 의미 있는 경우에 사용할 수 있다.
- **ELU** 
 Leaky ReLU와 비슷한 이유이다.

 ![activation-functions](/images/activation-functions.png)
 
자료가 보이지 않는다면 [🔗 wikipedia](https://en.wikipedia.org/wiki/Activation_function)를 참고하자.

---

자 이제 실제로 어떻게 optimization을 수행할지를 알아보도록 하자.

먼저, Loss는 가장 마지막 layer(output layer)의 output과 실제 값과의 차이가 될 것이다. 따라서, 다음과 같이 정의할 수 있다.

(아래서 $\bold{h}_{L}$은 L번째 layer의 output을 의미한다.)

$$
\begin{align*}
\mathcal{L} &= \sum_{n=1}^{N}{\ell(y_n, \bold{h}_L)} \\
&= \sum_{n=1}^{N}{(y_{n} - \bold{h}_{L})^2} \\
&= \sum_{n=1}^{N}{(y_{n} - \sigma(\bold{w}_{L}^{\top}\bold{h}_{L-1} + b_{L-1}))^2} \\
&= \sum_{n=1}^{N}{(y_{n} - \sigma(\bold{w}_{L}^{\top}\sigma(\bold{w}_{L-1}^{\top}\bold{h}_{L-2} + b_{L-2}) + b_{L-1}))^2} \\
&= ...
\end{align*}
$$

여기서 중요한 것은 우리는 전체 $\bold{W}$를 학습시켜야 한다는 것이다. 우리는 출력층만 학습하는 게 아니라 전체 모든 layer의 $\bold{w}_{i}$를 업데이트해야 한다는 것이다.

그러기 위해서는 우리는 ${{\partial\mathcal{L}}\over{\partial \bold{w}_{i}}}$를 모두 구해야 한다는 것이다. 아마 가장 습관적으로 하는 행위는 숫자가 작은 값부터 편미분하면서 진행하는 것이다. 하지만, 그렇게 하지말고 반대 순서로 미분을 하라는 것이 **backpropagation**의 main idea이다.

$$
{{\partial\mathcal{L}}\over{\partial \bold{w}_{L}}} = \sum_{n=1}^{N}\{({\partial \bold{h}_L \over \partial \bold{w}_{L}} )\times\red{-2(y_{n} - \sigma(\bold{w}_{L}^{\top}\bold{h}_{L-1} + b_{L-1}))}\}
$$

$$
{{\partial\mathcal{L}}\over{\partial \bold{w}_{L-1}}} = \sum_{n=1}^{N}\{({\partial \bold{h}_{L} \over \partial \bold{w}_{L-1} })\times\red{-2(y_{n} - \sigma(\bold{w}_{L}^{\top}\bold{h}_{L-1} + b_{L-1}))}\}
$$

즉, 다음과 같은 chain rule을 이용하는 것이다.

$$
\begin{align*}
{{\partial\mathcal{L}}\over{\partial \bold{w}_{L}}} &= \red{ {{\partial\mathcal{L}}\over{\partial \bold{h}_{L}}} } {{\partial\bold{h}_{L}}\over{\partial \bold{w}_{L}}} \\
{{\partial\mathcal{L}}\over{\partial \bold{w}_{L-1}}} &= \red{ {{\partial\mathcal{L}}\over{\partial \bold{h}_{L}}} } {{\partial\bold{h}_{L}}\over{\partial \bold{w}_{L-1}}} \\
&= \red{ {{\partial\mathcal{L}}\over{\partial \bold{h}_{L}}} } {{\partial\bold{h}_{L}}\over{\partial \bold{h}_{L-1}}} {{\partial\bold{h}_{L-1}}\over{\partial \bold{w}_{L-1}}} \\
&= \blue{ {{\partial\mathcal{L}}\over{\partial \bold{h}_{L-1}}} } {{\partial\bold{h}_{L-1}}\over{\partial \bold{w}_{L-1}}} \\
{{\partial\mathcal{L}}\over{\partial \bold{w}_{L-2}}} &= \blue{ {{\partial\mathcal{L}}\over{\partial \bold{h}_{L-1}}} } {{\partial\bold{h}_{L}}\over{\partial \bold{w}_{L-2}}} \\
\end{align*}
$$

우리는 빨간색과 파란색 부분의 연산을 재활용할 수 있다는 것이다. 또한, ${{\partial\bold{h}_{l}}\over{\partial \bold{w}_{l}}}$은 굉장히 쉬운 연산이기에 우리가 신경 써서 계산해야 할 값은 매단계를 연결해줄 $ {{\partial\bold{h}_{l}}\over{\partial \bold{h}_{l-1}}}$이다.

![ml-backpropagation](/images/ml-backpropagation.jpg)

## Loss Function

우선 KL-Divergence, Entropy, Cross Entropy에 대한 약간의 이해가 필요하니 이전 Posting([🔗 Base Knowledge](posts/ml-base-knowledge))을 살펴보고 오자.

위에서는 자연스럽게 Loss를 계산할 때, Squared Error를 사용하였다. 하지만 경우에 따라서는 다양한 함수를 사용할 수 있다. multiclass classification에서는 **Cross Entropy Loss**를 사용한다.

우선 Cross Entropy Loss는 대게 L2 Loss(Squared Error)와 같이 비교되어진다. 우선 우리가 이전 [🔗 Parametric Estimation](posts/ml-parametric-estimation)에서 MLE를 다룰 때, KL-Divergence를 통해서 MLE가 최적 parameter를 찾을 것이라는 걸 증명한 적이 있다. 그렇다면, 우리가 [🔗 Logistic Regression](/posts/ml-logistic-regression)에서 Squared Error를 통해서 Loss를 구했던 공식을 확인해보자.(Gradient Asecent Part)

여기서 우리는 다음과 공식을 봤었다.

$$
\argmax_{\bold{w}} \sum_{n=1}^{N}y_{n}\log{\sigma(\bold{w}^{\top}\bold{x}_{n}) + (1-y_{n})\log{(1-\sigma(\bold{w}^{\top}\bold{x}_{n}))} }
$$

이 공식을 Cross Entropy를 통해서 설명할 수 있다.

$$
\begin{align*}
H_{q}(p) &= - \sum_{x \in \Omega}q(x)\log_{2}p(x) \\
&= \sum_{n=1}^{N}{[-y_{n}\log\hat{y}_{n} - (1- y_{n})\log(1-\hat{y}_{n})]}
\end{align*}
$$

즉, 여기서 우리가 얻을 수 있는 insight는 Cross Entropy는 sigmoid를 취한 binary classification에서 Squared Error와 같고, 이러한 Cross Entropy를 Squared Error가 할 수 없는 Multiclass에는 적용할 수 있을 것이라는 점이다. 왜냐하면, multiclass classification에 사용되는 Softmax Function을 이용해서 Sigmoid function을 유도하기 때문이다. 잠시 까먹었을까봐 Softmax 함수를 다시 적는다.

$$
\hat{y}_{k} = {{\exp(\bold{w}_{k}^{\top}\bold{x})}\over{\sum_{i=1}^{K}{\exp(\bold{w}_{i}^{\top}\bold{x})}}}
$$

따라서, Cross Entropy Loss를 대입하여 다음과 같은 Loss를 얻을 수 있다.

$$
\mathcal{L} = \sum_{n=1}^{N}\sum_{k=1}^{K}[-y_{k,n}\log\hat{y}_{k,n}],\quad y_{k,n} = p(x_{n} \in C_{k}| x_{n})
$$

여기서 $y_{k,n}$은 one-hot encoding된 데이터로, 정답인 class만 1이고 나머지는 모두 0으로 되어 있다. 따라서, multiclass classification에서는 위와 같은 Loss를 주로 사용한다.

이 두가지 뿐만 아니라 여러가지 Loss Function이 이미 존재한다. 예전에 잠깐 설명했던 L1 Loss부터 시작해서 NLLLoss, KLDivLoss 등등 존재하며, data의 특성과 output의 형태에 따라서 우리는 스스로 Loss Function을 새로 정의할 수도 있다.

## Reference

- Tumbnail : Photo by [Markus Winkler](https://unsplash.com/@markuswinkler?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText) on [Unsplash](https://unsplash.com/@markuswinkler?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText)
- activation function, wikipedia, <https://en.wikipedia.org/wiki/Activation_function>

[ML] 6. Neural Network


## Intro

NLP를 수행할 때, 우리는 sequence of character를 처리하는 방식을 제대로 알아야 제대로 된 전처리와 후처리 등이 가능하다. 따라서 해당 chapter에서는 어떻게 원본 문자/단어/문장을 처리하는 방식을 다룰 것이다.

## Regular Express

아주 기본적인 문자열 처리 방법이다. 이를 알고 있어야 실질적인 처리가 가능하다. 해당 내용은 별도의 Posting으로 분리하여 다루었다. ([🔗 Regex](/posts/regex))를 살펴보도록 하자.

## Text Normalization

우리가 사용할 NL은 정제되어 있지 않아서 여러 전처리를 수행해야 한다. 그 중에서 대중적으로 좋다고 알려진 방법들을 살펴볼 것이다. 기본적으로는 아래 단계를 처리하는 것이 일반적이다.

1. Word Tokenization  
   말 그대로 NL 데이터가 입력되었을 때, 이를 단어 단위로 쪼개는 것이다.
2. Word Reformating  
   단어를 나누었다면, 각 단어의 형태를 처리하기 쉬운 형태로 Normalizing하는 것이다.  
3. Sentence Segmentation  
   문장 단위로 구분해는 과정이다.

이제 각 단계를 세부적으로 다뤄보겠다.

### 1. Word Tokenization

우선 쉽게 생각할 수 있는 것은 단순히 띄어쓰기를 기준으로 구분하는 것이다. 그렇게 하면, 우리는 입력으로 주어진 Corpus에서 token을 추출할 수 있다.

하지만, "San Francisco"와 같은 단어가 두 개의 token으로 나누는 것이 아니라 하나의 token으로 처리되기를 원할 수 있다. 뿐만 아니라 일부 언어들(특히 중국어와 일본어)의 경우 띄어쓰기 없이 작성하는 언어들의 경우 문제는 더 커질 수 있다. 이 경우에는 **Word Segmenting**이라는 알고리즘을 활용할 수도 있는데, 원리는 매우 간단하다. 언어의 모든 단어를 포함하는 사전을 기반으로 문장에서 사전에 일치하는 가장 긴 문자열을 찾을 수 있을 때까지 token을 연장해서 만드는 방식이다.

그러나 이 방식도 결국은 특정 언어(중국어, 등)에서는 잘 작동하지만, 일부 언어(영어 등)에서는 잘 작동하지 않는 경우가 많다. 따라서, 최근에는 확률에 기반하여 같이 등장하는 횟수가 많을 경우 하나의 token으로 묶는 형태의 tokenization을 더 선호한다.

이 과정에서 우리가 추가적으로 수행하는 것이 바로 word의 갯수를 추출하는 것이다. 대게 우리가 관심 있어하는 수는 총 3가지이다.

1. **number of tokens**  
   즉, 띄어쓰기로 나뉘어지는 token들의 총 갯수를 의미한다.
2. **number of types(Vocabulary)**  
   띄어쓰기로 나뉘어진 token들의 중복을 제거한 종류들의 갯수를 의미한다. 대게 이러한 type들의 모음을 Vocabulary라고 한다.
3. **number of each type's tokens**  
   각 종류의 token이 얼마나 많이 등장했는지를 의미한다.

여기서 이러한 token이나 type이 서로 같나는 것을 어떻게 구분할 수 있을까? 이를 위해서 Word Reformating을 수행하여 좀 더 일반적인 형태로 변형하여 위의 수들을 파악하기도 한다.

### 2. Word Normalization and Stemming(Word Reformating)

대게의 언어는 word의 형태가 여러 개로 존재한다. 이 과정에서 우리가 고려해야 할 것이 정말 많다. 그 중에서 가장 기본적으로 수행되어야 할 내용은 다음과 같다. 해당 내용은 영어에 중심을 둔 설명이다.

1. **Uppercase**  
   영어에서 첫 글자는 대문자로 시작한다는 규칙이 있다. 또는 강조하고 싶은 단어를 대문자로 표현하기도 한다. 그 결과 token의 종류를 추출하는 과정에서 문제를 일으키기도 한다. 따라서, 이를 모두 lowercase로 바꿔버리는 것이다. 하지만, 모든 경우에 이를 적용할 수 잇는 것은 아니다. 가장 대표적인 예시로 US와 us의 의미가 다르다는 것이다. 또, 고유 명사인 General Motors와 같은 경우도 다르게 처리하는 것이 좋다. 따라서, 이를 고려해서 먼저 처리한 이후에 전체 데이터를 lowercase로 변환하는 방식을 수행한다.  
2. **Lemmatization**  
   Lemma(기본형, 사전형)로 단어를 변환하는 것이다. 가장 기본적인 것은 am, are, is와 같은 be동사를 모두 be로 변환하거나 car, cars, car's를 모두 기본형태인 car로 바꾸는 것이다. 대게의 경우에는 이 과정에서 의미를 일부 잃어버리기 때문에 lemma + tag로 기존 token을 복구할 수 있도록 하는 tag를 포함하는 것이 좋다.
3. **Stemming**  
   morpheme(형태소)은 중심 의미를 가지는 stem과 핵심 의미는 아니지만 stem에 추가 의미를 더해주는 affixes로 나누어 word를 나눌 수 있다. 따라서, 각 token을 가장 core의 의미를 가지는 stem으로 나타내는 방식이다. 대표적인 예시가 automate, automatic, automation을 automat으로 변환하는 것이다. 이는 lemmatization보다 넓은 범위의 word를 하나로 묶기 때문에 세부의미가 더 손실될 수 있다. 따라서, 기존 의미로 복구할 수 있는 tag를 포함하는 것이 좋다.

### 3. Sentence Segmentation

문장을 구분할 수 있는 도구로 우리는 "?", "!", "."을 활용한다. "?"와 "!" 같은 경우는 문장의 끝을 의미하는것이 대게 자명하다. 하지만, "."은 꽤나 애매할 수 있다. 소수점, Abbreviation(Mr., Dr., Inc.)와 같은 경우에 빈번하게 사용되기 때문이다. 따라서, 이를 판단하기 위해서 Decision Tree를 만들어서 이를 수행한다. 아래와 같이 사람이 직접 규칙을 정할 수도 있지만 현재는 대게 통계 기반으로 수행한다.

![nlp-sentence-segmentation](/images/nlp-sentence-segmentation.jpg)

## Collocation(연어) processing

Text Normalization을 통해서 우리는 sentence를 구분하고, word를 추출할 수 있었다. 하지만, 단순히 하나의 word를 기반으로 처리하는 것이 아니라 주변 단어를 활용하여 처리해야만 얻을 수 있는 정보들이 있다. 우리는 이를 Collocation(연어)를 활용하여 수행한다. 이는 특정 단어쌍이 높은 빈도로 같이 붙어 사용되는 현상을 말한다. **"모든 단어는 이를 동반하는 주변 단어에 의해 특성 지어진다."** 따라서, 우리는 이 collocation을 co-ocurrence로 생각할 수 있다. 이를 통해서 우리는 다음과 같은 것들을 할 수 있다.

1. **lexicography(사전 편찬)** : 같가니 유사한 뜻을 가지는 단어는 빈번하게 붙어서 사용되는데 이를 이용해서 하나의 단어의 뜻을 안다면, 이를 통해서 다른 단어의 뜻을 추론하며 확장해나갈 수 있다.
2. **language modeling** : NL를 통해서 원하는 결과를 얻기 위해서 특정 parameter를 추정해내는 것을 language modeling이라고 하는데 이 과정에서 collocation을 활용하는 것이 단일 단어를 활용하는 것보다 context를 활용할 수 있다는 점에서 장점을 발휘할 수 있다.
3. **NL generation** : 우리는 문맥상 매끄러운 문장을 원한다. 즉, "감을 잡다"를 "감을 붙잡다"라고 했을 때, 뜻을 이해할 수는 있지만 어색하다고 느낀다. 따라서, 이 관계를 활용해서 NL을 생성해야 하기 때문에 collocation을 고려해야 한다.

그렇다면, 이러한 Collocation을 어떻게 찾을 수 있을까?

1. **Frequency**  
   가장 간단하게 단순히 동시 발생 빈도를 확인하는 것이다. 정확한 파악을 위해서는 빈번하게 등장하는 의미 없는 단어를 먼저 filtering할 필요가 있다. 대표적인 예시로 a, the, and 등이 있다.
2. **Hypothesis Testing**  
   가설 검증으로 우리가 가정한 collocation을 지정하고, 이 사건이 일어날 가능성을 굉장히 낮게 하는 가설을 반대로 가정한 후에 이것이 불가능하다는 것을 증명하는 Null Hypothesis를 이용한 증명으로 타당성을 확보하는 것이다. 따라서, 우리가 보이고자 하는 것은 word1, word2가 있을 때, 두 단어가 서로 의존적이라는 것을 증명하고 싶은 것이다. 따라서, Null Hypothesis로 두 단어는 독립이다라고 지정하면, 우리는 다음 식을 얻을 수 있다.  
   $p(w_{1}, w_{2}) = p(w_{1})p(w_{2})$  
   이를 바탕으로 t-검증을 다음과 같이 수행할 수 있다.  
   $t = {{p(w_{1}, w_{2}) - p(w_{1})p(w_{2})} \over \sqrt{p(w_{1}, w_{2})\over{N}}} $  
   t값이 이제 커질 수록 우리는 해당 가설이 틀렸음을 증명하여 collocation임을 주장할 수 있다.

## Minimum Edit Distance

단어 또는 문장 간 유사도를 측정할 때, 사전을 기반으로 수행할 수도 있지만 참고할 corpus가 마땅하지 않거나 더 추가적인 수치가 필요하다면, Minimum Edit Distance로 유사도를 측정하기도 한다. 즉, 두 문자열이 같아지기 위해서 어느정도의 수정이 필요한지를 수치화한 것이다. 여기서 연산은 새로운 문자 추가, 삭제, 대체만 가능하다.

```plaintext
S - N O W Y  | - S N O W - Y
S U N N - Y  | S U N - - N Y
distance : 3 | distance : 5
```

다음과 같이 표현이 가능하다.

1. 문자열 x, y가 있을 때, $E(i, j)$는 x의 0\~i까지를 포함하는 문자열과 y의 0~j까지를 포함하는 문자열의 distance라고 하자.
2. 이렇게 되면, $E(i,j)$에서 우리는 끝문자의 규칙을 볼 수 있다.

    오른쪽 끝 문자가 가질 수 있는 조합은 3가지 밖에 없다.

    ```plaintext
    x[i]        | -           | x[i]
    -           | y[j]        | y[j]
    distance: 1 | distance: 1 | distance: 0 or 1
    ```

3. 그렇다면 우리는 하나의 사실을 알게 된다.

    $E(i,j)$는 다음 경우의 수 중 하나여야만 한다.

    - $E(i-1, j) + 1$
    - $E(i, j-1) + 1$
    - $E(i-1, j-1) + ((x[i] == y[j])\text{ ? 0 : 1} )$
4. 따라서, 다음과 같은 식을 유도할 수 있다.

    $E(i, j) =\min( \\
      \quad E(i-1, j) + 1, \\
      \quad E(i, j-1) + 1,  \\
      \quad E(i - 1, j-1) + ((x[i] == y[j])\text{ ? 0 : 1} )\\
    )$

만약, 각 연산의 비용이 다를 경우라면, 1 대신에 그 값을 넣어주면 충분히 풀 수 있으며, 추가적으로 최적의 이동형태를 알고 싶다면, back pointer 하나를 추가하는 것으로 충분하다.

## Reference

- Tumbnail : Photo by [David Ballew](https://unsplash.com/@daveballew?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText) on [Unsplash](https://unsplash.com/@daveballew?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText)


[NLP] 2. Text Processing

## Intro

Natural Language(자연어, 사람이 사용하는 통상 언어)를 input으로 활용하고자 하는 노력은 컴퓨터의 등장부터 시작하여 여러 번 시도되어 왔다. 지금까지도 완벽하게 이를 처리하는 것은 힘들다. 왜 Natural Language를 다루는 것은 어렵고, 이를 해결하기 위해서 NLP에서는 어떤 방식을 활용할지에 대한 개략적인 overview를 제시한다. 또한, Natural Language의 특성과 분석 단계를 이해하기 위해서 Linguistics(언어학)을 간략하게 정리한다.

## NLP

Natural Language Processing의 약자로 사람이 사용하는 언어를 input으로 하여 원하는 값을 추출해내는 것이 목표이다. 이를 위해서 우리는 사람의 언어를 이해하거나 다룰 수 있는 능력을 컴퓨터에게 부여해야 한다.

먼저, 이러한 필요가 있는 대표적인 usecase를 살펴보면 다음과 같다.

### Usecase

- **Spam Detection** 
 가장 간단한 예시로 mail에서 spam 여부를 확인하는 기능이다.
- **POS tagging / NER** 
 특정 단어 단위의 처리를 수행하게 되는데 단어의 품사와 대략적인 의미를 가진 category로 분류로 tagging하는 과정이다. 이를 기반으로 하여 다른 usecase에서 활용하는 경우가 많다. 품사와 category는 단어의 뜻을 추론하는데 큰 도움을 주며, 이것이 문장의 이해 등에 도움을 주기 때문이다.
- **Sentiment Analysis** 
 감정/여론 분석 등의 영역을 의미하며, 텍스트 또는 대화에서의 긍정/부정 여부를 판단하거나 평점 등을 추출하는 기능이다.
- **Conference Resolution** 
 "he", "she" 등 대명사, 생략 단어 등을 원래의 단어로 대체하거나 채우는 과정을 수행한다. 이 역시도 여러 영역에서 이를 기반으로 추가적인 작업을 할 수 있다. 
- **Word Sense Disambiguation(WSD)** 
 특정 단어가 주어졌을 때, 동의어, 동음이의어 등에서 가르키는 진짜 의미를 헷갈리지 않게 명확하게 다시 한 번 처리한다. 이 역시도 다른 NLP usecase에서 두루 사용된다.
- **Parsing** 
 문장에서 단어들을 의미를 가지는 단위(구, 절, 문장)로 다시 grouping한다. 이 과정을 잘 수행하기 위해서는 이전 단계에서 WSD와 Conference Resolution, POS tagging, NER이 이루어지면 좋다. 이 과정을 통해서 문장의 개략적인 의미를 파악할 수 있다.
- **Machine Translation(MT)** 
 특정 언어를 또 다른 Natural Language로 변경하는 기능이다.
- **Information Extraction(IE)** 
 특정 문장에서 사용자에게 의미있을만한 데이터를 추출하는 것이다.
- **Q&A** 
 특정 사용자가 질문을 하였을 때, 이 뜻을 이해하고, 이에 적절한 대답을 수행하는 방식이다.
- **Paraphrase** 
 문장의 뜻을 이해하고, 더 쉬운 형태의 표현으로 변환하는 기능이다.
- **Summarization** 
 여러 문장으로 이루어진 글의 의미를 이해하고, 적절한 내용으로 요약하는 기능이다.
- **Dialog** 
 Natural Language를 사용하는 사람과 1:1로 담화를 주고 받는 것이다. 의미를 이해할 뿐만 아니라 자신이 내보낼 output에 대해서도 적절하게 생성할 수 있는 능력이 필요하다.

위와 같이 많은 usecase가 있는데 이를 구현하는 것은 지금까지도 굉장히 challenge한 부분이다. 그것은 Natural Language가 가지는 몇몇 특징 때문이다.

### Why is NLP difficult?

여기서는 Natural Language 중에서 영어를 기반으로 한 설명이지만, 한국어도 매우 유사하다.

- **non-standard** : Natural Language를 사용하는 사람들이 표준을 항상 따르지는 않는다는 것이다. 우리는 약어를 사용하거나 문법에 맞지 않는 비문을 사용하여 의사소통을 하기 때문에 이것을 시스템이 이해하게 하는 것은 어렵다.
- **segmentation** issues : 의미를 가지는 단어 단위로 묶는 것이 어렵다는 것이다. 우리는 문장의 띄어쓰기를 어디로 받아들이냐에 따라서 의미가 달라지는 것을 본 경우가 있을 것이다.
- **idioms** : 관용구의 사용은 NLP에서 예외처리로 해주어야 하는 것이다. 단어 그대로의 의미와 다른 의미를 가지기 때문이다.
- **neologisms** : 신조어는 계속해서 생겨나기 때문에 이를 계속해서 업데이트 해주는 것도 부담이 된다.
- **world knowledge** : 사전 지식을 알고 있어야 이해할 수 있는 단어, 문장이 존재한다. 즉, 어떤 지식을 가지고 있느냐에 따라서 해석이 달라진다는 것이다.
- **tricky entity names** : 고유 명사 중에서 특히 contents(노래, 그림, 소설) 등의 제목이 해석 시에 헷갈리게 한다. 예를 들면, "Let it be"라는 비틀즈의 노래는 문장 중간에 들어가면, 하나의 문장으로 받아들여지게 되는데 이를 잘 해결할 수 있도록 해야 한다.

위의 내용을 요약하자면, 다양한 단어가 다양한 현상과 다양한 법칙(Grammer)의 영향을 받기에 어려우며, 단어가 가지는 모호성이 문제를 야기한다는 것이다.

### Solutions

이러한 문제를 해결하기 위해서 크게 두 가지 방식을 사용할 수 있다.

- Rule based approach 
 Gammer와 같은 법칙을 모두 적용해서 prgoramming을 하는 것이다. 하지만, 이 방식은 비문과 같은 문장을 제대로 처리할 수 없을 뿐만 아니라 정확한 형태의 문장이라도 여러 의미로 해석되는 문장에서 경향성과 문맥을 전혀 파악할 수 없다.
- Statistic based approach 
 그래서 최근에는 경향성과 문맥을 파악할 수 있도록 AI 기술, ML, Deep Learning을 이용하여 NLP를 수행하는 것이 하나의 trend로 자리 잡았다. 그렇다면, 어떻게 통계적인 접근법이 경향성과 문맥을 포함할 수 있을까? 이는 통계가 가지는 경향성이라는 특징과 conditional probability를 사용할 때의 문맥을 포함한 경향성을 파악할 수 있다는 점을 활용해서 가능하다.

## Linguistics

결국 앞으로 통계적인 방식을 활용하더라도 우리는 최소한의 언어학적인 기본이 필요하다. 왜냐하면, 통계에 사용할 데이터를 처리하기 위해서이다. 우리가 사용할 데이터는 text 또는 음성이다. 이를 적절하게 처리하여 통계에 사용할 유의미한 데이터로 변환하는 과정이 필요하다. 이를 위해서 언어학에 대한 이해가 필요한 것이다.

일반적으로 언어를 분석할 때, 사용할 수 있는 도구는 **Grammar**이다. 이는 특정 language에서 허용되는 규칙의 집합을 정리한 것이다. 이것의 종류는 크게 두 가지로 나뉜다.

- **Classic Grammar** 
 사람이 실제로 언어를 사용함에 있어 발생하는 이상한 습관과 같은 언어 표현이다. 이러한 법칙들은 대게 예제들을 통해서 정의되는데 이런 것을 명확하게 구분할 수 있는 명백한 도구가 존재하지는 않는다. 예를 들면, 감탄사와 같은 것들이 여기에 포함되겠다. 이는 이러한 변칙적인 형태 때문에 programming적으로 표현하는 것이 불가능하다.
- **Explicit Grammar** 
 명백하게 정의되어 있는 언어 규칙을 의미한다. 이는 Programm으로 구현할 수 있으며, 여러 Grammar 정리 내용이 이미 정리되어 있다. (CFG, LFG, GPSG, HPSG, ....) 
 이를 문법적으로 분석하기 위해서 우리는 6단계의 순차적인 처리가 필요하다.

### 6 Layers in Language

각 단계는 input과 output을 가진다. 단계적으로 진행되기 때문에 이전 단계의 output이 다음 단계의 input이 되며, 때때로 몇 단계는 생략될 수 있기에 유연하게 생각하도록 하자.

각 단계에서 실제로 특정 문장이 처리되는 과정을 이해하기 위해서 "Astronomers saw stars with telescope"라는 문장이 음성 또는 text로 들어왔을 때를 가정하여 각 단계에는 무엇을 하고 이를 통해서 어떻게 이 문장을 바꿀 수 있는지를 확인해보겠다.

> **1. Phonetics/Orthography(음성학/맞춤법)**

먼저 Orthography는 맞춤법 검사를 의미하며, character sequence로 input이 들어오면, 이를 맞춤법에 맞는지를 확인하여 이것이 수정된 sequence로 반환한다. 
예시 문장에 있는 "telescope"는 문법에 맞지 않으므로 "telescopes"로 바뀌어야 한다.

| input | output |
| :------------------------------------ | :------------------------------------- |
| Astronomers saw stars with telescope. | Astronomers saw stars with telescopes. |

Phonetics는 음성학을 의미하며, 혀와 음성의 영향을 주는 다양한 근육의 위치 형태, 모양, 빈도를 활용하여 자음과 모음을 분류하는 작업을 수행한다. Orthoography와는 달리 억양이라는 것을 추가적으로 활용할 수 있다.

| input | output |
| :---------------------------------------------------------- | :------------------------------------- |
| Astronomers saw stars with telescopes.를 의미하는 음성 신호 | əsˈtrɒnəməz sɔː stɑːz wɪð ˈtɛlɪskəʊps. |

*<https://tophonetics.com/> 을 통해서 변환하여 얻을 수 있다.

> **2. Phonology/Lexicalization(음운론/어휘화)**

Phonology은 음운론으로 소리와 phonemes(음소)사이의 관계를 이용하여, 음소를 특정 word로 변환하고, Lexicalization에서는 해당 단어를 사전에서의 형태로 변환하는 과정을 수행한다.

| input | output |
| :------------------------------------- | :------------------------------------- |
| əsˈtrɒnəməz sɔː stɑːz wɪð ˈtɛlɪskəʊps. | Astronomers saw stars with telescopes. |

> **3. Morphology(어형론)**

Morphology는 어형론으로 음소의 구성을 기본형(lemma)의 형태로 변환하며, 각 단어들을 형태학적인 의미를 갖는 카테고리(category, tag)로 분류한다.
여기서 사용되는 lemma와 category가 무엇인지 좀 더 자세히 살펴보자.

- **lemma** 
 - 사전에 표기되는 단어의 기본형으로, 사전에서 word를 찾는 pointer가 된다. 
 - 동음이의어의 경우 특정 뜻을 지칭하고 싶은 경우에는 numbering을 수행하기도 한다.
 - 더 나아가서는 형태소(morpeheme)까지 구분하기도 한다. 이는 혼자서 쓰일 수 있는 자립 형태소(root)와 의존 형태소(stem)으로 나눌 수 있다. 
 - 예를 들면, quotations -> quote[root] + -ation[stem] + -s[stem]
 - 위와 같은 형태로 세분화할 수도 있지만, 대게는 lemma 단위에서 그친다.
- **categorizing** 
 - category는 정하기 나름이며, 이미 정해져있는 tagset들도(Brown, Penn, Multext) 많이 존재하고, 억양이나 실제 분류 등을 수행하는 것도 가능하다.
 - **POS tagging**은 category를 분류하는 방법 중에서 가장 유명한데, 이는 여러 언어에서 거의 호환되기 때문에 이 방식을 활용하여 분석하는 것이 가장 안정적인 방법이라고 할 수 있다. 이는 별도의 Posting에서 더 자세히 다루도록 하겠다.

또한, 단어의 형태는 언어마다 다양하기 때문에 어느정도 언어마다 다른 작업을 해주어야 한다. 크게 구분되는 형태로 언어를 3개의 종류로 나눌 수 있다.

1. **Analytical Language(고립어)** 
 하나의 단어가 대게 하나의 morpheme을 가진다. 따라서, 하나 이상의 category로 구분되어질 수 있다. 
 ex. English, Chinese, Italian
2. **Inflective Fusional Language(굴절어)** 
 prefix/suffix/infix가 모두 morpheme에 영향을 미치며, morpheme의 정의 자체가 애매해지는 언어 형태 
 ex. Czech, Russian, Polish, ...
3. **Agglutinative Language(교착어)** 
 하나의 단어에는 morpheme이 명확하게 구분되고, prefix/suffix/infix 또한 명확하게 구분 가능하다. 따라서, 각 morpheme에 명확한 category를 mapping하는 것이 가능하다. 
 ex. Korean, ...

| input | output(based on Brown tagset) |
| :------------------------------------- | :-------------------------------------------------------------------- |
| Astronomers saw stars with telescopes. | (astronomer/NNS) (see/VBD) (star/NNS) (with/IN) (telescope/NNS) (./.) |

> **4. Syntax(통사론)**

lemma나 morpheme을 구문의 요소인 S(Subject, 주어), V(Verb, 동사), O(Object, 목적어)와 같은 요소로 분류한다. 이 분류를 수행할 때에는 문장의 구성요소를 알아야 한다. 이를 bottom-up으로 살펴보자.

- **Word(단어)** 
 사전에 명시된 하나의 단위라고 볼 수 있다. 이는 관용어(dark horse)를 포함한다.
- **Phrase(구)** 
 둘 이상의 단어 또는 구의 결합으로 만들어진다. 대게 하나의 문법적인 의미로 변환되어진다. 
 - 대표적인 예시
 - Noun : a new book
 - Adjective : brand new
 - Adverbial : so much
 - Prepositional : in a class
 - Verb : catch a ball
 - **Elipse(생략)** 
 대게 단어 또는 구가 생략되는 경우가 많다. 특히 담화의 경우 더욱 그렇다. 
 이를 추론을 통해서 추가할 수도 있다.
- **Clause(절)** 
 절은 주어와 서술어를 갖춘 하나의 문장과 유사하지만, 문장 요소로서 더 상위 문장에 속하는 경우이다. 
 또한, 영어에서는 특히 접속사로 연결된 절이 아닌 경우에는 해당 절이 지칭하는 대상이 절 내부에서 생략된다. 이를 gap이라고 한다.
- **Sentense** 
 하나 이상의 절로 이루어지고, 영어에서는 시작 시에 대문자로 표기하며 종료 시에는 구분자로 .?!로 끝난다.

결국 우리는 이러한 요소를 적절하게 표시해야 하는데, 이를 위해서 tree 구조를 사용하는 것이 일반적이다. 대표적으로 두 가지의 구조가 있다.

1. **phrase structure(derivation tree)**
 문장을 기점으로 절, 구, 단어로 top-down으로 내려가는 구조를 가진다. 
 각 단위를 묶을 때에는 ()를 이용하고, 그 뒤애 해당하는 내용이 무슨 구, 절인지를 표기한다.
2. **dependency structure** 
 단어 간의 관계에 더 집중하여 나타낸다. 따라서, 사람이 보기에는 불명확해 보일 수 있지만 특정 usecase에서는 유용하다.

| input | output (phrase structure) |
| :-------------------------------------------------------------------- | :------------------------------------------------------------------------------------- |
| (astronomer/NNS) (see/VBD) (star/NNS) (with/IN) (telescope/NNS) (./.) | ((astronomer/NNS)NP ((see/VBD)V ((star/NNS)NP ((with/IN)P (telescope/NNS)NP)PP)NP)VP)S |

![nlp-phase-structure](/images/nlp-phase-structure.jpg)

> **5. Semantics(Meaning, 의미론)**

간단하게는 주어, 목적어와 같은 tag나 "Agent"나 "Effect"와 같은 tag를 적용하며, 전체적인 의미를 유추해낸다.

| input | output |
| :------------------------------------------------------------------------------------- | :---------------------------------------------------------------------------------------------------- |
| ((astronomer/NNS)NP ((see/VBD)V ((star/NNS)NP ((with/IN)P (telescope/NNS)NP)PP)NP)VP)S | ((astronomer/NNS)NP/agent ((see/VBD)V ((star/NNS)NP/affected ((with/IN)P (telescope/NNS)NP)PP)NP)VP)S |

> **6. Discourse/Pragmatics(담화/화용론)**

실제 대화 등과 같은 목표를 해결하기 위해서 앞서 보았던 문장 구조를 이용한다.

만약, 해당 데이터를 통해서 하고자 하는 것이 이 이야기를 한 사람이 식당 내부에 있는지를 판단하고자 한다고 가정해보자.

| input | output |
| :---------------------------------------------------------------------------------------------------- | :----- |
| ((astronomer/NNS)NP/agent ((see/VBD)V ((star/NNS)NP/affected ((with/IN)P (telescope/NNS)NP)PP)NP)VP)S | False |

## Reference

- Tumbnail : Photo by [David Ballew](https://unsplash.com/@daveballew?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText) on [Unsplash](https://unsplash.com/@daveballew?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText)
- text to phonetic converter, <https://tophonetics.com>

[NLP] 1. Linguistics

## Intro

이전 Posting에서는 SVM에 대해서 알아보았다. 일반적인 Logistic Regression에서는 softmax function을 통해서 여러 class를 구분할 수 있었지만, SVM의 경우 구분 선이 결국은 hyperplane으로만 표현 가능하다. 이를 해결하기 위한 SVM에서의 여러 해결책을 알아보자.

## Multiclass in SVM

가장 쉽게 생각할 수 있는 것은 SVM을 결합해서 Multiclass를 구분할 수 있다는 idea이다. 아래에서 곧바로 제시할 아이디어들이 이에 대한 내용이다.

> **1. OvR SVM**

One vs Rest 의 약자로 다양한 별명이 존재한다. (One vs All, OVA, One Against All, OAA) 
이름에서부터 느껴지다시피 하나의 class와 그 외에 모든 class를 하나로 묶어서 SVM을 총 class 갯수만큼 만들어서 각 decision boundary로 부터 거리가 양의 방향으로 가장 큰 class를 선택하는 방식이다.

$$
\argmax_{k \in [K]}(\bold{w}_{(k)}^{\top}\phi(\bold{x})+ b_{(k)})
$$

![svm-ovr](/images/svm-ovr.jpg)

이 방식은 하나의 큰 문제를 갖고 있는데, 그것은 과도한 데이터 불균형을 유발한다는 것이다. 이러한 문제는 class의 수가 많아질 수록 더 심해진다.

> **2. OvO SVM**

One vs (Another) One의 약자로, 해당 방식은 1대1로 비교하면서 각 SVM에서 선택한 class 중에서 가장 많은 선택을 받은 class를 최종한다. OvR과는 다르게 각 각의 class를 1대1로 비교하기 때문에 데이터의 불균형에 대한 위협은 덜하다. 하지만, 해당 과정을 수행하기 위해서는 총 K(K-1)/2개의 SVM이 필요하다.

![svm-ovo](/images/svm-ovo.jpg)

또한, 그림에서 "?"로 표시된 부분을 어떤 class로 선택할지에 대한 기준이 없다. 왜냐하면, 각 영역에서 한 표씩만 받기 때문이다.

> **3. DAG SVM**

앞 서 보았던 OvO와 OvR의 문제를 해결하기 위해서 장단점을 취하기 위해서 둘을 결합한 방식이다. 계층 형태로 SVM을 구성하기 때문에 OvO보다는 적은 SVM을 사용하면서, OvO에서의 과도한 데이터 불균형을 해결한다.

![svm-multiclass-comparing](/images/svm-multiclass-comparing.jpg)

> **4. WW SVM**

multiclass 구분을 SVM 최적화 과정에 적용하기 위해서 목적 함수의 형태를 변형하여 구현한 방법으로 자세히 다루지 않지만, 궁금하다면 해당 [🔗 link](https://www.csie.ntu.edu.tw/~cjlin/papers/multisvm.pdf)를 통해서 확인할 수 있다.

## Kernel Method

이전까지는 실제로 SVM의 형태를 변형시키거나 SVM을 여러 개 활용하여 multiclass classification을 수행하기 위한 방법을 보았다.

또 다른 방법이 존재한다. 바로 input 공간을 확장하는 것이다. 즉, 더 많은 유의미한 feature를 수집하거나 기존 feature를 가공하여 새로운 feature로 활용하는 것이다. 시스템적으로 해결할 수 있는 방법은 기존 feature를 가공하여 새로운 feature를 활용하는 것이다. 아래의 예시를 보자.

![feature-transposing](/images/feature-transposing.jpg)

왼쪽 공간에서는 SVM은 decision vector를 적절하게 선택하는 것이 어렵다. 하지만, 기존 x 데이터에 절대값을 취하여 나타내어 데이터에 추가하면, 쉽게 decision boundary를 결정하는 것을 볼 수 있다. 그렇다면, 이러한 여러 변환 함수를 적용해보며 여러 feature를 더 추출하는 것이 좋은 해결책을 가져다 줄 것이다.

그렇다면, 우리의 Soft margin SVM의 Dual Problem을 다시 한 번 살펴보자.

$$
\begin{align*}
 \text{maximize} \quad & -{1\over2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_{i}\alpha_{j}y_{i}y_{j}\bold{x}_{i}^{\top}\bold{x}_{j} + \sum_{i=1}^{N}\alpha_{i} &\\
 \text{subject to} \quad & \sum_{i=1}^{N}\alpha_{i}y_{i} = 0, & \\
 & 0 \leq \alpha_{i} \leq C, & i = 1, ..., N
\end{align*}
$$

이것을 feature 변환(basis function을 취한다.)을 통해서 다음과 같이 변형한다는 것이다.

$$
\begin{align*}
 \text{maximize} \quad & -{1\over2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_{i}\alpha_{j}y_{i}y_{j}\red{\boldsymbol{\phi}^{\top}(\bold{x}_{i})\boldsymbol{\phi}(\bold{x}_{j})} + \sum_{i=1}^{N}\alpha_{i} &\\
 \text{subject to} \quad & \sum_{i=1}^{N}\alpha_{i}y_{i} = 0, & \\
 & 0 \leq \alpha_{i} \leq C, & i = 1, ..., N
\end{align*}
$$

하지만, 우리가 새로운 feature를 생성할 수록, 그리고 기존 feature를 복잡하게 사용할 수록 $\boldsymbol{\phi}(\bold{x}_{i})$를 연산하는 비용이 커질 수 밖에 없다. 

따라서, 우리는 일종의 trick을 하나 사용하도록 한다. 바로, 매 bayese update 마다 변하지 않고 재사용되는 값인 $\boldsymbol{\phi}^{\top}(\bold{x}_{i})\boldsymbol{\phi}(\bold{x}_{j})$를 다른 값으로 대체하면 어떨까? 그렇게 하면 우리는 $\boldsymbol{\phi}(\bold{x}_{i})$를 계산하고 구성하는 수고를 덜 수 있다.

이것이 kernel method(trick)의 핵심 아이디어이다.

가장 대표적인 예시로 아래와 같은 복잡한 $\phi$ 가 주어졌을 때,

$$
\boldsymbol{\phi}(x) = \exp[{{-x^{2}}\over{2\sigma^{2}}}](1, \sqrt{1\over{1!\sigma^{2}}}x, \sqrt{1\over{2!\sigma^{4}}}x^{2}, \sqrt{1\over{3!\sigma^{6}}}x^{3}, \cdots)
$$

아래의 (RBF) kernel로 대체가 가능해진다.

$$
\kappa(x,x^{\prime}) = \exp(-{{(x - x^{\prime})}\over{2\sigma^{2}}}) = \boldsymbol{\phi}^{\top}(x)\boldsymbol{\phi}(x^{\prime})
$$

대게 우리가 표현하고자 하는 형태의 $\boldsymbol{\phi}$는 이미 특정 kernel 함수로 매핑되고 있으니 직접 $\boldsymbol{\phi}$를 계산하기 전에 찾아보는 것이 도움이 될 것이다.[🔗 link](https://dataaspirant.com/svm-kernels/#t-1608054630726)

## Reference

- Tumbnail : Photo by [Markus Winkler](https://unsplash.com/@markuswinkler?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText) on [Unsplash](https://unsplash.com/@markuswinkler?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText)
- A Comparison of Methods for Multi-class Support Vector Machines, Chih-Wei Hsu and Chih-Jen Lin, <https://www.csie.ntu.edu.tw/~cjlin/papers/multisvm.pdf>
- SEVEN MOST POPULAR SVM KERNELS, <https://dataaspirant.com/svm-kernels/#t-1608054630726>

[ML] 5. Multiclass Classification in SVM


## Intro

우리는 Classification을 하기 위해서 Logistic Regression을 수행하였다. 그 결과 결국 Classification도 결국은 선을 긋는 것이라는 결론을 내리게 되었다. 하지만, 여기서 그치지 않고 하나 더 고민해 볼 수 있는 것이 있다. 바로 주어진 데이터에 대해서 완벽하게 구분하는 decision boundary가 여러 개 있을 때, 어떤 것이 가장 좋은 것일까? 이것에 대한 아이디어를 제시하는 것이 SVM이다. 해당 Posting에서는 이에 대해서 살펴보도록 하겠다.

## (Hard Margin) SVM

Soft Vector Machine의 약자로, 위에서 제시한 문제를 해결하기 위해서 Margin이라는 것을 도입하였다.

> **Margin**

**Margin**이란 decison boundary와 가장 가까운 각 class의 두 점 사이의 거리를 2로 나눈 값이다.

![svm-1](/images/svm-1.jpg)

위의 그림은 똑같은 데이터 분포에서 대표적인 decision boundary 두 개를 제시한 것이다. 여기서 우리는 굉장히 많은 decision boundary를 그릴 수 있다. 그 중에서도 파란색 실선이 직관적으로 가장 적절한 decision boundary가 될 것이라고 짐작할 수 있다. 그 이유는 필연적으로 data는 noise에 의한 오차가 발생할 수 있는데 실제 데이터의 오차의 허용 범위를 우리는 **margin**(=capability of unexpected noise)만큼 확보할 수 있다는 의미로 이를 해석할 수 있다. 따라서, 이 margin을 크게 하면 할 수록 좋은 성능을 가지는 선을 그을 수 있을 것이라는 결론을 내릴 수 있다.

이것이 SVM의 핵심 아이디어이다.

그렇다면, margin을 수학적으로 정의해보자. 우리가 decision boundary를 $f(\bold{x}) := \bold{w}^{\top}\bold{x} + b = 0$이라고 한다면, 점($\bold{x}_{i}$)과 vector 직선 vector 사이의 거리 공식을 통해서 ${{|f(\bold{x}_{i})|}\over{||\bold{w}||^{2}}}$라는 것을 알 수 있다.

따라서 margin은 수학적으로 다음과 같다.

$$
\min_{i}{{|f(\bold{x}_{i})|}\over{||\bold{w}||^{2}}}
$$

```plaintext
 🤔 Canonical(법칙까지는 아니지만 사실상 표준화된) SVM

 SVM에서는 f(x) = 0인 등식 형태를 같는다. 즉 f(x)에 어떤 값을 곱해도 똑같다는 것이다.
 그런데 margin의 크기를 구할 때에는, w와 b에 어떤 값이 곱해진다면 이 값이 굉장히 달라지게 된다.
 따라서, 일반적으로 우리는 margin에서의 |f(x)| = 1이 될 수 있도록 설정한다. 
 이렇게 하면 계산이 굉장히 쉬워진다.
```

![svm-2](/images/svm-2.jpg)

따라서, 우리는 위의 그림과 같은 형태로 $\bold{x}^{-}$와 $\bold{x}^{+}$를 찾을 수 있는 것이다.

이제 마지막으로 margin을 정의해보자.

$$
\begin{align*}
\rho &= {1\over2}\{ {{|f(\bold{x}^{+})|}\over{||\bold{w}||^{2}}} - {{|f(\bold{x}^{-})|}\over{||\bold{w}||^{2}}}  \} \\
&= {1\over2}{1\over{||\bold{w}||^{2}}}\{\bold{w}^{\top}\bold{x}^{+} - \bold{w}^{\top}\bold{x}^{-}\} \\
&= {1\over{||\bold{w}||^{2}}}
\end{align*}
$$

> **Optimization**

그렇다면, 이제 우리는 문제를 해결할 준비가 된 것이다. 우리가 하고자 하는 것은 margin을 최대화하면서도, 모든 data를 오류없이 분류하는 것이다. 이는 다음과 같은 Constraint Optimization 형태로 변환할 수 있다.

$$
\begin{align*}
  \text{maximize}   \quad & {1\over{||\bold{w}||^{2}}} &\\
  \text{subject to} \quad & y_{i}(\bold{w}^{\top}\bold{x}_{i} + b) \geq 1, & i = 1, ..., N
\end{align*}
$$

Conditional Optimization은 이전 Posting([[ML] 0. Base Knowledge](/posts/ml-base-knowledge))에서 다룬바 있다. 해당 내용에 대해 미숙하다면 한 번 살펴보고 오도록 하자.

위 내용을 숙지하였다면, 위의 폼이 다소 바뀌어야 한다는 것을 알 것이다. 해당 형태를 바꾸면서, minimize 형태를 미분이 간편할 수 있도록 바꾸도록 하겠다.

$$
\begin{align*}
  \text{minimize}   \quad & {1\over2}||\bold{w}||^{2} &\\
  \text{subject to} \quad & 1 - y_{i}(\bold{w}^{\top}\bold{x}_{i} + b) \leq 0, & i = 1, ..., N
\end{align*}
$$

우선 lagrangian은 다음과 같다.

$$
\mathcal{L} = {1\over2}||\bold{w}||^{2} + \sum_{i=1}^{N}\alpha_{i}(1 - y_{i}(\bold{w}^{\top}\bold{x}_{i} + b))
$$

이것에 KKT Condition을 적용하여 정리하면 다음과 같은 등식을 얻을 수 있다.

$$
\bold{w} = \sum_{i=1}^{N}\alpha_{i}y_{i}\bold{x}_{i}
$$

$$
\sum_{i=1}^{N}\alpha_{i}y_{i} = 0
$$

이를 $\mathcal{L}$에 대입하여 식을 정리하면, 다음과 같다.

$$
\mathcal{L} = -{1\over2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_{i}\alpha_{j}y_{i}y_{j}\bold{x}_{i}^{\top}\bold{x}_{j} + \sum_{i=1}^{N}\alpha_{i}
$$

이제 이것을 이용해서 Dual Problem을 정의하면 다음과 같다.

$$
\begin{align*}
  \text{maximize}   \quad & -{1\over2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_{i}\alpha_{j}y_{i}y_{j}\bold{x}_{i}^{\top}\bold{x}_{j} + \sum_{i=1}^{N}\alpha_{i} &\\
  \text{subject to} \quad & \sum_{i=1}^{N}\alpha_{i}y_{i} = 0, & \\
  & \alpha_{i} \geq 0, & i = 1, ..., N
\end{align*}
$$

이 식에서 눈여겨 볼점은 바로 constraint 부분이다. 이 과정을 통해서 결론적으로 constraint 부분이 부등식에서 등식이 되었다. 이는 연산 과정을 매우 간단하게 한다. 뿐만 아니라 $\bold{x}_{i}^{\top}\bold{x}_{j}$는 한 번 계산하면, 전체 과정에서 계속해서 재사용할 수 있기 때문에 컴퓨팅 시에는 굉장한 이점을 발휘할 수 있다. 따라서, 실제로 값을 구할 때에는 이것을 이용하여 값을 구하는 것이 가장 일반적이다.

## (Soft Margin) SVM

SVM의 모든 절차를 살펴본 것 같지만, 우리가 간과한 사실이 하나 있다. 바로 그것은 우리는 data가 하나의 선을 통해서 완벽하게 나뉘어진다고 가정했다. 하지만, 실제 데이터는 그렇지 않을 가능성이 크다. 따라서, 우리는 어느 정도의 오차를 허용할 수 있도록 해야 한다. 이를 slack($\zeta$)이라고 한다.

![svm-2](/images/svm-2.jpg)

이를 적용하면, 우리의 목적함수와 제약 조건을 변경해야 한다. 이를 변경하는 방법은 두 가지가 존재하는데 각 각 slack variable의 L2-norm을 목적함수에 더하는 방식과 L1-norm을 더하는 방식이다.

> **L2-norm Optimization**

먼저 L2-norm을 더하는 방식을 알아보자
$$
\begin{align*}
  \text{minimize}   \quad & {1\over2}||\bold{w}||^{2} + C\sum_{i=1}^{N}\zeta_{i}^{2} &\\
  \text{subject to} \quad & 1 - y_{i}(\bold{w}^{\top}\bold{x}_{i} + b) - \zeta_{i} \leq 0, & i = 1, ..., N
\end{align*}
$$

여기서 $C$는 margin 최대화와 slackness 정도의 상대값을 의미한다. 만약, slackness보다 margin의 최대화가 중요하다면, C값은 커지고 반대라면 이 값은 작아진다.

우선 lagrangian을 먼저 구하면 다음과 같다.

$$
\mathcal{L} = {1\over2}||\bold{w}||^{2} + {C\over2}\sum_{i=1}^{N}\zeta_{i}^{2} + \sum_{i=1}^{N}\alpha_{i}(1 - \zeta_{i} - y_{i}(\bold{w}^{\top}\bold{x}_{i} + b))
$$

KKT condition을 이용하여 주요 값들을 구하면 다음과 같은 등식을 얻을 수 있다.

$$
\bold{w} = \sum_{i=1}^{N}\alpha_{i}y_{i}\bold{x}_{i}
$$

$$
\sum_{i=1}^{N}\alpha_{i}y_{i} = 0
$$

$$
\boldsymbol{\zeta} = {\alpha\over{C}}
$$

마지막으로 이를 Dual Problem으로 재정의하면 다음과 같아진다.

$$
\begin{align*}
  \text{maximize}   \quad & -{1\over2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_{i}\alpha_{j}y_{i}y_{j}(\bold{x}_{i}^{\top}\bold{x}_{j} + {1\over{C}}\delta_{ij}) + \sum_{i=1}^{N}\alpha_{i} &\\
  \text{subject to} \quad & \sum_{i=1}^{N}\alpha_{i}y_{i} = 0, & \\
  & \alpha_{i} \geq 0, & i = 1, ..., N
\end{align*}
$$

여기서 $\delta_{ij}$는 단위행렬이다. 기존 hard margin svm과 비교했을 때, ${1\over{C}}\delta_{ij}$ 외에는 바뀌지 않는 것을 알 수 있다.

> **L1-norm Optimization**

그 다음은 L1-norm이다.
$$
\begin{align*}
  \text{minimize}   \quad & {1\over2}||\bold{w}||^{2} + C\sum_{i=1}^{N}\zeta_{i} &\\
  \text{subject to} \quad & 1 - y_{i}(\bold{w}^{\top}\bold{x}_{i} + b) - \zeta_{i} \leq 0, & \\
  & \zeta_{i} \geq 0 & i = 1, ..., N
\end{align*}
$$

여기서는 slack variable이 반드시 0보다 크거나 같다는 것을 주의하자.

lagrangian은 다음과 같다.

$$
\mathcal{L} = {1\over2}||\bold{w}||^{2} + C\sum_{i=1}^{N}\zeta_{i} + \sum_{i=1}^{N}\alpha_{i}(1 - \zeta_{i} - y_{i}(\bold{w}^{\top}\bold{x}_{i} + b)) -  \sum_{i=1}^{N}\beta_{i}\zeta_{i}
$$

KKT condition을 이용하여 주요 값들을 구하면 다음과 같은 등식을 얻을 수 있다.

$$
\bold{w} = \sum_{i=1}^{N}\alpha_{i}y_{i}\bold{x}_{i}
$$

$$
\sum_{i=1}^{N}\alpha_{i}y_{i} = 0
$$

$$
\sum_{i=1}^{N}\beta_{i} = C
$$

마지막으로 이를 Dual Problem으로 재정의하면 다음과 같아진다.

$$
\begin{align*}
  \text{maximize}   \quad & -{1\over2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_{i}\alpha_{j}y_{i}y_{j}\bold{x}_{i}^{\top}\bold{x}_{j} + \sum_{i=1}^{N}\alpha_{i} &\\
  \text{subject to} \quad & \sum_{i=1}^{N}\alpha_{i}y_{i} = 0, & \\
  & 0 \leq \alpha_{i} \leq C, & i = 1, ..., N
\end{align*}
$$

결국 기존 Hard margin과 비교했을 대는 마지막 constraint에 $\alpha_{i} \leq C$가 추가된 것 밖에 없다.

---

마지막으로 여기서 하나의 insight를 더 얻을 수 있다.  
L1-norm의 optimization으로 돌아가보자.

$$
\begin{align*}
  \text{minimize}   \quad & {1\over2}||\bold{w}||^{2} + C\sum_{i=1}^{N}\zeta_{i} &\\
  \text{subject to} \quad & 1 - y_{i}(\bold{w}^{\top}\bold{x}_{i} + b) - \zeta_{i} \leq 0, & \\
  & \zeta_{i} \geq 0 & i = 1, ..., N
\end{align*}
$$

목적 함수의 slack variable에 constraint의 값을 대입하여, 다음과 같이 변환이 가능하다.

$$
\min {C^{\prime}\over2}||\bold{w}||^{2} + \sum_{i=1}^{N}max\{ 0, 1 - y_{i}(\bold{w}^{\top}\bold{x}_{i} + b) \}
$$

이 형태는 logistric regression에 regularization을 수행한 것과 동일한 형태를 가지게 된다. 즉, 이전 logistic regression에서 regularization을 다루지 않았는데, 결국은 soft margin svm의 L1-norm 목적함수가 logistic regression 중에서도 hinge function이라는 것을 이용했을 때의 regularization이 되는 것이다.

## Generalization

여태까지 살펴본 Regression을 통해서 우리는 General한 Classification 방식을 지정할 수 있다. 우선 아래 식을 살펴보자.

- Linear Regression(Quadratic Loss)  
  $\min {C^{\prime}\over2}||\bold{w}||^{2} + \sum_{i=1}^{N}{1\over2}(1 - y_{i}(\bold{w}^{\top}\phi(\bold{x}_{i})) )^{2}$
- Logit Regresion(Log Loss)  
  $\min {C^{\prime}\over2}||\bold{w}||^{2} + \sum_{i=1}^{N}\log( 1 + \exp[-y_{i}(\bold{w}^{\top}\phi(\bold{x}_{i})]) )$
- Binary SVM(Hinge Loss)  
  $\min {C^{\prime}\over2}||\bold{w}||^{2} + \sum_{i=1}^{N}max\{ 0, 1 - y_{i}(\bold{w}^{\top}\phi(\bold{x}_{i})) \}$

여태까지 나온 식들을 살펴보면 위와 같다. 우리는 여기서 아래와 같은 일반적인 형태의 Classification을 제시할 수 있다.

- General Classification  
  $\min {C^{\prime}\over2}||\bold{w}||^{2} + \sum_{i=1}^{N}\varepsilon\log( 1 + \exp[-y_{i}(\bold{w}^{\top}\phi(\bold{x}_{i})]) )$

여기서 $\varepsilon$이 1이면 바로 logistic regression이 되고, $\varepsilon$이 0에 수렴할 수록 SVM이 된다. 아래 그림을 보면 이를 알 수 있다.

![compare-regressions](/images/compare-regressions.jpg)

## Reference

- Tumbnail : Photo by [Markus Winkler](https://unsplash.com/@markuswinkler?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText) on [Unsplash](https://unsplash.com/@markuswinkler?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText)


[ML] 4. SVM


## Intro

이전까지 우리는 input data가 들어왔을 때, continuos한 output을 얻는 것을 목표로 했다. 하지만 현실에서는 대게 정확한 수치보다는 특정 분류로 나누는 것이 효과적인 경우가 많다. 예를 들어, spam 필터링, object detection, 등 등. 따라서, 해당 포스팅에서는 classification을 위해서 사용할 수 있는 logistic regression에 대해서 살펴볼 것이다.

## Classification

**Classification**이란 결국 특정 input이 들어왔을 때, 이를 하나의 Class라는 output을 내보내는 것이다. 즉, output은 연속적이지 않고, descret하다. 대게 Classification에서는 Class의 갯수를 K라고 표기하고, $C_k$는 k 번째 Class라는 의미로 사용되어진다.

그렇다면, 어떻게 Class를 나눌 수 있는 것일까? 매우 단순하게도 이는 **Decision Boundary**라는 선을 그어서 해결 할 수 있다.

![decision-boundary](/images/decision-boundary.jpg)

위의 예시처럼 우리는 선을 하나 그어서 $\red{\text{x}}$와 $\blue{\text{o}}$를 구분할 수 있다. 이를 통해서 우리는 Class 1에 해당할 것이라고 예측하는 구간 $R_1$이 만들어지고, Class 2라고 예측하는 구간 $R_2$를 구성할 수 있다.

즉, classification을 수행하기 위해서 해야할 일은 기존의 Regression 과정과 마찬가지로 선을 찾는 것이다.

결국 찾고자 하는 것이 선이라면, 이것을 Linear Regression으로 해결할 수 있을 것이다. 따라서, 우리는 다음과 같은 식으로 간단히 Linear Regression을 바꿔서 생각할 수 있다.

- 예측값($\hat{y}$, $h(\bold{x})$)  
  $h(\bold{x}) = \text{sign}(\bold{w}^{\top}\bold{x}) = \begin{cases} +1 & \bold{w}^{\top}\bold{x} \geq 0 \\ -1 & \text{otherwise}\end{cases}$
- Least Squared Error(LS, MLE)  
  실제로 parameter를 구할 때에는 sign을 취하지 않는데, sign을 취하게 되면 모두 LS는 결국 오답의 갯수 정도로 취급된다. 즉, 얼마나 예측이 잘못되었는지를 반영할 수 없다는 것이다. 따라서, 이는 기존 Linear Regression의 LS를 구하는 방법과 동일하게 수행한다.  
  $\argmin_{w} {1\over2}\sum_{n=1}^{N}{(y_n - (\bold{w}^{\top}\bold{x}))^2}$

이렇게 Linear Regression을 적용하면 문제가 없을 거 같다. 하지만, 실제로는 문제가 있다. 바로, 데이터가 불균형할 때이다. 만약 데이터가 decision boundary를 기준으로 대칭(symmetric)인 형태로 존재한다면, 문제가 없다. 하지만, 비대칭(asymmetric)인 경우 제대로 동작하지 않는다. 왜냐하면, linear regression은 최적에서 데이터의 평균을 반영하는데 불균형한 경우 데이터의 평균이 Decision Boundary가 되는 것은 문제가 있다.

![linear-in-classification](/images/linear-in-classification.jpg)

## Logistic Regression

위에서 제시한 문제를 해결하기 위해서 Classification에서는 Linear Regression이 아닌 Logistic Regression을 활용한다. 이를 이해하기 위해서 기반이 될 요소들을 먼저 살펴보자.

> **Discriminant Function**

판별함수(Discriminant Function, Score Function) 등으로 불리는 해당 함수는 특정 data가 특정 class에 속할 가능성(likelihood, probability, score)을 나타내는 함수이다. 즉, input으로 data를 받고, output으로 class에 속할 확률을 내보낸다.

이를 통해서 우리는 다음과 같은 과정을 할 수 있다.

만약, $f_k(\bold{x}) \gt f_j(\bold{x})$이라면, $\bold{x}$의 class는 $C_k$이다.

따라서, 우리는 다음과 같은 식으로 여러 개의 Class가 있는 공간에서 data를 분류할 수 있다.

$$
h(\bold{x}) = \argmax_{k}f_{k}(\bold{x})
$$

그렇다면, Discriminant Function으로 어떤 값을 쓰면 좋을까? 이에 대한 해결책을 Bayes Decision Rule에서 제시한다.

> **Bayes Decision Rule**

만약 우리가 특정 data가 특정 Class에 속할 확률을 구한다고 하자. 우리는 먼저 Likelihood를 생각할 수 있다. $P(x|C = k), P(x|C = j)$를 구하여 각 Class에 속할 확률을 비교할 수 있을까?  
물론 비교는 가능하다 하지만, 반쪽짜리 비교라고 할 수 있다. 만약, class k에 속하는 데이터보다 class j에 속하는 데이터가 훨씬 많다고 하자. 그러면, 일반적으로 class j가 발생할 확률 자체가 높다. 하지만, likelihood는 이러한 경향을 반영하지 않는다. 간단한 예시를 들어보자.

```plaintext
 🤔 어떤 동물의 털에 존재하는 색의 갯수가 주어졌을 때, 고양이일 확률과 호랑이일 확률이라고 하자.

  그리고, input data는 털에 존재하는 색의 수라고 하자. (호랑이는 대게 3가지 색, 백호 = 2가지 색, 고양이는 매우 다양)
  그렇다면, P(털의 색 = 3|C = 호랑이), P(털의 색 = 3|C = 고양이)를 비교했을 때, 우리는 당연히 전자가 크다고 생각할 것이다.
  하지만, 여기서 우리가 고려하지 않은 것이 있다. 바로 전체 고양이와 호랑이의 비율이다. 
  상대적으로 고양이가 호랑이보다 압도적으로 많다는 것을 고려했을 때, 고양이의 확률이 더 높을 수도 있다. 

  즉, 어떤 동물의 털에 존재하는 색의 갯수가 주어졌을 때, 고양이일 확률은 
  P(C=고양이|털의 색=3) =  P(털의 색 = 3|C = 고양이)P(C=고양이)이다. (분모는 생략함.)
```

즉, Bayes Rule에 기반하여 우리가 원하는 output은 Posterior라는 것을 명확히 알 수 있다.

$$
\begin{align*}
p(C_{k}|\bold{x}) &= {{p(\bold{x}| C_{k}) p(C_{k})}\over{\sum_{j=1}^{K}{p(\bold{x}|C_{j})p(C_{j})}}} \\
&\propto p(\bold{x}| C_{k}) p(C_{k})
\end{align*}
$$

위의 경우 Class간의 상대 비교에 사용하는 지표로 이를 사용하기 때문에, 분모(Normalization Factor, 확률의 총합이 1이 되도록 하는 역할)를 제외하여도 상관없기에 대게 복잡한 분모 계산을 제외하고 표현하는 것이 일반적이다.

또한, 앞선 예시에서 얻을 수 있는 insight는 편향된 데이터일수록 MLE를 사용할 수 없다는 것이다. 위에서 Linear Regression이 Classification에 부적함한 경우도 데이터의 편향이 있을 경우이다. 이 역시 Linear Regression이 결국은 MLE에 기반하기 때문인 것이다.

우리는 각 Class 자체의 확률(Prior)과 Likelihood를 이용할 수 있는 Discriminant Function을 구해야 한다는 것이다.

> **Logistic Regression**

자 이제 드디어 Logistric Regression을 시작해보자. 우리는 Discriminant Function을 먼저 지정해야 한다. 여러 가지 방법이 있지만, 가장 대표적으로 사용되는 방법은 **Softmax**를 활용하는 것이다. **Softmax**를 활용하여 식을 나타내면 아래와 같다.

$$
p(y_n = k | \bold{x}_n, \bold{w}) = {{\exp(\bold{w}_{k}^{\top}\bold{x}_n)}\over{\sum_{j=1}^{K}{\exp(\bold{w}_{j}^{\top}\bold{x}_n)}}}
$$

만약, class가 2개인 Binary Classification인 경우에 **Softmax**는 다음과 같아진다. 특히 이를 **Sigmoid**(**Logit**)라고 정의한다.

$$
p(y_n = k | \bold{x}_n, \bold{w}) = {1\over{1+\exp(-y_{n}\bold{w}^{\top}\bold{x}_{n})}}
$$

이를 유도하는 과정은 생략하지만, 여타 다른 블로그를 더 참고하면 좋다.

이를 Linear Regression과 비교해서 살펴보자.

![logistic-vs-linear](/images/logistic-vs-linear.jpg)

Linear Regression은 특정값을 향해 나아가고 있다. 해당 방식을 보면 x가 대상의 특성을 강하게 가지고 있다면, 명확하게 구분할 수 있는데, 이는 **sigmoid**($\sigma$) 함수가 [0, 1] 범위 내에서 정의되기 때문에 Regression 과정에서 극단 데이터(outlier)가 가지는 영향력이 Linear Regression보다 극단적으로 적다는 것을 알 수 있다.

자 이것이 가지는 의미를 이전에 살펴본 **Bayes Decision Rule**에 기반해서 생각해보자. **sigmoid**($\sigma$)는 결국 극단적인 데이터이든, 애매한 데이터이든 거의 비슷한 값으로 변환한다. 그렇다는 것은 기존에는 평균을 구하는데에 input(x)의 값이 큰 영향을 미쳤다면, **sigmoid**($\sigma$)에서는 특정 class에 속하는 x의 갯수가 많은 영향을 주는 것을 알 수 있다. 이를 통해서 **sigmoid**($\sigma$)가 완벽하지는 않지만, **Bayes Decision Rule**을 반영했다는 것을 알 수 있다.

마지막으로, MLE를 통해서 Logistic Regression의 parameter를 추정해보자. (MAP는 기존에 살펴본 Linear Regression과 동일하게 regularizer를 더해주는 방식이기 때문에 생략한다.)

$$
\begin{align*}
\argmax_{w}\log{p(\mathcal{D}|\bold{w})} &= \argmax_{w}\sum_{n=1}^{N}{\log p(y_{n}|\bold{x}_{n}, \bold{w})} \\
&= \argmax_{w}\sum_{n=1}^{N}{\log ({1\over{1+\exp(-y_{n}\bold{w}^{\top}\bold{x}_{n})}}) } \\
&= \argmax_{w}\sum_{n=1}^{N}{-\log (1+\exp(-y_{n}\bold{w}^{\top}\bold{x}_{n})) } \\
&= \argmin_{w}\sum_{n=1}^{N}{\log (1+\exp(-y_{n}\bold{w}^{\top}\bold{x}_{n})) } \\
\end{align*}
$$

## Gradient Descent/Ascent

위의 복잡한 식을 봤으면 알겠지만, 안타깝게도 일반식으로 $\bold{w}_{MLE}, \bold{w}_{MAP}$ 등을 구할 수는 없다. 따라서, 우리가 믿을 것은 Gradient를 이용한 방식이다.

> **Gradient Descent**

먼저, 위에서 봤겠지만, Loss는 다음과 같다.

$$
\mathcal{L} = \sum_{n=1}^{N}{\log(1+\exp(-y_{n}\bold{w}^{\top}\bold{x}_{n}))}
$$

이제 이를 미분해서 Gradient를 구하면 다음과 같다.

$$
\nabla_{\bold{w}}\mathcal{L}(\bold{w}) = \sum_{n=1}^{N}{{{-y_{n}\exp(-y_{n}\bold{w}^{\top}\bold{x}_{n})}\over{1+\exp(-y_{n}\bold{w}^{\top}\bold{x}_{n})}}\bold{x}_{n}}
$$

따라서, Gradient Descent 방식은 다음과 같이 진행된다.

$$
\bold{w}_{t+1} = \bold{w}_{t} - \alpha\nabla_{\bold{w}}\mathcal{L}(\bold{w}_{t})
$$

> **Gradient Ascent**

위의 방식이 가장 일반적이지만, 우리가 sigmoid의 class값으로 $y \in \{-1, 1\}$ 대신 $y \in \{0, 1\}$을 사용했을 경우 다른 식으로도 접근이 가능하다.

이 경우에는 Loss라기 보기 어렵지만, 다른 형태의 optimization 형태가 만들어진다. (여기서 $\sigma$는 sigmoid 함수를 의미한다.)

$$
\argmax_{\bold{w}} \sum_{n=1}^{N}y_{n}\log{\sigma(\bold{w}^{\top}\bold{x}_{n}) + (1-y_{n})\log{(1-\sigma(\bold{w}^{\top}\bold{x}_{n}))} }
$$

이를 똑같이 미분하여 사용하지만, 반대로 이 경우에는 maximization 이기 때문에 Gradient Ascent를 수행해야 한다.

우선 미분 결과 얻는 Gradient는 다음과 같다.

$$
\nabla_{\bold{w}}\mathcal{L}(\bold{w}) = \sum_{n=1}^{N}{[y_{n} - \sigma(\bold{w}^{\top}\bold{x}_{n})]\bold{x}_{n}}
$$

굉장히 간단하게 정리가 되어지는 것을 볼 수 있다.

$$
\bold{w}_{t+1} = \bold{w}_{t} - \alpha\nabla_{\bold{w}}\mathcal{L}(\bold{w}_{t})
$$

따라서, 아래와 같이 Gradient Ascent를 활용하여 계산하는 것도 충분히 가능하다.

> **Newton Method**

이러한 형태로 넘어오게 되면, 굉장히 많은 연산이 각 update마다 필요하다는 것을 알 수 있다. 따라서, 우리는 이 과정을 축약할 방법을 찾게 된다. 그 아이디어는 바로 gradient를 업데이트 할 때, linear 하게 update하는 것이 아니라 Quadratic하게 update하는 것이다. 이를 위한 방법론이 **Newton Method**이다. 이 방식을 Logistic Regression에 적용하였을 때, 이를 IRLS(Iterative Re-weighted Least Squared) Algorithm 이라고 부른다.

![newton-method](/images/newton-method.jpg)

위 그래프에서 f(x)가 Loss 라고 할 때, 우리는 $x_k$에서 직선형의 gradient를 사용하는 것보다 quadratic 형태를 사용하는 것이 더 빠르게 수렴값을 찾을 수 있다는 것을 알 수 있다.

이를 사용하기 위해서는 다음 2가지에 대한 사전 이해가 필요하다.

- Taylor Series  
  smooth한 형태를 가진 x에 대한 함수를 x에 대한 급수의 형태로 변환한 것이다. 따라서 이를 식으로 나타내면 다음과 같다.  
  $T_{\infin}(x) = \sum_{k=0}^{\infin}{f^{(k)}(x_{0})\over{k\!}}(x-x_{0})^{k} $  
  즉, sine 함수와 같은 형태의 그래프도 x의 급수 형태로 변환이 가능하다는 것이다. Newton Method에서는 무한대까지는 사용하지 않고, 대게 K=2까지를 쓴다.
- Hessian Matrix  
  특정 함수 $f(\bold{x})$를 각 feature에 대해서 이중 편미분한 결과를 저장한 행렬이다. 식은 다음과 같다.  
  $
  H = \nabla^{2}f(x) =
  \left[
    \begin{array}{ccc}
      \dfrac{\partial^{2} f(\mathbf{x})}{\partial x_{1}^{2}} & \cdots & \dfrac{\partial^{2} f(\mathbf{x})}{\partial x_{1} \partial x_{D}} \\
      \vdots & \ddots & \vdots \\
      \dfrac{\partial^{2} f(\mathbf{x})}{\partial x_{D} \partial x_{1}} & \cdots & \dfrac{\partial^{2} f(\mathbf{x})}{\partial x_{n}^{2}}
    \end{array}
  \right]
  $

이를 이용해서, Newton Method의 결과값을 정리하면 결과는 다음과 같다.

$$
\bold{w}^{(k+1)} = \bold{w}^{(k)} - [\nabla^{2}\mathcal{J}(\bold{w}^{(k)})]^{-1}\nabla\mathcal{J}(\bold{w}^{(k)})
$$

자 이제 이것을 실제로 Logistic Regression 식에 대입해보자.

$$
\begin{align*}
  \nabla\mathcal{J}(w) &= - \sum_{n=1}^{N}(y_{n}-\hat{y}_{n})x_{n} \\
  \nabla^{2}\mathcal{J}(w) &= \sum_{n=1}^{N}\hat{y}_{n}(1-\hat{y}_{n})\bold{x}_{n}\bold{x}_{n}^{\top}
\end{align*}
$$

여기서, 아래와 같이 변수를 정의하면,

$$
S =
  \begin{bmatrix}
    \hat{y}_{1}(1-\hat{y}_1)  & \cdots  & 0                         \\
    \vdots                    & \ddots  & \vdots                     \\
    0                         & \cdots  & \hat{y}_{N}(1-\hat{y}_N)  \\
  \end{bmatrix},

\bold{b} =
  \begin{bmatrix}
    {{y_{1} - \hat{y}_{1}}\over{\hat{y}_{1}(1-\hat{y}_{1})}} \\
    \vdots \\
    {{y_{N} - \hat{y}_{N}}\over{\hat{y}_{N}(1-\hat{y}_{N})}}
  \end{bmatrix}
$$

결과적으로 다음과 같은 형태를 얻을 수 있다.

$$
\begin{align*}
\bold{w}_{k+1} &= \bold{w}_{k} + (XS_{k}X^{\top})^{-1}XS_{k}\bold{b}_{k} \\
&= (XS_{k}X^{\top})^{-1}[(XS_{k}X^{\top})\bold{w}_{k} + XS_{k}\bold{b}_{k}] \\
&= (XS_{k}X^{\top})^{-1}XS_{k}[X^{\top}\bold{w}_{k} + \bold{b}_{k}]
\end{align*}
$$

이는 결코 계산 과정이 단순하다고는 할 수 없지만, 빠르게 수렴할 수 있기 때문에 가치있는 방법이다.

## Reference

- Tumbnail : Photo by [Markus Winkler](https://unsplash.com/@markuswinkler?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText) on [Unsplash](https://unsplash.com/@markuswinkler?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText)


[ML] 3. Logistic Regression

[ML] 2. Linear Regression

## Intro

Machine Learning은 특정 목표를 달성하기 위해서 데이터로 부터 pattern 또는 가정 등을 유도해내는 방법이다.
이를 위한 가장 일반적인 방법은 여러 개의 확률분포와 이것의 parameter의 조합(probabilistic model)들 중에서 측정된 데이터들을 가장 잘 나타내는 하나를 찾아내는 것이다.
그 중에서, 확률 분포를 결정한 상태에서 parameter를 찾아나가는 형태의 접근법을 우리는 Parametric Estimation이라고 한다. 그 외에도 Nonparametric, Semi-parametric 방식도 존재하지만 이는 여기서는 다루지 않는다.

## Small Example

간단한 예시를 통해서 Parametric Estimation의 흐름을 익혀보자.

한 학급에서 학생들의 형제자매 수에 대한 예측을 하고 싶다고 하자. 
그렇다면, 우리는 먼저 조사(관측)를 수행해야 한다. 이를 통해서 다음과 같은 데이터를 얻게 되었다고 하자.

| x | 1 | 2 | 3 | 4 | 5 | 6 | x$\geq$7 |
| :------- | :--- | :--- | :--- | :--- | :--- | :--- | :------- |
| $p(X=x)$ | 17 | 59 | 15 | 6 | 2 | 0 | 1 |

여기서 우리는 여러 사전 지식을 활용하여 해당 데이터를 보았을 때, 해당 분포가 Poisson 분포의 형태라는 것을 알 수 있다. 
따라서, 우리는 해당 분포를 Poisson이라고 가정한 다음에는 단순히 해당 분포에 대입하며, 가장 적절한 parameter만 찾으면 된다. 

이 과정과 단순히 각 x에서의 확률값을 구하는 방식이랑 무엇이 다른지를 알아야지 해당 과정의 의의를 알 수 있다.
먼저, 우리가 하고자 하는 일이 형제자매의 평균 수를 구한다고 하자. 이때의 평균 값과 Poisson 분포에서의 확률값은 다를 수 밖에 없다.

이렇게 확률 분포를 구하는 것의 의미는 이것말고도 보지 않은 데이터(unseen data)를 처리함에 있다. 우리가 만약 모든 가능한 경우의 수를 모두 알고 있고, 이를 저장할 공간이 충분하다면,
이러한 확률 분포를 구할 필요가 없다. 하지만, 우리가 원하는 추측은 unseen data에 대해서도 그럴사해야 한다. 이를 위해서는 결국 확률 분포가 필요하다.

위의 예시에서 만약, 형제자매가 3명인 경우의 데이터가 없다고 하자. 이 경우에도 확률분포를 통한 추측을 한다면, 우리는 유의미한 값을 구할 수 있는 것이다.

## Parametric Estimation

> **정의**

sample space $\Omega$에서 통계 실험의 관측 결과를 통해서 얻은 sample $X_1$, $X_2$, ... , $X_n$이 있다고 하자. 각 sample에 대한 확률 분포를 우리는 $p_\theta$라고 한다.
여기서 $\theta$는 특정 확률 분포에서의 parameter를 의미한다. 만약, bernoulli 라면, 단일 시행에 대한 확률이 될 것이고, binomial이라면, 단일 시행의 확률과 횟수가 해당 값이 될 것이다.

> **성능 평가**

여기서 우리가 찾기를 원하는 것은 전체 sample space $\Omega$를 모두 잘 표현할 수 있는 $\theta_{*}$(실제 true $\theta$)를 찾는 것이다.(이미 확률 분포의 형태(함수, ex. Bernoulli, Binomial)는 이미 정의되어 있다.) 
그렇다면, 실제 $\theta_*$와 추측을 통해 만든 $\hat{\theta}$ 사이의 비교를 위한 지표도 필요할 것이다. 즉, 우리가 만든 확률 분포의 예측 성능평가가 필요하다는 것이다. 이를 측정하기 위해서 우리는 **Risk**라는 것을 사용한다. 
간단하게도 실제 $\theta_*$와 $\hat{\theta}$의 Mean Square Error를 계산한다.

$$
\begin{align*}
Risk &= E[(\hat{\theta} - \theta_*)^2] = E[\hat{\theta}^2 - 2\hat{\theta}\theta_* + \theta_*^2] \\
&= E[\hat{\theta}^2] - 2\theta_*E[\hat{\theta}] + \theta_*^2 \\
&= E[\hat{\theta}^2] - 2\theta_*E[\hat{\theta}] + \theta_*^2 + (E^2[\hat{\theta}] - E^2[\hat{\theta}]) \\
&= (E[\hat{\theta}] - \theta_*)^2 + E[\hat{\theta}^2] - E^2[\hat{\theta}] \\
&= {Bias}^2 + Var[\hat{\theta}]
\end{align*}
$$

해당 식을 분석해보면, 이와 같은 의미로 해석하는 것이 가능하다. 우리가 특정 확률 분포의 파라미터를 단 하나로 단정하고 Risk를 계산하는 경우는 Variance 값은 0이다. 즉, 해당 확률 분포가 가지는 Risk는 단순히 해당 parameter와 실제 parameter가 얼마나 찾이가 나는가를 의미한다.

하지만, parameter를 특정하지 않고, 범위로 지정한다면, (예를 들어, 주사위를 던져 3이 나올 확률은 1/6 ~ 1/3이다.) 해당 확률의 평균과 Variance가 영향을 미칠 것이다. 
다소 처음에는 헷갈릴 수 있지만, 해당 식에서 평균이 의미는 잘 확인하자. 특정 확률 분포를 가지도록 하는 $\theta$가 $\theta_*$ 에 얼마나 근접한지를 확인하기 위한 식이라는 것을 다시 한 번 기억하자.

> **Estimation**

이제부터는 앞에서 살펴보았던, parameteric estimation에서 어떻게 $\hat{\theta}$를 구할 수 있는지를 다룰 것이다. 확률/통계 이론에서는 크게 3가지로 나눌 수 있다고 볼 수 있다. 각 각을 살펴보도록 하자.

**1. MLE**

Maximum Likelihood Estimation의 약자이다. 여기서, Likelihood는 가능성이라는 뜻을 가지며, 확률/통계 이론에서 이는 확률을 해당 사건이 발생할 가능성으로 해석하는 것이다. 이를 이용해서 우리가 풀고자 하는 문제, 우리가 추측한 $\theta$가 우리가 가진 Dataset를 만족시킬 가능성을 확인하기 위해 사용한다. 아래 수식을 보자.

$$
\begin{align*}
\mathcal{L}(\theta;\mathcal{D}) &= p(\mathcal{D}|\theta) = p(x_1, x_2, ..., x_n|\theta) \\
&= \prod_{i=1}^{n}{p(x_i|\theta)}
\end{align*}
$$

(위 식을 이해하려면, 먼저 Dataset의 각 data들은 서로 independent하다는 사실을 기억하자.) 
결국 $\theta$가 주어졌을 때, Dataset일 확률을 구하는 것이다. 이를 다시 생각하면, $\theta$가 얼마나 데이터셋의 확률을 잘 표현할 수 있는가와 같다.

이것을 직관적으로 이해하려면 하나의 예시를 보면 좋다.

![MLE example](/images/MLE-example.png)

첫 번째 그래프는 같은 가우시안 분포 함수를 쓰면서, parameter만 다르게 한 경우이고, 아래는 실제 데이터의 분포라고 하자.(빨간색 선 하나 하나가 데이터를 의미) 
이때, Likelihood를 각 각 구하면 각 x에서의 확률분포의 확률값을 모두 곱하면 된다. 그 경우 어떤 것이 제일 클지는 분명하다. 바로 파란색 분포일 것이다. 

그렇다면, 우리가 원하는 것은 무엇인가? 바로 가장 높은 가능성을 가지게 하는 $\theta$를 찾는 것이다. 따라서, 이를 식으로 표시하면 아래와 같다.

$$
\hat{\theta}_{MLE} = \argmax_{\theta}\mathcal{L}(\theta;\mathcal{D})
$$

여기서 하나 문제가 있을 수 있다. 바로, 컴퓨터로 연산하게 되면 underflow가 발생하는 것이다. 특정 언어가 계산할 수 있는 소수점 범위를 벗어난다면, 제대로 된 결과를 얻을 수 없다. 이와 같은 문제를 **vanishing likelihood**라고 한다. 
따라서, 우리는 log를 취했을 때와 log를 취하지 않았을 때의 경향성이 같음을 바탕으로 likelihood에 log를 취한 값을 이용하여 MLE를 구하는 것이 일반적이다. 이 방식을 maxmum log likelihood estimation 이라고 부른다.

$$
\mathcal{l}(\theta;\mathcal{D}) = \sum_{i=1}^{n}{\log{(p(x_i|\theta))}}
$$

이 방식을 이용하게 되면, 곱셈이 모두 덧셈으로 바뀌기 때문에 계산에서도 용이하다.

여기까지 살펴보면, 하나의 의문이 들 수도 있다. 바로, $p(\theta|\mathcal{D})$도 측정 기준으로 사용할 수 있지 않냐는 것이다. 이 역시도 Dataset이 주어질 때, $\theta$일 확률이라고 볼 수 있다. 
어찌보면, 사람의 생각으로는 이게 더 당연하게 느껴질 수도 있다. 이는 바로 다음 MAP에서 다룰 것이다. 우선 MLE를 먼저한 이유는 이것이 더 구하기 쉽기 때문임을 기억해두자.

```plaintext
 🤔 증명

 (*해당 내용은 정보 이론에 기반한 MLE에 대한 추가적인 이해를 위한 내용입니다. 해당 내용은 자세히 알 필요까지는 없습니다.)

 두 확률 분포 간 information Entropy의 차이를 나타내는 KL divergence의 최솟값을 구하는 것이 우리의 목표라고 정의할 수 있다. 
 따라서, 우리가 결국 얻고자 하는 것은 확률 분포 함수가 주어졌을 때, 
 n이 무한대로 갈 때, 경험적 확률(empirical probability)에 가장 근사하는 parameter를 찾는 것이다. 
 따라서, 우리는 KL divergence의 최솟값을 구하면 된다.
```

$$
\begin{align*}
\argmin_\theta KL(\tilde{p}||p_\theta) &= \argmin_\theta \int\tilde{p}(x)\log{\tilde{p}(x)\over{p_\theta(x)}}dx \\
&=\argmin_\theta[-\int\tilde{p}(x)\log{\tilde{p}(x)dx} - \int\tilde{p}(x)\log{p_\theta(x)dx}] \\
&= \argmax_\theta\int{\tilde{p}(x)\log{p_\theta(x)}dx} \\
&= \argmax_\theta\sum_{i=1}^{n}{\log{p_\theta(x_i)}} \\
&= \theta_{MLE}
\end{align*}
$$

**2. MAP**

Maximum A Posteriori의 약자이다. Posteriori는 사후 확률이라고도 부르며, dataset이 주어졌을 때, $\theta$일 확률을 구하는 것이다. 
이를 바로 구하는 것은 다소 어렵다. 왜냐하면, Dataset이 조건으로 들어가는 형태이기 때문이다. ($p(\theta|\mathcal{D})$) 
따라서, 우리는 Bayes' Theorem에 따라서 이전에 배운 Likelihood와 parameter의 확률, 그리고 Dataset의 확률을 활용히여 풀어낼 것이다.

$$
p(\theta|\mathcal{D}) = {p(\mathcal{D}|\theta)p(\theta)\over{p(\mathcal{D})}}
$$

여기서 주의해서 볼 것은 바로 $p(\theta|\mathcal{D})$와 $p(\theta)$의 관계이다. dataset이 주어질 때의 parameter의 확률을 구하기 위해서 원래 parameter의 확률이 필요하다는 것이다. 
어찌보면 굉장히 모순되어 보일 수 있지만, 우리가 이것을 사전 확률(priori)로 본다면 다르게 볼 여지가 있다. 
예를 들면, 우리가 수상한 주사위로 하는 게임에 참가한다고 하자. 이때, 우리는 수상한 주사위의 실제 확률은 알 수 없지만, 주사위 자체의 확률은 모두 1/6이라는 것을 알고 있다. 따라서, $p(\theta={1\over6}) = \alpha, p(\theta\neq{1\over6}) = \beta$ 라고 할 수 있다. 만약 정말 수상해보인다면, 우리는 $\alpha$가 점점 작아진다는 식으로 표현할 수 있고, 하나도 수상해보이지 않는 일반 주사위라면, $\alpha=1, \beta=0$으로 할 수도 있다. 이 경우에는 likelihood 값에 상관없이 다른 모든 값이 0이기 때문에 결국은 $p(\theta|\mathcal{D}) = p(\theta)$ 가 되는 것을 알 수 있다.

최종적으로, MAP도 결국은 Dataset을 얼마나 parameter가 잘 표현하는가에 대한 지표로 사용할 수 있다.
따라서, 이를 최대로 만드는 parameter는 $\theta_*$와 굉장히 근접할 것이다.

$$
\begin{align*}
\hat{\theta}_{MAP} &= \argmax_{\theta}p(\theta|\mathcal{D}) \\
&= \argmax_\theta{p(\mathcal{D}|\theta)p(\theta)\over{p(\mathcal{D})}} \\
&=\argmax_\theta{p(\mathcal{D}|\theta)p(\theta)} \\
&=\argmax_\theta{[\red{\log{p(\mathcal{D}|\theta)}} + \blue{\log{p(\theta)}}]}
\end{align*}
$$

MLE와 마찬가지로 이 또한 연산 및 **vanishing**을 막기 위해서 log를 취한다. 사실상 likelihood와 사전 확률의 합을 최대로 하는 $\theta$를 찾는 것이다.

**3. Bayesian Inference**

이제 마지막 방법으로 제시되는 Bayesian Inference이다. 이는 대게 Bayesian Estimation이라고 많이 불리는 것 같다. 이전까지 MLE, MAP는 결국 주어진 식을 최대로 하는 확정적 $\theta$ 하나를 구하는 것을 목표로 했다.

Bayesian Inference는 Dataset이 주어졌을 때, $\theta$의 평균값을 활용한다. 더 자세히 말하면, Posteriori(사후 확률)의 평균을 구하는 것이다. 
이를 구하는 과정을 살펴보면 이해하는데 도움이 될 것이다. 한 번 살펴보자.

$$
\begin{align*}
\hat{\theta}_{BE}&= E[\theta|\mathcal{D}] \\
&= {\int_{0}^{1}{{\theta}p(\theta|\mathcal{D})}d\theta} \\
&= {\int_{0}^{1}{\theta}{{p(\mathcal{D}|\theta)p(\theta)}\over{p(\mathcal{D})}}d\theta} \\
&= {{\int_{0}^{1}{\theta}{p(\theta)p(\mathcal{D}|\theta)}d\theta}\over{p(\mathcal{D})}} \\
&= {{\int_{0}^{1}{\theta}{p(\theta)\prod_{i=1}^{n}{p(x_i|\theta)}}d\theta}\over{p(\mathcal{D})}} \\
&= {{\int_{0}^{1}{\theta}{p(\theta)\prod_{i=1}^{n}{p(x_i|\theta)}}d\theta}\over{\int_0^1{p(\mathcal{D}|\theta)p(\theta)}d\theta}} \\
&= {{\int_{0}^{1}{\theta}{p(\theta)\prod_{i=1}^{n}{p(x_i|\theta)}}d\theta}\over{\int_0^1{p(\theta)\prod_{i=1}^{n}p(x_i|\theta)}d\theta}} \\
\end{align*}
$$

이를 구하는 과정은 이전과는 다르게 상대값이 아닌 평균을 구해야하기 때문에 posteriori(사후 확률,$p(\theta|\mathcal{D})$)를 구해야 한다.

하지만, 여기서 잡기술이 하나 존재한다. 바로 **Conjugate Prior**이다.

바로 두 확률 분포 함수(likelihood, prior)에 의한 posterior의 형태가 정해진 경우가 있기 때문이다.

| Prior $p(\theta \mid \alpha)$ | Likelihood $p(\mathcal{D} \mid \theta)$ | Posterior $p(\theta \mid \mathcal{D}, \alpha)$ | Expectation of Posterior |
| :----------------------------- | :------------------------------------------------------ | :--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | :----------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| Beta ($\alpha, \beta$) | Benoulli ($\sum _{i=1}^{n}x_{i}$) | Beta ($\alpha +\sum _{i=1}^{n}x_{i},\,\beta +n-\sum _{i=1}^{n}x_{i}$) | ${{\alpha + \sum _{i=1}^{n}x_{i}}\over{\alpha + \beta + n}}$ |
| Beta ($\alpha, \beta$) | Binomial ($\sum _{i=1}^{n}N_{i}, \sum _{i=1}^{n}x_{i}$) | Beta ($\alpha +\sum _{i=1}^{n}x_{i},\,\beta +\sum _{i=1}^{n}N_{i}-\sum _{i=1}^{n}x_{i}$) | ${{\alpha + \sum _{i=1}^{n}x_{i}}\over{\alpha + \beta + \sum _{i=1}^{n}N_{i}}}$ |
| Gaussian ($\mu_0, \sigma_0^2$) | Gaussian ($\mu, \sigma^2$) | Gaussian (${\displaystyle {\frac {1}{{\frac {1}{\sigma _{0}^{2}}}+{\frac {n}{\sigma ^{2}}}}}\left({\frac {\mu_{0}}{\sigma _{0}^{2}}}+{\frac {\sum_{i=1}^{n}x_{i}}{\sigma ^{2}}}\right),\left({\frac {1}{\sigma_{0}^{2}}}+{\frac {n}{\sigma ^{2}}}\right)^{-1}}$) | ${\displaystyle {\frac {1}{{\frac {1}{\sigma _{0}^{2}}}+{\frac {n}{\sigma ^{2}}}}}\left({\frac {\mu_{0}}{\sigma _{0}^{2}}}+{\frac {\sum_{i=1}^{n}x_{i}}{\sigma ^{2}}}\right)}$ |

이를 이용하면, 우리는 간단하게 Posteriori의 평균을 구할 수 있다.

## Reference

- Tumbnail : Photo by [Markus Winkler](https://unsplash.com/@markuswinkler?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText) on [Unsplash](https://unsplash.com/@markuswinkler?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText)