Machine Learning - 2.3 - Exercise
This post gives the solutions and the detailed reasoning for each exercise in week 2 of professor Andrew Ng’s Machine Learning course.
See the other posts at Machine Learning Course Structure.
1. Installing Octave
Nothing could be easier: Download Octave
Pick the 64-bit version: octave-4.4.1-w64-installer.exe (~ 238 MB)
2. Warmup
The task: return a 5x5 identity matrix
A = eye(5);3. Cost Function J
The formula:
$latex J(\theta) = \frac{1}{2m}\sum\limits_{i=1}^m(h_0(x^{(i)})-y^{(i)})^2$
Vectorize:
We have:
$latex h_0(x^{(i)}) =\theta_0X_0 + \theta_1X_1+…+\theta_nX_n$
If we treat $latex \theta$ as an $latex n\times1$ vector and X as an $latex m\times n$ matrix, the computation above becomes as simple as:
$latex h_0(x^{(i)})=\begin{bmatrix}x_0^{(1)} & x_1^{(1)} \\x_0^{(2)} & x_1^{(2)} \\ … & … \\ x_0^{(m)} & x_1^{(m)} \end{bmatrix}\times\begin{bmatrix}\theta_0 \\ \theta_1 \\ … \\ \theta_m \end{bmatrix}=X\times\theta$
So the cost function turns into:
$latex J(\theta) = \frac{1}{2m}\sum\limits_{i=1}^m(X\times\theta-y)^2$
Code:
J = (1/(2*m))*sum((X*theta - y).^2)4. Gradient Descent
The Gradient Descent algorithm has 2 steps:
- Compute the set of $latex \theta$ values
- Plug them into the cost function to check for convergence
For simplicity we’ll assume there are only 2 features, $latex x_0 = 1$ and $latex x_1$ (n = 2)
The formula:
$latex \theta_j = \theta_j - \alpha \frac{1}{m} \sum\limits_{i=1}^{m} (h_\theta(x^{(i)}) - y^{(i)}) \cdot x_j^{(i)}$
We split the formula above into 2 parts:
$latex \theta_j = \theta_j - gradient$
where
$latex gradient = \alpha \frac{1}{m} \sum\limits_{i=1}^{m} (h_\theta(x^{(i)}) - y^{(i)}) \cdot x_j^{(i)}$
with:
- X = $latex \begin{bmatrix}x_0^{(1)} & x_1^{(1)} \\x_0^{(2)} & x_1^{(2)} \\ … & … \\ x_0^{(m)} & x_1^{(m)} \end{bmatrix}$
- $latex \theta = \begin{bmatrix}\theta_0 \\ \theta_1 \end{bmatrix}$
- y = $latex \begin{bmatrix}y_1 \\ y_2 \\ … \\ y_m \end{bmatrix}$
Same as with the cost function, we get:
$latex (X\times\theta - y)=\begin{bmatrix} \theta_0x_0^{(1)}+\theta_1x_1^{(1)}-y_1 \\ \theta_0x_0^{(2)}+\theta_1x_1^{(2)}-y_2 \\ … \\ \theta_0x_0^{(m)}+\theta_1x_1^{(m)}-y_m \end{bmatrix}=\begin{bmatrix} a_1 \\ a_2 \\ … \\ a_m \end{bmatrix}= a$
where a is an m x 1 vector
Multiplying by $latex x_j^{(i)}$ and summing
For each element of vector a we multiply it by the matching x, then add all the results together.
To multiply, sum and return a vector holding the gradient values all at once, we have to transform the matrix X a bit.
$latex X^T = \begin{bmatrix}x_0^{(1)} & x_0^{(2)} & … & x_0^{(m)}\\ x_1^{(1)} & x_1^{(2)} & … & x_1^{(m)}\end{bmatrix}$
Multiplying this matrix by the vector a gives us the result we want.
$latex X^T\times a = \begin{bmatrix}x_0^{(1)} & x_0^{(2)} & … & x_0^{(m)}\\ x_1^{(1)} & x_1^{(2)} & … & x_1^{(m)}\end{bmatrix} \times \begin{bmatrix} a_1 \\ a_2 \\ … \\ a_m \end{bmatrix}=\begin{bmatrix} a_1x_0^{(1)} + a_2x_0^{(2)} + … + a_mx_0^{(m)} \\ a_1x_1^{(1)} + a_2x_1^{(2)} + … + a_mx_1^{(m)} \end{bmatrix}$
Code:
file gradientDescent.m
function [theta, J_history] = gradientDescent(X, y, theta, alpha, num_iters)
%GRADIENTDESCENT Performs gradient descent to learn theta
% theta = GRADIENTDESCENT(X, y, theta, alpha, num_iters) updates theta by
% taking num_iters gradient steps with learning rate alpha
% Initialize some useful values
m = length(y); % number of training examples
J_history = zeros(num_iters, 1);
for iter = 1:num_iters
gradient = (alpha/m) * X' * (X*theta - y);
theta = theta - gradient;
% Save the cost J in every iteration
J_history(iter) = computeCost(X, y, theta);
end
endThis code also works for gradient descent with many features
5. Normal Equation
This one is fairly easy, so I won’t explain it and will just give the code
file normalEqn.m
function [theta] = normalEqn(X, y)
%NORMALEQN Computes the closed-form solution to linear regression
% NORMALEQN(X,y) computes the closed-form solution to linear
% regression using the normal equations.
theta = zeros(size(X, 2), 1);
theta = pinv(X'*X)*X'*y;
endOn to week 3 :D