[Machine Learning] Exam 1(Programming Assignment)

해당 내용은 Andrew Ng 교수님의 Machine Learning 강의(Coursera)를 정리한 내용입니다.

※ 아래에 문제 풀이가 있습니다. 원하지 않는다면 스크롤을 내리지 마세요.

 

2주차를 끝내고 Octave로 직접 코드 작성하여 제출하는 과제이다.

과제를 다운로드하여 압축을 풀면 다음과 같은 파일들이 있다.

우리가 작성해야되는 목록은 다음과 같다. 자세한 내용은 Ex1.pdf를 참조하면 된다.

 

warmUpExercise.m - 5x5 단위행렬 A 반환하는 코드 작성(필수)

plotData.m - 데이터의 분포를 볼 수 있는 figure를 만드는 코드 작성(필수)

computeCost.m - univariate linear regression의 Cost Function J의 값을 반환하는 코드 작성(필수)

gradientDescent.m - univariate linear regression의 Gradient Descent를 연산하는 코드 작성(필수)

 

아래는 Optional 과제이다.

computeCostMulti.m - 변수가 여러개인 multivariate linear regression의 Cost Function J의 값을 반환하는 코드 작성(옵션)

gradientDescentMulti.m - multivariate linear regression의 Gradient Descent를 연산하는 코드 작성(옵션)

featureNormalize.m - Mean Normalization을 위한 코드 작성, 즉 re-scaling을 위한 연산(옵션)

normalEqn.m - Normal Equation으로 theta를 구하는 코드 작성

 

현재 featureNormalize.m 을 제외하고는 완료를 하였다.

코드는 https://github.com/junstar92/MachineLearning_Cousera/tree/master/ex1 를 참조하면 된다.

자세하게 풀어보는 건 Week3 수업을 다 듣고 정리해보겠다.

모두 완료하였다. 아래 Github을 참조하면 된다.

https://github.com/junstar92/Coursera/tree/master/MachineLearning/ex1

 

[warmUpExercise.m]

단순히 5x5 단위행렬을 반환하는 함수를 작성한다.

function A = warmUpExercise()
%WARMUPEXERCISE Example function in octave
%   A = WARMUPEXERCISE() is an example function that returns the 5x5 identity matrix

A = [];
% ============= YOUR CODE HERE ==============
% Instructions: Return the 5x5 identity matrix 
%               In octave, we return values by defining which variables
%               represent the return values (at the top of the file)
%               and then set them accordingly. 
A = eye(5);


% ===========================================


end

단위행렬 생성은 eye(n)으로 생성할 수 있으며, n x n 단위행렬을 생성한다는 의미이다.

 

[plotData.m]

데이터의 분포를 볼 수 있는 figure를 만드는 코드 작성한다. ex1data1.txt를 읽고, 이 데이터의 1열은 입력 x, 2열은 출력 y가 된다. m은 Training Set의 개수이다. 

여기서 m = 97이고, x와 y는 97 x 1 행렬이다. plot함수를 사용해서 만들면 되고, 'rx'는 빨간 x 표시로 그리라는 의미고, 뒤에 'MarkerSize', 10 은 마커 크기를 10으로 설정한다는 의미이다.

function plotData(x, y)
%PLOTDATA Plots the data points x and y into a new figure 
%   PLOTDATA(x,y) plots the data points and gives the figure axes labels of
%   population and profit.
 
figure; % open a new figure window
 
% ====================== YOUR CODE HERE ======================
% Instructions: Plot the training data into a figure using the 
%               "figure" and "plot" commands. Set the axes labels using
%               the "xlabel" and "ylabel" commands. Assume the 
%               population and revenue data have been passed in
%               as the x and y arguments of this function.
%
% Hint: You can use the 'rx' option with plot to have the markers
%       appear as red crosses. Furthermore, you can make the
%       markers larger by using plot(..., 'rx', 'MarkerSize', 10);
 
plot(x, y, 'rx', 'MarkerSize', 10);
ylabel('Profit in $10,000s');
xlabel('Population of City in 10,000s');
 
% ============================================================
 
end

결과로 아래와 같은 figure가 그려진다.

 

[computeCost.m]

Linear regression(univariate)의 cost를 계산하는 코드이다. 우리는 cost에 해당하는 \(J^(\theta)\) 를 반환하는 코드를 작성해야 한다. 데이터는 이전에서 사용했던 'ex1data1.txt'를 그대로 사용한다.

$$J^(\theta) = \frac{1}{2m} \sum_{i = 1}^{m}(h_\theta(x^{(i)}) - y^{(i)})^2$$

Cost는 위와 같이 구할 수 있으며, 이를 코드로 나타내면 아래와 같다.

function J = computeCost(X, y, theta)
%COMPUTECOST Compute cost for linear regression
%   J = COMPUTECOST(X, y, theta) computes the cost of using theta as the
%   parameter for linear regression to fit the data points in X and y
 
% Initialize some useful values
m = length(y); % number of training examples
 
% You need to return the following variables correctly 
J = 0;
 
% ====================== YOUR CODE HERE ======================
% Instructions: Compute the cost of a particular choice of theta
%               You should set J to the cost.
predictions = X * theta;
sqrErros = (predictions - y).^2;
J = 1 / (2*m) * sum(sqrErros);
 
 
% =========================================================================
 
end

우선 ex1.m에서 진행되는 코드를 살펴보자.

 ex1.m

\(h_\theta(x) = \theta_0x_0 + \theta_1x_1\) 로 나타낼 수 있고, \(x_0 = 1\)이다.

그래서 X의 1열은 전부 1로 채우고, 2열에 \(x_1\)을 읽어온다. 따라서 X는 97 x 2 행렬이다.

y는 ex1data1.txt의 2열만 읽어온다(97x1 행렬). 

theta는 \(\theta_0, \theta_1\)로 이루어졌고, \(\theta = \begin{bmatrix} \theta_0 \\ \theta_1 \end{bmatrix}\) 로 나타내어 진다. theta의 초기값은 모두 0이다.

 

predictions(line 15)가 Hypothesis Function \(h_\theta(x)\)이 계산된 값을 의미하며, X가 97 x 2 행렬이고, theta가 2 x 1 행렬이기 때문에 계산하면 결과값 y와 동일하게 97 x 1행렬로 계산된다.

sqrError(line 16)는 \((h_\theta(x^{(i)}) - y^{(i)})^2\)를 의미하며, 벡터화하여 표시하면 \((X\theta - y)^{2}\)으로 나타낼 수 있다. 이 식은 아래와 같은 식이 계산된다.

$$h_\theta(x^{(i)}) - y^{(i)} = X\theta - y = \begin{bmatrix} 1 && x_1^{(1)} \\ 1 && x_1^{(2)} \\ ... && ... \\ 1 && x_1^{(m)} \end{bmatrix} \begin{bmatrix} \theta_0 \\ \theta_1 \end{bmatrix} - \begin{bmatrix} y^{(1)} \\ y^{(2)} \\ ... \\ y^{(m)} \end{bmatrix} = \begin{bmatrix} \theta_0 + x_1^{(1)}\theta_1 - y^{(1)} \\ \theta_0 + x_1^{(2)}\theta_1 - y^{(2)} \\ ... \\ \theta_0 + x_1^{(m)}\theta_1 - y^{(m)} \end{bmatrix}$$

$$(h_\theta(x^{(i)}) - y^{(i)})^2 = \begin{bmatrix} ( \theta_0 + x_1^{(1)}\theta_1 - y^{(1)})^2 \\ (\theta_0 + x_1^{(2)}\theta_1 - y^{(2)})^2 \\ ... \\ (\theta_0 + x_1^{(m)}\theta_1 - y^{(m)})^2 \end{bmatrix}$$

즉, \(\sum_{i = 1}^{m}(h_\theta(x^{(i)}) - y^{(i)})^2\)는 \(\begin{bmatrix} ( \theta_0 + x_1^{(1)}\theta_1 - y^{(1)})^2 \\ (\theta_0 + x_1^{(2)}\theta_1 - y^{(2)})^2 \\ ... \\ (\theta_0 + x_1^{(m)}\theta_1 - y^{(m)})^2 \end{bmatrix}\) 의 element를 모두 더한 것과 같다. 여기서 m은 97이 된다.

그래서 line 17을 계산하면 Cost 값을 구할 수 있다.

 

 

[gradientDescent.m]

Gradient Descent를 진행하면서 theta 값을 갱신하는 함수를 작성해야 한다.

ex1.m

$$\theta_j := \theta_j - \alpha\frac{\partial}{\partial\theta_j}J(\theta)$$

매 Gradient Descent를 진행하면서 갱신되는 Theta 값, 즉, 우리는 위 식에 해당하는 부분을 구현해야 한다.

우선 구현되는 코드는 아래와 같다.

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
    % ====================== YOUR CODE HERE ======================
    % Instructions: Perform a single gradient step on the parameter vector
    %               theta. 
    %
    % Hint: While debugging, it can be useful to print out the values
    %       of the cost function (computeCost) and gradient here.
    %
    x1 = X(:,2);
    h = theta(1) + (theta(2)*x1);
    
    theta0 = theta(1) - alpha * (1/m) * sum(h-y);
    theta1 = theta(2) - alpha * (1/m) * sum((h-y) .*x1);
    
    
    theta = [theta0; theta1];
    % ============================================================
 
    % Save the cost J in every iteration    
    J_history(iter) = computeCost(X, y, theta);
end
end

\(\alpha\)는 Learning Rate로 주어지는 값이며, num_iters는 우리가 반복해야되는 횟수를 의미한다. 이 함수에서 우리는 theta와 J_history, 매 iter마다 cost J 값을 저장해서 반환하는 코드를 작성하는 것이다.

위 코드에서는 univariate linear regression으로 \(\theta_0, \theta_1\)만 구하면 되기 때문에 각각 따로 구했고, 우리는 이미 벡터화를 해서 일반화 시키는 방법을 배웠었다. 더욱 간단하게 표현하는 코드는 조금 있다가 보도록 하자.

 

우리는 Gradient Descent 에서의 theta를 갱신하는 식을 아래와 같이 나타낼 수 있다.

$$\theta_j := \theta_j - \frac{\alpha}{m}\sum_{i = 1}^{m}(h_\theta(x^{(i)}) - y^{(i)})x_j^{(i)}$$

여기서 j 는 0과 1만 존재하므로, 풀어서 나타내면,

\(\theta_0 := \theta_0 - \frac{\alpha}{m}\sum_{i = 1}^{m}(h_\theta(x^{(i)}) - y^{(i)})x_0^{(i)} = \theta_0 - \frac{\alpha}{m}\sum_{i = 1}^{m}(h_\theta(x^{(i)}) - y^{(i)}) \)

\(\theta_1 := \theta_0 - \frac{\alpha}{m}\sum_{i = 1}^{m}(h_\theta(x^{(i)}) - y^{(i)})x_1^{(i)}\)

 

위 식은 line 21과 line 22를 의미하고, theta를 업데이트하고 방금전에 구했던 costFunction 함수를 사용하여 Cost의 값을 기록하면 된다.

 

간단하게 Vector화하여 나타내는 것을 다시 이야기하자면, 우리는 아래처럼 Gradient Descent를 진행해야한다.

Repeat until convergence {

...

} simultaneously update for every j = 0, 1, ..., n

여기서 \(\frac{\partial}{\partial\theta}J(\theta)\) 를 벡터화하여 나타내면, 아래와 같이 나타낼 수 있다.

\(\frac{\partial}{\partial\theta}J(\theta) = \frac{1}{m}X^{T}(X\theta - y)\)

즉, Gradient Descent 를 벡터화하여 나타내면 다음과 같이 나타낼 수 있다.

$$\theta = \theta - \frac{\alpha}{m}X^{T}(X\theta - y) = \theta - \frac{\alpha}{m}(X^{T}X\theta - X^{T}y)$$

이걸 적용해서 코드로 나타내면 다음과 같다.

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
    % ====================== YOUR CODE HERE ======================
    % Instructions: Perform a single gradient step on the parameter vector
    %               theta. 
    %
    % Hint: While debugging, it can be useful to print out the values
    %       of the cost function (computeCost) and gradient here.
    %
    J = (1/m)*(X'*X*theta - X'*y);
    theta = theta - alpha*J;
    % ============================================================
 
    % Save the cost J in every iteration    
    J_history(iter) = computeCost(X, y, theta);
end
end

더욱 간단하게 표현이 되는 것을 볼 수 있다.

 

[computeCostMulti.m]

이제부터 multivariate linear regression을 코드로 구현을 해야한다. 우리는 앞서 일반화된 행렬식으로 이미 모두 표현을 했기 때문에, 앞서 univariate에서 구현했던 코드와 큰 차이가 없다.

function J = computeCostMulti(X, y, theta)
%COMPUTECOSTMULTI Compute cost for linear regression with multiple variables
%   J = COMPUTECOSTMULTI(X, y, theta) computes the cost of using theta as the
%   parameter for linear regression to fit the data points in X and y
 
% Initialize some useful values
m = length(y); % number of training examples
 
% You need to return the following variables correctly 
J = 0;
 
% ====================== YOUR CODE HERE ======================
% Instructions: Compute the cost of a particular choice of theta
%               You should set J to the cost.
J = 1/(2*m)*sum((X*theta - y).^2);
 
 
 
 
% =========================================================================
 
end

위 코드는 앞서 구현했던 costFunction.m 과 완전히 동일하다.

 

[gradientDescentMulti.m]

multivariate linear regression의 Gradient Descent 구현 코드이다. 앞서 gradientDescent.m 에서 일반화하여 표현한 코드를 이미 첨부해두었다. 해당 코드도 gradientDescent.m 과 완전히 동일하다.

function [theta, J_history] = gradientDescentMulti(X, y, theta, alpha, num_iters)
%GRADIENTDESCENTMULTI Performs gradient descent to learn theta
%   theta = GRADIENTDESCENTMULTI(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
 
    % ====================== YOUR CODE HERE ======================
    % Instructions: Perform a single gradient step on the parameter vector
    %               theta. 
    %
    % Hint: While debugging, it can be useful to print out the values
    %       of the cost function (computeCostMulti) and gradient here.
    %
    J_ = (1/m)*(X'*X*theta - X'*y);
    theta = theta - alpha*J_;
    % ============================================================
 
    % Save the cost J in every iteration    
    J_history(iter) = computeCostMulti(X, y, theta);
 
end
end

 

[featureNormalize.m]

normalize features 하는 함수를 작성하는 과제인데, 내가 이해하기로는 아래의 Mean normalization을 진행하라는 것으로 이해를 했다.

- Mean Normalization

Replace \(x_i\) with \(x_i \mu_i\) to make features have approximately zero mean(Do not apply to \(x_0 = 1\))

즉, \(x_i \leftarrow \frac{x_i - \mu_i}{s_i}\)를 적용하고, 이때, 과제에서 \(s_i\)는 std 함수를 사용하여 standard deviations(표준편차)를 구해 나누어 주면 된다.

function [X_norm, mu, sigma] = featureNormalize(X)
%FEATURENORMALIZE Normalizes the features in X 
%   FEATURENORMALIZE(X) returns a normalized version of X where
%   the mean value of each feature is 0 and the standard deviation
%   is 1. This is often a good preprocessing step to do when
%   working with learning algorithms.
 
% You need to set these values correctly
X_norm = X;
mu = zeros(1, size(X, 2));
sigma = zeros(1, size(X, 2));
 
% ====================== YOUR CODE HERE ======================
% Instructions: First, for each feature dimension, compute the mean
%               of the feature and subtract it from the dataset,
%               storing the mean value in mu. Next, compute the 
%               standard deviation of each feature and divide
%               each feature by it's standard deviation, storing
%               the standard deviation in sigma. 
%
%               Note that X is a matrix where each column is a 
%               feature and each row is an example. You need 
%               to perform the normalization separately for 
%               each feature. 
%
% Hint: You might find the 'mean' and 'std' functions useful.
%       
 
mu = mean(X);
sigma = std(X);
X_norm = (X - mu) ./ sigma;
 
 
 
 
% ============================================================
 
end

 

[normalEqn.m]

linear regression에서 Normal Equation에 해당하는 코드를 구현하는 과제이다.

우리는 결국 \(J(\theta)\)가 최소가 되는 \(\theta\)를 구하는 것이 목적이고, 결국 \(\frac{\partial}{\partial\theta_j}J(\theta) = 0\)이 되는 \(\theta)\)를 구하면 된다라는 것으로 Normal Equation의 출발점이었다.

즉, 

$$\frac{\partial}{\partial\theta_j}J(\theta) = \frac{1}{m}X^T(X\theta - y) = 0$$

\(\rightarrow X^T(X\theta - y) = 0\)

\(\rightarrow X^TX\theta - X^Ty = 0\)

\(\rightarrow X^TX\theta = X^Ty\)

\(\rightarrow (X^TX)^-1(X^TX)\theta = (X^TX)^-1X^Ty\)

$$\rightarrow \theta = (X^TX)^-1X^Ty$$

결국 위 식을 풀어서 \(\theta\)를 갱신하면 된다.

코드는 아래와 같다.

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);
 
% ====================== YOUR CODE HERE ======================
% Instructions: Complete the code to compute the closed form solution
%               to linear regression and put the result in theta.
%
 
% ---------------------- Sample Solution ----------------------
theta = pinv(X'*X)*X'*y;
 
 
 
% -------------------------------------------------------------
 
 
% ============================================================
end

여기서 pinv는 역행렬을 구해주는 octave 내장함수이며, 모든 행렬의 역행렬을 구해준다.