[BayesOpt 2] Gaussian Process for Regression

[BayesOpt 1] Gaussians and Gaussian Process
[BayesOpt 2] Gaussian Process for Regression
[BayesOpt 3] Bayesian Optimization – intuition (and some theory)

Bài này nằm trong Draft hơi lâu rồi, nên hôm nay publish luôn, mặc dù còn vài ý chưa viết hết. Hi vọng sẽ có lúc viết nốt phần còn lại.

Trừ khi bạn quá giàu, tìm nhà thuê chắc là chuyện mà bạn đã làm ít nhất một lần trong đời. Giả sử bạn vừa mới tìm được việc ở Sài Gòn, văn phòng công ty ở quận 7, và bạn muốn tìm một căn hộ để thuê.

Để cho đơn giản, giả sử tại mỗi quận ở TpHCM, bạn có một căn hộ để đến xem. Căn ở quận 7 thì gần văn phòng, mát mẻ yên tĩnh, nhưng giá hơi cao. Căn ở Tân Bình thì rẻ và rộng, nhưng quá xa văn phòng, và bạn không muốn dành 2 tiếng mỗi ngày chạy xe trên đường. Quận 4 thì không quá xa, nhưng nguy hiểm nếu về khuya, quận 8 thì kẹt xe và ngập nước, Bình Chánh gần nhưng đường đi toàn xe tải v.v…

Với tất cả các điều kiện trên, bạn phải chọn một chỗ để thuê. Đến lúc bạn ra quyết định, mặc dù có thể không để ý, nhưng chắc chắn trong đầu bạn đã hình thành một loại mô hình nào đó để sắp xếp các lựa chọn trên theo mức độ hài lòng. Gọi mô hình này là f(x), với mỗi x là địa điểm (tại mỗi quận), nó sẽ cho ra f(x) là điểm số mà bạn gán cho địa điểm đó, giả sử f(x) \in [0, 1].

Giờ vấn đề là bạn không biết mô hình này được xây dựng dựa trên những tham số nào. Có thể đó là hàm theo giá thuê, khoảng cách tới văn phòng, đường có xe tải hay không, chất lượng không khí, có bị ngập nước không, v.v… và v.v… Bằng cách nào đó, dựa vào kinh nghiệm cá nhân (a.k.a. prior knowledge), bạn vẫn chọn được chỗ thuê mà bạn hài lòng nhất.

Sau khi học Machine Learning thì bạn biết cách mô hình hoá bất kì mô hình nào kiểu như vầy, miễn là biết các input features (có thể dùng linear regression, hay bất kì thuật toán supervised nào khác). Nhưng trong trường hợp này, có quá nhiều features mà bạn không biết chắc là có tác động gì tới quyết định cuối cùng hay không. Hơn nữa, mỗi lần đi xem nhà là bạn phải mất 1 ngày, quá tốn kém về mặt thời gian, do đó bạn muốn giảm thiểu số lần đi xem nhà, mà vẫn có thể ra quyết định tối ưu (điều này hơi trái ngược với supervised learning truyền thống, khi mà càng nhiều dữ liệu thì càng tốt). Bằng cách nào đó, bộ não con người được thiết kế tốt để ra quyết định trong những hoàn cảnh như vậy. Câu hỏi là có mô hình Machine Learning nào làm được chuyện này?

Gaussian Process là một mô hình như vậy. Trong linear regression và rất nhiều mô hình supervised learning khác, prior knowledge được mô hình hoá bằng dạng hàm của mô hình, chẳng hạn f(x) = \theta_1 x_1 + \theta_2 x_2 + ... + \theta_n x_n, và giả sử rằng dữ liệu được sinh ra dựa trên mô hình như vậy. Gaussian Process không giả sử như vậy. Giả sử duy nhất của GP là hàm phải smooth. Chính vì giả sử không “mạnh” lắm này mà GP có thể dùng trong những trường hợp input feature không đầy đủ, hoặc là cho những hàm mà chi phí tính toán lớn, nghĩa là với mỗi x, việc tính f(x) có chi phí quá cao, do đó thu thập thật nhiều dữ liệu để huấn luyện mô hình bình thường là không khả thi.

Vậy làm thế nào?

Một cách hình thức, ta có tập huấn luyện \left\{\left(x_i, f_i\right)\right\}_{i=1}^N, với f_i = f\left(x_i\right), f là một hàm black-box, ta chỉ có thể tính f(x) tại x bất kì, nhưng nói chung không biết analytical form của nó  (hàm mức độ hài lòng của bạn cho mỗi căn nhà đã xem, đại loại vậy).

Cho một tập dữ liệu mới X_* \in \mathbb{R}^{N_* \times D}, ta muốn dự đoán f_* = f(X_*). Rõ ràng đây là bài toán regression, nhưng ta không biết dạng hàm của f.

Rất “đơn giản”, GP giả sử rằng f tuân theo phân phối Gaussian:

\displaystyle \left(\begin{array}{c} \mathbf{f} \\ \mathbf{f_*}\end{array}\right) \sim \cal{N}\left(\left(\begin{array}{c} \mathbf{\mu} \\ \mathbf{\mu_*}\end{array}\right), \left( \begin{array}{cc} \mathbf{K} & \mathbf{K_*} \\ \mathbf{K_*^T} & \mathbf{K_{**}}\end{array} \right)\right)

với K=\kappa\left(\mathbf{X},\mathbf{X}\right) \in \mathbb{R}^{N\times N}K_*=\kappa\left(\mathbf{X},\mathbf{X_*}\right) \in \mathbb{R}^{N\times N_*}, K_{**}=\kappa\left(\mathbf{X_*},\mathbf{X_*}\right) \in \mathbb{R}^{N_*\times N_*}.

\kappa gọi là kernel function (nghe quen quen?), sẽ được nói tới sau.

Với giả sử này, thì theo định lí quan trọng nhất vũ trụ đã nói tới trong bài trước, phân phối của f_* cũng là Gaussian:

\displaystyle \begin{array}{rl} p\left(\mathbf{f_*}\vert \mathbf{X_*},\mathbf{X},\mathbf{f}\right) = & \mathcal{N}\left(\mathbf{f_*};\mathbf{\mu_*},\mathbf{\Sigma_*}\right) \\ \mathbf{\mu_*} = & \mathbf{\mu}\left(\mathbf{X_*}\right) + \mathbf{K}_*^T\mathbf{K}^{-1}\left(\mathbf{f} - \mathbf{\mu}\left(\mathbf{X}\right)\right) \\ \mathbf{\Sigma_*} = & \mathbf{K}_{**} - \mathbf{K}_*^T\mathbf{K}^{-1}\mathbf{K}_* \end{array}

Đây chính là biểu thức quan trọng nhất của Gaussian Process.

Giờ tới phần lằng nhằng. Ta có thể đọc biểu thức trên theo nghĩa rằng f_* là giá trị của hàm f(\mathbf{X_*}), nhưng như vậy không đúng. Ta phải hiểu rằng f_* thật ra là một hàm, và biểu thức trên nói rằng thật ra GP là phân phối Gaussian trên hàm (distribution of functions), chứ không phải là distribution of values.

Tại sao như vậy? Nhìn vào biểu thức trên, ta thấy \mathbf{\mu}_*\mathbf{\Sigma}_* là hàm theo \mathbf{X}_*. Với mỗi \mathbf{X}_* ta sẽ có giá trị của \mathbf{\mu}_*\mathbf{\Sigma}_* khác nhau. Sau khi có \mathbf{\mu}_*\mathbf{\Sigma}_*, ta có thể lấy mẫu \mathbf{f}_* từ phân phối Gaussian như đã nói trong bài trước.

Giờ tưởng tượng ta lấy X_* là các điểm rời rạc trên toàn miền xác định của x (số điểm có thể là vô hạn). Về lí thuyết ta có thể lấy mẫu f_* tại tất cả các điểm trên, hay nói cách khác là mỗi mẫu lấy từ phân phối Gaussian nói trên thật ra là một hàm. Đây là lí do mà ta gọi GP là distribution of functions.

Lại nữa, rõ ràng giá trị của \mathbf{f} tại mỗi điểm đều tuân theo Gaussian, nên một cách nhìn khác, ta cũng có thể coi GP là phân phối Gaussian vô hạn chiều, mà bất kì tập con hữu hạn nào trên miền xác định của x cũng tuân theo phân phối Gaussian.

Đây là hai cách nhìn tương đương nhau về GP. Mình đọc khá nhiều kiểu trình bày nhưng đơn giản nhất vẫn là nhìn vào công thức trên (thật ra nghĩa là mình không biết giải thích thế nào cho dễ hiểu hơn).

Distribution of functions là thế quái nào? Hình sau minh hoạ khái niệm này:

figure_1

Khung đầu tiên vẽ mô hình GP trên không gian 1 chiều (trục hoành). Tưởng tượng ta lấy X_* là các điểm rời rạc (nhưng rất gần nhau: 0.01, 0.02, 0.03, …, 9.99, 10) trên trục hoành, thì đường nét đứt màu đỏ là giá trị của \mathbf{\mu}_*, vùng màu xám là giá trị của \mathbf{\Sigma}_*, và các điểm đánh dấu màu đỏ là tập huấn luyện \mathbf{X}. Đường màu xanh là giá trị thật của hàm mà ta (giả bộ là) chưa biết. Rõ ràng với chỉ vài điểm trong tập huấn luyện, ta có thể xấp xỉ đường màu xanh khá tốt.

Khung cuối cùng là 10 hàm khác nhau được lấy mẫu từ GP. Để ý rằng tất cả các hàm đều nằm trong vùng màu xám, và collapse tại các vị trí thuộc tập X. Như vậy ta có thể nghĩ GP là phân phối Gaussian trên các hàm.

Một góc nhìn khác, nếu xem các điểm trên trục hoành là các chiều của một phân phối multivariate Gaussian, thì có thể xem GP là phân phối Gaussian với số chiều vô hạn.

Hình ở giữa sẽ được giải thích trong bài sau.

Tưởng tượng trục hoành là các quận ở TpHCM. Các điểm màu đỏ được đánh dấu là điểm của mỗi quận mà ta đã đến xem nhà, như vậy bằng Gaussian Process ta có thể mô hình hoá được hàm mức độ hài lòng trên tất cả các quận, mà không cần biết bất kì thông tin gì khác về hàm này, ngoài tập huấn luyện. Bằng cách đó, ta có thể dễ dàng tìm ra quận mà làm maximize hàm mức độ hài lòng. Đây là tư tưởng chủ yếu của Bayesian Optimization.

Câu vừa rồi quan trọng: tư tưởng chủ yếu của Bayesian Optimization là dùng Gaussian Process để xấp xỉ một hàm phức tạp, sau đó tìm điểm optimal của phân phối biểu diễn bởi GP, hi vọng rằng đó cũng là điểm optimal của hàm phức tạp mà ta không biết.

Một chi tiết quan trọng mà ta chưa nhắc đến là hàm kernel. \kappa\left(x_1, x_2\right) đo mức độ “ảnh hưởng” lên nhau của 2 điểm x_1, x_2, nói cách khác nó thể hiện mức độ smooth của hàm mà ta đang mô hình hoá. Loại hàm kernel phổ biến nhất là Martern 5/2, nhưng hàm exponential đôi khi cũng dc dùng.

Một chi tiết quan trọng khác là mô hình trên quá “lí tưởng” vì không tính đến nhiễu. GP xử lí nhiễu bằng cách mô hình hoá trực tiếp \mathbf{y} = \mathbf{f}\left(x\right) + \epsilon, với \epsilon \sim \mathcal{N}\left(0,\sigma_y^2\right). Ta sẽ nói tiếp về Noisy GP trong một dịp khác.

Cài đặt đơn giản của GP có trên github, file interactive.py là code để sinh ra hình trên.

 

Advertisements

3 comments

  1. Bài viết cực kỳ tận tâm!
    Có điều e bắt đầu đọc lại mấy cái này với một số ký hiệu toán học, em quên hết ráo.
    Ko biết làm sao để có thể hiểu mấy cái symbol trong bài vậy anh!

      1. Mấy nay em học trên Coursera… mọi thứ bắt đầu thông não rồi anh!
        Đã đọc loạt bài của anh ngọt hơn rồi!

        Năm mới an lành anh nhé.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s