The Matrix Calculus You Need for Deep Learning

So, when you perform a regression of any sort, what you're doing is saying "Hey, I want to find parameters X,Y,Z, etc, that make this curve best fit the data that I have". One interpretation of 'best fit' is 'minimize the mean squared error'.

So regression is just a minimization problem. You're trying to find the values that minimize

  f(X,Y,Z...)

And, well, that means that you just want to find values for X,Y,Z such that

  ∇f(X,Y,Z) = 0

Why? Because the derivative tracks the rate of change. If the function isn't changing much locally, you've hit either a minimum or maximum (assuming the function is smooth).

Let's see how this plays out when you have a function that you're trying to minimize that only has 1 parameter. This is then just a regular old function of one variable, and we can easily visualize it.

  |     | |     x^2 + 2x
   \    |/
  ------------
     \_/|

And take it's dervative

       |   / 
       |  /
       | /      2x + 2
       |/
       |
      /|
     / |
  ------------

And then you'd say, oh hey I know the roots of 2x + 2 ! It's just x = -1. So x^2 + 2x would have a minimum at -1.

But when dealing with many functions you may not know the functional form, or there may not be a way to solve for the roots symbolically (or you don't know the tricks to do so), you might want to try a strictly numerical approach. You say "Look, I know how to compute the original function, can't I just use that directly?"

Well, one option would be to find two points on your function, one where it's positive, the other where it's negative, and then keep bisecting the interval down until you zoom in on the point where it crossed the x axis (with additional logic to handle multiple crossings). Of course, if you're function is discontinuous, or is discontinuous due to a floating point error, you're going to be hosed. This is the bisection method. However, it's not as fast as is desirable. Since each decimal point is an increase by a factor of 10 precision, and you typically want several decimal points at least, simply increasing your precision by a mere factor of 2 each time may not be good enough. This is especially true if you're doing this by hand. :)

So a faster method is to start at a point, and then draw a line tangent to that point, and see where that line intersects the x-axis. Evaluate that point, and normally it'll be closer to a zero than before. repeat. This, in many cases, will converge much faster than performing bisection.

This is known as the Newton-Raphson Method. Now, in order to draw a tangent line, you have to know how the function is changing at that point, so the line and the function's slopes will match, and well, that means you take the derivative. Since, however, the function which we're trying to find the root of is itself a derivative, this is now a second derivative.

So it turns out Newton-Raphson generalizes upwards in dimension. So when you start off with your error function that you're trying to minimize, you take it's derivative, but now you have to track how it changes in N dimensions, so the derivative object is now a vector.

Now, we're trying to minimize this vector valued function (the gradient), and set it to zero. So we take it's derivative, which, since it's vector valued, will now be a matrix, since each component can vary in N directions. So we now have a NxN matrix that tracks how everything is changing. This second order derivative is called the Hessian. And we can use it the same way (implementation left to the reader ;) ) as we did in one dimension.

Absolutely best guide (for me) on these things is http://www.psi.toronto.edu/~andrew/papers/matrix_calculus_fo... Also "Matrix algebra" by Magnus and Abadir.

In a general manner when you have a complex function you want to minimize to obtain your parameters. One way to proceed is to assume some initial parameters and refine them. To refine them, you locally approximate your function, get the minimum of the approximation, take a step toward this minimum and loop until convergence.

At first order you can approximate locally your function as a plane (the plane that go through the point and has the same first derivative), and to minimize that you take a small step (because your approximation is only valid locally) in the direction where the plane is inclined.

Alternatively you can make a better approximation of your function using higher order derivatives. So instead of approximating your function with a plane, you approximate it with a quadratic form (the multidimensional extension of the parabola). This quadratic form matches the first derivatives and also the Hessian (second derivatives in multi-dimension) of your function at your current parameters.

Once you have the approximation, there are closed formula for the minimum of the quadratic form so you can directly jump closer to the result (but how it will perform will depend how close your function resemble your approximation).

When to pick first order approximation or second order approximation is problem dependent, but a quick rule of thumb is second order is faster when close to the solution but consume memory quadratically with respect to the number of dimension so is only applicable when the dimension is low, or when you have problem specific simplifications like your problem being a sum of squares.

In practice interesting problem are too big and first order method is all you can do. But you can also improve things a little by approximating the diagonal of the Hessian, or some low-rank approximation of the Hessian. (This is another tractable kind of approximation of your function). You can also make some probabilistic approximation of your function (only considering a few examples instead of the whole training set) and from that you can derive all "on-line" methods, but this is a story for another day.

The explanatory style here is excellent. They explain clearly in 3 paragraphs what I was unable to get a good handle on in a semester of college math (due to awful teaching styles and textbooks), namely why partial derivatives are calculated the way they are.

It's amazing what a rich-get-richer effect products and content that really manage to solve problems in a high quality way get in comments sections around the web. (E.g. 3B1B.)