Mixture of Gaussian Density Estimation (MoG)

-
 03_2 : Anomaly Detection : (Mixture of) Gaussian Density Estimation

이전까지 normal data가 하나의 가우시안 분포로 부터 생성된다고 가정하였다. 하지만 하나의 가우시안만을 사용하는 것은 너무 엄격하다.(Strong model : uni-modal and convex)
때문에 여러개의 가우시안 분포의 혼합(multi-modal)을 사용하여 설명하려고 한다.

Mixture of Gaussian (MoG) Density Estimation

Mixture of Gaussian(MoG)는 여러개의 가우시안 분포의 선형 결합으로 이루어진다. 덕분에 이전의 하나의 가우시안을 사용하는 경우보다 더 bias가 적게 추정이 가능하다. 하지만 좀 더 많은 Training data를 필요로 한다.
$$f(x) = w_1N(\mu_1,\sigma_1^2) + w_2N(\mu_2,\sigma_2^2) + w_3N(\mu_3,\sigma_3^2)$$
이전의 방법에서는 $\mu$와 $\sigma$ 2개의 미지수를 추정하면 되었지만, $K$개의 가우시안을 혼합하는 MoG의 경우에는 각 가우시안 마다 $w_i,\,\mu_i,\,\sigma_i$ 3개씩 총 $3K$개의 미지수, 그리고 몇개의 가우시안을 사용할지 $K$까지 학습을 통해 추정해야 한다.


Components of MoG

  • Probability of an instance belonging to the normal class
$$p(x|\lambda) = \sum_{m=1}^M w_m g(x|\mu_m,\Sigma_m)$$
$$\lambda = \{w_m,\mu_m,\Sigma_m\},\;\;\;\;\;m=1,\cdots,M$$
  • Distribution of each Gaussian model
$$g(x|\mu_m,\Sigma_m) = \frac{1}{(2\pi)^{d/2}|\Sigma_m|^{1/2}}\exp{\big[\frac{1}{2}(x-\mu_m)^T\Sigma_m^{-1}(x-\mu_m)\big]}$$
$\lambda$는 미지수의 집합이고, 이때 $M$은 가우시안의 개수이다. 위 식의 의미를 살펴보자. 객체 $x$가 normal 일 확률 $p(x|\lambda)$는 각각의 가우시안 함수의 likelihood $g(x|\mu_m,\Sigma_m)$를 계산하여, 가중치 $w_m$를 곱하여 모두 더한 값이 된다.


Expectation-Maximization Algorithm

위와 같이 변수가 많은 저 예시에서 어떻게 미지수를 추정할지 막막하다. 가우시안 함수 하나만을 사용하는 경우 Convex함이 보장됨으로 바로 최적해를 찾으면 되지만, MoG의 경우 Convex를 보장할 수 없다. 이러한 미지수를 알아내는 최적화 문제에서 가장 흔하게 사용되는 기댓값 최대화 알고리즘(Expectation-Maximization Algorithm)을 사용해보자.

우리가 최적해를 찾아야 하는 문제의 미지수 집합 A와 B가 있다고 생각해보자. 동시에 A, B를 모두 최적화를 할 수 없다면, 아래와 같이 최적해를 찾을 수 있다.
  1. A 미지수 고정 $\rightarrow$ B 최적화
  2. B 미지수 고정 $\rightarrow$ A 최적화
  3. A 미지수 고정 $\rightarrow$ B 최적화
  4. B 미지수 고정 $\rightarrow$ A 최적화
  5. ... 수렴할 때까지 반복
MoG 문제에 적용해보자. 우리가 찾아야 하는 미지수는 $w_m,\mu_m,\Sigma_m$이다. 그리고 어떤 객체 $x$가 있을 때 $x$가 $m$번째 가우시안으로 표현될 확률 $p(m|x)$를 구하려 한다.

Expectation-Maximization Algorithm의 과정은 E-Step, M-Step 두 단계로 나누어진다.
  • E-Step (Expectation)
Given the current estimate of the parameters, compute the conditional probabilities.
가우시안의 미지수 $w_m,\mu_m,\Sigma_m$을 고정하고, 객체의 확률 $p(m|x)$를 계산한다.
  • M-Step (Maximization)
Update the parameters to maximize the expected likelihood found in the E-Step
객체의 확률 $p(m|x)$를 고정하고, 가우시안의 likelihood가 최대값을 가지도록 미지수 $w_m,\mu_m,\Sigma_m$를 계산한다.

$M=2$인 경우, 실제 시뮬레이션을 보면 처음에는 부적절한 가우시안 분포를 보이지만 알고리즘이 진행됨에 따라 적절한 분포로 수렴하는 것을 확인할 수 있다.
우리는 몇개의 가우시안 분포($M$)를 사용하는 것이 최적인지 모른다. 따라서 $M$값을 바꿔가면서 Expectation-Maximization Algorithm을 수행하고, likelihood가 가장 높은 $M$값을 선택한다.

수식으로 살펴보자.
  • E-Step (Expectation)
$$p(m|x_i,\lambda) = \frac{w_m g(x_i|\mu_m,\Sigma_m)}{\sum_{k=1}^M w_k g(x_t|\mu_k,\Sigma_k)}$$
  • M-Step (Maximization)
    • Mixture weight
$$w_m^{(new)} = \frac{1}{N}\sum_{i=1}^N p(m|x_i,\lambda)$$
    • Means
$$\mu_m^{(new)} = \frac{\sum_{i=1}^N p(m|x_i,\lambda)x_i}{\sum_{i=1}^N p(m|x_i,\lambda)}$$
    • Variances
$$\sigma_m^{2(new)} = \frac{\sum_{i=1}^N p(m|x_i,\lambda)x_i^2}{\sum_{i=1}^N p(m|x_i,\lambda)} - \mu_m^{2(new)}$$

정리하자면 모든 미지수가 수렴할 때까지 E-Step과 M-Step을 반복하여, 최적값을 찾는다.


Covariance matrix

Gaussian Density Estimation 처럼 MoG 또한 어떤 공분산행렬을 사용하는지에 따라서 가우시안 함수의 모양이 달라진다.
  • Spherical
$$\sigma^2 = \frac{1}{d}\sum_{i=1}^d\sigma_{i}^2\;\;\Sigma = \sigma^2\begin{equation*} \begin{bmatrix} 1&\cdots & 0\\ \vdots & \ddots & \vdots \\ 0 & \cdots & 1 \end{bmatrix}\end{equation*}$$
  • Diagonal
$$\Sigma = \begin{equation*} \begin{bmatrix} \sigma_1^2&\cdots & 0\\ \vdots & \ddots & \vdots \\ 0 & \cdots & \sigma_d^2 \end{bmatrix}\end{equation*}$$
  • Full
$$\Sigma = \begin{equation*} \begin{bmatrix} \sigma_{11}^2&\cdots & \sigma_{1d}^2\\ \vdots & \ddots & \vdots \\ \sigma_{d1}^2& \cdots & \sigma_{dd}^2 \end{bmatrix}\end{equation*}$$

MoG역시 Full 형태의 공분산 행렬을 사용하면 가장 좋은 성능을 보이겠지만, singular matrix가 되어서 역행렬이 없는 경우가 생길 수 있다. 또한 계산량이 너무 많아질 수 있다. 때문에 일반적으로 Diagonal형태의 공분산 행렬을 많이 사용한다.



※ 이 글은 고려대학교 산업경영공학과 강필성 교수님의 IME654 강의를 정리하고, 공부한 내용을 추가하여 작성되었습니다.

댓글

댓글 쓰기

이 블로그의 인기 게시물

One-Class SVM & SVDD

-
이미지
03_6 : Anomaly Detection : Auto-Encoder, 1-SVM, SVDD MoG와 같은 밀도기반 방법론들은 특정 객체가 정상범주에 속할 확률을 구했다. 반면 Support vector 기반 방법론들은 normal과 abnormal을 구분하는 분류경계면을 찾는다. 이번 글에서는 Support vector 기반의 Anomaly detection 방법 중 one-class SVM과 SVDD를 알아보자. One-class Support Vector Machine (1-SVM, OCSVM) 1-SVM의 목표는 Data를 feature space로 mapping 한 뒤, 분류경계면을 통해 mapping된 Data 중 normal data들이 원점으로부터 최대한 멀어지게 만드는 것이다. 위 그림에서 파란색 분류경계면이 (+1) normal data들을 구분하는 것을 확인할 수 있다. 이 목표를 수식화 한 Optimization problem부터 살펴보자. Optimization Problem $$\min_{\textbf{w}}\;\;\;\frac{1}{2}||\textbf{w}||^2 + \frac{1}{\nu l} \sum_{i=1}^l \xi_i - \rho$$ $$s.t.\;\;\;\textbf{w}\cdot \Phi (x_i) \geq \rho - \xi_i\;\;\;\;(i=1,2,\cdots,l),\;\;\xi_i\geq 0$$ $\frac{1}{2}||\textbf{w}||^2$ term은 SVR과 같이 $x$의 변화에 따른 변동이 크지 않도록 Regularization을 하는 term이다. $\rho$는 위 그림에서 주황 직선을 나타내는데, 원점과 분류경계면 Hyperplane과의 거리를 나타낸다. 이 값을 뺌으로써 최소화 문제를 만족하는 최적해일때 $\rho$가 최대가 되도록 한다. (원점에서 Hyperplane이 최대한 멀어지게 만든다) $\frac{1}{\nu l} \sum_{i=1}^l \xi_i$ term은 제약식에 따라 Hyp...
자세한 내용 보기

Support Vector Regression (SVR)

-
이미지
02_4 : Kernel based learning : Support Vector Regression (SVR) 앞에서 공부했던 SVM은 binary classification을 하기 위한 방법이었다. 이번 글에서 알아볼 SVR은 함수를 추정하여 연속적인 수치변수를 예측하는 회귀 방법이다.  SVR을 알아보기에 앞서 우리가 하려는 함수추정의 목적을 살펴보자. Fitting function 함수를 추정하고 싶을 때 우리의 목적은 크게 2가지로 나뉜다. Minimize an error measure (Loss function) 한마디로 error를 최소화 하여야 한다. (잘 맞춰야 한다) Function to be simple 같은 성능이라면, 함수는 최대한 단순해야 한다. 함수가 단순하다는 뜻은 아래의 조건들을 의미한다. Fewest basis functions Simplest basis functions Flatness is desirable Support Vector Regression (SVR) 위에서 살펴보았던 Loss function과 Flatness를 반영하도록 목적함수를 만들 것이다. SVR에도 여러 종류가 있는데, 우선 $\varepsilon$-SVR에 대하여 알아보자. 현실의 Data들은 어쩔 수 없이 발생하는 noise가 존재한다. 아래 식에서 noise는 $\varepsilon$이다. $$y = f(x)+\varepsilon$$ $\varepsilon$-SVR에서 핵심 아이디어는 $\varepsilon$ 보다 작은 noise에 대해서는 Loss를 주지 말자는 것이다.  왼쪽 그림에서 색이 칠해진 영역을 Epsilon-tube 라고 하는데, 이 영역안에 있는 객체들에게는 Loss를 부여하지 않는다. 이를 위한 Loss function은 오른쪽에 표현된다. 이 Loss function은 hinge를 닮았다고 해서, Hinge Loss 라고 불린다. 차이가 $\varepsilon$ 보다 작은 경우 loss는 0이고, $\vareps...
자세한 내용 보기

Self-Training & Co-Training

-
이미지
 05_2 : Semi-Supervised Learning : Self-Training and Co-Training 우선 가장 기본적인 준지도학습 방법 Self-Training에 대하여 알아보자.  Self-Training 우리에게 주어진 정보는 Labeled data $(\mathbf{X}_l,y_l)$과 Unlabeled data $\mathbf{X}_u$이다. Self-training과정은 다음과 같이 진행된다.  1. 우선 주어진 Labeled data $(\mathbf{X}_l,y_l)$를 사용하여 예측함수 $f$를 학습시킨다. $$y_l = f(x_l)$$ 2. 학습이 완료되면, 예측함수 $f$를 사용해 Unlabeled data $\mathbf{X}_u$의 예측값 $\hat{y}_u$를 구한다. $$\hat{y}_u = f(x_u)$$ $$\Downarrow$$ 3. 이제 기존의 Labeled data와 예측함수에 의해 labeling이 된 Unlabeled data를 합치고, 이 data를 사용해 예측함수 $g$를 학습한다. 이때 어떻게 Unlabeled data를 합치는지에 따라서 많은 variation이 있다. 대표적으로 Add all $(x_u,\hat{y}_u)$ to labeled data Add a few most confident $(x_u,\hat{y}_u)$ to labeled data Add all $(x_u,\hat{y}_u)$ to labeled data, weight each by confidence. 모든 Unlabeled data를 합치는 방법, 몇몇개의 가장 예측 confidence가 높은 data만을 합치는 방법, 모든 data를 합치치만 예측 confidence에 따라서 weight를 지정하는 방법 등이 있다. 4. 위와 같은 과정을 Unlabeled data가 없어지거나, 수렴할 때 까지 반복한다. Propagating 1-Nearest Neighbor 다른 예시로 Propagating ...
자세한 내용 보기