[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

## 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

이전 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)