{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Gradient Descent" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1. Gradient" ] }, { "cell_type": "code", "execution_count": 57, "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "import matplotlib.pylab as plt" ] }, { "cell_type": "code", "execution_count": 58, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAEKCAYAAAARnO4WAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAIABJREFUeJzt3Xd8leX9//HXlQFhhL1HCHsPISSIG3APtFUroIIIVK1Wf23t19ZaWztsbW2rVassBwKiuBFxAIpoCRA2hLAhzCQQMiA71++P+6BpTCCB3Oc+J+f9fDx4ZJz75Ppwn3PeuXN97us+xlqLiIjUfmFeFyAiIv6hwBcRCREKfBGREKHAFxEJEQp8EZEQocAXEQkRCnwRkRChwBcRCREKfBGREBHhdQFltWjRwsbGxnpdhohI0EhKSsqw1rasyrYBFfixsbGsXr3a6zJERIKGMWZvVbfVlI6ISIhQ4IuIhAgFvohIiHA18I0xTYwx840xW40xycaY890cT0REKud20/YZYJG19mZjTB2gvsvjiYhIJVwLfGNMI+BiYAKAtbYQKHRrPBEROT03p3S6AOnAy8aYtcaY6caYBi6OJyIip+Fm4EcAg4H/WGvPA04Aj5TfyBgzxRiz2hizOj093cVyREQCT9LeTKYt2+WXsdwM/P3Afmttou/r+Ti/AP6HtXaqtTbOWhvXsmWVFouJiNQKG/dnMWHmSmYn7iW3oNj18VwLfGvtYSDVGNPT962RwBa3xhMRCSZbDmZzx8xEGtWLZPbkYTSs6/6FD9we4QFgtu8MnV3AXS6PJyIS8FIO53D7jETqRYYzd/Iw2jep55dxXQ18a+06IM7NMUREgsmOtBzGTV9BRJhhzuRhxDT339nqWmkrIuInO9NzGTMtETDMnTKMzi38e+KiAl9ExA/2ZJxg7LQVlJZa5k5OoGvLhn6vQYEvIuKy1GMnGTttBYXFpcyZPIzuraM9qSOgrocvIlLb7M88yW1TV3CisIQ5kxPo2cabsAcd4YuIuOZQVh5jpyWSnV/E63cn0LddY0/rUeCLiLjgSHY+Y6auIPNEIbPuTqB/B2/DHhT4IiI1Li0nnzHTVpCeU8ArE+MZ1LGJ1yUBmsMXEalRGbkFjJuWyOGsfF6dGM+QTk29LulbOsIXEakhp8I+NfMkMycMZWhsM69L+h86whcRqQHpOQWMnbaC1MyTzBg/lGFdmntd0vco8EVEzlFaTj5jpyVyIDOPmROGMrxrC69LqpACX0TkHKRlOw3ag8fzefmuwDyyP0WBLyJylk6denk422nQxncOrDn78hT4IiJn4XCWc2Sflp3PaxPjiQuwBm1FFPgiItV0KCuPMVNXkJFbyGt3xzOkU+CHPSjwRUSq5cDxvG9X0L52dzyDYwLnPPszUeCLiFTR/syTjJm2guMni5g1KSFgVtBWlQJfRKQKUo85YZ+d51wIbWCQhT0o8EVEzij1mHOJ49yCYmZPGhYQF0I7Gwp8EZHT2JWey9hpieQVlTB7UgL92gdn2IMCX0SkUimHcxg3PRFrLW9MGUbvto28LumcKPBFRCqw6UAWd8xIpE5EGLMnnU+3Vv5/D9qapsAXESknaW8mE15eSaOoSOZMTqBT8wZel1QjXA18Y8weIAcoAYqttXFujicicq7+u/Mod7+6ilbRdZk9eRjtm9TzuqQa448j/MustRl+GEdE5Jx8uS2dKa+tJqZZfWZPSqBVoyivS6pRmtIREQE+3XyY++espVurhsy6O57mDet6XVKNc/sdryzwqTEmyRgzxeWxRETOyofrD3Lv7DX0bteIuZOH1cqwB/eP8C+w1h40xrQCPjPGbLXWLiu7ge8XwRSAmJgYl8sREflfb61O5f/e3kBcp2bMmBBHdFSk1yW5xtUjfGvtQd/HNOBdIL6CbaZaa+OstXEtW7Z0sxwRkf8xa8VeHp6/gQu6teDVifG1OuzBxcA3xjQwxkSf+hy4Atjk1ngiItXx4pc7eey9TYzq3Yppd8ZRr0641yW5zs0pndbAu8aYU+PMsdYucnE8EZEzstby1Ccp/OeLnVw3oC3/uHUQdSLcbmcGBtcC31q7Cxjo1s8XEamuklLLY+9vYk7iPsYlxPDE6H6Ehxmvy/IbnZYpIiGhsLiUn725jgUbDnHfpV15+Mqe+GYgQoYCX0RqvbzCEu6dncQXKek8cnUv7rmkq9cleUKBLyK1WlZeEZNeXcXqvZk8+YP+jIkP3dO/FfgiUmul5xQwfuZKtqfl8NyYwVw7oK3XJXlKgS8itdKB43ncPj2RQ1l5TB8/lEt6aJ2PAl9Eap0dabncMSOR3IJiXr87gbjYZl6XFBAU+CJSq2w6kMWdM1cSZgzzppxPn3bB/S5VNUmBLyK1xjc7MpgyK4nG9SJ5fVICnVvUjjcuqSmhsbxMRGq9BRsOMv7llbRvUo/5956vsK+AjvBFJOi98vVufr9gC0M7NWPanXE0rl+7L4J2thT4IhK0rLX87ZMUXvhiJ1f0ac2zY84jKrL2XwTtbCnwRSQoFZeU8qt3NvJW0n7GJsTwhxC7Ls7ZUOCLSNDJKyzhJ3PWsGRrGg+N6s6DI7uH3HVxzoYCX0SCSuaJQia+uor1qcf54439uH1YJ69LChoKfBEJGgeO53HnjERSM/N4YdwQrurXxuuSgooCX0SCwtbD2YyfuZKThSXMmhhPQpfmXpcUdBT4IhLwVu4+xt2vrqJ+nXDeuud8erXR6tmzocAXkYD24fqD/PzN9XRoVo/XJsbToWl9r0sKWgp8EQlI1lpe/HIXf120lfjYZky9cwhN6tfxuqygpsAXkYBTXFLK4x9sZnbiPq4f2I6/3TxAC6pqgAJfRALKiYJiHpi7liVb07jnkq788sqehGlBVY1Q4ItIwEjLyWfiK6vYcjBb59i7QIEvIgFh+5EcJry8imMnCpl2Zxwje7f2uqRax/XAN8aEA6uBA9ba69weT0SCz4pdR5ny2mrqRIQz78fDGNChidcl1Ur+uB7+g0CyH8YRkSD0/roD3DEjkVaNonj3vuEKexe5GvjGmA7AtcB0N8cRkeBjreX5pTt48I11DI5pytv3DKdjM51j7ya3p3T+BfwSiK5sA2PMFGAKQExMjMvliEggKCwu5TfvbeTN1fsZPagdT908gLoROu3Sba4d4RtjrgPSrLVJp9vOWjvVWhtnrY1r2bKlW+WISIDIPFHIHTMSeXP1fh4Y0Y1/3jpIYe8nbh7hXwDcYIy5BogCGhljXrfW3u7imCISwHam53L3K6s4eDyff/1oEDee197rkkKKa0f41tpfWWs7WGtjgduAJQp7kdD1zY4Mbnr+a3Lyi5kzOUFh7wGdhy8irpu7ch+PvbeJzi0aMHPCUDVnPeKXwLfWfgF84Y+xRCRwlJRanlyYzPTlu7m4R0ueG3sejaIivS4rZOkIX0RccaKgmAffWMvnyWmMP78Tj13Xh4hwfyz9kcoo8EWkxh08nsfdr64m5XA2v7+hL+OHx3pdkqDAF5Eati71OJNfW01+YQkzJwzl0p6tvC4pcB1PhaSX4ehOuPVV14dT4ItIjXl/3QF+OX8DLaPrMntSAj1aV7rmMnSVlsLuL2DldNj2MVgLPa+G4gKIqOvq0Ap8ETlnJaWWpz7Zyktf7iI+thkv3D6YFg3dDa+gk3cc1s+FVdPh6A6o3xwueBCG3AVN/XMZaAW+iJyTrLwiHnxjLV+kpDM2IYbfXd+XOhFqzn7r8EZYOQ02vgVFJ6HDULhpKvQZDZFRfi1FgS8iZ21nei6TX1vNvqMn9YYlZRUXwpb3naP51BUQEQX9b4ahk6HdIM/KUuCLyFlZmpLGT+euJTI8jNcnJTCsS3OvS/Je1n5Y/TKseRVOpEPTznDFn2DQWKjfzOvqFPgiUj3WWqYu28VfFm2lV5tGTL1jSGivnLUWdn3hHM2nLHS+7nEVDJ0EXUdAWOBMbynwRaTK8otKeOTtDby37iDX9m/L324ZQP06IRoj3zZhZ8DR7VCvGQz/KcRN9FsTtrpC9JESkeo6lJXHj2clsWF/Fr+4ogc/uawbxhivy/K/w5tg1TTY8KbThG0fBze9BH1u9HsTtroU+CJyRkl7M/nxrCTyCouZdmccl/cJsTcYLy6E5A+cs23+pwk7Cdqd53V1VabAF5FKWWt5PXEfT3y4mXZN6jFncogtpqqwCftHGDQuIJqw1aXAF5EK5ReV8Oi7m3h7zX4u69mSf/3oPBrXD4ErXVbYhL3SOaUywJqw1aXAF5HvST12knteT2LzwWweHNmdB0d2Jyysls/X52fBulMrYU81YR/wNWFjva6uRijwReR/fLktnZ/OXYu1lpkT4hjRq5bP13+vCTsEbnwR+t4U8E3Y6lLgiwgApaWWF77YwdOfbaNn62heumMInZo38Losd5xqwq6aDvv+6zRh+90MQ++G9oO9rs41CnwRITu/iJ/NW8/nyUcYPagdT/6gf+08vz7rgHM54qRX4USaM1Vz+R/gvNuDsglbXbXwERWR6kg5nMM9ryeReuwkj1/fhwnDY2vX+fXWwu4vnaP5rQvBlkL3KyB+MnQdGdRN2OpS4IuEsA/XH+SX8zfQMCqCuVOGMTS2Fh3l5mfB+jecoM/Y5mvC3u9cjrhZZ6+r84QCXyQEFRaX8uTHybz89R6GdGrKC+MG07pRLWlQHtnsLJDa8CYUnYB2g+HG//iasPW8rs5TCnyRELM/8yQ/mbOW9anHmTA8ll9f0zv4r1//bRN2Buz7BsLr+lbC3u2cdSOAAl8kpCxOPsLP3lzvnJEzbjDX9G/rdUnnJusAJL3irITNPQJNOsHlT8B5d4REE7a6XAt8Y0wUsAyo6xtnvrX2cbfGE5HKFZWU8vdPU3jpy130aduIF8YNJrZFkJ5yaS3sXuacO1+2CTt0EnQbFVJN2Opy8wi/ABhhrc01xkQCy40xH1trV7g4poiUczgrnwfmrmHVnkzGJsTw2+v6EBUZ7nVZ1ZefXaYJmwL1msL5P3FWwoZoE7a6qhT4xphWwAVAOyAP2ASsttaWVnYfa60Fcn1fRvr+2XOqVkSqZdm2dB6at478ohKeuW0Qowe197qk6juyxTmaXz9PTdhzdNrAN8ZcBjwCNAPWAmlAFHAj0NUYMx942lqbXcn9w4EkoBvwvLU2sYJtpgBTAGJiYs7+fyIi3yoptfzr8208t3QH3Vs15IVxQ+jWqqHXZVVdcSFs/dBpwu792mnC9vshxE9SE/YcnOkI/xpgsrV2X/kbjDERwHXA5cDbFd3ZWlsCDDLGNAHeNcb0s9ZuKrfNVGAqQFxcnP4CEDlHaTn5PDh3Hf/ddZRbhnTgidH9qFcnSKZwsg86TdikV9SEdcFpA99a+/BpbisG3qvKINba48aYL4CrcKaDRMQFy7dn8NC8deQWFPHUzQO4Na6j1yWdmbWw5yvn3PmtH/masJeXacIGyS+rIFDVOfxZwP3W2izf17HADGvtyNPcpyVQ5Av7esAo4K/nXLGIfE9RSSlPf7qNl5btpEuLBrw+KZ5ebRp5XdbpVdiEvc/XhO3idXW1UlXP0lkOJBpjfga0Bx4Gfn6G+7QFXvXN44cBb1prF5x1pSJSoX1HT/LAG85CqjHxHXnsuj6BfeGzI1uckN8wDwpznbcIHP0C9PuBmrAuq9Kzwlr7kjFmM7AUyADOs9YePsN9NgDB82aPIkHo/XUHePTdTRgDz48dzLUDAnQhVUkRJH/oBH3ZJuzQSdBBTVh/qeqUzh3AY8CdwABgoTHmLmvtejeLE5GKnSgo5vEPNjM/aT9DOjXlmdsG0aFpfa/L+r7sg86liJNegdzD0CQGRv3eacI2aO51dSGnqn/3/RC40FqbBsw1xrwLvIKO4EX8btOBLH46dy27j57ggRHdeHBkdyLCA2h1qbWwZ7lz7nzyAqcJ220UxD+rJqzHqjqlc2O5r1caYxLcKUlEKmKtZebXe/jrx1tp2iCSOZOGcX7XADpKzs925uVXTYf0rRDVBIbd61zATE3YgHCmhVe/AV6w1h4rf5u1ttAYMwKor2asiLuO5hbwi7fWszQlnVG9W/PUzQNo1qCO12U50pKdkF//htOEbTsIRj/vzNGrCRtQznSEvxH40BiTD6wB0nFW2nYHBgGfA392tUKRELc0JY1fzt9AVl4RT4zuyx3DOnn/jlQlRbB1AaycDnuX+5qwP4Chk533hPW6PqnQmQL/ZmvtBcaYX+JcVqEtkA28Dkyx1ua5XaBIqMorLOHPC5OZtWIvPVtH89rEeHq39fjc+uxDZVbCHobGMTDqd3DenWrCBoEzBf4QY0wnYBxwWbnb6uFcSE1Eatj61OP8v3nr2JVxgkkXduYXV/b07gqX32vCljjN16HPOCti1YQNGmcK/BeBRUAXYHWZ7xucK1+qEyNSg4pLSnnhi508u3g7LaPrMmdSAsO7tfCmmIIc30rYGZCe/F0TNm4iNO/qTU1yTs50LZ1ngWeNMf+x1t7rp5pEQtLeoyd4aN461u47zuhB7Xjihn40rh/p/0K+14QdCDc85zRh6wTguf5SZVU9LVNhL+ISay1vrErlDwu2EBFmeHbMedwwsJ1/izjVhF01w7mQWXgd6PsDiJ/sXI5YTdhaIYAvuCFS+2XkFvDI2xv5PPkIw7s25++3DKRdEz+eyphz+LsmbM4hpwk78nEYfCc08GgqSVyjwBfxyGdbjvCrdzaQnV/MY9f14a7hsYSF+eFI2lrnejYrpzlH9aXF0HUkXPdP571h1YSttRT4In6WdbKI33+4mXfWHqB320bMnjSInm2i3R/4e03YxpBwj5qwIUSBL+JHS7Ye4VfvbCQjt5CfjuzO/Zd1o06Ey9fBSdtapgmbA20GwA3/hn43qwkbYhT4In6QlVfEHxds4a2k/fRsHc2M8UPp176xewOWFDnvHrVqepkm7E3OStgOcWrChigFvojLvtyWziNvb+BIdj4/uawrPx3ZnboRLs2T5xz2XY74ZV8TtqPThD3vDmjY0p0xJWgo8EVckpNfxJ8+SuaNVal0b9WQF++7gIEdm9T8QNbC3m98K2E//K4Je+0/oMeVasLKtxT4Ii74ans6/zd/A4ez87nnkq48NKp7zV8aoSDHdzniGZC2xWnCxv/YuRyxmrBSAQW+SA3KOlnEHz9y5uq7tGzA/HuHMzimac0Okp7izM2vm6smrFSLAl+khny88RCPvb+ZzJOF3HepM1dfY0f1JcWQ8pFz7vz/NGEnQYehasJKlSjwRc5RWnY+j72/iU82H6Fvu0a8clcNnoHzbRP2Fcg56GvC/ta5HLGasFJNCnyRs2St5c3Vqfzxo2QKi0v5v6t6Mfmizuf+/rLWwr7/OkfzyR/4mrAj4Nqn1YSVc6LAFzkLe4+e4FfvbOSbnUdJ6NyMv/xwAJ1bNDi3H1qQW6YJu/m7JmzcRGjRrWYKl5DmWuAbYzoCrwFtgFJgqrX2GbfGE/GH4pJSXv56D09/lkJkWBh/uqkfY4bGnNs1cNJTnJBfPxcKsqFNf7j+Weh/M9Q5x18iImW4eYRfDPzcWrvGGBMNJBljPrPWbnFxTBHXrN2Xya/f3UTyoWxG9W7FH27sR9vGZ3lly5JiSFnonDu/e5nThO1zo3M5YjVhxSWuBb619hBwyPd5jjEmGWgPKPAlqGTnF/G3RSm8nriXVtF1+c+4wVzVr83ZvZF4zhFY8yqsftlpwjbqACMeg8Hj1YQV1/llDt8YEwucByRWcNsUYApATEyMP8oRqRJrLQs2HOKJBVs4mlvA+PNj+fkVPYiOqua7UFkL+1Y4R/NbPoDSIuhyGVz7d+h+JYSrlSb+4fozzRjTEHgbeMham13+dmvtVGAqQFxcnHW7HpGq2Hf0JL95fxPLtqXTv31jZo4fSv8O1TzVsiAXNr7pzM8f2QR1GztTNnF3qwkrnnA18I0xkThhP9ta+46bY4nUhMLiUqZ9tYtnF28nMjyMx6/vw53nxxJenaZs+jbf5Yh9TdjW/eH6Z6D/LWrCiqfcPEvHADOAZGvtP9waR6SmfLMzg8ff38z2tFyu7teGx6/vS5vGUVW787dN2Omw+0sIi4S+NzqXI+4YryasBAQ3j/AvAO4ANhpj1vm+92tr7UIXxxSptkNZefzpo2QWbDhEh6b1mDE+jpG9W1ftzjlHYM1rzuWIsw+UacLeCQ1buVu4SDW5eZbOckCHNRKwCotLmbF8N/9esp2SUstDo7pzzyVdz3z9mwqbsJfC1U9Bj6vUhJWApWemhKRl29L53Qeb2ZVxglG9W/P49X3o2OwMV5qsqAk7dJJzOeIW3f1TuMg5UOBLSDlwPI8/fLiFRZsPE9u8Pi9PGMplvc4w9ZKx3Xc54jm+Jmw/uO5fMOBWNWElqCjwJSTkF5Uw/atdPLd0BwAPX9mTSRd1rvytBkuKYdvHzgXMTjVh+4x2TqvsmKAmrAQlBb7UatZaPt50mD8vTGZ/Zh7X9G/Do9f2oX2TSi6JkJvmWwn7CmTvh0btYcRvfCth1YSV4KbAl1pr04EsnliwhZW7j9GrTTSzJyVwQbcW39/QWkhNdI7mt7xfpgn7F+hxtZqwUmvomSy1TlpOPn//JIW3kvbTrH4d/nxTf340tOP3F08VnoANp5qwG6FuI6cBG3c3tOzhTfEiLlLgS62RX1TCjOW7eWHpDgpLSpl8URfuH9GNRuWvfZOx3Qn5dXOgIOu7Jmz/W6BuQ2+KF/EDBb4EvfLz9Ff0ac2vr+lNbNk3JCkphm2LnHPnd33ha8Le4KyEjRmmJqyEBAW+BLWkvZk8uTCZ1Xsz6dUmmjmTEhhedp6+oibsZb9xVsJGV3E1rUgtocCXoLQrPZenFqWwaPNhWkbX5ckf9OfWON88vbWQutI5mt/8ntOE7XyJmrAS8vTMl6CSnlPAM4u3MXdlKlERYfzs8h5Muqgz9etEOE3YjW85i6QOqwkrUp4CX4LCiYJipn+1m6nLdlJQXMq4hBh+OrI7LRrWhYwdsHoGrJ3tNGFb9YXr/gn9b1UTVqQMBb4EtOKSUt5cvZ9/fr6N9JwCru7Xhoev7EmXZlGw/RPn3PldSyEswlkJqyasSKUU+BKQSkstH208xD8/28aujBPEdWrKi7cPYUjzYljzIiS9AlmpEN0OLnvUWQmrJqzIaSnwJaBYa1myNY2/f7qN5EPZ9GjdkJduH8wVjfZiVv0StrwHJYXQ+WK48s/Q8xo1YUWqSK8UCRjf7Mzgb5+ksHbfcTo1r8+/f9iTa83XhC1/9Lsm7JC7nEZsy55elysSdBT44rm1+zL5+6cpfL3jKG0aRfHvKxpxTcFHhC+eA/lZ0KoPXPsPGPAjNWFFzoECXzyTfCibpz/dxufJR2hZP5xpCWmMyHmf8GW+JmzvG5zLEcecryasSA1Q4IvfbT6YxbOLt/PJ5iPERJ1kbq+1JBx7n7D1+8s0Ye+E6DZelypSqyjwxW82HcjimcXb+WzLYS6su5uFHb+m97HFmD2FEHsRXHWqCRt55h8mItWmwBfXbdyfxTOLt7E8OZVboxJJbL6U1idSICsahkxw3hdWTVgR1ynwxTXrU4/zzOLt7EpZz8S6S3iuwTKiSnKgfm+49GlfEzba6zJFQoZrgW+MmQlcB6RZa/u5NY4EnlV7jvHCkhTCd3zGpDqfM7zuemxYBKbX9c5K2E7D1YQV8YCbR/ivAM8Br7k4hgQIay1LU9J4fXESvQ6+x58jF9O2TgalDdtA3K8xQ8arCSviMdcC31q7zBgT69bPl8BQXFLKRxsOsnTxQi7Oep8Xw1dQJ7KYkk4XQfwkwnpdqyasSIDQHL6clfyiEt5ZuZ19X77GdfkfMTpsD0V1GxA2aALETya8VS+vSxSRcjwPfGPMFGAKQExMjMfVyJlk5RWxYOly7KoZXFe6hCbmBDlNulN64dNEDlQTViSQeR741tqpwFSAuLg463E5Uol96Tks/3gOHXfOZpxZTzHhHI+9EnvpfUTHXqgmrEgQ8DzwJXBZa9mwbQe7Pn2RoRnvMdZkkBXZnLSB/49Wl/yYFo3ael2iiFSDm6dlzgUuBVoYY/YDj1trZ7g1ntSc4uISViz/lKL/TmV4/jIGmmL2NR5M5kVP0nTwTWrCigQpN8/SGePWzxZ3ZOdksW7hDFptncWFdhcniWJPzA+JueqnxLTXUgqRYKcpHWFXygYOfv4c/dMWcLE5QWpEDMn9f0uPKybTs14jr8sTkRqiwA9RRUVFrF/6FhFJMxhUsJoYG8bmxpcQfeE9dBl6pZqwIrWQAj/EZBw5SMrHz9N5z5vEkUYGTVkdO4VuVz/AwNY6LVakNlPghwBbWkpy0lJyv3qJgVlLuMAUkVx3ABmDH6XviLG0iKzjdYki4gcK/Fos83gWGz6ZSZuU1+lTuoMTNor1La+nzaj76d1riNfliYifKfBrGWsta9av4fiXLzLk2EdcYk6wLzyGNX0fpeeVk4hv1MzrEkXEIwr8WiI96ySrPn+TZlteJb54LaXGkNL0ErIvupeYwVcQoyasSMhT4AexopJSvt6QwrGvZhJ39D2uMWkcC2tGSs976XzlffRt3tHrEkUkgCjwg4y1ls0Hs/nvV5/SNmUWl5d+Q11TxJ7o8zg8/Pe0SbiFZloJKyIVUOAHibTsfD5M2knmynlcfuJDJoftIt/UI63bLbQZ9RNi22olrIicngI/gOUVlvB58hG+SlxFt33zuCX8S5qaXI5Hd+Hk+X+hftw4OkZpJayIVI0CP8AUFpeybFs6H65LpWDrp9xqP+Ev4eshIoyTXa6Ei+6lSexFWgkrItWmwA8AJaWWFbuO8sG6g3yzaRtXF33Ow5GL6RCWRmG9ljD0YcLi7qJho3ZelyoiQUyB75HSUsva1Ew+XH+IBRsO0e7EFibW+Zw/hv2XyMhCSmOGQ/xfqNPreojQSlgROXcKfD8qLill5e5jLNp8mE82H+Z4dg43Rq5gfv2lxNZNwUY2wAy8HYZOIqx1X6/LFZFaRoHvsvyiEr7ekcGiTYf5PPkImSeL6BaZzh+af8OldhF1irIgugeM+Btm4I8gqrHXJYtILaXAd0FOfhHLtmWwaPNhlm5NI7egmEZRYdxgBIgOAAAKeUlEQVTfcS83Fi2k5eFlmKww6HUtDJ0EnS9WE1ZEXKfAryG7M06wZGsaS7YeYeXuYxSVWJo3qMOP+tZnbJ1ldNkzD5O6Fxq0gosfhiEToHF7r8sWkRCiwD9LRSWlrNpzjCXJaSzZmsaujBMAdG/VkIkXdub65ofoc+Atwja/A8X5EDMcRj0OasKKiEcU+NVw8Hgey7dn8OW2dJZtSyenoJg64WEM69qc8cNjGdGtER0PLoKVv4PENRDZAAaOcaZt2mglrIh4S4F/GrkFxazYeZTlOzL4ans6O9Odo/hW0XW5dkBbRvRqxQXdWtDg5H5YNQNefh3yjkGLHnD1UzDwNjVhRSRgKPDLKC4pZeOBLL7ansHy7Rms2ZdJcaklKjKMhM7NGRMfw0XdW9KjdUOMtbBzMcyfBts/BRMGva7xNWEvURNWRAJOSAd+kS/gE3cdI3H3UVbvySS3oBhjoG+7Rky+uAsXdWvBkNim1I0Id+508hh8829YPQMy9/iasL+AIXepCSsiAc3VwDfGXAU8A4QD0621f3FzvDMpKC5hw/4sEncdJXH3MZL2ZnKysASAbq0acsOgdpzfpTkXdGtBswblGqsH1jjTNpvm+5qw58OIx6D3DWrCikhQcC3wjTHhwPPA5cB+YJUx5gNr7Ra3xiwvI7eANXszWZt6nDV7M1mXepyC4lIAerWJ5pYhHUjo0pz4zs1o0bDu939AUT5sfhdWTYMDSRBZ39eEvRva9PfXf0NEpEa4eYQfD+yw1u4CMMa8AYwGXAn8opJSkg9lfxfw+zJJPZYHQESYoW+7RoxL6ERCl2bExzajafkj+LIy98DqmbBmltOEbd4drvorDBqjJqyIBC03A789kFrm6/1AQk0PUlBcwh3TV7J+/3dH760b1WVwTFPuGNaJwTFN6de+MVGR4af/QaWlThN21XTY9onTdO15DcRPVhNWRGoFNwO/ooS039vImCnAFICYmJhqD1I3IpwW0XUYl9CJwZ2aMDimKW0bR2GqGtAnj8G62c78fObuMk3YCdC4Q7XrEREJVG4G/n6g7LtodwAOlt/IWjsVmAoQFxf3vV8IVfHCuCHVv9PBtbByerkm7G/UhBWRWsvNwF8FdDfGdAYOALcBY10c78yK8mHLe7ByGhxY7WvC3uZbCasmrIjUbq4FvrW22BhzP/AJzmmZM621m90a77Qy9zpN2LWz4OTR75qwA2+Dek08KUlExN9cPQ/fWrsQWOjmGJUqLYWdS3xN2EXfNWGHToIul6oJKyIhp/attD15DNbNcVbCHtsFDVrCRT+HuLvUhBWRkFZ7Av/gOmeB1Ma3oTgPOg6DS38NfW6AiAoWVYmIhJjgD/yCHJh1E+xf5TRhB9zqTNu0HeB1ZSIiASX4A79uNDTtDP1+6Fz2QE1YEZEKBX/gA/xwmtcViIgEvDCvCxAREf9Q4IuIhAgFvohIiFDgi4iECAW+iEiIUOCLiIQIBb6ISIhQ4IuIhAhj7Vm954grjDHpwN6zvHsLIKMGy6kpqqv6ArU21VU9qqv6zqa2TtballXZMKAC/1wYY1Zba+O8rqM81VV9gVqb6qoe1VV9btemKR0RkRChwBcRCRG1KfCnel1AJVRX9QVqbaqrelRX9blaW62ZwxcRkdOrTUf4IiJyGkEX+MaYq4wxKcaYHcaYRyq4va4xZp7v9kRjTKwfaupojFlqjEk2xmw2xjxYwTaXGmOyjDHrfP9+63ZdvnH3GGM2+sZcXcHtxhjzrG9/bTDGDPZDTT3L7Id1xphsY8xD5bbx2/4yxsw0xqQZYzaV+V4zY8xnxpjtvo9NK7nveN82240x4/1Q19+MMVt9j9W7xpgK3/HnTI+7C3X9zhhzoMzjdU0l9z3t69eFuuaVqWmPMWZdJfd1c39VmA+ePMestUHzDwgHdgJdgDrAeqBPuW3uA170fX4bMM8PdbUFBvs+jwa2VVDXpcACD/bZHqDFaW6/BvgYMMAwINGDx/QwzrnEnuwv4GJgMLCpzPeeAh7xff4I8NcK7tcM2OX72NT3eVOX67oCiPB9/teK6qrK4+5CXb8DflGFx/q0r9+arqvc7U8Dv/Vgf1WYD148x4LtCD8e2GGt3WWtLQTeAEaX22Y08Krv8/nASGOMcbMoa+0ha+0a3+c5QDLQ3s0xa9Bo4DXrWAE0Mca09eP4I4Gd1tqzXXB3zqy1y4Bj5b5d9nn0KnBjBXe9EvjMWnvMWpsJfAZc5WZd1tpPrbXFvi9XAB1qarxzqauKqvL6daUuXwbcCsytqfGq6jT54PfnWLAFfnsgtczX+/l+sH67je+FkQU090t1gG8K6TwgsYKbzzfGrDfGfGyM6eunkizwqTEmyRgzpYLbq7JP3XQblb8Ivdhfp7S21h4C5wULtKpgG6/33UScv84qcqbH3Q33+6aaZlYyPeHl/roIOGKt3V7J7X7ZX+Xywe/PsWAL/IqO1MufZlSVbVxhjGkIvA08ZK3NLnfzGpxpi4HAv4H3/FETcIG1djBwNfATY8zF5W73cn/VAW4A3qrgZq/2V3V4ue8eBYqB2ZVscqbHvab9B+gKDAIO4UyflOfZ/gLGcPqje9f31xnyodK7VfC9s95nwRb4+4GOZb7uABysbBtjTATQmLP787NajDGROA/mbGvtO+Vvt9ZmW2tzfZ8vBCKNMS3crstae9D3MQ14F+fP6rKqsk/dcjWwxlp7pPwNXu2vMo6cmtryfUyrYBtP9p2vcXcdMM76JnrLq8LjXqOstUestSXW2lJgWiXjebW/IoAfAPMq28bt/VVJPvj9ORZsgb8K6G6M6ew7OrwN+KDcNh8ApzrZNwNLKntR1BTf/OAMINla+49KtmlzqpdgjInH2fdHXa6rgTEm+tTnOA2/TeU2+wC40ziGAVmn/sz0g0qPurzYX+WUfR6NB96vYJtPgCuMMU19UxhX+L7nGmPMVcD/ATdYa09Wsk1VHvearqts3+emSsaryuvXDaOArdba/RXd6Pb+Ok0++P855kZX2s1/OGeVbMPp9j/q+94TOC8AgCicKYIdwEqgix9quhDnz6wNwDrfv2uAe4B7fNvcD2zGOTNhBTDcD3V18Y233jf2qf1Vti4DPO/bnxuBOD89jvVxArxxme95sr9wfukcAopwjqjuxun7LAa2+z42820bB0wvc9+JvufaDuAuP9S1A2dO99Tz7NQZae2Ahad73F2ua5bv+bMBJ8jalq/L9/X3Xr9u1uX7/iunnldltvXn/qosH/z+HNNKWxGREBFsUzoiInKWFPgiIiFCgS8iEiIU+CIiIUKBLyISIhT4IiIhQoEvIhIiFPgilTDGDPVdDCzKtxpzszGmn9d1iZwtLbwSOQ1jzB9xVm/XA/Zba5/0uCSRs6bAFzkN3zVfVgH5OJd3KPG4JJGzpikdkdNrBjTEeaeiKI9rETknOsIXOQ1jzAc478zUGeeCYPd7XJLIWYvwugCRQGWMuRMottbOMcaEA98YY0ZYa5d4XZvI2dARvohIiNAcvohIiFDgi4iECAW+iEiIUOCLiIQIBb6ISIhQ4IuIhAgFvohIiFDgi4iEiP8Pf0+Lrishb18AAAAASUVORK5CYII=\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "def numerical_diff(f, x):\n", " h = 1e-4 # 0.0001\n", " return (f(x+h) - f(x-h)) / (2*h)\n", "\n", "def function_1(x):\n", " return 0.01*x**2 + 0.1*x \n", "\n", "def tangent_line(f, x):\n", " d = numerical_diff(f, x)\n", " return lambda t: d * (t - x) + f(x)\n", " \n", "x = np.arange(0.0, 20.0, 0.1)\n", "y = function_1(x)\n", "plt.xlabel(\"x\")\n", "plt.ylabel(\"f(x)\")\n", "\n", "tf = tangent_line(function_1, 5)\n", "y2 = tf(x)\n", "\n", "plt.plot(x, y)\n", "plt.plot(x, y2)\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 2. Implement Gradient Descent in Python\n", "- https://towardsdatascience.com/implement-gradient-descent-in-python-9b93ed7108d1" ] }, { "cell_type": "code", "execution_count": 103, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/plain": [ "" ] }, "execution_count": 103, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f = lambda x: (x + 5)**2\n", "\n", "from IPython.display import Image\n", "Image(url= \"https://cdn-images-1.medium.com/max/800/1*5-56UEwcZHgzqIAtlnsLog.png\", width=300, height=300)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- Step 1 : Initialize parameters" ] }, { "cell_type": "code", "execution_count": 108, "metadata": {}, "outputs": [], "source": [ "f = lambda x: (x + 5)**2\n", "\n", "cur_x = 3 # The algorithm starts at x=3\n", "\n", "learning_rate = 0.1 # Learning rate\n", "\n", "precision = 0.000001 #This tells us when to stop the algorithm\n", "\n", "previous_step_size = 1 #\n", "\n", "max_iters = 10000 # maximum number of iterations\n", "\n", "iters = 0 #iteration counter\n", "\n", "df = lambda x: 2 * (x + 5) #Gradient of our function " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- Step 2 : Run a loop to perform gradient descent\n", " - Stop loop when difference between x values from 2 consecutive iterations is less than 0.000001 or when number of iterations exceeds 10,000" ] }, { "cell_type": "code", "execution_count": 109, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Iteration: 0 - X is 3.00000\n", "Iteration: 1 - X value is 1.40000\n", "Iteration: 2 - X value is 0.12000\n", "Iteration: 3 - X value is -0.90400\n", "Iteration: 4 - X value is -1.72320\n", "Iteration: 5 - X value is -2.37856\n", "Iteration: 6 - X value is -2.90285\n", "Iteration: 7 - X value is -3.32228\n", "Iteration: 8 - X value is -3.65782\n", "Iteration: 9 - X value is -3.92626\n", "Iteration: 10 - X value is -4.14101\n", "Iteration: 11 - X value is -4.31281\n", "Iteration: 12 - X value is -4.45024\n", "Iteration: 13 - X value is -4.56020\n", "Iteration: 14 - X value is -4.64816\n", "Iteration: 15 - X value is -4.71853\n", "Iteration: 16 - X value is -4.77482\n", "Iteration: 17 - X value is -4.81986\n", "Iteration: 18 - X value is -4.85588\n", "Iteration: 19 - X value is -4.88471\n", "Iteration: 20 - X value is -4.90777\n", "Iteration: 21 - X value is -4.92621\n", "Iteration: 22 - X value is -4.94097\n", "Iteration: 23 - X value is -4.95278\n", "Iteration: 24 - X value is -4.96222\n", "Iteration: 25 - X value is -4.96978\n", "Iteration: 26 - X value is -4.97582\n", "Iteration: 27 - X value is -4.98066\n", "Iteration: 28 - X value is -4.98453\n", "Iteration: 29 - X value is -4.98762\n", "Iteration: 30 - X value is -4.99010\n", "Iteration: 31 - X value is -4.99208\n", "Iteration: 32 - X value is -4.99366\n", "Iteration: 33 - X value is -4.99493\n", "Iteration: 34 - X value is -4.99594\n", "Iteration: 35 - X value is -4.99675\n", "Iteration: 36 - X value is -4.99740\n", "Iteration: 37 - X value is -4.99792\n", "Iteration: 38 - X value is -4.99834\n", "Iteration: 39 - X value is -4.99867\n", "Iteration: 40 - X value is -4.99894\n", "Iteration: 41 - X value is -4.99915\n", "Iteration: 42 - X value is -4.99932\n", "Iteration: 43 - X value is -4.99946\n", "Iteration: 44 - X value is -4.99956\n", "Iteration: 45 - X value is -4.99965\n", "Iteration: 46 - X value is -4.99972\n", "Iteration: 47 - X value is -4.99978\n", "Iteration: 48 - X value is -4.99982\n", "Iteration: 49 - X value is -4.99986\n", "Iteration: 50 - X value is -4.99989\n", "Iteration: 51 - X value is -4.99991\n", "Iteration: 52 - X value is -4.99993\n", "Iteration: 53 - X value is -4.99994\n", "Iteration: 54 - X value is -4.99995\n", "Iteration: 55 - X value is -4.99996\n", "Iteration: 56 - X value is -4.99997\n", "Iteration: 57 - X value is -4.99998\n", "Iteration: 58 - X value is -4.99998\n", "Iteration: 59 - X value is -4.99998\n", "Iteration: 60 - X value is -4.99999\n", "Iteration: 61 - X value is -4.99999\n", "Iteration: 62 - X value is -4.99999\n", "Iteration: 63 - X value is -4.99999\n", "Iteration: 64 - X value is -4.99999\n", "Iteration: 65 - X value is -5.00000\n", "Iteration: 66 - X value is -5.00000\n", "The local minimum occurs at -5.00000\n" ] } ], "source": [ "print(\"Iteration: {0:2d} - X is {1:8.5f}\".format(0, cur_x))\n", "\n", "while previous_step_size > precision and iters < max_iters:\n", " prev_x = cur_x #Store current x value in prev_x\n", " \n", " cur_x = cur_x - learning_rate * df(prev_x) #Grad descent\n", "\n", " previous_step_size = abs(cur_x - prev_x) #Change in x\n", "\n", " iters = iters + 1 #iteration count\n", " \n", " print(\"Iteration: {0:2d} - X value is {1:8.5f}\".format(iters, cur_x)) #Print iterations\n", " \n", "print(\"The local minimum occurs at {0:8.5f}\".format(cur_x))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 3. Implement 2D Gradient Descent in Python" ] }, { "cell_type": "code", "execution_count": 110, "metadata": {}, "outputs": [], "source": [ "f = lambda x, y: x ** 2 + y ** 2 + 10\n", "\n", "cur_x = 3 # The algorithm starts at x=3\n", "cur_y = -3 # The algorithm starts at y=-3\n", "\n", "learning_rate = 0.1 # Learning rate\n", "\n", "precision = 0.000001 #This tells us when to stop the algorithm\n", "\n", "previous_step_size = 1 #\n", "\n", "max_iters = 10000 # maximum number of iterations\n", "\n", "iters = 0 #iteration counter\n", "\n", "df_x = lambda x, y: 2 * x #Gradient of our function for x\n", "df_y = lambda x, y: 2 * y #Gradient of our function for y" ] }, { "cell_type": "code", "execution_count": 111, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Iteration: 0 - X is 3.00000, Y is -3.00000,\n", "Iteration: 1 - X is 2.40000, Y is -2.40000,\n", "Iteration: 2 - X is 1.92000, Y is -1.92000,\n", "Iteration: 3 - X is 1.53600, Y is -1.53600,\n", "Iteration: 4 - X is 1.22880, Y is -1.22880,\n", "Iteration: 5 - X is 0.98304, Y is -0.98304,\n", "Iteration: 6 - X is 0.78643, Y is -0.78643,\n", "Iteration: 7 - X is 0.62915, Y is -0.62915,\n", "Iteration: 8 - X is 0.50332, Y is -0.50332,\n", "Iteration: 9 - X is 0.40265, Y is -0.40265,\n", "Iteration: 10 - X is 0.32212, Y is -0.32212,\n", "Iteration: 11 - X is 0.25770, Y is -0.25770,\n", "Iteration: 12 - X is 0.20616, Y is -0.20616,\n", "Iteration: 13 - X is 0.16493, Y is -0.16493,\n", "Iteration: 14 - X is 0.13194, Y is -0.13194,\n", "Iteration: 15 - X is 0.10555, Y is -0.10555,\n", "Iteration: 16 - X is 0.08444, Y is -0.08444,\n", "Iteration: 17 - X is 0.06755, Y is -0.06755,\n", "Iteration: 18 - X is 0.05404, Y is -0.05404,\n", "Iteration: 19 - X is 0.04323, Y is -0.04323,\n", "Iteration: 20 - X is 0.03459, Y is -0.03459,\n", "Iteration: 21 - X is 0.02767, Y is -0.02767,\n", "Iteration: 22 - X is 0.02214, Y is -0.02214,\n", "Iteration: 23 - X is 0.01771, Y is -0.01771,\n", "Iteration: 24 - X is 0.01417, Y is -0.01417,\n", "Iteration: 25 - X is 0.01133, Y is -0.01133,\n", "Iteration: 26 - X is 0.00907, Y is -0.00907,\n", "Iteration: 27 - X is 0.00725, Y is -0.00725,\n", "Iteration: 28 - X is 0.00580, Y is -0.00580,\n", "Iteration: 29 - X is 0.00464, Y is -0.00464,\n", "Iteration: 30 - X is 0.00371, Y is -0.00371,\n", "Iteration: 31 - X is 0.00297, Y is -0.00297,\n", "Iteration: 32 - X is 0.00238, Y is -0.00238,\n", "Iteration: 33 - X is 0.00190, Y is -0.00190,\n", "Iteration: 34 - X is 0.00152, Y is -0.00152,\n", "Iteration: 35 - X is 0.00122, Y is -0.00122,\n", "Iteration: 36 - X is 0.00097, Y is -0.00097,\n", "Iteration: 37 - X is 0.00078, Y is -0.00078,\n", "Iteration: 38 - X is 0.00062, Y is -0.00062,\n", "Iteration: 39 - X is 0.00050, Y is -0.00050,\n", "Iteration: 40 - X is 0.00040, Y is -0.00040,\n", "Iteration: 41 - X is 0.00032, Y is -0.00032,\n", "Iteration: 42 - X is 0.00026, Y is -0.00026,\n", "Iteration: 43 - X is 0.00020, Y is -0.00020,\n", "Iteration: 44 - X is 0.00016, Y is -0.00016,\n", "Iteration: 45 - X is 0.00013, Y is -0.00013,\n", "Iteration: 46 - X is 0.00010, Y is -0.00010,\n", "Iteration: 47 - X is 0.00008, Y is -0.00008,\n", "Iteration: 48 - X is 0.00007, Y is -0.00007,\n", "Iteration: 49 - X is 0.00005, Y is -0.00005,\n", "Iteration: 50 - X is 0.00004, Y is -0.00004,\n", "Iteration: 51 - X is 0.00003, Y is -0.00003,\n", "Iteration: 52 - X is 0.00003, Y is -0.00003,\n", "Iteration: 53 - X is 0.00002, Y is -0.00002,\n", "Iteration: 54 - X is 0.00002, Y is -0.00002,\n", "Iteration: 55 - X is 0.00001, Y is -0.00001,\n", "Iteration: 56 - X is 0.00001, Y is -0.00001,\n", "Iteration: 57 - X is 0.00001, Y is -0.00001,\n", "Iteration: 58 - X is 0.00001, Y is -0.00001,\n", "Iteration: 59 - X is 0.00001, Y is -0.00001,\n", "Iteration: 60 - X is 0.00000, Y is -0.00000,\n", "Iteration: 61 - X is 0.00000, Y is -0.00000,\n", "Iteration: 62 - X is 0.00000, Y is -0.00000,\n", "Iteration: 63 - X is 0.00000, Y is -0.00000,\n", "Iteration: 64 - X is 0.00000, Y is -0.00000,\n", "The local minimum occurs at 0.00000, -0.00000\n" ] } ], "source": [ "print(\"Iteration: {0:2d} - X is {1:8.5f}, Y is {2:8.5f},\".format(0, cur_x, cur_y))\n", "\n", "while previous_step_size > precision and iters < max_iters:\n", " prev_x = cur_x #Store current x value in prev_x\n", " prev_y = cur_y #Store current x value in prev_x \n", " \n", " cur_x = cur_x - learning_rate * df_x(prev_x, prev_y) #Grad descent for x\n", " cur_y = cur_y - learning_rate * df_y(prev_x, prev_y) #Grad descent for x \n", "\n", " previous_step_size = abs(cur_x - prev_x) + abs(cur_y - prev_y) #Change in x\n", " \n", " iters = iters + 1 #iteration count\n", " \n", " print(\"Iteration: {0:2d} - X is {1:8.5f}, Y is {2:8.5f},\".format(iters, cur_x, cur_y)) #Print iterations\n", " \n", "print(\"The local minimum occurs at {0:8.5f}, {1:8.5f}\".format(cur_x, cur_y))" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.8" } }, "nbformat": 4, "nbformat_minor": 2 }