Variational Autoencoders 3: Training, Inference and comparison with other models

Variational Autoencoders 1: Overview
Variational Autoencoders 2: Maths
Variational Autoencoders 3: Training, Inference and comparison with other models

Recalling that the backbone of VAEs is the following equation:

\log P\left(X\right) - \mathcal{D}\left[Q\left(z\vert X\right)\vert\vert P\left(z\vert X\right)\right] = E_{z\sim Q}\left[\log P\left(X\vert z\right)\right] - \mathcal{D}\left[Q\left(z\vert X\right) \vert\vert P\left(z\right)\right]

In order to use gradient descent for the right hand side, we need a tractable way to compute it:

  • The first part E_{z\sim Q}\left[\log P\left(X\vert z\right)\right] is tricky, because that requires passing multiple samples of z through f in order to have a good approximation for the expectation (and this is expensive). However, we can just take one sample of z, then pass it through f and use it as an estimation for E_{z\sim Q}\left[\log P\left(X\vert z\right)\right] . Eventually we are doing stochastic gradient descent over different sample X in the training set anyway.
  • The second part \mathcal{D}\left[Q\left(z\vert X\right) \vert\vert P\left(z\right)\right] is even more tricky. By design, we fix P\left(z\right) to be the standard normal distribution \mathcal{N}\left(0,I\right) (read part 1 to know why). Therefore, we need a way to parameterize Q\left(z\vert X\right) so that the KL divergence is tractable.

Here comes perhaps the most important approximation of VAEs. Since P\left(z\right) is standard Gaussian, it is convenient to have Q\left(z\vert X\right) also Gaussian. One popular way to parameterize Q is to make it also Gaussian with mean \mu\left(X\right) and diagonal covariance \sigma\left(X\right)I, i.e. Q\left(z\vert X\right) = \mathcal{N}\left(z;\mu\left(X\right), \sigma\left(X\right)I\right), where \mu\left(X\right) and \sigma\left(X\right) are two vectors computed by a neural network. This is the original formulation of VAEs in section 3 of this paper.

This parameterization is preferred because the KL divergence now becomes closed-form:

\displaystyle \mathcal{D}\left[\mathcal{N}\left(\mu\left(X\right), \sigma\left(X\right)I\right)\vert\vert P\left(z\right)\right] = \frac{1}{2}\left[\left(\sigma\left(X\right)\right)^T\left(\sigma\left(X\right)\right) +\left(\mu\left(X\right)\right)^T\left(\mu\left(X\right)\right) - k - \log \det \left(\sigma\left(X\right)I\right) \right]

Although this looks like magic, but it is quite natural if you apply the definition of KL divergence on two normal distributions. Doing so will teach you a bit of calculus.

So we have all the ingredients. We use a feedforward net to predict \mu\left(X\right) and \sigma\left(X\right) given an input sample X draw from the training set. With those vectors, we can compute the KL divergence and \log P\left(X\vert z\right), which, in term of optimization, will translate into something similar to \Vert X - f\left(z\right)\Vert^2.

It is worth to pause here for a moment and see what we just did. Basically we used a constrained Gaussian (with diagonal covariance matrix) to parameterize Q. Moreover, by using \Vert X - f\left(z\right)\Vert^2 for one of the training criteria, we implicitly assume P\left(X\vert z\right) to be also Gaussian. So although the maths that lead to VAEs are generic and beautiful, at the end of the day, to make things tractable, we ended up using those severe approximations. Whether those approximations are good enough totally depend on practical applications.

There is an important detail though. Once we have \mu\left(X\right) and \sigma\left(X\right) from the encoder, we will need to sample z from a Gaussian distribution parameterized by those vectors. z is needed for the decoder to reconstruct \hat{X}, which will then be optimized to be as close to X as possible via gradient descent. Unfortunately, the “sample” step is not differentiable, therefore we will need a trick call reparameterization, where we don’t sample z directly from \mathcal{N}\left(\mu\left(X\right), \sigma\left(X\right)\right), but first sample z' from \mathcal{N}\left(0, I\right), and then compute z = \mu\left(X\right) + \mu\left(X\right)Iz'. This will make the whole computation differentiable and we can apply gradient descent as usual.

The cool thing is during inference, you won’t need the encoder to compute \mu\left(X\right) and \sigma\left(X\right) at all! Remember that during training, we try to pull Q to be close to P\left(z\right) (which is standard normal), so during inference, we can just inject \epsilon \sim \mathcal{N}\left(0, I\right) directly into the decoder and get a sample of X. This is how we can leverage the power of “generation” from VAEs.

There are various extensions to VAEs like Conditional VAEs and so on, but once you understand the basic, everything else is just nuts and bolts.

To sum up the series, this is the conceptual graph of VAEs during training, compared to some other models. Of course there are many details in those graphs that are left out, but you should get a rough idea about how they work.


In the case of VAEs, I added the additional cost term in blue to highlight it. The cost term for other models, except GANs, are the usual L2 norm \Vert X - \hat{X}\Vert^2.

GSN is an extension to Denoising Autoencoder with explicit hidden variables, however that requires to form a fairly complicated Markov Chain. We may have another post  for it.

With this diagram, hopefully you will see how lame GAN is. It is even simpler than the humble RBM. However, the simplicity of GANs makes it so powerful, while the complexity of VAE makes it quite an effort just to understand. Moreover, VAEs make quite a few severe approximation, which might explain why samples generated from VAEs are far less realistic than those from GANs.

That’s quite enough for now. Next time we will switch to another topic I’ve been looking into recently.

Variational Autoencoders 2: Maths

Variational Autoencoders 1: Overview
Variational Autoencoders 2: Maths
Variational Autoencoders 3: Training, Inference and comparison with other models

Last time we saw the probability distribution of X with a latent variable z as follows:

\displaystyle P(X) = \int P\left(X\vert z; \theta\right)P(z)dz  (1)

and we said the key idea behind VAEs is to not sample z from the whole distribution P\left(z\right), but actually from a simpler distribution Q\left(z\vert X\right). The reason is because most of z will likely to give P\left(X\vert z\right) close to zero, and therefore making little contribution to the estimation of P\left(X\right). Now if we sample z \sim Q\left(z\vert X\right), those values of z will more likely to generate X in the training set. Moreover, we hope that Q will has less modes than P\left(z\right), and therefore easier to sample from. The intuition of this is the locations of the modes of Q\left(z\vert X\right) depends on X, and this flexibility will compensate the limitation of the fact that Q\left(z\vert X\right) is simpler than P\left(z\right).

But how Q\left(z\vert X\right) can help with modelling P\left(X\right)? If z is sampled from Q, then using f we will get E_{z \sim Q}P\left(X\vert z\right). We will then need to show the relationship of this quantity with P\left(X\right), which is the actual quantity we want to estimate. The relationship between E_{z \sim Q}P\left(X\vert z\right) and P\left(X\right) is the backbone of VAEs.

We start with the KL divergence of Q\left(z\vert X\right) and P\left(z\vert X\right):

\mathcal{D}\left[Q\left(z\vert X\right) \vert\vert P\left(z\vert X\right)\right] = E_{z\sim Q}\left[\log Q\left(z\vert X\right) - log P\left(z\vert X\right)\right]

The unknown quantity in this equation is P\left(z\vert X\right), but at least we can use Bayes rule for it:

\mathcal{D}\left[Q\left(z\vert X\right) \vert\vert P\left(z\vert X\right)\right] = E_{z\sim Q}\left[\log Q\left(z\vert X\right) - log P\left(X\vert z\right) - \log P\left(z\right)\right] + \log P\left(X\right)

Rearrange things a bit, and apply the definition of KL divergence between Q\left(z\vert X\right) and P\left(z\right), we have:

\log P\left(X\right) - \mathcal{D}\left[Q\left(z\vert X\right)\vert\vert P\left(z\vert X\right)\right] = E_{z\sim Q}\left[\log P\left(X\vert z\right)\right] - \mathcal{D}\left[Q\left(z\vert X\right) \vert\vert P\left(z\right)\right]    (2)

If you forget everything, this formula is the thing you should remember. It is therefore important to understand what it means:

  • The left-hand-side is exactly what we want to optimize, plus an error term. The smaller this error term is, the better we are in mazimizing P\left(X\right). In other words, the left-hand-side is a lower-bound of what we want to optimize, hence the name variational (Bayesian).
  • If Q happens to be a differentiable function, the right-hand-side is something we can optimize with gradient descent (we will see how to do it later). Note that the right-hand-side happens to take the form of encoder and decoder, where Q encodes X into z, and then P decodes z to reconstruct X, hence the name “Autoencoder”. However, VAEs don’t really belong to the family of Denoising and Sparse Autoencoders, although there are indeed some connections.
  • Note that P\left(z\vert X\right) on the left hand side is something intractable. However, by maximizing the left hand side, we simultaneously minimize \mathcal{D}\left[Q\left(z\vert X\right)\vert\vert P\left(z\vert X\right)\right], and therefore pull Q\left(z\vert X\right) closer to P\left(z\vert X\right). If we use a flexible model for Q, then we can use Q as an approximation for P\left(z\vert X\right). This is a nice side effect of the whole framework.

Actually the above maths existed way before VAEs. However the trick was to use a feedforward network for Q, which gave rise to VAEs several years ago.

Next time, we will see how to do that, and hopefully conclude this series. Then we can move on with something more interesting.

Variational Autoencoders 1: Overview

In a previous post, we briefly mentioned some recent approaches for Generative Modeling. Among those, RBMs and DBMs are probably very tricky because the estimation of gradients in those models is based on a good mixing of MCMC, which tends to get worse during the course of training because the model distribution gets sharper. Autogressive models like PixelRNN, WaveNet, etc… are easier to train but have no latent variables, which makes them somewhat less powerful. Therefore, the current frontier in Generative Modelling is probably GANs and Variational Autoencoders (VAEs).

While GANs are too mainstream, I thought I can probably write a post or two about Variational Autoencoders, at least to clear up some confusions I am having about them.

Formally, generative modeling is the area in Machine Learning that deals with models of distributions P(X), defined over datapoints X in some high-dimensional space \mathcal{X}. The whole idea is to construct models of P(X) that assigns high probabilities to data points similar to those in the training set, and low probabilities every where else. For example, a generative models of images of cows should assign small probabilities to images of human.

However, computing the probability of a given example is not the most exciting thing about generative models. More often, we want to use the model to generate new samples that look like those in the training set. This “creativity” is something unique to generative models, and does not exist in, for instance, discriminative models. More formally, say we have a training set sampled from an unknown distribution P_\text{org}(X), and we want to train a model P which we can take sample from, such that P is as close as possible to P_\text{org}.

Needless to say, this is a difficult problem. To make it tractable, traditional approaches in Machine Learning often have to 1) make strong assumptions about the structure of the data, or 2) make severe approximation, leading to suboptimal models, or 3) rely on expensive sampling procedures like MCMC. Those are all limitations which make Generative modeling a long-standing problem in ML research.

Without further ado, let’s get to the point. When \mathcal{X} is a high-dimensional space, modeling is difficult mostly because it is tricky to handle the inter-dependencies between dimensions. For instance, if the left half of an image is a horse then probably the right half is likely another horse.

To further reduce this complexity, we add a latent variable z in a high-dimensional space \mathcal{Z} that we can easily sample from, according to a distribution P(z) defined over \mathcal{Z}. Then say we have a family of deterministic function f(z;\theta) parameterized by a vector \theta in some space \Theta where f: \mathcal{Z} \times \Theta \rightarrow \mathcal{X}. Now f is deterministic, but since z is a random variable, f(z;\theta) is a random variable in \mathcal{X}.

During inference, we will sample z from P(z), and then train \theta such that f(z;\theta) is close to samples in the training set. Mathematically, we want to maximize the following probability for every sample X in the training set:

\displaystyle P(X) = \int P\left(X\vert z; \theta\right)P(z)dz   (1)

This is the good old maximum likelihood framework, but we replace f(z;\theta) by P\left(X\vert z;\theta\right) (called the output distribution) to explicitly indicate that X depends on z, so that we can use the integral to make it a proper probability distribution.

There are a few things to note here:

  • In VAEs, the choice of the output distribution is often Gaussian, i.e. P\left(X\vert z;\theta\right) = \mathcal{N}\left(X; f(z;\theta), \sigma^2 * I\right), meaning it is a Gaussian distribution with mean f(z;\theta) and diagonal covariance matrix where \sigma is a scalar hyper-parameter. This particular choice has some important motivations:
    • We need the output distribution to be continuous, so that we can use gradient descent on the whole model. It wouldn’t be possible if we use discontinuous function like the Dirac distribution, meaning to use exactly the output value of f(z;\theta) for X.
    • We don’t really need to train our model such that f(z;\theta) produces exactly some sample X in the training set. Instead, we want it to produce samples that are merely like X. In the beginning of training, there is no way for f to gives exact samples in the training set. Hence by using a Gaussian, we allow the model to gradually (and gently) learn to produce samples that are more and more like those in the training set.
    • It doesn’t have to be Gaussian though. For instance, if X is binary, we can make P\left(X\vert z;\theta\right) a Bernoulli parameterized by f(z;\theta). The important property is that P\left(X\vert z\right) can be computed, and is continuous in the domain of \theta.
  • The distribution of z is simply the normal distribution, i.e. P(z) = \mathcal{N}\left(0,I\right). Why? How is it possible? Is there any limitation with this? A related question is why don’t we have several levels of latent variables. which potentially might help modelling complicated processes?
    All those question can be answered by the key observation that any distribution in d dimensions can be generated by taking d variables from the normal distribution and mapping them through a sufficiently complicated function.
    Let that sink for a moment. Readers who are interested in the mathematical details can have a look at the conditional distribution method described in this paper. You can also convince yourself if you remember how we can sample from any Gaussian as described in an earlier post.
    Now, this observation means we don’t need to go to more than one level of latent variable, with a condition that we need a sufficiently complicated function for f(z;\theta). Since deep neural nets has been shown to be a powerful function approximator, it makes a lot of sense to use deep neural nets for modeling f.
  • Now the only business is to maximize (1). Using the law of large numbers, we can approximate the integral by the expected value over a large number of samples. So the plan will be to take a very large sample \left\{z_1, ..., z_n\right\} from P(z), then compute P(X) \approx \frac{1}{n}\sum_i P\left(X\vert z_i;\theta\right). Unfortunately the plan is infeasible because in high dimensional spaces, n needs to be very large in order to have a good enough approximation of P(X) (imagine how much samples you would need for 200 \times 200 \times 3 images, which is in 120K dimensional space?)
    Now the key to realize is that we don’t need to sample z from all over P(z). In fact, we only need to sample z such that f(z;\theta) is more likely to be similar to samples in the training set. Moreover, it is likely that for most of z, P(X\vert z) is nearly zero, and therefore contribute very little into the estimation of P(X). So the question is: is there any way to sample z such that it is likely to generate X, and only estimate P(X) from those?
    It is the key idea behind VAEs.

That’s quite enough for an overview. Next time we will do some maths and see how we go about maximizing (1). Hopefully I can then convince you that VAEs, GANs and GSNs are really not far away from each other, at least in their core ideas.

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


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


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

Bayesian Optimization part 1: Gaussians and Gaussian Process

SigOpt, công ty làm về Bayesian Optimization  mà có lần mình làm chung vài thứ linh tinh, có hẳn một booth trong KDD năm nay. Nói như Nando de Freitas: “Bayesian Optimization is a thing“, thành ra mình nghĩ nên viết vài bài nghiêm túc về món này.

Hai bài đầu tiên sẽ điểm qua vài công thức cơ bản của Gaussian và Gaussian Process. Bài cuối cùng sẽ nói về lí thuyết Bayesian Optimization và một số chi tiết khác hay gặp trong thực tế.

1. Sample a Gaussian

Cái này phù hợp để làm một câu hỏi phỏng vấn được (cho vị trí nào thì chưa biết): cho 1 hàm lấy số ngẫu nhiên theo phân phối đều trong khoảng [0, 1). Định nghĩa (hoặc viết thuật toán cho) hàm lấy số ngẫu nhiên trong các trường hợp sau:

  1. x \sim \mathcal{N}\left(0, 1\right), với x là scalar value.
  2. x \sim \mathcal{N}\left(\mu, \sigma^2\right), với x là scalar value.
  3. \mathbf{x} \sim \mathcal{N}\left(0,\mathbf{I}\right), với \mathbf{x} \in \mathbb{R}^d
  4. \mathbf{x} \sim \mathcal{N}\left(\mathbf{\mu},\mathbf{\Sigma}\right), với \mathbf{x} \in \mathbb{R}^d

Câu 1 rất đơn giản. Kĩ thuật chuẩn mực để làm việc này gọi là Inverse Transform Sampling. Ý tưởng chính là dùng phân phối cummulative của phân phối Gaussian, như hình sau:

Screen Shot 2016-08-18 at 15.22.45

Do hàm cummulative của phân phối Gaussian có miền giá trị là [0, 1] nên ta sẽ lấy mẫu từ phân phối đều (t_1t_2 trong hình), sau đó dùng hàm ngược của hàm cummulative để tìm giá trị tương ứng x_1x_2.

Lưu ý rằng ta chỉ làm được việc này do hàm cummulative là hàm đơn ánh, và ta tính được chính xác hàm ngược của nó. Trong trường hợp hàm ngược không tính được, ta cần tới các phương pháp phức tạp hơn như Rejection sampling hoặc Gibbs sampling.

Gọi x \sim \mathcal{N}\left(0, 1\right) là kết quả của câu 1, thì ta có thể dễ dàng có kết quả của câu hỏi 2 bằng cách tính z = \mu + \sigma x.

Với câu hỏi 3, để ý rằng ma trận covariance là ma trận đơn vị, nên các thành phần x_i trong vector \mathbf{x} là uncorrelated. Thành ra ta có thể lấy mẫu từng phần tử x_i \sim \mathcal{N}\left(0, 1\right) như trong câu 1, và ghép chúng lại thành vector \mathbf{x}.

Với câu hỏi 4, để thực hiện lại trick mà ta đã dùng trong câu 2, ta cần cách nào đó để tính “căn bậc 2” của ma trận covariance \mathbf{\Sigma}. Ta biết rằng phân tích Cholesky có thể biến đổi \mathbf{\Sigma} = \mathbf{LL^T}, nên trick này có thể được dùng lại:

\mathbf{z} = \mathbf{\mu} + \mathbf{Lx},
với \mathbf{x} \sim\mathcal{N}\left(0,\mathbf{I}\right) được lấy mẫu như trong câu 3.

2. Multivariate Gaussian Theorem

Giả sử ta có một phân phối Gaussian trong không gian 2 chiều, và hàm phân phối của nó được vẽ như sau:

Screen Shot 2016-08-18 at 15.23.08

Hai đường màu xanh thể hiện hàm phân phối xác suất đang nói. Phân phối này sẽ có dạng hình nón, với đỉnh nón khá tròn. Tưởng tượng ta dùng 1 con dao để bổ dọc cái nón này theo một đường song song với trục x_2, tại vị trí mà x_1 = C (mặt phẳng màu đen trong hình), thì mặt cắt của cái nón trên mặt phẳng vẫn sẽ là một phân phối Gaussian một chiều.

Đây là intuition quan trọng để hiểu một trong những định lí quan trọng nhất của phân phối Gaussian (cho đến khi mình biết định lí khác quan trọng hơn). Định lí này nói rằng nếu vector (x_1, x_2) tuân theo phân phối Gaussian 2 chiều thì phân phối có điều kiện của x_2 cho trước x_1 cũng là một Gaussian. Một cách tổng quát, định lí phát biểu như sau:

Giả sử \mathbf{x} = \left(\mathbf{x_1, x_2}\right) tuân theo phân phối Gaussian với tham số:

\boldmath{\mu} = \left(\begin{array}{c} \boldmath{\mu}_1 \\ \boldmath{\mu}_2\end{array}\right) \;,\quad \boldmath{\Sigma} = \left(\begin{array}{cc}\boldmath{\Sigma}_{11} &\boldmath{\Sigma}_{12} \\  \boldmath{\Sigma}_{21} & \boldmath{\Sigma}_{22} \end{array}\right)\;,\quad \boldmath{\Lambda} = \boldmath{\Sigma}^{-1} = \left(\begin{array}{cc}\boldmath{\Lambda}_{11} &\boldmath{\Lambda}_{12} \\  \boldmath{\Lambda}_{21} & \boldmath{\Lambda}_{22} \end{array}\right)

thì các phân phối lề (marginals) là Gaussian:

\displaystyle \begin{array}{rl} p\left(\mathbf{x}_1\right) = & \mathcal{N}\left(\mathbf{x}_1; \boldmath{\mu}_1, \boldmath{\Sigma}_1\right) \\ p\left(\mathbf{x}_2\right) = & \mathcal{N}\left(\mathbf{x}_2; \boldmath{\mu}_2, \boldmath{\Sigma}_2\right)\end{array}

và phân phối có điều kiện cũng là Gaussian:

\displaystyle \begin{array}{rl} p\left(\mathbf{x}_1 \vert \mathbf{x}_2\right) = & \mathcal{N}\left(\mathbf{x}_1; \boldmath{\mu}_{1|2}, \boldmath{\Sigma}_{1|2}\right) \\ \boldmath{\mu}_{1|2} = &  \boldmath{\mu}_{1} + \boldmath{\Sigma}_{12}\boldmath{\Sigma}_{22}^{-1}\left(\mathbf{x}_2 - \boldmath{\mu}_2\right) \\ = & \boldmath{\mu}_{1} - \boldmath{\Lambda}_{11}^{-1}\boldmath{\Lambda}_{12}\left(\mathbf{x}_2 - \boldmath{\mu}_2\right) \\ = & \boldmath{\Sigma}_{1|2}\left(\boldmath{\Lambda}_{11}\boldmath{\mu}_1 - \boldmath{\Lambda}_{12}\left(\mathbf{x}_2 - \boldmath{\mu}_2\right)\right) \\ \boldmath{\Sigma}_{1|2} = & \boldmath{\Sigma}_{11} - \boldmath{\Sigma}_{12}\boldmath{\Sigma}_{22}^{-1}\boldmath{\Sigma}_{21} = \boldmath{\Lambda}_{11}^{-1}\end{array}

Nói chung toàn là Gaussian cả.

Định lí này được chứng minh trong các sách ML kinh điển, chẳng hạn quyển này. Đây cũng là nền tảng của Gaussian process, mà ta sẽ xem trong phần sau.