Machine Learning – 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à \theta_{0}\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 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:

  • \theta_{0} là trục x.
  • \theta_{1} là trục y.
  • J(\theta_{0},\theta_{1}) là trục z.

gradient descent graph

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ố \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ụ:

\theta_{j} := \theta_{j} - \alpha \frac{\partial}{\partial\theta_{j}}J(\theta_{0},\theta_{1})

với:

j=0,1,2,...,m, đại diện cho index

Với mỗi lần lặp, cả \theta_{0}\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 \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ụ:

\theta_{1} := \theta_{1} - \alpha \frac{\partial}{\partial\theta_{1}}J(\theta_{1})

với

  • \alpha là learning rate
  • \frac{\partial}{\partial\theta_{1}}J(\theta_{1}) là độ dốc của đường tiếp tuyến (slope) tại \theta_{1}

plot

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ị \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ố \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 \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ố \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 \theta_{1} không đổi với \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ố \theta_{0}\theta_{1}:

Lặp lại cho tới khi hội tụ:

\theta_0 := \theta_0 - \alpha \frac{1}{m} \sum\limits_{i=1}^{m}(h_\theta(x_{i}) - y_{i})

\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.
  • \theta_0 tham số sẽ thay đổi đồng thời với theta_1x_{i}.
  • 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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.