GradientFlow.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "nLytHilIDc-y"
   },
   "source": [
    "## Introduction \n",
    "\n",
    " Real valued functions with real inputs are defined as $f: \\mathbb{R} \\to \\mathbb{R}$. So the mapping is from the real numbers to the real numbers. Most of the famous functions follow this rule. For instance $\\sin, \\cos, \\log, \\exp$ . The derivatives with respect to these functions is well-known in all calculus books. \n",
    "\n",
    "$$\\begin{array}{|c|c|}  \n",
    "\\hline\n",
    " \\textbf{$f(x)$} & \\textbf{$f'(x)$} \\\\\n",
    " \\hline\n",
    " \\sin(x) & \\cos(x)\\\\  \n",
    " \\cos(x) & - \\sin(x)\\\\\n",
    " \\log(x) & \\frac{1}{x}\\\\\n",
    "  e^x & e^x\\\\\n",
    "  \\hline\n",
    "\\end{array}$$\n",
    "\n",
    "In calculus the derivative with respect to $x$ is evaluated using this limit \n",
    "\n",
    "$$ f(x_0) = \\lim_{x \\to x_0} \\frac{f(x) - f(x_0)}{x - x_0}$$\n",
    "\n",
    "Geometrically the derivative at a point approximates the slope of the tangent line at that point\n",
    "\n",
    "<center> <img src=\"https://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Tangent-calculus.svg/250px-Tangent-calculus.svg.png\"/> </center>\n",
    "\n",
    "The slope of a function is a representation of how fast the function accelerates/decelerates at a certain point $x$. If the derivative/slope at a certain point is positive then the function is increasing, if it is negative then the function is decreasing and if it is zero then the function is constant. \n",
    "\n",
    "This concept is very important in function **optimization**.  *Usually*, we want to find the point where the function achieves its minimum. We can set $f'(x) = 0 $ and find the zeros of such function. We can check the neighborhood of each root to decide if the function is a local minimum or maximum. The minimum of all local minma  is called a global minimum. \n",
    "\n",
    "<center> <img src=\"https://media1.shmoop.com/images/calculus/calc_hghderiv_locglob_narr_graphik_1.png\"/> </center>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "3sKWblDsKdi5"
   },
   "source": [
    "**Problems** \n",
    "\n",
    "\n",
    "1.   The derivative can be undefined for instance $|x|$ has no derivative at $x = 0$ because the limit from the left and the right are not equal \n",
    "$$f'(0^+) = \\lim_{x \\to 0 ^+} \\frac{- x - 0 }{x - 0} = -1 \\neq f'(0^-) = \\lim_{x \\to 0^-} \\frac{x - 0}{x - 0} = 1$$\n",
    "2.   The point could be a suddle point where the neighborhood of the function could be increasing  from the left and decreasing from the right or vice virsa.  For instance, the function $x^3$ has a saddle point at $x = 0 $. \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "DR3Lexe1JVgo"
   },
   "source": [
    "## Derivative Evaluation Algorithms\n",
    " There are bascially three approaches to implement gradients in computers \n",
    "\n",
    "1.   **Numerical Differentiation**, which basically uses the finite difference rule for small $h$\n",
    "$$f'(x) \\approx \\frac{f(x+h)-f(x)}{h}$$ This formula suffers for numerical instability for small values of $h$.\n",
    "2.   **Symbolic Differentiation**, this calculates a symbolic expression for the derivative of the function. This approach is bascially used in matlab and mathematica.  This approach is quite slow and requires symbols parsing and manipulation. \n",
    "\n",
    "3. **Automatic Differentiation**, this approach is the base that is used in most deep learning libraries like TensorFlow and Pytorch. Basically, the mathematical expressions are divided into primitve blocks and the derivative is evaluated using the chain rule. \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Txp2Po0JU_9_"
   },
   "source": [
    "## Automatic Differentiation\n",
    "\n",
    "Mainly, there are two main parts for automatic differentiation  \n",
    "\n",
    "*   **Forward-mode automatic differentiation**  Evaluates the gradient in a froward manner for all the input variables. \n",
    "\n",
    "*   **Reverse-mode automatic differentiation**  Evaluates the gradient with respect to the ouput first then back-probogate the gradient to the input. \n",
    "\n",
    "In most machine learning libraries the reverse-mode is mostly used because the forward mode is more expensive in terms of evaluating the gradient with respect to many inputs. For instance, Tensorflow uses reverse-mode differentiation as explained in this [post](https://www.tensorflow.org/tutorials/eager/automatic_differentiation). \n",
    "\n",
    "### Computation Graph\n",
    "\n",
    "Machine learning libraries like Tensorflow build computational graphs where each node represents a simple computation function. This makes reverse-mode differentiation very easy to compute as we back-progbogate the gradieht from the outputs to the inputs. \n",
    "\n",
    "<center> <img src=\"https://www.easy-tensorflow.com/files/1_1.gif\"/> </center>\n",
    "\n",
    "Basically, TensorFlow defines the primitive functions which are the functions that cannot be reduced further. This includes $x^n, e^x, \\sin(x), \\log(x), \\frac{1}{x}\\cdots$. We assume that any other function is a composition of these functions. The composition function is defined as \n",
    "\n",
    "$$g(x) = f_1 \\circ f_2 \\circ \\cdots f_n(x) = f_1(f_2(\\cdots f_n(x)))$$\n",
    "\n",
    "Note that the evaluation of the primitives start from the inner function to the outer function.  In addition, the derivaitve of each of these operations are already defined inside TensorFlow. After that TensorFlow uses the chain rule which states that the derivative of $g(x) = f_1 \\circ f_2 \\cdots \\circ f_n(x)$ is \n",
    "\n",
    "$$g'(x_0) = \\frac{df_n(x_0)}{dx} \\times \\frac{df_{n-1}(f_n(x_0))}{dx} \\times \\cdots \\times \\frac{df_1(f_2(\\cdots(f_n(x_0)))}{dx}$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "oDd62xqvL_kM"
   },
   "source": [
    "First we import the necessary libraries "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "tr1NmrQhXjb2"
   },
   "outputs": [],
   "source": [
    "import tensorflow as tf\n",
    "import tensorflow.contrib.eager as tfe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "CK9uqaV0MCOu"
   },
   "source": [
    "We will use eager execution to evaluate the operations directly "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "jmbndYZYXmrR"
   },
   "outputs": [],
   "source": [
    "tf.enable_eager_execution()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "4wQYnPBCu8yP"
   },
   "source": [
    "### Real-Valued Functions\n",
    "\n",
    "Here we look at the functions of the form $f: \\mathbb{R} \\to \\mathbb{R}$. So the input is a real number and the output is a real number.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "VSYSycSKMG2z"
   },
   "source": [
    "**Example**  \n",
    "Let us evaluate the gradient of a simple function $f(x) = x^2$. In mathematics we evaluate the gradient using the limit of the difference\n",
    "\n",
    "$$ f'(x) = \\lim_{h \\to 0} \\frac{(x+h)^2 - x^2}{h} = \\lim_{h \\to 0} \\frac{x^2 + 2hx + h^ 2 - x^ 2}{h} = \\lim_{h \\to 0} \\frac{h(2x + h)}{h} = 2x  $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "zN18WUvjXqvN"
   },
   "outputs": [],
   "source": [
    "#define the function to differentiate\n",
    "def f(x):\n",
    "  return x**2\n",
    "\n",
    "#evaluate the gradient as a yet-to-be evaluated function\n",
    "g = tfe.gradients_function(f)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "jepfaZYQMTMS"
   },
   "source": [
    "Evaluate the derivative of the function at $x = 5.0$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "QuuXuyY7X-xr",
    "outputId": "026eefc4-b0d5-4539-bb13-d925eb24236e"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10.0"
      ]
     },
     "execution_count": 12,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = tf.Variable(5.)\n",
    "\n",
    "g(x)[0].numpy()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "1RzK4zPXTFan"
   },
   "source": [
    "**Example**\n",
    "\n",
    "Suppose that we want to evaluate the gradient of the sigmoid function. \n",
    "\n",
    "$$ \\sigma (x) = \\frac{1}{1+e^{-x}} $$\n",
    "\n",
    "We can easily proof using calculus that \n",
    "\n",
    "$$\\sigma'(x) = \\sigma(x) (1-\\sigma(x))$$\n",
    "\n",
    "But, we will go the long way! We first decompose it into the primitives\n",
    "\n",
    "$$ \\sigma (x) = \\frac{1}{1+e^{-x}} = f_1 \\circ f_2 \\circ f_3\\circ f_4(x)$$\n",
    "\n",
    "where we have $f_1 = 1/ x, f_2 = 1+x , f_3 = e^{x}, f_4 = -1 \\cdot x$. \n",
    "\n",
    "Then TensorFlow will construct the following graph of these primitives. \n",
    "\n",
    "![alt text](https://www.researchgate.net/profile/Igor_Macedo_Quintanilha/publication/325694563/figure/fig3/AS:636339552784386@1528726580172/Computational-graph-of-sigmoid-The-values-in-black-red-on-the-top-bottom-of-the-arrows.png)\n",
    "\n",
    "\n",
    "Now we can evaluate the forward pass by composition and the backward pass by chain rule according to the following table where we evaluate $\\sigma'(1)$\n",
    "$$\\begin{array}{|c|c|}  \n",
    "\\hline\n",
    " \\textbf{Forward} & \\textbf{Backward} \\\\\n",
    " \\hline\n",
    " f_4(1) = -1 & f'_1(f_2(f_3(f_4(1)))) =-0.534 \\\\  \n",
    " f_3(f_4(1)) = 0.368 & f'_2(f_3(f_4(1))) =  1\\\\\n",
    " f_2(f_3(f_4(1))) = 1.368  & f'_3(f_4(1)) = 0.368\\\\\n",
    " f_1(f_2(f_3(f_4(1)))) = 0.731 & f'_4(1) = -1\\\\\n",
    "  \\hline\n",
    "\\end{array}$$\n",
    "\n",
    "From the table we see that \n",
    "\n",
    "$$\\sigma'(1) \\approx -0.534 \\times 1 \\times 0.368 \\times 1 = 0.19664$$\n",
    "\n",
    "Now let us evaluate the derivative using TensorFlow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "6koBsFy1WIsE"
   },
   "outputs": [],
   "source": [
    "def sigmoid(x):\n",
    "  return 1/(1+tf.exp(-x))\n",
    "\n",
    "g = tfe.gradients_function(sigmoid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "fQrKT9kjWTBi",
    "outputId": "40e41b33-ad48-4faa-f61a-95409797ef79"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.19661194"
      ]
     },
     "execution_count": 14,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g(1.)[0].numpy()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "2zS7yGofIovU"
   },
   "source": [
    "## Shape Input Convention \n",
    "Most machine learning libraries force the gradient to have the same dimension as the input to update the parameters. Conventionally, this might contradict with the basic rules of the matrix calculus. In a calculus form  given $x \\in \\mathbb{R}^{n_1 \\cdots n_k}$ and suppose that $f(x) = y$ where $y \\in \\mathbb{R}$ then $f'(x) = w$ then we enforce that $w \\in  \\mathbb{R}^{n_1 \\cdots n_k}$. \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "AtxvntayY1zj"
   },
   "source": [
    "## High Dimension Gradient\n",
    "\n",
    "### Gradient of vectors \n",
    "\n",
    "In mathematics we usually use the gradient term to generalize the derivative to higher dimensions. Mainly we define a real valued function with vector inputs as \n",
    "\n",
    "$$f: \\mathbb{R}^n \\to \\mathbb{R} $$\n",
    "\n",
    "Hence we could say $y = f(x)$ where $x = (x_1, x_2, \\cdots, x_n)$ and $y \\in \\mathbb{R}$. Then we can define the derivative as \n",
    "\n",
    "$$\\nabla f(x) = \\left( \\frac{ \\partial y}{\\partial x_1}, \\frac{\\partial y}{\\partial x_2}, \\cdots, \\frac{\\partial y}{\\partial x_n}\\right)$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "zaEBuV77xo9C"
   },
   "source": [
    "**Example**\n",
    "\n",
    "The norm of a function operates on vectors \n",
    "\n",
    "$$\\Vert x \\Vert = \\sqrt{\\sum_{i=1}^n x^2_i}$$\n",
    "\n",
    "So this function sums the squares of the components and takes the root. What is the gradient of the squared norm $f(x) = \\Vert x \\Vert ^2$ ? \n",
    "\n",
    "\n",
    "$$\\frac{\\partial f}{\\partial x_1} = 2x_1, \\frac{\\partial f}{\\partial x_2} = 2x_2, \\cdots , \\frac{\\partial f}{\\partial x_n} = 2x_n$$\n",
    "\n",
    "In a simpler format we have \n",
    "\n",
    "$$\\nabla f = (2x_1, \\cdots 2 x_n ) = 2 x $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "MDxOdbOeCqZt"
   },
   "outputs": [],
   "source": [
    "#create a variale with three components \n",
    "x = tf.Variable([1., 2. , 3.])\n",
    "\n",
    "#define the norm \n",
    "def norm(x):\n",
    "  return tf.reduce_sum(tf.square(x))\n",
    "\n",
    "#evaluate the gradient\n",
    "g = tfe.gradients_function(norm)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "L71YecDVDLvT",
    "outputId": "589223d9-1d88-4f2c-dbc6-568ec82f1111"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([2., 4., 6.], dtype=float32)"
      ]
     },
     "execution_count": 16,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g(x)[0].numpy()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "KJaqZXMUz2EZ"
   },
   "source": [
    "We can compute the second derivative in a similar approach"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "oeuf_grPZOwj"
   },
   "outputs": [],
   "source": [
    "#create a variale with three components \n",
    "x = tf.Variable([[1.], [2.], [3.]])\n",
    "\n",
    "#define the operation \n",
    "def op(x):\n",
    "  return tf.square(x)\n",
    "\n",
    "dx = tfe.gradients_function\n",
    "\n",
    "#compute the second order derivative\n",
    "g = dx(dx(op))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 68
    },
    "colab_type": "code",
    "id": "SxtANKE752WV",
    "outputId": "07ae5548-5692-4ca3-8d3e-5c0c17bb43c4"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[2.],\n",
       "       [2.],\n",
       "       [2.]], dtype=float32)"
      ]
     },
     "execution_count": 18,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g(x)[0].numpy()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "rU1hE2vJa944"
   },
   "source": [
    "We can also compute the gradient of functions with two variables"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "mAdhmGTlZTtA"
   },
   "outputs": [],
   "source": [
    "#create a variale with three components \n",
    "x = tf.Variable([[1.], [2.], [3.]])\n",
    "y = tf.Variable([[2.], [4.], [6.]])\n",
    "\n",
    "#define the operation \n",
    "def op(x, y):\n",
    "  return x + y \n",
    "\n",
    "g = tfe.gradients_function(op)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 153
    },
    "colab_type": "code",
    "id": "NaPeOHcsa4bf",
    "outputId": "7464e1b6-0b0a-43ee-ef74-9951eb35316b"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<tf.Tensor: id=190, shape=(3, 1), dtype=float32, numpy=\n",
       " array([[1.],\n",
       "        [1.],\n",
       "        [1.]], dtype=float32)>,\n",
       " <tf.Tensor: id=190, shape=(3, 1), dtype=float32, numpy=\n",
       " array([[1.],\n",
       "        [1.],\n",
       "        [1.]], dtype=float32)>]"
      ]
     },
     "execution_count": 20,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g(x, y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "JkzTLwl7OhuE"
   },
   "source": [
    "## The gradient of a matrix\n",
    "\n",
    " Mainly we define a real valued function with matrix inputs as \n",
    "\n",
    "$$f: \\mathbb{R}^{n \\times m} \\to \\mathbb{R} $$\n",
    "\n",
    "where we define $n$ as the number of rows and $m$ as the number of columns. We usually prefer to work with square matrices because of their nice properties. However, this approach should generalize easily to rectangular matrices \n",
    "\n",
    "**Example**\n",
    "\n",
    "Let us define the [frobenious norm](http://mathworld.wolfram.com/FrobeniusNorm.html) for a given matix $A$\n",
    "\n",
    "$$\\Vert A \\Vert_F = \\sqrt{\\sum_{i=1}^n \\sum_{j=1}^m |a_{ij}|^2} $$\n",
    "\n",
    "To make things simpler we could rewrite $\\Vert A \\Vert_F  = a_{11}^2 + \\dots + a_{nm}^2$.  Using this format we can easily deduce that the gradient with respec to the matrix can be evaluated as \n",
    "\n",
    "$$\\frac{\\partial \\Vert A \\Vert_F}{\\partial a_{ij}} = 2 a_{ij}$$\n",
    "\n",
    "Or in simpler terms \n",
    "\n",
    "$$\\frac{\\partial \\Vert A \\Vert_F}{\\partial A} = 2 A$$\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "dSUYfad4RvOy"
   },
   "outputs": [],
   "source": [
    "#create a variale with three components \n",
    "A = tf.constant([[2., 3., 4.], [5., 6., 7.], [8., 9. , 10.]])\n",
    "\n",
    "#define the norm \n",
    "def frobenious_norm(A):\n",
    "  return tf.reduce_sum(tf.square(A))\n",
    "\n",
    "#evaluate the gradient\n",
    "g = tfe.gradients_function(frobenious_norm)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 68
    },
    "colab_type": "code",
    "id": "JRDHxQtGR_NQ",
    "outputId": "4d374028-3a00-458c-899f-5250aa61f774"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 4.,  6.,  8.],\n",
       "       [10., 12., 14.],\n",
       "       [16., 18., 20.]], dtype=float32)"
      ]
     },
     "execution_count": 22,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g(A)[0].numpy()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "SAOMg-5pTCIO"
   },
   "source": [
    "## Jaccobian Matrix\n",
    "\n",
    "The Jaccobian matrix is the first order derivatives of a vector valued function. Vector valued functions are defined as $f: \\mathbb{R}^n \\to \\mathbb{R}^m$.\n",
    "\n",
    "\n",
    "Given $x \\in \\mathbb{R}^n$ and $f_j : \\mathbb{R}^n \\to \\mathbb{R}$ we have\n",
    "\n",
    "$$f(x) = \\begin{bmatrix}\n",
    "    f_1(x) \\\\\n",
    "    f_2(x) \\\\\n",
    "    \\vdots \\\\\n",
    "    f_m(x)\n",
    "\\end{bmatrix}$$\n",
    " \n",
    " We could then define the jaccobian  as \n",
    " \n",
    " $$J(x) = \\begin{bmatrix}\n",
    "    \\frac{\\partial f_1}{\\partial x_1} & \\frac{\\partial f_1}{\\partial x_2}  & \\dots  & \\frac{\\partial f_1}{\\partial x_n} \\\\\n",
    "    \\frac{\\partial f_2}{\\partial x_1} & \\frac{\\partial f_2}{\\partial x_2}  & \\dots  & \\frac{\\partial f_2}{\\partial x_n}  \\\\\n",
    "    \\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
    "    \\frac{\\partial f_m}{\\partial x_1} & \\frac{\\partial f_m}{\\partial x_2}  & \\dots  & \\frac{\\partial f_m}{\\partial x_n} \n",
    "\\end{bmatrix} $$\n",
    " \n",
    "Hence each row represents the derivative of a real valued function with input vectors. Note that using shape convention we must reshape that to have the same output as the vector input. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "8bD7dtEMyuSI"
   },
   "source": [
    "**Example**\n",
    "\n",
    "define $x \\in \\mathbb{R}^n$ and $f: \\mathbb{R}^n \\to \\mathbb{R}^2$ where $f(x) = ( x_1 , x_2)$. It is always customary to write it in an expanded form\n",
    "\n",
    "$$f \\left( \\begin{bmatrix}\n",
    "    x_{1} \\\\\n",
    "    x_{2} \\\\\n",
    "    \\vdots \\\\\n",
    "    x_{n}\n",
    "\\end{bmatrix} \\right) = \\begin{bmatrix}\n",
    "     x_1 \\\\\n",
    "     x_2 \\\\\n",
    "\\end{bmatrix}$$\n",
    "\n",
    "The gradient can be evaluated as \n",
    "\n",
    "$$J \\left(x \\right) = \\begin{bmatrix}\n",
    "     \\frac{\\partial x_1}{\\partial x} \\\\\n",
    "     \\frac{\\partial x_2}{\\partial x} \\\\\n",
    "\\end{bmatrix} = \\begin{bmatrix}\n",
    "     1 & 0 & 0 & \\cdots & 0 \\\\\n",
    "    0 & 1 & 0 & \\cdots & 0  \\\\\n",
    "\\end{bmatrix}$$\n",
    "\n",
    "Since we must have the same shape as the input we sum the rows and pad zeros for the other variables\n",
    "\n",
    "$$J(x) = \\begin{bmatrix}\n",
    "   1 & 1 & 0 & \\cdots & 0 \n",
    "\\end{bmatrix}^ T$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "0O6_ZYzaWmJW"
   },
   "outputs": [],
   "source": [
    "#create a variale with three components \n",
    "x = tf.Variable([[1.], [2.], [3.]])\n",
    "\n",
    "#define the operation \n",
    "def slice(x):\n",
    "  return x[0:2]\n",
    "\n",
    "g = tfe.gradients_function(slice)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 68
    },
    "colab_type": "code",
    "id": "b2suoSGsXQWq",
    "outputId": "2fb4a6f4-66df-4811-e735-7d84b06894fe"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[1.],\n",
       "       [1.],\n",
       "       [0.]], dtype=float32)"
      ]
     },
     "execution_count": 24,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g(x)[0].numpy()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "YUIUaX1zRJpv"
   },
   "source": [
    "**Example**\n",
    "\n",
    "Let $A$ be an $m \\times n$ constant matrix and $x$ be $n\\times 1$ vector \n",
    "\n",
    "$$f(x) = A x $$\n",
    "\n",
    "In an expanded form this is like \n",
    "\n",
    "$$f(x) = \\begin{bmatrix}\n",
    "    a_{11} & a_{12} & a_{13} & \\dots  & a_{1n} \\\\\n",
    "    a_{21} & a_{22} & a_{23} & \\dots  & a_{2n} \\\\\n",
    "    \\vdots & \\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
    "    a_{m1} & a_{m2} & a_{m3} & \\dots & a_{mn}\n",
    "\\end{bmatrix} \\times \\begin{bmatrix}\n",
    "    x_{1} \\\\\n",
    "    x_{2} \\\\\n",
    "    \\vdots \\\\\n",
    "    x_{n}\n",
    "\\end{bmatrix}  = \\begin{bmatrix}\n",
    "    A_1 \\cdot x \\\\\n",
    "    A_2 \\cdot x \\\\\n",
    "    \\vdots \\\\\n",
    "    A_n \\cdot x\n",
    "\\end{bmatrix} $$\n",
    "\n",
    "Where $A_i$ is the ith row and $\\cdot$ is the dot product of vectors. If we fix the other variables and took the derivative with $x_1$ for instance then we see that the partial derivative is in terms of the column vector of the form $A^T_1$ which is the 1st column of the array. Since we have multiple values we just sum them togehter. Generally $$ \\frac{\\partial f}{\\partial x_i} = \\sum_{j=1}^m a_{ji}$$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "z4d_BEqvXam1"
   },
   "source": [
    "We see that the derivative with respect to each variable is just the sum of the corrosponding column vector in the matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "s55vrSL2UhDC"
   },
   "outputs": [],
   "source": [
    "#create a variale with three components \n",
    "x = tf.Variable([[1.], [2.], [3.]])\n",
    "\n",
    "#define the multiplication \n",
    "def op(y):\n",
    "  A = tf.constant([[2., 3., 4.], [5., 6., 7.], [8., 9. , 10.]])\n",
    "  return tf.matmul(A, y)\n",
    "\n",
    "#evaluate the gradient\n",
    "g = tfe.gradients_function(op)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 68
    },
    "colab_type": "code",
    "id": "gL4jIKzFbF2p",
    "outputId": "efaa74aa-42aa-4de9-d77c-394e2f5750ad"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[15.],\n",
       "       [18.],\n",
       "       [21.]], dtype=float32)"
      ]
     },
     "execution_count": 26,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g(x)[0].numpy()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "-VBSUGKyZQwr"
   },
   "source": [
    "### References\n",
    "http://www.columbia.edu/~ahd2125/post/2015/12/5/\n",
    "\n",
    "https://www.easy-tensorflow.com/tf-tutorials/basics/graph-and-session\n",
    "\n",
    "https://rufflewind.com/2016-12-30/reverse-mode-automatic-differentiation"
   ]
  }
 ],
 "metadata": {
  "accelerator": "GPU",
  "colab": {
   "name": "Copie de GradientFlow.ipynb",
   "provenance": [],
   "version": "0.3.2"
  },
  "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": 1
}