K-means, GMM, EM：クラスタリングの三重マトリョーシカ

隠れた構造を見つける問題

この三つの関係は分かったようで、すぐ忘れてしまう。また混乱するであろう未来の自分のためにまとめておく。（Claudeの助けを借りて作成した。）

データがある。ラベルはない。しかし目で見ると何かしらの「塊」が見える。

この塊を自動的に見つけ出すのがクラスタリングだ。ここには根本的な問いが隠れている。

「各データがどの塊に属するのか」——この隠れた情報をどう推定するか？

この問いに答える三つの手法がある。K-means、GMM、EMアルゴリズム。驚くべきことに、この三つは独立した手法ではなく、マトリョーシカのように互いに入れ子になっている構造だ。


graph LR
    subgraph EM["EMアルゴリズム"]
        subgraph GMM["GMM"]
            K["K-means"]
        end
    end
    style EM stroke:#2196F3,stroke-width:2px
    style GMM stroke:#FF9800,stroke-width:2px
    style K stroke:#E91E63,stroke-width:2px

K-means：ハサミで切る

K-meansは最も直感的なクラスタリングだ。アルゴリズムは二つのステップを繰り返す。

各データを最も近い中心に割り当てる（Assign）
各グループの平均に中心を移動する（Update）


graph TD
    A["中心点を初期化"] --> B["各データを
最も近い中心に割り当て"]
    B --> C["中心をグループ平均に
移動"]
    C --> D{"変化あり？"}
    D -->|"はい"| B
    D -->|"いいえ"| E["完了"]

核心的な特性はhard assignmentだ。各データは必ず一つのクラスタにのみ属する。「70%はA、30%はB」のようなことは許されない。

K-meansが最小化するのは結局これだ：

$$J = \sum_{k=1}^{K} \sum_{x_i \in C_k} |x_i - \mu_k|^2$$

各データと所属クラスタ中心の間の距離の総和。単純で速い。しかし仮定が強い。

全てのクラスタが球形である
全てのクラスタのサイズが似ている
境界がナイフで切ったように明確である

現実のデータは普通こんなに綺麗ではない。

GMM：雲で包む

Gaussian Mixture ModelはK-meansの仮定を緩和する。各クラスタを「点」ではなく「雲」（ガウス分布）としてモデル化する。

$$p(x) = \sum_{k=1}^{K} \pi_k \cdot \mathcal{N}(x | \mu_k, \Sigma_k)$$

$\pi_k$：クラスタ$k$の割合（混合重み）
$\mu_k$：クラスタ$k$の中心
$\Sigma_k$：クラスタ$k$の形と大きさ（共分散行列）

K-meansとの決定的な違いはsoft assignmentだ。各データに対して「このデータがクラスタ$k$から生成された確率」を計算する。

$$r_{ik} = \frac{\pi_k \cdot \mathcal{N}(x_i | \mu_k, \Sigma_k)}{\sum_j \pi_j \cdot \mathcal{N}(x_i | \mu_j, \Sigma_j)}$$

この$r_{ik}$をresponsibility（責任度）と呼ぶ。「クラスタ$k$がデータ$x_i$に対してどれだけ責任があるか」という意味だ。

	K-means	GMM
クラスタ形状	球形のみ	楕円形、様々なサイズ
割り当て方式	hard（0か1）	soft（確率値）
パラメータ	中心点のみ	中心、共分散、混合比
結果の解釈	「このデータはAだ」	「このデータはAである確率80%」

EMアルゴリズム：隠れたものを見つける一般原理

GMMのパラメータをどう学習するか？データがどのクラスタから来たか分かれば簡単だ。しかしそれこそが知りたい情報だ。鶏が先か卵が先かの状況である。

クラスタ所属が分かればパラメータを求められるし、パラメータが分かれば所属を求められる。

EM（Expectation-Maximization）アルゴリズムはこの膠着状態を「交互に」解いていく。

E-step（Expectation）：現在のパラメータで潜在変数の期待値を計算する
M-step（Maximization）：その期待値を使ってパラメータを更新する


graph TD
    A["パラメータ初期化 θ⁰"] --> B["E-step
現在のθで潜在変数の
事後確率を計算"]
    B --> C["M-step
事後確率を使って
パラメータ更新"]
    C --> D{"収束？"}
    D -->|"いいえ"| B
    D -->|"はい"| E["最終パラメータ θ*"]

GMMに適用すると：

E-step：responsibility $r_{ik}$を計算（各データが各クラスタに属する確率）
M-step：$r_{ik}$を重みとして$\mu_k$、$\Sigma_k$、$\pi_k$を更新

EMはGMMだけに使われるものではない。潜在変数がある全ての確率モデルに適用可能な一般フレームワークだ。Hidden Markov Model、トピックモデルなどにも全てEMを使う。

核心的洞察：K-meansはGMMの極限である

ここで最も興味深い繋がりが明らかになる。GMMに以下の条件を課すと：

全クラスタの共分散を$\sigma^2 I$に固定（球形、同一サイズ）
$\sigma \to 0$とする

するとresponsibility $r_{ik}$はどうなるか？

$$\lim_{\sigma \to 0} r_{ik} = \begin{cases} 1 & \text{if } k = \arg\min_j |x_i - \mu_j|^2 \ 0 & \text{otherwise} \end{cases}$$

soft assignmentがhard assignmentに変わる。最も近いクラスタに確率1、それ以外に確率0。これはK-meansのassignステップと正確に同じだ。

直感的に理解すると：分散$\sigma^2$は「クラスタの雲の広がり具合」だ。雲が極端に鋭くなると（分散→0）、各雲は点になり、softな境界はナイフで切ったような境界になる。


graph LR
    A["GMM
σ²大きい
広がった雲"] --> B["GMM
σ²小さい
鋭い雲"]
    B --> C["K-means
σ² → 0
点"]
    A -.- D["soft assignment
確率的境界"]
    C -.- E["hard assignment
明確な境界"]
    style A stroke:#2196F3,stroke-width:2px
    style B stroke:#FF9800,stroke-width:2px
    style C stroke:#E91E63,stroke-width:2px

EMの保証：毎反復ごとに改善する

EMアルゴリズムが機能する理由は何か？核心はELBO（Evidence Lower Bound）にある。

最大化したいのはlog-likelihood $\log p(X|\theta)$だ。直接最大化が困難な時、EMはこの下界（lower bound）を反復的に引き上げる。

$$\log p(X|\theta) \geq \underbrace{E_{q(Z)}[\log p(X,Z|\theta)] + H[q(Z)]}_{\text{ELBO}}$$

E-stepはELBOを$\log p(X|\theta)$に密着させる（下界を最大限引き上げる）
M-stepは密着したELBOをさらに上げる（パラメータ改善）

この過程でlog-likelihoodは絶対に減少しない。毎反復ごとに単調増加が保証される。ただし大域最適（global optimum）に到達する保証はなく、局所最適（local optimum）に陥ることがある。

情報幾何学の視点

ここからもう一歩踏み込むと、EMアルゴリズムの動作原理が情報幾何学の言葉で綺麗に説明できる。

EM = KLダイバージェンスを反復的に減らす過程

E-stepとM-stepはそれぞれ異なるKLダイバージェンスを最小化する過程として見ることができる。

E-step：$q(Z)$と$p(Z|X,\theta)$の間のKLダイバージェンスを0にする。

$$q^*(Z) = \arg\min_q D_{KL}(q(Z) | p(Z|X,\theta)) = p(Z|X,\theta)$$

M-step：モデル分布とデータ分布の間のKLダイバージェンスを減らす。

$$\theta^* = \arg\min_\theta D_{KL}(p_{\text{data}} | p_\theta)$$

つまりEMは「二種類の距離を交互に縮めていく過程」だ。一回は潜在変数空間で、一回はパラメータ空間で。


graph TD
    A["現在の状態"] --> B["E-step
q(Z)とp(Z|X,θ)の間の
KL divergence → 0"]
    B --> C["M-step
モデルとデータの間の
KL divergence ↓"]
    C --> D["より良い状態"]
    D --> B
    style B stroke:#4CAF50,stroke-width:2px
    style C stroke:#FF9800,stroke-width:2px

パラメータ空間は平坦ではない

通常のgradient descentはパラメータ空間をユークリッド空間（平坦な空間）として扱う。しかし確率分布のパラメータ空間は曲がっている。

例えば、ガウス分布の平均を$\mu=0$から$\mu=1$に変えることと、$\mu=100$から$\mu=101$に変えることは「パラメータの数値上」同じ大きさの変化だ。しかし分布の形が変わる程度は分散（$\sigma^2$）によって全く異なる。分散が小さければ分布は大きく変わり、分散が大きければほとんど変わらない。

この「実際に分布がどれだけ変わるか」を測定するのがFisher informationだ。

$$F_{ij}(\theta) = E_{p_\theta}\left[\frac{\partial \log p_\theta(x)}{\partial \theta_i} \cdot \frac{\partial \log p_\theta(x)}{\partial \theta_j}\right]$$

Fisher informationはパラメータ空間の曲率を教えてくれる「計量テンソル（metric tensor）」だ。これを使ってgradientを補正するとnatural gradientになる。

$$\Delta\theta = -F(\theta)^{-1} \nabla_\theta \ell(\theta)$$

EM ≈ Natural Gradient

Amari（1998）の結果によれば、EMアルゴリズムの更新はnatural gradient descentと等価であることが知られている。つまりEMは自動的にパラメータ空間の曲率を考慮して、「情報的に最も効率的な方向」にパラメータを更新する。

これがEMが単純なgradient descentより収束が速い場合が多い理由だ。平坦な座標系での最短経路ではなく、確率分布空間での最短経路に沿って移動するからだ。

K-means → GMM → EMの情報幾何学的階層

手法	情報幾何学的解釈
K-means	各データをδ-分布（点分布）に割り当て。分布間KLダイバージェンスが無限大か0のみ許容
GMM-EM	ガウス分布たちの多様体（manifold）上で最適な混合を求める射影（projection）
EM（一般）	潜在変数モデルが定義する確率多様体上でのnatural gradient降下

GMMにおけるFisher Informationと「慣性」

GMM観点でFisher informationの直感をもう一つ付け加えると：

あるクラスタのresponsibilityが高いデータが多い → そのクラスタのパラメータに対するFisher informationが大きい → パラメータが簡単には変わらない（「慣性」が大きい）
逆にresponsibilityが曖昧な（複数クラスタにまたがる）データが多い領域ではFisher informationが小さい → パラメータが容易に変わる（「柔軟」）

確信のある割り当てほど安定的で、不確実な領域ほど敏感に反応するのだ。物理的な比喩に戻れば、質量の大きい物体（確固たるクラスタ）は押されにくく、質量の小さい物体（不確実なクラスタ）は少しの力でも大きく動く。

まとめ：一つの根から三つの枝へ


graph TD
    EM["EMアルゴリズム
潜在変数がある全モデルの
MLEのための一般フレームワーク"]
    GMM["GMM
潜在変数 = クラスタ所属
観測モデル = ガウシアン"]
    KM["K-means
GMMでσ→0
soft → hard assignment"]
    IG["情報幾何学的解釈
EM = natural gradient
パラメータ空間の曲率を
自動的に考慮"]

    EM --> GMM
    GMM --> KM
    EM -.- IG

    style EM stroke:#2196F3,stroke-width:2px
    style GMM stroke:#FF9800,stroke-width:2px
    style KM stroke:#E91E63,stroke-width:2px
    style IG stroke:#9C27B0,stroke-width:2px

K-meansは「最も近い中心に割り当てる」という直感的な方法だ
GMMは「確率的に割り当てる」ことで柔軟性を得る
EMはこのような「隠れた変数を推定する問題」一般を解くためのフレームワークだ
情報幾何学はEMがなぜ効率的か、三つの手法の関係がなぜそうなるかを「確率空間の幾何学」で説明する

結局この三つの手法は同じ問い——「見えない構造をどう見つけるか」——に対して、異なるレベルの一般性で答えるものなのだ。

参考文献

Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer. Chapter 9.
Amari, S. (1998). Natural Gradient Works Efficiently in Learning. Neural Computation, 10(2), 251-276.
Dempster, A. P., Laird, N. M., & Rubin, D. B. (1977). Maximum Likelihood from Incomplete Data via the EM Algorithm. JRSS-B, 39(1), 1-38.

隠れた構造を見つける問題#

K-means：ハサミで切る#

GMM：雲で包む#

EMアルゴリズム：隠れたものを見つける一般原理#

核心的洞察：K-meansはGMMの極限である#

EMの保証：毎反復ごとに改善する#

情報幾何学の視点#

EM = KLダイバージェンスを反復的に減らす過程#

パラメータ空間は平坦ではない#

EM ≈ Natural Gradient#

K-means → GMM → EMの情報幾何学的階層#

GMMにおけるFisher Informationと「慣性」#

まとめ：一つの根から三つの枝へ#

参考文献#