順序数の導入例

集合による「自然数」の定義

公理的集合論では、「集合」の概念を基礎として数学を構築することを目指しており、「自然数」の概念すらも集合を使って定義しようと試みます。もう少し柔らかく言うと、集合を使って、自然数の「代替品」となるものを用意できないかと考えます。

たとえば、何も無いことを表す空集合 $\phi$ を「0」の代替品として定義します。

　 $0 :=\phi$

次に、1 以上の数をどう定義するかですが、自然数には、大きさ順に一列に並べられる（固く言うなら、整列順序関係を持っている）という性質があるので、

・「n より小さい数（の代替品となる集合）を集めた集合」を「n」の代替品とする

というアイデアが考えられます。具体的に言うならば、1 の代替品は次になります。

　 $1 := \{0\} = \{\phi\}$

これは、「空集合を唯一の要素とする集合」であり、空集合そのものとは区別される点に注意してください。そして、2、3…の代替品は次になります。

　 $2 := \{0, 1\} = \{\phi,\{\phi\}\}$

　 $3 := \{0, 1, 2\} = \{\phi,\{\phi\},\{\phi,\{\phi\} \}\}$

　　 $\vdots$

最右辺を見ていると目がチラチラしてきますが、その1つ前の書き方を見ればアイデアは明確だと思います。ちなみに、この定義を用いれば、自然数の大小関係は、次のように定義することができます。

　 $n < m \ \Leftrightarrow\ n\in m$ --- (1-1)

これで任意の自然数 n に対して「n の代替品となる集合」が定義できましたが、これ以降は、これらの集合を「n を表す集合」と短く言い換えることにします。

そして、上記の定義は、帰納的に考えることもできます。すなわち、

・n を表す集合に対して、n 自身を要素として付け加えたものが、n+1 を表す集合になる

という性質があるので、次のように定義する事も可能です。

　 $0 := \phi$

　 $n+1 := n \cup \{n\}\ (n=0,1,\cdots)$ --- (1-2)

「n を表す集合」の性質（推移性）

前述の (1-2) をよく吟味すると、

・n は n+1 の要素であり、かつ、n+1 の部分集合でもある

というちょっと奇妙な性質が生まれることに気が付きます。

実際、 $n \cup \{n\}$ の左側を見ると、n は n+1 の部分集合であることがわかります。一方、右側を見ると、n は n+1 の要素としても含まれています。つまり、

　 $n\in n+1$

　 $n\subset n+1$

が同時に成り立つという、集合論ならではの奇妙な関係が成り立ちます。（型付けされたプログラミング言語では、とても表しようの無い世界ですね・・・）

特に部分集合の関係を帰納的に用いると、

　 $0 \subset 1 \subset 2 \subset\cdots$

となっており、自然数の大小関係が集合の包含関係に対応することがわかります。

　 $n < m \ \Rightarrow\ n\subset m$

元々のアイデアでは、自然数の大小関係は (1-1) で定義されていたので、次の公式が成り立ちます。

　 $n\in m\ \Rightarrow\ n\subset m$ --- (2-1)

ちょっとした言葉遊びですが、 $n\in m$ は「n は m の元である」と言えて、 $n\subset m$ は「n の元は m に属する」と言えるので、(2-1) の関係は、「m の元の元は、m に属する」と言うことができますので、(2-1) は、

　 $a \in b \in m\ \Rightarrow\ a \in m$ --- (2-2)

と書き直すことができます。（(2-1) と (2-2) が集合の性質として同値であることは、落ち着いて考えると、厳密に証明することができます。）

再び (1-1) を思い出すと、これは、

　 $a < b < m\ \Rightarrow\ a < m$

ということで、(1-1) で定義した大小関係は、自然数としての大小関係を正しく代替できていることになります。これは「順序数の推移性」と呼ばれるもので、順序数の根幹となる性質であることが追々わかってきます。

順序数の公理的定義

ここまで、自然数の代替物となる集合を作ってきましたが、公理的集合論ではこの代替物を「順序数」と呼びます。そして、本物の自然数の事はわすれて、集合で定義された代替物、すなわち、順序数そのものの性質を調べていくと、おどろくべきことに、順序数は、自然数だけではなくて、自然数をさらに超える「数（のようなもの）」を表現できることがわかります。

この点を正確に説明するために、一旦、自然数のことは忘れて、純粋に集合の言葉だけで順序数を定義しなおします。前述のように、推移性が順序数の根幹となる性質ですので、集合を要素とする集合 m が、

・推移性 (2-1)（もしくは (2-2)）を満たす
・任意の部分集合は、（(1-1) の意味の大小関係で）最小の要素を持つ

という条件を満たす時に、「m は順序数である」と言うことにします。2つ目の条件がちょっとわかりにくいですが、m の任意の 2 つの要素 a, b を取った時に部分集合 $\{a,b\}\subset m$ に最小要素があることから、必ず、 $a < b$ もしくは $b < a$ のどちらかが成り立ちます。つまり、この2つの条件があれば、m のすべての要素は (1-1) の大小関係で一列に並べることができて、さらに、m はそれらすべてよりも大きい数、ということになり、「m は、m より小さい数を集めた集合」という当初のアイデアが綺麗に反映されていることになります。

さらに、

・順序数 m の任意の要素 n は、（(1-1) の意味で）n より小さい要素を集めた m の部分集合に一致する

という関係を上の定義から示すことができます。

実際、n より小さい要素を集めた集合は、 $\{a\in m\mid a\in n\}$ と表せますが、推移性から $n\subset m$ となることを考えると、これは集合 n に一致します。

そして、「n より小さい要素を集めた m の部分集合」は、それ自体が順序数の定義を満たすことも容易にわかります。つまり、前述の定義から、順序数 m は、「m よりも小さい順序数を集めた集合」と言えるのです。

さらに、公理的定義の立場では、(1-2) は、「n の次に大きい順序数」を作り出す手続きと見なすことができます。n 自身が「n よりも小さい順序数の集合」ですので、これに、n 自身を要素として加えたものは、「n 以下の順序数の集合」であり、確かに、「n の次に大きい順序数」となっています。

自然数を超える「数」の存在

公理的に定義した順序数は、当初に考えた「自然数の代替物」としての性質を満たしており、実際、

　 $0 :=\phi$
　 $1 := \{0\} = \{\phi\}$
　 $2 := \{0, 1\} = \{\phi,\{\phi\}\}$
　 $3 := \{0, 1, 2\} = \{\phi,\{\phi\},\{\phi,\{\phi\} \}\}$
　　 $\vdots$

という集合はすべて順序数の定義を満たしており、この意味で、順序数は自然数を含む、ということが言えます。

ただし、重要なポイントは、「順序数に含まれる集合は自然数だけではない」という点にあります。順序数の定義から言える事は、「順序数の要素は、大小関係で一列に整列できる」という事だけであり、言い換えると、順序数は、「大小関係で一列に整列できる集合」一般を表現する「数（のようなもの）」になっているのです。

・・・どういうこと？

具体例を示しましょう。

たとえば、(1-2) によって帰納的に、すべての（順序数としての）自然数 $0, 1, 2,\cdots$ が定義されますが、これらをすべて集めた集合を考えます。

　 $\omega := \{0,1,2\cdots\}$

(1-2) の手続きを繰り返す限りでは、（有限回の操作に止まる限り）永遠に $\omega$ にたどり着くことはできませんが、無限集合として概念的に定義することは可能です。そして、この $\omega$ は順序数の定義を満たしており、任意の自然数 n よりも大きな順序数であることが容易に確認できます。つまり、順序数の世界では、

　 $0<1<2<\cdots<\omega$

という、任意の自然数よりも大きい（直感的に言えば「加算無限大」とも言える）「数」が存在するのです。

さらに、(1-2) の手続きを利用すれば、 $\omega$ の後続の順序数を帰納的に作ることもできて、

　 $0<1<2<\cdots<\omega<\omega+1<\omega+2<\cdots$

という無限列が得られます。

$\omega+1$ や $\omega+2$ が一体どんな「数」なのかと不思議に思うかも知れませんが、前述のように、順序数というのは「大小関係で一列に整列できる集合」を表現するものですので、これは、「集合の要素を一列に並べる方法」に対応すると考えると理解できます。

たとえば、可算無限個の石ころを一列にならべたものは、自然数全体を一列にならべたものと（並べ方として）同一視できますので、 $\omega$ は、このような「並べ方」を表現したものと言えます。

　 $○○○○○○○○\cdots \Leftarrow \omega$

そしてさらに、可算無限個ならべたあとに、さらに、新しい石ころを1つ加えます。これが $\omega+1$ です。

　 $○○○○○○○○\cdots○ \Leftarrow \omega+1$

「無限個の後ろってどこだ？」と思う方は、1列目に無限個並べておいて、次に、2列目に並べ始めると思えばよいでしょう。こんな感じ。

　 $\omega+1$
　 $○○○○○○○○\cdots$
　 $○$

　 $\omega+2$
　 $○○○○○○○○\cdots$
　 $○○$

そして、2列目も無限に並べ切ったものは、 $\omega+\omega$ に対応すると想像できます。さらには、縦横の両方向に無限個ならべた様子を考えたくなりますが、これは、直感的には、 $\omega\times\omega$ に対応するはずです。

このあたりは、あくまでも直感的な議論ですが、順序数に対する演算（足し算、掛け算、冪）を厳密に定義することができて、上記の議論を数学的に正当化することももちろん可能です。

なお、公理的に定義された順序数は「集合の要素を一列に並べる方法」に対応すると言いましたが、順序数そのものにも大小関係が定義されており、順序数全体も一列に並べることができる点も大切です。これにより、「順序数に関する数学的帰納法」を考えることができて、これは一般に「超限帰納法」と呼ばれる証明法になります。

整列順序について

順序数の定義をもう一度見直してみます。

・推移性 (2-1)（もしくは (2-2)）を満たす
・任意の部分集合は、最小の要素を持つ

2つ目の条件から、順序数 m の任意の異なる2要素は比較可能（つまり、 $a < b$ もしくは $a > b$ のどちらかが成り立つ）になり、m の要素を一列に並べることができると説明しました。それでは、なぜ、比較可能性を直接に要求しないのでしょうか？　実は、2つ目の条件は、一般に、「整列順序」と呼ばれる性質で、単に一列に並べられる「全順序」よりも強い性質になっています。つまり、整列順序は全順序になりますが、全順序は必ずしも整列順序にはなりません。

たとえば、整数全体を通常の大小関係で並べた場合、これは一列に並べることが可能な全順序になっていますが、部分集合 $\mathbb Z_- = \{a\mid a<0\}$ には最小要素がなく、これは整列順序にはなっていません。では、自然数のように、集合全体に最小要素があれば十分かというと、そうでもなくて、非負の実数全体は最小要素 0 を持ちますが、開区間を考えると、最小要素がなく、やはり整列順序にはなりません。感覚的言うと、「最小要素から出発して、離散的に一列に並べることができる」のが整列順序ということになります。

したがって、順序数全体というのは、可能な整列順序のすべてを代表した集まりになっており、順序数自体が整列順序になっていることから、

・整列順序の集まりは、（順序数としての大小関係によって）整列順序になる

という定理が成り立つことになります。

と言っておいて・・・順序数自体が整列順序になることは、自明でしょうか？　これは、次のように証明することができます。先に触れた「n は n+1 の要素であり、かつ、n+1 の部分集合である」という順序集合のちょっと病的（？）な性質がうまく効いて来る面白いところなので、丁寧に示してみます。

まず、順序数全体の集まりを ${\rm On}$ と表すとして、 $C$ を ${\rm On}$ の任意の要素を集めたものとします。この時、 $C$ に最小要素があることを示せばよいことになります。

$C$ の任意の1つの要素を $x$ とすると、 $x$ は順序数の1つですので、任意の部分集合に対して、最小要素が存在します。特に、部分集合 $x\cap C$ を考えて、この最小要素を $x_0$ とします。（ $x\cap C=\phi$ の場合は、 $x_0=x$ とします。）この時、 $x_0\in x$ であることから、推移性により、 $x_0\subset x$ となります。

そして、この $x_0$ が $C$ の最小要素であることが言えます。なぜなら、 $C$ の中に $x_0$ より小さい要素 $a$ 、すなわち、 $a\in x_0$ を満たすものがあったとすると、 $a\in x_0\subset x$ 、すなわち、 $a\in x$ であり、さらに、 $a$ は $C$ にも含まれるので、 $a\in x\cap C$ が言えて、 $x_0$ が $x\cap C$ の最小要素であることに矛盾します。（ $x\cap C=\phi$ の場合は、そもそもこの事実に矛盾します。）

なるほどー。

超限帰納法について

・ $C$ を ${\rm On}$ の任意の要素を集めたものとして、 $C$ に最小要素が存在する

という事実を示しましたが、実は、この事実から超限帰納法を「証明」することができます。通常の数学的帰納法は、公理のようなもので、数学的帰納法が成り立つこと自体を証明することは（普通は）ありませんが、超限帰納法はそうではないのです。（順序数には自然数も含まれているので、同じ証明法を適用すれば、通常の数学的帰納法も「証明」できることになりますが。）

論理式を使って超限帰納法を表すと、 $C$ を ${\rm On}$ の任意の要素を集めたもの、順序数 $a$ に対する任意の命題を $F(a)$ として、

　 $[\forall b \in C\, {\rm s.t.}\, b < a;\,F(b)]\ \rightarrow \ F(a)$ --- (3-1)

が成り立つならば、

　 $\forall a \in C;\, F(a)$ --- (3-2)

が成り立つ、と言うことができます。これを証明します。

今、(3-1) が成り立つものとして、(3-2) が成り立たないと仮定します。すると、 $F(a)$ を満たさない $a\in C$ が存在することになるので、そのような $a$ を集めた集合 $N$ を考えると、これは、順序数の集合（ ${\rm On}$ の任意の要素を集めたもの）なので、最小要素が存在します。これを $a_0$ とすると、 $b < a_0$ なる任意の $b\in C$ は $F(b)$ を満たします。（さもなくば、 $b \in N$ となり、 $a_0$ が $N$ の最小要素であることに矛盾します。）すると、(3-1) により、 $F(a_0)$ が成り立つことになり矛盾が生じます。したがって、(3-2) は必ず成り立つのです。

なるほどー。

超限帰納法は何が「超限」なのか？

通常の（自然数に対する）数学的帰納法では、(3-1) に相当する部分は、

　 $\forall k \in \mathbb N;[\, F(k)\ \rightarrow \ F(k+1)]$ --- (4-1)

すわなち、「 $k$ について成り立つ時、 $k$ の次の値（つまり $k+1$ ）についても成り立つ」という形で与えます。一方、値の範囲を順序数全体に拡張した超限帰納法では、このような形ではうまく行きません。なぜなら、 $k$ の値を 1 つずつ増やしていけば、任意の自然数 $n$ に到達できますが、さきほどの $\omega$ には永遠に到達することができないからです。そのため、超限帰納法を利用して、(3-2) を証明する場合は、通常の数学的帰納法よりも強い関係となる (3-1)、すなわち、「 $b < a$ である任意の $b$ について $F(b)$ が成り立つという前提で、 $F(a)$ が成り立つ」ことを証明する必要があります。これは、場合によっては、数学的帰納法よりも証明の難易度があがります。たとえば、任意の自然数 $n$ について $F(n)$ が成り立つ、という前提から、 $F(\omega)$ が成り立つことを証明する場合を想像するとよいでしょう。このように、順序数の列には、「次の値をたどっていく」だけでは永遠に到達できない「値のギャップ」が所々にあり、 $\omega$ のように、そのようなギャップの直後にある値を「極限数」と呼びます。

参考文献

・順序数（TAIKEI BOOK）
・順序数・基数（Eureka GAP）

2022-12-29

圏論における随伴関係の導入例

線形変換の2つの見方

ベクトル空間 $W$ からベクトル空間 $V$ への線形変換 $f$ は、本質的には、 $W$ の基底の集合 $\{\mathbf e_i\}$ の像で決まるので、

　 $(\{\mathbf e_i\},\, V) := 「\{\mathbf e_i\}$ から $V$ への写像全体」--- (1)

と

　 $(W,\, V) :=$ 「 $W$ から $V$ への線型写像全体」--- (2)

は、本質的に同一であり、それぞれの要素の間には 1:1 の対応が付けられます*1。

この時、(1) においては、 $V$ はベクトル空間であることは忘れて、単なる集合間の任意の写像を考えている事に注意してください。この点を明確にするために、ベクトル空間 $V$ の要素を集めた集合（つまり、要素間の演算の事を忘れ去った集合）を $G(V)$ と表すことにして、(1) を

　 $(\{\mathbf e_i\},\, G(V)) := 「\{\mathbf e_i\}$ から $G(V)$ への写像全体」--- (1)'

と書き直すことにします。また、 $\{\mathbf e_i\}$ が張るベクトル空間を $F(\{\mathbf e_i\})$ という記号で表すことにすると、 $W=F(\{\mathbf e_i\})$ となるので、(2) は、

　 $(F(\{\mathbf e_i\}),\, V) :=$ 「 $F(\{\mathbf e_i\})$ から $V$ への線型写像全体」--- (2)’

と書き直すことができます。(1)' と (2)' の要素の間に 1:1 の対応が付けられるという事実を

　 $(\{\mathbf e_i\},\, G(V)) \cong (F(\{\mathbf e_i\}),\, V)$ --- (3)

という記号で書き表します。

実はこれは、圏論で言うところの「随伴関係」の一例になっています。

(1)' では、集合間の任意の写像を考えることができる代わりに、写像の定義域が「基底の集合」という制限された集合になっています。一方、(2)' は定義域も値域も一般的なベクトル空間である代わりに、その写像には「線形性を満たす」という制限が加えられています。このように本質的に同一の「変換」に対して、2種類の異なった「見方」を与えるものが、圏論における随伴関係と言えるでしょう。

「ズレ」が無い場合の変換（関手）

上述の (1)' では、写像の定義域と値域にちょっとした「ズレ」がある点がポイントですが、2つのベクトル空間の基底同士を直接に対応づけて、

　 $\{\mathbf e'_j\} \xrightarrow{f} \{\mathbf e_i\}$ --- (4)

という「ズレ」の無い写像を考えることもできます。ここで、 $\{\mathbf e'_j\}$ と $\{\mathbf e_i\}$ は、それぞれ、異なるベクトル空間の基底の集合としてください。この場合も、それぞれの基底が張るベクトル空間 $F(\{\mathbf e'_j\})$ と $F(\{\mathbf e_i\})$ の間に、対応する線型写像が決まりますが、これを $F(f)$ という記号で表すことにします。

　 $F(\{\mathbf e'_j\}) \xrightarrow{F(f)} F(\{\mathbf e_i\})$ --- (5)

こちらは、圏論の世界では、「関手」と呼ばれる関係性になります。基底の集合をそれらが張るベクトル空間に変換する操作 $F$ は、それと同時に、基底の集合間の写像 $f$ を対応する線型写像 $F(f)$ に変換する操作を生み出すというわけです。

なお、先ほどの随伴では、あらゆる線型写像が網羅的に 1:1 対応できていたのに対して、こちらではそのような対称性はありません。定義域と値域、両方のベクトル空間で特定の基底 $\{\mathbf e'_j\}$ と $\{\mathbf e_i\}$ を定めてしまうと、これらの間で表現できる線型写像は限定的なものになるので、(4) の世界の写像で (5) の世界の写像を網羅することにはなりません。つまり、(4) の世界から (5) の世界への変換はできても、その逆変換はできないのです。

それでは、ベクトル空間を単なる要素の集合に変換する操作 $G$ について、同様のことを考えるとどうなるでしょうか？

まずは、2つのベクトル空間の間の線型写像を考えます。

　 $W\xrightarrow{f} V$ --- (6)

そして、それぞれのベクトル空間を単なる集合と思い直せば、写像 $f$ はそのままの形で、集合間の写像と思い直すことができます。これを $G(f)$ と表すことにしましょう。

　 $G(W)\xrightarrow{G(f)} G(V)$ --- (7)

これもまた、「関手」の一例となりますが、ここでもまた、随伴のような対称性は失われています。(7) は単なる集合間の写像ですので、(7) の世界で考えた写像の中には、線型写像にならないものもあります。先ほどと同様に、(6) から (7) への変換はできても、その逆はできません。随伴は、逆向きの2つの変換 $F, G$ をうまく「入れ子」にすることで、対称性を作り出していると言えるでしょう。

随伴関係の Naturality

随伴関係では、2つの世界の写像の間に 1:1 の対応関係がありました。そこで、(1)' の世界の写像 $f$ から決まる (2)' の世界の線型写像を $\overline f$ で表す事にします。同様に、(2)' の世界の線型写像 $g$ に対応する (1)' の世界の写像を $\overline g$ で表します。反対方向の対応づけに同じ記号 $\overline{\,\cdot\,}$ を使うのは、ちょっとよろしくないかもしれませんが、もともと 1:1 対応することが分かっているので、特に混乱することはないでしょう。（行列の転置記号のようなものと思えばよいかも？）この記号を使うと、当然ながら、 $\overline{\overline f}=f$ が成り立ちます。

この記号を用いると、随伴関係とそれを構成する2つの関手には、ある自然な関係が成り立つことがわかります。たとえば、

　　 $\{\mathbf e_i\}\,\xrightarrow{f}\,G(W)$ --- (8)
　 $F(\{\mathbf e_i\})\,\xrightarrow{\overline f}\,W$ --- (9)

という随伴の意味で同等な変換があった時、この変換の手前に、

　　 $\{\mathbf e'_j\}\,\xrightarrow{p}\,\{\mathbf e_i\}$
　 $F(\{\mathbf e'_j\})\,\xrightarrow{F(p)}\,F(\{\mathbf e_i\})$

という関手の世界での変換を付け加えてみます。

　　　 $\{\mathbf e'_j\}\,\xrightarrow{p} \{\mathbf e_i\}\,\xrightarrow{f}\,G(W)$ --- (10)
　 $F(\{\mathbf e'_j\})\,\xrightarrow{F(p)} F(\{\mathbf e_i\})\,\xrightarrow{\overline f}\,W$ --- (11)

この時、(10) の世界の合成変換 $f\circ p$ を考えると、対応する (11) の世界の線形変換 $\overline{f\circ p}$ はどのようなものになるでしょうか？　落ち着いて考えると分かるように、

　 $\overline{f\circ p} = \overline f\circ F(p)$ --- (12)

が成り立ちます。（基底ベクトル $\mathbf e'_j$ の最終的な行き先が同じになることが確認できればOKですよね。）

同様にして、(8)(9) の後ろに、

　 $G(W)\,\xrightarrow{G(q)}\,G(V)$
　　　 $W\,\xrightarrow{q}\,V$

という変換を付け加えてみます。

　　 $\{\mathbf e_i\}\,\xrightarrow{f}\,G(W)\,\xrightarrow{G(q)}\,G(V)$
　 $F(\{\mathbf e_i\})\,\xrightarrow{\overline f}\,W\,\xrightarrow{q}\,V$

この場合は、合成変換 $G(q)\circ f$ に対応する線形変換を考えて、

　 $\overline{G(q)\circ f} = q\circ \overline f$

という対応関係が成り立ちます。(12) と見た目が違うのが気になる場合は、 $g=\overline f$ と置いて、 $\overline{\overline\cdot} = \cdot$ の関係を使うと、

　 $\overline {q\circ g} = G(q)\circ\overline g$ --- (13)

と書き直すこともできます。

圏論における随伴関係では、一般に、(12)(13) の関係が成り立つことも随伴であることの条件として含まれます。

行って帰ってくるとどうなるか？（unit / counit）

随伴関係の 2 つの関手 $F,G$ は 2 つの世界を行ったり来たりするものですが、行って帰ってくるとどうなるか？という素朴な疑問が湧いたりもします。どういうことかというと、さきほどの (8)(9) で、 $W=F(\{\mathbf e_i\})$ として、(9) の世界では単純な恒等変換 $1_{F(\{\mathbf e_i\})}$ を取ってみます。

　　 $\{\mathbf e_i\}\,\xrightarrow{\overline{1_{F(\{\mathbf e_i\})}}}\,G(F(\{\mathbf e_i\}))$ --- (14)
　 $F(\{\mathbf e_i\})\,\xrightarrow{1_{F(\{\mathbf e_i\})}}\,F(\{\mathbf e_i\})$ --- (15)

この時、対応する (14) の世界では何がおきているのでしょうか？

まず、 $G(F(\{\mathbf e_i\}))$ というのは、ベクトル空間 $F(\{\mathbf e_i\})$ から演算を忘れたものなので、集合としては $F(\{\mathbf e_i\})$ と同等でした。また、(14) の世界は、(15) の世界における線型写像から、基底の像だけを取り出したものですので、恒等変換 $1_{F(\{\mathbf e_i\})}$ に対応する写像 $\overline{1_{F(\{\mathbf e_i\})}}$ は、単純に、恒等変換 $1_{F(\{\mathbf e_i\})}$ の定義域を基底だけに制限したものと考えればOKです。

まあまあ、シンプルですね。

これは、 $F$ で行って $G$ で帰ってきた場合の話ですが、では、その逆に、 $G$ で行って $F$ で帰ってくるとどうなるでしょう？　こちらはちょっと複雑ですが、なかなか興味深い結果になります。

ちょっと病的（？）な操作にも思えますが、まず、さきほどの (8)(9) で、 $\{\mathbf e_i\} = G(W)$ と置いて、(8) の世界で恒等変換 $1_G(W)$ を取ります。

　　 $G(W)\,\xrightarrow{1_G(W)}\,G(W)$ --- (14)
　 $FG(W)\,\xrightarrow{\overline{1_{G(W)}}}\,W$ --- (15)

$G(W)$ はベクトル空間 $W$ のあらゆる要素を集めた集合ですので、(14) は、ベクトル空間 $W$ の恒等写像と本質的には同じものです。一方、よくわからないのが、(15) にある $FG(W)$ です。 $F(S)$ というのは、集合 $S$ のそれぞれの要素を基底として、これらが張るベクトル空間を考えたものでしたので、今の場合、ベクトル空間 $W$ のあらゆる要素を（ベクトルという事実を忘れた、単なる集合の1要素と思って）独立した基底ベクトルとする、（無限個の基底ベクトルからなる）無限次元のベクトル空間が $FG(W)$ になります。

むむむ。どういうことでしょう。

たとえば、 $G(W)$ の中には、 $\mathbf v_1 = 2\mathbf e_i$ と $\mathbf v_2 = 3\mathbf e_i$ という2つの要素があります。 $FG(W)$ の中では、これらは「独立した基底ベクトル」とみなされるので、線型結合 $\mathbf w = a\mathbf v_1 + b\mathbf v_2$ は、これ以上簡単にすることはできません。もとの $W$ の世界であれば、

　 $\mathbf w = a\mathbf v_1 + b\mathbf v_2 = (2a+3b)\mathbf e_i$

という計算ができるにも関わらずです。なんだか、病的に「膨れ上がった」世界のようです。

そして、(15) の変換 $\overline {1_{G(W)}}$ は、この膨れ上がった世界 $FG(W)$ の要素を元のベクトル空間 $W$ の要素に変換しているようですが、どのような変換でしょうか？

(14) の世界は、「基底ベクトル」の行き先を表すことを思い出すと、上記の $G(W)$ の世界の基底ベクトル $\mathbf v_1,\mathbf v_2$ はそのまま、 $W$ の世界のベクトル $\mathbf v_1,\mathbf v_2$ に移る事になります。そして、 $\overline {1_{G(W)}}$ は線形変換であることから、先ほどの $\mathbf w$ の行き先は、

　 $\mathbf w = a\mathbf v_1 + b\mathbf v_2\, \xrightarrow{\overline {1_{G(W)}}}\,a\mathbf v_1 + b\mathbf v_2$ --- (16)

という結果になります。

え？やっぱり恒等写像？

いいえ。違います。

(16) の右側は、ベクトル空間 $W$ ですので、左側の $FG(W)$ と異なり、 $\mathbf v_1$ と $\mathbf v_2$ はもはや独立な基底ではありません。普通に、 $W$ の要素として、

　 $\mathbf w = a\mathbf v_1 + b\mathbf v_2 = (2a+3b)\mathbf e_i$

という計算ができてしまいます。

つまり、 ${\overline {1_{G(W)}}}$ は、 $FG(W)$ の要素を $W$ の要素と思い直して、「膨れ上がった世界」を元の $W$ の世界に戻してしまう（ $W$ の世界での演算を許す）という操作に対応しています。

いやー。なんだか面白いですね。

一般には、随伴関係 $F, G$ があった場合、 $\eta_A := \overline {1_{F(A)}}$ で決まる写像を Unit、 $\epsilon_B := \overline {1_{G(B)}}$ で決まる写像を counit と呼びます。これらは、さらに圏論で言うところの自然変換になっていて、三角恒等式を満たして・・・・という面白い話があるのですが、ここから先は、ぜひ、ちゃんとした圏論の教科書で学んでみてください。随伴については、下記の教科書がおすすめです。

ベーシック圏論普遍性からの速習コース

作者:Tom Leinster
丸善出版

Amazon

*1:本来は ${\rm Hom}(\{\mathbf e_i\},\, V)$ などと表記するべき所ですが、 ${\rm Hom}$ の意味を過剰に読み取ろうとすると混乱するので、あえてシンプルに表記しています。

2022-12-18

数理最適化と機械学習を比較してみる

数理最適化 Advent Calendar 2022 の記事です。

何の話かと言うと

Pythonではじめる数理最適化 ―ケーススタディでモデリングのスキルを身につけよう―

作者:岩永二郎,石原響太,西村直樹,田中一樹
オーム社

Amazon

上記の書籍の第7章では、次のような問題を取り扱っています。

細かい点は書籍に譲りますが、まず、生データとして次のようなデータが与えられます。

これは、あるショッピングサイトの利用履歴を集計して得られたもので、あるユーザーが同じ商品を閲覧した回数（freq）と、その商品を最後に閲覧したのが何日前か（rcen）の2つの値から、そのユーザーが次にサイトにやってきた時に、再度、その商品を閲覧する確率（prob）を実績ベースで計算したものです。実績ベースのデータなので、ガタガタしたグラフになっていますが、理論的には、

・freq が大きいほど prob は大きくなる
・rcen が小さいほど prob は大きくなる

という条件を満たした、なめらかな曲面になると期待することができます。

そこで何らかの方法で、このようななめらかな曲面のグラフを得ることができれば、これを予測に使うことができます。このサイトにユーザーがログインした際に、該当ユーザーの過去の閲覧履歴から、このユーザーが再度閲覧する確率が最も高い商品（つまり、このユーザーが、今、最も関心を持っている商品）を予測して、「おすすめ商品」として先回りして表示するなどの利用方法が考えられます。

原理的には、上記の実績ベースのグラフをそのまま使って予測することもできますが、実績ベースのデータは、理論的に妥当な予測値に対して、たまたまこのデータに含まれていたノイズ（理論には合わない例外的な行動や誤ったデータ）が加わってガタガタした結果になっていると考えれば、それよりも、理論的に妥当ななめらかな曲面のグラフで予測した方が、予測の精度は良いものと期待できます。

機械学習による予測

それでは、みなさんであれば、どのような方法で「理論的に妥当ななめらかな曲面のグラフ」を手に入れるでしょうか？　機械学習になじみのある方であれば、「上記のデータを学習データとして、最小二乗法で学習すればよいのでは？」と思いつくかもしれません。--- はい。私も最初、そう思いました。

で、やってみました。

データ数がそれほど多くないので、複雑なモデルにすると、簡単にオーバーフィッティングするのが目に見えているので、まずは、シンプルな線形モデルでやってみました。

　 $({\rm prob}) = w_1 ({\rm freq}) + w_2 ({\rm rcen}) + b$

というモデルを用意して、二乗誤差が最小になるように、 $w_1, w_2, b$ の値を学習します。

結果はこちらです。

確かに、

・freq が大きいほど prob は大きくなる
・rcen が小さいほど prob は大きくなる

という条件は満たしていますが、元データと比較すると、ちょっと「ズレ」が大きい気がします。もうちょっと改善したいところです。

で、次の手として、二次の項まで含めたモデルにしてみました。

　 $({\rm prob}) = w_1({\rm freq}) + w_2 ({\rm rcen}) + w_3 ({\rm freq})^2 + w_4 ({\rm rcen})^2 + w_5 ({\rm freq}) ({\rm rcen}) + b$

結果はこちらです。

先ほどの結果と比べると、元データに近い、もっともらしい結果が得られました。これなら使ってみてもよさそうです。

・・・・なのですが、よーくみてみると、この結果は、

・freq が大きいほど prob は大きくなる
・rcen が小さいほど prob は大きくなる

という条件が満たされなくなっています。

「予測精度が十分高ければ、このような条件を厳密に満たしてなくてもいいじゃん」という機械学習らしい考え方もできますが、仮に、どうしてもこの条件を満たす結果が必要であれば、みなさんならどうします？？？

まぁ、いろいろな方法がありそうな気はしますが、モデルそのものに作為的に手を加えすぎると、「データから学習する」という機械学習の本質からずれていきそうで、ちょっとアレな気分にならなくもないですね。

数理最適化モデルによる予測

一方、前述の書籍は、数理最適化の本なので、機械学習ではなく、数理最適化モデルを用いて予測を行います。詳細は、書籍に譲りますが、凸二次計画問題にモデリングして、

・recn に関する単調性
・freq に関する単調性
・recn に関する凸性（下に凸）
・freq に関する凹性（上に凸）

という制約条件を加えて最適化を行います。結果として、次のようなグラフが得られます。

最終的に、「予測値と実績値の二乗誤差を最小化する」という条件で最適化をおこなっていますので、この点については機械学習と同じことをやっていると言えますが、結果に対する単調性や凸性を明示的に制約条件として指定している点が、機械学習とは大きく異なるポイントになります。

数理最適化モデルと機械学習では、それぞれに得意・不得意がありますが、これまで機械学習を学んできた方で、「数理最適化はまだよく知らない」という方は、数理最適化モデルについても学んでみると、このような比較から、機械学習への理解がさらに深まるかもしれませんね。

追記

うーむ。確率をモデリングするならとりあえず、pをlog(p/(1-p))に変換した値をフィッティングすることを考えるかなぁ。いきなり多項式フィッティングは私はしないかなぁ。 https://t.co/icy3BOfMi6
— Takashi Miyamoto (@tmiya_) 2022年12月19日

この記事を公開した後、上記のコメントを Twitter でいただきました。ごもっともですね。確率値には $0\le p \le 1$ という本質的な制約がありますので、 $-\infty\le x\le\infty$ の値を取る線形モデルでフィッティングするというのは、筋のよいやり方ではありません。線形モデルの出力 $x$ をロジスティック関数

　 $\displaystyle p = \frac{1}{1+e^{-x}}$

で確率値に変換するのが定番のテクニックになります。ロジスティック関数の逆函数はロジット関数

　 $\displaystyle x = \log\left(\frac{p}{1-p}\right)$

ですので、確率 $p$ を上記の $\displaystyle x = \log\left(\frac{p}{1-p}\right)$ に変換したものを正解ラベルとして、これを線形モデルでフィッティングすればよいことになります。

で、実際にやった結果がこちらです。線形モデルでも十分に自然な結果が得られていますね。

めもめも

このブログに記載の内容は個人の見解であり、必ずしも所属組織の立場、戦略、意見を代表するものではありません。

順序数の導入例

集合による「自然数」の定義

「n を表す集合」の性質（推移性）

順序数の公理的定義

自然数を超える「数」の存在

整列順序について

超限帰納法について

超限帰納法は何が「超限」なのか？

参考文献

圏論における随伴関係の導入例

線形変換の2つの見方

「ズレ」が無い場合の変換（関手）

随伴関係の Naturality

行って帰ってくるとどうなるか？（unit / counit）

数理最適化と機械学習を比較してみる

何の話かと言うと

機械学習による予測

数理最適化モデルによる予測

追記