1
$\begingroup$

I am beginner in machine learning and I am currently trying to find the motivation for gradient descent method. I am confused why we want to employ gradient descent method for linear regression? I see the cost function the same as the OLS function, and gradient descent method here actually takes more effort than simply getting the derivatives equal one. Then why we always try to use gradient descent here? I am when the model gets more complicated , and also when we make more assumptions on the prior distribution of the theta(parameters). The optimization problem will become much more complicated. Then will gradient descent method still survive in terms of this? And OLS/MLE method will not be able to predict the parameters? I see OLS as minimize the cost, and the MLE method as maximize the prob, which is in essence the same.(reference http://www.cs.ubc.ca/~nando/540-2013/lectures/l3.pdf) Should I think gradient descent method as a improvement from the OLS method, while the E-M method(maximize the expected likelihood) as a imporvement from the MLE method. Thanks in advance!

$\endgroup$
  • $\begingroup$ I am probably lacking in context as I don't have background in machine learning, but generally gradient descent is a technique for numerical optimization, which can be used in particular for numerically solving a system of linear equations. Seeing as the OLS regression problem can be framed as a system of linear equations, it would seem to me that gradient descent is just a particular way to try to solve this problem. $\endgroup$ – Ian Mar 26 '15 at 0:22
  • $\begingroup$ @Ian Thanks for the reply! Yeah I get the idea it is just a optimization method, like the lagrange optimization. But I do not get the idea why it is so widely used in machine learning..I guess it is because when more restrictions are added to the parameters. The parameter space will change, and gradient descent method still work in terms of this?.. $\endgroup$ – DQ_happy Mar 26 '15 at 0:32
  • $\begingroup$ At least in numerical optimization, gradient descent and related methods are used because they are robust albeit slow, and because they can actually be applied even when the dimension is extremely large. $\endgroup$ – Ian Mar 26 '15 at 0:54
  • $\begingroup$ @Ian Thanks for the reply! Emm...but can't the lagrange optimization method be used when the dimension is extremely large?..I mean I still get the idea when gradient descent is better than the lagrange method.. $\endgroup$ – DQ_happy Mar 26 '15 at 1:17
  • $\begingroup$ What do you mean by Lagrange method? Lagrange multipliers? I suppose it would help if you could formulate the type of problem you want to solve. For instance, is it to minimize $\| Ax-b \|$ subject to $Cx=d$, or something like that? In that case, the Lagrange method is really only useful for acquiring a new unconstrained optimization problem to solve instead of the constrained one. You still need a method to solve the unconstrained problem. $\endgroup$ – Ian Mar 26 '15 at 1:35
0
$\begingroup$

In the case of linear regression, we want to obtain estimates of the coefficients $\theta_1, \theta_2 $ where:
$$y = \theta_0 + \theta_1x_1 + ...+ \theta_nx_n + \epsilon$$ where $\epsilon $ is the error modeled as $N(0,\sigma^2)$.

The optimal parameters will then be
$\hat\theta = argmin_\theta L(\theta)$
where L is the OLS function you want to minimize
$L(\theta) = \frac{1}{m}\sum_{i=1}^{m}(y_i - \theta^Tx_i)^2$

On finding the first derivative of this function, equating it to zero, you will find the optimal vector of $\theta$ as:
$\hat\theta = (XX^T)^{-1}XY$

Now the problem here is that matrix inversion is a very expensive operation and so for problems with a lot of data when X and Y are large matrices, it is better to use the gradient descent method even though it is a heuristic that gets us the locally optimal parameter values.

I didn't quite understand this part of your question:
"I am when the model gets more complicated , and also when we make more assumptions on the prior distribution of the theta(parameters). The optimization problem will become much more complicated." If you re-phrase it, I will edit my response and try to answer that part as well.

$\endgroup$

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.