今年(2020年)の6月にマルコフ圏というものを知りました。
マルコフ圏の直接的応用は圏論的確率論(「圏論的確率論におけるCタイプとAタイプ」参照)ですが、他の分野への応用もありそうです。「マルコフ圏の一族」より引用:
マルコフ圏が応用できそうな分野には、データベース理論、形式言語理論、オートマトン理論、プログラム意味論などがあります。これらはたまたま僕が少し知っている分野で、他にも物理や工学などに応用可能ではないかと思います。
当初から、マルコフ圏はデータベース理論とは親和性が高そうだと感じていました。一方、ここ一週間くらい、確率グラフィカルモデルの圏論的定式化を探していました。
昨日・今日で*1、公理(条件化可能公理〈conditionalizable axiom〉)を追加したマルコフ圏から得られる確率空間の圏*2、そしてデータベース理論に向いた圏が、同じ圏論的定式化を持つことが分かりました。それがカップル化可能圏〈couplable category〉です。
カップル化可能圏は線形代数(内積ベクトル空間の圏)にも事例があり、ラムダ計算やシーケント計算とも関連を持ちます。ハイパーグラフ圏(ハイパーグラフ圏 一瞥)や自己双対コンパクト閉圏もカップル化可能圏の事例になります*3。
この記事では、カップル化可能圏の形式的定義とすぐ分かる性質を手っ取り早く紹介します。カップル化可能圏の応用としては、当面はベイズ確率論とデータベース理論を想定していますが、応用はまた別な記事で。
内容:
簡単に経緯の説明
僕が主たる事例として考えていた圏は「確率グラフィカルモデルの背後にある圏は何か? // 見通し」で触れた (1/D)/=a.s. です。この圏が、ハイパーグラフ圏〈ダンジョン圏〉になっていれば好都合ですが、どうもそうではないようです。ハイパーグラフ圏でなくても、自己双対コンパクト圏にはなっているのでは? と期待してみたのですが、無理矢理にコンパクト構造をでっち上げてもいいことはないようです。
そこで、自己双対コンパクト圏よりさらに弱い構造を考えてみました。ラムダ計算(モノイド閉圏の計算)やトレース計算(トレース付き圏の計算)にならって、コンビネータ〈オペレーター〉を使って定義してみました。これはうまくいくようです。構造の中核となるコンビネータは「カップル化コンビネータ」と名付けました。カップル化コンビネータを備えた圏がカップル化可能圏です。カップル化可能圏は、自己双対コンパクト圏やハイパーグラフ圏より弱い〈一般的〉概念です。
カップル化可能圏が、実は、よく知られた圏の別定義だったという可能性はあります。そうであったとしても、カップル化コンビネータを使った定式化が無意味にはならないだろうと思います。カップル化コンビネータはけっこう使い勝手がいいですから。
以前に「確率的推論・判断の計算法:マルコフ・テンソル絵算」という記事を書きました -- ひたすら具体例を述べている記事です。この過去記事の「マルコフ・テンソル絵算」は、未整理ではありますが、今回述べるカップリング計算(カップル化可能圏の計算)であったようです。
今回の記事では、応用については述べませんが、カップル化可能圏の一般概念がデータベースとベイズ確率では何に対応するかを表にしておきます。末尾にアスタリスクが付いた言葉は、当該分野には対応する語がないので、檜山がテキトーにネーミングしたものです。
データベース | ベイズ確率 | カップル化可能圏 |
---|---|---|
ドメイン | 確率変数 | 対象 |
テーブルスキーマ | 確率変数のリスト | 多対象 |
関連 | マルコフ核 | 射、多射 |
テーブル | 同時確率分布 | 多ポイント |
二部テーブル* | 二部同時確率分布* | カップル |
二部テーブル化* | 二部同時化* | カップル化 |
関連化* | 条件化 | 反カップル化 |
等値ジョイン | ジョイン* | ジョイン |
転置* | 転置* | 転置 |
反転* | ベイズ反転 | ダガー |
[追記 date="後日 11月半ば"]
アスタリスクが付いた用語に関して、次のようにしようかと思ってます(変更点のみ)。
データベース | ベイズ確率 | カップル化可能圏 |
---|---|---|
二部テーブル* | カップル* | カップル |
二部テーブル化* | 同時化*, カップル化* | カップル化 |
等値ジョイン | リンク積* | ジョイン |
[/追記]
カップル化可能圏の定義
C = (C, , I, σ) (記号の乱用、一部省略)は対称モノイド圏とします。β:I → II in C は、I と II のあいだの同型だとします(β = λI = ρI)。Cの対象 X, Y ごとに写像 CouX,Y が割り当てられている状況を考えます。(X, Y) CouX,Y が以下の条件〈公理〉を満たすとき、対称モノイド圏とコンビネータ〈オペレーター〉の組 (C, Cou) がカップル化可能圏〈couplable category〉です。
- CouX,Y:C(X, Y) → C(I, XY) in Set
- CouX,Y は可逆で、逆写像 DecX,Y:C(I, XY) → C(X, Y) in Set を持つ。
- [結合公式〈composition formula〉] f:X → Y, g:Y → Z in C に対して、
CouX,Z(f;g) = CouX,Y(f);(idXg) - [積公式〈product formula〉] f:X → Y, h:Z → W in C に対して、
CouX⊗Z,Y⊗W(fh) = β;(CouX,Y(f)CouZ,W(h));(idXσY,ZidZ) - [可換律〈commutative law〉] X∈|C| に対して、
CouX,X(idX);σX,X = CouX,X(idX)
カップル化可能圏 (C, Cou) の構成素〈constituent | ingredient〉は次のように呼びます。用語のバリエーション記述に正規表現を使っています。必要なら「用語のバリエーション記述のための正規表現」を参照してください。
- 対称モノイド圏Cは、カップル化可能圏 (C, Cou) の台対称モノイド圏〈台{モノイド}?圏 | underlying {{symmetric}? monoidal}? category〉。
- Cou = (|C|×|C| CouX,Y) は、カップル化コンビネータ〈{カップル化 | カップリング} {オペレーター | コンビネータ}? | coupling {operator | combinator}〉。
- Dec = (|C|×|C| DecX,Y) は、反カップル化コンビネータ〈{{反 | 脱}カップル化 | デカップリング}{オペレーター | コンビネータ}? | decoupling {operator | combinator}? 〉。
カップル化可能圏とは、「結合公式・積公式・可換律を満たす可逆なカップル化コンビネータを備えた対称モノイド圏」です。
カップル化と反カップル化は互いに逆ですが、対称性(あるいは双対性)はありません。例えば、次の等式は成立しません(成立するとは限りません)。
- DecX,Z(f;g) = (idZf);DecY,Z(g)
結合公式・積公式・可換律の双対を仮定してしまうと、自己双対コンパクト圏になってしまいます。反カップル化には等式的法則を何も仮定してないので、自己双対コンパクト圏よりカップル化可能圏が一般的な概念になっています。どのくらい一般的になっているのか? 現状よく分かりません。事例をよく調べる必要があるでしょう。
短縮記法と幾つかの等式
モノイド圏Cにおいて、I → XY in C の形の射をカップル{射}?〈couple {morphism}?〉と呼びます。カップル化可能圏のカップル化コンビネータは、任意の射をカップルに変換するコンビネータ〈オペレーター〉です。以下、一般の射を f, g など、カップルを s, t などで表すことにします。
「射 f:X → Y in C のカップル化」、「カップル s:I → XY の反カップル化」をそれぞれ次のように略記します。
- ∩f := CouX,Y(f)
- ∪s := DecX,Y(s)
これは、絵図表現との対応を強く意識した象形文字記法です(後述)。また、カリー化/反カリー化との類似性も意識しています。
ラムダ計算 | カップリング計算 |
---|---|
カリー化 f∩ | カップル化 ∩f |
反カリー化 g∪ | 反カップル化 ∪s |
ベータ変換等式 f∩∪ = f | ∪∩f = f |
エータ変換等式 g∪∩ = g | ∩∪s = s |
右付き添字と左付き添字の左右に意味はありませんが、これでラムダ計算とカップリング計算の区別ができます。
絵算では、カップル化/反カップル化は、トレースやカリー化と同じワイヤー曲げオペレーター〈wire bending operator〉になります。次がカップル化/反カップル化の図示です。図の描画方向は↓→で旗で示しています(「絵算の描画方向を示すために旗を使うことにした」)。
ηX := ∩(idX) とすると、∩f = ηX;(idXf) と書けます
∩f = ∩(idX;f) // 結合公式 = ∩(idX);(idXf) // ηX の定義 = ηX;(idXf)
したがって、カップル化コンビネータは、特別な射 ηX とモノイド積 と結合 ; で書けます。しかし、反カップル化コンビネータが特別な射とモノイド積と結合で書けるとは限りません。
この事情は、カリー化/反カリー化のときとは逆で、反カリー化は特別な射(評価射)と結合で書けますが、カリー化(ラムダ抽象)はそうはいきません。
カップル化コンビネータと同等な機能を持つ特別な射 ηX は単位〈unit〉と呼びます。コンパクト構造〈コンパクト閉構造〉の単位と同じ機能を持つからです。ただし、余単位に相当する射の存在は保証されません。その意味で、カップル化可能圏は半コンパクト構造〈semi-compact structure〉を持つ圏だと言えます。
[追記]
「半コンパクト」って言葉を使いましたが、以前「超コンパクト」って言い方をしたことがありましたね。
このときの「超コンパクト」は、自己双対コンパクトの意味です。半コンパクトは、自己双対コンパクトよりもっと弱い構造になります。
[/追記]
可換律(カップル化可能圏の公理)から単位は次を満たします*4。
- ηX;σX,X = ηX
「ラムダ計算の自然性とお絵描き」で述べたタイトニング等式とスライディング等式(の類似)はカップル化/反カップル化でも成立します。ストレートなスライディング等式は結合公式そのものです。
- [タイトニング等式〈tightening〉] カップル s:I → XY in C と 射 g:Y → Z in Cに対して、
∪(s;(idXg)) = (∪s);g - [ストレート・スライディング等式〈straight sliding〉 射 f:X → Y, g:Y → Z in C に対して、
∩f;(idXg) = ∩(f;g)
後で述べるダガー(記号は (-)†)を使うと、カーブに沿ったスライディング等式も成立します。
- [カーブ・スライディング等式〈curved sliding〉] 射 f:X → Y, h:X → T in C に対して、
∩f;(hidY) = ∩(h†;f)
タイトニング等式、カーブ・スライディング等式は絵算を使えば容易に示せます(次節参照)。
絵図表現と絵算
(C, Cou) はカップル化可能圏だとします。カップル化コンビネータと反カップル化コンビネータは、前節の絵のように、ワイヤーを曲げる操作として描きます。したがって、カップル化/反カップル化された結果は曲がったワイヤーを持ちます。
カップル化可能圏における一般的な射 f:X → Y in C、カップル s:I → XY in C、単位 ηX:I → XX は次のように描きます。
単位 ηX は CouX,X(idX) のことでした。カップル化は、単位を前結合〈pre-compose〉することで得られました、∩f = ηX;(idXf) 。
カップル化と反カップル化が逆であることを表す ∪∩f = f (一種のニョロニョロ等式)は、単位を使って次のようにも表せます。
カップル化可能圏の公理である3つの法則は、絵等式では下のように描けます。
- [結合公式] ∩(f;g) = ∩f;(idXg)
- [積公式] ∩(fg) = β;(∩f∩g);(idXσY,ZidZ)
- [可換律] ηX;σX,X = ηX
タイトニング等式は下のようです。
- [タイトニング等式] ∪(s;(idXg)) = ∪s;g
カーブ・スライディング等式は次のようです。ここで、h† は、下側の等式を満たすような射です(一意に決まる)。
- [カーブ・スライディング等式]
- [ダガーの定義] ∩(h†) = ∩h;σX,T
カップルの圏
カップル化可能圏 (C, Cou) に対して、対象類〈対象集合〉は共有して、カップルを射とする新しい圏を作れます。新しい圏を D := Couple(C) として以下に定義します。
- |D| := |C|
- D(X, Y) := C(1, XY)
- 結合: s∈D(X, Y), t∈D(Y, Z) に対して、s*t := ∩(∪s;∪t)
- 恒等射: cidX := ηX
この定義に従えば、(D, *, cid) が圏になることは示せます。さらにDは、次のモノイド積 により対称モノイド圏になります。
- s:X → Y in D, u:Z → W in Dに対して、
su := β;su;(idXσY,ZidW)
定義等式の右辺では、s, u をCのなかで考えていることに注意してください。
カップルの結合とモノイド積は次のように図示します。
以上のように D := Couple(C) を定義すると、CouX,Y:C(X, Y) → D(X, Y) in Set となります。ホムセット間の写像 CouX,Y をすべて寄せ集めると、モノイド積も厳密に保存する関手 Cou:C → D になります。つまり、次が成立します。
- Cou(f;g) = Cou(f)*Cou(g)
- Cou(idX) = cidX
- Cou(fh) = Cou(f)Cou(h)
反カップル化は Dec:D → C という関手になり、CouとDecは互いに逆な関手になります。CouとDecにより、モノイド圏CとDはモノイド同型なモノイド圏です。モノイド同型ということは、CとDは区別がつかない程にソックリなモノイド圏ということです。
カップル化可能圏のカップルは、I → XY という形から積カップル〈product couple〉と言えるでしょう。一方、ラムダ計算で使うモノイド閉圏のカップルは I → [X, Y] という指数カップル〈exponential couple〉です。カップリング計算とラムダ計算が似ているけど違うのは、積カップルと指数カップルが似ているけど違うからでしょう。
ダガー構造
カップル化可能圏 (C, Cou) から作られたカップルの圏 D = Couple(C) のモノイド圏構造は次の記号を使うことにしました。
結合 | s*t |
恒等射 | cidX |
モノイド積 | su |
D の射(カップル)をもとの圏Cで考えることもあります。そのときは、;, id, で計算することもできます。
カップル s:I → XY in C (s:X → Y in D) に対して、sの転置〈transpose〉を次のように定義します。
- sT := (s;σX,Y in C)
定義等式の右辺はCのなかで考えてますが、こうして作られた sT を sT:Y → X in D と解釈します。
転置は次の性質を持ちます。
- (sT)T = s
- (s*t)T = tT*sT
- (cidX)T = cidX
これはダガー圏の公理です。さらに、ダガーはモノイド構造と協調します。
- (st)T = sTtT
- (αX,Y,Z)T = (αX,Y,Z)-1
- (λX)T = (λX)-1
- (ρX)T = (λX)-1
ここで、α, λ, ρ は、モノイド圏の構造射(結合律子、左単位律子、右単位律子)です。
f† = ∪((∩f)T) の関係で結ばれる、C上のダガー〈dagger〉に関しても同じ法則に従います。つまり、CもCouple(C)もダガー対称モノイド圏であり、CouとDecはダガー構造も含めた同型を与えることになります。
対称モノイド圏の標準簡約多圏の利用
今までの話は、まず対称モノイド圏があり、そこに様々な構造を載せていくスタイルでした。しかし、カップル化可能圏を計算デバイスと考えるときは、「対称モノイド多圏(簡約版)」で導入した簡約多圏を利用するのが便利です。
対称モノイド圏には、標準簡約多圏が存在します。標準簡約多圏は、対象がリスト(多対象)であり、厳密対称モノイド圏になっています。厳密モノイド圏は一般のモノイド圏に比べて扱いやすく、ストリング図との対応もより直接的になります。
カップリング計算の計算デバイスを組み立てる目的では、対称モノイド多圏を最初から準備して、その上にカップル化コンビネータ、反カップル化コンビネータを与えるほうがよさそうです。
おわりに
急ぎ足でカップル化可能圏の説明をしました。公理的定義は思い付いたばかりなので、不足や冗長性があるかも知れません。公理の妥当性を確認するには、具体例、特に「確率グラフィカルモデルの背後にある圏は何か? // 見通し」の (1/D)/=a.s. をよく調べる必要があります。データベースからの具体例も重要です。
感触としては、カップル化可能圏は絵算との相性が良く、かなりの再配置可能性〈reshapability〉(「ダンジョン圏における確率伝搬法」参照)を持つので、使いやすい気がします。
[追記]
2017年の初春に、確率の計算をゴタゴタ考えたことがあったけど、マルコフ圏とカップル化可能圏を使って整理できるかも知れないな。
[/追記]
*1:10月12日、池尻大橋駅すぐそばのカフェ・ベローチェで気づきました。 「余可換コモノイド・モダリティ事件の解説」に書いた余可換コモノイド・モダリティと部分圏の関係に気づいたのもカフェ・ベローチェでした。
*2:[追記]単なる確率空間の圏ではなくて、ホムセット上の同値関係による商を取る操作も必要です。[/追記]
*3:カップル化可能圏の事例達の相互関係; ハイパーグラフ圏は必然的に自己双対コンパクト閉圏になります。データベース理論に向いた圏(関係圏Rel)と内積ベクトル空間の圏は、自己双対コンパクト閉圏の事例です。マルコフ圏から得られる確率空間の圏は別種の事例です。
*4:絵図表現すると、可換律は、一種のヤンキング等式と言えます。