vietnamese

[Old but gold] RBM 4: Contrastive Divergence in training RBM and practical applications

RBM 1: Hopfield nets and Boltzmann Machines
RBM 2: Model definition and training of RBMs
RBM 3: Contrastive Divergence
RBM 4: Contrastive Divergence in training RBMs and practical applications

Chuỗi bài về RBM viết cách đây hơn 3 năm nhưng chưa bao giờ viết được phần cuối, một phần vì lười, nhưng chủ yếu là do RBM không còn là đề tài quan trọng trong Machine Learning nữa (sẽ nói thêm ở phần cuối). Tuy nhiên vì hôm trước có bạn hỏi nên sẽ viết nốt phần này.

Chính vì RBM không còn là đề tài “hot”, nên nếu bạn nào ở VN đang muốn nghiên cứu về đề tài này thì nên cân nhắc kĩ. Có một số đề tài khác thú vị hơn, có nhiều ý tưởng để làm hơn, và dễ xuất bản hơn là RBM.

Tất nhiên nếu như bạn muốn học RBM để cho biết, hoặc là để đi dạy lại người khác, thì RBM vẫn là một mô hình thú vị và đáng học. “Lịch sử” ngành Deep Learning cho thấy có những thứ 20-30 năm sau lại trở nên thịnh hành, nên biết đâu 10-20 năm nữa RBM lại trở thành mainstream, nhất là khi RBM có lẽ là mô hình generative dễ hiểu nhất (nếu không tính tới GMM hay K-means).

Cuối cùng, nếu bạn đang phải làm luận văn tốt nghiệp và thầy của bạn muốn bạn làm về RBM, thì không cần suy nghĩ nhiều. Viết luận văn và tốt nghiệp là những lí do hoàn toàn chính đáng để học RBM, và tốt nghiệp xong thì không phải ai cũng muốn đi làm nghiên cứu về Machine Learning (nếu viết luận văn thì nhớ cite blog này là được  😉 ).

Nói như vậy rồi, thì đây là RBM.

(more…)

[RL3c] TD(lambda) rule

[RL3a] Reinforcement Learning context
[RL3b] Temporal Difference Learning – intuition
[RL3c] TD(lambda) rule

Trong bài trước, ta đã đi đến công thức cập nhật giá trị của trạng thái như sau:

\displaystyle V_T(s) = V_{T-1}(s) + \alpha_T\left(R_T(s) - V_{T-1}(s)\right)

trong đó R_T(s) là reward tức thời (immediate reward) của trạng thái s tại thời điểm T. Trong thực tế, tại thời điểm T, agent thực hiện hành động s để tiến tới trạng thái s’ và thu được reward là r: s \overset{+r}{\longrightarrow} s'. Do đó R_T(s) là:

R_T(s) = r + \gamma V_{T-1}(s').

Nhận xét này dẫn ta đến thuật toán TD(\lambda) như sau:

Episode T
  for all s: e(s) = 0;  V_T(s) = V_{T-1}(s)
  After step t: s_{t-1}\overset{r_t}{\longrightarrow} s_t
    e(s_{t-1}) = e(s_{t-1}) + 1
    for all s:
      \displaystyle V_T(s) = V_T(s) + \alpha_T\left[r_t + \gamma V_{T-1}(s_t) - V_{T-1}(s_{t-1})\right]e(s)
      e(s) = \lambda\gamma e(s)

Ở trung tâm thuật toán này là phương trình cập nhật như trên. \gamma là discounted factor của MDP, \lambda là hằng số của thuật toán TD(\lambda), có giá trị trong khoảng [0, 1]. \alpha_T = \frac{1}{T} là learning rate.

Như vậy sử dụng thuật toán này, ta có thể ước lượng giá trị của tất cả các trạng thái, chỉ dựa vào các episodes trong tập huấn luyện. Thuật toán này được cài đặt ở đây.

\lambda là một tham số thú vị. Ta có thể thấy điều này nếu khai triển công thức ở trên theo thời gian (unroll):

E_1: V(s_t) = V(s_t) + \alpha_T\left[r_{t+1} + \gamma V(s_{t+1}) - V(s_t)\right]

E_2: V(s_t) = V(s_t) + \alpha_T\left[r_{t+1} + \gamma r_{t+2} + \gamma^2 V(s_{t+2}) - V(s_t)\right]

E_\infty: V(s_t) = V(s_t) + \alpha_T\left[r_{t+1} + ... + \gamma^{k-1} r_{t+k} + \gamma^k V(s_{t+k}) + ... - V(s_t)\right]

Việc khai triển này cũng tương tự như cách mà ta khai triển phương trình Bellman trong bài trước. Hơn nữa, cứ sau mỗi bước cập nhật, ta lại tăng e(s) lên một lượng \lambda. Thành ra có thể hiểu \lambda thể hiện mức độ tin tưởng của ta vào giá trị của s tại thời điểm gần nhất (\lambda = 0) hay rất xa trong quá khứ (\lambda = 1). Bất kì giá trị nào của \lambda nằm giữa 0 và 1 là sự trade-off giữa 2 thái cực trên. Thông thường giá trị của \lambda trong khoảng 0.5-0.7.

Ghi chú về learning rate

Nhớ rằng ta có công thức cập nhật \displaystyle V_T(s) = V_{T-1}(s) + \alpha_T\left(R_T(s) - V_{T-1}(s)\right), và định nghĩa learning rate \alpha_T = \frac{1}{T}. Với learning rate định nghĩa như trên thì ta đảm bảo rằng \lim_{T \rightarrow \infty} V_T(s) = V(s), nghĩa là V_T(s) hội tụ về giá trị “thật” V(s) khi có nhiều episode.

Rõ ràng tính chất hội tụ trên là vô cùng quan trọng, nếu không thì toàn bộ những lí thuyết ta học đều vô nghĩa.

Nhưng hoá ra không phải chỉ có mỗi learning rate \frac{1}{T} là thoả mãn yêu cầu trên. Thực tế thì bất kì learning rate nào thoả mãn 2 điều kiện sau:

\displaystyle \sum_T \alpha_T = \infty
\displaystyle \sum_T \alpha_T^2 < \infty

thì đều khiến cho chuỗi V_T(s) hội tụ.

Thành ra \frac{1}{T}\frac{1}{T^{2/3}} thoả điều kiện trên, trong khi \frac{1}{100}\frac{1}{T^2} hay \frac{1}{T^{1/2}} thì không thoả.

Nếu có dịp ta sẽ trở lại với tính chất này, bằng khái niệm contraction mapping.

 

[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…)

[RL3b] Temporal Difference Learning – intuition

[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
[RL3a] Reinforcement Learning context
[RL3b] Temporal Difference Learning – intuition

Như đã nói trong bài trước, ta sẽ tập trung vào Model-free RL, trong đó ta muốn học trực tiếp giá trị của các trạng thái V(s) từ tập huấn luyện <s, a, r>^*.

Cụ thể, tập huấn luyện sẽ gồm nhiều episodes, mỗi episode là một chuỗi s_1 \overset{r_1}{\longrightarrow} s_2 \overset{r_2}{\longrightarrow} s_3 \longrightarrow ... \longrightarrow s_F mà agent thực hiện cho đến khi kết thúc cuộc đời của nó. Chẳng hạn nếu là chơi cờ thì tập huấn luyện sẽ gồm nhiều trận đấu, mỗi trận là một chuỗi các nước đi. Từ tập huấn luyện này, ta tìm cách ước lượng V(s).

Tại sao lại ước lượng V(s), khi trong bài trước ta nói rằng Model-free RL tìm cách ước lượng giá trị Q(s, a)? Nhắc lại rằng ta có thể tính Q(s, a) từ V(s), R(s, a)T(s, a, s'), như đã nói trong bài này, mà R(s, a)T(s, a, s') có thể ước lượng một cách đơn giản từ tập huấn luyện (chẳng hạn dùng maximum likelihood), nên một khi có V(s) ta hoàn toàn có thể tính Q(s, a) nếu muốn. Tuy nhiên mục tiêu cuối cùng của RL vẫn là tìm ra policy tối ưu, chứ không phải tìm V(s) hay Q(s,a), mà từ V(s) vẫn có thể dùng \arg\max để tìm policy tối ưu, thành ra V(s) hay Q(s, a) cũng không còn quan trọng nữa.

Mọi chuyện sẽ dễ dàng hơn khi ta xem ví dụ sau. Cho một MDP với mô hình chuyển trạng thái T và hàm reward R như sau:

markov_states

Mô hình này có 6 trạng thái. Khi chuyển từ s_1 sang s_3 thì reward nhận được là +1, nghĩa là R(s_1, a) = +1. Tương tự như vậy cho các trạng thái khác. s_F là trạng thái cuối cùng, trò chơi kết thúc khi agent đi đến trạng thái này.

(more…)

[RL3a] Reinforcement Learning context

[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
[RL3a] Reinforcement Learning context

Lại nói tiếp chuyện Học củng cố. Trong các bài trước, ta đã xem xét mô hình Markov Decision Process (MDP) và các phương pháp giải MDP. Ta cũng đã nói qua về hàm Q-function, hàm quan trọng nhất trong MDP, có thể dùng để biểu diễn trạng thái của agent. Vì hàm này quan trọng nên viết lại ra đây:

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

Đương nhiên nếu ta biết trước mô hình (ma trận chuyển trạng thái T và hàm reward R), thì mọi chuyện không còn gì để bàn. Tưởng tượng là một agent, được thả vào trong môi trường lạ, agent này sẽ thực hiện một loạt các hành động a, rơi vào các trạng thái s và nhận được reward r. Nói cách khác, agent sẽ chỉ nhận được chuỗi <s_1, a_1, r_1>, <s_2, a_2, r_2>, ... và nhiệm vụ của nó là phải tìm ra policy \pi sao cho tối đa hoá expected reward. Reinforcement Learning, do đó, là thuật toán giúp agent tìm ra policy tối ưu, khi nó quan sát được chuỗi <s,a,r>*.

Có nhiều cách để làm việc này , nhưng nhìn chung có 3 cách sau:

untitled-diagram

  1. Model-based RL: trong cách này, trước tiên ta phải học được mô hình của MDP từ chuỗi <s,a,r>*, chẳng hạn T có thể là maximum likelihood estimation của các trạng thái, R là expected reward của mỗi trạng thái trong training set. Sau đó dùng các thuật toán trong phần trước để giải MDP và tìm ra policy tối ưu.
    Lưu ý là trong cách làm này, ta phải tìm cách ước lượng MDP.
  2. Value-function-based RL: ta tìm cách học trực tiếp hàm Q-function (nôm na là expected reward của agent khi ở trạng thái s và thực hiện hành động a), sau đó tìm policy tối ưu.
  3. Policy Search: trong cách này, ta trực tiếp tìm policy tối ưu từ training set, thay vì phải mô hình hoá Q-function.

Rõ ràng đi từ 1 đến 3 thì yêu cầu của thuật toán càng ngày càng “khó”, vì rõ ràng trong Policy Search thì rất khó để ước lượng trực tiếp policy tối ưu từ training set. Ta nói rằng Model-based RL thì more “supervised”.

Trong thực tế người ta chủ yếu tập trung vào Model-free RL. Chẳng hạn ta sẽ bàn về TD(\lambda) trong phần sau.

Truyện ngắn Nguyễn Huy Thiệp

Hồi xưa đi học, phân tích truyện ngắn là thứ mình thấy khó viết nhất. Giờ nhìn lại, thể loại này vẫn khó như vậy, nhưng vì giờ đã quá tuổi viết văn tới hơn chục năm, nên mình sẽ cố review cả vài truyện cùng lúc. Hi vọng là văn chương, sau hơn chục năm, không quá khó ngửi.

khong_co_vua__nguyen_huy_thiep

Tìm thấy quyển này cách đây vài năm, lúc đang lang thang trong mấy tiệm sách ở SG (đi mua sách tiếng Việt là chuyện mình hay làm nhất mỗi khi về nhà). Vốn ít đọc văn Việt Nam sau 1975, trừ vài quyển của Bảo Ninh, Chu Lai… nên cảm giác chung của mình là Văn thời này khá tẻ nhạt, nếu không viết về chiến tranh thì là văn tuyên truyền. Khi đất nước oằn mình đau khổ, lại còn bị đóng khung giáo điều, thì văn chương khó mà cất cánh được.

Với Nguyễn Huy Thiệp, đây là quyển đầu tiên mình đọc. Mãi tới gần đây mới đọc xong, và nói chung là rất ấn tượng. Lần tới về VN chắc sẽ tìm đọc Tướng về hưu.

Truyện ngắn nói chung là khó viết, và cũng không dễ đọc. Trong quyển này, có những truyện thực chất là tập hợp của vài truyện rất ngắn, nên mình đọc khá chậm.

Nhìn chung về nghệ thuật, mình hơi bối rối vì không biết nên đặt tác giả vào đâu. Có những truyện viết rất chắc tay, thủ pháp điêu luyện, kết cấu chắc chắn; nhưng cũng có những truyện hơi lỏng lẻo, hay thòng vào những câu triết lí đôi chút gượng gạo.

Mặc dù vậy, vẫn có thể nhận ra vài nét lớn trong văn chương Nguyễn Huy Thiệp từ quyển này.

(more…)

Deep Generative models – part 2: GSN, GAN and Ladder nets

Trong bài trước, ta đã nói vắn tắt về bài toán Generative Modeling trong Deep Learning. Bài này sẽ nói tiếp chuyện này một cách formal hơn, đồng thời điểm qua một số phương pháp đang “thịnh hành” trong cộng đồng gần đây. Lưu ý rằng Generative Modeling vẫn là một bài toán chưa được giải quyết trọn vẹn, thành ra có thể có vài cách tiếp cận khác không được điểm danh ở đây, và đa số các cách tiếp cận nói đến trong bài này đều vẫn còn đang ở trong tình trạng đang được nghiên cứu.

Bài toán ultimate trong học máy thống kê có lẽ là bài toán này: cho một tập mẫu \left\{x_i \right\}_{i=1}^N được lấy từ phân phối xác suất P\left(X\right) chưa biết. Xây dựng mô hình để “bắt chước” phân phối P\left(X\right) này.

Bài toán này khó vì ta giả sử rằng ta không biết gì về P\left(X\right), ngoại trừ một tập mẫu hữu hạn của nó. Hơn nữa, trong nhiều trường hợp, P\left(X\right) có thể rất phức tạp, chẳng hạn như mô hình sinh ra tất cả các ảnh RGB chụp phong cảnh tự nhiên, hay là ảnh X-quang chụp phổi bị ung thư, mô hình phái sinh ra thơ Shakespeare, v.v…. Trong những trường hợp như vậy, mô hình hoá trực tiếp P\left(X\right) có thể rất khó.

Mô hình mà mình nghĩ là “đơn giản” nhất trong Deep Learning để giải quyết bài toán này có lẽ là Sum-Product Networks (SPN). Ý tưởng chính của SPN là thiết kế mạng sao cho nó tractable sẵn, vì vậy huấn luyện SPN không cần phải quan tâm đến partition fuction, vì tính partition fuction trong SPN lúc nào cũng tractable (by construction). Mặc dù ý tưởng này rất tốt, nhưng một vài kết quả thực nghiệm cho thấy chính vì ràng buộc này mà có thể lớp hàm SPN có thể xấp xỉ không đủ lớn để mô hình hoá các phân phối phức tạp trong thực tế.

Ngoài SPN, một mô hình khác có vẻ hứa hẹn sẽ giải quyết được vấn đề này là Autoencoders, nhất là thể loại Denoising Autoencoder (DAE). DAE là mô hình rất đơn giản với chỉ một hidden layer. Đầu tiên ta chọn một phân phối nhiễu \mathcal{C}\left(\tilde{X}\vert X\right). Với mỗi mẫu “sạch” X từ phân phối P\left(X\right), ta áp dụng mô hình nhiễu, chẳng hạn nếu X là ảnh thì ta có thể thêm nhiễu Gaussian vào để tạo thành bản “lỗi” \tilde{X}. Sau đó ta đưa \tilde{X} vào cho DAE và huấn luyện để nó làm sạch nhiễu cho ta mẫu X ban đầu.

Nói theo ngôn ngữ function approximation thì DAE thực chất được huấn luyện để xấp xỉ phân phối có điều kiện P\left(X \vert \tilde{X}\right) (gọi là reconstruction function, vì đây là hàm sẽ cho ta phiên bản sạch X từ bản nhiễu \tilde{X}). Người ta cho rằng xấp xỉ P\left(X \vert \tilde{X}\right) dễ hơn nhiều so với xấp xỉ P\left(X\right), vì về cơ bản P\left(X \vert \tilde{X}\right) sẽ gồm ít mode hơn so với P\left(X\right). (more…)