Harder, Better, Faster, Stronger

In a previous post, I presented (generalized) linear regression from a linear algebra point of view (namely, the “normal equations”) and in this post, I discuss yet another take on the problem, this time using gradient descent.

Gradient descent isn’t particularly fascinating for this particular task (as we know closed, analytical expressions for obtaining the parameters), but linear regression is the simplest example of gradient descent I could come up with without being completely trivial.

So we have a bunch of points , and we want to fit a line of equation through them, minimizing some error function. Usually, we use the least mean square error (which corresponds to “vertical offsets“) because it usually yields easier analytical solutions. Let us define

,

and the error function

.

Since is convex in both and , we can solve

and

for and . After quite a bit of algebra, we find

and

.

Noticing that terms repeat a number of times, and possibly using special cases if the , we can arrive at an efficient, linear-time, implementation.

*
* *

While the relatively simple case of linear regression affords an analytical solution, we may (in real life) end up with another function 1) for which we can compute partial derivatives but 2) we cannot solve analytically for all its parameters, because, maybe, it is non-elementary, or it poses some other difficulty. The technique to use then is gradient descent.

Gradient descent is a relatively simple procedure conceptually—while in practice it does have its share of gotchas. Let’s say we have some function with parameter(s) which we want to minimize over the s. The variable(s) to adjust is . If we want to minimize , we must find that minimizes given the s which are fixed (or “observed” depending on how you look at it). If we can compute the partial derivative of with respect to , we know in which direction change so that decreases. We then have the update rule

,

which changes in the direction in which decreases.

However, if we know in which direction we must change it, we do not necessarily know by how much exactly, and so a function-dependent scaling factor is introduced. This scaling, the gradient step, will prevent us from updating too far and miss the minimum. If is too small it will take too long to find the minimum; if it is too large the procedure may diverge—essentially crash.

(The underlying assumption for gradient descent to work properly is that the function one wants to minimize is somewhat approximately convex, so that we follow the slope and find a (good local) minimum. If the function would highly non-convex, it would probably not work very well.)

If we have more than one parameter, then is a vector of parameters, and the derivative is replaced by a gradient, which is the vector formed by the partial derivatives in all the parameters. That is,

if we have parameters. It is therefore the general case where is a vector that gives the method its name, gradient descent.

*
* *

Back to the linear regression problem. Using , we find that the partial derivative w/ respect to the two parameters and are

and

and therefore

and the update rule is

However, for faster convergence, it is sometimes useful to use a different for each parameter. We then have

*
* *

Let us have a look at a C++ implementation. First, as with the general regression, we see that the expressions of the gradient have quite a few invariants we can factor out. Using the identities

and

,

we arrive at a constant-time computation of gradient in the iteration step (but it does take linear time, once, to initialize the invariants). Here’s how the actual code looks like:

void gradient_descent( const std::vector<float_x> & y,
                       float_x & a,
                       float_x & b )
 {
  const size_t n=y.size();
  const float_x sx=sum_of_int(n-1);
  const float_x sx2=sum_of_sqr(n-1);

  float_x sy=0;
  float_x sxy=0;

  for (size_t i=0;i<n;i++)
   {
    sy+=y[i];
    sxy+=i*y[i];
   }

  // initial guesses
  b=0;
  a=sy/n;

  // iterations
  float_x last_a,last_b;
  float_x sa=1e-3; // for n=100
  float_x sb=1e-6; // for n=100

  do
   {
    last_a=a;
    last_b=b;
    float_x db= -(sxy - a*sx - b*sx2);
    float_x da= -(sy - n*a - b*sx );

    a-=sa*da;
    b-=sb*db;
   }
  while ( (std::fabs(a-last_a)/a > 0.0001)
          ||
          (std::fabs(b-last_b)/b > 0.0001));
 }

*
* *

Where are the factors in front of the partial derivatives? Why are they gone? Think about it for a while, I’ll come back to it in a moment.

*
* *

Let us try it out!

Let and (why not) and let us add some uniform random noise . With , and not particularly efficient initial values for and , we have the following convergence:

So we see the parameters adjusting smoothly (which will not always be the case; more complex functions may yield surprises) and that we arrive to very good estimates after iterations (which, in this case, are inexpensive as being constant-time). After iterations, the algorithm bails out as it has detected convergence.

*
* *

We said earlier that might be function-specific. In the case of linear regression by means of gradient descent, the following s seems to be working fine:

100	1e-3	1e-6
1000	1e-4	1e-9
10000	1e-5	1e-12
100000	1e-6	1e-15

So and are the reason why we can drop the in front of the derivatives: the constant is absorbed into the and and so can be ignored.

*
* *

While this seems to be quite laborious for linear regression, gradient descent proves most useful in all kind of optimization problems, including machine learning. In machine learning gradient descent (and back-propagation) is used to train neural networks of all kinds. Newton’s method for finding square roots (last week’s post) can be thought of as gradient-descent type algorithm with an expression for that depends explicitly on .

We will certainly discuss gradient-descent methods again future posts.

This entry was posted on Tuesday, April 24th, 2012 at 9:37 am and is filed under algorithms, machine learning, Mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.