お勉強メモ：混合ベルヌーイ分布とEMアルゴリズム

前回の最尤推定法に引き続き、ITエンジニアのための機械学習理論入門で勉強したのでメモ。今回は７章のEMアルゴリズム。

ベルヌーイ分布での最尤推定

N 個の観測点 $\{ X_n \}_{n=1}^N$ が与えられて、観測点は D 次元の２値ベクトルとする。つまり $X = (x_1, \dots, x_D )^{T} , x_i \in \{ 0,1\}$ 。

各次元はベルヌーイ分布に従うと仮定したとき、 $x_i = 1$ である確率 $u_i \in [0,1$ ] をパラメータとして $x_i$ の確率密度関数は

$\displaystyle p_i(x_i \mid u_i ) = {u_i}^{x_i} (1 - u_i)^{1 - x_i}$

パラメータベクトルを $U = (u_1, \dots , u_D)^T$ とすると、X の確率密度関数は

$\displaystyle p(X \mid U ) = \prod_{i=1}^{D} p_i(x_i \mid u_i )$

このとき、観測データ $\{ X_n \}_{n=1}^N$ の尤度関数は

$\displaystyle P = \prod_{n=1}^{N} p(X_n \mid U )$

これを最大化するパラメータは手を動かせば解くことができて、以下の通り

$\displaystyle U = \frac{1}{N} \sum_{n=1}^{N} X_n$

混合ベルヌーイ分布での最尤推定

X が複雑で１つのベルヌーイ分布では表現できない場合でも、K 個のベルヌーイ分布を組み合わせて表現できる場合がある。

そこで、K 個のパラメータ $\{ U_k \}_{k=1}^{K}$ を用意し、X が k 番目のベルヌーイ分布 $p(X \mid U_k )$ で表現される確率 $\{ \pi_k \}_{k=1}^{K}$ （such that $\sum_{k=1}^{K} \pi_k = 1$ ）を新しいパラメータとして導入する。

このとき、X の確率密度関数（i.e., 混合ベルヌーイ分布）は

$\displaystyle p(X \mid U_k, \pi_k ) = \sum_{k=1}^{K} \pi_k p(X \mid U_k )$

同様に、観測データ $\{ X_n \}_{n=1}^N$ の尤度関数は

$\displaystyle P' = \prod_{n=1}^{N} p(X_n \mid U_k, \pi_k)$

これを最大化するパラメータは厳密に解くことができないので、EMアルゴリズムを使って極大化するパラメータを探索する。

EMアルゴリズム

観測点 $X_n$ が k 番目のベルヌーイ分布から得られる確率 $\gamma_{n,k}$ を負担率といい、以下のように定義する。

$\displaystyle \gamma_{n,k} = \frac{\pi_k p(X_n \mid U_k)}{ \sum_{k' = 1}^{K} \pi_{k'} p(X_n \mid U_{k'})}$

EMアルゴリズムでは、まずパラメータ $U_k, \pi_k$ を任意の値で初期化し、以下のEMステップを繰り返すことで負担率とパラメータを更新する。

Eステップ：パラメータ $U_k, \pi_k$ を固定し、上の式で負担率 $\gamma_{n,k}$ を更新
Mステップ：負担率 $\gamma_{n,k}$ を固定し、以下の式でパラメータ $U_k, \pi_k$ を更新

$\displaystyle U_k = \frac{\sum_{n=1}^{N} \gamma_{n,k} X_n}{\sum_{n=1}^{N} \gamma_{n,k}}, \pi_k = \frac{\sum_{n=1}^{N} \gamma_{n,k}}{N}$

このステップを繰り返すことで、尤度関数の値が単調増加し極大値に到達することが証明できる。実用では、尤度関数の値がある閾値に到達した時点で更新を打ち切る。

棚上げしたこと

教科書では潜在変数やベイズを導入せずに負担率を直感的にうまく説明していた。今回のメモでも同様にまとめているが、これは単純に自分がその辺りを理解できていないだけ。EMステップで極大値に到達する理由と更新式のお気持ちもちゃんと勉強する必要がある。とりあえず金森先生の本をポチってみた。PRMLはまだ怖い。