Tóm tắt Luận văn Thạc sĩ Khoa học: Thuật toán mô phỏng MCMC thích nghi và ứng dụng

Chia sẻ: Na Na | Ngày: | Loại File: PDF | Số trang:23

Thêm vào BST

Báo xấu

40
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục đích chính của luận văn này là trình bày các phương pháp MCMC cơ bản và hai thuật toán MCMC thích nghi từ bài báo. Đồng thời đưa ra các so sánh giữa các thuật toán MCMC và chứng minh chi tiết các định lý trong bài báo cũng như đưa ra một số ứng dụng của thuật toán. Sau đây là bản tóm tắt của luận văn.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt Luận văn Thạc sĩ Khoa học: Thuật toán mô phỏng MCMC thích nghi và ứng dụng

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------- NGUYỄN VĂN TÂN THUẬT TOÁN MÔ PHỎNG MCMC THÍCH NGHI VÀ ỨNG DỤNG Chuyên ngành: Lý thuyết xác suất và thống kê toán học Mã số: 60460106 TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. TRẦN MẠNH CƯỜNG Hà Nội - 2015
Mục lục Lời nói đầu 3 1 Kiến thức chuẩn bị 5 1.1 Sự hội tụ của dãy đại lượng ngẫu nhiên . . . . . . . . . . . 5 1.2 Dãy mixingale . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Các thuật toán mô phỏng cơ bản . . . . . . . . . . . . . . . 7 1.3.1 Phương pháp biến đổi nghịch đảo . . . . . . . . . . 7 1.3.2 Phương pháp loại bỏ . . . . . . . . . . . . . . . . . 7 1.3.3 Phương pháp lấy mẫu quan trọng . . . . . . . . . . 7 1.4 Xích Markov . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2 Phương pháp MCMC 11 2.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2 Mẫu Metropolis - Hastings . . . . . . . . . . . . . . . . . . 11 2.3 Một số thuật toán MCMC . . . . . . . . . . . . . . . . . . 12 2.3.1 Mẫu Gibbs . . . . . . . . . . . . . . . . . . . . . . . 12 2.3.2 Mẫu độc lập . . . . . . . . . . . . . . . . . . . . . . 12 2.3.3 Mẫu Metropolis - Hastings du động ngẫu nhiên . . 13 2.3.4 Mẫu Metropolis (thành phần đơn) . . . . . . . . . . 13 3 MCMC thích nghi 14 3.1 Thuật toán Metropolis du động ngẫu nhiên thích nghi . . . 14 3.1.1 Mô tả thuật toán . . . . . . . . . . . . . . . . . . . 14 3.1.2 Tính chất ergodic . . . . . . . . . . . . . . . . . . . 15 3.1.3 So sánh các thuật toán Metropolis với thuật toán AP 15 1
3.2 Thuật toán Metropolis thích nghi . . . . . . . . . . . . . . 15 3.2.1 Mô tả thuật toán . . . . . . . . . . . . . . . . . . . 15 3.2.2 Tính Ergodic . . . . . . . . . . . . . . . . . . . . . . 16 3.2.3 So sánh các thuật toán Metropolis với thuật toán AM 17 3.3 Một số ứng dụng của MCMC thích nghi . . . . . . . . . . . 18 3.3.1 Mô hình mô phỏng GOMOS . . . . . . . . . . . . . 18 3.3.2 Mô hình suy giảm oxy . . . . . . . . . . . . . . . . . 18 Kết quả chính 20 Tài liệu tham khảo 21 2
Lời nói đầu Để tìm hiểu về MC, ta xét bài toán sau: Giả sử ta cần tính tích phân R1 0 h(x)dx. Theo định lý Newton - Leibnitz, nếu F (x) là một nguyên hàm của h(x) thì
1 I = F (x)
= F (1) − F (0).
0 Tuy nhiên, trong nhiều trường hợp, ta không thể tìm được F(x). Giả sử f (x) là hàm mật độ trên [0, 1] sao cho nếu h(x) 6= 0 thì f (x) > 0. Ta viết R1 lại I = 0 fh(x) (x) f (x)dx. Khi đó, chúng ta lấy mẫu độc lập cùng phân phối (1) (n) (x , ..., x ) từ phân phối xác định bởi mật độ f và xét: n ˆ 1X In = h(x(i) )/f (x(i) ). n i=1 Luật số lớn cho ta thấy rằng Iˆn hội tụ với xác suất 1 tới tích phân I khi n tiến tới ∞ nghĩa là Iˆn → I(h.c.c). Như vậy để tính xấp xỉ I, ta phải thực hiện n mô phỏng cho biến ngẫu nhiên X. Các mô phỏng MC cơ bản này có ưu điểm là dễ thực hiện. Tuy nhiên, nó chỉ mô phỏng được đối với các trường hợp đơn giản. Trong nhiều trường hợp phức tạp như số chiều tăng lên (phân phối nhiều chiều) ... thì các MC cơ bản không thể thực hiện được. Đề giải quyết vấn đề này, chúng ta đưa ra một phương pháp gọi là phương pháp MCMC. Ý tưởng chính của phương pháp MCMC là đi xây dựng một xích Markov có tính ergodic mà phân phối dừng là π . Khi đó, chúng ta chạy X lên đến thời gian dài N và ước lượng E(h(Y )) bởi N1 N P n=1 h(Xn ). Định lý ergodic cho ta biết với N đủ lớn, ước lượng trên sẽ gần đến E(h(Y )). Chúng ta thấy rằng việc chọn lựa phân phối đề xuất là quan trọng cho 3
sự hội tụ của thuật toán MCMC. Việc chọn lựa được phân phối đề xuất tốt thường khó thực hiện vì thông tin về mật độ mục tiêu là không có hoặc rất ít. Hơn nữa, trong thuật toán MCMC, phân phối đề xuất được chọn cho mọi bước mô phỏng. Để sử dụng các thông tin đã thu được trong các bước mô phỏng trước để mô phỏng cho bước tiếp theo, chúng ta đưa ra thuật toán MCMC thích nghi. Ở đó, phân phối đề xuất được cập nhật cùng quá trình sử dụng thông tin đầy đủ tích lũy cho đến thời điểm hiện tại. Mỗi lựa chọn phân phối đề xuất thích nghi sẽ cho chúng ta một dạng MCMC thích nghi. Luận văn gồm 3 chương. • Chương 1 nhắc lại một số kiến thức bổ trợ về sự hội tụ của dãy đại lượng ngẫu nhiên, dãy mixingale, các thuật toán mô phỏng MC cơ bản và xích Markov. • Chương 2 trình bày về các phương pháp MCMC cơ bản. • Chương 3 trình bày chi tiết về hai phương pháp MCMC thích nghi từ hai bài báo [6] và [7]. Đó là thuật toán Metropolis du động ngẫu nhiên thích nghi ([6]) và thuật toán Metropolis thích nghi ([7]). Chỉ ra tính hội tụ của hai thuật toán và chứng minh tính ergodic của thuật toán Metropolis thích nghi. Sau mỗi thuật toán đều đưa ra sự so sánh giữa các thuật toán MCMC. Đồng thời đưa ra một số ứng dụng thực tế của mô hình MCMC thích nghi. Lời đầu tiên, xin chân thành cảm ơn thầy TS. Trần Mạnh Cường đã nhận hướng dẫn và tận tình giúp đỡ tôi hoàn thành luận văn này. Lòng biết ơn sâu sắc tôi cũng xin được gửi đến các thầy cô trong Trường ĐHKHTN - ĐHQGHN, Khoa Toán - Cơ - Tin đã giúp đỡ tôi hoàn thành khóa học. Hà Nội tháng 12 năm 2015 4
Chương 1 Kiến thức chuẩn bị 1.1 Sự hội tụ của dãy đại lượng ngẫu nhiên Giả sử (Ω, F, P ) là không gian xác suất. Định nghĩa 1.1. Một dãy các đại lượng ngẫu nhiên hay biến ngẫu nhiên (Xn ) được gọi là hội tụ hầu chắc chắn đến biến ngẫu nhiên X nếu: P {ω ∈ Ω : lim Xn (ω) 6= X(ω)} = 0. n→∞ Ký hiệu là limn→∞ Xn = X(h.c.c). Định nghĩa 1.2. Cho dãy (Xn ) các biến ngẫu nhiên. Fn (x), F (x) tương ứng là hàm phân phối của Xn , X . Gọi C(F ) là tập các điểm liên tục của hàm F . Ta nói dãy (Xn ) hội tụ theo phân phối đến X nếu ∀x ∈ C(F ), ta có: lim Fn (x) = F (x). n→∞ d Ký hiệu là Xn → − X. Định nghĩa 1.3. Một dãy các biến ngẫu nhiên (Xn ) được gọi là hội tụ theo xác suất đến biến ngẫu nhiên X nếu ∀ε > 0 ta có : P {ω ∈ Ω : |Xn (ω) − X(ω)| > ε} = 0. P Ký hiệu là Xn − → X. 5
Định nghĩa 1.4. Một dãy các biến ngẫu nhiên (Xn ) được gọi là hội tụ theo trung bình bậc r đến biến ngẫu nhiên X nếu r ≥ 1, E|Xn |r < ∞ ∀n, E|X|r < ∞ và : lim E{|Xn − X|r } = 0. n→∞ r L Ký hiệu là Xn −→ X . Định nghĩa 1.5. (luật số lớn) Cho dãy (Xn ) các biến ngẫu nhiên độc lập cùng phân phối có cùng kỳ vọng EXi = µ (i = 1, 2, ...). Đặt Sn = X1 +...+Xn n . Ta nói dãy (Xn ) tuân theo luật số lớn nếu Sn sẽ hội tụ theo xác suất đến µ. Định lí 1.6. (định lý giới hạn trung tâm) Cho dãy (Xn ) các biến ngẫu nhiên độc lập cùng phân phối, có cùng kỳ vọng EXi = µ và phương sai √ n −nµ . Khi đó Zn sẽ hội tụ DXi = σ 2 (i = 1, 2, ...). Đặt Zn = X1 +...+X σ n theo phân phối đến biến ngẫu nhiên Z có phân phối chuẩn tắc. 1.2 Dãy mixingale Định nghĩa 1.7. Cho dãy (Xn )n≥1 các biến ngẫu nhiên bình phương khả tích trong không gian xác suất (Ω, F, P ) và dãy (Fn )+∞ n=−∞ là dãy tăng các σ - đại số con của F . Khi đó, (Xn , Fn ) được gọi là dãy mixingale nếu với mọi dãy hằng không âm cn và ψm , trong đó ψm → 0 khi m → ∞, ta có: ||E(Xn |Fn−m )||2 ≤ ψm cn và ||Xn − E(Xn |Fn+m )||2 ≤ ψm+1 cn , với mọi n ≥ 1 và m ≥ 0. Định lí 1.8. [4, tr. 41] Nếu {Xn , Fn } là một mixingale và {bn } là một dãy hằng dương tăng đến ∞ sao cho ∞ X b−2 2 n cn < ∞ và ψn = O(n −1/2 (logn)−2 ) khi n → ∞ n=1 Pn thì b−1 n i=1 Xi → 0(h.c.c). 6
1.3 Các thuật toán mô phỏng cơ bản 1.3.1 Phương pháp biến đổi nghịch đảo Định lí 1.9. Xét hàm phân phối lũy tích (cdf) F (x). Gọi F −1 là nghịch đảo mở rộng của F , tức là: F −1 (u) = min{x ∈ S : F (x) ≥ u} u ∈ (0, 1] Gọi U là một biến ngẫu nhiên phân phối đều (0, 1) và đặt X = F −1 (U ), khi đó phân phối của X có cdf F (x). (Chú ý rằng đối với hàm phân phối liên tục thì nghịch đảo mở rộng là nghịch đảo thông thường). 1.3.2 Phương pháp loại bỏ Giả sử chúng ta muốn lấy mẫu X là một biến ngẫu nhiên liên tục với hàm mật độ f (x). Chúng ta không biết cách lấy mẫu từ X nhưng chúng ta biết cách lấy mẫu từ một biến ngẫu nhiên Y tương tự với hàm mật độ g(y). Gọi giá của f là supp(f ) = {x : f (x) > 0}. Nếu ta có supp(f ) ⊆ supp(g) và f (x)/g(x) ≤ M ∀x thì ta có thể lấy mẫu từ Y để tạo ra mẫu cho X . Chúng ta lặp lại các bước sau cho đến khi một mẫu được trả về. • Bước 1: Lấy mẫu Y = y từ g(y) và U = u từ phân phối đều U(0, 1). Sang bước 2. f (y) • Bước 2: Nếu u ≤ M g(y) thì đặt X = y . Ngược lại, quay lại bước 1. 1.3.3 Phương pháp lấy mẫu quan trọng Bây giờ, chúng ta tạo ra một mẫu độc lập cùng phân phối (x1 , ..., xn ) từ g và ước lượng I bởi: n n ˆ 1 X f (xi ) 1X I= h(xi ) = w(xi )h(xi ) n i=1 g(xi ) n i=1 Ta gọi cách lấy mẫu này là lấy mẫu quan trọng. Mật độ g được gọi là mật độ đề xuất hoặc mật độ công cụ và trọng số w(xi ) = fg(x (xi ) i) được gọi là 7
trọng số quan trọng. Chú ý rằng Iˆ là một ước lượng không chệch của I . 1.4 Xích Markov Trong đoạn này, chúng ta đưa ra một số định lý về xích Markov quan trọng cho phương pháp MCMC. Định nghĩa 1.10. Xích Markov. Một dãy đại lượng ngẫu nhiên X = {Xn , n = 0, 1, 2, 3, ...} nhận các giá trị trên tập S được gọi là xích Markov nếu: P(Xn+1 ∈ A|Xn = xn ,Xn−1 = xn−1 , ..., X0 = x0 ) = P(Xn+1 ∈ A|Xn = xn ) với mọi n > 0, A ⊆ S , x0 , x1 , ..., xn ∈ S . Định nghĩa 1.11. Tối giản: Xích Markov X được gọi là tối giản nếu tất cả các trạng thái đều liên lạc được, tức là với mọi i, j ∈ S , có một số n ≥ 0 sao cho: P(Xn = i|X0 = j) > 0. Định nghĩa 1.12. Hồi quy Một xích Markov X được gọi là hồi quy nếu xác suất để xích xuất phát từ trạng thái i quay trở lại i sau hữu hạn bước bằng 1, tức là: P(X trở lại trạng thái i sau hữu hạn bước |X0 = i) = 1 ∀i ∈ S. Định nghĩa 1.13. Hồi quy dương : Một xích hồi quy được gọi là hồi quy dương nếu E(Tii ) < ∞ với mọi i ∈ S , trong đó Tii là khoảng thời gian lần đầu tiên trở về trạng thái i. Nếu xích Markov là ergodic với phân phối dừng π thì π(i) = 1/E(Tii ). Ở đây, phân phối dừng π = (π(1), π(2), ...) còn được gọi là phân phối giới hạn. 8
P∞ (n) Định lí 1.14. Trạng thái i là hồi quy khi và chỉ khi n=1 pii = ∞. Định nghĩa 1.15. Tính không chu kỳ: Một xích Markov được gọi là không có chu kỳ nếu không tồn tại d > 2 và các tập con rời nhau S1 , S2 , ..., Sd ⊂ S sao cho: P (x, Si+1 ) = P(Xn+1 ∈ Si+1 |Xn = x) = 1 ∀x ∈ Si , i ∈ {1, 2, 3, ..., d−1} P (x, S1 ) = 1 ∀x ∈ Sd . Định nghĩa 1.16. φ - tối giản. Một xích Markov được gọi là φ - tối giản nếu tồn tại một độ đo không tầm thường φ trong X sao cho ∀A ⊆ X với φ(A) > 0 và ∀x ∈ X , tồn tại số nguyên dương n = n(x) sao cho: P (n) (x, A)(= P(Xn ∈ A|X0 = x)) > 0. Định nghĩa 1.17. Khoảng cách biến phân giữa hai độ đo xác suất P1 và P2 được định nghĩa bởi: kP1 (·) − P2 (·)k = sup |P1 (A) − P2 (A)|. A Định nghĩa 1.18. Hồi quy Harris: Một xích Markov X là hồi quy Harris nếu ∀B ⊆ X với π(B) > 0 và ∀x ∈ X ta có: P(Xn ∈ B với n > 0 | X0 = x) = 1. Định lí 1.19. Phân phối của một xích Markov không có chu kỳ, hồi quy Harris hội tụ đến phân phối giới hạn π , tức là: lim kP n (x, ·) − π(·)k = 0 ∀x ∈ X . n→∞ Chú ý rằng vì: Z (n) q (A) = P(Xn ∈ A) = q (0) (x)P n (x, A)dx nên ta có lim P(Xn ∈ A) = π(A) ∀A ⊆ X và với mọi phân phối ban đầu n→∞ (0) q . 9
Định lí 1.20. Định lý ergodic: Cho h là một hàm thực nào đó và X là một xích Markov có tính ergodic với phân phối dừng π . Xét ergodic trung bình: N ¯hN = 1 X h(Xn ). N n=1 Bây giờ giả sử Y có phân phối π . Nếu Eπ (|h(Y )|) < ∞ thì khi N → ∞, ¯ N hội tụ đến Eπ (h(Y )) với xác suất 1. ergodic trung bình h Định lí 1.21. Định lý giới hạn trung tâm Nếu X là ergodic hình học ([3])và Eπ (h(Y )2+ε ) < ∞ với ε > 0 thì 2 d ¯ N −→ τ h N (Eπ (h(X)), ) N với τ 2 là đại lượng có liên quan đến thời gian tự tương quan đầy đủ của X. 10
Chương 2 Phương pháp MCMC 2.1 Giới thiệu Trong nhiều trường hợp phức tạp như số chiều tăng lên (phân phối nhiều chiều) ... thì các mô phỏng cơ bản không thể thực hiện được. Hơn nữa, bây giờ, giả sử chúng ta muốn biết kỳ vọng của biến ngẫu nhiên h(Y) với Y có phân phối nhiều chiều được cho bởi hàm mật độ (hoặc hàm khối R xác suất) π . Tuy nhiên, chúng ta không thể tính E(h(Y )) = h(y)π(y)dy và các phương pháp mô phỏng cơ bản cũng không thực hiện được. Đề giải quyết vấn đề này, chúng ta đưa ra một phương pháp gọi là phương pháp MCMC. Ý tưởng chính của phương pháp MCMC là đi xây dựng một xích Markov có tính ergodic mà phân phối dừng là π . Khi đó, chúng ta chạy X lên đến thời gian dài N và ước lượng E(h(Y )) bởi N1 N P n=1 h(Xn ). Định lý ergodic cho ta biết với N đủ lớn, ước lượng trên sẽ gần đến E(h(Y )). 2.2 Mẫu Metropolis - Hastings Định nghĩa 2.1. Mẫu Metropolis - Hastings. Chọn các xác suất/mật độ chuyển q(x, y), x, y ∈ S . Chúng được gọi là các phân phối đề xuất. Bây giờ, giả sử Xn = x ∈ S . Tiến hành như sau: 11
1. Lấy mẫu Z= z dựa vào q(x, z), z ∈ S 2. Chấp nhận Z= z với xác suất π(z)q(z, x) α(x, z) = min 1, . π(x)q(x, z) Nếu Z= z được chấp nhận thì Xn+1 = z . Ngược lại, nếu Z= z không được chấp nhận thì Xn+1 = x. 2.3 Một số thuật toán MCMC 2.3.1 Mẫu Gibbs Mẫu Gibbs là một dạng lựa chọn phổ biến sử dụng phân phối có điều (1) (d) kiện đầy đủ như là phân phối đề xuất. Cho xt = (xt , ..., xt ) và (−i) xt = (x1 , ..., x(i−1) , x(i+1) , ..., x(d) ). Chúng ta chọn một thành phần i ∈ 1, ..., d và đề xuất như một trạng thái mới z = (x1 , ..., x(i−1) , y, x(i+1) , ..., x(d) ), với y được lấy mẫu từ mật độ có điều kiện đầy đủ (−i) π(z) π(y|xt )=R . π(x1 , ..., x(i−1) , w, x(i+1) , ..., x(d) )dw Người ta có thể chỉ ra rằng đối với lựa chọn phân phối đề xuất này, xác suất chấp nhận là gần bằng 1. Nếu phân phối có điều kiện đầy đủ là chuẩn tắc và dễ lấy mẫu thì mẫu Gibbs là một lựa chọn rất phổ dụng. Ta xem xét một ví dụ đơn giản: 2.3.2 Mẫu độc lập Như tên gọi chỉ trạng thái mẫu độc lập đề suất không phụ thuộc vào trạng thái hiện tại của xích, tức là q(x, y) = f (y) với mọi x ∈ S , trong đó 12
f là một hàm khối xác suất hoặc mật độ. Xác suất chấp nhận cho mẫu độc lập quy về: π(y)f (x) α(x, y) = min 1, . π(x)f (y) 2.3.3 Mẫu Metropolis - Hastings du động ngẫu nhiên Ở đây, chúng ta chọn q(x, y) = f (y − x) với hàm khối xác suất hoặc mật độ f nào đó. Mẫu Metropolis - Hastings du động ngẫu nhiên có tên như vậy từ thực tế rằng sự đề xuất là được tạo ra theo một cách du động ngẫu nhiên, tức là: y =x+z trong đó z được đưa ra từ f . Xác suất chấp nhận cho phân phối đề xuất này là: π(y)f (x − y) α(x, y) = min 1, . π(x)f (y − x) Chú ý rằng nếu f là đối xứng qua 0 thì đây là một mẫu Metropolis. Ví dụ cho mẫu Metropolis cũng như mẫu du động ngẫu nhiên MH là phân phối trộn. 2.3.4 Mẫu Metropolis (thành phần đơn) Đây là một đề xuất sáng tạo sử dụng hàm khối xác suất hoặc mật độ đề xuất đối xứng, tức là q(x, y) = q(y, x). Khi đó, xác suất chấp nhận được đơn giản hóa: π(x) α(x, y) = min 1, . π(y) 13
Chương 3 MCMC thích nghi 3.1 Thuật toán Metropolis du động ngẫu nhiên thích nghi 3.1.1 Mô tả thuật toán Giả sử rằng các điểm X1 , X2 , ..., Xk đã được lấy mẫu. Khi đó một điểm ứng viên Y được lấy mẫu từ phân phối đề xuất qk (·|X1 , X2 , ..., Xk ) mà bây giờ phụ thuộc vào lịch sử (X1 , X2 , ..., Xk ) (hoặc là một phần của lịch sử). Điểm ứng viên được chấp nhận với xác suất: π(Y ) α(Y, Xk ) = min 1, , π(Xk ) trong đó, π(·) biểu thị mật độ xác suất của phân phối mục tiêu. Trong trường hợp chấp nhận thì ta đặt Xk+1 = Y , ngược lại, Xk+1 = Xk . Phân phối đề xuất qk (·|X1 , X2 , ..., Xk ) là phân phối Gauss với kỳ vọng (trung bình) tại Xk và hiệp phương sai phụ thuộc vào một phần của lịch sử. qt (·|X1 , ..., Xt ) ∼ N (Xt , c2d Rt ), trong đó Rt là ma trận hiệp phương sai cấp d × d được xác định bởi H điểm Xt−H+1 , Xt−H+2 ..., Xt và yếu tố tỷ lệ cd chỉ phụ thuộc vào số chiều d. Hiệp phương sai Rt có thể được tính toán bởi họ các điểm Xt−H+1 , Xt−H+2 ..., Xt trong một ma trận K cấp H × d, ở đây mỗi hàng đại diện 14
cho một điểm lấy mẫu. Khi đó 1 eT e Rt = K K. H −1 Trong đó, K e là ma trận quy tâm (mỗi cột của ma trận tâm bằng hiệu của e = K − E[K]. Trong cột ma trận ban đầu trừ đi trung bình của cột đó): K thực hành, một cách dễ dàng cho việc lấy mẫu từ N (Xt , c2d Rt ), ví dụ như: cd N (Xt , c2d Rt ) ∼ Xt + √ e T N (0, IH ), K H −1 với N (0, IH ) là phân phối Gauss chuẩn tắc. 3.1.2 Tính chất ergodic Trước tiên ta thấy rằng thuật toán AP không có tính Markov. Trong đoạn này, chúng ta sẽ chỉ ra một cách ngắn gọn tính hội tụ của quá trình (Xn ) trong AP. Để đơn giản, chúng ta giả sử phân phối mục tiêu π bị chặn và chúng ta chỉ định một cận dưới cho kích thước của phân phối đề xuất. Bằng cách chiếu phân phối giới hạn của xích (Yk ) trở lại Rd thu được phân phối πe mà Xk mô phỏng cuối cùng. Vì tính đo được của các tập A nên hầu chắc chắn rằng: e(A) = lim (χA (X1 ) + χA (X2 ) + ... + χA (Xn )), π n→∞ với χA là hàm đặc trưng của tập A. 3.1.3 So sánh các thuật toán Metropolis với thuật toán AP 3.2 Thuật toán Metropolis thích nghi 3.2.1 Mô tả thuật toán Giả sử rằng tại thời điểm t − 1 chúng ta lấy mẫu các trạng thái X0 , X1 , ..., Xt−1 , trong đó X0 là trạng thái ban đầu. Khi đó điểm ứng viên Y được lấy mẫu từ phân phối đề xuất (đối xứng tiệm cận) qt (·|X0 , ..., Xt−1 ), 15
bây giờ, nó phụ thuộc vào toàn bộ lịch sử X0 , ..., Xt−1 . Điểm ứng viên Y được chấp nhận với xác suất: π(Y ) α(Xt−1 , Y ) = min 1, π(Xt−1 ) Trong trường hợp chấp nhận, ta đặt Xt = Y , ngược lại, ta đặt Xt = Xt−1 . Phân phối đề xuất qt (·|X0 , ..., Xt−1 ) được dùng trong thuật toán AM là phân phối Gauss với kỳ vọng tại điểm hiện tại Xt−1 và hiệp phương sai Ct = Ct (X0 , ..., Xt−1 ). . Chúng ta chọn một chỉ số t0 > 0 cho độ dài một chu kỳ ban đầu và định nghĩa:  C 0 t ≤ t0 Ct = (3.1) s cov(X , ..., X ) + s εI t > t d 0 t−1 d d 0 Với t ≥ t0 + 1, ta thu được hiệp phương sai Ct thỏa mãn công thức truy hồi: t−1 sd ¯ ¯ T ¯ ¯T T Ct+1 = Ct + (tX t−1 Xt−1 − (t + 1)Xt Xt + Xt Xt + εId ). (3.2) t t 3.2.2 Tính Ergodic Trong thuật toán AP, được mô tả ở trên, hiệp phương sai Ct được tính toán chỉ từ trạng thái cuối H , ở đây H ≥ 2. Ở phần trước, ta chỉ ra phương pháp này không có tính ergodic. Nhưng phân phối giới hạn của AP khác không đáng kể với phân phối mục tiêu. Mục tiêu trong đoạn này chỉ ra thuật toán AM có tính ergodic đúng và vì thế cung cấp mô phỏng chính xác của phân phối mục tiêu. Định lí 3.1. Cho π là mật độ của phân phối mục tiêu có giá trên một tập con đo được bị chặn S ⊂ Rd , và giả sử rằng π là bị chặn trên. Cho ε > 0 và µ0 là phân phối ban đầu bất kì trên S . Định nghĩa xích AM (Xn ) bởi dãy xác suất chuyển tổng quát như trong định nghĩa 3.1. Khi đó xích AM mô phỏng một cách đúng đắn phân phối mục tiêu π : với bất kỳ hàm bị chặn đo được f : S 7→ R, đẳng thức 1 Z lim (f (X0 ) + f (X1 ) + ... + f (Xn )) = f (x)π(dx) n→∞ n + 1 S 16