혼합 모델

혼합 모델(Mixture model)은 통계학에서 전체 집단안의 하위 집단의 존재를 나타내기 위한 확률 모델이다. 좀 더 형식적으로는 전체 집단의 확률 분포를 나타내는 혼합 분포(Mixture distribution)에 해당한다. 그러나 "혼합 분포"와 관련된 문제들은 하위 집단들로부터 전체 집단의 특징들을 얻는 것에 관련된 반면, "혼합 모델"들은 관찰된 집단이 주어졌을 때 하위 집단들의 특징들에 대해 통계적 추론을 하기 위해 쓰인다.

혼합 모델의 좀더 구체적인 사용 용도로는, 만약 관찰된 변수와 잠재 변수의 결합 분포를 정의한다면, 관찰된 변수들의 분포는 모든 잠재 변수에 대해 주변화(marginalize)함으로써 구할 수 있다. 이렇게 함으로써 관찰된 변수의 복잡한 분포를 잠재변수를 사용하여 더 단순하게 표현할 수 있다. 혼합 모델은 이러한 잠재변수를 가정하여 복잡한 분포를 추정하는데 사용된다. 또, 혼합 모델은 데이터를 군집화(clustering)하는 데 쓰일 수 있다.^[1]

잠재 변수를 포함하는 모델의 최대 우도 추정(Maximum likelihood estimation)을 위해서는 기대값 최대화(expectation-maximization) 알고리즘이 사용된다. 가우스 혼합 모델은 데이터마이닝, 패턴 인식, 머신 러닝, 통계분석 등에 광범위하게 쓰인다. 이 때 모델의 파라미터들은 EM 알고리즘을 통해 구한다.

혼합 모델의 배경

지도학습과 비지도 학습

지도학습(supervised learning)

관측된 자료가 특징 벡터 x 와 관측 값이 속해있는 클래스 ω 로 이루어진 변수 쌍 {x, ω}으로 구성될 경우의 학습은 특징벡터와 정확한 답이 주어졌기 때문에 교사/감독/지도(supervised: 교사와 함께 훈련한/교사가 지도한) 학습이라고 한다.

비지도학습(unsupervised learning)

클래스 라벨 ω 가 주어지지 않고 특징 벡터 x={x1, x2,...,xN } 만으로 이루어진 데이터 집합이 주어질 경우의 학습은 정확한 답은 제공 받지 못하므로 비교사/무감독/비지도 (unsupervised: 교사 없이 훈련한) 학습이라고 한다.

비지도 학습의 두 가지 접근법

• 모수적(parametric) 방법(혼합모델을 사용하는 방법)

이 방법은 여러 개의 모수적 확률밀도함수(주로 가우스)를 혼합하여 주어진 확률밀도함수를 모델링하는 방법으로 아래 식과 같이 모델링 되며, 모델 파라미터를 찾는 것이 목적이다. 이 방법을 “모수적 혼합 모델(parametric mixture models)”이라고 한다.

비지도 학습의 접근법 중 모수적(parametric) 방법의 대표적 방법인 가우스 혼합 모델 그래프

• 비모수적(non-parametric) 방법

이 방법은 주어진 데이터에 대한 어떠한 가정도 하지 않고 정해진 수의 클러스터들로 데이터를 나누는 방법으로 군집화 (클러스터링)라고 한다. 이 방법은 파라미터 최우추정(MLE)과 밀접하게 관련되어 있다.

클러스터 구분의 최적화 규준

클러스터링을 통해 데이터들을 클래스로 분류를 하게 되면 오차가 발생하게 된다. 클래스의 중심이 되는 값(클래스 내에 가장 밀도가 높은 지점)과 그 클래스로 분류된 데이터간의 차가 최소가 되도록 하는 것이 최적화 과정이다. 이 때 특징 벡터 x의 개수(N)는 항상 클래스의 개수(K)보다 훨씬 많고 서로 관계는 대부분 비선형이므로 직접적으로 최적의 값을 찾는 것은 불가능하다. 따라서 반복적인 최적화 과정을 통해 오차를 최소화 할 수 있다.

군집화에서 고려해야하는 중요한 문제점

1) 최적의 클래스(확률분포모델) 개수는 몇 개 인가?(K의 개수 결정)

2) 주어진 데이터에서 가장 근접한 클래스(확률분포모델)는 무엇인가?(클러스터링 과정)

3) 오차가 가장 최소가 되는 클래스(확률분포모델)는 무엇인가?(클래스 특징을 변화)

위의 3가지 문제를 고려하여 클래스 구성과 최적화 과정을 EM알고리즘을 통하여 진행한다.

K-means 알고리즘을 통하여 반복 수행하여 각 데이터들이 최소 오차를 가지는 군집으로 나뉘어 진다

^[2]

혼합 모델의 구조

일반적인 혼합 모델

일반적인 유한 차원의 혼합 모델은 다음의 구성요소로 이루어진 계층적 베이즈 모델이다. :

• N 관측에 대응 되는 확률 변수, 각각의 관측은 'K'개의 요소의 혼합에 의해 분포되어 있다고 가정한다. 각 구성요소는 같은 parametric family를 공유하는 확률 분포에 속한다. (즉, 모두 가우스 분포이거나 모두 Zipfian 분포에 속하는 등.)
• N 개의 잠재 변수들은 각각의 관측결과에 대해서, 혼합 구성요소의 존재를 나타낸다. 각각은 K 차원의 다항 분포를 따라 분포한다.
• K 개의 혼합 가중치 집합. 각각은 합이 1이 되는 확률값이다.
• K 개의 파라미터 집합, 각각은 대응되는 혼합 구성요소의 파라미터를 나타낸다. 예를 들어, 1차원 가우스 분포의 혼합에 따라 분포된 관측 결과들은 각 구성요소마다 평균과 분산값이 있다. 또, V차원 다항 분포의 혼합에 따르는 관측(예를 들어, 각 관측결과가 V개의 단어집합에 속하는 단어일 경우)은 V개의 확률 값을 가지는 벡터를 가진다. (전체적인 확률 값의 합은 1이 되어야 한다.)

추가적으로, 베이지안 세팅에서는 혼합 가중치와 파라미터들 자체가 확률 변수이며, 그러한 변수들에 대한 사전확률이 정의되어야 한다. 그런 경우에 가중치들은 보통 디리클레 분포로부터 뽑은 K차원의 랜덤 벡터라고 간주한다. (디리클레 분포는 다항 분포의 conjugate prior이다.) 따라서 파라미터들은 해당하는 conjugate prior에 따라 분포 될 것이다.

수학적으로, 기본적인 파라미터 혼합 모델은 다음과 같이 나타낼 수 있다 :

• ${\displaystyle K=}$ 혼합 구성요소의 수
• ${\displaystyle N=}$ 관측 데이터의 수
• ${\displaystyle \theta _{i=1\dots K}=}$ 구성요소와 연관된 관측의 분포의 매개변수
• ${\displaystyle \phi _{i=1\dots K}=}$ 혼합 가중치 즉, 특정 구성요소의 사전 확률
• ${\displaystyle \phi _{1\dots K}}$로 이루어진 ${\displaystyle {\boldsymbol {\phi }}=K}$ 차원의 벡터 </math>
• ${\displaystyle z_{i=1\dots N}=}$ 관측 데이터 i의 구성 요소
• ${\displaystyle x_{i=1\dots N}=}$ 관측 데이터 i
• ${\displaystyle F(x|\theta )=}$ 관측의 확률 분포 매개변수 ${\displaystyle \theta }$

${\displaystyle {\begin{array}{lcl}z_{i=1\dots N}&\sim &\operatorname {Categorical} ({\boldsymbol {\phi }})\\x_{i=1\dots N}&\sim &F(\theta _{z_{i}})\end{array}}}$

베이지안 세팅에서, 모든 파라미터들은 확률 변수와 다음과 같이 연관되어 있다. :

• ${\displaystyle K,N=}$ 위와 같음
• ${\displaystyle \theta _{i=1\dots K},\phi _{i=1\dots K},{\boldsymbol {\phi }}=}$ 위와 같음
• ${\displaystyle z_{i=1\dots N},x_{i=1\dots N},F(x|\theta )=}$ 위와 같음
• ${\displaystyle \alpha =}$ 구성요소 매개변수에 대한 공유 하이퍼 매개변수
• ${\displaystyle \beta =}$ 혼합 가중치에 대한 하이퍼 매개변수
• ${\displaystyle H(\theta |\alpha )=}$ 매개변수를 ${\displaystyle \alpha }$로 하는 구성요소 매개변수의 사전 확률

${\displaystyle {\begin{array}{lcl}\theta _{i=1\dots K}&\sim &H(\theta |\alpha )\\{\boldsymbol {\phi }}&\sim &\operatorname {Symmetric-Dirichlet} _{K}(\beta )\\z_{i=1\dots N}&\sim &\operatorname {Categorical} ({\boldsymbol {\phi }})\\x_{i=1\dots N}&\sim &F(\theta _{z_{i}})\end{array}}}$

데이터가 정규분포 혼합모델에서 관측되었다고 가정하고(모수적방법), EM알고리즘을 통해 매개변수들을 추정하는 과정이다. EM알고리즘을 반복하면서 매개변수들이 수렴하고 두개의 군집으로 나타나는 것을 확인 할 수 있다.

위와 같은 정의에서 F와 H는 각각 관찰과 파라미터에 대한 임의의 분포를 묘사하기 위해 사용된다. 보통 H는 F의 conjugate prior이다. F분포의 가장 흔한 선택 두가지로는 가우스 분포(실수값을 가지는 관측) 그리고 다항 분포(이산적인 값을 가지는 관측)가 있다. 혼합 구성요소로 가능한 다른 일반적인 분포들로는 다음과 같은 것들이 있다. :

• 이항 분포, 고정된 수의 전체 발생 중에서 어떤 사건이 일어나는 횟수
• 다항 분포, 이항 분포와 비슷하나, 두가지 사건이 아닌 여러 가지 사건중에 하나가 일어나는 횟수
• 음이항 분포(Negative binomial distribution), 이항 분포와 같은 관측상황 하에서 주어진 성공 횟수가 일어나기 위해서 일어난 실패 횟수
• 푸아송 분포, 주어진 기간동안 특정 사건이 일어나는 횟수 (사건이 일어나는 비율 고정되어 있을 때)
• 지수분포, 다음 사건이 일어나기 까지의 시간 (사건이 일어나는 비율 고정되어 있을 때)
• 로그 정규분포, 지수적으로 증가하는 실수 값 (수입이나 가격)
• 다변량 정규분포 결과가 관련되어 있는 벡터 값 , 각 값들은 가우스 분포를 가진다.

구체적인 예

가우스 혼합 모델

plate notation을 사용하여 나타낸 비(非)베이지안 혼합모델. 작은 사각형들은 고정된 파라미터들을 나타낸다. 큰 사각형들은 확률변수를 나타낸다. 색이 채워진 도형들은 알려진 값을 나타낸다. [K]는 사이즈 K인 벡터를 의미한다.

대표적인 비(非)베이지안 혼합모델은 다음과 같다.

• ${\displaystyle K,N=}$ 위와 같음
• ${\displaystyle \phi _{i=1\dots K},{\boldsymbol {\phi }}=}$ 위와 같음
• ${\displaystyle z_{i=1\dots N},x_{i=1\dots N}=}$ 위와 같음
• ${\displaystyle \mu _{i=1\dots K}=}$ 구성 요소 i의 평균
• ${\displaystyle \sigma _{i=1\dots K}^{2}=}$ 구성 요소 i의 분산

${\displaystyle {\begin{array}{lcl}z_{i=1\dots N}&\sim &\operatorname {Categorical} ({\boldsymbol {\phi }})\\x_{i=1\dots N}&\sim &{\mathcal {N}}(\mu _{z_{i}},\sigma _{z_{i}}^{2})\end{array}}}$

plate notation을 사용하여 나타낸 베이지안 가우스 혼합 모델. 작은 사각형은 고정된 파라미터를 뜻한다. 큰 원들은 확률 변수를 의미한다. 색이 채워진 도형들은 알려진 값을 나타낸다. [K]는 사이즈 K인 벡터를 의미한다.

베이지안 버전의 가우스 혼합 모델은 다음과 같다.

• ${\displaystyle K,N=}$ 위와 같음
• ${\displaystyle \phi _{i=1\dots K},{\boldsymbol {\phi }}=}$ 위와 같음
• ${\displaystyle z_{i=1\dots N},x_{i=1\dots N}=}$ 위와 같음
• ${\displaystyle \mu _{i=1\dots K}=}$ 구성 요소 i의 평균
• ${\displaystyle \sigma _{i=1\dots K}^{2}=}$ 구성 요소 i의 분산
• ${\displaystyle \mu _{0},\lambda ,\nu ,\sigma _{0}^{2}=}$ 공유되는 하이퍼 매개변수

${\displaystyle {\begin{array}{lcl}\sigma _{i=1\dots K}^{2}&\sim &\operatorname {Inverse-Gamma} (\nu ,\sigma _{0}^{2})\\{\boldsymbol {\phi }}&\sim &\operatorname {Symmetric-Dirichlet} _{K}(\beta )\\z_{i=1\dots N}&\sim &\operatorname {Categorical} ({\boldsymbol {\phi }})\\x_{i=1\dots N}&\sim &{\mathcal {N}}(\mu _{z_{i}},\sigma _{z_{i}}^{2})\end{array}}}$

다변량 가우스 혼합 모델

베이지안 가우스 혼합 모델은 흔히 미지의 파라미터 벡터에 적용될 수 있도록 확장되거나, 다변량 정규 분포로 확장된다. 다변량 분포에서(즉 N 개의 확률 변수를 모델링할 때, ${\displaystyle {\boldsymbol {x}}}$ ), 파라미터 벡터를 모델링할 때, 다음과 같이 가우스 혼합 모델 사전 분포를 사용하여 추정 할 수 있다.

${\displaystyle p({\boldsymbol {\theta }})=\sum _{i=1}^{K}\phi _{i}{\mathcal {N}}({\boldsymbol {\mu _{i},\Sigma _{i}}})}$

벡터의 i^th 요소는 가중치 ${\displaystyle \phi _{i}}$, 평균 ${\displaystyle {\boldsymbol {\mu _{i}}}}$ 그리고 공분산 ${\displaystyle {\boldsymbol {\Sigma _{i}}}}$을 갖는다. . 이러한 사전 확률을 베이지안 추론에 통합하기 위해서, 사전 확률은 조건부 ${\displaystyle {\boldsymbol {\theta }}}$ 데이터 ${\displaystyle {\boldsymbol {x}}}$의 알려진 분포 ${\displaystyle p({\boldsymbol {x|\theta }})}$와 곱해져야 한다. 이러한 공식하에서 posterior ${\displaystyle p({\boldsymbol {\theta |x}})}$확률 역시 다음과 같은 형태의 가우스 혼합 모델이다.

${\displaystyle p({\boldsymbol {\theta |x}})=\sum _{i=1}^{K}{\tilde {\phi _{i}}}{\mathcal {N}}({\boldsymbol {{\tilde {\mu _{i}}},{\tilde {\Sigma _{i}}}}})}$

새로운 파라미터들은 ${\displaystyle {\tilde {\phi _{i}}},{\boldsymbol {\tilde {\mu _{i}}}}}$ and ${\displaystyle {\boldsymbol {\tilde {\Sigma _{i}}}}}$ EM 알고리즘을 이용해서 업데이트된다. ^[3] EM 기반의 파라미터 업데이트 방식들을 사용하는 방법은 이미 잘알려져있지만, 이러한 파라미터들의 초기 추정치를 알아내는 것은 현재에도 활발하게 연구되고 있다. 이러한 공식화는 complete posterior 분포의 closed-form 해를 구할 수 있게 한다. 확률 변수${\displaystyle {\boldsymbol {\theta }}}$의 추정치들은 여러개의 posterior 분포의 최댓값이나 평균 등의 추정자들 중 하나로 구할 수 있다.

다항 혼합 모델

Non-Bayesian categorical mixture model using plate notation. 작은 사각형은 고정된 파라미터를 뜻한다. 큰 원들은 확률 변수를 의미한다. 색이 채워진 도형들은 알려진 값을 나타낸다. [K]는 사이즈 K인 벡터를 의미한다.

대표적인 다항 분포의 비(非)베이지안 혼합 모델 관측은 다음과 같다.

• ${\displaystyle K,N:}$ 위와 같음
• ${\displaystyle \phi _{i=1\dots K},{\boldsymbol {\phi }}:}$ 위와 같음
• ${\displaystyle z_{i=1\dots N},x_{i=1\dots N}:}$ 위와 같음
• ${\displaystyle V:}$ 다항 관측의 차원 (예, 단어의 수)
• ${\displaystyle \theta _{i=1\dots K,j=1\dots V}:}$ 구성요소 ${\displaystyle i}$ 가 데이터 ${\displaystyle j}$ 을 관측할 확률
• ${\displaystyle {\boldsymbol {\theta }}_{i=1\dots K}:}$ ${\displaystyle \theta _{i,1\dots V};}$로 이루어진 ${\displaystyle V,}$차원 벡터, 합이 1이 되어야 함.

확률 변수들은 다음과 같다.:

${\displaystyle {\begin{array}{lcl}z_{i=1\dots N}&\sim &\operatorname {Categorical} ({\boldsymbol {\phi }})\\x_{i=1\dots N}&\sim &{\text{Categorical}}({\boldsymbol {\theta }}_{z_{i}})\end{array}}}$

Bayesian categorical mixture model using plate notation. 작은 사각형은 고정된 파라미터를 뜻한다. 큰 원들은 확률 변수를 의미한다. 색이 채워진 도형들은 알려진 값을 나타낸다. [K]는 사이즈 K인 벡터를 의미한다.

대표적인 다항 분포의 베이지안 혼합 모델 관측은 다음과 같다.

• ${\displaystyle K,N:}$ 위와 같음
• ${\displaystyle \phi _{i=1\dots K},{\boldsymbol {\phi }}:}$ 위와 같음
• ${\displaystyle z_{i=1\dots N},x_{i=1\dots N}:}$ 위와 같음
• ${\displaystyle V:}$ 다항 관측의 차원 (예, 단어의 수)
• ${\displaystyle \theta _{i=1\dots K,j=1\dots V}:}$ 구성요소 ${\displaystyle i}$ 가 데이터 ${\displaystyle j}$ 을 관측할 확률
• ${\displaystyle {\boldsymbol {\theta }}_{i=1\dots K}:}$ ${\displaystyle \theta _{i,1\dots V};}$로 이루어진 ${\displaystyle V,}$차원 벡터, 합이 1이 되어야 함.
• ${\displaystyle \alpha :}$ 각 구성요소에 대한 공유 집중 하이퍼 매개변수 ${\displaystyle {\boldsymbol {\theta }}}$
• ${\displaystyle \beta :}$ 집중 하이퍼 매개변수 ${\displaystyle {\boldsymbol {\phi }}}$

확률 변수들은 다음과 같다.:

${\displaystyle {\begin{array}{lcl}{\boldsymbol {\phi }}&\sim &\operatorname {Symmetric-Dirichlet} _{K}(\beta )\\{\boldsymbol {\theta }}_{i=1\dots K}&\sim &{\text{Symmetric-Dirichlet}}_{V}(\alpha )\\z_{i=1\dots N}&\sim &\operatorname {Categorical} ({\boldsymbol {\phi }})\\x_{i=1\dots N}&\sim &{\text{Categorical}}({\boldsymbol {\theta }}_{z_{i}})\end{array}}}$

식별성(Identifiability)

정의

• 식별성은 특정 클래스에서의 어떠한 모델에 대해서 고유의 특성의 존재를 말한다. 모델이 식별 가능하지 않다면, 추정 과정이 잘 정의되지 않거나 점근적 이론(Asymptotic theory)이 성립하지 않을 수 있다.

예시

• 잠재 변수 모델(Latent variable model)에 대한 p(θ|D)를 계산할 때 생기는 문제는 사후확률이 다수의 봉우리를 포함한(multi-modal) 형태로 표현될 수도 있다는 것이다.
  • 그 예로 가우스 혼합 모델을 고려해보자. 만약 ${\displaystyle z_{i}}$값(각 가우스 분포의 비중)을 모두 알고 있다면, 매개변수 D를 이용하여 단봉형의 사후확률을 얻을 수 있다.
  • ${\displaystyle p(\theta |D)=p(\pi |D)\prod _{k=1}^{K}N(\mu _{k},\Sigma _{k}|D)}$
  • 그 결과, 전역적인 최적의 최대 사후확률 추정(MAP)을 쉽게 구할 수 있다.
  • 만약 ${\displaystyle z_{i}}$값을 모른다면, ${\displaystyle z_{i}}$값을 채워 넣는 방법에 따라 다른 단봉형의 우도를 얻게 된다. 그래서 ${\displaystyle z_{i}}$ 변수를 통합하여 식에서 제거한다면, p(θ|D)에 대해서 다수의 봉우리를 포함한 형태의 사후확률이 얻어진다. 이러한 형태는 군집들의 서로 다른 라벨링(labeling) 때문에 발생한다.
  • 단적인 예로, K=2인 2차원 가우스 혼합 모델의 데이터(${\displaystyle \pi _{k}}$=0.5, ${\displaystyle \mu _{1}}$=-10, ${\displaystyle \mu _{2}}$=10)에 대해서 우도 함수 p(D|${\displaystyle \mu _{1}}$,${\displaystyle \mu _{2}}$)는 두 개의 피크를 포함하고 있다. 하나는 ${\displaystyle \mu _{1}}$=-10, ${\displaystyle \mu _{2}}$=10인 피크이고, 다른 하나는 ${\displaystyle \mu _{1}}$=10, ${\displaystyle \mu _{2}}$=-10인 피크이다. 이 때 유일한 최대 우도 추정(MLE)이 존재하지 않기 때문에, 매개변수는 "식별 가능하지 않다"고 한다. 그러므로 사전확률이 특정 라벨링에 영향을 주지 않는다면, 유일한 최대 사후확률 추정(MAP)도 존재하지 않는다. 이는 사후확률이 다수의 봉우리를 포함한 형태라는 것과 같은 의미이다.^[4]
• 사후확률이 포함하는 봉우리의 개수가 몇 개인지 찾는 것은 굉장히 어려운 문제다. K개의 모델이 혼합되어있는 혼합모델은 K!의 라벨링 경우의 수가 있는데, 이 중 몇 개의 피크는 하나로 합쳐질 수 있기 때문이다. 특히 가우스 혼합 모델에 대한 최적의 최대 우도 추정을 찾는 방법이 NP-hard 문제라고 알려져 있다.^[5]

매개 변수 추정과 시스템 확인

• 매개변수 혼합 모델은 우리가 Y의 분포를 알고 있거나 X의 샘플을 가지고 있을 때 자주 사용된다. 그러나 우리는 ai와 θi의 값을 결정하기를 원한다. 그러한 상황은 몇 개의 다른 분포가 혼합된 것으로부터의 샘플을 통해 정보를 얻을 수 있다.
• 혼합 모델의 확률의 생각은 공통적으로 사라진 정보 문제에서부터 온다. 이때 사라진 정보는 샘플 데이터들이 어떠한 확률분포모델에 속해있는지에 대한 정보이다. 이를 이해하는 한 가지 방법은 데이터 좌표가 우리가 적용하고자 하는 모델의 분포 중에 하나의 모델에 적합하게 위치한다는 것을 가정하는 것이다. 이 추정에서 할 일은 우리가 선택한 모델의 함수에 맞는 적절한 매개변수를 고안하는 것이다. 데이터 좌표에 대한 연결은 각각의 개별 모델의 분포의 연관성으로 표현 된다.
• 혼합의 분해에 대한 문제의 다양한 접근이 제시되었다. 대부분 expectation maximization (EM) 또는 maximum a posteriori estimation (MAP) 와 같은 maximum likelihood 방식에 초점을 많이 맞추고 있다. 일반적으로 이러한 방법은 매개변수 추정의 문제와 시스템 정체확인으로 분리하여 고려된다. 즉 다시 말하면, 샘플 데이터들이 어떠한 확률분포모델에 속하는지 결정을 하는 과정과 확률분포모델의 매개변수를 새롭게 업데이트 하는 과정의 반복으로 문제를 해결한다.

EM(Expectation Maximization)알고리즘

• EM 알고리즘은 1958년에 Hartley에 의해서 처음 제안되었고 1977년에 Dempster에 의해서 체계화되어 된 군집 알고리즘이다. EM 알고리즘은 K-Means 알고리즘과 마찬가지로 초기 모델을 생성한 후 반복 정제과정을 통하여 모델을 최적화된 모델을 생성해간다. EM 알고리즘은 반복 정제 과정을 통하여 각 객체들이 혼합 모델(Mixture Model)에 속할 가능성(Probability)을 조정하여 최적의 모델을 생성해 간다. K-Means 알고리즘에서는 유클리디언(Euclidean) 거리 함수를 사용하는 반면에 EM 알고리즘은 log-likelihood 함수를 사용하여 모델의 적합성을 평가한다. 즉, K-Means가 거리 기반 군집 방법인 것에 비하여 EM은 확률 기반 군집(Probability-based clustering)이라고 한다.
• EM 알고리즘은 Finite Mixture Model 통계 개념에 기반하고 있다. Mixture 하는 것은 여러 개의 확률 분포를 혼합된 것을 의미한다. 군집의 개수가 k라고 하면 k개의 확률 분포를 갖는 것을 의미한다. EM 알고리즘에서는 각 레코드들은 여러 개의 확률 분포 모델(군집)에 속하는 가중치를 가지고 배정된다.
• EM 알고리즘은 최적해로 수렴한다는 것이 증명되어 있다. 루프를 돌 때마다 우도가 결코 줄어들지 않기 때문이다. 하지만 EM은 초기 해에 따라 최종 해가 달라지는 욕심 알고리즘(Greedy algorithm)이고, 전역 최적 해(Global optimal solution)이 아닌 지역 최적 해(Local optimal solution)로 수렴할 수도 있다.^[6]

EM 알고리즘

입력: 군집의 개수 k, 입력 데이터(샘플데이터), 종료 조건 출력: Log-likelihood를 최대화하는 k 군집의 가중치 값과 군집의 매개변수 값 ${\displaystyle L({\boldsymbol {\theta }};\mathbf {X} )=p(\mathbf {X} |{\boldsymbol {\theta }})=\sum _{\mathbf {Z} }p(\mathbf {X} ,\mathbf {Z} |{\boldsymbol {\theta }})}$ (1) 추정 단계(Expectation Step) k개의 확률 분포(군집)에 대하여 각 레코드들이 속할 확률을 계산하여 weight 로 변환하여 배정한다. ${\displaystyle Q({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(t)})=\operatorname {E} _{\mathbf {Z} |\mathbf {X} ,{\boldsymbol {\theta }}^{(t)}}\left[\log L({\boldsymbol {\theta }};\mathbf {X} ,\mathbf {Z} )\right]=\sum _{\mathbf {Z} }p(\mathbf {Z} |\mathbf {X} ,{\boldsymbol {\theta }}^{(t)})\log L({\boldsymbol {\theta }};\mathbf {X} ,\mathbf {Z} )}$ (2) 최대화 단계(Maximization Step) 혼합모델의 매개변수들을 업데이트한다 ${\displaystyle {\boldsymbol {\theta }}^{(t+1)}={\underset {\boldsymbol {\theta }}{\operatorname {arg\,max} }}\ Q({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(t)})\,}$ (3) 종료 조건 반복하는 과정에서 Log-likelihood의 변화 정도가 입력받은 종료 조건 값보다 작아 질 때 종료한다. 그렇지 않는다면 (1)의 과정으로 다시 돌아가서 반복한다.

EM알고리즘과 K-means 알고리즘과의 관계

• K-mean 알고리즘은 임의의 데이터 셋을 클러스터링 할 때 쓰이는 알고리즘으로, 가우스 혼합 모델의 EM 알고리즘과 비슷하다. K-means 알고리즘의 경우, 각 데이터 포인트에 클러스터를 정확히 1가지 지정하는데에 반해(hard assignment), EM알고리즘은 여러개의 클러스터에 대해 사후 확률에 비례하도록 지정한다(soft assignment). 실제로 가우스의 혼합 EM 알고리즘으로부터 K-means 알고리즘을 다음과 같이 유도할 수 있다.^[1]
• 공분산 행렬이 ${\displaystyle I\epsilon }$인 가우스 혼합 모델을 고려하자. ${\displaystyle \epsilon }$은 모든 혼합 구성요소들이 공유하는 분산값이고 ${\displaystyle I}$는 항등 행렬이다. 따라서,

${\displaystyle {\begin{array}{lcl}p(x|\mu _{k},\Sigma _{k})={\frac {1}{{2\pi \epsilon }^{1/2}}}exp(-{\frac {1}{2\epsilon }}\rVert {x-\mu _{k}}\rVert ^{2})\end{array}}}$

• 이제 위와 같은 K개의 가우스 혼합 모델을 위한 EM알고리즘을 고려하면, 특정 데이터 포인트에 대한 사후확률은 다음과 같다.

${\displaystyle {\begin{array}{lcl}\gamma (z_{nk})={\frac {\pi _{k}exp{-\rVert x_{n}-\mu _{k}\rVert ^{2}/2\epsilon }}{\Sigma _{j}\pi _{j}exp{-\rVert x_{n}-\mu _{j}\rVert ^{2}/2\epsilon }}}\end{array}}}$

• ${\displaystyle \epsilon \to 0}$ 일 때, 분모의 항중 가장 작은 ${\displaystyle -\rVert x_{n}-\mu _{k}\rVert ^{2}}$를 가진 항이 천천히 0 값에 가까워지므로, 데이터 포인트 ${\displaystyle x_{n}}$에 대한 사후확률 ${\displaystyle \gamma (z_{nk})}$ 은 j를 제외하고는 모두 0이 되고 j에 대한 사후확률은 1이된다. 이것은 모든 ${\displaystyle \pi _{k}}$값이 0이 아닌 한, ${\displaystyle \pi _{k}}$에 관계없이 성립한다.
• 따라서 위와 같은 경우, 클러스터 지정은 k-means 알고리즘과 똑같이 이루어진다. 따라서 데이터 포인트들은 가장 가까운 거리에 있는 클러스터에 배정되게 된다.
• K-means 알고리즘에서는 클러스터의 평균값만 추정하고 공분산값은 추정하지 않는다.

^[7]

혼합 모델의 응용

가우스 혼합 모델의 응용

여러 개의 가우스 분포

• 가우스 모델은 자연적인 현상을 표현하기에 좋은 모델이기 때문에, 많은 분야에서 가우스 모델이 사용될 수 있다.
• 두 개 이상의 봉우리를 가진 분포를 최소의 오류로 모델링하기 위해서는 여러 개의 가우시언 분포를 사용하는 가우스 혼합 모델을 사용해야한다.
• 지금부터의 가우스 혼합 모델의 매개변수를 찾아내는 과정은 "패턴인식,교보문고,2008,오일석"의 내용을 바탕으로 작성되었다.^[6]
  • 샘플의 집합이 ${\displaystyle X=(x_{1},x_{2},...,x_{N})}$으로 주어진다면, 주어진 X를 바탕으로 추정해야 할 매개변수는 다음과 같다.
    • 가우시언의 개수 ${\displaystyle K}$
    • k 번째 가우시언의 매개 변수 ${\displaystyle (\mu _{k},\Sigma _{k}),k=1,...,K}$
    • k 번째 가우시언의 가중치 ${\displaystyle \pi _{k},k=1,...,K}$
  • 최적화 대상이 되는 함수는 ${\displaystyle K}$개의 가우시언 분포의 합으로 다음과 같이 나타낼 수 있다.
    • ${\displaystyle p(x)=\sum _{k=1}^{K}\pi _{k}N(x|\mu _{k},\Sigma _{k})}$
  • 사용해야 하는 가우시언의 개수는 사용자가 미리 정해준다고 가정하면 나머지 매개변수를 추정하면 된다.(실제로 몇 개의 가우시언을 사용해야할지 자동으로 결정할 수는 있다.)
    • 추정할 매개변수 ${\displaystyle \Theta =(\pi =(\pi _{1},...,\pi _{k}),(\mu _{1},\Sigma _{1}),...,(\mu _{k},\Sigma _{k}))}$
  • 이들을 이용하여 다음과 같이 최대 우도 추정 문제로 발전시킬 수 있다.
    • ${\displaystyle p(X|\Theta )=\prod _{i=1}^{N}p(x_{i}|\Theta )=\prod _{i=1}^{N}(\sum _{k=1}^{K}\pi _{k}N(x_{i}|\mu _{k},\Sigma _{k}))}$
    • ${\displaystyle lnp(X|\Theta )=\sum _{i=1}^{N}ln(\sum _{k=1}^{K}\pi _{k}N(x_{i}|\mu _{k},\Sigma _{k}))}$
  • 따라서 관찰된 X에 대해 이것을 발생시켰을 가능성이 가장 큰 매개 변수 집합 ${\displaystyle \Theta }$를 찾아 그것을 해로 취하는 것이 최종 문제이다.
    • ${\displaystyle \Theta _{m}=argmax_{\Theta }lnp(X|\Theta )}$
  • 이 최적화 문제는 두 가지 단계가 필요하다. 먼저 샘플이 어느 가우시언에 속하는 지를 추정하는 단계가 기대화(Expectation) 단계이다. 이 때 가우시언에 속하는 정도를 확률로 표현하는 연성 소속을 사용한다. E 단계를 마친 뒤 매개 변수 집합 ${\displaystyle \Theta }$를 추정하는 단계가 최대화(Maximization) 단계이다. ${\displaystyle \Theta }$에는 두 가지 매개 변수가 있는데, 하나는 ${\displaystyle K}$개의 ${\displaystyle \mu }$와 ${\displaystyle \Sigma }$이고, 다른 하나는 혼합 계수 벡터 ${\displaystyle \pi }$이다. 따라서 ${\displaystyle \mu }$와 ${\displaystyle \Sigma }$를 먼저 계산한 후 ${\displaystyle \pi }$를 계산한다.
    • E 단계를 위해 필요한 가우시언에 속하는 정도에 대한 값의 식은 다음과 같다.(자세한 과정은 EM 알고리즘 참고)
    • ${\displaystyle P(z_{j}=1|x_{i})={\frac {\pi _{j}N(x_{i}|\mu _{j},\Sigma _{j})}{\sum _{k=1}^{K}\pi _{k}N(x_{i}|\mu _{k},\Sigma _{k})}}}$, 샘플 ${\displaystyle x_{i}}$가 관찰되었을 때 그것이 j번째 가우시언에서 발생했을 확률(사후확률)
    • M 단계를 위해 필요한 매개 변수 값들의 식은 다음과 같다.(자세한 과정은 EM 알고리즘 참고)
    • ${\displaystyle \mu _{j}={\frac {1}{N_{j}}}\sum _{i=1}^{N}P(z_{j}=1|x_{i})x_{i}}$, ${\displaystyle N_{j}=\sum _{i=1}^{N}P(z_{j}=1|x_{i})}$
    • ${\displaystyle \Sigma _{j}={\frac {1}{N_{j}}}\sum _{i=1}^{N}P(z_{j}=1|x_{i})(x_{i}-\mu _{j})(x_{i}-\mu _{j})^{T}}$
    • ${\displaystyle \pi _{j}={\frac {N_{j}}{N}}}$
  • 이들 E와 M단계를 번갈아 가며 반복하다가 수렴 조건이 만족되면 멈춘다.
• 이러한 과정을 통해 가우시언 혼합 모델을 아래와 같은 응용에 적용시킬 수 있다.

금융 모델

• 금융은 경제가 정상적일 때와 위기 상황일 때의 흐름이 매우 다르다. 따라서 이러한 상황을 모델링하기 위해서 혼합 모델을 사용하는 것이 적합하다. 그 모델로는 점프-확산 모델(jump-diffusion model), 두 개의 정규 분포의 혼합 모델 등이 사용된다.
• 더 자세한 내용은 Financial economics#Challenges and criticism에서 찾아볼 수 있다.

주택 가격

• 먼저 N개의 다른 주택의 가격을 관찰했다고 가정하자. 다른 거주 지역에 있는 다양한 종류의 주택 가격은 상당히 다를 것이다. 그러나 특정 거주 지역에 있는 특별한 종류의 주택의 가격은 평균 가격 주변에 가깝게 형성되어 있는 경향이 있을 것이다. 이러한 주택 가격은 K개의 서로 다른 성분으로 이루어진 혼합 모델로 정확하게 묘사할 수 있다. 각 성분은 주택의 종류나 거주 지역의 특정 조합을 나타내고, 미지의 평균과 분산 값을 가지는 정규 분포를 따른다고 가정한다. 이 모델을 관찰된 가격에 EM 알고리즘을 이용하여 적용시킨다면, 주택의 종류나 거주 지역에 따른 가격을 분류할 수 있을 것이고, 주택의 종류나 거주 지역에 따른 가격의 분포도 알 수 있을 것이다. (가격이나 수입과 같은 값은 항상 양수이고, 기하급수적으로 증가하는 경향이 있어서, 실제로 대수-정규 분포(Log-normal distribution)가 정규 분포보다 더 좋은 모델이 될 수 있다.)

퍼지 영상 분할(Fuzzy image segmentation)

• 영상 처리나 컴퓨터 비전에서 전통적인 영상 분할(image Segmentation) 모델은 하나의 픽셀을 오직 하나의 패턴에만 할당시켰다. 그런데 퍼지 영상 분할에서는 어느 패턴도 단일 픽셀에 대한 소유권을 가질 수 있다. 만약 패턴들이 가우스 분포라면, 퍼지 영상 분할은 가우스 혼합 모델 분포를 따르게 된다. 이 모델이 다른 분석적이고 기하학적인 기법(가령, 산만한 경계에서의 상전이)과 결합한다면, 공간적으로 정규화 된 혼합 모델로서 더 현실적이고 계산적으로 효율적인 분할 방법이 될 수 있다.

문서의 주제

• 문서가 N개의 서로 다른 단어와 전체 크기가 V인 어휘로 구성되어 있고, 각 단어는 K개의 주제 중 하나에 해당한다고 가정하자. 이러한 단어들의 분포는 K개의 서로 다른 V차원 범주형 분포(Categorical distribution)의 혼합 모델로 표현될 수 있다. 이런 종류의 모델은 주로 토픽 모델(Topic model)이라고 한다. 그런데 많은 수의 매개변수 때문에, EM 알고리즘을 이 모델에 적용하면 원하는 결과를 얻는 데에 실패하는 경우가 많다. 그래서 좋은 결과를 얻기 위해 몇 가지 추가 가정이 필요하다. 전형적으로 두 종류의 추가 가정이 모델에 추가된다.
  • 사전 분포(Prior distribution)는 아주 작은 수의 단어만 0이 아닌 확률을 가지고 있는 스파스 분포(Sparse distribution)를 만들기 위해 토픽 분포를 묘사하는 매개변수를 사용한다. 이를 위해 디리클레 분포(Dirichlet distribution)를 Concentration parameter를 1보다 상당히 작게 설정하여 적용한다.
  • 자연적 집단화(natural clustering)를 이용하기 위해, 몇몇 종류의 추가 조건은 단어들의 토픽 유사성(identities)을 사용한다.
• 더 자세한 내용은 토픽 모델(Topic model)의 참고문헌의 자료들로부터 알 수 있다.

필기 인식

• 다음 예시는 Christopher M. Bishop, Pattern Recognition and Machine Learning 의 한 예시를 바탕으로 하였다.^[8]
• 손으로 쓴 0과 9 사이의 숫자를 스캔한 N*N 크기의 흑백 이미지가 있는데, 어느 숫자가 쓰였는지는 모른다고 가정하자. 여기서 K=10인 서로 다른 성분으로 되어 있는 혼합 모델을 만들 수 있다. 각 성분은 크기가 ${\displaystyle N^{2}}$인 베르누이 분포(픽셀 당 하나)의 벡터로 되어 있다. 이 모델은 EM 알고리즘을 분류되지 않은 세트의 손으로 쓴 숫자에 적용시켜 훈련될 수 있고, 쓰인 숫자에 따라 이미지를 효과적으로 분류할 수 있다. 이와 같은 모델을 분류뿐만 아니라 다른 이미지의 숫자를 인식하는 데에 사용할 수 있다. 이는 모델에서 새로운 이미지에 대한 각 숫자의 확률을 계산하여 가장 높은 확률을 나타내는 숫자를 결과 값으로 나타내면 된다.
• 베르누이 혼합 모델은 손으로 쓴 숫자에 대한 전체적인 모델링에 사용된다.
  • 하나의 데이터 ${\displaystyle x}$가 D개의 2진 변수 ${\displaystyle x_{i}}$를 가지고 있고, ${\displaystyle x_{i}}$가 매개변수 ${\displaystyle \mu _{i}}$에 대해서 베르누이 분포를 가진다고 하면 그 식은 다음과 같다.
  • ${\displaystyle p(x|\mu )=}$${\displaystyle \prod _{i=1}^{D}}$${\displaystyle \mu _{i}^{x_{i}}(1-\mu _{i})^{(1-x_{i})}}$, ${\displaystyle x=(x_{1},...,x_{D})^{T}}$ and ${\displaystyle \mu =(\mu _{1},...,\mu _{D})^{T}}$
  • 이 분포에 대한 혼합 모델은 다음과 같다.
  • ${\displaystyle p(x|\mu ,\pi )=\prod _{k=1}^{K}\pi _{k}p(x|\mu _{k}),\mu =(\mu _{1},...,\mu _{K})^{T},\pi =(\pi _{1},...,\pi _{K})^{T},\pi }$: 혼합계수
• 이 혼합모델을 풀기 위해서 EM 알고리즘의 각 단계(E단계, M단계)를 위한 식을 구해야 하고, 이 혼합모델에 대한 최대 우도 추정을 구해야한다.
  • 완전한 데이터 로그 우도(Complete data log likelihood) ${\displaystyle L(\theta )}$를 구하는 과정은 다음과 같다.
  • ${\displaystyle P(X,Z|\mu ,\pi )=Pr(X|Z,\mu ,\pi )Pr(Z|\mu ,\pi )=\prod _{n=1}^{N}\prod _{k=1}^{K}(\pi _{k}\prod _{i=1}^{D}}$${\displaystyle \mu _{k,i}^{x_{n,i}}(1-\mu _{k,i})^{(1-x_{n,i})})^{z_{n,k}}}$
  • ${\displaystyle L(\theta )=lnP(X,Z|\mu ,\pi )=\sum _{n=1}^{N}\sum _{k=1}^{K}z_{n,k}(ln\pi _{k}+\sum _{i=1}^{D}x_{n,i}ln\mu _{k,i}+(1-x_{n,i})ln(1-\mu _{k,i}))}$
  • 위 값을 최대화하는 ${\displaystyle z_{n,k}}$값을 업데이트하는 과정이 기댓값(Expectation) 과정이다.
  • ${\displaystyle z_{n,k}={\frac {\pi _{k}\prod _{i=1}^{D}\mu _{k,i}^{x_{n,i}}(1-\mu _{k,i})^{1-x_{n,i}}}{\sum _{m=1}^{K}\pi _{m}\prod _{i=1}^{D}\mu _{m,i}^{x_{n,i}}(1-\mu _{m,i})^{1-x_{n,i}}}}}$
  • E 단계에서 구한 ${\displaystyle z_{n,k}}$을 이용하여 모델 매개변수를 업데이트하는 과정이 최대화(Maximization) 과정이다.
  • ${\displaystyle \mu _{m}={\frac {1}{N_{m}}}\sum _{n=1}^{N}z_{n,m}x_{n},N_{m}=\sum _{n=1}^{N}z_{n,m}}$
  • ${\displaystyle \pi _{m}={\frac {N_{m}}{N}}}$
• 따라서 위 EM 과정을 반복할수록 로그 우도를 최대화하는 매개변수에 수렴하게 되고, 이를 통해 손으로 쓴 숫자를 0~9까지 분류하여 판별할 수 있다.

직접적인 또는 간접적인 응용

• 위의 금융에 적용한 예시는 혼합 모델의 직접적인 응용 중 하나이다. 왜냐하면 근본적인 메커니즘을 가정하여 각각의 관찰된 정보가 서로 다른 구성성분이나 범주 중 하나에 반드시 속하도록 하였기 때문이다. 그러나 이러한 근본적인 메커니즘은 관찰될 수도 있고, 관찰되지 않을 수도 있다. 이러한 형태의 혼합 모델에서 각각의 구성 성분은 하나의 확률 밀도 함수에 의해 나타날 수 있다. 그리고 각 구성 성분의 계수는 관찰된 정보가 이 성분으로부터 올 확률에 해당한다.
• 혼합 모델의 간접적인 응용에서는 위의 메커니즘처럼 가정할 수 없다. 혼합 모델이 단순히 수학적으로 다루기 쉽도록 사용되는 것이다. 예를 들어, 서로 다른 2개의 정규 분포의 혼합 모델은 표준 범주형 분포(Standard parametric distribution)에 의해 모델링되지 않은 2개의 모드의 분포를 나타낸다. 또 다른 예로 혼합 모델을 사용하여, 기본적인 가우스 분포보다 더 평평한 꼬리 부분(tail)을 만들어서 극단적인 사건에 대해 더 잘 모델링되도록 하는 것이다.

각주

1. Bishop, C.M (2006). 《Pattern Recognition and Machine Learning》. 
2. 패턴인식 개론 Matlab 실습을 통한 입체적 학습 개정판, 한학용 저, 한빛미디어
3. Yu, Guoshen (2012). “Solving Inverse Problems with Piecewise Linear Estimators: From Gaussian Mixture Models to Structured Sparsity”. 《IEEE Transactions on Image Processing》 21 (5): 2481–2499. doi:10.1109/tip.2011.2176743. 
4. Machine Learning:A Probabilistic Perspective,Kevin P. Murphy,2012
5. Aloise et al. 2009; Drineas et al. 2004
6. 패턴인식,교보문고,2008,오일석
7. 대용량 데이터를 처리하기 위한 EM Survey, 김완섭
8. Bishop, Christopher (2006). Pattern recognition and machine learning. New York: Springer. ISBN 978-0-387-31073-2

외부 링크

• Mixture Model 영문 위키
• “Normal distribution”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Normal distribution”. 《Wolfram MathWorld》 (영어). Wolfram Research.