外部メモリー付きのニューラルネット”Differentiable Neural Computing (DNC)”について解説するよ

Outline

- この記事について

Differentiable Neural Computing (DNC)とは
ロジック解説
- DNC の全体像
- 外部 Memory の読み書きについて
Pyhthon – Chainer による実装例
参考URL

この記事について　

DeepMind が Nature に投稿した論文

Hybrid computing using a neural network with dynamic external memory

で使用されている “Differentiable Neural Computing (DNC)” について解説します。ロジックの説明がメインですが、Python – Chainer による実装例も紹介します。

Differentiable Neural Computing (DNC)とは

sequential data を Neural Net で処理したいという欲求は昔からあるようで、一番スタンダードなものは Recurrent Neural Net (RNN) です。しかし、RNN には”勾配消失問題”というものがありまして、それを克服したモデルが Long Short Term Memory (LSTM) と呼ばれています。何が short で何が long なのかというと、入力されたデータは、出力されるまで Neural Net の内部にとどまっているわけです。これはある意味で “Memory” のようなものと考えてもよさそうです。しかし、入力から出力までの”短時間”しか記憶ができない。なので、”short term momory” と呼ばれます。「この short term memory の記憶できる時間が長くなりましたよ」という意味で、Long Short Term Memory と名付けられているようです。そうすると、本当に long な Meomory は学習機内部ではなくて外部にあってもいいかもしれない、そんな気がしてきます。そういう思いから生まれた、かどうかは分かりませんが、Differentiable Neural Computing (DNC) とは、学習機の外部に Memory を用意してやって、Memory の使用法まで含めて学習させてしまうというものです。”Differentiable”の意味ですが、back propagation で学習させようと思うと、微分を計算できることが必要になります。ですので、外部 Memory に対する操作も含めて”微分計算が可能であること”という意味です。

ロジック解説

DNC の全体像

DNC の構成要素は、本体である Controller と外部 Memory です。論文によると、全体としてのデータの流れは下図のように表すことができます。

DNC は sequential data を扱いますので、現在の time-step を $t$ と表しています。前 step は $t-1$、次 step は $t+1$ となり、図中の添え字 $t$ は、それぞれの変数がどの time-step で生成されたものであるかを表しています。

それでは、データの流れを順を追って見ていきましょう。図中に(1)~(4)の番号が振ってありますので、この順で追ってください。

(1) : “Data Set” より入力データ $x_t$ が入力されます。これに、前 step での Memory からの出力 $\boldsymbol{r}_{t-1}$ とを合わせた $\boldsymbol{\chi}_t=[\boldsymbol{x}_t, \boldsymbol{r}_{t-1}]$ を Controller への入力とします。

(2) : Controller からの出力 $\boldsymbol{h}_t$ が得られますので、これを2つのルートに振り分けます。ひとつは、”Out Put” に向けての $\boldsymbol{v}_t$、もう1つは Memory を制御するための “interface vector” $\boldsymbol{\xi}_t$ です。論文中では、これらは $\boldsymbol{h}_t$ の線形変換 $\boldsymbol{v}_t=W_y \boldsymbol{h}_t$ と、$\boldsymbol{\xi}_t=W_{\xi} \boldsymbol{h}_t$ として書かれています。

(3) : “interface vector” $\boldsymbol{\xi}_t$ をもとに Memory へのデータの書き込みが行われ Memory の状態が更新されます。また、Memory からの読み出しも行われ、”read vector” $\boldsymbol{r}_t$ が得られます。

(4) : “read vector” $\boldsymbol{r}_t$ は、 “Out Put”への出力に加算される一方で、次 step での Controller への入力へと回されます。

(5) : Controller からの出力と、Memoryからの出力を合成し”Out Put” へ $\boldsymbol{y}_t = \boldsymbol{v}_t + W_r \boldsymbol{r}_t$ を出力します。

以上、(1)~(5) をもって、1 step が完了します。

Controller としては、多次元の入力を受け取り、多次元の出力を返す学習機なら何でもよいのですが、(Recurrent) Neural Net や LSTMなどを使うことが多いようです。(Recurrent) Neural Net や LSTM の解説は他にゆずるとして、この記事では、DNC の最大の特徴である「外部 Memory の読み書き」について解説していきます。

外部 Memory の読み書きについて

それでは、外部 Memory の読み書きについて解説しましょう。面倒なので、以下では単に Memory と呼ぶことにします。

Memory の構造

まずは、Memory の構造について把握しておきましょう。

Memory としては $N$ × $W$ の行列を用います。つまり、address が $1$~$N$ まで振られていて、各 address に $W$ 次元の数値ベクトルを格納できる slot があると考えます。Memory の状態は刻々と更新されていきますので、time-step $t$ での Memory を表す行列を $M_t$ と書くことにします。ただし、行列の次元 $N$ × $W$ は固定されているものとし、常に、$N$ は memory slot の総数（address の総数）、$W$ は slot の長さ（格納する数値ベクトルの次元）とします。

interface vector の詳細

「全体のデータの流れ」でも述べた通り、Controller による Memory の操作は

“interface vector” $\boldsymbol{\xi}_t$ を通して行われます。一口で Memory の操作といっても、読み込み/書き込み/addressの指定など、複数のタスクが考えられますので、$\boldsymbol{\xi}_t$ は機能別に各 component に分解されます。

\begin{align}

\boldsymbol{\xi}_t = \Big[ \boldsymbol{k}_t^{r, 1},...,\boldsymbol{k}_t^{r, R}, \; \hat{\beta}_t^{r, 1},...,\hat{\beta}_t^{r, R}, \; \boldsymbol{k}_t^w, \; \hat{\beta_t}^w, \hat{\boldsymbol{e}}_t, \; \boldsymbol{\nu}_t, \; \hat{f}_t^1,...,\hat{f}_t^R, \; \hat{g}_t^a, \; \hat{g}_t^w, \; \hat{\boldsymbol{\pi}}_t^1,...,\hat{\boldsymbol{\pi}}_t^R \Big]

\end{align}

‘$\hat{}$’ 記号がついているものは、さらに scale 変換をかけます。種類が多くてややこしいので、いったんまとめます。( , )内の値は、(次元, 個数)です。

・”read key” $(W, R) \; :\; \boldsymbol{k}_t^{r, 1},…,\boldsymbol{k}_t^{r, R}$

・”read strength” $(1, R) \; : \; \beta_t^{r, 1},…,\beta_t^{r, R} \;\;\big(\beta_t^{r, i}=\text{oneplus}(\hat{\beta}_t^{r, i})\big)$

・”write key” $(W, 1) \; : \; \boldsymbol{k}_t^w$

・”write strength” $(1,1) \; : \; \beta_t^w=\text{oneplus}(\hat{\beta}_t^w)$

・”erase vector” $(W, 1) \; : \; \boldsymbol{e}_t=\sigma(\hat{\boldsymbol{e}}_t)$

・”write vector” $(W, 1) \; : \; \boldsymbol{\nu}_t$

・”free gate” $(1, R) \; : \; f_t^1,…,f_t^R \;\; \big(f_t^i=\sigma(\hat{f}_t^i)\big)$

・”allocation gate” $(1, 1) \; :\; g^a_t=\sigma(\hat{g}^a_t)$

・”write gate” $(1, 1) \; :\; g^w_t=\sigma(\hat{g}^w_t)$

・”read mode” $(3, R) \; : \; \boldsymbol{\pi}_t^1,…,\boldsymbol{\pi}_t^R \;\; \big(\boldsymbol{\pi}_t^i=\text{softmax}(\hat{\boldsymbol{\pi}}_t^i)\big)$

スケール変換に用いる関数は、

\begin{align}

& \text{oneplus}(x)　= 1+\text{log}(1+e^x) \in [1, \infty) \\

& \sigma(x) = \frac{1}{1+e^{-x}} \in [0, 1] \\

& \text{softmax}(\boldsymbol{x}) = \frac{e^\boldsymbol{x}}{\sum_ie^{x_i}} \in [0, 1]

\end{align}

と定義されています。$\text{oneplus}(x)$、 $\sigma(x)$、$\text{exp}(x)$ の引数にベクトル値を取る場合は、成分ごとの作用を意味しますので注意してください。

ここでは、定義を羅列しただけなので、何もわからないと思います。以下、これらの component をどのように使って Memory を制御していくか、順に解説していきます。

先に進む前に、1点だけ説明を加えておきます。$R$ は Memory からの読み出しの回数を表しています。論文中の DNC では、1 step のうちで Memory からの読み出しを複数回行う設定となっていて、その回数が $R$ です。対して、書き込みは、1 step に1回のみの設定です。また、interface vector の次元は、$W$ と $R$ で決まっていて、$WR+3W+5R+3$ となることも分かるかと思います。

Memory の読み書き手順（概要）

Memory の読み書きには、読み書き対象となる Memory slot の address を指定する必要があります。ただし、back propagation による学習が可能であるためには、微分可能性、少なくとも演算の連続性が必要となります。よって、特定のひとつの address だけを指定するのではなく、幅を持たせて、どの address を重点的に読み込む/書き込むかの重みづけを行います。以後、この重みを、”read/write weighting”と呼ぶことにしますが、これらをどう求めていくかがポイントになります。

“read/write weighting” を求めてしまえば、読み込み/書き込みの演算自体は単純です。詳細は後に回しますが、概要をつかんでおきましょう。まず、読み込みの場合を考えてみます。今、”read weighting” $\boldsymbol{w}^r_t$ が得られたとします。このベクトルの次元は、Memory slot の総数と同じ $N$ です。各成分は対応する address の Memory slot にある情報をどれだけ”強く”読み込むかを表しています。すなわち、読みだされる情報は、Memory 行列と重みベクトルの積として、$M_t^T\boldsymbol{w}^r_t$と表されます。先にも述べましたが、論文中では 1 step で読み出しを $R$ 回行う設定なので、”read weighting” も $R$ 個 $\{\boldsymbol{w}_t^{r,i}\}_{i=1,…,R}$ 構成されます。また、読み出しによる増幅など防ぐため、自然な要請として

\begin{align}

& 0 \leqq \boldsymbol{w}_t^{r,i}[n] \leqq 1 \;\; (n=1,2,...,N)\\

& \sum_{n=1}^N \boldsymbol{w}_t^{r,i}[n] \leqq 1 \;\; (i=1,2,...,R)

\end{align}

を課すものとします。

同様に、書き込みの場合も考えてみましょう。”write weighting” $\boldsymbol{w_t^w}$ が得られたとします。また、書き込みたい情報を表すベクトル $\boldsymbol{\nu}_t$ も得られているとします。$\boldsymbol{w_t^w}$の次元は$N$で、各成分は対応する Memory slot にどれだけ”強く” $\boldsymbol{\nu}_t$ を書き込むかを意味します。つまり、Memory 行列 $M_{t-1}$ に、行列 $\boldsymbol{w_t^w}\boldsymbol{\nu}_t^T$ を加算することで書き込みを行い Memory を更新します。各成分に

\begin{align}

& 0 \leqq \boldsymbol{w}_t^w[n] \leqq 1 \;\; (n=1,2,...,N)\\

& \sum_{n=1}^N \boldsymbol{w}_t^w[n] \leqq 1 

\end{align}

を課す点は同様です。

Memory の読み書き手順（詳細）

論文中では、Memory への読み書き自体も含めて以下の4つの手順を踏んでいます。

①write weighting の更新

②Memory への書き込み

③read weighting の更新

④Memory からの読み込み

以下、このステップにそって解説していきますが、実装例でも、この順で処理をまとめていますので、参考にしてください。

尚、前 time-step での read/write weighting $\{\boldsymbol{w}_{t-1}^{r,i}\}_{i=1,…,R}$ / $\boldsymbol{w}_{t-1}^{w}$は得られているものとします。

①write weightingの更新

書き込み先の address の選択には2つの方法があり、write weighting は2つの要素から構成されます。つまり、(1) interface vector を通して入力された “key” をもとに書き込み先 slot を選択、(2)前 time-step までの読み出し状況をもとに使用済みの情報が残っている slot を選択、の2つです。

まずは、(1)から見ていきましょう。

interface vector $\boldsymbol{\xi}_t$ 中の “write key” $\boldsymbol{k}_t^w$ を各 Memory slot に保持されている情報と照合し類似度を計算します。また、weighting の peak の鋭さを調整するパラメータとして “write strength” $\beta_t^w$ も使用します。

この計算は、read weighting を求めるところでも共通なので、$N$×$W$ 行列 $M$、$W$ 次ベクトル $\boldsymbol{k}$、スカラー値 $\beta$ に対して、以下の演算を定義しておきます。

\begin{align}

\mathcal{C}(M, \boldsymbol{k}, \beta)[n] = \frac{\text{exp}\big(\mathcal{D}(\boldsymbol{k}, M[n,:])\beta \big)}{\sum_m\text{exp}\big(\mathcal{D}(\boldsymbol{k}, M[m,:])\beta \big)}

\end{align}

ここで、$\mathcal{D}$ は2つのベクトル間の距離で、とりかたはいろいろ考えられますが、論文に合わせてコサイン類似度

\begin{align}

\mathcal{D}(\boldsymbol{u}, \boldsymbol{v}) = \frac{\boldsymbol{u} \cdot \boldsymbol{v}}{||\boldsymbol{u}|| \; ||\boldsymbol{v}||}

\end{align}

としておきます。$\beta \rightarrow \infty$ の極限で $\mathcal{C}$ は鋭いピークがひとつだけ立ちます。

さて、ここで定義した演算を用いて、(1)の方法による write weighting は

\begin{align}

\boldsymbol{c}_t^w=\mathcal{C}(M_{t-1}, \boldsymbol{k}_t^w, \beta_t^w)

\end{align}

と計算されます。

次に(2)の方法による計算です。多少ややこしいですが、以下の順で求めていきます。

(2)-1. “retention vector” $\boldsymbol{\psi}_t$ の構成

前 time-step $t-1$ で情報を読み出した Memory slot は、使用済み slot として書き込みに利用したいと思うのは自然でしょう。しかし、今後も必要な情報が保持されている場合は、上書きしてはいけません。このように、前 time-step で読み込みを行った Memory slot を本当に開放して良いかどうかのフラグ（実際には0~1の連続値なので重み）が “free gate” $f_t^i\;(i=1,…,R)$ です。すなわち、$f_t^i \boldsymbol{w}_{t-1}^{r,i}$ を成分単位で考えて、「$f_t^i w_{t-1}^{r,i}$ $\simeq 1$ $\Leftrightarrow f_t^i \simeq 1$ and $w_{t-1}^{r,i}\simeq 1$」ならば読み込み済みかつ開放OKなので上書きします。また、「$f_t^i w_{t-1}^{r,i}$ $\simeq 0$ $\Leftrightarrow f_t^i \simeq 0$ or $w_{t-1}^{r,i}\simeq 0$」ならば前 time-step で読み込まれていない、または、読み込み済みだったとしても解放フラグが立っていないので上書き不可となります。今、各回の読み込みごとに考えていましたが、全 $R$ 回をひっくるめての使用中（上書き不可）フラグである “retention vector” $\boldsymbol{\psi}_t$を

\begin{align}

\boldsymbol{\psi}_t = \prod_{i=1}^R\big(1-f_t^i\boldsymbol{w}_{t-1}^{r, i}\big)

\end{align}

で定義します。積は成分ごとの積をとります。1からの差を求めた後で積を計算していますので、$R$ 回のうち1度でも上書き可と判断された memory slot は上書き可と判断されます。一方で、使用中（上書き不可） $\psi_t \simeq 1$ と判断されるのは、$R$ 回全てについて上書き不可と判断されたときに限られます。

(2)-2. “usage vector” $\boldsymbol{u}_t$ の構成

(2)-1では、使用中フラグ（正しくは重み）としての $\boldsymbol{\psi}_t$ を考えましたが、前 time-step での読み込みについてしか考えていませんでした。実際には、書き込みが行われた場合には使用中の度合いが高まるはずですし、直前 time-step より前の time-step での状況も考えるべきです。これらを踏まえて、各 Memory slot の使用中度合いを表す重み “memory usage vector” $\boldsymbol{u}_t$ を以下の更新式で定義します。

\begin{align}

\boldsymbol{u}_t &= \big(\boldsymbol{u}_{t-1} + \boldsymbol{w}_{t-1}^w - \boldsymbol{u}_{t-1} \circ \boldsymbol{w}_{t-1}^w \big) \circ \boldsymbol{\psi}_t \\

\boldsymbol{u}_0 &= 0, \;\; \boldsymbol{w}_0^w = 0

\end{align}

$\circ$は成分ごとの積を表します。(…)内第3項目は $\boldsymbol{u}_t$ の各成分が $1$ を超えないように調整するための補正です。$u_t = 1$ に達すると書き込みによる重みの更新は停止しますし、もし $u_t > 1$ となってしまっても更新により値を減少させます。

(2)-3. “allocation weighting” の構成

使用中度合い $\boldsymbol{u}_t$ に基づいて、書き込みを行う Memory slot の address を決めます。基本的には、使用中度合いが低いところに書き込む訳ですが、傾斜をつけます。まず、$\boldsymbol{u}_t$ の成分を値が小さい順に並べた時の index からなるベクトルを $\boldsymbol{\phi}_t$ とします。つまり、

\begin{align}

\boldsymbol{u}_t[\boldsymbol{\phi}_t[1]] \leqq \boldsymbol{u}_t[\boldsymbol{\phi}_t[2]] \leqq 

\boldsymbol{u}_t[\boldsymbol{\phi}_t[3]] \leqq \cdots \leqq 

\boldsymbol{u}_t[\boldsymbol{\phi}_t[N]]

\end{align}

です。これを用いて、”allocation weighting” $\boldsymbol{a}_t$ を

\begin{align}

\boldsymbol{a}_t[\boldsymbol{\phi}_t[n]] = \big(1-\boldsymbol{u}_t[\boldsymbol{\phi}_t[n]]\big) \prod_{m=1}^{n-1}\boldsymbol{u}_t[\boldsymbol{\phi}_t[m]]

\end{align}

で定義します。積は成分ごとの積をとります。基本的には、$1-\boldsymbol{u}_t$ なので使用済み（書き込み可）の度合いを表す重みとなっています。

以上、(1)と(2)の結果を統合し、write weighting $\boldsymbol{w}_t^w$ を

\begin{align}

\boldsymbol{w}_t^w = g_t^w\big(g_t^a\boldsymbol{a}_t+(1-g_t^a)\boldsymbol{c}_t^w\big)

\end{align}

として更新します。ここで、$g_t^a$ と $g_t^w$ は interface vector $\boldsymbol{\xi}_t$ を通して入力されていたものです。それぞれ、「使用済みフラグ or “key”のどちらに基づいて書き込みを行うか」、「そもそも書き込みを行うか」を制御する gate として働きます。

②Memory への書き込み

write weighting の更新が完了しましたので、Memory に書き込みを行います。ただし、書き込みと同時に古い情報の消去も行います。どの Memory slot を対象とするかの重みづけは、”write weighting” $\boldsymbol{w}_t^w$ で行います。書き込まれるデータは “write vector” $\boldsymbol{\nu}_t$、slot 内のデータをどのようなパターンで消去するかは、erase vector $\boldsymbol{e}_t$ で与えられ、この2つは interface vector を通して入力されています。

Memory 行列 $M_{t-1}$ の消去・書き込みによる更新は以下の式に従って行われます。

\begin{align}

& M_t[n,s] = M_{t-1}[n,s] \big(1-\boldsymbol{w}_t^w[n] \boldsymbol{e}_t[s] \big) + \boldsymbol{w}_t^w[n] \boldsymbol{\nu}_t[s] \\

& \Leftrightarrow M_t = M_{t-1} \circ \big(1-\boldsymbol{w}_t^w \boldsymbol{e}_t^T \big) + \boldsymbol{w}_t^w \boldsymbol{\nu}_t^T 

\end{align}

③read weightingの更新

読み込み先の address の選択にも2つの方法があります。つまり、

(1) interface vector を通して入力された “key” をもとに読み込み先 slot を選択、(2)書き込み順に従って slot を選択、の2つです。

(1)については、write weighting の時と同じように “read key” $\{\boldsymbol{k}_t^{r,i}\}_{i=1,2,..,R}$ と “read strength” $\{\beta_t^{r,i}\}_{i=1,2,..,R}$ を用いて、

\begin{align}

\boldsymbol{c}_t^{r, i} = \mathcal{C}\big(M_t, \boldsymbol{k}_t^{r,i}, \beta_t^{r,i}\big) \;\; (i=1,2,...,R)

\end{align}

と計算します。

(2)はやや長いですが、順に説明していきます。

説明の便宜上(2)-2 →(2)-1の順で解説しますが、実装する際は(2)-1 →(2)-2の流れです。

(2)-2. “precedence weighting” の構成

precedence weighting $\boldsymbol{p}_t$ を以下の更新式で定義します。

\begin{align}

& \boldsymbol{p}_0 = 0 \\

& \boldsymbol{p}_t = \Big(1-\sum_{n=1}^N \boldsymbol{w}_t^w[n]\Big)\boldsymbol{p}_{t-1} + \boldsymbol{w}_t^w

\end{align}

$\boldsymbol{w}_t^w$ はすでに①で更新が完了していることに注意してください。②で”強く”書き込みが行われた場合は、$\sum \boldsymbol{w}_t^w \simeq 1$ となるので、前 time-step の情報 $\boldsymbol{p}_{t-1}$ は消去され、現 time-step でどこに書き込みが行われたかが保存されます。書き込みが行われなかった場合は、最後に行われた書き込みの重みが保持され続けます。また、$\boldsymbol{p}_t[n] \leq 1$、$\sum_n \boldsymbol{p}_t[n] \leq 1$ であることはすぐにわかります。

(2)-1. “temporal link matrix” の構成

Memory slot への書き込み順を表す $N$ × $N$ 行列 $L_t$ を構成します。成分単位でみたときに $L_t[n, m] \simeq 1$ であることは「Memory $M_t$ において slot ‘n’ にある情報は slot ‘m’ にある情報の次に書き込まれたものである」という関係が表現できるように、更新式を以下で与えます。

\begin{align}

& L_0[n,m]=0 \\

& L_t[n,n]=0 \\

& L_t[n,m]=\big(1-\boldsymbol{w}_t^w[n]-\boldsymbol{w}_t^w[m]\big)L_{t-1}[n,m] + \boldsymbol{w}_t^w[n]\boldsymbol{p}_{t-1}[m]

\end{align}

対角成分は意味をなさないため $0$ で固定します。$0 \leqq L_t[n,m] \leqq 1$ および、$\sum_m L_t[n,m] \leqq 1$ はすぐに確かめられます。$\sum_n L_t[n,m] \leqq 1$ は確かめようとしましたが、示せませんでした。示せた方がおられましたら、コメントいただけると助かります。

(2)-3. “forward/backward weighting” の構成

Memory への書き込み順を考慮した forward/backward weighting $\{\boldsymbol{f}_t^i\}_{i=1,..,R}$ / $\{\boldsymbol{b}_t^i\}_{i=1,..,R}$をやや荒っぽいですが

\begin{align}

&\boldsymbol{f}_t^i[n]=\sum_{m=1}^NL_t[n,m]\boldsymbol{w}_{t-1}^{r,i}[m] \; \Leftrightarrow \; \boldsymbol{f}_t^i=L_t\boldsymbol{w}_{t-1}^{r,i} \\

&\boldsymbol{b}_t^i[m]=\sum_{n=1}^N\boldsymbol{w}_{t-1}^{r,i}[n]L_t[n,m] \; \Leftrightarrow \; \boldsymbol{b}_t^i=L_t^T\boldsymbol{w}_{t-1}^{r,i} \\

\end{align}

で構成します。$\sum_n L_t[n,m] \leqq 1$ が成り立つならば、$0\leqq \boldsymbol{f}_t^i[n] \leqq 1$ および $\sum_n\boldsymbol{f}_t^i[n]\leqq1$ が成立します。$\boldsymbol{b}_t^i$ についても同様です。

以上、(1)~(2)を統合して、read weighting $\{\boldsymbol{w}_t^{i,r}\}_{i=1,…,R}$ を更新します。

\begin{align}

\boldsymbol{w}_t^{r,i}=\boldsymbol{\pi}_t^i[1]\boldsymbol{b}_t^i + \boldsymbol{\pi}_t^i[2]\boldsymbol{c}_t^i + \boldsymbol{\pi}_t^i[3]\boldsymbol{f}_t^i \;\; (i=1,2,...,R)

\end{align}

$\{\pi_t^i\}_{i=1,…,R}$ は interface vector を通して入力されています。

④Memoryからの読み込み

Memory からの読み出しは簡単です。読み出し結果の “read vector” $\{\boldsymbol{r}_t^i\}_{i=1,..,R}$ は

\begin{align}

\boldsymbol{r}_t^i[s] = \sum_{n=1}^N \boldsymbol{w}_t^{r,i}[n]M_t[n,s] \; \Leftrightarrow \; \boldsymbol{r}_t^i = M_t^T\boldsymbol{w}_t^{r,i} \;\; (i=1,2,...,R)

\end{align}

と計算されます。

以上をもって、time-step $t$ の Memory 読み書きが完了します。

Pyhthon – Chainer による実装例

上で説明したロジックの python による実装例を紹介します。オリジナルのコードは、

DNC (Differentiable Neural Computers) の概要 + Chainer による実装

にあるものです。上の解説と比較しやすいように処理を関数にまとめたり、変数名を変えたりしていますが、内容はほぼ同じものです。

ひとつ注意しておきたいのですが、全体像で示した Controller からの出力 $\boldsymbol{h}_t$ は、論文では Controller の最終的な出力だけでなく、hidden layer の出力もすべて統合しているように見えます。しかし簡単のため、ここで使う Controller は 2層程度の簡単なものに限り、hidden layer の出力は Controller の外には取り出しません。

DNC の実装

dnc.py

import numpy as np

import chainer

from chainer import functions as F

from chainer import links as L

from chainer import optimizers, Chain, Link, Variable

# controller of DNC

class SimpleLSTM(Chain): 

    def __init__(self, d_in, d_hidden, d_out):

        super(SimpleLSTM, self).__init__(

            l1 = L.LSTM(d_in, d_hidden),

            l2 = L.Linear(d_hidden, d_out),

            )

    def __call__(self, x):

        return self.l2(self.l1(x))

    def reset_state(self):

        self.l1.reset_state()

class DNC(Chain):

    def __init__(self, X, Y, N, W, R):

        self.X = X # input dimension

        self.Y = Y # output dimension

        self.N = N # number of memory slot

        self.W = W # dimension of one memory slot

        self.R = R # number of read heads

        self.d_ctr_in = W*R+X # input dimension into the controller

        self.d_ctr_out = Y+W*R+3*W+5*R+3 # output dimension from the controller

        self.d_ctr_hidden = self.d_ctr_out # dimension of hidden unit of the controller

        self.d_interface = W*R+3*W+5*R+3 # dimension of interface vector

        self.controller = SimpleLSTM(self.d_ctr_in, self.d_ctr_hidden, self.d_ctr_out)

        super(DNC, self).__init__(

            l_ctr = self.controller, 

            l_Wy = L.Linear(self.d_ctr_out, self.Y),

            l_Wxi = L.Linear(self.d_ctr_out, self.d_interface), 

            l_Wr = L.Linear(self.R * self.W, self.Y), 

            )

        self.reset_state()

    def reset_state(self):

        # initialize all the recurrent state

        self.l_ctr.reset_state() # controller

        self.u = Variable(np.zeros((self.N, 1)).astype(np.float32)) # usage vector (N, 1)

        self.p = Variable(np.zeros((self.N, 1)).astype(np.float32)) # precedence weighting (N, 1)

        self.L = Variable(np.zeros((self.N, self.N)).astype(np.float32)) # temporal memory linkage (N, N)                     

        self.Mem = Variable(np.zeros((self.N, self.W)).astype(np.float32)) # memory (N, W)

        self.r = Variable(np.zeros((1, self.R*self.W)).astype(np.float32)) # read vector (1, R * W)

        self.wr = Variable(np.zeros((self.N, self.R)).astype(np.float32)) # read weighting (N, R)

        self.ww = Variable(np.zeros((self.N, 1)).astype(np.float32)) # write weighting (N, 1)

    # utility functions

    def _cosine_similarity(self, u, v):

        # cosine similarity as a distance of two vectors

        # u, v: (1, -) Variable  -> (1, 1) Variable

        denominator = F.sqrt(F.batch_l2_norm_squared(u) * F.batch_l2_norm_squared(v))

        if (np.array_equal(denominator.data, np.array([0]))):

            return F.matmul(u, F.transpose(v))

        return F.matmul(u, F.transpose(v)) / F.reshape(denominator, (1, 1))

    def _C(self, Mem, k, beta):

        # similarity between rows of matrix Mem and vector k

        # Mem:(N, W) Variable, k:(1, W) Variable, beta:(1, 1) Variable -> (N, 1) Variable

        N, W = Mem.shape 

        ret_list = [0] * N

        for i in range(N):

            # calculate distance between i-th row of Mem and k

            ret_list[i] = self._cosine_similarity(F.reshape(Mem[i,:], (1, W)), k) * beta 

        # concat horizontally because softmax operates along the direction of axis=1 

        return F.transpose(F.softmax(F.concat(ret_list, 1))) 

    def _u2a(self, u):

        # convert usage vector u to allocation weighting a

        # u, a: (N, 1) Variable

        N = u.shape[0]

        phi = np.argsort(u.data.flatten()) # u.data[phi]: ascending

        a_list = [0] * N    

        cumprod = Variable(np.array([[1.0]]).astype(np.float32)) 

        for i in range(N): 

            a_list[phi[i]] = cumprod * (1.0 - F.reshape(u[phi[i]], (1, 1)))

            cumprod *= F.reshape(u[phi[i]], (1, 1))

        return F.concat(a_list, 0) 

    # operations of the DNC system

    def _controller_io(self, x):

        # input data from the Data Set : x (1, X) Variable  

        # out-put from the controller h is split into two ways : v (1, Y), xi(1, W*R+3*W+5*R+3) Variable

        chi = F.concat([x, self.r], 1) # total input to the controller 

        h = self.l_ctr(chi) # total out-put from the controller

        self.v = self.l_Wy(h)

        self.xi = self.l_Wxi(h)

        # interface vector xi is split into several components

        (self.kr, self.beta_r, self.kw, self.beta_w,

         self.e, self.nu, self.f, self.ga, self.gw, self.pi

         ) = F.split_axis(self.xi, np.cumsum(

             [self.W*self.R, self.R, self.W, 1, self.W, self.W, self.R, 1, 1]), 1) # details of the interface vector

        # rescale components

        self.kr = F.reshape(self.kr, (self.R, self.W)) # read key (R, W)

        self.beta_r = 1 + F.softplus(self.beta_r) # read strength (1, R)

        # self.kw : write key (1, W)

        self.beta_w = 1 + F.softplus(self.beta_w) # write strength (1, 1)

        self.e = F.sigmoid(self.e) # erase vector (1, W)

        # self.nu : write vector (1, W)

        self.f = F.sigmoid(self.f) #  free gate (1, R)

        self.ga = F.sigmoid(self.ga) # allcation gate (1, 1)

        self.gw = F.sigmoid(self.gw) # write gate (1, 1)

        self.pi = F.softmax(F.reshape(self.pi, (self.R, 3))) # read mode (R, 3)

    def _up_date_write_weighting(self):

        # calculate retention vector : psi (N, 1) 

        # here, read weighting : wr (N, R) must retain state one step former

        psi_mat = 1 - F.matmul(Variable(np.ones((self.N, 1)).astype(np.float32)), self.f) * self.wr # (N, R)

        self.psi = Variable(np.ones((self.N, 1)).astype(np.float32)) 

        for i in range(self.R):

            self.psi = self.psi * F.reshape(psi_mat[:,i],(self.N,1)) # (N, 1)

        # up date usage vector : u (N, 1)

        # here, write weighting : ww (N, 1) must retain state one step former

        self.u = (self.u + self.ww - (self.u * self.ww)) * self.psi 

        # calculate allocation weighting : a (N, 1)

        self.a = self._u2a(self.u) 

        # calculate write content weighting : cw (N, 1)

        self.cw = self._C(self.Mem, self.kw, self.beta_w) 

        # up date write weighting : ww (N, 1)

        self.ww = F.matmul(F.matmul(self.a, self.ga) + F.matmul(self.cw, 1.0 - self.ga), self.gw) 

    def _write_to_memory(self):

        # erase vector : e (1, W) deletes information on the Memory : Mem (N, W) 

        # and write vector : nu (1, W) is written there

        # write weighting : ww (N, 1) must be up-dated before this step

        self.Mem = self.Mem * (np.ones((self.N, self.W)).astype(np.float32) - F.matmul(self.ww, self.e)) + F.matmul(self.ww, self.nu)

    def _up_date_read_weighting(self):    

        # up date temporal memory linkage : L (N, N)

        ww_mat = F.matmul(self.ww, Variable(np.ones((1, self.N)).astype(np.float32))) # (N, N)

        # here, precedence wighting : p (N, 1) must retain state one step former

        self.L = (1.0 - ww_mat - F.transpose(ww_mat)) * self.L + F.matmul(self.ww, F.transpose(self.p)) # (N, N)

        self.L = self.L * (np.ones((self.N, self.N)) - np.eye(self.N)) # constrain L[i,i] == 0   

        # up date prcedence weighting : p (N, 1)

        self.p = (1.0 - F.matmul(Variable(np.ones((self.N, 1)).astype(np.float32)), F.reshape(F.sum(self.ww),(1, 1)))) * self.p + self.ww 

        # calculate forward weighting : fw (N, R)

        # here, read wighting : wr (N, R) must retain state one step former

        self.fw = F.matmul(self.L, self.wr) 

        # calculate backward weighting : bw (N, R)

        self.bw = F.matmul(F.transpose(self.L), self.wr)

        # calculate read content weighting : cr (N, R)

        self.cr_list = [0] * self.R

        for i in range(self.R):

            self.cr_list[i] = self._C(self.Mem, F.reshape(self.kr[i,:], (1, self.W)), F.reshape(self.beta_r[0,i],(1, 1))) # (N, 1)

        self.cr = F.concat(self.cr_list, 1) # (1, N * R)       

        # compose up-dated read weighting : wr (N, R)

        bcf_tensor = F.concat([

                            F.reshape(F.transpose(self.bw), (self.R, self.N, 1)),

                            F.reshape(F.transpose(self.cr), (self.R, self.N, 1)),

                            F.reshape(F.transpose(self.fw), (self.R, self.N, 1))

                            ], 2) # (R, N, 3)

        self.pi = F.reshape(self.pi, (self.R, 3, 1)) # (R, 3, 1)

        self.wr = F.transpose(F.reshape(F.batch_matmul(bcf_tensor, self.pi), (self.R, self.N))) # (N, R)

    def _read_from_memory(self): 

        # read information from the memory : Mem (N, W) and compose read vector : r (W, R) to reshape (1, W * R)

        # read weighting : wr (N, R) must be up-dated before this step

        self.r = F.reshape(F.matmul(F.transpose(self.Mem), self.wr), (1, self.R * self.W))

    def __call__(self, x):

        self._controller_io(x) # input data is processed through the controller

        self._up_date_write_weighting() 

        self._write_to_memory() # memory up-date

        self._up_date_read_weighting()  

        self._read_from_memory() # extract information from the memory

        self.y = self.l_Wr(self.r) + self.v # compose total out put y : (1, Y)

        return self.y

使用例

使用例も載せますが、DNC (Differentiable Neural Computers) の概要 + Chainer による実装にあるものと内容は同じです。

固定長の one-hot ベクトルをランダムな個数入力し、入力完了後に、出力として入力データを echo させます。echo させたデータと入力データの2乗誤差を loss として、1セットの入力ごとに学習を行います。学習が終了したら、次セットの one-hot ベクトルを入力します。

dnc_echo_test.py

import dnc

import numpy as np

import chainer

from chainer import functions as F

from chainer import links as L

from chainer import optimizers, Chain, Link, Variable

def onehot(x, n):

    ret = np.zeros(n).astype(np.float32)

    ret[x] = 1.0

    return ret

X = 5

Y = 5

N = 10

W = 10

R = 2

model = dnc.DNC(X, Y, N, W, R)

optimizer = optimizers.Adam()

optimizer.setup(model)

n_data = 10000 # number of input data

loss = 0.0

acc = 0.0

acc_bool = []

for data_cnt in range(n_data):

    loss_frac = np.zeros((1, 2))    

    # prepare one pair of input and target data 

    # length of input data is randomly set

    len_content = np.random.randint(3, 6) 

    # generate one input data as a sequence of randam integers

    content = np.random.randint(0, X-1, len_content) 

    len_seq = len_content + len_content # the former is for input, the latter for the target

    x_seq_list = [float('nan')] * len_seq # input sequence

    t_seq_list = [float('nan')] * len_seq # target sequence

    for i in range(len_seq):

        # convert a format of input data

        if (i < len_content):

            x_seq_list[i] = onehot(content[i], X)

        elif (i == len_content):

            x_seq_list[i] = onehot(X-1, X)

        else:

            x_seq_list[i] = np.zeros(X).astype(np.float32)

        # convert a format of output data

        if (i >= len_content):

            t_seq_list[i] = onehot(content[i - len_content], X)         

    model.reset_state() # reset reccurent state per input data

    # input data is fed as a sequence

    for cnt in range(len_seq):

        x = Variable(x_seq_list[cnt].reshape(1, X))

        if (isinstance(t_seq_list[cnt], np.ndarray)):

            t = Variable(t_seq_list[cnt].reshape(1, Y))

        else:

            t = []

        y = model(x)

        if (isinstance(t, chainer.Variable)):

            loss += (y - t)**2

            acc_bool.append(np.argmax(y.data)==np.argmax(t.data))                        

            if (np.argmax(y.data)==np.argmax(t.data)): acc += 1

        if (cnt+1==len_seq):

            # training by back propagation

            model.cleargrads()

            loss.grad = np.ones(loss.shape, dtype=np.float32)

            loss.backward()

            optimizer.update()

            loss.unchain_backward()

            # print loss and accuracy

            if data_cnt < 50 or data_cnt >= 9950:

                print('(', data_cnt, ')', acc_bool, ' :: ', loss.data.sum()/loss.data.size/len_content, ' :: ', acc/len_content)

            loss_frac += [loss.data.sum()/loss.data.size/len_seq, 1.]

            loss = 0.0

            acc = 0.0

            acc_bool = []

test 結果

10000回繰り返した時の結果です。

[ ]内の bool 値は、出力べクトルで最大値を1に、その他を0に振り直したものが、入力値と一致するかを bool 値で表したものです。

・最初の20回の結果

( 0 ) [True, False, False]  ::  0.197543557485  ::  0.3333333333333333

( 1 ) [False, False, False, False]  ::  0.209656882286  ::  0.0

( 2 ) [True, False, False]  ::  0.172263367971  ::  0.3333333333333333

( 3 ) [False, True, True]  ::  0.185363880793  ::  0.6666666666666666

( 4 ) [True, True, True, True]  ::  0.157090616226  ::  1.0

( 5 ) [False, False, False, False, False]  ::  0.191528530121  ::  0.0

( 6 ) [True, False, False, False, False]  ::  0.175649337769  ::  0.2

( 7 ) [False, False, False, True, True]  ::  0.173387451172  ::  0.4

( 8 ) [True, False, True, True]  ::  0.150813746452  ::  0.75

( 9 ) [False, True, False]  ::  0.163899072011  ::  0.3333333333333333

( 10 ) [False, False, False, False, False]  ::  0.183468780518  ::  0.0

( 11 ) [True, False, True, False]  ::  0.152743542194  ::  0.5

( 12 ) [False, False, True, False]  ::  0.170574557781  ::  0.25

( 13 ) [False, True, False, True, False]  ::  0.161617393494  ::  0.4

( 14 ) [False, False, False, False]  ::  0.168220555782  ::  0.0

( 15 ) [False, False, False]  ::  0.167814588547  ::  0.0

( 16 ) [False, True, False, False]  ::  0.158575570583  ::  0.25

( 17 ) [False, False, False, False]  ::  0.165678012371  ::  0.0

( 18 ) [False, False, False]  ::  0.165241924922  ::  0.0

( 19 ) [False, True, False]  ::  0.143808253606  ::  0.3333333333333333

・最後20回の結果

( 9980 ) [True, True, True, True]  ::  0.000208107382059  ::  1.0

( 9981 ) [True, True, True, True, True]  ::  0.000164349582046  ::  1.0

( 9982 ) [True, True, True, True, True]  ::  0.000122650777921  ::  1.0

( 9983 ) [True, True, True]  ::  0.000181751077374  ::  1.0

( 9984 ) [True, True, True, True, True]  ::  0.000318505689502  ::  1.0

( 9985 ) [True, True, True, True, True]  ::  0.00023639023304  ::  1.0

( 9986 ) [True, True, True, True, True]  ::  0.000988183766603  ::  1.0

( 9987 ) [True, True, True, True, True]  ::  0.000226851813495  ::  1.0

( 9988 ) [True, True, True]  ::  0.000401457709571  ::  1.0

( 9989 ) [True, True, True, True]  ::  0.000256504747085  ::  1.0

( 9990 ) [True, True, True, True, True]  ::  0.000165695995092  ::  1.0

( 9991 ) [True, True, True, True]  ::  0.000123940082267  ::  1.0

( 9992 ) [True, True, True, True, True]  ::  0.000351718552411  ::  1.0

( 9993 ) [True, True, True, True]  ::  0.000147357559763  ::  1.0

( 9994 ) [True, True, True, True]  ::  0.000173216045368  ::  1.0

( 9995 ) [True, True, True, True]  ::  0.000108330522198  ::  1.0

( 9996 ) [True, True, True, True]  ::  0.00016659933608  ::  1.0

( 9997 ) [True, True, True]  ::  0.000255667418242  ::  1.0

( 9998 ) [True, True, True]  ::  0.000280433737983  ::  1.0

( 9999 ) [True, True, True, True, True]  ::  0.000443447269499  ::  1.0

完璧に正解しています。20回分しか載せていませんが、最後の100回中でFalseは0回でした。ただし、他の手法と比較まではしていないので、DNC だからこそなのかは不明です。

今回はロジックの紹介が目的だったのでここまでとします。

参考URL

・Chainerの実装例はこのページのものを使わせていただきました

DNC (Differentiable Neural Computers) の概要 + Chainer による実装

・今回はGPU、バッチ処理などは考えてませんでしたが下のページが参考になるかと思います

(Chainer) DNC(Differentiable Neural Computers)で文字列の学習&生成

・Tensor Flowでの実装もあるようです

https://github.com/Mostafa-Samir/DNC-tensorflow

・LSTMの解説はここがわかりやすいです

わかるLSTM ～最近の動向と共に

『 Python 』Article List

Category List

Androidに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Pythonに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Swiftに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Unityに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。