k-means・GMMとEMアルゴリズムの収束原理

ハードクラスタリングとソフトクラスタリング

クラスタリングは正解ラベルのない 教師なし学習 の代表で、データを似たもの同士のグループに分けます。割り当て方は二つに分かれます。ハードクラスタリングは各点をちょうど一つのクラスタへ排他的に割り当てます（k-means が典型）。ソフトクラスタリングは「クラスタ1に 0.7、クラスタ2に 0.3」のような所属確率を与えます（混合ガウスモデル＝GMM が典型）。

二つのクラスタの中間にある点を、ハードは無理に片方へ押し込みますが、ソフトは「どちらとも言い切れない」不確実性を数値のまま保持します。GMM のこの所属確率を responsibility（負担率） と呼び、EM アルゴリズムの心臓部になります。

GMM：混合ガウスの潜在変数モデル

GMM はデータが K 個のガウス分布の重み付き和から生成されたと仮定します。観測点 x の密度は次の混合分布です。

p(x) = Σ_{k=1..K} π_k · N(x | μ_k, Σ_k)
       π_k ≥ 0,  Σ_k π_k = 1

π_k は混合係数（各成分の事前の選ばれやすさ）、N(x | μ_k, Σ_k) は平均 μ_k・共分散 Σ_k のガウス密度です。鍵になるのが潜在変数 z。各点 x_n には「どの成分から生まれたか」を表す one-hot ベクトル z_n（成分 k なら z_nk = 1）が裏に存在すると考えます。生成の流れは、まず z_n を π に従って引いて使うガウスを決め、次にその成分のガウスから x_n を引く、というものです。

p(z_nk = 1) = π_k
p(x_n | z_nk = 1) = N(x_n | μ_k, Σ_k)

もし z が観測できていれば、成分ごとに点を集めて平均・分散を計算するだけで済みます。問題は z が見えないこと。z を周辺化して消した対数尤度を直接最大化しようとすると、

log p(X) = Σ_n log( Σ_k π_k · N(x_n | μ_k, Σ_k) )

log の中に Σ_k の和が入り込み、各成分のパラメータが和の中で絡み合うため、∂/∂μ_k = 0 を解いても閉じた解になりません。見えない z が尤度最大化を直接解けなくしている——ここが EM の出発点です。

EMアルゴリズム：E/Mステップの導出

EM は「z の事後分布を埋める E ステップ」と「埋めた z のもとでパラメータを更新する M ステップ」を交互に回します。

Eステップは、現在のパラメータのもとで各点の responsibility を計算します。これは z_nk = 1 の事後確率で、ベイズの定理そのものです。

γ_nk = p(z_nk = 1 | x_n)
     = π_k · N(x_n | μ_k, Σ_k) / Σ_j π_j · N(x_n | μ_j, Σ_j)

分子はその成分が x_n を説明する尤もらしさ、分母は全成分での正規化で、γ_nk は「点 n がクラスタ k にどれだけ所属するか」を表し Σ_k γ_nk = 1 を満たします。

Mステップは、この γ を重みとした重み付き最尤推定です。各点が γ_nk の割合だけ成分 k に属するソフトカウントとみなして更新します。

N_k = Σ_n γ_nk                                （成分 k の実効的な点数）
μ_k = (1/N_k) Σ_n γ_nk · x_n                  （responsibility 加重平均）
Σ_k = (1/N_k) Σ_n γ_nk · (x_n − μ_k)(x_n − μ_k)ᵀ
π_k = N_k / N                                （N は総点数）

形は通常のガウス最尤推定と同じで、違いは各点が 0/1 ではなく γ_nk ∈ [0,1] の重みで効く点だけです。E と M を交互に繰り返すと、対数尤度は反復のたびに改善していきます。

# GMM の EM（1反復）
# Eステップ：responsibility を計算
for n in range(N):
    dens = [pi[k] * gaussian(x[n], mu[k], Sigma[k]) for k in range(K)]
    gamma[n] = dens / sum(dens)        # 正規化して Σ_k = 1

# Mステップ：γ を重みにパラメータを更新
Nk = gamma.sum(axis=0)                  # 各成分の実効点数
for k in range(K):
    mu[k]    = (gamma[:, k] @ X) / Nk[k]
    Sigma[k] = weighted_cov(X, mu[k], gamma[:, k]) / Nk[k]
    pi[k]    = Nk[k] / N

なぜ対数尤度は単調増加するのか

EM の収束保証の核は、対数尤度の下界を作って押し上げるという変分推論の発想です。任意の分布 q(z) を使い、対数尤度を分解します。

log p(X | θ) = L(q, θ) + KL( q(z) ‖ p(z | X, θ) )
  L(q, θ) = Σ_z q(z) · log( p(X, z | θ) / q(z) )     ← 下界

KL ダイバージェンスは常に 0 以上なので、L(q, θ) は log p(X | θ) の下界です。同じ下界の発想は VAE の ELBO と完全に共通で、EM はその離散・厳密版にあたります。ここで二つのステップを下界の言葉で読み替えると、単調増加が見えてきます。

論理を順に追います。Eステップで q = p(z | X, θ_old) と選ぶと KL が 0 になり、下界が現在の対数尤度に接します（L = log p）。続くMステップで L(q, θ) を θ について最大化すると、θ_new での下界は θ_old 以上です。新しい θ_new では KL が再び 0 以上に開くだけなので、

log p(X | θ_new) ≥ L(q, θ_new) ≥ L(q, θ_old) = log p(X | θ_old)

つまり反復ごとに対数尤度は決して減らない。これが EM の収束原理です。単調増加する数列は、上に有界でありさえすれば必ずある値に収束します（対数尤度の値そのものではなく、その収束を保証するのは単調性のほうです）。ただし GMM では密度値が 1 を超えうるため対数尤度は本質的には上に有界でなく、後述の特異点さえ避ければ実用上は停留点へ収束します。

k-means は GMM の特殊例

k-means は一見まったく別の手法に見えますが、GMM を極限まで単純化したものです。次の制約を置きます。(1) 全成分の共分散を等方かつ等しい Σ_k = ε·I に固定、(2) 混合係数を一律 π_k = 1/K に固定、(3) ε → 0 の極限を取る。

このとき responsibility を見ると、ε → 0 でガウスが鋭く尖り、各点に最も近い中心の γ だけが 1、残りが 0 に飛びます。ソフト割り当てが 0/1 のハード割り当てに退化するのです。

k-means の二つのステップ——「各点を最近傍重心へ割り当て」「重心を所属点の平均で更新」——は、まさに退化した E ステップと M ステップです。だから k-means も反復ごとに目的関数（クラスタ内二乗和）が単調に減り、有限ステップで収束します。EM の単調性の特殊例にほかなりません。逆に、k-means が球状で等サイズのクラスタを暗黙に仮定し細長い分布や密度差に弱いのは、共分散を ε·I に固定したことの直接の帰結です。

初期化が結果を決める：k-means++

EM も k-means も非凸な目的関数を解くため、初期値が最終解の質を大きく左右します。k-means の素朴な初期化（中心を一様ランダムに選ぶ）は、たまたま近い点ばかり選ぶと貧弱な局所解に落ちます。これを確率的に改善するのが k-means++ です。

1. 最初の中心 c_1 をデータ点から一様ランダムに1つ選ぶ
2. 残りの各中心は、既存中心までの最短距離 D(x)^2 に比例する確率で点を選ぶ
   （D(x) = 既存のどの中心からも遠い点ほど選ばれやすい）
3. K 個の中心が揃うまで 2 を繰り返す
4. 以降は通常の k-means（Lloyd 法）を回す

既存の中心から遠い点ほど次に選ばれやすくすることで、初期中心が空間に散らばり、クラスタを取りこぼしにくくなります。k-means++ は期待値で最適 SSE の O(log K) 倍以内という近似保証も持ちます。GMM の EM でも、まず k-means++ で重心を決め、それを各ガウスの初期平均にする初期化が広く使われます。

まとめ

GMM・k-means・EM は一本の論理でつながっています。GMM は「各点がどの成分から生まれたか」を潜在変数とする確率モデルで、その z が見えないため尤度を直接解けません。EM は responsibility を埋める E ステップとパラメータを更新する M ステップを交互に回し、下界を介して対数尤度を単調増加させます。k-means はこの GMM の分散を 0 に飛ばしたハード割り当ての特殊例で、同じ EM の骨格と初期値依存の弱点を持ち、それを k-means++ が緩和します。「見えない潜在変数を期待値で埋め、下界を押し上げて尤度を上げる」という EM の発想は、VAE や隠れマルコフモデルなど潜在変数モデル全般を貫く普遍的な道具です。