狠狠撸

狠狠撸Share a Scribd company logo

Oshasta em

?
?
Naotaka Yamada
Naotaka Yamada

EMアルゴリズムについてざっくり解説 完全データの対数尤度を最大化なら簡単にできる という仮定が鍵。そのかたちにうまいこと持っていく。理論的な背景はPRML 9.4を参照

1 of 15
くり ざっ EMアルゴリズム入門 2012/06/06 20:40-21:00 おしゃれstatistics 勉強会 @teikaw 12年6月7日木曜日
初めまして ? 山田 直敬 @teikaw ? 東京大学 情報理工学系 研究科 M1 ? 機械学習の研究をして います ? 特技はヴィオラ演奏。 たまにライブやります 12年6月7日木曜日
本日のキーワード ? ベイズの定理、事後確率 ? 最尤推定、ラグランジュの未定乗数法 ? k-means法 前提知識 ? 多変量正規分布 ? 隠れ変数、混合モデル 今日の内容 ? EM アルゴリズム 発展形 ? 変分ベイズ、ノンパラベイズ 12年6月7日木曜日
発表の流れ ? 【動機づけ】 混合正規分布モデルの紹介 ? 【導入】EMアルゴリズム = 隠れ変数を仮定した最尤推定 ? 【定式化】具体的な中身 ? 【評価】 EMアルゴリズムの諸性質、一般論 なめ は少 数式 12年6月7日木曜日
みんな大好きk-means法 ? クラスタリングといえばこれ ? 丸いクラスタができる ? クラスタ内の分散が一定であ ることが暗に仮定 http://www.aishack.in/2010/07/k-means-clustering/ ? クラスタのメンバーが同じくら いの数だけ存在することも暗 に仮定される ? データに偏りがあるとうまくいかない http://www.kamishima.net/jp/clustering/ 12年6月7日木曜日
そこで混合正规分布モデル (Gaussian Mixture Model; GMM) ? データが複数の正規分布の 重ねあわせによって生成され たと考える。 K p(x;θ ) = ∑ π k N ( ? k , Σ k ) k=1 ? 分散の違う分布でフィット 可能。柔軟性が高い ? 事後確率最大となるような クラスタを決定すれば良い http://scikit-learn.org/stable/modules/mixture.html 12年6月7日木曜日
骋惭惭のパラメタを最尤推定で求めたいが… 混合比,平均, 分散共分散行列 の組(π,μ, ∑)をk個 K データ一つあたりの尤度は p(x;θ ) = ∑ π k N ( ?k , Σ k ) だから、 k=1 i.i.dに生成した全データに対する対数尤度は N N K ln p(X;θ ) = ln ∏ p(x;θ ) = ∑ ln∑ π k N ( ? k , Σ k ) n=1 n=1 k=1 となる。 ただし、 不都合：logの中に足し算の形 logとexpがキャンセルされない K ∑π exp {(x ? ? ) Σ (x ? ? )}. 1 k = 1 , N ( ?, Σ) = T ?1 k=1 2πΣ 混合正規分布の対数尤度関数は、ラグランジュの未定乗数法を 用いて直接最大化しようとしても、解析解が求まらない 12年6月7日木曜日
隠れ変数を導入する ? データの生成過程を次の ようにモデル化する ? まず、混合正規分布の どのクラスタに属する のかが決まる 今見えているデータXは不完全だ～ 非観測な情報=隠れ変数Z p(Z=k)= πk ? 決められた正規分布に 従ってデータが発生 p(x|Z=k;θ) = N (μk,∑k ) p(x;θ) = ∑ p(x|Z;θ)p(Z) Z = ∑ πk N(μk,∑k) k 潜在変数(ラベル)Zが与えられていると仮定 12年6月7日木曜日
都合のいい完全データ｛X,Z} ? データセットXの全ての要素に対して、 ラベル(隠れ変数)Zが分かっている状態 ? 例えば, Zn=j の時、尤度は簡単な形に p(xn , zn = j;θ ) = π j N(xn ; ? j, Σ j ) ? znk は、kがデータ xn のラベルならば1 , from Bishop PRML Chapter 9 p.433 それ以外なら0を取るメンバシップ変数 N K とすると、 ln p(X, Z;θ ) = ∑ ∑ znk {ln π k + ln N(xn ; ? k, Σ k )} n=1 k=1 ? 完全データに対する対数尤度は次のよ logの中に足し算なし。 うになる 実質的な計算は正規分布一つの時と全く同じ 12年6月7日木曜日
かね お 待ち EMアルゴリズム ? 不完全データに対して、隠れ変数を仮定した場合の最尤推定法。 N ? 本来解くべき問題はmax ln p(X;θ ) = ∑ ln∑ p(x | Z;θ )p(Z ) 不完全データの対数尤度 n=1 Z だが潜在変数の総和がlogの中に入っているため解析解が得られず。 ? 無いものねだりで隠れ変数(ラベルデータ)Zが与えられていると仮定し て、完全データの対数尤度を最大化する。これは解析解OK N K ln p(X, Z;θ ) = ∑ ∑ znk {ln π k + ln N(xn ; ? k, Σ k )} n=1 k=1 ? 隠れ変数(ラベルデータ)は直接知ることはできず、実際はZの事後確率 しか分からない。そこでラベルを推定するために、ひとまず前回のパ ラメタを利用する。(これが反復法になる理由) 12年6月7日木曜日
贰惭アルゴリズム详细 ? INIT ? 忘却-step(仮) ? 不完全データのことは忘れる！！ ? これからは潜在変数を自分で推定し、 完全データで計算すると誓う ? 適当な初期化パラメータθ を設定 old 12年6月7日木曜日
Expectation Maximization ? E-Step (Expectation) ? 潜在変数を推定する ? すなわち p(Z | X; θold)を計算する(Bayesの定理) ? p(Z | X; θold)= p(X | Z; θold) p(Z; θold)/ p(X; θold) ? M-Step(Maximization) ? θnew = arg max Q(θ, θold) を計算する ? ここで Q(θ ,θ old ) = ∑ Z p(Z | X;θ old ) ln p(X, Z;θ ) 完全データの対数尤度の 潜在変数の事後分布についての期待値 ? θが収束するまで繰り返す 12年6月7日木曜日
蚕関数のおいしい性质 ? じつはEMアルゴリズムの各ステップで ln p(X;θ) = Q(θ,θold) + const が成立。忘れていたはずの不完全データのmaxを 毎ステップ解いていたところがpoint ? しかも、Q関数は各ステップで単調増加するの で、収束値の局所最適性が保証される！ ? (証明略) 12年6月7日木曜日
欠点 ? EMはk-meansよりも遅い ? 局所最適性しか保証しないので、大域的最適 解を得るには何度かrandom restartさせる必要 ? クラスタ数Kはどうやって決めるの？ ? 勘、情報量基準、ノンパラベイズ 12年6月7日木曜日
summary ? EMアルゴリズムとは ? 隠れ変数を仮定した場合の最尤推定法 ? 隠れ変数が見える完全データの対数尤度は簡単に求まる ? 隠れ変数をでっち上げる。現状のパラメタから求めた事 後確率についての期待値Q関数を求める(E-step) ? ラグランジュの未定乗数法を用いてQ関数最大化(M-step) ? 単調減少性 、局所最適性の保証 / ランダムリスタートの 必要 性 12年6月7日木曜日

More Related Content

Oshasta em

  • 1. くり ざっ EMアルゴリズム入門 2012/06/06 20:40-21:00 おしゃれstatistics 勉強会 @teikaw 12年6月7日木曜日
  • 2. 初めまして ? 山田 直敬 @teikaw ? 東京大学 情報理工学系 研究科 M1 ? 機械学習の研究をして います ? 特技はヴィオラ演奏。 たまにライブやります 12年6月7日木曜日
  • 3. 本日のキーワード ? ベイズの定理、事後確率 ? 最尤推定、ラグランジュの未定乗数法 ? k-means法 前提知識 ? 多変量正規分布 ? 隠れ変数、混合モデル 今日の内容 ? EM アルゴリズム 発展形 ? 変分ベイズ、ノンパラベイズ 12年6月7日木曜日
  • 4. 発表の流れ ? 【動機づけ】 混合正規分布モデルの紹介 ? 【導入】EMアルゴリズム = 隠れ変数を仮定した最尤推定 ? 【定式化】具体的な中身 ? 【評価】 EMアルゴリズムの諸性質、一般論 なめ は少 数式 12年6月7日木曜日
  • 5. みんな大好きk-means法 ? クラスタリングといえばこれ ? 丸いクラスタができる ? クラスタ内の分散が一定であ ることが暗に仮定 http://www.aishack.in/2010/07/k-means-clustering/ ? クラスタのメンバーが同じくら いの数だけ存在することも暗 に仮定される ? データに偏りがあるとうまくいかない http://www.kamishima.net/jp/clustering/ 12年6月7日木曜日
  • 6. そこで混合正规分布モデル (Gaussian Mixture Model; GMM) ? データが複数の正規分布の 重ねあわせによって生成され たと考える。 K p(x;θ ) = ∑ π k N ( ? k , Σ k ) k=1 ? 分散の違う分布でフィット 可能。柔軟性が高い ? 事後確率最大となるような クラスタを決定すれば良い http://scikit-learn.org/stable/modules/mixture.html 12年6月7日木曜日
  • 7. 骋惭惭のパラメタを最尤推定で求めたいが… 混合比,平均, 分散共分散行列 の組(π,μ, ∑)をk個 K データ一つあたりの尤度は p(x;θ ) = ∑ π k N ( ?k , Σ k ) だから、 k=1 i.i.dに生成した全データに対する対数尤度は N N K ln p(X;θ ) = ln ∏ p(x;θ ) = ∑ ln∑ π k N ( ? k , Σ k ) n=1 n=1 k=1 となる。 ただし、 不都合：logの中に足し算の形 logとexpがキャンセルされない K ∑π exp {(x ? ? ) Σ (x ? ? )}. 1 k = 1 , N ( ?, Σ) = T ?1 k=1 2πΣ 混合正規分布の対数尤度関数は、ラグランジュの未定乗数法を 用いて直接最大化しようとしても、解析解が求まらない 12年6月7日木曜日
  • 8. 隠れ変数を導入する ? データの生成過程を次の ようにモデル化する ? まず、混合正規分布の どのクラスタに属する のかが決まる 今見えているデータXは不完全だ～ 非観測な情報=隠れ変数Z p(Z=k)= πk ? 決められた正規分布に 従ってデータが発生 p(x|Z=k;θ) = N (μk,∑k ) p(x;θ) = ∑ p(x|Z;θ)p(Z) Z = ∑ πk N(μk,∑k) k 潜在変数(ラベル)Zが与えられていると仮定 12年6月7日木曜日
  • 9. 都合のいい完全データ｛X,Z} ? データセットXの全ての要素に対して、 ラベル(隠れ変数)Zが分かっている状態 ? 例えば, Zn=j の時、尤度は簡単な形に p(xn , zn = j;θ ) = π j N(xn ; ? j, Σ j ) ? znk は、kがデータ xn のラベルならば1 , from Bishop PRML Chapter 9 p.433 それ以外なら0を取るメンバシップ変数 N K とすると、 ln p(X, Z;θ ) = ∑ ∑ znk {ln π k + ln N(xn ; ? k, Σ k )} n=1 k=1 ? 完全データに対する対数尤度は次のよ logの中に足し算なし。 うになる 実質的な計算は正規分布一つの時と全く同じ 12年6月7日木曜日
  • 10. かね お 待ち EMアルゴリズム ? 不完全データに対して、隠れ変数を仮定した場合の最尤推定法。 N ? 本来解くべき問題はmax ln p(X;θ ) = ∑ ln∑ p(x | Z;θ )p(Z ) 不完全データの対数尤度 n=1 Z だが潜在変数の総和がlogの中に入っているため解析解が得られず。 ? 無いものねだりで隠れ変数(ラベルデータ)Zが与えられていると仮定し て、完全データの対数尤度を最大化する。これは解析解OK N K ln p(X, Z;θ ) = ∑ ∑ znk {ln π k + ln N(xn ; ? k, Σ k )} n=1 k=1 ? 隠れ変数(ラベルデータ)は直接知ることはできず、実際はZの事後確率 しか分からない。そこでラベルを推定するために、ひとまず前回のパ ラメタを利用する。(これが反復法になる理由) 12年6月7日木曜日
  • 11. 贰惭アルゴリズム详细 ? INIT ? 忘却-step(仮) ? 不完全データのことは忘れる！！ ? これからは潜在変数を自分で推定し、 完全データで計算すると誓う ? 適当な初期化パラメータθ を設定 old 12年6月7日木曜日
  • 12. Expectation Maximization ? E-Step (Expectation) ? 潜在変数を推定する ? すなわち p(Z | X; θold)を計算する(Bayesの定理) ? p(Z | X; θold)= p(X | Z; θold) p(Z; θold)/ p(X; θold) ? M-Step(Maximization) ? θnew = arg max Q(θ, θold) を計算する ? ここで Q(θ ,θ old ) = ∑ Z p(Z | X;θ old ) ln p(X, Z;θ ) 完全データの対数尤度の 潜在変数の事後分布についての期待値 ? θが収束するまで繰り返す 12年6月7日木曜日
  • 13. 蚕関数のおいしい性质 ? じつはEMアルゴリズムの各ステップで ln p(X;θ) = Q(θ,θold) + const が成立。忘れていたはずの不完全データのmaxを 毎ステップ解いていたところがpoint ? しかも、Q関数は各ステップで単調増加するの で、収束値の局所最適性が保証される！ ? (証明略) 12年6月7日木曜日
  • 14. 欠点 ? EMはk-meansよりも遅い ? 局所最適性しか保証しないので、大域的最適 解を得るには何度かrandom restartさせる必要 ? クラスタ数Kはどうやって決めるの？ ? 勘、情報量基準、ノンパラベイズ 12年6月7日木曜日
  • 15. summary ? EMアルゴリズムとは ? 隠れ変数を仮定した場合の最尤推定法 ? 隠れ変数が見える完全データの対数尤度は簡単に求まる ? 隠れ変数をでっち上げる。現状のパラメタから求めた事 後確率についての期待値Q関数を求める(E-step) ? ラグランジュの未定乗数法を用いてQ関数最大化(M-step) ? 単調減少性 、局所最適性の保証 / ランダムリスタートの 必要 性 12年6月7日木曜日