こんにちは。

本日はEMアルゴリズムについてお話ししようと思います。「EMアルゴリズム？」と思った方へ先に簡単に紹介すると

Expectation-Maximization Algorithm

の略で、潜在変数（Z）を用いて、iterativeに尤度最大化を行う手法です。iterativeというのはE-step、M-stepと言われる２種類を交互に行い尤度を最大化し、パラメータを決定します。2ステップに分けて行うことがミソなんですけれど数式ゴリゴリすると途中で自分が何をやっていたかわからなくなるんですよね。その点に注意しながら進めていこうと思います。
Notation
  • m個の独立なデータ(observable)、{x^{1},\cdots,x^{m}}
  • モデルのパラメータ、\theta
  • 潜在変数(unobservable)、z
今回の目標はEMアルゴリズムの流れを知ることと数式になれることです。音声解析、時系列解析など前処理でも使われる対数変換は今回も登場します。

    \[l(\theta) = \sum_{i=1}^{m} \log p(x^{i};\theta) = \sum_{i=1}^{m}\log \sum_{z}^{}p(x^{i},z;\theta)\]

もちろんコレを最大化するのが目的なんですが、上の式から\sum_z Q_i(z)=1,Q_i(z)\geq 0を満たすとある確率分布Qを用いて下界を導出します。

    \[= \sum_{i}^{}\log\sum_{z^{(i)}}^{}Q_i(z^{(i)})\frac{p(x^{i},z^{(i)};\theta)}{Q_i(z^{(i)})}\]


    \[\geq \sum_{i}^{}\sum_{z^{(i)}}^{} Q_i(z^{(i)})\log\frac{p(x^{i},z^{(i)};\theta)}{Q_i(z^{(i)})}\]

最後の不等号ですが、イェンセンの不等式を使いました。fを区間I上で定義される凸関数とする。以下が満たされるとき
  • x_1,x_2,\cdots,x_n \in I
  • \lambda_1,\lambda_2,\cdots,\lambda_n \geq 0 \sum_{i=1}^{n}\lambda_i = 1,

    \[f\left (\sum_{i=1}^{n}\lambda_i x_i\right) \leq \sum_{i=1}^{n}\lambda_if(x_i)\]

が成り立ちます。対数関数はconcaveなのでイェンセンの不等式より逆に

    \[In\sum_{i=1}^{n} \lambda_i x_i \geq \sum_{i=1}^{n} \lambda_i In(x_i)\]

となります。先ほどの変形はコレを用いました。さらにイェンセンの等号成立条件は

    \[ \frac{p\left(x^{i}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)}=constant\]

なので以下を満たすようにすればいいことがわかります。

    \[ Q_{i}\left(z^{(i)}\right) \propto p\left(x^{i}, z^{(i)} ; \theta\right)\]

ここで先ほどのQの性質、\sum_z Q_i(z^{(i)}) = 1を用いると

    \[Q_i(z^{(i)}) = \frac{p(x^{i},z^{(i)};\theta)}{\sum_z p(x^{i},z;\theta)}\]


    \[= \frac{p(x^{i},z^{(i)};\theta)}{p(x^{i};\theta)}\]


    \[= p(z^{(i)}|x^{i};\theta)\]

となり、初めに「とある」としていたQが求まりました。コレがE-stepです。M-stepは下界の最大化です。つまり

    \[ \theta :=\arg \max_{\theta} \sum{i} \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \log \frac{p\left(x^{i}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)}\]

簡単にまとめますと
  1. 潜在変数zの事後確率計算
  2. パラメータ\thetaの更新
以前、Lassoの理論編でメジャライザー最小化をしましたがそれとやっていることはほとんど同じです。
今回の場合、テイラー展開に対応する部分がE-stepで、Minimizeに対応する部分がMaximizeのパラメータ更新です。

では、コレで下界の最大化ができたことになりますがその際、本来の目的関数、つまりl(\theta)も同時に最大化されているのでしょうか？ではステップをtとし、\theta^{(t)}, \theta^{(t+1)}で確認してみます。Q_i^{(t)}(z^{(i)}) := p(z^{(i)}|x^{i},\theta^{(t)})とすることでイェンセンの等式は保持されるので

    \[ l\left(\theta^{(t)}\right)=\sum_{i} \sum_{z^{(i)}} Q_{i}^{(t)}\left(z^{(i)}\right) \log \frac{p\left(x^{i}, z^{(i)} ; \theta^{(t)}\right)}{Q_{i}^{(t)}\left(z^{(i)}\right)}\]

となります。よって

    \[ l\left(\theta^{(t+1)}\right) \geq \sum_{i} \sum_{z^{(i)}} Q_{i}^{(t)}\left(z^{(i)}\right) \log \frac{p\left(x^{i}, z^{(i)} ; \theta^{(t+1)}\right)}{Q_{i}^{(t)}\left(z^{(i)}\right)}\]

が成り立ち、M-stepより逆に

    \[ \geq \sum_{i} \sum_{z^{(i)}} Q_{i}^{(t)}\left(z^{(i)}\right) \log \frac{p\left(x^{i}, z^{(i)} ; \theta^{(t)}\right)}{Q_{i}^{(t)}\left(z^{(i)}\right)} = l(\theta^{(t)})\]

となります。コレでちゃんと最大化されてることがわかりました。ひとまず安心です。ではこの勢いでEMとKLの関係についてもみていきたいと思います。

EMとKL

先ほどのこの式

    \[ \sum_{i} \log p\left(x^{i} \theta\right) \geq \sum_{i} \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \log \frac{p\left(x^{i}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)}\]

この両辺の間に注目します。つまり、何が不等号を作っているのか、乖離はなんなのか？ということでデータをX、潜在変数をZとして左辺から右辺を引いたものを考えますと

    \[L(X, Z, \theta) &=\ln p(X ; \theta)-\sum_{Z} Q(Z) \operatorname{In} \frac{p(X, Z ; \theta)}{Q(Z)}\]


    \[= \ln p(X ; \theta) \sum_{Z} Q(Z)-\sum_{Z} Q(Z) \operatorname{In} \frac{p(X, Z ; \theta)}{Q(Z)}\]


    \[= \sum_{Z} Q(Z) \ln p(X ; \theta)-\sum_{Z} Q(Z) \ln \frac{p(X, Z ; \theta)}{Q(Z)}\]


    \[= \sum_{Z} Q(Z) \ln p(X ; \theta)-\sum_{Z} Q(Z)\left{\ln \frac{p(Z | X ; \theta) p(X ; \theta)}{Q(Z)}\right\]


    \[=-\sum_{Z} Q(Z) \ln p(X ; \theta)-\sum_{Z} Q(Z){\ln p(Z | X ; \theta)+\ln p(X ; \theta)-\ln Q(Z)}\]


    \[=-\sum_{Z} Q(Z) \ln p(X ; \theta)-\sum_{Z} Q(Z){\ln p(Z | X ; \theta)+\ln p(Z))\]


    \[=K L[Q(Z) | p(Z | X ; \theta)-\ln Q(Z))\]

KLが登場しました。コレはつまり

    \[ \ln p(X ; \theta)=\sum_{Z} Q(Z) n \frac{p(X, Z ; \theta)}{Q(Z)}+K L[Q(Z) | p(Z | X ; \theta)]\]

ということですね。で、何がわかるかと言いますと先ほどイェンセンより等式をホールドしました。それはつまり上式のKLがゼロということですよね。もうお気づきかと思いますがKLがゼロになるのは分布が同じ時かつそのときのみに限りますよね。つまり、Q(Z) = p(Z|X;\theta)ということですが先ほどと同じ結果が得られていますね。

今回はEMアルゴリズムをもとに数式をずらずらとやってみました。日本の大学はレジュメも講義もほとんど公開してないですね、、

References