Linear regression - Một thuật toán cơ bản trong Machine Learning

#1

Hôm nay rảnh rỗi mình viết bài chia sẻ về thuật toán Graient Descent (GD). Những ai đã làm quen với AI chắc cũng đã nghe qua, mình sẽ cố gắng trình bày 1 cách dễ hiểu nhất cho những bạn mới bắt đầu.

Gradient Descent là gì?

GD là một thuật toán rất cơ bản và cực kỳ quan trọng trong lĩnh vực học máy. Nó xoay quanh việc tìm cực tiểu gần đúng của một hàm số bất kỳ cho trước. Gradient Descent dịch nôm na là trượt/xuống dốc, chúng ta sẽ tìm giá trị cực tiểu bằng cách lần mò từng step 1 để bước xuống dốc cho tới khi nào chạm điểm cực tiểu.

Vậy tại sao lại phải phức tạp như vậy. Ở phổ thông chúng ta đã biết để tìm được 1 điểm cực trị của hàm số, chúng ta chỉ cần giải phương trình đạo hàm của hàm số đó tại điểm giá trị đạo hàm bằng không. Câu trả lời là không phải hàm số nào cũng có thể giải phương trình đạo hàm bằng 0 một cách dễ dàng (nhiều lúc là không thể)

Bài toán

Giả sử bạn cần dự báo độ ẩm của 1 vùng dựa trên nhiệt độ của vùng đó. Dựa vào kết quả đo đạc ở quá khứ, xếp của bạn cung cấp 1 dữ liệu đầu vào - training dataset cho bạn như sau ( Dữ liệu có thể không chính xác trong thực tế ):

Temperature Humidity
1 2.2
2 3.9
3 5.8
4 8
5 10
6 12.2

Để dễ hình dung, dữ liệu được biểu thị trên hệ tọa độ descartes như sau:

image

Phần chấm màu đỏ là dữ liệu đầu vào (training datasets). Dựa vào dữ liệu đầu vào dễ dàng nhận thấy giá trị của humidity phụ thuộc tuyến tính vào temperature, hay nói cách khác, chúng ta có thể biểu thị dưới dạng toán học như sau :

$$h(x) = a_{1} + a_{2}x$$

Trong đó, x là temperature, h(x) là kết quả dự đoán humidity dựa vào temperature, hàm số h(x) được gọi là hàm Hypothesis . Như vậy, để giải quyết bài toán này thực chất là chúng ta đi tìm giá trị $a_{1}$ và $a_{2}$ sao cho đường thẳng $h(x) = a_{1}x + a_{2}$ đi qua các điểm màu đỏ “gần nhất” ( như hình màu xanh ở trên hình), tức là đúng với training dataset nhất. Gần nhất ở đây có nghĩa là có thể không tồn tại giá trị $a_{1}$ và $a_{2}$ để đường thẳng h(x) đi qua tất cả các điểm. Trong ML nói chung thì chúng ta không chắc chắn giải quyết được bài toán 1 cách chính xác về mặt toán học. Luôn luôn có sai số xảy ra, nhưng chúng ta hy vọng sẽ giải được bài toán với sai số nhỏ nhất ( chấp nhận được ).

Linear regression && Gradient Descent

Error function

Quay lại xét phương thức biểu thị sự phụ thuộc của độ ẩm vào nhiệt độ như sau (hàm Hypothesis )

$$h(x) = a_{1} + a_{2}x$$

Trong đó x là nhiệt độ, h(x) là giá trị độ ẩm được tiên đoán bởi nhiệt độ. Gọi $x_{i}$ là phần tử thứ i của tập dữ liệu nhiệt độ đầu vào, $y_{i}$ là phần tử thứ i của tập dữ liệu độ ẩm đầu vào. Như vậy với cá dữ liệu nhiệt độ đầu vào $x_{i}$ như ở trên, chúng ta sẽ tiên đoán được các giá trị độ ẩm $y_{i}$ tương ứng. Ta viết lại phương trình như sau :

$$h(x_{i}) = a_{1} + a_{2}x_{i}$$

So sánh giá trị $h(x_{i})$ là giá trị được tiên đoán, với$y_{i}$ là giá trị thực tế thu nhận được, ta có sai số như sau

$$error = h(x_{i}) - y_{i}$$

là sai số tại phần tử thứ i. Để tính sai số trên toàn tập dự liệu một cách hiệu quả, người ta đưa ra khái niệm Mean squared error như sau:

$$mse = \frac{1}{2m}\sum_{i=0}^m (h(x_{i}) - y_{i})^2$$

Trong đó m là số phần tử - row của training dataset. Giải thích 1 chút về function trên. $h(x_{i}) - y_{i}$ biểu thị cho sai số tại phần tử thứ i, vì giá trị này có thể là số âm, nên người ta sẽ bình phương nó lên (squared), sau đó thì tính tổng các sai số và chia cho m (mean) để lấy giá trị sai số trung bình trên toàn tập dữ liệu. Cuối cùng chia nó cho 2, lý do chia cho 2 là để thuận tiện tính toán thuần túy về mặt toán học, mình sẽ giải thích sau.

Bài toán thu về việc tìm giá trị $a_{1}$ và $a_{2}$ sao cho hàm mse có giá trị nhỏ nhất (vì hàm lỗi càng nhỏ thì mô hình dự đoán của mình càng chính xác). Và thuật toán gradient descent sẽ giúp chúng ta làm điều này.

3.2 Gradient Descent

Như chúng ta đã biết, đạo hàm của 1 hàm số cho biết sự biến thiên tức thời của hàm số đó tại 1 điểm nhất định. Mình sẽ không giải thích quá nhiều về lý thuyết đạo hạm ở đây ( các bạn có thể tra google để tìm hiểu thêm ), mà hãy xét 1 ví dụ sau. Giả sử cho hàm số :

$$y(x) = 3x^2 + 2x - 3$$

Xem hình dưới.

image

Đạo hàm của hàm số này là

$$d(x) = 6x + 2$$

Như vậy, tại điểm x = 1, hàm y(x) có độ biến thiên tức thời là $\Delta = 8$,tại điểm x = -1, hàm y(x) có độ biến thiên tức thời là $\Delta = -4$

Nhìn vào đồ thị trên, chúng ta dễ dàng nhận thấy, tại điểm có x = 1, để tiến tới được giá trị minimum (tại điểm x = 0.333), x cần phải xịch sang trái, nghĩa là cộng x với 1 đại lượng âm, còn tại điểm có x = -1, để tiến tới được giá trị minimum, x cần phải xịch sang phải, nghĩa là cộng x với 1 đại lượng dương. Hay nói các khác, kết hợp với ví dụ tính đạo hàm ở trên, để tiến tới điểm minimum của hàm số y(x), thì x cần phải cộng với 1 đại lượng trái dấu với với đạo hàm của hàm số tại điểm đó.

$$ x = x - \alpha d(x) $$

Trong đó $\alpha$ là 1 hằng số được gọi là learning rate. ( Có những bài toán thực tế phức tạp, learning rate thay đổi theo thời gian, nhưng chúng ta không xét ở đây ).

Tư tưởng của thuật toán gradient descent là xuất phát từ 1 điểm tùy ý (x tùy ý), xê dịch từng bước nhỏ -baby step, ngược dấu với đạo hàm để mong sẽ tới gần được điểm minimum nhất ( có thể sẽ không bao giờ chạm vào được điểm minimum tùy vào giá trị learning rate được chọn, luôn luôn có sai số). Tại mỗi bước đi, thực hiện đánh giá lại error ( bằng mse ), nếu error < 1 giá trị nào đấy (bias), tức là chấp nhận được, thì sẽ kết thúc và xem vị trí đó là điểm minimum cần tìm. Hoặc bạn cũng có thể set cứng sau n bước đi thì sẽ dừng lại

Xét lại hàm số ở trên:

$$y(x) = 3x^2 + 2x - 3$$

Đạo hàm của hàm số này là

$$d(x) = 6x + 2$$

Mình sẽ viết 1 chương trình nhỏ (python) để minh họa thuật toán này. Giả sử điểm xuất phát của mình là x = 1. ( Bạn có thể chọn bất cứ giá trị nào nếu muốn )

# định nghĩa y(x)
def y(x):
    return 3 * x * x + 2 * x - 3
# định nghĩa d(x)
def dx(x):
    return 6 * x + 2

# 1000 bước đi
n = 10000

start_x = 1
learning_rate = 0.01
for i in range(1,n):
    start_x -= learning_rate * dx(start_x)

print(start_x)

Kết quả cho giá trị tại x = -0.33333333333333287 thì hàm số y sẽ có giá trị gần với cực tiểu nhất. Về mặt toán học, bằng cách giải đạo hàm d(x) = 0, chúng ta tìm được giá trị cực tiểu của y(x) tại điểm có x = 1 /3. Như vậy kết quả giải bằng thuật toán Gradient Descent vẫn có 1 sai số nhỏ nhất định.

Giải quyết bài toán

4.1 Phân tích toán học

Quay lại bài toán ở trên, bạn cần dự báo độ ẩm của 1 vùng dựa trên nhiệt độ của vùng đó. Chúng ta có hàm số biểu diễn sự phụ thuộc của độ ẩm vào nhiệt độ như sau (hàm Hypothesis ):

$$y = a_{1} + a_{2}x$$

Hàm lỗi như sau

$$mse = \frac{1}{2m}\sum_{i=0}^m (h(x_{i}) - y_{i})^2$$

Đây là 1 hàm số 2 biến số $a_{1}$ và $a_{2}$, do đó chúng ta cần tính đạo hàm riêng phần. Chú ý quan trọng là hàm mse ở đây biến số không phải là x, mà là a1 và a2 , đồ y ở đây mô tả biến thiên giá trị lỗi của mô hình dự đoán trên tập dữ liệu training x (xem như hằng số) theo a1 và a2 (xem như biến số) - chúng ta đang cần tìm minimum của hàm error dựa trên các giá trị a1,a2. Hàm mse được viết cụ thể như sau

$$\begin{align}mse = \frac{1}{2m}\sum_{i=0}^m (h(x_{i}) - y_{i})^2) \ = \frac{1}{2m}\sum_{i=0}^m (a_{1}x_{i} + a_{2} - y_{i})^2) \ = \frac{1}{2m}\sum_{i=0}^m (a_{1}^2 + 2a_{1}a_{2}x_{i} + a_{2}^2x_{i}^2 - 2a_{1}y_{i} - 2a_{2}x_{i}y_{i} + y_{i}^2)\ \end{align} $$

Đạo hàm của mse theo $a_{1}$ :

$$\begin{align}d(a_{1}) = \frac{1}{2m}\sum_{i=0}^m (2a_{1} + 2a_{2}x_{i} - 2y_{i})\ = \frac{1}{m}\sum_{i=0}^m (a_{1} + a_{2}x_{i} - y_{i})\ = \frac{1}{m}\sum_{i=0}^m (f(x_{i}) - y_{i}) \end{align} $$

Tương tự, Đạo hàm của mse theo $a_{2}$ :

$$\begin{align}d(a_{2}) = \frac{1}{2m}\sum_{i=0}^m (2a_{1}x_{i} + 2a_{2}x_{i}^2 - 2x_{i}y_{i})\ = \frac{1}{m}\sum_{i=0}^m (a_{1}x_{i} + a_{2}x_{i}^2 - x_{i}y_{i})\ = \frac{1}{m}\sum_{i=0}^m (a_{1} + a_{2}x_{i} - y_{i})x_{i}\ = \frac{1}{m}\sum_{i=0}^m (f(x_{i}) - y_{i})x_{i} \end{align} $$

Khi tính đạo hàm, 1/2 sẽ bị triệt tiêu đi, chỉ còn lại 1/m.

Áp dụng thuật toán gradient descent, thực hiện lặp cho tới khi mse < 1 giá trị bias cho trước, tại mỗi vòng lặp, update lại giá trị $a_{1}$ và $a_{2}$ và tính lại mse như sau :$$ a_{1} = a_{1} - learningrate * d(a_{1})\ a_{2} = a_{2} - learningrate * d(a_{2})\ mse = \frac{1}{2m}\sum_{i=0}^m (h(x_{i}) - y_{i})^2 $$

Coding

1. Input training dataset

train_data = np.array(
[
    [1,2.2],
    [2,3.9],
    [3,5.8],
    [4,8],
    [5,10],
    [6,12.2]
])

# plot value
plt.plot(train_data[:,0], train_data[:,1], 'ro')

plt.axis([0, 15, 0, 15])
plt.xlabel('Temperature')
plt.ylabel('Humidity')
plt.show()

image

2. Khởi tạo giá trị bất kì cho a1, a2

a1 = random.randint(0,10)
a2 = random.randint(0,10)

3. Định nghĩa hàm Hypothesis

def h(x):
    return a1 + a2 * x

4. Định nghĩa hàm mean square error

$$mse = \frac{1}{2m}\sum_{i=0}^m (h(x_{i}) - y_{i})^2$$

def mean_square_error():
    error = 0
    for d in train_data:
        tmp = h(d[0]) - d[1]
        error += tmp * tmp
    return 1 / 2 / train_data.shape[0]  * error

5. Định nghĩa đạo hàm riêng phần cho biến a1

$$\begin{align}d(a_{1}) = \frac{1}{2m}\sum_{i=0}^m (2a_{1} + 2a_{2}x_{i} - 2y_{i})\ = \frac{1}{m}\sum_{i=0}^m (a_{1} + a_{2}x_{i} - y_{i})\ = \frac{1}{m}\sum_{i=0}^m (f(x_{i}) - y_{i}) \end{align} $$

def derivative_a1():
    sum = 0
    for d in train_data:
        sum += h(d[0]) - d[1]
    return 1 / train_data.shape[0] * sum

6. Định nghĩa đạo hàm riêng phần cho biến a2

$$\begin{align}d(a_{2}) = \frac{1}{2m}\sum_{i=0}^m (2a_{1}x_{i} + 2a_{2}x_{i}^2 - 2x_{i}y_{i})\ = \frac{1}{m}\sum_{i=0}^m (a_{1}x_{i} + a_{2}x_{i}^2 - x_{i}y_{i})\ = \frac{1}{m}\sum_{i=0}^m (a_{1} + a_{2}x_{i} - y_{i})x_{i}\ = \frac{1}{m}\sum_{i=0}^m (f(x_{i}) - y_{i})x_{i} \end{align} $$

def derivative_a2():
    sum = 0
    for d in train_data:
        sum += (h(d[0]) - d[1]) * d[0]
    return 1 / train_data.shape[0] * sum

7. Thực hiện training

#train
error = 5
learning_rate = 0.1
for i in range(100000): # lặp cho tới khi lỗi < 0.1
    tmp1 = a1 - learning_rate * derivative_a1()
    tmp2 = a2 - learning_rate * derivative_a2()
    a1 = tmp1
    a2 = tmp2
    error = mean_square_error()
print(a1,a2)

-0.03333333333333033 2.0142857142857133

Kết quả thu được a1 = -0.03333333333333033 gần = 0, a2 = 2.0142857142857133 gần =2, tức là giá trị độ ẩm gần bằng gấp đôi nhiệt độ. Nhìn vào dữ liệu training chúng ta cũng có thể thấy điều đó. Như vậy model dự đoán của chúng ta khá chính xác. Thể hiện kết quả dự đoán trên biểu đồ

#plot train data
plt.plot(train_data[:,0], train_data[:,1], 'ro')

# plot result
x_test = np.arange(0,10)
y_test = h(x_test)
plt.plot(x_test,y_test)

plt.axis([0, 15, 0, 15])
plt.xlabel('X axis')
plt.ylabel('Y axis')
plt.show()

image

Chú ý :

  1. Sau khi có các giá trị a1,a2 chúng ta sẽ có thể dự đoán được giá trị độ ẩm bằng nhiệt độ trong tương lai.
  2. Chúng ta dự đoán là giá trị độ ẩm sẽ gấp đôi nhiệt độ ( về mặt công thức ) nhưng train data lại cho thấy không chính xác về mặt toán học => luôn luôn có nhiễu trong input data.
  3. Giá trị learning rate ở trên nhằm để hạn chế chúng ta chỉ dịch chuyển những bước nhỏ. Nếu giá trị này lớn quá có thể xảy ra tình trạng “nhảy” qua điểm minimum, còn nếu nhỏ quá thì có thể nó sẽ rơi vào điểm local minimum ( đối với hàm số có nhiều điểm cực trị, nhưng cái mà ta tìm thấy không phải là cực trị bé nhất ). Việc lựa chọn learning rate mang nặng tính kinh nghiệm hơn là có công thức.
  4. Không có khái niệm chính xác tuyệt đối trong các bài toán ML, chúng ta chỉ có khái niệm sai số chấp nhận được trong các bài toán thực tế.
  5. Càng nhiều biến số, nhiều dữ liệu, thì thuật toán GD ngày càng phực tạp hơn, việc train có thể mất vài giờ, vài ngày, vài tháng (LOL).
  6. GD không chỉ xuất hiện ở bài toán Linear Regression mà còn ở Classification / Neural network.
  7. Hàm Hypothesis ở trên là quá đơn giản (cho các bạn dễ hiểu), trong thực tế thì phức tạp hơn rất nhiều (tất nhiên). Minh hoa 1 bài toán Linear Regresstion với h(x) là phương trình bậc 2 : https://lehoai.github.io/linear_regression.html
11 Likes
IT - Tuần này có gì mới #3 - 11/10/2019
#2

Học ML nhiều chỗ phải quay lại học toán trước rồi mới hiểu ML. Bác có link về support vector machine ko?

#3

Mình cũng chỉ ·xem trên youtube thôi bạn à.

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?