DNCは、Dijkstraのアルゴリズムを発見できるか？

吉田さんのコメント

先日のマルレク「ニューラル・コンピュータとは何か？」について、吉田さんから、次のようなコメントをいただきました。

「さて、内容について一点、コメントさせていただきたいと思います。
タイトルを「ニューラル・コンピュータとは何か？」とされていますが、どうしてDifferentiableという単語を省かれたのかしら、と思っています。

私がDNCに大きく期待している点は、Differentiableなアーキテクチャーを設計してみせたことにあります。

DNCは、これまでのディープラーニングネットワークに、「連想リスト」と「双方向リンクドリスト」の機能を与えたものですが、それらを微分可能な形で導入したことが重要なポイントだと考えます。

これにより、大量の訓練データさえあれば、勾配降下法を使って「連想リスト」と「双方向リンクドリスト」の“使い方”を学習可能であることを示した、という点に大きな魅力を感じています。

つまり、ｂとｃとｆを単純に足しておくだけで、後は十分に訓練すれば、どの時点ではリンクドリストを手繰ればよくて、どの時点では検索すればよいか、を学習できるわけですので、もしかしたらDijkstraのアルゴリズムだって発見できるのではなかろうか、と私は期待しているのです。

いかがでしょうか？」

僕の考えを、以下に述べたいと思います。

Differentiableについて

紹介の段階では、ずっと「可微分ニューラルコンピュータ」と呼んできたのですが、マルレクのタイトルから外したのは、少し、わけがあります。

一つは、"differentiable" という術語が指すものに、少し、同語反復的なものを感じたからです。論文のタイトルでは、"Hybrid computing using a neural network with dynamic external memory" となってて、"differentiable"という言葉は出てきていませんね。このタイトルは、これはこれで正確だと思っています。（以前の GravesのNTM論文、"Neural Turing Machine" とは違ったタイトルのつけ方ですね。）

論文の中で "differentiable" という言葉が出てくるのは、次の箇所です。

1. Here we introduce a machine learning model called a differentiable neural computer (DNC), which consists of a neural network that can read from and write to an external memory matrix, analogous to the random-access memory in a conventional computer.
2. The whole system is differentiable, and can therefore be trained end-to-end with gradient descent, allowing the network to learn how to operate and organize the memory in a goal-directed manner.
3. the network, referred to as the ‘controller’, is a differentiable CPU whose operations are learned with gradient descent.
4. Whereas conventional computers use unique addresses to access memory contents, a DNC uses differentiable attention mechanisms.
5. The heads use three distinct forms of differentiable attention.
6. To allow the controller to free and allocate memory as needed, we developed a differentiable analogue of the ‘free list’ memory allocation scheme.

確かに、二つ目の引用にあるように、DNCでは、メモリー管理の部分を含めシステム全体が Gradient Descent で学習可能になっているのは、NTMとの大きな違いです。そのことを、どう評価するかについては、あとで書きます。

ただ、これらの記述では、"differentiable"は、ほとんど、Gradient Descent で訓練可能なものと「同義」で使われているようんに思います。Gradient Descentというのは、損失関数をL、ネットワークのパラメータを$P_i$とした時に、$\partial L / \partial P_i$ を計算することが基本ですので、Lは、当然 "differentiable"でなければなりません。

その意味では、Gradient Descentで訓練する、Feed Forward な Full Connect なネットワークも、CNNもRNNも、Attention Mechanismも、"differentiable" でなければなりません。少なくとも、いわゆるDeep Learningで括られることのあるニューラル・ネットの世界は、すべからく"differentiable" なんだと僕は思っています。"differentiable"  Full Connect, "differentiable" CNN, "differentiable" RNN, "differentiable" Attention と、あえていう必要はないと感じています。

Gravesは、"Differentiable"という言葉を、いつから使ったのか？

どこからこうした言葉遣いが出てきたのか、興味あります。今だったら、Gravesの”Differentiable Neural Computer"が、最大の根拠になりそうですが。 他にリソースがある可能性もあるんですが、 ....

実は、Gravesは、DNC論文に先行するNTM論文で、既に、"differentiable"  という言葉を使っています。

1. The combined system is analogous to a Turing Machine or Von Neumann architecture but is differentiable end-toend, allowing it to be efficiently trained with gradient descent.
2. Unlike a Turing machine, an NTM is a differentiable computer that can be trained by gradient descent, yielding a practical mechanism for learning programs.
3. Other important precursors to our work include differentiable models of attention
4. Crucially, every component of the architecture is differentiable, making it straightforward to train with gradient descent.
5. which is clearly differentiable with respect to both the memory and the weighting.
6. Since both erase and add are differentiable, the composite write operation is differentiable too.
7. Like conventional neural networks, the architecture is differentiable end-to-end and can be trained with gradient descent

NTM論文では、すでに、"NTM is a differentiable computer" だとされているんです。The whole system is differentiable であることが、システムをdifferentiable と呼ぶ条件ではないと思います。

DNC, NTM論文の一つ前のGravesの論文に、"Generating Sequences With Recurrent Neural Networks"という論文があります。ただ、この論文では、"differentiable"という言葉は、一回も使われていません。この論文の次のような表現が、differentiableなシステムについて語っていると思うことができます。

RNNs are ‘fuzzy’ in the sense that they do not use exact templates from the training data to make predictions, but rather—like other neural networks— use their internal representation to perform a high-dimensional interpolation between training examples. This distinguishes them from n-gram models and compression algorithms such as Prediction by Partial Matching [5], whose predictive distributions are determined by counting exact matches between the recent history and the training set.

こうした理解は、とても参考になります。

Gravesは、NTM論文を書く時点で、ニューラル・ネットワークのGradient Descentでトレーニング可能なものを、"differentiable" と呼ぶことを思いついたのではないかと想像しています。ちゃんと調べる必要があるのですが ....。

（これは、僕の全くの空想ですが、Differential Neural Computer というネーミング で、Gravesの念頭にあったのは、Babbageの”Difference Engine" だったのではとないかと妄想しています。"Turing Machine"も"Difference Engine"も、イギリス製ですからね。）

NTMからDNCへの「発展」を、どう評価するのか

空想は、さておき、NTMからDNCへの「発展」を、どう評価するのかという問題があります。

変化は、メモリー管理機構の所に集中しています。これは、本当に徹底してよくやったなとは思います。確かに、それは、content-baseのread/writeとsequentialなread/writeの使い分けを学習できるでしょう。ただ、これは、メモリーへのアクセスを、ロケーション N上の重み付け分布で行うという、NTM, DNCの基本的なアイデアのcorollary として出てきたものような気がします。（どっから出てきたものでも、結果が出てくれば、いいのですが。）

ただ、それはプリミティブなもので、複雑なデータ構造や、baBiのような自然言語の理解に届く飛躍につながるものだとは、僕は考えていません。ただ、積極的な言い方をすれば、知能における記憶へのアクセスの問題と、変数概念の重要性を初めて強調していることは、高く評価しています。

メモリー管理の問題で、細かなことですが、次のようなところも気になっています。Gravesは、DNC論文の中で次のように書いています。また、ロケーション・サイズを、256から512に拡大した場合のメモリーの利用状況のマップ(Extended Data Figure 2)も示しています。

The allocation mechanism is independent of the size and contents of the memory, meaning that DNCs can be trained to solve a task using one size of memory and later upgraded to a larger memory without retraining

ただ、この部分、僕は少し疑っています。

メモリーのロケーション・サイズの変更は、コンピュータから見てDNCは、一つのアプリケーションでしかないので、OSレベルの mallocでも使えば、すぐにできます。それは、いいんです。

ロケーションのサイズが、NからN'になった時、メモリーにアクセスするロケーション上の重み付けベクトルは、N次元のものからN'次元のものに変わります。添え字を、全部、NからN'に変えなければいけないわけで、中の計算結果も変わるはずです。size=Nとsize=N'の計算結果が、完全に一致するのは、重み付けベクトルが、One-Hot-Valueの形をしている場合だけな気がします。

もしも、そうした性質が、メモリーの拡張性にとって重要であるなら、メモリー・アクセスに'blur'な（でも、’sharp'な）重み付けを導入する意味がよくわかりません。NTMで使っていた、Rotational Shiftも、Convolutionを使わないで、ベクトルの要素ごと、丸ごとシフトする方法だってあるような気がします。

僕には、残念ながら、メモリー・アロケーションシステムに、Gravesのいう"differentiable"なメカニズムを導入したことは、「成果」というより、その働きがよくわかっていないのです。この辺りは、色々なvariantがあるような気がしています。ただ、先にも述べましたが、知能研究で、（脳でも機械でも）「記憶へのアクセス」のモデル化は重要だと思っています。これは、これから重要になる分野だと思います。

DNCは、Dijkstra法を発見できるか？

Dijkstraのアルゴリズムを、DNCが発見できるのではという意見については、僕は、否定的です。

まず、冷静に、DNCが行った三つの実験の成績を評価することから、始めるのがいいと思います。それについては、今回の講演スライドでもいくつか、僕の評価を述べています。

次に、機械に何ができるのかを議論する際の、方法論的に面倒臭い議論を意識する必要があります。これについては、前回のマルレクのGoogle機械翻訳の回の講演資料の「方法論的な問題」という節を読んでいただければと思います。

ここでは、別の切り口を述べて見たいと思います。

ノードaからノードzへの最短経路を求めよという問題があったとします。一般に、教師有りのニューラル・ネットの訓練では、入力xと正解としてのターゲットtの二つを、損失関数Lに与えます。Gradient Descentは、多数の（x,t）データが与えられると、Lをパラメーターで偏微分した値が最小になるようにパラメーターの値を繰り返し変更します。

まず、マシンDNC1が、「総当たり法」と解釈される方法で（ニューラル・ネットが内部で行っている処理を、外部から「アルゴリズム」として把握するのは、実は難しいのです。これも、いろんな議論がありそうです。もっとも単純な議論は、「アルゴリズムがわかっているのなら、ニューラルネットなど使わないで、それを使え」ということになるでしょう。）問題を解いたとしましょう。

問題は、このマシンDNC1に、「総当たり法」ではない方法で、問題を解けと、どう指示できるかということです。

同じ形式のデータセット(s,t)を使っている限りは、データをいくら増やしても、同じ解き方をするはずです。「総当たり法」は、それが効率の問題を別にすれば、正しい答えを与えるアルゴリズムである以上、Gradient Discent 的には、誤った解を与える「局所的な極小値」ではなく、「最小値」を与えているからです。

ですから、マシンDNC2に、Dijkstra法を発見させるためには、データセット(s,t)を与えるだけでは不十分です。（このデータセットについては、マシンDNC1が「総当たり法」で解いたと仮定しています。）

すぐに思いつく一つのアイデアは、ターゲットに、計算量のオーダー O(C) とか、メモリー使用量のオーダー O(M)とかを含ませることです。

でも、データセット（s,(t, O(C), O(M)))は、形おかしいですね。s, t は、データごとに値の変わる具体的な値を持つインスタンスなのに、O(C), O(M)は、O(N^2)とか、O(NlogN)とか、変数を含んだ式で表現されることになります。しかも、求めたいアルゴリズムについては、いつも同じ値をとります。（あるアルゴリズムについて、これらのオーダーを、あらかじめ与えることも、実際には、難しいのです。同じオーダーでも、異なるアルゴリズムも、当然、ありえます。）

じゃ、それらを、ターゲットの中ではなく、ネットワークのメタ・パラメータにすればいいかというと、それは、ユニバーサルなGradient Descent の手法を修正することにしかならないでしょう。

僕には、別のアイデアもあります。Gravesが、NTMからDNCへのメモリー管理機構の増設を通じて、DNCに、いくつかの能力を付与したように、dijkstra法に必要な、メカニズムを、differentiableな形で後付けすることです。でも、これじゃ、何をしているのかわかりませんね。

もう一つのアイデアは、今回の講演では、割愛したのですが、DNCの訓練で利用されている Curriculum learningというのを使うことです。順番に、学習すべきことを誘導するやり方ですね。

SORTの問題をDNCに解かせてみるのが、面白いと思います。DNCのメモリー管理機構が可能にしたアドレッシングを使って、問題を解くような気がします。ただ、それで解けちゃうのなら、再帰的なQuick Sortは、思いつかないでしょう。

再帰なら、DNCにstack構造の操作を教えてみるのも面白いと思います。これは、すぐ、できそうな気がします。

一方、「ある問題を解く、アルゴリズムを全て求めよ」という問題は、形式的には、きちんと定義できるかもしれません。もちろん、定義できたとしても、明らかに、recursive には、解けない問題になるでしょうね。ただ、ニューラル・ネットワークでは、定式化すら難しい問題になってしまうと思います。