1
$\begingroup$

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?
$\endgroup$
  • $\begingroup$ Let $y_i = \mathbf{x}_i ' \mathbf{b} + e_i$. Let $f(\mathbf{b}) = \frac{1}{n} \sum_{i=1}^n e_i^2 = \frac{1}{n} \sum_{i=1}^n \left( y_i - \mathbf{x}_i' \mathbf{b} \right)^2$. What's the gradient of $f$ (with respect to $\mathbf{b}$)? $\endgroup$ – Matthew Gunn Mar 10 '19 at 20:36
  • $\begingroup$ @MatthewGunn I suppose it will be: 1/n * sum_i_n(2 * x_i^2 * b - 2 * x_i * y_i) $\endgroup$ – Andrzej Gis Mar 11 '19 at 19:45
  • $\begingroup$ Yes if $\mathbf{x}_i$ is a scalar, but that's not quite correct if $\mathbf{x}_i$ is a vector. Writing the gradient as a column vector, the answer is $\frac{\partial f}{\partial \mathbf{x}} = -\frac{1}{n} \sum_{i=1}^n 2 (y_i - \mathbf{x}'_i \mathbf{b}) \mathbf{x}_i$. Define $\mathbf{x}'_i \mathbf{b} - y_i$ as the forecast error, and you see the code computes the gradient (except the code drops the 2). $\endgroup$ – Matthew Gunn Mar 11 '19 at 20:25
  • $\begingroup$ @MatthewGunn That starts to make sense, but you used MSE activation function, while I used simple y - score. Why does it still work in my case? $\endgroup$ – Andrzej Gis Mar 11 '19 at 21:59
  • 1
    $\begingroup$ @AndrzejGis Math typsetting is supported using Latex-like markup. More information: math.meta.stackexchange.com/questions/5020/… $\endgroup$ – Sycorax Mar 11 '19 at 22:07
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks. This is a perfect explaination. No further questions :) $\endgroup$ – Andrzej Gis Mar 12 '19 at 6:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.