{ "cells": [ { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# CS 236756 - Technion - Intro to Machine Learning\n", "---\n", "#### Tal Daniel\n", "\n", "## Tutorial 07 - Optimization\n", "---" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Agenda\n", "---\n", "* [Optimization Problems](#-Optimization-Problems)\n", "* [1-Dimensional Optimization](#-1-D-Optimization)\n", " * [Gradient Descent](#(Batch)-Gradient-Descent)\n", " * [Least-Squares](#-Example---Linear-Least-Squares)\n", " * [Stochastic Gradient Descent (SGD)](#Stochastic-Gradient-Descent-(Mini-Batch-Gradient-Descent))\n", "* [Mathematical Background](#-Mathematical-Background)\n", " * [Gradient](#-Multivariate-Calculus)\n", " * [Chain Rule](#-The-Chain-Rule)\n", " * [Multi-dimensional Calculus](#--Multi-Dimensional-Optimization)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "* [Multi-dimensional Optimization](#--Multi-Dimensional-Optimization)\n", "* [Constrained Optimization](#-Constrained-Optimization)\n", " * [Largrange Multipliers](#-Largrange-Multipliers)\n", " * [Examples: Entropy](#-Exercise-2---Max-Entropy-Distribution)\n", "* [Recommended Videos](#-Recommended-Videos)\n", "* [Credits](#-Credits)" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "# imports for the tutorial\n", "import numpy as np\n", "import pandas as pd\n", "import matplotlib.pyplot as plt\n", "from mpl_toolkits.mplot3d import Axes3D\n", "%matplotlib notebook" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Optimization Problems\n", "---\n", "### Definitions\n", "\n", "* **Objective Function** - mathematical function which is optimized by changing the values of the design variables.\n", "* **Design Variables** - variables that we, as designers, can change.\n", "* **Constraints** - functions of the design variables which establish limits in individual variables or combinations of design.\n", " * For example - \"Find $\\theta$ that minimizes $f_{\\theta}(x)$ s.t. (subject to) $\\theta \\leq 1$\"\n", " \n", "**The main problem in optimization** is *how* to search for the values of decision variables that minimize the cost/objective function." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "#### Types of Objective Functions\n", "---\n", "* **Unimodal** - only **one** optimum, that is, the *local* optimum is also global.\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "* **Multimodal** - more than one optimum\n", "\n", "\n", "Most search schemes are based on the assumption of **unimodal** surface. The optimum determined in such cases is called **local optimum design**.\n", "\n", "The **global optimum** is the best of all *local optimum* designs." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Convexity\n", "---\n", "* **Definition**: $$\\forall x_1, x_2 \\in X, \\forall t \\in [0,1]: $$ $$ f(tx_1 + (1-t)x_2) \\leq tf(x_1) + (1-t)f(x_2) $$\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "\n", "Image Source" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "* Convex functions are **unimodal**\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Continuous Optimization\n", "---\n", "* Derivative based optimization - the search directions are determined based on deivative information\n", "* Methods include:\n", " * **Gradient Descent**\n", " * Newton method\n", " * Conjugate gradient\n", "* We will focus on *Gradient Descent*" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## 1-D Optimization\n", "---\n", "### (Batch) Gradient Descent\n", "---\n", "* Generic optimization algorithm capable of finding optimal solutions to a wide range of problems.\n", "* The general idea is to tweak parameters **iteratively** to minimize a cost function.\n", "* It measures the local gradient of the error function with regards to the parameter vector ($\\theta$ or $w$), and it goes down in the direction of the descending gradient. Once the gradient is zero - the minimum is reached (=convergence)." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "* **Learning Rate** hyperparameter - it is the size of step to be taken in each iteration.\n", " * Too *small* $\\rightarrow$ the algorithm will have to go through many iterations to converge, which will take a long time\n", " * Too *high* $\\rightarrow$ might make the algorithm diverge as it may miss the minimum\n", " * Image Source" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "* **Pseudocode**:\n", " * **Require**: Learning rate $\\alpha_k$\n", " * **Require**: Initial parameter $w$\n", " * **While** stopping criterion not met **do**\n", " * Compute gradient: $g \\leftarrow f'(x,w)$ (more specifically, for $M$ samples: $g \\leftarrow \\frac{1}{M}\\sum_{i=1}^M f'(x_i,w)$, where $f'$ is w.r.t $\\theta$ or $w$)\n", " * Apply update: $w \\leftarrow w - \\alpha_k g$\n", " * $k \\leftarrow k + 1$\n", " * **end while**" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "* **Visualization**:\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "\n", "\n", "* **Convergene**: When the cost function is *convex* and its slope does not change abruptly, (Batch) GD with a *fixed* learning rate will eventually converge to the optimal solution (but the time is depndent on the rate)." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Example - Linear Least Squares\n", "---\n", "* **Problem Formulation**\n", " * $y \\in \\mathbb{R}^N$ - vector of values\n", " * $X \\in \\mathbb{R}^N$ - data matrix with *one feature* (= data *vector*)\n", " * $w \\in \\mathbb{R}$ - the *parameter* to be learnt\n", "* **Goal**: find $w$ that best fits the measurement y\n", "* Mathematically:\n", "$$\\min_w f(w;x,y) = \\min_w \\sum_{i=1}^N(wx_i-y_i)^2 $$\n", "* In vector form:\n", "$$\\min_w f(w;x,y) = \\min_w ||wX - Y||_2^2 $$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "#### LLS - Analytical Solution\n", "---\n", "* Mathematically:\n", "$$\\min_w f(w;x,y) = \\min_w \\sum_{i=1}^N(wx_i-y_i)^2 = \\min_w \\sum_{i=1}^N w^2x_i^2 -2wx_iy_i + y_i^2$$\n", "* The derivative: \n", "$$\\sum_{i=1}^N 2wx_i^2 - 2x_iy_i = 0 \\rightarrow w = \\frac{\\sum_{i=1}^N y_i x_i}{\\sum_{i=1}^N x_i^2}$$\n", "* The second derivative, to ensure minimum:\n", "$$f''(w;x,y) = \\sum_{i=1}^N 2x_i^2 > 0 \\rightarrow good! $$" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "# generate some random data\n", "N = 20\n", "x = np.linspace(1, 20, N)\n", "y = 5 * x + np.random.randn(N)" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "best w: 4.973943975346493\n" ] } ], "source": [ "# lls - analytical solution\n", "# we want to find w that minimizes (wx-y)^2\n", "# by the above derivation\n", "w = np.sum(y * x) / np.sum(np.square(x))\n", "print(\"best w:\", w)" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "def plot_lls_sol(x, y, w, title=\"\"):\n", " fig = plt.figure(figsize=(8,5))\n", " ax = fig.add_subplot(1,1,1)\n", " ax.scatter(x, y, label=\"y\")\n", " ax.plot(x, w * x, label=\"wx\", color='r')\n", " ax.legend()\n", " ax.grid()\n", " ax.set_xlabel(\"x\")\n", " ax.set_title(title)" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAeYAAAFNCAYAAADVSMziAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nO3deXxU1fnH8c9jDBAFG5YaIIioxQiKGgE3BKFUU/dgrUsRaEVwQURFFH4qWquCRgUFl2pRQK2IiqiAIiIBWwVBAoJCwAVswqKAYQ37+f1xb3AI2UgyuTOT7/v1yiuZe+/c+5xMkifn3DPnMeccIiIiEhkOCToAERER+ZUSs4iISARRYhYREYkgSswiIiIRRIlZREQkgigxi4iIRBAlZok6ZvaAmb1azue2N7PsSohhhZn9oaLnqczzmllTM9tiZnFhiKudmS33z59e2ecvw/W/NrOOB3H8EDO7LYwhlXb9CWb2x2L21TKz/zOzC6s6LokOSswSVmaWaWa/mFnNgK7vzOx3BY+dc58651LCfM0mZva2ma0zs41mtsjM/hqG6+yXxJ1zPzrnajvn9lT2tYAHgZH++SeG4fwlcs6d6JzLLMuxZvZboDvwz7AGVbKhwMOFN/r/NL0BdAFeL5y8zex4M3vXzH42sw1mNtXMwvrzKpFHiVnCxsyaAe0BB1waaDBV6xXgf8DRQH28JLE20Igq7mjg6/I80cwOreRYSvNXYIpzLr+Kr7uPc+4L4Agza1No1wtATaAD3u/Ey2Z2esj+ROA9IAVIAr4A3g1/xBJJlJglnLoDs4HRQI/QHWY22syeMbPJZrbZzOaY2XEh+58ys/+Z2SYz+9LM2hd1Af/5fQtt+8rM0s1slr9poT8Ee5WZdTSznJBjj/KHHX82s/VmNtLffpyZfeJvW2dmr5lZYhnb3RYY7Zzb6pzb7ZzLcs59EHLNS/2h2Tx/RKFFMW0bbWYPhTzeF7uZvQI0Bd7323aXmTXzRwgO9Y9pbGbv+T2vb82sV8i5HjCz8WY21v/+f11EEik49jvg2JBr1SzDud8ys1fNbBNeoiyqbc+a2Qf+Of9rZg3NbLg/wrLUzFJDjt83OlCG2C8AZoY8d6aZ/cn/+hz/e3Sh//gPZrbA//o5M3sr5HmPmtl0M7Mi4h9gZm8X2jbCzIaHbMoELgrZPwRoAFzmnMt3zs0ELgf+XdArds594Zwb5Zzb4JzbBQwDUsysflGvjcQmJWYJp+7Aa/5HmpklFdp/DfB3oC7wLfsP/c0FTgXqAf8G3jSzWkVcYwxwbcEDMzsFSMbrMXXwN5/iD8G+EfpEf1hxErASaOY/b1zBbmAI0BhoARwFPFDGds8GnjGzq82saaFrHg+8DtwG/BaYgpfwapTx3AA457oBPwKX+G17rIjDXgdy/DZcATxiZp1D9l+K196CXtrIYq51XKFr7SjDuS8D3vLP/VoxzbgSuBcvWe0APgfm+4/fAp4s4VtQUuytgNB5BDOBjv7XHYDvgXNDHhck8f7AyWb2V/8fwZ5AD1f0usWvAn8s+GfN/2foKrzRkgJLgFMKHjjnBjnnLvO/fwXbPnfO/c45V9y8hw7AGufc+mL2SwxSYpawMLNz8IY/xzvnvgS+A/5S6LAJfg9hN94f71MLdjjnXnXOrfd7nE/gDf8Vda/tXaC5mTX3H3cD3nDO7SxDmKfjJZYBfu92u3PuP/71v3XOTXPO7XDO/YyXJM4t6WQh/gx8CtwH/GBmC8ysrb/vKmCyf+5dwONAAnB2Gc9dJmZ2FHAOcLffrgXAv/C+PwX+45yb4t+TfoWQJFIJ5/7cOTfRObe3hCHld5xzXzrntgPvANudc2P9eN4AUot5XmmxJwKbQx7PZP9EPCTk8bn+fpxz2/D+yXsSL/H2dc7lUATn3GpgFt5rDfBHYJ3/s15gsx9LuZhZE+AZ4I7ynkOikxKzhEsP4CPn3Dr/8b8pNJwNrAn5ehtQu+CBmfU3syXmTZ7KA36D15Paj9/7GA9ca2aH4PXCXyl8XDGOAlb6/xjsx8yONLNxZpbrD8e+WtT1i+Kc+8U5N9A5dyLefcIFwER/SLQxXg+94Ni9ePejk8sYc1k1BjY450IT1MpC1yn8/a9lZbsfXJZz/68M5wm9755fxOPaFK+k2H8B6oTs/xw43h+xORUYCxxlZg3w/jkruOVRcG/4e7wRk/EF20OG3LeYWVd/c+hozbUc+HNXB8groQ3FMm8C20fAs86518tzDoleSsxS6cwsAW+Y8lwzW2Nma4DbgVP8oebSnt8euNs/R13nXCKwEe+PZVHGAF2BzsA259znZQz1f0DTYpLRELxJayc7547A+8Nb3PWL5f9j8jheMqsHrMIbSQDAT9ZHAblFPH0rcFjI44aFT1/CpVcB9cwsNEE1LeY6B6ss5w6ybN1XwPH7AvF6wl8C/YDF/mjKZ3g90e9C/nnEzPrgjc6sAu4KOccF/jB+bedcwdD8RLyh75OAizlwyL4FsPBggzezunhJ+T3n3AEzuyX2KTFLOKQDe4CWeD2UU/H+SH2Kd9+5NHWA3cDPwKFmNhg4oriD/US8F3iCA3sta/EmLhXlC2A1MNTMDjfv/aXtQmLYAuSZWTIwoAxxA/smDZ1kZof6yesm4Fv/PuF44CIz62xm8Xj3NXfgJYrCFgAXmlk9M2uId1+6TG1zzv3PP+cQv10n490zLe5+b5mF89yVZAoH3naYCdzCr/eTMws9Lrj//xDeP2HdgLvM7FSK4Q/Bv4U3GvSFc+7HQoecC3xwwBNLYGZHAFOB/zrnBh7McyV2KDFLOPQAXvbfV7um4ANvgk7XMgyXTsX7g7YMb4h0O6UPjY7Fm/RTeOGRB4Ax5s2AvjJ0h39/8hLgd3iTm3Lw7gGDNyntNLye+mRgQinXD3UY3j3TPLxh0aPx3y7mT/K5FhgBrPOvf0kx98RfwetxrcDrQb1RaP8Q4F6/bXcW8fxr8Ca1rfLjud85N+0g2lGScJ67osbi/UOTELJtJt4/W7OKeuz/TL4KPOqcW+icWw78H/CKlfwe/DF4P3f7/UPozynY6g+NH4wueLP6/xYydL6l8CRCiW1W9IRDkehiZt2B3s65c4KORYJnZo8APznnhpd6cMWu0xRYCjR0zm0K2f42MMo5NyWc15fYpMQsUc/MDgM+wZsoMzboeKR68CcbPgkc4Zy7Luh4JHZoKFuimpml4d2LXot3r08k7MzscGATcB5wf8DhSIxRj1lERCSCqMcsIiISQZSYRUREIkhVV30pUoMGDVyzZs2CDqNSbd26lcMPPzzoMCqV2hQ9YrFdsdgmiM12qU1l8+WXX65zzv228PaISMzNmjVj3rx5QYdRqTIzM+nYsWPQYVQqtSl6xGK7YrFNEJvtUpvKxsxWFrVdQ9kiIiIRRIlZREQkgigxi4iIRJCIuMdclF27dpGTk8P27duDDqVcfvOb3/DDDz/QpEkT4uPjgw5HRESiRMQm5pycHOrUqUOzZs3wKuNFl02bNrFz505ycnI45phjgg5HRESiRKlD2Wb2kpn9ZGaLQ7bVM7NpZrbc/1w3ZN8gM/vWzLL95RLLZfv27dSvXz8qkzKAmVG/fv2o7fGLiEgwynKPeTTwx0LbBgLTnXPNgen+Y8ysJXA1cKL/nGfNLK68wUVrUi4Q7fGLiEjVKzUxO+dmARsKbb4Mrw4p/uf0kO3jnHM7nHM/AN8Cp1dSrCIiIjGvvLOyk5xzqwH8z0f625PZv6B9jr9NREREyqCyJ38VNXZbZPkqM+sN9AZISkoiMzNzv/2/+c1v2Lx5cyWHd3CGDx9OzZo1uemmmxg4cCCLFy9m0qRJZGZmkpGRQW5uLtOnT6du3bpccMEF3HXXXXTu3BmAPXv2sHnzZrZv335A26LVli1bYqYtBWKxTRCb7YrFNkFstivW2lRj3TrqT59OZhVdr7yJea2ZNXLOrTazRsBP/vYc4KiQ45oAq4o6gXPuBeAFgDZt2rjCS50tWbKEOnXqlDO8ynHeeefxxBNPcNddd/HVV1+xY8cOatWqxfz58+natStxcXHceeednHHGGbRq1Yr09PR9z928eTN16tShVq1apKamBtiKyqNl9qJHLLYrFtsEsdmumGnT7t3wzDNw333s2bGDuEGDoGnTsF+2vIn5PaAHMNT//G7I9n+b2ZNAY6A58EVFg+S222DBggqfZj+nngrDh5d4SOvWrfnyyy/ZvHkzNWvW5LTTTmPevHl8+umnPP3007Rs2ZI333yT559/ngWVHZ+IiATns8/g5pth4UI+P74ty264jhf+/S0D0uJITw3vHdqyvF3qdeBzIMXMcsysJ15CPs/MlgPn+Y9xzn0NjAe+AT4E+jjn9oQr+HCLj4+nWbNmvPzyy5x99tm0b9+eGTNm8N1339GiRQu2bdtGTk4O4A3diIhIlFu3Dq6/Htq1Y9uan7j1inu5Jn0wm5IakZuXz6AJi5iYlRvWEErtMTvnrilmV+dijn8YeLgiQR2glJ5tOHXo0IHHH3+cl156iVatWnHHHXfQunVrzIy7776brl27cvTRR9OrVy8mTZoUWJwiIlIBe/fCSy/B3XfDpk0wYACXHn4u3+bvf1j+rj1kTM0Oa69Za2WXon379qxevZqzzjqLpKQkatWqRfv27Zk5cyZz587dl5xr1KjByy+/HHS4IiJysBYsgHbtoFcvOOkk7/Fjj/FdftGHr8orZkclidglOSNF586d2bVr177Hy5Yt2/f17Nmz9309YcKEKo1LREQqaONGGDwYRo6EBg1g7Fi49lrwF4dqnJhAbhFJuHFiQljDUo9ZRESqF+fg9dfhhBNgxAi48UZYuhS6dduXlAEGpKWQEL//4pUJ8XEMSEsJa3jqMYuISPWxdCn06QOffAJt2sD773ufi1BwHzljajawmeTEBAakpYR9VrYSs4iIxL5t2+Chh+Dxx+Hww+G557x7ynEll3NIT00mPTWZzMxM+nbtWCWhKjGLiEhMmJiVS8bUbFbl5dM4tHf73ntw662wciX06AGPPQZHHln6CQOixCwiIlFvYlYugyYsIn+Xt3RGbl4+I0dN44xF/6bRrGlw4okwcyZ06BBwpKVTYhYRkaiXMTV7X1KusXsX1899h76fvYE7xLzh61tvhfj4gKMsGyVmERGJegXvLT57xQL+Me15jtuQw+SUdjz0+1583r9HwNEdHCVmERGJeicfspWeE5/h0iWzWJHYiB5//jszj21NcpjfcxwOMZOYi73pXwH33XcfDRo0oF+/fgDcc889JCUlceutt1ZGyCIiUlF+Bai3nr6Xvdt3MKzdX3j+zCvYcWiNKnnPcTjExAIjBTf9c/PycVBpC4337NmTMWPGALB3717GjRtH165dKyFiERGpsM8/996DfNttxLc/h5kTZvDWxT3ZeWgNkhMTGHJ5q7C/5zgcYqLHHHrTv0BlLDTerFkz6tevT1ZWFmvXriU1NZX69etXNFwREamIdetg4EAYNQqaNIG334YuXTjfjPMvDTq4iouJxFzcguKVsdD49ddfz+jRo1mzZg3XXXddhc8nIiLlVEQFKAYPhtq1g46sUsXEUHZxC4pXxkLjXbp04cMPP2Tu3LmkpaVV+HwiIlIOxVSAirWkDDGSmMO50HiNGjXo1KkTV155JXGlLN0mIiKVbONG6NcPWreG77/3KkBlZnoLhsSomBjKDl1ovDJnZYM36Wv27Nm8+eabFT6XiIiUkXMwbhzccQesXQs33eStdV23btCRhV1MJGb4daHxyvTNN99w8cUX06VLF5o3b16p5xYRkWIcRAWoWBQziTkcWrZsyffffx90GCIi1cO2bfDww5CRcVAVoGKNErOIiAQvyipAhVNET/5yzgUdQoVEe/wiImG3YgVceilcdpk3w3rmTBg9utomZYjgxFyrVi3Wr18ftcnNOcf69eupVatW0KGIiESeHTvgkUegZUvvXvLjj0NWVlSUZQy3iB3KbtKkCTk5Ofz8889Bh1Iu27dvJzExkSZNmgQdiohIZPn4Y29y17JlcMUVMGyYt4KXABGcmOPj4znmmGOCDqPcMjMzSU1NDToMEZHIsWoV9O8P48axpcnRDP7rEN5JakXjV5cxIM2icl3rcIjYxCwiIjHCrwDFfffBzp0sueEOrq57LhudN9u6oPAQoORMBN9jFhGRGBBSAYp27eDrr7m+2UX7knKBgsJDosQsIiLhsG4dXH89nH02rF/vVYCaMgWOOy6shYdigRKziIhUnr17aTR5MqSkwJgxXgWoJUvg8svBDAhv4aFYoMQsIiKVw68AlfL44yVWgApn4aFYoMQsIiIVs2mTdw/ZrwC1ZNCgEitApacmM+TyViQnJmBAcmICQy5vpYlfPs3KFhGR8immAtTahQtp4Q9bFycchYdihRKziIgcvGpeASqcNJQtIiJlt20b3HMPnHwyzJ/vVYCaPVtJuRKpxywiIsWamJVLxtRsVuXlc+WqLO7/+J8ctjqn2leACiclZhERKdLErFwGTVhE/XWreOHjf3Let1+w/LdHs+bFt2h//Z+CDi9mKTGLiEiRhk9exN9mvU7fz95grxkPd7yOl9tcStK6Ovw36OBimBKziIgcaPp0Rg3rxXEbcpic0o5//L4Xa45oAGiFrnBTYhYRkV+FVICqWa8xPf78d2Ye23q/Q7RCV3hpVraIiHgVoJ56Ck44Ad55Bx54gPmTZ/FFyun7HaYVusJPPWYRkeru88+9xUEWLoQ//hFGjoTjjuNSYG/NWvtmZTdOTGBAWooWBgkzJWYRkepq3ToYOBBGjYImTbwKUF267Cs2AVqhKwgayhYRqW727oV//avEClASHPWYRURiROhiIMUOOy9Y4A1bz54N7dvDs896laAkYlSox2xmt5vZ12a22MxeN7NaZlbPzKaZ2XL/c93KClZERIpWsBhIbl4+DsjNy2fQhEVMzMr1DgitAPXddzB2LMycqaQcgcqdmM0sGbgVaOOcOwmIA64GBgLTnXPNgen+YxERCaOMqdnk79qz37b8XXvI+HApvP66N2z99NNw442QnQ3dumnYOkJVdCj7UCDBzHYBhwGrgEFAR3//GCATuLuC1xERkRIUtejHcev/x4PjnoOVX6kCVBQpd2J2zuWa2ePAj0A+8JFz7iMzS3LOrfaPWW1mWuFcRCTMGicmkOsn51q7tnPL5+PpPWcC22vU8ipA9eoFcXEBRyllYc658j3Ru3f8NnAVkAe8CbwFjHTOJYYc94tz7oD7zGbWG+gNkJSU1HrcuHHliiNSbdmyhdq1awcdRqVSm6JHLLYrFtsEldeuvPxd5P6ST9Mv53Du2Bc5Yt3PLGn/e3646QYOa1S1/aNYfK3C0aZOnTp96Zw7cAjDOVeuD+DPwKiQx92BZ4FsoJG/rRGQXdq5Wrdu7WLNjBkzgg6h0qlN0SMW2xWLbXKuEtv1ww9uVYfznAO3tEFTd1PvYe6d+TmVc+6DFIuvVTjaBMxzReTEitxj/hE408wOwxvK7gzMA7YCPYCh/ud3K3ANEREpyY4d8MQT8NBDNDrkEMjIIKVfP56Njw86MimnitxjnmNmbwHzgd1AFvACUBsYb2Y98ZL3nysjUBERKWT6dOjTx5tlfcUVMGyYt4KXRLUKzcp2zt0P3F9o8w683rOIiIRDSAUojjsOPvjAW+NaYoKW5BQRiRZFVIBi8WIl5RijJTlFRKJBMRWgJPaoxywiEsnWr/feg3z22d7Xb78NU6YoKccwJWYRkUgUWgFq9GhVgKpGNJQtIhJpVAGqWlOPWUQkUqgClKAes4hI8Jzz3vp0xx2wdq3XW37oIairqrnVkXrMIiIBmJiVS7uhn5Az92vmNW8Nf/mLtzjIF1/AM88oKVdj6jGLiFSxiVm5/P2NufSc9TrXfDGBLYfW5O8X9OGUB+8ivU3ToMOTgCkxi4hUsc+Gv8z7E0fQZNNPLGnfiWtP6cn6wxNJ/vhbJWZRYhYRqTIrVsCtt/LY+++T3aApV/5lKO0vPIH1i7w/xav8espSvSkxi4iEW0gFKA45hJEX3MDwEy9gd9yhtGf3vsMaJyYEGKRECk3+EhEJp+nT4ZRT4J574KKLYOlSmjx8H/G1au53WEJ8HAPSUgIKUiKJeswiIuFQQgWodL8yY8bUbGAzyYkJDEhLIT01Obh4JWIoMYuIVKbdu723O913H+zc6VWAuvtuqFVrv8PSU5NJT00mMzOTvl07BhKqRCYlZhGRylK4AtSIEfC73wUdlUQZ3WMWEamo4ipAKSlLOajHLCJSgolZuWRMzWZVXj6NC98L3rsXXnoJBg6EjRu9ClCDB0Pt2sEGLVFNiVlEpBgTs3IZNGER+bv2AJCbl8+gCYsASLefVQFKwkKJWUSkGBlTs/cl5QJxWzaz85ZbYfZEqF/fqwB17bWqkSyVRolZRKQY+63E5RyXLpnFvZ/8iwZb8+BmVYCS8NDkLxGRYhSsxHXs+hxee+Menn4/g9V1GtCrzzOqACVhox6ziEgxBnZoSu5d93Ld52+TH1+Te8+/mXfaXMjDV5wadGgSw5SYRUSK8v77XNK3L6xcyZTTzmfw2d2pmdyIh7VCl4SZErOISKgVK6BfP3jvPTjxRJg5kws7dODCoOOSakP3mEVEwKsA9cgj0LKlV3giIwOysqBDh6Ajk2pGPWYRkenToU8fyM6GP/0Jhg2Do44KOiqpptRjFpHqa/Vq+Mtf4A9/8IpPfPABvPWWkrIESj1mEYkZJS6fGWr3bm+lrnvv9SpA3X+/t6xmoQpQIkFQYhaRmFDi8pmhyXn2bG8pzQULIC0NRo5UsQmJKBrKFpGYUNTymfm79pAxNdt7UFAB6qyz4OefvSHrDz5QUpaIo8QsIjFhv+UzQ6z+ZSuMGgUpKfDyy3DnnbBkiTfJS+tbSwTSULaIxITGiQnkFkrOLX76nsemPw8/fgPnnAPPPacKUBLx1GMWkZgwIC2FhPg4AGrv2MZ9019k0ujbOH7zWhg9GmbNUlKWqKAes4jEhPTUZHCO+RnP02fSc/x26y+suKIbx/5zuIpNSFRRYhaR2JCdTfpdfUifPh1at4bnPuTYtm2DjkrkoGkoW0Si27Zt3vuRW7WCefO8coxz5oCSskQp9ZhFJHpNmgR9+3qFJ7p3h8ceg6SkoKMSqRD1mEUk+qxcCenpcMklcNhhkJkJY8YoKUtMUGIWkeixcycMGQItWsC0aV4PecECOPfcoCMTqTQayhaRqJA4f763lObSpXD55TB8uIpNSExSYhaRyLZ6Ndx5J6f++99w7LEwZQpccEHQUYmEjYayRSQy7d4NTz8NJ5wAb73Fih49YPFiJWWJeUrMIhJ5Zs/23u7Ur59XdGLxYlb89a+QkBB0ZCJhV6HEbGaJZvaWmS01syVmdpaZ1TOzaWa23P+sJXdEpGzWr4fevX+tAPXmm14FqObNg45MpMpU9B7zU8CHzrkrzKwGcBjwf8B059xQMxsIDATuruB1RCTGTMzKJWNqNqvy8kk+oiYjdiwg9ZmhkJfnVYAaPBjq1Ak6TJEqV+7EbGZHAB2AvwI453YCO83sMqCjf9gYIBMlZhEJMTErl0ETFpG/aw8tfvqeh155ltRVS1l36uk0mPEvbxUvkWrKnHPle6LZqcALwDfAKcCXQD8g1zmXGHLcL865A4azzaw30BsgKSmp9bhx48oVR6TasmULtWvXDjqMSqU2RY9Ib1f2ms24zVs4Y8LrnDJ1Mtvr1OG/V/fg+46dSWl0RJHPifQ2lVcstkttKptOnTp96Zxrc8AO51y5PoA2wG7gDP/xU8A/gLxCx/1S2rlat27tYs2MGTOCDqHSqU3RI6LbtXevu+WSAW5N7XpuD+ZeOfUCd/Ktr7uj757kmt09qdinRXSbKiAW26U2lQ0wzxWREytyjzkHyHHOzfEfv4V3P3mtmTVyzq02s0bATxW4hojEkuxs6NOHEdOn81XD39Hr8nv5qtHx+3Y3TtSsa5FyJ2bn3Boz+5+ZpTjnsoHOeMPa3wA9gKH+53crJVIRiV7btsEjj3hLaB52GAsHPsxfDjmFrXt+PSQhPo4BaSnBxSgSISo6K7sv8Jo/I/t74G94b8Eab2Y9gR+BP1fwGiISzUIrQHXrBhkZnJKUxMMhs7IbJyYwIC2F9NTkoKMVCVyFErNzbgHevebCOlfkvCISA1au9BYIefddaNnSqwAVUmwiPTVZiVikCFr5S0QqlypAiVSIiliISOX55BPo00cVoEQqQD1mEam41auha1fo3NnrMU+ZAm+/raQsUg5KzCJSfoUqQHH//aoAJVJBGsoWkfKZPRtuusm7f5yWBiNGqNiESCVQj1lEDo4qQImElXrMIlKigipQq3/ZSq9vZ3LHJy9Rc/Mm6N/fG7pWBSiRSqXELCLFKqgC1Sx3OU999Bxtcpcw76gT2fTP8fz+yj8EHZ5ITFJiFpFiPfPufO78cBQ9vnyfjbVq0//C23n7pN+T/P0h/D7o4ERilBKziBzIORg/nlefuJnfbvmF11IvIKNDdzbV8srercrLDzhAkdilxCwi+8vOhltugY8/5pfk4w+oAAWqAiUSTpqVLSKebdvg3nuhVSuYOxeeeYalE6exvGmL/Q5TFSiR8FKPWUSKrABFUhLpAHFxqgIlUoWUmEWqs1IqQIGqQIlUNQ1li1RHqgAlErHUYxapbgpXgBo2DJo2DToqEfGpxyxSXRRXAUpJWSSiKDGLxDpVgBKJKhrKFollqgAlEnXUYxaJQYdu3KgKUCJRSj1mkViydy+MHs0Zt98OW7eqApRIFFKPWSRWLFzI+tTToWdPfm6YTLdbnmdi19uVlEWijHrMItFu0ya4/372jhgBNb0KUM2u6cCni+OZN2ERgBYIEYki6jGLRCvn4I03vNnWTz3Fu20u5PfXP8/brTqDGQD5u/aQMTU74EBF5GAoMYtEo+xsOP98uPpqaNwY5szhjo43sDHhwGFrlWgUiS5KzCLRpIgKUMyZA23bFluKUSUaRaKLErNItJg0CU48ER5+2OspZ2fDzTdDXBwAA9JSSIiP2+8pKtEoEn00+Usk0pWhAhT8OsHLu6e8mWSVaBSJSgOmAVAAABVZSURBVErMIgGZmJVbcp3jnTvhiSfgH//wJnM99hjcdhvExxd7zoISjZmZmfTt2jH8jRCRSqfELBKAiVm5DJqwiPxdewDIzctnUOhbm1QBSqTa0j1mkQBkTM3el5QL5O/aw0tvfrZ/BajJk1UBSqSaUY9ZJACF38IUt3cP3eZP5o5PXwV2w+DBMHAgJGhGtUh1o8QsEoDGiQnk+sk5NXcpD330LCf+9D2zm7flzMmvqdiESDWmoWyRAAxIS6HRrq088uEI3nn1Tupt20i/P/0fa8ZNUFIWqebUYxapanv3kp41lQteupO4TRt5sW0Xxl90HX0uTdVbm0REiVmkSi1c6C0K8tln1DznHHj2WXq1akWvoOMSkYihoWyRqrBpE9x+O7RuDcuXw+jRMGuWt7SmiEgI9ZhFwsk5GD/eS8pr1sANN3hLatarF3RkIhKhlJhFwiU7G265BT7+2Ospv/sutG0bdFQiEuE0lC1S2UqoACUiUhr1mEUq06RJ0LcvrFgB3bpBRgYkJQUdlYhEEfWYRSrDypWQng6XXAKHHeZVgBo7VklZRA6aErNIRezcCUOHQosWMG2aVwFqwYIiyzKKiJRFhROzmcWZWZaZTfIf1zOzaWa23P9ct+JhikSgTz6BU06BQYPgggtgyRIYMKDEsowiIqWpjB5zP2BJyOOBwHTnXHNguv9YJHasXq0KUCISNhWa/GVmTYCLgIeBO/zNlwEd/a/HAJnA3RW5jkiQJmblkjE1m7UbttBnyUfckjmW+J07VAFKRMKiorOyhwN3AXVCtiU551YDOOdWm9mRFbyGSGAmZuUyaMIiUlZ+wz8/epaT1n7Hf449jfwnh3PeZe2DDk9EYpA558r3RLOLgQudczebWUfgTufcxWaW55xLDDnuF+fcAfeZzaw30BsgKSmp9bhx48oVR6TasmULtWvXDjqMSlUd27RieS5tXh/DSTOmsaVufWZ168l3bc+ixqFxpDSsU+zzglYdX6toFYvtUpvKplOnTl8659oU3l6RxDwE6AbsBmoBRwATgLZAR7+33AjIdM6llHSuNm3auHnz5pUrjkiVmZlJx44dgw6jUlWrNu3dC6NHs+GW2zli+xZeanMZT7W7hq01DwPAgB+GXlSlsR6MavVaRblYbJfaVDZmVmRiLvfkL+fcIOdcE+dcM+Bq4BPn3LXAe0AP/7AewLvlvYZIIBYuhPbtoWdP/pfUlIv+9jSP/L7nvqQM0DhR95VFJDzC8T7mocB5ZrYcOM9/LBL5iqgA9cPbH/Bj4+P2OywhPo4BaSUOAomIlFulLMnpnMvEm32Nc2490LkyzitSJUqoAJUOYEbG1GxW5eXTODGBAWkppKcmBx21iMQorZUt1VrCjz/C+eeXWAEqPTVZiVhEqowSs1RP27bBI4/Q9tFH4fDDvQpQN9wAcXFBRyYi1ZwSs1Q/IRWgfjrvPBq+8oqKTYhIxFBilupj5Uro188brm7ZEjIzWeocDZWURSSCqLqUxL7CFaAefRSyslQBSkQiknrMEts++QT69IGlS+Hyy2HYMBWbEJGIph6zxCZVgBKRKKXELDHl3bkrGXZpXzY1+x0733iTpb1ug8WL4cILgw5NRKRMlJglZswc8x7NL+3M7e+PZEHjFM6/biRdktKYuHRD0KGJiJSZErNEv/XroXdvzv3rZdTdksdNlw2k+5UPsqJeMvm79pAxNTvoCEVEykyTvyR6+RWguOsuyMvjxbZdGB5SAarAqrz8YOITESkH9ZglOoVUgKJFC8jKYvTltxyQlEGVoEQkuigxS3QJrQC1bJnXY541C1q1YkBaCgnx+y+pqUpQIhJtNJQt0aGEClAFCgpNqBKUiEQzJWaJfMuWeYuElFABqoAqQYlItNNQtkSubdvgvvugVSuYO9erADVnTrFJWUQkFqjHLJEppAIU3bpBRoYqQIlItaAes0SWlSshPR0uuQQOOwwyM2HsWCVlEak2lJglMqgClIgIoKFsCcjErNx9s6cvXr+URz5+njorvlUFKBGp9pSYpcpNzMpl0IRF1P7lZ4bNGEX6NzP5MbEhi58ew1l9uwcdnohIoJSYpco9OeUbrpw9kf6zXqHmnp08dfY1PHvmFTTYmsh/gw5ORCRgSsxStWbP5tkRN3HS2u+Y1SyVwefdyIp63vuOtaa1iIgSs1SV9eth0CB48UWOPKIBN102kA9S2oHZvkO0prWIiGZlS7jt3QsvvwwnnAAvvQT9+/PF5P+Q2erc/ZKy1rQWEfGoxyzh89VXcNNN8Nln0K4dPPcctGrFxcDuw2trTWsRkSIoMUvl27wZ7r8fnn4a6tb1eszdu8Mhvw7QaE1rEZGiKTFL5XEO3nzTqwC1enWRFaBERKRkuscslWPZMkhLg6uugoYNYfZsb+haSVlE5KAoMUvF5Of/WgHqiy9g5Ejv8+mnBx2ZiEhU0lC2lN/kyV4FqB9+gGuv9SpANWwYdFQiIlFNPWYp1cSsXNoN/YRFuRtpN/QTpk6eA126wMUXQ61aMGMGvPKKkrKISCVQj1lKVLCudf6uPRzSaBeXfPgK7Qe/zu64Qzj00UfhttugRo2gwxQRiRlKzFKijKnZ5O/aw5k/fsU1rzxLvVU5fHj8WbzQpS8T7rom6PBERGKOErOUaGfOKobNGEWXbzLZ+Nsk/nbF/cw4ri1W+lNFRKQclJilaHv2wHPPMeNfA4nfvYOnzr6a+Ou7MCP7cEDrWouIhIsSsxxozhxvKc2sLLad2YHup3VnaZ2G9K+xG9C61iIi4aRZ2fKrDRu81brOOgvWroXx4znys0xuvP6PJPs95OTEBIZc3krLaYqIhIl6zOJVgBozBu66C375xVtS84EHoE4d4Nd1rTMzM+nbtWOgoYqIxDol5uruq6/g5pvhv//1KkA9+yycfHLQUYmIVFsayq6uNm+G/v3htNMgO9urADVrlpKyiEjA1GOubgpXgOrdGx55RMUmREQihBJzjJmYlUvG1GxW5eXTODGBAWkpv07UWrYMbrkFpk2D1FSYMAHOOCPYgEVEZD/lTsxmdhQwFmgI7AVecM49ZWb1gDeAZsAK4Ern3C8VD1VKE7p8JkBuXj6DJizikO35XPrBWHj0UW9t65Ej4cYbIS4u4IhFRKSwitxj3g30d861AM4E+phZS2AgMN051xyY7j+WKlCwfGaoM5fOpvVFHeAf/4Arr/TuJ/fpo6QsIhKhyt1jds6tBlb7X282syVAMnAZ0NE/bAyQCdxdoSilTFbl5e/7uvGmn7j/4xdIWz6b5fWP8ipAdewYXHAiIlImlXKP2cyaAanAHCDJT9o451ab2ZGVcQ0pXePEBH5av4mec9/l1s9eB2DouX/lgz9czUwlZRGRqGDOuYqdwKw2MBN42Dk3wczynHOJIft/cc7VLeJ5vYHeAElJSa3HjRtXoTgizZYtW6hdu3aVXvPQOfNo+fRT1FuVw3etz2BWt+vZ9tsjSa6bQGJCfIXPH0Sbwi0W2wSx2a5YbBPEZrvUprLp1KnTl865NgfscM6V+wOIB6YCd4RsywYa+V83ArJLO0/r1q1drJkxY0bVXWz1aue6dnUO3Jbkpq5/j4dds7snubOHTHfvzM+ptMtUaZuqSCy2ybnYbFcstsm52GyX2lQ2wDxXRE6syKxsA0YBS5xzT4bseg/oAQz1P79b3mtIKfwKUNxzD2zfDvfdx+GDBvF4QgKPBx2biIiUS0XuMbcDugGLzGyBv+3/8BLyeDPrCfwI/LliIUqR5szxltKcPx/OOw+eeQaaNw86KhERqaCKzMr+D2DF7O5c3vNKKTZsgEGD4MUXoVEjGD8errgCrLiXQkREoonWyo4We/d661mnpMCoUd6SmkuXwp//rKQsIhJDtCRnNFAFKBGRakM95kimClAiItWOesyRSBWgRESqLfWYI82yZZCWBlddBUlJ8Pnn8PzzSsoiItWEEnOkyM+HwYOhVSvvrVAjRsDcuSrLKCJSzWgoOxJMmeLVSf7hB7j2WsjIgIYNg45KREQCoB5zkH78ES6/HC66yKuTPGMGvPKKkrKISDWmxByEnTvh0UehRQuYOhWGDoUFC1SWUURElJirXGYmnHoqDBzIzGNOo12PkbRzbZn49c9BRyYiIhFA95irypo1cOed8NprbE1uSv+r/s6HzVp7+/LyGTRhEQDpqckBBikiIkFTYg63IipAXRx/Fj9s3bvfYfm79pAxNVuJWUSkmtNQdjjNmQOnnw59+3pve1q0CB58kBWFknKBVXn5VRygiIhEGiXmcNiwgeOffBLOOssbwh4/3pvkdfzxADROTCjyacVtFxGR6kOJuTKFVIBqNHlysRWgBqSlkBAft99TE+LjGJCWUtURi4hIhNE95jKYmJVLxtRsVuXl0zgxgQFpKQfeCy5UAWre3/5G2549izxfwXNLPaeIiFQ7SsylmJiVy6AJi8jftQeA3MIzqDdvhgcegKeegrp1vR5z9+5snTWrxPOmpyYrEYuIyAGUmEuRMTV7X1IukL9rDxkfLiV9+X9VAUpERCqVEnMpipopfcyGXB5843lYkQWpqTBhgopNiIhIpVBiLkXjxARy/eRcc9cObp79JjfOeYtdh9b0KkDddBPExZVyFhERkbLRrOxSFMyg7vjdXKaNupl+n41jaosOfPr+p15FKCVlERGpROoxlyK9/h5O/+9wGs+YyvL6R9H3+sfpfPPVXKCJWyIiEgZKzMXZuROGDYMHH6QxwNChNL/9dkbUqBF0ZCIiEsOUmIuSmem9J3nJEujSBYYPh6ZNg45KRESqAd1jDrVmDXTrBp06eQUnJk3yZlwrKYuISBVRYgavAtTIkXDCCd661vfdB19/DRddFHRkIiJSzWgoe84cb9h6/nw47zwvQfvFJkRERKpa9e0xb9gAN95YbAUoERGRIFS/xBxSAYp//avYClAiIiJBqF5D2aEVoM4+G557Dk4+OeioRERE9qkePebNm6F/fzjtNMjOhpdegk8/VVIWEZGIE3M95v1qJ/+mFsPivuX0px70KkD16gVDhqgClIiIRKyYSsyhtZOP2ZDL3994ntNXZJF3wkkkqgKUiIhEgZhKzBlTs9m7bRu3+xWgdsTVYPAfbmBGpz/xqZKyiIhEgZhKzKvy8jl87x6u+uojpqScwyOdevJz7brYpp1BhyYiIlImMZWYvdrJkHbdM2xMqLPfdhERkWgQU7OyC2onhyblhPg4BqSlBBiViIhI2cVUjzndr5G8b1Z2YgID0lL2bRcREYl0MZWYwUvOSsQiIhKtYmooW0REJNopMYuIiEQQJWYREZEIosQsIiISQZSYRUREIogSs4iISARRYhYREYkgSswiIiIRxJxzQceAmf0MrAw6jkrWAFgXdBCVTG2KHrHYrlhsE8Rmu9SmsjnaOffbwhsjIjHHIjOb55xrE3QclUltih6x2K5YbBPEZrvUporRULaIiEgEUWIWERGJIErM4fNC0AGEgdoUPWKxXbHYJojNdqlNFaB7zCIiIhFEPWYREZEIosRcAWZ2lJnNMLMlZva1mfUr4piOZrbRzBb4H4ODiPVgmNkKM1vkxzuviP1mZk+b2bdm9pWZnRZEnGVlZikh3/8FZrbJzG4rdExUvE5m9pKZ/WRmi0O21TOzaWa23P9ct5jn/tHMsv3XbWDVRV2yYtqUYWZL/Z+vd8wssZjnlvizGqRi2vWAmeWG/JxdWMxzo+m1eiOkPSvMbEExz43I16q4v+OB/l455/RRzg+gEXCa/3UdYBnQstAxHYFJQcd6kO1aATQoYf+FwAeAAWcCc4KO+SDaFgeswXv/YNS9TkAH4DRgcci2x4CB/tcDgUeLafd3wLFADWBh4Z/VCGvT+cCh/tePFtUmf1+JP6sR2K4HgDtLeV5UvVaF9j8BDI6m16q4v+NB/l6px1wBzrnVzrn5/tebgSVAcrBRVYnLgLHOMxtINLNGQQdVRp2B75xzUbmgjXNuFrCh0ObLgDH+12OA9CKeejrwrXPue+fcTmCc/7zAFdUm59xHzrnd/sPZQJMqD6yCinmtyiKqXqsCZmbAlcDrVRpUBZXwdzyw3ysl5kpiZs2AVGBOEbvPMrOFZvaBmZ1YpYGVjwM+MrMvzax3EfuTgf+FPM4hev4huZri/3BE2+tUIMk5txq8PzLAkUUcE82v2XV4IzRFKe1nNRLd4g/Rv1TM8Gi0vlbtgbXOueXF7I/416rQ3/HAfq+UmCuBmdUG3gZuc85tKrR7Pt6w6SnACGBiVcdXDu2cc6cBFwB9zKxDof1WxHMifnq/mdUALgXeLGJ3NL5OByNaX7N7gN3Aa8UcUtrPaqR5DjgOOBVYjTf0W1hUvlbANZTcW47o16qUv+PFPq2IbRV+rZSYK8jM4vFezNeccxMK73fObXLObfG/ngLEm1mDKg7zoDjnVvmffwLewRuuCZUDHBXyuAmwqmqiq5ALgPnOubWFd0Tj6xRibcGtBP/zT0UcE3WvmZn1AC4Gujr/hl5hZfhZjSjOubXOuT3Oub3AixQdbzS+VocClwNvFHdMJL9WxfwdD+z3Som5Avx7KqOAJc65J4s5pqF/HGZ2Ot73fH3VRXlwzOxwM6tT8DXeJJzFhQ57D+juz84+E9hYMOQT4Yr9jz7aXqdC3gN6+F/3AN4t4pi5QHMzO8YfObjaf15EMrM/AncDlzrnthVzTFl+ViNKobkYXSg63qh6rXx/AJY653KK2hnJr1UJf8eD+70KekZcNH8A5+ANW3wFLPA/LgRuBG70j7kF+Bpvtt5s4Oyg4y6lTcf6sS70477H3x7aJgOewZuNuAhoE3TcZWjXYXiJ9jch26LudcL7x2I1sAvvv/WeQH1gOrDc/1zPP7YxMCXkuRfizTj9ruB1jYSPYtr0Ld69u4Lfq+cLt6m4n9VI+SimXa/4vzNf4f0BbxTtr5W/fXTB71LIsVHxWpXwdzyw3yut/CUiIhJBNJQtIiISQZSYRUREIogSs4iISARRYhYREYkgSswiIiIRRIlZREQkgigxi4iIRBAlZpFqyMza+oUUavmrMn1tZicFHZeIoAVGRKorM3sIqAUkADnOuSEBhyQiKDGLVFv+2r5zge14S5DuCTgkEUFD2SLVWT2gNlAHr+csIhFAPWaRasrM3gPGAcfgFVO4JeCQRAQ4NOgARKTqmVl3YLdz7t9mFgd8Zma/d859EnRsItWdeswiIiIRRPeYRUREIogSs4iISARRYhYREYkgSswiIiIRRIlZREQkgigxi4iIRBAlZhERkQiixCwiIhJB/h+tUQmN8whOkgAAAABJRU5ErkJggg==\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "# let's plot\n", "plot_lls_sol(x, y, w, \"Analytical Solution for min(wx-y)^2\")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "#### LLS - Gradient Descent Solution\n", "* **Pseudocode**:\n", " * **Require**: Learning rate $\\alpha_k$\n", " * **Require**: Initial parameter $w$\n", " * **While** stopping criterion not met **do**\n", " * Compute gradient: $g \\leftarrow \\frac{1}{N}\\sum_{i=1}^N 2wx_i^2 -2x_iy_i$\n", " * Apply update: $w \\leftarrow w - \\alpha_k g$\n", " * $k \\leftarrow k + 1$\n", " * **end while**" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "iter: 0 w = 0\n", "iter: 1 w = 7.1376096046222175\n", "iter: 2 w = 4.032749426611554\n", "iter: 3 w = 5.383363604046192\n", "iter: 4 w = 4.795846436862124\n", "iter: 5 w = 5.051416404587194\n", "iter: 6 w = 4.940243468626789\n", "iter: 7 w = 4.988603695769565\n", "iter: 8 w = 4.967566996962457\n", "iter: 9 w = 4.9767179609435495\n", "iter: 10 w = 4.972737291611774\n", "iter: 11 w = 4.974468882771096\n", "iter: 12 w = 4.973715640616791\n", "iter: 13 w = 4.974043300953914\n", "iter: 14 w = 4.973900768707265\n", "iter: 15 w = 4.973962770234557\n", "iter: 16 w = 4.973935799570186\n", "iter: 17 w = 4.973947531809187\n", "iter: 18 w = 4.973942428285222\n", "iter: 19 w = 4.973944648318146\n", "best w: 4.973943682603824\n" ] } ], "source": [ "# lls - gradient descent solution\n", "N = 20 # num samples\n", "num_iterations = 20\n", "alpha_k = 0.005\n", "# we want to find w that minimizes (wx-y)^2\n", "# initialize w\n", "w = 0\n", "for i in range(num_iterations):\n", " print(\"iter:\", i, \" w = \", w)\n", " gradient = np.sum(2 * w * np.square(x) - 2 * x * y) / N\n", " w = w - alpha_k * gradient\n", "print(\"best w:\", w)" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAeYAAAFNCAYAAADVSMziAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nO3de5xV8/7H8dfHmGoopgujJoSTUYRUbiklzMl1clxP0qHkktwSdRDHNQaFXA5KcZCQkEjSlJ+U0nRBTbkUTTeV6Trdv78/1prsxtyaPXvW3nvez8djP2bvtdZe+/OdNbM/+/tda38/5pxDREREosNeQQcgIiIif1JiFhERiSJKzCIiIlFEiVlERCSKKDGLiIhEESVmERGRKKLELBFnZovM7Ez//r/N7JWgY6qKzGyYmT0UxvO/N7N2FRhSwX5TzGyyma03sycrev9leP0XzezePdj+bDMbHcmYSnn9m81sQAnru5nZjZUZk1QsJeYqzswuN7NpZrbRzFb69280M4vE6znnHnHOdQ93P2bWyMycme1dwjb3m9k2/w1/vZktMLPBZlY/3NePFL9NfythfTUze9LMlpjZBjP7xcwGRiCOvyRx59zRzrmsin4toAewCtjPOdc7AvsvkXPueufcg3vwlEeAYhNjJXgJuNLMDiy8wsz6AP8BepvZg4XWVTezIWa22P9/yDazjpUUs+wBJeYqzMx6A08DmcBBQApwPdAaqFbMcxIqLcCK8bZzrhZQB+iE185vozk5l6If0BI4EagFtAeyA40ofIcCP7hyzHZU0gezSDCzVsD+zrmplfm6oZxzm4FPgKtCl5tZV+AGoC3QBrjYzHqGbLI38BtwOrA/cC8w0swaRT5q2SPOOd2q4A3vH3Mj8I9SthsGvACM9bc/EzgXLxmsw/tHv7/Qc7oAi4HVwN3AIuBMf939wP9Ctj0ZmALkAbOBdiHrsoAHga+A9cBnQD1/3a+AAzb4t1OKiH231/KXJfiv80TIsvOAWX4MU4BjQ9bdBeT6r58DdAjZz7+Bn/x13wIH++uOAsYDa/znXFro9/kc8LH/vGnAEf66yX6bNvptuqyINo0Bbi3heDXxf295wPfABYVe+yH//r+A/yv0XAf8Da8Huw3Y6sfxkb8+9DhWBwYBS/3bIKC6v64dsAToDawElgFXl/D3FfpaZ5Zx33cBy4HXi9jnv/y/mYH+7+Fn4FR/+W9+TF2L+b2UGDvQH3gl5PF/gGf9+4n+sXvcf5wEbAZqA5f5ceznr+vox39AEfG3AlYAe4cs+wcwK+RxZ2BiyONzgR/w/wb9ZQfi/Z9eUsLfyxxKeQ/QrfJvgQegW0AHHv4ObA/95y9mu2HAWrxe9F5ADf/Nq5n/+Fj/TSTD376p/wbb1n+Dfcp/nb8kZiAVL3mf4+/rLP/xAf76LLzEd6T/JpcFDPDXNcJLJMXGTxGJ2V/+ADDNv3+C/wZ8El6y7YqXgKoDaf4beYOQ1yxIon2Auf42BhwH1AX29Z9zNV4P5QS8YdqjQ36fa/B6vHsDbwAjQmJzwN9KaNM9eB9KbvSPgYWsSwR+xPvAUA04Ay/5p4W8dqmJufC2IesXhRzHB4CpeG/+B+B9oHnQX9fOP+YP+DGdA2wCapfwN/ZQoeNT2r4f849RUhH7+5e/zdX+MX3I/5095z/nbP/3UrOI30uJsQPvAH1CXusMYK5//1S8v9dpIetmh2z7hv9adfE+cJxXwnH+AegY8vh9oHfI4xOANWG+B6TgfXA4Kuj3I912v2kou+qqB6xyzm0vWGBmU8wsz8zyzaxtyLYfOOe+cs7tdM5tds5lOefm+o/nAG/hDY8BXAyMcc5Nds5twRsu21lMDFcCY51zY/19jQdm4L0ZFnjVObfAOZcPjASOr4C2L8Ub2ga4Fvivc26ac26Hc244sAWvJ78D7428qZklOucWOed+8p/XHbjHOZfjPLOdc6vxet+LnHOvOue2O+dmAu/5v5cCo5xz3/i/+zf2sE2P4iWlzni/q1x/CBM/5pp4H162Oue+wOthX7EH+y+rzsADzrmVzrnf8XqOXULWb/PXb3POjcX7sJZWQfveCdznnNvi/10U5Rf/GOwA3gYO9ve5xTn3GV4Pvbhz+SXFnoyX1At8DTQ2s7p4H0aHAKlmVhPvf2JSyLY98ZJ1Ft4oxJgSfgfD8f4/MLM6QDrwZsj69XijXuViZol4f3vDnXPzy7sfiQwl5qprNVAv9Bydc+5U51yyvy70b+O30Cea2UlmNtHMfjeztXjnpev5qxuEbu+c2+jvryiHApf4HwbyzCwPOA0IPf+7POT+JrzEE65UvF5rQQy9C8VwMF4v+UfgVrye90ozG2FmDfznHYzXOyqqTScV2l9nvHPbYbfJ//DwnHOuNV6SeBgYamZN8H/3zrnQD0KL/fZWtAb+vkNfp0HI49WhH/rYs3aWtu/fnXeetSQrQu7nAzjnCi8rLp6SYv8D79w+/j7z8T4gnY6XmCfh9fBbUygxO+fy8HrcxwC7rj73v6mwwb+96C/+H3C+n+AvBb50zi0LiakW3kjWHjOzvYDX8T6c3FSefUhkKTFXXV/j9QwvLMO2hS/KeRP4EO981v7Ai3jDueCdkzu4YEMz2wdv6K4ov+GdI0wOue3rnCvLFa/lKovmvymdD3wZEsPDhWLYxzn3FoBz7k3n3Gl4Cdfh9VYLnndEMW2aVGh/NZ1zN5Qn3pI45/Kdc8/hJYumeCMBB/ttLHAI3jnywjYC+xQ8MLODCq0v7fe7FO93Evo6S8sYemlK23eQJfHm4J1aCTUJryfcHJjuP07HO10xuWAjMzseuAZvhOmZguXO+6ZCTf92vb8sF+9/tBPeaMHrhV6zCd61EnvE/7bFELxh7H8457bt6T4k8pSYqyj/0/t/gOfN7GIzq2lme/lvHvuW8vRaeOe3NpvZicA/Q9a9C5xnZqeZWTW8c3XF/Z0V9ArSzSzBzGqYWTsza1iGJvyON6R5eBm2xcwS/V7lW3i916f8VS8D1/ujAGZm+5rZuWZWy8zSzOwMM6uOdy4uH294G+AV4EEza+w/71h/OHMMcKSZdfFfM9HMWvmvXRYrSmqTmd3q/46SzGxvfxi7Ft5FPtPwEu6d/uu2w/sQMqKIXc0Gjjaz482sBt6oQJnjwPs93mNmB5hZPbyLov5XphaWLpL7DtdY/jxtU2AS3hXSPzjntuINVXfHG07/HcD/Hf8P7/z/1XjD3aV91/g14E68awneL7TudLwrs/fUC3hJ/fwSTgNIwJSYqzDn3OPA7Xj//Cvx3oz/i3fF65QSnnoj8ICZrcd70xwZss/v8c6lvYnXe/4D7yrXol7/N7we+7/xEu1veBdVlfp36ZzbhDeM+5U/ZHxyMZteZmYb8K7O/RBvWL2Fc26pv58ZeOeZB/ux/oh38RB455cH4F28tRzvYqR/++ue8tv9Gd7V6UPwLkRaj3dx0eV4vbzl/HmhUlncDwz323RpEevz8YZBl/tx9cTr+fzsJ4UL8K74XQU8D1xV1DlE59wCvA9NnwMLgf8rtMkQvHPreVb0ZBoP4Q3hzsG7CG6mv6wiRHLfYfGvGVhrZieFLJ6Cd3FiQe/4B7wPcpNDtnkUWOKce8G/9uJK4CEza1zCy72PN3Lwvn9KCNiV5M/BOw9dZmZ2KHAd3jUNy0OGzzvvyX4k8sy5IEeFRERii5mdDdzonMuohNf6CbjOOfd5yLJeeKeR7oz060swlJhFRKKQmf0Db7TlyEIX9Emcq9RZc0REpHRmloV3QV8XJeWqRz1mERGRKKKLv0RERKKIErOIiEgUiYpzzPXq1XONGjUKOowKtXHjRvbdt7SvA8cWtSl2xGO74rFNEJ/tUpvK5ttvv13lnDug8PKoSMyNGjVixowZQYdRobKysmjXrl3QYVQotSl2xGO74rFNEJ/tUpvKxswWF7VcQ9kiIiJRRIlZREQkiigxi4iIRJGoOMdclG3btrFkyRI2by6tult02n///fnll19o2LAhiYmJQYcjIiIxImoT85IlS6hVqxaNGjXCq1QWW9atW8fWrVtZsmQJhx12WNDhiIhIjCh1KNvMhprZSjP7LmRZHTMbb2YL/Z+1Q9b1M7MfzSzHzNLLG9jmzZupW7duTCZlADOjbt26MdvjFxGRYJTlHPMw4O+FlvUFJjjnGgMT/MeYWVO8cndH+8953swSyhtcrCblArEev4iIVL6y1L2dDKwptPhC/qwFOhzICFk+wjm3xTn3C15t2xMrKFYREZG4V96rslOcc8sA/J8H+stT8YrdF1jiLxMREZEyqOiLv4oauy2yfJWZ9QB6AKSkpJCVlbXb+v3335/169dXcHh7ZtCgQVSvXp0bbriBvn378t133zFmzBiysrLIzMwkNzeXCRMmULt2bTp27Midd95Jhw4dANixYwfr169n8+bNf2lbrNqwYUPctKVAPLYJ4rNd8dgmiM92xVubqq1aRd0JE8iqpNcrb2JeYWb1nXPLzKw+sNJfvgQ4OGS7hsDSonbgnHsJeAmgZcuWrvBUZ/PmzaNWrVrlDK9inHXWWTz55JPceeedzJkzhy1btlCjRg1mzpxJ586dSUhI4I477uCkk06iWbNmZGRk7Hru+vXrqVWrFjVq1KB58+YBtqLiaJq92BGP7YrHNkF8titu2rR9Ozz3HNx7Lzu2bCGhXz845JCIv2x5E/OHQFdggP/zg5Dlb5rZU0ADoDHwTbhBcuutMGtW2LvZzfHHw6BBJW7SokULvv32W9avX0/16tU54YQTmDFjBl9++SXPPPMMTZs25Z133uHFF19kVkXHJyIiwZkyBW68EWbP5usjW7Hgumt46c0f6ZOeQEbzyJ6hLcvXpd4CvgbSzGyJmXXDS8hnmdlC4Cz/Mc6574GRwA/Ap0BP59yOSAUfaYmJiTRq1IhXX32VU089lTZt2jBx4kR++uknmjRpwqZNm1iyZAngDd2IiEiMW7UKuneH1q3ZtHwlN198D1dk9GddSn1y8/LpN2ouo7NzIxpCqT1m59wVxazqUMz2DwMPhxPUX5TSs42ktm3b8sQTTzB06FCaNWvG7bffTosWLTAz7rrrLjp37syhhx7Ktddey5gxYwKLU0REwrBzJwwdCnfdBevWQZ8+XLDv6fyYv/tm+dt2kDkuJ6K9Zs2VXYo2bdqwbNkyTjnlFFJSUqhRowZt2rRh0qRJTJ8+fVdyrlatGq+++mrQ4YqIyJ6aNQtat4Zrr4VjjvEeP/44P+UXvfnSvGJWVJConZIzWnTo0IFt27bterxgwYJd96dOnbrr/qhRoyo1LhERCdPatdC/PwweDPXqwWuvwZVXgj85VIPkJHKLSMINkpMiGpZ6zCIiUrU4B2+9BUcdBc8+C9dfD/PnQ5cuu5IyQJ/0NJISd5+8MikxgT7paRENTz1mERGpOubPh5494YsvoGVL+Ogj72cRCs4jZ47LAdaTmpxEn/S0iF+VrcQsIiLxb9MmeOgheOIJ2HdfeOEF75xyQsnlHDKap5LRPJWsrCx6dW5XKaEqMYuISFwYnZ1L5rgclubl0yC0d/vhh3DzzbB4MXTtCo8/DgceWPoOA6LELCIiMW90di79Rs0lf5s3dUZuXj6Dh4znpLlvUn/yeDj6aJg0Cdq2DTjS0ikxi4hIzMscl7MrKVfbvo3u09+n15S3cXuZN3x9882QmBhwlGWjxCwiIjGv4LvFpy6axYPjX+SINUv4OK01D51xLV/37hpwdHtGiVlERGLesXttpNvo57hg3mQWJden6yX/YdLhLUiN8HeOIyFuEnOxJ/3DcO+991KvXj1uueUWAO6++25SUlK4+eabKyJkEREJl18B6t1n7mHn5i0MbP1PXjz5YrbsXa1SvnMcCXExwUjBSf/cvHwcVNhE4926dWP48OEA7Ny5kxEjRtC5c+cKiFhERML29dfed5BvvZXENqcxadRE3j2vG1v3rkZqchKPXtQs4t85joS46DGHnvQvUBETjTdq1Ii6deuSnZ3NihUraN68OXXr1g03XBERCceqVdC3LwwZAg0bwnvvQadOnG3G2RcEHVz44iIxFzeheEVMNN69e3eGDRvG8uXLueaaa8Len4iIlFMRFaDo3x9q1gw6sgoVF0PZxU0oXhETjXfq1IlPP/2U6dOnk56eHvb+RESkHIqpABVvSRniJDFHcqLxatWq0b59ey699FISSpm6TUREKtjatXDLLdCiBfz8s1cBKivLmzAkTsXFUHboROMVeVU2eBd9TZ06lXfeeSfsfYmISBk5ByNGwO23w4oVcMMN3lzXtWsHHVnExUVihj8nGq9IP/zwA+eddx6dOnWicePGFbpvEREpxh5UgIpHcZOYI6Fp06b8/PPPQYchIlI1bNoEDz8MmZl7VAEq3igxi4hI8GKsAlQkRfXFX865oEMIS6zHLyIScYsWwQUXwIUXeldYT5oEw4ZV2aQMUZyYa9SowerVq2M2uTnnWL16NTVq1Ag6FBGR6LNlCzzyCDRt6p1LfuIJyM6OibKMkRa1Q9kNGzZkyZIl/P7770GHUi6bN28mOTmZhg0bBh2KiEh0+fxz7+KuBQvg4oth4EBvBi8BojgxJyYmcthhhwUdRrllZWXRvHnzoMMQEYkeS5dC794wYgQbGh5K/389yvspzWjwvwX0SbeYnNc6EqI2MYuISJzwK0Bx772wdSvzrrudy2ufzlrnXW1dUHgIUHImis8xi4hIHJgyZVcFKFq3hu+/p3ujc3cl5QIFhYdEiVlERCJh1Sro3t1LxqtXexWgxo6FI46IaOGheKDELCIiFWfnTup//DGkpcHw4V4FqHnz4KKLwAyIbOGheKDELCIiFcOvAJX2xBMlVoCKZOGheKDELCIi4SlUAWpev34lVoDKaJ7Koxc1IzU5CQNSk5N49KJmuvDLp6uyRUSkfIqpALVi9mya+MPWxYlE4aF4ocQsIiJ7ropXgIokDWWLiEjZbdoEd98Nxx4LM2d6FaCmTlVSrkDqMYuISLFGZ+eSOS6HpXn5XLo0m/s+/y/7LFtS5StARZISs4iIFGl0di79Rs2l7qqlvPT5fznrx29YeMChLH/5Xdp0/0fQ4cUtJWYRESnSoI/ncvXkt+g15W12mvFwu2t4teUFpKyqxVdBBxfHlJhFROSvPv+coQO7c/iaXD5Oa82DZ1zL8v3qAZqhK9KUmEVE5E8hFaCq1WlA10v+w6TDW+y2iWboiixdlS0iIl4FqKefhqOOgvffh/vvZ+bHk/km7cTdNtMMXZGnHrOISFX39dfe5CCzZ8Pf/w6DB8MRR3ABsLN6jV1XZTdITqJPepomBokwJWYRkapq1Sro2xeGDIGGDb0KUJ067So2AZqhKwgayhYRqWp27oRXXimxApQERz1mEZE4EToZSLHDzrNmecPWU6dCmzbw/PNeJSiJGmH1mM3sNjP73sy+M7O3zKyGmdUxs/FmttD/WbuighURkaIVTAaSm5ePA3Lz8uk3ai6js3O9Ddatg1tv9SpA/fQTvPYaTJqkpByFyp2YzSwVuBlo6Zw7BkgALgf6AhOcc42BCf5jERGJoMxxOeRv27HbsvxtO8j8dD689ZY3bP3MM3D99ZCTA126aNg6SoU7lL03kGRm24B9gKVAP6Cdv344kAXcFebriIhICYqa9OOI1b/xwIgXYPEcVYCKIeVOzM65XDN7AvgVyAc+c859ZmYpzrll/jbLzEwznIuIRFiD5CRy/eRcY9tmbvp6JD2mjWJztRpeBahrr4WEhICjlLIw51z5nuidO34PuAzIA94B3gUGO+eSQ7b7wzn3l/PMZtYD6AGQkpLSYsSIEeWKI1pt2LCBmjVrBh1GhVKbYkc8tise2wQV1668/G3k/pHPId9O4/TXXma/Vb8zr80Z/HLDdexTv3L7R/F4rCLRpvbt23/rnPvrEIZzrlw34BJgSMjjq4DngRygvr+sPpBT2r5atGjh4s3EiRODDqHCqU2xIx7bFY9tcq4C2/XLL25p27OcAze/3iHuhh4D3fszl1TMvvdQPB6rSLQJmOGKyInhnGP+FTjZzPbBG8ruAMwANgJdgQH+zw/CeA0RESnJli3w5JPw0EPU32svyMwk7ZZbeD4xMejIpJzCOcc8zczeBWYC24Fs4CWgJjDSzLrhJe9LKiJQEREpZMIE6NnTu8r64oth4EBvBi+JaWFdle2cuw+4r9DiLXi9ZxERiYSQClAccQR88ok3x7XEBU3JKSISK4qoAMV33ykpxxlNySkiEguKqQAl8Uc9ZhGRaLZ6tfcd5FNP9e6/9x6MHaukHMeUmEVEolFoBahhw1QBqgrRULaISLRRBagqTT1mEZFooQpQgnrMIiLBc8776tPtt8OKFV5v+aGHoLaq5lZF6jGLiARgdHYurQd8wZLp3zOjcQv45z+9yUG++Qaee05JuQpTj1lEpJKNzs7lP29Pp9vkt7jim1Fs2Ls6/+nYk+MeuJOMlocEHZ4ETIlZRKSSTRn0Kh+NfpaG61Yyr017rjyuG6v3TSb18x+VmEWJWUSk0ixaBDffzOMffUROvUO49J8DaHPOUaye670VL/XrKUvVpsQsIhJpIRWg2GsvBne8jkFHd2R7wt60YfuuzRokJwUYpEQLXfwlIhJJEybAccfB3XfDuefC/Pk0fPheEmtU322zpMQE+qSnBRSkRBP1mEVEIqGEClAZfmXGzHE5wHpSk5Pok55GRvPU4OKVqKHELCJSkbZv977udO+9sHWrVwHqrrugRo3dNstonkpG81SysrLo1bldIKFKdFJiFhGpKIUrQD37LPztb0FHJTFG55hFRMJVXAUoJWUpB/WYRURKMDo7l8xxOSzNy6dB4XPBO3fC0KHQty+sXetVgOrfH2rWDDZoiWlKzCIixRidnUu/UXPJ37YDgNy8fPqNmgtAhv2uClASEUrMIiLFyByXsyspF0jYsJ6tN90MU0dD3bpeBagrr1SNZKkwSswiIsXYbSYu57hg3mTu+eIV6m3MgxtVAUoiQxd/iYgUo2AmrsNXL+GNt+/mmY8yWVarHtf2fE4VoCRi1GMWESlG37aHkHvnPVzz9XvkJ1bnnrNv5P2W5/DwxccHHZrEMSVmEZGifPQR5/fqBYsXM/aEs+l/6lVUT63Pw5qhSyJMiVlEJNSiRXDLLfDhh3D00TBpEue0bcs5QcclVYbOMYuIgFcB6pFHoGlTr/BEZiZkZ0PbtkFHJlWMeswiIhMmQM+ekJMD//gHDBwIBx8cdFRSRanHLCJV17Jl8M9/wplnesUnPvkE3n1XSVkCpR6ziMSNEqfPDLV9uzdT1z33eBWg7rvPm1azUAUokSAoMYtIXChx+szQ5Dx1qjeV5qxZkJ4Ogwer2IREFQ1li0hcKGr6zPxtO8gcl+M9KKgAdcop8Pvv3pD1J58oKUvUUWIWkbiw2/SZIZb9sRGGDIG0NHj1VbjjDpg3z7vIS/NbSxTSULaIxIUGyUnkFkrOTVb+zOMTXoRff4DTToMXXlAFKIl66jGLSFzok55GUmICADW3bOLeCS8zZtitHLl+BQwbBpMnKylLTFCPWUTiQkbzVHCOmZkv0nPMCxyw8Q8WXdyFw/87SMUmJKYoMYtIfMjJIePOnmRMmAAtWsALn3J4q1ZBRyWyxzSULSKxbdMm7/vIzZrBjBleOcZp00BJWWKUeswiErvGjIFevbzCE1ddBY8/DikpQUclEhb1mEUk9ixeDBkZcP75sM8+kJUFw4crKUtcUGIWkdixdSs8+ig0aQLjx3s95Fmz4PTTg45MpMJoKFtEYkLyzJneVJrz58NFF8GgQSo2IXFJiVlEotuyZXDHHRz/5ptw+OEwdix07Bh0VCIRo6FsEYlO27fDM8/AUUfBu++yqGtX+O47JWWJe0rMIhJ9pk71vu50yy1e0YnvvmPRv/4FSUlBRyYScWElZjNLNrN3zWy+mc0zs1PMrI6ZjTezhf5PTbkjImWzejX06PFnBah33vEqQDVuHHRkIpUm3HPMTwOfOucuNrNqwD7Av4EJzrkBZtYX6AvcFebriEicGZ2dS+a4HJbm5ZO6X3We3TKL5s8NgLw8rwJU//5Qq1bQYYpUunInZjPbD2gL/AvAObcV2GpmFwLt/M2GA1koMYtIiNHZufQbNZf8bTtosvJnHnr9eZovnc+q40+k3sRXvFm8RKooc86V74lmxwMvAT8AxwHfArcAuc655JDt/nDO/WU428x6AD0AUlJSWowYMaJccUSrDRs2ULNmzaDDqFBqU+yI9nblLF+PW7+Bk0a9xXHjPmZzrVp8dXlXfm7XgbT6+xX5nGhvU3nFY7vUprJp3779t865ln9Z4Zwr1w1oCWwHTvIfPw08COQV2u6P0vbVokULF28mTpwYdAgVTm2KHVHdrp073U3n93HLa9ZxOzD3+vEd3bE3v+UOvWuMa3TXmGKfFtVtCkM8tkttKhtghisiJ4ZzjnkJsMQ5N81//C7e+eQVZlbfObfMzOoDK8N4DRGJJzk50LMnz06YwJyD/sa1F93DnPpH7lrdIFlXXYuUOzE755ab2W9mluacywE64A1r/wB0BQb4Pz+okEhFJHZt2gSPPOJNobnPPszu+zD/3Os4Nu74c5OkxAT6pKcFF6NIlAj3quxewBv+Fdk/A1fjfQVrpJl1A34FLgnzNUQkloVWgOrSBTIzOS4lhYdDrspukJxEn/Q0MpqnBh2tSODCSszOuVl455oL6xDOfkUkDixe7E0Q8sEH0LSpVwEqpNhERvNUJWKRImjmLxGpWKoAJRIWFbEQkYrzxRfQs6cqQImEQT1mEQnfsmXQuTN06OD1mMeOhffeU1IWKQclZhEpv0IVoLjvPlWAEgmThrJFpHymToUbbvDOH6enw7PPqtiESAVQj1lE9owqQIlElHrMIlKigipQy/7YyLU/TuL2L4ZSff066N3bG7pWBSiRCqXELCLFKqgC1Sh3IU9/9gItc+cx4+CjWfffkZxx6ZlBhycSl5SYRaRYz30wkzs+HULXbz9ibY2a9D7nNt475gxSf96LM4IOTiROKTGLyF85ByNH8r8nb+SADX/wRvOOZLa9inU1vLJ3S/PyAyaWyKIAABb0SURBVA5QJH4pMYvI7nJy4Kab4PPP+SP1yL9UgAJVgRKJJF2VLSKeTZvgnnugWTOYPh2ee475o8ez8JAmu22mKlAikaUes4gUWQGKlBQyABISVAVKpBIpMYtUZaVUgAJVgRKpbBrKFqmKVAFKJGqpxyxS1RSuADVwIBxySNBRiYhPPWaRqqK4ClBKyiJRRYlZJN6pApRITNFQtkg8UwUokZijHrNIHNp77VpVgBKJUeoxi8STnTth2DBOuu022LhRFaBEYpB6zCLxYvZsVjc/Ebp14/eDUuly04uM7nybkrJIjFGPWSTWrVsH993HzmefhepeBahGV7Tly+8SmTFqLoAmCBGJIeoxi8Qq5+Dtt72rrZ9+mg9ansMZ3V/kvWYdwAyA/G07yByXE3CgIrInlJhFYlFODpx9Nlx+OTRoANOmcXu761ib9Ndha5VoFIktSswisaSIClBMmwatWhVbilElGkViixKzSKwYMwaOPhoeftjrKefkwI03QkICAH3S00hKTNjtKSrRKBJ7dPGXSLQrQwUo+PMCL++c8npSVaJRJCYpMYsEZHR2bsl1jrduhSefhAcf9C7mevxxuPVWSEwsdp8FJRqzsrLo1bld5BshIhVOiVkkAKOzc+k3ai7523YAkJuXT7/QrzapApRIlaVzzCIByByXsyspF8jftoOh70zZvQLUxx+rApRIFaMes0gACn+FKWHnDrrM/Jjbv/wfsB3694e+fSFJV1SLVDVKzCIBaJCcRK6fnJvnzuehz57n6JU/M7VxK07++A0VmxCpwjSULRKAPulp1N+2kUc+fZb3/3cHdTat5ZZ//JvlI0YpKYtUceoxi1S2nTvJyB5Hx6F3kLBuLS+36sTIc6+h5wXN9dUmEVFiFqlUs2d7k4JMmUL1006D55/n2mbNuDbouEQkamgoW6QyrFsHt90GLVrAwoUwbBhMnuxNrSkiEkI9ZpFIcg5GjvSS8vLlcN113pSadeoEHZmIRCklZpFIycmBm26Czz/3esoffACtWgUdlYhEOQ1li1S0EipAiYiURj1mkYo0Zgz06gWLFkGXLpCZCSkpQUclIjFEPWaRirB4MWRkwPnnwz77eBWgXntNSVlE9pgSs0g4tm6FAQOgSRMYP96rADVrVpFlGUVEyiLsxGxmCWaWbWZj/Md1zGy8mS30f9YOP0yRKPTFF3DccdCvH3TsCPPmQZ8+JZZlFBEpTUX0mG8B5oU87gtMcM41Bib4j0Xix7JlqgAlIhET1sVfZtYQOBd4GLjdX3wh0M6/PxzIAu4K53VEgjQ6O5fMcTmsWLOBnvM+46as10jcukUVoEQkIsK9KnsQcCdQK2RZinNuGYBzbpmZHRjma4gEZnR2Lv1GzSVt8Q/897PnOWbFT/zf4SeQ/9QgzrqwTdDhiUgcMudc+Z5odh5wjnPuRjNrB9zhnDvPzPKcc8kh2/3hnPvLeWYz6wH0AEhJSWkxYsSIcsURrTZs2EDNmjWDDqNCVcU2LVqYS8u3hnPMxPFsqF2XyV268VOrU6i2dwJpB9Uq9nlBq4rHKlbFY7vUprJp3779t865loWXh5OYHwW6ANuBGsB+wCigFdDO7y3XB7Kcc2kl7atly5ZuxowZ5YojWmVlZdGuXbugw6hQVapNO3fCsGGsuek29tu8gaEtL+Tp1lewsfo+ABjwy4BzKzXWPVGljlWMi8d2qU1lY2ZFJuZyX/zlnOvnnGvonGsEXA584Zy7EvgQ6Opv1hX4oLyvIRKI2bOhTRvo1o3fUg7h3Kuf4ZEzuu1KygANknVeWUQiIxLfYx4AnGVmC4Gz/Mci0a+IClC/vPcJvzY4YrfNkhIT6JNe4iCQiEi5VciUnM65LLyrr3HOrQY6VMR+RSpFCRWgMgDMyByXw9K8fBokJ9EnPY2M5qlBRy0icUpzZUuVlvTrr3D22SVWgMponqpELCKVRolZqqZNm+CRR2j12GOw775eBajrroOEhKAjE5EqTolZqp6QClArzzqLg15/XcUmRCRqKDFL1bF4Mdxyizdc3bQpZGUx3zkOUlIWkSii6lIS/wpXgHrsMcjOVgUoEYlK6jFLfPviC+jZE+bPh4sugoEDVWxCRKKaeswSn1QBSkRilBKzxJUPpi9m4AW9WNfob2x9+x3mX3srfPcdnHNO0KGJiJSJErPEjUnDP6TxBR247aPBzGqQxtnXDKZTSjqj568JOjQRkTJTYpbYt3o19OjB6f+6kNob8rjhwr5cdekDLKqTSv62HWSOywk6QhGRMtPFXxK7/ApQ3Hkn5OXxcqtODAqpAFVgaV5+MPGJiJSDeswSm0IqQNGkCWRnM+yim/6SlEGVoEQktigxS2wJrQC1YIHXY548GZo1o096GkmJu0+pqUpQIhJrNJQtsaGEClAFCgpNqBKUiMQyJWaJfgsWeJOElFABqoAqQYlIrNNQtkSvTZvg3nuhWTOYPt2rADVtWrFJWUQkHqjHLNEppAIUXbpAZqYqQIlIlaAes0SXxYshIwPOPx/22QeysuC115SURaTKUGKW6KAKUCIigIayJSCjs3N3XT193ur5PPL5i9Ra9KMqQIlIlafELJVudHYu/UbNpeYfvzNw4hAyfpjEr8kH8d0zwzml11VBhyciEiglZql0T439gUunjqb35NepvmMrT596Bc+ffDH1NibzVdDBiYgETIlZKtfUqTz/7A0cs+InJjdqTv+zrmdRHe97x5rTWkREiVkqy+rV0K8fvPwyB+5Xjxsu7Msnaa3BbNcmmtNaRERXZUuk7dwJr74KRx0FQ4dC79588/H/kdXs9N2Ssua0FhHxqMcskTNnDtxwA0yZAq1bwwsvQLNmnAds37em5rQWESmCErNUvPXr4b774JlnoHZtr8d81VWw158DNJrTWkSkaErMUnGcg3fe8SpALVtWZAUoEREpmc4xS8VYsADS0+Gyy+Cgg2DqVG/oWklZRGSPKDFLePLz/6wA9c03MHiw9/PEE4OOTEQkJmkoW8rv44+9ClC//AJXXulVgDrooKCjEhGJaeoxS6lGZ+fSesAXzM1dS+sBXzDu42nQqROcdx7UqAETJ8Lrryspi4hUAPWYpUQF81rnb9vBXvW3cf6nr9Om/1tsT9iLvR97DG69FapVCzpMEZG4ocQsJcocl0P+th2c/Oscrnj9eeosXcKnR57CS516MerOK4IOT0Qk7igxS4m2LlnKwIlD6PRDFmsPSOHqi+9j4hGtsNKfKiIi5aDELEXbsQNeeIGJr/QlcfsWnj71chK7d2Jizr6A5rUWEYkUJWb5q2nTvKk0s7PZdHJbrjrhKubXOoje1bYDmtdaRCSSdFW2/GnNGm+2rlNOgRUrYORIDpySxfXd/06q30NOTU7i0YuaaTpNEZEIUY9ZvApQw4fDnXfCH394U2refz/UqgX8Oa91VlYWvTq3CzRUEZF4p8Rc1c2ZAzfeCF995VWAev55OPbYoKMSEamyNJRdVa1fD717wwknQE6OVwFq8mQlZRGRgKnHXNUUrgDVowc88oiKTYiIRAkl5jgzOjuXzHE5LM3Lp0FyEn3S0/68UGvBArjpJhg/Hpo3h1Gj4KSTgg1YRER2U+7EbGYHA68BBwE7gZecc0+bWR3gbaARsAi41Dn3R/ihSmlCp88EyM3Lp9+ouey1OZ8LPnkNHnvMm9t68GC4/npISAg4YhERKSycc8zbgd7OuSbAyUBPM2sK9AUmOOcaAxP8x1IJCqbPDHXy/Km0OLctPPggXHqpdz65Z08lZRGRKFXuHrNzbhmwzL+/3szmAanAhUA7f7PhQBZwV1hRSpkszcvfdb/BupXc9/lLpC+cysK6B3sVoNq1Cy44EREpkwo5x2xmjYDmwDQgxU/aOOeWmdmBFfEaUroGyUmsXL2ObtM/4OYpbwEw4PR/8cmZlzNJSVlEJCaYcy68HZjVBCYBDzvnRplZnnMuOWT9H8652kU8rwfQAyAlJaXFiBEjwooj2mzYsIGaNWtW6mvuPW0GTZ95mjpLl/BTi5OY3KU7mw44kNTaSSQnJYa9/yDaFGnx2CaIz3bFY5sgPtulNpVN+/btv3XOtfzLCudcuW9AIjAOuD1kWQ5Q379fH8gpbT8tWrRw8WbixImV92LLljnXubNz4DakHuJ6d33YNbprjDv10Qnu/ZlLKuxlKrVNlSQe2+RcfLYrHtvkXHy2S20qG2CGKyInhnNVtgFDgHnOuadCVn0IdAUG+D8/KO9rSCn8ClDcfTds3gz33su+/frxRFISTwQdm4iIlEs455hbA12AuWY2y1/2b7yEPNLMugG/ApeEF6IUado0byrNmTPhrLPgueegceOgoxIRkTCFc1X2/wFWzOoO5d2vlGLNGujXD15+GerXh5Ej4eKLwYo7FCIiEks0V3as2LnTm886LQ2GDPGm1Jw/Hy65RElZRCSOaErOWKAKUCIiVYZ6zNFMFaBERKoc9ZijkSpAiYhUWeoxR5sFCyA9HS67DFJS4Ouv4cUXlZRFRKoIJeZokZ8P/ftDs2beV6GefRamT1dZRhGRKkZD2dFg7FivTvIvv8CVV0JmJhx0UNBRiYhIANRjDtKvv8JFF8G553p1kidOhNdfV1IWEanClJiDsHUrPPYYNGkC48bBgAEwa5bKMoqIiBJzpcvKguOPh759mXTYCbTuOpjWrhWjv/896MhERCQK6BxzZVm+HO64A954g42ph9D7sv/waaMW3rq8fPqNmgtARvPUAIMUEZGgKTFHWhEVoM5LPIVfNu7cbbP8bTvIHJejxCwiUsVpKDuSpk2DE0+EXr28rz3NnQsPPMCiQkm5wNK8/EoOUEREoo0ScySsWcORTz0Fp5ziDWGPHOld5HXkkQA0SE4q8mnFLRcRkapDibkihVSAqv/xx8VWgOqTnkZSYsJuT01KTKBPelplRywiIlFG55jLYHR2Lpnjclial0+D5CT6pKf99VxwoQpQM66+mlbduhW5v4LnlrpPERGpcpSYSzE6O5d+o+aSv20HALmFr6Bevx7uvx+efhpq1/Z6zFddxcbJk0vcb0bzVCViERH5CyXmUmSOy9mVlAvkb9tB5qfzyVj4lSpAiYhIhVJiLkVRV0oftiaXB95+ERZlQ/PmMGqUik2IiEiFUGIuRYPkJHL95Fx92xZunPoO1097l217V/cqQN1wAyQklLIXERGRstFV2aUouIK63U/TGT/kRm6ZMoJxTdry5UdfehWhlJRFRKQCqcdcioy6Ozjxq0E0mDiOhXUPplf3J+hw4+V01IVbIiISAUrMxdm6FQYOhAceoAHAgAE0vu02nq1WLejIREQkjikxFyUry/tO8rx50KkTDBoEhxwSdFQiIlIF6BxzqOXLoUsXaN/eKzgxZox3xbWSsoiIVBIlZvAqQA0eDEcd5c1rfe+98P33cO65QUcmIiJVjIayp03zhq1nzoSzzvIStF9sQkREpLJV3R7zmjVw/fXFVoASEREJQtVLzCEVoHjllWIrQImIiAShag1lh1aAOvVUeOEFOPbYoKMSERHZpWr0mNevh9694YQTICcHhg6FL79UUhYRkagTdz3m3Won71+DgQk/cuLTD3gVoK69Fh59VBWgREQkasVVYg6tnXzYmlz+8/aLnLgom7yjjiFZFaBERCQGxFVizhyXw85Nm7jNrwC1JaEa/c+8jont/8GXSsoiIhID4ioxL83LZ9+dO7hszmeMTTuNR9p34/eatbF1W4MOTUREpEziKjF7tZMh/ZrnWJtUa7flIiIisSCursouqJ0cmpSTEhPok54WYFQiIiJlF1c95gy/RvKuq7KTk+iTnrZruYiISLSLq8QMXnJWIhYRkVgVV0PZIiIisU6JWUREJIooMYuIiEQRJWYREZEoosQsIiISRZSYRUREoogSs4iISBRRYhYREYki5pwLOgbM7HdgcdBxVLB6wKqgg6hgalPsiMd2xWObID7bpTaVzaHOuQMKL4yKxByPzGyGc65l0HFUJLUpdsRju+KxTRCf7VKbwqOhbBERkSiixCwiIhJFlJgj56WgA4gAtSl2xGO74rFNEJ/tUpvCoHPMIiIiUUQ9ZhERkSiixBwGMzvYzCaa2Twz+97Mbilim3ZmttbMZvm3/kHEuifMbJGZzfXjnVHEejOzZ8zsRzObY2YnBBFnWZlZWsjvf5aZrTOzWwttExPHycyGmtlKM/suZFkdMxtvZgv9n7WLee7fzSzHP259Ky/qkhXTpkwzm+//fb1vZsnFPLfEv9UgFdOu+80sN+Tv7JxinhtLx+rtkPYsMrNZxTw3Ko9Vce/jgf5fOed0K+cNqA+c4N+vBSwAmhbaph0wJuhY97Bdi4B6Jaw/B/gEMOBkYFrQMe9B2xKA5XjfH4y54wS0BU4AvgtZ9jjQ17/fF3ismHb/BBwOVANmF/5bjbI2nQ3s7d9/rKg2+etK/FuNwnbdD9xRyvNi6lgVWv8k0D+WjlVx7+NB/l+pxxwG59wy59xM//56YB6QGmxUleJC4DXnmQokm1n9oIMqow7AT865mJzQxjk3GVhTaPGFwHD//nAgo4inngj86Jz72Tm3FRjhPy9wRbXJOfeZc267/3Aq0LDSAwtTMceqLGLqWBUwMwMuBd6q1KDCVML7eGD/V0rMFcTMGgHNgWlFrD7FzGab2SdmdnSlBlY+DvjMzL41sx5FrE8Ffgt5vITY+UByOcW/ccTacSqQ4pxbBt6bDHBgEdvE8jG7Bm+Epiil/a1Go5v8IfqhxQyPxuqxagOscM4tLGZ91B+rQu/jgf1fKTFXADOrCbwH3OqcW1do9Uy8YdPjgGeB0ZUdXzm0ds6dAHQEeppZ20LrrYjnRP3l/WZWDbgAeKeI1bF4nPZErB6zu4HtwBvFbFLa32q0eQE4AjgeWIY39FtYTB4r4ApK7i1H9bEq5X282KcVsSzsY6XEHCYzS8Q7mG8450YVXu+cW+ec2+DfHwskmlm9Sg5zjzjnlvo/VwLv4w3XhFoCHBzyuCGwtHKiC0tHYKZzbkXhFbF4nEKsKDiV4P9cWcQ2MXfMzKwrcB7Q2fkn9Aorw99qVHHOrXDO7XDO7QRepuh4Y/FY7Q1cBLxd3DbRfKyKeR8P7P9KiTkM/jmVIcA859xTxWxzkL8dZnYi3u98deVFuWfMbF8zq1VwH+8inO8KbfYhcJV/dfbJwNqCIZ8oV+wn+lg7ToV8CHT173cFPihim+lAYzM7zB85uNx/XlQys78DdwEXOOc2FbNNWf5Wo0qhazE6UXS8MXWsfGcC851zS4paGc3HqoT38eD+r4K+Ii6Wb8BpeMMWc4BZ/u0c4Hrgen+bm4Dv8a7WmwqcGnTcpbTpcD/W2X7cd/vLQ9tkwHN4VyPOBVoGHXcZ2rUPXqLdP2RZzB0nvA8Wy4BteJ/WuwF1gQnAQv9nHX/bBsDYkOeeg3fF6U8FxzUabsW06Ue8c3cF/1cvFm5TcX+r0XIrpl2v+/8zc/DewOvH+rHylw8r+F8K2TYmjlUJ7+OB/V9p5i8REZEooqFsERGRKKLELCIiEkWUmEVERKKIErOIiEgUUWIWERGJIkrMIiIiUUSJWUREJIooMYtUQWbWyi+kUMOflel7Mzsm6LhEBE0wIlJVmdlDQA0gCVjinHs04JBEBCVmkSrLn9t3OrAZbwrSHQGHJCJoKFukKqsD1ARq4fWcRSQKqMcsUkWZ2YfACOAwvGIKNwUckogAewcdgIhUPjO7CtjunHvTzBKAKWZ2hnPui6BjE6nq1GMWERGJIjrHLCIiEkWUmEVERKKIErOIiEgUUWIWERGJIkrMIiIiUUSJWUREJIooMYuIiEQRJWYREZEo8v/J3e78IJ3W5gAAAABJRU5ErkJggg==\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "plot_lls_sol(x, y, w, \"Gradient Descent Solution for min(wx-y)^2\")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "* **Least Squares Visualization**:\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Stochastic Gradient Descent (Mini-Batch Gradient Descent)\n", "---\n", "* The main problem with (Batch) GD is that it uses the **whole** training set to compute the gradients. But what if that training set is huge? Computing the gradient can take a very long time.\n", "* *Stochastic* Gradient Descent on the other hand, samples just one instance randomly at every step and computes the gradients based on that single instance. This makes the algorithm much faster but due to its randomness, it is much less stable. Instead of steady decreasing untill reaching the minimum, the cost function will bounce up and down, **decreasing only on average**. With time, it will get *very close* to the minimum, but once it is there it will continue to bounce around!\n", "* The final parameters are good but **not optimal**." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "* When the cost function is very irregular, this bouncing can actually help the algorithm escape local minima, so SGD has better chance to find the *global* minimum.\n", "* How to find optimal parameters using SGD?\n", " * **Reduce the learning rate gradually**: this is called *learning schedule*\n", " * But don't reduce too quickly or you will get stuck at a local minimum or even frozen!\n", "* *Mini-Batch* Gradient Descent - same idea as SGD, but instead of one instance each step, $m$ samples.\n", " * Get a little bit closer to the minimum than SGD but a little harder to escape local minima." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "* **Pseudocode**:\n", " * **Require**: Learning rate $\\alpha_k$\n", " * **Require**: Initial parameter $w$\n", " * **While** stopping criterion not met **do**\n", " * Sample a minibatch of $m$ examples from the training set ($m=1$ for SGD)\n", " * Set $\\{x_1,...,x_m,\\}$ with corresponding targets $\\{y_1,...,y_m\\}$\n", " * Compute gradient: $g \\leftarrow \\frac{1}{m} \\sum_{i=1}^m f'(x_i,w)$\n", " * Apply update: $w \\leftarrow w - \\alpha_k g$\n", " * $k \\leftarrow k + 1$\n", " * **end while**" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "\n", "\n", "Image Source" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "def batch_generator(x, y, batch_size, shuffle=True):\n", " \"\"\"\n", " This function generates batches for a given dataset x.\n", " \"\"\"\n", " N = len(x)\n", " num_batches = N // batch_size\n", " batch_x = []\n", " batch_y = []\n", " if shuffle:\n", " # shuffle\n", " rand_gen = np.random.RandomState(0)\n", " shuffled_indices = rand_gen.permutation(np.arange(len(x)))\n", " x = x[shuffled_indices]\n", " y = y[shuffled_indices]\n", " for i in range(N):\n", " batch_x.append(x[i])\n", " batch_y.append(y[i])\n", " if len(batch_x) == batch_size:\n", " yield np.array(batch_x), np.array(batch_y)\n", " batch_x = []\n", " batch_y = []\n", " if batch_x:\n", " yield np.array(batch_x), np.array(batch_y)" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "total batches: 4\n", "iter: 0 batch: 0 w = 0\n", "iter: 1 batch: 0 w = 3.714921791540526\n", "iter: 2 batch: 0 w = 4.660336847464463\n", "iter: 3 batch: 0 w = 4.900936698046245\n", "iter: 4 batch: 0 w = 4.962167252538953\n", "iter: 5 batch: 0 w = 4.9777498923220564\n", "iter: 6 batch: 0 w = 4.981715537654223\n", "iter: 7 batch: 0 w = 4.982724759655079\n", "iter: 8 batch: 0 w = 4.982981597814244\n", "iter: 9 batch: 0 w = 4.983046960876035\n", "iter: 10 batch: 0 w = 4.983063595202728\n", "iter: 11 batch: 0 w = 4.983067828493167\n", "iter: 12 batch: 0 w = 4.983068905828502\n", "iter: 13 batch: 0 w = 4.983069180000908\n", "iter: 14 batch: 0 w = 4.983069249775384\n", "iter: 15 batch: 0 w = 4.983069267532377\n", "iter: 16 batch: 0 w = 4.9830692720513765\n", "iter: 17 batch: 0 w = 4.983069273201423\n", "iter: 18 batch: 0 w = 4.983069273494099\n", "iter: 19 batch: 0 w = 4.983069273568582\n", "best w: 4.983069273587538\n" ] } ], "source": [ "# mini-batch gradient descent\n", "batch_size = 5\n", "num_batches = N // batch_size\n", "print(\"total batches:\", num_batches)\n", "num_iterations = 20\n", "alpha_k = 0.001\n", "batch_gen = batch_generator(x, y, batch_size, shuffle=True)\n", "# we want to find w that minimizes (wx-y)^2\n", "# initialize w\n", "w = 0\n", "for i in range(num_iterations):\n", " for batch_i, batch in enumerate(batch_gen):\n", " batch_x, batch_y = batch\n", " if batch_i % 5 == 0:\n", " print(\"iter:\", i, \"batch:\", batch_i, \" w = \", w)\n", " gradient = np.sum(2 * w * np.square(batch_x) - 2 * batch_x * batch_y) / len(batch_x)\n", " w = w - alpha_k * gradient\n", " batch_gen = batch_generator(x, y, batch_size, shuffle=True)\n", "print(\"best w:\", w)" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAeYAAAFNCAYAAADVSMziAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nO3deXwU9f3H8dfHECAKGhVFDhWvRlGKCFqroFCr1Dv0p9aKt9YDxAtRqOJtC0XUemuLFKmI2iIiWlGBoOIFEhSVS0WRgAhqOGJAjs/vj5ngErJJSHYzu5v38/HII7szszOf787ufvb7ndn5mLsjIiIiqWGbqAMQERGRnykxi4iIpBAlZhERkRSixCwiIpJClJhFRERSiBKziIhIClFiTmFm9qiZDUz0sslmZl+a2W+jjiOWmZ1vZm/F3F9tZntHGVN9ZGZtzMzNrEENH9/TzF5NdFzhui83s6Xha2PnZGyjkm3vEW43ayseM9XMOiQzrkq23cjM5pjZrnHm72Nmt5pZ27qOLRMoMUcgTFw/mVmzctNnhh9abQDc/TJ3v6M666xq2XCbpeGb/wcze8nMdq9mvLX6MK3G+luY2T/MbHEY3xdm9i8z2z8Z2wNw9ybu/kVt1xPGeWcVy7iZlYRt+87MJprZH2q77WQJP1D/XcUync3sbTNbYWbfh0ni0ATHscXrzt2fcvfjErmdcFvZwD3AceFr47tEb6My7r4w3O6G6ixvZicDq9y9MMmhVcjd1wJPADeUn2dmuwGvAt2AV81sj3LzTzSzt8ys2My+Cd/7Tesk8DShxBydBcAfy+6YWTsgJ8nbPNndmwAtgKXAA0neXpXCnsnbwLZAF6ApcAgwBTg2zmOS8gUhydqHz30e8C/gQTO7JdqQasbMtgfGE7x+dgJaAbcBa6OMq5aaA42BT7b2gRao68/Sy4CRdbzN8kYB55lZo7IJ4Wvjf8Aodz8auBd4pdwIxA7AnUBL4ACgNTCkzqJOB+6uvzr+A74EbgKmxUy7G7gRcKBNOO1fwJ3h7a7AIqAv8C2wBLgg5vGblq1km7+NuX8CMC/m/olAIbAS+Bq4NWbewjCu1eHfr8PpfwJmA6uAT4FDYrZ1HfARsAJ4BmgcJ647gQ+BbSqJvU24/YvCWN4Ipz8HfBNu4w3gwJjH7AyMC9vzPnAH8FbMfAf2DW83Cp//hQRfWB4Fcqp63oFLgHXAT+Hz8mKc+DdtK2baacAaYOfw/g7AsHD9ReHzkhXO25fgi8oKYDnwTMx6DgReA74PY/9zOH0boD/wOfAd8CywU7nn87ywzcuBG8N5vwvbsy5s04cVtKcTUFzJ/tqG4PX9VficPQnsUG7bDeK8Lm8F/h3vdQecX24/HgFMC5+bacARMfMKwv0+leA1+irQrIJ4fwGUxGxrUjXXfVe47tLy+zembf0I3gcl4f5tTpC4VgGvAzvGeV7ixg40DLfZOrzfOLxfNv8mYD2wfcx77L7wcTOBPuH0rHD9N8fZjy+VLRsz7SMgP+b+fODomPfRZGBAucf0IvjyvV2c7fwemJWIz9ZM+Ys8gPr4V/ZhBMwl+MaYRZAM96TyxLweuB3IJkisP8a8sTctW9k2w9vbAiOAJ2PmdwXaEXyo/pLgQz4/nLfZh0Y47XSCBHIoYATJY8+Ybb1P8I14J4LkfVmcuN4l5ktAnGXKtv8ksB0/J80LCXrYjcIPnpkxjxlNkIy2Aw4KY42XmO8jSOI7het7EfhrIp738tuKmZYdrvf48P5Y4LEw3l3D5+/ScN7TBF/atiH4EO4cTm9KkMj7htObAr8K510dPretw+fnMeDpcs/nPwhGadoT9HYPCOffSpgc47Rne4JkPwI4vuy5iJl/IfAZsDfQBBgDjKzotUTliXmzZcNp55ftx3B//QCcAzQgGIH6gZ+/7BQQfDH5RdjOAmBQFa+xBlux7oUEX4waANlx3nPvEiTjVgRfUmYAHcJ9Mgm4Jc7248YebrOk3LbeAP4vvP1q+NjjY+b1CG8fFLbjAILX1LuEXwAriP8M4L2Y++3D/d4wZto44Mpafh7eB4yuzToy7U9D2dEaCZxLMGQ7hyB5VGYdcLu7r3P3lwm+3edtxfbGmlkxQS/yWGKGj9y9wN1nuftGd/+IIBkcXcm6Lgb+5u7TPPCZu38VM/9+d1/s7t8TJLqD46ynGUGvFwAzOyU89rSqgpN8bnX3EncvDWN+wt1XeXC861agvZntEJ5A838EPYESd/+YIIlswcyMoOd/jbt/7+6rgL8AZ8YsVtvnfQvuvo6gp7qTmTUnSHBXh/F+SzAEWBbDOoIvbS3dfY27l53EdhLwjbsPDaevcvf3wnmXEvSCF8U8P6eVOwxwm7uXuvuHBKMW7asZ+0qgMz8n92VmNi5sB0BP4B53/8LdVwMDgDOTcAjiRGC+u4909/Xu/jTB++jkmGWGu/u88DXzLPFfhzVZ97/c/ZNw/ro463nA3Ze6exHwJkGiKwz3yfMESTqeeLHnEvSiY00Bjg6f418C94f3GxN8eX4TIHwv3Blu+zrgHI9/XPsFYD8z2y+8fw7BaM1PMcusCuOpETM7lmDk5uaariMTKTFHayRwFkEv4MlqLP+du6+Puf8jQY9kM2b2v/BEo9Vm1jNmVr675xJ8W78CmBKeqIGZ/crMJpvZMjNbQXAMq1n5dcfYneBbeTzfxNyuMM6yNhEc8wbA3ceFMV5DMPQW6+uYNmaZ2SAz+9zMVhL0Tghj3oWgF/N1zGNjvzTE2oVgBOGD8AtBMfBKOH1TjNV53rdGeLLRLgRD0HsS9KCXxMTwGEHPGeB6glGJ983sEzO7MJxe2T7YE3g+Zn2zgQ0Evbcy1d1HW3D32e5+vru3JuiFtSTo+RDejn2+vyLYH81JrPLbKdtWq5j7NW1jddb9NVVbGnO7tIL7lcUTL/YfCEZHYk0hGN05BJhFcHjjaOBw4DN3Xx6z7AiCHvrL7j6/bGLMZ8ZqM9sj/PLwLHB2eAz9j2x5XLspUFxJG+Iys8MJjlOf5u7zarKOTKXEHKGwh7mAYHh0TALXe7wHZ3g2cfenKpi/wd3HEHxQdw4njyIYltrd3XcgOM5qZQ+pYDNfA/skINyJQH41T56JjeMs4FSCQwI7EHzQQBDzMoJh4tizzjc7MzTGcoIPyAPdPTf828GDE7Wqo6LnpjpODWN8n+C5XEtwjLAshu3d/UAAd//G3f/k7i0JesIPm9m+VL4PviYYysyN+Wsc9twS2iZ3n0MwpH9QOGkxwReDMnuEbV3KlkoIvhiV2W0r4ii/nbJtVaeNVanOumu672trPsFgT+yXhLcJRnF6AFPc/VOCeE8kSNqxHiY4ea+7mZW9/4n5zGji7gvDySMIRkCOAX5093fKresAgtGWrRL+zGsccKG7T9zax2c6JeboXQT8xt1L6mqD4VmkpwI7EvSkIPjm+727rzGzwwgSX5llwEaCY4Zl/glcZ2Ydw/Xta2blP8iq454wjpEW/PbRwp9OVDXk2JQgmX1H8MH+l7IZ4dDcGOBWM9vWgt9SnlfRStx9I8Fw7L0W/ibTzFqZWfdqxr+UzZ+XSpnZTuEoxkPAYHf/zt2XEBwXHGpm25vZNuFzcXT4mNPNrHW4ih8IEsIGgg/X3czsagt+V9rUzH4VLvcocFfZPjGzXcJ9Xt02tYn3ZcnM9jezvmUxWfCzuz8SHK+E4DDINWa2l5k1Idg3z5QbdSgzk2CYO9vMOhGcFFemotddrJeBX5jZWWbWwIKfoLUleF5qK5nrrpVw2Px1Yg41ufuPwAdAb35OxG8TfJHblJjN7BygI8Eo3ZXAiHAfxdvWOwT7YCjlesvhF4Od+Hm/V4uZHUQwKtXH3V/cmsfWF0rMEXP3z919eh1t7kUzW01wjPku4Dx3L/t5SC/gdjNbRXC859mYGH8Ml58aDo0e7u7PhdNGERxnGkvwJt0q4RDb4QRnKL8VrmsmQeK9vJKHPkkwtFhEcEZ4+Q+HKwiG/r4h6M0Nr2RdNxCcrPRuOCz+OtU/hjwMaBs+L2MrWe7D8Ln/jOD4/DXuHntc7VyCoftPCZLvf/h5iP9Q4L3w8eOAq9x9QXg8/FiC457fEPSkuoWP+Xu47KvhPn0XKEvaVXku/P+dmc2oYP6qcF3vmVlJuO6PCU5Cg+D3rSMJTjpaQLBv+8TZ1kCCXv8PBD+5GlU2o6LXXewDPfit8Unhdr8jGPI/qdywbY0kc90J8hjBMd9YUwgOibwfc78pwX7Agt8T3wec6+6r3X0UMJ3gfIbKPElwYmj537afBYwIh7y3Rl+CwzjDYobOt/pnapnM3KMajRERkZqy4Ep2fTzJFxkxs3OBS9y9c8y0RgRD2EeFJytKAikxi4hIhcxsW4KfdT3s7tU5QVUSQEPZIiKyhfA8i2UE5xyMqmJxSSD1mEVERFKIeswiIiIpRIlZREQkhaRElZ5mzZp5mzZtog4joUpKSthuu+2iDiOh1Kb0kYntysQ2QWa2S22qng8++GC5u+9SfnpKJOY2bdowfXpd/ZS3bhQUFNC1a9eow0gotSl9ZGK7MrFNkJntUpuqx8wqvFSwhrJFRERSiBKziIhIClFiFhERSSEpcYy5IuvWrWPRokWsWbMm6lBqZIcddmDBggW0bt2a7OzsqMMREZE0kbKJedGiRTRt2pQ2bdpgZlU/IMWsXLmSn376iUWLFrHXXntFHY6IiKSJlB3KXrNmDTvvvHNaJmUAM2PnnXdO2x6/iIhEo8rEbGZPmNm3ZvZxzLSdzOw1M5sf/t8xZt4AM/vMzOZuRU3beNuuzcMjl+7xi4hI3atOj/lfwO/KTesPTHT3/YCJ4X3CgvRnAgeGj3nYzLISFq2IiEiGqzIxu/sbwPflJp8KjAhvjwDyY6aPdve17r6AoCj8YQmKVUREJOPV9OSv5u6+BMDdl5jZruH0VsC7McstCqdtwcwuAS4BaN68OQUFBZvN32GHHVi1alUNw0uM++67j0aNGnH55ZfTv39/Pv74Y8aPH09BQQFDhgyhqKiIiRMnsuOOO3L88cdz/fXXc8wxxwCwYcMGVq1axZo1a7ZoW7pavXp1xrSlTCa2CTKzXZnYJsjMdmVamxouX87OEydSUEfbS/RZ2RUdVK2wrqS7Pw48DtCpUycvf6mz2bNn07Rp0wSHt3WOPfZYhg4dyvXXX89HH33E2rVrady4MTNmzKBnz55kZWVx3XXX8atf/Yp27dqRn5+/6bGrVq2iadOmNG7cmA4dOkTYisTRZfbSRya2KxPbBJnZroxp0/r18NBDMHAgG9auJWvAANhjj6RvtqaJeamZtQh7yy2Ab8Ppi4DdY5ZrDSyuTYAAXH01zJxZ69Vs5uCD4b77Kl2kY8eOfPDBB6xatYpGjRpxyCGHMH36dN58803uv/9+2rZty3PPPcejjz7KzETHJyIi0Xn7bejVCz78kHd+cSjzLr2Qx0d9Rr/uWeR3qHAgOGFq+nOpccB54e3zgBdipp9pZo3MbC9gP+D92oUYnezsbNq0acPw4cM54ogj6NKlC5MnT+bzzz/ngAMO4Mcff2TRokVAMHQjIiJpbvlyuPhiOPJIfvzmW6487Sb+mH8zK5u3oKi4lAFjZjG2sCipIVTZYzazp4GuQDMzWwTcAgwCnjWzi4CFwOkA7v6JmT0LfAqsB3q7+4ZaR1lFzzaZjjrqKO6++26eeOIJ2rVrx7XXXkvHjh0xM2644QZ69uzJnnvuyZ/+9CfGjx8fWZwiIlILGzfCE0/ADTfAypXQrx+nbHc0n5Vuvljpug0MmTA3qb3m6pyV/Ud3b+Hu2e7e2t2Huft37n6Mu+8X/v8+Zvm73H0fd89z9/8lLfI60qVLF5YsWcKvf/1rmjdvTuPGjenSpQtTpkxh2rRpm5Jzw4YNGT58eNThiojI1po5E448Ev70JzjooOD+3/7G56UVL764OM6MBEnZS3KmimOOOYZ169Ztuj9v3rxNt9999+cT0MeMGVOncYmISC2tWAE33wwPPgjNmsGTT8LZZ0N4caiWuTkUVZCEW+bmJDWslL0kp4iISFK4w9NPw/77wwMPwGWXwZw5cM45m5IyQL/ueeRkb36NrJzsLPp1z0tqeOoxi4hI/TFnDvTuDZMmQadO8OKLwf8KlB1HHjJhLrCKVrk59Ouel/SzspWYRUQk8/34I9x5J9x9N2y3HTzySHBMOavyq0bnd2hFfodWFBQU0Kdn1zoJVYlZREQywtjCIoZMmMvi4lJaxvZux42DK6+Er76C886Dv/0Ndt216hVGRIlZRETS3tjCIgaMmUXpuuAXukXFpTw47DV+NWsULd54DQ48EKZMgaOOijjSqikxi4hI2hsyYe6mpNxw/TounvY8fd5+Bt/GguHrK6+E7OyIo6weJWYREUl7Zb8tPuLLmdzx2qPs8/0iXso7kjt/8yfe6XteFY9OLUrMIiKS9n65TQkXjX2IU2a/wZe5LTjv9NuYsndHWiX5N8fJkDGJOe5B/1oYOHAgzZo146qrrgLgxhtvpHnz5lx55ZWJCFlERGorrAD1n/tvYuOatdx75Fk8evhprG3QsE5+c5wMGXGBkbKD/kXFpTgk7ELjF110ESNGjABg48aNjB49mp49eyYgYhERqbW33w5+g3z11WR36cyUMZP5z0kX8VODhrTKzeGvv2+X9N8cJ0NG9JhjD/qXScSFxtu0acPOO+9MYWEhS5cupUOHDuy88861DVdERGpj+XLo3x+GDYPWreG//4UePTjOjONOiTq42suIxBzvguKJuND4xRdfzL/+9S+++eYbLrzwwlqvT0REaqiCClDcfDM0aRJ1ZAmVEUPZ8S4onogLjffo0YNXXnmFadOm0b1791qvT0REaqCwsMIKUJmWlCFDEnMyLzTesGFDunXrxhlnnEFWFZduExGRBFuxAq66KjiW/MUXQQWogoLggiEZKiOGsmMvNJ7Is7IhOOnr3Xff5bnnnqv1ukREpJrKKkD17QtLl0KvXsG1rnNzo44s6TIiMcPPFxpPpE8//ZSTTjqJHj16sN9++yV03SIiEsfs2UEFqMmT4dBDK60AlYkyJjEnQ9u2bfniiy+iDkNEpH4oKYG77trqClCZRolZRESi98ILwfWsFy6E88+HwYNTugJUMqX0yV/uHnUItZLu8YuIJN2CBXDyyZCfD9tvD2+8AcOH19ukDCmcmBs3bsx3332XtsnN3fnuu+9o3Lhx1KGIiKSetWuDYeu2bYOzrO++G2bMgC5doo4scik7lN26dWsWLVrEsmXLog6lRtasWUNubi6tW7eOOhQRkdTy+uvByV3z5sHpp8M99wRX8BIghRNzdnY2e+21V9Rh1FhBQQEdOnSIOgwRkdSxeDFcey088wyrd2/DwAsGMXbXg2j573n0625peV3rZEjZxCwiIhli/Xp48MHg8pk//cTsy/pyZu5RrPDgbOuywkOAkjMpfIxZREQywNtvQ8eOcM010LkzfPIJF+95wqakXKas8JAoMYuISDIsXw4XXRRc3/qHH2DMGHjpJdhnn6QWHsoESswiIpI4GzfSYvx4yMsLrmt9/fXw6afQoweYAcktPJQJlJhFRCQxCgvhiCPIGzoU2rULKkANHrxFBahkFh7KBErMIiJSOytWBFft6tQJFixg9p//HFznOk4FqPwOrfjr79vRKjcHA1rl5vDX37fTiV8hnZUtIiI1E6cC1NKZMzkgHLaOJxmFhzKFErOIiGy98hWgxo8Pzr6WWtNQtoiIVF9JCfz5z9C+fXBM+ZFH4J13lJQTSD1mERGpHlWAqhPqMYuISFxjC4s47fqnmLjvYZCfz4qGOaoAlWTqMYuISIXGvfcFX/a/jX+/NZoNtg13druQZw7vwR1N9iY/6uAymBKziIhs6fXXOfiPF3DK8kWMz+vMnb+5mG+2bwYbYciEuTqjOomUmEVE5GcxFaA27NiCc0+/jTf23vzELl06M7mUmEVEZIsKUNx2GxfaYSwo2bDForp0ZnLp5C8RkfquggpQ3HwzV53UTpfOjIASs4hIfRVbAer77zerAAW6dGZUNJQtIlLfbNwIw4ZB//6wcmVQAWrgwC2KTYAunRkFJWYRkQwxtrCIIRPmsri4lJa5OfTrnrdlUi0shMsvh/feg6OPhoceiltsQqKhoWwRkQwwtrCIAWNmUVRcigNFxaUMGDOLsYVFwQIrVsBVV22qAMXIkZVWgJLo1Coxm9k1ZvaJmX1sZk+bWWMz28nMXjOz+eH/HRMVrIiIVGzIhLmUrtv8DOrSdRsY8socGDUK9t8fHngg6C3PnQtnnw1VVICSaNQ4MZtZK+BKoJO7HwRkAWcC/YGJ7r4fMDG8LyIiSVTRb4v3Wf41Qx69Fnr2hN13h2nTgp9E5eZGEKFUV22HshsAOWbWANgWWAycCowI548AXblNRCTZYn9bnPPTGvpNGcH/hvfhoG+/UAWoNFPjxOzuRcDdwEJgCbDC3V8Fmrv7knCZJYCuci4ikmT9uueRk53Fb+e/x2vDetH73ecYf1A33hr/Flx2GWRlVb0SSQnm7jV7YHDs+L/AH4Bi4DngP8CD7p4bs9wP7r7FcWYzuwS4BKB58+YdR48eXaM4UtXq1atpUsFPD9KZ2pQ+MrFdmdgmSFy7Gi9ZQpv7/s5u77/H8tZ7MPWiy/FfdSQ3JzsBUW6dTNxXyWhTt27dPnD3TlvMcPca/QGnA8Ni7p8LPAzMBVqE01oAc6taV8eOHT3TTJ48OeoQEk5tSh+Z2K5MbJN7Atq1Zo37nXe6N27svt127nff7f7TTwmJraYycV8lo03AdK8gJ9bmd8wLgcPNbFugFDgGmA6UAOcBg8L/L9RiGyIiEs/rr0Pv3jBvHpx2Gtx7L7RuHXVUUks1Tszu/p6Z/QeYAawHCoHHgSbAs2Z2EUHyPj0RgYqISCimAhT77guvvALdu0cdlSRIra785e63ALeUm7yWoPcsIiKJVEEFKK6/Hho3jjoySSBdklNEJB28/XZwcZCPPoLjjw8uFhIWm5DMoktyioiksioqQEnmUWIWEUlFGzfCP/4BeXnw5JPBkPXs2dCjhy6lmeE0lC0ikmpiK0AddRQ8/LCKTdQj6jGLiKSK8hWgnnwSCgqUlOsZ9ZhFRKLmDk8/DX37wtKl0KsX3Hmnik3UU+oxi4hEYGxhEUcOmsSi9z/mg30PUQUo2UQ9ZhGROja2sIjbnpnGxVNG8cdpz7O6QSNuPf4KDr69H/kd94g6PImYErOISB17597hvPjCA7Re+S2fdvkN57S/kO+2y6XV65+R30mJub5TYhYRqSsLFsCVVzJ4/HjmNNuT088axFEn7M93s4KP4sXFpREHKKlAiVlEJNnWroW77w5O6MrK4oETLuXvbY9nfVYDjmL9psVa5uZEGKSkCp38JSKSTK+/Dr/8Jdx0E5x0EsyZw+53DiS7caPNFsvJzqJf97yIgpRUoh6ziEgyVFIBKj+szDhkwlxgFa1yc+jXPY/8Dq2ii1dShhKziEgiVbMCVH6HVuR3aEVBQQF9enaNJlZJSUrMIiKJogpQkgA6xiwiUlvLl8PFF6sClCSEeswiIpUYW1jEkAlzWVxcSsvyx4I3boRhw6B/f1i5MhiyHjgQmjSJNmhJa0rMIiJxjC0sYsCYWZSu2wBAUXEpA8bMAiCfb1UBSpJCiVlEJI4hE+ZuSsplGqxeyU9X9IF3X4BmzYIKUGefrRrJkjBKzCIicWx2JS53Tpk9hZsmDaNZSTH0VgUoSQ6d/CUiEkfZlbj2+e5rnnrmRu5/8W4Wb9+MP/V+SBWgJGnUYxYRiaP/UbuzuN9ALnj3v5RmN+LG43oxttMJ3HXawVGHJhlMiVlEpCIvvMDJV14JCxfyUsfu3PLrc2jUqgV36QpdkmRKzCIiscIKUIwfDwcdBG+8wYldunBi1HFJvaFjzCIiEFSAuusuaNsWCgqCalAzZkCXLlFHJvWMeswiIq+/Dr17w7x5cPrpcM890Lp11FFJPaUes4jUX4sXw5lnwrHHBlfxeuUVePZZJWWJlHrMIpIxKr18Zqz164MCE7fcUmkFKJEoKDGLSEao9PKZscl56lTo1UsVoCRlaShbRDJCRZfPLF23gSET5gZ3li+Hiy6Czp3hhx9UAUpSlhKziGSEzS6fGWPJDyXw+OOQlxdc1/qGG2D2bOjRQ9e3lpSkoWwRyQgtc3MoKpecD1z6OX+b+Ch8PRuOPjqoANW2bUQRilSPeswikhH6dc8jJzsLgKZrS7jl9ccYN+Ia9ilZBiNHwuTJSsqSFtRjFpGMkN+hFbjz4eCH6fXSI+z040q+OuNc9n70XhWbkLSixCwimWH2bPL79iK/oAAOPRQeeYS9O3aMOiqRraahbBFJbyUlMGAAtG8PH34Ijz4K77wDSsqSptRjFpH05A7jxgUFJxYuhAsugMGDYZddoo5MpFaUmEUk/ZSvAPXmm8Hvk0UygIayRSR9rF0Ld975cwWooUODClBKypJB1GMWkbSw4/TpcMklMH++KkBJRlNiFpHUVlQEffvS/plnYN99YcIEOO64qKMSSRoNZYtIalq/Hu69F/bfH8aOZcEFF8CsWUrKkvGUmEUk9UydGvzc6dpr4aij4JNP+Orcc1WWUeqFWiVmM8s1s/+Y2Rwzm21mvzaznczsNTObH/7fMVHBikiGq6gC1PjxqgAl9UptjzH/HXjF3U8zs4bAtsCfgYnuPsjM+gP9gRtquR0RyTBjC4sYMmEui4tLabV9Ix748QM6PPI3WLkyqAA1cCBst13UYYrUuRonZjPbHjgKOB/A3X8CfjKzU4Gu4WIjgAKUmEUkxtjCIgaMmUXpug0cuPRz7nzyYTosmcvyjofT7MlhKjYh9Vptesx7A8uA4WbWHvgAuApo7u5LANx9iZntWvswRSSTDJkwlwarV3LLm//m3Bkv8X3O9lx9Ul+mHXE8U5WUpZ4zd6/ZA806Ae8CR7r7e2b2d2Al0Mfdc2OW+8HdtzjObGaXAJcANG/evOPo0aNrFEeqWr16NU2aNIk6jIRSm9JHSrfLnbXPvUjnUcPZduUKZv32eN457Sx+2i6It12rHSp8WEq3qRYysV1qU/V06z5C9vQAABjISURBVNbtA3fvVH56bRLzbsC77t4mvN+F4HjyvkDXsLfcAihw97zK1tWpUyefPn16jeJIVQUFBXTt2jXqMBJKbUofKduu2bOhVy8oKGBmi/246bjefLzbvptmt8rNYWr/31T40JRtUy1lYrvUpuoxswoTc42Hst39GzP72szy3H0ucAzwafh3HjAo/P9CTbchIhmipCS4lObQodCkCTP/PIieHETJhp8XycnOol/3Sr/Di9QLtT0ruw/wVHhG9hfABQQ/wXrWzC4CFgKn13IbIpKuyleAOv98GDyYg3fdlbtizspumZtDv+555HdoFXXEIpGrVWJ295nAFt1wgt6ziNRnVVSAyu/QSolYpAK68peIJJYqQInUiopYiEjivPYaXHEFzJunClAiNaQes4jU3uLFcOaZQYGJjRuDClDPPqukLFIDSswiUnPlKkBx++2qACVSSxrKFpGamTo1+E3yRx/BCSfA/fer2IRIAqjHLCJbRxWgRJJKPWYRqVRZFaglP5Rw6fzJXDNpOA1LVqsClEiSKDGLSFxlVaD2XjSPBycEFaDe36Mdq4b9nWP+r1vU4YlkJCVmEYnr4Rc+4Pr//XOzClBj23al1XzXVYREkkSJWUS25A5PP81Td/dmpx9XMrLDCdzT5WxWNg6q6ywuLo04QJHMpcQsIpubPRt694bJk1nWOo8LTrt1swpQAC1zcyIKTiTz6axsEQmUlMCAAdC+PcycCY8+yrznX+Xz3Tev+KQqUCLJpR6zSH0XpwIUu+5KPkBWlqpAidQhJWaR+qyKClCgKlAidU1D2SL1kSpAiaQs9ZhF6htVgBJJaeoxi9QX5StAvfKKKkCJpCAlZpFMV74C1G23BRWgunePOjIRqYCGskUymSpAiaQd9ZhFMlD2ihWqACWSptRjFskkGzfCsGEcdt118OOPqgAlkoaUmEUyRWEhXH45vPceJe3bkztqVPBzKBFJKxrKFkl3K1YEFwnp1Ik18z/ntjP6M/K6Wzly3DeMLSyKOjoR2UrqMYukq7ACFNdeC99+yxenn8uZe5zEt1k59LX1FBWXMmDMLABduUskjajHLJKOZs+GY46Bnj1hjz1g2jTO6XAu32ZtXvWpdN0GhkyYG1GQIlITSswi6aSCClC88w507Bi3RrJqJ4ukFyVmkXTgDi+8EJzMNWhQ0FOeMwcuvRSysoD4NZJVO1kkvSgxi6S6BQvglFMgPx+23z6oADV8OOy662aL9eueR0521mbTVDtZJP3o5C+RiIwtLKq8zvHatXD33UEVqAYNggpQffpAdnaF6yt7bHBMeRWtVDtZJC0pMYtEYGxhEQPGzKJ03QaALc+grmEFqLLayQUFBfTp2TWZTRCRJNFQtkgEhkyYuykplyldt4Hhz01VBSiRek49ZpEIlD9TOmvjBs7/4EWufuspsI1BBajrr4fGjSOKUESiosQsEoGWuTkUhcm546JPufPVhzlg2Ze884vD+PXLo1RsQqQe01C2SAT6dc+jxbrVDH757/z3qevZfk0JfU67iaVP/1dJWaSeU49ZpK5t3Ej+tJc4YdgNbLNqFY/+6v/4z/EXcMUpB+sMahFRYhapUzEVoBoefTQ8/DCXtW3LZVHHJSIpQ0PZInUhpgIUCxbAyJEwebLKMorIFtRjFkkmdxg1Cvr2hWXLoFcvuOMOyM2NOjIRSVFKzCLJMnt2kIgLCuDQQ+Gll6Bjx6ijEpEUp6FskUSLrQD14YebVYASEamKeswiiVJWAeqqq2DhQrjgAhg8GHbZJerIRCSNKDGLJMIXXwQnd730Ehx0UFABqnPnqKMSkTSkoWyR2li7Nqj+dOCBMGVKUAFqxgwlZRGpsVonZjPLMrNCMxsf3t/JzF4zs/nh/x1rH6ZICnrtNWjXDgYODOolz5kD114btyyjiEh1JKLHfBUwO+Z+f2Ciu+8HTAzvi2SOoiL4wx+CClDuMGECPPMMtNJVu0Sk9mqVmM2sNXAi8M+YyacCI8LbI4D82mxDJGpjC4s4ctAk9r1+HPef1It1v8iDcePg9tth1qwgQYuIJEhtT/66D7geaBozrbm7LwFw9yVmtmsttyESmbGFRQwYM4u2C2bxz7AC1JR9D2XtPfdx3MlHRB2eiGQgc/eaPdDsJOAEd+9lZl2B69z9JDMrdvfcmOV+cPctjjOb2SXAJQDNmzfvOHr06BrFkapWr15NkyZNog4joepjm76at4hDn/oXbd+YyKqdm/HGORfzRcdf0bBBFnm7NY37uKjVx32VrjKxXWpT9XTr1u0Dd+9UfnptEvNfgXOA9UBjYHtgDHAo0DXsLbcACtw9r7J1derUyadPn16jOFJVQUEBXbt2jTqMhKpXbdq4Ef75T4qv6st2P5Xyz0N7cP8RZ1LasDEABiwYdGKdxro16tW+SnOZ2C61qXrMrMLEXONjzO4+wN1bu3sb4ExgkrufDYwDzgsXOw94oabbEInEjBnw61/DpZfyRct9OP6CBxjc9fxNSRmgZW5OhAGKSCZLxu+YBwHHmtl84NjwvkjqKy6GPn2C61p/9RX8+98sfG48RS322myxnOws+nWvdBBIRKTGEnLlL3cvAArC298BxyRivSJ1opIKUPkAZgyZMJfFxaW0zM2hX/c88jvop1Eikhy6JKfUa9t+9RX85jdBBajDDoOXX4ZDDtlsmfwOrZSIRaTOKDFL/VRSAnfcQae774btt4fHHoOLL4ZtdJVaEYmWErPUL+UqQC393e9o8eSTqgAlIilDiVnqj9gKUO3awZtvMnf9elooKYtICtG4nWS+8hWg7rkHPvhAFaBEJCWpxyyZ7bXXoHdvmD8fzjgjSMoqNiEiKUw9ZslMsRWgQBWgRCRtKDFLZlm/Hu69F/bfP6gAdccdqgAlImlFiVkyx9SprGj7S7j2Wibtuj+n9/kHY0+8ABo1ijoyEZFq0zFmSX/LlsENN8Dw4ZRsvwv9etzIq/sdDmZ8PGYWgC4QIiJpQ4lZ0ldYAYr+/WHVKkYefSZ/OeS0zYpNlK7bwJAJc5WYRSRtaChb0lNMBSjat4cPP+Tmw8/eLCmXWVxcGkGAIiI1o8Qs6aWCClBMmgRt28YtxagSjSKSTpSYJT24w1NPBWdbP/xwUAFqzhzo2RPMAOjXPY+c7KzNHqYSjSKSbnSMWVLf7NlBIq6kAhT8fIKXSjSKSDpTYpbUFVaAYuhQaNq0WhWgVKJRRNKdErOknnIVoLjgAhg8WBWgRKReUGKW1FJBBSgVmxCR+kQnf0lqKF8BauhQVYASkXpJPWaJnipAiYhsoh6zRGJsYRGnDniG8QccBccdx+q161UBSkQE9ZglAi9M+4o5N/6Fp6aMJHvDeoZ27smIzmdw+y4Hkh91cCIiEVNilro1dSptTzuXU7/5gkl7d+KWYy/j69zdwNE1rUVEUGKWuhJTAWrbprtwSUwFqDK6prWIiBKzJFu5ClDccAPnbtuFz3/cclFd01pERCd/STJVUAGKQYPoc/LBuqa1iEgcSsySeJVUgILgspl//X07WuXmYECr3Bz++vt2Or4sIoKGsiWR3GHUKOjbNzim3KtXcK3r3NwtFtU1rUVEKqbELIlRvgLUSy9Bx45RRyUiknY0lC21U1ICAwbAL38ZHEN+7DF45x0lZRGRGlKPWWpGFaBERJJCPWap0tjCIo4cNIlZRSs4ctAkXn3xbTj5ZOjRA3bYIagA9cQTSsoiIgmgHrNUamxhEQPGzKJ03Qa22W0dPV4ezlEDn2Vdw2yyhw4Nzr7Ozo46TBGRjKHELJUaMmEupes20HlBIWeNeIQdv1nM+P278I/83rxw7R+iDk9EJOMoMUulNnz9NQ9OGsZJc96kuHkLzjnjdt7c6xDMo45MRCQzKTFLxdavhwceYNI/b2SbjRsY2rknOReeyptztwV0+UwRkWRRYpYtTZ0a/Cb5o49Y2fk3nNP+bOY32ZW+DdcDunymiEgy6axs+dmyZXDhhdC5M/zwA4wZw25vvE7vi46jVdhD1uUzRUSSSz1mqbACFAMHwnbbAT9fPrOgoIA+PbtGG6uISIZTYq7vZswIhq3few+6doWHHtpUbEJEROqehrLrq9gKUF9+uUUFKBERiYZ6zPXNVlSAEhGRuqfEnGHGFhYxZMJcFheX0jI3h37d834+UUsVoEREUl6Nh7LNbHczm2xms83sEzO7Kpy+k5m9Zmbzw/87Ji5cqUzZ5TOLiktxoKi4lAFjZvHi2/M3rwD16KOqACUikqJqc4x5PdDX3Q8ADgd6m1lboD8w0d33AyaG96UOlF0+cxN3unzyFoee2BkGDYJzzoG5c+HSS2EbnV4gIpKKajyU7e5LgCXh7VVmNhtoBZwKdA0XGwEUADfUKkqplsXFpZtu7178Dbe+/hjHfD6NObu0Ybc33wx+nywiIiktIceYzawN0AF4D2geJm3cfYmZ7ZqIbUjVWubmsGz5Si55/79c8c6zrN8mizu6XcRrx5zBG0rKIiJpwdxrV43AzJoAU4C73H2MmRW7e27M/B/cfYvjzGZ2CXAJQPPmzTuOHj26VnGkmtWrV9OkSZM63Wb21Hc58MEHyP1mMfMPO4I3e15IabNdaLVjDrk5tS/NGEWbki0T2wSZ2a5MbBNkZrvUpurp1q3bB+7eaYsZ7l7jPyAbmABcGzNtLtAivN0CmFvVejp27OiZZvLkyXW3sUWL3M84wx181e5t/OoLBnubG8b7EX+d6M/PWJSwzdRpm+pIJrbJPTPblYltcs/MdqlN1QNM9wpyYo2Hss3MgGHAbHe/J2bWOOA8YFD4/4WabkOqEFaA4uabg9u3306Tfv24t3Fj7o06NhERqZHaHGM+EjgHmGVmM8NpfyZIyM+a2UXAQuD02oUoFYqpAMUJJwQJeu+9o45KRERqqTZnZb8FWJzZx9R0vVKFZcuCIhPDh8Puu8Pzz8Opp4LF2xUiIpJO9GPWdLFxIzz+OOTlwciRQXKePRvy85WURUQyiC7JmQ5mzIDLL4f331cFKBGRDKcecyqLrQD11VeqACUiUg+ox5yKVAFKRKTeUmJONZ9+Cr17/1wB6uWX4ZBDoo5KRETqiIayU0VJCfTvD+3bBxWgHnssqAClpCwiUq+oxxw1d3jhBbjySvj6a7jwwqAS1C67RB2ZiIhEQD3mKH3xBZx8MvToERw/fustGDZMSVlEpB5TYo7C2rXByVwHHghTpsA99wQ/iTryyKgjExGRiCkx17VXX4V27eDmm3n9F4dz+LkPcuTa9oydtTTqyEREJAXoGHNdKSqCa66B555j9R57cdVZdzFx9/bBvOJSBoyZBUB+h1YRBikiIlFTYk62deuCAhO33BJUgLrjDk6iE1+u3rDZYqXrNjBkwlwlZhGRek5D2cn01lvQsWNwoZCjj4ZPPoGbbuKrckm5zOLi0joOUEREUo0SczIsW0be4MHQpQusWAFjx8KLL24qy9gyN6fCh8WbLiIi9YcScyJt3BhcGCQvj+avvRZcMOTTT7coy9ivex452VmbPTQnO4t+3fPqOmIREUkxOsZcDWMLixgyYS6Li0tpmZtDv+55Wx4LLlcBavp553HY+edXuL6yx1a5ThERqXeUmKswtrCIAWNmUbouOC5cVP4M6uJiGDgQHn44uDDIv/8NZ53Fj1OmVLre/A6tlIhFRGQLGsquwpAJczcl5TKl6zYw5JU58NRTsP/+QVLu3RvmzIGePTcbthYREdka6jFXoaIzpfddvpA7nn4EFs5SBSgREUkoJeYqtMzNoShMzjk/reHKt0dz8bTnKW20bXCi18UXwzYaeBARkcRQRqlCv+555DTYhuPmvcPr/7ycy9/7D+PaHcNb49+CSy5RUhYRkYRSj7kK+Tus5fApd7PbW5OYs0sbLjvrJn536f9xgk7cEhGRJFBijmftWvjb3+Avf2G3Bg3gnnvYv08fHm2gp0xERJJHWaYir74KV1wB8+fDGWcEZRlbqYcsIiLJpwOksYqK4A9/gO7dg/uvvgrPPKOkLCIidUaJGYIKUPfcE/wmedw4uOMOmDULjj026shERKSe0VD21KnBpTRnzYITT4T7799UbEJERKSu1d8e87JlcOGF0LlzhRWgREREolD/EvPGjfD445CXByNHxq0AJSIiEoX6NZRdrgIUDz0EbdtGHZWIiMgm9aPHXFwMffrAoYfCV18FFaAmTVJSFhGRlJNxPebNaifv0Ji/b/yUTg/cFRxT7t0bbr8dcnOjDlNERKRCGZWYY2snl1WA6rRwFt8fdDA7qQKUiIikgYxKzEMmzMV/LOGGqUEFqJKGOQzofgVvHnUqbykpi4hIGsioxLy4uJQcd075dArPH9iNQV0v4Pttd8BWro06NBERkWrJqMQc1E6G3130IKsabbfZdBERkXSQUWdl9+ueR0521mZJOSc7i37d8yKMSkREpPoyqsecH9ZI3nRWdm4O/brnbZouIiKS6jIqMUOQnJWIRUQkXWXUULaIiEi6U2IWERFJIUrMIiIiKUSJWUREJIUoMYuIiKQQJWYREZEUosQsIiKSQpSYRUREUoi5e9QxYGbLgK+ijiPBmgHLow4iwdSm9JGJ7crENkFmtkttqp493X2X8hNTIjFnIjOb7u6doo4jkdSm9JGJ7crENkFmtkttqh0NZYuIiKQQJWYREZEUosScPI9HHUASqE3pIxPblYltgsxsl9pUCzrGLCIikkLUYxYREUkhSsy1YGa7m9lkM5ttZp+Y2VUVLNPVzFaY2czw7+YoYt0aZvalmc0K451ewXwzs/vN7DMz+8jMDokizuoys7yY53+mma00s6vLLZMW+8nMnjCzb83s45hpO5nZa2Y2P/y/Y5zH/s7M5ob7rX/dRV25OG0aYmZzwtfX82aWG+exlb5WoxSnXbeaWVHM6+yEOI9Np331TEx7vjSzmXEem5L7Kt7neKTvK3fXXw3/gBbAIeHtpsA8oG25ZboC46OOdSvb9SXQrJL5JwD/Aww4HHgv6pi3om1ZwDcEvx9Mu/0EHAUcAnwcM+1vQP/wdn9gcJx2fw7sDTQEPiz/Wk2xNh0HNAhvD66oTeG8Sl+rKdiuW4HrqnhcWu2rcvOHAjen076K9zke5ftKPeZacPcl7j4jvL0KmA20ijaqOnEq8KQH3gVyzaxF1EFV0zHA5+6elhe0cfc3gO/LTT4VGBHeHgHkV/DQw4DP3P0Ld/8JGB0+LnIVtcndX3X39eHdd4HWdR5YLcXZV9WRVvuqjJkZcAbwdJ0GVUuVfI5H9r5SYk4QM2sDdADeq2D2r83sQzP7n5kdWKeB1YwDr5rZB2Z2SQXzWwFfx9xfRPp8ITmT+B8c6bafyjR39yUQfMgAu1awTDrvswsJRmgqUtVrNRVdEQ7RPxFneDRd91UXYKm7z48zP+X3VbnP8cjeV0rMCWBmTYD/Ale7+8pys2cQDJu2Bx4AxtZ1fDVwpLsfAhwP9Dazo8rNtwoek/Kn95tZQ+AU4LkKZqfjftoa6brPbgTWA0/FWaSq12qqeQTYBzgYWEIw9FteWu4r4I9U3ltO6X1Vxed43IdVMK3W+0qJuZbMLJtgZz7l7mPKz3f3le6+Orz9MpBtZs3qOMyt4u6Lw//fAs8TDNfEWgTsHnO/NbC4bqKrleOBGe6+tPyMdNxPMZaWHUoI/39bwTJpt8/M7DzgJKCnhwf0yqvGazWluPtSd9/g7huBf1BxvOm4rxoAvweeibdMKu+rOJ/jkb2vlJhrITymMgyY7e73xFlmt3A5zOwwguf8u7qLcuuY2XZm1rTsNsFJOB+XW2wccG54dvbhwIqyIZ8UF/cbfbrtp3LGAeeFt88DXqhgmWnAfma2VzhycGb4uJRkZr8DbgBOcfcf4yxTnddqSil3LkYPKo43rfZV6LfAHHdfVNHMVN5XlXyOR/e+ivqMuHT+AzoTDFt8BMwM/04ALgMuC5e5AviE4Gy9d4Ejoo67ijbtHcb6YRj3jeH02DYZ8BDB2YizgE5Rx12Ndm1LkGh3iJmWdvuJ4IvFEmAdwbf1i4CdgYnA/PD/TuGyLYGXYx57AsEZp5+X7ddU+IvTps8Ijt2Vva8eLd+meK/VVPmL066R4XvmI4IP8Bbpvq/C6f8qey/FLJsW+6qSz/HI3le68peIiEgK0VC2iIhIClFiFhERSSFKzCIiIilEiVlERCSFKDGLiIikECVmERGRFKLELCIikkKUmEXqITM7NCyk0Di8KtMnZnZQ1HGJCLrAiEh9ZWZ3Ao2BHGCRu/814pBEBCVmkXorvLbvNGANwSVIN0QckoigoWyR+mwnoAnQlKDnLCIpQD1mkXrKzMYBo4G9CIopXBFxSCICNIg6ABGpe2Z2LrDe3UeZWRbwtpn9xt0nRR2bSH2nHrOIiEgK0TFmERGRFKLELCIikkKUmEVERFKIErOIiEgKUWIWERFJIUrMIiIiKUSJWUREJIUoMYuIiKSQ/wetRt6Ixs6M3wAAAABJRU5ErkJggg==\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "# let's plot\n", "plot_lls_sol(x, y, w, \"Mini-Batch Gradient Descent Solution for min(wx-y)^2\")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### GD Comparison Summary\n", "---\n", "\n", "| Method|Accuracy | Update Speed | Memory Usage |Online Learning |\n", "|---|---|---|---|---|\n", "| **Batch** Gradient Descent | Good | Slow | High | No |\n", "| **Stochastic** Gradient Descent | Good (with softening) | Fast | Low | Yes |\n", "| **Mini-Batch** Gradient Descent | Good | Medium | Medium | Yes (depends on the MB size) |\n", "\n", "\n", "* **\"Online\"** - samples arrive while the algorithm runs (that is, when the algorithm starts running, not all samples exist)\n", "* Note: All of the Gradient Descent algorithms require **scaling** if the feaures are not within the same range!\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "#### Challenges\n", "---\n", "* Choosing a **learning rate**\n", " * Defining **learning schedule**\n", "* Working with features of different scales (e.g. heights (cm), weights (kg) and age (scalar))\n", "* Avoiding **local minima** (or *suboptimal* minima)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Mathematical Background\n", "---\n", "### Multivariate Calculus\n", "---\n", "* **The Derivative** - the derivative of $f: \\mathbb{R} \\rightarrow \\mathbb{R}$ is a *function* $f': \\mathbb{R} \\rightarrow \\mathbb{R}$ given by:\n", "$$ f'(x) = \\frac{df(x)}{dx} = \\lim_{h \\to 0} \\frac{f(x+h) - f(x)}{h}$$\n", " * Illustration: \n", " " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "* Rewrite the above: $$ \\lim_{h \\to 0} \\frac{f(x+h) - f(x) -f'(x) \\cdot h}{h}=0$$\n", " * " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "* **The Gradient** - the gradient of $f: \\mathbb{R}^N \\rightarrow \\mathbb{R}$ is a *function* $\\nabla f: \\mathbb{R}^N \\rightarrow \\mathbb{R}^N$ given by: $$ \\lim_{h \\to 0} \\frac{||f(\\overline{x}+\\overline{h}) - f(\\overline{x}) -\\nabla f(\\overline{x}) \\cdot \\overline{h}||}{||\\overline{h}||} = 0$$\n", " *
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "* The gradient can be expressed in terms of the function's **partial derivatives**: $$\\nabla f(x) = \\begin{bmatrix} \\frac{\\partial f}{\\partial x_1} \\\\ \\frac{\\partial f}{\\partial x_2} \\\\ \\vdots \\\\ \\frac{\\partial f}{\\partial x_n} \\end{bmatrix} $$\n", " * Illustration: " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "* **The Hessian Matrix**\n", " * Definition: $H(f)(x)_{i,j} = \\frac{\\partial^2}{\\partial x_i \\partial x_j} f(x)$\n", " * $$ \\begin{bmatrix} \\frac{\\partial^2 f}{\\partial x_1^2} & \\frac{\\partial^2 f}{\\partial x_1 \\partial x_2} & \\cdots & \\frac{\\partial^2 f}{\\partial x_1 \\partial x_n} \\\\ \\frac{\\partial^2 f}{\\partial x_2 x_1} & \\frac{\\partial^2 f}{\\partial x_2^2} & \\cdots & \\frac{\\partial^2 f}{\\partial x_2 \\partial x_n} \\\\ \\vdots & \\vdots & \\ddots & \\vdots \\\\ \\frac{\\partial^2 f}{\\partial x_n x_1} & \\frac{\\partial^2 f}{\\partial x_n \\partial x_2} & \\cdots & \\frac{\\partial^2 f}{\\partial x_n^2} \\end{bmatrix} $$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Matrix Calculus - Vector & Matrix Derivatives\n", "---\n", "* We will use most of the derivations \"as is\" without derivation.\n", "* A good reference: **The Matrix Cookbook**\n", "* **REMEMBER** - ALWAYS write the dimensions of each component and identify whether the expression is a **matrix, vector or scalar**!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Derivative of Vector Multiplication\n", "---\n", "* Let $x, a \\in \\mathbb{R}^N \\rightarrow x, a$ are vectors\n", "* $\\frac{\\partial x^Ta}{\\partial x} = \\frac{\\partial a^Tx}{\\partial x} = a$\n", " * $x^Ta = a^Tx$ are **scalars**\n", " * $a$ is a **vector**\n", " * Derivation: $$ f = x^Ta = [x_1, x_2, ..., x_n] \\begin{bmatrix} a_{1} \\\\a_{2} \\\\ \\vdots \\\\a_{n}\\end{bmatrix} = a_1 x_1 + a_2 x_2 + ... + a_n x_n = \\sum_{i=1}^n a_i x_i$$ $$\\frac{\\partial x^Ta}{\\partial x} = \\begin{bmatrix}\\frac{\\partial f}{\\partial x_1} \\\\ \\frac{\\partial f}{\\partial x_2} \\\\ \\vdots \\\\ \\frac{\\partial f}{\\partial x_n} \\end{bmatrix} = \\begin{bmatrix} a_{1} \\\\ a_{2} \\\\ \\vdots \\\\ a_{n} \\end{bmatrix} = a $$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "#### Common Derivations\n", "---\n", "* $\\nabla_x Ax = A^{T}$\n", "* $\\nabla_x x^{T} A x = (A + A^{T}) x$ \n", " * If $W$ is **symetric**:\n", " * $\\frac{\\partial}{\\partial s} (x-As)^T W (x-As) = -2A^TW(x-As)$\n", " * $\\frac{\\partial}{\\partial x} (x-As)^T W (x-As) = 2W(x-As)$\n", "* $\\frac{\\partial}{\\partial A} \\ln |A| = A^{-T}$\n", "* $\\frac{\\partial}{\\partial A} Tr[AB] = B^{T}$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### The Chain Rule\n", "---\n", "* Let $$ f(x) = h(g(x))$$ $$x \\in \\mathbb{R}^n $$ $$ f, g : \\mathbb{R}^n \\rightarrow \\mathbb{R}$$ $$ h: \\mathbb{R} \\rightarrow \\mathbb{R}$$\n", "* $ \\nabla f = h' \\cdot \\nabla g$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "#### Exercise 1 - The Chain Rule\n", "---\n", "Find the gradient of $f(x) = \\sqrt{x^TQx}$ ($Q$ is positive definite)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "#### Solution 1\n", "---\n", "* $g(x) = x^TQx \\rightarrow \\nabla g = (Q + Q^T) x = 2Qx$\n", "* $h(z) = \\sqrt{z} \\rightarrow h'(z) = \\frac{1}{2\\sqrt{z}}$\n", "* $\\nabla f =\\frac{1}{2\\sqrt{x^TQx}}2Qx = \\frac{Qx}{\\sqrt{x^TQx}} $" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Multi-Dimensional Optimization\n", "---\n", "### Optimality Conditions\n", "---\n", "* If $f$ has *local* optimum at $x_0$ then $\\nabla f(x_0) = 0$\n", "* If the **Hessian** is:\n", " * **Positive Definite** (all eigenvalues *positive*) at $x_0 \\rightarrow$ *local minimum*\n", " * **Negative Definite** (all eigenvalues *negative*) at $x_0 \\rightarrow$ *local maximum*\n", " * Both **positive and negative** eigenvalues at $x_0 \\rightarrow$ *saddle* point\n", " * " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Example - (Multivariate) Linear Least Squares\n", "---\n", "* **Problem Formulation**\n", " * $y \\in \\mathbb{R}^N$ - vector of values\n", " * $X \\in \\mathbb{R}^{N \\times L}$ - data matrix with $N$ examples and *$L$ features*\n", " * $w \\in \\mathbb{R}^L$ - the *parameters* to be learnt, a **weight for each feature**\n", "* **Goal**: find $w$ that best fits the measurement y, that is, find a *weighted linear combination* of the feature vector to best fit the measurment $y$\n", "* Mathematiacally, the problem is:\n", "$$\\min_w f(w;x,y) = \\min_w \\sum_{i=1}^N||x_i w-y_i||^2 $$\n", "* In vector form:\n", "$$\\min_w f(w;x,y) = \\min_w ||Xw - Y||^2 $$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "#### (Multivariate) LLS - Analytical Solution\n", "---\n", "* Mathematically:\n", "$$\\min_w f(w;x,y) = \\min_w ||Xw - Y||^2 = \\min_w (Xw-Y)^T(Xw-Y)= \\min_w (w^TX^TXw -2w^TX^TY + Y^TY)$$\n", "* The derivative: \n", "$$\\nabla_w f(w;x,y) = (X^TX + X^TX)w -2X^TY = 0 \\rightarrow w=(X^TX)^{-1}X^TY $$ $$X^TX \\in \\mathbb{R}^{L \\times L} $$" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
iddiagnosisradius_meantexture_meanperimeter_meanarea_meansmoothness_meancompactness_meanconcavity_meanconcave points_mean...texture_worstperimeter_worstarea_worstsmoothness_worstcompactness_worstconcavity_worstconcave points_worstsymmetry_worstfractal_dimension_worstUnnamed: 32
187874373B11.7117.1974.68420.30.097740.061410.038090.03239...21.3984.42521.50.13230.10400.15210.109900.25720.07097NaN
323895100M20.3421.51135.901264.00.117000.187500.256500.15040...31.86171.101938.00.15920.44920.53440.268500.55580.10240NaN
3559010258B12.5619.0781.92485.80.087600.103800.103000.04391...22.4389.02547.40.10960.20020.23880.092650.21210.07188NaN
828611555M25.2224.91171.501878.00.106300.266500.333900.18450...33.62211.702562.00.15730.60760.64760.286700.23550.10510NaN
329895633M16.2621.88107.50826.80.116500.128300.179900.07981...25.21113.70975.20.14260.21160.33440.104700.27360.07953NaN
80861103B11.4520.9773.81401.50.110200.093620.045910.02233...32.1684.53525.10.15570.16760.17550.061270.27620.08851NaN
53091858B11.7517.5675.89422.90.107300.097130.052820.04440...27.9888.52552.30.13490.18540.13660.101000.24780.07757NaN
486913102B14.6416.8594.21666.00.086410.066980.051920.02791...25.44106.00831.00.11420.20700.24370.078280.24550.06596NaN
984501001M12.4624.0483.97475.90.118600.239600.227300.08543...40.6897.65711.40.18531.05801.10500.221000.43660.20750NaN
48857155B12.0514.6378.04449.30.103100.090920.065920.02749...20.7089.88582.60.14940.21560.30500.065480.27470.08301NaN
\n", "

10 rows × 33 columns

\n", "
" ], "text/plain": [ " id diagnosis radius_mean texture_mean perimeter_mean area_mean \\\n", "187 874373 B 11.71 17.19 74.68 420.3 \n", "323 895100 M 20.34 21.51 135.90 1264.0 \n", "355 9010258 B 12.56 19.07 81.92 485.8 \n", "82 8611555 M 25.22 24.91 171.50 1878.0 \n", "329 895633 M 16.26 21.88 107.50 826.8 \n", "80 861103 B 11.45 20.97 73.81 401.5 \n", "530 91858 B 11.75 17.56 75.89 422.9 \n", "486 913102 B 14.64 16.85 94.21 666.0 \n", "9 84501001 M 12.46 24.04 83.97 475.9 \n", "48 857155 B 12.05 14.63 78.04 449.3 \n", "\n", " smoothness_mean compactness_mean concavity_mean concave points_mean \\\n", "187 0.09774 0.06141 0.03809 0.03239 \n", "323 0.11700 0.18750 0.25650 0.15040 \n", "355 0.08760 0.10380 0.10300 0.04391 \n", "82 0.10630 0.26650 0.33390 0.18450 \n", "329 0.11650 0.12830 0.17990 0.07981 \n", "80 0.11020 0.09362 0.04591 0.02233 \n", "530 0.10730 0.09713 0.05282 0.04440 \n", "486 0.08641 0.06698 0.05192 0.02791 \n", "9 0.11860 0.23960 0.22730 0.08543 \n", "48 0.10310 0.09092 0.06592 0.02749 \n", "\n", " ... texture_worst perimeter_worst area_worst smoothness_worst \\\n", "187 ... 21.39 84.42 521.5 0.1323 \n", "323 ... 31.86 171.10 1938.0 0.1592 \n", "355 ... 22.43 89.02 547.4 0.1096 \n", "82 ... 33.62 211.70 2562.0 0.1573 \n", "329 ... 25.21 113.70 975.2 0.1426 \n", "80 ... 32.16 84.53 525.1 0.1557 \n", "530 ... 27.98 88.52 552.3 0.1349 \n", "486 ... 25.44 106.00 831.0 0.1142 \n", "9 ... 40.68 97.65 711.4 0.1853 \n", "48 ... 20.70 89.88 582.6 0.1494 \n", "\n", " compactness_worst concavity_worst concave points_worst symmetry_worst \\\n", "187 0.1040 0.1521 0.10990 0.2572 \n", "323 0.4492 0.5344 0.26850 0.5558 \n", "355 0.2002 0.2388 0.09265 0.2121 \n", "82 0.6076 0.6476 0.28670 0.2355 \n", "329 0.2116 0.3344 0.10470 0.2736 \n", "80 0.1676 0.1755 0.06127 0.2762 \n", "530 0.1854 0.1366 0.10100 0.2478 \n", "486 0.2070 0.2437 0.07828 0.2455 \n", "9 1.0580 1.1050 0.22100 0.4366 \n", "48 0.2156 0.3050 0.06548 0.2747 \n", "\n", " fractal_dimension_worst Unnamed: 32 \n", "187 0.07097 NaN \n", "323 0.10240 NaN \n", "355 0.07188 NaN \n", "82 0.10510 NaN \n", "329 0.07953 NaN \n", "80 0.08851 NaN \n", "530 0.07757 NaN \n", "486 0.06596 NaN \n", "9 0.20750 NaN \n", "48 0.08301 NaN \n", "\n", "[10 rows x 33 columns]" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# let's load the cancer dataset\n", "dataset = pd.read_csv('./datasets/cancer_dataset.csv')\n", "# print the number of rows in the data set\n", "number_of_rows = len(dataset)\n", "# reminder, the data looks like this\n", "dataset.sample(10)" ] }, { "cell_type": "code", "execution_count": 32, "metadata": { "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "def plot_3d(x, y, z):\n", " %matplotlib notebook\n", " fig = plt.figure(figsize=(5, 5))\n", " ax = fig.add_subplot(111, projection='3d')\n", " ax.scatter(x, y, z)\n", " ax.set_xlabel('Radius Mean')\n", " ax.set_ylabel('Area Mean')\n", " ax.set_zlabel('Perimeter Mean')\n", " ax.set_title(\"Breast Cancer - Radius Mean vs. Area Mean vs. Perimeter Mean\")" ] }, { "cell_type": "code", "execution_count": 33, "metadata": { "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "application/javascript": [ "/* Put everything inside the global mpl namespace */\n", "window.mpl = {};\n", "\n", "\n", "mpl.get_websocket_type = function() {\n", " if (typeof(WebSocket) !== 'undefined') {\n", " return WebSocket;\n", " } else if (typeof(MozWebSocket) !== 'undefined') {\n", " return MozWebSocket;\n", " } else {\n", " alert('Your browser does not have WebSocket support. ' +\n", " 'Please try Chrome, Safari or Firefox ≥ 6. ' +\n", " 'Firefox 4 and 5 are also supported but you ' +\n", " 'have to enable WebSockets in about:config.');\n", " };\n", "}\n", "\n", "mpl.figure = function(figure_id, websocket, ondownload, parent_element) {\n", " this.id = figure_id;\n", "\n", " this.ws = websocket;\n", "\n", " this.supports_binary = (this.ws.binaryType != undefined);\n", "\n", " if (!this.supports_binary) {\n", " var warnings = document.getElementById(\"mpl-warnings\");\n", " if (warnings) {\n", " warnings.style.display = 'block';\n", " warnings.textContent = (\n", " \"This browser does not support binary websocket messages. \" +\n", " \"Performance may be slow.\");\n", " }\n", " }\n", "\n", " this.imageObj = new Image();\n", "\n", " this.context = undefined;\n", " this.message = undefined;\n", " this.canvas = undefined;\n", " this.rubberband_canvas = undefined;\n", " this.rubberband_context = undefined;\n", " this.format_dropdown = undefined;\n", "\n", " this.image_mode = 'full';\n", "\n", " this.root = $('
');\n", " this._root_extra_style(this.root)\n", " this.root.attr('style', 'display: inline-block');\n", "\n", " $(parent_element).append(this.root);\n", "\n", " this._init_header(this);\n", " this._init_canvas(this);\n", " this._init_toolbar(this);\n", "\n", " var fig = this;\n", "\n", " this.waiting = false;\n", "\n", " this.ws.onopen = function () {\n", " fig.send_message(\"supports_binary\", {value: fig.supports_binary});\n", " fig.send_message(\"send_image_mode\", {});\n", " if (mpl.ratio != 1) {\n", " fig.send_message(\"set_dpi_ratio\", {'dpi_ratio': mpl.ratio});\n", " }\n", " fig.send_message(\"refresh\", {});\n", " }\n", "\n", " this.imageObj.onload = function() {\n", " if (fig.image_mode == 'full') {\n", " // Full images could contain transparency (where diff images\n", " // almost always do), so we need to clear the canvas so that\n", " // there is no ghosting.\n", " fig.context.clearRect(0, 0, fig.canvas.width, fig.canvas.height);\n", " }\n", " fig.context.drawImage(fig.imageObj, 0, 0);\n", " };\n", "\n", " this.imageObj.onunload = function() {\n", " fig.ws.close();\n", " }\n", "\n", " this.ws.onmessage = this._make_on_message_function(this);\n", "\n", " this.ondownload = ondownload;\n", "}\n", "\n", "mpl.figure.prototype._init_header = function() {\n", " var titlebar = $(\n", " '
');\n", " var titletext = $(\n", " '
');\n", " titlebar.append(titletext)\n", " this.root.append(titlebar);\n", " this.header = titletext[0];\n", "}\n", "\n", "\n", "\n", "mpl.figure.prototype._canvas_extra_style = function(canvas_div) {\n", "\n", "}\n", "\n", "\n", "mpl.figure.prototype._root_extra_style = function(canvas_div) {\n", "\n", "}\n", "\n", "mpl.figure.prototype._init_canvas = function() {\n", " var fig = this;\n", "\n", " var canvas_div = $('
');\n", "\n", " canvas_div.attr('style', 'position: relative; clear: both; outline: 0');\n", "\n", " function canvas_keyboard_event(event) {\n", " return fig.key_event(event, event['data']);\n", " }\n", "\n", " canvas_div.keydown('key_press', canvas_keyboard_event);\n", " canvas_div.keyup('key_release', canvas_keyboard_event);\n", " this.canvas_div = canvas_div\n", " this._canvas_extra_style(canvas_div)\n", " this.root.append(canvas_div);\n", "\n", " var canvas = $('');\n", " canvas.addClass('mpl-canvas');\n", " canvas.attr('style', \"left: 0; top: 0; z-index: 0; outline: 0\")\n", "\n", " this.canvas = canvas[0];\n", " this.context = canvas[0].getContext(\"2d\");\n", "\n", " var backingStore = this.context.backingStorePixelRatio ||\n", "\tthis.context.webkitBackingStorePixelRatio ||\n", "\tthis.context.mozBackingStorePixelRatio ||\n", "\tthis.context.msBackingStorePixelRatio ||\n", "\tthis.context.oBackingStorePixelRatio ||\n", "\tthis.context.backingStorePixelRatio || 1;\n", "\n", " mpl.ratio = (window.devicePixelRatio || 1) / backingStore;\n", "\n", " var rubberband = $('');\n", " rubberband.attr('style', \"position: absolute; left: 0; top: 0; z-index: 1;\")\n", "\n", " var pass_mouse_events = true;\n", "\n", " canvas_div.resizable({\n", " start: function(event, ui) {\n", " pass_mouse_events = false;\n", " },\n", " resize: function(event, ui) {\n", " fig.request_resize(ui.size.width, ui.size.height);\n", " },\n", " stop: function(event, ui) {\n", " pass_mouse_events = true;\n", " fig.request_resize(ui.size.width, ui.size.height);\n", " },\n", " });\n", "\n", " function mouse_event_fn(event) {\n", " if (pass_mouse_events)\n", " return fig.mouse_event(event, event['data']);\n", " }\n", "\n", " rubberband.mousedown('button_press', mouse_event_fn);\n", " rubberband.mouseup('button_release', mouse_event_fn);\n", " // Throttle sequential mouse events to 1 every 20ms.\n", " rubberband.mousemove('motion_notify', mouse_event_fn);\n", "\n", " rubberband.mouseenter('figure_enter', mouse_event_fn);\n", " rubberband.mouseleave('figure_leave', mouse_event_fn);\n", "\n", " canvas_div.on(\"wheel\", function (event) {\n", " event = event.originalEvent;\n", " event['data'] = 'scroll'\n", " if (event.deltaY < 0) {\n", " event.step = 1;\n", " } else {\n", " event.step = -1;\n", " }\n", " mouse_event_fn(event);\n", " });\n", "\n", " canvas_div.append(canvas);\n", " canvas_div.append(rubberband);\n", "\n", " this.rubberband = rubberband;\n", " this.rubberband_canvas = rubberband[0];\n", " this.rubberband_context = rubberband[0].getContext(\"2d\");\n", " this.rubberband_context.strokeStyle = \"#000000\";\n", "\n", " this._resize_canvas = function(width, height) {\n", " // Keep the size of the canvas, canvas container, and rubber band\n", " // canvas in synch.\n", " canvas_div.css('width', width)\n", " canvas_div.css('height', height)\n", "\n", " canvas.attr('width', width * mpl.ratio);\n", " canvas.attr('height', height * mpl.ratio);\n", " canvas.attr('style', 'width: ' + width + 'px; height: ' + height + 'px;');\n", "\n", " rubberband.attr('width', width);\n", " rubberband.attr('height', height);\n", " }\n", "\n", " // Set the figure to an initial 600x600px, this will subsequently be updated\n", " // upon first draw.\n", " this._resize_canvas(600, 600);\n", "\n", " // Disable right mouse context menu.\n", " $(this.rubberband_canvas).bind(\"contextmenu\",function(e){\n", " return false;\n", " });\n", "\n", " function set_focus () {\n", " canvas.focus();\n", " canvas_div.focus();\n", " }\n", "\n", " window.setTimeout(set_focus, 100);\n", "}\n", "\n", "mpl.figure.prototype._init_toolbar = function() {\n", " var fig = this;\n", "\n", " var nav_element = $('
');\n", " nav_element.attr('style', 'width: 100%');\n", " this.root.append(nav_element);\n", "\n", " // Define a callback function for later on.\n", " function toolbar_event(event) {\n", " return fig.toolbar_button_onclick(event['data']);\n", " }\n", " function toolbar_mouse_event(event) {\n", " return fig.toolbar_button_onmouseover(event['data']);\n", " }\n", "\n", " for(var toolbar_ind in mpl.toolbar_items) {\n", " var name = mpl.toolbar_items[toolbar_ind][0];\n", " var tooltip = mpl.toolbar_items[toolbar_ind][1];\n", " var image = mpl.toolbar_items[toolbar_ind][2];\n", " var method_name = mpl.toolbar_items[toolbar_ind][3];\n", "\n", " if (!name) {\n", " // put a spacer in here.\n", " continue;\n", " }\n", " var button = $('');\n", " button.click(method_name, toolbar_event);\n", " button.mouseover(tooltip, toolbar_mouse_event);\n", " nav_element.append(button);\n", " }\n", "\n", " // Add the status bar.\n", " var status_bar = $('');\n", " nav_element.append(status_bar);\n", " this.message = status_bar[0];\n", "\n", " // Add the close button to the window.\n", " var buttongrp = $('
');\n", " var button = $('');\n", " button.click(function (evt) { fig.handle_close(fig, {}); } );\n", " button.mouseover('Stop Interaction', toolbar_mouse_event);\n", " buttongrp.append(button);\n", " var titlebar = this.root.find($('.ui-dialog-titlebar'));\n", " titlebar.prepend(buttongrp);\n", "}\n", "\n", "mpl.figure.prototype._root_extra_style = function(el){\n", " var fig = this\n", " el.on(\"remove\", function(){\n", "\tfig.close_ws(fig, {});\n", " });\n", "}\n", "\n", "mpl.figure.prototype._canvas_extra_style = function(el){\n", " // this is important to make the div 'focusable\n", " el.attr('tabindex', 0)\n", " // reach out to IPython and tell the keyboard manager to turn it's self\n", " // off when our div gets focus\n", "\n", " // location in version 3\n", " if (IPython.notebook.keyboard_manager) {\n", " IPython.notebook.keyboard_manager.register_events(el);\n", " }\n", " else {\n", " // location in version 2\n", " IPython.keyboard_manager.register_events(el);\n", " }\n", "\n", "}\n", "\n", "mpl.figure.prototype._key_event_extra = function(event, name) {\n", " var manager = IPython.notebook.keyboard_manager;\n", " if (!manager)\n", " manager = IPython.keyboard_manager;\n", "\n", " // Check for shift+enter\n", " if (event.shiftKey && event.which == 13) {\n", " this.canvas_div.blur();\n", " event.shiftKey = false;\n", " // Send a \"J\" for go to next cell\n", " event.which = 74;\n", " event.keyCode = 74;\n", " manager.command_mode();\n", " manager.handle_keydown(event);\n", " }\n", "}\n", "\n", "mpl.figure.prototype.handle_save = function(fig, msg) {\n", " fig.ondownload(fig, null);\n", "}\n", "\n", "\n", "mpl.find_output_cell = function(html_output) {\n", " // Return the cell and output element which can be found *uniquely* in the notebook.\n", " // Note - this is a bit hacky, but it is done because the \"notebook_saving.Notebook\"\n", " // IPython event is triggered only after the cells have been serialised, which for\n", " // our purposes (turning an active figure into a static one), is too late.\n", " var cells = IPython.notebook.get_cells();\n", " var ncells = cells.length;\n", " for (var i=0; i= 3 moved mimebundle to data attribute of output\n", " data = data.data;\n", " }\n", " if (data['text/html'] == html_output) {\n", " return [cell, data, j];\n", " }\n", " }\n", " }\n", " }\n", "}\n", "\n", "// Register the function which deals with the matplotlib target/channel.\n", "// The kernel may be null if the page has been refreshed.\n", "if (IPython.notebook.kernel != null) {\n", " IPython.notebook.kernel.comm_manager.register_target('matplotlib', mpl.mpl_figure_comm);\n", "}\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# plot\n", "plot_3d_lls(xs, ys, zs, lls_sol, \"Breast Cancer - Radius Mean vs. Area Mean vs. Perimeter Mean - LLS Analyitical\")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## What If L is Very Large???\n", "If $L = 1000$, we would need to invert a $1000 \\times 1000$ matrix, which would take about $10^9$ operations!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### (Batch) Gradient Descent\n", "---\n", "* **Pseudocode**:\n", " * **Require**: Learning rate $\\alpha_k$\n", " * **Require**: Initial parameter vector $w$\n", " * **While** stopping criterion not met **do**\n", " * Compute gradient: $g \\leftarrow \\nabla f(x,w)$ \n", " * Apply update: $w \\leftarrow w - \\alpha_k g$\n", " * $k \\leftarrow k + 1$\n", " * **end while**" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "* For **Linear Least Squares**:\n", " * **Require**: Learning rate $\\alpha_k$\n", " * **Require**: Initial parameter vector $w$\n", " * **While** stopping criterion not met **do**\n", " * Compute gradient: $g \\leftarrow 2X^TXw - 2X^Ty$ \n", " * Apply update: $w \\leftarrow w - \\alpha_k g$\n", " * $k \\leftarrow k + 1$\n", " * **end while**" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": false, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "# multivariate lls - gradient descent solution\n", "X = dataset[['radius_mean', 'area_mean']].values\n", "Y = dataset[['perimeter_mean']].values\n", "# Scaling\n", "X = (X - X.mean(axis=0, keepdims=True)) / X.std(axis=0, keepdims=True)\n", "Y = (Y - Y.mean(axis=0, keepdims=True)) / Y.std(axis=0, keepdims=True)\n", "num_iterations = 20\n", "alpha_k = 0.0001\n", "L = X.shape[1]\n", "# initialize w\n", "w = np.zeros((L, 1))\n", "for i in range(num_iterations):\n", " print(\"iter:\", i, \" w = \")\n", " print(w)\n", " gradient = 2 * X.T @ X @ w - 2 * X.T @ Y\n", " w = w - alpha_k * gradient\n", "lls_sol = X @ w\n", "print(\"w:\")\n", "print(w)" ] }, { "cell_type": "code", "execution_count": 38, "metadata": { "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "application/javascript": [ "/* Put everything inside the global mpl namespace */\n", "window.mpl = {};\n", "\n", "\n", "mpl.get_websocket_type = function() {\n", " if (typeof(WebSocket) !== 'undefined') {\n", " return WebSocket;\n", " } else if (typeof(MozWebSocket) !== 'undefined') {\n", " return MozWebSocket;\n", " } else {\n", " alert('Your browser does not have WebSocket support. ' +\n", " 'Please try Chrome, Safari or Firefox ≥ 6. ' +\n", " 'Firefox 4 and 5 are also supported but you ' +\n", " 'have to enable WebSockets in about:config.');\n", " };\n", "}\n", "\n", "mpl.figure = function(figure_id, websocket, ondownload, parent_element) {\n", " this.id = figure_id;\n", "\n", " this.ws = websocket;\n", "\n", " this.supports_binary = (this.ws.binaryType != undefined);\n", "\n", " if (!this.supports_binary) {\n", " var warnings = document.getElementById(\"mpl-warnings\");\n", " if (warnings) {\n", " warnings.style.display = 'block';\n", " warnings.textContent = (\n", " \"This browser does not support binary websocket messages. \" +\n", " \"Performance may be slow.\");\n", " }\n", " }\n", "\n", " this.imageObj = new Image();\n", "\n", " this.context = undefined;\n", " this.message = undefined;\n", " this.canvas = undefined;\n", " this.rubberband_canvas = undefined;\n", " this.rubberband_context = undefined;\n", " this.format_dropdown = undefined;\n", "\n", " this.image_mode = 'full';\n", "\n", " this.root = $('
');\n", " this._root_extra_style(this.root)\n", " this.root.attr('style', 'display: inline-block');\n", "\n", " $(parent_element).append(this.root);\n", "\n", " this._init_header(this);\n", " this._init_canvas(this);\n", " this._init_toolbar(this);\n", "\n", " var fig = this;\n", "\n", " this.waiting = false;\n", "\n", " this.ws.onopen = function () {\n", " fig.send_message(\"supports_binary\", {value: fig.supports_binary});\n", " fig.send_message(\"send_image_mode\", {});\n", " if (mpl.ratio != 1) {\n", " fig.send_message(\"set_dpi_ratio\", {'dpi_ratio': mpl.ratio});\n", " }\n", " fig.send_message(\"refresh\", {});\n", " }\n", "\n", " this.imageObj.onload = function() {\n", " if (fig.image_mode == 'full') {\n", " // Full images could contain transparency (where diff images\n", " // almost always do), so we need to clear the canvas so that\n", " // there is no ghosting.\n", " fig.context.clearRect(0, 0, fig.canvas.width, fig.canvas.height);\n", " }\n", " fig.context.drawImage(fig.imageObj, 0, 0);\n", " };\n", "\n", " this.imageObj.onunload = function() {\n", " fig.ws.close();\n", " }\n", "\n", " this.ws.onmessage = this._make_on_message_function(this);\n", "\n", " this.ondownload = ondownload;\n", "}\n", "\n", "mpl.figure.prototype._init_header = function() {\n", " var titlebar = $(\n", " '
');\n", " var titletext = $(\n", " '
');\n", " titlebar.append(titletext)\n", " this.root.append(titlebar);\n", " this.header = titletext[0];\n", "}\n", "\n", "\n", "\n", "mpl.figure.prototype._canvas_extra_style = function(canvas_div) {\n", "\n", "}\n", "\n", "\n", "mpl.figure.prototype._root_extra_style = function(canvas_div) {\n", "\n", "}\n", "\n", "mpl.figure.prototype._init_canvas = function() {\n", " var fig = this;\n", "\n", " var canvas_div = $('
');\n", "\n", " canvas_div.attr('style', 'position: relative; clear: both; outline: 0');\n", "\n", " function canvas_keyboard_event(event) {\n", " return fig.key_event(event, event['data']);\n", " }\n", "\n", " canvas_div.keydown('key_press', canvas_keyboard_event);\n", " canvas_div.keyup('key_release', canvas_keyboard_event);\n", " this.canvas_div = canvas_div\n", " this._canvas_extra_style(canvas_div)\n", " this.root.append(canvas_div);\n", "\n", " var canvas = $('');\n", " canvas.addClass('mpl-canvas');\n", " canvas.attr('style', \"left: 0; top: 0; z-index: 0; outline: 0\")\n", "\n", " this.canvas = canvas[0];\n", " this.context = canvas[0].getContext(\"2d\");\n", "\n", " var backingStore = this.context.backingStorePixelRatio ||\n", "\tthis.context.webkitBackingStorePixelRatio ||\n", "\tthis.context.mozBackingStorePixelRatio ||\n", "\tthis.context.msBackingStorePixelRatio ||\n", "\tthis.context.oBackingStorePixelRatio ||\n", "\tthis.context.backingStorePixelRatio || 1;\n", "\n", " mpl.ratio = (window.devicePixelRatio || 1) / backingStore;\n", "\n", " var rubberband = $('');\n", " rubberband.attr('style', \"position: absolute; left: 0; top: 0; z-index: 1;\")\n", "\n", " var pass_mouse_events = true;\n", "\n", " canvas_div.resizable({\n", " start: function(event, ui) {\n", " pass_mouse_events = false;\n", " },\n", " resize: function(event, ui) {\n", " fig.request_resize(ui.size.width, ui.size.height);\n", " },\n", " stop: function(event, ui) {\n", " pass_mouse_events = true;\n", " fig.request_resize(ui.size.width, ui.size.height);\n", " },\n", " });\n", "\n", " function mouse_event_fn(event) {\n", " if (pass_mouse_events)\n", " return fig.mouse_event(event, event['data']);\n", " }\n", "\n", " rubberband.mousedown('button_press', mouse_event_fn);\n", " rubberband.mouseup('button_release', mouse_event_fn);\n", " // Throttle sequential mouse events to 1 every 20ms.\n", " rubberband.mousemove('motion_notify', mouse_event_fn);\n", "\n", " rubberband.mouseenter('figure_enter', mouse_event_fn);\n", " rubberband.mouseleave('figure_leave', mouse_event_fn);\n", "\n", " canvas_div.on(\"wheel\", function (event) {\n", " event = event.originalEvent;\n", " event['data'] = 'scroll'\n", " if (event.deltaY < 0) {\n", " event.step = 1;\n", " } else {\n", " event.step = -1;\n", " }\n", " mouse_event_fn(event);\n", " });\n", "\n", " canvas_div.append(canvas);\n", " canvas_div.append(rubberband);\n", "\n", " this.rubberband = rubberband;\n", " this.rubberband_canvas = rubberband[0];\n", " this.rubberband_context = rubberband[0].getContext(\"2d\");\n", " this.rubberband_context.strokeStyle = \"#000000\";\n", "\n", " this._resize_canvas = function(width, height) {\n", " // Keep the size of the canvas, canvas container, and rubber band\n", " // canvas in synch.\n", " canvas_div.css('width', width)\n", " canvas_div.css('height', height)\n", "\n", " canvas.attr('width', width * mpl.ratio);\n", " canvas.attr('height', height * mpl.ratio);\n", " canvas.attr('style', 'width: ' + width + 'px; height: ' + height + 'px;');\n", "\n", " rubberband.attr('width', width);\n", " rubberband.attr('height', height);\n", " }\n", "\n", " // Set the figure to an initial 600x600px, this will subsequently be updated\n", " // upon first draw.\n", " this._resize_canvas(600, 600);\n", "\n", " // Disable right mouse context menu.\n", " $(this.rubberband_canvas).bind(\"contextmenu\",function(e){\n", " return false;\n", " });\n", "\n", " function set_focus () {\n", " canvas.focus();\n", " canvas_div.focus();\n", " }\n", "\n", " window.setTimeout(set_focus, 100);\n", "}\n", "\n", "mpl.figure.prototype._init_toolbar = function() {\n", " var fig = this;\n", "\n", " var nav_element = $('
');\n", " nav_element.attr('style', 'width: 100%');\n", " this.root.append(nav_element);\n", "\n", " // Define a callback function for later on.\n", " function toolbar_event(event) {\n", " return fig.toolbar_button_onclick(event['data']);\n", " }\n", " function toolbar_mouse_event(event) {\n", " return fig.toolbar_button_onmouseover(event['data']);\n", " }\n", "\n", " for(var toolbar_ind in mpl.toolbar_items) {\n", " var name = mpl.toolbar_items[toolbar_ind][0];\n", " var tooltip = mpl.toolbar_items[toolbar_ind][1];\n", " var image = mpl.toolbar_items[toolbar_ind][2];\n", " var method_name = mpl.toolbar_items[toolbar_ind][3];\n", "\n", " if (!name) {\n", " // put a spacer in here.\n", " continue;\n", " }\n", " var button = $('');\n", " button.click(method_name, toolbar_event);\n", " button.mouseover(tooltip, toolbar_mouse_event);\n", " nav_element.append(button);\n", " }\n", "\n", " // Add the status bar.\n", " var status_bar = $('');\n", " nav_element.append(status_bar);\n", " this.message = status_bar[0];\n", "\n", " // Add the close button to the window.\n", " var buttongrp = $('
');\n", " var button = $('');\n", " button.click(function (evt) { fig.handle_close(fig, {}); } );\n", " button.mouseover('Stop Interaction', toolbar_mouse_event);\n", " buttongrp.append(button);\n", " var titlebar = this.root.find($('.ui-dialog-titlebar'));\n", " titlebar.prepend(buttongrp);\n", "}\n", "\n", "mpl.figure.prototype._root_extra_style = function(el){\n", " var fig = this\n", " el.on(\"remove\", function(){\n", "\tfig.close_ws(fig, {});\n", " });\n", "}\n", "\n", "mpl.figure.prototype._canvas_extra_style = function(el){\n", " // this is important to make the div 'focusable\n", " el.attr('tabindex', 0)\n", " // reach out to IPython and tell the keyboard manager to turn it's self\n", " // off when our div gets focus\n", "\n", " // location in version 3\n", " if (IPython.notebook.keyboard_manager) {\n", " IPython.notebook.keyboard_manager.register_events(el);\n", " }\n", " else {\n", " // location in version 2\n", " IPython.keyboard_manager.register_events(el);\n", " }\n", "\n", "}\n", "\n", "mpl.figure.prototype._key_event_extra = function(event, name) {\n", " var manager = IPython.notebook.keyboard_manager;\n", " if (!manager)\n", " manager = IPython.keyboard_manager;\n", "\n", " // Check for shift+enter\n", " if (event.shiftKey && event.which == 13) {\n", " this.canvas_div.blur();\n", " event.shiftKey = false;\n", " // Send a \"J\" for go to next cell\n", " event.which = 74;\n", " event.keyCode = 74;\n", " manager.command_mode();\n", " manager.handle_keydown(event);\n", " }\n", "}\n", "\n", "mpl.figure.prototype.handle_save = function(fig, msg) {\n", " fig.ondownload(fig, null);\n", "}\n", "\n", "\n", "mpl.find_output_cell = function(html_output) {\n", " // Return the cell and output element which can be found *uniquely* in the notebook.\n", " // Note - this is a bit hacky, but it is done because the \"notebook_saving.Notebook\"\n", " // IPython event is triggered only after the cells have been serialised, which for\n", " // our purposes (turning an active figure into a static one), is too late.\n", " var cells = IPython.notebook.get_cells();\n", " var ncells = cells.length;\n", " for (var i=0; i= 3 moved mimebundle to data attribute of output\n", " data = data.data;\n", " }\n", " if (data['text/html'] == html_output) {\n", " return [cell, data, j];\n", " }\n", " }\n", " }\n", " }\n", "}\n", "\n", "// Register the function which deals with the matplotlib target/channel.\n", "// The kernel may be null if the page has been refreshed.\n", "if (IPython.notebook.kernel != null) {\n", " IPython.notebook.kernel.comm_manager.register_target('matplotlib', mpl.mpl_figure_comm);\n", "}\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "w:\n", "[[0.55894282]\n", " [0.42792729]]\n" ] } ], "source": [ "# plot\n", "plot_3d_lls(X[:,0], X[:, 1], Y, lls_sol, \"Breast Cancer - Radius Mean vs. Area Mean vs. Perimeter Mean - LLS Mini-Batch GD\")\n", "print(\"w:\")\n", "print(w)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Constrained Optimization\n", "---\n", "### Largrange Multipliers\n", "---\n", "* A method for optimization with **equality constraints**\n", "* The general case: $$ \\min f(x,y) $$ $$ \\textit{s.t. (subject to)}: g(x,y)=0 $$\n", "* The *Lagrange* function (*Lagrangian*) is defined by: $$ \\mathcal{L}(x,y,\\lambda) = f(x,y) -\\lambda \\cdot g(x,y) $$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "* Geometric Intuition: let's look at the following figure where we wish to **maximize** $f(x,y)$ s.t $g(x,y)=0$ -
\n", "
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "* To maximize $f(x,y)$ subject to $g(x,y)=0$ is to find the largest value $c \\in \\{7,8,9,10,11\\}$ such that the level curve (contour) $f(x,y) = c$ intersects with $g(x,y)=0$\n", "* It happens when the curves just touch each other\n", " * When they have a common tangent line\n", "* Otherwise, the value of $c$ should be increased" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "* Since the gradient of a function is **perperndicular** to the contour lines:\n", " * The *contour lines* of $f$ and $g$ are **parallel** iff the *gradients* of $f$ and $g$ are **parallel**\n", " * Thus, we want points $(x,y)$ where $g(x,y) = 0$ and $$\\nabla_{x,y}f(x,y)=\\lambda \\nabla_{x,y} g(x,y) $$\n", " * $\\lambda$ - \"The Lagrange Multiplier\" is required to adjust the **magnitudes** of the (parallel) gradient vectors." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Multiple Constraints\n", "---\n", "* Extenstion of the above for problems with **multiple constraints** using a similar argument\n", "* The general case: minimize $f(x)$ s.t. $g_i(x)=0$, $i = 1,2,..., m$ \n", "* The **Lagrangian** is a weighted sum of objective and constraint functions: $$ \\mathcal{L}(x, \\lambda_1, ..., \\lambda_m) = f(x) - \\sum_{i=1}^m \\lambda_i g_i(x)$$\n", " * $\\lambda_i$ is the Lagrange multipler associated with $g_i(x) = 0$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "* The **solution** is obtained by solving the (unconstrained) optimization problem: $$\\nabla_{x, \\lambda_1, ..., \\lambda_m}\\mathcal{L}(x, \\lambda_1, ..., \\lambda_m) = 0 \\iff \\begin{cases}\n", " \\nabla_x \\big[f(x) - \\sum_{i=1}^m \\lambda_ig_i(x) = 0 \\big]\\\\\n", " g_1(x) = ... = g_m(x) = 0\n", " \\end{cases}$$\n", " * Amounts to solving $d + m$ equations in $d+m$ unknowns\n", " * $d = |x|$ is the dimension of $x$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### Exercise 2 - Max Entropy Distribution\n", "---\n", "Maximize $H(P) = -\\sum_{i=1}^d p_i \\log p_i$ subject to $\\sum_{i=1}^d p_i = 1$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "#### Solution 2\n", "---\n", "* The Lagrangian is: $$L(P,\\lambda) = -\\sum_{i=1}^d p_i \\log p_i -\\lambda \\big(\\sum_{i=1}^dp_i -1 \\big) $$\n", "* Find stationary point for $L$:\n", " * $\\forall i$, $\\frac{\\partial L(P,\\lambda)}{\\partial p_i} = -\\log p_i -1 -\\lambda =0 \\rightarrow p_i = e^{-\\lambda - 1}$\n", " * $\\frac{\\partial L(P,\\lambda)}{\\partial \\lambda} = -\\sum_{i=1}^d p_i + 1 = 0 \\rightarrow \\sum_{i=1}^d e^{-\\lambda - 1} = 1 \\rightarrow e^{-\\lambda - 1} = \\frac{1}{d} = p_i$\n", " * The Max Entropy distribution is the **uniform distribution**" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Recommended Videos\n", "---\n", "#### Warning!\n", "* These videos do not replace the lectures and tutorials.\n", "* Please use these to get a better understanding of the material, and not as an alternative to the written material.\n", "\n", "#### Video By Subject\n", "\n", "* Gradient Descent - Gradient Descent, Step-by-Step\n", " * Mathematics of Gradient Descent - Intelligence and Learning\n", "* Stochastic Gradient Descent - Stochastic Gradient Descent, Clearly Explained\n", "* Constrained Optimization - Constrained Optimization with LaGrange Multipliers\n", "* Lagrange Multipliers - Lagrange Multipliers | Geometric Meaning & Full Example" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "## Credits\n", "---\n", "* Icons from Icon8.com - https://icons8.com\n", "* Datasets from Kaggle - https://www.kaggle.com/" ] } ], "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.9" } }, "nbformat": 4, "nbformat_minor": 2 }