<jupyter_start><jupyter_text>Table of Contents1&nbsp;&nbsp;Objectives2&nbsp;&nbsp;Solving the Line of Best Fit by Guessing3&nbsp;&nbsp;The Loss Function4&nbsp;&nbsp;The Cost Function5&nbsp;&nbsp;Better Way of Guessing: Gradient Descent5.1&nbsp;&nbsp;Gradient Descent in Words5.2&nbsp;&nbsp;Stepping Down a Hill: Step Size5.3&nbsp;&nbsp;Putting It All Together6&nbsp;&nbsp;Level Up: Gradient Descent Walk Through<jupyter_code>import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline<jupyter_output><empty_output><jupyter_text>Objectives - Explain and use the concept of a gradient- Explain the algorithm of gradient descent- Describe the effect of the "learning rate" in the algorithm  Solving the Line of Best Fit by Guessing Let's say we have some data below:<jupyter_code># Randomly created data in x & y
np.random.seed(27)

x = np.random.rand(30,1).reshape(30)
y_randterm = np.random.normal(0,3,30)
y = 3 + 50 * x + y_randterm<jupyter_output><empty_output><jupyter_text>Here's the data plotted out:<jupyter_code>f, ax = plt.subplots(figsize=(8,6))
ax.scatter(x, y)

ax.set_title('Data Points to Model')
ax.set_xlabel('x', fontsize=14)
ax.set_ylabel('y', fontsize=14)
ax.set_xlim(0,1)
ax.set_ylim(0,60)
plt.tight_layout()<jupyter_output><empty_output><jupyter_text>If we wanted to make a best-fit line, what would you say it's about? Let's create a couple functions to make this easier to make a guess<jupyter_code># Plotting a guess of a regression line
def regression_formula(x, a, b):
    return a*x + b

def plot_data_and_guess(slope, intercept, ax, x1=x, x2=y, **kwargs):
    '''
    Plot our data and regression line on the given axis.

    Arguments:
        slope : float
            Value for the slope the regression line.
            
        intercept : float
            Value for the intercept the regression line.
        
        ax : Axes
            Axis to plot data and regression line
        
        x1 : array-like
            Values along the x-axis
        
        x2 : array-like
            Values along the y-axis
        
    Returns:
        fig : Figure

        ax : Axes
    '''
    # Plot data and regression line
    ax.scatter(x1, x2)
    yhat = regression_formula(x1, slope ,intercept)
    ax.plot(x1, yhat, 'r-', **kwargs)
    
    # Embelishments
    ax.set_title('Data Points to Model')
    ax.set_xlabel('x', fontsize=14)
    ax.set_ylabel('y', fontsize=14)
    ax.set_xlim(0,1)
    ax.set_ylim(0,60)

    return ax<jupyter_output><empty_output><jupyter_text>So what do you think the regression parameters are?<jupyter_code># Our guess
guess = {
    'slope': 30,
    'intercept': 0,
    'color':'orange'
}

f, ax = plt.subplots(figsize=(8,6))
plot_data_and_guess(**guess, ax=ax)<jupyter_output><empty_output><jupyter_text>What would be your next guess be? - How can we tell when our guess is "better"?- Could we formalize this?  The Loss Function One way we can know how well our guess or _model_ did is to compare the predicted values with the actual values. These are the _residuals_. So this would give us the error for each data point:$$ r_i = \hat{y}_i - y_i $$<jupyter_code>def calculate_residuals(x_values, y_values, slope, intercept):
    '''Find the residulas for each data point'''
    yhat = intercept + slope*x_values
    errors = y_values - yhat
    return errors<jupyter_output><empty_output><jupyter_text>This is great but we can go further by having just one number to represent how "bad" or "good" our model was to the real points. This leads us to the **mean squared error** or **MSE**. This is all the residuals squared and then averaged:$$ MSE = \frac{1}{n} \sum_{i}^{n} (\hat{y}_i - y_i)^2 $$<jupyter_code>def mse(x_values, y_values, slope, intercept):
    
    resid_sq = calculate_residuals(x_values, y_values, slope, intercept)**2 

    return sum(resid_sq)/len(x_values)
# Use our guess from earlier
slope = guess.get('slope', 30)
intercept = guess.get('intercept', 0)

mse(x,y,slope,intercept)<jupyter_output><empty_output><jupyter_text>> The function we use to find how bad our model did in prediction is typically called the **loss function** What we found here is great! We can now compare different models with one another.If we made a few different guesses, we could make our predictions and then calculate from the _loss function_ how good or bad our model did! We will want to find the _smallest loss_.  The Cost Function Now our model changes based on the different model _parameters_ (the coefficients $\beta_i$ for linear regression). If we imagine all the different ways we can adjust these parameters $\vec{\theta}$ and measure how well the model with the loss or **cost function** $J(\vec{\theta})$, we can plot this as a surface in this multidimensional plane. See the image below: ![](img/gradientdescent.png) > Note that the terms **loss function** and **cost function** are frequently used interchangeably. Sometimes they are the same function, but sometimes they differ by making changes in the cost to improve _training_ or _learning_. Let's try creating the cost function's curve/surface for just one parameter (slope) using our earlier data example:<jupyter_code>table = np.zeros((20,2))
# Find the MSE for different slope values
for idx, val in enumerate(range(40, 60)):
    table[idx,0] = val
    table[idx,1] = mse(x, y, slope=val, intercept=0)

plt.figure(figsize=(10,7))
plt.plot(table[:,0], table[:,1], '-')
plt.xlabel("Slope Values", fontsize=14)
plt.ylabel("MSE", fontsize=14)
plt.title("MSE with changes to slope", fontsize=16);<jupyter_output><empty_output><jupyter_text>Based on this graph, what is the optimal slope value?How could we extend this to find the best slope _and_ intercept combination?  Better Way of Guessing: Gradient Descent So this probably all sounds great! We just need to find the minimum of the cost function!But there's some bad news; we don't usually know what the cost function (which can be complicated!) "looks" like without trying a whole lot of different parameters $\vec{\theta}$. We'd need an _infinite_ number of parameter combinations to know $J(\vec{\theta})$ completely. So what can we do?Well, we can take one "guess" (set of  parameters) and then measure $J(\vec{\theta})$. Then we can adjust our guess/parameters in a "good" direction, "down the hill". This is the basic idea of gradient descent. > **Gradient descent** is an optimization procedure that uses the _gradient_ (a generalized notion of a derivative) of the cost function. So how do find this "better" guess? Well, we need to find the best direction to move "downhill" the fastest. We can do this with a generalization of the derivative called the **gradient**:$$\begin{align}\\    \large -\nabla J &= \sum_i \dfrac{\partial J}{\partial \theta_i} \\            &= \frac{\partial J}{\partial \theta_1} +  \frac{\partial J}{\partial \theta_2} + \dots +  \frac{\partial J}{\partial \theta_n}\end{align}$$ In the multivariate case, the gradient tells us how the function is changing **in each dimension**. A large value of the derivative with respect to a particular variable means that the gradient will have a large component in the corresponding direction. Therefore, **the gradient will point in the direction of steepest increase**. ![](img/gradientdescent.png)  Gradient Descent in Words - Make a guess at where the function attains its minimum value- Calculate the gradient/derivative at that point- Use that value to decide how to make your next guess!Repeat until we get the derivative as close as we like to 0.If we want to improve our guess at the minimum of our loss function, we'll move in the **opposite direction** of the gradient away from our last guess. Hence we are using the *gradient* of our loss function to *descend* to the minimum value of the relevant loss function.  Stepping Down a Hill: Step Size So we now have the basic idea of gradient descent of "going down a hill" and hopefully it's obvious that the steeper the hill, the more we can adjust our parameters to get to "bottom" (optimal parameters) faster.But a big question is how big of a step do we take? > The amount we adjust our parameter is determined by out **step size** or **learning rate** $\alpha$ If our steps are _too big_, we risk skipping over the minimum value (optimal parameters).If our steps are _too small_, it might take us too long to reach the minimum value. ![learning_rate](https://www.jeremyjordan.me/content/images/2018/02/Screen-Shot-2018-02-24-at-11.47.09-AM.png) Here's an elegant solution: Make the size of your step **proportional to the value of the derivative at the point where you currently are in parameter space**! If we're very far from the minimum, then our values will be large, and so we therefore can safely take a large step; if we're close to the minimum, then our values will be small, and so we should therefore take a smaller step.I said the size of the step is proportional to the value of the derivative. The constant of proportionality is often called the **"learning rate"**. This page helps to explain the dangers of learning rates that are too large and too small: https://www.jeremyjordan.me/nn-learning-rate/. > Note there are other optimizations we can do for gradient descent and rely on adjusting our cost function or how we take steps or both.  Putting It All Together The general algorithm looks like this:We'll make a guess, $\vec{s}$, at where our loss function attains a minimum. If we're not happy with how close the value of the gradient there is to 0, then we'll make a new guess, and the new guess will be constructed as follows:$\large\vec{s}_{new} = \vec{s}_{old} - \alpha\nabla f(\vec{s}_{old})$,where $\alpha$ is the learning rate.In the one-dimensional case, we'll have:$\large x_{new} = x_{old} - \alpha\frac{df}{dx}|_{x_{old}}$.  Level Up: Gradient Descent Walk Through Let's go back to our original example and implement gradient descent to find the optimal parameters (slope and intercept)<jupyter_code>f, ax = plt.subplots(figsize=(8,6))
ax.scatter(x, y)

ax.set_title('Data Points to Model')
ax.set_xlabel('x', fontsize=14)
ax.set_ylabel('y', fontsize=14)

plt.tight_layout()<jupyter_output><empty_output><jupyter_text>First we need to find the gradient for each cost function (2-dimensions: a & b; slope & intercept):$$ \frac{\partial}{\partial b} (y_i - (b + ax_i))^2 = -2 \cdot (y_i-ax_i - b)$$$$ \frac{\partial}{\partial a} (y_i - (b + ax_i))^2 = -2 \cdot x_i \cdot (y_i-ax_i - b)$$ Let's formalize this into a function:<jupyter_code>def partial_deriv(a, b, x_i, y_i, respect_to):
    '''
    Get the partial derivative for cost function with respect to slope (a) 
    or intercept (b).
    '''
    if respect_to == 'b': # intercept
        return (y_i - (a * x_i + b))
    elif respect_to == 'a': # slope
        return (x_i * (y_i - (a * x_i + b)))
    else:
        print('Choose either respect_to: a or b ')
        return 0<jupyter_output><empty_output><jupyter_text>Next let's define the step we take (amount we adjust the parameters by) using the gradient and learning rate:<jupyter_code>def step_gradient(a, b, x, y, learning_rate):
    db = 0
    da = 0 
    # For each data point, update the derivative for the slope & intercept
    N = len(x)
    for i in range(len(x)):
        # Derivatives already pre-done
        
        # Partial derivatives of loss/cost function with respect to b & a
        db +=  -(2/N) * partial_deriv(a,b,x[i],y[i],respect_to='b')
        da +=  -(2/N) * partial_deriv(a,b,x[i],y[i],respect_to='a')
        
    # Adjust the slope & intercept by the gradient
    new_b = b - (learning_rate * db)
    new_a = a - (learning_rate * da)
    
    return (new_a, new_b)<jupyter_output><empty_output><jupyter_text>Let's try it out and keep track of our guesses<jupyter_code>guesses = []
alpha = 0.05
# Our guess
guess = {
    'slope': 60,
    'intercept': 10
}

guesses.append(guess)
f, ax = plt.subplots(figsize=(8,6))
plot_data_and_guess(**guess, ax=ax);
step = step_gradient(guess['slope'], guess['intercept'], x, y, learning_rate=alpha)
step
mse(x, y, guess['slope'], guess['intercept'])<jupyter_output><empty_output><jupyter_text>Let's update our guess and try again:<jupyter_code># Our guess using the new step
new_slope, new_intercept = step
guess = {
    'slope': new_slope,
    'intercept': new_intercept
}
guesses.append(guess)

# Getting adjusted parameters
step = step_gradient(guess['slope'], guess['intercept'], x, y, learning_rate=alpha)
display(step)
display(mse(x, y, guess['slope'], guess['intercept']))

# Plotting out our new parameters
f, ax = plt.subplots(figsize=(8,6))
plot_data_and_guess(**guess, ax=ax);<jupyter_output><empty_output><jupyter_text>Let's repeat this another 200 times:<jupyter_code>for i in range(200):
    # Our guess using the new step
    new_slope, new_intercept = step
    guess = {
        'slope': new_slope,
        'intercept': new_intercept
    }
    guesses.append(guess)

    # Getting adjusted parameters
    step = step_gradient(guess['slope'], guess['intercept'], x, y, learning_rate=alpha)
    #  Only display every 10
    if (i % 10) == 0:
        print(f'Step # {i}:')
        display(step)
        display(mse(x, y, guess['slope'], guess['intercept']))
        print('-'*30)<jupyter_output><empty_output><jupyter_text>What does our final result look like?<jupyter_code># Plotting out our new parameters
f, ax = plt.subplots(figsize=(8,6))
plot_data_and_guess(**guesses[-1], ax=ax);<jupyter_output><empty_output><jupyter_text>Let's take a look at the MSE over the guesses:<jupyter_code>mses = [
    mse(x,y,d['slope'],d['intercept']) for d in guesses
]
plt.plot(range(len(mses)),mses)<jupyter_output><empty_output>