Regression
Last updated
Last updated
Gradient descent vs. Close form solution
In Andrew Ng's , he introduces linear regression and logistic regression, and shows how to fit the model parameters using gradient descent and Newton's method.
Gradient descent can be useful in some applications of machine learning, but in the more general case is there any reason why you wouldn't solve for the parameters in closed form -- i.e., by taking the derivative of the cost function and solving via Calculus?
What is the advantage of using an iterative algorithm like gradient descent over a closed-form solution in general, when one is available?
Unless the closed form solution is extremely expensive to compute, it generally is the way to go when it is available.
However,
For most nonlinear regression problems there is no closed form solution.
Even in linear regression (one of the few cases where a closed form solution is available), it may be impractical to use the formula. The following example shows one way in which this can happen.
For linear regression on a model of the form y = X * β, where X is a matrix with full column rank, the least squares solution,
β̂ = arg min‖X * β − y‖2
is given by
β̂ = (XT * X)^−1 * XT * y
Now, imagine that X is a very large but sparse matrix. e.g. X might have 100,000 columns and 1,000,000 rows, but only 0.001% of the entries in XX are nonzero. There are specialized data structures for storing only the nonzero entries of such sparse matrices.
Also imagine that we're unlucky, and XT * X is a fairly dense matrix with a much higher percentage of nonzero entries. Storing a dense 100,000 by 100,000 element XT * X matrix would then require 1 × 10 ^ 10 floating point numbers (at 8 bytes per number, this comes to 80 gigabytes.) This would be impractical to store on anything but a supercomputer. Furthermore, the inverse of this matrix (or more commonly a Cholesky factor) would also tend to have mostly nonzero entries.
However, there are iterative methods for solving the least squares problem that require no more storage than X, y, and β̂ and never explicitly form the matrix product XT * X.
In this situation, using an iterative method is much more computationally efficient than using the closed form solution to the least squares problem.
This example might seem absurdly large. However, large sparse least squares problems of this size are routinely solved by iterative methods on desktop computers in seismic tomography research.
There are also numerical accuracy issues that can make the use of the closed form solution to the least squares problem unadvisable.
In practice, it's best to use the QR factorization or SVD to solve small scale least squares problems. I'd argue that a solution using one of these orthogonal factorizations is also a "closed form solution" in comparison to using an iterative technique like LSQR
QR Factorization: A = Q * R, where Q is an orthogonal matrix and R is an upper triangular matrix.
In linear algebra, the singular-value decomposition (SVD) is a factorization of a real or complex matrix. It is the generalization of the eigen decomposition of a positive semidefinite normal matrix (for example, a symmetric matrix with positive eigenvalues) to any m x n matrix via an extension of the polar decomposition. It has many useful applications in signal processing and statistics.
