このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

豊饒プロ関手は豊饒な世界を提供するのか

昨日の記事「順序集合や距離空間も実はモノイドだった」において:

この事実の背後には大きなストーリーがありそうですが、個別事例としても面白いと思います。


冒頭で、「この事実の背後には大きなストーリーがありそう」と言いました。とはいえ、大きなストーリーはよく分かってません。

よく分かってないのだけど、「こんなんかも知れない」という現時点での感じをとりとめなく記しておきます。

内容:

行列計算の一般化

順序集合や距離空間も実はモノイドだった」の話は、特殊な圏を技巧的に使って、無理矢理な当てはめをしている印象があるかも知れません。そのような印象が生じる理由は、扱っている話題がミニチュア過ぎるせいだと思うのです。

もっと大規模な現象があって、極端に単純な一部を取り出しているのだろう、と。その大規模な現象を「大きなストーリー」と呼んだのです。ミニチュアによる実験結果と断片的な知識を、妄想で繋ぎ合わせると、大きなストーリーがおぼろげに浮かび上げる感じがします。

大きなストーリー=妄想をひと言でいえば、豊饒プロ関手(enriched profunctor)の計算体系があるだろう、ということです。「順序集合や距離空間も実はモノイドだった」では、順序半環を係数域とする行列計算をベースにしましたが、もっと大規模な行列計算だって出来るはず。大規模つっても、100万列×100万行の行列とかって話じゃなくて、構造的階層の上位における計算ね。

どうもうまい言葉が見つからない。つまんない言葉で表現するなら、行列計算の一般化です。

豊饒圏とプロ関手

豊饒圏に関しては:

ちょっと言葉に関して; 英語だと、-edと-ingを使って"enriched category"と"enriching category"の区別が出来るけど、日本語だと-ed, -ingみたいな区別ができないので、"enriching category"を意訳して豊饒化基礎圏とします。豊饒化基礎圏Vで豊饒化(enrichment)された圏をV-圏と呼びます。

モノイド圏Vを豊饒化基礎圏として、Xを対象の集合とする豊饒圏のホムは、X×X→V で与えられます。これは、半環Kを係数域とする正方行列 S×S→K と似てます。

特殊例 一般化?
係数の半環K 豊饒化基礎圏V
添字の集合S 対象の集合X
正方行列 S×S→K 豊饒圏 X×X→V

しかし、正方行列は掛け算が出来ますが、同じ対象集合X上の豊饒圏CDがあっても掛け算が定義できません。

掛け算ができる“圏のようなもの”としてプロ関手があります。C, Dを普通の(ホムが集合である)圏だとして、プロ関手は、Dop×CSet という二項関手(双関手)として定義されます。

FがCからDへのプロ関手、GがDからEへのプロ関手のとき、FとGの結合(合成)は次の公式で計算します。

 (G \circ F)(e, c) = \int^{d : D}G(e, d) \times F(d, c)

積分記号はコエンド(coend)と呼ばれる圏的演算で、無限和のようなものだと思ってかまいません。この公式は、形の上からは行列の積の公式と同じです。プロ関手が行列の一般化だと思って良さそうです。

プロ関手は集合圏Setを“係数域”に使ってますが、C, DV-豊饒圏なら、Vを使って、Dop×CV と定義するのが自然でしょう。次の一般化が考えられます。

特殊例 一般化
係数の半環K 豊饒化基礎圏V
添字の集合S V-豊饒圏C
正方行列 S×S→K V-プロ関手 Cop×CV
Kの掛け算 Vのモノイド積
総和 コエンド
行列の掛け算 V-プロ関手の結合
行列のあいだの順序 V-プロ関手のあいだの自然変換

ヒューズのアロー

ヒューズ(John Hughes)によるアロー(Arrows; http://www.cse.chalmers.se/~rjmh/Papers/arrows.pdf)は、いろいろな解釈がありますが、"Arrows, like Monads, are Monoids" (Chris Heunen and Bart Jacobs)によれば、とある圏のなかのモノイドとみなせます*1

とある圏とは、Cop×CC という二項関手の圏です。この形になっているのは、Cが自分自身を豊饒化基礎圏としているからです。アローが、Cop×CV(ただし、V = C)というV-プロ関手の圏のなかのモノイド対象の実例になります。

アローはモナドの一般化だと言われています。それは、圏Cの自己関手と自然変換の圏 Cat(C, C) が、圏Cの自己プロ関手と自然変換の圏 Prof(C, C) に埋め込めるからです。この埋め込みにより、Cat(C, C)内のモノイドであるモナドは、Prof(C, C)内のモノイドであるアローとして解釈できます。この事情は、S→S という写像が、添字集合Sのブール値正方行列(S上の関係)とみなせるのと同じです。

"What is a Categorical Model of Arrows?"でアトキー(Robert Atkey)は、アローはフレイド圏やその変種でモデル化できると言っています。また "Freyd categories are enriched Lawvere theories" (Sam Staton)は、フレイド圏が豊饒ローヴェル・セオリーだと主張しています。

アローがプロ関手の圏のなかに棲んでいる生き物だとすると、同種の存在物らしきフレイド圏/ローヴェル・セオリーもプロ関手の圏のなかで飼えるでしょう。

垣間見えたり、見えなかったり

プロ関手の圏(双圏)をProfとして、SetRel = CatProf という“比例式”はよく指摘されます。さらに、Kを順序半環、Vをモノイド圏として、SetRel : K-Mat = CatProfV-Prof という“三項比例式”が成立しそうです。

K-Matは、K係数の行列の全体です。K-Matにおけるお馴染みの概念や計算がV-Profにおける対応物を持つだろうと期待できます。行列計算の係数域Kを変えると様相がガラリと変わるように、豊饒化基礎圏Vを変えると V-Prof も変わります。その変わり方は、係数域の取り替えと同じように、(余)インデックス圏の構造で制御されるでしょう。

形式言語理論のための代数」で述べたように、オートマトン(ラベル付き遷移系)も行列とのアナロジーを持ちます。行列を中継して、オートマトンとプロ関手のアナロジーをたどると:

オートマトン プロ関手
型式言語の代数 豊饒化基礎圏V
状態空間 V-圏
オートマトン V-プロ関手
形式言語の包含順序 Vの射
オートマトンの順序 プロ関手のあいだの自然変換
状態空間のあいだの関係 V-圏のあいだの関手?
関係の転置 関手の随伴?
模倣
双模倣

模倣/双模倣あたりになるとナンダカ分かりません。

以上に述べたような“比例式”(対応)が正確である自信はありませんが、ミニチュアな実験結果から垣間見える向こうに大きなストーリーがあるのは間違いないと思えます。見えそうで見えない事が多いので、フラストレーションを感じますけど。

*1:[追記]Exequiel Rivas, Mauro Jaskelioff の http://www.fceia.unr.edu.ar/~mauro/pubs/Notions_of_Computation_as_Monoids.pdf (38p)にも、色々なモノイドの例があります。[/追記]