RBM 3: Contrastive Divergence

Chuỗi bài viết về RBMs:
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

Mặc dù chỉ bắt đầu “nổi tiếng” sau khi được dùng để huấn luyện Restricted Boltzmann Machines (RBMs) nhưng Contrastive Divergence thực ra đã được đề xuất từ trước đó, và bản thân thuật toán này cũng có vẻ đẹp theo cách riêng của nó. Do vậy trong bài này, ta tạm thời quên đi RBMs để xét thuật toán Contrastive Divergence từ góc độ tổng quan hơn. Cách áp dụng Contrastive Divergence trong huấn luyện RBMs sẽ được đề cập trong bài tiếp theo (và hi vọng là cuối cùng) của chuỗi bài này.

1. Contrastive Divergence là gì

Giả sử ta cần mô hình phân phối xác suất của một vector x bằng cách sử dụng một hàm có dạng f\left(x; \theta\right), trong đó \theta là vector chứa toàn bộ tham số của mô hình. Phân phối xác suất của x, kí hiệu p\left(x;\theta\right) phải có tổng bằng 1 nên:

\displaystyle p\left(x; \theta\right) = \frac{1}{Z\left(\theta\right)}f\left(x; \theta\right)       (1)

trong đó Z\left(\theta\right) gọi là partition function và được tính như sau:

\displaystyle Z\left(\theta\right) = \int f\left(x; \theta\right) dx        (2)

Cho một tập huấn luyện \mathbf{X} = \left\{x_i\right\}_{i=1}^N, ta cần phải xác định tham số \theta bằng cách nào đó. Một cách tiếp cận phổ biến là Maximum Likelihood Estimation (MLE), theo đó hàm likelihood của mô hình trên tập huấn luyện được viết là (với giả sử các samples trong X là i.i.d):

\displaystyle \mathcal{L}\left(\textbf{X};\theta\right) = \prod_{i=1}^N \frac{1}{Z\left(\theta\right)}f\left(x_i;\theta\right)      (3)

và ta sẽ tìm cách cực đại hóa hàm này. Tuy nhiên thông thường ta tìm cách cực tiểu hóa hàm negative log-likelihood, được viết như sau:

\displaystyle E\left(\textbf{X};\theta\right) = \log Z\left(\theta\right) - \frac{1}{N}\sum_{i=1}^N \log f\left(x_i;\theta\right)   (4)

Với hàm mục tiêu này, cách làm của MLE là tính đạo hàm của E\left(\textbf{X};\theta\right) theo các tham số, sau đó:

  • Nếu biểu thức nhận được thuộc dạng closed-form thì giải phương trình \frac{\partial E}{\partial\theta_i} = 0 để tìm giá trị của các tham số.
  • Nếu không là closed-form thì ta phải dùng các phương pháp tối ưu như gradient descent để cực tiểu hóa hàm này, như đã viết trong một bài khác.

Rõ ràng tính chất của bài toán phụ thuộc vào cách chọn hàm f\left(x;\theta\right). Ta xét vài trường hợp sau.

1.1. Phân phối Gaussian

Giả sử ta chọn hàm f\left(x;\theta\right) là phân phối Gaussian \mathcal{N}\left(x;\mu, \sigma\right), như vậy tập tham số là \theta = \left\{\mu, \sigma\right\}. Tích phân của phân phối Gaussian trên toàn miền xác định bằng 1, nên \log Z\left(\theta\right) = 0. Lấy đạo hàm của phương trình (4) theo \mu và giải \frac{\partial E}{\partial\mu} = 0 ta được giá trị tối ưu của \mu là mean của tập huấn luyện \hat{\mu} = \frac{1}{N}\sum_{i=1}^N x_i. Tương tự ta cũng có giá trị tối ưu cho \sigma là căn bậc 2 của variance của tập huấn luyện.

Trong tình huống này, vì ta có thể viết các đạo hàm riêng dưới dạng closed form nên có thể tính ngay giá trị tối ưu của các tham số. Nếu tưởng tượng hàm E\left(\textbf{X};\theta\right) trong không gian các tham số là một cánh đồng bát ngát và ta muốn tìm điểm thấp nhất của cánh đồng này, thì trường hợp này tương ứng với khi ta đang ở trên cánh đồng trong 1 ngày đẹp trời, ta biết chính xác điểm thấp nhất và có thể đi thẳng ngay tới đó.

1.2. Mixture model

Giả sử ta chọn hàm f\left(x;\theta\right) là tổng có trọng số của K phân phối Gaussian, như vậy tập tham số là \theta = \left\{w_{1,\ldots,K}, \mu_{1,\ldots, K}, \sigma_{1,\ldots, K}\right\} và:

\displaystyle f\left(x;\theta\right) = \sum_{k=1}^K w_k \mathcal{N}\left(x;\mu_k, \sigma_k\right)       (5)

Mô hình này gọi là mixture of Gaussians hay là sum-of-experts. Vì tích phân của phân phối Gaussian bằng 1 nên \log Z\left(\theta\right) = \log \sum_{k=1}^K w_k. Tuy nhiên nếu ta tính đạo hàm riêng của phương trình (4) theo mỗi tham số của mô hình thì kết quả lại phụ thuộc vào các tham số khác nên các biểu thức này không phải là closed-form. Vì vậy ta không thể giải phương trình đạo hàm riêng bằng 0 một cách trực tiếp được. Thay vào đó ta phải dùng các phương pháp local optimization, mà điển hình là gradient descent, để tìm local minimum của hàm E\left(\textbf{X};\theta\right) (phương pháp chuẩn mực để huấn luyện mô hình mixture of Gaussian là Expectation Maximization).

Trở lại với ví dụ về cánh đồng, có thể nói gradient descent giống như việc ta đang ở trên cánh đồng vào 1 đêm tối tăm và trong tay chỉ có một ngọn đuốc. Ta có thể cảm nhận độ cao của cánh đồng trong một vùng nhỏ xung quanh chỗ đang đứng. Sau đó bằng cách chiếu ngọn đuốc về hướng thấp nhất, ta có thể xác định khoảng cách tới điểm thấp nhất theo hướng đã chọn. Cứ như vậy cho đến khi ta tìm được một điểm thấp nhất (cục bộ), tương ứng với local minimum của hàm mục tiêu E\left(\textbf{X};\theta\right).

1.3. Product-of-experts

Cuối cùng, giả sử ta chọn hàm f\left(x;\theta\right) là tích của K phân phối Gaussian, như vậy tập tham số là \theta = \left\{\mu_{1,\ldots, K}, \sigma_{1,\ldots, K}\right\} và:

\displaystyle f\left(x;\theta\right) = \prod_{k=1}^K \mathcal{N}\left(x;\mu_k, \sigma_k\right)       (6)

Mô hình này gọi là product-of-experts. Trong trường hợp này, Z\left(\theta\right) không còn là hằng số nữa. Chẳng hạn với 2 phân phối Gaussian có cùng variance \sigma^2 = 1 thì khi \mu_1 = -\infty, \mu_2 = +\infty thì Z\left(\theta\right) = 0, nhưng khi \mu_1 = \mu_2 = 0 thì Z\left(\theta\right) = \frac{1}{2\sqrt{\pi}}.

Trong trường hợp đặc biệt này (tích của các phân phối Gaussian), thực ra khi cho trước giá trị của tham số \theta thì ta vẫn có thể được tính chính xác Z\left(\theta\right). Tuy nhiên trong trường hợp tổng quát thì tích phân trong công thức (2) không thể tính chính xác được. Khi đó ta phải dùng các phương pháp xấp xỉ để tính đạo hàm từng phần của phương trình (4) theo các tham số, rồi sử dụng gradient descent để tối ưu hóa. Việc tính xấp xỉ đạo hàm nói chung là tốn thời gian và nếu mô hình có quá nhiều tham số thì việc này trở nên không khả thi. Đây là trường hợp tổng quát nhất khi ta cố gắng tối ưu một hàm mà ta không thể tính chính xác được.

Đây là khi Contrastive Divergence (CD) tỏ ra hiệu quả. Mặc dù ta không thể tính được hàm mục tiêu E\left(\textbf{X};\theta\right), Contrastive Divergence vẫn có thể tính xấp xỉ đạo hàm từng phần của hàm này. Trong ví dụ về cánh đồng, đây là khi chúng ta ở trên cánh đồng trong một đêm đen như mực và không có bất kì ý niệm nào về độ cao của cánh đồng (vì ta không thể tính được giá trị của hàm mục tiêu). CD trong tình huống này cho ta một số ý niệm về gradient của một vùng rất nhỏ ngay dưới chân ta, do đó ta có thể bước từng bước rất nhỏ với hi vọng có thể tìm đến local optimum nào đó.

2. Thuật toán Contrastive Divergence

Như đã trình bày ở phần trước, Contrastive Divergence (CD) là thuật toán ước lượng xấp xỉ đạo hàm riêng của một hàm mục tiêu với tập tham số \theta và dataset X. Đầu tiên, ta có đạo hàm riêng của phương trình (4) là:

\displaystyle \begin{aligned} \frac{\partial E\left(\mathbf{X};\theta\right)}{\partial\theta} & =\frac{\partial\log Z\left(\theta\right)}{\partial\theta}-\frac{1}{N}\sum_{i=1}^{N}\frac{\partial\log f\left(x_{i};\theta\right)}{\partial\theta}\\ & =\frac{\partial\log Z\left(\theta\right)}{\partial\theta}-\left\langle \frac{\partial\log f\left(x_{i};\theta\right)}{\partial\theta}\right\rangle _{\mathbf{X}} \end{aligned}         (7)

trong đó \left\langle\cdot\right\rangle_\textbf{X} là kì vọng của \cdot tính trên tập dữ liệu X.

Phần phía trước dấu trừ của phương trình (7) là đạo hàm của logarithm của partition function. Với định nghĩa của Z\left(\theta\right) trong phương trình (2), ta có:

\displaystyle \begin{aligned} \frac{\partial\log Z\left(\theta\right)}{\partial\theta} & =\frac{1}{Z\left(\theta\right)}\frac{\partial Z\left(\theta\right)}{\partial\theta}\\ & =\frac{1}{Z\left(\theta\right)}\frac{\partial}{\partial\theta}\int f\left(x;\theta\right)dx\\ & =\frac{1}{Z\left(\theta\right)}\int\frac{\partial f\left(x;\theta\right)}{\partial\theta}dx\\ & =\frac{1}{Z\left(\theta\right)}\int f\left(x;\theta\right)\frac{\partial\log f\left(x;\theta\right)}{\partial\theta}dx\\ & =\int p\left(x;\theta\right)\frac{\partial\log f\left(x;\theta\right)}{\partial\theta}dx\\ & =\left\langle \frac{\partial\log f\left(x;\theta\right)}{\partial\theta}\right\rangle _{p\left(x;\theta\right)} \end{aligned}     (8)

Dĩ nhiên phép tích phân trong công thức trên là intractable, nhưng từ đẳng thức cuối cùng của (8), ta thấy rằng có thể xấp xỉ nó bằng một tập các sample lấy từ phân phối p\left(x;\theta\right) của mô hình đang xét (gọi là proposed distribution).

Mặc dù ta không thể lấy mẫu trực tiếp từ phân phối p\left(x;\theta\right) (công thức (1)) vì không thể tính được Z\left(\theta\right), nhưng ta vẫn có thể sử dụng MCMC để chuyển các sample trong tập huấn luyện (vốn tuân theo target distribution mà ta muốn mô hình hóa) thành sample của proposed distribution. Việc này là khả thi vì các bước lấy mẫu trong MCMC khi đó chỉ yêu cầu tính tỉ số của 2 xác suất \frac{p\left(x';\theta\right)}{p\left(x;\theta\right)} nên partition function bị triệt tiêu. Gọi \textbf{X}^n là tập sample sau n bước lấy mẫu MCMC, và \textbf{X}^0 \equiv \textbf{X}. Thay (8) vào (7) ta có:

\displaystyle \frac{\partial E\left(\mathbf{X};\theta\right)}{\partial\theta} = \left\langle \frac{\partial\log f\left(x_{i};\theta\right)}{\partial\theta}\right\rangle _{\mathbf{X}^\infty} - \left\langle \frac{\partial\log f\left(x_{i};\theta\right)}{\partial\theta}\right\rangle _{\mathbf{X^0}}     (9)

Ta vẫn còn một vấn đề nữa là các bước lấy mẫu MCMC thông thường sẽ rất lớn và trở nên không thực tế. Đây là lúc mà mẹo của Hinton phát huy tác dụng. Hinton cho rằng chỉ cần vài bước lấy mẫu MCMC là đủ để tính xấp xỉ đạo hàm trong (9). Ý tưởng nôm na là chỉ cần sau vài bước lấy mẫu MCMC, tập dữ liệu đã bắt đầu di chuyển từ proposed distribution sang target distribution, do đó là một cách xấp xỉ hợp lí đạo hàm của hàm mục tiêu. Hơn nữa trong ngữ cảnh của các mô hình ML huấn luyện bằng mini-batch gradient descent, việc thực hiện quá nhiều bước lấy mẫu MCMC cho mỗi mini-batch rõ ràng là không cần thiết. Bằng các kết quả thực nghiệm, Hinton chỉ ra rằng chỉ cần 1 bước lấy mẫu MCMC cũng đủ để thuật toán hội tụ tới một local optimum đủ tốt. Thuật toán Contrastive Divergence với k bước lấy mẫu MCMC được kí hiệu là CD-k. Khi tập dữ liệu lớn, ban đầu ta có thể dùng CD-1, sau đó là CD-3, CD-5 hoặc CD-10. Lí do là vì càng huấn luyện thì ta càng có cơ hội xấp xỉ tốt hơn đạo hàm bằng nhiều bước lấy mẫu MCMC hơn.

Với cách tính xấp xỉ đạo hàm như trong (9), ta có thể viết công thức cập nhật trọng số như sau (lưu ý là ta muốn đi ngược chiều của đạo hàm):

\displaystyle \Delta\theta \propto \left\langle \frac{\partial\log f\left(x_{i};\theta\right)}{\partial\theta}\right\rangle _{\mathbf{X}^0} - \left\langle \frac{\partial\log f\left(x_{i};\theta\right)}{\partial\theta}\right\rangle _{\mathbf{X^1}}    (10)

Công thức (10) đủ tổng quát để sử dụng với các kiểu trick trong ML như learning rate, momentum v.v…

3. Kết luận

Bài này viết về thuật toán Contrastive Divergence như một cách xấp xỉ đạo hàm (cục bộ) của một hàm mục tiêu mà ta không thể tính được. Thuật toán này sẽ được sử dụng để huấn luyện RBM, như sẽ thấy trong bài tiếp theo.

Advertisements

6 comments

  1. Admin ơi, còn bài viết về phần cuối, Ad viết chưa, cho mình xin tham khảo được không ah

    1. Hi em,

      Bài cuối anh chưa có thời gian viết, nhưng nếu em có câu hỏi nào liên quan tới mấy thứ của nợ này thì cứ hỏi, a sẽ trả lời nếu a biết.

      Cheers,

  2. Thanks anh. Một chuỗi bài viết rất hay và rõ ràng về RBM mặc dù chưa thể thẩm thấu hết đc. Em thấy ng ta dùng RBM để pre-training trong DBN. Anh có thể giới thiệu một pp pre-training khác trong DBN, ex AutoEncoder….Theo anh pp nào sẽ đem lại kết quả tốt hơn.
    p/s: chờ bài viết cuối của anh

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