4 ms·

I get that this is suppose to be an introduction to gradient descent, and that the author chose a simple example to work with to illustrate the method (and expl

I get that this is suppose to be an introduction to gradient descent, and that the author chose a simple example to work with to illustrate the method (and explained it very well - kudos!). However, they should probably at least mention that the linear regression problem has an analytical solution[0] which is much faster than using gradient descent. The strength of gradient descent is that it can be used for more complicated problems, where an analytical solution isn't known (for example - you can train a neural network using gradient descent! The standard algorithm uses back-propagation to compute the errors associated with each layer of the network, and then the "learning" step shifts each parameter in the direction of those errors - just like gradient descent). [0] http://en.wikipedia.org/wiki/Linear_regression#Least-squares_estimation_and_related_techniques http://en.wikipedia.org/wiki/Linear_regression#Least-squares...

mturmon 12y ago
Agreed. Someone might actually implement linear regression in the way described! That would be embarrassing. Another thing worth mentioning is the behavior of gradient descent for problems where the Hessian is not well-conditioned (i.e., highly eccentric elliptical contours in the cost function). This would be well-illustrated by a simple example - I think a case where the y = a x + b line had a very large a would do the trick, because then a and b would be tightly coupled (choose the wrong "a" and the intercept would change a lot, due to the large slope). The number of iterations will skyrocket, which is why gradient descent is avoided if possible in favor of conjugate gradient or related approaches.
RogerL 12y ago
Also, he states that "Lines that fit our data better will result in lower error values". Strictly speaking, that is not true. The error function is a mathematical model for reality; the result is a 'best fit in a linear least squares fit' sense only. I.e you are fitting your model, not necessarily reality - what the data represents. Sure, that is all implied in the article, and I don't believe that the author is confused at all by this point. But I witness so many people just running a linear regression, claim it's "optimum", and go on to conclude grossly incorrect things. So I think it is worth stressing (repeatedly), that this is 'optimum' only in the very strict sense of minimizing your error function. Let's take a problem I am working on at the moment - tracking an object in flight. The data is noisy, but in a complicated way. Yes, you have the typical Gaussian measurement noise, but then you also have outlier measurements that have nothing to do with the object you are trying to track. Blithely applying least squares unduly weights the bad measurements because of the distance squared amplifying the influence of points that lie far away from the real trajectory. I could run gradient descent on the data (we tend to use Levenberg-Marquardt), but boy, the output will not model reality very well. It's optimum, but it is also wrong. So, for my data, the sentence should read "Lines that fit our data better will result in higher error values". Well, the relationship is more complicated that that, but you get the idea. I'm not dismissing the article (I liked it), just discussing the next steps you have to start thinking about. If you know you have linear data with Gaussian noise you'll get a meaningful minimum using this approach. If that is not true, then do not trust this to give you meaningful information. Get thee to a University, go (which is what the author also suggests at the end).
babs474 12y ago
You need it for l1 and l2 regularization which is popular these days don't you?
- throwaway283719 12y ago
  No. L2 regularization (ridge regression) also has an analytical solution, and L1 regularization (lasso) can be more efficiently solved using the LARS (least-angle regression) algorithm. Gradient descent would work for ridge regression (it would just be slow). It wouldn't even work for lasso, because the penalty function isn't differentiable at the origin.
deleted 12y ago
[deleted]
- Sherlock 12y ago
  That's a common (notation-induced) mistake. You just need to solve a linear system.
- GFK_of_xmaspast 12y ago
  I think n is the number of predictor variables, not the data size.
- teraflop 12y ago
  Nope, ordinary linear regression can be done in O(n) time and O(1) space. http://en.wikipedia.org/wiki/Simple_linear_regression http://en.wikipedia.org/wiki/Simple_linear_regression
- grayclhn 12y ago
  Just to add to the other comments: you almost never want to invert the X'X matrix. (Which is k by k, where k is the number of regressors.) The QR decomposition is much more reliable. (for those that want a citation: Seber and Lee's Linear regression analysis is great.)
mattnedrich 12y ago
Author here. These are all great points. I chose linear regression because it's simple and easy to understand. There is obviously a simple closed form solution to this problem. However, as already mentioned, gradient descent has some nice advantages like scaling. Further, a "close enough" solution/approximation might be sufficient depending on the application.
- grayclhn 12y ago
  There are algorithms to add variables and observations to an estimated linear regression model, so scaling is not an advantage of gradient descent. You should mention in the post that there are better ways to estimate this model, even if you're just presenting it as an example.
- nkurz 12y ago
  One tiny improvement to the article would be to change the "visualization of the surface" images to to show the part of the surface where the solution is eventually found. The 3D graph cuts off at y = -2, which makes things a little harder to understand.
jmalicki 12y ago
Actually, although the direct method is often faster than gradient descent, it is not faster than conjugate gradient. And conjugate gradient is more numerically stable. So the question is, why would anyone competent use the direct method for linear regression?

mturmon 12y ago

Agreed. Someone might actually implement linear regression in the way described! That would be embarrassing. Another thing worth mentioning is the behavior of gradient descent for problems where the Hessian is not well-conditioned (i.e., highly eccentric elliptical contours in the cost function). This would be well-illustrated by a simple example - I think a case where the y = a x + b line had a very large a would do the trick, because then a and b would be tightly coupled (choose the wrong "a" and the intercept would change a lot, due to the large slope). The number of iterations will skyrocket, which is why gradient descent is avoided if possible in favor of conjugate gradient or related approaches.

RogerL 12y ago

Also, he states that "Lines that fit our data better will result in lower error values". Strictly speaking, that is not true. The error function is a mathematical model for reality; the result is a 'best fit in a linear least squares fit' sense only. I.e you are fitting your model, not necessarily reality - what the data represents. Sure, that is all implied in the article, and I don't believe that the author is confused at all by this point. But I witness so many people just running a linear regression, claim it's "optimum", and go on to conclude grossly incorrect things. So I think it is worth stressing (repeatedly), that this is 'optimum' only in the very strict sense of minimizing your error function. Let's take a problem I am working on at the moment - tracking an object in flight. The data is noisy, but in a complicated way. Yes, you have the typical Gaussian measurement noise, but then you also have outlier measurements that have nothing to do with the object you are trying to track. Blithely applying least squares unduly weights the bad measurements because of the distance squared amplifying the influence of points that lie far away from the real trajectory. I could run gradient descent on the data (we tend to use Levenberg-Marquardt), but boy, the output will not model reality very well. It's optimum, but it is also wrong. So, for my data, the sentence should read "Lines that fit our data better will result in higher error values". Well, the relationship is more complicated that that, but you get the idea. I'm not dismissing the article (I liked it), just discussing the next steps you have to start thinking about. If you know you have linear data with Gaussian noise you'll get a meaningful minimum using this approach. If that is not true, then do not trust this to give you meaningful information. Get thee to a University, go (which is what the author also suggests at the end).

babs474 12y ago

You need it for l1 and l2 regularization which is popular these days don't you?

throwaway283719 12y ago
No. L2 regularization (ridge regression) also has an analytical solution, and L1 regularization (lasso) can be more efficiently solved using the LARS (least-angle regression) algorithm. Gradient descent would work for ridge regression (it would just be slow). It wouldn't even work for lasso, because the penalty function isn't differentiable at the origin.

deleted 12y ago

[deleted]

Sherlock 12y ago
That's a common (notation-induced) mistake. You just need to solve a linear system.
GFK_of_xmaspast 12y ago
I think n is the number of predictor variables, not the data size.
teraflop 12y ago
Nope, ordinary linear regression can be done in O(n) time and O(1) space. http://en.wikipedia.org/wiki/Simple_linear_regression http://en.wikipedia.org/wiki/Simple_linear_regression
grayclhn 12y ago
Just to add to the other comments: you almost never want to invert the X'X matrix. (Which is k by k, where k is the number of regressors.) The QR decomposition is much more reliable. (for those that want a citation: Seber and Lee's Linear regression analysis is great.)

mattnedrich 12y ago

Author here. These are all great points. I chose linear regression because it's simple and easy to understand. There is obviously a simple closed form solution to this problem. However, as already mentioned, gradient descent has some nice advantages like scaling. Further, a "close enough" solution/approximation might be sufficient depending on the application.

grayclhn 12y ago
There are algorithms to add variables and observations to an estimated linear regression model, so scaling is not an advantage of gradient descent. You should mention in the post that there are better ways to estimate this model, even if you're just presenting it as an example.
nkurz 12y ago
One tiny improvement to the article would be to change the "visualization of the surface" images to to show the part of the surface where the solution is eventually found. The 3D graph cuts off at y = -2, which makes things a little harder to understand.

jmalicki 12y ago

Actually, although the direct method is often faster than gradient descent, it is not faster than conjugate gradient. And conjugate gradient is more numerically stable. So the question is, why would anyone competent use the direct method for linear regression?