DeepLearning-02-Neural-Networks-Backpropagation.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Neural Networks - Backpropagation<a id=\"Top\"></a>\n",
    "\n",
    "<div class=\"alert alert-block alert-info\" style=\"margin-top: 20px\">\n",
    "\n",
    "<font size = 3>\n",
    "Table of Content\n",
    "<ul>\n",
    "<li>1. Multi-Layer Perceptron and backpropagation, a very short review</li>\n",
    "<li>2. <a href=\"#Part_2\">Forward-Mode Autodiff</a></li>\n",
    "<li>3. <a href=\"#Part_3\">Reversed-Mode Autodiff</a></li>\n",
    "<li>4. <a href=\"#Part_4\">Backpropagation, a simplified derivation</a></li>\n",
    "</font>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Multi-Layer Perceptron (MLP) and backpropagation, a very short review\n",
    "\n",
    "An MLP is composed of one input layer, one or more layers of LTUs called hidden layers, and one final layer of LTUs called the output layer. The following figure is an example.\n",
    "\n",
    "<img src=\"./images/fig_MLP.png\" width='500'>\n",
    "\n",
    "A key to the success of neural networks is the development of backpropagation technique. Here is a breakdown of the algorithm\n",
    "\n",
    "For each training instance $x$:\n",
    "\n",
    "- Forward pass: Feed $x$ to the network and computes the outputs of every neuron in each layer.\n",
    "- Measure the network's output error by comparing the desired output and actual output.\n",
    "- Computes how much each neuron in the last hidden layer contributed to each output neuron's error.\n",
    "- Estimates how much of these error contributions came from the previous layer.\n",
    "- Keep doing the same backward error estimation until the algorithm reaches the input layer.\n",
    "- The last step: apply Gradient Descent on all connection weights using the error gradients measured previously. So the weights get adjusted in order to redue the error.\n",
    "\n",
    "The reverse pass efficiently measures the error gradient across all the connection weights by __propagating the error gradient backward__ in the network. In essence, the backpropagation could be described as __gradient descent using reverse-mode autodiff.__ The algorithm boils down to evaluating differentiations across the network. How is this differentiaton done in TensorFlow in an efficient and accurate way?\n",
    "\n",
    "The simplest solution is to compute the differentiation using the definition\n",
    "\n",
    "$$ f'(x_0) = \\lim_{x\\rightarrow x_0}\\frac{f(x) - f(x_0)}{x-x_0} $$\n",
    "\n",
    "So suppose we'd like to know $f'(x)$ at $x=3$, we can simply compute the difference $f(3+\\epsilon)-f(3)$ divided by $\\epsilon$ where $\\epsilon$ is a small number. While this method is simple and straightforward, the result is not precise (depending on $\\epsilon$) and the accuracy gets worse as the function gets more complex. Fortunately, forward-mode autodiff comes to the rescue."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Forward-Mode Autodiff<a id=\"Part_2\"></a>\n",
    "<a href=\"#Top\">Back to page top</a>\n",
    "\n",
    "Forward-mode autodiff is neither numerical differentiation nor symbolic differentiation. In some sense, it is a mxture of the two. This method is based on two very simple ideas: __dual numbers__ and __Taylor expansion__.\n",
    "  \n",
    "1. __Dual numbers__: They are real number of the form $a+b\\epsilon$, where $a$, $b$, and $\\epsilon$ are all real numbers.\n",
    "In particular, $\\epsilon$ is an infinitesimal number such that it satisfies $\\epsilon^2=0$ within numerical\n",
    "accuracy.\n",
    "  \n",
    "2. __Taylor expansion__: For any real differentiable function $f(z)$, we can expan the it around $z=z_0$:\n",
    "\n",
    "  $$ f(z) = f(z_0) + f'(z_0)(z-z_0) + \\frac{1}{2!}f''(z_0)(z-z_0)^2 + \\frac{1}{3!}f'''(z_0)(z-z_0)^3 + \\ldots$$\n",
    "  \n",
    "By putting these two concepts together, we can get compute the derivative of an arbitrary function with high accuracy. To see this, let's say we'd like to compute the derivative of a function $f(z_0)$ at $z_0=a$: $f'(a)$. Now let $z = a+\\epsilon$ where $\\epsilon$ is a dual number, then Taylor expansion formula gives\n",
    "  \n",
    "$$ f(a+\\epsilon) = f(a) + f'(a)\\,\\epsilon$$\n",
    "  \n",
    "Higher order terms in the expansion vanish automatically because $\\epsilon^2=0$. Next we evaluate the function on the left hand side $f(a+\\epsilon)$, keeping in mind that terms of $\\epsilon^n$ can be discarded safely for $n\\geq 2$. For the identy to hold, the coefficient of the $\\epsilon$ terms on both sides must be equal. So by looking at the coefficient of the $\\epsilon$ term on the left hand side, we get the value of $f'(a)$. \n",
    "\n",
    "The downside of the forward-mode autodiff method is that for a function with $k$ variables, the number of calculations required to get $f'(z_i)$ for $\\forall\\, i \\in (1, \\ldots, k)$ is proportional to $k$. So the computational cost could be expansion for training sets with a huge number of features.\n",
    "  \n",
    "Now let's look at an example. Suppose we are given a function\n",
    "  \n",
    "$$f(x, y) = x^2y+y+2,$$\n",
    "  \n",
    "and we would like to compute its partial derivative $\\partial f/\\partial x$ evaluated a $(x,y)=(3,4)$. Based on the\n",
    "rule we just discussed, we can proceed as follows\n",
    "  \n",
    "  $$ f(3+\\epsilon, 4) = 4(3+\\epsilon)^2 + 4 + 2 = 42+24\\epsilon,$$\n",
    " \n",
    "  which can be summarized y the following graph. Therefore we immediately have $\\partial f/\\partial x|_{(3,4)} = 24$. \n",
    "  \n",
    "  <img src=\"./images/fig_Forward_Autodiff.png\" width='400'>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Reverse-Mode Autodiff<a id=\"Part_3\"></a>\n",
    "<a href=\"#Top\">Back to page top</a>\n",
    "\n",
    "The reverse-mode autodiff is implemented in TensorFlow. The algorithm is based on the __chain rule__. It first works the graph in the forward direction. In the this pass, it computes the value of every node (labeled by $n_1\\sim n_7$ in the following figure) of the graph. In the second pass, the method computes all the partial derivatives using chain rule. Let's use an example to demonstrate the idea.\n",
    "\n",
    "Here again we have the function $f(x,y)=x^2y+y+2$. Its computation can be represented using the following graph\n",
    "\n",
    "<img src=\"./images/fig_Reverse_Autodiff.png\" width='600'>\n",
    "\n",
    "In this graph we have three input nodes $n_1=x$, $n_2=y$, and $n_3=2$. The functional dependency between the rest of the nodes are\n",
    "$$\n",
    "  \\begin{align}\n",
    "    n_4 &= n_1 \\times n_1,\\\\\n",
    "    n_5 &= n_4 \\times n_2,\\\\  \n",
    "    n_6 &= n_2 + n_3,\\\\    \n",
    "    n_7 &= n_5 + n_6.\n",
    "  \\end{align}\n",
    "$$\n",
    "  \n",
    "These relations enable us to work out the desired derivaties. For example, $n_7$ is an output \n",
    "node that simply gives the node's value: $f = n_7$. Therefore \n",
    "  \n",
    "$$\\frac{\\partial f}{\\partial n_7}=1.$$\n",
    "  \n",
    "Moving on to the next level, we could compute the derivative with respect to $n_6$ and $n_5$:\n",
    "\n",
    "$$\n",
    "  \\begin{align}\n",
    "      \\frac{\\partial f}{\\partial n_6} &= \\frac{\\partial f}{\\partial n_7}\\frac{\\partial n_7}{\\partial n_6} \n",
    "                                       = 1 \\times 1 = 1,\\\\\n",
    "      \\frac{\\partial f}{\\partial n_5} &= \\frac{\\partial f}{\\partial n_7}\\frac{\\partial n_7}{\\partial n_5} \n",
    "                                       = 1 \\times 1 = 1.\n",
    "  \\end{align}\n",
    "$$\n",
    "  \n",
    "Similarly, we have:\n",
    "\n",
    "$$\n",
    "  \\begin{align}\n",
    "      \\frac{\\partial f}{\\partial n_4} &= \\frac{\\partial f}{\\partial n_5}\\frac{\\partial n_5}{\\partial n_4} \n",
    "                                       = 1 \\times n_2 = 4, \\\\\n",
    "      \\frac{\\partial f}{\\partial n_3} &= \\frac{\\partial f}{\\partial n_6}\\frac{\\partial n_6}{\\partial n_3} \n",
    "                                       = 1 \\times 0 = 0, \\\\                                   \n",
    "      \\frac{\\partial f}{\\partial n_2} &= \\frac{\\partial f}{\\partial n_6}\\frac{\\partial n_6}{\\partial n_2} +\n",
    "                                         \\frac{\\partial f}{\\partial n_5}\\frac{\\partial n_5}{\\partial n_2}\n",
    "                                       = 1 \\times 1 + 1\\times n_4 = 10, \\\\\n",
    "      \\frac{\\partial f}{\\partial n_1} &= \\frac{\\partial f}{\\partial n_4}\\frac{\\partial n_4}{\\partial n_1} \n",
    "                                       = 4 \\times 2n_1 = 24.\n",
    "  \\end{align}\n",
    "$$\n",
    "\n",
    "We can see that by the time we reach the input nodes $n_1=x$ and $n_2=y$, all the necessary partial\n",
    "derivatives have been computed. As a result, we can immediately obtain \n",
    "$\\partial f/\\partial x|_{(3,4)} = 24$ and $\\partial f/\\partial y|_{(3,4)} = 10$.\n",
    "  \n",
    "\n",
    "The reverse-mode autodiff is powerful in that it only needs one pass for an arbitrary number of inputs.\n",
    "As a result, the ${\\cal O}(n_{outputs}+1)$ computational cost is much less than the forward-mode autodiff\n",
    "${\\cal O}(n_{inputs})$ for a dataset that have a huge number of input features (here $n_{inputs}$ and \n",
    "$n_{outputs}$ are the number of inputs and outputs of the graph).\n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Backpropagation, a simplified derivation<a id=\"Part_4\"></a>\n",
    "<a href=\"#Top\">Back to page top</a>\n",
    "\n",
    "Now it is time to describe the idea of backpropagation. We will use the following neural network structure as \n",
    "an example.\n",
    "\n",
    "<img src=\"./images/fig_backpropagation.png\" width='550'>\n",
    "\n",
    "The network consists of an input layer with $K$ neurons $x_1,\\ldots, x_K$, an output layer with $M$ neurons \n",
    "$y_1,\\ldots, y_M$. The hidden layer has $N$ neurons $h_1,\\ldots, h_N$. The weights between input-hidden and\n",
    "hidden-output layers are characterized collectively by $\\{w_{ki}\\}$ and $\\{w'_{ij}\\}$. The activation function\n",
    "$\\varphi(z)$ is smooth and differentiable. As described above, there are several options. Here we use the logistic\n",
    "function\n",
    "\n",
    "$$ \\varphi(z) = \\frac{1}{1+e^{-z}}, $$\n",
    "\n",
    "whose first derivative has a nice form\n",
    "\n",
    "$$ \\varphi'(z) = \\varphi(z)\\left( 1-\\varphi(z) \\right). $$\n",
    "\n",
    "An output neuron, say, $y_j$, takes $h_1$, $h_2$, $\\ldots$, $h_N$ from the hidden layer and form\n",
    "a weighted sum\n",
    "\n",
    "$$u'_j = \\displaystyle\\sum_{i=1}^N w'_{ij}\\,h_i.$$\n",
    "\n",
    "$u'_j$ is then fed to the activation function in order to decide the output $y_j$:\n",
    "\n",
    "$$ y_j = \\varphi(u'_j).$$\n",
    "\n",
    "The same procedure applies to other layer outputs.\n",
    "\n",
    "The purpose of network training is to find a set of weights $\\{w_{ki}\\}$ and $\\{w'_{ij}\\}$ so that for a given\n",
    "set of training instances, the output error $E$ can be as low as possible. A typical mearure of $E$ is the mean\n",
    "squared error\n",
    "\n",
    "$$ E = \\frac{1}{2M}\\sum_{j=1}^M\\,\\left( y_j - t_j \\right)^2, $$\n",
    "\n",
    "where $t_j$ is the target output of the $j$-th output neuron. If one plots $E$ as a function of $y_j$ and $t_j$,\n",
    "the result will be a paraboloid, which has a global minimum. In this sense, deep learning (or in general, machine\n",
    "learning) at the very heart is an optimization (minimization) problem. The most common method for searching\n",
    "the minimum is gradient descent. For this purpose, we need to compute gradients of $E$ with respect to all the\n",
    "weights. This is when the idea of backpropagation comes into play.\n",
    "\n",
    "Let's begin with the output layer and compute the drivative of $E$ with respect to $w'_{ij}$. Recall that $E$ is\n",
    "a function of $y_j$ which in turn depends on $w'_{ij}$ and $h_i$ through the activation function. Therefore\n",
    "\n",
    "$$ \n",
    "   \\frac{\\partial E}{\\partial w'_{ij}} = \\frac{\\partial E}{\\partial y_j}\\,\n",
    "                                         \\frac{\\partial y_j}{\\partial u'_j}\\,\n",
    "                                         \\frac{\\partial u'_j}{\\partial w'_{ij}}. \n",
    "$$\n",
    "\n",
    "Recall that $y_j = \\varphi(u'_j)$ and that $u'_j$ is just a weighted sum of $h_i$, we have\n",
    "\n",
    "$$\n",
    "   \\frac{\\partial E}{\\partial w'_{ij}} = \\frac{\\partial E}{\\partial y_j}\\cdot\n",
    "                                        y_j\\cdot(1-y_j)\\cdot h_i.\n",
    "$$\n",
    "\n",
    "With this gradient, the weight $w'_{ij}$ is updated as\n",
    "\n",
    "$$ w'^{,new}_{ij} = w'^{,old}_{ij} - \\eta \\cdot \\frac{\\partial E}{\\partial y_j}\\cdot\n",
    "                                        y_j\\cdot(1-y_j)\\cdot h_i. $$\n",
    "\n",
    "Now to compute the derivative with respect to the weights that couple the input and hidden layers, we proceed\n",
    "as follow.\n",
    "\n",
    "$$\n",
    "  \\frac{\\partial E}{\\partial w_{ki}} = \\sum_{j=1}^M\\,\n",
    "                                         \\left( \\frac{\\partial E}{\\partial y_j}\\,\n",
    "                                         \\frac{\\partial y_j}{\\partial u'_j}\\,\n",
    "                                         \\frac{\\partial u'_j}{\\partial h_i}\\right)\\,\n",
    "                                         \\frac{\\partial h_i}{\\partial u_i}\\,\n",
    "                                         \\frac{\\partial u_i}{\\partial w'_{ij}}.\n",
    "$$\n",
    "\n",
    "The summation is required in order to take into account the fact that the hidden unit that $w_{ki}$ connects to is\n",
    "itself connected to every output unit. Using the definition of $u'_j$ and $u_i$, we arrive at the following equation\n",
    "\n",
    "$$\n",
    "\\frac{\\partial E}{\\partial w_{ki}} = \\sum_{j=1}^M\\,\n",
    "                                         \\left(\\frac{\\partial E}{\\partial y_j}\\cdot\n",
    "                                         y_j \\cdot (1-y_j)\\cdot w'_{ij} \\right)\\cdot\n",
    "                                         h_i\\cdot (1-h_i) \\cdot x_k.\n",
    "$$\n",
    "\n",
    "With the gradient vector in hand, we can update the weight $w_{ki}$ accordingly\n",
    "\n",
    "$$ w^{new}_{ki} = w_{ki}^{old} - \\eta\\cdot \\sum_{j=1}^M\\,\n",
    "                                         \\left(\\frac{\\partial E}{\\partial y_j}\\cdot\n",
    "                                         y_j \\cdot (1-y_j)\\cdot w'_{ij} \\right)\\cdot\n",
    "                                         h_i\\cdot (1-h_i) \\cdot x_k.\n",
    "$$\n",
    "\n",
    "The same procedure is repeated if there are more than one hidden layers until the input layer is reached.\n",
    "Because the error gets propagated in reversed direction, from output all the way to input neurons, the \n",
    "algorithm is hence called backpropagation. This, in essense, is the reverse-mode autodiff we just saw\n",
    "in the earlier discussion. In that example, the computation of $\\partial f/\\partial n_2$ needs to take\n",
    "into account the contribution from both nodes $n_5$ and $n_6$."
   ]
  },
  {
   "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.6.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}