EMアルゴリズム （英 えい expectation–maximization algorithm ）とは、統計 とうけい 学 がく 確 かく 率 りつ モデル のパラメータを最 さい 尤 ゆう 推定 すいてい 手法 しゅほう 一 ひと 観測 かんそく 不可能 ふかのう 潜在 せんざい 変数 へんすう 確 かく 率 りつ 依存 いぞん 場合 ばあい 用 もち EM法 ほう 、期待 きたい 値 ち 最大 さいだい 化 か 法 ほう 呼 よ 一般 いっぱん 性 せい 高 たか 機械 きかい 学習 がくしゅう 音声 おんせい 認識 にんしき 因子 いんし 分析 ぶんせき 広汎 こうはん 応用 おうよう
EMアルゴリズムは反復 はんぷく 法 ほう 一種 いっしゅ 期待 きたい 値 ち 英 えい expectation, E ) ステップと最大 さいだい 化 か 英 えい maximization, M )ステップを交互 こうご 繰 く 返 かえ 計算 けいさん 進行 しんこう 現在 げんざい 推定 すいてい 潜在 せんざい 変数 へんすう 分布 ぶんぷ 基 もと 尤 ゆう 度 ど 期待 きたい 値 ち 計算 けいさん 求 もと 尤 ゆう 度 ど 期待 きたい 値 ち 最大 さいだい 化 か 求 もと 求 もと 次 つぎ 使 つか 潜在 せんざい 変数 へんすう 分布 ぶんぷ 決定 けってい 用 もち
今 いま 値 ち x z 取 と 確 かく 率 りつ 分布 ぶんぷ 確 かく 率 りつ 分布 ぶんぷ 確 かく 率 りつ 密度 みつど 関数 かんすう
p
(
x
,
z
|
θ しーた )
{\displaystyle p(x,z|\theta )}
未知 みち 母 はは 数 すう
θ しーた ∈
R
m
{\displaystyle \theta \in \mathbb {R} ^{m}}
R
{\displaystyle \mathbb {R} }
実数 じっすう 全体 ぜんたい 集合 しゅうごう 表 あらわ
そして
p
(
x
,
z
|
θ しーた )
{\displaystyle p(x,z|\theta )}
従 したが 標本 ひょうほん
(
x
1
,
z
1
)
,
…
,
(
x
n
,
z
n
)
{\displaystyle (x_{1},z_{1}),\ldots ,(x_{n},z_{n})}
独立 どくりつ 抽出 ちゅうしゅつ 何 なん 事情 じじょう
Z
=
(
z
1
,
…
,
z
n
)
{\displaystyle Z=(z_{1},\ldots ,z_{n})}
値 ね 観測 かんそく
X
=
(
x
1
,
…
,
x
n
)
{\displaystyle X=(x_{1},\ldots ,x_{n})}
観測 かんそく 実 じつ 応用 おうよう 上 じょう 例 たと
θ しーた =
(
θ しーた
1
,
θ しーた
2
)
{\displaystyle \theta =(\theta _{1},\theta _{2})}
形 かたち 観測 かんそく 不能 ふのう
z
i
∼
p
1
(
z
|
θ しーた
1
)
{\displaystyle z_{i}\sim p_{1}(z|\theta _{1})}
選 えら 後 のち
z
i
{\displaystyle z_{i}}
依存 いぞん 観測 かんそく 可能 かのう
x
i
∼
p
2
(
x
|
θ しーた
2
,
z
i
)
{\displaystyle x_{i}\sim p_{2}(x|\theta _{2},z_{i})}
選 えら 使 つか 事 こと 多 おお 必 かなら
簡単 かんたん 為 ため 記号 きごう 混用 こんよう X Z 同時 どうじ 確 かく 率 りつ 分布 ぶんぷ 確 かく 率 りつ 密度 みつど 関数 かんすう
p
(
X
,
Z
|
θ しーた )
{\displaystyle p(X,Z|\theta )}
書 か 以下 いか Z 離散 りさん 変数 へんすう 場合 ばあい 説明 せつめい Z 連続 れんぞく 変数 へんすう 場合 ばあい 総和 そうわ 積分 せきぶん 置 お 換 か 以外 いがい 同様 どうよう [ 3]
このような状況 じょうきょう 母 はは 数 すう θ しーた 最 さい 尤 ゆう 推定 すいてい 事 こと 我々 われわれ 目標 もくひょう Z 知 し 場合 ばあい
X
=
(
x
1
,
…
,
x
n
)
{\displaystyle X=(x_{1},\ldots ,x_{n})}
関 かん 対数 たいすう 尤 ゆう 度 ど
ℓ
(
θ しーた
|
X
)
:=
log
p
(
X
|
θ しーた )
=
log
∑
Z
p
(
X
,
Z
|
θ しーた )
{\displaystyle \ell (\theta |X):=\log p(X|\theta )=\log \sum _{Z}p(X,Z|\theta )}
を最大 さいだい 値 ち 直接 ちょくせつ 計算 けいさん 一般 いっぱん 簡単 かんたん
EMアルゴリズムは、反復 はんぷく 法 ほう 数列 すうれつ
θ しーた ^
(
t
)
{\displaystyle {\hat {\theta }}^{(t)}}
対数 たいすう 尤 ゆう 度 ど
ℓ
(
θ しーた ^
(
t
)
|
X
)
{\displaystyle \ell ({\hat {\theta }}^{(t)}|X)}
単調 たんちょう 非 ひ 減少 げんしょう 作 つく 最 さい 尤 ゆう 推定 すいてい 量 りょう
θ しーた ^
M
L
E
{\displaystyle {\hat {\theta }}_{\mathrm {MLE} }}
ℓ
(
θ しーた ^
M
L
E
|
X
)
≥
ℓ
(
θ しーた ^
(
t
)
|
X
)
{\displaystyle \ell ({\hat {\theta }}_{\mathrm {MLE} }|X)\geq \ell ({\hat {\theta }}^{(t)}|X)}
である事 こと
ℓ
(
θ しーた ^
M
L
E
|
X
)
{\displaystyle \ell ({\hat {\theta }}_{\mathrm {MLE} }|X)}
有限 ゆうげん
ℓ
(
θ しーた ^
(
t
)
|
X
)
{\displaystyle \ell ({\hat {\theta }}^{(t)}|X)}
単調 たんちょう 性 せい
ℓ
(
θ しーた ^
(
t
)
|
X
)
{\displaystyle \ell ({\hat {\theta }}^{(t)}|X)}
必 かなら 収束 しゅうそく
EMアルゴリズムでは、以下 いか 手順 てじゅん 数列 すうれつ
θ しーた ^
(
0
)
,
θ しーた ^
(
1
)
,
…
{\displaystyle {\hat {\theta }}^{(0)},{\hat {\theta }}^{(1)},\ldots }
作 つく [ 3]
初期 しょき 値 ち
θ しーた ^
(
0
)
{\displaystyle {\hat {\theta }}^{(0)}}
何 なん 方法 ほうほう 選 えら
t
=
0
,
1
,
…
{\displaystyle t=0,1,\ldots }
対 たい 以下 いか 実行 じっこう E ステップ :
p
(
Z
|
X
,
θ しーた ^
(
t
)
)
{\displaystyle p(Z|X,{\hat {\theta }}^{(t)})}
求 もと M ステップ :
θ しーた ^
(
t
+
1
)
=
a
r
g
m
a
x
θ しーた
Q
(
θ しーた
|
θ しーた ^
(
t
)
)
{\displaystyle {\hat {\theta }}^{(t+1)}={\underset {\theta }{\operatorname {arg\,max} }}\ Q(\theta |{\hat {\theta }}^{(t)})\,}
求 もと ここでQ は対数 たいすう 尤 ゆう 度 ど 関数 かんすう
log
p
(
X
,
Z
|
θ しーた )
{\displaystyle \log p(X,Z|\theta )}
Z 関 かん 条件 じょうけん 付 つ 期待 きたい 値 ち
Q
(
θ しーた
|
θ しーた
(
t
)
)
:=
E
Z
|
X
,
θ しーた ^
(
t
)
[
log
p
(
X
,
Z
|
θ しーた )
]
=
∑
Z
p
(
Z
|
X
,
θ しーた ^
(
t
)
)
log
p
(
X
,
Z
|
θ しーた )
{\displaystyle Q(\theta |\theta ^{(t)}):=\operatorname {E} _{Z|X,{\hat {\theta }}^{(t)}}{\big [}\log p(X,Z|\theta ){\big ]}=\sum _{Z}p(Z|X,{\hat {\theta }}^{(t)})\log p(X,Z|\theta )\,}
である。実 じつ 応用 おうよう 上 じょう
θ しーた ^
(
t
)
{\displaystyle {\hat {\theta }}^{(t)}}
値 ね 十分 じゅうぶん 小 ちい 判定 はんてい 何 なん 条件 じょうけん 事前 じぜん 定 さだ 条件 じょうけん 満 み 上述 じょうじゅつ 終了 しゅうりょう 終了 しゅうりょう 条件 じょうけん 値 ち 対数 たいすう 尤 ゆう 度 ど 関数 かんすう 使 つか 定 さだ [ 3]
EステップとMステップの切 き 目 め 書籍 しょせき 異 こと 注意 ちゅうい 必要 ひつよう 。本 ほん 項 こう 次節 じせつ 議論 ぎろん 整合 せいごう 性 せい 為 ため 文献 ぶんけん [ 3] 切 き 目 め 従 したが 文献 ぶんけん [ 4]
Q
(
θ しーた
|
θ しーた ^
(
t
)
)
{\displaystyle Q(\theta |{\hat {\theta }}^{(t)})}
計算 けいさん 所 ところ
Q
(
θ しーた
|
θ しーた ^
(
t
)
)
{\displaystyle Q(\theta |{\hat {\theta }}^{(t)})}
a
r
g
m
a
x
{\displaystyle \operatorname {arg\,max} }
取 と
ステップの名称 めいしょう 期待 きたい 値 ち 最大 さいだい 化 か 略 りゃく [ 4] 文献 ぶんけん [ 4]
Q
(
θ しーた
|
θ しーた ^
(
t
)
)
{\displaystyle Q(\theta |{\hat {\theta }}^{(t)})}
求 もと 為 ため 期待 きたい 値 ち 計算 けいさん
Q
(
θ しーた
|
θ しーた ^
(
t
)
)
{\displaystyle Q(\theta |{\hat {\theta }}^{(t)})}
a
r
g
m
a
x
{\displaystyle \operatorname {arg\,max} }
取 と 名称 めいしょう 由来 ゆらい
EMアルゴリズムで我々 われわれ 求 もと
X
=
(
x
1
,
…
,
x
n
)
{\displaystyle X=(x_{1},\ldots ,x_{n})}
観測 かんそく 際 さい 対数 たいすう 尤 ゆう 度 ど
ℓ
(
θ しーた
|
X
)
:=
log
p
(
X
|
θ しーた )
{\displaystyle \ell (\theta |X):=\log p(X|\theta )}
を最大 さいだい 化 か 母 はは 数 すう
θ しーた
{\displaystyle \theta }
動作 どうさ 原理 げんり 説明 せつめい 為 ため 以下 いか 汎 ひろし 関数 かんすう 考 かんが
L
(
q
,
θ しーた )
:=
∑
Z
q
(
Z
)
log
p
(
X
,
Z
|
θ しーた )
q
(
Z
)
{\displaystyle {\mathcal {L}}(q,\theta ):=\sum _{Z}q(Z)\log {p(X,Z|\theta ) \over q(Z)}}
Eq.1 )ここで
q
(
Z
)
{\displaystyle q(Z)}
任意 にんい 確 かく 率 りつ 密度 みつど 関数 かんすう
p
X
,
θ しーた
(
Z
)
:=
p
(
Z
|
X
,
θ しーた )
{\displaystyle p_{X,\theta }(Z):=p(Z|X,\theta )}
p
(
Z
|
X
,
θ しーた )
p
(
X
|
θ しーた )
=
p
(
X
,
Z
|
θ しーた )
{\displaystyle p(Z|X,\theta )p(X|\theta )=p(X,Z|\theta )}
カルバック・ライブラー情報 じょうほう 量 りょう
K
L
(
q
|
|
p
X
,
θ しーた
)
=
−
∑
Z
q
(
Z
)
log
p
(
Z
|
X
,
θ しーた )
q
(
Z
)
{\displaystyle \mathrm {KL} (q||p_{X,\theta })=-\sum _{Z}q(Z)\log {p(Z|X,\theta ) \over q(Z)}}
を使 つか
L
(
q
,
θ しーた )
=
ℓ
(
θ しーた
|
X
)
−
K
L
(
q
|
|
p
X
,
θ しーた
)
{\displaystyle {\mathcal {L}}(q,\theta )=\ell (\theta |X)-\mathrm {KL} (q||p_{X,\theta })}
Eq.2 )と書 か 事 こと 分 わ 情報 じょうほう 量 りょう 常 つね 非負 ひふ 事 こと ギブスの不等式 ふとうしき ）から、
ℓ
(
θ しーた
|
X
)
≥
L
(
q
,
θ しーた )
{\displaystyle \ell (\theta |X)\geq {\mathcal {L}}(q,\theta )}
であるので、
L
(
q
,
θ しーた )
{\displaystyle {\mathcal {L}}(q,\theta )}
ℓ
(
θ しーた
|
X
)
{\displaystyle \ell (\theta |X)}
下限 かげん 下限 かげん
L
(
q
,
θ しーた )
{\displaystyle {\mathcal {L}}(q,\theta )}
逐次 ちくじ 的 てき 改善 かいぜん
ℓ
(
θ しーた
|
X
)
{\displaystyle \ell (\theta |X)}
可能 かのう 限 かぎ 最大 さいだい 化 か 以下 いか 書 か 換 か 事 こと 示 しめ 事 こと [ 3]
E ステップ :
q
^
(
t
)
=
a
r
g
m
a
x
q
L
(
q
,
θ しーた ^
(
t
)
)
{\displaystyle {\hat {q}}^{(t)}={\underset {q}{\operatorname {arg\,max} }}{\mathcal {L}}(q,{\hat {\theta }}^{(t)})}
求 もと M ステップ :
θ しーた ^
(
t
+
1
)
=
a
r
g
m
a
x
θ しーた
L
(
q
^
(
t
)
,
θ しーた )
{\displaystyle {\hat {\theta }}^{(t+1)}={\underset {\theta }{\operatorname {arg\,max} }}{\mathcal {L}}({\hat {q}}^{(t)},\theta )}
求 もと この事実 じじつ 対数 たいすう 尤 ゆう 度 ど
ℓ
(
θ しーた ^
(
t
)
|
X
)
{\displaystyle \ell ({\hat {\theta }}^{(t)}|X)}
単調 たんちょう 非 ひ 減少 げんしょう 性 せい 明 あき 従 したが 但 ただ 反復 はんぷく 法 ほう 常 つね 初期 しょき 値 ち 尤 ゆう 度 ど 最大 さいだい 点 てん 極大 きょくだい 点 てん 到達 とうたつ 停止 ていし 可能 かのう 性 せい
本節 ほんぶし 上述 じょうじゅつ 書 か 換 か 示 しめ 本節 ほんぶし 証明 しょうめい 文献 ぶんけん [ 3] 参考 さんこう
カルバック・ライブラー情報 じょうほう 量 りょう
K
L
(
q
|
|
p
X
,
θ しーた
)
{\displaystyle \mathrm {KL} (q||p_{X,\theta })}
最小 さいしょう 値 ち
q
=
p
θ しーた ,
X
{\displaystyle q=p_{\theta ,X}}
場合 ばあい 事 こと Eq.2
L
(
q
,
θ しーた )
{\displaystyle {\mathcal {L}}(q,\theta )}
q
(
Z
)
=
p
(
Z
|
X
,
θ しーた )
{\displaystyle q(Z)=p(Z|X,\theta )}
が満 み 場合 ばあい 最大 さいだい 値 ち 取 と
θ しーた =
θ しーた ^
(
t
)
{\displaystyle \theta ={\hat {\theta }}^{(t)}}
固定 こてい 状態 じょうたい
L
(
q
,
θ しーた )
{\displaystyle {\mathcal {L}}(q,\theta )}
最大 さいだい 化 か
q
{\displaystyle q}
q
^
(
t
)
:=
p
X
,
θ しーた ^
(
t
)
=
a
r
g
m
a
x
q
L
(
q
,
θ しーた ^
(
t
)
)
{\displaystyle {\hat {q}}^{(t)}:=p_{X,{\hat {\theta }}^{(t)}}={\underset {q}{\operatorname {arg\,max} }}{\mathcal {L}}(q,{\hat {\theta }}^{(t)})}
を求 もと
L
(
q
,
θ しーた )
{\displaystyle {\mathcal {L}}(q,\theta )}
定義 ていぎ 式 しき Eq.1
q
^
(
t
)
=
p
X
,
θ しーた ^
(
t
)
{\displaystyle {\hat {q}}^{(t)}=p_{X,{\hat {\theta }}^{(t)}}}
代入 だいにゅう
L
(
q
^
(
t
)
,
θ しーた )
=
∑
Z
p
(
Z
|
X
,
θ しーた
(
t
)
)
log
p
(
X
,
Z
|
θ しーた )
p
(
Z
|
X
,
θ しーた
(
t
)
)
=
Q
(
θ しーた
|
θ しーた
(
t
)
)
−
H
X
,
θ しーた
(
t
)
(
Z
)
{\displaystyle {\mathcal {L}}({\hat {q}}^{(t)},\theta )=\sum _{Z}p(Z|X,\theta ^{(t)})\log {p(X,Z|\theta ) \over p(Z|X,\theta ^{(t)})}=Q(\theta |\theta ^{(t)})-H_{X,\theta ^{(t)}}(Z)}
が成立 せいりつ
H
X
,
θ しーた
(
t
)
(
Z
)
=
∑
Z
p
(
Z
|
X
,
θ しーた
(
t
)
)
log
p
(
Z
|
X
,
θ しーた
(
t
)
)
{\displaystyle H_{X,\theta ^{(t)}}(Z)=\textstyle \sum _{Z}p(Z|X,\theta ^{(t)})\log p(Z|X,\theta ^{(t)})}
条件 じょうけん 付 つ 上 うえ 式 しき 右辺 うへん 第 だい 二 に 項 こう θ しーた 依存 いぞん
θ しーた ^
(
t
+
1
)
=
a
r
g
m
a
x
θ しーた
Q
(
θ しーた
|
θ しーた ^
(
t
)
)
=
a
r
g
m
a
x
θ しーた
L
(
p
X
,
θ しーた ^
(
t
)
,
θ しーた )
{\displaystyle {\hat {\theta }}^{(t+1)}={\underset {\theta }{\operatorname {arg\,max} }}Q(\theta |{\hat {\theta }}^{(t)})={\underset {\theta }{\operatorname {arg\,max} }}{\mathcal {L}}(p_{X,{\hat {\theta }}^{(t)}},\theta )}
が成立 せいりつ
EMアルゴリズムは観測 かんそく 対数 たいすう 尤 ゆう 度 ど 繰 く 返 かえ 最大 さいだい 化 か 正確 せいかく 関数 かんすう α あるふぁ 一般 いっぱん 化 か 対数 たいすう 用 もち 特例 とくれい 含 ふく 作 つく 上 あ 場合 ばあい 尤 ゆう 度 ど α あるふぁ 尤 ゆう 度 ど 比 ひ α あるふぁ 用 もち 基本 きほん 等式 とうしき 導 みちび 得 え α あるふぁ [ 5] 含 ふく α あるふぁ 適切 てきせつ α あるふぁ 選 えら 高速 こうそく 隠 かく 推定 すいてい 含 ふく α あるふぁ 高速 こうそく α あるふぁ 得 え [ 6]
EMアルゴリズムは、アーサー・デンプスター （英語 えいご 版 ばん ナン・レアード （英語 えいご 版 ばん ドナルド・ルービン による1977年 ねん 論文 ろんぶん [ 7] 導入 どうにゅう 名 な 付 つ 彼 かれ 複数 ふくすう 著者 ちょしゃ 特殊 とくしゅ 文脈 ぶんみゃく 提案 ていあん 述 の 上 うえ 一般 いっぱん 化 か 行 おこな 背後 はいご 理論 りろん 追求 ついきゅう
本来 ほんらい 期待 きたい 値 ち 評価 ひょうか 潜在 せんざい 変数 へんすう 値 ね 列挙 れっきょ 必要 ひつよう 効率 こうりつ 的 てき 扱 あつか 分布 ぶんぷ 限 かぎ 後 ご マルコフ連鎖 れんさ 法 ほう や変 へん 分 ぶん 法 ほう （英語 えいご 版 ばん 考案 こうあん 一般 いっぱん 分布 ぶんぷ 現実 げんじつ 的 てき 時間 じかん 計算 けいさん 可能 かのう
^ a b c d e f #PRML pp.156, 164-171
^ a b c #ESL pp.316-317.
^ Matsuyama, Yasuo (2003). “The α あるふぁ α あるふぁ IEEE Transactions on Information Theory 49 (3): 692-706. ^ Matsuyama, Yasuo (2011). “Hidden Markov model estimation based on alpha-EM algorithm: Discrete and continuous alpha-HMMs”. International Joint Conference on Neural Networks : 808-816. ^ Dempster, A.P., Laird, N.M., Rubin, D.B., (1977). “Maximum Likelihood from Incomplete Data via the EM Algorithm”. Journal of the Royal Statistical Society . Series B (Methodological) 39 (1): 1–38. JSTOR2984875 . MR 0501537 .
Robert Hogg, Joseph McKean and Allen Craig. Introduction to Mathematical Statistics . pp. 359-364. Upper Saddle River, NJ: Pearson Prentice Hall, 2005.
The on-line textbook: Information Theory, Inference, and Learning Algorithms , by David J.C. MacKay includes simple examples of the E-M algorithm such as clustering using the soft K-means algorithm, and emphasizes the variational view of the E-M algorithm.A Gentle Tutorial of the EM Algorithm and its Application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models , by Jeff Bilmes includes a simplified derivation of the EM equations for Gaussian Mixtures and Gaussian Mixture Hidden Markov Models.Variational Algorithms for Approximate Bayesian Inference , by M. J. Beal includes comparisons of EM to Variational Bayesian EM and derivations of several models including Variational Bayesian HMMs.The Expectation Maximization Algorithm , by Frank Dellaert, gives an easier explanation of EM algorithm in terms of lowerbound maximization.The Expectation Maximization Algorithm: A short tutorial , A self contained derivation of the EM Algorithm by Sean Borman.The EM Algorithm , by Xiaojin Zhu.Geoffrey J. McLachlan and Thriyambakam Krishnan: "The EM Algorithm and Extensions", Wiley series in probability and statistics, John Wiley & Sons, Inc., ISBN 0-471-12358-7 (1997).
Geoffrey J. McLachlan and Thriyambakam Krishnan:"The EM Algorithm and Extensions", 2nd Edition, Wiley & Sons Inc., ISBN 978-0-471-20170-0 (February 2008). 上記 じょうき 改訂 かいてい 第 だい 版 はん
小西 こにし 貞 さだ 則 そく 越智 おち 義道 よしみち 大森 おおもり 裕 ひろし 浩 ひろし 計算 けいさん 統計 とうけい 学 がく 方法 ほうほう 朝倉書店 あさくらしょてん 予測 よそく 発見 はっけん 科学 かがく ISBN 978-4-254-12785-0 、2008年 ねん 月 がつ 日 にち 関原 せきはら 謙介 けんすけ 信号 しんごう 処理 しょり 共立 きょうりつ 出版 しゅっぱん ISBN 978-4-320-08574-9 、2015年 ねん 月 がつ 関原 せきはら 謙介 けんすけ 推論 すいろん 基礎 きそ 信号 しんごう 処理 しょり 応用 おうよう Kenneth Lange: "MM Optimization Algorithms", SIAM, ISBN 978-1-611974-39-3 (2016). ※ "MM algorithm " は "EM" アルゴリズムの一般 いっぱん 化 か 提唱 ていしょう
黒田 くろだ 正博 まさひろ 共立 きょうりつ 出版 しゅっぱん 統計 とうけい 学 がく 巻 かん ISBN 978-4-320-11269-8 、2020年 ねん 月 がつ 日 にち 
Category:データマイニング
![{\displaystyle Q(\theta |\theta ^{(t)}):=\operatorname {E} _{Z|X,{\hat {\theta }}^{(t)}}{\big [}\log p(X,Z|\theta ){\big ]}=\sum _{Z}p(Z|X,{\hat {\theta }}^{(t)})\log p(X,Z|\theta )\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/88e40d2e7e87008ad50afa845d7f198343282ae8)
