マルコフ連鎖を1から — 「今だけ見る」確率過程

次に何が起きるかは、今どこにいるかだけで決まる — この割り切りがマルコフ連鎖です。遷移行列と定常分布から、PageRankがなぜ固有ベクトルなのか、MCMCがなぜ正規化定数を無視できるのかまでを、前提知識ゼロから積み上げます。

すごろくは、来た道を覚えていない

すごろくで12番のマスにいるとき、次にどこへ進むかはサイコロの目と今のマスだけで決まります。7番から飛んで来たのか、5番から歩いて来たのかは、次の1手に一切影響しません。この「過去の道のりを忘れて、今の位置だけを見る」割り切りがマルコフ連鎖です。

天気なら「今日が雨なら、明日も雨が0.6、曇りが0.3、晴れが0.1」というルールだけを持つモデル。乱暴に見えますが、この乱暴さのおかげで計算が驚くほど簡単になり、その簡単さのままウェブ検索のランキングにも、ベイズ統計の計算にも、拡散モデルにも使われています。

誤解しやすいのは「記憶がない」という言い方です。正確には、記憶が現在の状態にすべて畳み込まれている。過去を捨てているのではなく、「未来に効く情報は今の状態を見れば分かるように設計してある」という宣言なのです。

マルコフ性: 何を捨て、何を残すのか

時刻 $t$ の状態を $X_t$ と書きます。状態とは「晴れ・曇り・雨」のような、モデルが取りうる場所の一覧です。

$P(A \mid B)$ は「Bという条件のもとでAが起きる確率」。左辺は全履歴を知ったうえでの明日の確率、右辺は今日の状態だけを使った確率です。要するに、明日の予報に必要なのは今日の天気だけで、先週の天気は知っていても答えが変わらないと言っています。

現実のデータはたいていこの仮定を破ります。ユーザーの次のクリックは直前のページだけでなく「そもそも何を探しに来たか」に依存する。逃げ道は状態を太らせることです。昨日と今日で決まると考えたいなら、状態を「(昨日, 今日)」のペアにすれば、また「今だけ見る」で話が閉じます。言語モデルのn-gramはまさにこれで、代償は状態数の爆発です(語彙1万語で直前2語なら1億通り)。

つまりマルコフ連鎖を使う仕事の本体は、式を解くことではなく何を状態と呼ぶかを決めることにあります。

遷移行列: 表にすると、予測が掛け算になる

状態が3つなら、遷移確率は3×3の表に収まります。

約束は2つだけです。行が「今日」、列が「明日」。そして各行の合計は必ず1(明日はどこかの状態に必ず居るので)。この表が遷移行列 $P$ です。列の合計は1になりません — 人気の状態は多くの行から矢印を集めるからです。

今日の天気を「晴れ50%・曇り30%・雨20%」のような分布で持ち、横並びの数の列 $\pi_t = (0.5,\ 0.3,\ 0.2)$ と書けば、明日の分布は掛け算1回で出ます。

要するに、「今どこに何割いるか」に「そこからどこへ何割行くか」を掛けると「明日どこに何割いるか」が出る。中身は「晴れの割合×晴れ→曇りの確率 ＋ …」という足し算にすぎません。繰り返せば $n$ 日後も一発です。

言い換えれば、マルコフ連鎖の予測とは行列のべき乗です。ここから先は「同じ行列を掛け続けると何が起きるか」の一点に集約されます。

定常分布: 回し続けると、初期値を忘れる

さきほどの行列を、初期分布を変えて何度も掛けてみると面白いことが起きます。「確実に晴れ」から始めても「確実に雨」から始めても、10日ほどで分布はほぼ同じ値に落ち着く。初期値の情報が消えるのです。この落ち着き先を定常分布と呼びます。

$\pi$ が定常分布、$\sum_i \pi_i = 1$ は「確率なので全部足すと1」。要するに、1日進めてもまったく同じままの分布です。

ここで線形代数と合流します。$\pi P = 1 \cdot \pi$ と読めば、定常分布とは固有値1の固有ベクトル(正確には左固有ベクトル)にほかなりません。固有ベクトルが「変換しても向きが変わらない方向」だという話はLoRAとRAGを支える線形代数にあります。ここではそれが「明日になっても割合が変わらない」に翻訳されます。