はじめに
Machine Learning Advent Calendar 2013の15日目を担当する@yag_aysです．専門はバイオインフォマティクスという計算機を使って生物学をする分野で，生モノではなく遺伝子の文字列相手に格闘している大学院生です．今回は初心者の人を対象に，なるべく数式を使わずにEMアルゴリズムについて解説してみたいと思います．
EMアルゴリズムは，SVMやニューラルネットワークといった華々しい機械学習の手法の一つではなく，機械学習の中で使われる尤度最大化という一部分を担当するアルゴリズムです．そのため多くの人にとってEMアルゴリズムは，それ単体を使ってみたりだとか独自に改良をしたりするような対象ではないでしょう．でも，EMアルゴリズムなんて仰々しい名前が付けられているだけあって，いざ自分の仕事に組み込む場合には中身を理解していないと「なぜEMアルゴリズムを使ったの？」であったり「それを使うと何が嬉しいの？」といった質問が来たときに困るし，とりあえず概念だけでも一通り理解しておきたいと思う人もいると思います．そこで今回は，大雑把にEMアルゴリズムを理解することを目的に，細かい定義やら数式は抜きにしてイメージで覚えられるような解説を書いてみました．まあ結局PRMLの受け売りなのですが，紙の上で見るよりかは分かりやすくしたと思うので勘弁してください．
- この記事の対象となる人
- EMアルゴリズムについて聞いたことはあるけどよく分かっていない人
- 例えば「これEMアルゴリズム使ってるけど，局所解に落ちてるんじゃない」って言われたとして，？？？ってなる人
- この記事の対象ではない人
- 「パターン認識と機械学習」(PRML)下巻9章を読み通した人
- イメージと聞いて情報幾何の話だと思った人
EMアルゴリズムとは
EMアルゴリズムは，潜在変数が存在する時の尤度関数を最大化するアルゴリズムです．機械学習の文脈では，よく混合ガウス分布（GMM）などの潜在変数を用いたモデリングの際に用いられます．PRMLで言うところの下巻9章「混合モデルとEM」ですね．また，今回のMLAC 2013ではm_ishihataさんの記事でも出てきますので，何に使うのかピンと来ない人はそちらも参照してもらえればと思います．
ここで覚えておいて欲しいのは，尤度関数を最大化するということです．確率的な機械学習の手法を使っていると，ときどき尤度関数というものが出てきます．特にEMアルゴリズムのような潜在変数が存在する時には，尤度関数は数式には書くことができても，実際にそれがどういう形をしていてどの値で最大になるのかといったことは全く予想ができません．尤度関数に適当に数字を入れれば値が帰ってきますが，それをパラメータすべてについて計算することは現実的には不可能です．そういった条件でどうにか上手いこと計算して効率よく最大値を求めたいといったときに，EMアルゴリズムは使われます．
イメージで理解するEMアルゴリズム
前置きはこのくらいにして，では実際にEMアルゴリズムが何をしているのかをスライドで見てもらいましょう．なお，これはあくまでイメージですので，実際にはデータ数に依存する高次元の空間ですし，EMアルゴリズムの計算途中で対数尤度関数がこのように図示できるわけでもありません．その点は注意してください．なお，以下の解説はPRML下巻9章の図9.14 (P.169)を参考にしています．
さて，PRMLの図を動かしてみたという感じですが，どうだったでしょうか？途中に少し記号を書いてしまいましたが，あまり気にしないでください．EMアルゴリズムの各ステップを更新していくことで，対数尤度の山を徐々に登っていく様子が何となくつかめたと思います．初期値だったパラメータも，，と更新されて，尤度関数を最大化するパラメータが求められたことがわかります．
EMアルゴリズムにおける下界
とは言うものの，下界って何だとかどうやって計算するんだとか色々あやふやなところがあるので，その辺を少し補足しておきましょう．下界（Lower Bound）とは，その名の通り対数尤度がここよりも小さくならないということを表しています．EMアルゴリズムでは，この下界というものを使ってだんだん底上げしていくことで対数尤度を増加させていくという感じです．Eステップでパラメータを固定したときの下界というものを求めて，Mステップで潜在変数の分布を固定したときの下界と対数尤度の値が同じになるように下界を押し上げます．あとはこれの繰り返しになるのですが，必ず下界よりも対数尤度は上にあるので，決して対数尤度が小さくはなりません．こうやってEMアルゴリズムは対数尤度を最大化していきます．
下界の求め方も今回は数式を使わずに説明するということで，対数尤度式からアレコレ計算すると出てくる程度に捉えておいてもらえればと思います．例えば混合ガウス分布にEMアルゴリズムを適用する場合だと，Jensenの不等式を使って数式の変形することにより下界は求めることができます．下界と対数尤度の差が実はKLダイバージェンスになっているという話もあるのですが，潜在変数の分布について話してないのでここでは割愛します．詳しくはPRMLの数式を追ってみてください．
イメージで分かるEMアルゴリズムの性質
ここからは，EMアルゴリズムで注意しなければいけない点を解説します．先ほど紹介したイメージを持っていれば，数式を使わずともEMアルゴリズムの持つ問題点を指摘できるはずです．
各ステップを繰り返す必要がある
当然ですが，EMアルゴリズムはEステップとMステップを繰り返す必要があります．EMアルゴリズムが適用できる問題ならば各ステップの計算自体は簡単ですが，パラメータや対数尤度値がある程度収束するまでは，計算し続けなければいけません．
初期値に依存し，局所最適解に落ちることもある
先ほど示したイメージでは，下界を引き上げていく際に二次関数のようなものの頂点と対数尤度関数を行ったり来たりしていました．ということは，きちんと勾配にしたがって最大化してくれるという保証がある一方で，それらがある程度一致したところでパラメータは更新しようがないということになります．そのため，EMアルゴリズムは初期値によっては局所最適解に落ちる可能性があります．
まとめ
いかがだったでしょうか？この記事で少しでもEMアルゴリズムのイメージがつかめてもらえれば幸いです．そうすれば，PRMLなどの数式の出てくる参考書を読んでも，EMアルゴリズムというものが一体何がしたいのかといったことが理解しやすくなるんじゃないかと思います．
少し個人的な話になりますが，私自身はこうやって模式図やイメージを実際に頭のなかで組み立てると，とても理解が捗ります．私が機械学習の勉強をするときにこういうことを意識しはじめたのは，PRML復々習レーンで第3章の線形回帰モデルの冒頭を発表したときでした．そのときには3.1.2の「最小二乗法の幾何学」という項が一体何を言っているのか全く分からず，発表の際に堂々と「分かりませんでした！」と言ったことをよく覚えています．その時に発表の際に参加者の皆さんに教えていただいたおかげで，最小二乗法の理解が一気に深まったように思えました．よくわからない数式の最小化という漠然とした状態から，数式の各項が何を表していて，何を最小化するのかということまで具体的に理解できたのはこのときでした．こういった感覚はPRMLを読むうちに何度もあり，自分の中できちんと理解に落としこむことの重要性を実感しています．今回の記事では，その一つとしてEMアルゴリズムをイメージでつかんでもらえるような紹介の仕方をしてみました．勿論のことながら，自分で自由自在に使いこなすくらい理解するにはきちんと数式を追わなければいけないですし，図式としてイメージできないことも多々あります．しかしながら，どんな難しいアルゴリズムや手法でも，やってることは絵にかけるほど単純なのだというリラックスした感覚で臨めば，意外と理解につながるものだと思います．機械学習の勉強で壁にぶち当たったときは，ぜひ図を書いたり具体的な絵にして考えなおしてみると上手くいくかもしれません．