位相空間について
"位相"と聞くと、なにやらSFの香りがしてきますが、そんな話ではなく、純粋に数学の"位相空間"について復習する。
definition 開集合系と位相空間
集合$S$に対し、開集合系$\textrm{Open}(S)$とは、次の3つを満たす$S$の部分集合族のことである。
- $S \in \textrm{Open}(S)$ 、かつ、$\varnothing \in \textrm{Open}(S) $
- 自然数$ m \in \mathbb{N} $ で $ \mathit{O}_1,\mathit{O}_2,\dots,\mathit{O}_m \in \textrm{Open}(S) $ なら次が成り立つ。\[ \bigcap_{k=1}^m \mathit{O}_k \in \textrm{Open}(S) \]
- 任意の集合$\Lambda$(無限集合でもよい)に対し、各元$\lambda \in \Lambda$から$\mathit{O}_{\lambda} \in \textrm{Open}(S) $への対応を与えたときつぎがなりたつ。\[ \bigcup_{\lambda \in \Lambda} \mathit{O}_{\lambda} \in \textrm{Open}(S) \]
この開集合系$\textrm{Open}(S)$と元の集合$S$のペア、$( S,\textrm{Open}(S) )$を位相空間という。(位相を入れる、という動詞はこの開集合系を構成することである)
ややこしいが、開集合系の
- 条件2は、部分集合の"有限"な共通集合もその開集合系に含むことを表し、
- 条件3は、部分集合の"無限も含めた"和集合も開集合系に含む、
ということを示している。
ところで、以前までの説明で、Pre順序とPre順序圏$\textrm{PrO}$というのを書いた。
Category Theory for scientists(David spivak) メモ ... グラフとPre順序
Pre順序という構造は、実は、集合$S$の部分集合$\mathbb{P}(S)$に対しても当てはまる。
ある集合$S$の部分集合$ X,Y \in \mathbb{P}(S)$に対して、$X \subseteq Y$である場合に、Pre順序の表記$ X \le Y $と対応させれば、$(\mathbb{P}(X),\subseteq )$はPre順序である。つまり、集合の部分集合の関係を、順序関係に翻訳すればよい。
戻って、先の位相空間$(S,\textrm{Open}(S) )$の開集合系$\textrm{Open}(S)$を考えると、共通集合と和集合の条件2,3から、開集合系とは、対象集合の部分集合族から順序構造も維持される状態で選びだされたもの、ということがわかる。
最もよく見かける位相空間は、3次元のユークリッド空間だが、これに対しては、各点$x \in S$の距離が定義できて*1、この距離によって、順序関係が定義されているとイメージしている。
さて次に、位相空間と位相空間の間の連続写像というものについて、定義を見る。
definition 位相空間の連続写像
位相空間$(X,\textrm{Open}(X) )$と、$(Y,\textrm{Open}(Y) )$における関数 $f:X \to Y$が、連続写像であるとは、任意の$Y$の開集合系の逆像が$X$の開集合となることをいう。
すなわち、
\[ Y \in \textrm{Open(Y)} \rightarrow f^{-1}(Y) \in \textrm{Open}(X) \]
が成り立つ$f$のことである。
なんだか不思議な定義で、$f$の逆像$f^{-1}$が定義の中に含まれている。これが何で"連続"になるかについては、多様体の基礎のキソにある、"位相空間の基礎のキソ"の資料がお勧め。(位相空間の定義自体のイメージ化もできるのでぜひ参考に)
要するに、集合側については、$f:X \to Y$なのだが、部分集合族で定義された開集合系においては、逆像$f^{-1}:\textrm{Open}(Y) \to \textrm{Open}(X) $となっているような写像ということになる。開集合系とは、部分集合の順序構造によって定義されている。直感的には、この順序の構成が逆像によって対応することで、連続が担保されている、と理解している。
この写像の定義を使って圏を構成することができる。つまり、いろいろな位相空間をオブジェクトとして、射を上述の連続写像とした圏である。これを、$\textrm{Top}$とかく。
位相圏$\textrm{Top}$と集合圏$\textrm{Set}$の間には、忘却関手が存在する。これは自明だろう。
\[ \textrm{Top} \rightarrow \textrm{Set} \]
さらに、位相圏$\textrm{Top}$とPre順序圏$\textrm{PrO}$の間には、反変関手*2が存在する。これは、上記の連続写像の定義で$f^{-1}$を割り当てればよい。
\[ \textrm{Top} \rightarrow \textrm{PrO} \]
最後に、"コンパクト"の定義についてメモる。
definition コンパクト空間
位相空間 $ ( X , \textrm{Open}(X) )$がコンパクトであるとは、その部分集合 $A$において、
\[ A \subset \bigcup_{\lambda \in \Lambda} \mathit{O}_\lambda \mathit{O}_\lambda \in \textrm{Open}(X) \]
であれば、かならず有限個の$\lambda_1,\lambda_2,\dots,\lambda_n \in \Lambda$を選んで
\[ A \subset \bigcup_{k=1}^n \mathit{O}_{\lambda_k} \mathit{O}_{\lambda_k} \in \textrm{Open}(X) \]
とすることができること。(参：コンパクト空間 - Wikipedia )
これまたややこしくなっている。一番最初に説明した位相空間の開集合系の定義で3つ目の和集合の条件は、無限でもよかったのだが、これが無限であっても、有限個の集合で"上から押さえられる"様なイメージでいればよいかと。
ちなみに、任意の点$x \in X $に対して、コンパクトであれば、"局所コンパクト"という。
ちなみに、距離空間$M$がコンパクトであることと、$M$が完備かつ全有界であることは同値なのだそうだ。
数学とは、言語の学問なんだな。
Category Theory for scientists(David spivak) メモ ... 関手
前回までで圏の例を説明したので、今度は関手(functor)の説明に入る。
Definition 4.1.2.1.
$C$と$C'$を圏とする。$C$から$C'$への関手(functor)は、$F:C \to C' $と書き、次のA,B,の成分を持ち、1,2,の法則が成り立つものとする。
- A. オブジェクトの関数 $ Ob(F): Ob(C) \to Ob(C') $ これは単純に$ F: Ob(C) \to Ob(C') $ と記述してもよい。
- B. すべてのオブジェクトのペア$c,d \in Ob(C) $に対して、\[ \textrm{Hom}_{F}(c,d) : \textrm{Hom}_C(c,d) \to \textrm{Hom}_C'( F(c),F(d)). \] これは、単純に$F:\textrm{Hom}_C(c,d) \to \textrm{Hom}_C'(F(c),F(d))$ と書いてもよい。
- $F$に対して、Identitiesが保存される。つまり、どんなオブジェクトでも、$c \in Ob(C) $ 次が成り立つ。$ F(\textrm{id}_c) = \textrm{id}_{F(c)} $
- $F$に対し、合成に関して保存される。つまり、どんなオブジェクト $ b,c,d \in Ob(C) $と射$g:b \to c , h: c \to d $でも、次が成り立つ。$ F(h \circ g) = F(h) \circ F(g) $
今まで説明した圏で、最も単純な例として、モノイドから集合への関手がある。モノイドの定義では、$ \textit{M}= (M,e,*) $と書き、$ M $ は集合になるのであった。そして、モノイド圏$\textrm{Mon}$における射は、$ f: M \to M' $と、$ M $ の写像でかけるのであった。そこで、各モノイド$\textit{M}$から、集合 $ M $ を抽出する関数を$U$と描くことにしよう。
\[ U:\textrm{Mon} \rightarrow \textrm{Set} \]
$U$は、上記の定義どおり関手となる。(このように、構造自体を忘れる関手を忘却関手と呼ぶ)
同様な忘却関手として群の圏$\textrm{Grp}$とモノイド圏の関手も定義できる。
\[ U:\textrm{Grp} \rightarrow \textrm{Mon} \]
プレ順序圏$\textrm{PrO}$とグラフ圏$\textrm{Grph}$についても関手を構成することができる。すなわち、
\[ P:\textrm{PrO} \rightarrow \textrm{Grph} \]
あるプレ順序圏のオブジェクトであるプレ順序構造を$\chi \in \textrm{PrO}$とすると、$ \chi $のそれぞれの要素をグラフの頂点とし、射の関係$ \le $ をグラフの矢印とみなせば、$\chi$はグラフ化することができる。これが、関手$P$の$ Ob(P): Ob(\textrm{PrO}) \to Ob(\textrm{Grph}) $ にあたる。プレ順序圏の準同型 $ f : \chi \to \eta $ についても、$ \textrm{Grph} $ と同様の構造に関する準同型が定義されているので、対応する $ \textrm{Grph} $ の準同型を見つけることができる。
ただし、これは全射ではない。グラフにおいては、圏の合成則のように $a,b,c$があるグラフ構造の頂点として、$ a \to b $かつ$b \to c $の矢印があれば、$ a \to c $という矢印が存在する、とは限らない。これらのグラフは、先の関手$P$で写像先に対応するオブジェクト（これをImageと呼ぶ$\textrm{Im}(P)$）には入らない。(プレ順序には合成則が成り立つから)
ところが、前回説明したグラフのパス ${\textrm{Path}}_G$ の定義を用いると、さきとは逆の、
\[ Im:\textrm{PrO} \rightarrow \textrm{Grph} \]
という関手も定義して作り出せることがわかる。$\textrm{Path}_G$は、$v_1,v_2,\dots,v_n$と、各頂点を矢印でたどったすべての集合だった。この$v_1,v_n $について、$\textrm{Path}_G$が存在するのであれば、新たに$src(a') =v_1 , tgt(a')=v_n$なる矢印$a'$を矢印集合$A$に追加する($A'= a' \cup A$)。
こうして、$\textrm{Path}$が通っている頂点同士を新たに矢印と考えた矢印集合$A'$を用いたグラフ上では、矢印の合成則が成り立つ。合成則が成り立てば、対応するプレ順序圏を構成できるので、対応するプレ順序圏のオブジェクトを見当つけることができるというわけである。(こちらは全射のはずだ)
さて、今まで示したように、圏と圏は関手で関係付けることができる。これは、圏のオブジェクトと圏の射と同じ構造になっている!!!!つまり、圏自体をオブジェクト、関手を射とした(メタな)圏が構成できるということになる。これを、$\textrm{Cat} $と呼ぶ。
\[ \textrm{Hom}_{\textrm{Cat}}(C,D) = \{ F:C \to D | F は関手 \} \]
(※実はデータベースのスキーマはこの圏の圏と同値である、というのがCT4Sの主題である。この話はまた後で)
最後に、以前紹介したモノイド作用を関手で表現する方法について紹介する。
モノイドについては、モノイドをオブジェクト、モノイドの準同型を射としたモノイド圏$\textrm{Mon}$というものを紹介した。しかし、モノイド自体を圏と考えることもできる。このとき、圏のオブジェクトは1つ(これを$\bigstar$としよう)で、射は$M$の元である。
\[ \textrm{Hom}(\bigstar,\bigstar)= M \]
モノイドの単位元$e$は、この圏の$\textrm{id}$だし、合成則もそれぞれ成り立つ。あるモノイド$(M,e,*)$の圏を$\textit{M}$とおくことにする。すると、それぞれのモノイドの間の準同型はモノイド圏$\textit{M} , \textit{M'}$の関手、
\[ \textit{M} \rightarrow \textit{M'} \]
であることがわかる。
モノイド作用は、以下のように集合に対してモノイドの元で"操作"するものであった。
\[ \circlearrowleft : M \times S \to S \]
これは、先のあるモノイドを圏とみなした$\textit{M}$から集合圏$\textrm{Set}$への関手(a set-valued functor)とみなすことができる。
\[ F: \textit{M} \rightarrow \textrm{Set} \]
$\textit{M}$は、オブジェクトが一つ$\bigstar$であった。これは、$\textrm{Set}$上の何らかの集合$S$へと関手により割り当てられる。そして、各モノイドの元$M$は、集合$S$から集合$S$への射に割り当てられる。つまり、
\[ H_F : M \rightarrow \textrm{Hom}_{\textrm{Set}}(S,S) \]
である。
このように、ある圏と圏の関手が対象の構造を表すということがありうる。もう一つ例として、有向グラフついて紹介する。次のような圏を考える。
\[ A \overset{src}{\underset{tgt}{\rightrightarrows}} V \]
これは、$A$と$V$という２つのオブジェクトを持ち、$src$と$tgt$の射を持つ圏である。これを$\textrm{GrIn}$と書く。この圏から集合への関手を考えると、
\[ G : \textrm{GrIn} \rightarrow \textrm{Set} \]
実は、あるグラフの構造を示していることがわかる。
$A$のオブジェクトが$\textrm{Set}$のうちのある集合に対応すると、それがグラフの矢印の集合となり、同様に$V$のオブジェクトが頂点集合へ対応する。そして、それぞれ$src$、$tgt$は、矢印集合から頂点集合への"集合としての写像"(はいくつもあるが、ここで表現しようとしているグラフの構造に対応する写像)に対して、対応すればよい。
このように$\textrm{GrIn}$から、$\textrm{Set}$への関手は、グラフの具体例(instance)を示すことができるのである。
(※CT4Sの主題であるデータベースについては、データベーススキーマの圏$\textrm{Sch}$から集合$\textrm{Set}$への関手がデータベースインスタンス を表現できることが示される。)
parallel python + Simple MapReduce
BigData系のhadoopなどで有名になったMapReduceという処理体系がある。 大量のデータ処理をサーバ間を超えて並列に実行したい場合、それぞれのサーバ同期は最小限に抑えたほうがよい。MapReduceは、MapperとReducerという２つの処理を並列に実行することで、サーバ同期を最小限に抑えて実行できるものである。(と、僕は理解している)
これの簡単なpythonのサンプルが以下にある。
multiprocessing で MapReduce を実装する
これはこれで面白くって、非常に簡単なコードで並列処理ができるので、結構使っている。けれど、せっかくなので超並列MPPで、異なるサーバ間で実行できるようにしたくなる。
pythonの超並列実行モジュールとして、先のコードでも利用しているmultiprocessingでもできるのであろうが、非常に簡単に実装できるということで、Parallel pythonを使ってみる。
以下、コード。
import itertools
import collections
import pp
def forfunc(func,lst):
out=[]
for l in lst:
out.append( func(l) )
return out
class SimpleMapReduceServer(object):
def __init__(slf, hosts, ncpus=None):
slf.map_func = None
slf.reduce_func = None
if ncpus==None:
slf.js = pp.Server(ppservers=hosts)
else:
slf.js = pp.Server(ncpus=ncpus,ppservers=hosts)
def SetMapReduce(slf,map_func, reduce_func):
slf.map_func = map_func
slf.reduce_func = reduce_func
def partition(slf, mapped_values):
partitioned_data = collections.defaultdict(list)
for key, value in mapped_values:
partitioned_data[key].append(value)
return partitioned_data.items()
def __call__(slf, inputs, map_chunksize=1,reduce_chunksize=100):
map_jobs=[]
for i in range(0,len(inputs),map_chunksize):
ipt=inputs[i:i+map_chunksize]
map_jobs.append(slf.js.submit(forfunc,(slf.map_func,ipt),(slf.map_func,)) )
mapped_values=[]
for process_out in [ j() for j in map_jobs]:
mapped_values+=process_out
partitioned_data = slf.partition(itertools.chain(*mapped_values))
reduce_jobs=[]
for i in range(0,len(partitioned_data),reduce_chunksize):
pd = partitioned_data[i:i+reduce_chunksize]
reduce_jobs.append(slf.js.submit(forfunc,(slf.reduce_func,pd),(slf.reduce_func,)) )
slf.js.print_stats()
reduced_values=[j() for j in reduce_jobs]
return [o for o in itertools.chain(*reduced_values)]
コードをややこしくしているのは、chunksizeの存在。parallel python には、multiprocessing のmap関数のようなものがないようなので、chunksizeでリストを分割し、forfuncというリストを繰り返し実行する関数を介して、それぞれのmapfunc/reducefuncにアクセスするようにしている。# もともとのSimpleMapReduceでは、reduce処理のchunksizeは指定していなかったが、これを追加している。
実行の仕方は、multiprocessing_wordcountの以下の部分を書き換える。
# 上記のファイルをpp_mapreduce.pyとしたので
from pp_mapreduce import SimpleMapReduceServer
～
def file_to_words(filename):
# サーバ間でプロセス実行するために 関数内でmoduleをインポートする
import multiprocessing
import string
～
# 実際のアクセス方法は、以下のとおり
ppservers=("192.168.1.1:60000","192.168.1.2:60000","192.168.1.3:60000")
mapper = SimpleMapReduceServer( ppservers )
mapper.SetMapReduce(file_to_words,count_words)
word_counts = mapper(input_files)
これで実行すると、(kvm上の各ノード192.168.1.1～3で事前にppserver.pyを実行しておいた)
Job execution statistics:
job count | % of all jobs | job time sum | time per job | job server
3 | 0.78 | 0.4296 | 0.143188 | 192.168.1.2:60000
30 | 7.81 | 0.3886 | 0.012954 | 192.168.1.1:60000
340 | 88.54 | 2.9437 | 0.008658 | local
11 | 2.86 | 0.3927 | 0.035704 | 192.168.1.3:60000
Time elapsed since server creation 2.09296107292
0 active tasks, 3 cores
成功！！(slf.js.print_stats()のところの出力。実行結果などは省略)
(parallel python は、CPU負荷を見てロードバランスしタスクプロセスを振り分けているらしいが、仮想kvmを使っているせいか、localの分量が多くなってしまった。。。)
これで、hdfsみたいな分散ファイルと、racawarenessみたいなタスク分散スケジューラが実装できれば、pythonでhadoop(hadoopy??)みたいなことできるんじゃないか!!
Category Theory for scientists(David spivak) メモ ... グラフとPre順序
前回に続いて、圏の例としてグラフとPre順序を簡単に説明する。
まずグラフとは、有向グラフのことである。
Definition 3.3.1.1.
グラフ $G$は、次の $ (V , A , src , tgt ) $ 4つ組で、以下の条件が成り立つものである。
- $V$は集合で、$G$の頂点の集合とよぶ。
- $A$は集合で、$G$の矢印の集合である。
- $src$は$ A \to V $の関数で、$G$のソース関数と呼ぶ。
- $tgt$は$ A \to V $の関数で、$G$のターゲット関数と呼ぶ。
ある矢印$a \in A$ を与えると、$src(a)$は$a$のソースの頂点と呼び、$tgt(a)$は$a$のターゲットの頂点と呼ぶ。要するに、有向グラフの矢印の元が$src(a)$で、先が$tgt(a)$でよろしい。
これによって定義されるグラフにはいろいろなものがあるが、わかりやすいものとして自然数$n$で定義されているものである。
$n \in \textrm{N} $で $[n]$とは、\[ 0 \to 1 \to 2 \to \dots \to n \]と書けるグラフで、"長さnのチェーングラフ"と呼ぶ。
※このあたり、$[n]$の表現はものの本によってことなるっぽい。
グラフにはPathというものが定義できて、これが今後の圏論を検討するうえで重要となる。
Definition 3.3.2.1.
グラフを $G = (V,A,src,tgt)$とする。グラフの長さnのパスとは、$ p \in {\textrm{Path}}^{(n)}_G $ と書き、G上の矢印の次のようなシーケンスである。
\[ p= ( v_0 \xrightarrow{a_1} v_1 \xrightarrow{a_2} v_2 \xrightarrow{a_3} \dots \xrightarrow{a_n} v_n) \]
特に、標準的な同型として、$ {\textrm{Path}}^{(0)}_G \simeq A $ と、$ {\textrm{Path}}^{(0)}_G \simeq V $ がある。$G$上のPathをすべて集めた集合を ${\textrm{Path}}_G$とすると、
\[ {\textrm{Path}}_g := \bigcup_{n \in \textrm{N}} {\textrm{Path}}^{(n)}_G \]
と書ける。
グラフとグラフを比較すると、そこに準同型写像(homomorphism)が見出せる。これは、monoidの場合と同じように、構造を保存した状態で、それぞれの要素の写像を考えたものである。
Definition 3.3.3.1
$G=(V,A<src,tgt) , G'=(V',A',src',tgt')$がグラフとする。グラフのGからG'への準同型写像(homomorphism)は、$f:G \to G'$とかき、次の２つの可換図を満足する2つの関数、$f_0:V \to V' $ と、$f_1:A \to A' $である。
$$ \begin{array}{cccccc} A & \xrightarrow{f_1} & A' & \qquad & A & \xrightarrow{f_1} & A' \\ {\scriptsize src} \downarrow \quad & & \quad \downarrow {\scriptsize src'} & \qquad & {\scriptsize tgt} \downarrow & & \downarrow {\scriptsize tgt'} \\ V & \xrightarrow{f_0} & V & \qquad & V & \xrightarrow{f_0} & V \end{array}' $$
それぞれの矢印のソース関数、ターゲット関数が、準同型写像に関して一致していればよいことになる。
次に、順序集合について整理しておく。
順序集合は、Pre順序(preorder) 、半順序(partial order) , 全順序(linear order) の3種類が存在してそれぞれの定義は以下のとおり。※この日本語訳も結構いろいろある。
Definition 3.4.1.1.
$S$が集合で $ R \subseteq S \times S $ は、Sの二項関係とする。$(s,s') \in R$ であれば、$s \le s' $ と書けるとして、 $R$がPre順序(preorder)とは、すべての$s,s',s'' \in S$ において、次の2つが満たされることである。
Reflexivity: $ s \le s $
Transitivity: もし、$ s \le s' $ で、$ s' \le s'' $ なら、$ s \le s'' $
$R$が半順序(partial order) であるとは、上記のPre順序(preorder)の条件に加えて、すべての$s,s' \in S $ で次が成り立つことである。
Antisymmetry: もし、$ s \le s' $ かつ $ s' \le s $ なら、$ s=s' $
$R$が全順序(linear order) であるとは、上記の半順序(partial order)の条件に加えて、すべての$s,s' \in S $ で次が成り立つことである。
Comparability: s,s'について、$ s \le s' $ か、$ s' \le s$どちらか一方(もしくは両方)が成り立つ。
いずれの場合も、部分集合を $ (S , \le)$ と記述する。
Pre順序はたとえば、集合と集合の二項関係を、$ X \subseteq Y $ を $ X \le Y $とすれば、これは、Pre順序となる。
で、先に説明したグラフから、Pre順序の構造を見出すことができる。$\textrm{Path}$関数を使って、$ v,v' \in G $においてPathが存在すれば、$ v \le v' $ とおくことで、$(V , \le) $ は、Pre順序となる。
※あと、meet(最大下限=and)とjoin(最小上限=or)という概念を説明している。ちなみに、meetとjoinが唯一存在して演算として定義できれば、束構造(lattice)ということになる。
最後に、順序集合についても、準同型写像(homomorphism)が定義できる。
Definition 3.4.4.1
$S:=(S , \le)$と$S':=(S',\le')$ がPre順序(preorder)とする。preorderの準同型写像とは、$S$から、$S'$への関数 $f$で、$f:S \to S' $ と表し、すべてのペア要素 $ s_1,s_2 \in S $ で、もし、 $ s_1 \le s_2 $なら、$f(s_1) \le' f(s_2) $が成り立つ関数である。
グラフやモノイドのときと同じように、Pre順序も構造を保存しながらの写像が準同型写像(homomorphism)であるとわかる。
さて、Monoidのときと同じように、グラフやPre順序も、それぞれをobjectとした、圏が構成できる。
グラフは、いろいろなグラフを圏のobjectとしてとり、グラフの準同型写像を圏の射とした圏を、$\textrm{Grph} $ とかく。
Pre順序は、いろいろなPre順序集合を圏のobjectとしてとり、Pre順序の準同型写像を圏の射とした圏を、$\textrm{PrO} $ とかく。
aprioriアルゴリズム(2)
前回のaprioriアルゴリズムについて。
このアルゴリズムの肝は、調査する頻度の最低値を決めておいて、"あらかじめこの最低値より頻度が少ないとわかる組み合わせを、N+1組の計算をするときに、N組の計算結果から調べて削除する"ことであり、これがapriori_gen関数であった。
具体的に言うと、アイテムの集合 $I$があったときに、その部分集合 $ X,Y \subseteq I $ の組み合わせが発生する頻度を $ \textrm{Supp}(X) , \textrm{Supp}(Y) $ と書くとすると、
\[ X \subseteq Y \longrightarrow \textrm{Supp}(Y) < \textrm{Supp}(X) \]
という関係が成り立つことを、利用している。
$ X $ が調査する頻度の最低値$min\_support$を下回っていたことがわかれば、$ \textrm{Supp}(X) < min\_support $ であり、 $ X \subseteq Y $ なら、$ \textrm{Supp}(Y) < min\_support $ となることがわかので、$Y$の頻度は計算しなくてもよい。
- $Y$の組み合わせで、$X$が部分集合として含まれるものは調査に除外してよい。
逆に言うと、頻度最低値$min\_support$を超える集合を部分集合として含むものであれば、調査する必要が発生する。
例のプログラムでは、N組の組み合わせの集合 に A．同じN組の組み合わせ集合か、B. 1組の組み合わせの集合(頻度の少ないものは除外済み) のどちらかを掛け合わせて、集合として、N+1組になるものを計算しているが、実は、この方法では、1.で示した除外してよい組み合わせが、含まれてしまう可能性がある。
仮に、N組の組み合わせが、以下だったとしたとき、
\[ X_N = \{ item_1,item_2, ... , item_N \} \ \]
和集合の確認をして、N+1組の組み合わせが、
\[ Y_{N+1} = \{ item_1,item_2, ... , item_N , item_{N+1} \} \]
となったとする。
$X_N$ が最小頻度以上の想定なので、$Y_{N+1}$ も最小頻度以上の可能性はある。しかし、今の例のアルゴリズムでは、追加となった$item_{N+1}$を含んだ部分集合が、N組以下の組み合わせの計算時に最小頻度以下として除外された集合の可能性は否定できない。
これを単純に確認する方法としては、事前に最小頻度の組み合わせとして除外された組み合わせを保持しておいて、N組組み合わせ生成の際に、それらの部分集合が含まれていないかチェックする方法であろう。
def apriori_gen(flst,ex_f,items_list):
if len(flst)<items_list:addlst=flst
else:addlst=items_list
tmp=[ ]
for i in flst:
for j in addlst:
n=len(i)
f=set(i).union(set(j))
if len(f)==n+1 and f not in tmp:
if [1 for l in ex_f if set(l) in f]==[ ]:
tmp.append(f)
return [ list(t) for t in tmp ]
def apriori_func(idata,tran_num,f,min_support,max_k):
sol=[ ]
ex_f=[ ]
k=1
while f!=[ ]:
n_f=[ ]
print "f[%d]=%d" % (k,len(f))
for x in f:
isum,usum = support_func(tran_num,idata,x)
sup=1.0*isum/tran_num
if sup >= min_support:
sol.append([ x,sup,(isum,usum) ])
n_f.append(x)
else:
ex_f.append(x)
if k==1:f1=n_f[:]
if max_k <= k: break
f=apriori_gen(n_f,ex_f,f1)
k+=1
return sol
ex_fを使って除外する集合をチェックする。
しかし、この方法も微妙で、除外する組み合わせが多くなればなるほど、apriori_genのチェックに非常に時間を要してしまう。
こういった問題を回避できるのが、もっと別の方法のアルゴリズムとして、FP-Treeアルゴリズムである。集合の頻度の高いもの順に組み合わせを木構造化することで、こういった組み合わせ検索の問題が回避されている。(もちろんメモリを使うことになるのだが)
このアルゴリズムの実装についてはまた今度。
apriori アルゴリズム
ちょっとあまりに稚拙だが、
相関性分析におけるaprioriアルゴリズムをpythonで書いたので、書き残す。
#!/usr/bin/env python
items=['beer','nuts','cheese','jam','butter']
testdata=[ ['beer','nuts','cheese'],
['beer','nuts','jam'],
['beer','butter'],
['nuts','cheese'],
['beer','nuts','cheese','jam'],
['butter'],
['beer','nuts','jam','butter'],
['jam'] ]
def apriori_gen(flst,items_list):
if len(flst)<items_list:addlst=flst
else:addlst=items_list
tmp=[]
for i in flst:
for j in addlst:
n=len(i)
f=set(i).union(set(j))
if len(f)==n+1 and f not in tmp:
tmp.append(f)
return [ list(t) for t in tmp]
def support_func(num,idata,xlst):
isum,usum=set(range(num)),set()
for x in xlst:
if x in idata:
isum=isum.intersection(set(idata[x]))
usum=usum.union(set(idata[x]))
lisum,lusum=len(isum),len(usum)
if lusum==0:lisum=0
return lisum,lusum
def create_idata(testdata):
idata={}
num=len(testdata)
for i in items:
for j in range(num):
if i in testdata[j]:
if idata.has_key(i):
idata[i].append(j)
else:
idata[i]=[j]
return idata,num
def apriori_func(idata,tran_num,f,min_support,max_k):
sol=[]
k=1
while f!=[]:
n_f=[]
print "f[%d]=%d" % (k,len(f))
for x in f:
isum,usum = support_func(tran_num,idata,x)
sup=1.0*isum/tran_num
if sup >= min_support:
sol.append([ x,sup,(isum,usum) ])
n_f.append(x)
if k==1:f1=n_f[:]
if max_k<=k: break
f=apriori_gen(n_f,f1)
k+=1
return sol
def apriori(testdata,items,min_support,max_k):
idata,tran_num = create_idata(testdata)
f=[ [i] for i in items]
return apriori_func(idata,tran_num,f,min_support,max_k)
sol=apriori(testdata,items,3.0/8.0,4)
print solaprioriアルゴリズムは、アイテムの組み合わせにおける頻度を計算するもの。
たとえば購買のトランザクションデータがあったときに、どの商品の組み合わせを一緒に購入しているのか？の分析ができる。データ分析における相関分析(アソシエーション分析)と呼ばれるもののベースの情報を提供する。
例のプログラムの場合、itemsが各商品である。testdataの一行ごとが各購入のトランザクションデータとみなされる。
普通に各商品の相関分析をしようとした場合、(商品 x 商品)の組み合わせを全トランザクションで試して、同じトランザクションに現れる頻度を計算すればよい。(商品 x 商品)だから 商品数^2を試すことになる。
ところが、これだけでは分析としては物足りなくて、(商品 x 商品 x 商品)の３組の組み合わせ、(商品 x 商品 x 商品 x 商品)の４組の組み合わせ、のようにN組分の商品の組み合わせに対しても相関を分析したい。しかし、これでは商品数^Nの分だけ全トランザクションでの頻度を調べることになる。計算量が莫大だ。
これを効率よく分析するのが、aprioriアルゴリズム。
具体的には、上記プログラム、min_supportのように頻度を調べる最低値を決めておく。で、N+1組の組み合わせを調べる前に、あらかじめこの最低値より頻度が少ないとわかる組み合わせを、N組の計算結果から調べて削除する、というのがアルゴリズムのあらましである。
具体的な実装としては、以下となる。
- アイテムN組の組み合わせ(apiori_func関数のf)の頻度を調べる
- 頻度の結果から最低値min_supportより大きくなった組み合わせを次の組み合わせの候補(apriori関数のn_f)とする。(min_supportより小さくなった組み合わせは、それ以上、別のアイテムが増えて頻度が増えることはないため、最低値min_supportより頻度が少ないとして削除できる。)
- 次の組み合わせ候補(n_f)から、N+1組の組み合わせを生成(apriori_gen関数)する。N+1組の組み合わせで調べるべきは、2.で作成した候補が含まれる組み合わせであることから、N組の組み合わせから和集合を探して、N+1組(cardinarity=N+1)になればよい。(和集合の探す当ては、ソースのように、アイテム(これは1組の組み合わせ)か自分自身(N組の組み合わせ)として、ループ回数を減らすしている。)
- これを次の組み合わせ候補がなくなるまで繰り返す。
文で書くと結構ややこしい。
プログラムでは、ソースを簡単にするために、いったん、testdataをアイテムからトランザクション種類を引ける辞書型(idata)に変換している。(create_idata関数)
これを使って、それぞれのアイテムから引いたトランザクションのリストを集合として積をとれば、各アイテムの組み合わせの頻度がわかる。(support_func関数。ついでに和集合もとっている)
パラメータとして、組み合わせ数の上限(max_k)を決めて、調整できるようにしておく。
例のitems,testdataの例で言うと、2組の組み合わせ(商品 x 商品)では、
>>> for i in sorted([l for l in sol if len(l[0])==2 and l[1]<3.0/8.0],key=lambda x:x[1],reverse=True):print i[0],i[1] ... ['cheese', 'beer'] 0.25 ['butter', 'beer'] 0.25 ['butter', 'nuts'] 0.125 ['cheese', 'jam'] 0.125 ['butter', 'jam'] 0.125 ['butter', 'cheese'] 0.0
が次の候補に外れて、
>>> for i in sorted([l for l in sol if len(l[0])==2 and l[1]>=3.0/8.0],key=lambda x:x[1],reverse=True):print i[0],i[1] ... ['beer', 'nuts'] 0.5 ['beer', 'jam'] 0.375 ['cheese', 'nuts'] 0.375 ['jam', 'nuts'] 0.375
を含む組み合わせが、3組の組み合わせ(商品 x 商品 x 商品)の調べる候補となる。3組の商品組み合わせで調べているのは、これだけ。
>>> for i in sorted([l for l in sol if len(l[0])==3 ],key=lambda x:x[1],reverse=True):print i[0],i[1] ... ['beer', 'jam', 'nuts'] 0.375 ['cheese', 'beer', 'nuts'] 0.25 ['cheese', 'jam', 'nuts'] 0.125
ちなみに、相関ルール分析としては、次のような原因と結果ルールを導くのが目的なので、
- 「AならばBである(A → B)」
- 「AかつCならばBである(A,C → B)」
上記で計算した頻度( = 支持度)のほかに条件付確率( = 信頼度)とか、リフト値(信頼度 / Pr(結果))を計算して各確率を考量する必要がある。
- 支持度 ... Pr(A,B) や Pr(A,B,C)
- 信頼度 ... Pr(B|A)=Pr(A,B)/Pr(A) や Pr(B|(A,C)) = Pr(A,B,C)/Pr(A,C)
- リフト値 ... Pr(B|A)/Pr(B) や Pr(B|(A,C))/Pr(B)
いずれも、aprioriアルゴリズムで算出した結果を組み合わせて計算できる。
Category Theory for scientists(David spivak) メモ ... Monoidについて
圏の定義をした後、圏の例として集合の圏$\textrm{Set}$やモノイドの圏$\textrm{Mon}$の説明があるのだが、ここでは、モノイドについて説明する。
※CT4Sでは、事前に集合の圏論的な話をやって(Chapter2)、次にモノイドや群、プレ順序やグラフなどの説明(Chapter3)をした後に、圏の定義をしているため、すんなり説明が理解できるようになっている。
definition 3.1.1.1
モノイドとは、次の三つ組$(M,e,*)$で定義されるもので、$M$は、集合であり、$e$は、Mのある一つの要素$e \in M$であり、$*$は、$*:M \times M \to M$ の関数である。それぞれは、次を満たす。ただし、$ m,n,p \in M$。
- $ m * e = m $
- $ e * m = m $
- $ ( m * n ) * p = m * ( n * p ) $
eは単位元で、三番目の条件はmultiplication formulaである。
これで、$*$に逆元 $ m * m' = e$ なる$m' \in M$が存在すると群になる。さらに別の演算子$+$が定義できて分配則を満たすと環になり、さらに体になり...と数学の代数における基本的な構造の、もっとも基本的なところにmonoidはある。
モノイドの例としては、$(\mathbb{N} , 0 , + )$ とか、$(\mathbb{N} , 1 , \times )$とか。さらに、適当な集合$M$を用意して、自由モノイドというのを造ることができる。
Definition 3.1.1.15
Xを集合として、"Xによって生成された自由モノイド"とは、$ M=( \textrm{List}(X) , [ ] , ++ ) $ である。ここで、$\textrm{List}(X) $ とは、たとえば、$X={a,b,c}$ だとすると $[a,b,a,b,c,a,b,b]$ みたいな$X$の要素を用いて作った文字の並びリストのこと。$[ ]$は、空のListで$++$の演算子は、リストのコンカチを表わす。たとえばこんな感じ
\[ [a,b,a,b,c,a,b,b] ++ [a,b,c] \to [a,b,a,b,c,a,b,b,a,b,c] \]
Listはいろんなパターンが無限に続けられるが、これをすべて、モノイドの要素として考えてしまうのが自由monoidである。ここで、集合$X$をmonoid $ M$ の生成子(generators)と呼ぶ。
自由モノイドにおいて、$List(X)$の要素 $ m , m' \in \textrm{List}(X)$ を、"同値として定義することを考えらることができる。たとえば、
\[ [ a,b,a,b,c] \sim [ c,a] \]
なんていう定義を、自由モノイドの中に組み込んでおくと、先のListは、$ [a,b,a,b,c,a,b,b] = [c,a,a,b,b] $ と変換できて、これを$\textrm{List}(X)$において、同一の要素として定義することができる。これを"Presented monoid"という。
Definition 3.1.1.17
有限な集合$G$、nを自然数$ n \in \mathbb{N} $ とし、$m,m'$は、$\textrm{List}(G)$の要素$ m,m' \in \textrm{List}(G) $ で、 $i$を$ 1 \le i \le n $ とする。”生成子Gと関係$ \{ (m_i,m'_i) | 1 \le i \le n \}$ によって提示される(presented)モノイド”とは、次のように定義される。$ \sim$ を$\textrm{List}(G)$上の同値関係として $ \{ ( xm_iy \sim x m'_i y ) | x,y \in \textrm{LIst}(G),1 \le i \le n \} $ と定義し、 $ M = \textrm{List}(G)/\sim $と定義された自由モノイドである。
そんなにややこしい話ではない。たとえば$ ( \mathbb{N} , 0 , + ) $ 足し算のmonoidにおいては、$ 1 + 2 = 1 + 1 + 1 = 3 $のように、$1+2$と$1+1+1$は同値関係である。前述した定義が成り立つ構造のものならばmonoidであるから、monoidはいろいろなもの考えられるが、同値関係によってmonoidの構造の特徴が表せると考えられる。
次に、monoid 作用というものがある。
Definition 3.1.2.1
monoidを$(M,e,*)$として、 $S$を集合とする。"S上の$(M,e,*)$による作用"とは、次のような関数のこと：
\[ \circlearrowleft : M \times S \to S \]
これは、$ m,n \in M$ と$s \in S$において、次の条件が成り立つ。
- $ e \circlearrowleft s = s $
- $ m \circlearrowleft ( m \circlearrowleft s ) = ( m * n ) \circlearrowleft s $
$s \in S$という状態に対して、monoidの要素を"操作”と考えて、$s$がその操作によって次の状態$s'$へ遷移することが表現できる。つまりこれによって、決定性の有限状態機械、オートマトンを表現できるのである。
オートマトンの状態遷移図は、表によって記述することもできる。たとえば、モノイドを$G={a,b}$で生成される自由モノイドで、状態$S$を$S=\{状態0,状態1,状態2\}$とかけるとする。
| ID | a | b |
|---|---|---|
| 状態0 | 状態1 | 状態2 |
| 状態1 | 状態2 | 状態1 |
| 状態2 | 状態0 | 状態0 |
この表は、IDの状態が a or b のモノイド作用によってそれぞれの行の状態に遷移する、ということを表現している。たとえば、状態0の場合で、操作がaの場合は状態1、bの場合は状態2、(表の2列目)というふうに。
最後に、monoidのhomomorphismについて：
Definition 3.1.4.1
$\textit{M}:=(M,e,*) $ と$\textit{M'}:=(M',e',*')$をモノイドとしたとき、"$\textit{M}$から$\textit{M'}$へのモノイドの準同型写像"(monoid homomorphism)とは、$ f：\textit{M} \to \textit{M'} $ と書ける関数で、モノイドの要素に対しての関数 $ f:= M \to M' $ であり、次の条件を満足するもの。
- $ f(e) = e' $で
- $ f(m_1 * m_2) = f(m_1) *' f(m_2) for all m_1,m_2 \in M
つまりいろいろなモノイドについての写像が定義できるということである。
集合の圏$\textrm{Set}$が、いろいろな集合をobjectとし、集合の写像を圏の射として定義できたのと同様に、monoidについても、いろいろなモノイドをobjectとして、monoidの写像を圏の写像とみなして圏を構成することができる。これをmonoid圏$\textrm{Mon}$とかく。
Category Theory for scientists(David spivak) メモ ... 圏の定義
圏について（CT4S 4.1.1)
カテゴリ(圏)は、モノの集まり(collection)とそれらの関係について表したものだ。数学では、モノの集まり(collection)とそれらのpairの間の関係の型として解釈される。モノの関係性のたぐいを圏論として考えるとき、二つのルールをチェックする必要がある。それは、単純にいうと次のようなものである：「1.すべてのモノは、単純に自分自身と関係していて、2.もし、ある一つが他と関係していて、二つ目が三つ目と関係しているなら、一つ目は三つ目とも関係を持つ、ということである。」圏論においては、"モノ"をobjectsと呼び、"関係性"をmorphismと呼ぶ。
Definition 4.1.1.1.
圏 $C$ は次のように定義する。以下のような成分(A.objects , B.morphisms , C.identities , D.compositions)を持っていて、これらは、1～2の法則が成り立つ。
A. collections $Ob(C)$ は、objectsと呼ばれる要素である。
B.すべてのペア $ x,y \in Ob(C) $ は、集合 $ \textrm{Hom}_{C}(x,y) \in \textrm{Set} $とかく。xからyへのHom集合と呼ぶ。この要素は、xからyへのmorphism(写像)である。
C.すべてのオブジェクト $ x \in Ob(C) $ には、特別なmorphism $ \textrm{id}_x \in \textrm{Hom}_C(x,x) $ が存在する。これをxのidentity morphismと呼ぶ。
D.すべての三つのオブジェクト $ x,y,z \in Ob(C) $は、関数、
\[ \circ : \textrm{Hom}_C(y,z) \times \textrm{Hom}_C(x,y) \to \textrm{Hom}_C(x,z) \]
これを、合成則と呼ぶ。
$ x,y \in Ob(C) $ が与えられたら、morphism $ f \in \textrm{Hom}_C(x,y) $ が $ f: x \to y $ で定義できて、xをfのdomain、yをfのcodomainと呼ぶ。さらに、 $ g: y \to z $ が与えられたら、 合成則によって $ g \circ f : x \to z $ は、 $ \circ (g,f) \in \textrm{Hom}_C(x,z) $ と書ける。
1～2の法則は以下である。
1.すべての $ x,y \in Ob(C) $ では、すべてのmorphism $ f: x \to y $ で次が成り立つ。
\[ f \circ \textrm{id}_x = f かつ \textrm{id}_y \circ f = f \]
2. どの$ w,x,y,z \in Ob(C) $であっても、$ f: w \to x , g:x \to y , h:y \to z $ のmorphismにたいして、次の2つの合成は同じである。
\[(h \circ g) \circ f = h \circ ( g \circ f) \in \textrm{Hom}_C(w,z) \]
この後、$Ob(C)$を集合と呼ばずに、"collection"と読んでいる点についてを説明している。"すべての集合の圏"=集合圏$\textrm{Set}$を扱うことがあるためであり、圏のobjectを"set"と呼んでしまうと”ラッセルのパラドクス”に陥ってしまうのだそうな。これを回避するために、"universe"という馬鹿でかい集合"$\kappa$"を定義するのだけれど、ここでは扱わない。これは数学的には厳密な定義を与える意味で重大なことで、マクレーンの本やそのほか圏論の資料にも説明があるのだが、spivakさんはラフな説明でほぼスルー。数学者ではなく、応用を考える科学者に対しては、ここで説明する必要はなかろうとのこと。
圏の定義については、単純に有向グラフに、idと合成則がついたもの、という感覚を持って理解している。有向グラフで考えた場合のidの法則は、"同じ頂点への矢印が必ず入る"という制限が入るという意味となる。また、合成則の場合は、たとえば頂点 $ a,b,c $ があった場合、$ a \to b $と$ b \to c $の矢印があったら、$ a \to c $ という矢印も、"存在なければならない"という意味になる。この点で圏と有向グラフは異なる。(このあたり、spivakさんの教科書にもあるようにグラフのパスをmorphismとした$ \textrm{Path}$ が、僕の理解に重なる。)
あと一点、有向グラフのイメージするときに注意しなければなければならないのは、有向グラフの頂点における"要素"は一つとは限らない、ということ。集合圏"$\textrm{Set}$"の場合は、$Ob(\textrm{Set})$は集合そのもので、$\textrm{Hom}_{\textrm{Set}}(x,y)$は、xからyへの集合の写像である。(このあたりはspivakさんのChapter2である)有向グラフの頂点に該当するのは集合で、その要素としては一つとは限らない。(もちろん圏によっては要素が一つということもありうるのだが)
ecaについて
ecaとは
ecaとは... wikiではあいまい回避で結構いろいろな定義がリストされるが、ここで話したいのは、elementary cellar automaton ... 一次元セルオートマトンのこと。
細かい話は、wikiを参照.。
セルオートマトンのプログラムを書いてみた。
#!/usr/bin/env python class eca: def __init__(slf,rule,N): slf.rule=rule slf.N=N slf.i=0 slf.status=[ [ 0 for i in range(slf.N)] for j in range(2)] def next_func(slf,l,s,r): d=int("%s%s%s" % (l,s,r),2) return (slf.rule >> d ) % 2 def next_id(slf): if slf.i==0:return 1 else:return 0 def next(slf): s=slf.status[slf.i] t=slf.status[slf.next_id()] for i in range(slf.N): t[i]=slf.next_func(s[i-1 % slf.N],s[i],s[(i+1) % slf.N]) slf.i=slf.next_id() return slf.prnt() def prnt(slf): def char_prnt(c): if c==1:return "+" else:return " " return "".join([char_prnt(i) for i in slf.status[slf.i] ]) def set_status(slf,i,s): slf.status[slf.i][i]=s def get_status(slf,i): return slf.status[slf.i][i] if __name__=="__main__": d=eca(110,50) d.set_status(25,1) for j in range(130): print d.next()
で、これだけでは面白くないので、深さ優先探索で一次セルオートマトンの逆に推移するプログラムを書いてみた。
#!/usr/bin/env python import eca class inverse_eca: def __init__(slf,rule,N): slf.rule=rule slf.N=N slf.i=0 slf.status=[ [ 0 for i in range(slf.N)] for j in range(2)] slf.tlst=[[] for i in range(2)] for i in range(8): slf.tlst[(slf.rule >> i) % 2].append("%03d" % int(format(i,'b'))) def inverse_func(slf,s,k): tmp=[ i for i in slf.tlst[s] ] return [ [int(i[0]),int(i[2])] for i in tmp if int(i[1])==k] def next_id(slf): if slf.i==0:return 1 else:return 0 def next(slf): s=slf.status[slf.i] t=slf.status[slf.next_id()] tmp=[[0,1] for i in range(slf.N)] def recur_func(p_lst,i,k): if not k in p_lst[i]:return False idec,iinc= (i-1) % slf.N,(i+1) % slf.N n_tset=slf.inverse_func(s[i],k) for nt in n_tset: if nt[0] in p_lst[idec] and nt[1] in p_lst[iinc]: if len(p_lst[i])==1 and len(p_lst[idec])==1 and len(p_lst[iinc])==1: return True save_idec ,save_i = p_lst[idec],p_lst[i] p_lst[idec],p_lst[i] = [nt[0]],[k] if recur_func(p_lst,iinc,nt[1]): return True p_lst[idec],p_lst[i] = save_idec,save_i return False if not recur_func(tmp,0,0) and not recur_func(tmp,0,1): print "Falt!!!! " return slf.prnt() for i in range(slf.N):t[i]=tmp[i][0] slf.i=slf.next_id() return slf.prnt() def prnt(slf): def char_prnt(c): if c==1:return "*" else:return " " return "".join([char_prnt(i) for i in slf.status[slf.i] ]) def set_status(slf,i,s): slf.status[slf.i][i]=s def get_status(slf,i): return slf.status[slf.i][i] def set_statusstr(slf,str): i=0 for s in str: if s=='*':slf.status[slf.i][i]=1 else:slf.status[slf.i][i]=0 i+=1 if __name__=="__main__": rule=90 N=50 init_N=int(N/2) def trans(obj,tn): for i in range(tn):print "%2d,%s|" %(i,obj.next()) def eca_copy(obj,obj2): for i in range(obj.N):obj2.set_status(i,obj.get_status(i)) d=eca.eca(rule,N) e=inverse_eca(rule,N) d.set_status(init_N,1) print "%2d,%s|" %(0,d.prnt()) trans(d,30) eca_copy(d,e) trans(e,5)
後者は、全体のセルの状態に対して非決定性オートマトンの実装にはなっていないので、推移先(通常のセルオートマトンにおいての推移元)の状態がなければ停止します。
覚書でした。
Category Theory for scientists(David spivak) を読む
圏論とリレーショナルデータベースの融合。これはおもしろい。
David Spivakさんは、MITでCategorical informaticsなる話を研究されている数学者。
Spivakさんのこの研究内容は、データベースエンジニアとしても無視できない技術内容ということで、論文をいくつか参照していたのだが、圏論を詳しく理解していなかったため、なかなか骨が折れて挫折しかけていた。圏論自体は1年ほど前から少し興味を持っていたのだが、どうも埒が明かないでいた。そこで、教科書的な表題の資料を読み進めて、データベースとの関係がうっすらと見えてきたように思う。
RDBMSのスキーマの概念は、"圏"と一対一対応だったとは。
さらに、DMLやDDLが、スキーマを圏とした場合の関手の自然変換だったとは。
まだまだ完全に理解したわけではないし、この本は入門編で圏論のお話も序の序だと思う。再読しながら他の論文をあさろうという気になってきた。
※最近流行の列指向データベースは、RDBMSがスキーマ圏と集合圏への関手という構造であることを考えると、実はかなりしっくりとしたRDBMSとしてのアーキテクチャのように思われる。
