- DSP log - http://www.dsplog.com -

Closed form solution for linear regression

Posted By Krishna Sankar On December 4, 2011 @ 6:07 pm In DSP | 10 Comments

In the previous post on Batch Gradient Descent [1] and Stochastic Gradient Descent [2], we looked at two iterative methods for finding the parameter vector  which minimizes the square of the error between the predicted value  and the actual output  for all  values in the training set.

A closed form solution for finding the parameter vector  is possible, and in this post let us explore that. Ofcourse, I thank Prof. Andrew Ng for putting all these material available on public domain (Lecture Notes 1 [3]).

Notations

Let’s revisit the notations.

 be the number of training set (in our case top 50 articles),

 be the input sequence (the page index),

 be the output sequence (the page views for each page index)

 be the number of features/parameters (=2 for our example).

The value of  corresponds to the  training set

The predicted the number of page views for a given page index using a hypothesis  defined as :

where,

 is the page index,

.

Formulating in matrix notations:

The input sequence is,

 of dimension [m x n]

The measured values are,

 of dimension [m x 1].

The parameter vector is,

 of dimension [n x 1]

The hypothesis term is,

of dimension [m x 1].

From the above,

.

Recall :

Our goal is to find the parameter vector  which minimizes the square of the error between the predicted value  and the actual output  for all  values in the training set i.e.

.

From matrix algebra, we know that

.

So we can now go about to define the cost function  as,

.

To find the value of  which minimizes , we can differentiate  with respect to .

To find the value of  which minimizes ,  we set

,

.

Solving,

Note : (Update 7th Dec 2011)

As pointed by Mr. Andre KrishKevich, the above solution is same as the formula for liner least squares fit (linear least squares [4], least square in wiki [5])

Matlab/Octave code snippet

clear ;
close all;
x = [1:50].';
y = [4554 3014 2171 1891 1593 1532 1416 1326 1297 1266 ...
	1248 1052 951 936 918 797 743 665 662 652 ...
	629 609 596 590 582 547 486 471 462 435 ...
	424 403 400 386 386 384 384 383 370 365 ...
	360 358 354 347 320 319 318 311 307 290 ].';

m = length(y); % store the number of training examples
x = [ ones(m,1) x]; % Add a column of ones to x
n = size(x,2); % number of features
theta_vec = inv(x'*x)*x'*y;

The computed  values are

.

 

Note :

a)

(Refer: Matrix calculus notes [6] - University of Colorado)

b)

(Refer : Matrix Calculus Wiki [7])

References

An Application of Supervised Learning – Autonomous Deriving (Video Lecture, Class2) [8]

CS 229 Machine Learning Course Materials [9]

Refer: Matrix calculus notes [6] - University of Colorado

Matrix Calculus Wiki [7]


Article printed from DSP log: http://www.dsplog.com

URL to article: http://www.dsplog.com/2011/12/04/closed-form-solution-linear-regression/

URLs in this post:

[1] Batch Gradient Descent: http://www.dsplog.com/2011/10/29/batch-gradient-descent/

[2] Stochastic Gradient Descent: http://www.dsplog.com/2011/11/15/stochastic-gradient-descent/

[3] Lecture Notes 1: http://cs229.stanford.edu/notes/cs229-notes1.pdf

[4] linear least squares: http://www.dsplog.com/2007/07/15/straight-line-fit-using-least-squares-estimate/

[5] least square in wiki: http://en.wikipedia.org/wiki/Least_squares

[6] Refer: Matrix calculus notes: http://www.colorado.edu/engineering/cas/courses.d/IFEM.d/IFEM.AppD.d/IFEM.AppD.pdf

[7] Refer : Matrix Calculus Wiki: http://en.wikipedia.org/wiki/Matrix_calculus

[8] An Application of Supervised Learning – Autonomous Deriving (Video Lecture, Class2): http://academicearth.org/lectures/supervised-learning-autonomous-deriving

[9] CS 229 Machine Learning Course Materials: http://cs229.stanford.edu/materials.html

[10] click here to SUBSCRIBE : http://www.feedburner.com/fb/a/emailverifySubmit?feedId=1348583&loc=en_US

Copyright © 2007-2012 dspLog.com. All rights reserved. This article may not be reused in any fashion without written permission from http://www.dspLog.com.