View source for Differentiable neural computer

{{short description|Artificial neural network architecture}}
[[File:DNC training recall task.gif|thumb|300px|A differentiable neural computer being trained to store and recall dense binary numbers. Performance of a reference task during training shown. Upper left: the input (red) and target (blue), as 5-bit [[Word (computer architecture)|words]] and a 1 bit interrupt signal. Upper right: the model's output.]]

In [[artificial intelligence]], a '''differentiable neural computer''' ('''DNC''') is a memory augmented [[artificial neural network|neural network]] architecture (MANN), which is typically (but not by definition) recurrent in its implementation. The model was published in 2016 by [[Alex Graves (computer scientist)|Alex Graves]] et al. of [[DeepMind]].<ref name="DNCnature2016"/>

== Applications ==
DNC indirectly takes inspiration from [[Von Neumann architecture|Von-Neumann architecture]], making it likely to outperform conventional architectures in tasks that are fundamentally algorithmic that cannot be learned by finding a [[decision boundary]].

So far, DNCs have been demonstrated to handle only relatively simple tasks, which can be solved using conventional programming. But DNCs don't need to be programmed for each problem, but can instead be trained. This attention span allows the user to feed complex [[data structure]]s such as [[Graph (abstract data type)|graphs]] sequentially, and recall them for later use. Furthermore, they can learn aspects of [[Symbolic Reasoning|symbolic reasoning]] and apply it to working memory. The researchers who published the method see promise that DNCs can be trained to perform complex, structured tasks<ref name="DNCnature2016">{{Cite journal|last1=Graves|first1=Alex|last2=Wayne|first2=Greg|last3=Reynolds|first3=Malcolm|last4=Harley|first4=Tim|last5=Danihelka|first5=Ivo|last6=Grabska-Barwińska|first6=Agnieszka|last7=Colmenarejo|first7=Sergio Gómez|last8=Grefenstette|first8=Edward|last9=Ramalho|first9=Tiago|date=2016-10-12|title=Hybrid computing using a neural network with dynamic external memory|url=http://www.nature.com/articles/nature20101.epdf?author_access_token=ImTXBI8aWbYxYQ51Plys8NRgN0jAjWel9jnR3ZoTv0MggmpDmwljGswxVdeocYSurJ3hxupzWuRNeGvvXnoO8o4jTJcnAyhGuZzXJ1GEaD-Z7E6X_a9R-xqJ9TfJWBqz|journal=Nature|language=en|volume=538|issue=7626|doi=10.1038/nature20101|issn=1476-4687|pages=471–476|pmid=27732574|bibcode=2016Natur.538..471G|s2cid=205251479}}</ref><ref>{{Cite web|url=https://deepmind.com/blog/differentiable-neural-computers/|title=Differentiable neural computers {{!}} DeepMind|website=DeepMind|date=12 October 2016 |access-date=2016-10-19}}</ref> and address big-data applications that require some sort of reasoning, such as generating video commentaries or semantic text analysis.<ref name=":0" /><ref>{{Cite journal|last=Jaeger|first=Herbert|date=2016-10-12|title=Artificial intelligence: Deep neural reasoning|journal=Nature|language=en|volume=538|issue=7626|doi=10.1038/nature19477|issn=1476-4687|pages=467–468|pmid=27732576|bibcode=2016Natur.538..467J|doi-access=free}}</ref>

DNC can be trained to navigate [[rapid transit]] systems, and apply that network to a different system. A neural network without memory would typically have to learn about each transit system from scratch. On graph traversal and sequence-processing tasks with [[supervised learning]], DNCs performed better than alternatives such as [[long short-term memory]] or a neural turing machine.<ref name=":1">{{Cite web|url=http://www.i-programmer.info/news/105-artificial-intelligence/10174-deepminds-differential-nn-thinks-deeply.html|title=DeepMind's Differentiable Neural Network Thinks Deeply|last=James|first=Mike|date=|website=www.i-programmer.info|access-date=2016-10-20}}</ref> With a [[reinforcement learning]] approach to a block puzzle problem inspired by [[SHRDLU]], DNC was trained via curriculum learning, and learned to make a [[Automated planning and scheduling|plan]]. It performed better than a traditional [[recurrent neural network]].<ref name=":1" />

== Architecture ==
[[File:Differentiable Neural Computer.svg|thumb|DNC system diagram]]

DNC networks were introduced as an extension of the [[Neural Turing Machine]] (NTM), with the addition of memory attention mechanisms that control where the memory is stored, and temporal attention that records the order of events. This structure allows DNCs to be more robust and abstract than a NTM, and still perform tasks that have longer-term dependencies than some predecessors such as Long Short Term Memory ([[Long short-term memory|LSTM]]). The memory, which is simply a matrix, can be allocated dynamically and accessed indefinitely. The DNC is [[Differentiable function|differentiable]] end-to-end (each subcomponent of the model is differentiable, therefore so is the whole model). This makes it possible to optimize them efficiently using [[gradient descent]].<ref name=":0">{{Cite news|url=https://www.wired.co.uk/article/deepmind-ai-tube-london-underground|title=DeepMind's AI learned to ride the London Underground using human-like reason and memory|last=Burgess|first=Matt|newspaper=WIRED UK|language=en-GB|access-date=2016-10-19}}</ref><ref>{{Cite news|url=https://www.pcmag.com/news/348701/deepmind-ai-learns-to-navigate-london-tube|title=DeepMind AI 'Learns' to Navigate London Tube|newspaper=PCMAG|access-date=2016-10-19}}</ref><ref>{{Cite web|url=https://techcrunch.com/2016/10/13/__trashed-2/|title=DeepMind's differentiable neural computer helps you navigate the subway with its memory|last=Mannes|first=John|website=TechCrunch|date=13 October 2016 |access-date=2016-10-19}}</ref>

The DNC model is similar to the [[Von Neumann architecture]], and because of the resizability of memory, it is [[Turing complete]].<ref>{{cite web|url=https://www.youtube.com/watch?v=steioHoiEms?t=721|title=RNN Symposium 2016: Alex Graves - Differentiable Neural Computer|website=[[YouTube]]|date=22 March 2017 }}</ref>

=== Traditional DNC ===
{{Confusing section|date=October 2017|reason=a list of equations (without, e.g., an '''exhaustive''' association with a complete diagram of the DNC) is not a digestible description for many readers of this article}}

DNC, as originally published<ref name="DNCnature2016"/>

{|
| style="padding-top:2em;" | '''Independent variables'''
|
|-
| <math>\mathbf{x}_t</math>
| Input vector
|-
| <math>\mathbf{z}_t</math>
| Target vector
|-
| style="padding-top:2em;"| '''Controller'''
|
|-
| <math>\boldsymbol\chi_t = [\mathbf{x}_t; \mathbf{r}_{t-1}^1; \cdots; \mathbf{r}_{t-1}^R]</math>
| Controller input matrix
|-
|<hr>
|<hr>
|-
| [[Long short-term memory|Deep (layered) LSTM]]
| <math>\forall\;0\leq l\leq L</math>
|-
| <math>\mathbf{i}_t^l = \sigma(W_{i}^l [\boldsymbol\chi_t; \mathbf{h}_{t-1}^l; \mathbf{h}_t^{l-1}] + \mathbf{b}_i^l)</math>
| Input gate vector
|-
| <math>\mathbf{o}_t^l = \sigma(W_{o}^l [\boldsymbol\chi_t; \mathbf{h}_{t-1}^l; \mathbf{h}_t^{l-1}] + \mathbf{b}_o^l)</math>
| Output gate vector
|-
| <math>\mathbf{f}_t^l = \sigma(W_{f}^l [\boldsymbol\chi_t; \mathbf{h}_{t-1}^l; \mathbf{h}_t^{l-1}] + \mathbf{b}_f^l)</math>
| Forget gate vector
|-
| <math>\mathbf{s}_t^l = \mathbf{f}_t^l \mathbf{s}_{t-1}^l + \mathbf{i}_t^l\tanh(W_{s}^l [\boldsymbol\chi_t; \mathbf{h}_{t-1}^l; \mathbf{h}_t^{l-1}] + \mathbf{b}_s^l)</math>
| State gate vector,<br><math>s_0 = 0</math>
|-
| <math>\mathbf{h}_t^l = \mathbf{o}_t^l \tanh(\mathbf{s}_t^l)</math>
| Hidden gate vector,<br><math>h_0=0; h_t^0=0\;\forall\;t</math>
|-
|<hr>
|<hr>
|-
| <math>\mathbf{y}_t=W_y[\mathbf{h}_t^1;\cdots;\mathbf{h}_t^L]+W_r[\mathbf{r}_t^1;\cdots;\mathbf{r}_t^R]</math>
| DNC output vector
|-
| style="padding-top:2em;" | '''Read & Write heads'''
|
|-
| <math>\xi_t = W_\xi[h_t^1;\cdots;h_t^L]</math>
| Interface parameters
|-
| colspan="2" | <math>=[\mathbf{k}_t^{r,1};\cdots;\mathbf{k}_t^{r,R};\hat{\beta}_t^{r,1};\cdots;\hat{\beta}_t^{r,R};\mathbf{k}_t^w;\hat{\beta_t^w};\mathbf{\hat{e}}_t;\mathbf{v}_t;\hat{f_t^1};\cdots;\hat{f_t^R};\hat{g}_t^a;\hat{g}_t^w;\hat{\boldsymbol\pi}_t^1;\cdots;\hat{\boldsymbol\pi}_t^R]</math>
|-
|<hr>
|<hr>
|-
| Read heads
| <math>\forall\;1\leq i\leq R</math>
|-
| <math>\mathbf{k}_t^{r,i}</math>
| Read keys
|-
| <math>\beta_t^{r,i}=\text{oneplus}(\hat{\beta}_t^{r,i})</math>
| Read strengths
|-
| <math>f_t^i=\sigma(\hat{f}_t^i)</math>
| Free gates
|-
| <math>\boldsymbol\pi_t^i=\text{softmax}(\hat{\boldsymbol\pi}_t^i)</math>
| Read modes,<br><math>\boldsymbol\pi_t^i\in\mathbb{R}^3</math>
|-
|<hr>
|<hr>
|-
| Write head
| 
|-
| <math>\mathbf{k}_t^w</math>
| Write key
|-
| <math>\beta_t^w=\hat{\beta}_t^w</math>
| Write strength
|-
| <math>\mathbf{e}_t=\sigma(\mathbf{\hat{e}}_t)</math>
| Erase vector
|-
| <math>\mathbf{v}_t</math>
| Write vector
|-
| <math>g_t^a=\sigma(\hat{g}_t^a)</math>
| Allocation gate
|-
| <math>g_t^w=\sigma(\hat{g}_t^w)</math>
| Write gate
|-
| style="padding-top:2em;" | '''Memory'''
|
|-
| <math>M_t=M_{t-1}\circ(E-\mathbf{w}_t^w\mathbf{e}_t^\intercal)+\mathbf{w}_t^w\mathbf{v}_t^\intercal</math>
| Memory matrix,<br>Matrix of ones <math>E\in\mathbb{R}^{N\times W}</math>
|-
| <math>\mathbf{u}_t=(\mathbf{u}_{t-1}+\mathbf{w}_{t-1}^w-\mathbf{u}_{t-1}\circ\mathbf{w}_{t-1}^w)\circ\boldsymbol\psi_t</math>
| Usage vector
|-
| <math>\mathbf{p}_t=\left(1-\sum_i\mathbf{w}_t^w[i]\right)\mathbf{p}_{t-1}+\mathbf{w}_t^w</math>
| Precedence weighting,<br><math>\mathbf{p}_0=\mathbf{0}</math>
|-
| <math>L_t=(\mathbf{1} - \mathbf{I})\left[(1-\mathbf{w}_t^w[i]-\mathbf{w}_t^w[j])L_{t-1}[i,j]+\mathbf{w}_t^w[i]\mathbf{p}_{t-1}^j\right]</math>
| Temporal link matrix,<br><math>L_0=\mathbf{0}</math>
|-
| <math>\mathbf{w}_t^w=g_t^w[g_t^a\mathbf{a}_t+(1-g_t^a)\mathbf{c}_t^w]</math>
| Write weighting
|-
| <math>\mathbf{w}_t^{r,i}=\boldsymbol\pi_t^i[1]\mathbf{b}_t^i+\boldsymbol\pi_t^i[2]c_t^{r,i}+\boldsymbol\pi_t^i[3]f_t^i</math>
| Read weighting
|-
| <math>\mathbf{r}_t^i=M_t^\intercal\mathbf{w}_t^{r,i}</math>
| Read vectors
|-
|<hr>
|<hr>
|-
| <math>\mathcal{C}(M,\mathbf{k},\beta)[i]=\frac{\exp\{\mathcal{D}(\mathbf{k},M[i,\cdot])\beta\}}{\sum_j\exp\{\mathcal{D}(\mathbf{k},M[j,\cdot])\beta\}}</math>
| [[Content-based addressing]],<br>Lookup key <math>\mathbf{k}</math>, key strength <math>\beta</math>
|-
| <math>\phi_t</math>
| Indices of <math>\mathbf{u}_t</math>,<br>sorted in ascending order of usage
|-
| <math>\mathbf{a}_t[\phi_t[j]]=(1-\mathbf{u}_t[\phi_t[j]])\prod_{i=1}^{j-1}\mathbf{u}_t[\phi_t[i]]</math>
| Allocation weighting
|-
| <math>\mathbf{c}_t^w=\mathcal{C}(M_{t-1},\mathbf{k}_t^w,\beta_t^w)</math>
| Write content weighting
|-
| <math>\mathbf{c}_t^{r,i}=\mathcal{C}(M_{t-1},\mathbf{k}_t^{r,i},\beta_t^{r,i})</math>
| Read content weighting
|-
| <math>\mathbf{f}_t^i=L_t\mathbf{w}_{t-1}^{r,i}</math>
| Forward weighting
|-
| <math>\mathbf{b}_t^i=L_t^\intercal\mathbf{w}_{t-1}^{r,i}</math>
| Backward weighting
|-
| <math>\boldsymbol\psi_t=\prod_{i=1}^R\left(\mathbf{1}-f_t^i\mathbf{w}_{t-1}^{r,i}\right)</math>
| Memory retention vector
|-
| style="padding-top:2em;" | '''Definitions'''
|
|-
| <math>\mathbf{W},\mathbf{b}</math>
| [[Weight matrix]], bias vector
|-
| <math>\mathbf{0},\mathbf{1},\mathbf{I}</math>
| Zeros matrix, ones matrix, [[identity matrix]]
|-
| <math>\circ</math>
| Element-wise multiplication
|-
| <math>\mathcal{D}(\mathbf{u},\mathbf{v})=\frac{\mathbf{u}\cdot\mathbf{v}}{\|\mathbf{u}\|\|\mathbf{v}\|}</math>
| [[Cosine similarity]]
|-
| <math>\sigma(x)=1/(1+e^{-x})</math>
| [[Sigmoid function]]
|-
| <math>\text{oneplus}(x)=1+\log(1+e^x)</math>
| Oneplus function
|-
| <math>\text{softmax}(\mathbf{x})_j = \frac{e^{x_j}}{\sum_{k=1}^K e^{x_k}}</math> &nbsp;&nbsp; for ''j'' = 1, ..., ''K''.
| [[Softmax function]]
|}

=== Extensions ===
Refinements include sparse memory addressing, which reduces time and space complexity by thousands of times. This can be achieved by using an approximate nearest neighbor algorithm, such as [[Locality-sensitive hashing]], or a random [[k-d tree]] like Fast Library for Approximate Nearest Neighbors from [[University of British Columbia|UBC]].<ref>{{cite arXiv|eprint=1610.09027|title=Scaling Memory-Augmented Neural Networks with Sparse Reads and Writes|author1=Jack W Rae|author2=Jonathan J Hunt|last3=Harley|first3=Tim|last4=Danihelka|first4=Ivo|last5=Senior|first5=Andrew|last6=Wayne|first6=Greg|last7=Graves|first7=Alex|author8=Timothy P Lillicrap|class=cs.LG|year=2016}}</ref> Adding Adaptive Computation Time (ACT) separates computation time from data time, which uses the fact that problem length and problem difficulty are not always the same.<ref>{{cite arXiv|eprint=1603.08983|title=Adaptive Computation Time for Recurrent Neural Networks|last1=Graves|first1=Alex|class=cs.NE|year=2016}}</ref> Training using synthetic gradients performs considerably better than [[Backpropagation through time]] (BPTT).<ref>{{cite arXiv|eprint=1608.05343|title=Decoupled Neural Interfaces using Synthetic Gradients|last1=Jaderberg|first1=Max|author2=Wojciech Marian Czarnecki|last3=Osindero|first3=Simon|last4=Vinyals|first4=Oriol|last5=Graves|first5=Alex|last6=Silver|first6=David|last7=Kavukcuoglu|first7=Koray|class=cs.LG|year=2016}}</ref> Robustness can be improved with use of layer normalization and Bypass Dropout as regularization.<ref>{{cite arXiv|eprint=1807.02658|title=Robust and Scalable Differentiable Neural Computer for Question Answering|last1=Franke|first1=Jörg|last2=Niehues|first2=Jan|last3=Waibel|first3=Alex|class=cs.CL|year=2018}}</ref>

==See also==
*[[Differentiable programming]]

== References ==
{{Reflist}}

== External links ==
* [https://jaspock.github.io/funicular/dnc.html A bit-by-bit guide to the equations governing differentiable neural computers]
* [http://www.i-programmer.info/news/105-artificial-intelligence/10174-deepminds-differential-nn-thinks-deeply.html DeepMind's Differentiable Neural Network Thinks Deeply]

{{Artificial intelligence navbox}}

[[Category:Neural network architectures]]
[[Category:Artificial neural networks]]