Machine Learning – 2.3 – Exercise

Bài viết này đưa ra bài giải và chi tiết cách giải của mỗi bài tập trong tuần 2 của khóa học Machine Learning của giáo sư Andrew Ng.

Xem các bài viết khác tại Machine Learning Course Structure.

1. Cài đặt Octave

Còn gì dễ hơn: Download Octave

Chọn phiên bản 64-bit nha: octave-4.4.1-w64-installer.exe (~ 238 MB)

2. Warmup

Yêu cầu: Trả về 5×5 identity matrix

A = eye(5);

3. Cost Function J

Công thức:

J(\theta) = \frac{1}{2m}\sum\limits_{i=1}^m(h_0(x^{(i)})-y^{(i)})^2

Vectorize:

Ta có:

h_0(x^{(i)}) =\theta_0X_0 + \theta_1X_1+...+\theta_nX_n

Nếu coi \theta là vector n\times1, X là matrix m\times n, thì phép tính trên còn đơn giản như sau:

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

Vậy cost function biến đổi lại thành:

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

Thuật toán Gradient Descent có 2 bước:

  1. Tính bộ giá trị \theta
  2. Thay vào cost function để kiểm tra hội tụ

Để cho đơn giản, ta sẽ giả định rằng chỉ có 2 feature là x_0 = 1x_1 (n = 2)

Công thức:

\theta_j = \theta_j - \alpha \frac{1}{m} \sum\limits_{i=1}^{m} (h_\theta(x^{(i)}) - y^{(i)}) \cdot x_j^{(i)}

Ta tách công thức trên thành 2 phần:

\theta_j = \theta_j - gradient

với

gradient = \alpha \frac{1}{m} \sum\limits_{i=1}^{m} (h_\theta(x^{(i)}) - y^{(i)}) \cdot x_j^{(i)}

với:

  • X = \begin{bmatrix}x_0^{(1)} & x_1^{(1)} \\x_0^{(2)} & x_1^{(2)} \\ ... & ... \\ x_0^{(m)} & x_1^{(m)} \end{bmatrix}
  • \theta = \begin{bmatrix}\theta_0 \\ \theta_1 \end{bmatrix}
  • y = \begin{bmatrix}y_1 \\ y_2 \\ ... \\ y_m \end{bmatrix}

Tương tự như cost function, ta có:

(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

với a là vector m x 1

Nhân với x_j^{(i)} và tính tổng

Đối với mỗi tham số của vector a, ta nhân nó với x tương ứng, rồi cộng tất cả các kết quả lại.

Để vừa nhân, vừa tính tổng và trả về một vector chứa kết quả là các giá trị của gradient, ta sẽ phải biến đổi matrix X một chút.

X^T = \begin{bmatrix}x_0^{(1)} & x_0^{(2)} & ... &  x_0^{(m)}\\ x_1^{(1)} & x_1^{(2)} & ... & x_1^{(m)}\end{bmatrix}

Khi nhân matrix này với vector a, ta sẽ có kết quả như mong muốn.

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
end

Code này có thể dùng chung cho gradient descent với nhiều feature

5. Normal Equation

Cái này thì khá dễ, nên mình không giải thích mà sẽ đưa code luôn nhé

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;
end

Bắt đầu tuần 3 nào 😀

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.