Machine Learning - 1.3 - Parameter Learning
Bài thứ 3 trong chuỗi bài viết tự học Machine Learning.
Ở 2 bài trước, chúng ta đã có hàm hypothesis và cách để biết hàm đó có phù hợp với bộ training example của chúng ta hay ko. Bây giờ chúng ta sẽ tìm cách tìm ra các tham số cho hàm hypothesis.
Xem các bài viết khác tại Machine Learning Course Structure
1. Gradient Descent
Ở 2 bài trước, chúng ta đã có hàm hypothesis và cách để biết hàm đó có phù hợp với bộ training example của chúng ta hay ko. Bây giờ chúng ta sẽ tìm cách tìm ra các tham số cho hàm hypothesis, và đó là nhiệm vụ của Gradient Descent.
Để đơn giản, trong phần này, ta sẽ xét các hàm hypothesis có 2 tham số là $latex \theta_{0}$ và $latex \theta_{1}$. Đối với các trường hợp có nhiều hơn 2 tham số, cách thực hiện là tương tự.
1.1. Biểu diễn đồ thị
Gọi $latex J(\theta_{0},\theta_{1})$ là kết quả của cost function. Ta biểu diễn các tham số lên một đồ thị có 3 trục x, y và z như sau:
- $latex \theta_{0}$ là trục x.
- $latex \theta_{1}$ là trục y.
- $latex J(\theta_{0},\theta_{1})$ là trục z.
Các mũi tên đỏ chỉ những điểm thấp nhất của đồ thị này, đó là các điểm mà ta tìm kiếm (nhằm mục đích tối thiểu giá trị của cost function).
1.2. Mô tả thuật toán
Chọn 1 điểm bất kỳ, sau đó di chuyển từng bước nhỏ về vùng trũng nhất của đồ thị.
Cách làm là lấy đạo hàm của cost function. Đối với một hàm số, đạo hàm của nó chính là đường tiếp tuyến của nó. Độ dốc của đường tiếp tuyến tại một điểm chính là giá trị của hàm đạo hàm tại điểm đó. Độ dốc này cho ta biết hướng đi để chọn điểm tiếp theo.
Độ dài của mỗi step được xác định bởi tham số $latex \alpha$, gọi là learning rate.
Điểm ban đầu được chọn khác nhau sẽ cho ra các kết quả rất khác nhau. Hình bên trên có 2 điểm ban đầu khác nhau, và sẽ cho ra 2 điểm thấp nhất là 2 mũi tên đỏ.
Như vậy, thuật toán Gradient Descent sẽ là:
lặp lại cho tới khi hội tụ:
$latex \theta_{j} := \theta_{j} - \alpha \frac{\partial}{\partial\theta_{j}}J(\theta_{0},\theta_{1})$
với:
$latex j=0,1,2,…,m$, đại diện cho index
Với mỗi lần lặp, cả $latex \theta_{0}$ và $latex \theta_{1}$ phải được tính đồng thời.
1.3. Xây dựng
Để cho đơn giản, ta sẽ dùng hàm số chỉ có 1 biến $latex \theta_{1}$ và từng bước xây dựng công thức cho Gradient Descent.
Vậy công thức của ta còn:
Lặp lại cho tới khi hội tụ:
$latex \theta_{1} := \theta_{1} - \alpha \frac{\partial}{\partial\theta_{1}}J(\theta_{1})$
với
- $latex \alpha$ là learning rate
- $latex \frac{\partial}{\partial\theta_{1}}J(\theta_{1})$ là độ dốc của đường tiếp tuyến (slope) tại $latex \theta_{1}$
Nhìn vào đồ thị trên, khi slope nằm bên trái của điểm hội tụ, thì giá trị $latex \theta_{1}$ tăng, và ngược lại khi nó nằm bên phải của điểm hội tụ.
Tham số $latex \alpha$ nên được điều chỉnh hợp lý sao cho thuật toán gradient descent hội tụ trong 1 khoảng thời gian phù hợp.
Khi $latex \alpha$ quá nhỏ, thời gian tìm đến điểm hội tụ sẽ lâu. Khi quá lớn, thuật toán rất có thể sẽ không tìm thấy điểm hội tụ.
Với một tham số $latex \alpha$ hợp lý, càng về gần điểm hội tụ, độ dốc của tiếp tuyến sẽ càng nhỏ, do đó, thuật toán gradient descent sẽ có bước đi nhỏ hơn, và sẽ bằng 0 khi tới điểm hội tụ.
Trong trường hợp điểm xuất phát chính là điểm hội tụ, thì thuật toán gradient descent sẽ cho ra $latex \theta_{1}$ không đổi với $latex \alpha$ bất kỳ, vì đạo hàm của nó là 0.
2. Gradient Descent cho Linear Regression
Khi áp dụng thuật toán Gradient Descent vào hàm số Hypothesis của ta trong các bài viết trước, ta có thể tìm được 2 tham số $latex \theta_{0}$ và $latex \theta_{1}$:
Lặp lại cho tới khi hội tụ:
$latex \theta_0 := \theta_0 - \alpha \frac{1}{m} \sum\limits_{i=1}^{m}(h_\theta(x_{i}) - y_{i})$
$latex \theta_1 := \theta_1 - \alpha \frac{1}{m} \sum\limits_{i=1}^{m}\left((h_\theta(x_{i}) - y_{i}) x_{i}\right)$
với:
- m là tổng số training example.
- $latex \theta_0$ tham số sẽ thay đổi đồng thời với $latex theta_1$ và $latex x_{i}$.
- $latex y_{i}$ là các giá trị được cho bởi bộ training example.
Như vậy, số 2 dưới mẫu trong công thức của bài kỳ trước đã bị triệt tiêu vì đạo hàm
Gradient Descent trong bài toán này thường được gọi là
Batch Gradient Descent, vì nó tính tổng của tất cả các giá trịHàm hypothesis của bài toán Linear Regression có hình dạng như một cái tô, và chỉ có 1 điểm hội tụ duy nhất.