{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Lecture 6: Training II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "![](https://www.tensorflow.org/images/colab_logo_32px.png)\n",
    "[Run in colab](https://colab.research.google.com/drive/18org-B5m6ZtN7E9GBSoLtkXb6-Fc2bgh)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-10T00:19:34.924839Z",
     "iopub.status.busy": "2024-01-10T00:19:34.924473Z",
     "iopub.status.idle": "2024-01-10T00:19:34.932173Z",
     "shell.execute_reply": "2024-01-10T00:19:34.931501Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Last executed: 2024-01-10 00:19:34\n"
     ]
    }
   ],
   "source": [
    "import datetime\n",
    "now = datetime.datetime.now()\n",
    "print(\"Last executed: \" + now.strftime(\"%Y-%m-%d %H:%M:%S\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Stochastic gradient descent"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Problems with batch gradient descent\n",
    "\n",
    "- Uses the entire training set to compute gradients at every step (slow when the training set is large).\n",
    "\n",
    "- Full training set needs to be held in memory."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Properties of stochastic gradient descent\n",
    "\n",
    "- Uses a (random) single instance from the training set to compute gradients at each iteration (fast since very little data considered for each iteration).\n",
    "- Only one instance of training data then needs to be held in memory.\n",
    "- Less regular than batch gradient descent.\n",
    "  - Helps to escape local minima.\n",
    "  - Ends up close to a minimum but continues to explore vacinity around minimum (\"bounces\" around)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Simulated annealing\n",
    "\n",
    "To mitigate issue of bouncing around minimum, can reduce learning rate as algorithm proceeds.\n",
    "\n",
    "Called *simulated annealing* by analogy with annealing in metallurgy.\n",
    "\n",
    "*Learning schedule* defines how learning rate changes over time.\n",
    "\n",
    "- If learning rate reduces too quickly, may get stuck on local minimum or end up frozen half-way to minimum.\n",
    "- If learning rate reduces too slowly, may jump around minimum for long time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Example learning schedule\n",
    "\n",
    "Set learning rate $\\alpha$ at iteration $t$ by\n",
    "\n",
    "$$\\alpha(t) = \\frac{t_0}{t + t_1},$$\n",
    "\n",
    "where $t_0$ and $t_1$ are parameters."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Stochastic gradient descent example"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-10T00:19:34.974213Z",
     "iopub.status.busy": "2024-01-10T00:19:34.973677Z",
     "iopub.status.idle": "2024-01-10T00:19:35.388064Z",
     "shell.execute_reply": "2024-01-10T00:19:35.387394Z"
    }
   },
   "outputs": [],
   "source": [
    "# Common imports\n",
    "import os\n",
    "import numpy as np\n",
    "np.random.seed(42) # To make this notebook's output stable across runs\n",
    "\n",
    "# To plot pretty figures\n",
    "%matplotlib inline\n",
    "import matplotlib\n",
    "import matplotlib.pyplot as plt\n",
    "plt.rcParams['axes.labelsize'] = 14\n",
    "plt.rcParams['xtick.labelsize'] = 12\n",
    "plt.rcParams['ytick.labelsize'] = 12"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Set up training data (repeating example from previous lecture)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-10T00:19:35.392076Z",
     "iopub.status.busy": "2024-01-10T00:19:35.391426Z",
     "iopub.status.idle": "2024-01-10T00:19:35.624448Z",
     "shell.execute_reply": "2024-01-10T00:19:35.623816Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 22856 characters]",
      "text/plain": [
       "<Figure size 900x600 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "m = 100\n",
    "X = 2 * np.random.rand(m, 1)\n",
    "y = 4 + 3 * X + np.random.randn(m, 1)\n",
    "plt.figure(figsize=(9,6))\n",
    "plt.plot(X, y, \"b.\")\n",
    "plt.xlabel(\"$x_1$\", fontsize=18)\n",
    "plt.ylabel(\"$y$\", rotation=0, fontsize=18)\n",
    "plt.axis([0, 2, 0, 15]);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Add bias terms"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-10T00:19:35.627965Z",
     "iopub.status.busy": "2024-01-10T00:19:35.627484Z",
     "iopub.status.idle": "2024-01-10T00:19:35.631843Z",
     "shell.execute_reply": "2024-01-10T00:19:35.631191Z"
    }
   },
   "outputs": [],
   "source": [
    "X_b = np.c_[np.ones((m, 1)), X]         # add x0 = 1 to each instance\n",
    "X_new = np.array([[0], [2]])\n",
    "X_new_b = np.c_[np.ones((2, 1)), X_new] # add x0 = 1 to each instance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Solve by SGD with learning schedule"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-10T00:19:35.635312Z",
     "iopub.status.busy": "2024-01-10T00:19:35.635050Z",
     "iopub.status.idle": "2024-01-10T00:19:35.639860Z",
     "shell.execute_reply": "2024-01-10T00:19:35.639206Z"
    }
   },
   "outputs": [],
   "source": [
    "theta_path_sgd = []\n",
    "m = len(X_b)\n",
    "np.random.seed(42)\n",
    "\n",
    "n_epochs = 50\n",
    "t0, t1 = 5, 50  # learning schedule hyperparameters\n",
    "\n",
    "def learning_schedule(t):\n",
    "    return t0 / (t + t1)\n",
    "\n",
    "theta = np.random.randn(2,1)  # random initialization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-10T00:19:35.642955Z",
     "iopub.status.busy": "2024-01-10T00:19:35.642348Z",
     "iopub.status.idle": "2024-01-10T00:19:35.887038Z",
     "shell.execute_reply": "2024-01-10T00:19:35.886346Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 54604 characters]",
      "text/plain": [
       "<Figure size 900x600 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.figure(figsize=(9,6))\n",
    "for epoch in range(n_epochs):\n",
    "    for i in range(m):\n",
    "        \n",
    "        # Plot current model\n",
    "        if epoch == 0 and i < 10:                   \n",
    "            y_predict = X_new_b.dot(theta)          \n",
    "            style = \"b-\" if i > 0 else \"r--\"         \n",
    "            plt.plot(X_new, y_predict, style)        \n",
    "        \n",
    "        # SGD update\n",
    "        random_index = np.random.randint(m)\n",
    "        xi = X_b[random_index:random_index+1]\n",
    "        yi = y[random_index:random_index+1]\n",
    "        gradients = 2 * xi.T.dot(xi.dot(theta) - yi)\n",
    "        alpha = learning_schedule(epoch * m + i)        \n",
    "        theta = theta - alpha * gradients\n",
    "        theta_path_sgd.append(theta)                 \n",
    "\n",
    "plt.plot(X, y, \"b.\")                                 \n",
    "plt.xlabel(\"$x_1$\", fontsize=18)                     \n",
    "plt.ylabel(\"$y$\", rotation=0, fontsize=18)           \n",
    "plt.axis([0, 2, 0, 15]);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-10T00:19:35.890139Z",
     "iopub.status.busy": "2024-01-10T00:19:35.889906Z",
     "iopub.status.idle": "2024-01-10T00:19:35.895764Z",
     "shell.execute_reply": "2024-01-10T00:19:35.895204Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[4.21076011],\n",
       "       [2.74856079]])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "theta"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Use only 50 passes over the data, compared to 1000 for batch gradient descent."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    },
    "tags": [
     "exercise_pointer"
    ]
   },
   "source": [
    "**Exercises:** *You can now complete Exercise 1 in the exercises associated with this lecture.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Mini-batch gradient descent"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "\n",
    "Use *mini-batches* of small random sets of instances of training data.\n",
    "\n",
    "Trades off properties of batch GD and stochastic GD.\n",
    "\n",
    "Can get a performance boost over SGD by exploiting hardware optimisation for matrix operations, particuarly for GPUs."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Shuffling training data\n",
    "\n",
    "First step is to randomly shuffle or reorder data-set since do not want to be sensitive to ordering of data (want mini-batch considered to be representative)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    },
    "tags": [
     "exercise_pointer"
    ]
   },
   "source": [
    "**Exercises:** *You can now complete Exercise 2 in the exercises associated with this lecture.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Comparing gradient descent algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Batch gradient descent (from previous lecture)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-10T00:19:35.899258Z",
     "iopub.status.busy": "2024-01-10T00:19:35.898708Z",
     "iopub.status.idle": "2024-01-10T00:19:35.905654Z",
     "shell.execute_reply": "2024-01-10T00:19:35.905047Z"
    }
   },
   "outputs": [],
   "source": [
    "theta_path_bgd = []\n",
    "\n",
    "def plot_gradient_descent(theta, alpha, theta_path=None):\n",
    "    m = len(X_b)\n",
    "    plt.plot(X, y, \"b.\")\n",
    "    n_iterations = 1000\n",
    "    for iteration in range(n_iterations):\n",
    "        if iteration < 10:\n",
    "            y_predict = X_new_b.dot(theta)\n",
    "            style = \"b-\" if iteration > 0 else \"r--\"\n",
    "            plt.plot(X_new, y_predict, style)\n",
    "        gradients = 2/m * X_b.T.dot(X_b.dot(theta) - y)\n",
    "        theta = theta - alpha * gradients\n",
    "        if theta_path is not None:\n",
    "            theta_path.append(theta)\n",
    "    plt.xlabel(\"$x_1$\", fontsize=18)\n",
    "    plt.axis([0, 2, 0, 15])\n",
    "    plt.title(r\"$\\alpha = {}$\".format(alpha), fontsize=16)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-10T00:19:35.908611Z",
     "iopub.status.busy": "2024-01-10T00:19:35.907981Z",
     "iopub.status.idle": "2024-01-10T00:19:36.473185Z",
     "shell.execute_reply": "2024-01-10T00:19:36.472575Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 70212 characters]",
      "text/plain": [
       "<Figure size 1000x400 with 3 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "np.random.seed(42)\n",
    "theta = np.random.randn(2,1)  # random initialization\n",
    "\n",
    "plt.figure(figsize=(10,4))\n",
    "plt.subplot(131); plot_gradient_descent(theta, alpha=0.02)\n",
    "plt.ylabel(\"$y$\", rotation=0, fontsize=18)\n",
    "plt.subplot(132); plot_gradient_descent(theta, alpha=0.1, theta_path=theta_path_bgd)\n",
    "plt.subplot(133); plot_gradient_descent(theta, alpha=0.5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Convert lists to numpy arrays"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-10T00:19:36.476582Z",
     "iopub.status.busy": "2024-01-10T00:19:36.475915Z",
     "iopub.status.idle": "2024-01-10T00:19:36.482264Z",
     "shell.execute_reply": "2024-01-10T00:19:36.481660Z"
    }
   },
   "outputs": [],
   "source": [
    "theta_path_bgd = np.array(theta_path_bgd)\n",
    "theta_path_sgd = np.array(theta_path_sgd)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Algorithm trajectories"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-01-10T00:19:36.485127Z",
     "iopub.status.busy": "2024-01-10T00:19:36.484696Z",
     "iopub.status.idle": "2024-01-10T00:19:36.727779Z",
     "shell.execute_reply": "2024-01-10T00:19:36.727175Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2.5, 4.5, 2.3, 3.9)"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "[encoded data, 63780 characters]",
      "text/plain": [
       "<Figure size 1000x500 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.figure(figsize=(10,5))\n",
    "plt.plot(theta_path_sgd[:, 0], theta_path_sgd[:, 1], \"r-s\", linewidth=1, label=\"Stochastic\")\n",
    "plt.plot(theta_path_bgd[:, 0], theta_path_bgd[:, 1], \"b-o\", linewidth=3, label=\"Batch\")\n",
    "plt.legend(loc=\"upper left\", fontsize=16)\n",
    "plt.xlabel(r\"$\\theta_0$\", fontsize=20)\n",
    "plt.ylabel(r\"$\\theta_1$   \", fontsize=20, rotation=0)\n",
    "plt.axis([2.5, 4.5, 2.3, 3.9])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "We finally show the full trajectory for all optimisation methods, including mini-batch gradient descent (computed in exercises)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"https://raw.githubusercontent.com/astro-informatics/course_mlbd_images/master/Lecture06_Images/algorithm_trajectories.png\" alt=\"trajectories\" style=\"height: 400px;\"/>"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.8.18"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
