ロジスティック回帰
当たり前のようで、何を言ってるかよくわからない部分があったので、調べなおしてみました。
二値分類
まずは一番簡単な二値分類の場合のロジスティック回帰について説明します.
とする. これに対して,ある を用意する. 例えば自然言語処理だと,単語の分散表現等 そして、 を用いて,
と定めます.これは2つの事象 と となる確率が合計1であることから、 上の確率(測度)を定めます. ですが、これは適当な確率であって、我々が本当に知りたい。 に対して、そのラベルが である確率を表しているわけてはありません.
そうすると上の式でできる限り,我々の知りたい確率に近づくようにとりたくなります.
このために,データの中で に対し に対して, にできるだけ近づけるようにパラメータ を取りかえるというアイデアを採用します. なので,損失関数 として,これが最小になる を求めます。
こうやって確率を内部で求めるので回帰と名付けられているわけですが、実際に問題を解く場合はその確率が一定の値以上の場合は1,そうでない場合は-1と分けるので,二値分類になります.
パラメータの変更は例えば確率的勾配降下等で計算するのが速く、実用的になっているようです. また、損失関数も今のままの は過学習しやすい傾向があることが多く、経験的に、正則化項と呼ばれる項 等を加えるとよいようです.
余談
実際こうした方法の特徴はなんでしょうか。例えばSVMのような直線を引くのとどちらがわかりやすいのか... 指数関数を使うので、外れ値を無視しやすいとかそういう傾向があったりしないんでしょうかね。
多値分類
多値の場合も実質二値分類と同じです. 先ほどは 上の確率分布だったのを適当に 上の確率分布だと思って求めればよいです.
その場合は
とします. です. 後は損失関数も全て同じです.
ACL読み回2018
ACLの読み回に参加してきました.
感想を三行でまとめると
- NLP界隈の常識がわかる
- 発表者の疑問がわかる
- 数式はお気持ち
NLP界隈の常識がわかる
一人でやっているのでは伝わらない当たり前の知識が伝わるのがとてもよかったです. Seq2Seq + Attentionがデファクトスタンダードだけれど、 - 未知語が対処できない - 同じものが複数回生成される という課題があり,それらにどう対応するかが考えられている.
とはいえ、ネットワークを劇的に改善させるというよりは - ドキュメントっぽさ.前の文章の情報を加える. - 意味っぽい情報を加える
というのが基本で、劇的に新しい手法はなさそう.Transofomerも出てきたけど、あまりそれを使っていない模様.
相変わらずデータが重要で、分散表現等を工夫する余地はまだまだあるのだなという風に感じた.
自分がよく知らないけど、当たり前っぽい用語がたくさん出てきたのもよい. 文章要約のROUGEは自分はまだあまりなじみがないけれど、覚えておくべきだと思ったし,NLPの人と関わりの薄い自分からすると,聞いたことがあるという感覚自体に意味があると思った次第です。
発表者の疑問がわかる
何故ここで検証していないのか,解釈できない.そもそもこれは悪手なのではという点を説明していて,それを適切に議論できるのはとてもよい.
特に一番最後のベストペーパーについての解説が, これ課題に対応していないからおかしくないか?やこの課題の正答率低すぎないか?に対していろいろ見解を述べていて,そこにはアイデアが新規である分,完成度の低さを感じれたし.やっぱりお気持ちだから曖昧になるのだなと思うこともわかった.
数式はお気持ち
皆思い思いに絵をかいたり数式を書いてるけど、どう考えてもその辺に対して曖昧さがあるなあと思うなど.
なんというか、私は数学的なものは数学的なレイヤーで思考できるので、その観点で問題ないかや何を意味しているかをチェックするのだけれど,皆その辺は何もしていないのだろうなと思った.
「微分できない」、何から何の関数だと思ったときに〇〇だから微分できないって思うの20秒もかからないと思うのだけれど、そういうのは説明されないし,気にならないし、気にしていないのだろうなあ。 実際実装はそれらのお気持ちを反映してNNで数式ときちんと対応しているのかもきわどいところなので.
逆に言うと,皆機械学習ですらなく自然言語処理のレイヤーで思考していた. 具体的には言語の処理固有の課題を見つけ,それに対応する何かを加えるというアイデアが基本で,適当に実装してみて一番よかったのをみると、こんな感じという主張にも見えた.
その辺実際どの程度理解しているのか突っ込んで聞いてみたくも思ったけど、今回はまだまだ知らない人ばっかりだったので、諦めた.
理解の仕方の違いでもあるので、質問しまくっても問題ない人を見つけてどう理解しているのかどうしてもそこは問題ないと思うのかを徹底的に議論したいなあと思うなど.
具体的な話
資料はここ
今日聞いていても一番思ったのはこれ
論文に対して自分の感想を書く程でもなく 資料によく書かれていると思ったので、今回は割愛します。
発表してくださった方々、企画してくださった方々ありがとうございました。
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 の数列は全部で nm 通り存在します。 この nm 通りの数列すべてに対して美しさを求めて、 それらの平均を出力してください。
制約
- 0 ≤ d <n≤109
- 2≤m≤109
- 入力はすべて整数
解答
美しさが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≤105
- 1≤m≤105
- 1≤s,t≤n
- s≠t
- 1≤ui<vi≤n1≤ai,bi≤109
- 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.をキューがなくなるまで実施する。
こうなることで最短の経路を求められ、かつ無駄な操作はあまりないというものになります。
基数の理論
これは,数学カフェ基礎論回の 予習回第6回の講演内容のメモです.
このセミナーの最終目標は連続体仮説がZFCと独立であることの証明です。 今回は連続体仮説が何を主張しているかを理解することを目指して解説します.
連続体仮説の主張は以下のようなものでした.
Statement(連続体仮説) |
---|
ここで出てくる は基数です. 基数は順序数であり,また加法,乗法,指数関数が定義できます. 上で現れる は基数 と2の定める指数関数です.
さて,任意の整列集合はあるただひとつの順序集合と順序同型であり,その意味で順序数は整列集合としての代表元を定めたものでした. 基数は整列集合ではなく,集合の代表元を定めたものとなります. 集合の代表元を定めるには集合としての構造が等しいことを定義する必要があります. とはいえ集合には他に構造もないので全単射が存在することで集合として"等しい"ことを定めます. 集合はその集合の濃度を取るという操作によって,集合の代表元として基数を定めることになります. 基数は順序数なので.集合の大小関係を記述するためにも使えます. 一方で順序同型の場合は順序数の大小がそのまま、順序同型の有無に影響していましたが、 集合として考える場合は、順序数としては,真に大きい順序数であっても集合として同型になる場合があります。 そこで、我々は集合として同型になる順序数の中で最小なものとして、基数を定義します.
今回は基数と集合の関係を述べ,その基数との関係が理解するために必要な集合上の操作と 連続体仮説を理解するのに必要な基数の定義や操作を説明します. 具体的には
- 全ての集合が整列順序づけ可能であること
- 集合の対等性を定義し,集合の対等生に関するベルンシュタインの定理、カントールの定理を証明する
- 基数を順序数の対等類の最小要素として定義する
- 基数の加法と乗法を定義し,性質を調べる.
- 基数の指数関数を定義し,連続体仮説の主張を述べる.
実際に独立性証明のためには連続体仮説の主張を理解するだけでなく,絶対性や強制法等の議論が必要です.そこは本番に期待したいと思います。
全ての集合が整列順序づけ可能であること
全ての集合が整列順序づけ可能であることはツェルメロの定理と呼ばれています。 この章ではその定理の証明をします。 また、今までは選択公理はあまり仮定されていませんでしたが、 この章では選択公理を使います
そのため、最初に選択公理について確認し、我々が仮定した選択公理から選択関数が存在すること およびその時に使われる商集合について言及したいと思います.
Definition |
---|
集合上の関係が 同値関係 であるとは,以下を満たすことである. 1) 2) 3) |
同値関係の重要なところは商集合が定義できるところです
Definition |
---|
上の同値関係に対し、は集合となり、それを 商集合 と呼ぶ |
上の定義には同値関係が必要ありません。関係であることと冪集合公理と分出公理だけから集合の存在を示すことができます. しかし,同値関係による商集合には以下が成りつという特徴があります.
商集合
は元の集合
の分割になっている。すなわち、以下が成り立つ.
1)
2)
に対し,
3)
ここから、以下が従います.
さて、我々が採用した選択公理のStatemnetは以下でした.
Axiom of Choice |
---|
これは先程の商集合の性質と照らし合わせると、 というある同値関係で割られた商集合には,その完全代表系のなす集合が存在するという意味になります.
この命題は商集合側でとっていますが,実際使う際は以下の選択公理と同値な定理として使われることが多いです.
Theorem |
---|
ひとまず,選択公理から上の定理が従うことを示します.
proof:
に対し, 上の同値関係 を を として定めます. 実際,反射律、対称律、推移律を満たすので、同値関係になります. この時同値関係の定め方から, となるので,選択公理より
は集合になる. この時作った から欲しい選択関数 が得らること示す. これは,任意の に対して,ただ一つの が存在し, となればいい. の作り方からもし任意の に対し, となる がただ一つ存在することが言えればよい, それは の定め方から成り立つので、求める選択関数の存在がいえた.
先ほどまでで選択公理に関する準備が終わりました. ここからが本番です, まずは順序数が十分たくさんあることを証明します.
Theorem(ハルトークスの定理) |
---|
を任意の集合とした時.ある順序数を一対一の関数が存在しないようにとれる |
証明の方針
- 任意の集合 に対し、その整列可能な部分集合全体 は空集合でない.
- の元の順序型全体のなす集合は順序数の推移的集合
- 順序数の推移的集合が順序数であること
- 順序数から単射があると,その像は整列集合として構造が可能であること
- 順序数には自身が属さないこと
証明: に対し, , は整列集合を定める関係
とします.
の各元は整列集合なので,それに対応する順序型 が存在する.
は冪集合の公理と分離公理より直積集合が存在し,そこから制限することで集合であることを示せる. さらに置換公理により
は集合になる.さらに,定義から かつ, なら, の始切片と が同型になるので, となる.よって, は順序数の推移的集合になるので,順序数となる. もし, から への一対一の関数 が存在したとすると,それから は のもつ順序構造から誘導される順序構造をいれることで,整列集合となる.この時 の順序型は となり,特に となる.これは順序数の性質と矛盾する.よって一対一の関数が存在しない順序数は存在する.
上の定義から,任意の集合に対し,それへの一対一対応が存在しない順序数 の存在が示されました. そこで順序数 の部分集合 から への一対一関数が存在しない は順序数の定義から最小限を持つので,以下が定義できます.
Definition |
---|
集合に対し,一対一の関数が存在しない最小の順序数を と書き、 ハルトークスのアレフ という |
この章のメインの定理を証明します.
Theorem(ツェルメロの整列定理) |
---|
任意の集合は整列順序付け可能である |
証明の方針
- 集合
に対し,順序数全体から
への写像
で以下を満たすものを超限再帰をもちいて構成する.
かつ の時,
かつ の時,
ある について かつ なら
3.となる最小の を定義域として制限すると は全射
- 選択関数から で となるものを構成できる.
関数 を以下で定める.
となる時
それ以外の時,
超限帰納法から が上の1.~4.を満たす.
- 1.2.は写像の定義から を使うといえる.
- 3.は存在しないと が単射になることとハルトークスの定理が矛盾
- 4.は全射でないとすると の定義から となるので矛盾.
- ハルトークスの定理から任意の集合 に対し,ある順序数 が存在し, への一対一写像が存在ないものが存在する.
証明 集合 が与えられたとする.集合全体は真のクラスになるので. に属さない集合が存在する. 仮にそれを と名付ける.選択関数の存在から, で となるものが存在する. そこで関数 を以下で定める.
となる時
それ以外の時,
これを超限再帰を使って と定める. この時、この関数 は以下の性質が成り立つ
かつ の時,
かつ の時,
ある について
この時3.より, となる最小の順序数 が 以下に存在する. とすると, と は同値なので, fの終域は となる.さらにもし とすると, なので,特に の部分集合でないので, となり, に矛盾する.したがって であり, は と との間の全単射である. よって は が誘導する順序構造をいれることにより整列順序づけ可能である.
の作り方がかなりトリッキーで証明を追えば正しいことは確認できますが、どうやってこれを思いついたのか気になるものですね.
集合の対等生
この章では対等生にまつわる集合の有名な定理を証明します. ベルンシュタインの定理はその中でも最たるものです.
Definition |
---|
集合と集合に全単射の関数が存在する時,と書き,とは 対等 といいます.また集合から集合への単射が存在する時,と書きます |
Theorem |
---|
かつが成立する時となる |
証明の方針
- を単射とし, とする.
- [tex: {a_n = g``b{n-1},b_n = f``a{n-1}}] とする.
- (= a^*)は全単射であり,
逆に の時, は全単射となる.の時
の時
の時
さらに, は全単射.
- 上3つをうまく使い の全単射と が全単射を使うことと と分割でき, を以下で定める.
の時
の時
の時
この時,それぞれが全単射となるので,全体でみて全単射にんる.
Theorem |
---|
任意の2つの集合とに対し, かか少なくとも一方が成立する. |
proof 整列可能定理より と はそれぞれある順序数 に対し、全単射 が存在する. 順序数の場合 ならば なので, は一対一になる. なら が一対一写像になる.
この定理も選択公理が必要.
Lemma |
---|
全ての自然数に対し, |
proof より, となる. で単射となるものが存在しないことを示せばよい. は射が存在しないので, 成り立つ. に単射が存在しない仮定して, を任意の関数とする. を と を置換する写像とする.すると は全単射であり, より, が単射と仮定すると, はwell-definedであり,単射となるので,矛盾.
Definition |
---|
集合があるの元と対等となる時,有限.有限出ない時 無限 という |
選択公理を認めるとデデキント無限と無限が同値になる. デデキント無限とは自分の真部分集合と全単射が存在すること.
Theorem |
---|
すべての集合に対し,となる |
proof: は単射なので . に全射が存在しないことを示せばよい. とし, とすると. であり, の任意の要素 について, よりある に対し, とすると となり,矛盾する. よって任意の に対し, となる.矛盾する.
基数
Definition |
---|
集合と対等な最小の順序数をと書き,の 濃度 という. |
Lemma |
---|
次の1)-5)が成り立つ 1) 2) 3) 4) 順序数に対し, 5) |
proof
1) より→は言える。逆は明らか. 2) なら なので, となる.逆に とすると, から への単射存在ない.もし存在したとすると から への単射が存在し,仮定に矛盾するので. 3) 1),2)jから明らか 4)濃度の定義から言える. 5) から への単射が存在しないので,逆に から への単射が存在するので言える.
Definition |
---|
基数 とは自分より真に小さい順序数と対等にならない順序数のことである. |
Lemma |
---|
次の1)-5)が成り立つ 1) 自然数は全て基数 2)最初の無限順序数は基数 3) 基数ばかりを要素とする集合の最小上界は基数 4) 全ての集合に対し,は基数である. 5) 全ての集合に対し,は基数である. |
proof 1) より, から への一対一の関数は存在せず, からそれ未満の自然数への全単射も存在しないので,基数 2)もし と対等とすると から への単射が存在し, から への単射が存在することからベルンシュタインの定理で と が対等となり, と が対等となるので,矛盾. 3) に極大元が存在していた場合は明らか, に極大元が存在していないとする.もし, が基数でないとすると,ある順序数 と対等になっている.それはsupは最小上界なので は上界でなく,つまり.ある に対し, となる.この時,最大元が に存在してないので, より真に大きい が存在する.この時 と からベルンシュタインの定理より, と が同型となり矛盾する. 4)濃度の最小性から従う. 5)ハルトークスのアレフの定義から より真に大きい最小の順序数なので,最小性から基数になる.
ハルトークスのアレフは順序数 に対し,それより真に大きい最小の
Lemma |
---|
1)基数と順序数についてならである 2)順序数とに対し,とは同値である. |
proof 1)は は基数なので, となる.よって と対等な順序数は全て より真に小さい. 2) なら明らかに成り立つ.逆に とすると,もし とすると, が より大きい最小の基数であることに矛盾する.よって, となり, となる.
Lemma |
---|
無限基数は極限順序数である |
Proof 無限順序数 に対し, と が対等であることを示せば良い. を以下で定める.
の時,
の時,
の時
とするとこれは全単射なので, となる.
Definition |
---|
全ての順序数に対し,を以下のように超限再帰で定める. 1) 2) が極限順序数である時, |
Lemma |
---|
集合が有限でなければしたがって,である. |
proof
集合 の整列順序付け が存在するので, の順序型を とする. なら は有限になる.なので が有限でない時 となる. は基数なので, となる.
この定理は集合の整列順序可能性を用いるので,選択公理を使う.
Lemma |
---|
1) 全ての は無限基数 2)とは同値 無限基数は全てなんらかのについてとなる. |
Proof 1) が無限基数であることと,順序数 に対し, が基数となることと、基数のなす集合の が基数であることから,超限帰納法で示せる. 2) から超限帰納法で示せる. 3)無限基数 に対し, とする. この時 は順序数の推移的集合になるので,順序数であり, となるので, となる. もし なら, は最小の無限基数 であり, である. なら, であり, より, の最小性から となる. もし が極限順序数なら
なので, となる.
Definition |
---|
無限基数はとかける時, 後続型基数 と呼ばれ,そうでない時 極限基数 と呼ばれる |
定義から全ての順序数 に対し, は無限基数であり,( の時) が後続型基数であることと が後続型順序数であることは同値. は後続とも極限とも言いづらいものである.
Definition |
---|
基数に対し,の濃度をと定める.また,直積集合の濃度を積として定める |
以降では基本的には基数としての演算を扱うが,順序数としての演算と区別するときは などとかく.
Lemma |
---|
任意の順序数について 1) 2) |
Lemma |
---|
基数について次のことが成り立つ.和と積はいずれも基数の演算の意味で考える 1) 2) 3) 4) 5) 6) の時,かつ |
proof 全て具体的に全単射を構成すればいい. 1)
を とすればよい. 他も同様.
Definition |
---|
順序数の順序対とに対して, と定める |
Lemma |
---|
二項関係はの整列順序付けであり,各順序数についてはの始切片である |
Proof 真クラスに対する整列順序付けの細かいことはひとまず気にしない. 整列順序付けであることを示すために以下を示す
- 定義から言える
- なら これも具体的に試せばよい.
- 三分率,従う.
そのため,整列順序付けになっていることを示せば良い.
- 始切片が集合?
- 集合 が で最小限を持てばよい.
に対し とした時(これは整列集合なので が存在することから言える), とし,同様に の中で が最小になるもの全体を とし, の元で が最小となる元 は の最小元になるので,示せた. また, は の最小性から つまり, と同値になる.よって は と一致する.
Theorem |
---|
任意の無限基数について,基数の演算の意味でとなる. |
証明 順序数 に対し,整列集合 の順序型を とかくと,
が極限順序数の時,
となる. これは が の始切片であることから, は から の要素が の小さい順に 個並び, が 個並ぶことからわかる. 定義から なので,全ての無限基数について が言えればよい. まず任意の順序数に対し, となる. の時,[tex: {\tau_2(n) = n2}] より, となる. を より真に大きい基数として, 未満のすべての無限基数 に対し, が成立していると仮定する. すると,順序数 には となるので, が 未満の無限順序数の場合,帰納法の仮定から となる. このことから, となるので, となる.
連続体仮説
とかく.
Definition |
---|
基数に対し,を基数としての指数関数と定める. |
Lemma |
---|
任意の集合に対し, |
証明 に対し,特性関数 を
- の時1
- の時0
で定める.すると は を定める. これは全単射である.単射は とすると が存在すると思ってよい(必要であれば と を取り替えればよい).この時 となるので,単射となる.全射は に対し, を とした時 となるのでいえた.
Lemma |
---|
実数全体のなす濃度は |
proof を
と定める.すると の時, となる の最小値を とする. 今 とし であり, となるので, となる. 一方で, を の整数部分が奇数 と定める.これは単射である.それは,もし とすると, となる最小の に対し, より,単射となる.
また, が単射なので,ベルンシュタインの定理より, よって,実数全体の濃度は となる.
Theorem |
---|
全ての基数。に対し,|カントールの定理から任意の集合に対し,その冪集合への全射はなく,またうえで示した補題より,から従う. |
Statement(連続体仮説) |
---|
これは示せるのか??全くわからない!!!!!!!
完結編は6/2,6/3.乞うご期待
機械学習で読んだ本
機械学習関係で読んだ本とその内容について紹介します. 全部を熟読した本はないのと,私は数学系の人間なので,理論系に厳しいのはご了承ください.
理論系
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件) を見る
トピックモデル
- 作者: 岩田具治
- 出版社/メーカー: 講談社
- 発売日: 2015/04/08
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (2件) を見る
トピックモデルを中心にベイズ推定や変分近似について丁寧に書いてある本 ベイズ推定のいい勉強になると思います.
生命情報処理における機械学習 多重検定と推定量設計
生命情報処理における機械学習 多重検定と推定量設計 (機械学習プロフェッショナルシリーズ)
- 作者: 瀬々潤,浜田道昭
- 出版社/メーカー: 講談社
- 発売日: 2015/12/09
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (1件) を見る
生命情報をベースに統計(仮説検定)を紹介した本. あまりちゃんと読めていませんが,丁寧にまとまっている印象です. 生物系をやろうと思っているならよい本です.
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'>
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()
軸の名前
軸を設定するには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()
グラフ/線のタイトル
グラフのタイトルは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()
基本編は以上です. 複雑なことはこれから鍛えていこうと思います.
陰関数定理
最適化を考える時に 陰関数定理とラグランジュの未定乗数法を考える事が多いので,これらについて紹介したいと思います.
今回は二変数の場合の陰関数定理について紹介します.
定理 |
---|
がを満たし,の近傍で微分可能でともに偏微分が連続で, とする.この時,あるの開近傍上定義され,となる関数で,任意の上,を満たすものが存在する. |
これを証明します.存在を示すので,具体的に構成できればよいわけです.
まず偏微分が連続であることと, の近傍で微分可能であることから, を含む の開近傍 上で, に対し, は符号が全て同じとなるものが存在します. 符号はひとまず正とします.(負の場合は をとればよいです)
これにより, 上, となり,逆に 上 となります. の連続性から,十分小さい開近傍を取ると, で, と は符号が変わらず, でも 同様となります.そのため, を固定すると は単調増加で符号が変わることから,任意の に対し,ただ1つの となる が存在することがわかります.
よって関数 を と定めればよいです.
さらに,これは微分可能であることもわかります.
証明は平均値の定理を使うことで出ます.