<>:42: SyntaxWarning: invalid escape sequence '\m'
<>:43: SyntaxWarning: invalid escape sequence '\m'
<>:44: SyntaxWarning: invalid escape sequence '\m'
<>:42: SyntaxWarning: invalid escape sequence '\m'
<>:43: SyntaxWarning: invalid escape sequence '\m'
<>:44: SyntaxWarning: invalid escape sequence '\m'
/var/folders/gx/6w78f6997l5___173r25fp3m0000gn/T/ipykernel_74977/1951455018.py:42: SyntaxWarning: invalid escape sequence '\m'
plt.title('Log Likelihood for 500 Observations with $(\mu_1,\mu_2)=(0,3.1)$')
/var/folders/gx/6w78f6997l5___173r25fp3m0000gn/T/ipykernel_74977/1951455018.py:43: SyntaxWarning: invalid escape sequence '\m'
plt.xlabel('$\mu_1$')
/var/folders/gx/6w78f6997l5___173r25fp3m0000gn/T/ipykernel_74977/1951455018.py:44: SyntaxWarning: invalid escape sequence '\m'
plt.ylabel('$\mu_2$')
A Blog Entry on Bayesian Computation by an Applied Mathematician
$$
$$
1 最尤推定
クラスタリングを一度さっぱり忘れて,最尤推定を思い出してみる.
1.1 最尤推定と最適化
すなわち,最尤推定量とは最適化問題の解として定式化されるのである.
最大値点であるということは,停留点である必要があるから,微分が零になるという条件を通じて解析的に求まることもある.この
また,計算機的な方法では,Iterative Propertional Fittting や勾配に基づく最適化手法を用いることも考えられる (Robbins and Monro, 1951), (Fletcher, 1987).
最尤推定量が解析的に求まらない場面には,代表的には欠測モデルなどがある.欠測モデルは,観測される確率変数
この場合には,モデルの構造を利用して最尤推定量を求めるための MM アルゴリズム (Sun et al., 2016) の例がある.これが EM アルゴリズム (Dempster et al., 1977) である.
現在でも,その他の MM アルゴリズムが,種々の最適化問題に対する “problem-driven algorithm” であり続けている (T. T. Wu and Lange, 2010).
1.2 最尤推定と Bayes 推定
最尤推定は,一様事前分布をおいた場合の MAP 推定 とみなせる.この意味で,Bayes 推定の特殊な場合である.
Bayes 推定は MCMC や SMC などのサンプリング法によって統一的に行えるが,殊に MAP 推定に対しては,効率的な最適化法として EM アルゴリズムが使える,ということである.
より一般の Bayes 推定に対応できるような EM アルゴリズムの一般化が,近似アルゴリズムとして存在する.これが次稿で紹介する 変分推論 である.
2 EM アルゴリズム
EM アルゴリズムは,混合モデルに対する最尤推定アルゴリズムである.一般に,目的関数が
2.1 欠測データと混合モデル
欠測データ (incomplete data) とは,2つの確率変数
これは,
これは潜在変数
このように,
2.2 EM アルゴリズム
値域
この事実に基づき,
-ステップ: を について最大化する. より, で最大化される.8 -ステップ: を について最大化する. より, の停留点で最大化される.
総じて,EM アルゴリズムは
2.3 -ステップの変形
モデル
そこで,
また,この
2.4 -ステップの変形
しかしこれが難しい場合,厳密な最大化は行わず,代わりにせめて「現状よりは大きくする」ことを実行するアルゴリズムを用いた場合,これを 一般化 EM アルゴリズム (GEM: Generalized EM) ともいう (Bishop, 2006, p. 454), (Hastie et al., 2009, p. 277).
例えば,大域的最大化の代わりに条件付き最大化を行うこととする方法 ECM (Expectation Conditional Maximization) などがその例である (Meng and Rubin, 1991), (Meng and Rubin, 1993).(Christian P. Robert and Casella, 2004, p. 200) も参照.
2.5 EM アルゴリズムの有効性
よって,EM アルゴリズムは局所解には収束する.
しかし,常に尤度が単調増加するという性質上,局所解に囚われてしまった場合,そこから逃れることはないことになる.
大域解に収束することを保証したい場合は,異なる初期値で複数回 EM アルゴリズムを実行するか,擬似除冷 (simulated annealing)12 などの別の手法を用いることを考える必要がある (Finch et al., 1989).
3 EM アルゴリズムの実装(Gauss 有限混合モデルの場合)
負担率に確率モデルを置いた場合,ソフト
EM アルゴリズムは一般に多峰性に弱いことをここで示す.13
3.1 Guass 有限混合モデル
ここでは,以下の,有限な混合モデルで,さらに混合される分布は正規であるものを考える:
Equation 3 は
3.2 Gauss 有限混合モデルでの EM アルゴリズム
Section 2.2 での議論を,今回の Gauss 有限混合モデルに当てはめてみる.
対数周辺尤度は
という下界を持つ.
これに基づき,観測
-ステップ: を計算して, に代入する. -ステップ: を について最大化する.これは,次の値を計算することに等しい:
3.3 -平均アルゴリズムとの対応
ハード
3.4 Gauss 混合モデルの場合17
実は,混合モデルでは,ここまで単純な例でさえ,尤度は多峰性を持つ.
試しに,
真値
3.5 EM アルゴリズムの初期値依存性
EM アルゴリズムはその初期値依存性からランダムな初期値から複数回実行してみる必要がある.モデル 4 の場合,その結果は次のようになる:
Code
class EM_1d:
"""
Gauss 有限混合モデルに対する EM アルゴリズム
Parameters:
- K (int): 混合成分の数.デフォルトは2.
- max_iter (int): アルゴリズムの最大反復回数.デフォルトは100.
- tol (float): 収束の閾値.連続する反復での対数尤度の差がこの値以下になった場合,アルゴリズムは収束したと見なされる.デフォルトは1e-4.
"""
def __init__(self, K=2, init=None, max_iter=100, tol=1e-4):
self.K = K
self.max_iter = max_iter
self.tol = tol
self.means = None
self.variances = None
self.mixing_coefficients = None
self.log_likelihood_history = []
self.mean_history = []
self.initial_value = init
def expectation(self, X):
"""
E ステップ
Parameters:
- X (ndarray): 観測データ.
"""
= X.shape[0]
N = np.zeros((N, self.K))
r for k in range(self.K):
= norm.pdf(X, self.means[k], np.sqrt(self.variances[k]))
pdf = self.mixing_coefficients[k] * pdf
r[:, k] /= r.sum(axis=1, keepdims=True)
r return r
def maximization(self, X, r):
"""
M ステップ
Parameters:
- X (ndarray): 観測データ.
- r (ndarray): 負担率.
"""
= X.shape[0]
N = r.sum(axis=0)
Nk self.means = (X.T @ r / Nk).T
self.variances = np.zeros(self.K)
for k in range(self.K):
= X - self.means[k]
diff self.variances[k] = (r[:, k] @ (diff ** 2)) / Nk[k]
self.mixing_coefficients = Nk / N
def compute_log_likelihood(self, X):
"""
対数尤度の計算
Parameters:
- X (ndarray): 観測データ.
"""
= 0
log_likelihood for x in X:
+= np.log(np.sum([self.mixing_coefficients[k] * norm.pdf(x, self.means[k], np.sqrt(self.variances[k])) for k in range(self.K)]))
log_likelihood return log_likelihood
def fit(self, X):
"""
EM アルゴリズムの実行
Parameters:
- X (ndarray): 観測データ.
"""
= X.shape[0]
N 42)
np.random.seed(
if self.initial_value is None:
= np.random.choice(N, self.K, replace=False)
random_indeces self.initial_value = X[random_indeces]
self.means = self.initial_value
self.initial_value = self.means
self.variances = np.ones(self.K)
self.mixing_coefficients = np.ones(self.K) / self.K
# 反復
for _ in range(self.max_iter):
= self.expectation(X)
r self.maximization(X, r)
= self.compute_log_likelihood(X)
log_likelihood self.log_likelihood_history.append(log_likelihood)
self.mean_history.append(self.means)
if len(self.log_likelihood_history) >= 2 and np.abs(self.log_likelihood_history[-1] - self.log_likelihood_history[-2]) < self.tol:
break
return self
<>:32: SyntaxWarning: invalid escape sequence '\m'
<>:33: SyntaxWarning: invalid escape sequence '\m'
<>:34: SyntaxWarning: invalid escape sequence '\m'
<>:32: SyntaxWarning: invalid escape sequence '\m'
<>:33: SyntaxWarning: invalid escape sequence '\m'
<>:34: SyntaxWarning: invalid escape sequence '\m'
/var/folders/gx/6w78f6997l5___173r25fp3m0000gn/T/ipykernel_74977/163584773.py:32: SyntaxWarning: invalid escape sequence '\m'
axs[1].set_title('Mean Values Progress ($\mu_1,\mu_2$)')
/var/folders/gx/6w78f6997l5___173r25fp3m0000gn/T/ipykernel_74977/163584773.py:33: SyntaxWarning: invalid escape sequence '\m'
axs[1].set_xlabel('$\mu_1$')
/var/folders/gx/6w78f6997l5___173r25fp3m0000gn/T/ipykernel_74977/163584773.py:34: SyntaxWarning: invalid escape sequence '\m'
axs[1].set_ylabel('$\mu_2$')
4 Monte Carlo 法による解決
Equation 1 の逆向きの関係
このような欠測モデルの文脈で Gibbs サンプラーを用いる手法は,データ拡張 の名前でも知られる (Tanner and Wong, 1987).
加えて,初期値依存性や局所解へのトラップが懸念されるという EM アルゴリズムの問題点を,MCMC はいずれも持ち合わせていない.
さらに,混合数
最尤推定の代わりに Bayes 推定を行なっているため,データ数が少なくとも,過学習の問題が起こりにくいという利点もある.
Bayes 階層モデルは複雑なモデルに対する表現力が高く,地球科学をはじめとして多くの応用分野で使われている (Hrafnkelsson, 2023).
4.1 Gibbs サンプリング
高次元な確率変数
- 任意の初期値
を与える. - 各
について, をサンプリングする. - 十分時間が経過した際,アルゴリズムの出力
は と同分布になる.
実際,
4.2 確率的 EM アルゴリズム
Gibbs サンプリングアルゴリズムは,EM アルゴリズム2.2の変形とみなせる:
-ステップ:EM アルゴリズムでは を評価するところであったが,Gibbs サンプリングでは, のサンプリングを行う. -ステップ:EM アルゴリズムでは を求めるところであったが,Gibbs サンプリングでは, のサンプリングを行う.
これは
4.2.1 EM アルゴリズムへの部分的な適用: -ステップ
またこの美点のみを用いて,
この場合,
4.2.2 EM アルゴリズムへの部分的な適用: -ステップ
Gibbs サンプリングの考え方を
4.3 諸言
欠測モデル2.1のように,一般に グラフィカルモデル として知られる,局所的な関係のみから指定されるモデルや潜在変数を持つモデルでは,Gibbs サンプリングにより効率的に結合分布からサンプリングができる.
MCMC はグラフィカルモデルを用いた Bayes 推論の,強力な武器である.22
References
Footnotes
(Carmer, 1946, p. 498) によると,(Fisher, 1912) が初出であるが,以前に Gauss がその特別な形を用いていた.また,(Carmer, 1946, p. 499) での定義はこことは違い,尤度関数の停留点(=尤度方程式の解)と定義している.↩︎
(Christian P. Robert and Casella, 2004, p. 174) 式(5.7).
を完備化された尤度 (completed likelihood) ともいう. を incomplete data, を complete data ともいう (Bishop, 2006, pp. 433, p.440).↩︎特に,隠れ Markov モデルの文脈では,EM アルゴリズムは Baum-Welch アルゴリズム とも呼ばれる (Chopin and Papaspiliopoulos, 2020, p. 70).↩︎
それぞれ,(Christian P. Robert, 2007, p. 330),(Christian P. Robert and Casella, 2004, p. 176),(Hastie et al., 2009, p. 276),↩︎
正確には確率核
.↩︎この
は多く とも表され, -関数ともいう. やその対数は 証拠 (evidence) ともいうので, は 証拠下界 (ELBO: Evidence Lower BOund) ともいう.↩︎式変形は (Bishop, 2006, p. 450) も参照.この
は観測 の下での,潜在変数 の条件付き分布である.しかし,このように双方を最大化ステップと見る変分法的な見方が出来るのである (Wainwright and Jordan, 2008, pp. 153–154), (Neal and Hinton, 1998), (Hastie et al., 2009, p. 277).よって,この -ステップも,GEM のように,必ずしも完全な最大化を達成する必要はないことがわかる (Neal and Hinton, 1998), (Bishop, 2006, p. 454).例えば変分近似を行った場合,変分 EM アルゴリズムができあがる (Wainwright and Jordan, 2008, p. 154).↩︎(Johnston et al., 2024) にも言及あり.↩︎
(Christian P. Robert and Casella, 2004, p. 177) 定理5.15,(Christian P. Robert, 2007, p. 334) 演習6.52.↩︎
この用語は (甘利俊一, 1989, p. 141) の 模擬除冷 の表現に触発された.↩︎
(Bishop, 2006, pp. 436–439) も参照.↩︎
(Christian P. Robert and Casella, 2004, pp. 181–182) 例5.19 も参照.↩︎
とした.↩︎(Christian P. Robert, 2007, p. 309) 補題6.3.6,(鎌谷研吾, 2020, p. 139) 定理5.7.↩︎
(Christian P. Robert and Casella, 2004, p. 200) 5.5.1 節も参照.↩︎