本日はEMアルゴリズムについてお話ししようと思います。「EMアルゴリズム?」と思った方へ先に簡単に紹介すると
Expectation-Maximization Algorithm
の略で、潜在変数(Z)を用いて、iterativeに尤度最大化を行う手法です。iterativeというのはE-step、M-stepと言われる2種類を交互に行い尤度を最大化し、パラメータを決定します。2ステップに分けて行うことがミソなんですけれど数式ゴリゴリすると途中で自分が何をやっていたかわからなくなるんですよね。その点に注意しながら進めていこうと思います。Notation
- 個の独立なデータ(observable)、
- モデルのパラメータ、
- 潜在変数(unobservable)、
もちろんコレを最大化するのが目的なんですが、上の式からを満たすとある確率分布を用いて下界を導出します。
最後の不等号ですが、イェンセンの不等式を使いました。を区間上で定義される凸関数とする。以下が満たされるとき
- ,
が成り立ちます。対数関数はconcaveなのでイェンセンの不等式より逆に
となります。先ほどの変形はコレを用いました。さらにイェンセンの等号成立条件は
なので以下を満たすようにすればいいことがわかります。
ここで先ほどのの性質、を用いると
となり、初めに「とある」としていたが求まりました。コレがE-stepです。M-stepは下界の最大化です。つまり
簡単にまとめますと
- 潜在変数の事後確率計算
- パラメータの更新
では、コレで下界の最大化ができたことになりますがその際、本来の目的関数、つまりも同時に最大化されているのでしょうか?ではステップをとし、で確認してみます。とすることでイェンセンの等式は保持されるので
となります。よって
が成り立ち、M-stepより逆に
となります。コレでちゃんと最大化されてることがわかりました。ひとまず安心です。ではこの勢いでEMとKLの関係についてもみていきたいと思います。
EMとKL
先ほどのこの式この両辺の間に注目します。つまり、何が不等号を作っているのか、乖離はなんなのか?ということでデータをX、潜在変数をZとして左辺から右辺を引いたものを考えますと
KLが登場しました。コレはつまり
ということですね。で、何がわかるかと言いますと先ほどイェンセンより等式をホールドしました。それはつまり上式のKLがゼロということですよね。もうお気づきかと思いますがKLがゼロになるのは分布が同じ時かつそのときのみに限りますよね。つまり、ということですが先ほどと同じ結果が得られていますね。
今回はEMアルゴリズムをもとに数式をずらずらとやってみました。日本の大学はレジュメも講義もほとんど公開してないですね、、
References
- https://www.cs.utah.edu/~piyush/teaching/EM_algorithm.pdf
- http://www.princeton.edu/~amirali/Public/Teaching/ORF523/S16/ORF523_S16_Lec7_gh.pdf
- http://pianopiano.sakura.ne.jp/ml/em-algorithm/
- https://oimeg.blogspot.jp/2015/07/em.html
- https://en.wikipedia.org/wiki/Convex_function
- https://mathtrain.jp/jensen_proof
- http://cs229.stanford.edu/notes/cs229-notes8.pdf
- https://math.stackexchange.com/questions/628386/when-jensens-inequality-is-equality
- https://qiita.com/kenmatsu4/items/59ea3e5dfa3d4c161efb
- https://math.stackexchange.com/questions/247795/what-is-the-covariance-of-mixture-bernoulli-distribution