No bad local minima: Data independent training error guarantees for multilayer neural networks

論文

今まで「3行で」コーナーやってたけど、「概要でよくね？」という気がしてきたし、なんとなく馬鹿らしくなってきたのでやめる。

"No local bad minima"というタイトル見た瞬間面白そうだと思ったので読もうと思った。

概要

ニューラルネットの学習誤差をネットワークの構造によって解析的に評価しようという内容。
凸最適化ならば勾配法で最適化できることが保証されるが、非凸最適化の場合は極小値にトラップしてしまい、最適な学習ができない可能性がある。
しかし、非凸な誤差関数でも学習誤差を抑えることができることを示している。
前提として誤差関数を勾配法で最小化する学習を想定しているので、誤差関数の微分可能な極小値(DLM; Differentiable Local Minimum)における解析を行う。
隠れ層1層の場合は意外とシンプルな解析で評価できるので、そのアナロジーで隠れ層の層数が一般の場合に拡張し、極小値における安定性を議論している。

隠れ層数が1の場合

f:id:levelfour:20160604160445p:plain

まず、教師データを(x,y)、第l層の活性化要素をa_l、出力をv_l、全体の推定誤差をe、ニューラルネットの総層数をLとして以下のように定式化する。

v_l=\mathrm{diag}({a_l})W_lv_{l-1}
e=v_L-y

活性化関数は非線形の関数(シグモイド関数等)が用いられることもあるが、ここでは線形の関数およびその組合せで書ける関数(ReLU, max-pooling等)に限定する。このように制限すると、活性化の定式化を上記のように行列演算を用いて行うことができ、解析の都合上楽になる。
最近の結果では、特にCNN等複雑な構造になればなるほど、下手に非線形関数を活性化関数に用いるよりも、ReLUを用いた方が高精度な識別器が得られることが多い。

例えばReLUの場合、

  • a_iu_i=u_i (u_i>0の場合)
  • a_iu_i=0 (otherwise)

を実現するには

  • a_i=1 (u_i>0の場合)
  • a_i=0 (otherwise)

で十分。

次に、誤差関数(MSEを用いる)の定式化は

\displaystyle \mathrm{MSE}=\frac{1}{2}\mathbb{E}[e^2]=\frac{1}{2N}\sum_{i=1}^N(e^{(n)})^2=\frac{1}{2N}\|\boldsymbol{e}\|^2

となる。ただし、Nは訓練データ数である。

隠れ層数1としてMSEの式をもう少し整理すると

\displaystyle \mathrm{MSE}=\frac{1}{2}\mathbb{E}\left[(y-W_2\mathrm{diag}(a_1)W_1x)^2\right]=\frac{1}{2}\mathbb{E}\left[(y-a_1^\mathrm{T}\mathrm{diag}(w_2)W_1x)^2\right]

となる。活性化行列が対角成分しか持たないので、W_2もその対角成分w_2しか寄与しない。
ニューラルネットのパラメータ行列をまとめて\tilde{W_1}=\mathrm{diag}(w_2)W_1と書くと、

\displaystyle \mathrm{MSE}=\frac{1}{2}\mathbb{E}\left[(y-a_1^\mathrm{T}\tilde{W_1}x)^2\right]

となる。シンプルな形になった。

さて、極小点ではパラメータ行列\tilde{W_1}に関する微分係数が0、すなわち

\nabla\mathrm{MSE}=\mathbb{E}[ea_1x^\mathrm{T}]=0

である。もう少し具体的に書き下すと、

e^{(1)}a_1(x^{(1)})^\mathrm{T}+\cdots+e^{(N)}a_1(x^{(N)})^\mathrm{T}=0

である。紛らわしいのだが、eやxに関する上付き添字は個々の訓練データのインデックスである。

これをクロネッカー積*1を用いて次のような行列G_1を定義する。
（余談だが、クロネッカー積という単語を見たときはじめはクロネッカーのデルタと関係があるのかと思ったが、想像以上に関係無かった。テンソル積の行列だった。詳細はWikipediaを参照されたい）

\displaystyle G_1=[a_1\otimes x^{(1)},\cdots,a_1\otimes x^{(N)}]

すると、極値条件はシンプルに記述できる。

G_1\boldsymbol{e}=0

ややこしく見えるが、先程の極値条件を成分ごとに分解し、「各成分=0」という条件式を並べたのが最後のG_1\boldsymbol{e}=0になる。

さて、この条件は\boldsymbol{e}\in\ker G_1と言い換えられる。核空間\ker{G_1}の次元はN-\mathrm{rank}({G_1})だが、もし仮に行列G_1がフルランクだったとすると核空間の次元は0になるので、\boldsymbol{e}=0、すなわちMSEが0になる。

ところで、先程のクロネッカー積による表示は、一般にはKhatari-Rao積といい、Khatari-Rao積に関するいくかの事実を適用すると、N\le d_1d_0のときにMSEが0になることがいえる。

この結果自体は、パラメータ数が訓練標本数よりも多いことが条件として課されているので、MSEが0になるのはある意味で当然であるように感じられるが、グローバルな最小解だけでなくローカルな極小解にトラップしてもMSEが0に収束することが保証されているという意味で価値があるのだろう。

隠れ層数がL一般の場合

式を追うのに疲れたので割愛するが 基本的には1層の場合と同様の解析手法を適用することができる。
ただし隠れ層間の依存関係があるので、最後の2層以外はパラメータを固定し、最後の2層に同じ議論を適用するといった工夫が必要だ。

f:id:levelfour:20160604171225p:plain

感想

内容としては理論系の論文の中でも新規アルゴリズム提案といったものでもなく、一般にはインパクトを出すのは難しそうに感じるが、数値実験によっても目に見えやすい結果で、こういうパターンもあるのかと感じた。
結果自体はover-parametrizedしたら誤差が0になるというのは自明に感じられてしまうのでアレなのだが、解析手法自体はなかなか興味深かった。
類似の解析手法を積み重ねれば、さらにstrictな結果を述べることができるのだろうか？

参考

  1. [1605.08361] No bad local minima: Data independent training error guarantees for multilayer neural networks

*1:クロネッカー積 - Wikipedia

Learning Multiagent Communication with Backpropagation

論文

果たしてこのシリーズが続くのか、はたまた3日坊主になるのか。
（まあ流石に毎日やるつもりはないのだけど）

3行で

  • マルチエージェントシステムに関して
  • 相互に通信するようなニューラルネット(CommNNと呼ばれている)を用いて制御
  • 交通渋滞回避などに応用できそう

概要

マルチエージェントシステムは元々生体の形態形成に触発されて提唱された計算パラダイムで、個々の個体(computational particleとか、または普通にエージェントとか呼ばれるみたい)はすべて同様のプログラムで動いていて、システム全体として見ると計算が行われるようなシステムのことを指す。
エージェントは自分のglobalな位置を知ることはできず、半径r内近傍のエージェントとの距離や、自身の状態を知ることのみ許されている。

具体的な例としては、ハーバード大学で開発された群ロボットであるKilobotが有名だろう。

www.youtube.com

マルチエージェントシステムは、分散計算やロボティクス等の分野での応用が期待されている。
今回は、マルチエージェントの制御にニューラルネットを用いるという研究である。
エージェントにどのように動くべきか予めプログラムを与えずに、環境からの報酬を元に最適な挙動を学習する、所謂強化学習を行う。

提案手法

ニューラルネットとしてのマルチエージェントシステム

まず、各エージェントの挙動について、

  • 個々のエージェントが自身のプログラムに従って動作する
  • マルチエージェントシステム全体をモデルとして見做し、モデルがエージェントを同時に制御する

という2つの見方ができる。今回は後者の見方を採用する。
するとこのモデルとして、全エージェントの報酬・位置・状態を入力として受け取り、各エージェントの行動を出力するニューラルネットを考えることができる。

通信モデル

エージェントjの状態h_j^iは次の関係で決まるとする。

{\displaystyle h_j^{i+1}=f^i(h_j^i,c_j^i) }
{\displaystyle c_j^{i+1}=\frac{1}{J-1}\sum_{j'\ne j}h_{j'}^{i+1} }

ここで、上付き文字iはi回目の通信ステップ、f^iはニューラルネット、Jはエージェント数を表す。
各イテレーションでは各エージェントが他のエージェントからメッセージを受信し、それ(c_j^{i})を用いて自身の状態h_j^iを計算する。

f:id:levelfour:20160601143033p:plain
(図は論文より引用)

Figure 1はf^iが隠れ層なし1層のニューラルネット、すなわち活性化関数\tanhのみのニューラルネットの場合を図示化したものだ。

強化学習ではエージェントjは状態s_jから次に取るべき行動a_jを選択する。
これは、ニューラルネットの入力h_j^0を

\displaystyle h_j^0=r(s_j)

のようにして得る。rはエンコーダ関数であり、問題に依存する。同様に出力は

\displaystyle a_j=q(h_j^K)

のようにして得る。

モデルの拡張

上記で定式化した通信モデル(ConnNN)にいくつかの拡張を加える。

まず、Local Connectivityを導入する。冒頭でマルチエージェントシステムは「各エージェントが近傍の他のエージェントの状態しか知り得ない」と触れていたが、上記の定式化ではglobalにエージェントの情報を知ることができる。
勿論モデルとしては近傍半径r=\inftyとすれば妥当ではあるのだが、応用問題を考えたときに不適当である。
そこで、エージェントjは集合N(j)\subset\{1,\cdots,J\}に含まれるエージェントとしか通信できないものと制限する。
このような制限を加えると、c_j^iの更新式は

\displaystyle c_j^{i+1}=\frac{1}{|N(j)|}\sum_{j'\in N(j)}h_{j'}^{i+1}

と変更される。N(j)はシステムの遷移とともに変化する。

次に、先程提示したhとcに関する漸化式の添字iは各通信ステップに関する添字だったが、時間遷移として見做すことができる。
すると、モデル全体が時間再帰型のNN、つまりRecurrent Neural Networkとしてみなせる。論文中の実験ではLSTMを用いて実装も実験の一例として行っている。

最後に、入力h_j^0を常にニューラルネットの入力として与えると便利らしい。

\displaystyle h_j^{i+1}=f^i(h_j^i, c_j^i, h_j^0)

Skip Connectionsと呼ばれている。

応用例

応用例としていくつか上げられているが、個人的に渋滞緩和の例(5.2.1)が最も面白かったので、それを取り上げる。

f:id:levelfour:20160601145412p:plain
(図は論文からの引用である)

Figure 2の左図のように、このシミュレーションでは交差点の各方向から一定の確率で車がランダムに出現する。
出現した車は交差点でいずれかの方向に進み、その過程で

  • (gas) 自分の進行ルート上を1マス進む
  • (brake) その場で止まる

のいずれかの動作を行う。

車の衝突とは、不幸にも同タイミングで同セルに2つ以上の車が存在してしまうことである。このシミュレーションでは、衝突しても報酬の変化以外には何も影響を与えない（衝突しても無視して進み続ける）。
交差点に現れてから出て行くまでに各車は

\displaystyle r(t)=C^tr_{coll}+\sum_{i=1}^{N^t}\tau_ir_{time}

だけの報酬を得ることになる。ただしC^tは衝突回数、N^tは交差点上に存在した時間ステップ数、r_{coll}、r_{time}はそれぞれ衝突と時間経過における報酬である。報酬とはいえども、どちらも負の値なのでどちらかと言えばペナルティである。
つまり、この強化学習では「できるだけ衝突せずに速く交差点を通過する」ことを目的とする。

詳細なニューラルネットの構成については論文を参照してただきたい。結論としては、エージェント間の通信を行うことによって大幅に衝突率を下げることができるということだ。
これは単なるシミュレーションなので実際に活用できるかどうかについては疑問が残るが、自動運転技術の実用化が視野に入りつつある中、興味を惹かれる内容だった。

シミュレーションの様子は動画もあり、論文中にYouTubeへのリンクがある。
（一応URLを知っている人のみのアクセス制限がかかっているようなので、ここからの直接リンクは遠慮しておく）

参考

  1. [1605.07736] Learning Multiagent Communication with Backpropagation

Learning Deep Structured Semantic Models for Web Search using Clickthrough Data

論文

大学の4年生ともなるので、"ちゃんと"論文を読み込んでストックしたいと思い、ブログに読んだ論文を簡単にまとめていきたい。
巷では「百本読むまで人権無し」とも言われるそうなので、できるだけある程度の頻度でアウトプットしていければなと思っている。

（そういうことはないよう努力は尽くすが）間違っていることもあるだろうから、読まれる方はぜひ鵜呑みにせず、遠慮無くご指摘いただきたい。

3行で

  • 3層のニューラルネットを用いて
  • Word Hashingと呼ばれる次元削減手法で効率的に
  • 文章の潜在意味が学習できた

概要

de:code 2016にてMicrosoftの女子高校生風会話エージェント「りんな」のバックエンドについてのセッションがあったのは記憶に新しい人も多いだろう。

http://internet.watch.impress.co.jp/docs/event/20160526_759214.htmlinternet.watch.impress.co.jp

見てみると「DSSM + RNN-GRU」で実現されているらしい。
RNNは「まあそうだよな」という一方、「DSSMってなんだ？」という疑問があったので、元論文を読んでみた。
それが今回の論文で、Microsoftが2015年にpublishした論文だ。

元々はWeb検索において、検索クエリとクリックしたページ(Clickthrough Data)の組をベースにして、文章の潜在意味を学習したいというのが動機だ。
文章の潜在意味解析としてはpLSA (probabilistic Latent Semantic Analysis)やLDA (Latent Dirichlet Allocation)が有名なのだが、いかんせん前者は巨大行列の演算、後者は確率分布の推定のためコストが非常に大きい。
Web検索のバックエンドとしてはリアルタイム性が要求されるだろうから、これらのモデルを素朴に用いるのは難しい。

本論文で提案されたのは、3層のDeep Neural Networkであり、最初の1層は非線形活性化関数なしの次元削減層(Word Hashing)だ。
これにより、従来のモデルより精度を上昇させることができたという。

関連研究

潜在意味解析の分野では、昨今2種類の研究がなされている。

1つ目は潜在意味モデルで、よく知られている例が共起行列の特異値分解だ。
共起行列を特異値分解すると、直感的には2つの単語の共起の強さが特異値として求まる。
この共起の強さを意味の類似度と考えることができ、セマンティクスによるクラスタリング等ができる。

2つ目はDeep Learningである。Hinton自身がやっていたらしいのだが、Deep RBMで元クエリを復元できるよう訓練し、中間層で最も次元を落とした層の出力をセマンティクスと捉えるという手法だ。
しかし、どうもクエリの復元には適しているものの、セマンティクスとして捉えるには不適当なのか、従来のモデルに比べ精度が出ないらしい。
さらに、普遍的な自然言語を扱うと単語数が爆発するが、この手法では高々2000words程度しか扱えない。これを超えると計算終了できない。

この論文では、ある意味で両者の折衷案を取ったことになる。

提案手法

f:id:levelfour:20160531082504p:plain
(図は論文から引用)

この論文ではDeep Structured Semantic Models; DSSMというモデルを提案している。
Deepという語を冠する通り、基本的にはDeep Neural Networkだ。隠れ層数は3層である。
ただし、1層目は非線形活性化関数を出力にかけない。他の層の活性化関数はf=\tanhだ。

l_1=W_1x
l_i=f(W_il_{i-1}+b_i)
y=f(W_4l_3+b_4)

さらに、W_1は訓練しない。本文中ではn-gramベースの変換と表現されている。
元の入力クエリはone-hotベクトルxとして与えられる。当然one-hotなので、次元数は非常に大きい。事実、Figure 1では50万次元で与えられている。
ここでn-gramを用いて次元削減する。例えば

latent semantic analysis

というクエリが与えられた場合、one-hotでは(latent=1, semantic=1, analysis=1, otherwise=0)というベクトルになるが、2-gramの場合

#l, la, at, te, en, nt, t_, _s, ... , is, s#

となる。実装では3-gramを使っていて、入力次元数が50万の場合、3-gram変換によって3万次元まで落ちるそうだ。

3-gramの場合、素朴には"#"と空白とアルファベット26文字と数字10文字の計38文字の順列なので{}_{38}P_3=54872で、3万次元という結果にもうなずけるのだが、2-gramの場合は{}_{38}P_2=1444で、Table 1では1607次元まで落ちるとあるが残りの150次元はどこから降ってきたんだという気がする(?)

DNNを経て得られた128次元の潜在意味出力y間で、今度はコサイン類似度をとる。

\displaystyle R(Q,D)=\frac{y_Q^\mathrm{T}y_D}{\|y_Q\|\|y_D\|}

これでクエリとクリックしたページの関連性が得られるので、ドキュメントの特徴として捉えられた。
最後にクエリからドキュメントが生成される事後確率をsoftmax関数で得る。

実験

実験で用いられたデータは、サーチエンジンの16510個のクエリログだ。平均的に各々のクエリは15個のドキュメントと紐付いている。
そしてなんと、クエリとドキュメントの関連度を0〜4の5段階で人間がラベリングしたらしい。
その労力も然ることながら、恣意性はどうなんだという気もするが、これがまだまだ教師付き学習における課題なのだろう。

感想

これだけのモデルで精度を上げられるのはDeep Learning時代様様という感じだが、やはり得られたセマンティクスにはどういう意味があるのか（ないのか？）気になってしまう。
そもそも自然言語のシンタックスとセマンティクスに強い結びつきがあるのは人間の思い込みかもしれないので、求まったセマンティクスに意味を求めるのも見当違いなのかもしれない。
実際にりんなでそれなりの会話精度が出ているので、あながち明後日の方向を向いているわけではないのだろうが。

参考

  1. http://research.microsoft.com/en-us/um/people/jfgao/paper/2013/cikm2013_DSSM_fullversion.pdf