圏論では、さまざまな絵図/テキスト式が出てきます。絵図〈diagram | picture〉とテキスト式〈text expression〉とのあいだの相互翻訳や、絵図/テキスト式を使った計算は、機械的作業(アルゴリズムの実行)です。したがって、手順をマスターすれば、誰でも出来ることです。ひらめきや才能が必要なのではなくて、トレーニングが必要なだけです。
ただし、手早く処理したりショートカットするために、多少のコツはあります。この記事では、ストリング図で記述されているマルコフ射(マルコフ圏の射)を、テキスト式に翻訳して計算する手順とコツを述べます。ここでのコツとは、「変数に名前を付けないで番号で済ませる」という(割とくだらない)方法です。
内容:
マルコフ圏とその多圏
マルコフ圏についてはここでは説明しません。「マルコフ圏 A First Look -- 圏論的確率論の最良の定式化」とそこから参照されている記事を参照してください。
C がマルコフ圏のとき、C をそのまま使うより(簡易的な)多圏を作ったほうが便利です(作り方は「対称モノイド多圏(簡約版)」参照)。D = Poly(C) を、Cから作った簡約多圏〈reduced polycategory〉とすると、D = Poly(C) は次のように定義されます。
- 対象: ( の対象のリストの集合)
- ホムセット:
ここで出てきたリストに対する総モノイド積 は次のように定義されます。
- ( の単位対象)
圏Dの結合と恒等射は、この定義と整合するように決めます。また、Dのモノイド構造は次のように定義します。
- (リストの連接 がモノイド積)
- 射に対するモノイド積は、 のモノイド積を引き継ぐ(多少の細工が必要)。
- (空リストが単位対象)
多圏Dにおけるプロファイルの書き方に、略記の習慣があります。
のとき、 を次のように書きます。
リストを囲む丸括弧を省略します。ここではこの略記を採用せずに、次のように丸括弧をちゃんと書きます。略記による便利さより弊害のほうが大きいと思うので。
マルコフ・テンソル
マルコフ圏の典型例は、可測空間の圏Meas上のジリィモナドのクライスリ圏Stocです。Stocの射はマルコフ核と呼びます(「マルコフ核: 確率計算のモダンな体系」参照)。
可測空間を有限離散可測空間だけに制限すると、マルコフ圏Stocの部分マルコフ圏FinDiscStocになります。圏FinDiscStocの射であるマルコフ核は(ちょっと拡張した)マルコフ行列で表現できます。そして、Poly(FinDiscStoc) の射はマルコフテンソル(後述)で表現できます。
「テンソル」は多義曖昧語ですが、ここで出てきたテンソル*1は、次の形の写像です。
ここで、ボールド体の などは有限集合のリストを表し、 は非負実数の半環を意味します。 はリストに対する総直積で、 と同様に定義されます。次の点には注意してください -- 空リストの総直積は単元集合*2で、その唯一の要素をアスタリスクで表します。
テンソル s をラムダ記法で書くならば:
として、露骨〈explicit〉な成分表示(入れ子の括弧を若干省略)をするなら:
反図式順記法に合わせるために、引数の左右順序をひっくり返す(ペアの右が第一成分、左が第二成分、区切り記号を縦棒とする)と:
色々省略して簡潔に書けば:
成分に展開するのをやめれば:
- 対象: ( は有限集合の圏)
- ホムセット:
テンソル(Tの射)の結合は、次のように定義します。
恒等射は次のようです。
ここで、 は、2つの引数が等しければ 1 を返し、そうでなければ 0 を返す関数です。
2つのテンソルのテンソル積(圏のモノイド積)は次のようです。
テンソル がマルコフテンソル〈Markov tensor〉であるとは、次の条件(保存法則〈conservation law〉という)を満たすことです。
- (保存法則)
射をマルコフテンソルだけに制限すると、圏 T の部分圏となるので、その部分圏を MT とします。
今定義した圏MTと、有限離散可測空間とマルコフ核の圏から作った簡約多圏 Poly(FinDiscStoc) のあいだには規準的〈canonical〉な同型があります。
この規準的な同型を通して、MT と Poly(FinDiscStoc) はしばしば同一視されます。ここでは、もっぱら圏 MT を扱いますが、その背後に Poly(FinDiscStoc) があることは想定しています。
この記事では触れませんが、関連するいくつかの圏があります。それらを表にまとめておきます。([追記]「マルコフ・テンソルに関連する圏達」により詳しい話を書きました。[/追記])
対象が番号/番号リスト | 対象が集合/集合リスト | 簡約多圏 |
---|---|---|
L | FinSet | Poly(FinSet) |
Mat | FXMat | Poly(FXMat) = FXTens |
Tens | FXTens = T | - |
L は、|L| := N, L(n, m) := Map({1, ..., n}, {1, ..., m}) で定義される圏です。行列の圏 Mat の対象集合も N で、番号ベースのテンソルの圏 Tens の対象集合は List(N) です。FXTens をこの記事では短く T と書いています。T は既に定義しました。
N, List(N) を、有限集合/有限集合のリストに一般化した圏が表の二列目にあります。表の三列目は二列目の圏を多圏化した簡約多圏です。FXTens は既に多圏なので多圏化する必要はありません。
FX は、Finitely eXtended の略で、単に X なら有限性の条件が外れます。
- XMat : 対象を(有限とは限らない)任意の集合にまで拡張した行列の圏
- XTens : 対象を(有限とは限らない)任意の集合のリストにまで拡張したテンソルの圏
保存法則を満たす行列・テンソルの圏には M を付けることにすると:
- MMat : 番号ベースのマルコフ行列の圏*4
- MTens : 番号ベースのマルコフテンソルの圏
- MFXMat : 集合ベースのマルコフ行列の圏、FinDiscStoc と同型。
- MFXTens : 集合ベースのマルコフテンソルの圏、Poly(FinDiscStoc) と同型。
[/補足]
例題: 同時化
次のストリング図を例題にします。この図が表す射をテキスト式で書き下します。
ストリング図をXyJaxで描いているので(「カリー/ハワード対応のための記法・図法」参照)だいぶ不格好です。幾つか注意をしておくと:
- 矢印があるので明らかですが、描画方向は上から下です。
- ノード(射の図示) は、三角形で表すのが多数派です。三角で囲むことが出来なかったので丸で囲んでます。
- は、マルコフ圏の対角射〈コピー射〉です。枝分かれしたワイヤーだけで描くことが多いと思います。
- 左側の I は恒等射です。通常、恒等射はノードとしては描かずワイヤーだけです。
図に出現している射のプロファイルを列挙します。
ストリング図全体として、次の射を表しています。
この射(テンソル)を、ラムダ記法で具体的に表現したらどうなるか? が課題です。
まず、ストリング図に出現するワイヤーに番号を付けておきます。
この番号を変数名に含む変数を使うことにします。次の5つの変数です。
そして、アスタリスク は、 の唯一の要素です。
それぞれの射(テンソル)を簡略なラムダ記法で表示すると次のようです。
ちょっとずつ計算してみると:
ここから先は、ラムダ関数式の本体式〈body expression〉だけを抜き出して計算します。次の表示を利用します。
計算を続けましょう。(後に解説があります。)
上の計算の詳細は次節にあるので、とりあえず結果を認めてもう一度ラムダ関数式のなかに収めると:
最後の変形は、ラムダ束縛変数の名前は好きにリネーム(アルファ変換という)してよい、という規則を使っています。
最終的結果である は、 の による同時化〈jointfication〉といいます。つまり、最初のストリング図は同時化の図だったのです。
総和の計算規則
ここからは、計算の規則の説明をします。個々の計算ではなくて、計算全般に共通するパターンの説明です。このテの説明には、式や変数を表すメタ変数が必要になります。筆記体の などは式を表すメタ変数、ギリシャ小文字 などは変数を表すメタ変数とします。
次はひとつの計算規則です。併置(単に並べる)は掛け算を意味します。
ただし、無条件に使える計算規則ではなくて、次の条件が付きます。
- 式 のなかに変数 が現れない。
例を挙げると:
これは、次のようにして計算規則を適用している例です。
- 変数 が、実際には
- 式 が、実際には
- 式 が、実際には
- 等式の左右は入れ替わって
次も総和に関する計算規則です。
総和の繰り返しは、2つの変数を同時に動かして一気に総和したものと同じです。総和記号はまとめたり分解したりできます。
例を挙げると:
これは、次のようにして計算規則を適用している例です。
- 変数 が、実際には (2個の変数)
- 変数 が、実際には
- 式 が、実際には
最後に、総和記号を消去するときに使う計算規則です。
記号の説明をすると:
- は、式 に出現する変数 を で置き換えた式
例を挙げると:
これは、次のようにして計算規則を適用している例です。
- 一番外側の総和はそのまま、内側の総和に計算規則を適用
- 変数 が、実際には
- 変数 が、実際には
- を前に持ってくる。
- 式 が、実際には
変数に名前を付けない
先の計算例では、使う変数は次のような名前を持っていました。
bashの関数定義やTeXのマクロ定義では、変数に名前はなくて番号で識別します。これはもちろん不便なことがありますが、変数は無名でもよい事例になっています。
変数を、ドル記号+番号 として先の計算をしてみると次のようになります。
ウゲゲ、なんか気持ち悪いですね。自然数値が定数として出現することはほとんどないので、番号(自然数値)そのものを変数として使ってしまっても問題はないでしょう。
これなら見やすい。さらに、 は と略記すると次のようになります。これが、僕が普段実際に使っている書き方です。
ワイヤーに番号が付いたストリング図(下に再掲)と見比べならが計算すると、ラクチンに計算できます。テキスト式が反図式順なので、上下左右の方向には注意する必要があります。
例題: 周辺化
もうひとつ例題をやっておきましょう。
射(テンソル) は次のプロファイルを持ちます。
とりあえずは名前のある変数を導入しましょう。
この変数により射をラムダ記法で書くと:
次の等式が使えます。
次の計算規則があると思ってもいいです。
変数を番号だけにして予備的な計算をしてみましょう。
これより:
最後の変形は、ラムダ束縛変数のリネーム(アルファ変換)です。この計算で得られた結果は、 の第一周辺化〈1st marginalization〉といいます。ストリング図の左右を入れ替えると第二周辺化〈2nd marginalization〉が定義できます。
まとめ
テンソル(Tの射)の結合と恒等射とテンソル積は、次のようです。
マルコフテンソルを定義する保存法則〈保存性〉は次の条件です。
基本的な射 に関しては次の等式が使えます。(変数名は適当に変更してかまいません。)
総和に関する計算規則には次があります。
- 式 のなかに変数 が現れないとき、