6. Gradient Descent.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>\n",
       "\n",
       "div.cell { /* Tunes the space between cells */\n",
       "margin-top:1em;\n",
       "margin-bottom:1em;\n",
       "}\n",
       "\n",
       "div.text_cell_render h1 { /* Main titles bigger, centered */\n",
       "font-size: 2.2em;\n",
       "line-height:1.4em;\n",
       "text-align:center;\n",
       "}\n",
       "\n",
       "div.text_cell_render h2 { /*  Parts names nearer from text */\n",
       "margin-bottom: -0.4em;\n",
       "}\n",
       "\n",
       "\n",
       "div.text_cell_render { /* Customize text cells */\n",
       "font-family: 'Arial';\n",
       "font-size:1.5em;\n",
       "line-height:1.4em;\n",
       "padding-left:3em;\n",
       "padding-right:3em;\n",
       "}\n",
       "\n",
       ".MathJax {\n",
       "    font-size: 70%;\n",
       "}\n",
       "</style>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.display import HTML\n",
    "css_file = './custom.css'\n",
    "HTML(open(css_file, \"r\").read())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Gradient Descent\n",
    "\n",
    "© 2018 Daniel Voigt Godoy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Definition\n",
    "\n",
    "Gradient Descent is a generic optimization algorithm used to find optimal solutions (maximum or minimum). It can be used to minimize a given cost function of a Machine Learning algorithm, for instance.\n",
    "\n",
    "It works by tweaking a set of parameters, performing incremental changes to them at every step, gradually converging to the solution (or not!).\n",
    "\n",
    "The key is the ***incremental changes*** of the parameters. How does it know if it should ***increase*** or ***decrease*** a given parameter? How does it know ***how much*** to change?\n",
    "\n",
    "This is what the ***partial derivative*** is used for. It determines how much the ***cost function changes*** if  ***one parameter changes a little bit***. \n",
    "\n",
    "If we want to know ***how much*** $J(w_1, w_2) \\\\ $ ***changes*** when we ***modify*** the value of $w_1 \\ $ ***a bit***, we have the ***partial derivative of*** $J(w_1, w_2) \\\\ $ ***with respect to*** $w_1 \\ $:\n",
    "\n",
    "$$\n",
    "\\frac{\\partial{J(w_1, w_2)}}{\\partial{w_1}}\n",
    "$$\n",
    "\n",
    "The same holds for $w_2$:\n",
    "\n",
    "$$\n",
    "\\frac{\\partial{J(w_1, w_2)}}{\\partial{w_2}}\n",
    "$$\n",
    "\n",
    "So, ***gradient descent*** will compute ***partial derivatives with respect to every weight*** (and the ***bias*** too!)\n",
    "\n",
    "Then it will ***update each weight*** using its corresponding ***partial derivative*** and a ***multiplying factor*** $\\eta$ which is known as the ***learning rate***.\n",
    "\n",
    "$$\n",
    "w_1 = w_1 - \\eta \\frac{\\partial{J(w_1, w_2)}}{\\partial{w_1}}\n",
    "$$\n",
    "\n",
    "***IMPORTANT***:\n",
    "   - The ***learning rate*** is the ***single most important hyper-parameter*** to tune when you are using ***Deep Learning*** models! \n",
    "   - If it is ***too small***, convergence to the solution will be ***extremely slow***, but if it is ***too big***, you may end up ***not converging at all***. You will understand these mechanisms in the ***interactive example*** and the ***experiment***.\n",
    "   \n",
    "![](http://cs231n.github.io/assets/nn3/learningrates.jpeg)\n",
    "<center>Source: CS231n CNN for Visual Recognition</center>\n",
    "\n",
    "After ***updating all weights***, it restarts the process, ***re-evaluating the partial derivatives using the updated weights*** and ***updating all weights one more time***, and so on and so forth!\n",
    "\n",
    "That is just it! No rocket science, it is quite simple, actually!\n",
    "\n",
    "But ***partial derivatives*** can be a bit intimidating, so let's go through an interactive example!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from intuitiveml.optimizer.GradientDescent import *\n",
    "vb = VBox(build_figure_deriv())\n",
    "vb.layout.align_items = 'center'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "42b4efc6b247430092ccf536a4c9785f",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "VBox(children=(FigureWidget({\n",
       "    'data': [{'line': {'color': 'black'},\n",
       "              'mode': 'lines',\n",
       "       …"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "vb"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Click the ***Step*** button once. It will show you vectors: ***red*** and ***gray***.\n",
    "\n",
    "The ***red*** vector is our ***update*** to the weight.\n",
    "\n",
    "The ***gray*** vector shows ***how much the cost changes*** given our update.\n",
    "\n",
    "If you divide their ***lengths***, gray over red, it will give you the ***approximate partial derivative***.\n",
    "\n",
    "The ***update*** itself equals the ***partial derivative*** times the ***learning rate***.\n",
    "\n",
    "Change the ***learning rate*** to 0.25. If you click the ***Step*** button once again, you should see a much bigger update.\n",
    "\n",
    "#### Exercises:\n",
    "\n",
    "1. Now, choose a different learning rate, reset the plot and follow some steps. Observe the path it traces and check if it hits the minimum. Try different learning rates, see what happens if you choose a really big value for it.\n",
    "\n",
    "\n",
    "2. Then, change the function to a ***Non-convex*** and set the learning rate to the minimum before following some steps. Where does it converge to? Try resetting and observing its path. Does it reach the global minimum? Try different learning rates and see what happens then."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2 Types of Gradient Descent\n",
    "\n",
    "There are 3 types of Gradient Descent, depending on the number of samples it uses to compute the partial derivatives.\n",
    "\n",
    "#### 1.2.1 Batch\n",
    "\n",
    "It uses ***all data points*** to compute the partial derivatives and, therefore, its path towards the solution is stable, yet it is going to be ***very slow*** on large datasets.\n",
    " \n",
    "#### 1.2.2 Stochastic\n",
    "\n",
    "It uses a ***single data point*** to compute the partial derivative and, because of it, it is ***very fast***, but its path towards the solution is going to be ***erratic*** and ***jumpy***.\n",
    "\n",
    "#### 1.2.3 Mini-Batch\n",
    "\n",
    "It uses ***some data points*** to compute the partial derivative and it is a compromise between ***stability*** and ***speed***. Its size is a ***hyper-parameter*** on its own, although a value of 32 (and other powers of 2) are commonly used."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Experiment\n",
    "\n",
    "Time to try it yourself!\n",
    "\n",
    "There are two parameters, x1 and x2, and we're using Gradient Descent to try to reach the ***minimum*** indicated by the ***star***.\n",
    "\n",
    "The dataset has only 50 data points.\n",
    "\n",
    "The controls below allow you to:\n",
    "- adjust the learning rate\n",
    "- scale the features x1 and x2\n",
    "- set the number of epochs (steps)\n",
    "- batch size (since the dataset has 50 points, a size of 64 means using ***all*** points)\n",
    "- starting point for x1 and x2 (initialization)\n",
    "\n",
    "Use the controls to play with different configurations and answer the questions below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "x1, x2, y = data()\n",
    "mygd = plotGradientDescent(x1, x2, y)\n",
    "vb = VBox(build_figure(mygd))\n",
    "vb.layout.align_items = 'center'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "6b5c0fa2b7884e2eb51221908e110279",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "VBox(children=(FigureWidget({\n",
       "    'data': [{'type': 'contour',\n",
       "              'uid': '2c5dd0fc-a0f9-4825-9e96-2…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "vb"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Questions\n",
    "\n",
    "1. ***Without scaling features***, start with the ***learning rate at minimum***:\n",
    "    - change the batch size - try ***stochastic***, ***batch*** and ***mini-batch*** sizes - what happens to the trajectory? Why?\n",
    "    - keeping ***maximum batch size***, increase ***learning rate*** to 0.000562 (three notches) - what happens to the trajectory? Why?\n",
    "    - now reduce gradually ***batch size*** - what happens to the trajectory? Why?\n",
    "    - go back to ***maximum batch size*** and, this time, increase ***learning rate*** a bit further- what happens to the trajectory? Why?\n",
    "    - experiment with different settings (yet ***no scaling***), including initial values ***x1*** and ***x2*** and try to get as close as possible to the ***minimum*** - how hard is it?\n",
    "    - what was the ***largest learning rate*** you manage to use succesfully?\n",
    "\n",
    "\n",
    "2. Check ***Scale Features*** - what happened to the surface (cost)? What about its level (look at the scale)?\n",
    "\n",
    "\n",
    "3. ***Using scaled features***, answer the same items as in ***question 1***.\n",
    "\n",
    "\n",
    "4. How do you compare the ***performance*** of gradient descent with and without ***scaling***? Why did this happen? (think about the partial derivatives with respect to each feature, especially without scaling)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. More Resources\n",
    "\n",
    "[Gradient descent, how neural networks learn](https://www.youtube.com/watch?v=IHZwWFHWa-w)\n",
    "\n",
    "[Intro to optimization in deep learning: Gradient Descent](https://blog.paperspace.com/intro-to-optimization-in-deep-learning-gradient-descent/)\n",
    "\n",
    "[Stochastic Gradient Descent with momentum](https://towardsdatascience.com/stochastic-gradient-descent-with-momentum-a84097641a5d)\n",
    "\n",
    "[An overview of gradient descent optimization algorithms](http://ruder.io/optimizing-gradient-descent/)\n",
    "\n",
    "[Why Momentum Really Works](https://distill.pub/2017/momentum/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### This material is copyright Daniel Voigt Godoy and made available under the Creative Commons Attribution (CC-BY) license ([link](https://creativecommons.org/licenses/by/4.0/)). \n",
    "\n",
    "#### Code is also made available under the MIT License ([link](https://opensource.org/licenses/MIT))."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<script>\n",
       "  function code_toggle() {\n",
       "    if (code_shown){\n",
       "      $('div.input').hide('500');\n",
       "      $('#toggleButton').val('Show Code')\n",
       "    } else {\n",
       "      $('div.input').show('500');\n",
       "      $('#toggleButton').val('Hide Code')\n",
       "    }\n",
       "    code_shown = !code_shown\n",
       "  }\n",
       "\n",
       "  $( document ).ready(function(){\n",
       "    code_shown=false;\n",
       "    $('div.input').hide()\n",
       "  });\n",
       "</script>\n",
       "<form action=\"javascript:code_toggle()\"><input type=\"submit\" id=\"toggleButton\" value=\"Show Code\"></form>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.display import HTML\n",
    "HTML('''<script>\n",
    "  function code_toggle() {\n",
    "    if (code_shown){\n",
    "      $('div.input').hide('500');\n",
    "      $('#toggleButton').val('Show Code')\n",
    "    } else {\n",
    "      $('div.input').show('500');\n",
    "      $('#toggleButton').val('Hide Code')\n",
    "    }\n",
    "    code_shown = !code_shown\n",
    "  }\n",
    "\n",
    "  $( document ).ready(function(){\n",
    "    code_shown=false;\n",
    "    $('div.input').hide()\n",
    "  });\n",
    "</script>\n",
    "<form action=\"javascript:code_toggle()\"><input type=\"submit\" id=\"toggleButton\" value=\"Show Code\"></form>''')"
   ]
  },
  {
   "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.5.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}