gradient descent vectorization

In linear regression problem, we often use gradient descent algorithm to minimize the cost function $𝐽\left(𝜃\right)$.

This is my derive for vectorize gradient descent algorithm, and I’ll use 1-index in this article.

Symbols：

m : number of training example.

n : number of features plus 1.

X : input of training set, X is a [n x m] dimension matrix.

${𝑥}_{𝑗}^{𝑖}$ : the ${𝑗}^{𝑡ℎ}$ input of the ${𝑖}^{𝑡ℎ}$ training example.

PS: ${𝑥}_1^{𝑖}$ is always 1 for any i in [1:m].

Y : output of training set, Y is a [1 x m] dimension matrix.

${𝑦}^{𝑖}$ : the output of the ${𝑖}^{𝑡ℎ}$ training example.

${ℎ}_{𝜃\left(𝑥\right)}$ : linear hypothesis function. In linear regression problem, ${ℎ}_{𝜃\left(𝑥\right)}$ is often as follow: ${ℎ}_{𝜃\left({𝑥}^{𝑖}\right)}={𝜃}_1+{𝜃}_2{𝑥}_2^{𝑖}+\cdots +{𝜃}_{𝑛}{𝑥}_{𝑛}^{𝑖}={𝜃}_1{𝑥}_1^{𝑖}+{𝜃}_2{𝑥}_2^{𝑖}+\cdots +{𝜃}_{𝑛}{𝑥}_{𝑛}^{𝑖}$

$𝜃$ : parameters of hypothesis function, $𝜃$ is a [n x 1] dimension matrix or n dimension column vector.

$𝐽\left(𝜃\right)$ : cost function of hypothesis function, in gradient descent without regularization,cost function is often defined as follow:

Gradient descent algorithm can be described as the psuedocode below.

do:

(for j in [1:n])

until convergence

This algorithm actually need to update all the parameters $𝜃$ simultaneously, so i didn’t put the update operation in a for loop.

$𝛼$ is the learning rate, which controls how large a step our algorithm takes.

we actually need 4 nested loop to do this without vectorization. Not only will this implementation be complicated, but also slow. So we need to vectorize.

As we assumed, X is as follow:

Y is:

$𝜃$ is :

so

here ${𝑥}^{𝑖}$ is the ${𝑖}^{𝑡ℎ}$ column training data.

so

which is J($𝜃$)=1/2/m .* sum(($𝜃$’ .* X - Y) .^ 2) in octave.

Now let’s see the partial derivative term,

Keep going, we get:

Finally we get our update rules:

In octave, it looks like this:

update = 1 / col * input * (theta' * input - output)';
theta = theta - step * update;

And here is the code:

function parameters = gd(input, output, theta, step, eps)
% function that implement gradient descent algorithm
col = length(output);
do
  % j = 1 / 2 / col * sum((theta' * input - output) .^ 2);
  % 上行注释计算costfunction
  update = 1 / col * input * (theta' * input - output)';
  theta = theta - step * update;
until max(abs(update)) <= eps
parameters = theta;