確率的最適化代数

本ページは daitai-algebra の確率的最適化フラグメントを紹介します。訓練、推論、古典的勾配降下が、いかにして単一のプリミティブ Step と少数の書き換え規則のもとに統一されるかを述べます。

土台となる状態遷移関係はステップ意味論を 5 分でを参照してください。本ページはその Step を確率的設定に拡張します。

立場

古典的な機械学習は次のように書きます:

θ_{t+1} = θ_t − η · ∇L(θ_t)

daitai はこう書きます:

θ は RandomVar である。最適化とは、証拠を所与とした分布の更新である。

これは推論としての最適化です。daitai-algebra においてこれは一つの観点ではなく、唯一の定義です。決定論的な勾配降下は、分布が Dirac デルタである特殊例として導かれます。

種 (Sorts)

コアに三つの種が追加されます:

種	意味
`Param`	パラメータ。`RandomVar` として型付けされる
`ParamDist`	`Param` 上の分布
`Loss`	`Param → Scalar`

プリミティブ演算子

E       : ParamDist × Expr           → Scalar
KL      : ParamDist × ParamDist      → Scalar
Observe : Loss × Scalar → ParamDist  → ParamDist
Step    : ParamDist × Loss × Scalar  → ParamDist

E(q, f) は q のもとでの f の期待値。KL(q, q') ≥ 0 であり KL(q, q) = 0。対称性は仮定しません。

Observe(L, β)(q) は q(θ) · exp(−β · L(θ)) に比例する事後分布を導きます。正規化は暗黙です。

Step 公理

Step(q, L, η)
  := argmin_{q'}  KL(q' || q) + η · E(q', L)

これは定義であり、アルゴリズムではありません。バックエンドは SGD、自然勾配、鏡像降下、変分推論、サンプリングのいずれで実現してもよく、代数は気にしません。バックエンドの許容誤差の範囲で等式を満たしさえすればよいのです。

安定性則

任意の有効な q, L, η について:

KL(Step(q, L, η), q)  ≤  η · E(q, L)

ステップは、消費するエネルギー以上に（KL の意味で）分布を動かすことはできません。コンパイラはこれを読みます。あなたが書く必要はありません。

勾配降下への退化

ParamDist ≡ Dirac(θ) のとき:

Step(Dirac(θ), L, η)  ⇒  Dirac(θ − η · ∇L(θ))

したがって θ_{t+1} = θ_t − η ∇L(θ_t) はプリミティブではなく定理です。

書き換え規則

意味論を保つので、いずれのバックエンドもこれらの書き換えを適用してよい。

R1 — ゼロステップ

Step(q, L, 0)  ⇒  q

R2 — ゼロ損失

Step(q, L, η)  ⇒  q       if ∀θ. L(θ) = 0

R3 — 加法性（同じ損失）

Step(Step(q, L, η₁), L, η₂)  ⇒  Step(q, L, η₁ + η₂)

R4 — 合成（異なる損失）

Step(Step(q, L₁, η₁), L₂, η₂)  ⇒  Step(q, L₁ + L₂, η*)

η* はバックエンドが選ぶ合成子。コアは線形性も対称性も仮定しません。

R5 — 不動点

Step(q, L, η)  ⇒  q
  if  argmin_{q'} KL(q' || q) + η · E(q', L)  =  q

R6 — Dirac 退化

上述の古典的勾配降下書き換え。∇L(θ) が存在し、バックエンドが決定論的表現を許す場合に必要。

R7 — Moore–Penrose による自然勾配

q ≡ N(μ, Σ) で H_L(μ) が存在するとき:

Step(q, L, η)
  ⇒  N(
       μ − η · pinv(H_L(μ)) ∘ ∇L(μ),
       pinv(H_L(μ))
     )

pinv は Moore–Penrose 擬似逆行列。H_L は特異でも構いません — だからこそ擬似逆が現れます。

R8 — 情報駆動の書き換え

maximize MI(A, B) using Step は L := −MI(A, B) を用いた minimize L using Step に書き換わります。相互情報量最大化は新しいプリミティブではなく、ひとつの損失です。

これで得られるもの

同じ Step 演算子で次のすべてが扱えます:

確率的勾配降下
自然勾配
鏡像降下
変分推論
確率的 PCA、ICA、CCA
相互情報量最大化

これらはすべて一つの定義のインスタンスであり、バックエンドはアルゴリズムごとに再導出することなく、安定性則と合成則に依拠できます。

次に読むもの

ステップ意味論を 5 分で — 本ページが拡張する古典的状態関係。
bra-ket プリミティブ — Param と ParamDist が差し込まれる量子的/古典的な状態語彙。