Nguyễn Việt Hưng, cựu sinh viên K53

Nếu biết một giảng viên Python bán chuối, bán 10 quả anh có 30 nghìn VNĐ, bán 3 quả anh có 9 nghìn, bán 5 quả anh có 15 nghìn. Hỏi bán 9 quả anh có bao nhiêu tiền? Để giải bài này, ta sẽ dùng 1 thuật toán trong machine learning có tên Linear Regression.

CHÚ Ý

Nếu bạn không biết tiếng Anh, bài viết này cung cấp đủ dùng cho bạn.
Bạn chỉ cần biết toán cấp 2, không cần biết toán cấp 3 hay đại học để hiểu bài này. Bạn nên biết Python để code và xem kết quả (nhưng cũng có thể bỏ qua nếu chỉ cần hiểu tư tưởng).

Linear regression là gì?

(trong một số sách Tiếng Việt gọi là “hồi quy tuyến tính”).
Linear regression là một phương pháp (thuật toán) thuộc loại đơn giản nhất trong machine learning (từ đây viết là ML), với mục đích TÌM (vẽ) ra một đường thẳng, sao cho nó đi qua hoặc đi gần nhất với các điểm cho trước. Từ một tập dữ liệu cho trước, khi ta vẽ được một đường thẳng như vậy, ta có thể đoán xem các điểm khác sẽ nằm ở đâu.

Linear là gì?

linear /ˈlɪnɪə/ Able to be represented by a straight line on a graph.

Vì ta cần tìm ra 1 đường thẳng, đường thẳng trong tiếng Anh là line, linear là “có thể biểu diễn bằng 1 đường thẳng” — trong toán học Việt Nam còn gọi là “tuyến tính” (tuyến trong tiếng Hán Việt nghĩa là đường thẳng — tuyến tính là có tính chất của đường thẳng).

Regression là gì?

Regression /rɪˈɡrɛʃ(ə)n/ (ri gờ rét sờn)

Là một cái tên lấy từ bộ môn thống kê (statistics), một thuật toán/khái niệm mang từ bên statistics về dùng.
Regression trong các sách tiếng Việt dịch là “hồi quy”, vậy thì hồi quy là gì? 
Việc sử dụng các từ Hán Việt cho các khái niệm chả khác nào đánh đố người học, khi mà đọc “hồi quy”, ít người hiểu nó là gì. Vậy thà ta cứ dùng tiếng Anh, nhiều khi nghĩa còn rõ ràng hơn.

Định nghĩa lấy từ từ điển Oxford:
regression |rɪˈɡrɛʃ(ə)n| (ri gờ rét sờn)

Trong ngành thống kê: regression là mối quan hệ giữa giá trị đầu ra (y) với các giá trị (biến) đầu vào (x, t …).
Trong tiếng Anh, regression được định nghĩa như sau:

a return to a former or less developed state

sự quay trở lại trạng thái trước đó hoặc trạng thái “kém phát triển” hơn.

Nghĩa thuần trong tiếng Anh thường dùng và nghĩa trong ngành thống kê của từ này có vẻ không liên quan gì. Mối quan hệ đâu liên quan gì tới sự thụt lùi (hồi quy)?

Tại sao trong ngành thống kê lại đẻ ra từ “regression”?

Đây là một từ mang tính chất lịch sử, khi Francis Galton nghiên cứu về chiều cao trong dân số, kết quả cho thấy nếu một người bố rất cao thì gen đó không được truyền cho con, mà nói chung là chiều cao sẽ tiến dần đến giá trị trung bình của toàn dân số. Sự thụt lùi (hồi quy) trong tiếng Anh là “regression”.

Vậy ta nên hiểu theo nghĩa của bộ môn thống kê: regression là mối quan hệ giữa một giá trị (đầu ra: y) với các giá trị khác (đầu vào: x, …). Và linear regression là mối quan hệ giữa đầu vào và đầu ra biểu diễn được trên một đường thẳng.

Bài toán tìm giá nhà

Nếu ta có số liệu về diện tích của 3 ngôi nhà, và giá của chúng đã bán được, liệu với ngôi nhà rộng 3000 mét vuông, ta nên bán với giá bao nhiêu?

Phân tích bài toán và chọn mô hình

Ban đầu ta chưa biết được phải giải bài này thế nào, nên ta vẽ số liệu này lên đồ thị 2 chiều, trục x sẽ chứa diện tích ngôi nhà, trục y sẽ chứa giá của ngôi nhà. Nhìn vào hình vẽ thì thấy có vẻ như, ta có thể vẽ 1 đường thẳng đi qua tất cả các điểm này. Vậy ta sẽ thử đi tìm đường thẳng đó.

Đường thẳng trong toán học

Thay vì cứ cố gắng mô tả bằng “diện tích ngôi nhà” — “giá của ngôi nhà”, hay “số tiền chi cho quảng cáo” — “số hàng bán được”, ta mô hình hoá bài toán để có những từ khoá thống nhất, ngắn gọn. Toán học giúp ta mô hình hoá vấn đề, làm cho mọi thứ ngắn gọn, có chuẩn. Ở đây ta dùng toán như một công cụ giúp ta giải quyết bài toán chứ không phải một mớ công thức để đi thi toán cao cấp cuối học kỳ.

Đường thẳng trong toán học được biểu diễn bằng biểu thức sau:

y = ax + b

Xem đồ thị các đường thẳng sau để thấy rõ mối quan hệ giữa giá trị a, b đối với hình dáng, vị trí của đường thẳng.

NẾU, mối quan hệ giữa diện tích ngôi nhà và giá nhà là một đường thẳng, ta có thể tính giá nhà bằng công thức:

giá nhà = a * (diện tích ngôi nhà) + b

Ta đã có một tập giá nhà (y) và diện tích ngôi nhà (x), giờ chỉ việc đi tìm a và b. Sau khi tìm được a và b, ta có thể đoán (tính) được y khi có x.

Chuẩn hoá công thức

Ai cũng có thể tự mình viết ra công thức toán, người sẽ dùng y = ax + b, người không thích lại viết y = kx + t hay y = bx + a… sẽ khiến việc chia sẻ/ nói chuyện / biểu diễn không thống nhất.
Ở đây, ta sẽ sử dụng ký hiệu theo lớp học ML của Stanford:

h(x) = theta_0 + theta_1 * x

theta, ký hiệu là θ , đọc là “thi tơ” /ˈθiːtə/

Hàm cost (cost function)

Ta mong muốn vẽ được 1 đường thẳng đi qua tất cả các điểm, nhưng thực tế thì sẽ có vài điểm không nằm trên đường thẳng mà chỉ nằm gần. Vậy cách nào để đánh giá đường thẳng vừa vẽ có đủ tốt hay không? có đường nào tốt hơn không? Ta đưa ra một giá trị để đo xem đường thẳng này có tốt không, dễ thấy giá trị đó có thể là tính bằng tổng khoảng các của tất cả các điểm đã biết tới đường thẳng. Ta gọi tên giá trị này là “cost” (giá tiền), khi cost = 0, tức là điểm không cách đường thẳng — hay chúng nằm trên đường thẳng — đường thẳng ta vẽ ra là đúng tuyệt đối. Khi cost càng lớn, thì các điểm càng lệch khỏi đường thẳng, tức đường thẳng này không được tốt cho lắm. Hàm số biểu diễn các giá trị cost gọi là J(theta_0, theta_1). Mục tiêu của ta là đi tìm đường thẳng mà có giá trị J nhỏ nhất.

Giá trị độ lệch tính bằng tổng của y-h(x), với mỗi x và y đã biết.
Cách tìm theta_1 và theta_0 hay tìm hàm h(x) đơn giản nhất: 
tính lần lượt cost function với mỗi theta_0 và theta_1, chọn ra giá trị cost nhỏ nhất. Phương pháp “vô học” này có tên là “brute-force”, thử tất cả các trường hợp có thể, việc chọn từ 1 tập vô hạn giá trị — là một việc làm không khả thi, nên ta chọn bừa một khoảng số nguyên cho theta_1 (VD: từ 0 đến 200) và cố định theta_0 = 0. Rõ ràng cách làm này không thu được giá trị cost nhỏ nhất nếu giá trị thật sự của theta_1 và theta_0 không nằm trong khoảng ta chọn. Nhưng hãy cứ thử xem với bài toán cụ thể này:

import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline

def cost(theta_0, theta_1, xs, ys):
    distance = 0
    for x,y in zip(xs, ys):
        predicted_value = theta_0 + theta_1 * x
        distance = distance + abs(y - predicted_value)
    return distance/len(xs)

areas = [1000, 2000, 4000]
prices = [200000, 250000, 300000]
theta_0 = 0
testno = 200
costs = [cost(theta_0, theta_1, areas, prices) for theta_1 in np.arange(testno)]
plt.plot(np.arange(testno), costs)

 

 

costs.index(min(costs)) # trả về 75

Bằng mắt thường cũng thấy được có vẻ như giá trị của y nhỏ nhất khi x ở đâu đó quanh 75. Nhưng hãy nhớ rằng đây là theta_1 khi ta đặt theta_0 = 0.

Vậy làm cách nào để tìm ra giá trị theta_1 và theta_0 nhanh nhất, đúng nhất? đã đến lúc mang một công cụ toán học cực mạnh vào cuộc chơi: đạo hàm 😳 NGƯNG SỢ HÃI.

Đạo hàm - derivative /dɪˈrɪvətɪv/

Cost function là một hàm số, và đạo hàm là công cụ giúp ta tìm được xem tại 1 điểm, đồ thị đang đi lên hay đi xuống. Đó là điều duy nhất ta cần hiểu ở đây. Còn giải thích TẠI SAO, hay cách tính từ công thức ban đầu ra công thức tính ta sẽ dùng cuối cùng, sẽ được trình bày ở một bài viết khác.

Gradient descend

Nếu derivative là khái niệm dành cho hàm số với một biến, thì cách nào để ta tìm được derivative đối với hàm h(x) có 2 biến theta_1 và theta_2?

Gradient /ˈɡreɪdɪənt/ là khái niệm tương tự như derivative, nhưng dành cho hàm nhiều biến (multi-variable)
Nếu derivative giúp ta biết hướng xuống dốc / lên dốc trong function 1 biến tại một điểm thì gradient giúp ta biết điều này trong function nhiều biến (2 trở lên).
Descend /dɪˈsɛnd/ <verb>
Eng: move or fall downwards
Vie: đi xuống phía dưới / xuống dốc

Gradient descend là một thuật toán giúp tìm điểm cực tiểu cục bộ (local minimum) của hàm số bằng cách đi dần dần về phía giảm của gradient (gradient descend).

Local (cục bộ) là gì?

Tưởng tượng chữ W là một đồ thị hàm số, nó có 2 điểm thất nhất, đó là 2 cực tiểu cục bộ, 2 điểm đó lần lượt thấp nhất so với các điểm xung quanh nó. Để biết cực tiểu toàn cục (global minimum), ta phải tìm hết các điểm cực tiểu cục bộ và so sánh với nhau.

Ban đầu ta có cost function J, sử dụng gradient descend sẽ tìm được điểm cực tiểu của cost function J ấy, tại đó giá trị cost function J là nhỏ nhất. Việc đi từ công thức toán học của cost function, cho đến công thức tính gradient descend, là việc của các nhà toán học. Ta chỉ lấy kết quả cuối cùng và thay số và để tính thôi (ta sẽ thử làm việc của các nhà toán học ở một bài khác). Hãy coi việc sử dụng công thức này như lý do bạn chấp nhận việc tính diện tích tam giác một cách vô điều kiện là 1/2 độ dài đáy nhân chiều cao, hay tính diện tích hình tròn bằng Pi * (bán kính) ^ 2 (và số PI từ đâu ra?)…

Giải bài toán linear regression với Python

Giờ đây ta có công thức tính gradient descend, nhưng việc tính gradient descend, cuối cùng, cũng chỉ để tính ra theta_0 và theta_1. Các thư viện Python đã giúp ta tính sẵn rồi, không cần phải tính lại nữa, chỉ việc dùng function có sẵn.

Các từ khoá:
- intercept/observation noise: điểm mà đường thẳng cắt trục Y. Là giá trị theta_0 trong công thức của h(x).
- slope/coefficients: độ dốc của đường thẳng h(x) — tương ứng giá trị theta_1 trong công thức h(x),

Numpy

import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
xi = np.array([1000, 2000, 4000])
y = [200000, 250000, 300000]
A = np.array([ xi, np.ones(len(xi))])
w = np.linalg.lstsq(A.T,y)[0]
line = w[0]*xi+w[1] # regression line
print("Numpy solution: %s" % w)
plt.plot(xi, line, 'b-', xi, y, 'o')

Numpy 

from scipy import stats
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline

xi = np.array([1000, 2000, 4000])
y = [200000, 250000, 300000]
A = np.array([ xi, np.ones(len(xi))])
slope, intercept, r_value, p_value, std_err = stats.linregress(xi,y)
line = slope*xi+intercept
print(slope, intercept)
plt.plot(xi,line,'b-',xi,y,'x')

scikit-learn

from sklearn import linear_model

regr = linear_model.LinearRegression()
xi = np.array([1000, 2000, 4000])
y = [200000, 250000, 300000]
regr.fit(xi.reshape(-1, 1), y)
print(regr.coef_, regr.intercept_) # [ 32.14285714] 175000.0

Cả 3 cách làm đều cho cùng một kết quả theta_0 là 175000.0
và theta_1 là 32.14285714

Tính giá cho ngôi nhà 3000 foot vuông

from sklearn import linear_model

regr = linear_model.LinearRegression()
xi = np.array([1000, 2000, 4000])
y = [200000, 250000, 300000]
regr.fit(xi.reshape(-1, 1), y)
print(regr.coef_, regr.intercept_)  # [ 32.14285714] 175000.0
print(regr.predict(3000))  # 271428.57142857

Quay lại bài toán thầy giáo PyMi.vn bán chuối 🍌

Nếu biết một giảng viên Python tại PyMi.vn đi bán chuối, bán 10 quả anh có 30 nghìn VNĐ, bán 3 quả anh có 9 nghìn, bán 5 quả anh có 15 nghìn. Hỏi bán 9 quả anh có bao nhiêu tiền?
Hẳn là không cần giỏi toán, chỉ cần học hết cấp 1 bạn đã giải được bài này. Dễ dàng tính được giá một quả chuối là 30 / 10 = 3 nghìn, 3 * 9 = 27 000 VND. Và rõ ràng (với trình độ toán cấp 2), ta biểu diễn được mối quan hệ giữa số tiền thu được, với số quả chuối — bằng một đường thẳng: y = 3x + 0

import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
import matplotlib
matplotlib.rc('font', family='Arial')

matplotlib.style.use('ggplot')

yi = np.array([30, 9, 15])
xi = np.array([10, 3, 5])
x = np.arange(0,12)
y = 3 * x 
plt.plot(x, y, 'b-', xi, yi, 'rx')
plt.title('Mối quan hệ giữa chuối và tiền thu được')

Nhưng hãy dùng linear regression để giải bài này

import numpy as np
from sklearn import linear_model

y = np.array([30, 9, 15])
xi = np.array([10, 3, 5])
regr = linear_model.LinearRegression()
regr.fit(xi.reshape(-1, 1), y) # biến vector 1x3 thành 3x1
print(regr.coef_, regr.intercept_)
print(regr.predict(9))

[ 3.] -3.5527136788e-15
[ 27.]

9 quả chuối 🍌, giá là 27 000 VNĐ.

Tổng kết

- Linear Regression là thuật toán để tìm ra một đường thẳng đi qua các điểm đã biết.
- Để tính một đường thẳng có đủ tốt không, sử dụng hàm cost 
- Dùng gradient descend để tìm đường thẳng có cost nhỏ nhất 
- Thuật toán đơn giản này đõ có trong cả 3 thư viên numpy, scipy, sklearn

Nếu dữ liệu không thể dùng 1 đường thẳng để dự đoán, ta có thể sẽ phải dùng đường cong (non-linear).
Bài toán tìm đường để phân tách dữ liệu thành 2 tập cũng có thể dùng phương pháp tương tự, và có tên Logistic Regression — sẽ được viết ở các bài tiếp theo.

Tham khảo

Bài viết http://adit.io/posts/2016-02-20-Linear-Regression-in-Pictures.html có nhiều hình vẽ, giúp hiểu các thuật toán tốt hơn.

https://www.coursera.org/learn/machine-learning

https://en.wikipedia.org/wiki/Regression_analysis
https://www.quora.com/topic/Regression-statistics