{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Gradient descent in action" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Goal\n", "\n", "The goal of this lab is to explore how chasing function gradients can find the function minimum. If the function is a loss function representing the quality of a model's fit to a training set, we can use function minimization to train models.\n", "\n", "When there is no symbolic solution to minimizing the loss function, we need an iterative solution, such as gradient descent." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Set up" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "import pandas as pd\n", "\n", "from mpl_toolkits.mplot3d import Axes3D # required even though not ref'd!\n", "from sklearn.linear_model import LinearRegression, LogisticRegression, Lasso, Ridge\n", "from sklearn.ensemble import RandomForestRegressor\n", "from sklearn.datasets import load_boston\n", "from sklearn.model_selection import train_test_split\n", "from sklearn.metrics import confusion_matrix, precision_score, recall_score, log_loss, mean_absolute_error\n", "\n", "import matplotlib.pyplot as plt\n", "import matplotlib as mpl\n", "%config InlineBackend.figure_format = 'retina'" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def normalize(X):\n", " X = X.copy()\n", " for colname in X.columns:\n", " u = np.mean(X[colname])\n", " s = np.std(X[colname])\n", " if s>0.0:\n", " X[colname] = (X[colname] - u) / s\n", " else:\n", " X[colname] = (X[colname] - u)\n", " return X" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def plot3d(X, y, b0_range, b1_range):\n", " b0_mesh, b1_mesh = np.meshgrid(b0_range, b1_range, indexing='ij')\n", " L = np.zeros(b0_mesh.shape)\n", "\n", " for i in range(len(b0_range)):\n", " for j in range(len(b1_range)):\n", " L[i,j] = loss([b0_range[i],b1_range[j]], X=X, y=y)\n", "\n", " fig = plt.figure(figsize=(5,4))\n", " ax = fig.add_subplot(111, projection='3d')\n", " surface = ax.plot_surface(b0_mesh, b1_mesh, L, alpha=0.7, cmap='coolwarm')\n", " ax.set_xlabel('$\\\\beta_0$', fontsize=14)\n", " ax.set_ylabel('$\\\\beta_1$', fontsize=14)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Simple function gradient descent\n", "\n", "Let's define a very simple quadratic in one variable, $y = f(x) = (x-2)^2$ and then use an iterative solution to find the minimum value." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def f(x) : return (x-2)**2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can hide all of the plotting details in a function, as we will use it multiple times." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def fplot(f,xrange,fstr='',x0=None,xn=None):\n", " plt.figure(figsize=(3.5,2))\n", " lx = np.linspace(*xrange,200) \n", " fx = [f(x) for x in lx]\n", " plt.plot(lx, fx, lw=.75)\n", " if x0 is not None:\n", " plt.scatter([x0], [f(x0)], c='orange')\n", " plt.scatter([xn], [f(xn)], c='green')\n", " plt.xlabel(\"$x$\", fontsize=12)\n", " plt.ylabel(fstr, fontsize=12)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "fplot(f, xrange=(0,4), fstr=\"$(x-2)^2$\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "To minimize a function of $x$, we need the derivative of $f(x)$, which is just a function that gives the slope of the curve at every $x$.\n", "\n", "**1. Define a function returning the derivative of $f(x)$**\n", "\n", "You can ask for symbolic derivatives at a variety of sites, but here's one [solution](https://www.symbolab.com/solver/derivative-calculator/%5Cfrac%7Bd%7D%7Bdx%7D%5Cleft(x-2%5Cright)%5E%7B2%7D)." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def df(x): ..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "Solution\n", "
\n",
    "def df(x): return 2*(x-2)
\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**2. Pick an initial $x$ location and take a single step according to the derivative**\n", "\n", "Use a learning rate of $\\eta = 0.4$. The output should be `1.76`. (Also keep in mind that the minimum value is clearly at $x=2$.)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "x = .8 # initial x location" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "x = ...\n", "print(x)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "Solution\n", "
\n",
    "x = x - .4 * df(x); print(x)\n",
    "
\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Q.** How can we symbolically optimize a quadratic function like this with a single minimum?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "Solution\n", "When the derivative goes to zero, it means the curve is flat, which in turn means we are at the function minimum. Set the derivative equal to zero and solve for $x$: $\\frac{d}{dx} (x-2)^2 = 2(x-2) = 2x-4 = 0$. Solving for $x$ gives $x=2$.\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**3. Create a loop that takes five more steps (same learning rate)**\n", "\n", "The output should look like:\n", "\n", "```\n", "1.952\n", "1.9904\n", "1.99808\n", "1.999616\n", "1.9999232\n", "```" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "for i in range(5):\n", " x = x - 0.4 * df(x);\n", " print(x)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "Solution\n", "
\n",
    "for i in range(5):\n",
    "    x = x - 0.4 * df(x); print(x)\n",
    "
\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Notice how fast the iteration moves $x$ to the location where $f(x)$ is minimum!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Minimizing a more complicated function\n", "\n", "This iterative minimization approach works for any (smooth) function, assuming we choose a small enough learning rate. For example, let's find one of the minima for $f(x) = x \\sin(0.6x)$ in the range \\[-1,10\\]. The plot should look something like:\n", "\n", "\n", "\n", "Depending on where we start, minimization will find either minimum at $x=0$ or at $8.18$. The location of the lowest function value is called the global minimum and any others are called local minima." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**1. Define a function for $x \\sin(0.6x)$**" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def f(x) : ..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "Solution\n", "
\n",
    "def f(x) : return np.sin(0.6*x)*x\n",
    "
\n", "
" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "fplot(f, xrange=(-1,10), fstr=\"$x \\sin(0.6x)$\")\n", "#plt.tight_layout(); plt.savefig(\"xsinx.png\",dpi=150,bbox_inches=0)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**2. Define the derivative function: $\\frac{df}{dx} = 0.6x \\cos(0.6 x) + \\sin(0.6 x)$**" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def df(x): ..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "Solution\n", "
\n",
    "def df(x): return 0.6*x * np.cos(0.6*x) + np.sin(0.6*x)\n",
    "
\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**3. Pick a random initial value, $x_0$, between -1 and 10; display that value**" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "x0 = np.random.rand()*11 - 1 # pick value between -1 and 10\n", "x0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**4. Start $x$ at $x_0$ and iterate 12 times using the gradient descent method**\n", "\n", "Use a learning rate of 0.4." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "x = x0\n", "for i in range(12):\n", " x = x - .4 * df(x); print(f\"{x:.10f}\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**5. Plot the starting and stopping locations on the curve**" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "fplot(f, xrange=(-1,10), fstr=\"$x \\sin(0.6x)$\", x0=x0, xn=x)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**6. Rerun the notebook several times to see how the random start location affects where it terminates.**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Q.** Rather than iterating a fixed number of times, what's a better way to terminate the iteration?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "Solution\n", "A simple stopping condition is when the (norm of the) gradient goes to zero, meaning that it does not suggest we move in any direction to get a lower loss of function value. We could also check to see if the new $x$ location is substantially different from the previous.\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## The effect of learning rate on convergence\n", "\n", "Let's move back to the simple function $f(x) = (x-2)^2$ and consider different learning rates to see the effect." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def df(x): return 2*(x-2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's codify the minimization process in a handy function:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def minimize(df,x0,eta):\n", " x = x0\n", " for i in range(10):\n", " x = x - eta * df(x);\n", " print(f\"{x:.2f}\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**1. Update the gradient descent loop to use a learning rate of 1.0**\n", "\n", "Notice how the learning rate is so large that iteration oscillates between two (incorrect) solutions. The output should be:\n", "\n", "```\n", "3.20\n", "0.80\n", "3.20\n", "0.80\n", "3.20\n", "0.80\n", "3.20\n", "0.80\n", "3.20\n", "0.80\n", "```" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "minimize(df, x0=0.8, eta=...)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**2. Update the gradient descent loop to use a learning rate of 2.0**\n", "\n", "Notice how the solution diverges when the learning rate is too big. The output should be:\n", "\n", "```\n", "5.60\n", "-8.80\n", "34.40\n", "-95.20\n", "293.60\n", "-872.80\n", "2626.40\n", "-7871.20\n", "23621.60\n", "-70856.80\n", "```" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "minimize(df, x0=0.8, eta=...)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**2. Update the gradient descent loop to use a learning rate of 0.01**\n", "\n", "Notice how **slowly** the solution converges when the learning rate is two small. The output should be:\n", "\n", "```\n", "0.82\n", "0.85\n", "0.87\n", "0.89\n", "0.92\n", "0.94\n", "0.96\n", "0.98\n", "1.00\n", "1.02\n", "```" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "minimize(df, x0=0.8, eta=...)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Q.** How do you choose the learning rate $\\eta$?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "Solution\n", "The learning rate is specific to each problem unfortunately. A general strategy is to start with a small $\\eta$ and gradually increase it until it starts to oscillate around the solution, then back off a little bit. Having a single global learning rate for un-normalized data usually means very slow convergence. A learning rate small enough to be appropriate for a variable with small range is unlikely to be appropriate for variable with a large range. This is overcome with the more sophisticated gradient descent methods, such as the Adagrad strategy you will use in your project. In that case, we keep a history of gradients and use that to speed up descent in directions that are historically shallow in the gradient.\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Examine loss surface for LSTAT var from Boston dataset\n", "\n", "Turning to a common toy data set, the Boston housing data set, let's pick the most important single feature and look at the loss function for simple OLS regression." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**1. Load the Boston data set into a data frame**" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "boston = load_boston()\n", "X = pd.DataFrame(boston.data, columns=boston.feature_names)\n", "y = boston.target\n", "X.head()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**2. Train an OLS linear regression model**" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "lm = LinearRegression()\n", "lm.fit(X, y)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**3. Using `rfpimp` package, display the feature importances**" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from rfpimp import *\n", "\n", "I = importances(lm, X, y)\n", "plot_importances(I)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**4. LSTAT is most important variable so train a new model with just `X['LSTAT']`**\n", "\n", "Print out the true $\\beta_0, \\beta_1$ coefficients." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "X_ = X['LSTAT'].values.reshape(-1,1) # Extract just one x variable\n", "\n", "lm = LinearRegression()\n", "lm.fit(X_, y)\n", "print(f\"True OLS coefficients: {np.array([lm.intercept_]+list(lm.coef_))}\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**5. Show marginal plot of LSTAT vs price**" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "fig, ax1 = plt.subplots(figsize=(5,2.0))\n", "ax1.scatter(X_, y, s=15, alpha=.5)\n", "lx = np.linspace(np.min(X_), np.max(X_), num=len(X))\n", "ax1.plot(lx, lm.predict(lx.reshape(-1,1)), c='orange')\n", "ax1.set_xlabel(\"LSTAT\", fontsize=10)\n", "ax1.set_ylabel(\"price\", fontsize=10)\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**6. Define an MSE loss function for single variable regression**\n", "\n", "$$\n", "\\frac{1}{n} \\sum_{i=1}^n (y - (\\beta_0 + \\beta_1 x^{(i)}))^2\n", "$$" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def loss(B,X,y): # B=[beta0, beta1]\n", " y_pred = ...\n", " return np.mean(...)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "Solution\n", "
\n",
    "def loss(B,X,y):\n",
    "    y_pred = B[0] + X*B[1]\n",
    "    return np.mean((y - y_pred)**2)\n",
    "
\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**7. Check the loss function value at the true OLS coordinates**" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "loss(np.array([34.55384088, -0.95004935]), X_, y) # demo loss function at minimum" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**8. Plot the loss function in 3D in region around $\\beta$s**\n", "\n", "When you enter the correct loss function above, the plot should look something like:\n", "\n", "\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "b0_range = np.linspace(-50, 120, 70)\n", "b1_range = np.linspace(-6, 4, 70)\n", "\n", "plot3d(X_, y, b0_range, b1_range)\n", "#plt.tight_layout(); plt.savefig(\"boston-loss.png\",dpi=150,bbox_inches=0)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Repeat using normalized data" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**1. Normalize the $x$ variables**" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "X_norm = normalize(X)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**2. Retrain the model**" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "X_ = X_norm['LSTAT'].values.reshape(-1,1)\n", "\n", "lm = LinearRegression()\n", "lm.fit(X_, y)\n", "print(f\"True OLS coefficients: {np.array([lm.intercept_]+list(lm.coef_))}\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**3. Show the marginal plot again**\n", "\n", "Notice how only the $x$ scale has changed but not $y$, nor has the shape changed." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "fig, ax1 = plt.subplots(figsize=(5,2.0))\n", "ax1.scatter(X_, y, s=15, alpha=.5)\n", "lx = np.linspace(np.min(X_), np.max(X_), num=len(X))\n", "ax1.plot(lx, lm.predict(lx.reshape(-1,1)), c='orange')\n", "ax1.set_xlabel(\"LSTAT\", fontsize=10)\n", "ax1.set_ylabel(\"price\", fontsize=10)\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**4. Plot the cost surface with a region around the new minimum location**" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "b0_range = np.linspace(15, 30, 70)\n", "b1_range = np.linspace(-10, 5, 70)\n", "\n", "plot3d(X_, y, b0_range, b1_range)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Q.** Compare the loss function contour lines of the unnormalized and normalized variables." ] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "Solution\n", "The normalized variables clearly result in a bowl shaped loss function, which gives spherical contours. A gradient descent method with a single learning rate will convergent much faster given visible shape.\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Q.** Look at the loss function directly from above; in which direction do the gradients point?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "Solution\n", "The negative of the gradients will point directly at the minimum loss function value location. The gradients themselves, however, point in the exact opposite direction.
" ] } ], "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.8.8" } }, "nbformat": 4, "nbformat_minor": 4 }