HashedNets

HashedNets [1] を chainer で実装しました。

HashedNets の説明

ニューラルネットワークのパラメータ数は非常に多く、パラメータは冗長な表現になっていることが多いです。

そこで、自由なパラメータの数を減らして、正則化と軽量化を達成するための手法の一つとして HashedNets が考案されました。

HashedNets では、ハッシュ関数を使って、同じハッシュ値となる辺どうしを重み共有します。

具体的にはまず層ごとに自由なパラメータの数 $K$ を決めて $K$ 次元のパラメータ $w$ を用意します。

次に、ネットワークの辺から $\{ 1,..\ K \}$ へのハッシュ関数 $h$ と $\{ -1, 1 \}$ へのハッシュ関数 $\xi$ を定めます。

順伝播させるときには、辺 $i$ の重みは $\xi(i) \cdot w_{h(i)}$ として計算します。

重み共有する辺の決定にハッシュ関数を使うことで、ランダムに割り付けができ、対応関係の情報を陽に持つ必要が無いので容量の削減が実現できます。

実装

Python 3.5.3 + chainer 2.0.1 で実装しました。

gist.github.com

簡単のため $\xi$ は実装していません。

$\xi$ があれば同じパラメータ数でももう少し表現力が上がったかもしれません。

逆伝播の計算では numpy.bincound を使うと便利でした。

実験

$K$ の値を変えて MNIST の分類を 3 層の全結合ニューラルネットワーク行いました。

元のニューラルネットワークにおいてはパラメータ数はそれぞれ $78400 \sim 2^{16.26}, 10000 \sim 2^{13.29}, 1000 \sim 2^{9.97}$ です。

f:id:joisino:20170724190837p:plain

このときの $K = 2^{10}$ 程度あれば正解率 0.95 くらいまで出ています。

容量の圧縮率はパラメータの数だけ見る単純計算で $(78400+10000+1000) / (1024 \cdot 3) \sim 29.10$ 倍くらいです。

最後に

何か間違いや質問などがあればお願いします。

最後まで読んでいただきありがとうございました。

参考文献

[1] W. Chen. et al. (2015) Compressing Neural Networks with the Hashing Trick

2017-07-23

本質的に曖昧な文脈自由言語

本質的に曖昧な文脈自由言語が存在するという事実は色んなところで何度も目にしてきたのですが、証明を見たことが無かったのでここで紹介します。

流れは大体 [1] と同じですが、補題の証明はオリジナルも混ざってます（本質的には同じだとは思います）（間違ってたら教えてください）

今回本質的に曖昧だと示すのは $L = \{ a^{i} b^{j} c^{k} \mid i, j, k \ge 1, i = j \lor j = k \}$ です。（これが文脈自由であることは簡単なので省略します）

ちなみに、これは計算理論の基礎 [2] （めっちゃいい本）の第2版の演習問題 2.29 です。（本に答えは載っていません）

めちゃくちゃ難しいと思うのですが自信のある人は考えてみてください（僕は分かりませんでした）

少しずつ補題を証明していく形式なので、少しずつ読んで考えてみるのも面白いかもしれません。（最後のステップだけでも普通に難しいと思います）

基本的な記法と定義

文脈自由文法を非終端記号 $V_{N} = \{ A_{1}, A_{2},... ,A_{n} \}$ 、終端記号 $V_{T}$ 、生成規則 $R$ 、開始記号 $A_{n}$ の組 $G = ( V_{N}, V_{T}, R, A_{n} )$ で定義します。

生成規則を $A_{i} \rightarrow \alpha_{1}... \alpha_{k}$ のように表します。

生成規則を 0 回以上適用して新しい列を生成することを $A_{i} \rightarrow^{*} \alpha_{1}... \alpha_{k}$ のように表します。

生成規則を 1 回以上適用して新しい列を生成することを $A_{i} \rightarrow^{+} \alpha_{1}... \alpha_{k}$ のように表します。

文法 $G$ が生成する言語を $L(G)$ と表します。

$x, y, w$ は終端記号の列を表すメタ変数とします。

文法 $G$ が既約であるとは、任意の非終端記号 $A_{i}$ について導出の過程で $A_{i}$ を使って言語の要素を導出できることとします。（つまり、開始記号からある非終端記号に到達できなかったり、ある非終端記号から無限ループやデッドエンドに陥って語を生成できないといったことがないということです。）

証明

補題0

任意の曖昧でない文脈自由文法 $G = ( V_{N}, V_{T}, R, A_{n} )$ について、 $L(G') = L(G)$ となる既約な曖昧でない文脈自由文法 $G'$ が存在する。

補題0の証明

到達できない記号や無限ループやデッドエンドに陥る非終端記号を取り除くだけでよいです。

具体的には

$V_{N}^{*} = \{ A_i \mid ( \exists x,y\, s.t.\, A_{n} \rightarrow^{*} x A_i y ) \land ( \exists w\, s.t.\, A_i \rightarrow^{*} w ) \}$ とすると、 $G' = ( V_{N}^{*}, V_{T}, R, A_{n} )$ とすればよいです。

補題1

任意の既約な曖昧でない文脈自由文法 $G = ( V_{N}, V_{T}, R, A_{n} )$ について、 $A_i \rightarrow^{+} A_i$ となることはない。

補題1の証明

$A_i \rightarrow^{+} A_i$ となる非終端記号があると、 $A_{n} \rightarrow^{*} x A_i y \rightarrow^{*} w$ と $A_{n} \rightarrow^{*} x A_i y \rightarrow^{+} x A_i y \rightarrow^{*} w$ と木の形が違う二通りの導出ができてしまうので、曖昧な文法になります。

定義 ( $P(G)$ )

文法 $G$ について $P(G) = \{ A_i \mid \exists x,y\, s.t.\, A_i \rightarrow^{*} x A_i y \land xy \neq \varepsilon \}$

ここで、補題1 より $G$ が既約で曖昧でないとき、 $xy = \varepsilon$ となることはないので、 $A_{i} \not \in P(G)$ のとき $A_{i}$ から $A_{i}$ を含む列を生成することはありません。

定義 (almost looping)

文法 $G = ( V_{N}, V_{T}, R, A_{n} )$ が almost looping であるとは、

$G$ は既約
$A_{1},... ,A_{n-1} \in P(G)$
任意の $w \in L(G)$ の導出において $A_{n}$ は一度しか出現しない

3 の条件が元の論文と少し違うので注意してください。

補題2

任意の既約な曖昧でない文脈自由文法 $G = ( V_{N}, V_{T}, R, A_{n} )$ について、 $L(G') = L(G)$ となる almost looping な曖昧でない文脈自由文法 $G'$ が存在する。

補題2の証明

まず、 3 が成り立っていないときは新しい開始記号 $X$ と規則 $X \rightarrow A_{n}$ を用意すれば、既約性と非曖昧性は変わらず 3 が成り立つので、最初から 3 は成り立っているものとします。

$G_{0} = G$ から非終端記号 $A_{1},... , A_{n-1}$ を 1 つずつ帰納的に処理して $G_{1},... , G_{n-1}$ と変形していきます。

処理の仕方は、ループしない非終端記号については単純に木を 1 段増やすだけなので、そのような非終端記号を文法から取り除いて、子を親に直接つなぐように生成規則を変化させるというやり方です。

具体的には以下のようになります。

(1) $A_{i} \in P(G_{i-1})$ のとき

このときは何も変化させません。

$G_{i} = G_{i-1}$ とします。

(2) $A_{i} \not \in P(G_{i-1})$ のとき

$G_{i-1} = ( V_{N,i-1}, V_{T}, R_{i-1}, A_{n} )$ とします。

$R_{i-1}$ のうち、左辺が $A_{i}$ であるものの集合を $S_{i}$ とします。

$P(G_{i-1})$ の定義と $G_{i-1}$ の非曖昧性（と補題1）より $S_{i}$ の右辺に $A_{i}$ はないはずです。

$A_{i}$ が右辺にある $G_{i-1}$ の生成規則について、 $A_{i}$ の出現をそれぞれ $S_{i}$ の右辺で置き換えたものを　 $R_{i}$ とします。

$A_{i}$ が右辺に $x$ 回出現する規則の場合は、 $|S_{i}|^x$ 個の規則に置き換わります。

そして、 $G_{i} = ( V_{N,i-1} - \{ A_{i} \}, V_{T}, R_{i}, A_{n} )$ とします。

既約性と非曖昧性は (1) の場合は文法が変化していないので成立し、 (2) の場合も、木の $A_i$ が出てくるノードについて子を親に直接つなぐようにしただけなので成立します。

また、 $j \le i$ なる非終端記号 $A_{j} \in V_{N,i}$ について $A_{j} \in P(G_{i})$ です。

これは、(i) は場合分けの定義からそのままで、(ii) も $A_i$ が無くなったので帰納法の仮定からそのまま成り立ちます。

また、生成する言語も変化しません。

以上より $G' = G_{n-1}$ とすれば目標達成です。

補題3

$L(G) = L (= \{ a^{i} b^{j} c^{k} \mid i, j, k \ge 1, i = j \lor j = k \})$ となる almost looping な文脈自由文法 $G = ( V_{N}, V_{T}, R, A_{n} )$ の開始記号でない非終端記号 $A_{i}$ は以下の 3 タイプのうちちょうど 1 つにあてはまる

$n_i, m_i \ge 0, n_i + m_i \ge 1$ が存在して $A_{i} \rightarrow^{+} a^{n_i} A_{i} a^{m_i}$ または $A_{i} \rightarrow^{+} c^{n_i} A_{i} c^{m_i}$
$n_i \ge 1$ が存在して $A_{i} \rightarrow^{+} a^{n_i} A_{i} b^{n_i}$
$n_i \ge 1$ が存在して $A_{i} \rightarrow^{+} b^{n_i} A_{i} c^{n_i}$

補題3の証明

まず各非終端記号がどのタイプかに属することを示します。

almost looping の定義から、 $A_{i} \rightarrow^{*} x A_{i} y \rightarrow^{*} w \land xy \neq \varepsilon$ となります。

ここで、 $x$ または $y$ に二種類以上の非終端記号を含むとすると、 $A_{i} \rightarrow^{*} x A_{i} y \rightarrow^{*} xx A_{i} yy$ となり、 $L$ が $a, b, c$ の順に並ばなければいけないことに反します。

よって、 $x$ と $y$ に含まれる非終端記号は高々 1 種類となり、ありえる組み合わせは次の 16 通りです

x	y	タイプ
空	空	ありえない(i)
a	空	1
b	空	ありえない(iii)
c	空	1
空	a	1
a	a	1
b	a	ありえない(ii)
c	a	ありえない(ii)
空	b	ありえない(iii)
a	b	2(v)
b	b	ありえない(iii)
c	b	ありえない(ii)
空	c	1
a	c	ありえない(iv)
b	c	3(v)
c	c	1

(i) について: $xy \neq \varepsilon$ です。

(ii) について: $L$ が $a, b, c$ の順に並ばなければいけないことに反します。

(iii) について:

$x = b^{s}, y = b^{t}$ とします。

$A_{n} \rightarrow^{*} u A_{i} v \rightarrow^{*} a^{i} b^{j} c^{k} \in L$ とします。

この真ん中の段階において、 $A_{i} \rightarrow^{*} x A_{i} y$ を $i+k+1$ 回繰り返すと、 $A_{n} \rightarrow^{*} a^{i} b^{j+(s+t)(i+k+1)} c^{k} \not \in L$ となり矛盾します。

(iv) について:

$x = a^{s}, y = c^{t}$ とします。 $A_{n} \rightarrow^{*} u A_{i} v \rightarrow^{*} a^{i} b^{j} c^{k} \in L$ とします。

この真ん中の段階において、 $A_{i} \rightarrow^{*} x A_{i} y$ を $j+1$ 回繰り返すと、 $A_{n} \rightarrow^{*} a^{i+s(j+1)} b^{j} c^{k+t(j+1)} \not \in L$ となり矛盾します。

(v) について:

$x = a^{s}, y = b^{t}, s \neq t$ とします。

$A_{n} \rightarrow^{*} u A_{i} v \rightarrow^{*} a^{i} b^{j} c^{k} \in L$ とします。この真ん中の段階において、 $A_{i} \rightarrow^{*} x A_{i} y$ を $i+j+k+1$ 回繰り返すと、 $A_{n} \rightarrow^{*} a^{i+s(i+j+k+1)} b^{j+t(i+j+k+1)} c^{k} \not \in L$ となり矛盾します。

よって $s = t = n_{i}$ です。

$x = b^{s}, y = c^{t}$ のときも同様です。

次に、どれか一つのタイプにしか属せないことを示します。

仮に、タイプ 1 とタイプ 2 に属していたとすると、

$A_{i} \rightarrow^{*} a^{s} A_{i} b^{s} \rightarrow^{*} a^{s} a^{t} A_{i} a^{u} b^{s} ( s \ge 1, t+u \ge 1 )$ となります。

$y$ は一種類の終端記号しか生成してはいけないので、 $u = 0$ または $s = 0$ です。

$s = 0$ のとき $s \ge 1$ に反します。

$u = 0$ のとき (v) の議論から $t = 0$ となり $t+u \ge 1$ に反します。

これは矛盾です。

タイプ 1 とタイプ 3 についても同様です。

仮に、タイプ 2 とタイプ 3 に属していたとすると、

$A_{i} \rightarrow^{*} a^{s} A_{i} b^{s} \rightarrow^{*} a^{s} b^{t} A_{i} c^{t} b^{s} ( s, t \ge 1 )$ となります。

$L$ が $a, b, c$ の順に並ばなければいけないことに反します。

以上より示せました。

補題4

$L(G) = L$ となる almost looping な文脈自由文法 $G = ( V_{N}, V_{T}, R, A_{n} )$ について、 $w \in L$ が $A_{n}$ と補題3のタイプ1の非終端記号からのみ生成できるとき、 $w$ に含まれる $b$ の個数は $l_{G}$ 個以下となる（ $l_{G}$ は文法 $G$ により定まる定数）

補題4の証明

$w$ の導出木を考えます。

almost looping なので、 $A_{n}$ は一度しか現れません。

タイプ1の非終端記号 $A_{i}$ を表す頂点 $v$ の子孫に $A_{i}$ を表す頂点 $u$ が現れるとき、 $v$ の部分木を $u$ の部分木で置き換えても $b$ の個数は変わりません。

これを繰り返して、子孫に同じ非終端器号が現れない木 $T$ を作り、これが表す終端記号列を $w'$ とします。

根からのパスに同じ非終端記号が現れないので $T$ の深さは $n+1$ 以下です。

$R$ の生成規則の右辺に現れる記号の最大数を $r$ とします。

すると、 $|w'| \le r^{n}$ なので、 $w$ に含まれる $b$ の個数も $r^{n}$ 個以下です。

よって、 $l_{G} = r^{n}$ とすれば良いことが分かります。

$L$ が本質的に曖昧であることの証明

背理法により証明します。

$L$ を生成する曖昧でない文法 $G$ が存在したと仮定します。

補題0 より、 $L$ を生成する既約で曖昧でない文法 $G'$ が存在します。

補題2 より、 $L$ を生成する almost looping な曖昧でない文法 $G^{*}$ が存在します。

補題3 のタイプ 2 とタイプ 3 について $n_i$ を全て掛けあわせたものを $K$ とします。

補題4 の $l_{G}$ について、 $p > l_{G^{*}}$ となる $K$ の倍数 $p$ をとります。

$w_{1} = a^{p} b^{p} c^{2p} \in L$ を考えます。

$p > l_G^{*}$ なので、補題 4 より、タイプ 2 かタイプ 3 の非終端記号が $w$ の導出の過程で現れます。

仮にタイプ 3 の非終端記号 $A_{i}$ が $w$ の導出で出現したとすると、

$A_{n} \rightarrow^{*} u A_{i} v \rightarrow^{*} a^{p} b^{p} c^{2p}$

$A_{n} \rightarrow^{*} u A_{i} v \rightarrow^{*} u b^{p} A_{i} c^{p} v \rightarrow^{*} a^{p} b^{2p} c^{3p} \not \in L$

となり矛盾するので、 $w$ の導出にはタイプ 3 の非終端記号は含まれていません。

よって、タイプ 2 の終端記号 $A_{j}$ が $w$ の導出の過程で出現します。

$A_{n} \rightarrow^{*} u A_{j} v \rightarrow^{*} a^{p} b^{p} c^{2p}$

$A_{n} \rightarrow^{*} u A_{j} v \rightarrow^{*} u a^{p} A_{j} b^{p} v \rightarrow^{*} a^{2p} b^{2p} c^{2p}$

この導出の過程でタイプ 2 の非終端記号が出現し、タイプ 3 の非終端記号は出現しません。

同様に $w_{2} = a^{2p} b^{p} c^{p} \in L$ を考えると、タイプ 3 の非終端記号が出現し、タイプ 2 の非終端記号は出現しないような $a^{2p} b^{2p} c^{2p}$ の導出があります。

これは $a^{2p} b^{2p} c^{2p}$ の異なる導出木があることを意味し、 $G^{*}$ が曖昧な文法となり、矛盾が生じます。

よって、 $L$ は本質的に曖昧です。

最後に

もしもっと簡単に証明できるのならぜひ教えてください。

何か間違いや質問などがあればお願いします。

最後まで読んでいただきありがとうございました。

参考文献

[1] Herman A. Maurer. (1969). A Direct Proof of the Inherent Ambiguity of a Simple Context-Free Language.

[2] Michael Sipser. (2008). 計算理論の基礎 [原著第2版] 1.オートマトンと言語. (訳書)

2017-07-20

Adam

Adam [1] を chainer で実装しました。

Adam の説明

少ない時間・空間計算量で高い性能を出すということで、深層学習の分野で最近よく使われている最適化手法です。

$\theta$ をパラメータに取る関数 $f(x,\theta)$ の（期待値）最小化を考えます。 $f$ の $\theta$ に対する勾配を $g$ とします。

一番元となったアルゴリズムは SGD ( stochastic gradient descent ) です。

SGD は以下のようにパラメータを更新するものでした。

$t \leftarrow 1$ とする
$x$ をサンプルする
$\theta_{(t)} \leftarrow \theta_{(t-1)} - \alpha \cdot g(x,\theta_{(t-1)})$
収束したら終了
$t \leftarrow t + 1$
2 に戻る

Adam では、 3 のステップを以下の処理に置き換えます。

$\displaystyle m_{(t)} \leftarrow \beta_{1} \cdot m_{(t-1)} + ( 1 - \beta_{1} ) \cdot g(x,\theta^{(t-1)})$
$\displaystyle v_{(t)} \leftarrow \beta_{2} \cdot v_{(t-1)} + ( 1 - \beta_{2} ) \cdot g(x,\theta^{(t-1)}) \odot g(x,\theta^{(t-1)})$
$\displaystyle \hat{m}_{(t)} \leftarrow \frac{m_{(t)}}{ 1 - \beta_{1}^{t} }$
$\displaystyle \hat{v}_{(t)} \leftarrow \frac{v_{(t)}}{ 1 - \beta_{2}^{t} }$
$\displaystyle \theta_{(t)} \leftarrow \theta_{(t-1)} - \alpha \cdot \frac{\hat{m}_{(t)}}{ \sqrt{\hat{v}_{(t)}} + \varepsilon }$

ここで、 $m_{(0)}, v_{(0)}$ は $0$ に初期化されているものとし、 $\odot$ は要素ごとの掛け算を表します。

論文では、 $\alpha = 0.001, \beta_{1} = 0.9, \beta_{2} = 0.999, \varepsilon = 10^{-8}$ 程度を目安としています。

1, 2 については、 $g$ と $g^{2}$ (要素ごとの自乗) の指数移動平均を求めています。

過去の結果をできるだけ使いたいが、パラメータが変化したことで分布も変化するので、このような指数移動平均を使っているのだと思います。

また、こうすることで時間と共に $f$ が変化するような問題にもうまく適合するようになるようです。

3, 4 では、正規化のようなことをしています。

例えば、 $g$ が一定値 $g_0$ をとるものとすると、 $\hat{m} = g_0$ となります。

5 が、 SGD における 3 に直接対応するものです。

$\varepsilon$ は $\hat{v}$ が極端に小さかったときに数値的な安定を保つためのものなのであまり深く考えなくても良いと思います。

$g$ の代わりに、移動平均を正規化した $\hat{m}$ を使い、 $\sqrt{\hat{v}}$ で割って変化量を正規化しています。

$\sqrt{\hat{v}}$ で割っていることで、 $f$ を定数倍しても、 $\theta$ の変化量は変わりません。

また、変化量はおおよそ $\alpha$ で抑えられます。

このようなスケールに対する不変性があるので、様々な問題に対して少ないハイパーパラメータのチューニングでうまく適合できるようです。

実装

Python 3.5.1 + chainer 2.0.0 を使って実装しました。

gist.github.com

実験

MNIST の分類を 3 層の全結合ニューラルネットワーク行いました。

f:id:joisino:20170719160803p:plain

訓練データ、テストデータ共に、少ない反復回数で高い認識率を示しています。

最後に

何か間違いや質問などがあればお願いします。

最後まで読んでいただきありがとうございました。

参考文献

[1] Kingma, Diederik P. et al. (2015) Adam: A Method for Stochastic Optimization

2017-07-16

大学のソフトウェア実験用のプログラム自動生成

大学のソフトウェア実験でMLのインタプリタを作っているのですが、テスト用にMLプログラムの自動生成プログラムを書きました。

generator.sh は一部 @basemusi 君に書いてもらってます。

github.com

型推論器のデバッグ用に作ったのでこの名前ですが、インタプリタ部分でも使えるはずです。

中身の説明

`main.cpp`

文法の開始記号から生成規則をランダムに適用していっています。

一番小さい非終端記号の aexpr に到達した回数が一定以上になると木をそれ以上大きくしないようにして木の大きさを調整しています。

生成規則の選び方をハードコーディングしていたり、木を作りながらその場でどんどん標準出力に出すというひどい実装です。30分くらいで書いたので許してください。

`generator.sh`

main.cpp では文法に合うデタラメなプログラムを生成するので、この出力を OCaml インタプリタに食わせて、型が正しく付いたものだけを出力するようにしています。

実行例

実行例を掲載します。

seed は固定なので、どの環境でも同じものが出力されると思います。

他のものを出力したければ、generator.sh をいじって seed を変更してみてください。

# bash generator.sh -n 10
let a = fun c -> 7 + 7 + 3 < 7;;
fun a -> 1 + 9 + 2;;
let b = fun b -> 5 + ( let rec c = fun c -> fun c -> true in 9 ) + 6;;
8;;
let rec a = fun b -> 8 + 7 + 5 + 8;;
let a = 9;;
6;;
4 + 5 + 7;;
let c = 4 + 3 + 6 + 6 + 3 < 4;;
let rec b = fun b -> false;;

# bash generator.sh -n 10 -1
false;;
5;;
4;;
1 + 2 + 5;;
4;;
7 + ( 8 ) < 5;;
2 < 7;;
false;;
2 + 9 + 2;;
7 + 7 + ( 7 );;

# bash generator.sh -n 10 -2
1 + 2 + 5;;
let b = 6 < 6 + 4;;
let b = 9;;
let a = 7 + ( 8 );;
let a = 6;;
let c = 1;;
let c = 2 + 7 + 8;;
3 < 5;;
let b = 8 + 8 + 3;;
let c = if let b = 2 + 3 < 3 + 1 in false then 6 else 2;;

# bash generator.sh -n 10 -3
let c = 3 < 2;;
false;;
let b = 6 < 6 + 4;;
let a = 7 + ( 8 );;
let a = 6;;
let a = fun b -> 9 + 2;;
let c = 2 + 7 + 8;;
3 < 5;;
let b = 8 + 8 + 3;;
let b = 4 + 6;;

おわりに

雑に書いたので実装はひどいですが、デバッグにはある程度使えるはずなので、来年以降実験を履修するひとは使ってみてください。

何か間違いや質問などがあればお願いします。

最後まで読んでいただきありがとうございました。

2017-07-13

Dilated Convolution

Dilated Convolution を chainer で実装しました。

Dilated Convolution の説明

Dilated Convolution は、フィルターとの積を取る相手の間隔をあける畳み込みのことです。

例えば、以下のような画像において、 12 を中心に 3 x 3 の普通の畳み込みフィルターを適用すると、 6, 7, 8, 11, 12, 13, 16, 17, 18 との積を取って和を取ると思います。

0	1	2	3	4
5	6	7	8	9
10	11	12	13	14
15	16	17	18	19
20	21	22	23	24

3 x 3 の dilate = 2 の Dilated Convolution フィルターを 12 を中心に適用すると、0, 2, 4, 10, 12, 14, 20, 22, 24 と 1 つおきに取ってきて、それらに 3 x 3 の畳み込みフィルターを適用します。

これは 5 x 5 の通常の畳み込みフィルターのうち、9 箇所以外を 0 に固定したものと見ることもできます。

dilate = 1 の Dilated Convolution は普通の畳込みになります。

dilate が 1 増えるごとに間隔が 1 ずつ開きます。

縦横で異なる dilate を使用する場合もあります。

この Dilated Convolution の何が嬉しいかというと、受容野（あるマスに影響する入力部分）を簡単に増やすことができることです。

例えば、 3 x 3 の畳み込み層を 10 層適用すると、出力の 1 つのマスにある情報は、最初の層の 21 x 21 の部分の情報をまとめたものになります。

入力画像がとても大きい場合、これではごく局所的な情報しか集約できていません。

ここで、簡単に受容野を増やすには

層の数を増やす
フィルターを大きくする
プーリング層を使う

などの方法があります。

1, 2 については、受容野の一辺の長さは層数とフィルターの一辺の長さに対して線形なので、画像がとても大きい場合はあまり有用ではありません。

3 は簡単に情報を集約できるので有用で、昔からよく使われてきました。

ただ、3 の欠点の一つとして、プーリング層を入れると画像がその分小さくなってしまうことがあります。

例えば画像を入力として、そのうち人間が写っている部分を出力したいといったタスクを考えると、できるだけ元の入力と同じ大きさの画像を出力したいです。

また、ネットワークを深くしたいときに画像の大きさによって限界がきてしまうのも困ります。

そこで、Dilated Convolution を使うと、この欠点なしに情報を集約できます。

よく使われるのは、Dilate を 1, 2, 4, 8, 16, …, 512 と指数的に増やす方法です。

こうすると、パラメータ数は層数に線形なのに対して、受容野の大きさを指数的に増やすことができ、画像もそこまで小さくなりません（パディングで対応できる程度です）。

実際に、 Dilated Convolution は大域的な情報が必要なタスクでは有用なようです。

実装

gist.github.com

chainer で実装してみました。

最初は愚直な 7 重ループで実装したのですが、重すぎて学習が始まらなかったので書き直しました。

numpy 配列をまとめて計算するのとランダムアクセスするのが同じ計算時間でできると思うと痛い目をみるようです。

このへんの細かい仕様はよく分かってないのでまた調べたいです。

二度目の実装にあたっては chainer の dilated_convolution_2d を大いに参考にしました。

相違点として気をつけるべきなのが、変形後の x の次元が、chainer の方では (batch, in_layer, conv_y, conv_x, out_height, out_width) なのに対し、この実装は (batch, in_layer, out_height, out_width, conv_y, conv_x) となってることです。

こちらの方が直感的だとは思ったのですが、よく考えると画像の大きさよりもフィルターの大きさの方が小さいので、 chainer の実装方針でやったほうが効率は良いはずです。

他にも要因はあるかと思いますが、実際に速度は 4 倍ほど chainer の実装の方が速いです。

また、パラメータの初期値でもハマりました。

最初は全てのパラメータを平均 0 分散 1 の正規分布で初期化していたのですが、さすがに大きすぎたようでほとんど精度が出ませんでした。

chainer 標準の initializer を使うとうまくいきました。

initializer も中身をよく理解していないのでまた調べたいです。

実験

MNIST の分類を行いました。

Dilated Convolution

f:id:joisino:20170712164414p:plain

通常の Convolution

f:id:joisino:20170712164439p:plain

ほとんど変わりませんね。

むしろ最終的に dilate = 1 の方が精度が出ていて残念です。

MNIST の分類程度では違いは出ないということなのでしょうか。

Dilated Convolution のほうでもちゃんと学習が進んでくれたのでよしとします。

最後に

何か間違いや質問などがあればお願いします。

最後まで読んでいただきありがとうございました。

参考文献

[1] F. Yu et al. (2015). Multi-Scale Context Aggregation by Dilated Convolutions

[2] Dilated Convolutions and Kronecker Factored Convolutions ( http://www.inference.vc/dilated-convolutions-and-kronecker-factorisation/ )

[3] van den Oord et al. (2016). WaveNet: A Generative Model for Raw Audio

2017-07-09

Batch Normalization

Batch Normalization [1] を chainer で実装しました。

色々な場合に適用できて、学習速度が速くなったり汎化性能が上がったりするすごいテクです。

Batch Normalization の説明

上層（出力層に近い層）の入力は、当然下層（入力層に近い側）のパラメータに依存します。

学習が進むにしたがって下層のパラーメータは変化するので、それにしたがって上層の入力の分布が変化します。

このような中間層の入力の分布の変化を Internal Covariate Shift と呼びます。

入力の分布が変化した層はそれに合わせてパラメータも学習しなおさなければなりません。

これが、学習の速度を下げる要因になります。

Batch Normalization は、Internal Covariate Shift が起きないように各層の入力の分布を一定に保とうとするテクです。

具体的には、各層の入力 ( = 前層の出力 ) をバッチごとに標準化します。

$\displaystyle \mu = \frac{1}{m} \sum_{i=1}^{m} x_i$

$\displaystyle \sigma^{2} = \frac{1}{m} \sum_{i=1}^m ( x_i - \mu )^{2}$

$\displaystyle \hat{x} = \frac{ x - \mu }{ \sqrt{ \sigma^{2} + \varepsilon } }$

ここで、 $\varepsilon$ は $\sigma^{2}$ が $0$ に近い時に数値的な安定を保つためのハイパーパラメーターです。

ただ標準化するだけでは、例えば活性化関数にシグモイドを使っていた場合に線形部分しか使われなくなるかもしれないなどの問題が生じるかもしれません。

そこで、パラメータとして新しく $\beta$ と $\gamma$ を用意して、

$\displaystyle y = \gamma \hat{x} + \beta$

と線形変換して、これを新しい入力とすれば完成です。

Batch Normalization は、Internal Covariate Shift を抑制するだけでなく、層の入力が異常に大きくなって勾配が消失してしまう問題を防いだり、学習率を大きくしたときにパラメータが発散してしまう問題を防ぐなどの効果もあるようです。

実装

gist.github.com

学習が終わって推論の段階で、バッチの組み合わせによって同じ入力が違う出力になるのがつらいときは、学習時の統計を使って $\hat{x}$ の変換式を固定すると良いようですが、今回は実装していません。

実験

三層のパーセプトロンで MNIST の分類を行いました。

Batch Normalization なし

f:id:joisino:20170706120414p:plain

Batch Normalization あり

f:id:joisino:20170706120428p:plain

links.BatchNormalization を使った場合

f:id:joisino:20170706120441p:plain

Batch Normalization を入れると、最終的な汎化性能は変わりませんが学習速度は速くなっています。

自作の BatchNormalization は chainer に入っている links.BatchNormalization と性能はほとんど同じになっています。

ただし、自作の BatchNormalization は自分で勾配を計算したわけではなく既存の functions を組み合わせて作ったので、速度は 4 割ほど落ちます。

最後に

何か間違いや質問などがあればお願いします。

最後まで読んでいただきありがとうございました。

参考文献

[1] Ioffe, S. et. al. (2015). Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift

2017-07-06

Generative Adversarial Nets

Generative Adversarial Nets [1] を chainer で実装しました。

いわゆる GAN です。

最近いろいろ派生系が出ています。画像の生成モデルはほとんどこれの派生な気がします。

画像を生成する Generator （以下 G）と、画像が本物か G が生成したものかを識別する Discriminator (以下 D) という 2 つのモデルを同時に学習させていきます。

論文に書いてあるように、G は偽札製造業者、 D は警察という類推がわかりやすいです。

業者は警察にバレないように紙幣にできるだけ似せたものの作り方を学ぶ一方で、警察はより精巧な偽札を本物と区別できるように学習する、ということを繰り返すうちに、互いの技術は向上していきます。

これと同様に、G は生成するデータと教師データが D に区別できないようなパラメータを学習する一方で、 D は本物のデータか G が生成したデータかを正しく識別するようパラメータを学習していきます。

具体的には、以下の式で最適化します。

$\displaystyle min_{G} max_{D} V(D,G) = \mathbb{E}_{x \sim p_{data}(x)}[log D(x)] + \mathbb{E}_{z \sim p_{x}(z)}[log(1-D(G(z)))]$

$p_x(z)$ は G に食わせるデータです。一様分布から生成されるノイズなどを使う場合が多いようです。

教師データを正例、G の生成したデータを負例としたときの交差エントロピー誤差をお互い最適化するということです。

論文に証明が書いてある通り、この関数の大域最適解において、G が生成するデータの分布と、教師データの分布は一致します。

あとはこれを逐次的に最適化していけばよいです。

今回の実装では、教師データに MNIST を使いました。

ソースコードは以下の通りです。

gist.github.com

生成した画像は以下の通りです。（学習の最後に出力された 10 枚を掲載します）

f:id:joisino:20170703180931p:plain f:id:joisino:20170703180935p:plain f:id:joisino:20170703180939p:plain f:id:joisino:20170703180943p:plain f:id:joisino:20170703180947p:plain f:id:joisino:20170703180950p:plain f:id:joisino:20170703180954p:plain f:id:joisino:20170703180957p:plain f:id:joisino:20170703181000p:plain f:id:joisino:20170703181006p:plain