user-avatar
Today is Thursday
October 19, 2017

Tag: gradient descent

April 22, 2017

Explanation of vectorized form of the for loop calculation of gradient descent in Exercise 1 in ML class in couresa

by viggy — Categories: Uncategorized — Tags: , , , Leave a comment

Source: Storing this for future reference

If you are wondering how the seemingly complex looking for loop can be vectorized and cramped into a single one line expression, then please read on. The vectorized form is:

theta = theta – (alpha/m) * (X’ * (X * theta – y))

Given below is a detailed explanation for how we arrive at this vectorized expression using gradient descent algorithm:

This is the gradient descent algorithm to fine tune the value of θ: enter image description here

Assume that the following values of X, y and θ are given:

m = number of training examples
n = number of features + 1

Here

m = 5 (training examples)
n = 4 (features+1)
X = m x n matrix
y = m x 1 vector matrix
θ = n x 1 vector matrix
xi is the ith training example
xj is the jth feature in a given training example

Further,

h(x) = ([X] * [θ]) (m x 1 matrix of predicted values for our training set)
h(x)-y = ([X] * [θ] – [y]) (m x 1 matrix of Errors in our predictions)

whole objective of machine learning is to minimize Errors in predictions. Based on the above corollary, our Errors matrix is m x 1 vector matrix as follows:

To calculate new value of θj, we have to get a summation of all errors (m rows) multiplied by jth feature value of the training set X. That is, take all the values in E, individually multiply them with jth feature of the corresponding training example, and add them all together. This will help us in getting the new (and hopefully better) value of θj. Repeat this process for all j or the number of features. In matrix form, this can be written as:


This can be simplified as:

[E]’ x [X] will give us a row vector matrix, since E’ is 1 x m matrix and X is m x n matrix. But we are interested in getting a column matrix, hence we transpose the resultant matrix.

More succinctly, it can be written as:

Since (A * B)’ = (B’ * A’), and A” = A, we can also write the above as

This is the original expression we started out with:

theta = theta – (alpha/m) * (X’ * (X * theta – y))