2018-07-10

ロジスティック回帰

当たり前のようで、何を言ってるかよくわからない部分があったので、調べなおしてみました。

二値分類

まずは一番簡単な二値分類の場合のロジスティック回帰について説明します.

${D= \{x_i,y_i\}_{i=1}^d,x_i \in \mathbb{R}^m,y_i = \{-1,1\}}$ とする. これに対して,ある ${\phi:\mathbb{R}^m \to \mathbb{R}^n}$ を用意する. 例えば自然言語処理だと,単語の分散表現等そして、 ${w_i \in \mathbb{R}^n}$ を用いて,

${ \displaystyle p(y_i \mid x_i):= \frac{1}{1 + \mathrm{exp}(- y_i {}^tw \phi(x_i))} }$

と定めます.これは2つの事象 ${y_i=1}$ と ${y_i=-1}$ となる確率が合計1であることから、 ${\{-1,1\}}$ 上の確率(測度)を定めます. ですが、これは適当な確率であって、我々が本当に知りたい。 ${x_i}$ に対して、そのラベルが ${y_i}$ である確率を表しているわけてはありません.

そうすると上の式でできる限り,我々の知りたい確率に近づくようにとりたくなります.

このために,データの中で ${x_i}$ に対し ${y_i}$ に対して, ${p(y_i \mid x_i)=1}$ にできるだけ近づけるようにパラメータ ${w}$ を取りかえるというアイデアを採用します. なので,損失関数 ${L(w):= - \sum p(y_i \mid x_i)}$ として,これが最小になる ${w}$ を求めます。

こうやって確率を内部で求めるので回帰と名付けられているわけですが、実際に問題を解く場合はその確率が一定の値以上の場合は1,そうでない場合は-1と分けるので,二値分類になります.

パラメータの変更は例えば確率的勾配降下等で計算するのが速く、実用的になっているようです. また、損失関数も今のままの ${L}$ は過学習しやすい傾向があることが多く、経験的に、正則化項と呼ばれる項 ${C \vert w\vert^2}$ 等を加えるとよいようです.

余談

実際こうした方法の特徴はなんでしょうか。例えばSVMのような直線を引くのとどちらがわかりやすいのか... 指数関数を使うので、外れ値を無視しやすいとかそういう傾向があったりしないんでしょうかね。

多値分類

多値の場合も実質二値分類と同じです. 先ほどは ${\{-1,1\}}$ 上の確率分布だったのを適当に ${\{1,2,3,4,...\}}$ 上の確率分布だと思って求めればよいです.

その場合は

${ \displaystyle p(y_i \mid x_i):= \frac{\mathrm{exp}(\lambda f(x_i,y_i))}{\sum_j \mathrm{exp}(\lambda f(x_j,y_j))} }$

とします. ${f:\mathbb{R}^m \times \mathbb{R}^k \to \mathbb{R}^n}$ です. 後は損失関数も全て同じです.

2018-07-08

ACL読み回2018

machine learning NLP

ACLの読み回に参加してきました.

感想を三行でまとめると

NLP界隈の常識がわかる
発表者の疑問がわかる
数式はお気持ち

NLP界隈の常識がわかる

一人でやっているのでは伝わらない当たり前の知識が伝わるのがとてもよかったです. Seq2Seq + Attentionがデファクトスタンダードだけれど、 - 未知語が対処できない - 同じものが複数回生成されるという課題があり,それらにどう対応するかが考えられている.

とはいえ、ネットワークを劇的に改善させるというよりは - ドキュメントっぽさ.前の文章の情報を加える. - 意味っぽい情報を加える

というのが基本で、劇的に新しい手法はなさそう.Transofomerも出てきたけど、あまりそれを使っていない模様.

相変わらずデータが重要で、分散表現等を工夫する余地はまだまだあるのだなという風に感じた.

自分がよく知らないけど、当たり前っぽい用語がたくさん出てきたのもよい. 文章要約のROUGEは自分はまだあまりなじみがないけれど、覚えておくべきだと思ったし,NLPの人と関わりの薄い自分からすると,聞いたことがあるという感覚自体に意味があると思った次第です。

発表者の疑問がわかる

何故ここで検証していないのか,解釈できない.そもそもこれは悪手なのではという点を説明していて,それを適切に議論できるのはとてもよい.

特に一番最後のベストペーパーについての解説が, これ課題に対応していないからおかしくないか?やこの課題の正答率低すぎないか?に対していろいろ見解を述べていて,そこにはアイデアが新規である分,完成度の低さを感じれたし.やっぱりお気持ちだから曖昧になるのだなと思うこともわかった.

数式はお気持ち

皆思い思いに絵をかいたり数式を書いてるけど、どう考えてもその辺に対して曖昧さがあるなあと思うなど.

なんというか、私は数学的なものは数学的なレイヤーで思考できるので、その観点で問題ないかや何を意味しているかをチェックするのだけれど,皆その辺は何もしていないのだろうなと思った.

「微分できない」、何から何の関数だと思ったときに〇〇だから微分できないって思うの20秒もかからないと思うのだけれど、そういうのは説明されないし,気にならないし、気にしていないのだろうなあ。実際実装はそれらのお気持ちを反映してNNで数式ときちんと対応しているのかもきわどいところなので.

逆に言うと,皆機械学習ですらなく自然言語処理のレイヤーで思考していた. 具体的には言語の処理固有の課題を見つけ,それに対応する何かを加えるというアイデアが基本で,適当に実装してみて一番よかったのをみると、こんな感じという主張にも見えた.

その辺実際どの程度理解しているのか突っ込んで聞いてみたくも思ったけど、今回はまだまだ知らない人ばっかりだったので、諦めた.

理解の仕方の違いでもあるので、質問しまくっても問題ない人を見つけてどう理解しているのかどうしてもそこは問題ないと思うのかを徹底的に議論したいなあと思うなど.

具体的な話

資料はここ

今日聞いていても一番思ったのはこれ

論文に対して自分の感想を書く程でもなく資料によく書かれていると思ったので、今回は割愛します。

発表してくださった方々、企画してくださった方々ありがとうございました。

2018-07-08

AtCoder SoundHound Inc. Programming Contest 2018 -Masters Tournament-

At Coder のコンテストのログです.

C

問題文

数列 (a_1,...,a_n) の美しさを、隣り合う 2 項の組であって、差の絶対値が d であるものの個数として定義します。例えば、d=1 であるとき、数列 (3,2,3,10,9) の美しさは 3 です。各要素が 1 以上 n 以下の整数である長さ m の数列は全部で n^m 通り存在します。この n^m 通りの数列すべてに対して美しさを求めて、それらの平均を出力してください。

制約

0 ≤ d <n≤10⁹
2≤m≤10⁹
入力はすべて整数

解答

美しさが1上がる時は数列内に a_i,a{i+1} の差が d となる時です.それは前後の列には関係ありません。そのため、期待値の線形性から長さ m の数列の美しさの期待値は(a_0,a_1)の美しさの期待値 + ... + (a{m-1},a_m)の期待値になります.

(a_0,a_1) について考えます. もし a_0 < d, a_0> n -d なら美しさが1となる組はただ1つ定まります. d \le a_0 \le n-d ならば,美しさが1あがるのは a_1 = a_0 + d,a_0 -d があります。これは d = 0 の時一通り,それ以外は2通りあることになります。

これから答えは以下のようになります.

n,m,d = list(map(int,input().split()))

if n > 2 * d and d > 0:
    l = n -2 * d
else:
    l = 0
# 問題文を読み違えて美しさが0 or 1になるものだと勘違いした名残
sums = [(m -1 ) * ( n +  l)]
print( sum(sums) / (n ** 2 ))

D

問題文

kenkoooo さんはすぬけ国での旅行の計画を立てています。すぬけ国には n 個の都市があり、m 本の電車が走っています。都市には 1 から n の番号がつけられていて、 i 番目の電車は都市 ui と vi の間を両方向に走っています。どの都市からどの都市へも電車を乗り継ぐことで到達できます。すぬけ国で使える通貨には、円とスヌークの 2 種類があります。どの電車の運賃も円とスヌークのどちらの通貨でも支払え、 i 番目の電車の運賃は、円で支払う場合 ai 円、スヌークで払う場合 bi スヌークです。両替所のある都市に行くと、1 円を 1 スヌークに両替することができます。ただし、両替をするときには持っている円すべてをスヌークに両替しなければなりません。つまり、kenkoooo さんの所持金が X 円であるときに両替をすると、 kenkoooo さんの所持金は X スヌークになります。現在、両替所は n 個の都市すべてに存在しますが、 i 番目の都市の両替所は今年から i 年後に閉鎖されてしまい、 i 年後とそれ以降は使うことができません。 kenkoooo さんは 10^{15} 円を持って都市 s から旅に出て、都市 t へ向かおうと思っています。移動中、kenkoooo さんは両替所のある都市のいずれかで円をスヌークに両替しようと考えています。ただし、都市 s または都市 t の両替所で両替をしてもよいものとします。 kenkoooo さんは移動の経路と両替をする都市を適切に選ぶことで、できるだけ多くのスヌークを持っている状態で都市 t に辿り着きたいと考えています。 i=0,...,n−1 のそれぞれについて、i 年後に都市 s から都市 t へ移動した際に kenkoooo さんが所持しているスヌークの最大額を求めてください。ただし、旅行中に年をまたぐことは無いとします。

制約

2≤n≤10⁵
1≤m≤10⁵
1≤s,t≤n
s≠t
1≤ui<vi≤n1≤ai,bi≤10⁹
i≠j のとき ui≠uj または vi≠vj
どの都市からどの都市へも電車を乗り継ぐことで到達できる入力はすべて整数

解答

問題文が長いので条件を整理すると

円とスヌークの価値は同じ
スヌークから円への交換はできないので、交換はただ一度のみ可能
スヌークへの交換は必ず一度はしないといけない?(スヌークの最大値求める問題であるため、一度は必ず交換するが)
i 年後は{i + 1}以降でしか交換できない.
どの道も自由に通れる.

このことから,円について s から i まで移動するのにかかるお金の最小値とスヌークについて i から t まで移動するのにかかるお金の最小値を求め、その和が最小になる i で答えを求めれば良い. i から t までの移動にかかるお金の最小値は t から i へのお金の最小値と同じなので、これらについて動的計画法というか、この場合はダイクストラ法を使えば求まる.

ちなみに私は問題文を読み違えて、スヌークから円にも交換できるから、計算時間あふれるやんどうするんだ？？ってなりました。 ~~実際そうなったら計算時間のかからない方法は存在しない気がします.~~

from collections import defaultdict
import heapq
n,m,s,t =list(map(int,input().split()))

uvab =  [list(map(int,input().split())) for _ in range(m)]
en = [[] for _ in range(n) ]
snuke = [[] for _ in range(n)]

 
for u,v,a,b in uvab:
    u=u-1
    v=v-1
    en[u].append((a,v))
    en[v].append((a,u))
    snuke[u].append((b,v))
    snuke[v].append((b,u))
 
 
def dijkstra(edges, s):
    INF = 10 ** 15
    d = [INF for x in range(n)]
    d[s] = 0
    que = []
    heapq.heappush(que, (0,s))
 
    while len(que) > 0:
        u_d,u = heapq.heappop(que)
        if d[u] < u_d:
            continue
        for  v_d,v in edges[u]:
            if d[v] > d[u] + v_d:
                d[v] = d[u] + v_d
                heapq.heappush(que,(d[v],v))
    return d

en_ds =  dijkstra(en,s-1)
snuke_ds = dijkstra(snuke,t-1)
scores = [0] * n
for i in range(n):
  scores[i] = 10**15 - (en_ds[i] + snuke_ds[i])

ans = [ 10 ** 15 for _ in range(n)]
ans[n-1] = scores[n-1]
for i in range(n-2,-1,-1):
    ans[i] = max(ans[i+1],scores[i])
for a in ans:
    print(a)

ダイクストラ法とは

反省の意味も込めてダイクストラ法を解説します. ダイクストラ法はグラフ G=(V,E) に対し,その辺に重み k が与えられた時に、 s から t に対する最短経路を求める方法です.

基本的には 1. s から1辺で繋がる点に対する長さの最小値となる点を求める. 2. その点に対して,長さの最小値が確定する(できる) 3. 二辺で繋がる辺の最短経路の確定できる点を増やす

実装上は 1.　予め全点に距離を∞にした配列dを作成(この配列は計算段階での最小の重さの配列を表す) 2.　始点sに距離を0にする(d[s]= 0) 3.　始点sとその時点での距離0をキューにいれる 4.　キューからpopし、点uとその時の距離u_dを取得する。それと現時点でわかる最短距離d[u]を比較し、d[u]が小さければ飛ばす.(これによってすでに計算済みのものは扱わないという操作) 5.　popした点uと辺で繋がる点vに対し,その時点での最短距離d[v]と u までの最短距離＋dまでの長さd[u]+v_dを比較しそれが小さければd[v]を更新し、(v,d[v])をキューに加える 6. 4.5.をキューがなくなるまで実施する。

こうなることで最短の経路を求められ、かつ無駄な操作はあまりないというものになります。

2018-05-27

基数の理論

数学

これは,数学カフェ基礎論回の予習回第６回の講演内容のメモです.

このセミナーの最終目標は連続体仮説がZFCと独立であることの証明です。今回は連続体仮説が何を主張しているかを理解することを目指して解説します.

連続体仮説の主張は以下のようなものでした.

Statement(連続体仮説)
${\aleph_1 = 2^{\aleph_0}}$

ここで出てくる ${\aleph_1 , 2^{\aleph_0}}$ は基数です. 基数は順序数であり,また加法,乗法,指数関数が定義できます. 上で現れる ${2^{\aleph_0}}$ は基数 ${\aleph_0}$ と2の定める指数関数です.

さて,任意の整列集合はあるただひとつの順序集合と順序同型であり,その意味で順序数は整列集合としての代表元を定めたものでした. 基数は整列集合ではなく,集合の代表元を定めたものとなります. 集合の代表元を定めるには集合としての構造が等しいことを定義する必要があります. とはいえ集合には他に構造もないので全単射が存在することで集合として"等しい"ことを定めます. 集合はその集合の濃度を取るという操作によって,集合の代表元として基数を定めることになります. 基数は順序数なので.集合の大小関係を記述するためにも使えます. 一方で順序同型の場合は順序数の大小がそのまま、順序同型の有無に影響していましたが、集合として考える場合は、順序数としては,真に大きい順序数であっても集合として同型になる場合があります。そこで、我々は集合として同型になる順序数の中で最小なものとして、基数を定義します.

今回は基数と集合の関係を述べ,その基数との関係が理解するために必要な集合上の操作と連続体仮説を理解するのに必要な基数の定義や操作を説明します. 具体的には

全ての集合が整列順序づけ可能であること
集合の対等性を定義し，集合の対等生に関するベルンシュタインの定理、カントールの定理を証明する
基数を順序数の対等類の最小要素として定義する
基数の加法と乗法を定義し,性質を調べる.
基数の指数関数を定義し,連続体仮説の主張を述べる.

実際に独立性証明のためには連続体仮説の主張を理解するだけでなく,絶対性や強制法等の議論が必要です.そこは本番に期待したいと思います。

全ての集合が整列順序づけ可能であること

全ての集合が整列順序づけ可能であることはツェルメロの定理と呼ばれています。この章ではその定理の証明をします。また、今までは選択公理はあまり仮定されていませんでしたが、この章では選択公理を使います

そのため、最初に選択公理について確認し、我々が仮定した選択公理から選択関数が存在することおよびその時に使われる商集合について言及したいと思います.

Definition
集合 ${X}$ 上の関係 ${R \subset X \times X }$ が同値関係であるとは,以下を満たすことである. 1) ${\forall x, \forall y (\langle x,y \rangle \in R \to \langle y,x \rangle \in R) }$ 2) ${\forall x,\forall y \forall z (\langle x,y\rangle \in R \land \langle y,z \rangle \in R \to \langle x,z\rangle \in R)}$ 3) ${ \forall x \in X \langle x,x\rangle \in R }$

同値関係の重要なところは商集合が定義できるところです

Definition
${X}$ 上の同値関係 ${R}$ に対し、 ${X/R := \{ b \in P(X) \mid \exists a \in X , b= \{ y \in X \mid \langle y,a \rangle\in R\} \}}$ は集合となり、それを商集合と呼ぶ

上の定義には同値関係が必要ありません。関係であることと冪集合公理と分出公理だけから集合の存在を示すことができます. しかし,同値関係による商集合には以下が成りつという特徴があります.

商集合 ${X/R}$ は元の集合 ${X}$ の分割になっている。すなわち、以下が成り立つ.
1) ${\bigcup X/R = X}$
2) ${a \in X/R ,b \in X/R }$ に対し, ${ a \neq b \leftrightarrow a \cap b = \emptyset}$
3) ${\emptyset \notin X/R}$

ここから、以下が従います.

${\forall x \in X \exists ! y \in X /R ( x \in y)}$
${\forall y \in X/R \exists x \in X (x \in y)}$

さて、我々が採用した選択公理のStatemnetは以下でした.

Axiom of Choice
${\forall a( \emptyset \notin a \land x,y \in a (x \neq y \to x \cap y = \emptyset) \to \exists b \forall x \in a \exists c \in x (b \cap x = \{c\})}$

これは先程の商集合の性質と照らし合わせると、 ${a}$ というある同値関係で割られた商集合には,その完全代表系のなす集合が存在するという意味になります.

この命題は商集合側でとっていますが,実際使う際は以下の選択公理と同値な定理として使われることが多いです.

Theorem
${\forall a( \emptyset \notin a \to \exists f ( (f:a \to \bigcup a) \land (\forall x \in a ( f(x) \in x))) }$

ひとまず,選択公理から上の定理が従うことを示します.

proof: ${t = \{ \langle x,p \rangle \in u \times \bigcup u\mid p \in x \}}$

に対し, ${t}$ 上の同値関係 ${E}$ を ${\langle x,p\rangle E \langle y,q \rangle}$ を ${x =y}$ として定めます. 実際,反射律、対称律、推移律を満たすので、同値関係になります. この時同値関係の定め方から, ${\emptyset \notin t/E \land a,b \in t/E (a \neq b \to a \cap b = \emptyset)}$ となるので,選択公理より ${c =\{ d \in t \mid \forall a \in t ,c \cap a = \{ d \} \} }$

は集合になる. この時作った ${c}$ から欲しい選択関数 ${f}$ が得らること示す. これは,任意の ${x}$ に対して,ただ一つの ${p}$ が存在し, ${x \in p}$ となればいい. ${t}$ の作り方からもし任意の ${x}$ に対し, ${\langle x,p\rangle \in c}$ となる ${p}$ がただ一つ存在することが言えればよい, それは ${c}$ の定め方から成り立つので、求める選択関数の存在がいえた.

先ほどまでで選択公理に関する準備が終わりました. ここからが本番です, まずは順序数が十分たくさんあることを証明します.

Theorem(ハルトークスの定理)
${a}$ を任意の集合とした時.ある順序数 ${\alpha}$ を一対一の関数 ${f:\alpha \to a}$ が存在しないようにとれる

証明の方針

任意の集合 ${a}$ に対し、その整列可能な部分集合全体 ${w}$ は空集合でない.
${w}$ の元の順序型全体のなす集合は順序数の推移的集合
順序数の推移的集合が順序数であること
順序数から単射があると,その像は整列集合として構造が可能であること
順序数には自身が属さないこと

証明: ${a}$ に対し, ${ w = \{ \langle b,r \rangle \mid b \subset a ,r \subset b \times b}$ , ${r}$ は整列集合を定める関係 ${\} }$

とします.

${w}$ の各元は整列集合なので，それに対応する順序型 ${\mathrm{type}\langle b,r\rangle }$ が存在する.

${w}$ は冪集合の公理と分離公理より直積集合が存在し,そこから制限することで集合であることを示せる. さらに置換公理により

${ \displaystyle q = \{ \mathrm{type}(\langle b,r \rangle)\ \mid \langle b,r \rangle \in w \} }$

は集合になる.さらに,定義から ${ \beta \in q}$ かつ, ${ \gamma \lt \beta}$ なら, ${b}$ の始切片と ${\gamma}$ が同型になるので, ${\gamma \in q}$ となる.よって, ${q}$ は順序数の推移的集合になるので,順序数となる. もし, ${q}$ から ${a}$ への一対一の関数 ${f}$ が存在したとすると,それから ${f``q}$ は ${q}$ のもつ順序構造から誘導される順序構造をいれることで,整列集合となる.この時 ${f``q}$ の順序型は ${q}$ となり,特に ${q \in q}$ となる.これは順序数の性質と矛盾する.よって一対一の関数が存在しない順序数は存在する. ${q.e.d}$

上の定義から,任意の集合に対し,それへの一対一対応が存在しない順序数 ${\alpha}$ の存在が示されました. そこで順序数 ${\alpha}$ の部分集合 ${\beta = \{ x \in \alpha \mid x }$ から ${a}$ への一対一関数が存在しない ${\} }$ は順序数の定義から最小限を持つので,以下が定義できます.

Definition
集合 ${a}$ に対し,一対一の関数 ${f:\alpha \to a }$ が存在しない最小の順序数 ${\alpha}$ を ${\aleph(a)}$ と書き、ハルトークスのアレフという

この章のメインの定理を証明します.

Theorem(ツェルメロの整列定理)
任意の集合は整列順序付け可能である

証明の方針

集合に対し,順序数全体からへの写像で以下を満たすものを超限再帰をもちいて構成する.
1. ${F( \alpha ) \neq stop}$ かつ ${ \beta \lt\alpha}$ の時, ${F(\beta) \neq stop}$
2. ${F(\alpha) \neq stop}$ かつ ${ \beta \lt\alpha}$ の時, ${F(\beta) \neq F(\alpha)}$
3. ある ${\alpha}$ について ${F(\alpha) =stop}$ かつ ${\alpha \lt\beta}$ なら ${F(\beta) = stop}$
4. 3.となる最小の ${\alpha}$ を定義域として制限すると ${f = F \upharpoonright_{\alpha}: \alpha \to a}$ は全射
選択関数から ${ s : \mathcal{P}(a) \setminus \{ \emptyset \} \to a}$ で ${s(b) \in b}$ となるものを構成できる.
関数 ${g: \mathcal{P}(a \cup \{stop\}) \to a \cup\{stop\}}$ を以下で定める.
- ${x \subset \{stop \}}$ となる時 ${g(x) = stop}$
- それ以外の時, ${s(x \setminus \{stop\})}$
超限帰納法から ${F(\alpha) = g( a \cup \{stop\} \setminus F``\alpha )}$ が上の1.~4.を満たす.
1.2.は写像の定義から ${F(\alpha) \notin F``(\alpha) }$ を使うといえる.
3.は存在しないと ${F}$ が単射になることとハルトークスの定理が矛盾
4.は全射でないとすると ${F}$ の定義から ${F(\alpha) \in a}$ となるので矛盾.
ハルトークスの定理から任意の集合 ${a}$ に対し,ある順序数 ${\alpha}$ が存在し, ${a}$ への一対一写像が存在ないものが存在する.

証明集合 ${a}$ が与えられたとする.集合全体は真のクラスになるので. ${a}$ に属さない集合が存在する. 仮にそれを ${stop}$ と名付ける.選択関数の存在から, ${ s : \mathcal{P}(a) \setminus \{ \emptyset \} \to a}$ で ${s(b) \in b}$ となるものが存在する. そこで関数 ${g: \mathcal{P}(a \cup \{stop\}) \to a \cup\{stop\}}$ を以下で定める.

${x \subset \{stop \}}$ となる時 ${g(x) = stop}$
それ以外の時, ${s(x \setminus \{stop\})}$

これを超限再帰を使って ${F(\alpha) = g( (a \cup \{stop\}) \setminus F``a)}$ と定める. この時、この関数 ${F}$ は以下の性質が成り立つ

${F( \alpha ) \neq stop}$ かつ ${ \beta \lt\alpha}$ の時, ${F(\beta) \neq stop}$
${F(\alpha) \neq stop}$ かつ ${ \beta \lt\alpha}$ の時, ${F(\beta) \neq F(\alpha)}$
ある ${\alpha}$ について ${F(\alpha) =stop}$

この時3.より, ${F(\alpha ) = stop}$ となる最小の順序数 ${\alpha}$ が ${\aleph(a)}$ 以下に存在する. ${f = F \lceil_{\alpha} }$ とすると, ${ \beta \in \alpha}$ と ${\beta \lt\alpha }$ は同値なので, fの終域は ${a}$ となる.さらにもし ${\mathrm{rng}(f) \neq a}$ とすると, ${ a \setminus F``\alpha \neq \emptyset}$ なので,特に ${stop}$ の部分集合でないので, ${F(\alpha) = s(a \setminus F'' \alpha) \in a}$ となり, ${F(\alpha) = stop}$ に矛盾する.したがって ${\mathrm{rng}(f) = a}$ であり, ${f}$ は ${a}$ と ${\alpha}$ との間の全単射である. よって ${a}$ は ${f}$ が誘導する順序構造をいれることにより整列順序づけ可能である. ${q.e.d}$

${g}$ の作り方がかなりトリッキーで証明を追えば正しいことは確認できますが、どうやってこれを思いついたのか気になるものですね.

集合の対等生

この章では対等生にまつわる集合の有名な定理を証明します. ベルンシュタインの定理はその中でも最たるものです.

Definition
集合 ${a}$ と集合 ${b}$ に全単射の関数が存在する時, ${a \sim b}$ と書き, ${a}$ と ${b}$ は対等といいます.また集合 ${a}$ から集合 ${b}$ への単射が存在する時, ${a \preceq b}$ と書きます

Theorem
${a \preceq b}$ かつ ${b \preceq a}$ が成立する時 ${a \sim b}$ となる

証明の方針

${f:a \to b,g:b \to a}$ を単射とし, ${a_0 = a,b_0=b}$ とする.
[tex: {a_n = g``b{n-1},b_n = f``a{n-1}}] とする.
${f:a_n \setminus a_{n+1} \to b_{n+1}\setminus b_{n+2}}$ (= a^*)は全単射であり,
逆に ${n \ge 1}$ の時, ${g^{-1} : a_n \setminus a_{n+1} \to b_{n-1} \setminus b_n }$ は全単射となる.の時 ${h(x) = f(x)}$
${x \in a^-}$ の時 ${h(x) = g^{-1}(x)}$
${x \in a^*}$ の時 ${h(x) = f(x)}$
さらに, ${ f : \cap a_n \to \cap b_n}$ は全単射.
上3つをうまく使い ${f: a_{2n} \setminus a_{2n+1} \to b_{2n+2} \setminus b_{2n+1}}$ の全単射と ${g^{-1}:a_{2n+1} \setminus a_{2n+2} \to b_{2n} \setminus b_{2n+1} }$ が全単射を使うことと ${a = \bigcup a_{2n}\setminus a_{2n+1}(= a^+) \cup \bigcup a_{2n+1} \setminus a_{2n+2} (= a^-)\cup \bigcap a_n(= a^*)}$ と分割でき, ${h:a \to b}$ を以下で定める.
${x \in a^+}$ の時 ${h(x) = f(x)}$
${x \in a^-}$ の時 ${h(x) = g^{-1}(x)}$
${x \in a^*}$ の時 ${h(x) = f(x)}$

この時,それぞれが全単射となるので,全体でみて全単射にんる.

Theorem
任意の2つの集合 ${a}$ と ${b}$ に対し, ${a \preceq b}$ か ${b \preceq a}$ か少なくとも一方が成立する.

proof 整列可能定理より ${a}$ と ${b}$ はそれぞれある順序数 ${\alpha,\beta}$ に対し、全単射 ${f:a \to \alpha,g:b \to \beta}$ が存在する. 順序数の場合 ${\alpha \le \beta}$ ならば ${\alpha \subset \beta}$ なので, ${g \circ f^{-1}:a \to b}$ は一対一になる. ${\beta \le \alpha}$ なら ${f \circ g^{-1}}$ が一対一写像になる.

この定理も選択公理が必要.

Lemma
全ての自然数 ${n}$ に対し, ${n \prec n+ 1}$

proof ${n \subset n + 1}$ より, ${ n \preceq n + 1}$ となる. ${ n + 1 \to n }$ で単射となるものが存在しないことを示せばよい. ${ 1 \to 0}$ は射が存在しないので, 成り立つ. ${ m + 1 \to }$ に単射が存在しない仮定して, ${f:m + 2 \to m + 1}$ を任意の関数とする. ${g:m + 1 \to m + 1}$ を ${m}$ と ${f(m + 1)}$ を置換する写像とする.すると ${g}$ は全単射であり, ${f \circ f(m + 1) =m}$ より, ${f}$ が単射と仮定すると, ${g \circ f \upharpoonright_{m + 1} : m + 1 \to m}$ はwell-definedであり,単射となるので,矛盾.

Definition
集合 ${x}$ がある ${\omega}$ の元と対等となる時,有限.有限出ない時無限という

選択公理を認めるとデデキント無限と無限が同値になる. デデキント無限とは自分の真部分集合と全単射が存在すること.

Theorem
すべての集合 ${a}$ に対し, ${a \prec P(a)}$ となる

proof: ${ a \to \mathcal{P}(a),x \mapsto \{x\}}$ は単射なので ${a \preceq \mathcal{P}(a)}$ . ${a \to \mathcal{P}(a)}$ に全射が存在しないことを示せばよい. ${f :a \to \mathcal{P}(a)}$ とし, ${d ~ \{x \in a \mid x \notin f(x)\}}$ とすると. ${ d \in \mathcal{P}(a)}$ であり, ${a}$ の任意の要素 ${x}$ について, ${x \in d \leftrightarrow x \notin f(x)}$ よりある ${x \in a}$ に対し, ${ f(x) = d}$ とすると ${ x \in d =f(x) \leftrightarrow x \notin f(x)}$ となり,矛盾する. よって任意の ${x\in a}$ に対し, ${f(x) \neq d}$ となる.矛盾する.

基数

Definition
集合 ${x}$ と対等な最小の順序数を ${\vert a \vert}$ と書き, ${x}$ の濃度という.

Lemma
次の1)-5)が成り立つ 1) ${ \vert x\vert = \vert y \vert \leftrightarrow x \sim y}$ 2) ${\vert x\vert \le \vert y \vert \leftrightarrow x \preceq y}$ 3) ${\vert x\vert \lt \vert y \vert \leftrightarrow x \prec y}$ 4) 順序数 ${\alpha}$ に対し, ${ \vert \alpha \vert \le \alpha}$ 5) ${ \vert x \vert \lt\aleph(x)}$

proof

1) ${x\sim \vert x \vert = \vert y\vert \sim y}$ より→は言える。逆は明らか. 2) ${\vert x \vert \le \vert y\vert}$ なら ${ \vert x \vert \subset \vert y \vert}$ なので, ${x \preceq y}$ となる.逆に ${ \vert y\vert \lt\vert x \vert}$ とすると, ${x}$ から ${y}$ への単射存在ない.もし存在したとすると ${\vert x \vert }$ から ${\vert y\vert}$ への単射が存在し,仮定に矛盾するので. 3) 1),2)ｊから明らか 4)濃度の定義から言える. 5) ${\aleph(x)}$ から ${x}$ への単射が存在しないので,逆に ${x}$ から ${\aleph(x)}$ への単射が存在するので言える.

Definition
基数とは自分より真に小さい順序数と対等にならない順序数のことである.

Lemma
次の1)-5)が成り立つ 1) 自然数は全て基数 2)最初の無限順序数 ${\omega}$ は基数 3) 基数ばかりを要素とする集合 ${u}$ の最小上界 ${\mathrm{sup}u}$ は基数 4) 全ての集合 ${x}$ に対し, ${\vert x\vert}$ は基数である. 5) 全ての集合 ${x}$ に対し, ${\aleph(x)}$ は基数である.

proof 1) ${ n \preceq n+1}$ より, ${n+1}$ から ${n}$ への一対一の関数は存在せず, ${n+1}$ からそれ未満の自然数への全単射も存在しないので,基数 2)もし ${n \in \omega}$ と対等とすると ${n}$ から ${n+1}$ への単射が存在し, ${n+1}$ から ${\omega}$ への単射が存在することからベルンシュタインの定理で ${n+1}$ と ${\omega}$ が対等となり, ${n}$ と ${n+1}$ が対等となるので,矛盾. 3) ${u}$ に極大元が存在していた場合は明らか, ${u}$ に極大元が存在していないとする.もし, ${\mathrm{sup}u}$ が基数でないとすると,ある順序数 ${\alpha \lt\mathrm{sup}u}$ と対等になっている.それはsupは最小上界なので ${\alpha}$ は上界でなく,つまり.ある ${\beta \in u}$ に対し, ${\alpha \le \beta}$ となる.この時,最大元が ${u}$ に存在してないので, ${\beta}$ より真に大きい ${\gamma}$ が存在する.この時 ${\gamma \lt\mathrm{sup}u}$ と ${\mathrm{sup}u \preceq \beta}$ からベルンシュタインの定理より, ${\gamma}$ と ${\beta}$ が同型となり矛盾する. 4)濃度の最小性から従う. 5)ハルトークスのアレフの定義から ${x}$ より真に大きい最小の順序数なので,最小性から基数になる.

ハルトークスのアレフは順序数 ${\alpha}$ に対し,それより真に大きい最小の

Lemma
1)基数 ${\alpha}$ と順序数 ${\beta}$ について ${\vert \beta\vert \lt\alpha }$ なら ${\beta \lt\alpha}$ である 2)順序数 ${\alpha}$ と ${\beta}$ に対し, ${\alpha \sim \beta}$ と ${\vert \alpha\vert \le \beta \lt\alpha^+}$ は同値である.

proof 1)は ${\alpha}$ は基数なので, ${\vert b\vert \preceq \alpha}$ となる.よって ${\vert \beta\vert}$ と対等な順序数は全て ${\alpha}$ より真に小さい. 2) ${\alpha \sim \beta}$ なら明らかに成り立つ.逆に ${\vert \alpha\vert \le \beta \lt\alpha^+}$ とすると,もし ${\vert \alpha\vert \lt\vert \beta\vert}$ とすると, ${\alpha^+}$ が ${\alpha}$ より大きい最小の基数であることに矛盾する.よって, ${\vert \alpha\vert = \vert \beta\vert}$ となり, ${\alpha \sim \beta}$ となる.

Lemma
無限基数は極限順序数である

Proof 無限順序数 ${\alpha}$ に対し, ${S(\alpha) = \alpha \cup \{\alpha\}}$ と ${\alpha}$ が対等であることを示せば良い. ${f:S(\alpha) \to \alpha}$ を以下で定める.

${\xi = \alpha}$ の時, ${f(\xi)=0}$
${\xi \lt\omega }$ の時, ${f(\xi)=\xi + 1}$
${\omega \le \xi \lt\alpha}$ の時 ${f(\xi) = \xi}$

とするとこれは全単射なので, ${S(\alpha) \sim \alpha}$ となる.

Definition
全ての順序数 ${\alpha}$ に対し, ${\aleph_{\alpha}}$ を以下のように超限再帰で定める. 1) ${\aleph_0 = \omega }$ 2) ${\aleph_{\alpha+1} = (\aleph_{\alpha})^+}$ ${\alpha}$ が極限順序数である時, ${\aleph_{\alpha} = \mathrm{sup}\{\aleph_{\beta} \mid \beta \lt \alpha \} }$

Lemma
集合 ${x}$ が有限でなければ ${\omega \preceq x}$ したがって, ${\aleph_0 \le \vert x\vert}$ である.

proof

集合 ${x}$ の整列順序付け ${\lt_r}$ が存在するので, ${(x,\lt_r)}$ の順序型を ${\delta}$ とする. ${\delta \lt\omega}$ なら ${\delta \sim x}$ は有限になる.なので ${x}$ が有限でない時 ${\omega \le \delta}$ となる. ${\omega}$ は基数なので, ${\aleph_0 \le \vert x\vert}$ となる.

この定理は集合の整列順序可能性を用いるので,選択公理を使う.

Lemma
1) 全ての ${\aleph_{\alpha}}$ は無限基数 2) ${\alpha \lt\beta}$ と ${ \aleph_{\alpha} \lt\aleph_{\beta}}$ は同値無限基数は全てなんらかの ${\alpha}$ について ${\aleph_{\alpha}}$ となる.

Proof 1) ${\omega}$ が無限基数であることと,順序数 ${\alpha}$ に対し, ${\alpha^+}$ が基数となることと、基数のなす集合の ${\mathrm{sup}}$ が基数であることから,超限帰納法で示せる. 2) ${\aleph_{\alpha} \lt\aleph_{\alpha + 1}}$ から超限帰納法で示せる. 3)無限基数 ${\kappa}$ に対し, ${\alpha = \{\beta \mid \alpha_{\beta} \lt\kappa \}}$ とする. この時 ${\alpha}$ は順序数の推移的集合になるので,順序数であり, ${\alpha \notin \alpha}$ となるので, ${\aleph_{\alpha} \ge \kappa}$ となる. もし ${\alpha=0}$ なら, ${\kappa}$ は最小の無限基数 ${\omega}$ であり, ${\kappa=\aleph_{0}}$ である. ${\alpha= \beta + 1}$ なら, ${\aleph_{\beta} \lt\kappa}$ であり, ${\aleph_{\alpha} = \aleph_{\beta}^+ \ge \kappa}$ より, ${+}$ の最小性から ${\kappa = \aleph_{\alpha}}$ となる. もし ${\alpha}$ が極限順序数なら ${ \aleph_{\alpha}\ge \kappa \ge \mathrm{sup}\{\aleph_{\beta} \mid \beta \lt\alpha\}=\aleph_{\alpha} }$

なので, ${\kappa = \aleph_{\alpha}}$ となる.

Definition
無限基数 ${\kappa}$ は ${\lambda^+}$ とかける時, 後続型基数と呼ばれ,そうでない時極限基数と呼ばれる

定義から全ての順序数 ${\alpha}$ に対し, ${\aleph_{\alpha}}$ は無限基数であり,( ${\alpha > 0}$ の時) ${\aleph_{\alpha}}$ が後続型基数であることと ${\alpha}$ が後続型順序数であることは同値. ${o}$ は後続とも極限とも言いづらいものである.

Definition
基数 ${\alpha,\beta}$ に対し, ${(\alpha \times \{0\}) \cup (\beta \times \{1\})}$ の濃度を ${\alpha + \beta}$ と定める.また,直積集合 ${\alpha \times \beta}$ の濃度を積 ${\alpha \beta}$ として定める

以降では基本的には基数としての演算を扱うが,順序数としての演算と区別するときは ${+_c}$ などとかく.

Lemma
任意の順序数 ${\alpha,\beta}$ について 1) ${\vert \alpha +_o \beta\vert = \vert \alpha\vert +_c \vert \beta \vert}$ 2) ${\vert \alpha\cdot_o \beta \vert = \vert \alpha\vert \cdot_c \vert \beta\vert}$

Lemma
基数 ${\alpha,\beta,\gamma}$ について次のことが成り立つ.和と積はいずれも基数の演算の意味で考える 1) ${(\alpha + \beta) + \gamma = \alpha + (\beta + \gamma),(\alpha \beta) \gamma = \alpha(\beta \gamma)}$ 2) ${\alpha + \beta = \beta + \alpha ,\alpha \beta = \beta \alpha}$ 3) ${\alpha(\beta + \gamma) = (\alpha \beta) + (\alpha \gamma )}$ 4) ${\alpha + 0 = 0 + \alpha = \alpha, 1 \alpha = \alpha 1 = \alpha }$ 5) ${0 \alpha = \alpha 0 = 0}$ 6) ${\alpha \le \beta}$ の時, ${\alpha + \gamma \le \beta + \gamma}$ かつ ${\alpha \gamma \le \beta \gamma}$

Lemma

基数 ${\alpha,\beta,\gamma}$ について次のことが成り立つ.和と積はいずれも基数の演算の意味で考える
1) ${(\alpha + \beta) + \gamma = \alpha + (\beta + \gamma),(\alpha \beta) \gamma = \alpha(\beta \gamma)}$
2) ${\alpha + \beta = \beta + \alpha ,\alpha \beta = \beta \alpha}$
3) ${\alpha(\beta + \gamma) = (\alpha \beta) + (\alpha \gamma )}$
4) ${\alpha + 0 = 0 + \alpha = \alpha, 1 \alpha = \alpha 1 = \alpha }$
5) ${0 \alpha = \alpha 0 = 0}$
6) ${\alpha \le \beta}$ の時, ${\alpha + \gamma \le \beta + \gamma}$ かつ ${\alpha \gamma \le \beta \gamma}$

proof 全て具体的に全単射を構成すればいい. 1) ${f: (\alpha \times \{0\} \cup \beta \times \{ 1\} ) \times \{ 0\} \cup \gamma \times \{1\} \to \alpha \times \{0\} \cup (\beta \times \{0\} \cup \gamma \times \{1\}) \times \{1\} }$

を ${(a,0,0) \mapsto (a,0),(b,1,0) \mapsto (b,0,1),(c,1) \mapsto (c,1,1)}$ とすればよい. 他も同様.

Definition
順序数の順序対 ${\langle \alpha_0.\alpha_1 \rangle}$ と ${\langle \beta_0.\beta_1 \rangle}$ に対して, ${\langle \alpha_0,\alpha_1 \rangle \lhd_2 \langle \beta_0.\beta_1 \rangle \leftrightarrow^{def}}$ ${ \mathrm{max}\{\alpha_0,\alpha_1\} \lt\mathrm{max}\{\beta_0.\beta_1\} \lor (\mathrm{max}\{\alpha_0,\alpha_1\} = \mathrm{max}\{\beta_0,\beta_1\} \land (\alpha_0 \lt\beta_0 \lor( \alpha_0 = \beta_0 \land \alpha_1 \lt\beta_1) ))}$ と定める

Definition

順序数の順序対 ${\langle \alpha_0.\alpha_1 \rangle}$ と ${\langle \beta_0.\beta_1 \rangle}$ に対して, ${\langle \alpha_0,\alpha_1 \rangle \lhd_2 \langle \beta_0.\beta_1 \rangle \leftrightarrow^{def}}$
${ \mathrm{max}\{\alpha_0,\alpha_1\} \lt\mathrm{max}\{\beta_0.\beta_1\} \lor (\mathrm{max}\{\alpha_0,\alpha_1\} = \mathrm{max}\{\beta_0,\beta_1\} \land (\alpha_0 \lt\beta_0 \lor( \alpha_0 = \beta_0 \land \alpha_1 \lt\beta_1) ))}$ と定める

Lemma
二項関係 ${\lhd_2}$ は ${\mathrm{Ord} \times \mathrm{Ord}}$ の整列順序付けであり,各順序数 ${\alpha}$ について ${\langle \alpha \times \alpha \rangle,\lhd_2)}$ は ${(\mathrm{Ord}\times \mathrm{Ord}.\lhd_2)}$ の始切片である

Proof 真クラスに対する整列順序付けの細かいことはひとまず気にしない. 整列順序付けであることを示すために以下を示す

${\langle \alpha_0,\alpha_1 \rangle \not\lt \langle \alpha_0,\alpha_1 \rangle}$ 定義から言える
${\langle \alpha_0,\alpha_1 \rangle \lt\langle \beta_0.\beta_1 \rangle,\langle \beta_0,\beta_1 \rangle \lt\langle \gamma_0,\gamma_1 \rangle}$ なら ${\langle \alpha_0,\alpha_1 \rangle \lt\langle \gamma_0,\gamma_1 \rangle}$ これも具体的に試せばよい.
三分率,従う.

そのため,整列順序付けになっていることを示せば良い.

始切片が集合?
集合 ${u \subset \mathrm{Ord} \times \mathrm{Ord}}$ が ${\lhd_2}$ で最小限を持てばよい.

${u}$ に対し ${\beta = \mathrm{min}\{ \mathrm{max}\{\alpha_0,\alpha_1\} \mid \langle \alpha_o,\alpha_1 \rangle \in u \} }$ とした時(これは整列集合なので ${\mathrm{min}}$ が存在することから言える), ${v = \{ \langle \alpha_0,\alpha_1 \rangle \mid \mathrm{max}\{\alpha_0 ,\alpha_1\} = \beta\}}$ とし,同様に ${\beta}$ の中で ${\alpha_0}$ が最小になるもの全体を ${w}$ とし, ${w}$ の元で ${\alpha_1}$ が最小となる元 ${\gamma}$ は ${u}$ の最小元になるので,示せた. また, ${\langle \alpha_0,\alpha_1 \rangle \lhd_2 \langle 0,\alpha \rangle}$ は ${0}$ の最小性から ${\mathrm{max}\{\alpha_0,\alpha_1\} \lt\alpha}$ つまり, ${\langle \alpha_0,\alpha_1 \rangle \in \alpha \times \alpha}$ と同値になる.よって ${\alpha \times \alpha}$ は ${\mathrm{seg}(\mathrm{Ord} \times \mathrm{Ord},\lhd_2,\langle 0,\alpha \rangle)}$ と一致する.

Theorem
任意の無限基数 ${\kappa}$ について,基数の演算の意味で ${\kappa \kappa = \kappa + \kappa = \kappa}$ となる.

証明順序数 ${\alpha}$ に対し,整列集合 ${\langle \alpha,\alpha \rangle ,\lhd_2}$ の順序型を ${\tau_2(\alpha)}$ とかくと,

${\tau_2(0)=0}$
${\tau_2(\alpha + 1) = \tau_2(\alpha) + \alpha + \alpha + 1 }$
${\alpha}$ が極限順序数の時, ${\tau_2(\alpha) = \mathrm{sup}\{ \tau_2(\beta) \mid \beta \lt\alpha\}}$

となる. これは ${\alpha \times \alpha}$ が ${\langle (0,\alpha) \rangle}$ の始切片であることから, ${\alpha + 1 \times \alpha + 1}$ は ${\alpha \times \alpha}$ から ${\{ \langle \xi,\alpha \rangle \mid \xi \lt\alpha\}}$ の要素が ${\xi}$ の小さい順に ${\alpha}$ 個並び, ${\{\langle \alpha,\xi \rangle \mid \xi \le \alpha\}}$ が ${\alpha + 1}$ 個並ぶことからわかる. 定義から ${\tau_2(\alpha) \sim \alpha \times \alpha}$ なので,全ての無限基数について ${\tau_2(\kappa) = \kappa}$ が言えればよい. まず任意の順序数に対し, ${\tau_2(\alpha) \ge \alpha}$ となる. ${n \lt\omega}$ の時,[tex: {\tau_2(n) = n²}] より, ${\tau_2(\omega)= \omega}$ となる. ${\kappa}$ を ${\omega}$ より真に大きい基数として, ${\kappa}$ 未満のすべての無限基数 ${\delta}$ に対し, ${\tau_2(\delta) = \delta}$ が成立していると仮定する. すると,順序数 ${\alpha}$ には ${\tau_2(\alpha) \sim \alpha \times \alpha \sim \vert \alpha\vert \times \vert \alpha\vert \sim \tau_2(\vert\alpha \vert)}$ となるので, ${\alpha}$ が ${\kappa}$ 未満の無限順序数の場合,帰納法の仮定から ${\vert \tau_2(\alpha)\vert = \vert \tau_2(\vert \alpha\vert)\vert = \vert \alpha\vert \lt\kappa}$ となる. このことから, ${\kappa \ge \mathrm{sup}\{\tau_2(\alpha) \mid \alpha \lt\kappa\}}$ となるので, ${\tau_2(\kappa) = \kappa}$ となる.

連続体仮説

${^{a}b = \{f:f:a \to b\}}$ とかく.

Definition
基数 ${\alpha,\beta}$ に対し, ${\vert ^{\alpha}\beta\vert}$ を基数としての指数関数 ${\beta^{\alpha}}$ と定める.

Lemma
任意の集合 ${x}$ に対し, ${\vert \mathcal{P}(x)\vert = 2^{\vert x\vert}}$

証明 ${ u \subset x}$ に対し,特性関数 ${ \chi_u :x \to \{0,1\}}$ を

${v \in u }$ の時1
${ v \notin u}$ の時0

で定める.すると ${ u \mapsto \chi_u}$ は ${\mathcal{P}(x) \to ^x2}$ を定める. これは全単射である.単射は ${u \neq w \subset x }$ とすると ${ y \in w \setminus u}$ が存在すると思ってよい(必要であれば ${w}$ と ${u}$ を取り替えればよい).この時 ${\chi_u(y) \neq \chi_w(y)}$ となるので,単射となる.全射は ${g \in ^x2}$ に対し, ${g^{-1}(1) = \{ a \in u \mid g(a) = 1 \}}$ を ${u}$ とした時 ${\chi_u = g}$ となるのでいえた.

Lemma
実数全体のなす濃度は ${2^{\aleph_0}}$

proof ${f: \mathcal{P}(\omega) \to \mathbb{R}}$ を ${u \mapsto \sum_{n = 0}^{\infty} \frac{2 \chi_u(n)}{3^n} }$

と定める.すると ${u \neq v \subset \mathcal{P}(\omega)}$ の時, ${(x \in u \land x \notin v) \lor (x \notin u \land x \in v)}$ となる ${x}$ の最小値を ${y}$ とする. 今 ${f(u) \ge f(v)}$ とし ${f(u) -f(v) = \frac{2}{3^y} - \sum_{n=y+1}^{\infty}\frac{2 \chi_u(n) - 2x_{v}(n) }{3^n} }$ であり, ${ \vert\sum_{n=y+1}^{\infty}\frac{2 \chi_u(n) - 2x_{v}(n) }{3^n}\vert \le \frac{1}{3^y}}$ となるので, ${f(u) \neq f(v)}$ となる. 一方で, ${g:[0,1) \to \mathcal{P}(\omega)}$ を ${g(x) = \{ i \in \omega \mid x \cdot 2^{i + 1}}$ の整数部分が奇数 ${ \}}$ と定める.これは単射である.それは,もし ${x > y}$ とすると, ${2^{n+1}(x -y) > 1}$ となる最小の ${n}$ に対し, ${n \in g(x) \leftrightarrow n \notin g(y)}$ より,単射となる.

また, ${\mathbb{R} \to [0,1) , x \mapsto 1/1 + e^{x}}$ が単射なので,ベルンシュタインの定理より, ${\mathcal{P}(\omega) \sim \mathbb{R}}$ よって,実数全体の濃度は ${2^{\aleph_0}}$ となる.

Theorem
全ての基数 ${\kappa}$ 。に対し, ${\kappa \lt2^{\kappa}}$ \|カントールの定理から任意の集合に対し,その冪集合への全射はなく,またうえで示した補題より, ${2^{\kappa} \sim \mathcal{P}(\kappa)}$ から従う.

Statement(連続体仮説)
${\aleph_1 = 2^{\aleph_0}}$

これは示せるのか？？全くわからない!!!!!!!

完結編は6/2,6/3.乞うご期待

2018-04-15

機械学習で読んだ本

機械学習関係で読んだ本とその内容について紹介します. 全部を熟読した本はないのと，私は数学系の人間なので，理論系に厳しいのはご了承ください．

理論系

Understanding Machine Learning:From Theory to Algorithms

Understanding Machine Learning: From Theory to Algorithms

作者: Shai Shalev-Shwartz,Shai Ben-David
出版社/メーカー: Cambridge University Press
発売日: 2014/05/19
メディア: ハードカバー
この商品を含むブログを見る

いくつか見た機械学習の本で一番数学科向けの本です. 比較的定義もしっかりしている.真面目に勉強するならこの本しかないかもしれない.

ただ400ページ以上あるので,適切にトピックを選んだほうがよい気がしているのと, VCDimension等使う際はそこまでという部分はとばしてもいいかもしれません.

パターン認識と機械学習

パターン認識と機械学習上

作者: C.M.ビショップ,元田浩,栗田多喜夫,樋口知之,松本裕治,村田昇
出版社/メーカー: 丸善出版
発売日: 2012/04/05
メディア: 単行本（ソフトカバー）
購入: 6人クリック: 33回
この商品を含むブログ (20件) を見る

とても有名な本ですが，私は最初の一章を読んで，やめました．最初に読む気がなくなったのは過学習の説明です. 過学習は訓練誤差が徐々に落ちるが，評価誤差がどんどんあがる現象という理解です.

これは次数を増やすに連れ,評価誤差がどんどんあがるから過学習だと言っているように読めました．

ここは不満が二つあります. 1つはモデルのとれる場所を途中で変えていること．機械学習はある関数のなす集合から，訓練データに対する誤差を小さくする関数をもとめています. なので,訓練データの点だけに特化しすぎた関数になるのはわかるのですが, 上の説明は関数のなす集合を変更しています.

また,10個の点を通る10時多項式は一意に定まりますが,10個の点を通る100次多項式は一意に定まらないし，なかには評価データに対しても誤差が低いものがあるかもしれません．(私は計算していないので実際はわかりません)

ですが，そうした状況を何1つ考慮せずに断定している状況をみて,この本を読んでも，客観的にそれが正しいか確認できる状態にならず,勉強にならないと思いやめました．細かくはいろいろ不満がありますが，この本で勉強するのをやめた理由はそこです.

Deep Learning

Deep Learning (Adaptive Computation and Machine Learning series)

作者: Ian Goodfellow,Yoshua Bengio,Aaron Courville,Francis Bach
出版社/メーカー: The MIT Press
発売日: 2016/11/18
メディア: ハードカバー
この商品を含むブログ (1件) を見る

2章,3章は私かるすとお気持ちが並んでいるだけに見えたので, 理論的な理解をしたい人は,この本を読む理由はないのかなと思っています. 後ろの方は実用的な話かもしれません.

グラフィカルモデル

グラフィカルモデル (機械学習プロフェッショナルシリーズ)

作者: 渡辺有祐
出版社/メーカー: 講談社
発売日: 2016/04/20
メディア: 単行本（ソフトカバー）
この商品を含むブログ (1件) を見る

Amazonの書評で数学書みたいと書いてあったのをきっかけに前半を読みました. きっちり書いてくれている部分も多いですが, 数学書だと思うと言いたいことは多数あります. 特につらいのは証明が汚いことです.作者は証明を理解しているんだろうかという気持ちになったものも多数あります. (僕がTAで採点しているなら☓にしようかなと思うものが…)

ある程度わかりましたが,今ひとつ消化しきれていないです.

ゼロから作るディープラーニング

ゼロから作るDeep Learning ―Pythonで学ぶディープラーニングの理論と実装

作者: 斎藤康毅
出版社/メーカー: オライリージャパン
発売日: 2016/09/24
メディア: 単行本（ソフトカバー）
この商品を含むブログ (18件) を見る

理論系にならべていいのかわかりませんが，いい本です. 私は実装経験が薄いのでこの本を読んで直接実装したくなりました.

フレームワーク系

詳解ディープラーニング: TensorFlow・Kerasによる時系列データ処理

詳解ディープラーニング　TensorFlow・Kerasによる時系列データ処理

作者: 巣籠悠輔
出版社/メーカー: マイナビ出版
発売日: 2017/05/30
メディア: Kindle版
この商品を含むブログを見る

当時RNNをメインにしっかり扱った本がなかったのでとてもよかったのではないかと思います. とはいえ,私の感覚とコードの命名規則が噛み合っていなかったのでその辺は相性があるかもしれません Tensorflow含めフレームワークはどんどんあたらしくなので,今勧められるかきわどい本です.

TensorFlow機械学習クックブック Pythonベースの活用レシピ60+

TensorFlow機械学習クックブック Pythonベースの活用レシピ60+ (impress top gear)

作者: Nick McClure,株式会社クイープ
出版社/メーカー: インプレス
発売日: 2017/08/14
メディア: 単行本（ソフトカバー）
この商品を含むブログ (1件) を見る

Tensorflowの写経用の本として便利. プログラミングに慣れていない人の場合は,これを写経しながら実際書いてみて挙動を理解する方がよいかもしれません.

将棋AIで学ぶディープラーニング

作者: 山岡忠夫
出版社/メーカー: マイナビ出版
発売日: 2018/03/14
メディア: 単行本（ソフトカバー）
この商品を含むブログ (2件) を見る

Chainerと強化学習が知りたくて購入しました. とても面白そうな気配がするのですが，現状ほとんとChainerも強化学習も使っていないということで後回しになっています.時間を作って読みたいものです.

ビジネス系

仕事で始める機械学習

仕事ではじめる機械学習

作者: 有賀康顕,中山心太,西林孝
出版社/メーカー: オライリージャパン
発売日: 2018/01/16
メディア: 単行本（ソフトカバー）
この商品を含むブログ (5件) を見る

とりあえず,一読しておくべき本. 実際にデータを集めて,モデリングする時とうまくいかなくておとしどころを考えるべき時に効果を発揮します.

応用系

深層学習による自然言語処理

深層学習による自然言語処理 (機械学習プロフェッショナルシリーズ)

作者: 坪井祐太,海野裕也,鈴木潤
出版社/メーカー: 講談社
発売日: 2017/05/25
メディア: 単行本（ソフトカバー）
この商品を含むブログ (1件) を見る

Word2VecからメモリネットワークまでDeepLearningで行われている基本的な部分は網羅されています. 自然言語で一番しっかり書いてくれている本だと思いますが，数学の扱いはまだまだ不十分だなと思うことも多いです.

トピックモデル

トピックモデル (機械学習プロフェッショナルシリーズ)

作者: 岩田具治
出版社/メーカー: 講談社
発売日: 2015/04/08
メディア: 単行本（ソフトカバー）
この商品を含むブログ (2件) を見る

トピックモデルを中心にベイズ推定や変分近似について丁寧に書いてある本ベイズ推定のいい勉強になると思います.

生命情報処理における機械学習多重検定と推定量設計

生命情報処理における機械学習多重検定と推定量設計 (機械学習プロフェッショナルシリーズ)

作者: 瀬々潤,浜田道昭
出版社/メーカー: 講談社
発売日: 2015/12/09
メディア: 単行本（ソフトカバー）
この商品を含むブログ (1件) を見る

生命情報をベースに統計(仮説検定)を紹介した本．あまりちゃんと読めていませんが，丁寧にまとまっている印象です. 生物系をやろうと思っているならよい本です.

2018-04-13

Matplotlibの使い方

matplotlib 機械学習

機械学習の結果を表現するのにいろいろな二次元のグラフを使うのが便利なので, 起勉強しながら記事にしてみました．

Matplotlibの描き方

描画は以下の順に行います.

figure関数でFigureオブジェクトを作成
FigureオブジェクトからAxesオブジェクトを作成
Axesオブジェクトからデータをプロット
実際に描写

本当に簡単なコードにしてみました．

import matplotlib.pyplot as plt
plt.style.use("ggplot")

##### 1. figure関数でFigureオブジェクトを作成
fig = plt.figure()
print(type(fig))

##### 2. FigureオブジェクトからAxesオブジェクトを作成
ax = fig.add_subplot(111)
print(type(ax))

##### 3. Axesオブジェクトからデータをプロット
ax.plot([0,1,2],[0,2,4])

### 実際に描写
plt.show()

出力はこんな形です．

<class 'matplotlib.figure.Figure'>
<class 'matplotlib.axes._subplots.AxesSubplot'>

f:id:padic-aririri:20180413215639p:plain

plotの入力はArrayクラス,numpy.ndarray,pandas.Seriesクラス等が受け取れます. これで最低限書き方のイメージはつかめました．とはいえグラフはこれだけでは終わりません.

グラフを作る時考えるのは - データ以外をどうするとすぐわかるか - 何グラフで描画するかかなと思います.

これらについての設定方法を説明しておきます.

グラフの種類

散布図
折れ線
箱ひげ図
ヒストグラム
円グラフ

先程はplotでしたが,これらの図に合わせて使うメソッドが違います

関数	図の種類
scatter()	散布図
plot()	折れ線
boxplot()	箱ひげ図
hist()	ヒストグラム
pie()	円グラフ

メソッドの詳細は公式ページやここをみるとわかりやすいと思います.

データ以外の作成方法

グラフの見た目を改善するということで思い浮かんだのは以下でした.

文字
軸の名前
タイトル

これらについて具体的に説明します.

文字

import matplotlib.pyplot as plt
fig = plt.figure()
ax1 = fig.add_subplot(331)
ax2 = fig.add_subplot(332)
ax3 = fig.add_subplot(333)

for i ,ax in enumerate([ax1,ax2,ax3],start = 1):
    txt = "ax{0}\n(33{0})".format(i)
    ax.text(0.2,0.4,txt,fontsize=12)
plt.show()

f:id:padic-aririri:20180413215855p:plain

軸の名前

軸を設定するにはset_xlabel.set_ylabelを使えばできます.,

import matplotlib.pyplot as plt
fig = plt.figure()
ax = fig.add_subplot(111)
ax.plot([1,4,3],[0,1,4],label="sample")
ax.set_xlabel("x-layer")
ax.set_ylabel("y-layer")
plt.show()

f:id:padic-aririri:20180413220818p:plain

グラフ/線のタイトル

グラフのタイトルはplt.title()で設定できます. 線のタイトルはplot()の引数にlabel=として設定してできます. ax.legend()をすることでラベルが具体的に見えます.

plt.style.use("ggplot")
fig = plt.figure()
ax = fig.add_subplot(122)
x = np.linspace(0,2.0,100)
y = np.exp(x)
z = np.sin(x * np.pi )

ax.plot(x,y,label="exp")
ax.set_xlabel("x-layer")
ax.set_ylabel("y-layer") 
ax.plot(x,z,label="sin")
ax.set_title("Graph Title")
ax.legend()
bx = fig.add_subplot(121)
bx.hist(y,label="sinhist",bins=20)
bx.set_title("hist")
plt.show()

f:id:padic-aririri:20180413222535p:plain

基本編は以上です．複雑なことはこれから鍛えていこうと思います．

2018-04-12

陰関数定理

math 微分

最適化を考える時に陰関数定理とラグランジュの未定乗数法を考える事が多いので，これらについて紹介したいと思います.

今回は二変数の場合の陰関数定理について紹介します.

定理
${F: \mathbb{R}^2 \to \mathbb{R}}$ が ${F(x_0,y_0)=0}$ を満たし, ${(x_0,y_0)}$ の近傍 ${U}$ で微分可能で ${x,y}$ ともに偏微分が連続で, ${\frac{\partial F(x_0,y_0)}{\partial y} \neq 0}$ とする.この時,ある ${x_0}$ の開近傍 ${V}$ 上定義され， ${f(x_0) = y_0}$ となる関数 ${f:V \to \mathbb{R}}$ で,任意の ${a \in V}$ 上, ${F(a,f(a)) = 0}$ を満たすものが存在する.

定理

${F: \mathbb{R}^2 \to \mathbb{R}}$ が ${F(x_0,y_0)=0}$ を満たし, ${(x_0,y_0)}$ の近傍 ${U}$ で微分可能で ${x,y}$ ともに偏微分が連続で, ${\frac{\partial F(x_0,y_0)}{\partial y} \neq 0}$ とする.この時,ある ${x_0}$ の開近傍 ${V}$ 上定義され， ${f(x_0) = y_0}$ となる関数 ${f:V \to \mathbb{R}}$ で,任意の ${a \in V}$ 上, ${F(a,f(a)) = 0}$ を満たすものが存在する.

これを証明します.存在を示すので,具体的に構成できればよいわけです.

まず偏微分が連続であることと, ${ (x_0,y_0)}$ の近傍で微分可能であることから, ${ (x_0,y_0)}$ を含む ${ \mathbb{R}^2}$ の開近傍 ${ U'}$ 上で, ${ (x',y') \in U'}$ に対し, ${ \frac{\partial F(x',y')}{\partial y}}$ は符号が全て同じとなるものが存在します. 符号はひとまず正とします.(負の場合は ${ -F}$ をとればよいです)

これにより, ${ y \lt y_0}$ 上, ${ F(x_0,y) \lt 0 }$ となり,逆に ${ y>y_0}$ 上 ${ F(x_0,y) > 0}$ となります. ${ F}$ の連続性から，十分小さい開近傍を取ると, ${ y > y_0}$ で, ${ 0 \lt F(x_0,y)}$ と ${ F(x,y)}$ は符号が変わらず， ${ y \lt y_0}$ でも同様となります.そのため, ${ x}$ を固定すると ${ \frac{\partial F(x,y)}{\partial y}}$ は単調増加で符号が変わることから,任意の ${ x}$ に対し,ただ1つの ${ F(x,y)=0}$ となる ${ y}$ が存在することがわかります.