Intuition behind computing gradient for a model

Question

I'm trying to understand gradient computation. The basic formula I found looks like so:

learning_rate = 0.0001
score = x.dot(w)
error = y - score
gradient = x.T.dot(error) / len(x) # what's going on in here?
w += (learning_rate * gradient)

I understand score computation. Every row in w corresponds to a certain output feature and represents how much every input feature from x_i influences the output feature.

Error computation is obvious, we measure how much the model is off.

I'm having troubles interpreting the gradient computation line. I know what gradient is but this line isn't clear to me. Could someone explain to me the logic behind:

1. Why this line results in a gradient in the first place? I can see no derivatives in there.
2. Why do we transpose the inputs vector x? (Yes we need to transpose it to make it work with the dot product, but what's the intuition here?)
3. Why do we scale the gradient with /len(x)?
4. Given x contains all training examples, do we need a small learning rate? Will gradient ever explode? Why?

Answer 1

If you really want to understand what is going on, you will have to break the matrix gradients down into vector/scalar gradients and work through the math. These stuff and the transposes are confusing for all of us at first but you'll get used to it with practice.

Simple case: x and w are vectors

Assume $x$ is an our input of size $(1,D)$, where $D$ is the number of dimensions. $w$ is our weight matrix of size $(D,1)$, and $score$ is our output which is a scalar. In this case: $$score = xw\\ = [x_1,x_2,...,x_D] \begin{bmatrix} w_{1} \\ w_{2} \\ \vdots \\ w_{D} \end{bmatrix}\\ = x_{1}w_{1}+x_{2}w_{2}+...+x_{D}w_{D} $$ And the squared error (${error^2}$) is: $$ {error^2} = \frac{1}{2}(score-y)^2 \\ = \frac{1}{2}(x_{1}w_{1}+x_{2}w_{2}+...+x_{D}w_{D}-y)^2 $$ Now, the gradient of ${error^2}$ with respect to $w$ will be of the same shape of $w$: $$\nabla_{w} {error^2} = \begin{bmatrix} \nabla_{w_1} {error^2} \\ \nabla_{w_2} {error^2} \\ \vdots \\ \nabla_{w_D} {error^2} \end{bmatrix}$$ Let's compute each term individually: $$\nabla_{w_1} {error^2} = \dfrac{\partial (\frac{1}{2}(x_{1}w_{1}+x_{2}w_{2}+...+x_{D}w_{D}-y)^2)}{\partial w_1} = x_1(score-y)\\ \nabla_{w_2} {error^2} = \dfrac{\partial (\frac{1}{2}(x_{1}w_{1}+x_{2}w_{2}+...+x_{D}w_{D}-y)^2)}{\partial w_2} = x_2(score-y)\\ .\\.\\.\\ \nabla_{w_D} {error^2} = \dfrac{\partial (\frac{1}{2}(x_{1}w_{1}+x_{2}w_{2}+...+x_{D}w_{D}-y)^2)}{\partial w_D}= x_D(score-y)$$ Therefore, we can write the gradient of ${error^2}$ with respect to $w$ as: $$\nabla_{w} {error^2} =\begin{bmatrix} x_{1} \\ x_{2} \\ \vdots \\ x_{D} \end{bmatrix} (score-y)\\ = x^T (score-y)$$ Then, the gradient descent update would be: $$ w_{\text{new}} = w_{\text{old}} - \nabla_{w_{\text{old}}} {error^2}\\ = w_{\text{old}} + x^T (y-score) $$

Which is the same as the update to $w$ which you have in your code:

error = y - score
gradient = x.T.dot(error) / len(x) # here, len(x)=1 (since x is of shape (1, D))
w += (learning_rate * gradient)

More General Case: X is a matrix, w is still a vector

Before we only had one input sample $x$ which had $D$ dimensions, now let's say you have $N$ input samples where each sample has $D$ dimensions. For each sample, you can compute the $error^2$ like above, so you will have $N$ different $error^2$ values. Now, you can get the average value of these $error^2$s to get the MSE: $$ \text{MSE} = \frac{1}{N}\sum_{i=1}^{N}{error^2}^{(i)} $$ Now, if you want to minimize the MSE, you need to compute the gradient of MSE with respect to $w$: $$ \nabla_{w} \text{MSE} = \frac{1}{N} \sum_{i=1}^{N}\nabla_{w} {error^2}^{(i)}\\ = \frac{1}{N} \sum_{i=1}^{N} {{x^{(i)}}^T} (y^{(i)}-score^{(i)}) $$ Now, remember that $X$ was of shape $(N,D)$, and $w$ was of shape $(D,1)$, so $score$ and $y$ would be of shape $(N,1)$. So you can write the above formulation in matrix form as: $$ \nabla_{w} \text{MSE} = \frac{1}{N} X^T (y-score) $$ So this is where you get the $\frac{1}{N}$ from. It comes from computing the mean of errors for MSE. In your code, $N$ would be len(x), thus:

error = y - score
gradient = x.T.dot(error) / len(x) # len(x)=N
w += (learning_rate * gradient)

Why you need a small learning rate

With gradient descent, your update step only depends on the first order derivative of the error function. This means that you are approximating your error function as a linear function (its first order Taylor series approximation) without considering the second order derivatives and so on. Your error function is clearly not truly a linear function, however it does behave linearly around a certain point for a small enough step. That is why we need to use a small learning rate, because we can only estimate our function to be linear in a very small region around the current point.

More intuitively, your gradient gives you local information about which direction to move in to reduce your error. Since this information is local, you can only expect your error to get smaller if you move a small step in that direction. You can't expect your error to reduce if you take a big jump in that direction.

This has nothing to do with exploding gradients. Gradient explosion is witnessed in deep neural networks and has little to do with the learning rate.

Practical Tips

• The Matrix Cookbook is a life saver for matrix derivatives. Knowing some of the formulations will help you compute gradients much faster than if you were to break it down like this.
• Always keep the dimensionalities in mind. Gradient of a scalar (loss or error) with respect to any matrix should have the same shape as that matrix.

One Last Note

I think it would be much more standard to change your code to this:

learning_rate = 0.0001
score = x.dot(w)
error = np.mean((1/2)*((y - score)**2))
grad_error = (y - score) / len(x)
gradient = x.T.dot(grad_error)
w += (learning_rate * gradient)

since previously error was not actually the error but rather it was the gradient of the MSE with respect to score.