Linear Algebra

[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?

(more…)

Advertisements

[RL2d] Bellman Equations revisited

[RL1] Markov Decision process – Introduction
[RL2a] Markov Decision Process – Discounted Reward
[RL2b] Markov Decision Process – Bellman equation
[RL2c] Markov Decision Process – Solving Bellman equation
[RL2d] Bellman Equations revisited
[RL3] Q-Learning
[RL4] Game Theory – overview

Trong bài trước, ta có nói Bellman equation là như thế này:

\displaystyle U\left(s\right) = R\left(s\right) + \gamma \max_a \sum_{s'} T\left(s, a, s'\right) U\left(s'\right)

Tuy nhiên ta cũng có thể viết lại nó thành thế này:

\displaystyle V\left(s\right) = \max_a \left(R\left(s, a\right) + \gamma\sum_{s'}T\left(s,a,s'\right)V\left(s'\right)\right)

Hàm này gọi là Value function, kí hiệu là V. Thật ra thì nó biểu diễn cùng 1 thứ so với phương trình ở trên, nhưng ta buộc luôn cả action a vào trong hàm reward R(s, a), nghĩa là thay vì nhận được reward tại mỗi state s như trong phương trình U(s), ta sẽ nhận reward sau khi thực hiện action a khi đang đứng tại state s. Vì sự thay đổi này nên hàm max phải được đem ra ngoài cùng. Suy nghĩ thêm một chút thì ta thấy rằng U(s) hay V(s) thật ra đều chỉ cùng 1 thứ, là “giá trị” của mỗi trạng thái s trong dài hạn.

Thật ra thì cuộc đời của một agent trong MDP có thể biểu diễn là một chuỗi các hành động:

s1 –> a1 –> R(s1, a1) —> s2 –> a2 –> R(s2, a2) —> s3 –>a3 –> R(s3, a3) —>….

Nghĩa là agent rơi vào trạng thái s1, thực hiện hành động a1, nhận được reward R(s1, a1) rồi rơi vào trạng thái s2, cứ như vậy lặp lại.

Người Pháp có câu Métro, boulot, dodo, chính là để chỉ cuộc đời kiểu này.

(more…)

Linear Algebra textbook

For anyone who is serious about Machine Learning, Linear Algebra background is a must. I was asked several times by several people about a good introductory textbook in Linear Algebra, and every single time I struggled to recall the name of the textbook I used.

But here it is, I somewhat magically found it very recently

51pGKKQb5tL._AC_UL320_SR226,320_

It is super concise and  greatly educational. Digesting the whole 300 pages will prepare you more than enough for pretty much any Linear Algebra stuff you will find in Machine Learning.

I learned Linear Algebra in undergraduate (with pretty decent professors I have to say), but it is in this book where my moment of enlightenment happened. Very early in the book, it presents how we should see the matrix multiplication in a slightly yet radically different view:  the multiplication A*x should not be interpreted as multiplying every row of A with x, but actually it is using elements of x to create a linear combination of the columns in A. This is the fundamental of all the reasoning in Linear Algebra, because with this view, Ax belong to the column space of A (a.k.a the range of A). Every Linear Algebra reasoning becomes super clean with this interpretation. Every matrix decomposition you find in Machine Learning (SVD, Cholesky, LU…) suddenly becomes all easy.

In other words, this is highly recommended for any newbie in Machine Learning. I believe you will enjoy it as much as I did.

Review sách: The Master Algorithm

the-master-algorithm-by-pedro-domingos

Dạo gần đây rảnh nên đọc được nhiều hơn, tạm thời sẽ review sách trước khi quay lại với series về Học củng cố (a.k.a. Reinforcement Learning).

Mình biết tới Pedro Domingos cách đây vài năm, khi đang làm vài thứ liên quan tới Sum-Product Networks. Lúc đó khá ấn tượng với paper SPN, vì cách tiếp cận thật sự rất fresh và original. Mặc dù vậy SPN có những hạn chế cố hữu (có thể sẽ viết 1 bài riêng về cái này) nên ứng dụng thực tế không nhiều. Tiếp theo “truyền thống” đó, sách này của Domingos cũng trình bày 1 góc nhìn tươi mới và hệ thống về Machine Learning nói chung.

Đọc sách này, người đọc rất dễ liên tưởng tới A Brief History of Time của Stephen Hawking. Cả 2 đều là sách nhập môn dành cho người không chuyên, một quyển cho Vật lí hiện đại và quyển kia cho Máy học. Cả 2 quyển sách đều làm việc đó bằng cách kể một câu chuyện, đều bắt đầu và diễn tiến bằng mục tiêu đi tìm một lí thuyết chung nhất cho lĩnh vực của nó: trong sách của Hawking là sự hợp nhất Thuyết tương đối rộng của Einstein với Quantum physics, trong sách của Domigos là universal learner: thuật toán “trùm cuối” của cả ngành Machine Learning. Mỗi quyển sách đều chỉ chứa đúng 1 công thức: sách của Hawking là E = mC^2, của Domingos là công thức của Markov Logic Networks. Thậm chí không biết vô tình hay cố ý, Domigos còn sử dụng chính xác định nghĩa của Hawking về scientific theory.

(more…)

[RL2a] Markov Decision Process – Discounted Reward

[RL1] Markov Decision process – Introduction
[RL2a] Markov Decision Process – Discounted Reward
[RL2b] Markov Decision Process – Bellman equation
[RL2c] Markov Decision Process – Solving Bellman equation
[RL3] Q-Learning
[RL4] Game Theory – overview

Trong bài trước, ta đang dừng ở hàm Utility của một chuỗi trạng thái, và ta nói rằng U\left(s_0, s_1, s_2, ...\right) không thể là tổng reward của tất cả trạng thái. Nói cách khác:

U\left(s_0, s_1, s_2,...\right) \neq \sum_{t=0}^\infty R\left(s_t\right)

Vì sao như vậy?

Tất cả là vì giả sử Infinite Horizons. Vì chuỗi trạng thái có thể kéo dài vô tận nên tổng của các reward rất có khả năng diverge, và trở thành infinity. Khi đó ta không thể so sánh chuỗi trạng thái này có tốt hơn chuỗi khác hay không (không thoả điều kiện Utility of Sequence), vì cả hai đều là infinity.

Nói cách khác, nếu bạn bất tử thì việc mỗi ngày bạn làm ra bao nhiêu tiền cũng không còn quan trọng gì nữa.

Ta sẽ xem ví dụ sau:

Giả sử bạn là Cuội, và bất tử. Hằng Nga một ngày nọ buồn tình Trư Bát Giới, cho Cuội 2 lựa chọn:

  1. Ngày nào Hằng Nga cũng cấp cho Cuội 1$ tiền Mặt trăng, không bao giờ dừng lại (vì Cuội bất tử)
  2. Ngày nào cũng cấp cho 2$ tiền Mặt trăng

Nếu là Cuội thì bạn chọn option nào?

Thật ra cả 2 đều như nhau, vì 1 + 1 + 1 + … và 2 + 2 + 2 + … đều là infinity (trừ khi chọn Hằng Nga).

Đương nhiên nếu Cuội không bất tử, thì lựa chọn 2 chắc chắn tốt hơn, nhưng trong ngữ cảnh infinite series thì intuition về các phép toán mà ta đã quen trong ngữ cảnh finite thường không còn đúng nữa, dẫn đến rất nhiều kết quả bất ngờ kiểu như thế này.

Vậy giờ tổng của chuỗi vô hạn thì sẽ có khả năng diverge, thanh niên ham học phải làm sao?

(more…)

[RL1] Markov Decision Process – Introduction

[RL1] Markov Decision process – Introduction
[RL2a] Markov Decision Process – Discounted Reward
[RL2b] Markov Decision Process – Bellman equation
[RL2c] Markov Decision Process – Solving Bellman equation
[RL3] Q-Learning
[RL4] Game Theory – overview

Đây là bài đầu tiên trong chuỗi bài về Reinforcement Learning. Đáng lẽ sẽ viết về Bayesian Optimization trước khi chuyển qua đề tài mới, nhưng vì Reinforcement Learning hay quá nên không kiềm chế được. Theo kế hoạch thì sẽ cố gắng viết 4 bài trước, sau đó có thể sẽ viết thêm về Game Theory, hoặc Deep Reinforcement Learning, tuỳ tình hình học bài tới đâu. Bayesian Optimization sẽ viết sau, khi nào có thời gian.

Cách dễ nhất để nghĩ về Reinforcement Learning chắc là ứng dụng điều khiển robot. Đại loại là một robot (gọi chung là agent) hoạt động trong một thế giới gồm N trạng thái. Có thể hiểu mỗi trạng thái là một vị trí mà robot có thể đi tới. Trong số các trạng thái này, có một số trạng thái đặc biệt mà khi robot đi vào đó thì trò chơi kết thúc: robot tìm được báu vật, hoặc bị giết. Tại mỗi trạng thái, robot sẽ được tặng một phần thưởng nhỏ nào đó (gọi là reward), riêng các trạng thái đặc biệt thì thường có reward lớn hơn. Tại mỗi trạng thái, robot phải quyết định thực hiện 1 hành động (action) nào đó trong số các hành động mà nó biết (đi qua trái, đi qua phải, đi thẳng v.v…), sao cho chuỗi các trạng thái này sẽ dẫn nó tới trạng thái có phần thưởng cao nhất (tìm được kho báu). Nói cách khác, bài toán đặt ra là xác định chuỗi hành động để robot tìm được kho báu.

(more…)

Monte Carlo và Markov Chain Monte Carlo

The devil is in the details, hoá ra ứng dụng Bayesian Optimization trong thực tế khá là phức tạp. Vậy nên bài này sẽ ôn lại kiến thức về phương pháp Monte Carlo và MCMC. Vẫn chưa biết đến khi nào mới có thể viết một bài tổng hợp về Bayesian Optimization.

1. Luật mạnh số lớn (Strong law of large numbers – SLLN)

Luật mạnh số lớn rất đơn giản: khi N càng lớn thì trung bình mẫu hội tụ gần như chắc chắn (almost surely converge) về kì vọng:

\displaystyle \frac{1}{N}\sum_{i=1}^N x_i \overset{a.s.}{\rightarrow} \mu khi N \rightarrow \infty

với điều kiện là các mẫu x_i phải là i.i.d.

Mặt khác, ta biết rằng nếu biến ngẫu nhiên X tuân theo phân phối xác suất f\left(x\right), và g\left(X\right) là một hàm theo X, thì kì vọng của g\left(X\right) được tính là:

\displaystyle E\left[g\left(X\right)\right] = \int g\left(x\right)f\left(x\right)dx

Vậy nên theo luật mạnh số lớn, khi số mẫu càng lớn thì giá trị trung bình mẫu của g\left(X\right) sẽ hội tụ về kì vọng:

\displaystyle \left(\frac{1}{N}\sum_{i=1}^N g\left(X_i\right)\right) \overset{a.s.}{\rightarrow} \left(\int g\left(x\right)f\left(x\right)dx\right) khi N \rightarrow \infty    (1)

Như vậy khi tích phân ở bên phải không tính được, ta có thể tính xấp xỉ nó bằng cách lấy thật nhiều mẫu X_i và tính biểu thức ở bên trái. Đây là tư tưởng cơ bản của phương pháp Monte Carlo, như sẽ trình bày sau đây.

2. Phương pháp Monte Carlo: Importance Sampling

Hầu hết các mô hình máy học có giám sát (supervised ML models) đều cố gắng mô hình hoá xác suất likelihood p\left(y\vert x; \theta\right), trong đó \theta là các tham số trong mô hình. Như trong bài trước, ta biết rằng trong cách tiếp cận Bayesian thì tham số \theta tuân theo phân phối tiền nghiệm p\left(\theta\right), và ta sẽ quan tâm đến xác suất hậu nghiệm (posterior):

\displaystyle p\left(\theta\vert x, y\right) = \frac{p\left(y\vert x, \theta\right)p\left(\theta\right)}{\int p\left(y\vert x, \theta\right)p\left(\theta\right)d\theta} = \frac{1}{Z}p\left(y\vert x, \theta\right)p\left(\theta\right)    (2)

Vấn đề là

Z = \displaystyle \int p\left(y\vert x, \theta\right)p\left(\theta\right)d\theta     (3)

là tích phân trên toàn miền xác định của \theta, và nói chung là khó chịu. Vậy nên ta không thể tính chính xác xác suất hậu nghiệm này được.

Cái mẹo chủ yếu của phương pháp Monte Carlo là ta sẽ nhân và chia công thức (3) cho một đại lượng q\left(\theta\right):

\displaystyle Z = \int p\left(y\vert x, \theta\right)p\left(\theta\right)d\theta = \int \frac{p\left(y \vert x, \theta\right)p\left(\theta\right)}{q\left(\theta\right)}q\left(\theta\right)d\theta =\int \omega\left(\theta\right) q\left(\theta\right)d\theta

Để ý rằng nếu q\left(\theta\right) là phân phối của \theta thì tích phân ở trên chính là kì vọng của \omega\left(\theta\right).

Bây giờ nếu ta lấy mẫu \theta^{\left(i\right)} \sim q\left(\theta\right), thì theo luật mạnh số lớn (1), khi N càng lớn thì trung bình mẫu hội tụ về kì vọng:

\displaystyle \left(\frac{1}{N}\sum_{i=1}^N \omega\left(\theta^{\left(i\right)}\right)\right) \overset{a.s.}{\rightarrow} \left(\int \omega\left(\theta\right) q\left(\theta\right)d\theta\right) khi N \rightarrow \infty    (4)

Với công thức này, ta có thể lấy mẫu để tính xác suất hậu nghiệm của tham số \theta trong (2).

Tuy nhiên trong thực tế ta hay phải làm prediction, tức là cho tập huấn luyện D = \left\{x_i, y_i\right\}_{i=1}^t và một mẫu input x_{t+1}, ta muốn mô hình hoá xác suất p\left(y_{t+1} \vert D, x_{t+1}\right). Ta viết như sau:

\displaystyle \begin{array}{rl} p\left(y_{t+1} \vert D, x_{t+1}\right) & \displaystyle = \int p\left(y_{t+1} \vert x_{t+1}, \theta\right) p\left(\theta \vert D \right)d\theta \\ & \displaystyle = \int p\left(y_{t+1} \vert x_{t+1}, \theta\right) \frac{p\left(D \vert \theta \right) p\left(\theta\right)}{p\left(D\right)}d\theta \\ & \displaystyle = \frac{1}{p\left(D\right)} \int p\left(y_{t+1} \vert x_{t+1}, \theta \right) p\left(D \vert \theta\right) p\left(\theta\right) d\theta \\ & = \frac{\displaystyle \int p\left(y_{t+1} \vert x_{t+1}, \theta \right) p\left(D \vert \theta\right) p\left(\theta\right) \frac{q\left(\theta\right)}{q\left(\theta\right)} d\theta}{\displaystyle \int p\left(D \vert \theta\right) p\left(\theta\right) \frac{q\left(\theta\right)}{q\left(\theta\right)} d\theta } \\ & = \frac{\displaystyle \int p\left(y_{t+1} \vert x_{t+1}, \theta \right) \omega\left(\theta\right) q\left(\theta\right) d\theta}{\displaystyle \int \omega\left(\theta\right) q\left(\theta\right) d\theta } \end{array}

Trong đó \omega\left(\theta\right) = \frac{p\left(D \vert \theta \right)p\left(\theta\right)}{q\left(\theta\right)}.

Áp dụng (4) ta có:

\displaystyle \begin{array}{rl} p\left(y_{t+1} \vert D, x_{t+1}\right) & = \frac{\displaystyle \int p\left(y_{t+1} \vert x_{t+1}, \theta \right) \omega\left(\theta\right) q\left(\theta\right) d\theta}{\displaystyle \int \omega\left(\theta\right) q\left(\theta\right) d\theta } \\ & \approx \frac{\displaystyle \frac{1}{N}\sum_i p\left(y_{t+1}\vert x_{t+1}, \theta^{\left(i\right)}\right)\omega\left(\theta^{\left(i\right)}\right)}{\displaystyle \frac{1}{N}\sum_j \omega\left(\theta^{\left(j\right)}\right)} \\ & \displaystyle \approx \sum_i \tilde{\omega}\left(\theta^{\left(i\right)}\right) p\left(y_{t+1}\vert x_{t+1}, \theta^{\left(i\right)}\right)\end{array}

với \tilde{\omega}\left(\theta^{\left(i\right)}\right) = \frac{\omega\left(\theta^{\left(i\right)}\right)}{\sum_j\omega\left(\theta^{\left(j\right)}\right)}.

q\left(\theta\right) là phân phối xác suất do ta “bịa” ra, ta sẽ chọn q\left(\theta\right) sao cho dễ lấy mẫu. Như vậy ta có thể lấy thật nhiều mẫu \theta_i, sau đó dùng công thức trên để xấp xỉ xác suất hậu nghiệm.

Điều tricky là để luật mạnh số lớn áp dụng được thì các mẫu \theta_i phải là i.i.d. Hơn nữa nếu q\left(\theta\right) càng gần p\left(D\vert \theta\right) p\left(\theta\right) thì chất lượng lấy mẫu sẽ càng cao.

3. Markov Chain Monte Carlo

Ý tưởng chính là ta sẽ “cơ cấu” một chuỗi Markov để lấy mẫu từ p\left(D\vert \theta\right) p\left(\theta\right), đồng thời bằng cách đi theo chuỗi Markov ta sẽ navigate qua tất cả các region quan trọng của phân phối này.

Hai thuật toán quan trọng của MCMC là Metropolis-Hasting và Gibbs sampling, sẽ được trình bày trong một bài khác, khi có dịp.