Training

Training is a process of adjusting parameters automatically based on the training set. Let's find out how exactly that works.

Goal

We want to minimise the loss function.

For our current logistic regression model with 30 features the loss function consists of three parts:

$$L = -\frac{1}{n} \sum_{i=1}^{n} \big[ y_i \log_e(\hat{y}_i) + (1 - y_i) \log_e(1 - \hat{y}_i) \big]$$ $$y_i = \frac{1}{1 + e^{-z_i}}$$ $$z_i = w_0 + w_1 x_{i, 1} + w_2 x_{i, 2} + ... + w_{30} x_{i, 30}$$

If we combine these three parts into a single loss function $L(w_0, w_1, ..., w_{30})$, we will see that it depends only on parameters as the $x$ and $y$ values come from the training set.

We need to find the combination of $w$ values which gives the lowest value of $L$.

Gradient descent

We will use gradient descent algorithm to achieve the goal. The idea is to pick random values for parameters first. Then adjust them slightly in the right direction, so the loss value is less than before. Repeat it multiple times, and gradually approach a minimum.

Derivatives

The algorithm sounds simple, but how exactly to adjust the parameters values in each step to make the loss value smaller? Gradient descent uses derivatives for that.

Derivatives tell us how much the value of a function $y$ changes relative to a tiny (infinitesimally small) change in $x$.

$$\frac{dy}{dx} = \lim_{h \to 0} \frac{f(x+h) - f(x)}{h}$$

• The $\frac{dy}{dx}$ is a notation for derivative
• The $h$ represents that tiny change in the input

For example, the derivative of a function $y=x^2$ is $\frac{dy}{dx} = 2x$, because

$$\begin{aligned} \frac{dy}{dx} &= \lim_{h \to 0} \frac{(x+h)^2 - x^2}{h} \\ &= \lim_{h \to 0} \frac{x^2 + 2xh + h^2 - x^2}{h} \\ &= \lim_{h \to 0} \frac{2xh + h^2}{h} \\ &= \lim_{h \to 0} \frac{h(2x + h)}{h} \\ &= \lim_{h \to 0} (2x + h) \\ &= 2x \end{aligned}$$

• The curve is flat at $x = 0$ since $\frac{dy}{dx} = 0$
• For positive $x$, the function grows faster as $x$ gets bigger. For example, at $x = 3$, a small increase in $x$ will result in about six times larger increase in $y$
• For negative $x$, the derivative is negative, meaning that a small increase in $x$ will decrease $y$

Chain rule

Our loss function is more complex. As it consists of three functions we calculate the derivative for each function separately and multiply the results.

This is called a chain rule.

$$\frac{dL}{dw_j} = \frac{dL}{d\hat{y}} \cdot \frac{d\hat{y}}{dz} \cdot \frac{dz}{dw_j}$$

If we do the calculation applying the definition of the derivative to each function, it will result in a very clean form (and using $e$ constant in the sigmoid and the logarithm contributes to that):

• $\frac{dL}{dw_0} = \frac{1}{n}\sum_{i=1}^{n}(\hat{y}_i - y_i)$
• $\frac{dL}{dw_1} = \frac{1}{n}\sum_{i=1}^{n}(\hat{y}_i - y_i) \cdot x_{i, 1}$
• ...
• $\frac{dL}{dw_{30}} = \frac{1}{n} \sum_{i=1}^{n} (\hat{y}_i - y_i) \cdot x_{i, 30}$

Updating the parameters

Knowing the derivatives values, we can get an idea of how to change the parameters to decrease the loss.

• If the value of a derivative with respect to a parameter is positive, we should decrease the parameter
• If the value of a derivative with respect to a parameter is negative, we should increase the parameter.

In other words, we should step in the opposite direction of the derivative:

$w_{i_\text{new}} = w_{i_\text{old}} - \eta \cdot \frac{dL}{dw_i}$

The $\eta$ here is a learning rate.

It is needed to control the step size.

• If the step is too big, we might pass the minimum.
• If it is too small, we might need to make many steps before reaching the minimum which makes the training slow.

To better illustrate it, let's look at a model with only one feature, one parameter ($w_0$ is predefined as -6) and a small training set.

$$\hat{y} = \sigma(-6 + w_1 \cdot x_1)$$

See how the learning rate value affects how the model reaches the minimum.

Complete algorithm

Putting it all together, for our model with 30 features and 900 messages in the training set, the complete algorithm is:

• Start with random values for all parameters
• Repeat several times (one complete step is called an epoch and the total number of epochs is adjustable):
  • Compute predictions for all training examples (this is called a forward pass)
    • $\hat{y}_i = \sigma(w_0 + w_1 x_{i,1} + ... + w_{30} x_{i,30})$
  • Compute derivatives with respect to each parameter (this is called a backward pass)
    • $\frac{dL}{dw_0} = \frac{1}{n} \sum_{i=1}^{n} (\hat{y}_i - y_i)$
    • $\frac{dL}{dw_1} = \frac{1}{n} \sum_{i=1}^{n} (\hat{y}_i - y_i) \cdot x_{i,1}$
    • ...
    • $\frac{dL}{dw_{30}} = \frac{1}{n} \sum_{i=1}^{n} (\hat{y}_i - y_i) \cdot x_{i,30}$
  • Update all parameters:
    • $w_{0_\text{new}} = w_{0_\text{old}} - \eta \cdot \frac{dL}{dw_0}$
    • $w_{1_\text{new}} = w_{1_\text{old}} - \eta \cdot \frac{dL}{dw_1}$
    • ...
    • $w_{{30}_\text{new}} = w_{{30}_\text{old}} - \eta \cdot \frac{dL}{dw_{30}}$

Testing the model

Running this algorithm on all 900 training examples, we reach the 0.11 training error mentioned earlier. The generalisation error is 0.14 and the accuracy on the test set is 93%.

Here are the adjusted parameters values and how the model behaves on any text message: