TRƯỜNG ĐẠI HỌC QUỐC GIA HÀ NỘI
ĐẠI HỌC CÔNG NGHỆ HÀ NỘI
----------

Tiểu luận môn:

Khai phá dữ liệu
ĐỀ TÀI

PHƯƠNG PHÁP MONTE CARLO
Học viên:
Lớp:

KHMT – Khoá

Giảng viên:

Hà Nội, Tháng Năm


MỤC LỤC


LỜI NÓI ĐẦU
Ngày nay với sự bùng nổ của cuộc cách mạng khoa học cơng nghệ 4.0 thì học máy
hay học sâu đang ngày càng trở thành những chủ đề nóng cần được nghiên cứu và phổ biến
rộng rãi. Cảm ơn thầy Hà Quang Thụy với môn học “Khai phá dữ liệu” đã truyền đạt những
kiến thức thiết thực về các vấn đề dữ liệu, học sâu…Các hiểu biết về khai phá xử lý dữ liệu,
khai thác bài toán dữ liệu.
Qua cuốn sách “Deep Learning” của tác giả Ian Goodfellow, Yoshua Bengio, Aaron
Courville do thầy cung cấp một lần nữa hệ thống kiến thức cần cho bộ môn học máy, học sâu

trong thời đại công nghệ.
Chương thứ 17 trong cuốn sách có nói tới phương pháp Monte Carlo là một phương
pháp rất hay trong việc giải quyết các bài toán khó trong học sâu, dưới đấy là phương pháp
Monte Carlo.


MONTE CARLO METHODS
Thuật toán ngẫu nhiên được chia làm 2 loại: thuật toán Las Vegas và thuật toán Monte
Cartlo. Thuật tốn Las Vegas ln trả về chính xác câu trả lời (hoặc báo cáo rằng họ đã thất
bại), thuật toán này tiêu thụ một lượng lớn tài nguyên bộ nhớ, thời gian. Ngược lại thuật toán
Monte Cartlo trả về với một kết quả với sai số và sai số này có thể được giảm bớt bằng việc
mở rộng thêm tài ngun (thời gian, bộ nhớ). Khi ta phải tính tốn bất cứ thứ gì thuật tốn
Mote Carlo cũng có thể cung cấp một câu trả lời mang tính xấp xỉ.
Có nhiều vấn đề trong học máy mà chúng ta không mong đợi sẽ có kết quả chính xác
nên chúng ta có thể sử dụng các thuật tốn gần đúng xác định hoặc xấp xỉ Monte Carlo. Cả
hai cách tiếp cận này đều khổ biến trong học máy. Trong bài tiểu luận này, tôi sẽ tập trung vào
phương pháp Monte Carlo.

1. Chọn mẫu và phương pháp Monte Carlo
Nhiều công nghệ quan trọng trong học máy được dùng để hoàn thành mục tiêu trên các
bản vẽ mẫu từ một số phân bố xác suất và sử dụng mẫu này để hình thành một ước tính Monte
Carlo về số lượng mình mong muốn.
1.1.

Tại sao phải chọn mẫu

Có nhiều lý do mà tơi muốn vẽ mẫu từ xác suất phân phối. Chọn mẫu cung cấp cách để
ước tính khoản tiền tích với chi phí giảm. Đôi khi sử dụng điều này cũng giúp tăng tốc độ
đáng kể có thể sẽ phải chi phí một khoản tốn kém nhưng có thể xử lý được như trong trường
hợp tơi trừ đi tồn bộ chi phí đào tạo với minibatches. Trong trường học khác thuật tốn của

tơi u cầu ước tính một tổng khơng thể tách rời, chẳng hạn như độ dốc hàm phân vùng trong
mơ hình vô hướng. Trong nhiều trường hợp khác chọn mẫu là mục tiêu, ta có thể tạo ra một
mơ hình có thể chọn mẫu từ các vùng đào tạo.
1.2.

Khái niệm cơ bản về chọn mẫu Monte Carlo

Khi tổng, tích khơng thể xác định chính xác (ví dụ: tổng có số mũ và khơng có thể đơn
giản hóa chính xác) thường chúng ta có thể ước lượng bằng cách chọn mẫu Monte Carlo. Ý
tưởng là xem tổng hoặc tích chúng ta kì vọng nó sẽ được phân phối và ứng tính gần đúng
bằng mức trung bình tương ứng:
(1.1)
hoặc
(1.2)


là tổng hoắc tích để ước tính, viết lại như một kì vọng, với rằng buộc p là phân bố xác suất
(cho tổng) hoặc mật độ xác suất (cho tích) trên biến ngẫu nhiên .
Chúng ta có thể ước lượng s bằng cách vẽ mẫu từ p và sau đó hình thành trung bình
thực nghiệm
(1.3)
Phép tính xấp xỉ này được chứng mình bởi vài thuộc tính khác nhau. Đầu tiên chúng ta quan
sát được là cân bằng, vì:
(1.4)
Nhưng ngồi ra, định luật số lượng lớn nói rằng nếu các mẫu vật thì trung bình hội tụ gần
như chính xác với gia trị mong đợi:
(1.5)
miễn phương sai của các giới hạn là riêng biệt, Var [f()], bị chặn. Nhìn điều đó rõ ràng hơn,
xem xét phương sai của as n tăng. Phương sai Var [] giảm và hội tụ về 0. Miễn là Var [f()] < :
(1.6)

Kết quả này cho chúng ta biết làm thế nào để ước tính khơng chắc chắn trong Monte Carlo
trung bình hoặc tương đương, lỗi dự kiến trong Monte Carlo xấp xỉ. Tính cả trung bình thực
nghiệm f( và phương sai của nó. Sau đó chia phương sai ước tính cho tổng số lượng mẫu để ra
bộ ước lượng . Định lý giới hạn trung tâm cho biết mức phân phối trung bình của , hội tụ và
phân phối phương sai trung bình và phương sai . Điều này cho phép chúng ta ước tính
khoảng tin cậy xung quanh sử dụng phân bố tích lũy của mật độ thông thường.
Tuy nhiên, tất cả điều này dựa và khả năng chọn mẫu từ phân phối cơ bản p(x), nhưng
khơng phải lúc nào cũng có thể làm vậy. Khi khơng thể chọn mẫu từ p chúng có cịn nhiều
cách khác đước trình bày trong các phần sau. Một cách tiếp cận tổng quát hơn là tạo thành
một chuỗi các bộ ước lượng hội tụ theo hướng phân phối lợi ích. Đó là cách tiếp cận của
chuỗi Monte Carlo Markov.

2. Lấy mẫu theo trọng số
Một bước quan trọng trong q trình phân tích (hoặc tổng kết) được sử dụng bởi phương
pháp Monte Carlo trong phương trình (1.2) quyết định phần nào của tích đóng vai trị xác xuất
p(x) và phần nào sẽ đóng vai trị số lượng trong f(x) giá trị kỳ vọng (theo phân bố xác xuất
đó) được tính theo cơng thức. Khơng có sự phân tách vì p(x) f(x) ln có thể được viết thành:
(2.1)


Bây giờ chúng là chọn mẫu từ q và trung bình . Trong nhiều trường hợp khác chúng ta kỳ
vọng một phép tính q và f đã cho trước, và thực tế là vấn đề được xác định ngay từ đầu kỳ
vọng p và f đương nhiên sẽ được chọn lọc tách ra. Tuy nhiên, đặc điểm kỹ thuật ban đầu của
vấn đề không phải là việc lựa chọn tối ưu về số mẫu cần thiết để có được một mức độ chính
xác nhất định. May mắn thay, hình thức lựa chọn tối ưu q* có thể chuyển hóa dễ dàng. Tối ưu
q* tương ứng với sự quan trọng trong việc chọn mẫu. Do tình trạng giống nhau được trình bày
trong phương trình (2.1) với bất vì bộ ước lượng Mote Carlo nào.
(2.2)
có thể được biến thành một bộ mẫu thử quan trọng
(2.3)

chúng ta dễ dàng nhận ra rằng giá trị của một bộ ước lượng không phụ thuộc vào q:
(2.4)
Tuy nhiên phương sai của bộ ước lượng mẫu theo trọng số có thể nhảy cảm với sự lựa chọn q.
Phương sai được đưa ra bởi:
(2.5)
Phương sai tối thiệu khi q xảy ra là:
(2.6)
Trong đó Z là hằng số chuẩn hóa, được lựa chọn sao cho tổng q*(x) hoặc tích tới 1 là thích
hợp. Phân chia mẫu theo trọng số tốt hơn khi đặt trọng lượng nhiều hơn tích lớn hơn. Trong
thực tế khi f(x) khơng đổi dấu, Var, có nghĩa là một mẫu đơn là đủ khi phân phối ưu tiên được
sử dụng. Tất nhiên, điều này chỉ về tính tốn q*, vấn đề ban đầu đặt ra về cơ bản đã được giải
quyết, vì vậy trong thực tế thường không sử dụng phương pháp này cho trong phân phối tối
ưu.
Bất kì sự lựa chọn nào về phân bố chọn mẫu q đều hợp lệ (theo mẫu năng xuất giá trị kì
vọng chính xác) và q* là giá trị tối ưu (theo tối thiểu phương sai). Chọn mẫu q* thường không
khả thi, nhưng các lựa chọn khác của q có thể là khả thi trong khi phương sai vẫn giảm.
Một cách tiếp cận khác là sự dụng mẫu theo trọng số, trong đó lợi thế của việc khơng u
cầu p hoặc q bình thường hóa. Trong trường hợp các biến rời rạc ươc tính chọn mẫu được đưa
ra bởi
(2.7)


(2.8)
(2.9)
Trong đó là các dạng p và q khơng chuẩn hóa và x(i) là các mẫu từ q. Cơng cụ tính tốn
này thiên vị vì , ngoại trừ tiệm cận khi và mẫu số của phương trình (2.7) hội tụ về 1. Do đó
ước tính này được gọi là khơng thiên vị.
Mặc dù một lựa chọn tốt của q có thể cải thiện đáng kể hiệu quả của phép toán Monte
Carlo, một sự lựa chọn khơng tốt có thể làm kết quả tồi tệ hơn. Quay trở lại phương trình 2.5
chúng ta thấy rằng nếu có các mẫu q mà là lớn thì phương sai của bộ ước lượng có thể rất

lơn. Điều này có thể xảy ra khi q(x) nhỏ và p(x) f(x) cả hai đủ nhỏ ta có thể loại bỏ nó. Q
phân phối thường được chọn là một phân phối rất đơn giản để nó có thể dễ dàng lấy từ mẫu.
Khi không gian x cao sự đơn giản này có thể làm cho sự phối hợp p hoặc p|f| kém. Khi việc
thu thập các mẫu là vô dụng (tổng của các số nhỏ hoặc số 0). Mặt khác, khi trường hợp này ít
khi xảy ra, tỷ lệ có thể rất lớn. Bởi vì sự kiện này rất hiếm, chúng ta khơng hiển thị trong mẫu
điển hình năng xuất đánh giá điển hình của s, được đền bù khi đánh giá quá cao. Nhưng con
số rất lớn hoặc rất nhỏ này là điển hình khi x là chiều cao, bởi vì chiều cao phạm vi năng động
của các xác suất chung có thể rất lớn.
Mặc dù nguy hiểm này, lấy các mẫu theo trọng số và biến thể của rất hữu ích trong học
máy, bao gồm các thuật tốn học sâu. Ví dụ, sử dụng mẫu theo trọng số trong việc tăng tốc
mạng nơron trong mơ hình ngôn ngữ từ vựng lớn hoặc mạng nơron với số đầu ra lớn. Xem
cách chọn mẫu theo trọng số để ước tính một hàm phân vùng (hằng số chuẩn hóa của xác suất
phân phối) và ước tính khả năng can thiệp sâu các mơ hình như bộ mã hóa tự động biến thiên.
Chọn mẫu theo trọng số cũng có thể được sử dụng ước tính tốc độ của hàm chi phí được sử
dụng để đào tạo thơng số mơ hình với hàm radient descent, đặc biệt cho các mơ hình chẳng
hạn như các trình phân loại trong đó phần lớn tổng giá trị của hàm chi phí đến từ số lượng nhỏ
các ví dụ được phân loại sai. Việc chọn mẫu các giá trị khó khăn hơn khi giảm phương sai
trong các trường hợp đó.

3. Chuỗi Markov trong phương pháp Monte Carlo
Trong nhiều trường hợp, chúng ta hy vọng sẽ sử dụng kỹ thuật Monte Carlo nhưng
phương pháp này không dễ thực hiện cho việc vẽ chính xác các mẫu phân phối pmodel(x) hoặc
từ việc chọn một mẫu phân phối q(x) tốt (phương sai nhỏ). Trong học sâu điều này thường
được xảy ra nhất khi pmodel(x) được đại diện bởi một mơ hình. Trong tốn học việc sử dụng
chuỗi Markov trong việc biểu diễn ước tính Mote Carlo được gọi là Markov chain Monte
Carlo methods (MCMV). Chuỗi Markov trong phương pháp Mote Carlo cho học máy được


mơ tả chính xác hơn trong Koller and Friedman (2009). Tiêu chuẩn đảm bảo chung cho kỹ
thuật MCMC chỉ áp dụng khi mơ hình khơng gian xác suất bằng 0 cho bất kì trạng thái nào.

Vì vậy nó phù hợp với các kỹ thuật chọn mẫu từ mơ hình năng lượng (EBM) . Trong EMB,
mọi trạng thái đảm bảo có xác suất khác 0. Phương pháp MCMC trên thực tế áp dụng rộng rãi
hơn và có thể sử dụng với nhiều phân phối xác suất chứa các trạng thái xác suất bằng 0. Tuy
nhiên, các đảm bảo lý thuyết liên quan đến hành vi của phương pháp MCMC phải được
chứng minh trên cơ sở từng trường hợp khác nhau. Trong học sâu, nó được phổ biến dựa vào
các đảm bảo lý thuyết chung cho tất cả các mơ hình dựa trên năng lượng. Để hiểu rõ lý do tại
sao vẽ mẫu dựa trên mơ hình là khó khăn, xem xet EBM chỉ qua hai biến xác định phân phối
p(a, b). Theo thứ tự, để lấy mẫu a chúng ta phải vẽ từ p(a|b), và để lấy mẫu b chúng ta phải vẽ
từ p(b|a). Nhìn nhận nó như một vấn đề quả trứng và con gà (cái nào có trước). Các mơ hình
được chỉ định là tránh điều này vì biểu đồ của chúng định hướng và tuần hoàn. Để thực hiện,
chọn mẫu tổ tiên là mẫu của từng biến trong thứ tự cấu trúc liên kết điều kiện là cha mẹ của
từng biến đã được lấy mẫu. Lấy mẫu tổ tiên hiệu quả, dễ dàng thức hiện.
Trong EBM chúng ta có thể tránh vấn đề gà trứng bằng cách sử dụng chuỗi Markov. Ý
tưởng cốt lõi của chuỗi Markov là có trạng thái x bắt đầu như một giá trị tùy ý. Theo thời gian
chúng tôi cập nhật x liên tục. Cuối cùng x trở thành (rất gần) với một mẫu từ p(x). Chính thức,
một chuổi markov được xác định bởi một trạng thái ngẫu nhiên x và phân bố chuyển tiếp
T(x’|x) xác định cập nhật ngẫu nhiên trạng thái x’ từ trạng thái x. Chạy chuỗi Markov có
nghĩa là liên tục cập nhật trạng thái x thành giá trị x’ lấy mẫu từ T(x’|x).
Để hiểu được lý thuyết hoạt động của phương thức MCMC nó hữu ích cho vấn đề tham
số. Đầu tiên ta hạn chế việc biến ngẫu nhiên x có nhiều trạng thái. Chúng ta có thể để x đại
diện cho một số nguyên dương. Các giá trị khác của x sẽ ánh xạ nó trong vấn đề ban đầu.
Hãy xem nhưng gì xảy ra khi chúng ta chạy vô số các chuỗi Markov song song. Tất cả
các trạng thái khác của chuỗi Markov được rút ra từ một số phân phối trong đó t là số thời
gian đã trôi qua. Bắt đầu, chọn q(0) là số để khởi tạo tùy ý cho x cho mỗi chuỗi Markov. Sau
đó q(t) bị ảnh hưởng bởi tất cả các bước tiếp theo của chuỗi Markov. Mục tiểu của chúng ta là
để hội tụ thành p(x).
Bởi vì chúng ta đã đặt vấn đề tạo tham số nguyên dương x, chúng ta có thể mơ tả xác suất
q bằng vector v, với
(3.1)
Hãy xem đều gì xảy ra khi chúng ta cập nhật của chuổi Markov từ x thành x’. Xác suất

của trạng thái duy nhất là


(3.2)
Sử dụng tham số là số nguyên dương. Chúng ta có thể mơ tả q trình chuyển đổi tốn tử
T sử dụng ma trận A. A được định nghĩa như sau:
(3.3)
Sử dụng định nghĩa, chúng ta có thể viết lại phương trình (3.2). Thay vì viết nó vào q và
T có thể hiểu như là trạng thái cập nhật đơn lẻ. Chúng ta có thể sử dụng v và A cho việc mơ tả
cách phân phối trên tồn bộ chuỗi Markov (chạy song song) thay đổi khi cập nhật:
(3.4)
Áp dụng cập nhật chuỗi Markov liên tục làm cho ma trận A được lặp lại nhiều lần. Nói
cách khác, chúng ta có thể nghĩ nó như là một tiến trình lũy thừa ma trận A:
(3.5)
Ma trận A có cấu trúc đặc biệt bởi vì mỗi dịng đại điện cho một phân phối xác suất. Các
ma trận như vậy được gọi là ma trận ngẫu nhiên. Nếu có một trạng thái khơng chuyển sang
bất kì trạng thái nào cho t, theo định lý Perron-Frobenius đảm bảo giá trị riêng lớn nhất là số
thực và bằng 1. Thêm nữa, chúng ta có thể nhìn thấy tất cả giá trị riêng lũy thừa:
(3.6)
Tiến trình này làm cho tất cả các giá trị riêng không bằng 1 phân rã thành 0. Dưới một số
điều kiện bổ sung, A đảm bảo cho chỉ một vector riêng có giá trị riêng bằng 1. Do đó q trình
hội tụ một phân phối cố định đôi khi được gọi là phân phối cân bằng. Hội tụ,
(3.7)
Và tương tự điều kiện này được giữ cho mọi bước bổ sung. Đây là phương trình vector
riêng. Để trở thành điểm dừng, v phải là một vector riêng tương ứng với giá trị riêng bằng 1.
Điều kiện này đảm bảo khi chúng ta đạt đến phân phối tĩnh. Các ứng dụng lặp lại của quy
trình lấy mẫu chuyển tiếp khơng thay đổi phân phối trên các trạng thái của tất cả các chuỗi
Markov khác nhau (tất nhiên mặc dù nhà điều hành chuyển đổi thay đổi từng trạng thái riêng
lẻ). Nếu chúng ta đã chọn T đúng, thì phân phối tĩnh q sẽ bằng nhau với p phân phối mà
chúng tôi muốn lấy mẫu từ. Chúng tôi sẽ mô tả cách chọn T ở phần sau.f

Hầu hết các thuộc tính của chuỗi Markov với các trạng thái có thể đếm được đều có thể
được khái qt hóa để biến liên tục. Trong tình huống này, một số tác giả gọi chuỗi Markov
một chuỗi Harris nhưng chúng tôi sử dụng thuật ngữ Chuỗi Markov để mô tả cả hai điều kiện.


Nói chung, một chuỗi Markov với nhà điều hành chuyển tiếp T sẽ hội tụ, dưới ánh sáng điều
kiện, đến một điểm cố định được mơ tả bởi phương trình.
(3.8)
trong trường hợp rời rạc chỉ viết lại phương trình (3.7). Khi x là rời rạc, kỳ vọng tương ứng
với tổng, và khi x là liên tục, kỳ vọng tương ứng với tích phân.
Bất kể trạng thái là liên tục hay rời rạc, tất cả chuỗi Markov phương pháp bao gồm nhiều
lần áp dụng bản cập nhật ngẫu nhiên cho đến khi cuối cùng trạng thái bắt đầu lấy mẫu từ sự
phân bố cân bằng. Chạy chuỗi Markov cho đến khi nó đạt đến sự phân bố cân bằng của nó
được gọi là "đốt cháy" chuỗi Markov. Sau khi chuỗi đã đạt đến trạng thái cân bằng, một chuỗi
vô hạn nhiều mẫu có thể được rút ra từ sự phân bố cân bằng. Họ đang phân phối giống nhau
nhưng bất kỳ hai mẫu liên tiếp nào sẽ có mối tương quan cao với nhau. Do đó, một chuỗi các
mẫu hữu hạn có thể khơng mang tính đại diện của sự phân bố cân bằng. Một cách để giảm
thiểu vấn đề này là trả lại chỉ mỗi n mẫu liên tiếp, để ước tính của chúng tơi về số liệu thống
kê của sự phân bố cân bằng không bị thiên vị bởi sự tương quan giữa một MCMC mẫu và một
số mẫu tiếp theo. Do đó, chuỗi Markov đáng để sử dụng vì thời gian cần thiết để ghi vào sự
phân bố cân bằng và thời gian cần thiết để chuyển đổi từ mẫu này sang mẫu khác đã được giải
thích hợp lý sau khi đạt đến trạng thái cân bằng. Nếu người ta mong muốn các mẫu thực sự
độc lập, người ta có thể chạy nhiều chuỗi Markov song song. Cách tiếp cận này sử dụng tính
tốn song song thêm để loại bỏ độ trễ. Chiến lược chỉ sử dụng một chuỗi Markov để tạo ra tất
cả các mẫu và chiến lược sử dụng một chuỗi Markov cho mỗi mẫu mong muốn là hai thái
cực; học viên học tập sâu thường sử dụng một số chuỗi tương tự như số lượng ví dụ trong một
xe nhỏ và sau đó rút ra càng nhiều mẫu khi cần thiết từ bộ chuỗi Markov cố định này. Một số
thường được sử dụng chuỗi Markov là 100. Một khó khăn khác là chúng ta khơng biết trước
bao nhiêu bước chuỗi Markov phải chạy trước khi đạt được sự phân bố cân bằng của nó.
Chiều dài này thời gian được gọi là thời gian trộn. Nó cũng rất khó để kiểm tra xem một

Markov chuỗi đã đạt đến trạng thái cân bằng. Chúng tơi khơng có lý thuyết chính xác để
hướng dẫn chúng tơi trả lời câu hỏi này. Lý thuyết cho chúng ta biết rằng chuỗi sẽ hội tụ,
nhưng không nhiều hơn nữa. Nếu chúng ta phân tích chuỗi Markov từ quan điểm của ma trận
A hành động trên một vectơ xác suất v, sau đó chúng ta biết rằng chuỗi hỗn hợp khi At đã mất
hiệu quả tất cả các giá trị riêng từ A ngoài giá trị riêng biệt duy nhất của 1. Điều này có nghĩa
là độ lớn của giá trị riêng lớn thứ hai sẽ xác định thời gian trộn. Tuy nhiên, trong thực tế,
chúng ta không thể thực sự đại diện cho chuỗi Markov về mặt ma trận. Số trạng thái mà mơ
hình xác suất của chúng tơi có thể truy cập có số lượng lớn theo số mũ, do đó khơng thể đại
diện v, A, hoặc các giá trị riêng của A. Do những trở ngại này, chúng ta thường làm không biết


liệu chuỗi Markov có trộn lẫn hay khơng. Thay vào đó, chúng tơi chỉ cần chạy Markov chuỗi
trong một khoảng thời gian mà chúng tơi ước tính gần đúng là đủ và sử dụng phương pháp
heuristic để xác định liệu chuỗi có hỗn hợp hay khơng. Những phương pháp heuristic bao
gồm kiểm tra thủ công mẫu hoặc đo lường mối tương quan giữa các mẫu liên tiếp.

4. Chọn mẫu Gibbs
Cho đến nay chúng ta đã mô tả cách vẽ mẫu từ phân phối q(x) bằng nhiều lần vẫn đang
cập nhật .Tuy nhiên, chúng ta chưa mô tả cách đảm bảo rằng q(x) là phân phối hữu ích. Hai
phương pháp cơ bản được xem xét trong cuốn sách học sâu. Đầu tiên là lấy T từ một pmodel đã
học, được mô tả dưới đây với trường hợp lấy mẫu từ EBM. Thứ hai là trực tiếp tham số T và
tìm hiểu nó, để phân phối tĩnh của nó ngầm định nghĩa rõ ràng pmodel. Các ví dụ về phương
pháp thứ hai này được thảo luận trong các phần sau của cuốn sách học sâu.
Trong bối cảnh học sâu, chúng ta thường sử dụng chuỗi Markov để vẽ các mẫu từ một
mô hình dựa trên năng lượng xác định một pmodel phân phối (x). Trong trường hợp này, chúng
ta muốn q(x) cho chuỗi Markov là pmodel(x). Để có được giá trị q(x) mong muốn, chúng ta phải
chọn một T(x’|x) thích hợp.
Một cách tiếp cận khái niệm đơn giản và hiệu quả để xây dựng một chuỗi Markov từ các
mẫu từ pmodel(x) là sử dụng lấy mẫu Gibbs, trong đó lấy mẫu từ T(x’|x) được thực hiện bằng
cách chọn một biến xi và lấy mẫu nó từ pmodel có điều kiện trên các láng giềng của nó trong đồ

thị vơ hướng G xác định cấu trúc của mơ hình dựa trên năng lượng. Cũng có thể lấy mẫu một
số biến tại cùng một thời gian miễn là chúng độc lập về mặt điều kiện cho tất cả những người
láng giềng của chúng. Như được hiển thị trong ví dụ RBM trong trước của cuốn sách học sâu,
tất cả các đơn vị ẩn của một RBM có thể được lấy mẫu đồng thời bởi vì chúng độc lập về mặt
điều kiện từ nhau cho tất cả các đơn vị nhìn thấy được. Tương tự như vậy, tất cả các đơn vị
hiển thị có thể được lấy mẫu đồng thời vì chúng độc lập với điều kiện từ mỗi khác cho tất cả
các đơn vị ẩn. Phương pháp lấy mẫu Gibbs cập nhật nhiều các biến đồng thời theo cách này
được gọi là lấy mẫu Gibbs khối.
Phương pháp thay thế để thiết kế chuỗi Markov để lấy mẫu từ pmodel là khả thi. Ví dụ,
thuật toán Metropolis-Hastings được sử dụng rộng rãi trong các kỹ thuật khác. Trong bối cảnh
của phương pháp tiếp cận học tập sâu sắc đối với mơ hình khơng được hướng dẫn, hiếm khi
sử dụng bất kỳ phương pháp nào khác ngoài lấy mẫu Gibbs. Cải thiện lấy mẫu kỹ thuật là một
biên giới nghiên cứu khả thi.


5. Việc kết hợp giữa các cơng thức riêng biệt
Khó khăn chính liên quan đến các phương pháp MCMC là chúng có xu hướng kết hợp
kém. Lý tưởng nhất là các mẫu liên tiếp từ một chuỗi Markov được thiết kế để lấy mẫu từ p
(x) sẽ hoàn toàn độc lập với nhau và sẽ ghé thăm nhiều các vùng khác nhau trong không gian
x tỷ lệ thuận với xác suất của chúng. Thay vào đó, đặc biệt trong các trường hợp chiều cao,
các mẫu MCMC trở nên rất tương quan. Chúng tôi tham khảo để hành vi như trộn chậm hoặc
thậm chí khơng trộn. Phương pháp MCMC với trộn chậm có thể được xem như vơ tình biểu
diễn một thứ gì đó giống gradient gốc trên chức năng gốc, hoặc tương đương với xác suất, đối
với trạng thái của chuỗi (các biến ngẫu nhiên là lấy mẫu). Chuỗi có xu hướng thực hiện các
bước nhỏ (trong không gian trạng thái của huỗi Markov), từ cấu hình x(t-1) đến cấu hình x(t),
với năng lượng E(x(t)) thường thấp hơn hoặc xấp xỉ bằng năng lượng E(x(t-1))với một ưu tiên
cho các di chuyển mang lại cấu hình năng lượng thấp hơn. Khi bắt đầu từ một thay vì cấu hình
khơng thể xảy ra (năng lượng cao hơn so với các cấu hình điển hình từ p (x)), chuỗi có xu
hướng giảm dần năng lượng của no và chỉ thỉnh thoảng chuyển sang chế độ khác. Khi chuỗi
đã tìm thấy một vùng năng lượng thấp (cho ví dụ, nếu các biến là pixel trong một hình ảnh,

một vùng năng lượng thấp có thể là một đa tạp được kết nối của các hình ảnh của cùng một
đối tượng), mà chúng tôi gọi là một chế độ, chuỗi sẽ có xu hướng đi bộ xung quanh chế độ đó
(sau một loại đi bộ ngẫu nhiên). Một lần trong một thời gian nó sẽ bước ra khỏi chế độ đó và
thường trở lại nó hoặc (nếu nó tìm thấy một lối thốt) di chuyển về phía chế độ khác. Vấn đề
là thành cơng các tuyến thoát hiểm là rất hiếm đối với nhiều bản phân phối thú vị, vì vậy
chuỗi Markov sẽ tiếp tục lấy mẫu cùng một chế độ dài hơn.
Điều này rất rõ ràng khi chúng ta xem xét thuật toán lấy mẫu Gibbs. Trong hoàn cảnh
này, hãy xem xét xác suất chuyển từ một chế độ sang chế độ lân cận trong một số bước nhất
định. Điều gì sẽ xác định xác suất đó là hình dạng của “rào cản năng lượng” giữa các chế độ
này. Chuyển tiếp giữa hai chế độ được ngăn cách bởi hàng rào năng lượng cao (một vùng có
xác suất thấp) là ít khả năng hơn (về mặt chiều cao của rào cản năng lượng). Đây là minh họa
trong hình 1. Vấn đề phát sinh khi có nhiều chế độ với xác suất cao được phân cách bởi các
vùng có xác suất thấp, đặc biệt là khi mỗi bước lấy mẫu Gibbs phải cập nhật chỉ một tập nhỏ
các biến có các giá trị phần lớn được xác định bởi các biến số khác.
Như một ví dụ đơn giản, hãy xem xét một mơ hình dựa trên năng lượng qua hai biến a và
b, là cả đều là số nhị phân có dấu, nhận giá trị −1 và 1. Nếu E(a, b) = −ab đối với một số số
dương lớn , thì mơ hình thể hiện niềm tin mạnh mẽ rằng và b có cùng dấu. Xem xét cập nhật b
bằng cách sử dụng bước lấy mẫu Gibbs với a = 1. Phân bố có điều kiện trên b được cho bởi P
(b = 1 | a = 1) = σ (). Nếu w là lớn, saturates sigmoid, và xác suất cũng gán b là 1 là gần 1.


Tương tự, nếu a = −1, xác suất gán b là −1 là gần 1. Theo Pmodel(a, b), cả hai dấu hiệu của cả
hai biến đều có khả năng giống nhau.

Hình 1: Đường dẫn tiếp theo lấy mẫu Gibbs cho ba bản phân phối, với Markov chuỗi được
khởi tạo ở chế độ trong cả hai trường hợp. (Trái) Phân phối bình thường đa biến với hai biến
độc lập. Lấy mẫu Gibbs trộn đều vì các biến độc lập. (Trung tâm) Phân phối bình thường đa
biến với các biến tương quan cao. Sự tương quan giữa các biến làm cho chuỗi Markov khó
trộn lẫn. Bởi vì cập nhật cho mỗi biến phải được điều chỉnh trên biến số khác, tương quan
làm giảm tốc độ chuỗi Markov có thể di chuyển khỏi điểm xuất phát. (Phải) Một hỗn hợp của

Gaussians với các chế độ phân tách rộng rãi không được căn chỉnh trục. Kết hợp lấy mẫu
Gibbs rất chậm vì rất khó thay đổi chế độ trong khi thay đổi chỉ có một biến tại một thời
điểm.
Theo Pmodel (a|b) cả hai biến có cùng dấu. Điều này có nghĩa là mẫu Gibbs sẽ rất ít khi đảo đấu
các biến này.
Trong các tình huống thực tế hơn, thách thức thậm chí cịn lớn hơn bởi vì chúng ta khơng
quan tâm chỉ về việc chuyển đổi giữa hai chế độ nhưng thông thường hơn giữa tất cả các chế
độ mà một mơ hình thực có thể chứa. Nếu một số chuyển đổi như vậy rất khó vì khó trộn giữa
các chế độ, sau đó chúng ta sẽ rất khó để có được một bộ mẫu đáng tin cậy bao gồm hầu hết
các chế độ và sự hội tụ của chuỗi để phân phối cố định của nó là rất chậm.
Đơi khi vấn đề này có thể được giải quyết bằng cách tìm các nhóm phụ thuộc nhiều đơn
vị và cập nhật tất cả chúng đồng thời trong một khối. Thật không may, khi các phụ thuộc phức
tạp, nó có thể khó tính tốn để vẽ mẫu từ nhóm. Xét cho cùng, vấn đề mà chuỗi Markov ban
đầu giới thiệu để giải quyết vấn đề này là lấy mẫu từ một nhóm lớn các biến.


Trong bối cảnh các mơ hình có biến ẩn, xác định phân phối chung p model (x, h), chúng ta
thường vẽ các mẫu x bằng cách xen kẽ giữa lấy mẫu từ p model (x | h) và lấy mẫu từ mơ hình
p(h|x). Từ quan điểm trộn

Hình 2: Minh họa về vấn đề trộn chậm trong các mơ hình xác suất sâu. Mỗi bảng phải được
đọc từ trái sang phải, từ trên xuống dưới. (Trái) Các mẫu liên tiếp từ lấy mẫu Gibbs được áp
dụng cho một máy Boltzmann sâu được đào tạo về bộ dữ liệu MNIST. Các mẫu liên tiếp
tương tự nhau. Vì việc lấy mẫu Gibbs được thực hiện trong một mơ hình đồ họa sâu, sự tương
tự này dựa trên hình ảnh ngữ nghĩa hơn là ngun các tính năng, nhưng vẫn khó cho chuỗi
Gibbs chuyển đổi từ một chế độ của phân phối khác, ví dụ bằng cách thay đổi nhận dạng chữ
số. (Phải) Liên tiếp các mẫu tổ tiên từ một mạng lưới đối kháng sinh sản. Vì lấy mẫu tổ tiên
tạo ra từng mẫu độc lập với các mẫu khác, khơng có vấn đề trộn.
nhanh chóng, chúng tơi muốn pmodel (h | x) có entropy rất cao. Tuy nhiên, từ quan điểm của
việc học một biểu diễn hữu ích của h, chúng tơi muốn h để mã hóa đủ thơng tin về x để tái tạo

lại nó tốt, ngụ ý rằng h và x nên có thơng tin lẫn nhau rất cao. Hai mục tiêu này có tỷ lệ cược
với mỗi mục tiêu khác. Chúng ta thường tìm hiểu các mơ hình sinh học rất chính xác mã hóa
x thành h nhưng khơng thể trộn tốt. Tình trạng này phát sinh thường xuyên với Boltzmann
máy móc - sự phân phối của máy Boltzmann càng trở nên sắc nét, nó là để lấy mẫu chuỗi
Markov từ phân phối mơ hình để trộn đều. Điều này vấn đề được minh họa trong hình 2.
Tất cả điều này có thể làm cho các phương pháp MCMC ít hữu ích hơn khi phân phối sự
quan tâm có cấu trúc đa dạng với đa tạp riêng biệt cho mỗi lớp: phân phối được tập trung
xung quanh nhiều chế độ và các chế độ này được phân cách bởi các khu vực rộng lớn năng
lượng cao. Loại phân phối này là những gì chúng ta mong đợi trong nhiều phân loại vấn đề và
sẽ làm cho các phương pháp MCMC hội tụ rất chậm vì trộn chậm giữa các chế độ.


5.1.

Sự xáo trộn giữa các phương thức

Khi phân phối có các đỉnh nhọn có xác suất cao được bao quanh bởi các vùng xác suất
thấp, rất khó để kết hợp giữa các chế độ phân phối khác nhau. Một số kỹ thuật để trộn nhanh
hơn dựa trên việc xây dựng các phiên bản thay thế phân phối đích trong đó các đỉnh không
cao và xung quanh thung lũng không thấp. Các mơ hình dựa trên năng lượng cung cấp một
cách đặc biệt đơn giản để làm như vậy. Cho đến nay, chúng tơi đã mơ tả một mơ hình dựa trên
năng lượng như xác định một xác suất phân phối
(5.1)
Các mơ hình dựa trên năng lượng có thể được tăng cường với sự kiểm soát tham số bổ sung
phân phối đạt mức cao là:
(5.2)
Tham số β thường được mô tả như là nghịch đảo của nhiệt độ, phản ánh nguồn gốc của các
mơ hình dựa trên năng lượng trong vật lý thống kê. Khi mà nhiệt độ giảm xuống mức 0 và
tăng lên đến vơ cùng, mơ hình dựa trên năng lượng trở nên xác định. Khi nhiệt độ tăng lên
đến vô cùng và β giảm xuống 0, phân phối (x rời rạc) trở nên đồng nhất.

Thông thường, một mô hình được đào tạo để được đánh giá tại β = 1. Tuy nhiên, chúng ta
có thể thực hiện sử dụng nhiệt độ khác, đặc biệt là những nơi mà β <1. ủ là một chung chiến
lược pha trộn giữa các chế độ p1 nhanh chóng bằng cách vẽ các mẫu với β <1.
Chuỗi Markov dựa trên sự chuyển tiếp cường độ (Neal, 1994) tạm thời lấy mẫu từ các
bản phân phối nhiệt độ cao hơn để trộn với các chế độ khác nhau, sau đó tiếp tục lấy mẫu từ
phân bố nhiệt độ đơn vị. Những kỹ thuật này đã được áp dụng cho các mơ hình như RBMs
(Salakhutdinov, 2010). Khác cách tiếp cận là sử dụng tính tốn song song (Iba, 2001), trong
đó chuỗi Markov mơ phỏng nhiều trạng thái khác nhau song song, ở các nhiệt độ khác nhau.
Cao nhất trạng thái nhiệt độ trộn chậm, trong khi trạng thái nhiệt độ thấp nhất, ở nhiệt độ 1,
cung cấp các mẫu chính xác từ mơ hình. Tốn tử chuyển đổi bao gồm một cách ngẫu nhiên
trao đổi trạng thái giữa hai mức nhiệt độ khác nhau, để mẫu xác suất đủ cao từ khe nhiệt độ
cao có thể nhảy vào khe nhiệt độ thấp hơn. Cách tiếp cận này cũng đã được áp dụng cho RBM
(Desjardins et al., 2010; Cho et al., 2010). Mặc dù ủ là một cách tiếp cận đầy hứa hẹn, tại
điểm này nó đã không cho phép các nhà nghiên cứu tiến bộ mạnh mẽ trong việc giải quyết
thách thức lấy mẫu từ EBM phức tạp. Một lý do có thể là ở đó là nhiệt độ tới hạn mà q trình
chuyển đổi nhiệt độ phải là rất chậm (khi nhiệt độ giảm dần) để ủ có hiệu lực.


5.2.

Độ sâu có thể trộn

Khi vẽ mẫu từ mơ hình biến tiềm ẩn p (h, x), chúng ta đã thấy rằng nếu p(h|x) mã hóa x
quá tốt, sau đó lấy mẫu từ p(x|h) sẽ không thay đổi x rất nhiều và trộn sẽ nghèo. Một cách để
giải quyết vấn đề này là làm cho h trở thành một đại diện sâu sắc, mã hóa x thành h theo cách
mà chuỗi Markov trong khơng gian của h có thể trộn dễ dàng hơn. Nhiều thuật toán học đại
diện, như vậy như bộ tự động và RBM, có xu hướng tạo ra phân phối cận biên trên h thống
nhất hơn và đơn phương hơn so với phân phối dữ liệu gốc trên x. Nó có thể được lập luận
rằng điều này phát sinh từ việc cố gắng giảm thiểu lỗi tái thiết khi sử dụng tất cả khơng gian
biểu diễn có sẵn, bởi vì giảm thiểu lỗi tái tạo qua các ví dụ đào tạo sẽ đạt được kết quả tốt hơn

khi các ví dụ đào tạo khác nhau có thể dễ dàng phân biệt với nhau trong không gian h và do
đó tách biệt tốt. Bengio et al. (2013a) đã quan sát thấy các ngăn xếp tự động hóa hoặc RBM
mang lại phân phối cận biên trong không gian h cấp cao nhất xuất hiện nhiều hơn trải ra và
thống nhất hơn, với ít khoảng cách giữa các vùng tương ứng sang các chế độ khác nhau (danh
mục, trong thử nghiệm). Đào tạo RBM trong đó khơng gian cấp cao hơn cho phép lấy mẫu
Gibbs để trộn nhanh hơn giữa các chế độ. Nó vẫn cịn tuy nhiên khơng rõ cách khai thác quan
sát này để giúp đào tạo và lấy mẫu tốt hơn từ các mơ hình sinh trưởng sâu.
Mặc dù khó trộn, kỹ thuật Monte Carlo rất hữu ích và thường là cơng cụ tốt nhất hiện có.
Thật vậy, chúng là cơng cụ chính được sử dụng để đối đầu chức năng phân vùng có thể xâm
nhập của các mơ hình khơng được phân tích, được thảo luận tiếp theo.