2017-01-09

「これからの強化学習」勉強会#3（準備中）→ ノート3

本読み強化学習

読んでいる本（出典）：これからの強化学習 | 牧野貴樹, 澁谷長史, 白川真一 |本 | 通販 | Amazon

前回：勉強会#2 ／次回：まだ
目次：これからの強化学習／ Sutton & Barto 強化学習（邦訳）の目次：強化学習

「これからの強化学習」のエア勉強会3回目の準備中。
（スライドはできて）ないです。第2章の2.1節はページ数が多いし、後半は学習アルゴリズムのオムニバスなので、自分なりの講義にする余地がなくてスライドをつくれなさそう。

以下、2.1節（72～111ページ）の読書メモ。

2.1節： 「パラメタライズされたモデルでおいた価値関数はちゃんと収束するのか」が中心的話題。
まず、パラメタライズされたモデルといっても色んなモデルが仮定できるけど、状態と行動が離散的で、実質的に固定した動的プログラミング（方策反復）と変わらないモデルを考える（各状態のがそのままパラメータになっている）。これは当然収束する（だって方策反復DPだから）。
テキストでは、収束するかちゃんと確かめなければならない理由を、教師あり学習と違って固定された教師信号との誤差の最小化になっていない、と。強化学習には正解がないので最初からパラメータの到達すべき場所はわからない。前ステップの推定モデルで測った価値より今ステップの推定モデルで測った価値が現実をよく表すように動かすしかない（その測った価値すらモデル依存）。と考えると、本当にちゃんとどこかにたどり着くのかは確かに不安だと思う。
そして、もっと違うモデルにした場合でも同じパラメータ更新式を使用することに決め打つと（なんで同じパラメータ更新式をつかい回しすことに決め打ったのかちょっとよくわからない）、「方策オンかつ線型モデル」でない限り収束が保証されない。線型かつ方策オフのとき収束が保証されない理由はもうちょっとかいてあるけど、非線形のときはよくわかりません。
TD(λ) 法の場合は λ=1（要はモンテカルロ法）の場合はモデルにかかわらず収束する。
Sarsa や Q学習は、固定のときと同じ感じで、方策オンかつ線型の限られた場合でのみ収束する。
最初に決め打ったパラメータ更新式ではなくて、実際に何らかの目的関数を最適化する学習アルゴリズムも色々ある。色々あるけど、ひっくるめてセミパラメトリック推定として理解できると。
- 教師あり学習で2乗誤差の勾配方向に適切な距離だけパラメータ更新していけばモデルはちゃんと改善する（74ページ）って進研ゼミじゃなくて青い本のオンライン機械学習でやった。でも強化学習では近づくべき正解もわからなければ、得られるデータも自分の行動に依存するので同じ議論ができないと。
- マルコフ連鎖が規約ならば唯一の定常分布をもつ（75ページ）って伊庭先生のMCMCの本でやった。
  - マルコフ連鎖モンテカルロ法とその周辺読書会(5)：参加メモ - クッキーの日記
- 「状態価値関数（中略）に収束する。これは、ベルマンオペレータが一様ノルムに対して縮小写像となることから示すことができる（76ページ）」：このくだりは、Sutton でいうと「系列 $\{V_k\}$ が極限 $k \to \infty$ で $V^\pi$ に収束することが一般的に示される（96ページ）」に相当する。
- 78ページ (2.1.24) 式で言いたいのは、「最良な行動をとったときの報酬の最大値の期待値（最左辺 & 中辺）」と「最良な行動をとったときの期待値の最大値（最右辺）」は等しくないと。
  - 転職に悩めるエージェント（勉強会#1のスライド10ページ）が「不満」な状態にあるとき、「転職」することが最良な行動だとして、前者は $A-c$ だけど、後者は $\beta (A-c) + (1-\beta)(B-c)$ だから等しくない（転職に悩めるエージェント問題は状態遷移のみが確率的で、報酬は与えられた状態-行動-状態組について決定的としていたが、一般にはさらに報酬も確率的）。
- 78ページ (2.1.27) は Sarsa の更新式そのもの、(2.1.28) はQ学習の更新式そのもの。
  - ただし、86ページの書き方だと、毎ステップ $\pi$ を改善しないなら Sarsa ではない？この本での Sarsa の初出箇所（33ページ～）では、 $\pi$ を更新しようとしなかろうとこの更新式で $\pi$ の下での価値関数を改善するのが Sarsa のようには読めた。
- 「一般に、ある行動方策に従って得られる状態行動系列は、状態遷移確率のもつマルコフ性を有するため、集合 $\mathcal{S}$ から一様ランダムに選択して得られる状態とは大きく異なる（79ページ）」：だからこそ、Sutton の 135ページ～の方策オフ型モンテカルロのような、目的の行動方策の下での確率測度への変換を行う手法があると思うんだけど、こちらの本ではそのような手法の紹介はこれより後。
- 81ページ (2.1.29) の線形モデルのイメージ：これって、をそのままに書き換えただけ。「この更新則が、式 (2.1.29) の関数近似器を用いるとき、テーブル表現した価値関数のTD学習に一致することを確かめてみよう（82ページ）」というのも、書き換えただけなので当然。
  - $\theta=($ 盤面1の価値. 盤面2の価値, 盤面3の価値, $\cdots)$
    $\phi ($ 盤面1 $)=(1, 0, 0, \cdots)$
    $\phi ($ 盤面2 $)=(0, 1, 0, \cdots)$
- TD(λ) 法の前方観測と後方観測って何だったっけ。
  - 強化学習：ノート14 - クッキーの日記

2017-01-08

数理論理学：ノート2

本読み数理論理学

読んでいる本（出典）：数理論理学 | 戸次大介 |本 | 通販 | Amazon

前回：ノート1 ／次回：ノート3
目次：数理論理学

以下、第3章の自分の理解。第3章は一階命題論理。

一階命題論理の統語論

一階命題論理では、命題（≡ 真偽を問うことのできる形式）を下のような論理式にかきあらわす。
この形式を満たさないものは論理式ではない。
一階命題論理に
おける論理式 $P, \; Q, \; R,$ 　命題記号は論理式
$\top , \; \perp , \; \lnot(P) , \; \land(P, Q) , \; \to \! \! (P, Q),$ 　 $n$ 項真理関数に論理式を代入した形式も論理式
$\lnot(\top) , \; \lor(\land(P, Q), R) , \; \leftrightarrow \! \! (\lnot(\top), \lor(\land(P, Q), R))$ 　なので、これらも論理式
ちなみに、上の例の最後の論理式の部分論理式の集合は以下。
${\rm SubF}\bigl( \leftrightarrow \! \! (\lnot(\top), \lor(\land(P, Q), R)) \bigr) = \{ \leftrightarrow \! \! (\lnot(\top), \lor(\land(P, Q), R)) \} \cup {\rm SubF}\bigl( \lnot(\top) \bigr) \cup {\rm SubF}\bigl( \lor(\land(P, Q), R)) \bigr)$
　 $= \{ \leftrightarrow \! \! (\lnot(\top), \lor(\land(P, Q), R)), \; \lnot(\top), \; \lor(\land(P, Q), R)) \} \cup {\rm SubF}\bigl( \top \bigr) \cup {\rm SubF}\bigl( \land(P, Q) \bigr) \cup {\rm SubF}\bigl( R \bigr)$
　 $= \{ \leftrightarrow \! \! (\lnot(\top), \lor(\land(P, Q), R)), \; \lnot(\top), \; \lor(\land(P, Q), R)), \; \top, \; \land(P, Q), \; R \} \cup {\rm SubF}\bigl( P \bigr) \cup {\rm SubF}\bigl( Q \bigr)$
　 $= \{ \leftrightarrow \! \! (\lnot(\top), \lor(\land(P, Q), R)), \; \lnot(\top), \; \lor(\land(P, Q), R)), \; \top, \; \land(P, Q), \; R, \; P, \; Q \}$

一階命題論理における論理式	$P, \; Q, \; R,$ 　命題記号は論理式 $\top , \; \perp , \; \lnot(P) , \; \land(P, Q) , \; \to \! \! (P, Q),$ 　 $n$ 項真理関数に論理式を代入した形式も論理式 $\lnot(\top) , \; \lor(\land(P, Q), R) , \; \leftrightarrow \! \! (\lnot(\top), \lor(\land(P, Q), R))$ 　なので、これらも論理式

一階命題論理の意味論

上で命題をあらわす論理式に形式的定義を与えたので、次に、論理式の真偽を考える。ここで「真偽を問う」というのは、「集合 $D_t \equiv \{1,0\}$ の要素へ対応させる」ということとする。この $D_t$ を領域という。ここでの領域には「真（1）」と「偽（0）」のみがあり、「ちょっと真」とかはない。
それで論理式の真偽を考えると、「 $n$ は偶数である」「今年は2月29日がある」「丸の内線の線路は地下にある」「コイルはでんきタイプ単色である」など、真か偽かは状況によることに気付く。このようなあらゆる状況を明示的に取り扱うことはできない気がする。

逆に、「論理式の集合 $\rightarrow D_t$ 」という写像の1つ1つが「このような状況」を表しているといえる。

例えば、以下の原子命題を考える。
　　　　　 $P$ コイルはでんき単 $\equiv$ 「コイルはでんきタイプ単色である」
このとき、コイルはでんき単なる写像全体は以下の2つ。これらがそれぞれ状況に相当する。
写像1 写像2
$P$ コイルはでんき単 $\mapsto \; 1$ $P$ コイルはでんき単 $\mapsto \; 0$
- 写像1は感覚的には、コイルがでんき単色だった "第1世代" という状況に相当する。
- 写像2は感覚的には、はがねタイプが追加された "第2世代以降" という状況に相当する。

写像1	写像2
$P$ コイルはでんき単 $\mapsto \; 1$	$P$ コイルはでんき単 $\mapsto \; 0$

ここに原子命題をもう1つ付け加える。

　　　　　 $P$ コイルはでんき単 $\equiv$ 「コイルはでんきタイプ単色である」
　　　　　 $P$ ピッピはノーマル $\equiv$ 「ピッピはノーマルタイプである」

$\{P$ コイルはでんき単 $, \; P$ ピッピはノーマル $\} \to D_t$ なる写像全体は以下の4つになる。

写像3	写像4	写像5	写像6
$P$ コイルはでんき単 $\mapsto \; 1$ $P$ ピッピはノーマル $\mapsto \; 1$	$P$ コイルはでんき単 $\mapsto \; 1$ $P$ ピッピはノーマル $\mapsto \; 0$	$P$ コイルはでんき単 $\mapsto \; 0$ $P$ ピッピはノーマル $\mapsto \; 1$	$P$ コイルはでんき単 $\mapsto \; 0$ $P$ ピッピはノーマル $\mapsto \; 0$

写像3は感覚的には、"第1世代" という状況に相当する。
写像4のような世代は実際なかったが、とりあえず状況としては定義できる。
写像5は感覚的には、"第2～5世代" という状況に相当する。
写像6は感覚的には、フェアリータイプ追加後の "第6世代" という状況に相当する。

この「 $I:$ 論理式の集合 $\rightarrow D_t$ 」であるような写像 $I$ を解釈という。解釈という言葉へのイメージは、「地球は動いている」は、「天動説」という解釈の下では偽で、「地動説」という解釈の下では真みたいな。
解釈をつかうと、「 $P$ コイルはでんき単は真か？」という問いへの答えは「 $I(P$ コイルはでんき単 $)=1$ であるような解釈 $I$ の下では真である」になるけど、これ自体は「真のときは真です」と言っているだけなので何もうれしくない。
ただ、論理式が原子命題ではない場合、例えば「 $P$ コイルはでんき単 $\lor P$ ピッピはノーマルは真か？」という問いには、部分論理式に含まれる原子命題の真偽で場合分けすればよく、「写像3, 写像4, 写像5で表される解釈の下では真で、写像6で表される解釈の下では偽です」となる。これは「真のときは真です」以上のことを言っている。真偽を考えるべき論理式は無数に存在するが、考えなければならない状況の数は $2$ 原子命題の数だけでよい。
解釈によらず真な論理式（恒真式）もある。よく知られているものは例えば以下。
- $\varphi \land \psi \leftrightarrow \psi \land \varphi$ 　交換律
- $\varphi \lor \psi \leftrightarrow \psi \lor \varphi$ 　交換律
- $\varphi \to \psi \leftrightarrow \lnot \psi \to \lnot \varphi$ 　対偶律
- $\varphi \land \lnot \varphi$ 　排中律

じゃあ一階命題論理において妥当な推論とは何か

妥当な推論とは何かとは意味論的推論に基づくことにしていたのだが、意味論的推論を一階命題論理の言葉に書き直すとこうなる：を論理式列として（ただしは高々）、以下を満たすとき「はを意味論的に含意する」といい、とかく。
- 以下のような解釈が存在しない。
  - $\Gamma$ に含まれるすべての論理式 $\varphi$ について $I(\varphi)=1$ である。
  - $\Delta$ に含まれるすべての論理式 $\psi$ について $I(\psi)=0$ である。
例えば、は妥当な推論である。つまり、が成立する。これは、以下の真偽値表で確認できる。
- まず、登場する原子命題が $P, Q, R$ の3つなので、 $2^3=8$ つの解釈を考えればよい（下表の各行）。
- それぞれの解釈の下での $P \to Q, \; Q \to R, \; P \to R$ の真偽値を書き入れる。
- $P \to Q, \, Q \to R \, \models \, P \to R$ であるためには、 $I(P \to Q), \; I(Q \to R)$ が $1$ であって、 $I(P \to R)$ が $0$ であるような解釈 $I$ が存在してはならないが、 $I(P \to Q), \; I(Q \to R)$ が $1$ であるような行を薄い青で塗ると、それらの行ではすべて $I(P \to R)$ が $1$ なので、 $P \to Q, \, Q \to R \, \models \, P \to R$ は成立する。

$P$	$Q$	$R$	$P$	$\to$	$Q$	$Q$	$\to$	$R$	$P$	$\to$	$R$
1	1	1	1	1	1	1	1	1	1	1	1
1	1	0	1	1	1	1	0	0	1	0	0
1	0	1	1	0	0	0	1	1	1	1	1
1	0	0	1	0	0	0	1	0	1	0	0
0	1	1	0	1	1	1	1	1	0	1	1
0	1	0	0	1	1	1	0	0	0	1	0
0	0	1	0	1	0	0	1	1	0	1	1
0	0	0	0	1	0	0	1	0	0	1	0

$\quad \models \varphi$ は論理式 $\varphi$ が恒真であることを意味する（ $I(\varphi)=0$ となる解釈 $I$ が存在しないということだから）。
$\Gamma \models \quad$ は論理式列 $\Gamma$ が矛盾していることを意味する（ $\Gamma$ に含まれるすべての $\varphi$ を同時に $I(\varphi)=1$ とする解釈 $I$ が存在しないということだから）。
$\varphi \models \psi$ かつ $\psi \models \varphi$ のとき、 $\varphi$ と $\psi$ は意味論的に同値であるといい、 $\varphi = \! \! \! | | \! \! \! = \psi$ とかく。
真偽値表をかけばどんな推論も妥当かどうか手続き的に確かめられるが、以下のような定理（教科書には他にも色々示されている）を活用するともっと楽になる。「推論が意味論的に妥当かどうか」を、「論理式が恒真かどうか」という確認に落とし込むとよい。
- $\varphi \models \psi \; \Longleftrightarrow \; \models \varphi \to \psi$
- $\varphi = \! \! \! | | \! \! \! = \psi \; \Longleftrightarrow \; \models \varphi \leftrightarrow \psi$
- ある論理式と、その論理式の部分論理式を意味論的同値な論理式に置き換えた論理式は、意味論的同値。置き換え
- $\Gamma \models \varphi, \; \; \Delta, \varphi, \Delta' \models \psi \; \Longrightarrow \; \Delta, \Gamma, \Delta' \models \psi$ 　カット
- $\varphi, \Gamma \models \perp \; \Longleftrightarrow \; \Gamma \models \lnot \varphi$ 　背理法

ここまで来て気付くこと

項真理関数を色々考えていたけど、冷静に考えると任意の真偽値の出力ってだけでできるのでは。
- 真偽値表で1になる行を全部抜いてきて、 $(P \land Q \land R) \lor (P \land \lnot Q \land R) \lor \cdots$ のようにつないでいけばよい。選言標準形
- 逆に、真偽値表で0になる行を抜いてきて、 $(P \land Q \land \lnot R) \land (P \land \lnot Q \land \lnot R) \land \cdots$ のようにつないでいって最後に全体に $\lnot$ してもよい。連言標準形
もっというと、ドゥ・モルガンの法則をつかうとをに換えたり、その逆ができるので、からかのどちらか一方をリストラしてもあらゆる真偽値の出力がつくれる。表現的適格性
- $\{ \lnot, \; \land \}$ や $\{ \lnot, \; \lor \}$ という組でなくてもよい。例えば $\{\lnot, \; \to\}$ でもOK。
さらにいうと、NAND または NOR は単独で表現的に適格になれる。

練習問題3.27　面倒なので略。

まず、(論理式全体の集合)＝(命題記号の集合) $\oplus$ (複合論理式の集合)。
仮定より、解釈 $I_1$ と $I_2$ で、任意の命題記号について、 $I_1 ($ 命題記号 $)=I_2 ($ 命題記号 $)$ 。
複合論理式は、手元に命題記号たちだけがある状態からはじめて、項真理関数を有限回つかえばつくれる。
以下を帰納法で示せばよい。
- $I_1 ($ $n$ 項真理関数を1回つかった論理式 $)=I_2 ($ $n$ 項真理関数を1回つかった論理式 $)$
- $I_1 ($ $n$ 項真理関数を2回つかった論理式 $)=I_2 ($ $n$ 項真理関数を2回つかった論理式 $)$
- $\cdots$

練習問題3.28　面倒なので略。

練習問題3.31

$2^{2^0}=2$ より、0項真理関数は2個ある。だから、 $\top, \; \perp$ で全部。

練習問題3.35

$2^{2^1}=4$ より、1項真理関数は4個ある。だから、 $\lnot$ の他に3個ある（練習問題3.36）。

練習問題3.36

どんな値を取っても1を返す関数。
どんな値を取っても0を返す関数。
「取った値に何もせずそのまま返す」という関数。

練習問題3.39

$2^{2^2}=16$ より、2項真理関数は16個ある。だから、 $\land , \; \lor, \; \to, \; \leftrightarrow$ の他に12個ある。
っていう話を数学ガールの秘密ノート第172回でやってた。
- 第172回裏の裏は表（後編）｜数学ガールの秘密ノート｜結城浩｜cakes（ケイクス）

練習問題3.40

$n$ 項真理関数は $2$ の $2^n$ 乗個ある。

練習問題3.42　面倒なので略。

練習問題3.44　真偽値表で38～39ページの恒真式が恒真式であることを確認せよという問題。ドゥ・モルガンの法則だけ。

①	①	③		①	②	①		④	②	①	③	②	①
$\varphi$	$\psi$	$\lnot$	$($	$\varphi$	$\land$	$\psi$	$)$	$\leftrightarrow$	$\lnot$	$\varphi$	$\lor$	$\lnot$	$\psi$
1	1	0		1	1	1		1	0	1	0	0	1
1	0	1		1	0	0		1	0	1	1	1	0
0	1	1		0	0	1		1	1	0	1	0	1
0	0	1		0	0	0		1	1	0	1	1	0

①	①	③		①	②	①		④	②	①	③	②	①
$\varphi$	$\psi$	$\lnot$	$($	$\varphi$	$\lor$	$\psi$	$)$	$\leftrightarrow$	$\lnot$	$\varphi$	$\land$	$\lnot$	$\psi$
1	1	0		1	1	1		1	0	1	0	0	1
1	0	0		1	1	0		1	0	1	0	1	0
0	1	0		0	1	1		1	1	0	0	0	1
0	0	1		0	0	0		1	1	0	1	1	0

練習問題3.45　面倒なので略。

練習問題3.47　面倒なので略。

練習問題3.52

「 $\quad \models \varphi$ 」がいえるなら、左側にどんな論理式列を書いたっていい。
「 $\Gamma \models \quad$ 」がいえるなら、右側にどんな論理式を書いたっていい。

練習問題3.53

「 $\quad \models \quad$ 」は「解釈 $I$ が存在しない」を意味するが、たとえその言語に原子命題が1つもなくとも $I$ は存在するので、「 $\quad \models \quad$ 」は成立しない。

練習問題3.54

「」は「かつかつであるが存在しない」を意味する。
- $\varphi_1, \, \cdots, \, \varphi_n$ がすべて矛盾式（恒偽式）であれば「 $\varphi_1, \, \cdots, \, \varphi_n \models \quad$ 」である。
- ただ、すべて矛盾式でなくとも、 $\varphi_1, \, \cdots, \, \varphi_n$ に1つでも矛盾式が含まれれば「 $\varphi_1, \, \cdots, \, \varphi_n \models \quad$ 」である。
- もっというと、個々の論理式は矛盾式でなくとも、に含まれる2つ以上の論理式の組をすべて真にする解釈がなければ、「」である。
  - 例えば、 $P$ と $\lnot P$ それぞれを真にする解釈はあるが、これらを同時に真にする解釈はない。

練習問題3.58　面倒なので略。

練習問題3.59　最初のだけ上のノート内で解いた。

練習問題3.63　面倒なので略。

練習問題3.64　面倒なので略。

練習問題3.66　面倒なので略。

練習問題3.67

1) 　 $(\lnot P \to P) \leftrightarrow P$ は恒真式。
2) 　左側が恒偽式なので、右側は何でもいい。
3) 　 $\lnot P \leftrightarrow (P \to \perp)$ は恒真式。
4) 　 $(P \to Q) \to (\lnot P \to \lnot Q)$ は恒真式ではないので意味論的妥当性は成立していない。

練習問題3.71　面倒なので略。

練習問題3.73　面倒なので略。

1) 　対偶律＋二重否定律
2) 　分配律＋ドゥ・モルガンの法則
3) 　同一律＋ドゥ・モルガンの法則＋二重否定律

練習問題3.80　面倒なので略。

練習問題3.84　何この問題。

身内の犯行であるならば、貞夫か光枝が犯人である。	$P \to Q \lor R$
貞夫が犯人ならば、犯人は財産目当てではない。	$Q \to \lnot S$
犯人が財産目当てならば、光枝は犯人ではない。	$S \to \lnot R$
したがって、身内の犯行であるならば、犯人は財産目当てではない。	$P \to \lnot S$

妥当性を示すべき推論： $P \to Q \lor R, \; \; Q \to \lnot S, \: \: S \to \lnot R \; \; \models \; \; P \to \lnot S$
以下に略解を記す。

1)	$Q \to \lnot S , \; \; R \to \lnot S \; \; \models \; \; Q \lor R \to \lnot S$	（構成的両刃論法）
2)	$Q \to \lnot S , \; \; S \to \lnot R \; \; \models \; \; Q \lor R \to \lnot S$	（1) の前提の一部を対偶律で置き換え）
3)	$P \to Q \lor R , \; \; Q \lor R \to \lnot S \; \; \models \; \; P \to \lnot S$	（推移律）
4)	$P \to Q \lor R , \; \; Q \to \lnot S , \; \; S \to \lnot R \; \; \models \; \; P \to \lnot S$	（2) と 3) をカット）

練習問題3.87

1)	$\models \; \; \varphi \to \psi \; \; \; \Longleftrightarrow \; \; \; \varphi \; \; \models \; \; \psi$	（定理 3.60）
2)	$\models \; \; \psi$	（ $\models \varphi$ と 1) をカット）

練習問題3.89　面倒なので略。

練習問題3.91
背理法以前にこの推論は妥当でない。出題ミス？

練習問題3.94
左側は0になっている行がないので連言標準形の手続きを進めることができないし、右側は1になっている行がないので選言標準形の手続きを進めることができないよね。

練習問題3.95　面倒なので略。

練習問題3.101　面倒なので略。

練習問題3.103　 $n$ 項真理関数を別の $n$ 項真理関数で表現。

1) 　 $\varphi \to \psi \; = \! \! \! | | \! \! \! = \; \lnot(\varphi \land \lnot \psi)$
2) 　 $\varphi \to \psi \; = \! \! \! | | \! \! \! = \; \lnot \varphi \lor \psi$
3) 　 $\varphi \lor \psi \; = \! \! \! | | \! \! \! = \; (\varphi \to \psi) \to \psi$
4) 　 $\varphi \land \psi \; = \! \! \! | | \! \! \! = \; ((\varphi \to \psi) \to \psi) \leftrightarrow (\varphi \leftrightarrow \psi)$
5) 　 $\land$ は $\to$ のみでは表現できないことを示すのはすぐできなさそうなのでパス。

練習問題3.106　面倒なので略。

練習問題3.107
一項真理関数は原子命題を1つとって「そのまま返す」「裏返して返す」「1にして返す」「0にして返す」しかできない。
2つ目以降の原子命題を全く考慮できない。

所感

以下の記事を書くときにペアノの公理の5番目ってなんでこんな浮いているんだろうと思ったけど、自然数の定義に自然数をつかってはいけないのでそんな感じにせざるをえない。たぶん。
- 雑記：読書メモ - クッキーの日記
それで、一階命題論理では集合の概念をつかっているけど、本来集合の概念自体が論理体系を整えた上にあるのに大丈夫？というのが心配になるけど、それについては集合の概念を回避できる意味論もあるらしい（35ページ注釈9）。
意味論的同値の記号 $= \! \! \! | | \! \! \! =$ ってこうですか。わかりません。
= \! \! \! | | \! \! \! =

2017-01-02

「これからの強化学習」勉強会#2

本読み強化学習

読んでいる本（出典）：これからの強化学習 | 牧野貴樹, 澁谷長史, 白川真一 |本 | 通販 | Amazon

前回：勉強会#1 ／次回：まだ
目次：これからの強化学習／ Sutton & Barto 強化学習（邦訳）の目次：強化学習

「これからの強化学習」の1人勉強会#2。

以下、スライドの補足でもない感想。

例によって例示（というレベルのものはないですが）は自分で考えたものなので適当です。
5～6頁の例はしゃべらないとわからないような気はします。
8頁、REINFORCE にしたかっただけ感がすごいですが、最良線形不偏推定量 BLUE とかはまだしも略語が他の単語になるととても紛らわしいと思うんですが。といって他の単語でもないアルファベットの羅列になったところですぐ忘れますが。
Sutton だとアクター・クリティックの登場の仕方が唐突だったが、"これから" ではわかりやすかった。
自然勾配の例示を途中まで書いていたらフィッシャー情報行列が逆行列をもたなくなってしまったので削ったんですが今度リファクタリングします。
POMDP は Sutton ではほぼ名前だけだったので勉強になりました。スライド上は力尽きています。

あと強化学習関連の雑談：以下の記事は CoastRunners というボートレースのゲームをエージェントに学習させようとして、コース周辺のターゲットを撃ち落とすことに報酬を与えたらボートがコースを周回してくれなくなったという話。記事中ほどには、AIがコースを周回せずにひたすらターゲットを撃ち落とし続けるようすの動画がある。
openai.com
記事にはこのような報酬の設計ミスの回避方法が3つ提言されていて、「人間のプレイの真似をさせる」「行動評価／行動選択に人間のフィードバックを入れる」「他の多くの似たようなゲームで訓練させて、『常識』的な報酬関数を推論させる（コースがあったら周回するのが筋だろうと／実際、人間の学習はこれに近いはず）」と。先の2つはそれはそうだろうって感じだけど、最後の3つ目は最近の以下のニュースを想起させる。

もう東大はあきらめたということだけど東ロボプロジェクトの、国語の「文章読解」で「人間社会において通常合理的と考えられている文章のつながりや流れ」とされている概念はまさに、「レースゲームでは、コースは周回するもの」みたいなのがなす集合だろう。
- 国語 - ロボットは東大に入れるか。Todai Robot Project
それで、DeepMind が10月に発表した Differentiable neural computers で RNN にくっついている "RAM" が、そういう "常識" のような知見をつかさどるようになるんだろうというイメージ。
- Hybrid computing using a neural network with dynamic external memory : Nature

何にせよ報酬の設計はよく考えないといけなくて、それは何も相手がAIだからというのでなく人間相手だってそう。
例えばあなたが「社員の残業を減らしたい」を達成したいとして、何に対して（プラスあるいはマイナスの）報酬を与える制度を設計すればよいだろうか。まあ自分は面倒なので考えないんですけど。例えば全社員の合計残業時間が減っても、一部の人が過重労働になる方策はいい方策だろうか。となるようなら制度設計以前に達成したいことが明確化されていない。「要求が明確化できない（できるのにしていない／できない）」「明確化されているが上手く報酬が設計できない」は区別する必要があると思います。ただ、他のレースゲームからセオリーを学んでこいというのは「最適方策を学んで！達成したいこと？自分で察して！」という話ですけど。AIは大変だなあ。

2017-01-01

ライブラリまとめ

最終更新日： 2017-01-16
統計処理の各種ライブラリについてまとめておくためのページ

Python ライブラリ篇

名前	説明
Keras https://keras.io/ja/	深層学習の便利ライブラリ。本体として TensorFlow か Theano が必要。 Keras でロジスティック回帰するだけ keras-rl の example コードを実行するだけ
keras-rl https://github.com/matthiasplappert/keras-rl	Keras をつかった深層強化学習のライブラリ。
OpenAI Gym https://gym.openai.com/	色々な強化学習タスクの "環境" ライブラリ。囲碁もあるらしい。 https://gym.openai.com/envs#board_game

R パッケージ篇

名前	説明
tseries https://cran.r-project.org/web/packages/tseries/index.html	時系列解析用のパッケージで garch() が入っている。 R garch をつかってみるだけ
dlm https://cran.r-project.org/web/packages/dlm/index.html	名前の通り動的線型モデルのパッケージ。 Rによるベイジアン動的線型モデル：ノート4 R dlm をつかってみるだけ
class https://cran.r-project.org/web/packages/class/index.html	クラス分類用のパッケージでk近傍法が入っている。雑記
h2o https://cran.r-project.org/web/packages/h2o/index.html	機械学習ライブラリ H2O の R 用 I/F で、R で深層学習ができる。 R h2o をつかってみるだけ

2017-01-01

論文読みまとめ

最終更新日： 2017-02-19
参考になりそうな論文をとりあえずメモしておくページ

確率的勾配降下法
深層学習（基礎）
強化学習（基礎）
強化学習（応用）
位相的データ解析（基礎）

確率的勾配降下法

表題	Shun-ichi Amari. Natural Gradient Works Efficiently in Learning, Neural Computation, Vol. 10, No. 2, pp. 251-276 (1998).
リンク	http://www.maths.tcd.ie/~mnl/store/Amari1998a.pdf
備考	自然勾配の原論文。

表題	Diederik Kingma and Jimmy Ba: Adam: A Method for Stochastic Optimization, arXiv:1412.6980 (2014).
リンク	https://arxiv.org/pdf/1412.6980v8.pdf
備考	Adam の原論文。

深層学習（基礎）

表題	George Cybenko: Approximation by Superpositions of a Sigmoidal Function (1989).
リンク	http://www.dartmouth.edu/~gvc/Cybenko_MCSS.pdf
備考	ニューラルネットワークの普遍性定理（Universal Approximation Theorem）の原論文。

強化学習（基礎）

表題	R. J. Williams: Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning, Machine Learning, Vol. 8, Issue 3, pp. 229-256 (1992).
リンク	http://www-anw.cs.umass.edu/~barto/courses/cs687/williams92simple.pdf
備考	方策勾配のREINFORCEアルゴリズム。

表題	R. S. Sutton, D. A. McAllester, S. P. Singh, and Y. Mansour. Policy Gradient Methods for Reinforcement Learning with Function Approximation, Advances in Neural Information Processing Systems 12, pp. 1057-1063 (2000).
リンク	https://webdocs.cs.ualberta.ca/~sutton/papers/SMSM-NIPS99.pdf
備考	方策のパラメータ勾配の表式、アクター・クリティックのパラメータ更新式など。

表題	Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time Analysis of the Multiarmed Bandit Problem. Machine Leraning, 47(2/3):235-256 (2002).
リンク	https://homes.di.unimi.it/~cesabian/Pubblicazioni/ml-02.pdf
備考	UCBアルゴリズムの原論文。 $\varepsilon$ -greedy 方策において $\varepsilon$ を減衰させたときのリグレットも。

表題	Sebastien Bubeck and Nicolo Cesa-Bianchi. Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems. (2012)
リンク	https://arxiv.org/pdf/1204.5721.pdf
備考	様々な問題設定の多腕バンディットタスクについてリグレットを解析したサーベイ。

強化学習（応用）

表題	David Silver et al., Mastering the Game of Go with Deep Neural Networks and Tree Search (2016)
リンク	http://airesearch.com/wp-content/uploads/2016/01/deepmind-mastering-go.pdf
備考	AlphaGo。
メモ	雑記： AlphaGoって何 - クッキーの日記

表題	Barret Zoph, Quoc Le, Neural Architecture Search with Reinforcement Learning (2016)
リンク	https://openreview.net/forum?id=r1Ue8Hcxg
備考	RNN をどんな風に設計するか自体を強化学習にやらせていると思う。

位相的データ解析（基礎）

表題	Herbert Edelsbrunner, David Letscher, and Afra Zomorodian. Topological persistence and simplification（2002）
リンク	https://www.cs.duke.edu/~edels/Papers/2002-J-04-TopologicalPersistence.pdf
備考	パーシステントホモロジーの原論文。

表題	Robert Ghrist, Barcodes: The Persistent Topology of Data（2008）
リンク	https://www.math.upenn.edu/~ghrist/preprints/barcodes.pdf]
備考	バーコード（＝データ点群から位相情報を抽出したフォーマットの1つ）。