ToanNV's Blog

ToanNV

Developer, living in Tokyo, get married.


Đừng kể rắc rối của bạn cho bất cứ ai. 20% chẳng quan tâm, còn 80% thì vui mừng vì bạn gặp chuyện.

[Course][ML] Linear regression

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 feet2feet^{2}(x)Price($) in 1000's
2104460
1464232
1534315
852178
......

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

linear regression

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

  • mm: là số lượng training examples.
  • xsx's: là giá trị đầu vào(features).
  • ysy's: là giá trị đầu ra(target variable).
  • (x,y)(x, y) là một tranining example.
  • (x(i),y(i))(x^{(i)}, y^{(i)}) là training example thứ ithi^{th}.

Sau khi biểu diễn các điểm (x,y)(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:

hθ=θ0+θ1xh_{\theta} = \theta_{0} + \theta_{1}x

Nhiệm vụ tiếp theo mà chúng ta cần làm là xác định θi\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θ(x)yhθ(x)yh_{\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θ(x)h_{\theta}(x)yy 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 θi\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:

J(θ0,θ1)=12mi=1m(hθ(x(i))y(i))2J(\theta_{0}, \theta_{1}) = \frac{1}{2m}\sum\limits_{i=1}^m(h_{\theta}(x^{(i)}) - y^{(i)})^2

Giải thích một chút về công thức trên J(θ0,θ1)J(\theta_{0}, \theta_{1})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 mm example trong tập training set.

J(θ0,θ1)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θ(x(i))y(i))(h_{\theta}(x^{(i)}) - y^{(i)})? Tại sao lại là 12m\frac{1}{2m} chứ không phải là 1m\frac{1}{m}?

Tính bình phương hiệu số (hθ(x(i))y(i))(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 1m\frac{1}{m} hay 12m\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 12m\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 minimizeJ(θ0,θ1)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(θ0,θ1)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(θ0,θ1)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ụ {\{

θj:=θjαθjJ(θ0,θ1)\theta_{j} := \theta_{j} - \alpha\frac{\partial}{\partial\theta_{j}}J(\theta_{0}, \theta_{1})
(Simultaneouslyupdatej=0andj=1)(Simultaneously\;update\;j = 0\;and\;j = 1)

}\}

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 θj\theta_{j} được tiến hành đồng thời chứ không phải là update θ0\theta_{0} xong mới update θ1\theta_{1}.

θjJ(θ0,θ1)\frac{\partial}{\partial\theta_{j}}J(\theta_{0}, \theta_{1}) là đạo hàm của hàm mất mát J(θ0,θ1)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

αtoosmall\alpha\;too\;small

Alpha too large

αtoolarge\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

hθ=θ0+θ1xh_{\theta} = \theta_{0} + \theta_{1}x

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

J(θ0,θ1)=12mi=1m(hθ(x(i))y(i))2J(\theta_{0}, \theta_{1}) = \frac{1}{2m}\sum\limits_{i=1}^m(h_{\theta}(x^{(i)}) - y^{(i)})^2

Để tìm minJ(θ0,θ1)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ụ {\{

θj:=θjαθjJ(θ0,θ1)\theta_{j} := \theta_{j} - \alpha\frac{\partial}{\partial\theta_{j}}J(\theta_{0}, \theta_{1})
(Simultaneouslyupdatej=0andj=1)(Simultaneously\;update\;j = 0\;and\;j = 1)

}\}

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

θjJ(θ0,θ1)=θj12mi=1m(hθ(x(i))y(i))2\frac{\partial}{\partial\theta_{j}}J(\theta_{0}, \theta_{1}) = \frac{\partial}{\partial\theta_{j}}\frac{1}{2m}\sum\limits_{i=1}^m(h_{\theta}(x^{(i)}) - y^{(i)})^2
θjJ(θ0,θ1)=θj12mi=1m(θ0+θ1x(i)y(i))2\Leftrightarrow\;\frac{\partial}{\partial\theta_{j}}J(\theta_{0}, \theta_{1}) = \frac{\partial}{\partial\theta_{j}}\frac{1}{2m}\sum\limits_{i=1}^m(\theta_{0} + \theta_{1}x^{(i)} - y^{(i)})^2

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

j=0:θ0J(θ0,θ1)=1mi=1m(hθ(x(i))y(i))j = 0: \frac{\partial}{\partial\theta_{0}}J(\theta_{0}, \theta_{1}) = \frac{1}{m}\sum\limits_{i=1}^m(h_{\theta}(x^{(i)}) - y^{(i)})
j=1:θ1J(θ0,θ1)=1mi=1m(hθ(x(i))y(i)).x(i)j = 1: \frac{\partial}{\partial\theta_{1}}J(\theta_{0}, \theta_{1}) = \frac{1}{m}\sum\limits_{i=1}^m(h_{\theta}(x^{(i)}) - y^{(i)}).x^{(i)}

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

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

θ0:=θ0α1mi=1m(hθ(x(i))y(i))\theta_{0} := \theta_{0} - \alpha\frac{1}{m}\sum\limits_{i=1}^m(h_{\theta}(x^{(i)}) - y^{(i)})
θ1:=θ1α1mi=1m(hθ(x(i))y(i)).x(i)\theta_{1} := \theta_{1} - \alpha\frac{1}{m}\sum\limits_{i=1}^m(h_{\theta}(x^{(i)}) - y^{(i)}).x^{(i)}
(Simultaneouslyupdateθ0andθ1)(Simultaneously\;update\;\theta_{0}\;and\;\theta_{1})

}\}

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.

hθ(x)=θ0+θ1x1+θ2x2+θ3x4+++θnxnh_{\theta}(x) = \theta_{0} + \theta_{1}x_{1} + \theta_{2}x_{2} + \theta_{3}x_{4} + \dots + + \theta_{n}x_{n}

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

X=[x0x1x2xn]X = \begin{bmatrix} x_{0} \\ x_{1} \\ x_{2} \\ \vdots \\ x_{n} \\ \end{bmatrix}
Θ=[x0x1x2xn]\Theta = \begin{bmatrix} x_{0} \\ x_{1} \\ x_{2} \\ \vdots \\ x_{n} \\ \end{bmatrix}
hθ(x)=ΘTX\Rightarrow h_{\theta}(x) = \Theta^{T}X

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

J(Θ)=12mi=1m(hθ(x(i))y(i))2J(\Theta) = \frac{1}{2m}\sum\limits_{i=1}^m(h_{\theta}(x^{(i)}) - y^{(i)})^2

và gradient descent:

θj:=θjαθjJ(Θ) \theta_{j} := \theta_{j} - \alpha\frac{\partial}{\partial\theta_{j}}J(\Theta)
(Simultaneouslyupdateforeveryj=0,,n) (Simultaneously\;update\;for\;every\;j = 0,\dots,n)

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 JJ 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à x1x_{1} và số lượng phòng ngủ x2x_{2}. khi đó, hàm J(Θ)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][-1, 1] hoặc [0.5,0.5][-0.5, 0.5] tuỳ thuộc vào từng bài toán.

xi=xiμisix_{i} = \frac{x_{i} - \mu_{i}}{s_{i}}

Trong đó:

  • μi\mu_{i} là giá trị trung bình của feature xix_{i} trong tập training set.
  • si=maxmins_{i} = max - min (max, min lần lượt là giá trị lớn nhất và nhỏ nhất của feature đó trong tập training set)

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:

J(Θ)=12mi=1m(hθ(x(i))y(i))2J(\Theta) = \frac{1}{2m}\sum\limits_{i=1}^m(h_{\theta}(x^{(i)}) - y^{(i)})^2
J(Θ)=12mi=1m(ΘTXiyi)2J(\Theta) = \frac{1}{2m}\sum\limits_{i=1}^m(\Theta^{T}X_{i} - y_{i})^2

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(Θ)J(\Theta) bằng 0.(J(Θ)=0J'(\Theta)=0)

J(Θ)=1mi=1m(ΘTXiyi)XiT=0J'(\Theta)=\frac{1}{m}\sum\limits_{i=1}^m(\Theta^{T}X_{i} - y_{i})X_{i}^{T} = 0
i=1mΘTXiXiT=i=1myiXiT\Leftrightarrow \sum\limits_{i=1}^m\Theta^{T}X_{i}X_{i}^{T} = \sum\limits_{i=1}^my_{i}X_{i}^{T}
Θ=(XXT)1yXT\Leftrightarrow \Theta = (XX^{T})^{-1}yX^{T}

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 descentNormal equation
bắt buộc phải chọn α\alphaKhông cần chọn α\alpha
cần lặp lại nhiều lầnKhông cần phải lặp lại
O(kn2)O(kn^2)O(n3)O(n^3)
hoạt động tốt với n lớnvới n lớn thì thời gian tính toán lâu