学步园

from: http://www.csrdu.org/nauman/2010/06/25/regression-with-gradient-descent-in-low-level-matlab/

I just finished writing my first machine learning algorithm in
Matlab. The algorithm is based on gradient descent search for estimating
parameters of linear regression (but can be easily extended to
quadratic or even higher-dimensional polynomials). It’s fairly easy if
you know the theory behind the model. So, first a very brief theory
portion. This isn’t a tutorial on statistics. Go read a book if you
don’t know about regression.

Just to recall: Regression comes in when you want to estimate a response variable (
) given explanatory variables (
). The goal for linear regression is to come up with values for parameters
(
) such that you get a ‘best possible fit’ for each jth instance in the dataset of m instances:

In matrix notation, that comes simply to:

(For ease, we assume that
is a vector of all 1s thus making
the y-intercept).

The idea of gradient descent is to come up with the best (locally) values of
. It does this by repeatedly updating the value of
using the formula:

If you have no idea what this is or if you want to know this in-depth, read till the end.

Here’s the Matlab code for this whole procedure I wrote at first. Note the use of W for
:

% Gradient descent algo for linear regression<br /> % author: Nauman (recluze@gmail.com)</p> <p>%set the data<br /> X=[1 1 1 1 1 1 1; 22 49 80 26 40 54 91];<br /> Y=[20 24 42 22 23 26 55];<br /> hold on;<br /> plot(X(2,:),Y, 'x');</p> <p>% set the actual values of W<br /> W = [5.775 0.474]';<br /> YAct = (W' * X);</p> <p>% GRADIENT DESCENT<br /> W = zeros(2,1); % initialize W to all zeros<br /> m = size(X,2); % number of instances<br /> n = size(W,1); % number of parameters<br /> alpha = 0.000025; % gradient descent step size</p> <p>disp('Starting Weights:');<br /> W</p> <p>% 1) do the loop for W estimation using gradient descent ------------<br /> for iter = 1 : 20 % let's just do 5 iterations for now ... not til convergence<br /> % for each iteration<br /> for i = 1 : n % looping for each parameter W(i)<br /> % find the derivative of J(W) for all instances<br /> sum_j = 0;<br /> for j = 1 : m<br /> hW_j = 0;<br /> for inner_i = 1 : n<br /> hW_j = hW_j + W(inner_i) * X(inner_i,j);<br /> end<br /> sum_j = sum_j + ( (hW_j - Y(j)) * X(i,j) ) ;<br /> end<br /> % calculate new value of W(i)<br /> W(i) = W(i) - alpha * sum_j;<br /> end<br /> % plot the thingy<br /> newY = (W' * X);<br /> gColor = 0.05 * iter;<br /> plot(X(2,:),newY, 'Color', [0 gColor 0]);</p> <p>% end 1) ------------<br /> end<br /> % output the final weights<br /> disp ('Final calculated weights');<br /> W<br /> % output actual weights from formula in Red W = [5.775 0.474]'<br /> plot(X(2,:),YAct, 'Color',[1 0 0]);<br /> % finish off<br /> hold off;

Then I figured that I was just doing loops and didn’t really need the
matrices. So, I went back and thought about the whole nested loop thing
and replaced the loop portion with this:

for i = 1 : n % looping for each parameter W(i)<br /> % calculate new value of W(i)<br /> W(i) = W(i) - alpha * sum( ((W'*X) - Y) .* X(i,:) );<br /> end

Seems suspiciously like the original formula, doesn’t it? Here’s what
the plot look like. The red line shows the linear regression line
calculated from a closed-form formula and the other lines show
estimations of
with the darkest colored ones being the initial guess and lighter ones are successive guesses.

And finally, as promised, here’s where you can learn all about this stuff: machine learning video lectures from Stanford
.