optimization/gradient-descent-and-backpropagation/gradient-descent-and-backpropagation.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Gradient Descent and Backpropagation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Idea\n",
    "\n",
    "### Gradient Descent\n",
    "\n",
    "Gradient descent is defined as a optimization algorithm, which is used to find the local min or max of a function. The algorithm consists of the basic steps of starting from a point on the graph of a function. From there find the direction in which the function decreases the fastes and go one small step into that direction.\n",
    "\n",
    "### Backpropagation\n",
    "\n",
    "Backpropagation is defined as a algorithm in order to propagation the total error of a function backward to all variables by calculation the gradient of each weight and bias to eventually minimize the total error of the function.\n",
    "\n",
    "![](./gradient-descent.png) - [Reference](https://medium.com/@divakar_239/stochastic-vs-batch-gradient-descent-8820568eada1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Concept\n",
    "\n",
    "The weights and biases get updated with a subtraction of the gradient of that weight times a learning rate $\\alpha$.\n",
    "\n",
    "\n",
    "$w:=w-\\alpha\\frac{\\theta J(w,b)}{\\theta w}$\n",
    "\n",
    "$b:=b-\\alpha\\frac{\\theta J(w,b)}{\\theta b}$\n",
    "\n",
    "### Chain Rule\n",
    "\n",
    "Define $F(x) = (f\\circ g)(x)$\n",
    "\n",
    "The deriative is $F'(x)=f'(g(x))g'(x)$\n",
    "\n",
    "If we have $y=f(u)$ and $g(x)$ then the deriative of $y$ is\n",
    "\n",
    "$\\frac{dy}{dx}=\\frac{dy}{du}\\frac{du}{dx}$\n",
    "\n",
    "#### Example\n",
    "\n",
    "![](computation-graph.jpg) - [Reference](https://www.tutorialspoint.com/python_deep_learning/python_deep_learning_computational_graphs.htm)\n",
    "\n",
    "Given $x=1, y=3, z=-3$\n",
    "\n",
    "**Forward**\n",
    "\n",
    "1. $p=x+y=1+3=4$\n",
    "2. $g=p*z=4*-3=12$\n",
    "\n",
    "**Backward**\n",
    "\n",
    "1. First compute the gradient from the output itself: $\\frac{\\partial g}{\\partial g}=1$\n",
    "2. $g=p*z$\n",
    "3. $\\frac{\\partial g}{\\partial p}=\\frac{\\partial g}{\\partial g}\\frac{\\partial g}{\\partial z}=1*z=-3$\n",
    "4. $\\frac{\\partial g}{\\partial z}=\\frac{\\partial g}{\\partial g}\\frac{\\partial g}{\\partial p}=1*p=4$\n",
    "5. $p=x+z$\n",
    "6. $\\frac{\\partial g}{\\partial x}=\\frac{\\partial g}{\\partial p}\\frac{\\partial p}{\\partial x}=-3$\n",
    "7. $\\frac{\\partial g}{\\partial y}=\\frac{\\partial g}{\\partial p}\\frac{\\partial p}{\\partial y}=-3$\n",
    "\n",
    "### Logistic Regression Backward Path\n",
    "\n",
    "Remember: $\\hat{y}= \\sigma(w^Tx+b)$ - [Logistic Regression](../linear-logistic-regression/linear-logistic-regression.ipynb)\n",
    "\n",
    "Given input x:\n",
    "\n",
    "1. $z = wx+b$\n",
    "2. $\\hat{y}=a=\\sigma(z)$\n",
    "3. $L(a,y) = -(y\\log{\\hat{y}}+(1-y)\\log{(1-\\hat{y})})$\n",
    "\n",
    "The task is to modify $w, b$ in order to reduce $L(a,y)$\n",
    "\n",
    "1. $da = \\frac{dL(a,y)}{da}$\n",
    "    1. $da = \\frac{-y}{a}+\\frac{1-y}{1-a}$ \n",
    "2. $dz = \\frac{dL(a,y)}{dz}$\n",
    "    1. $dz = \\frac{dL}{da}\\frac{da}{dz}$\n",
    "    2. $\\frac{da}{dz}=a(1-a)$\n",
    "    3. $da = \\frac{-y}{a}+\\frac{1-y}{1-a}$\n",
    "    4. $dz = a - y$\n",
    "3. $\\frac{\\delta L}{\\delta w}=dw=x*dz$\n",
    "4. $\\frac{\\delta L}{\\delta b}=db=dz$\n",
    "\n",
    "\n",
    "Finally (with vectorization and $m$ examples):\n",
    "\n",
    "$\\frac{\\theta J}{\\theta w} = \\frac{1}{m}X(A-Y)^T$\n",
    "\n",
    "$\\frac{\\theta J}{\\theta b} = \\frac{1}{m}\\sum^m_{i=1}(a^{(i)}-y^{(i)})$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# import libraries\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def logistic_backward(X, Y, A):\n",
    "    m = X.shape(1)\n",
    "    \n",
    "    dw = 1/m * np.dot(X, (A - Y).T)\n",
    "    db = 1/m * np.sum(A - Y)\n",
    "    \n",
    "    grads = {\"dw\": dw, \"db\": db}\n",
    "    return grads    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References\n",
    "\n",
    "1. [Gradient Descent and Backpropagation](https://www.linkedin.com/pulse/gradient-descent-backpropagation-ken-chen/)\n",
    "2. [Chain Rule - Wiki](https://en.wikipedia.org/wiki/Chain_rule)\n",
    "3. [Chain Rule - Lamar.edu](http://tutorial.math.lamar.edu/Classes/CalcI/ChainRule.aspx)"
   ]
  }
 ],
 "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.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}