08-05-gradient-descent.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "\n",
    "\n",
    "# Introduction to Gradient Descent\n",
    "\n",
    "The Idea Behind Gradient Descent 梯度下降\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "![](./img/stats/gradient_descent.gif)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "![](./img/stats/gradient2.png)\n",
    "\n",
    "\n",
    "**如何找到最快下山的路？**\n",
    "- 假设此时山上的浓雾很大，下山的路无法确定;\n",
    "- 假设你摔不死！\n",
    "\n",
    "    - 你只能利用自己周围的信息去找到下山的路径。\n",
    "    - 以你当前的位置为基准，寻找这个位置最陡峭的方向，从这个方向向下走。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "![](./img/stats/gradient.png)\n",
    "\n",
    "**Gradient is the vector of partial derivatives**\n",
    "\n",
    "One approach to maximizing a function is to\n",
    "- pick a random starting point, \n",
    "- compute the gradient, \n",
    "- take a small step in the direction of the gradient, and \n",
    "- repeat with a new staring point.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Gradient Descent\n",
    "\n",
    "以下内容同[《第七章 神经网络与深度学习》](https://chengjun.github.io/mybook/09-11-neural-network-intro.html)\n",
    "\n",
    "![image.png](./images/neural9.png)\n",
    "\n",
    "Let's represent parameters as $\\Theta$, learning rate as $\\alpha$, and gradient as $\\bigtriangledown J(\\Theta)$,"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "\n",
    "![](images/gradient.gif)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "![](./img/stats/gd.webp)\n",
    "\n",
    "Let's represent parameters as $\\Theta$, learning rate as $\\alpha$, and gradient as $\\bigtriangledown J(\\Theta)$, "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "To the find the best model is an optimization problem\n",
    "- “minimizes the error of the model” \n",
    "- “maximizes the likelihood of the data.” "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "We’ll frequently need to maximize (or minimize)  functions. \n",
    "- to find the input vector v that produces the largest (or smallest) possible value.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-11-21T13:02:56.099816Z",
     "start_time": "2021-11-21T13:02:56.047568Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Mannual Gradient"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-12-01T06:18:42.154809Z",
     "start_time": "2023-12-01T06:18:38.323418Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYQAAAEJCAYAAACUk1DVAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/MnkTPAAAACXBIWXMAAAsTAAALEwEAmpwYAAAb1UlEQVR4nO3dfWxV9eHH8c+tLUUmXaBcqOsW3YhRQhitoBPdik0ohV6geGFAYDZAqBadjYyV1RZx1mfoYJCOhDkHQatJtQ+wRYpOjVELQzunVBrnIBhoWR/BPtnH+/39weX+rIXeHsa595a9X4mRc77n9nw8fumn93u4HIcxxggA8D8vLNgBAAChgUIAAEiiEAAAXhQCAEAShQAA8KIQAACSKAQAgFd4sAP8N86ebZfHY/1jFNHR16mpqc2GRP8dcllDLutCNRu5rLncXGFhDo0Z851Ljg/rQvB4zGUVwoXXhiJyWUMu60I1G7mssSMXS0YAAEkUAgDAi0IAAEiyuRDefvttud1uzZ07V08++eSA8erqarndbiUnJys3N1e9vb12xgEADMK2Qjh16pQee+wx7dy5U/v379exY8f07rvv9jsmKytLmzZt0sGDB2WMUVFRkV1xAGDYazlcoRMb1uuDhYt1YsN6tRyuuKJf37ZCePPNN5WSkqKYmBhFRERo27Ztmjp1qm+8pqZGnZ2diouLkyS53W6Vl5fbFQcAhrWWwxWq27tHvc1NkjHqbW5S3d49V7QUbCuEL7/8Un19fcrIyFBqaqpefvllffe73/WN19fXy+l0+radTqfq6ursigMAw1pjSbFMd3e/faa7W40lxVfsHLZ9DqGvr08fffSRXnzxRY0aNUpr165VaWmp3G63JMnj8cjhcPiON8b02x6K6OjrLjuf0zn6sl9rJ3JZQy7rQjUbuQb3r7PNF93fe7b5imW0rRDGjRunGTNmaOzYsZKkWbNm6dNPP/UVQkxMjBoaGnzHNzY2avz48ZbO0dTUdlkfznA6R6uhodXy6+xGLmvIZV2oZiOXf+Fjxp5fLrrI/qFmDAtzDPqDtG1LRomJiXr//ffV0tKivr4+vffee5o8ebJvPDY2VpGRkaqsrJQk7du3TwkJCXbFAYBhbZx7kRwjRvTb5xgxQuPci67YOWwrhKlTp2rNmjVavny5UlJS9L3vfU+LFi1Senq6jh49KknKz8/XM888ozlz5qijo0NpaWl2xQGAYS3qjjs1IW2lwsdGSw6HwsdGa0LaSkXdcecVO4fDGBOaf1HHELBkFBjksiZUc0mhm41c1lxurqAtGQEAhhcKAQAgiUIAAHhRCAAASRQCAMCLQgAASKIQAABeFAIAQBKFAADwohAAAJIoBACAF4UAAJBEIQAAvCgEAIAkCgEA4EUhAAAk2fhMZUm699571dzcrPDw86fJy8vT1KlTfeMFBQUqLi5WVFSUJGnJkiVasWKFnZEAAJdgWyEYY3Ty5Em98847vkL4tqqqKm3dulXx8fF2xQAADJFtS0YnTpyQJK1evVoLFizQSy+9NOCYqqoq7dq1S/Pnz1deXp66urrsigMA8MO2Zyp//PHHeuWVV/Too4+qp6dHaWlpeuSRR3TXXXdJktrb2/Xwww8rOztbN9xwg7KzsxUbG6t169bZEQcA4IdthfBte/bsUW1trXJyci46fuzYMeXk5KisrGzIX7OpqU0ej/X4V9uDs+1GLmtCNZcUutnIZc3l5goLcyg6+rpLj/83oQbz0Ucf6dChQ75tY0y/ewm1tbV67bXXLjkOAAgs2wqhtbVVmzdvVldXl9ra2lRaWqqkpCTf+MiRI7VlyxadOnVKxhgVFhb2GwcABJZtP5InJibqk08+0cKFC+XxeLR8+XLFx8crPT1dmZmZmjJlivLy8rR27Vr19PTo1ltv1apVq+yKAwDwI2D3EOzAPYTAIJc1oZpLCt1s5LJm2N1DAAAMLxQCAEAShQAA8KIQAACSKAQAgBeFAACQRCEAALwoBACAJAoBAOBFIQAAJFEIAAAvCgEAIIlCAAB4UQgAAEkUAgDAi0IAAEiy8YlpknTvvfequbnZ96zkvLw8TZ061TdeXV2t3Nxctbe3a/r06Xr88cd5rjIABIlt332NMTp58qTeeeedS36Tz8rK0pNPPqm4uDjl5OSoqKhIy5cvtysSAGAQti0ZnThxQpK0evVqLViwQC+99FK/8ZqaGnV2diouLk6S5Ha7VV5eblccAIAftr1DaGlp0YwZM/Too4+qp6dHaWlp+uEPf6i77rpLklRfXy+n0+k73ul0qq6uztI5Bns2qD9O5+jLfq2dyGUNuawL1WzkssaOXLYVQnx8vOLj433bixcv1rvvvusrBI/HI4fD4Rs3xvTbHoqmpjZ5PMZytqvtwdl2I5c1oZpLCt1s5LLmcnOFhTkG/UHatiWjjz76SIcOHfJtG2P63UuIiYlRQ0ODb7uxsVHjx4+3Kw4AwA/bCqG1tVWbN29WV1eX2traVFpaqqSkJN94bGysIiMjVVlZKUnat2+fEhIS7IoDAPDDtiWjxMREffLJJ1q4cKE8Ho+WL1+u+Ph4paenKzMzU1OmTFF+fr42btyotrY2TZ48WWlpaXbFAQD44TDGWF+EDxHcQwgMclkTqrmk0M1GLmuG3T0EAMDwQiEAACRRCAAALwoBACCJQgAAeFEIAABJFAIAwItCAABIohAAAF4UAgBAEoUAAPCiEAAAkigEAIAXhQAAkEQhAAC8bHtAzgXPPfeczp49q2effbbf/oKCAhUXFysqKkqStGTJEq1YscLuOACAS7C1EA4dOqTS0lLdfffdA8aqqqq0detWxcfH2xkBADBEti0ZnTt3Ttu2bVNGRsZFx6uqqrRr1y7Nnz9feXl56urqsisKAGAIbCuETZs2ad26db4loW9qb2/XpEmTlJWVpdLSUrW0tGjnzp12RQEADIEtz1R+9dVX9e9//1uPPPKISkpKdOTIkQH3EL7p2LFjysnJUVlZ2ZWOAgAYIlvuIbz++utqaGhQamqqvvrqK3V0dOjpp59WTk6OJKm2tlYVFRVavHixJMkYo/Bw61Gamtrk8Vjvs6vtwdl2I5c1oZpLCt1s5LLmcnOFhTkUHX3dJcdtKYTdu3f7fn3hHcKFMpCkkSNHasuWLfrJT36i73//+yosLFRSUpIdUQAAQxTQzyGkp6fr6NGjGjt2rPLy8rR27VrNmTNHxhitWrUqkFEAAN9iyz2EQGHJKDDIZU2o5pJCNxu5rLFryYhPKgMAJFEIAAAvCgEAIIlCAAB4UQgAAEkUAgDAi0IAAEiiEAAAXhQCAEAShQAA8KIQAACSKAQAgBeFAACQRCEAALwoBACAJAoBAOBleyE899xzys7OHrC/urpabrdbycnJys3NVW9vr91RAACDsLUQDh06pNLS0ouOZWVladOmTTp48KCMMSoqKrIzCmC7lsMVOrFhvT5YuFgnNqxXy+GKYEcCLPFbCA899JAqKqxP7HPnzmnbtm3KyMgYMFZTU6POzk7FxcVJktxut8rLyy2fAwgVLYcrVLd3j3qbmyRj1NvcpLq9eygFDCt+CyEpKUk7d+5UcnKyXnjhBZ07d25IX3jTpk1at26doqKiBozV19fL6XT6tp1Op+rq6oaeGggxjSXFMt3d/faZ7m41lhQHKRFgXbi/AxYsWKAFCxbo+PHjKi4u1uLFixUfH697771XP/7xjy/6mldffVXXX3+9ZsyYoZKSkgHjHo9HDofDt22M6bc9VIM9LNofp3P0Zb/WTuSyJlRy/ets80X3955tDpmMF4RangvIZY0dufwWgnT+G/iXX36pkydPqq+vT9HR0frtb3+ru+++W5mZmQOOf/3119XQ0KDU1FR99dVX6ujo0NNPP62cnBxJUkxMjBoaGnzHNzY2avz48ZbDNzW1yeMxll/ndI5WQ0Or5dfZjVzWhFKu8DFjzy8XXWR/qGSUQuuafRO5rLncXGFhjkF/kPZbCNu2bVNJSYl+8IMfaPny5dq+fbsiIiLU0dGhxMTEixbC7t27fb8uKSnRkSNHfGUgSbGxsYqMjFRlZaWmTZumffv2KSEhwep/GxAyxrkXqW7vnn7LRo4RIzTOvSiIqQBr/BZCc3Oznn/+ed1yyy399o8aNUq/+93vLJ0sPT1dmZmZmjJlivLz87Vx40a1tbVp8uTJSktLs5YcCCFRd9wp6fy9hN6zzQofM1bj3It8+4HhwGGMsb7mEiJYMgoMclkTqrmk0M1GLmvsWjLik8oAAEkUAgDAi0IAAEiiEAAAXhQCAEAShQAA8KIQAACSKAQAgBeFAACQRCEAALwoBACAJAoBAOBFIQAAJFEIAAAvCgEAIIlCAAB4DemZypdr+/btOnjwoBwOhxYvXqxVq1b1Gy8oKFBxcbGioqIkSUuWLNGKFSvsjAQAuATbCuHIkSM6fPiw9u/fr97eXqWkpGjmzJn60Y9+5DumqqpKW7duVXx8vF0xAABDZNuS0e233669e/cqPDxcTU1N6uvr06hRo/odU1VVpV27dmn+/PnKy8tTV1eXXXEAAH7Y/kzlHTt26M9//rPmzJmjZ555Rg6HQ5LU3t6uhx9+WNnZ2brhhhuUnZ2t2NhYrVu3zs44AIBLsL0QJOnrr79WRkaGUlJStHTp0osec+zYMeXk5KisrGzIX7epqU0ej/X4V9uDs+1GLmtCNZcUutnIZc3l5goLcyg6+rpLj/83oQZz/PhxVVdXS5KuvfZazZ49W59//rlvvLa2Vq+99ppv2xij8HBb73EDAAZhWyGcPn1aGzduVHd3t7q7u/XWW29p2rRpvvGRI0dqy5YtOnXqlIwxKiwsVFJSkl1xAAB+2PYj+cyZM/Xpp59q4cKFuuaaazR79my5XC6lp6crMzNTU6ZMUV5entauXauenh7deuutA/5YKgAgcAJyD8Eu3EMIDHJZE6q5pNDNRi5rht09BADA8EIhAAAkUQgAAC8KAQAgiUIAAHhRCAAASRQCAMCLQgAASKIQAABeFAIAQBKFAADwohAAAJIoBACAF4UAAJBEIQAAvGwthO3btyslJUUul0u7d+8eMF5dXS23263k5GTl5uaqt7fXzjgAgEHYVghHjhzR4cOHtX//fhUXF+vFF1/UiRMn+h2TlZWlTZs26eDBgzLGqKioyK44AAA/bCuE22+/XXv37lV4eLiamprU19enUaNG+cZramrU2dmpuLg4SZLb7VZ5ebldcQAAfti6ZBQREaEdO3bI5XJpxowZmjBhgm+svr5eTqfTt+10OlVXV2dnHADAIMLtPkFmZqbS09OVkZGhoqIiLV26VJLk8XjkcDh8xxlj+m0PxWDPBvXH6Rx92a+1E7msIZd1oZqNXNbYkcu2Qjh+/Li6u7s1adIkXXvttZo9e7Y+//xz33hMTIwaGhp8242NjRo/frylczQ1tcnjMZazXW0PzrYbuawJ1VxS6GYjlzWXmysszDHoD9K2LRmdPn1aGzduVHd3t7q7u/XWW29p2rRpvvHY2FhFRkaqsrJSkrRv3z4lJCTYFQcA4IdthTBz5kzdfffdWrhwoRYtWqT4+Hi5XC6lp6fr6NGjkqT8/Hw988wzmjNnjjo6OpSWlmZXHACAHw5jjPU1lxDBklFgkMuaUM0lhW42clkz7JaMAADDC4UAAJBEIQAAvCgEAIAkCgEA4EUhAAAkUQgAAC8KAQAgiUIAAHhRCAAASRQCAMCLQgAASKIQAABeFAIAQBKFAADwohAAAJJsfKayJBUUFOjAgQOSzj9BbcOGDQPGi4uLFRUVJUlasmSJVqxYYWckAMAl2FYIFRUVev/991VaWiqHw6E1a9bozTffVFJSku+Yqqoqbd26VfHx8XbFAAAMkW2F4HQ6lZ2drREjRkiSJk6cqNra2n7HVFVVadeuXaqpqdFtt92m3/zmN4qMjLQrEgBgELbdQ7jpppsUFxcnSTp58qQOHDigmTNn+sbb29s1adIkZWVlqbS0VC0tLdq5c6ddcQAAfjiMMdafUm/BF198ofvvv18PPfSQ7rnnnksed+zYMeXk5KisrMzOOACAS7D1pnJlZaUyMzOVk5Mjl8vVb6y2tlYVFRVavHixJMkYo/Bwa3Gamtrk8VjvM6dztBoaWi2/zm7ksoZc1oVqNnJZc7m5wsIcio6+7tLj/02owZw5c0YPPvig8vPzB5SBJI0cOVJbtmzRqVOnZIxRYWFhvxvOAIDAsu0dwgsvvKCuri49++yzvn3Lli3T22+/rczMTE2ZMkV5eXlau3atenp6dOutt2rVqlV2xQEA+GH7PQQ7sWQUGOSyJlRzSaGbjVzWDLslIwDA8EIhAAAkUQgAAC8KAQAgiUIAAHhRCAAASRQCAMCLQgAASKIQAABeFAIAQBKFAADwohAAAJIoBACAF4UAAJBEIQAAvCgEAIAkm5+pXFBQoAMHDkiSZs6cqQ0bNvQbr66uVm5urtrb2zV9+nQ9/vjjlp+rbEXL4Qo1lhTrX2ebFT5mrMa5FynqjjttOx8ADCe2vUOoqKjQ+++/r9LSUpWVlemzzz7Tm2++2e+YrKwsbdq0SQcPHpQxRkVFRXbFUcvhCtXt3aPe5ibJGPU2N6lu7x61HK6w7ZwAMJzYVghOp1PZ2dkaMWKEIiIiNHHiRNXW1vrGa2pq1NnZqbi4OEmS2+1WeXm5XXHUWFIs093db5/p7lZjSbFt5wSA4cS29ZmbbrrJ9+uTJ0/qwIEDeuWVV3z76uvr5XQ6fdtOp1N1dXWWzjHYs0G/7V9nmy+6v/dss5zO0ZbOa6dQyvJN5LImVHNJoZuNXNbYkcvWewiS9MUXX+j+++/Xhg0bdOONN/r2ezweORwO37Yxpt/2UDQ1tcnjMUM6NnzM2PPLRRfZHyoP0b7aHuhtN3JZF6rZyGXN5eYKC3MM+oO0rX/KqLKyUitXrtT69et1zz339BuLiYlRQ0ODb7uxsVHjx4+3Lcs49yI5Rozot88xYoTGuRfZdk4AGE5sK4QzZ87owQcfVH5+vlwu14Dx2NhYRUZGqrKyUpK0b98+JSQk2BVHUXfcqQlpKxU+NlpyOBQ+NloT0lbyp4wAwMu2JaMXXnhBXV1devbZZ337li1bprfffluZmZmaMmWK8vPztXHjRrW1tWny5MlKS0uzK46k86UQdcedIfs2EACCyWGMGdoifAiycg/hm0K1EMhlDbmsC9Vs5LJmWN5DAAAMHxQCAEAShQAA8LL9cwh2Cguz9rmFK/VaO5HLGnJZF6rZyGXN5eTy95phfVMZAHDlsGQEAJBEIQAAvCgEAIAkCgEA4EUhAAAkUQgAAC8KAQAgiUIAAHhRCAAASVdpIbS1tWnevHk6ffr0gLHq6mq53W4lJycrNzdXvb29kqTa2lqtWLFCc+bM0dq1a9Xe3h7QXH/729+UmpqqBQsW6IEHHtBXX30lSSotLdVPf/pTpaamKjU1Vdu2bQtoroKCAiUmJvrOX1hYKCm416u6utqXJzU1VT/72c80b948SfZfr4KCArlcLrlcLm3evHnAeLDml79cwZpf/nIFa34NliuY82v79u1KSUmRy+XS7t27B4zbPr/MVeaf//ynmTdvnpk8ebI5derUgHGXy2U+/vhjY4wxjzzyiCksLDTGGHPfffeZv/71r8YYYwoKCszmzZsDlqu1tdXcdddd5j//+Y8xxpjf//735oknnjDGGJOXl2f+8pe/XNEsQ81ljDH333+/+cc//jFgfzCv1zd1dHQYl8tlPvzwQ2OMvdfrgw8+MEuXLjVdXV2mu7vbpKWlmTfeeKPfMcGYX/5yBWt+DeV6BWN+DSXXBYGcX3//+9/NsmXLTE9Pj/n6669NYmKiOX78eL9j7J5fV907hKKiIj322GMXfT5zTU2NOjs7FRcXJ0lyu90qLy9XT0+PPvzwQyUnJ/fbH6hcPT09euyxxzRhwgRJ0s0336wzZ85Iko4eParS0lLNnz9fv/71r30/2QUilyRVVVVp165dmj9/vvLy8tTV1RX06/VNu3bt0m233abp06dLsvd6OZ1OZWdna8SIEYqIiNDEiRNVW1vrGw/W/PKXK1jzy18uKTjzayi5Lgjk/Lr99tu1d+9ehYeHq6mpSX19fRo1apRvPBDz66orhKeeesr3P+/b6uvr5XQ6fdtOp1N1dXU6e/asrrvuOoWHh/fbH6hcY8aMUVJSkiSps7NTf/zjHzVr1ixflgceeED79+/X9ddfr7y8vIDlam9v16RJk5SVlaXS0lK1tLRo586dQb9eF7S2tqqoqEi//OUvffvsvF433XST7zfjyZMndeDAAc2cOdM3Hqz55S9XsOaXv1zBml/+cl0Q6PklSREREdqxY4dcLpdmzJjhK3EpMPPrqiuEwXg8Hjkc///Xvxpj5HA4fP/+pm9vB0Jra6vuu+8+3XLLLbrnnnskSX/4wx80bdo0ORwOrVmzRu+9917A8nznO9/R888/r4kTJyo8PFyrV6/Wu+++GzLXa//+/Zo1a5aio6N9+wJxvb744gutXr1aGzZs0I033ujbH+z5dalcFwRrfl0qV7Dnl7/rFaz5lZmZqUOHDunMmTMqKiry7Q/E/PqfKoSYmBg1NDT4thsbGzV+/HiNHTtWra2t6uvrkyQ1NDT4Xaq40urr67V8+XLdfPPNeuqppySd/w28Z88e3zHGGF1zzTUBy1RbW6vXXnut3/nDw8ND4npJ52+UpqSk+LYDcb0qKyu1cuVKrV+/3vdN9YJgzq/BcknBm1+D5Qrm/PJ3vaTAz6/jx4+rurpaknTttddq9uzZ+vzzz33jgZhf/1OFEBsbq8jISFVWVkqS9u3bp4SEBEVERGj69Ol6/fXXJUllZWVKSEgIWK6+vj5lZGRo7ty5ys3N9bX7qFGj9Kc//UmffPKJJOmll17yvfUPhJEjR2rLli06deqUjDEqLCxUUlJS0K+XdP4342effab4+HjfPruv15kzZ/Tggw8qPz9fLpdrwHiw5pe/XMGaX/5yBWt++cslBWd+nT59Whs3blR3d7e6u7v11ltvadq0ab7xgMyvy7oVPQwkJib6/nTKmjVrzKeffmqMMaa6utosWrTIJCcnm1/96lemq6vLGGPM6dOnzS9+8Qszd+5cs3r1anPu3LmA5XrjjTfMzTffbBYsWOD7JycnxxhjzIcffmgWLlxo5syZYzIyMkxLS0vAchljTHl5uXG5XGb27NkmOzs7JK6XMcY0NjaaO++8c8Dxdl6vJ554wsTFxfX7//Tyyy8HfX75yxWs+TWU6xWM+TWUXMGYX8YYs2PHDjN37lwzb948s2PHDmNMYL9/8cQ0AICk/7ElIwDApVEIAABJFAIAwItCAABIohAAAF4UAgBAEoUAAPCiEIArpLS0VLNmzVJ7e7s6Ojo0d+5clZWVBTsWMGR8MA24gtavX6/Ro0eru7tb11xzjZ544olgRwKGjEIArqC2tjalpqZq5MiRKikpUWRkZLAjAUPGkhFwBTU1Namrq0stLS2qr68PdhzAEt4hAFdIT0+Pli1bpmXLlsnj8ejVV1/VK6+8ooiIiGBHA4aEdwjAFbJ161aNGzdOP//5z7V06VKNGTPmij+EHbAT7xAAAJJ4hwAA8KIQAACSKAQAgBeFAACQRCEAALwoBACAJAoBAOBFIQAAJEn/Byuw/JIUxD9QAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "import seaborn as sns\n",
    "sns.set()\n",
    "\n",
    "x_data = [1.0, 2.0, 3.0]\n",
    "y_data = [2.0, 4.0, 6.0]\n",
    "\n",
    "plt.plot(x_data, y_data, 'ro')\n",
    "plt.ylabel('y')\n",
    "plt.xlabel('x');"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-12-01T06:19:05.632926Z",
     "start_time": "2023-12-01T06:19:05.628833Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "# our model for the forward pass\n",
    "def forward(x):\n",
    "    return x * w\n",
    " \n",
    "# Loss function\n",
    "def loss(y_pred, y_val):\n",
    "    return (y_pred - y_val) ** 2 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-12-01T06:21:28.658846Z",
     "start_time": "2023-12-01T06:21:28.654499Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "# List of weights/Mean square Error (Mse) for each input\n",
    "w_list = []\n",
    "mse_list = []\n",
    "\n",
    "for w in np.arange(0.0, 4.1, 0.1):\n",
    "    # Print the weights and initialize the lost\n",
    "    #print(\"w=\", w)\n",
    "    l_sum = 0\n",
    "    for x_val, y_val in zip(x_data, y_data):\n",
    "        # For each input and output, calculate y_hat\n",
    "        # Compute the total loss and add to the total error\n",
    "        y_pred = forward(x_val)\n",
    "        l = loss(y_pred, y_val)\n",
    "        l_sum += l\n",
    "        #print(\"\\t\", x_val, y_val, y_pred_val, l)\n",
    "    # Now compute the Mean squared error (mse) of each\n",
    "    # Aggregate the weight/mse from this run\n",
    "    #print(\"MSE=\", l_sum / 3)\n",
    "    w_list.append(w)\n",
    "    mse_list.append(l_sum / 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-12-01T06:21:58.428164Z",
     "start_time": "2023-12-01T06:21:58.262586Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYoAAAEJCAYAAACKWmBmAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/MnkTPAAAACXBIWXMAAAsTAAALEwEAmpwYAAAyDUlEQVR4nO3deVRTd94G8CcbIAIqNAjijgsOri21btWqRVSgTGnruLRqHfvOdKP1nXHGaqe2vmPrqF3GsbZO6+lMR+0UF9yqjI5atYW6oKIodUFREEUWBYIkhOS+f1BSICEhSHJvkudzTs8x9+Y2j9ck39z722SCIAggIiJqglzsAEREJG0sFEREZBULBRERWcVCQUREVrFQEBGRVSwURERkFQsFERFZpRQ7gCPcuVMJo9H+4SFBQX4oKdE4INH9kWouQLrZmMs+zGUfd8sll8vQoUPbJve7ZaEwGoUWFYq6Y6VIqrkA6WZjLvswl308KRdvPRERkVUsFEREZBULBRERWcVCQUREVrllY7a90s/dwtZDOSgt1yEwwBuJY8IxPDJE7FhERM3i6O8wjy8U6edu4Z97fkR1jREAUFKuwz/3/AgALBZEJHnO+A7z+FtPWw/lmE5wneoaI7YeyhEpERFR8znjO8zjC0VJuc6u7UREUuKM7zCPLxRBAd52bScikhJnfId5fKFIHBMOL2XD06BUyJA4JlykREREzRf9cBezbV5Keat+h3l8Y3ZdY09djwHIgNAgXzZkE5FL0FTVAADa+3mjTMNeTw4zPDIEwyNDoFb7Y+2W0/gm/RpKy7UIDPAROxoRUZMMRiO+O1OAAT2DMG/KIKjV/igqqmj11/H4W0+NPTqwEwQBOHLmpthRiIisOptTiruaaowe1Mmhr8NC0Yi6fRtEdu+AI2cKJDs7JBERABzOLEBAWy8M6hXk0NdhobBg9OAwlJbrkHW1ROwoREQW3anQITOnGKMGhEKpcOxXuUPbKDQaDaZOnYpPP/0UOTk5+OCDD0z7CgsLMWjQIKxdu7bBMSkpKXj//fcRFFRbIR977DHMmzfPkTHNDOn9APx9VTh0ugADwx9w6msTETXHd2cKIAjA6EGhDn8thxWKzMxMvPnmm8jNzQUAjBkzBmPGjAEAFBUVYdq0aXjjjTfMjsvKysKCBQsQFxfnqGg2KRVyjBwQir3H8nBXo0N7P46pICLpMAoCjpy5iX7dOiC4g6/DX89h1yvJyclYvHgxgoODzfYtX74cU6dORffu3c32nT17FikpKYiPj8fvf/97lJWVOSqiVaMHdYJREPD9WTZqE5G0nM8tRXGZFmMGO7YRu47DCsXSpUsRFRVltj03NxfHjh3DzJkzLR6nVqvx0ksvYceOHQgNDcWSJUscFdGqkEBf9O3SHoczC2AU2KhNRNJx+HQB/NqoMKS32imv5/RxFF9//TWmT58OLy8vi/s//vhj05/nzp2L6Ohou18jKMivxfnUan/Tn+Me7Yn3N57Erbs6DOrjnH+QptTPJTVSzcZc9mEu+4iV606FFqcuFSP+0Z7oFNrObL8jcjm9UOzfvx/r1q2zuK+iogJbtmzB7NmzAQCCIEChUNj9GiUlmhZ1bW08WKVPJ3+09VFix+HL6NRBvMF3jhpE0xqkmo257MNc9hEz154frsFgFBDV+wGzDC3NJZfLrP7Admr32NLSUmi1WnTpYj43CQD4+vri888/R2ZmJgBg/fr1LbqiaC0qpQLDI0Nw8mIRKu5Vi5aDiAio/fF8OLMAvTu3Q6cH2jrtdZ1aKPLz8xESYj7/yKJFi7B//34oFAp89NFHePvttzFp0iScO3cO8+fPd2ZEM6MHd0KNQUBa1i1RcxARXbh+F4V3qhw+ErsxmSC4X0tta916qrPg0zQUl+tgNAoIEmGpVKlefgPSzcZc9mEu+zg7V91SpyXlOsgAzJ4cgUcHmhcLR9164qSANqSfu4WSn4oEwKVSici5Gi91KgDYsPcilAq5076DOIWHDVsP5cDQ6OqES6USkbNIYblmFgobuFQqEYlJCt9BLBQ2cKlUIhKTFL6DWChssLRUamsvM0hE1JTEMeGQyRpuc/Z3EBuzbai/VGrdpd64B8PYkE1ETtG3S3sIAuDjpYC22iBKz0sWimaoWyq1xmDE/DVpKCi5J3YkIvIQh04XQAbgnTlDoW7fRpQMvPVkB6VCjtGDOuFsTgmK7laJHYeI3FyNwYhDmQUYEB4kWpEAWCjsNmZwJ8hkMnx76obYUYjIzZ28WITyymqMe7CzqDlYKOwUGOCDIb0fwJEzN6GvMYgdh4jc2IGMfKjb+6B/z0BRc7BQtMC4B8OgqdLjWPZtsaMQkZvKv63BxfwyjB3SGfLG3Z6cjIWiBSK6dUBokC8OnOTtJyJyjAOnbkCllGPUQMeviW0LC0ULyGQyjB0Shqs3y3H1ZrnYcYjIzVTpapCedQtD+wXDr41K7DgsFC01on8ovFUKHORVBRG1srSsW9DpDaI3YtdhoWghXx8lhkd2xNHsQmiq9GLHISI3IQgCDpzMR49Qf/QIDRA7DgAWivsy9sHO0NcY8d2Zm2JHISI38eP1u7hZcg9jh0jjagJgobgvXYL90LtzO3x76gaM7rf+ExGJ4ODJfLT1UWJov2Cxo5hwCo/7NPbBMPx9x3nM+9t3qLinF2UeFiJyfennbmHzwRzc0ejg46VAxsUiyXyPOPSKQqPRIC4uDvn5+QCAN954AxMmTEBCQgISEhKwb98+s2MKCgowY8YMTJw4ES+++CIqKysdGfG+GQy1VxIV92rbKepWwEs/xzW2iah56laxu6OpnXhUW22Q1PeIwwpFZmYmpk2bhtzcXNO2rKwsrF+/Htu3b8f27dsRHR1tdtw777yD6dOnIzU1Ff3798eaNWscFbFVbDtyxWwbV8AjIntIYRU7axxWKJKTk7F48WIEB9feZ6uqqkJBQQEWLlyI+Ph4rFq1CkZjwxOj1+tx/PhxxMTEAAASExORmprqqIitQgqrTxGRa5P694jDCsXSpUsRFRVlelxcXIxhw4bh3XffRXJyMk6cOIHNmzc3OObOnTvw8/ODUlnbdKJWq1FYWOioiK1CCqtPEZFrk/r3iNMas7t06YKPP/7Y9Pi5557Dtm3bMGXKFNM2QRAgazSnSePHzREU5NfinGq1v13Pnx0XidWbMqHT/zxBoLdKgdlxkXb/v1ozlzNJNRtz2Ye57NOauaIf6Y5/77vQYFtLv0cccb6cViguXLiA3Nxc020lQRBMVw51AgMDUVFRAYPBAIVCgaKiItOtK3uUlGhgNNrfXVWt9kdRUYVdx0R2bY+ZE/uaVsCTy2V4LqYPIru2t/v/1Zq5nEWq2ZjLPsxln9bOdTnvDlQKGfx9vVBaoTP1nrT3e6SlueRymdUf2E4rFIIg4N1338WwYcPg6+uLr7/+Gk8++WSD56hUKkRFRWH37t2Ij4/Htm3bMHr0aGdFbLG6FfCOZRfi0+3n4Ost/twsROQaisuqkHHhNiYO7YpnxvYSO45FThtwFxERgf/5n//BtGnTEBsbi379+iEuLg4AsGjRIuzfvx8AsHjxYiQnJ2Py5Mk4ceIEXn/9dWdFvG8P9lGjg7839h6/LnYUInIR+zPyIYMM4x+Szkjsxhx+RXHgwAHTn2fMmIEZM2aYPWfp0qWmP4eFheFf//qXo2M5hFIhx+MPdcamb3NwvbACXTtK894qEUlDla4GhzNvIipCjcAAH7HjNIlTeLSy0YM7wUslx74TeWJHISKJ+/7sTVTpahD9cBexo1jFQtHK2vqoMHJAKI6eL0SZRhp9oIlIeoxGAf89kY/wTgEI79RO7DhWsVA4QHRUF9QYBBw8xbUqiMiyzJxi3L5bJfmrCYCFwiFCAn0xKDwIB0/dgL7GYPsAIvI4+47nITDAGw/1VYsdxSYWCgeJfrgLKu7p8cM5aY8sJyLnu15YgR+v38X4hzpDIZf+17D0E7qoft06oLPaD/tO5EHgWhVEVM++43nwVikwZlAnsaM0CwuFg8hkMkQ/3Bn5RZXIvnZH7DhEJBFlGh2OZhdi1IBQ+Pq4xuBcFgoHGvaLjgjwVWHvcXaVJaJaB07egMEg4PEo6Q6wa4wr3DmQSqlAr7B2OHmpGHOWHeDqd0QeLP3cLWw5lIPSch1USjmu3CxHx0BfsWM1CwuFA6Wfu4WzV0tNj+tWvwPAYkHkQepWsKtbnEhfY3Sp7wLeenKgrYdyoJfwqlVE5BxSX8HOFhYKB5L6qlVE5Byu/l3AQuFAUl+1ioicw9W/C1goHChxTDi8lA1PsUIuQ+KYcJESEZEYRvQ3b4fwUspd5ruAjdkOVNdIVbf6nVIhg7dKjocj7F+1j4hc1/VCDbxVcrT1UTVYwc4VGrIBFgqHq1v9DgBOXy7Gqs1ncDz7NoZb+IVBRO4nv0iDzJwS/HJUDzwxqofYcVqEt56caGB4EMIeaIvdR69xWg8iD7Hnh+vwUskxTsIr2Nni0EKh0WgQFxeH/Px8AMDXX3+NuLg4xMfH44033kB1dbXZMSkpKRg1ahQSEhKQkJCADz/80JERnUouk2HSsK64UVSJMzklYschIgcrKdPiWHYhxgwKg18b15iuwxKHFYrMzExMmzYNubm5AICrV69i3bp1+Pe//40dO3bAaDRi48aNZsdlZWVhwYIF2L59O7Zv34558+Y5KqIohvbriKAAb+z54ZrYUYjIwf5z/DoAIGao9NecsMZhhSI5ORmLFy9GcHBtw62XlxcWL14MPz8/yGQy9OnTBwUFBWbHnT17FikpKYiPj8fvf/97lJWVOSqiKJQKOSYM7YqL+WW4nO9efzci+pmmSo/DmQUY9ouOkl4PuzkcViiWLl2KqKgo0+OwsDCMHDkSAFBaWooNGzZg/PjxZsep1Wq89NJL2LFjB0JDQ7FkyRJHRRTN6IGd4NdGhd28qiByW/sz8lGtN2LisG5iR7lvTu/1VFhYiLlz5+Kpp57CI488Yrb/448/Nv157ty5iI6Otvs1goL8WpxPrfZv8bH2eOLRnti49wLuGQR0Cwmw+Xxn5WoJqWZjLvswl32s5dLqanDgZD4eiQzB4H7O7eHoiPPl1EKRk5ODuXPn4rnnnsOcOXPM9ldUVGDLli2YPXs2AEAQBCgUCrtfp6REA6PR/l5FarU/iooq7D6uJYb1C8bmg5fw1Z5s/DruF5LJZS+pZmMu+zCXfWzl2nciDxX39Bg/JMyp+Vt6vuRymdUf2E7rHqvRaPDrX/8ar732msUiAQC+vr74/PPPkZmZCQBYv359i64oXIFfGxVGD+qEH84XoqRMK3YcImolNQYj9h67jj6d26FX53Zix2kVTrui2Lx5M4qLi/HFF1/giy++AACMGzcOr732GhYtWoRx48Zh/Pjx+Oijj/D2229Dq9Wie/fuWL58ubMiOl3Mw12x/0Q+/rTuKLTVBpcbrUlEP0s/d8s0CwMARLnRDAwywQ1HfrnCrSeg9o21btd51I/qpZRj1qSIBsVCqpffgHSzMZd9mMs+jXM1Xm8CsPxZdnau5pLMrScyt/VQDhrXM1eao56Iarn6ehO2sFCIyNXnqCeiWu7+WWahEJGrz1FPRLXc/bPMQiEiS+tVqFxojnoiqvXk6J6QNdrmSutN2MJpxkXUeL0KABgUHsReT0Quxt/XCwKAtj5KVGpr3K4HIwuFyOqvV/HRpkxkX7uDKl0N2njzn4bIFQiCgB3fXUVQgDfe+81wKBXud6PG/f5GLixhVA9UamuH/hORaziXW4qcgnLEDu/ulkUCYKGQlB6hARjQMwj/OZYHbXWN2HGIyIbaq4lcBAZ4Y9TAULHjOAwLhcQ8Mao7NFV6HDx5Q+woRGTD+Wt3cPlGGWKHdXPbqwmAhUJywju1Q/+egdhz9DqvKogkTBAEbP/uKjr4e2PUwE5ix3EoFgoJShjZo/aq4hSvKoikKvvaHVzOL0Ps8G5QKd37q9S9/3YuKjysHSJ7BCL16HXoqg1ixyGiRup6OnXw98ajbn41AbBQSFbCyB6ouMerCiIpOptTjIv5ZZg8zP2vJgCOo5CsXp3bodMDvtj07WVsOngZgW42gIfIFdWfSlwmA7xV7l8kABYKyUo/dwu371ShbhL4knId/rnnRwBgsSASQeOpxAUBWL/3IhQKudt/Jj2jHLqgrYdyUGNoOAe5O01bTORq3H0qcWtYKCTK3actJnI1nvyZZKGQKHeftpjI1XjyZ9KhhUKj0SAuLg75+bVzF6WlpSE+Ph4TJkzAhx9+aPGYgoICzJgxAxMnTsSLL76IyspKR0aULEtTkCvkMreZtpjI1TzYR222zZ2mEremWYWiuLgY+/fvBwCsWLECs2bNwo8//mj1mMzMTEybNg25ubkAAK1Wi4ULF2LNmjXYvXs3srKycOjQIbPj3nnnHUyfPh2pqano378/1qxZY+dfyT0MjwzBrEkRCArwhgz4qWgI+EW3DmJHI/I4BqMRWVdL0d7PC4E/fSaDArydvia2WJpVKBYsWIC8vDykp6fjyJEjSEhIwJ///GerxyQnJ2Px4sUIDg4GAJw5cwbdunVDly5doFQqER8fj9TU1AbH6PV6HD9+HDExMQCAxMREs+d4kuGRIVjx0kjseD8B7/x6KAAZdqblih2LyOOknb2FmyX38OyEvlj502dyxUsjPaJIAM0sFHfv3sXs2bNx+PBhxMXFITExEVVVVVaPWbp0KaKiokyPb9++DbX650u34OBgFBYWNjjmzp078PPzg1JZ22tXrVabPcdTdezgi9GDOuHQ6QLcvmv93BNR69HXGLDtu6vo2SkAQ3o/IHYcUTRrHIVer4der8eRI0ewbNkyVFVV4d69e3a9kNFohEz282KBgiA0eNzUtsaPmyMoyM/uY+qo1f4tPtaR1Gp/zH6iP77PuoXUY3n43YyHxI5kIuVzJkXMZR+xc207dBl3KnSY/2wUgoMDTNvFztUUR+RqVqEYP348hg8fjn79+qF///6Ii4tDXFycXS8UEhKCoqIi0+OioiLTbak6gYGBqKiogMFggEKhsPic5igp0cBoFGw/sRG12h9FRRV2H+do9XNFR3XG7vRreGxQKLp2FP+N6grnTEqYyz5i57qnrcHX+y6if49AhLTzNmURO1dTWppLLpdZ/YHdrFtPSUlJ2LVrF7788ksAwMqVK/Hyyy/bFWTQoEG4evUqrl27BoPBgF27dmH06NENnqNSqRAVFYXdu3cDALZt22b2HE838ZGuaOOtxNbDV8SOQuT2/nPsOjRVejzlAT2brGl2r6dz585BJpNhxYoVeO+992z2emrM29sby5Ytw6uvvorJkyejZ8+emDhxIgBg0aJFpl5VixcvRnJyMiZPnowTJ07g9ddft+9v5Oba+qgweXg3nMkpwcW8u2LHIXJbZZXV2Hs8Dw9HBKNbiPhX72KSCYJg8x7N3LlzMWrUKPTt2xfvvfceZs+eja1bt2L9+vXOyGg3d771BAA6vQEL1qZD3b4N3pjxYIvacRyVTSqYyz7MZW7Dvos4ePIG/vzCIwgJ9JVMLmtEvfXUkl5P5DjeKgUSRvbA5fwyZOaUiB2HyO0U3a3Ct6du4NFBoWZFwhM5rdcTta5RA0ORcuQKPt56FgajgCBOQ0503+pPIw4AYeq2IieShmZdUdT1eurQoQP69++PZ555xu5eT9S6jv94G1W6Ghh+usVWNw15+rlbIicjck1104jXn+Rv88EcfqbQzCuKpKQkTJkyBSEhtb9WV65ciYiICIcGI+usTUPOqwoi+1mbRtzTP1PNKhRGoxE7d+7E4cOHUVNTg5EjR6JXr16mEdTkfJ485TGRI/Az1bRm3Xp6//338cMPP2DWrFl4/vnncerUKSxfvtzR2cgKT57ymMgRAvmZalKzCsWRI0fw6aef4vHHH8eECRPwySef4PDhw47ORlZYmoZcLoNHTHlM5AgRXc1nZvaUacRtada9I0EQoFKpTI+9vLwaPCbnq7tnWtdDw8dLAW21AZ2C2EuDyF6VWj0yLxcjNLANqmuMKCnXsSdhPc0qFBEREXj33Xfx7LPPQiaTYf369ejTp4+js5ENwyNDTG/ie1o9Fqz9AV/tv4Q/Th8i6iA8Ilez47tc3NPWYP60IZKYQ01qmnXrafHixSgvL8fUqVMxZcoUlJSUYNq0aY7ORnbw9VHhydE9cTHvLjIuFNk+gIgAADdLKnHgZD4eHdSJRaIJzbqi8PPzw7Jlyxpse/DBB3Hy5EmHhKKWGT0oFAdO5iP54GUM6hUElVIhdiQiyUs+cBkqpRxPju4pdhTJavGa2c2YIoqcTCGXY+q43igu02LfiXyx4xBJXtbVEmTmlCB+RHe0a+sldhzJanGh4D1waYrsEYjBvR7ArrRclGnY/5uoKQajEV/vvwx1ex88HtVF7DiS1uJCQdI1ZVwv6GuMSDnCNSuImnL4dAFuFFdiytheUCn5VWiN1TaKIUMs954RBAFardZhoej+hAT6YvxDnbH3eB4yL5egrLKaXf2IfpJ+7hY2f5uDOxU6KBUy6PQGsSNJntVCsWvXLmfloFYWElQ7NXJZZTWAnycNBMBiQR6rbuK/ujmdagwCvky9AJlMxs+FFVYLRVhYmLNyUCv7Ji3XbBsnOCNPx4n/Wsbps/pt2rSpwcp4+fn5SEhIwFtvvWXatnr1amzZsgUBAQEAgClTpmDGjBnOjurSOMEZkTl+LlrG6YXimWeewTPPPAMAuHTpEl5++WW88sorDZ6TlZWFDz74AEOGDHF2PLcRFOBt8c3PCc7Ik/m1UUJTVWO2nZ8L60Rt6n/77bcxb948BAYGNtielZWFtWvXIj4+HkuWLIFOx2pvL0uTBqoUnOCMPFelVo+aGiMad8/hxH+2iVYo0tLSoNVqMWnSpAbbKysr0a9fP8yfPx8pKSkoLy/HmjVrRErpuoZHhmDWpAjTLyWZDOjg74VHftFR5GRE4th66Ap0NUY8+WgP0+ciKMAbsyZFsH3CBpkg0hDrpKQkTJgwweaSqufPn8fChQuxbds25wRzUwdOXMeHX53CK88MQsyw7mLHIXKqi9fv4PerDiN+VE+88MsBYsdxOaIsUVddXY3jx4+bzR8FAAUFBUhLS8PTTz8NoHbMhr0r6ZWUaGA02l//1Gp/FBVV2H2co7VGrv5d26Nvl/b4Yuc59ArxR0ArTVfgzufMEZjLPq2Ry2A04q//Pol2bb0QE9W5Vf6e7na+5HIZgoL8mt5/P6Fa6sKFC+jevTt8fX3N9vn4+GDFihXIy8uDIAjYsGEDoqOjRUjpXmQyGZ6L6QtttQHJBy+LHYfIaQ5k3MD1Qg2mPd4Hbby5fHNLiFIo8vLyEBLS8J7gCy+8gLNnzyIwMBBLlizBiy++iIkTJ0IQBDz//PNixHQ7nR5oi4mPdEVa1i38eO2O2HGIHO5OhQ4pR66gf89ARPVVix3HZYlSXidPnozJkyc32PbZZ5+Z/hwTE4OYmBhnx/IIcSO64+j5Qvxr7wW8M2colArOcUPu66v9l2AwCng2ug8nMr0PvA7zMN4qBZ6d0AcfbTqD11Z9hypdDeeBIreSfu6WaYlgAIjq+wCCO5jf5qbm489JD1SprYFMBlTpagce1c0DlX7ulsjJiO5P3VxO9Qebnskp5Xv7PrFQeKCth3LQuFN03Xw3RK7M2lxO1HIsFB6I892Qu+J72zFYKDxQU/PacL4bcnWBfG87BAuFB7I0D5RMBi4uTy6ve0d/s22cy+n+sVB4oMbzQPl6KyEIMGu3IHIl125VIDOnBL3CAjiXUytj91gPNTwyxPThMRoFLNt4El/99xJ+0T0QHfx5mU6upcZgxLpvsuHXRoWkpwfBr41K7EhuhVcUBLlchl9P7ocagxH/TP0RIs0TSdRiO7/PRX6RBrMmRrBIOAALBQEAOgb64qkx4TiTU4Lvz7LPObmOa7cq8E36NYzoH4LBvR8QO45bYqEgk/FRndGnczt8tf8SSsu1YschsklfY8Tn35xHQFsVpj3eW+w4bouFgkzkMhmej+0Hg9GIf/AWFLmAnWlXcaOoErMmRqCtD285OQobs6mBjh188fSYcGz87yUk/fUIKrWcC4qkpfFcTr07B2BQL95yciReUZAZXx8lZLLaOaEAzgVF0mFpLqfcWxq+Nx2MhYLMpBy+wrmgSJIszeWk53vT4VgoyAznyyGp4ntTHCwUZIZzQZFUNTUYlO9Nx2KhIDOW5oICgNgR3Z0fhugnRqOANl4Ks+2cy8nxRCkUzz33HGJjY5GQkICEhARkZmY22J+dnY3ExETExMRg0aJFqKmpESOmx2o8F1S7tl6QATh3tZRdZkk0u3+4hoKSexg9MJRzOTmZ07vHCoKA3NxcHDx4EEql5ZefP38+/vznP2Pw4MFYuHAhkpOTMX36dCcn9Wz154ICgD1Hr2HTwRx8e7oAY4eEiZiMPNHl/DJsO3IVQ/sFY9akCK5/7WROv6K4cuUKAGDOnDl44oknsH79+gb7b9y4Aa1Wi8GDBwMAEhMTkZqa6uyY1EjM0K7o3yMQX/33EvJva8SOQx6kUqvH2h1ZCGrnjZkxLBJicPoVRXl5OYYPH44//elP0Ov1mDlzJnr06IGRI0cCAG7fvg21Wm16vlqtRmFhoV2vERTk1+J8arX5fPZSIIVcf5w1FEnvH8Rn35zHB6+NgY937dtHCtksYS77SDGXIAjYuP8y7mqqsfzVR9GtSwexI5lI8XwBjsnl9EIxZMgQDBkyxPT46aefxqFDh0yFwmg0NvjFIAiC3b8gSko0MBrtv5euVvujqKjC7uMcTUq55sT2wwf/Po03P/kOxWValJbrECjBkdtSOmf1MVfzNB59/Ui/YHRoo5RMRqmdrzotzSWXy6z+wHb6racTJ04gPT3d9FgQhAZtFSEhISgqKjI9Li4uRnBwsFMzUtMiuwdiUK8gXMgrQ0m5DgI4cptal6XR16cuFfP9JSKnF4qKigosX74cOp0OGo0GKSkpiI6ONu0PCwuDt7c3MjIyAADbt2/H6NGjnR2TrLhuoY2CI7eptVgafc33l7icfutp7NixyMzMxC9/+UsYjUZMnz4dQ4YMwQsvvICkpCQMGDAAK1euxJtvvgmNRoPIyEjMnDnT2THJilKOjiUH4uhr6RFl9tjXX38dr7/+eoNtn332menPERER2Lx5s5NTUXMFBXhb/NBydCy1hjbeClTpDGbb+f4SD0dmk90sjdxWyGUcHUv37eTFIlTpDJA36r/C0dfiYqEgu9UfuS0D4K2Sw2AULE77QdRcN4o0+GzXefQI9cfseu8vjr4WHxcuohapG7mtVvuj4OZdLNtwCp/vykbHDr7oHNzycSzkmTRVevxty1n4qBR4JXEgOvh7Y9TATpLthupp+BOQ7ptKqcAriQPg463A37aegaZKL3YkciEGoxFrt2ehtEKLlxMHNDlDLImHVxTUKjr4e+OVJwfgLxtPYtmGDGirDSgt13EZVbKo/oA6Hy8FtNUGzJ4UgV5h7cSORhbwioJaTXhYO4yIDEFB8T1TF1oOxqPGGg+o01YbIJfJoGIbl2TxX4Za1bncUrNtHCxF9VkaUGcUBL5HJIyFgloVB0uRLXyPuB4WCmpVXEaVbOFypq6HhYJaVVPLqD4e1VmENCQ1Vboas8F0AAfUSR0LBbWqxsuotvfzgpdShoMnC1BWWS1yOhJTjcGIj1PO4k5FNWKGduFypi6E3WOp1TVeRjWnoAwrvjqFD5NP44/TH0Qbb77tPI1REPD5rvM4n3sHv47th5EDQvGrcb3FjkXNxCsKcrjwTu3w0i8HIP92JVZvPQt9ox4v5N4EQcC//3sJx7Jv45nHwjFyQKjYkchO/GlHTjEwPAjPT47Aum+ysWxDBsoqqzkgz43VH1DXxluJKl0NJjzcBRMf6Sp2NGoBFgpympEDQpF1pQRHs2+bttUNyAPAYuEm6gbU1Y2VqGvA7trRz+5ljUkaeOuJnOryjTKzbRyQ514sD6gDUg5fESkR3S8WCnIqDrZyf/w3dj+i3HpavXo19uzZAwAYM2YM/vCHP5jt37JlCwICAgAAU6ZMwYwZM5yek1ofV8dzf23bKFFZVWO2nf/GrsvphSItLQ3fffcdUlJSIJPJMHfuXOzbtw/R0dGm52RlZeGDDz7AkCFDnB2PHCxxTHiD+9d1OnZoA6MgQM572C7t0OkbqKyqgUwGCMLP2zmgzrU5/daTWq3GggUL4OXlBZVKhfDwcBQUFDR4TlZWFtauXYv4+HgsWbIEOh0vWd1F4wF5QQHeGBgeiPPX7uLL1B9hrP/tQi5lf0Y+/pl6obaHW6N/Yw6oc21Ov6Lo3fvnQTa5ubnYs2cPvvrqK9O2yspK9OvXD/Pnz0e3bt2wYMECrFmzBvPmzXN2VHKQxgPyBEFAypGr2JWWi5sllSgp17HrrAuo3wXW11uJe7oaDOn9AH6b0B8qpRyjBnYSOyK1EpkgiPMT7tKlS/jNb36DV199FU8++WSTzzt//jwWLlyIbdu2OS8cieK9fx5D2pmbDbZ5qxR45ZlBeOyhLiKlIku+zcjD6k2Z0OkNpm1ymQxJvxqM8Q9zrIS7EaUxOyMjA0lJSVi4cCFiY2Mb7CsoKEBaWhqefvppALW/NpVK+2KWlGhgNNpf/6S6Pq9UcwGtm+2ChbUsdHoD/rHrHCK7thctV2tyl1z/2HWuQZEAaqfp+Nfu8xjYvYNouZzF3XLJ5TIEBTW91r3T2yhu3ryJl19+GStXrjQrEgDg4+ODFStWIC8vD4IgYMOGDQ0ausl9sVul6+C/lWdx+hXFunXroNPpsGzZMtO2qVOn4sCBA0hKSsKAAQOwZMkSvPjii9Dr9XjwwQfx/PPPOzsmiaCprrPt2nqJkIaaUn6vGkqFDDUG86t2doF1T6K1UTgSbz05T2tmazz1Qx2lQoZXnxqIAT2DRMnVmlw9143iSvx1UyZKy7WQyxsWCy+lvNV7N7n6+XI2t7n1RNQUS11npz3eG6FBbfHRpkzsz8gXOaFny7pagnf/dQLVNUa88dxDeH5yP3aB9RCcFJAkpXHXWQB4dGAo/r7jPDbsu4hTF2/j1p0qdp91gvrdX9v6KFGprUFntR9ee3oggtr5ILxTO557D8ErCpI8Hy8lXkkcgIE9awfmlf7UjlE382z6uVsiJ3Q/dbcB69qMKrW1o63HPxSGoHY+IqcjZ2OhIJcgl8two7jSbDtnnnUMSzPACgKwKy1XnEAkKhYKchnskuk8PNdUHwsFuYymul4qFTKUlmudnMY9VelqsO6b803uZ/dXz8TGbHIZlmaeVchlEATgrXXHMGtSBGoMtbeiSst1CGRjt011Ddal5ToEtPWC0ShAU6XH4N5BOH/1ToNzzRlgPRcLBbmMui/8up44db2eenYKwN93nMMn27Igl9WupgZwmVVbGo9bKausBgDEDe+GxDHhDXo9sYeZZ2OhIJdiqfssALzx7EN4bdURVOkazj9U19jNLzhzlhqsgdoCUlcUeN4IYBsFuQmlQm5WJOqwAdbcPa2eDdbUbLyiILfR1FxRbbwV0OkN8FYpREglLUZBwHdnbmKLlS7FbLCmxlgoyG1YauyWy4AqnQGLPvsBQ3qrcfpSkUfdc6/fzhDQ1gsqhQwl5Tr06twO0Q8FYlf6NTZYk00sFOQ26jd21+/1FOjvjc92nm8wV5QnNHQ3bqwu/6mxeuyQTnh2Ql/IZDIEtW/DXmJkEwsFuZW6BlizWTRl5s9194bu5AOXLTZWn8kpgUxWe0KaPF9E9bBQkEcotdJwe/R8IaIi1DiWfdvluoM27sL65Oie6ODvg9Sj103dXRtjYzXZi4WCPEJTDd1yuQxrd5zD+r1KaKsNMPw0CMMVbk01vrVUUq7Dul3ZEAAE+KrQxlthsScYG6vJXiwU5BEsNXR7KeWYObEv2ngr8cm2LFORqFP/1pSYg8+aem2LE/cBaOujxIqXRuDEhSKLf2c2VpO9WCjIIzQ1qrtuu6VlPYHaX+nJBy7hwMkbDX65O+tqw9JVwxe7s/HDuVtN3kKq1NZApVTY/DsTNZcohWLnzp345JNPUFNTg1mzZmHGjBkN9mdnZ2PRokWorKxEVFQU3nnnHSiVrGl0f6yNNG7q1hQApB7LM9vWuCHc1hVH/TmVGvcusnaspauGGoOAs1dKoVLKobfQWF3/1hJHV1NrcPrI7MLCQnz44YfYuHEjtm3bhq+//hqXL19u8Jz58+fjrbfewn/+8x8IgoDk5GRnxyQPkzgmHF7Khh8HL6Uccyb3a/KYknIdthzKwYZ9F/GPeov8NF5Qqf4iQEKj/Y0XCKq7Yvg45Qz+tuWM1Ybn2ZMiLGbmrSVqbU4vFGlpaRg2bBjat28PX19fxMTEIDU11bT/xo0b0Gq1GDx4MAAgMTGxwX4iR7C0XvesSREYNTC0ycZfhVyG1KPXsT8j3+yXfXWNEV+m/ojkg5exfu9Fs6uC2v0XzNoQgNorhowLxSgouWdWCOoEBXg3mZlXENTanH4/5/bt21Cr1abHwcHBOHPmTJP71Wo1CgsL7XqNoCC/FudTq/1bfKwjSTUXIN1s9uZ64jF/PPFYb7Pts+MisXpTJnT6n3sQeasUeOWZQRgxsBOeWrDL4v9PpzfiQEa+xbEMtfstz00F1A77+HxRNL7NyLP42rPjIqFW+zeZuSXc5d/RWTwpl9MLhdFoNA32AQBBEBo8trW/OUpKNDAaLTdOWiPVQUdSzQVIN1tr5ors2h4zJ/Y1a0eI7NoeZXfvNdm+ERTgjRUvjcTv13xvcRxH3ZWApWMDA7xRVFRh9bVb87x7wr9ja3K3XHK5zOoPbKcXipCQEJw4ccL0uKioCMHBwQ32FxUVmR4XFxc32E8kBmuNwk11va1rK3jKxn5bXVjZIE1ic3obxYgRI5Ceno7S0lJUVVVh7969GD16tGl/WFgYvL29kZGRAQDYvn17g/1EUmOrraD+flmj/WxnIFfg9CuKjh07Yt68eZg5cyb0ej2efvppDBw4EC+88AKSkpIwYMAArFy5Em+++SY0Gg0iIyMxc+ZMZ8cksoutX/3W5lTiFQNJnUwQBPtv5ksc2yicR6rZmMs+zGUfd8tlq42CK9wREZFVLBRERGQVCwUREVnllhMoyeX2jbtorWMdSaq5AOlmYy77MJd93CmXrWPcsjGbiIhaD289ERGRVSwURERkFQsFERFZxUJBRERWsVAQEZFVLBRERGQVCwUREVnFQkFERFaxUBARkVUeWSh27tyJyZMnY8KECdiwYYPZ/uzsbCQmJiImJgaLFi1CTU2NJHKtXr0aY8eORUJCAhISEiw+x1E0Gg3i4uKQn59vtk+s82Url1jna/Xq1YiNjUVsbCyWL19utl+s82Url1jn669//SsmT56M2NhYfPHFF2b7xXx/2com5mfyL3/5CxYsWGC23SHnS/Awt27dEsaOHSvcuXNHqKysFOLj44VLly41eE5sbKxw6tQpQRAE4Y033hA2bNggiVy/+c1vhJMnTzo8S2OnT58W4uLihMjISCEvL89svxjnqzm5xDhf33//vfCrX/1K0Ol0QnV1tTBz5kxh7969DZ4jxvlqTi4xztfRo0eFqVOnCnq9XqiqqhLGjh0r5OTkNHiOWO+v5mQT6zOZlpYmPPLII8If//hHs32OOF8ed0WRlpaGYcOGoX379vD19UVMTAxSU1NN+2/cuAGtVovBgwcDABITExvsFysXAGRlZWHt2rWIj4/HkiVLoNPpHJ4LAJKTk7F48WKLa5eLdb5s5QLEOV9qtRoLFiyAl5cXVCoVwsPDUVBQYNov1vmylQsQ53wNHToUX375JZRKJUpKSmAwGODr62vaL+b7y1Y2QJxzdvfuXXz44Yf47W9/a7bPUefL4wrF7du3oVarTY+Dg4NRWFjY5H61Wt1gv1i5Kisr0a9fP8yfPx8pKSkoLy/HmjVrHJ4LAJYuXYqoqCiL+8Q6X7ZyiXW+evfubfqQ5ubmYs+ePRgzZoxpv1jny1YuMd9fKpUKq1atQmxsLIYPH46OHTua9on5/rKVTaxz9tZbb2HevHkICAgw2+eo8+VxhcJoNEIm+3lKXUEQGjy2tV+sXG3btsVnn32G8PBwKJVKzJkzB4cOHXJ4LlvEOl+2iH2+Ll26hDlz5uAPf/gDunfvbtou9vlqKpfY5yspKQnp6em4efMmkpOTTdvFPl/WsolxzjZt2oTQ0FAMHz7c4n5HnS+PKxQhISEoKioyPS4qKmpw66Lx/uLi4iZvbTgzV0FBATZv3mx6LAgClErxlxMR63zZIub5ysjIwOzZs/G73/0OTz75ZIN9Yp4va7nEOl85OTnIzs4GALRp0wYTJkzAhQsXTPvFPF+2solxznbv3o3vv/8eCQkJWLVqFQ4cOIB3333XtN9R58vjCsWIESOQnp6O0tJSVFVVYe/evRg9erRpf1hYGLy9vZGRkQEA2L59e4P9YuXy8fHBihUrkJeXB0EQsGHDBkRHRzs8ly1inS9bxDpfN2/exMsvv4yVK1ciNjbWbL9Y58tWLrHOV35+Pt58801UV1ejuroa+/fvx0MPPWTaL+b7y1Y2Mc7ZF198gV27dmH79u1ISkrCuHHjsHDhQtN+h52v+24Od0E7duwQYmNjhQkTJgh///vfBUEQhLlz5wpnzpwRBEEQsrOzhaeeekqIiYkR/vd//1fQ6XSSyJWammrav2DBAqflqjN27FhT7yIpnC9bucQ4X//3f/8nDB48WHjiiSdM/23cuFH089WcXGK9v1atWiVMmjRJiIuLE1atWiUIgnTeX7ayifmZ3LJli6nXk6PPF1e4IyIiqzzu1hMREdmHhYKIiKxioSAiIqtYKIiIyCoWCiIisoqFgoiIrGKhICIiq1goiBwkISEB6enpAIBdu3ZhwIAB0Gq1AIBFixZh48aNYsYjajYWCiIHiY6OxuHDhwEAR44cQbt27XDixAkIgoBDhw5JYgoWouZgoSBykLpCIQgCTpw4gdmzZ+P777/H6dOn0bVr1wbTQRNJmfjTjxK5qb59+0Kv12P//v3o3r07xo4di3nz5kGpVCImJkbseETNxisKIgd6/PHH8f7772PkyJEIDw+HRqPBzp07MWHCBLGjETUbCwWRA0VHR+PKlSsYMWIEgNrp5NVqNUJDQ0VORtR8nD2WiIis4hUFERFZxUJBRERWsVAQEZFVLBRERGQVCwUREVnFQkFERFaxUBARkVUsFEREZNX/AyKYkrqa2OejAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Plot it all\n",
    "plt.plot(w_list, mse_list, 'b-o')\n",
    "plt.ylabel('Loss')\n",
    "plt.xlabel('w')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-12-01T06:26:02.505123Z",
     "start_time": "2023-12-01T06:25:57.470565Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Epoch: 9 w= 2.0 loss= 0.0\r"
     ]
    }
   ],
   "source": [
    "from time import sleep\n",
    "# compute gradient\n",
    "def gradient(x, y):  # d_loss/d_w\n",
    "    return 2 * x * (x * w - y)\n",
    "\n",
    "# Training loop\n",
    "for epoch in range(10):\n",
    "    for x_val, y_val in zip(x_data, y_data):\n",
    "        # Compute derivative w.r.t to the learned weights\n",
    "        # Update the weights\n",
    "        # Compute the loss and print progress\n",
    "        grad = gradient(x_val, y_val)\n",
    "        w = w - 0.01 * grad\n",
    "        print(w, end= '\\r')\n",
    "        #print(\"\\tgrad: \", x_val, y_val, round(grad, 2))\n",
    "        y_pred = forward(x_val)\n",
    "        l = loss(y_pred, y_val)\n",
    "    sleep(0.5)\n",
    "    print(\"Epoch:\", epoch, \"w=\", round(w, 2), \"loss=\", round(l, 2),  end='\\r')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Mathematics behind Gradient Descent\n",
    "\n",
    "A simple mathematical intuition behind one of the commonly used optimisation algorithms in Machine Learning.\n",
    "\n",
    "https://www.douban.com/note/713353797/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The cost or loss function:\n",
    "\n",
    "$$Cost = \\frac{1}{N} \\sum_{i = 1}^N (Y' -Y)^2$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "![](./img/stats/x2.webp)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Parameters with small changes:\n",
    "$$ m_1 = m_0 - \\delta m,  b_1 = b_0 - \\delta b$$\n",
    "\n",
    "The cost function J is a function of m and b:\n",
    "\n",
    "$$J_{m, b} = \\frac{1}{N} \\sum_{i = 1}^N (Y' -Y)^2 = \\frac{1}{N} \\sum_{i = 1}^N Error_i^2$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "$$\\frac{\\partial J}{\\partial m} = 2 Error \\frac{\\partial}{\\partial m}Error$$\n",
    "\n",
    "$$\\frac{\\partial J}{\\partial b} = 2 Error \\frac{\\partial}{\\partial b}Error$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Let's fit the data with linear regression:\n",
    "\n",
    "$$\\frac{\\partial}{\\partial m}Error = \\frac{\\partial}{\\partial m}(Y' - Y) = \\frac{\\partial}{\\partial m}(mX + b - Y)$$\n",
    "\n",
    "Since $X, b, Y$ are constant:\n",
    "\n",
    "$$\\frac{\\partial}{\\partial m}Error = X$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "$$\\frac{\\partial}{\\partial b}Error = \\frac{\\partial}{\\partial b}(Y' - Y) = \\frac{\\partial}{\\partial b}(mX + b - Y)$$\n",
    "\n",
    "Since $X, m, Y$ are constant:\n",
    "\n",
    "$$\\frac{\\partial}{\\partial m}Error = 1$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Thus:\n",
    "    \n",
    "$$\\frac{\\partial J}{\\partial m} = 2 * Error * X$$\n",
    "$$\\frac{\\partial J}{\\partial b} = 2 * Error$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Let's get rid of the constant 2 and multiplying the learning rate  $\\alpha$, who determines how large a step to take:\n",
    "\n",
    "$$\\frac{\\partial J}{\\partial m} = Error * X *  \\alpha$$\n",
    "$$\\frac{\\partial J}{\\partial b} = Error * \\alpha$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Since $ m_1 = m_0 - \\delta m,  b_1 = b_0 - \\delta b$:\n",
    "\n",
    "$$ m_1 = m_0 -  Error * X * \\alpha$$\n",
    "\n",
    "$$b_1 = b_0 - Error * \\alpha$$\n",
    "\n",
    "**Notice** that the slope b can be viewed as the beta value for X = 1. Thus, the above two equations are in essence the same.\n",
    "\n",
    "Let's represent parameters as $\\Theta$, learning rate as $\\alpha$, and gradient as $\\bigtriangledown J(\\Theta)$, we have:\n",
    "\n",
    "\n",
    "$$\\Theta_1 = \\Theta_0 - \\alpha \\bigtriangledown J(\\Theta)$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "\n",
    "\n",
    "<img src='./img/stats/gd.webp' width = '800' align = 'center'>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Hence,to solve for the gradient, we iterate through our data points using our new $m$ and $b$ values and compute the partial derivatives. \n",
    "\n",
    "This new gradient tells us \n",
    "- the slope of our cost function at our current position  \n",
    "- the direction we should move to update our parameters. \n",
    "\n",
    "- The size of our update is controlled by the learning rate."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-04-07T16:16:42.584919Z",
     "start_time": "2019-04-07T16:16:42.573596Z"
    },
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "# Size of the points dataset.\n",
    "m = 20\n",
    "# Points x-coordinate and dummy value (x0, x1).\n",
    "X0 = np.ones((m, 1))\n",
    "X1 = np.arange(1, m+1).reshape(m, 1)\n",
    "X = np.hstack((X0, X1))\n",
    "# Points y-coordinate\n",
    "y = np.array([3, 4, 5, 5, 2, 4, 7, 8, 11, 8, 12,\n",
    "    11, 13, 13, 16, 17, 18, 17, 19, 21]).reshape(m, 1)\n",
    "\n",
    "# The Learning Rate alpha.\n",
    "alpha = 0.01"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-04-07T16:17:04.134904Z",
     "start_time": "2019-04-07T16:17:04.108505Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def error_function(theta, X, y):\n",
    "    '''Error function J definition.'''\n",
    "    diff = np.dot(X, theta) - y\n",
    "    return (1./2*m) * np.dot(np.transpose(diff), diff)\n",
    "\n",
    "def gradient_function(theta, X, y):\n",
    "    '''Gradient of the function J definition.'''\n",
    "    diff = np.dot(X, theta) - y\n",
    "    return (1./m) * np.dot(np.transpose(X), diff)\n",
    "\n",
    "def gradient_descent(X, y, alpha):\n",
    "    '''Perform gradient descent.'''\n",
    "    theta = np.array([1, 1]).reshape(2, 1)\n",
    "    gradient = gradient_function(theta, X, y)\n",
    "    while not np.all(np.absolute(gradient) <= 1e-5):\n",
    "        theta = theta - alpha * gradient\n",
    "        gradient = gradient_function(theta, X, y)\n",
    "    return theta\n",
    "\n",
    "# source：https://www.jianshu.com/p/c7e642877b0e"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-04-07T16:19:07.236028Z",
     "start_time": "2019-04-07T16:19:07.171443Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optimal parameters Theta: 0.5158328581734093 0.9699216324486175\n",
      "Error function: 405.98496249324046\n"
     ]
    }
   ],
   "source": [
    "optimal = gradient_descent(X, y, alpha)\n",
    "print('Optimal parameters Theta:', optimal[0][0], optimal[1][0])\n",
    "print('Error function:', error_function(optimal, X, y)[0,0])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "![](./images/end.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "## Estimating the Gradient"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "If f is a function of one variable, its derivative at a point x measures how f(x) changes when we make a very small change to x. \n",
    "\n",
    "> It is defined as the limit of the difference quotients:\n",
    "\n",
    "\n",
    "差商（difference quotient）就是因变量的改变量与自变量的改变量两者相除的商。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-04-07T16:08:29.774271Z",
     "start_time": "2019-04-07T16:08:29.771043Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def difference_quotient(f, x, h):\n",
    "    return (f(x + h) - f(x)) / h"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "For many functions it’s easy to exactly calculate derivatives. \n",
    "\n",
    "For example, the square function:\n",
    "\n",
    "        def square(x): \n",
    "            return x * x\n",
    "\n",
    "has the derivative:\n",
    "    \n",
    "        def derivative(x): \n",
    "            return 2 * x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-04-07T16:08:30.714322Z",
     "start_time": "2019-04-07T16:08:30.709209Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def square(x):\n",
    "    return x * x\n",
    "\n",
    "def derivative(x):\n",
    "    return 2 * x\n",
    "\n",
    "derivative_estimate = lambda x: difference_quotient(square, x, h=0.00001)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-04-07T16:09:28.375610Z",
     "start_time": "2019-04-07T16:09:28.372132Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def sum_of_squares(v):\n",
    "    \"\"\"computes the sum of squared elements in v\"\"\"\n",
    "    return sum(v_i ** 2 for v_i in v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-04-07T16:11:00.628162Z",
     "start_time": "2019-04-07T16:11:00.425853Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAD8CAYAAAB0IB+mAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4xLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvDW2N/gAAEdhJREFUeJzt3X+MHPV9xvHnqV2oRFFI6ws4gHsQuagGtW5ysUJFmxhoYqwIB1Qs548WRCSLNkhNlCgCUSWX5p+GiEaqGqAXFUErBLhpCRYQfgVHbqUAPiPjHxiD+RFhy4F1oLhVKiLg0z9mDHvHrnfuZmdm577vl7S63ZnxzFez6+fmZufzGUeEAAAL3681PQAAQD0IfABIBIEPAIkg8AEgEQQ+ACSCwAeARBD4AJAIAh8AEkHgA0AiFjc9gG5LliyJ8fHxpocBAK2yffv2wxExNmi5kQr88fFxTU9PNz0MAGgV2z8rshyndAAgEQQ+ACSCwAeARBD4AJAIAh8AEkHgA0BTrr9e2rJFkjQ5mU/bsiWbXgECHwCa8vGPS+vXS1u26JvfVBb269dn0ytA4ANAU1avljZtykJeyn5u2pRNrwCBDwANmZyUfP5q+XBHkuTDHfn81e+d3hkyAh8AGjI5KcWjWxRLsq4IsWRM8egWAh8AFpyj5+w3bcpeHz29k3+RO2wEPgA0Zdu2d8/Zf+Mbeu+c/rZtlWzOEVHJiudjYmIiaJ4GAHNje3tETAxajiN8AEgEgQ8AiSDwASARBD4AzFfNrRHKIvABYL5qbo1QFoEPAPNVc2uEsgh8AJinulsjlDWUwLd9i+1Xbe/umjZp+6DtHflj7TC2BQCjou7WCGUN6wj/Vklrekz/bkSszB/3D2lbADAaam6NUNZQAj8itkp6bRjrAoDWqLk1QllDa61ge1zSvRFxTv56UtIVko5Impb0lYh4/VjroLUCAMzdKLRWuEnSRyStlHRI0g29FrK90fa07elOp1PhcAAgbZUFfkS8EhFvR8Q7kr4vaVWf5aYiYiIiJsbGxqoaDgAkr7LAt7206+Ulknb3WxYAGtGyStmyhnVZ5h2SfirpLNsHbH9B0vW2d9neKWm1pC8PY1sAMDQtq5Qti374ANKWh7wPd7Lr6Ue4UrafUfjSFgBGWtsqZcsi8AEkq22VsmUR+ADS1bJK2bIIfADpalmlbFl8aQsALceXtgCAGQh8AEgEgQ+gvRKrlC2LwAfQXolVypZF4ANor5bdU7ZpBD6A1kqtUrYsAh9Aa6VWKVsWgQ+gvRKrlC2LwAfQXolVypZFpS0AtByVtgCAGQh8AEjEsG5xeIvtV23v7pr2W7Yftv1c/vODw9gWAGB+hnWEf6ukNbOmXSPpxxGxXNKP89cA8B5aI9RqKIEfEVslvTZr8jpJt+XPb5P0uWFsC8ACQmuEWlV5Dv/kiDiUP/+5pJMr3BaANqI1Qq1q+dI2sms/e17/aXuj7Wnb051Op47hABgRtEaoV5WB/4rtpZKU/3y110IRMRURExExMTY2VuFwAIwaWiPUq8rA3yzp8vz55ZLuqXBbANqI1gi1GtZlmXdI+qmks2wfsP0FSX8n6U9tPyfpwvw1ALyH1gi1orUCALQcrRUAADMQ+ACQCAIfwPxRKdsqBD6A+aNStlUIfADzR6VsqxD4AOaNStl2IfABzBuVsu1C4AOYPyplW4XABzB/VMq2CpW2ANByVNoCAGYg8AEgEQQ+ACSCwAdSRmuEpBD4QMpojZAUAh9IGa0RkkLgAwmjNUJaKg982y/Z3mV7h20usgdGCK0R0lLXEf7qiFhZpDAAQI1ojZAUTukAKaM1QlIqb61g+0VJr0sKSf8UEVP9lqW1AgDMXdHWCotrGMt5EXHQ9ockPWz7mYjYenSm7Y2SNkrSsmXLahgOAKSp8lM6EXEw//mqpLslrZo1fyoiJiJiYmxsrOrhAECyKg182yfYPvHoc0mflrS7ym0CSaFSFnNQ9RH+yZL+y/ZTkp6QdF9EPFDxNoF0UCmLOaj0HH5EvCDpD6rcBpC0GZWyHSplcUxclgm0GJWymAsCH2gxKmUxFwQ+0GZUymIOCHygzaiUxRxwE3MAaDluYg4AmIHAB4BEEPhAk6iURY0IfKBJVMqiRgQ+0CTuKYsaEfhAg6iURZ0IfKBBVMqiTgQ+0CQqZVEjAh9oEpWyqBGVtgDQclTaAgBmIPABIBGVB77tNbb32d5v+5qqtwcA6K3qm5gvkvQ9SRdJWiHp87ZXVLlNoFa0RkCLVH2Ev0rS/oh4ISJ+JelOSesq3iZQH1ojoEWqDvxTJb3c9fpAPg1YGGiNgBZp/Etb2xttT9ue7nQ6TQ8HmBNaI6BNqg78g5JO73p9Wj7tXRExFRETETExNjZW8XCA4aI1Atqk6sDfJmm57TNsHydpg6TNFW8TqA+tEdAilQZ+RLwl6WpJD0raK2lTROypcptArWiNgBahtQIAtBytFQAAMxD4AJAIAh9po1IWCSHwkTYqZZEQAh9po1IWCSHwkTQqZZESAh9Jo1IWKSHwkTYqZZEQAh9po1IWCaHSFgBajkpbAMAMBD4AJILAB4BEEPhoN1ojAIUR+Gg3WiMAhRH4aDdaIwCFEfhoNVojAMVVFvi2J20ftL0jf6ytaltIF60RgOKqPsL/bkSszB/3V7wtpIjWCEBhnNJBu9EaASisstYKticlXSHpiKRpSV+JiNeP9W9orQAAc1dLawXbj9je3eOxTtJNkj4iaaWkQ5Ju6LOOjbanbU93Op0ywwEAHEMtzdNsj0u6NyLOOdZyHOEDwNw13jzN9tKul5dI2l3VttBiVMoCtanyS9vrbe+yvVPSaklfrnBbaCsqZYHaLK5qxRHx51WtGwvIjErZDpWyQIW4LBONolIWqA+Bj0ZRKQvUh8BHs6iUBWpD4KNZVMoCteEm5gDQco1fhw8AGC0EPgAkgsBHOVTKAq1B4KMcKmWB1iDwUQ73lAVag8BHKVTKAu1B4KMUKmWB9iDwUQ6VskBrEPgoh0pZoDWotAWAlqPSFgAwA4EPAIkoFfi2L7O9x/Y7tidmzbvW9n7b+2x/ptwwAQBllT3C3y3pUklbuyfaXiFpg6SzJa2RdKPtRSW3hSrQGgFIRqnAj4i9EbGvx6x1ku6MiDcj4kVJ+yWtKrMtVITWCEAyqjqHf6qkl7teH8inYdTQGgFIxsDAt/2I7d09HuuGMQDbG21P257udDrDWCXmgNYIQDoWD1ogIi6cx3oPSjq96/Vp+bRe65+SNCVl1+HPY1soYXJSmvxkdhrHhztZiwSO8IEFqapTOpslbbB9vO0zJC2X9ERF20IZtEYAklH2ssxLbB+QdK6k+2w/KEkRsUfSJklPS3pA0hcj4u2yg0UFaI0AJIPWCgDQcrRWAADMQOADQCII/LajUhZAQQR+21EpC6AgAr/tqJQFUBCB33JUygIoisBvOW4iDqAoAr/tqJQFUBCB33ZUygIoiEpbAGg5Km0BADMQ+ACQCAIfABJB4DeN1ggAakLgN43WCABqQuA3jdYIAGpC4DeM1ggA6lL2FoeX2d5j+x3bE13Tx23/n+0d+ePm8kNdmGiNAKAuZY/wd0u6VNLWHvOej4iV+eOqkttZuGiNAKAmpQI/IvZGxL5hDSZJtEYAUJOhtFaw/RNJX42I6fz1uKQ9kp6VdETS30TEfw5aD60VAGDuirZWWFxgRY9IOqXHrOsi4p4+/+yQpGUR8QvbH5P0Q9tnR8SRHuvfKGmjJC1btmzQcAAA8zQw8CPiwrmuNCLelPRm/ny77ecl/a6k9x2+R8SUpCkpO8Kf67YAAMVUclmm7THbi/LnZ0paLumFKrbVOCplAbRE2csyL7F9QNK5ku6z/WA+608k7bS9Q9IPJF0VEa+VG+qIolIWQEvQD38Y8pD34U52PT2VsgBqRD/8mlApC6AtCPySqJQF0BYEfllUygJoCQK/LCplAbQEX9oCQMvxpS0AYAYCHwASQeADQCIIfFojAEgEgU9rBACJIPC5iTiARCQf+LRGAJAKAn+S1ggA0pB84NMaAUAqCHxaIwBIBK0VAKDlaK0AAJih7C0Ov2P7Gds7bd9t+6Suedfa3m97n+3PlB8qAKCMskf4D0s6JyJ+X9Kzkq6VJNsrJG2QdLakNZJuPHpT86GjUhYACikV+BHxUES8lb98TNJp+fN1ku6MiDcj4kVJ+yWtKrOtvqiUBYBChnkO/0pJP8qfnyrp5a55B/Jpw0elLAAUMjDwbT9ie3ePx7quZa6T9Jak2+c6ANsbbU/bnu50OnP951TKAkBBiwctEBEXHmu+7SskfVbSBfHeNZ4HJZ3etdhp+bRe65+SNCVll2UOHvJMk5PS5Cez0zg+3MkqZjnCB4D3KXuVzhpJX5N0cUT8smvWZkkbbB9v+wxJyyU9UWZbfVEpCwCFlD2H/4+STpT0sO0dtm+WpIjYI2mTpKclPSDpixHxdslt9UalLAAUQqUtALQclbYAgBkIfABIBIEPAIkg8AEgEQQ+ACRipK7Ssd2R9LMSq1gi6fCQhlMFxlcO4yuH8ZUzyuP7nYgYG7TQSAV+Wbani1ya1BTGVw7jK4fxlTPq4yuCUzoAkAgCHwASsdACf6rpAQzA+MphfOUwvnJGfXwDLahz+ACA/hbaET4AoI9WBb7ty2zvsf2O7YlZ8wbeNN32GbYfz5e7y/ZxFY/3rryL6A7bL9ne0We5l2zvyperrXuc7UnbB7vGuLbPcmvy/brf9jU1ju87tp+xvdP23bZP6rNcbftv0L7IW4Lflc9/3PZ4lePpsf3TbW+x/XT+f+WveyzzKdtvdL3vX695jMd8v5z5h3wf7rT90RrHdlbXftlh+4jtL81aptH9V0pEtOYh6fcknSXpJ5ImuqavkPSUpOMlnSHpeUmLevz7TZI25M9vlvSXNY79Bklf7zPvJUlLGtifk5K+OmCZRfn+PFPScfl+XlHT+D4taXH+/NuSvt3k/iuyLyT9laSb8+cbJN1V83u6VNJH8+cnSnq2xxg/Jeneuj9vRd8vSWuV3S7Vkj4h6fGGxrlI0s+VXeM+MvuvzKNVR/gRsTci9vWYNfCm6bYt6XxJP8gn3Sbpc1WOd9a210u6o47tDdkqSfsj4oWI+JWkO5Xt78pFxEMR8Vb+8jFld05rUpF9sU7ZZ0vKPmsX5O9/LSLiUEQ8mT//H0l7VdX9pKuzTtK/ROYxSSfZXtrAOC6Q9HxElCkGHSmtCvxjKHLT9N+W9N9dAVLdjdXf748lvRIRz/WZH5Iesr3d9saaxnTU1fmfzbfY/mCP+fXdkP7YrlR21NdLXfuvyL54d5n8s/aGss9e7fLTSX8o6fEes8+1/ZTtH9k+u9aBDX6/RuUzt0H9D9Ka3H/zNvCetnWz/YikU3rMui4i7ql7PIMUHO/ndeyj+/Mi4qDtDym7e9gzEbG16vFJuknSt5T9B/yWstNOVw5ju0UV2X+2r5P0lqTb+6ymsv3XVrZ/U9K/S/pSRByZNftJZacp/jf/3uaHym5DWpeRf7/y7/culnRtj9lN7795G7nAjwE3Te+jyE3Tf6HsT8PF+ZFX3xurz8Wg8dpeLOlSSR87xjoO5j9ftX23slMHQ/kPUHR/2v6+pHt7zCp8Q/r5KLD/rpD0WUkXRH4Ctcc6Ktt/sxTZF0eXOZC/9x9Q9tmrje1fVxb2t0fEf8ye3/0LICLut32j7SURUUufmALvV6WfuYIukvRkRLwye0bT+6+MhXJKZ+BN0/Ow2CLpz/JJl0uq4y+GCyU9ExEHes20fYLtE48+V/ZF5e4axqVZ50Uv6bPdbZKWO7vC6Thlf+Zurml8ayR9TdLFEfHLPsvUuf+K7IvNyj5bUvZZe7TfL6oq5N8X/LOkvRHx932WOeXo9wq2VynLgVp+KRV8vzZL+ov8ap1PSHojIg7VMb4uff8qb3L/ldb0t8ZzeSgLpQOS3pT0iqQHu+Zdp+wKin2SLuqafr+kD+fPz1T2i2C/pH+TdHwNY75V0lWzpn1Y0v1dY3oqf+xRdiqjrv35r5J2Sdqp7D/Z0tnjy1+vVXa1x/M1j2+/snO5O/LHzbPHV/f+67UvJP2tsl9KkvQb+Wdrf/5ZO7Ou/ZVv/zxlp+h2du23tZKuOvo5lHR1vq+eUvZl+B/VOL6e79es8VnS9/J9vEtdV+TVNMYTlAX4B7qmjcT+K/ug0hYAErFQTukAAAYg8AEgEQQ+ACSCwAeARBD4AJAIAh8AEkHgA0AiCHwASMT/A7LM6/xy4DGhAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# plot to show they're basically the same\n",
    "import matplotlib.pyplot as plt\n",
    "x = range(-10,10)\n",
    "plt.plot(x, list(map(derivative, x)), 'rx')           # red  x\n",
    "plt.plot(x, list(map(derivative_estimate, x)), 'b+')  # blue +\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "When f is a function of many variables, it has multiple partial derivatives."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-04-07T16:08:32.859665Z",
     "start_time": "2019-04-07T16:08:32.850606Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def partial_difference_quotient(f, v, i, h):\n",
    "    # add h to just the i-th element of v\n",
    "    w = [v_j + (h if j == i else 0)\n",
    "         for j, v_j in enumerate(v)]\n",
    "    return (f(w) - f(v)) / h\n",
    "\n",
    "def estimate_gradient(f, v, h=0.00001):\n",
    "    return [partial_difference_quotient(f, v, i, h)\n",
    "            for i, _ in enumerate(v)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Using the Gradient"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-04-07T16:08:34.771460Z",
     "start_time": "2019-04-07T16:08:34.766201Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def step(v, direction, step_size):\n",
    "    \"\"\"move step_size in the direction from v\"\"\"\n",
    "    return [v_i + step_size * direction_i\n",
    "            for v_i, direction_i in zip(v, direction)]\n",
    "\n",
    "def sum_of_squares_gradient(v):\n",
    "    return [2 * v_i for v_i in v]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-04-07T16:30:36.585523Z",
     "start_time": "2019-04-07T16:30:36.581608Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "from linear_algebra import distance, vector_subtract, scalar_multiply\n",
    "from functools import reduce\n",
    "import math, random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-04-07T16:34:01.449426Z",
     "start_time": "2019-04-07T16:34:01.419878Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "using the gradient\n",
      "[-4, 10, 6]\n",
      "[-4, 10, 6] 152\n",
      "[-1.4566787203484681, 3.641696800871171, 2.1850180805227026] 20.15817249600249\n",
      "[-0.5304782235790126, 1.3261955589475318, 0.7957173353685193] 2.6733678840696777\n",
      "[-0.19318408497395115, 0.482960212434878, 0.28977612746092685] 0.35454086152861664\n",
      "[-0.07035178642288623, 0.17587946605721566, 0.10552767963432938] 0.04701905160246833\n",
      "[-0.025619987555179666, 0.0640499688879492, 0.03842998133276951] 0.006235645742111834\n",
      "[-0.0093300226718057, 0.023325056679514268, 0.013995034007708552] 0.0008269685690358806\n",
      "[-0.0033977113715970304, 0.008494278428992584, 0.005096567057395551] 0.00010967220436445803\n",
      "[-0.0012373434632228497, 0.003093358658057131, 0.0018560151948342769] 1.4544679036813049e-05\n",
      "[-0.0004506029731597509, 0.0011265074328993788, 0.0006759044597396269] 1.9289088744938724e-06\n",
      "[-0.00016409594058189027, 0.00041023985145472635, 0.00024614391087283554] 2.558110382968256e-07\n",
      "[-5.975876618530154e-05, 0.00014939691546325416, 8.963814927795238e-05] 3.3925546291900725e-08\n",
      "[-2.1762330764102098e-05, 5.440582691025532e-05, 3.264349614615315e-05] 4.499190882718763e-09\n",
      "[-7.925181032313087e-06, 1.9812952580782747e-05, 1.1887771548469638e-05] 5.96680696751885e-10\n",
      "[-2.8861106411699463e-06, 7.215276602924873e-06, 4.32916596175492e-06] 7.913152901420692e-11\n",
      "minimum v [-1.6064572436336709e-06, 4.0161431090841815e-06, 2.409685865450507e-06]\n",
      "minimum value 2.4516696318419405e-11\n"
     ]
    }
   ],
   "source": [
    "print(\"using the gradient\")\n",
    "\n",
    "# generate 3 numbers \n",
    "v = [random.randint(-10,10) for i in range(3)]\n",
    "print(v)\n",
    "tolerance = 0.0000001\n",
    "\n",
    "n = 0\n",
    "while True:\n",
    "    gradient = sum_of_squares_gradient(v)   # compute the gradient at v\n",
    "    if n%50 ==0:\n",
    "        print(v, sum_of_squares(v))\n",
    "    next_v = step(v, gradient, -0.01)       # take a negative gradient step\n",
    "    if distance(next_v, v) < tolerance:     # stop if we're converging\n",
    "        break\n",
    "    v = next_v                              # continue if we're not\n",
    "    n += 1\n",
    "\n",
    "print(\"minimum v\", v)\n",
    "print(\"minimum value\", sum_of_squares(v))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Choosing the Right Step Size"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Although the rationale for moving against the gradient is clear, \n",
    "- how far to move is not. \n",
    "    - Indeed, choosing the right step size is more of an art than a science."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Methods:\n",
    "1. Using a fixed step size\n",
    "1. Gradually shrinking the step size over time\n",
    "1. At each step, choosing the step size that minimizes the value of the objective function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-04-07T16:13:14.748507Z",
     "start_time": "2019-04-07T16:13:14.745314Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "step_sizes = [100, 10, 1, 0.1, 0.01, 0.001, 0.0001, 0.00001]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "It is possible that certain step sizes will result in invalid inputs for our function. \n",
    "\n",
    "So we’ll need to create a “safe apply” function\n",
    "- returns infinity for invalid inputs:\n",
    "    - which should never be the minimum of anything"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-04-07T16:13:15.408907Z",
     "start_time": "2019-04-07T16:13:15.403349Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def safe(f):\n",
    "    \"\"\"define a new function that wraps f and return it\"\"\"\n",
    "    def safe_f(*args, **kwargs):\n",
    "        try:\n",
    "            return f(*args, **kwargs)\n",
    "        except:\n",
    "            return float('inf')  # this means \"infinity\" in Python\n",
    "    return safe_f"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Putting It All Together"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "- **target_fn** that we want to minimize\n",
    "- **gradient_fn**. \n",
    "\n",
    "For example, the target_fn could represent the errors in a model as a function of its parameters, \n",
    "\n",
    "To choose a starting value for the parameters `theta_0`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-04-07T16:13:17.051767Z",
     "start_time": "2019-04-07T16:13:17.028782Z"
    },
    "code_folding": [],
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def minimize_batch(target_fn, gradient_fn, theta_0, tolerance=0.000001):\n",
    "    \"\"\"use gradient descent to find theta that minimizes target function\"\"\"\n",
    "\n",
    "    step_sizes = [100, 10, 1, 0.1, 0.01, 0.001, 0.0001, 0.00001]\n",
    "\n",
    "    theta = theta_0                           # set theta to initial value\n",
    "    target_fn = safe(target_fn)               # safe version of target_fn\n",
    "    value = target_fn(theta)                  # value we're minimizing\n",
    "\n",
    "    while True:\n",
    "        gradient = gradient_fn(theta)\n",
    "        next_thetas = [step(theta, gradient, -step_size)\n",
    "                       for step_size in step_sizes]\n",
    "\n",
    "        # choose the one that minimizes the error function\n",
    "        next_theta = min(next_thetas, key=target_fn)\n",
    "        next_value = target_fn(next_theta)\n",
    "\n",
    "        # stop if we're \"converging\"\n",
    "        if abs(value - next_value) < tolerance:\n",
    "            return theta\n",
    "        else:\n",
    "            theta, value = next_theta, next_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-04-07T16:13:17.853373Z",
     "start_time": "2019-04-07T16:13:17.845012Z"
    },
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "minimum v [0.0009304595970494407, -0.001196305196206424, -0.00026584559915698326]\n",
      "minimum value 2.367575066803034e-06\n"
     ]
    }
   ],
   "source": [
    "# minimize_batch\"\n",
    "v = [random.randint(-10,10) for i in range(3)]\n",
    "v = minimize_batch(sum_of_squares, sum_of_squares_gradient, v)\n",
    "print(\"minimum v\", v)\n",
    "print(\"minimum value\", sum_of_squares(v))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Sometimes we’ll instead want to maximize a function, which we can do by minimizing its negative"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-10-27T07:13:08.983326Z",
     "start_time": "2018-10-27T07:13:08.974094Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def negate(f):\n",
    "    \"\"\"return a function that for any input x returns -f(x)\"\"\"\n",
    "    return lambda *args, **kwargs: -f(*args, **kwargs)\n",
    "\n",
    "def negate_all(f):\n",
    "    \"\"\"the same when f returns a list of numbers\"\"\"\n",
    "    return lambda *args, **kwargs: [-y for y in f(*args, **kwargs)]\n",
    "\n",
    "def maximize_batch(target_fn, gradient_fn, theta_0, tolerance=0.000001):\n",
    "    return minimize_batch(negate(target_fn),\n",
    "                          negate_all(gradient_fn),\n",
    "                          theta_0,\n",
    "                          tolerance)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Using the batch approach, each gradient step requires us to make a prediction and compute the gradient for the whole data set, which makes each step take a long time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Error functions are additive\n",
    "- The predictive error on the whole data set is simply the sum of the predictive errors for each data point.\n",
    "\n",
    "When this is the case, we can instead apply a technique called **stochastic gradient descent** \n",
    "- which computes the gradient (and takes a step) for only one point at a time. \n",
    "- It cycles over our data repeatedly until it reaches a stopping point."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Stochastic Gradient Descent"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "During each cycle, we’ll want to iterate through our data in a random order:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-10-27T07:20:12.768921Z",
     "start_time": "2018-10-27T07:20:12.763245Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "def in_random_order(data):\n",
    "    \"\"\"generator that returns the elements of data in random order\"\"\"\n",
    "    indexes = [i for i, _ in enumerate(data)]  # create a list of indexes\n",
    "    random.shuffle(indexes)                    # shuffle them\n",
    "    for i in indexes:                          # return the data in that order\n",
    "        yield data[i]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "This approach avoids circling around near a minimum forever\n",
    "- whenever we stop getting improvements we’ll decrease the step size and eventually quit."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-10-28T07:35:19.050828Z",
     "start_time": "2018-10-28T07:35:19.015811Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "def minimize_stochastic(target_fn, gradient_fn, x, y, theta_0, alpha_0=0.01):\n",
    "    data = list(zip(x, y))\n",
    "    theta = theta_0                             # initial guess\n",
    "    alpha = alpha_0                             # initial step size\n",
    "    min_theta, min_value = None, float(\"inf\")   # the minimum so far\n",
    "    iterations_with_no_improvement = 0\n",
    "\n",
    "    # if we ever go 100 iterations with no improvement, stop\n",
    "    while iterations_with_no_improvement < 100:\n",
    "        value = sum( target_fn(x_i, y_i, theta) for x_i, y_i in data )\n",
    "\n",
    "        if value < min_value:\n",
    "            # if we've found a new minimum, remember it\n",
    "            # and go back to the original step size\n",
    "            min_theta, min_value = theta, value\n",
    "            iterations_with_no_improvement = 0\n",
    "            alpha = alpha_0\n",
    "        else:\n",
    "            # otherwise we're not improving, so try shrinking the step size\n",
    "            iterations_with_no_improvement += 1\n",
    "            alpha *= 0.9\n",
    "\n",
    "        # and take a gradient step for each of the data points\n",
    "        for x_i, y_i in in_random_order(data):\n",
    "            gradient_i = gradient_fn(x_i, y_i, theta)\n",
    "            theta = vector_subtract(theta, scalar_multiply(alpha, gradient_i))\n",
    "\n",
    "    return min_theta"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-10-28T07:35:20.053076Z",
     "start_time": "2018-10-28T07:35:20.048925Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "def maximize_stochastic(target_fn, gradient_fn, x, y, theta_0, alpha_0=0.01):\n",
    "    return minimize_stochastic(negate(target_fn),\n",
    "                               negate_all(gradient_fn),\n",
    "                               x, y, theta_0, alpha_0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-10-28T07:45:14.892154Z",
     "start_time": "2018-10-28T07:45:14.862917Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "print(\"using minimize_stochastic_batch\")\n",
    "\n",
    "x = list(range(101))\n",
    "y = [3*x_i + random.randint(-10, 20) for x_i in x]\n",
    "theta_0 = random.randint(-10,10) \n",
    "v = minimize_stochastic(sum_of_squares, sum_of_squares_gradient, x, y, theta_0)\n",
    "\n",
    "print(\"minimum v\", v)\n",
    "print(\"minimum value\", sum_of_squares(v))\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Scikit-learn has a Stochastic Gradient Descent module  http://scikit-learn.org/stable/modules/sgd.html"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "幻灯片",
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.7"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}