Restricted Boltzmann Machine

{jcomments on}

Author: Vũ Nguyễn Minh Huy

Published date: 29/1/2022

1. GIỚI THIỆU:

Máy Boltzmann giới hạn (Restricted Boltzman machine, viết tắt là RBM) là một biến thể của máy Boltzmann giới hạn được phát triển bởi Paul Smolensky năm 1986 với tên Harmonium. Giữa năm 2000, Geoffrey Hinton và cộng sự đã phát minh ra giải thuật học nhanh cho mô hình, giúp mô hình trở nên phổ biến và được ứng dụng thực tế. Máy Boltzmann giới hạn được ứng dụng trong nhiều bài toán như Dimensionality reduction, Collaborative Filtering, Feature Learning, Regression Classification và Topic Modeling. Trong bài viết này, tôi sẽ trình bày cách hoạt động của RBM.

Trước khi bắt đầu nội dung, tôi xin cảm ơn anh Nguyễn Tấn Đạt và Team học thuật đã góp ý bài viết. Trong đó, đặc biệt cảm ơn anh Đạt đã giúp tôi hoàn thiện không chỉ về nội dung mà cách tôi diễn đạt câu từ, cách trình bày. Mặc dù vậy, bài viết vẫn có thể gặp những sai sót về nội dung, ban đọc góp ý có thể gửi qua mail This email address is being protected from spambots. You need JavaScript enabled to view it.. 

Nội dung bài viết được trình bày như sau:

• Mô hình sinh và mô hình dựa vào năng lượng
• Mô hình máy Bolzman giới hạn
  • Hàm tối ưu và đạo hàm
  • Gibbs Sampling
  • Áp dụng Gibbs sampling
  • K-Contrastive Divergence
• Tổng kết
• Tham khảo.

 

2. MÔ HÌNH SINH VÀ MÔ HÌNH DỰA VÀO NĂNG LƯỢNG:

Các mô hình học máy có thể được phân thành hai nhóm - Mô hình phân biệt (discriminative model) và mô hình sinh (generative model). Nói một cách đơn giản, mô hình phân biệt có thể thực hiện một dự đoán trên mẫu dữ liệu chưa quan sát bao giờ, được áp dụng cho bài toán phân loại lẫn bài toán hồi quy. Ngược lại, mô hình sinh tập trung vào mô hình hóa phân phối của dữ liệu, trả về một giá trị xác suất trên mẫu dữ liệu mới - mẫu dữ liệu này giống với tập quan sát thế nào.

Hình 1: Minh hoạ mô hình phân biệt (Trái) và mô hình sinh (phải) Tham khảo [8]. Trong ví dụ trên, cho mẫu dữ liệu mới, mô hình phân biệt có thể dự đoán mẫu này thuộc nhóm xanh, hay nhóm đỏ dựa trên đường thẳng nét đứt (Boundary). Ngược lại, mô hình sinh mô hình hóa phân phối tập dự liệu (hai hình oval), giá trị xác suất trả về biểu diễn mẫu dữ liệu mới giống (nằm bên trong, nằm ngoài, gần hay xa) như thế nào.

Mô hình dựa vào năng lượng (Energy-based model) là mô hình cụ thể của mô hình sinh có nguồn gốc từ vật lý thống kế. Thay vì phân loại x thành y, mô hình cố gắng dự đoán xem cặp \((x,y)\) có hợp với nhau hay không. Nói các khác, tìm \(y\) tương thích với x. Chúng ta chuyển bài toán về dạng tìm \(y\) sao cho giá trị trả về \(F(x,y)\) là thấp, với \(F\) là hàm năng lượng. Ví dụ:

• Có phải \(y\) là một ảnh có độ phân giải cao chính xác của \(x\) không?
• Có phải văn bản A là một bản dịch thuật từ B hay không?

Chúng ta định nghĩa hàm năng lượng \(F: X \times Y \rightarrow R\), trong đó \(F(x,y)\) biểu diễn mức độ phụ thuộc lẫn nhau giựa cặp \((x,y)\). Cách để suy luận ra \(y\) dựa vào công thức sau:

\[\begin{align} \widetilde{y} = argmin_y \{F(x,y)\} \end{align}\]

3. MÔ HÌNH MÁY BOLTZMANN GIỚI HẠN

Máy Boltzmann giới hạn (Restricted Boltzmann machine, viết tắt là RBM) là một mô hình dựa vào năng lượng, có nguồn gốc từ máy Boltzmann [9]. Mô hình bao gồm tầng nhìn thấy (visible layer) có \(I\) nút tương ứng với các scalar của vector \(\mathbf{v} = [v_1, v_2, ...,v_{I}]\), \(v_i\in\{0,1\}\), và tầng ẩn (hidden layer) có \(J\) nút tương ứng với các scalar của vector \(\mathbf{h} = [h_1, h_2, ..., h_J]\), \(h_j \in \{0, 1\}\). Khác với máy Boltzman, chỉ có các nút không cùng một tầng có kết nối với nhau. Kết nối giữa hai nút là duy nhất, và chỉ có 1 trọng số \(W_{ij}\) dùng chung cho hai chiều.

Hinh 2: Kiến trúc mô hình máy Boltzman giới hạn. Mô hình này có hai tầng. Tầng thấp hơn gọi là tầng thấy được, là tầng nhận dữ liệu đầu vào. Tầng trên là tầng ẩn, có chức năng trích xuất đặc trưng thông tin truyền từ tầng thấy được. Mỗi nút trên mỗi tầng được kết nối một chiều với độ lệch Số nút tầng thấy được và tầng ẩn hông nhất thiết bằng nhau. Thông tin truyền từ tầng thấy được sang tầng ẩn gọi là mã hóa, ngược lại là giải mã. Tham khảo tại [2]

Quan sát hình 2, RBM hoạt động dựa trên mô thức mã hóa giải mã (encoder-decoder paradigm). Bạn đọc hiểu mô hình này qua ví dụ hình 3:

Trong ví dụ này, người chơi 1 và 2 đóng vai trò lần lượt là Encoder, Decoder, và hình ảnh chính là trạng thái ẩn - giá trị của biến ẩn. Encoder phải chuyển đầu vào thành một dữ liệu có dạng cụ thể (ví dụ hình ảnh) và mang thông tin về dữ liệu đầu vào (Hình con thỏ). Thông thường, biến ẩn cần mang những giá trị cô đọng nhất từ dữ liệu đầu vào. Giả sử bạn là người chơi 1 và từ được lấy không phải là Rabbit mà là câu phức tạp “Con thỏ trắng nhỏ ăn cỏ khô trên cánh đồng miền quê nước Việt” thì bạn sẽ vẽ như thế nào?

Vì là mô hình dựa vào năng lượng, hàm năng lượng của RBM được định nghĩa như sau:

\[\begin{align}E(\mathbf{v, h})=-\sum_{i=1}^Lc_iv_i-\sum_{j=1}^Jb_jh_j -\sum_{i,j=1}^{L,J}W_{ji}v_ih_j\end{align}\]

Trong đó, c_i,b_j lần lượt là độ lệch của nút thấy được thứ i và nút ẩn thứ j . \bold{c} \in R^I, \bold{b} \in R^J W_{ji} là trọng số nối từ nút ẩn thứ \(j\) tới nút thấy được thứ \(i\), \(\mathbf{W} \in R^{J\times I}\)

Tương tự như huấn luyện các mô hình học máy khác, chúng ta cần cập nhật trọng số mô hình để tối ưu hóa hàm mục tiêu. Phương pháp cập nhật thường sử dụng là gradient descent (nếu tìm minimum) hoặc gradient ascent (nếu tìm maximum). Anh Vũ Khắc Tiệp có bài viết minh họa chi tiết về phương pháp này . Bạn đọc chưa biết có thể đọc thêm tại [14].Trong phần tiếp theo, tôi sẽ trình bày hàm mục tiêu và cách áp dụng gradient ascent để tối ưu hàm mục tiêu này.

3.1 Xây dựng hàm tối ưu và đạo hàm:

Mô hình máy Boltzman giới hạn có hàm mục tiêu như sau:

\[argmax_\theta P(\mathbf{v}|\theta)\]

Trong đó, \(\theta\) làm tham số mô hình, bao gồm độ lệch \(\mathbf{c, b}\) và trọng số \(\mathbf{W}\). Hàm trên thường gọi là hàm likelihood.

Tối ưu hóa hàm likelihood tương đương với việc tối ưu hóa hàm log-likelihood, vì hàm log là hàm đồng biến, log hàm số giúp hạn việc giá trị quá lớn:

\[\begin{align}argmax_\theta \log P(\mathbf{v}|\theta) \end{align}\]

Trong đó, \(P(\mathbf{v}|\theta)\) được tính như sau:

\[\begin{align}P(\mathbf{v}|\theta) &= \frac{1}{Z}\times \sum _he^{-E(\mathbf{v,h})} \\ Z &= \sum_{\mathbf{v,h}}e^{-E(\mathbf{v,h})} \end{align}\]

Trong đó, \(E\) là hàm năng lượng, phân phối của \(P(\mathbf{v}|\theta)\) là phân phối Gibbs-Bolzmann.

Thay \(P(\mathbf{v}|\theta)\) trong (3) bởi (4), (5), chúng ta có:

\[\begin{align}argmax_\theta \log p(\mathbf{v}|\theta) = argmax_\theta \log(\sum_\mathbf{h}e^{-E(\mathbf{v,h})}) - \log(\sum_{\mathbf{v,h}}e^{-E(\mathbf{v, h})}) \end{align}\]

Đạo hàm (6) theo \theta:

\[\begin{align}\frac{\partial \log p(\mathbf{v}|\theta)}{\partial \theta} = \underbrace{-\sum_{\mathbf{h}}p(\mathbf{h|v)}\frac{\partial E(\mathbf{v,h})}{\partial \theta}}_{\text{positive phase}} + \underbrace{\sum_{\mathbf{v,h}}p(\mathbf{v,h})\frac{\partial E(\mathbf{v,h})}{\partial \theta}}_{\text{negative phase}} \end{align}\]

Bạn đọc có thể tự đạo hàm để có được (7). Đây có thể coi là bài tập nhỏ cho bạn đọc (hoặc ban có thể tham khảo cách giải ở đây [2]).

Trong đó, \(p(\mathbf{h|v) }\) và \(p(\mathbf{v|h})\) được tính như sau:

\[\begin{align}p(\mathbf{v}|\mathbf{h})= \prod_i^I p(v_i=1|\mathbf{h})=\prod_i^I\sigma(c_i+\sum_{j=1}^JW_{ji}h_j) \\ p(\mathbf{h}|\mathbf{v})= \prod_i^I p(h_j=1|\mathbf{v})=\prod_j^J\sigma(b_j+\sum_{i=1}^IW_{ji}v_i) \end{align}\]

Đạo hàm \(\frac{\partial E(\mathbf{v,h})}{\partial \theta}\) có thể dễ dạng tính toán. Do đó, chúng ta đã có đạo hàm hàm tối ưu theo tham số và có thể cập nhật trọng số mô hình theo phương pháp gradient ascent (vì tối đa hóa hàm likelihood). Tiếc thay, \(p(\mathbf{v,h}) = \frac{1}{Z}\times \sum _\mathbf{h} e^{-E(\mathbf{v,h})}\)  không hề dễ tính toán, hoặc thâm chí là không tính được. Một trong các phương pháp khác giải quyết vấn đề này là Gibb sampling.

3.2 Gibbs Sampling:

Chắc hẳn bạn đọc đã biết đến bài toán kinh điển tìm giá trị \(\pi\) bằng cách lấy tỉ số giữa số mẫu nằm trong vòng tròn trên tổng số mẫu được lấy. Đây là chỉ là một bài toán trong các bài toán xấp xỉ bằng cách lấy mẫu. Trong các bài toán ứng dụng phương pháp Bayesian, xác suất hậu nghiệm thường phải tính tích phân trong không gian nhiều chiều. Có nhiều giải pháp được đề xuất để xấp xỉ tính toán này, trong đó kể đến tập các giải thuật Monte Carlo (MC), sau đó là nhánh Markov Chain Monte Carlo (MCMC). Gibbs sampling là giải thuật thuộc nhóm MCMC.

Để tính toán tích phân phức tạp:

\[\int_a^bh(x)dx\]

Ý tưởng của phương pháp Monte Carlo là phân tích \(h(x)\) thành tích của một hàm \(f(x)\) và một hàm mật độ xác suất \(p(x)\) trên miền (a,b) như sau:

\[\begin{align}\int^b_ah(x)dx = \int_a^bf(x)p(x)dx=E_{p(x)}[f(x)] \end{align}\]

Trong đó, \(E_{p(x)}[f(x)]\) gọi là kỳ vọng của \(f(x)\) trên hàm mật độ \(p(x)\). Nói cách khác, Nếu chúng ta lấy thật nhiều mẫu \(x\) từ hàm mật độ \(p(x)\) trên miền (a, b), chúng ta có thể xấp xỉ được tích phân \(\int_a^bh(x)\) bằng cách lấy kỳ vọng của \(f(x).\)

Tuy nhiên, đối với dữ liệu nhiều chiều, việc lấy mẫu trên hàm mật độ xác suất kết hợp thường phức tạp. Ý tưởng của Gibbs sampling là việc lấy mẫu trên hàm xác suất có điều kiện sẽ đơn giản hơn.

Hình 4: Khi nào cần dùng Gibbs

Xét một phân phối chuẩn có hai biến, và chúng ta mong muốn tính toán xác suất biên của một trong hai biến, \(p(x), p(y)\). Với giá trị khởi đầu \(y_0\). Các bước thuật toán Gibbs sampling sẽ được đề cập ở phần thuật toán CD-K sắp tới.

3.3 Áp dụng Gibbs sampling

Tại công thức (9), postive phase lẫn negative phase đều đã được phân tích thành hai thành phần và hàm phân phối xác suất \(p(h|v)\) hoặc \(p(v,h)\). Công thức (9) được viết lại như sau:

\[\begin{equation}\frac{\partial \log p(v)}{\partial \theta} = \underbrace{- \bigg<\frac{\partial E(\mathbf{v,h})}{\partial \theta} \bigg>_0}_{\text{positive phase}} + \underbrace{\bigg<\frac{\partial E(\mathbf{v,h})}{\partial \theta} \bigg>_\infty}_{\text{negative phase}} \end{equation}\]

Trong đó, theo cách hoạt động của RBM \(\big<.\big>_0\) là kỳ vọng của phân phối dữ liệu được quan sát \(p(\mathbf{h|x)}.\big<.\big>_{\infty}\) là kỳ vọng theo phân phối dữ liệu của mô hình \(p(\mathbf{v,h})\). Gibbs sampling được áp dụng ở phần negative phase. Quy trình lấy mẫu được minh họa như trong hình.

Hinh 5: Mô phỏng cách thực thiện lấy mẫu Gibbs tham khảo tại [2]. Một Gibbs step gồm hai bước: Lấy mẫu \(h^{(t+1)}\), lấy mẫu \(v^{(t+1)}\). Việc này được lặp lại liên tục rất nhiều lần để có kết quả xấp xỉ chính xác.

Đầu tiên, Công thức (8), (9) được dùng để tính khả năng giá trị các nút về 1. Sau đó, chúng ta sẽ gán \(h_j\) bằng 1 nếu \(p(h_j|v)\) lớn hơn một số ngẫu nhiên nào đó trong khoảng (0, 1) và bằng 0 ngược lại. Việc biến đổi về giá trị nhị phân là quan trọng trong việc tái tạo lại vector đầu vào. Sau khi đã có mẫu \(h^{\infty}, v^{\infty}\), chúng ta cập nhật tham số theta như sau:

\[\begin{align}\Delta W_{ji} = \frac{\partial \log p(v)}{\partial \theta} &= -\big<v_ih_j\big>_0 + \big<v_ih_j\big>_\infty &\rightarrow& W_{ji} += \eta\Delta W_{ji} \\ \Delta c_{i} = \frac{\partial \log p(v)}{\partial \theta} &= -\big<v_i\big>_0 + \big<v_i\big>_\infty &\rightarrow& c_{i} += \eta\Delta c_{i}\\ \Delta b_{j} = \frac{\partial \log p(v)}{\partial \theta} &= -\big<h_j\big>_0 + \big<h_j\big>_\infty &\rightarrow& b_{j} += \eta\Delta b_{j}\end{align}\]

Tuy nhiên, negative phase cần phải lấy mẫu rất nhiều để tránh bị ảnh hưởng từ giá trị khởi tạo (bạn đọc tìm hiểu thêm tại [3]). Do đó, việc tính toán negative phase là không thể.

3.4 K-Contrastive Divergence

Để giải quyết vấn đề trên, Geoffrey Hinton áp dụng giải thuật mà tác giả đã đề xuất năm 2002: giải thuật phân kỳ tương phản (Contrastive Divergence, viết tắt là CD-k). Tác giả đề xuất thay vì phải liên tục lấy mẫu ở negative phase, CD-k chỉ cần thực hiện lấy mẫu k lần. Việc lấy mẫu ít có thể dẫn đến việc xấp xỉ không chính xác, tuy nhiên, nhiều nghiên cứu cho thấy tham số mô hình có xu hướng được cập nhật chính xác. Giải thuật CD-K được biểu diễn như sau:

\[\begin{equation}\frac{\partial \log p(v)}{\partial \theta} = \underbrace{- \bigg<\frac{\partial E(\mathbf{v,h})}{\partial \theta} \bigg>_0}_{\text{positive phase}} + \underbrace{\bigg<\frac{\partial E(\mathbf{v,h})}{\partial \theta} \bigg>_k}_{\text{negative phase}} \end{equation}\]

Sau đó, các tham số được cập nhật tương tự như trên.

Hình 6: Tổng quát các bước của giải thuật CD-K, tham khảo tại [1].

4. TỔNG KẾT

Máy Bolzman giới hạn là một hình sinh dựa vào năng lượng. Mô hình chỉ có hai tầng: tầng thấy được và tầng ẩn, và chỉ nhận giá trị nhị phân. Hàm tối ưu của mô hình là max log-likelihood, và phương pháp gradient ascent được sử dụng để cập nhật tham số mô hình. Việc tính toán đạo hàm mô hình là phức tạp, Gibbs sampling - một phương pháp tính toán xấp xỉ bằng cách lấy mẫu - được đề xuất để tính đạo hàm. Tuy nhiên, phương pháp này cần phải lấy mẫu rất nhiều và lâu, Geoffrey Hinton đề xuất giải pháp CD-k lấy mẫu ít hơn nhưng vẫn hoạt động hiệu quả. Ví dụ áp dụng mô hình RBM, bạn đọc có thể xem tại [11]. Để hiểu hơn về code, bạn đọc tham khảo tại đây [12], [13]

5. THAM KHẢO:

[1] Chapter 12: Deep Learning with Neural Networks Part I, Assoc.Prof.Dr. Duong Tuan Anh (12/2016), Faculty of Computer Science and Engineering, HCMC Univ. of Technology,

[2] Lopes, N., & Ribeiro, B. (2015). Machine learning for adaptive many-core machines: A practical approach.

[3] B. Walsh (2002), Markov Chain Monte Carlo and Gibbs Sampling, Lecture Notes for EEB 596z

[4] Salakhutdinov, R., Mnih, A., & Hinton, G. (2007, June). Restricted Boltzmann machines for collaborative filtering. In Proceedings of the 24th international conference on Machine learning (pp. 791-798).

[5] LeCun, Yann. “Deep Learning, 9 Mar. 2020, Energy-Based Models · Deep Learning https://atcold.github.io/pytorch-Deep-Learning/en/week07/07-1/.

[6] “Generative Model.” Wikipedia, Wikimedia Foundation, 31 Dec. 2021, https://en.wikipedia.org/wiki/Generative_model.

[7] Quora, Why does Gibbs sampling in an RBM in contrastive divergence allow us to approximate the log of the partition function?, https://www.quora.com/Why-does-Gibbs-sampling-in-an-RBM-in-contrastive-divergence-allow-us-to-approximate-the-log-of-the-partition-function

[8] GOYAL, C. H. I. R. A. G. (2021, July 19). Deep understanding of discriminative and generative models. Analytics Vidhya. Retrieved January 25, 2022, from https://www.analyticsvidhya.com/blog/2021/07/deep-understanding-of-discriminative-and-generative-models-in-machine-learning/

[9] Wikimedia Foundation. (2021, December 22). Boltzmann machine. Wikipedia. Retrieved January 25, 2022, from https://en.wikipedia.org/wiki/Boltzmann_machine#:~:text=A Boltzmann machine (also%20called,is%20a%20Markov%20random%20field.

[10] BM, N., 2020. What is an encoder decoder model?, Medium. https://towardsdatascience.com/what-is-an-encoder-decoder-model-86b3d57c5e1a

[11] Restricted Boltzmann Machines (RBM) - A friendly introduction, Serrano.Academy, https://www.youtube.com/watch?v=Fkw0_aAtwIw

[12]  VuHuy-cse-9, (2021), deepbeliefnetwork,github,https://github.com/VuHuy-cse-9/Machine-Learning-Collection/tree/main/DeepLearning/deepbeliefnetwork

[13] albertbup (2017), A Python implementation of Deep Belief Networks built upon NumPy and TensorFlow with scikit-learn compatibility, github, https://github.com/albertbup/deep-belief-network

[14] Vu, T. K. (2017, January 12). Bài 7: Gradient Descent (phần 1/2). Tiep Vu's blog. Retrieved January 29, 2022, from https://machinelearningcoban.com/2017/01/12/gradientdescent/