Calculus

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

Advertisements

K-means is a special case of Gaussian Mixtures?

Some while ago I had a coffee chat with a former colleague at Arimo Inc., where we somehow talked about K-means and its properties. At some points I profoundly claimed I am pretty sure that K-means is just a special case of Gaussian mixture models, with all clusters having the same identity covariance matrix. I had no proof for that but deep down, I believe that is true, and my intuition also assures that (c’mon, the K-means training algorithm is almost exactly the EM algorithm used to train GMM). I was even so tempted to sit down and write the maths out, but we went on discussing other stuff, and forgot about K-means.

Without proof, I failed to convince my colleague, but the question still hangs in my head. Plus, after the slides I made several years ago, I planned to write something seriously about GMM and its relatives, but have never managed to.

Last night the question somehow popped out again. For god sake, I can’t handle too many questions simultaneously in my head, so I have to sort this thing out (since it seems to be the easiest one, compared to others).

The answer is actually written in Bishop’s book, section 9.3.2, which is excerpted below

Capture

There we go. Take GMM, if we make the covariance matrices of all the components to be \displaystyle \epsilon \mathbf{I}, where \displaystyle \epsilon is a fixed constant shared by all the components, and take the limit when \displaystyle \epsilon \rightarrow 0 , then we get K-means.

Things get interesting when you don’t take the limit, in which case it will become the Fuzzy C-means algorithm. If you take the limit but the covariance matrix is not constrained to be identity, then you get the elliptical K-means algorithm.

Although my gut feeling was wrong (missing the limit detail), but at the end of the day, learning new things everyday seems to be a rewarding experience.

Local normalization in Neural networks

Local normalization là một kĩ thuật tương đối mới trong neural network. Kĩ thuật này được sử dụng với ConvNN trong paper ImageNet 2012 của Hinton đã giúp giảm độ lỗi từ 1 đến 2%.

Về ý nghĩa, local normalization có thể xem là một kĩ thuật regularization cho neural network. Tuy nhiên thay vì tập trung vào thuật toán Backpropagation như nhiều kĩ thuật khác, phương pháp này trực tiếp thay đổi kiến trúc mạng. Cụ thể phương pháp này tỏ ra có hiệu quả khi sử dụng với các non-linearity không bị chặn như rectified linear unit (ReLU) vì nó ngăn không cho activation của các neuron có giá trị quá lớn so với các neuron chung quanh.

Tuy vậy, như sẽ thấy ngay sau đây, local normalization thêm vào 4 hyper-parameter cho mạng neural, làm tăng thêm gánh nặng hyper-parameter tuning vốn đã là “ác mộng” trong việc huấn luyện mạng neural. Cứ mỗi lớp normalization là có 4 hyper-parameter kèm theo.

Bài này ghi lại công thức và đạo hàm tương ứng của các thể loại local normalization. Chi tiết sẽ được viết sau, khi có dịp.

1. Local response normalization

Across maps:

\displaystyle b_{x,y}^i = \frac{a_{x,y}^i}{\displaystyle \left(k + \alpha\sum_{j=\max\left(0,i-\frac{n}{2}\right)}^{\min\left(N-1,i+\frac{n}{2}\right)}\left(a_{x,y}^j\right)^2\right)^\beta}

Same map:

\displaystyle b_{x,y}^i = \frac{a_{x,y}^i}{\displaystyle \left(k + \alpha\sum_{\left(u, v\right)=\left(\max\left(0,x-\frac{n}{2}\right), \max\left(0,y-\frac{n}{2}\right)\right)}^{\left(\min\left(S-1,x+\frac{n}{2}\right), \min\left(S-1,y+\frac{n}{2}\right)\right)}\left(a_{u,v}^i\right)^2\right)^\beta}

Đạo hàm:
Do local normalization không có tham số nào, nên ta chỉ cần tính đạo hàm của output đối với input. Tuy nhiên việc này hơi tricky vì ta phải tính hai thành phần:

  •  đạo hàm của b_{x, y}^i đối với a_{x, y}^i
  • đạo hàm của b_{x, y}^j đối với a_{x, y}^i, với b_{x, y}^j là output ở trong phạm vi neighborhood của b_{x, y}^i, và dĩ nhiên j \neq i

Ta có:

{\displaystyle \frac{\partial b_{x,y}^{i}}{\partial a_{x,y}^{i}}=\frac{1}{{\displaystyle \left(d_{x,y}^{i}\right)^{\beta}}}-2\alpha\beta a_{x,y}^{i}\frac{{\displaystyle b_{x,y}^{i}}}{d_{x,y}^{i}}}

{\displaystyle \frac{\partial b_{x,y}^{j}}{\partial a_{x,y}^{i}}=-2\alpha\beta a_{x,y}^{i}\frac{{\displaystyle b_{x,y}^{j}}}{d_{x,y}^{j}}}\quad\quad\left(j\neq i\right)

Vậy nên đạo hàm của output đối với a_{x, y}^i là tổng các đạo hàm riêng tại tất cả các vị trí trong local neighborhood của nó:

\displaystyle \frac{\partial b}{\partial a_{x,y}^i} = \displaystyle \sum_{j \in \mathcal{N}\left(i\right)}\frac{\partial b_{x,y}^j}{\partial a_{x,y}^i} = \frac{1}{\left(d_{x,y}^i\right)^\beta} - 2\alpha\beta a_{x,y}^i\sum_{j \in \mathcal{N}\left(i\right)}\frac{b_{x,y}^j}{d_{x,y}^j}

Trong đó d_{x,y}^i là kí hiệu tắt cho mẫu số trong biểu thức ban đầu:

\displaystyle d_{x,y}^{i}=k+\alpha\sum_{j=\max\left(0,i-\frac{n}{2}\right)}^{\min\left(N-1,i+\frac{n}{2}\right)}\left(a_{x,y}^{j}\right)^{2}

Trong cài đặt của thuật toán Backpropagation, ta sẽ quan tâm đến đạo hàm của hàm lỗi (tạm gọi là C) đối với input a_{x, y}^i. Sử dụng chain rule, ta có:

\begin{array}{rl} \displaystyle \frac{\partial C}{\partial a_{x,y}^{i}} & \displaystyle =\sum_{j}\frac{\partial C}{\partial b_{x,y}^{j}}\frac{\partial b_{x,y}^{j}}{\partial a_{x,y}^{i}} \\ & \displaystyle =\frac{\partial C}{\partial b_{x,y}^{i}}\frac{1}{\left(d_{x,y}^{i}\right)^{\beta}}-2\alpha\beta a_{x,y}^{i}\sum_{j}\frac{\partial C}{\partial b_{x,y}^{j}}\frac{b_{x,y}^{j}}{d_{x,y}^{j}}\end{array}

Đây là công thức cuối cùng. Công thức này viết cho trường hợp across maps, trường hợp same map hoàn toàn tương tự.

2. Local contrast normalization

Trong khi local response normalization tính correlation trong vùng neighborhood thì local contrast normalization tính variance bằng cách tính thêm mean của vùng neighborhood. Chi tiết này làm tăng đáng kể sự phức tạp của đạo hàm cũng như khi cài đặt trên máy tính

Across maps:

\displaystyle b_{x,y}^i = \frac{a_{x,y}^i}{\displaystyle \left(k + \alpha\sum_{j=\max\left(0,i-\frac{n}{2}\right)}^{\min\left(N-1,i+\frac{n}{2}\right)}\left(a_{x,y}^j - m_{x,y}^i\right)^2\right)^\beta}

Same map:

{\displaystyle b_{x,y}^{i}=\frac{a_{x,y}^{i}}{{\displaystyle \left(k+\alpha\sum_{\left(u,v\right)=\left(\max\left(0,x-\frac{n}{2}\right),\max\left(0,y-\frac{n}{2}\right)\right)}^{\left(\min\left(S-1,x+\frac{n}{2}\right),\min\left(S-1,y+\frac{n}{2}\right)\right)}\left(a_{u,v}^{i}-m_{x,y}^{i}\right)^{2}\right)^{\beta}}}}

Đạo hàm:

Tương tự như local response normalization, đạo hàm cũng gồm 2 thành phần:

{\displaystyle \frac{\partial b_{x,y}^{i}}{\partial a_{x,y}^{i}}=\frac{1}{{\displaystyle \left(d_{x,y}^{i}\right)^{\beta}}}-2\alpha\beta\left(a_{x,y}^{i}-m_{x,y}^{i}\right)\frac{{\displaystyle b_{x,y}^{i}}}{d_{x,y}^{i}}}

{\displaystyle \frac{\partial b_{x,y}^{j}}{\partial a_{x,y}^{i}}=-2\alpha\beta\left(a_{x,y}^{i}-m_{x,y}^{j}\right)\frac{{\displaystyle b_{x,y}^{j}}}{d_{x,y}^{j}}}\quad\quad\left(j\neq i\right)

Và công thức đạo hàm của hàm lỗi theo input là:

\begin{array}{rl}{\displaystyle \frac{\partial C}{\partial a_{x,y}^{i}}} & ={\displaystyle \sum_{j}\frac{\partial C}{\partial b_{x,y}^{j}}\frac{\partial b_{x,y}^{j}}{\partial a_{x,y}^{i}}}\\ & ={\displaystyle \frac{\partial C}{\partial b_{x,y}^{i}}\frac{1}{\left(d_{x,y}^{i}\right)^{\beta}}-2\alpha\beta\sum_{j}\left(a_{x,y}^{i}-m_{x,y}^{j}\right)\frac{\partial C}{\partial b_{x,y}^{j}}\frac{b_{x,y}^{j}}{d_{x,y}^{j}}}\end{array}

Con đường tơ lụa, hay là hành trình từ perceptron, logistic regression đến neural network

Perceptron khi huấn luyện bằng gradient descent với hàm squared error thì chính là linear regression. Logistic regression chính là linear regression cộng với một hàm non-linearity, và logistic regression cũng là một neural network đơn giản nhất với chỉ 1 neuron. SVM nếu dùng hàm kernel là sigmoid function thì tương đương với một mạng neural 2 lớp.

Bài này sẽ chỉ ra con đường tơ lụa kết nối perceptron, linear regression và logistic regression. Một cách trực quan ta cũng dễ dàng thấy logistic regression tương đương với 1 neuron. Câu chuyện giữa SVM và mạng neural sẽ được trở lại trong bài khác.

Thực ra động lực để viết bài này là sau khi mình có cuộc nói chuyện vô tiền khoáng hậu khoảng 2, 3 tuần trước. Lúc đó đã nói về neural network, optimization và rất nhiều thứ khác, nhưng đến logistic regression thì lại ngọng. Trước giờ  chỉ đọc qua một vài lần nên trong phút chốc không thể nhớ lại đầy đủ và hệ thống được. Tuy nhiên qua đó cũng thấy trí nhớ ngắn hạn của mình ngày càng unreliable. Vì vậy mặc dù còn rất nhiều đề tài muốn đọc và viết, nhưng tạm thời ta sẽ dành thời gian để nhìn lại một chút lịch sử trong bài này.

1. Perceptron

Perceptron có lẽ là thuật toán máy học đơn giản nhất. Được giới thiệu vào những năm 60 của thế kỉ trước, perceptron từng được gắn với nhiều claim rất mạnh mẽ thời bấy giờ. Tuy nhiên năm 1969, Minsky viết quyển sách “Perceptrons” phân tích chi tiết mô hình này, và chỉ ra nhiều hạn chế của nó, khiến perceptron dần thoái trào. Ở đây có một bài viết khá thú vị về chủ đề này.

1.1. Định nghĩa

Trong ngữ cảnh bài toán phân lớp nhị phân (binary classification), thuật toán perceptron sử dụng hàm quyết định là tổng có trọng số giữa vector input \mathbf{x} và vector tham số \boldsymbol{\theta}:

\displaystyle h_\theta\left(\mathbf{x}\right)=\theta_0+\sum_{i=1}^n \theta_i x_i         (1)

Để phân lớp, thuật toán này sử dụng luật quyết định đơn giản sau:

(more…)

Neural network: Backpropagation với softmax và cross-entropy

Entry này chỉ để ghi lại vài công thức cập nhật trọng số cho mạng neural network, dùng trong thuật toán Backpropagation. Những công thức này dùng trong một bài tập lập trình gần đây. Chi tiết về neural network, backpropagation và các khái niệm khác trong bài này có thể sẽ trở lại sau, nếu có dịp.

1. Kiến trúc mạng

Mạng neuron trong bài này có:

  • 3 lớp: input, hidden, output
  • Input layer có 256 logistic units
  • Hidden layer có m logistic units
  • Output layer dùng hàm soft-max với 10 neurons
  • Hàm cost function là cross-entropy.
  • Dùng L2-regularization

Mục tiêu ban đầu của mạng này là nhận dạng chữ số viết tay trong MNIST, do đó ta tạm thời cố định số neurons trong lớp input và output lần lượt là 256 và 10. Đương nhiên mọi khai triển dưới đây đều có thể được tổng quát hóa với số neurons bất kì.

Mạng neural network dùng trong bài.

Nhắc lại về soft-max và cross-entropy: với neuron thứ i trong output layer, ta có:

\displaystyle{ y_i = \frac{e^{z_i}}{\sum_{j\in \text{group}}e^{z_j}}}

Trong đó z_i là phần logit (tổng input) của mỗi neuron. Ở đây thay vì dùng hàm logistics như bình thường, ta dùng hàm soft-max để biểu diễn posterior distribution của toàn bộ output layer. Ta sẽ trở lại với cách làm này khi có dịp.

Khi dùng soft-max cho output layer thì hàm cost function thường được dùng là hàm cross-entropy:

\displaystyle C = -\sum_j t_j \log y_j

Trong đó y_j là output của neuron thứ j theo công thức trên, và t_j là giá trị target của neuron j khi huấn luyện. Ta dùng hàm này, thay vì hàm squared error như bình thường vì với cross-entropy và soft-max thì đạo hàm của C theo y_i có dạng rất đẹp:

{\displaystyle \frac{\partial C}{\partial y_i} = -\frac{t_i}{y_i}}

Đạo hàm này có vài tính chất rất đẹp so với hàm logistic và squared error, đặc biệt là trong backward phase của backpropagation. Ta sẽ trở lại khi có dịp.

(more…)

Đạo hàm và vi phân

Bài này chỉ nhắc lại về notation của đạo hàm (derivative), và link đến một bài viết về vi phân (differential) toàn phần của hàm nhiều biến. Mục đích chính là để tra cứu sau này, nếu có quên.

1. Đạo hàm

Để kí hiệu đạo hàm có vài kiểu notation sau đây. Xem thêm ở wiki.

1.1. Leibniz notation

Thường dùng để biểu diễn đạo hàm của mối liên hệ y = f\left(x\right) của biến độc lập x và biến phụ thuộc y:

\displaystyle \frac{dy}{dx}

Hàm số mà giá trị tại x_0 chính là đạo hàm của y tại x_0 được kí hiệu là:

\displaystyle \frac{d\left(f\left(x\right)\right)}{dx} hay \displaystyle \frac{d}{dx}f\left(x\right)

Các đạo hàm bậc lớn hơn được kí hiệu là:

(more…)