[Course][ML] Linear regression

- 9 mins

Linear regression

Linear regression with one variable

Approach

Cho một dataset bao gồm các features và kết quả chính xác của đầu ra. Mục tiêu là đưa ra được một mô hình để dự đoán cho các dữ liệu có feature tương tự. Ví dụ: cho một dataset có chứa 2 tham số là diện tích căn nhà và giá bán thực tế của căn nhà đó. Mục tiêu là xây dựng một mô hình để dự đoán giá của một căn nhà khi biết diện tích của nó.

linear regression

Cost function

Cho một training set:

Size in $feet^{2}$(x) Price($) in 1000’s
2104 460
1464 232
1534 315
852 178

Biểu diễn tập training set lên hệ trục toạ độ:

linear regression

Giả sử ta định nghĩa:

Sau khi biểu diễn các điểm $(x, y)$ lên hệ trục toạ độ, chúng ta có thể dễ dàng dự đoán được hàm số Hypothesis mapping dữ liệu đầu vào và đầu ra có dạng:

Nhiệm vụ tiếp theo mà chúng ta cần làm là xác định $\theta_{i}$ để thu được mô hình tốt nhất. Vậy thế nào là mô hình tốt? Mô hình tốt là mô hình có kết quả dự đoán và giá trị thực tế gấn giống nhau, nghĩa là $h_{\theta}(x) \sim y\Leftrightarrow |h_{\theta}(x) - y|$ càng nhỏ thì mô hình càng tốt.

Chính bởi vì $h_{\theta}(x)$ và $y$ luôn có sự khác biệt nên người ta sinh ra một hàm số để đo sự khác biệt này. Nó có tên gọi là: Cost funtion. Khi cost function càng nhỏ thì ta sẽ thu được mô hình cảng tốt.

$\Rightarrow$ Từ bài toán đi tìm $\theta_{i}$ chuyển thành tối ưu hàm Cost funtion.

Trong bài toán Linear regression with one variable thì cost function có dạng như sau:

Giải thích một chút về công thức trên $J(\theta_{0}, \theta_{1})$ là cost function. Đây là hàm tính sai số trung bình của output thực tế và output của mô hình với $m$ example trong tập training set.

$J(\theta_{0}, \theta_{1})$ là hàm tính trung bình, ok fine. Vậy tại sao lại phải tính bình phương hiệu số $(h_{\theta}(x^{(i)}) - y^{(i)})$? Tại sao lại là $\frac{1}{2m}$ chứ không phải là $\frac{1}{m}$?

Tính bình phương hiệu số $(h_{\theta}(x^{(i)}) - y^{(i)})$ nhằm mục đích làm cho kết quả không bị âm mà thôi. Còn viêc lấy trung bình $\frac{1}{m}$ hay $\frac{1}{2m}$ hay lấy tổng của chúng, về mặt toán học thì không ảnh hưởng tới nghiệm của bài toán. Do dữ liệu tính toán có thể sẽ rất lớn gây tràn bộ nhớ, và thời gian tính toán, nên khi tính toán ta lấy trung bình $\frac{1}{2m}$ sẽ tốt.

Ok quay lại với cost function. Mục đích của chúng ta là tối ưu hàm $minimize J(\theta_{0}, \theta_{1})$.

Đến đây bạn có thể cần nhớ lại 1 chút kiến thức về giải tích. Để ý thấy hàm $J(\theta_{0}, \theta_{1})$ là hàm bậc hai của $\theta$ nên nó sẽ có dạng là hình bowl, và hàm $J(\theta_{0}, \theta_{1})$ khi mà đạo hàm của nó bằng 0. (Nhớ lại bảng biến thiên và kiến thức cấp 3)

cost function

Gradient descent

Với bài toán trên, ta có thể dễ dàng tìm ra nghiệm bằng cách đạo hàm, và giải phương trình đạo hàm bằng 0. Tuy nhiên, trong thực tế việc giải phương trình đạo hàm bằng 0 hầu như là rất khó, nếu không muốn nói là không làm được. Vì nhu cầu đó, nên thuật toán Gradient descent ra đời. Ý tưởng của thuật toán khá đơn giản. Đó là xác định 1 điểm gần với điểm mà ta cho là nghiệm của bải toán, sau đó dùng một phép toán lặp để tiến đến gần điểm cần tìm. Phép lặp được dừng lại khi hội tụ.

Nhìn chung có thể khái quát như sau:

Lặp lại cho đến khi hội tụ ${$

$}$

Nên nhớ trong công thức trên sử dụng phép toán $:=$ chứ không phải phép toán $=$, và việc update $\theta_{j}$ được tiến hành đồng thời chứ không phải là update $\theta_{0}$ xong mới update $\theta_{1}$.

$\frac{\partial}{\partial\theta_{j}}J(\theta_{0}, \theta_{1})$ là đạo hàm của hàm mất mát $J(\theta_{0}, \theta_{1})$

$\alpha$ được gọi là learning rate(tốc độ học).

Tốc độ, và độ chính xác của thuật toán này dựa phụ thuộc vào hai yếu tố: điểm khởi tạo ban đầu và tốc độ học. Thật vậy, nếu bạn chọn điểm ban đầu cách quá xa điểm hội tụ thì thời gian tìm ra điểm hội tụ sẽ lâu hơn, hoặc giả như ta chọn tốc độ học quá nhỏ cũng làm cho việc tiến đến điểm hội tụ bị chậm, hoặc tốc độ học quá lớn khiến cho công thức trên không thể hội tụ.

Alpha too small

Alpha too large

Để hiểu hơn về thuật toán Gradient descent, bạn có thể tham bài viết của anh Tiệp.

Gradient descent for linear regression

OK đến đây chúng ta sẽ tổng hợp lại một chút.

Mô hình linear regression có dạng

Với hàm mất mát là:

Để tìm $min\;J(\theta_{0}, \theta_{1})$ ta có thể áp dụng thuật toán gradient descent.

Lặp lại cho đến khi hội tụ ${$

$}$

Vậy ta cần tính đạo hàm của hàm mất mát $J(\theta_{0}, \theta_{1})$ trong mô hình linear regression.

$\Rightarrow$ Với j lần lượt là 0 và 1 ta sẽ có:

Khi đó bài toán sẽ trở thành:

Lặp lại cho đến khi hội tụ ${$

$}$

Linear Regression with multiple variables

Vậy là xong với bài toán Linear Regression một biến. Tuy nhiên, trong thực tế có rất ít bài toán mà chỉ có một feature, mà thường là sẽ có rất nhiều features. Ví dụ như trong bài toán dự đoán giá nhà như đã nói ở phần trước, trong thực tế sẽ có rất nhiều features khác nữa ví dụ như: số lượng phòng ngủ, tuổi của căn nhà, có phòng khách hay không… Khi đó hàm mô Hypothesis sẽ thành hàm nhiều biến.

Ở đây ta thấy hàm $h_{\theta}(x)$ dường như bằng tích của hai vector. Thật vậy, nếu giả sử $x_{0} = 1$. Khi đó:

Và khi đó hàm mất mát sẽ trở thành:

và gradient descent:

Feature Scaling

Trong bài toán với nhiều tham số thì việc scale các fetures về cùng một khoảng là điều cần thiết. Vì nếu không làm việc này thì hàm mất mát $J$ sẽ rất khó hội tụ, vì ratio của các features lớn.

feature scaling

Trong ví dụ trên là bài toán dự đoán giá nhà với hai tham số là: diện tích căn nhà $x_{1}$ và số lượng phòng ngủ $x_{2}$. khi đó, hàm $J(\Theta)$ sẽ được biểu diễn trên hệ trục toạ độ như hình. Khi ratio của các feature cao thì đồ thị trở thành hình eclipse, ratio càng cao thì hình eclipse càng bị dẹt, khi đó việc tiến đến điểm hội tụ sẽ khó khăn. Vì vậy, việc đưa các features về cùng cùng một khoảng đủ nhỏ là cần thiết cho việc tính toán, chẳng hạn như khoảng $[-1, 1]$ hoặc $[-0.5, 0.5]$ tuỳ thuộc vào từng bài toán.

Trong đó:

Learning rate

Cũng giống như trường hợp Linear regression with one variable, nếu chọn $\alpha$ quá nhỏ thì thời gian hội tụ sẽ lâu, nếu chọn $\alpha$ quá lớn thì khả năng không hội tụ được rất cao. Vì thế với mỗi bài toán cụ thể thì cần phải thử $\alpha$ với nhiều giá trị như: 0.001, 0.003, 0.01, 0.1, 1,…

Normal equation

Theo như trên, ta có hàm mất mát của mô hình Linear regression with multiple variables như sau:

Mô hình là tốt khi hàm mất mát là nhỏ nhất, nghĩa là đạo hàm của hàm $J(\Theta)$ bằng 0.($J’(\Theta)=0$)

Từ trên công thức trên ta có thể dễ dàng tìm được $\Theta$ bằng các tính toán đại số.

Gradient descent vs Normal equation

Gradient descent Normal equation
bắt buộc phải chọn $\alpha$ Không cần chọn $\alpha$
cần lặp lại nhiều lần Không cần phải lặp lại
$O(kn^2)$ $O(n^3)$
hoạt động tốt với n lớn với n lớn thì thời gian tính toán lâu
ToanNV

ToanNV

Developer, living in Tokyo, get married.

ToanNV © 2019
rss facebook twitter github youtube mail spotify instagram linkedin google google-plus pinterest medium vimeo stackoverflow reddit quora