>_

Optimization: Gradient Descent

Written by

tiancho99

in

Gradient descent is one of the most used algorithms to optimize a function. Optimizing a function means finding the hyperparameter values for that function that give us the best possible outcome.

Gradient descent has broad applications, but in this text, we will focus on its use in Machine Learning to minimize model loss in a linear function.

Mean Squared Error (MSE)

Before tal

Linear regression

In linear regression, the model is represented as:

    \[f(x) = mx + b\]

Where:

  • m is the slope,
  • b is the intercept.

The goal of linear regression is to minimize the error between the predicted values and the actual data points. This error is often measured using the average squared distance from the predicted values to the actual values also known as Mean Squared Error (MSE). Since our model generates the predicted values, we must adjust m and b to reduce the discrepancy between predictions and real data.

Gradient descent helps achieve this by iteratively updating m and b in the direction that reduces the error. This process continues until no further improvement is found or a predefined benchmark is reached, ensuring the model fits the data as accurately as possible.

Sum of Squared Errors (SSE)

The SSE for our linear regression model is:

    \[\text{SSE}(m, b) = \sum_{i=1}^{n} \left( y_i - (mx_i + b) \right)^2\]

Where:

  • (y_i) are the actual data points (true values),
  • (x_i) are the input values (independent variable),
  • (m) and (b) are the parameters to be optimized.

We want to minimize this function with respect to (m) and (b).

Step 1: Calculate the Gradients

To update (m) and (b) using gradient descent, we first calculate the partial derivatives of the SSE with respect to both (m) and (b).

Derivative with respect to (m) (Slope)

    \[\frac{\partial \text{SSE}(m, b)}{\partial m} = -2 \sum_{i=1}^{n} x_i \left( y_i - (m x_i + b) \right)\]

Derivative with respect to (b) (Intercept):

    \[\frac{\partial \text{SSE}(m, b)}{\partial b} = -2 \sum_{i=1}^{n} \left( y_i - (m x_i + b) \right)\]

Step 2: Update the Parameters (Slope and Intercept)

Once we have the gradients, we update (m) and (b) using the following formulas:

    \[m_{\text{new}} = m_{\text{old}} - \eta \cdot \frac{\partial \text{SSE}(m, b)}{\partial m}\]

    \[b_{\text{new}} = b_{\text{old}} - \eta \cdot \frac{\partial \text{SSE}(m, b)}{\partial b}\]

Where:

  • (\eta) is the learning rate, a hyperparameter that controls how big the step is during each update.

Step 3: Apply to Our Linear Model

Let’s assume we are working with the following values for our linear function (f(x) = 1x + 1):

  • Initial slope: (m_0 = 0),
  • Initial intercept: (b_0 = 0),
  • Learning rate: (\eta = 0.01),
  • Data points: ((x_1, y_1) = (0.5, 0.8)), ((x_2, y_2) = (2.0, 1.0)), ((x_3, y_3) = (1.0, 1.5)).

Now, let’s go step by step to find the new values of (m) and (b).

Compute the Derivative with Respect to (m):

First, we need to calculate the predicted values using the current parameters. Initially, both (m) and (b) are set to 0.

  • For (x_1 = 0.5), the prediction is (f(x_1) = 0 \cdot 0.5 + 0 = 0).
  • For (x_2 = 2.0), the prediction is (f(x_2) = 0 \cdot 2.0 + 0 = 0).
  • For (x_3 = 1.0), the prediction is (f(x_3) = 0 \cdot 1.0 + 0 = 0).

Now, calculate the partial derivative with respect to (m):

    \[\frac{\partial \text{SSE}}{\partial m} = -2 \left( 0.5(0.8 - 0) + 2.0(1.0 - 0) + 1.0(1.5 - 0) \right)\]

    \[= -2 \left( 0.5 \times 0.8 + 2.0 \times 1.0 + 1.0 \times 1.5 \right)= -2 \left( 0.4 + 2.0 + 1.5 \right) = -2 \times 3.9 = -7.8\]

\subsubsection*{Compute the Derivative with Respect to (b):}

Now, calculate the partial derivative with respect to (b):

    \[\frac{\partial \text{SSE}}{\partial b} = -2 \left( (0.8 - 0) + (1.0 - 0) + (1.5 - 0) \right)\]

    \[= -2 \left( 0.8 + 1.0 + 1.5 \right) = -2 \times 3.3 = -6.6\]

\subsubsection*{Update the Parameters:}

Now, use the learning rate (\eta = 0.01) to update the slope and intercept:

    \[m_{\text{new}} = 0 - 0.01 \times (-7.8) = 0.078\]

    \[b_{\text{new}} = 0 - 0.01 \times (-6.6) = 0.066\]

Step 4: Repeat the Process

Now that we have the updated slope and intercept, we would repeat this process for multiple iterations to gradually converge to the optimal values for (m) and (b).

with each iteration, the model will find the best fit line for the given data points.

More posts