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

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

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

参照用 記事

絵図的手法: 中間整理

以下は、最近書いた記事のリスト(並びは日付順)です。内容は、絵図的〈pictorial | graphical | diagrammatic〉手法に関するものです。

  1. テンソルの可視化のための半グラフ
  2. 型付き半グラフと指標
  3. 半グラフからシステムの記述へ
  4. 入れ子の半グラフとバエズ/ドーラン・ツリー
  5. スケマティック圏: お絵描きできる場所

ここらで中間的な整理をしておきます。$`\newcommand{\mrm}[1]{\mathrm{#1}}
\newcommand{\cat}[1]{\mathcal{#1}}
\newcommand{\In}{\text{ in } }
\newcommand{\hyp}{\text{-} }
\newcommand{\id}{\mathrm{id} }
`$

内容:

視覚化可能な組み合わせ構造

絵図的手法と言っているのは、視覚化可能な組み合わせ構造を主たる道具として使っているからです。“視覚化可能な組み合わせ構造”の呼び名が色々あるのでまとめておきます。横の並びは同義語です。

1 半グラフ 無向ストリング図 無向ワイヤリング図
2 有向半グラフ ストリング図 有向ワイヤリング図
3 ワイヤリング図(無向・有向のどちらか)
4 ワイヤリング図(無向も有向も)

横方向の行ごとの説明は:

  1. ワイヤーに向きがない場合。単に「半グラフ」と言ったら、ワイヤーに向きはありません。
  2. ワイヤーに向きがある場合。単に「ストリング図」と言ったら、ワイヤーに向きがあります。
  3. デフォルトとして、無向または有向だと約束している場合。
  4. デフォルトの約束がない場合。単に「ワイヤリング図」と言ったら、無向と有向を総称していることにします。

有向だけでなくて無向の場合を扱いたいので、総称的な意味で「ワイヤリング図」を使うことにします。「ネットワーク」も「ワイヤリング図」と同義ですが、意味が広すぎるので単独では使わず、「テンソルネットワーク」のような形容詞・修飾語付きで使います。(テンソルネットワークは、ボックスがテンソルを表すワイヤリング図です。)

有限集合に載る構造

有限集合に追加する構造として次のようなものがあります。

  1. 付点構造: 有限集合の一点〈特定要素〉を指定する。
  2. ラベリング: ひとつの集合 $`L`$ を決めて、有限集合から $`L`$ への写像を指定する。
  3. 全順序構造: 有限集合の要素を一列に順序付ける。
  4. 循環順序構造: 実際には順序ではないが、全順序構造と同様に後者〈サクセッサ〉を指定できる。

典型的ラベリングには次があります。

  1. 型付け〈typing〉: 型の集合 $`T`$ へのラベリング
  2. 極性付け〈polarization〉: $`\{+, -\}`$ へのラベリング

有限集合 $`X`$ に全順序があると、標準的な順序構造である $`1 \lt 2 \lt \cdots \lt n`$ とのあいだに順序を保った同型写像があります。逆に、$`X`$ と集合 $`\{1, 2, \cdots, n\}`$ との同型があれば、その同型から $`X`$ 上に全順序を誘導できます。

$`\bar{n} = \{1, 2, \cdots, n\}`$ として、有限集合 $`X`$ との同型

$`\quad e: X \to \bar{n} \text{ isomorphism } \In {\bf FinSet}`$

を、$`X`$ の列挙〈enumeration〉と呼ぶことにします。先に述べた事情から、次の2つの概念は同じことです。

  1. 全順序を持った有限集合 $`(X, \le)`$
  2. 列挙を持った有限集合 $`(X, e)`$

以上に述べたような構造を持つ有限集合は次のように呼びます。

  1. 付点有限集合〈pointed finite set〉
  2. 型付き有限集合〈typed finite set〉
  3. 極性付き有限集合〈polarized finite set〉
  4. 全順序有限集合〈totally ordered finite set〉
  5. 循環順序有限集合〈cyclically ordered finite set〉
  6. 列挙付き有限集合〈enumerated finite set〉

構造が載った有限集合は、スケマティック圏の対象として使います。

スケマティック圏

スケマティック圏〈schematic category〉は「スケマティック圏: お絵描きできる場所」で定義しました。標準スケマティック圏 $`{\bf SC}`$ は恒等関手を忘却関手としてスケマティック圏です。他のスケマティック圏の概要を述べます。

次のようなスケマティック圏があります。

略称 対象
TypedSC 型付き有限集合 型を保存する写像
PolarSC 極性付き有限集合 任意の写像
EnumSC 列挙付き有限集合 任意の写像

前節で述べたように、列挙付き有限集合は全順序有限集合と同じことです。また、次も同じです。

  • 付点循環順序有限集合は全順序有限集合と同じ。
  • 極性付き全順序有限集合は、分割された部〈パート〉ごとに全順序を持つ二分割された〈bipartite〉有限集合と同じ。

スケマティック圏の対象は、Typed, Polar, Enum の組み合わせでだいたい作り出せます。極性付き有限集合を対象とするスケマティック圏の特別なものとして、極性を反転させるワイヤリング写像に制限したスケマティック圏があります。ワイヤリング写像が極性を反転するなら、すべてのワイヤーに向きが付きます。ワイヤーに向きが付くスケマティック圏の略称は DirSC とします。

ここまでに出てきたスケマティック圏の固有名は次のようです。

  • $`{\bf SC}`$
  • $`{\bf TypedSC}`$
  • $`{\bf PolarSC}`$
  • $`{\bf EnumSC}`$
  • $`{\bf DirSC}`$

組み合わせすると、例えば次のようなスケマティック圏も作れます。

  • $`{\bf DirTypedSC}`$
  • $`{\bf EnumPolarTypedSC}`$

ワイヤリング射、ワイヤリングオペレーション、ワイヤリング図

スケマティック圏 $`\cat{S}`$ を次のように書くことにします。最後の $`U^\cat{S}`$ は標準スケマティック圏 $`{\bf SC}`$ への忘却関手です。

$`\quad \cat{S} = (\cat{C}^\cat{S}, N^\cat{S}, \nu^\cat{S}, W^\cat{S}, \cat{W}^\cat{S}, U^\cat{S})
`$

ワイヤリング射の全体 $`W^\cat{S}`$ は、台圏 $`\cat{C}^\cat{S}`$ の射の集合 $`\mrm{Mor}(\cat{C}^\cat{S})`$ の部分集合です。

$`\quad W^\cat{S} \subseteq \mrm{Mor}(\cat{C}^\cat{S})`$

対象 $`A\in |\cat{C}^\cat{S}|`$ に対して、$`W^\cat{S}(A)`$ を次のように定義します。

$`\quad W^\cat{S}(A) := W^\cat{S} \cap \cat{C}^\cat{S}(A, A)`$

この記法を使うと、ワイヤリングオペラッド $`\cat{W}^\cat{S}`$ のオペレーション〈複射〉の集合〈マルチホムセット〉 $`\cat{W}^\cat{S}(\hyp, \hyp)`$ は次のように定義できます。

$`\quad \cat{W}^\cat{S}( (A_1, \cdots, A_n), B) := W^\cat{S}( (\sum_{i = 1}^n A_i) + N(B) )
`$

この定義は集合としての同一性を主張してますが、同じ集合の要素でも役割り・位置づけが違うので、次のように呼び分けます。

  • $`W^\cat{S}(\hyp)`$ の要素をワイヤリング射〈wiring morphism〉と呼ぶ。
  • $`\cat{W}^\cat{S}(\hyp, \hyp)`$ の要素をワイヤリンオペレーション〈wiring operation〉と呼ぶ。

オペラッド〈複圏〉 $`\cat{W}^\cat{S}`$ のオペラッド結合は、オペレーション〈複射〉に対するオペレーション〈演算〉です。

ワイヤリングオペレーションは、自然数でインデックス付けられたボックス〈頂点〉を持つ半グラフ(場合により有向)とみなせます。「半グラフ、または有向半グラフ」と「ワイヤリング図」は同義語なので、ワイヤリングオペレーションの視覚化がワイヤリング図だと言えます。

システムスキーマとSSモナド

半グラフからシステムの記述へ で次のような概念・用語を導入しました。

  • インターフェイス付き圏
  • システムスキーマ〈SS〉
  • SS構成
  • SSモナド

インターフェイス付き圏〈category with interface〉は、スケマティック圏 $`\cat{I}`$ (Interface の意味で I を使う)への関手を備えた圏です。ソフトウェアシステムを想定していた文脈なので「インターフェイス」を使いましたが、「インターフェイス」と同義あるいは類義な言葉に次があります。

  • 型、プロファイル、指標〈シグネチャ〉、アリティ

「境界プロファイル」、「ボーダー情報」といった言葉を使ったこともあります。行きがかりで言葉は変わる可能性がありますが、ここでのインターフェイスは“外部からの見え方を特徴づける情報”のことです。内部構造はインターフェイスに反映されません。

システムスキーマ〈system schema〉は、実体としてはワイヤリング図です。ソフトウェアシステムを想定していた文脈であったことと、ワイヤリングオペレーションとしてのワイヤリング図との混同をさけるために別な言葉「システムスキーマ」を使いました。回路図〈circuit diagram〉とか単に図式〈diagram〉と呼ぶ案もありますが:

Circ構成、Diag構成と混同しないようにSS構成としたわけです。SS構成〈SS construction〉は、インターフェイス付き圏 $`\cat{D}`$ からインターフェイス付き圏 $`\mrm{SS}(\cat{D})`$ を作る構成です。インターフェイス付き圏達の圏の自己関手になります。

SS構成は単なる関手ではなくてモナドになります。SSモナド〈SS monad〉です。SSモナドが絵図的手法のメインの道具だと思います。特に、SSモナドのアイレンベルク/ムーア代数は重要な構造です。「インターフェイス」「システムスキーマ」という言葉はソフトウェアに寄り過ぎなので、呼び名を変える可能性はありますが、SSモナドが重要であることに変わりはありません。

そしてそれから

図式的手法に関する今までの記事で、不明瞭だったと思える幾つかの点について補足しました。

枠組みだけの議論では面白くないので、具体的なインターフェイス付き圏を定義して、SS構成により新しいインターフェイス付き圏を構成する例が欲しいですね。インターフェイス付き圏として述語〈predicate〉の圏が、論理との関連もあり面白そうです。