part1/deepmind/DNC/Hybrid_computing_using_a_neural_network_with_dynamic_external_memory.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Hybrid computing using a neural network with dynamic external memory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 싸이그래머 / HAI : 파트 1 - 딥마인드 논문리뷰 [1]\n",
    "* 김무성"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Contents\n",
    "* System overview\n",
    "* Interaction between the heads and the memory\n",
    "* Synthetic question answering experiments\n",
    "* Graph experiments\n",
    "* Block puzzle experiments"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 참고\n",
    "* [2] Differentiable neural computers - https://deepmind.com/blog/differentiable-neural-computers/\n",
    "* [3] Deep Learning for Computer Vision: Attention Models (UPC 2016) - http://www.slideshare.net/xavigiro/deep-learning-for-computer-vision-attention-models-upc-2016\n",
    "* [4] Neural Turing Machines(Ilya Kuzovkin's SlideShare) - http://www.slideshare.net/iljakuzovkin/neural-turing-machines\n",
    "* [5] Neural Turing Machines(SlideShare) - http://www.slideshare.net/yuzurukato/neural-turing-machines-43179669"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"figures/cap1.png\"  />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Artificial neural networks are remarkably adept at sensory processing, sequence learning and reinforcement learning, <font color=\"blue\">but are limited in their ability</font> <font color=\"green\">to represent variables and data structures and to store data over long timescales</font>, owing to the <font color=\"red\">lack of an external memory</font>. \n",
    "\n",
    "Here we introduce a machine learning model called a <font color=\"red\">differentiable neural computer (DNC)</font>, \n",
    "* which consists of a neural network that can <font color=\"red\">read from and write to an external memory matrix</font>, analogous to the random-access memory in a conventional computer. \n",
    "* Like a conventional computer, it can use its memory to represent and manipulate complex data structures, but, <font color=\"red\">like a neural network, it can learn to do so from data</font>."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We aim to combine the advantages of neural and computational processing by providing a neural network with read–write access to external memory. \n",
    "* The access is narrowly focused, minimizing interference among memoranda and enabling long-term storage.\n",
    "* The whole system is differentiable, and can therefore be trained end-to-end with gradient descent, \n",
    "    - allowing the network to learn how to \n",
    "        - operate and \n",
    "        - organize \n",
    "    - the memory in a goal-directed manner."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# System overview"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A DNC is <font color=\"purple\">a neural network coupled to an external memory matrix</font>.\n",
    "* If the <font color=\"red\">memory</font> can be thought of as the <font color=\"red\">DNC’s RAM</font>, \n",
    "* then <font color=\"blue\">the network</font>, referred to as the <font color=\"blue\">‘controller’</font>, \n",
    "    - is a <font color=\"blue\">differentiable CPU</font> \n",
    "        - whose operations are learned \n",
    "            - with gradient descent.\n",
    "* An earlier form of DNC, the neural Turing machine, had a similar structure, but more limited memory access methods (see Methods for further discussion)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### memory, attention, locaton, weightings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Whereas conventional computers use unique addresses to access memory contents, a DNC uses \n",
    "    - differentiable <font color=\"red\">attention mechanisms</font> \n",
    "    - to define distributions \n",
    "        - over the N rows, or ‘locations’, \n",
    "            - in the N × W memory matrix M.\n",
    "* These distributions, which we call <font color=\"red\">weightings</font>, represent \n",
    "    - the <font color=\"red\">degree</font> to \n",
    "        - which <font color=\"red\">each location is involved</font> \n",
    "            - in a read or write operation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### read "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The read vector r returned by a read weighting $w^r$ over memory M is a weighted sum over the memory locations:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"figures/eq_r.png\" width=600 />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### write"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Similarly, the write operation uses a write weighting $w^w$ to first erase with an erase vector $e$, then add a write vector $v$:\n",
    "\n",
    "$M[i,j]$ ← $M[i,j](1 − w^w[i]e[j]) + w^w[i]v[j]$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### read and write heads"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The functional units that determine and apply the weightings are called read and write heads."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"figures/cap1.png\"  />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Interaction between the heads and the memory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The heads use three distinct forms of differentiable attention. \n",
    "* The first is <font color=\"red\">content lookup</font>, \n",
    "    - in which a <font color=\"blue\">key vector</font> \n",
    "        - emitted by the controller\n",
    "    - is <font color=\"blue\">compared to the content</font> of \n",
    "        - each location in memory \n",
    "            - according to a <font color=\"blue\">similarity measure</font> \n",
    "                - (here, cosine similarity).\n",
    "    - The similarity scores determine a weighting that can be used by the read heads for associative recall1 or by the write head to modify an existing vector in memory.\n",
    "    - Importantly, a key that only partially matches the content of a memory location can still be used to attend strongly to that location.\n",
    "    - <font color=\"green\">In general, key-value retrieval provides a rich mechanism for navigating associative data structures in the external memory, because the content of one address can effectively encode references to other addresses.</font>\n",
    "* A second attention mechanism <font color=\"red\">records transitions</font>\n",
    "    - between consecutively written locations \n",
    "        - in an N × N <font color=\"blue\">temporal link matrix L</font>.\n",
    "    - L[i, j] is close to 1 if i was the next location written after j, and is close to 0 otherwise. \n",
    "    - For any weighting w, the operation Lw <font color=\"blue\">smoothly shifts</font> the focus <font color=\"blue\">forwards</font> to the locations written after those emphasized in w, whereas $L^⊤w$ shifts the focus <font color=\"blue\">backwards</font>.\n",
    "    -  <font color=\"green\">This gives a DNC the native ability to recover sequences in the order in which it wrote them, even when consecutive writes did not occur in adjacent time-steps</font>.\n",
    "* The third form of attention <font color=\"red\">allocates memory for writing</font>.\n",
    "    - The <font color=\"blue\">‘usage’ of each location</font> is represented as a number between 0 and 1, and a weighting that picks out unused locations is delivered to the write head. \n",
    "    - As well as automatically increasing with each write to a location, usage can be decreased after each read. \n",
    "    - <font color=\"green\">This allows the controller to reallocate memory that is no longer required.</font>\n",
    "    - <font color=\"green\">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</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### mammalian hippocampus"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* The design of the attention mechanisms was motivated largely by computational considerations. \n",
    "    - Content lookup enables the formation of associative data structures;\n",
    "    - temporal links enable sequential retrieval of input sequences; \n",
    "    - and allocation provides the write head with unused locations.\n",
    "* However, there are interesting parallels between the memory mechanisms of a DNC and the functional capabilities of the mammalian hippocampus."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Synthetic question answering experiments"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our first experiments investigated the capacity of the DNC to perform question answering. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 참고\n",
    "* [6] Playground for bAbI tasks - https://yerevann.github.io/2016/02/23/playground-for-babi-tasks/\n",
    "* [7] Dynamic Memory Networks by YerevanNN Web Demo - http://yerevann.com/dmn-ui/#/\n",
    "* [8] Curriculum Learning - http://videolectures.net/icml09_bengio_cl/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### bAbI Task\n",
    "* To compare DNCs to other neural network archi- tectures, we considered the bAbI dataset26, which includes 20 types of synthetically generated questions designed to mimic aspects of textual reasoning. \n",
    "* We found that a single DNC, jointly trained on all 20 question types with 10,000 instances each, was able to achieve a mean test error rate of 3.8% with task failure (defined as >5% error) on 2 types of questions, compared to 7.5% mean error and 6 failed tasks for the best previous jointly trained result21. \n",
    "* We also found that DNCs performed much better than both long short-term memory (LSTM; at present the benchmark neural network for most sequence processing tasks) and the neural Turing machine16 (see Extended Data Table 1 for details). \n",
    "* Unlike previous results on this dataset, the inputs to our model were single word tokens without any preprocessing or sentence-level features (see Methods for details)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Graph experiments"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Although bAbI is presented in natural language, each declarative sen- tence involves a limited vocabulary and is generated from a simple triple containing an actor, an action and a set of arguments. Such sentences could easily be rendered in graphical form.\n",
    "*  In this sense, the <font color=\"red\">propositional knowledge</font> in many of the bAbI tasks is equivalent to a set of constraints on an underlying <font color=\"red\">graph structure</font>."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=\"red\">We therefore turn next to a set of synthetic reasoning experiments on randomly generated graphs.</font>\n",
    "* Unlike bAbI, the edges in our graphs were presented explicitly, with each input vector specifying a triple consisting of two node labels and an edge label. \n",
    "* We generated training graphs with random labelling and connectivity and defined <font color=\"red\">three kinds of query</font>: \n",
    "    - ‘traversal’, \n",
    "    - ‘shortest path’ and \n",
    "    - ‘inference’"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "After training with curriculum learning using graphs and queries with gradually increasing complexity, the networks were tested (with no retraining) on two specific graphs as a test of generalization to realistic data: \n",
    "* a symbolic map of the London Underground and \n",
    "* an invented family tree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"figures/cap2.png\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### traversal task "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For the traversal task (Fig. 2b), the network was instructed to report the node arrived at after leaving a start node and following a path of edges generated by a random walk."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### shortest-path task"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* For the shortest-path task (Fig. 2b), a random start and end node were given as the query, and the net- work was asked to return a sequence of triples corresponding to a minimum-length path between them. \n",
    "* Because we considered paths of up to length five, this is a harder version of the path-finding task in the bAbI dataset, which has a maximum length of two."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### inference task"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* For the inference task (Fig. 2c), we predefined 400 ‘relation’ labels that stood as abbreviations for sequences of up to five connected edge labels.\n",
    "* A query consisted of an incomplete triple specifying a start node and a relation label, and the required answer was the final node after following the relation sequence.\n",
    "* Because the relation sequences were never presented to the network, they had to be inferred from the queries and targets."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### result\n",
    "* As a benchmark we again compared DNCs with LSTM. \n",
    "* In this case, the best LSTM network we found in an extensive hyper-parameter search failed to complete the first level of its training curriculum of even the easiest task (traversal), reaching an average of only 37% accuracy after almost two million training examples; \n",
    "* DNCs reached an average of 98.8% accuracy on the final lesson of the same curriculum after around one million training examples."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"figures/cap3.png\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Block puzzle experiments"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"figures/cap4.png\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"figures/cap5.png\" width=600 />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Discussion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 참고자료\n",
    "* [1] Hybrid computing using a neural network with dynamic external memory - http://www.nature.com/nature/journal/vaop/ncurrent/full/nature20101.html\n",
    "* [2] Differentiable neural computers - https://deepmind.com/blog/differentiable-neural-computers/\n",
    "* [3] Deep Learning for Computer Vision: Attention Models (UPC 2016) - http://www.slideshare.net/xavigiro/deep-learning-for-computer-vision-attention-models-upc-2016\n",
    "* [4] Neural Turing Machines(Ilya Kuzovkin's SlideShare) - http://www.slideshare.net/iljakuzovkin/neural-turing-machines\n",
    "* [5] Neural Turing Machines(SlideShare) - http://www.slideshare.net/yuzurukato/neural-turing-machines-43179669\n",
    "* [6] Playground for bAbI tasks - https://yerevann.github.io/2016/02/23/playground-for-babi-tasks/\n",
    "* [7] Dynamic Memory Networks by YerevanNN Web Demo - http://yerevann.com/dmn-ui/#/\n",
    "* [8] Curriculum Learning - http://videolectures.net/icml09_bengio_cl/"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}