拡張スタイルのジリィモナド - 檜山正幸のキマイラ飼育記 (はてなBlog)

「絵算で見る、拡張スタイルのモナドとモノイド・スタイルのモナド」にて：

拡張スタイルは ...[snip]... モナド法則の証明がモノイド・スタイルより容易になる場合があります。

このことの実例として、ジリィモナドを拡張スタイルで記述してみましょう。モノイド・スタイルより、幾分計算しやすいと思います。（測度論が絡むところは、どうやっても難しいですけどね。）

予備知識として、ジリィモナドとマルコフ核につていは次の記事を参照してください。

測度論的議論は適当にはしょっています（測度論をよく知らないので）。

内容：

記号の約束
確率測度達の可測空間
カリー化マルコフ核
デルタ測度
拡張オペレーター
マルコフ核の拡張は可測写像
外単位律と内単位律
入れ子律の表示
マルコフ核に関する随伴公式と入れ子律

記号の約束

拡張スタイルのジリィモナド〈Giry monad〉の素材〈構成素〉を次のように決めます。

基礎圏 Meas（可測空間と可測写像の圏）
対象構成子 P:|Meas| → |Meas| （確率測度達の可測空間）
単位 For X∈|Meas|, δ_X:X → P(X) in Meas （デルタ測度）
拡張オペレーター： For X, Y∈|Meas|, Ext_X,Y:Meas(X, P(Y)) → Meas(P(X), P(Y)) in Set

Ext_X,Y(F) を F^# とも書きます。

これらがモナドを形成するためには、拡張スタイルのモナド法則を満たす必要があります。

外単位律： For F:X → P(Y) in Meas, δ_X;F^# = F
内単位律： For X in Meas, δ_X^# = id_P(X)
入れ子律： For F:X → P(Y), G:Y → P in Meas, (F;G^#)^# = F^#;G^#

この記事で、素材をキチンと定義して、モナド法則を示していきます。

他の記号の約束は：

Measの射、つまり可測写像は f, g などのラテン文字小文字で表す。実数値可測関数は ψ, φ なども使う。
ジリィモナドのクライスリ射、つまり X → P(X) の形の可測写像は F, G などのラテン文字大文字で表す。
P(X) の要素、つまりX上の確率測度は、μ, ν などのギリシャ文字小文字で表す。

「マルコフ核：確率計算のモダンな体系」において、マルコフ核は X×ΣY → [0, 1] という二項〈二変数 | 二引数〉写像でした。ここでは、二項のマルコフ核をカリー化した写像 X → Map(ΣY, [0, 1]) をマルコフ核だとします。両者を区別したいときは、二項マルコフ核〈two-argument Markov kernel | Markov kernel with two arguments〉、カリー化マルコフ核〈curried Markov kernel〉とします。この記事内で単にマルコフ核といったらカリー化マルコフ核のことです。

確率測度達の可測空間

可測空間を、記号を乱用して X = (X, ΣX) のように書きます。可測空間とその台集合をどちらもXで表します（邪悪なオーバーロード）。

可測空間Xに対するP(X)は、集合としては次のように定義します。

P(X) := {μ:ΣX → [0, 1] | μは確率測度}

P(X)∈|Meas| とするためには、シグマ集合代数 ΣP(X) = Σ(P(x)) も定義する必要があります。ΣP(X) の定義のために、いくつか記号を導入します。A∈ΣX に対して、 $\hat{A}$ :P(X) → [0, 1] を、

$\hat{A}$ (μ) := μ(A)

と定義します*1。

ΣP(X)⊆Pow(P(X)) は、すべての $\hat{A}$ :P(X) → [0, 1] を可測関数にする最小のシグマ集合代数と定義します。シグマ集合代数の生成系となる集合族は、次の形をした集合達で構成されます。

A∈ΣX, r∈[0, 1] に対する ${\hat{A}}^{-1}$ ([0, r]) = {μ∈P(X) | μ(A) ≦ r}

${\hat{A}}^{-1}$ ([0, r]) を $\mathscr{M}_X$ (A, r) ⊆P(X) とも書くことにします。繰り返し書いておくと：

$\mathscr{M}_X$ (A, r) := {μ∈P(X) | μ(A) ≦ r} ⊆P(X)

$\mathscr{M}_X$ (A, r) を P(X) の可測集合としますが、補集合と可算無限の合併を取ることに関して閉じた集合族にまで拡張したものが ΣP(X) です。

カリー化マルコフ核

X, Y∈|Meas| として、可測写像 F:X → P(Y) in Meas がカリー化マルコフ核です。ここではカリー化マルコフ核を単にマルコフ核と呼ぶ約束をしました。マルコフ核 F:X → P(X) を反カリー化した二変数関数を F_∪:X×ΣY → [0. 1] とします。このとき、次が成立します。

F:X → P(Y) に対する F_∪:X×ΣY → [0. 1] は、「マルコフ核：確率計算のモダンな体系」の意味のマルコフ核である。

「マルコフ核：確率計算のモダンな体系」のマルコフ核〈二項マルコフ核〉の定義を再掲すると：

x∈X を固定すると、ΣY∋B $\mapsto$ F_∪(x, B)∈[0, 1] は、Y上の確率測度になる。
B∈ΣY を固定すると、X∋x $\mapsto$ F_∪(x, B)∈[0, 1] は、X → [0, 1] の可測写像になる。

一番目は F_∪(x, B) = F(x)(B) でBを動かしたときに確率測度になることなので、定義から明らかですね。二番目を示すことにしましょう。

B∈ΣY を固定して、関数 λx∈X.F_∪(x, B):X → [0, 1] を考えます。これが可測写像であるためには、

(λx∈X.F_∪(x, B))^-1([0, r]) が可測集合

なら十分です。

   a ∈ (λx∈X.F_∪(x, B))^-1([0, r])
⇔ (λx∈X.F_∪(x, B))(a)∈[0, r]
⇔ F_∪(a, B)∈[0, r]
⇔ F(a)(B)∈[0, r]
⇔ F(a)(B) ≦ r
⇔ F(a)∈{ν∈P(Y) | ν(B) ≦ r}
⇔ a∈F^-1({ν∈P(Y) | ν(B) ≦ r})

これから次が言えます。

(λx∈X.F_∪(x, B))^-1([0, r]) = F^-1( $\mathscr{M}_Y$ (B, r))

イコールの右辺が可測集合なので、左辺も可測集合です。これで、λx∈X.F_∪(x, B) が可測写像なことがわかり、F_∪ が二項マルコフ核であることが示せました。

同様な議論で、次も言えます。

Φ:X×ΣY → [0, 1] が二項マルコフ核ならば、そのカリー化 Φ^∩:X → Map(ΣX, [0, 1]) は、Φ^∩:X → P(Y) というカリー化マルコフ核になる。

デルタ測度

ジリィモナドの単位〈モナド単位〉はデルタ測度〈ディラック測度〉で与えられます。

For X∈|Meas|, x∈X, A∈ΣX,
δ_X(x)(A) := if (x∈A) then 1 else 0

δ(x) を δ_x と添字で書くことはここではしません。添字には可測空間Xが入ります。

モノイド・スタイルのモナドの定義では、δが自然変換であることを要求しますが、拡張スタイルでは単に可測空間で添字付けられた写像の族です。が、各写像δ_Xが可測写像（Measの射）であることは要求します。

δ_X:X → P(X) が可測であるためには、 $\mathscr{M}_X$ (A, r)⊆P(X) の逆像がXの可測集合なら十分です。

   a∈δ_X^-1({μ∈P(X) | μ(A) ≦ r})
⇔ δ_X(a)∈{μ∈P(X) | μ(A) ≦ r}
⇔ δ_X(a)(A) ≦ r
⇔ a∈{x∈X | δ_X(x)(A) ≦ r}

以上から、次が言えました。

δ_X^-1( $\mathscr{M}_X$ (A, r)) = {x∈X | δ_X(x)(A) ≦ r}

イコールの右辺の集合が可測集合ならいいわけですが、r = 1 と r ≠ 1 の場合に分けて考えます。

r = 1 ならば、{x∈X | δ_X(x)(A) ≦ r} = {x∈X | δ_X(x)(A) ≦ 1} = X
r ≠ 1 ならば、{x∈X | δ_X(x)(A) ≦ r} = {x∈X | δ_X(x)(A) = 0} = (Aの補集合)

Xも(Aの補集合)も可測集合なので、δ_X:X → P(X) が可測写像だと示せました。

拡張オペレーター

F:X → P(Y) in Meas に対して、F^#:P(X) → P(Y) を定義します。とりあえず、F^# が可測写像かどうかは後回しにして、F^#:P(X) → P(Y) in Set として定義します。

$F^\# := \lambda\,\mu\in P(X). \lambda\, B\in \Sigma X.{\displaystyle \int_{x\in X}} F(x)(B)\mu(dx)$

まず、μ∈P(X) に対して、F^#(μ)∈P(Y) かどうかが問題になります。つまり、次が成立するかどうかです。

$F^\#(\mu)(Y) = 1$
$F^\#(\mu)(\coprod_{i = 1}^\infty B_i) = \sum_{i = 1}^\infty F^\#(\mu)(B_i)$

1番は定義から明らかです。2番を考えましょう。次の計算が合理化できればいいですね。

$\:\:\:\: {\displaystyle \int_{x\in X} F(x)(\coprod_{i = 1}^\infty B_i)\,\mu(dx) } \\ = {\displaystyle \int_{x\in X} \left(\sum_{i = 1}^\infty F(x)(B_i) \right)\mu(dx) } \\ = {\displaystyle \sum_{i = 1}^\infty \int_{x\in X} F(x)(B_i)\,\mu(dx) }$

1行目から2行目は、F(x)が確率測度であることから言えます。2行目から3行目は積分論の収束定理から言えます。より詳しく言えば：

次のように置きます。

$\phi := \lambda\, x\in X.F(x)(\coprod_{i = 1}^\infty B_i)$
$\psi_k := \sum_{i = 1}^k F(x)(B_i) \:\mbox{ for }k = 1, 2, \cdots$

Fがマルコフ核であることから、これらの関数はすべてX上の実数値可測関数です。 $\lim_{k \to \infty}\psi_k = \phi$ （各点収束）が成立します。また、次も成立しています。

$\forall k\in\{1, 2, \cdots\}. \forall x\in X.(0 \le \psi_k(x) \le \phi(x))$ （支配条件）

先の等式的計算は次のように書けます。

$\:\:\:\: {\displaystyle \int_{x\in X} \phi(x)\,\mu(dx) } \\ = {\displaystyle \int_{x\in X} \lim_{k \to \infty}\psi_k(x) \,\mu(dx) } \\ = {\displaystyle \lim_{k \to \infty} \int_{x\in X} \psi_k(x) \,\mu(dx) }$

積分と極限の交換は、支配条件があるので許されます。

さらに、F^#:P(X) → P(Y) が可測写像である必要があります。そうでないと、拡張オペレーターが圏Meas内で働くことが保証できません。F^#が可測写像であることは次節で述べます。

マルコフ核の拡張は可測写像

測度論的議論をしたくないので、次に述べる事実は天下りに仮定します。ψはX上の非負実数値可測関数で、次は成立しているとします。

任意の確率測度 μ∈P(X) に対して、 $\int_{x\in X}\psi(x)\mu(dx) \le 1$

実際に使うのは、マルコフ核 F:X → P(Y) と B∈ΣY に対して ψ := λx∈X.F(x)(B) と定義されるψです。この状況で、ψによって定義される次の写像は可測写像になります。

$\lambda\, \mu\in P(X).\int_{x\in X}\psi(x)\mu(dx) \:\: : P(X) \to [0, 1]$

この写像の可測性を天下りに仮定しますが、特別な場合だけ確認しておきます。ψが、A∈ΣX に対する指示関数〈indicator function〉χ_A であるときを見ましょう。上記写像の [0, r]⊆[0, 1] に対する逆像を計算します。

$\:\:\:\: \left(\lambda\, \mu\in P(X).\int_{x\in X}\chi_A(x)\mu(dx)\right)^{-1}([0, r]) \\ = \{\mu \in P(X) \mid \int_{x\in X}\chi_A(x)\mu(dx) \leq r \} \\ = \{\mu \in P(X) \mid \int_{x\in A}\mu(dx) \leq r \} \\ = \{\mu \in P(X) \mid \mu(A) \leq r \} \\ = \mathscr{M}_X(A, r)$

$\mathscr{M}_X(A, r)$ ⊆ P(X) は可測空間P(X)の可測集合でした。この特殊ケースを一般の場合まで押し広げる論法が“測度論的議論”です。

さて、マルコフ核 F:X → P(Y) in Meas の拡張 F^#:P(X) → P(Y) （現時点では可測写像かどうか分からない）に対して、 $\mathscr{M}_Y$ (B, r) ⊆ P(Y) の逆像を計算しましょう。混乱を避けるため、ΣY 上を走るラムダ変数は B' にします、B∈P(Y) は可測集合です。

$\:\:\:\: (F^\#)^{-1}( \mathscr{M}_Y(B, r) ) \\ = (\lambda\, \mu. \lambda\, B'.\int_{x\in X}F(x)(B')\mu(dx))^{-1}( \mathscr{M}_Y(B, r) ) \\ = \{\mu \in P(X) \mid (\lambda\, B'.\int_{x\in X}F(x)(B')\mu(dx)) \in \mathscr{M}_Y(B, r) \} \\ = \{\mu \in P(X) \mid \int_{x\in X}F(x)(B)\mu(dx) \le r \}$

B∈P(Y) は固定していたので、ψ := λx.F(x)(B) と置いて続きの計算をすると：

$\:\:\:\: \{\mu \in P(X) \mid \int_{x\in X}F(x)(B)\mu(dx) \le r \} \\ = \{\mu \in P(X) \mid \int_{x\in X}\psi(x)\mu(dx) \le r \} \\ = (\lambda\, \mu.\int_{x\in X}\psi(x)\mu(dx))^{-1}([0, r])$

最後の集合がP(X)の可測写像であることは、この節の最初に仮定したことからしたがいます。よって、マルコフ核 F:X → P(Y) in Meas の拡張 F^# は可測写像となり、F^#:P(X) → P(Y) in Meas と書いてもいいことになりました。

外単位律と内単位律

前節までで、拡張スタイルのジリィモナドの素材は揃ったので、拡張スタイルのモナド法則を示していきます。外単位律と内単位律を示しましょう。

外単位律： For F:X → P(Y) in Meas, δ_X;F^# = F
内単位律： For X in Meas, δ_X^# = id_P(X)

ラムダ式を簡潔にするために、ラムダ変数の型（所属する集合）を次のように約束して、型を省略します。

a, x∈X, b, y∈Y, c, z∈Z
A∈ΣX, B∈ΣY, C∈ΣZ
μ∈P(X), ν∈P(Y)

$\newcommand{\LA}{\big[\!\!\big(\,}\newcommand{\RA}{\,\big)\!\!\big]}$ 凹レンズ括弧（ $\LA \cdots \RA$ ）は、直前の式に対する代入操作を表します。

外単位律は次の計算で示せます。

$\:\:\:\: \delta_X ; F^\# \\ = (\lambda\,a.\delta_X(a) );( \lambda\,\mu.F^\#(\mu) ) \\ = \lambda\,a.(\, F^\#(\mu) \LA \mu = \delta_X(a) \RA \,) \\ = \lambda\,a.(\, (\lambda\, B.{\displaystyle \int_{x\in X}} F(x)(B)\mu(dx) )\LA \mu = \delta_X(a)\RA \,)\\ = \lambda\,a.(\, \lambda\, B.{\displaystyle \int_{x\in X}} F(x)(B)\delta_X(a)(dx) \,) \\ = \lambda\,a.(\, \lambda\, B.( F(a)(B) ) \,)\\ = \lambda\,a.\lambda\, B. F(a)(B) \\ = F$

内単位律は次の計算で示せます。

$\:\:\:\: {\delta_X}^\# \\ = \lambda\, \mu. \lambda\, A. {\displaystyle \int_{x\in X}} \delta_X(x)(A)\,\mu(dx) \\ = \lambda\, \mu. \lambda\, A. {\displaystyle \int_{x\in A \subseteq X}} \mu(dx) \\ = \lambda\, \mu. \lambda\, A. \mu(A) \\ = \lambda\, \mu. \mu \\ = \mathrm{id}_{P(X)}$

入れ子律の表示

残るモナド法則は入れ子律です。

入れ子律： For F:X → P(Y), G:Y → P(Z) in Meas, (F;G^#)^# = F^#;G^#

まず、この等式の両辺を露骨〈explicit〉に書き下すことにします。前節同様、ラムダ変数の型は省略します。

左辺（入れ子になった拡張）の内側：

$\:\:\:\: F;G^\# \\ = (\lambda\, x.F(x));(\lambda\, \nu. G^\#(\nu)) \\ = \lambda\, x.(\, G^\#(\nu) \LA \nu = F(x) \RA \,) \\ = \lambda\, x.(\,(\lambda\, C.\int_{y\in Y}G(y)(C)\nu(dy))\LA \nu = F(x) \RA \,) \\ = \lambda\, x.(\, \lambda\, C.\int_{y\in Y}G(y)(C)\,F(x)(dy) \,)$

ここで、 $H(x)(C) := \int_{y\in Y}G(y)(C)\,F(x)(dy)$ と置いて $H = \lambda\,x. \lambda\, C.H(x)(C)$ の拡張を計算します。

$\:\:\:\: H^\# \\ = \lambda\, \mu .\lambda\, C. \int_{x\in X}H(x)(C)\,\mu(dx) \\ = \lambda\, \mu .\lambda\, C. \int_{x\in X} \left(\int_{y\in Y}G(y)(C)\,F(x)(dy)\right) \,\mu(dx) \\$

最後の表示が入れ子律の左辺になります。

右辺（拡張の結合）：

$\:\:\:\: F^\#; G^\# \\ = (\lambda\, \mu.F^\#(\mu));(\lambda\, \nu. G^\#(\nu)) \\ = \lambda\, \mu.(\, G^\#(\nu)\LA \nu = F^\#(\mu)\RA \,) \\ = \lambda\, \mu.(\, (\lambda\, C.\int_{y\in Y}G(y)(C)\,\nu(dy) )\LA \nu = F^\#(\mu)\RA \,) \\ = \lambda\, \mu.(\, \lambda\, C.\int_{y\in Y}G(y)(C)\,F^\#(\mu)(dy) \,) \\ = \lambda\, \mu.\lambda\, C. \int_{y\in Y}G(y)(C)\,F^\#(\mu)(dy)$

よって、入れ子律は次の等式と同値です。

$\forall \mu \in P(X). \forall C \in \Sigma Z. \\ {\displaystyle \int_{x\in X} \left(\int_{y\in Y}G(y)(C)\,F(x)(dy)\right) \,\mu(dx) = \int_{y\in Y}G(y)(C)\,F^\#(\mu)(dy) }$

マルコフ核に関する随伴公式と入れ子律

「随伴公式 -- マルコフ核の場合」にあるマルコフ核に関する随伴公式をそのまま再掲します。

${\displaystyle \int_{x\in X} \left(\int_{y\in Y} \psi(y)F(dy|x) \right)L(dx) = \int_{y\in Y} \psi(y) \left(\int_{x\in X} F(dy|x)L(dx) \right) }$

記法を今回の記事に合わせれば：

${\displaystyle \int_{x\in X} \left(\int_{y\in Y} \psi(y)F(x)(dy) \right)\mu(dx) = \int_{y\in Y} \psi(y) \left(\int_{x\in X} F(x)(dy) \mu(dx) \right) }$

右辺の括弧に包まれた積分は、関数の積分ではなくて、マルコフ核Fによる確率測度μの前送り測度 F_*(μ) を便宜的に積分形式に書いているだけです。次のように書いたほうがむしろ正確です。

${\displaystyle \int_{x\in X} \left(\int_{y\in Y} \psi(y)F(x)(dy) \right)\mu(dx) = \int_{y\in Y} \psi(y) F_\ast (\mu)(dy) }$

行きがかり上、マルコフ核の拡張は上付き飾りが付いた F^# と表しましたが、測度の前送り F_* と同じです。よって、前節最後の入れ子律の等式は、マルコフ核に関する随伴公式に帰着されます。

随伴公式は積分のフビニの定理です。ただし、マルコフ核が絡むと、単純なフビニの定理と少し違った形になります。単純なテンソル積測度ではなくて、依存テンソル積とでも呼ぶべき構成が必要です。が、この話題は別な機会にします。（[追記]「マルコフ核の随伴公式とフビニの定理」に書きました。[/追記]）

*1:事象〈可測集合〉Aは、確率的状態空間 P(X) 上のファジー述語 $\hat{A}$ :P(X) → [0, 1] とみなせるわけです。