stack構造を実現するneural networkモデルの紹介と実装

  • 3
    いいね
  • 0
    コメント

DeepLearning Advent Calendar 12月12日の記事です.
思考が死んでるのとAdvent Calendar書いてみたかったから書きます.

本記事はNeural network(NN)を用いてstack1構造を実現するモデルを,その背景と概要と共に紹介するものです.具体的には次の2つのモデルの説明を行います.

3行で

  • NNを用いてstack構造を実現したモデル2つを紹介する.
  • chainerを用いて実装したコードがある(ただしcopying task).
  • 模倣は原始的な動機っぽい.

背景

plainなRNNとその限界

plainなRecurrent neural network(RNN)は,内部状態と入力$\mathbf{h}_t,\mathbf{x}_t$に対し,次の式で更新される.

\mathbf{h}_{t+1} = f(\mathbf{A} \mathbf{h}_t+\mathbf{U} \mathbf{x}_t)

このモデルは常に活性化関数$f$を適応するため長期的な情報の記憶が難しかった2.LSTMはこれを改善することをモチベーションの1つとして$\mathbf{c}_t$という内部状態を1つ追加した.この$\mathbf{c}_t$は,gateによるweightedを除いて非線形関数をかけられないため,情報が長期的に残ることが期待できる3

でももっと外部リソースを利用したい.世界知識とか,コーパス内で誰がどうしたとか理解できるなら素敵だ.或いは古典的な離散モデルのNeural implementaiton4をするとご利益がありそう.そんな背景があってExternal memory系と一部で呼ばれるNeural networkのextensionが研究なされている.

External memory系とstack構造

External memoryを実現する研究はそのメモリの構造の違いから大きく分けて2つのクラスが存在する.1つがmemory networkやneural turing machineなどのvectorが並んでるもので,googleがDifferentiable neural computerやfacebookのmemory networkなど比較的知名度があり,関連研究も幾つかある5.大陸の方では人気っぽい.

もう1つが今回紹介するもので,stack構造をneural implementationするアプローチを取るもの.とはいえこのモデルの数はそれほど多くはない.一応古く(?)は1993に次の論文が登場していたりする.ただ大規模にこのテーマで研究がなされたということはないようだ.

The Neural Network Pushdown Automaton: Model, Stack and Learning Simulations

そして計算機の性能向上と共に時間は進み,2015年に次の2つの論文が出た.

Inferring Algorithmic Patterns with Stack-Augmented Recurrent Nets

Learning to Transduce with Unbounded Memory

そんな背景.

モデル紹介

Inferring Algorithmic Patterns with Stack-Augmented Recurrent Nets

入力を$\mathbf{x}_t$,隠れ状態を$\mathbf{h}_t$,出力を$\mathbf{y}_t$とする.
stack $s_t$は各インデックス$i$にスカラ$s_t[i] \in \mathcal{R}$をストアしている,またstackの上から$k$個を1つのベクトルとして考えたものを$\mathbf{s}_t^k \in \mathcal{R}^{k}$と表記する.

上記の定義の元,次のような更新式を繰り返していく.

\begin{eqnarray}
\mathbf{h}_t
&=&\sigma(U\mathbf{x}_t+R\mathbf{h}_{t-1}+P\mathbf{s}^k_{t-1}) \\

\mathbf{y}_t &=& f(V\mathbf{h}_t)\\
\mathbf{a}_t &=& Softmax(A\mathbf{h}_t) \in \mathcal{R}^{2}\\

s_t[i] &=&
  \begin{cases}
  \mathbf{a}_t[PUSH] \sigma(D\mathbf{h}_t)
  +
  \mathbf{a}_t[POP] s_{t-1}[1] & ( i=0 ) \\
  \mathbf{a}_t[PUSH] s_{t-1}[i-1]
  +
  \mathbf{a}_t[POP] s_{t-1}[i+1] & (  i\neq 0 )
  \end{cases} \\
\end{eqnarray}

$\mathbf{h}_t$と$\mathbf{y}_t$の意味は通常のRNNと変わらない.問題はstack $s_t$に付随する処理と,$\mathbf{a}_t[POP],\mathbf{a}_t[PUSH]$の意義で式を眺めてるより図を見た方が理解が早いだろう.そのため,次の図を用いて直感的な説明を行う6

まず$t=3$,$s_3=(3,1,2)$かつ$\mathbf{a}_3[POP]=-1$,$\mathbf{a}_3[PUSH]=2$であるとする.この時,$t=4$のスタック$s_4$は

$s_3$ $POP(s_3)$ $PUSH(s_3)$ $s_4$
$i=0$ $3$ $-1*1=-1$ $\sigma(D\mathbf{h}_3)$ $-1+\sigma(D\mathbf{h}_3)=-1+\sigma(D\mathbf{h}_3)$
$i=1$ $1$ $-1*2=-2$ $2*3=6$ $-2+6=4$
$i=2$ $2$ $0$ $2*1=2$ $0+2=2$
$i=3$ $0$ $2*2=4$ $0+4=4$

という風に計算される.
このように,インデックスの値が1つ上にずれたstackとインデックスの値が1つ下にずれたstackとの,$\mathbf{a}_3[POP]$と$\mathbf{a}_3[PUSH]$を用いたweighted sumが次の$s_4$となる.これは通常のStackをPOPした状態とPUSHした状態を足し合わせた形になっている.

variants and extensions

拡張として,上がる操作と下がる操作のPOPとPUSHに加え,現状維持の操作NO-OPを加えたモデルと,stackを複数用意することにより実質的にstackにベクトルをstoreするモデルに関しても言及している.

また上記はstack構造を用いているが,原論文はDoubly-linked listsを用いたバリアントも提案している.本記事では説明しないが,興味のある方は読んでみると楽しいと思う.

Inferring Algorithmic Patterns with Stack-Augmented Recurrent Nets

Learning to Transduce with Unbounded Memory

入力を$\mathbf{x}_t$,出力を$\mathbf{y}_t$とする7.stackの各インデックス$i$には,ベクトル$\mathbf{V}_t[i] \in \mathcal{R}^d$とスカラ$s_t \in \mathcal{R}$がストアされている.またstackをreadしたベクトルを$\mathbf{r}_{t}\in \mathcal{R}^d$とする.

まずRNNが1つあり,内部状態は$\mathbf{x}_t,\mathbf{r}_{t-1}$を用いて更新される.また更新されたLSTMからの出力を$\mathbf{o}'_t$とし,これら2つの操作をまとめて次のように表記するとする.

\begin{eqnarray}
\mathbf{o}'_t
= RNN(\mathbf{x}_t,\mathbf{r}_{t-1})
\end{eqnarray}

このRNNの出力$\mathbf{o}'_{t}$を次の式に適用し,stackの更新に必要な値が計算される.

\begin{eqnarray}
d_t &=& \sigma(W_d \mathbf{o}'_t + b_d) 
&,&
u_t &=& \sigma(W_u \mathbf{o}'_t + b_u) \\
\mathbf{v}_t &=& tanh(W_v \mathbf{o}'_t+\mathbf{b}_v)
&,&
\mathbf{y}_t &=& tanh(W_o \mathbf{o}'_t+\mathbf{b}_o)\\
\end{eqnarray}

$\mathbf{y}_t$は通常のoutputと同じである.それ以外の値を用い,stackと$\mathbf{r}_t$が更新される.ただし見やすさのために$ReLU(x)=max(0,x)$と表記した.

\begin{eqnarray}
\mathbf{V}_t[i] &=&
  \begin{cases}
    \mathbf{V}_{t-1}[i] & ( 1 \leq i \leq t ) \\
    \mathbf{v}_t & (  i=t )
  \end{cases}\\

s_t[i]
 &=&
  \begin{cases}
    ReLU(s_{t-1}[i]-ReLU(u_t-\sum_{j=i+1}^{t-1} s_{t-1}[j])) & ( i\leq i \leq t) \\
    d_t & (  i=t )
  \end{cases}\\

\mathbf{r}_t &=&
\sum_{i=1}^{t}min(s_t[i],ReLU(1-\sum_{j=i+1}^{t} s_t[j])) \mathbf{V}_t[i]
\end{eqnarray}

$\mathbf{V}_t$の更新は,素直にベクトルをストアしているだけで,そのままだと思う.ただこのそのままさがsoftmaxをとった値が乗算されていくStack-Augmented Recurrent Netsとは違う点でもある.また$d_t$も上に置くだけなので,やはりそのままだろう.

問題は,$s_t$と$\mathbf{r}_t$の更新が少しややこしと思う.ただ$\mathbf{r}_t$は$s_t$の更新が理解できたら理解出来ると思うので,$s_t$の更新を具体的な事例を用いて直感的に説明しよう.6

$s_3[i]$ \ $u_3$ $0$ $1$ $2$ $3$ $4$ $5$ $6$
$s_3[1]=3$ 3 3 3 3 2 1 0
$s_3[2]=1$ 1 1 1 0 0 0 0
$s_3[3]=2$ 2 1 0 0 0 0 0

$t=3$,$s_3 = (3,1,2)$とし,$u_3$の値を変えた時にどういう値が計算されるかを書いたものが上記の表である.

$u_3$の値の分だけ下から$s_3$を引いていることが読み取れる.具体的には,下から$s_3[i]$を足し合わせた値と$u_3$を比較し,もし負になるようなら$0$が,正の値ならその残りが$s_3[i]$には代入される.これは$s_t$がReLUをはさむためである.また$s_t$は減算されるばかりなので,一度$0$になれば以降その値はずっと$0$のままである.この性質と$\mathbf{r}_t$の更新式から,$0$になったインデックスは$\mathbf{r}_t$に足し合わされることはなく,結果としてstackから排除されるのと同様の挙動を示す.

variants and extensions

原論文ではNeural StackとNeural Queue, Neural Dequeの3つのvariantが提案されている.基本はNeural Stackと似た感じで,でもNeural implementaitonとしては面白いので興味ある方は是非.

Learning to Transduce with Unbounded Memory

感想

  • Inferring Algorithmic Patterns with Stack-Augmented Recurrent Netsはsoftmaxのweighted sumをするため,stackは乗算的な側面を持つ.

  • Learning to Transduce with Unbounded Memoryは上から一定の値を削ることを繰り返してPush and popするため,引き算的な性質を持つ.

やはり語りすぎず要点をちゃんと書くというのは難しい.
がんばります.

コード

https://github.com/takuo-h/NeuralStackModels

chainerを用いた上記2モデルの実装.taskはcopying.
EncodingとDecodingが切り替わるタイミングをどう与えるかが分からなかったため,通常の意味でのEncoder-decoderを部分的に用いてる.
通常の意味での機械翻訳や強化学習への改変もそこまで難しくない気はしますが,必要であれば書き直します.

注釈


  1. 本記事ではStackの単語をNNのレイヤを積み重ねる意味で用いることはありません 

  2. vanishing and exploding gradientに関しては割愛 

  3. この意味でLSTMとResidual network(Deep Residual Learning for Image Recognition)は似た性質を持つ. 

  4. Neural networkを用いてモデルを実現しようとすることを,個人的にこう読んでいる.自然言語処理でいえばparsingアルゴリズムの一種であるArc-eagerとかの実現が考えられる. 

  5. 怖いから読んでないけど,Neural Random-Access MachinesLie Access Neural Turing Machineがそれらしい.誰か紹介して下さい. 

  6. 本来の式はsigmoid等をはさむためこのような値を取ることはなく,これらはあくまで説明用の値である. 

  7. 原論文での表記は$i_t$と$\mathbf{o}_t$であるが,表記の統一のため先述のように定義する 

この投稿は DeepLearning Advent Calendar 201612日目の記事です。