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.

Advertisements

2 comments

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