Thuật toán linear regression giải quyết các bài toán có đầu ra là giá trị thực, ví dụ: dự đoán giá nhà, dự đoán giá cổ phiếu, dự đoán tuổi,…

Bài toán

Bạn làm ở công ty bất động sản, bạn có dữ liệu về diện tích và giá nhà, giờ có một ngôi nhà mới bạn muốn ước tính xem giá ngôi nhà đó khoảng bao nhiêu. Trên thực tế giá nhà thì phụ thuộc rất nhiều yếu tố: diện tích, số phòng, gần trung tâm thương mại,.. nhưng để cho bài toán đơn giản giả, sử giá nhà chỉ phụ thuộc vào diện tích căn nhà. Bạn có dữ liệu về diện tích và giá bán của 30 căn nhà như sau:

Diện tích(m2)	Giá bán (triệu VNĐ)
30	448.524
32.4138	509.248
34.8276	535.104
37.2414	551.432
39.6552	623.418
…	…

Nếu giờ yêu cầu bạn ước lượng nhà 50 mét vuông khoảng bao nhiêu tiền thì bạn sẽ làm thế nào? Vẽ một đường thẳng gần với các điểm trên nhất và tính giá nhà ở điểm 50.

Về mặt lập trình cũng cần làm 2 việc như vậy:

• Training: tìm đường thẳng (model) gần các điểm trên nhất. Mọi người có thể vẽ ngay được đường thẳng mô tả dữ liệu từ hình 1, nhưng máy tính thì không, nó phải đi tìm bằng thuật toán Gradient descent ở phía dưới. (Từ model và đường thẳng có thể bị sử dụng thay thế lẫn nhau trong phần còn lại của bài viết).
• Inference: dự đoán xem giá của ngôi nhà 50 m^2 có giá bao nhiêu dựa trên đường tìm được ở phần trên.

Thiết lập công thức

Model

Phương trình đường thẳng có dạng y = ax + b.

Thay vì dùng kí hiệu a, b cho phương trình đường thẳng; để tiện cho biểu diễn ma trận phần sau ta sẽ thay w_1 = a, w_0 = b

Nên phương trình được viết lại thành: y = w_1 * x + w_0 => Việc tìm đường thẳng giờ thành tìm w_0, w_1 .

Để tiện cho việc thiết lập công thức, ta sẽ đặt ký hiệu cho dữ liệu ở bảng dữ liệu: (x_1, y_1) = (30, 448.524), (x_2, y_2) = (32.4138, 509.248),..

Tức là nhà diện tích x_i thực sự có giá y_i . Còn giá trị mà model hiện tại đang dự đoán kí hiệu là \hat{y_i}=w_{1} * x _i+ w_{0}

Loss function

Việc tìm w_0, w_1 có thể đơn giản nếu làm bằng mắt nhưng máy tính không biết điều đấy, nên ban đầu giá trị được chọn ngẫu nhiên ví dụ w_0 = 0, w_1 = 1 sau đấy được chỉnh dần.

Rõ ràng có thể thấy đường y = x không hề gần các điểm hay không phải là đường mà ta cần tìm. Ví dụ tại điểm x = 42 (nhà 42 m^2 ) giá thật là 625 triệu nhưng giá mà model dự đoán chỉ là 42 triệu.

Nên giờ cần 1 hàm để đánh giá là đường thẳng với bộ tham số (w_0, w_1) = (0, 1) có tốt hay không. Với mỗi điểm dữ liệu (x_i, y_i) độ chênh lệch giữa giá thật và giá dự đoán được tính bằng: \displaystyle \frac{1}{2} * (\hat{y_i} - y_i)^2. Và độ chênh lệch trên toàn bộ dữ liệu tính bằng tổng chênh lệch của từng điểm:

\displaystyle J = \frac{1}{2} * \frac{1}{N} * (\sum_{i=1}^{N} (\hat{y_i} - y_i)^2) (N là số điểm dữ liệu). Nhận xét:

• J không âm
• J càng nhỏ thì đường thẳng càng gần điểm dữ liệu. Nếu J = 0 thì đường thẳng đi qua tất các điểm dữ liệu.

=> Bài toán tìm đường thẳng gần các điểm dữ liệu nhất trở thành tìm
w_0, w_1 sao cho hàm J nhỏ nhất. Nhưng vì tìm giá trị nhỏ nhất của J cũng giống tìm giá trị nhỏ nhất của k*J (k là số thực, dương) nên ta sẽ đi tìm giá trị nhỏ nhất của

\displaystyle J = \frac{1}{2} *(\sum_{i=1}^{N} (\hat{y_i} - y_i)^2)

Tóm tắt: đầu tiên từ việc tìm đường thẳng (model) -> tìm w_0, w_1 để hàm J nhỏ nhất. Giờ cần một thuật toán để tìm giá trị nhỏ nhất của hàm J. Đó chính là gradient descent.

Gradient descent

Đạo hàm là gì

Mình tin có nhiều người có thể tính được đạo hàm của hàm f(x) = x^2 hay f(x) = sin(cos(x)) nhưng vẫn không biết thực sự đạo hàm là gì.

Theo tiếng hán đạo là con đường, hàm là hàm số nên đạo hàm chỉ sự biến đổi của hàm số hay có tên thân thương hơn là độ dốc của đồ thị.

Như mọi người đã học đạo hàm f(x) = x^2 là \displaystyle f'(x) = \frac {df(x)}{dx} = 2*x (hoàn toàn có thể chứng minh từ định nghĩa nhưng cấp 3 mọi người đã học quá nhiều về công thức nên mình không đề cập lại). Nhận xét:

• f'(1) = 2 * 1 < f'(2) = 2 * 2 nên mọi người có thể thấy trên hình là đồ thị gần điểm x = 2 dốc hơn đồ thị gần điểm x = 1 => trị tuyệt đối của đạo hàm tại một điểm càng lớn thì gần điểm đấy càng dốc.
• f'(-1) = 2 * (-1) = -2 < 0 => đồ thị đang giảm hay khi tăng x thì y sẽ giảm; ngược lại đạo hàm tại điểm nào đó mà dương thì đồ thị quanh điểm đấy đang tăng.

Gradient descent

Gradient descent là thuật toán tìm giá trị nhỏ nhất của hàm số f(x) dựa trên đạo hàm. Thuật toán:

Bước 1: Khởi tạo giá trị x = x_0 tùy ý

Bước 2: Gán x = x – learning_rate * f'(x)( learning_rate là hằng số không âm ví dụ learning_rate = 0.001)

Bước 3: Tính lại f(x):

• Nếu f(x) đủ nhỏ thì dừng lại.
• Ngược lại tiếp tục bước 2

Nôm na là lặp lại bước 2 một số lần đủ lớn (100 hoặc 1000 lần tùy vào bài toán và hệ số learning_rate) cho đến khi f(x) đạt giá trị đủ nhỏ.

Ví dụ cần tìm giá trị nhỏ nhất hàm y = x^2 , dĩ nhiên là hàm này ai cũng biết là giá giá trị nhỏ nhất là 0 tại x = 0 nhưng để cho mọi người dễ hình dung hơn về thuật toán Gradient descent nên mình lấy ví dụ đơn giản.

Bước 1: Khởi tạo giá trị ngẫu nhiên x = -2 (điểm A).

Bước 2: Do ở A đồ thị giảm nên f'(x=-2) = 2*(-2) = -4 < 0 => Khi gán x = x – learning_rate * f'(x) nên x tăng nên đồ thị bước tiếp theo ở điểm C. Tiếp tục thực hiện bước 2, gán x = x – learning_rate * f'(x) thì đồ thị ở điểm D,… => hàm số giảm dần dần tiến tới giá trị nhỏ nhất.

Moị người có để ý là trị tuyệt đối đàm tại A lớn hơn tại C và tại C lớn hơn tại D không. Đến khi đến gần điểm đạt giá trị nhỏ nhất x = 0, thì đạo hàm xấp xỉ 0 đến khi hàm đạt giá trị nhỏ nhất tại x = 0, thì đạo hàm bằng 0, nên tại điểm gần giá trị nhỏ nhất thì bước 2 gán x = x – learning_rate * f'(x) là không đáng kể và gần như là giữ nguyên giá trị của x.

Tương tự nếu giá trị khởi tạo tại x = 2 (tại B) thì đạo hàm tại B dương nên do x = x – learning_rate * f'(x) giảm -> đồ thị ở điểm E -> rồi tiếp tục gán x=x -learning_rate * f'(x) thì hàm f(x) cũng sẽ giảm dần dần đến giá trị nhỏ nhất.

Nhận xét:

• Thuật toán hoạt động rất tốt trong trường hợp không thể tìm giá trị nhỏ nhất bằng đại số tuyến tính.
• Việc quan trọng nhất của thuật toán là tính đạo hàm của hàm số theo từng biến sau đó lặp lại bước 2.

Việc chọn hệ số learning_rate cực kì quan trọng, có 3 trường hợp:

• Nếu learning_rate nhỏ: mỗi lần hàm số giảm rất ít nên cần rất nhiều lần thực hiện bước 2 để hàm số đạt giá trị nhỏ nhất
• Nếu learning_rate hợp lý: sau một số lần lặp bước 2 vừa phải thì hàm sẽ đạt giá trị đủ nhỏ.
• Nếu learning_rate quá lớn: sẽ gây hiện tượng overshoot và không bao giờ đạt được giá trị nhỏ nhất của hàm.

Cách tốt nhất để kiểm tra learning_rate hợp lý hay không là kiểm tra giá trị hàm f(x) sau mỗi lần thực hiện bước 2 bằng cách vẽ đồ thị

Áp dụng vào bài toán

Ta cần tìm giá trị nhỏ nhất của hàm

\displaystyle J(w_{0}, w_{1}) = \frac{1}{2} * (\sum_{i=1}^{N} (\hat{y_i} - y_i)^2) = \frac{1}{2} * (\sum_{i=1}^{N} (w_0 + w_1 * x_i - y_i)^2) \newline

Việc tìm giá trị lớn nhất hàm này hoàn toàn có thể giải được bằng đại số nhưng để giới thiệu thuật toán Gradient descent cho bài Neural network nên mình sẽ áp dụng Gradient descent luôn.

Việc quan trọng nhất của thuật toán gradient descent là tính đạo hàm của hàm số nên giờ ta sẽ đi tính đạo hàm theo từng biến.

Nhắc lại kiến thức h'(x) = f(g(x))’ = f'(g)*g'(x). Ví dụ:

h(x) = (3x+1)^2 thì f(x) = x^2, g(x) = 3x+1 => h'(x) = f'(g) * g'(x) = f'(3x+1) * g'(x) = 2 * (3x+1) * 3 = 6 * ( 3x+1).

Tại 1 điểm (x_{i}, y_{i}) gọi

\displaystyle f(w_{0}, w_{1}) = \frac{1}{2} * (w_{0} + w_{1} * x_i - y_i)^2 \\ \\

Ta có:

\displaystyle \frac{df}{dw_0} = w_{0}+w_{1} * x_i - y_i \\ \\ \displaystyle \frac{df}{dw_1} = x_i * (w_{0}+w_{1} * x_i - y_i)\\

Do đó

\displaystyle \frac{dJ}{dw_0} = \sum_{i=1}^{N} (w_{0} + w_{1} * x_i - y_i) \newline \newline \displaystyle \frac{dJ}{dw_1} = \sum_{i=1}^{N} x_i * (w_{0} + w_{1} * x_i - y_i) \\ \\

Ma trận

Ma trận là gì

Ma trận là một mảng chữ nhật có m hàng và n cột, ta gọi là ma trận m * n (số hàng nhân số cột).

Ví dụ về ma trận 3 * 4

Chỉ số ma trận thì hàng trước cột sau ví dụ A[1, 2] = -5 (hàng 1, cột 2); A[3, 1] = 4 (hàng 3, cột 1)

Phép nhân ma trận

Phép tính nhân ma trận A * B chỉ thực hiện được khi số cột của A bằng số hàng của B, hay A có kích thước m*n và B có kích thước n*k.

Ma trận C = A * B thì C có kích thước m * k và
C[i,j] = \sum_{k=1}^{n} A[i,k]*B[k,j]

C[1][1] = A[1][1] * B[1][1] + A[1][2] * B[2][1] = ax + cy

C[2][1] = A[2][1] * B[1][1] + A[2][2] * B[2][1] = bx + dy

Element-wise multiplication matrix

Ma trận A và B cùng kích thước m*n thì phép tính này cho ra ma trận C cùng kích thước m*n và C[i,j] = A[i,j] * B[i,j]. Hay là mỗi phần tử ở ma trận C bằng tích 2 phần tử tương ứng ở A và B.

Kí hiệu C = A \otimes B, ví dụ:

Biểu diễn bài toán

Do với môi điểm x_i, y_i ta cần phải tính (w_{0} + w_{1} * x_i - y_i) nên thay vì tính cho từng điểm dữ liệu một ta sẽ biểu diễn dưới dạng ma trận, X kích thước n * 2, Y kích thước n * 1 (n là số điểm dữ liệu trong tập dữ liệu mà ta có).

X[:, i] hiểu là ma trận kích thước n*1 lấy dữ liệu từ cột thứ i của ma trận X, nhưng do trong python chỉ số bắt đầu từ 0, nên cột đầu tiên là cột 0, cột thứ hai là cột 1, …. Phép tính sum(X) là tính tổng tất cả các phần tử trong ma trận X.

Mở rộng

Mọi người mới có thể bỏ qua phần này

Hàm bậc hai

Giả sử bài toán vẫn như trên nhưng khi bạn vẽ đồ thị dữ liệu sẽ như thế này

Bạn có thể đoán được model có thể là hàm bậc hai giờ bạn sẽ thiết lập công thức khác đi

Gaussian Process (GP)

Tiếp nếu bạn vẽ đồ thị dữ liệu lên và bạn không thể đoán được model là hàm gì thì sao? Câu trả lời là hãy dùng Gaussian Process. Mô hình ở trên bạn để ý thì mình có những tham số cần đi tìm w_0, w_1, w_2 nhưng ở GP thì không hề có tham số nào cả (hoặc có thể coi là vô số tham số). Bài viết này giới thiệu về GP khá hay mọi người có thể đọc thêm.

Python code

Dữ liệu và code các bạn có thể lấy ở đây

# -*- coding: utf-8 -*-
"""
Created on Mon Feb 18 22:06:34 2019

@author: DELL
"""

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
#numOfPoint = 30
#noise = np.random.normal(0,1,numOfPoint).reshape(-1,1)
#x = np.linspace(30, 100, numOfPoint).reshape(-1,1)
#N = x.shape[0]
#y = 15*x + 8 + 20*noise
#plt.scatter(x, y)

data = pd.read_csv('data_linear.csv').values
N = data.shape[0]
x = data[:, 0].reshape(-1, 1)
y = data[:, 1].reshape(-1, 1)
plt.scatter(x, y)
plt.xlabel('mét vuông')
plt.ylabel('giá')

x = np.hstack((np.ones((N, 1)), x))

w = np.array([0.,1.]).reshape(-1,1)

numOfIteration = 100
cost = np.zeros((numOfIteration,1))
learning_rate = 0.000001
for i in range(1, numOfIteration):
    r = np.dot(x, w) - y
    cost[i] = 0.5*np.sum(r*r)
    w[0] -= learning_rate*np.sum(r)
    # correct the shape dimension
    w[1] -= learning_rate*np.sum(np.multiply(r, x[:,1].reshape(-1,1)))
    print(cost[i])
predict = np.dot(x, w)
plt.plot((x[0][1], x[N-1][1]),(predict[0], predict[N-1]), 'r')
plt.show()

x1 = 50
y1 = w[0] + w[1] * 50
print('Giá nhà cho 50m^2 là : ', y1)

Vậy là kết thúc bài đầu tiên, mình biết có thể rất lâu rồi mọi người chưa động đến toán, có thể là lần đầu tiên lập trình. Không có điều gì đạt được quá dễ dàng cả, chỉ cần các bạn qua được cửa ải bài 1 thì những bài sau sẽ nhẹ nhàng hơn.

Mọi người không hiểu chỗ nào hay có đóng góp gì cứ bình luận ở phía dưới mình sẽ giải đáp. Cảm ơn mọi người rất nhiều !!!

Tags: Deep learningGradient descentLinear RegressionMachine learning