NTM Familiarization.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Neural Turing Machine"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "All the logical Representations done in the paper (arXiv:1410.5401 [cs.NE]) understood during the first read through the paper"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Reading "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Memory matrix $M_t$ is of size NxM where N is the number of memory locations and M is the vector size at each location.\n",
    "\n",
    "For the weights emitted by the $\\verb|Read Head|$ for attention purposes, let it be defined by the vector $w_t$, which defines the weight over the N locations emitted by the $\\verb|Read Head|$ at time $t$.\n",
    "\n",
    "Note that these weights are normalised, thus, $w_t$ is should obey the following constraints.\n",
    "\n",
    "$\\sum_i w_t(i) = 1$ and $0 \\le w_t(i) \\le 1$,  $\\forall i$\n",
    "\n",
    "The output will be a size $M$ long vector $r_t$ which is a combination of the weights $w_t(i)$ and the row-vectors $M_t(i)$, as following:-\n",
    "\n",
    "$r_t = \\sum_i w_t(i) M_t(i)$\n",
    "\n",
    "this is just the dot product of $w_t$ with $M_t$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "N = 10\n",
    "M = 5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Initializing random Memory"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [],
   "source": [
    "memory_t = np.random.randn(N,M)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 1.02566554,  0.26984035,  2.32146663, -0.04645675, -0.74322073],\n",
       "       [-0.4219099 , -0.69259713,  1.26132611,  0.03370328,  1.00963184],\n",
       "       [ 0.49032976, -1.21833442,  0.99009593, -1.74248038,  1.10700821],\n",
       "       [-1.14657412, -0.38178142, -1.70991989, -0.37022442,  0.63975417],\n",
       "       [-0.16097788, -0.41253773, -2.31352148, -1.72432896,  1.87729238],\n",
       "       [ 0.50284768,  1.25865532,  1.44719464, -3.23064775, -0.38729273],\n",
       "       [ 0.44668247,  1.02202843,  0.40753485, -0.54830743, -3.25076998],\n",
       "       [-0.85941436, -0.20088155, -0.42805193, -0.04100567, -1.39025753],\n",
       "       [-0.32842488,  0.75626153, -1.09374307, -1.45523358, -1.99149845],\n",
       "       [ 0.48134513, -0.05964692, -0.22696669,  0.82176327,  0.9962702 ]])"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "memory_t"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Read Weight for this time step being Initialised Below"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "w_t = np.random.rand(1,N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [],
   "source": [
    "w_t = w_t/np.sum(w_t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0.12663217, 0.01609757, 0.13725025, 0.13981906, 0.00046411,\n",
       "        0.12766177, 0.16276443, 0.04685124, 0.15513073, 0.08732867]])"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "w_t"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$w_t$ is constraied accordingly now"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0000000000000002"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.sum(w_t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [],
   "source": [
    "r_t = np.dot(w_t, memory_t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Shape check for output $r_t$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r_t.shape == (1,M)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Writing "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are 3 objects in this module\n",
    "\n",
    "1. Weight vector $w_t$ emitted by $\\verb|Write Head|$ at time $t$\n",
    "2. Erase vector $e_t$ of length M, whose elements lie in the interval $(0,1)$\n",
    "3. Add vector $a_t$ of length M\n",
    "\n",
    "In the writing module, each write is decomposed in two steps *Erase & Add*\n",
    "\n",
    "*Erase Step*\n",
    "\n",
    " $\\hat M_t(i) = M_{t-1}(i)[\\mathbf{1} - w_t(i)e_t]$\n",
    " \n",
    " Here Mulitplication is Pointwise\n",
    " \n",
    "*Add Step*\n",
    "    \n",
    " $M_t(i) = \\hat M_t(i) + w_t(i)a_t$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [],
   "source": [
    "write_w_t = np.random.rand(N,1)\n",
    "e_t = np.random.rand(1,M)\n",
    "a_t = np.random.randn(1,M)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ERASE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "M_hat_t = memory_t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array([[0.67363339],\n",
       "        [0.84866616],\n",
       "        [0.0744187 ],\n",
       "        [0.86792403],\n",
       "        [0.00443963],\n",
       "        [0.93665241],\n",
       "        [0.87952246],\n",
       "        [0.52303087],\n",
       "        [0.17449281],\n",
       "        [0.18220917]]),\n",
       " array([[0.54679476, 0.17789317, 0.83328383, 0.95704984, 0.91626833]]))"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "write_w_t,e_t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [],
   "source": [
    "matrix = np.dot(write_w_t,e_t) #Each row of matrix will provide the corresponding row (ith)in the Erase Equation  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[3.68339207e-01, 1.19834781e-01, 5.61327809e-01, 6.44700724e-01,\n",
       "        6.17228937e-01],\n",
       "       [4.64046210e-01, 1.50971917e-01, 7.07179789e-01, 8.12215810e-01,\n",
       "        7.77605923e-01],\n",
       "       [4.06917551e-02, 1.32385787e-02, 6.20118991e-02, 7.12224044e-02,\n",
       "        6.81874975e-02],\n",
       "       [4.74576313e-01, 1.54397761e-01, 7.23227063e-01, 8.30646554e-01,\n",
       "        7.95251302e-01],\n",
       "       [2.42756589e-03, 7.89779696e-04, 3.69947108e-03, 4.24894623e-03,\n",
       "        4.06789146e-03],\n",
       "       [5.12156632e-01, 1.66624070e-01, 7.80497311e-01, 8.96423040e-01,\n",
       "        8.58224941e-01],\n",
       "       [4.80918272e-01, 1.56461041e-01, 7.32891844e-01, 8.41746826e-01,\n",
       "        8.05878573e-01],\n",
       "       [2.85990543e-01, 9.30436225e-02, 4.35833172e-01, 5.00566615e-01,\n",
       "        4.79236627e-01],\n",
       "       [9.54117533e-02, 3.10410794e-02, 1.45402036e-01, 1.66998314e-01,\n",
       "        1.59882234e-01],\n",
       "       [9.96310176e-02, 3.24137669e-02, 1.51831952e-01, 1.74383253e-01,\n",
       "        1.66952488e-01]])"
      ]
     },
     "execution_count": 95,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0.63166079, 0.88016522, 0.43867219, 0.35529928, 0.38277106],\n",
       "       [0.53595379, 0.84902808, 0.29282021, 0.18778419, 0.22239408],\n",
       "       [0.95930824, 0.98676142, 0.9379881 , 0.9287776 , 0.9318125 ],\n",
       "       [0.52542369, 0.84560224, 0.27677294, 0.16935345, 0.2047487 ],\n",
       "       [0.99757243, 0.99921022, 0.99630053, 0.99575105, 0.99593211],\n",
       "       [0.48784337, 0.83337593, 0.21950269, 0.10357696, 0.14177506],\n",
       "       [0.51908173, 0.84353896, 0.26710816, 0.15825317, 0.19412143],\n",
       "       [0.71400946, 0.90695638, 0.56416683, 0.49943338, 0.52076337],\n",
       "       [0.90458825, 0.96895892, 0.85459796, 0.83300169, 0.84011777],\n",
       "       [0.90036898, 0.96758623, 0.84816805, 0.82561675, 0.83304751]])"
      ]
     },
     "execution_count": 97,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "matrix = 1 - matrix\n",
    "matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(10, 5)"
      ]
     },
     "execution_count": 98,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "matrix.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [],
   "source": [
    "M_hat_t = np.multiply(memory_t,matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 104,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "M_hat_t.shape == (N,M)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ADD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {},
   "outputs": [],
   "source": [
    "matrix2 = np.dot(write_w_t,a_t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(10, 5)"
      ]
     },
     "execution_count": 106,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "matrix2.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(10, 5)"
      ]
     },
     "execution_count": 107,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "M_hat_t.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "metadata": {},
   "outputs": [],
   "source": [
    "M_t = (M_hat_t + matrix2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Final Output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 115,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "M_t.shape == (N,M)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Addressing Mechanism "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1. Focusing by Content"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Parameters:-\n",
    "\n",
    "1. $k_t$: Vector(M), Key Vector.\n",
    "2. $\\beta_t$: Scalar, Key Strength at time t.\n",
    "3. $K[.,.]$: Function, Similarity Measure.\n",
    "\n",
    "Equation:-\n",
    "\n",
    "$\\Large w_t^c(i) = \\frac{exp( \\beta_tK[\\mathbf{k}_t, \\mathbf{M}_t(i)] )}{\\sum_j exp(\\beta_tK[\\mathbf{k}_t, \\mathbf{M}_t(j)])} $\n",
    "\n",
    "For the similarity measure, the paper used cosine similarity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Cosine_similarity(u,v):\n",
    "    u,v = u.reshape(1,-1),v.reshape(-1,1)\n",
    "    return np.dot(u,v)/(np.linalg.norm(u)*np.linalg.norm(v))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Initializing Random Key vector and $\\beta_t$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 153,
   "metadata": {},
   "outputs": [],
   "source": [
    "k_t = np.random.randn(1,M)\n",
    "b_t = 1\n",
    "K = Cosine_similarity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 154,
   "metadata": {},
   "outputs": [],
   "source": [
    "K_on_each_row = np.apply_along_axis(K, 1, M_t,k_t).reshape(-1,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 155,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[-0.62821605],\n",
       "       [ 0.22539885],\n",
       "       [ 0.3690185 ],\n",
       "       [ 0.13202885],\n",
       "       [ 0.51681715],\n",
       "       [-0.24193407],\n",
       "       [-0.54663512],\n",
       "       [-0.36324891],\n",
       "       [-0.56025637],\n",
       "       [ 0.44502288]])"
      ]
     },
     "execution_count": 155,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "K_on_each_row"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 156,
   "metadata": {},
   "outputs": [],
   "source": [
    "w_ct = np.exp(b_t * K_on_each_row) / np.sum(b_t * np.exp(K_on_each_row))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 157,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0.05209612],\n",
       "       [0.12232792],\n",
       "       [0.14122085],\n",
       "       [0.11142317],\n",
       "       [0.16371443],\n",
       "       [0.07665941],\n",
       "       [0.05652434],\n",
       "       [0.06790146],\n",
       "       [0.05575963],\n",
       "       [0.15237268]])"
      ]
     },
     "execution_count": 157,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "w_ct"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 159,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 159,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "w_ct.shape == (N,1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. Focusing by Location"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\Large \\mathbf{w}_t^g = g_t\\mathbf{w}_t^c + (1 - g_t)\\mathbf{w}_{t-1}$\n",
    "\n",
    "Where $g_t$ is the scalar Interpolation Gate $\\in$ (0,1) and $w_{t-1}$ is the weght vector produced by the *head* in the previous time step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 161,
   "metadata": {},
   "outputs": [],
   "source": [
    "g_t = 1\n",
    "w_prev = np.random.rand(N,1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above variables initialised just for reference, as this notebook doesn't aims to implement TNM"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 162,
   "metadata": {},
   "outputs": [],
   "source": [
    "w_gt = g_t * w_ct + (1 - g_t) * w_prev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 164,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0.05209612],\n",
       "       [0.12232792],\n",
       "       [0.14122085],\n",
       "       [0.11142317],\n",
       "       [0.16371443],\n",
       "       [0.07665941],\n",
       "       [0.05652434],\n",
       "       [0.06790146],\n",
       "       [0.05575963],\n",
       "       [0.15237268]])"
      ]
     },
     "execution_count": 164,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "w_gt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "After Interpolation, each head emits a *shift weighting* $\\mathbf{s}_t$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "NOTE: **Defining Shift Locations/Range as just a random vector (for now)**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 165,
   "metadata": {},
   "outputs": [],
   "source": [
    "s_t = np.random.rand(1,N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 167,
   "metadata": {},
   "outputs": [],
   "source": [
    "s_t = s_t/np.sum(s_t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 170,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0.06053958, 0.10537119, 0.12345044, 0.04555618, 0.10079448,\n",
       "        0.13570933, 0.07399194, 0.13712262, 0.12233864, 0.09512561]])"
      ]
     },
     "execution_count": 170,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s_t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 187,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0.05209612],\n",
       "       [0.12232792],\n",
       "       [0.14122085],\n",
       "       [0.11142317],\n",
       "       [0.16371443],\n",
       "       [0.07665941],\n",
       "       [0.05652434],\n",
       "       [0.06790146],\n",
       "       [0.05575963],\n",
       "       [0.15237268]])"
      ]
     },
     "execution_count": 187,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "w_gt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 218,
   "metadata": {},
   "outputs": [],
   "source": [
    "w_hat_t = np.convolve(w_gt.reshape(-1), s_t.reshape(-1))[:N]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 219,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0.00315388, 0.01289511, 0.02787058, 0.03910086, 0.04990956,\n",
       "       0.06148034, 0.0714763 , 0.07357927, 0.08621996, 0.10353205])"
      ]
     },
     "execution_count": 219,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "w_hat_t"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Defining Sharpening Factor $\\gamma_t \\ge 1$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 220,
   "metadata": {},
   "outputs": [],
   "source": [
    "gamma_t = 1.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 221,
   "metadata": {},
   "outputs": [],
   "source": [
    "w_new_t = np.power(w_hat_t,gamma_t)/np.sum(np.power(w_hat_t,gamma_t))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 222,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0.00128238, 0.01060198, 0.03368747, 0.05597947, 0.08072816,\n",
       "       0.1103707 , 0.13835424, 0.1445049 , 0.18329942, 0.24119128])"
      ]
     },
     "execution_count": 222,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "w_new_t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 226,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 226,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "w_new_t.shape == (N,)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}