ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN TRẦN THỊ BÍCH NGỌC PHƯƠNG PHÁP MCMC VÀ MỘT SỐ ỨNG DỤNG LUẬN VĂN THẠC SỸ KHOA HỌC Chuyên ngành : LÝ THUYẾT XÁC SUẤT VÀ THỐNG KÊ TOÁN HỌC Mã số : 60 46 01 06 NGƯỜI HƯỚNG DẪN KHOA HỌC: TS NGUYỄN THỊNH HÀ NỘI, 2014 Mục lục LỜI MỞ ĐẦU BẢNG KÝ HIỆU TỔNG QUAN 1.1 Suy luận Bayes 1.1.1 Đặc điểm mơ hình Bayes 1.1.2 Các tiên nghiệm Jeffreys 1.2 Tích phân Monte Carlo 1.2.1 Bài toán 1.2.2 Xấp xỉ Monte Carlo 1.2.3 Monte Carlo thông qua lấy mẫu theo trọng 1.3 Phương pháp sinh biến ngẫu nhiên 1.3.1 Phương pháp biến đổi 1.3.2 Phương pháp chấp nhận - bác bỏ 1.3.3 Phương pháp tỷ số 1.4 Xích Markov 1.4.1 Các định nghĩa kí hiệu 1.4.2 Sự hội tụ phân phối 1.4.3 Giới hạn giá trị trung bình số 8 9 10 10 11 12 13 13 14 15 16 18 19 19 MẪU GIBBS 21 2.1 Mẫu Gibbs 21 2.2 Thuật toán mở rộng liệu 24 THUẬT TOÁN METROPOLIS-HASTINGS 27 3.1 Thuật toán Metropolis – Hastings 27 3.1.1 Khái niệm 27 3.2 3.3 3.4 3.1.2 Mẫu độc lập 3.1.3 Xích bước ngẫu nhiên Thuật toán Metropolis- Hasting cho phân phối nhiều chiều 3.2.1 Cập nhật khối 3.2.2 Cập nhật thành phần Các dạng khác thuật toán Metropolis - Hastings 3.3.1 Thuật toán chạm chạy 3.3.2 Thuật toán Langevin 3.3.3 Thuật toán đa phép thử MH Thuật toán bước nhảy ngược MCMC cho tốn lựa chọn mơ hình Bayes 3.4.1 Thuật toán bước nhảy ngược MCMC 3.4.2 Xác định điểm thay đổi Phương pháp biến phụ trợ MCMC 4.1 Mô nhiệt luyện 4.2 Mơ điều hồ nhiệt 4.3 Thuật toán Moller 4.4 Thuật toán trao đổi Tài liệu tham khảo 29 30 30 30 34 36 36 37 38 39 39 43 46 48 49 51 53 56 LỜI CẢM ƠN Luận văn hoàn thành với hướng dẫn tận tình nghiêm khắc TS Nguyễn Thịnh Thầy dành nhiều thời gian quý báu để hướng dẫn giải đáp thắc mắc tơi suốt q trình làm luận văn Tơi muốn tỏ lịng biết ơn chân thành sâu sắc tới người thầy Tơi muốn gửi tới tồn thể thầy Khoa Toán - Cơ - Tin học trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội, thầy đảm nhận giảng dạy khóa Cao học 2011 - 2013, đặc biệt thầy cô tham gia giảng dạy nhóm Xác suất thống kê 2011 - 2013 lời cám ơn chân thành công lao dạy dỗ suốt thời gian khóa học Tơi xin cám ơn gia đình, bạn bè, đồng nghiệp anh chị em nhóm Xác suất thống kê 2011 - 2013 quan tâm, giúp đỡ, tạo điều kiện động viên tinh thần để tơi hồn thành khóa học LỜI MỞ ĐẦU Luận văn với mục đích trình bày phương pháp MCMC số ứng dụng nó.Luận văn xây dựng dựa lý thuyết suy luận Bayes,tích phân Monte Carlo xích Markov Luận văn gồm có chương: Chương Tổng quan Suy luận Bayes: giới thiệu suy luận Bayes, đặc điểm mơ hình Bayes, tiên nghiệm Jeffreys Tích phần Monte Carlo: Bài tốn tích phân Monte Carlo, xấp xỉ Monte Carlo, Monte Carlo thông qua lấy mẫu theo trọng số Phương pháp sinh biến ngẫu nhiên: Phương pháp biến đổi, phương pháp chấp nhận - bác bỏ, phương pháp tỷ số Xích Markov: Các định nghĩa kí hiệu, Sự hội tụ phân phối, giới hạn giá trị trung bình Chương Mẫu Gibbs Giới thiệu phương pháp lấy mẫu Gibbs ví dụ cho trường hợp biến ngẫu nhiên nhiều chiều Thuật toán mở rộng liệu:mơ tả thuật tốn số ví dụ tương ứng Chương Thuật toán Metropolis- Hastings Thuật tốn Metropolis- Hasting: Khái niệm, mẫu độc lập, xích bước ngẫu nhiên Thuật toán Metropolis - Hasting phân phối nhiều chiều: giới thiệu ứng dụng thuật toán Metropolis - Hasting biến ngẫu nhiên nhiều chiều cập nhật khối, cập nhật thành phần Các dạng khác thuật toán Metropolis - Hasting: Thuật toán chạm chạy, thuật toán Langevin, thuật toán đa phép thử MH Chương Phương pháp biến phụ trợ MCMC Giới thiệu mặt lý thuyết vài thuật tốn phương pháp MCMC có sử dụng biến phụ trợ: Phương pháp mô nhiệt luyện, mơ điều chỉnh nhiệt,Moller, thuật tốn trao đổi, phương pháp lấy mẫu MH kép Do thời gian gấp rút kiến thức hạn chế nên luận văn khơng thể tránh khỏi thiếu sót, vậy, mong nhận ý kiến đóng góp thầy cô bạn bè đồng nghiệp, xin trân trọng cám ơn Hà Nội, tháng 11 năm 2014 BẢNG KÝ HIỆU MCMC: Xích Markov Monte Carlo AD: Thuật tốn mở rộng liệu AR: Thuật toán chấp nhận - bác bỏ h.c.c: hầu chắn MTH: thuật toán đa phép thử Metropolis - Hastings MTM: thuật toán đa phép thử Metropolis RJMCMC: Thuật toán bước nhảy ngược MCMC Chương TỔNG QUAN 1.1 Suy luận Bayes Suy luận Bayes công thức suy luận xác suất Với ưu điểm tính tốn đơn giản với phát triển gần phương pháp xích Markov Monte Carlo(MCMC) cho việc tính xấp xỉ tích phân có số chiều cao mà suy luận Bayes ngày sử dụng rộng rãi Suy luận Bayes bắt nguồn từ Thomas Bayes (1764), người rút xác suất nghịch đảo xác suất thành công θ dãy phép thử độc lập Bernoulli, θ lấy từ phân phối khoảng (0,1) Ví dụ 1.1 (Mơ hình Bernoulli với tiên nghiệm biết) Giả sử θ ∼ U nif (0, 1) phân phối khoảng (0,1),và x1 , x2 , , xn mẫu lấy từ Bernoulli (θ) với không gian mẫu X = {0, 1} hàm khối xác suất Pr (X = |θ ) = θ; Pr (X = |θ ) = − θ (1.1) X biến ngẫu nhiên Bernoulli với X = thành công, X = thất bại n Ta viết N = i=1 xi số quan sát thành công n phép thử Bernoulli Khi N |θ ∼ B (n, θ) phân phối nhị thức với cỡ n xác suất thành công θ Xác suất nghịch đảo θ cho x1 , x2 , , xn hiểu phân phối hậu nghiệm,được xem phân phối Beta, Beta(1+N,1+n-N) với hàm mật độ xác suất θ(1+N )−1 (1 − θ)(1+n−N )−1 (0 ≤ θ ≤ 1) (1.2) B(1 + N, + n − N ) B (◦ ,◦ ) kí hiệu hàm Beta 1.1.1 Đặc điểm mơ hình Bayes Theo nghiên cứu tốn học biết để xác định mơ hình Bayes ta cần : (i) Chỉ rõ mơ hình lấy mẫu từ liệu quan sát X, có điều kiện đại lượng chưa biết θ (X ∈ X , θ ∈ Θ) X ∼ f (X |θ ) (1.3) f (X |θ ) hàm mật độ xác suất, (ii) Chỉ rõ phân phối biên,được gọi phân phối tiên nghiệm hay đơn giản tiên nghiệm π (θ) θ: θ ∼ π (θ) (θ ∈ Θ) (1.4) Phân tích liệu dựa kết suy luận nhằm mục đích rút gọn tính tốn tích phân phân phối hậu nghiệm, hay nói gọn hậu nghiệm, π (θ |X ) = π (θ) L (θ |X ) π (θ) L (θ |X ) dθ (θ ∈ Θ) (1.5) L (θ |X ) ∝ f (X |θ ) δ gọi thống kê hợp lý δ với X cho 1.1.2 Các tiên nghiệm Jeffreys Một cách tự nhiên ta thấy việc rõ mơ hình Bayes chẳng khác việc tổng hợp thơng tin thực tế theo quan điểm xác suất xác Đồng thời, việc rõ mơ hình xác suất liệu quan sát X việc làm tất yếu Thêm vào xét mơ hình lấy mẫu liệu quan sát X đại lượng chưa biết θ suy luận Bayes yêu cầu tiên nghiệm cho θ phải xác định rõ ràng Trong trường hợp thông tin tiên nghiệm θ sẵn có biết cách xác phân phối xác suất điều hiển nhiên Tuy nhiên, trường hợp thơng tin khơng sẵn có khơng dễ xác định phân phối xác suất xác, đặc biệt toán với số chiều cao, phương pháp thường sử dụng phương pháp Jeffreys, với việc giả thiết tiên nghiệm có dạng: (θ ∈ Θ) πJ (θ) ∝ |I (θ)| (1.6) Trong I (θ) lượng thơng tin Fisher Ví dụ 1.2 Giả sử ta xét mẫu lấy từ phân phối N (µ, 1) Thông tin Fisher thu sau: +∞ φ (x − µ) dx = I (µ) = −∞ Trong 1 φ (x − µ) = (2π) exp − (x − µ)2 hàm mật độ N (µ, 1) Điều dẫn đến tiền nghiệm Jeffreys θ πJ (θ) ∝ (−∞ < µ < +∞) (1.7) Ta thu phân phối hậu nghiệm tương ứng θ cho X sau: πJ (µ |X ) = N (X, 1) 1.2 1.2.1 (1.8) Tích phân Monte Carlo Bài tốn Cho ν độ đo xác suất σ - trường Borel X với khơng gian mẫu X ⊆ Rd , Rd khơng gian Euclide d-chiều Một khó khăn thường gặp tốn ước tính tích phân dạng: Eν [h (X)] = h (x) ν (dx) X 10 (1.9) Ta xét phân phối tiên nghiệm: π (k, pk , Φk , η |Z ) với k thoả mãn Kmin ≤ k ≤ Kmax Khi đó,phân phối hậu nghiệm (k, pk , Φk , η |Z ) là: π(k, pk , Φk , η |Z ) ∝ f (Z |k, pk , Φk , η ) π(k, pk , Φk , η) (3.12) Để mô tả (3.12) RJMCMC bao gồm dạng dịch chuyển "sinh", "tử","cập nhật tham số" 1, Trong dịch chuyển "sinh", thành phần sinh (pk , Φk ) trở thành: {(p1 (1 − p) , φ1 ) , , (pk (1 − p) , φk ) , (p, φ)} 2, Trong dịch chuyển "tử", thành phần lựa chọn ngẫu nhiên i loại bỏ (pk , Φk ) trở thành: pi−1 pi+1 pk p1 , φ1 , , , φi−1 , , φi+1 , , , φk − pi − pi − pi − pi 3, Trong dịch chuyển "cập nhật tham số", tham số (pk , Φk , η) cập nhật thông qua việc sử dụng thuật tốn MH Tóm lại, RJMCMC hoạt động ví dụ sau đây: Cho (k, pk , Φk , η) trạng thái xích Markov Chọn giá trị k ∗ theo ma trận ngẫu nhiên Q, đó, ví dụ ta đặt: Qk,k+1 = Qk,k−1 = Qk,k = 13 với Kmin < k < Kmax QKmin ,Kmin +1 = QKmax ,Kmax −1 = ; QKmin ,Kmin = QKmax ,Kmax = 3 Tùy theo giá trị k ∗ thực bước (a),(b) (c) (a) Nếu k ∗ = k + 1, thực dịch chuyển "sinh" Lấy p ∼ U nif [0, 1] p từ phân phối điều kiện g (φ |pk , Φk , η ) chấp nhận miền với xác suất: 1, π(k + 1, pk+1 , Φk+1 , η |Z ) Qk+1,k π(k, pk , Φk , η |Z ) Qk,k+1 (k + 1) g (φ |pk , Φk , η ) 42 (b) Nếu k ∗ = k − 1, thực dịch chuyển "tử": chọn ngẫu nhiên thành phần , gọi thành phần i, khử chấp nhận miền với xác suất 1, π(k − 1, pk−1 , Φk−1 , η |Z ) Qk−1,k kg (φi |pk−1 , Φk−1 , η ) π(k, pk , Φk , η |Z ) Qk,k−1 (c) Nếu k ∗ = k , thực dịch chuyển "cập nhật tham số", cập nhật tham số (pk , Φk , η) cách sử dụng thuật toán MH Sinh (p∗k , Φ∗k , η ∗ ) từ phân phối điều kiệnq (p∗k , Φ∗ , η ∗ |pk , Φ, η ) chấp nhận điều kiện với xác suất: π(k, p∗k , Φ∗ , η ∗ |Z ) q (pk , Φk , η |p∗k , Φ∗ , η ∗ ) 1, π(k, pk , Φk , η |Z ) q (p∗k , Φ∗ , η ∗ |pk , Φ, η ) Trong bước(a),(b), số hạng Jacobi sử dụng biến đổi đồng dịch chuyển "sinh" "tử" Bước (c) chia thành số bước nhỏ, cập nhật tham số pk , Φk , η cách riêng biệt 3.4.2 Xác định điểm thay đổi Xét ứng dụng sau RJMCMC cho toán xác định điểm thay đổi Đặt Z = (z1 , , zn ) dãy quan sát độc lập Đặt ϑ = (ϑ1 , , ϑn−1 ) số điểm thay đổi, vector nhị phân với ϑc1 = = ϑck = ngược lại Nghĩa là, = c0 < c1 < < ck < ck+1 = n zi ∼ pr (.) , cr−1 < i ≤ cr với r = 1, 2, , k + Mục đích ta xác định vị trí điểm thay đổi c1 , , ck Ta xét trường hợp pr (.) phân phối Gauss với tham số µr , σr2 chưa biết Đặt η (k) = ϑ(k) , µ1 , σ12 , , µk+1 , σk+1 đó:Xk khơng gian mơ hình với k điểm thay đổi,ϑ(k) ∈ Xk , X = n Xk Logarit hợp lý (logk=0 43 likelihood) η (k)  ci k+1  ci − ci−1 (k) L Z η log σi + =  2σi j=c i=1 (zj − µi )2   (3.13)  i−1 +1 Giả sử vector ϑ(k) có phân phối tiên nghiệm: (k) P ϑ = λk (n − − k)! n−1 j=0 λj j! , k = 0, 1, , n − (n − 1)! Tương đương với việc giả sử Xk có phân phối Poisson rút gọn (n−1)! với tham số λ với mẫu [k!(n−1−k)!] Xk tiên nghiệm phù hợp đồng bậc Giả sử phương sai σi2 phụ thuộc vào phân phối Gamma ngược IG (α, β) Giả sử tiên nghiệm độc lập mật độ loga viết k+1 log P η (k) (α − 1) log σi2 + = ak − i=1 β σi2 (3.14) ak = (k + 1) [α log β − log Γ (α)] + log (n − − k)! + k log λ α, β, λ siêu tham số xác định người dùng Loga hậu nghiệm η (k) thu cách thêm (3.8),(3.9) Tích hợp từ phân phối hậu nghiệm đầy đủ, ta có: tham số µ1 σ12 , , µk+1 σk+1 log P ϑ(k) |Z = ak + k+1 log(ci −ci−1 ) − log Γ k+1 log 2π− log(ci −ci−1 −1) +α + i=1  ci   zj  ci   j=c +1 i−1   log β + zj − 2(ci −ci−1 −1)   j=ci−1 +1   (ci −ci−1 −1) +α (3.15) Ta sử dụng ước lượng MPA (cực đại hậu nghiệm) ϑ(k) để giải vấn đề Tuy nhiên, ta sử dụng ước lượng phân phối hậu nghiệm P (Xk , Z) cách sử dụng thuật toán bước nhảy ngược MCMC Khơng tính tổng qt ta xét mơ hình thỏa mãn 44 kmin ≤ k ≤ kmax Bởi tốn xác định điểm thay thể nên dịch chuyển nhảy chiều thực sau: Đặt ϑ(k,l) mẫu thứ l sinh bước lặp t, k số điểm thay đổi mẫu Các mẫu tạo theo bước sau đây: a, Đặt j = k − j = k j = k + theo xác suất qk,j qk,k = với kmin ≤ k ≤ kmax qkmin ,kmin +1 = qkmax ,kmax −1 = 32 vqk,k+1 = qk,k−1 = 3 kmin < k < kmax b, Nếu j = k , cập nhật ϑt (k,l) dịch chuyển đồng thời (mơ tả phía dưới) Nếu j = k + 1, cập nhật ϑt (k,l) dịch chuyển ’sinh’ (mô tả bên dưới) j = k-1, cập nhật ϑt (k,l) dịch chuyển ’tử’ (mô tả bên dưới) Trong dịch chuyển sinh, số ngẫu nhiên kí hiệu u, lần rút từ tập 0,1, ,k, sau số ngẫu nhiên khác, kí hiệu v , rút từ tập {cu + 1, , cu+1 − 1} đề xuất để thiết lập ϑv = Khi đó, kết mẫu biểu thị (k) ϑ∗ Xác suất chấp nhận dịch chuyển sau: Đối với dịch chuyển ’sinh’ xác suất chấp nhận là:    P ϑ(k+1) |X qk+1,k cu+1 − cu −  ∗ (3.16) 1,  P ϑ(k,l) |X qk,k+1  t Số hạng Jacobi 1, mẫu trực tiếp rút không gian Xk+1 Tương tự dịch chuyển “tử”, xác suất chấp nhận là:    P ϑ(k−1)  |X qk−1,k ∗ (3.17) 1,  P ϑ(k,l) |X qk,k−1 cu+1 − cu−1 −  t Đối với dịch chuyển đồng thời, xác suất chấp nhận là:    P ϑ(k)  |X ∗ (3.18) 1,  P ϑ(k,l) |X  t đề nghị đối xứng theo nghĩa: (k,l) T ϑt (k,l) → ϑ(k) = T ϑ(k) ∗ ∗ → ϑt 45 = cu+1 − cu−1 − Chương Phương pháp biến phụ trợ MCMC Ta xét toán lấy mẫu từ phân phối nhiều biến với hàm mật độ f (x) Ta biết nguyên tắc mô Monte Carlo: Để đạt hội tụ tốt mô MC, ta cố gắng lấy tích phân thành phần x nhiều Tuy nhiên, để đẩy nhanh làm chậm mơ người ta bổ sung vào nhiều biến ngẫu nhiên Điều dẫn đến vấn đề sau: 1, Phân phối mục tiêu f (x) nhiều đỉnh: Khi ta sử dụng biến ngẫu nhiên phụ trợ, ví dụ nhiệt độ đo đạc không dễ quan sát mắt thường, chứa mô để giúp hệ thống thoát từ bẫy địa phương 2, Phân phối mục tiêu f (x) chứa số khó chuẩn hóa: Khi ta thực bổ sung biến phụ trợ X vào mô để hủy bỏ số chuẩn hóa Thuật tốn Metropolis - Hastings(MH) bao gồm hai thành phần bản: phân phối mục tiêu phân phối đề nghị Do đó, phương biến phụ trở thực theo hai cách, bổ sung biến phụ trợ phân phối mục tiêu bổ sung biến phụ trợ phân phối đề nghị Phương pháp bổ sung phân phối mục tiêu thực sau: 1, Chỉ rõ biến phụ trợ u phân phối có điều kiện f (u |x) để xác định phân phối đồng thời :f (x, u) = f (u |x) f (x) 2, Cập nhật (x, u) cách sử dụng thuật toán MH mẫu Gibbs Cơng thức bổ sung phân phối đề nghị thực sau: 46 1, Chỉ rõ phân phối đề nghị T (x , u |x) phân phối đề nghị nghịch đảo T (x, u |x ) cho T (x , u |x)du = T (x |x) T (x, u |x )du = T (x |x ) 2, Sinh mẫu đề cử x từ đề nghị T (x , u |x) chấp nhận với xác suất {1, r (x, x , u)} đó: r (x, x , u) = f (x ) T (x, u |x ) f (x) T (x , u |x) Lặp lại bước để sinh x1 , , xN có phân phối xấp xỉ f (x) N rộng Tính đắn của cơng thức trình bày sau Đặt:   K (x |x) = s (x, x∗ , u) dudx∗  s (x, x , u) du + I (x = x ) 1 − U X U (4.1) nhân chuyển dịch tích phân từ x tới x , s (x, x , u) = T (x , u |x) r (x, x , u) I(.) hàm tiêu Khi đó: s (x, x , u) du =∫ {f (x ) T (x, u |x ) , f (x) T (x , u |x)} du f (x) U U (4.2) đối xứng x x Điều kéo theo: f (x) K (x |x) = f (x ) K (x |x ), nghĩa điều kiện cân chi tiết thỏa mãn dịch chuyển x → x Trong chương ta xem xét lại tồn công thức phụ trợ MCMC Các công thức bổ sung phân phối mục tiêu bao gồm mô nhiệt, mô điều chỉnh nhiệt, thuật toán Moller Một cách nghiêm túc, thuật toán bổ sung liệu mô tả mục 2.2 thuộc lớp ta xem xét quan sát thiếu biến ngẫu nhiên phụ trợ 47 4.1 Mô nhiệt luyện Trong công nghiệp, nhiệt luyện có liên quan tới phương pháp sử dụng để luyện thép Đầu tiên thép đốt nóng nhiệt độ cao, hầu hết điểm biển đổi trạng thái lỏng Sau đó, thép làm nguội cách từ từ đủ để tạo nên nguyên tử tự thứ tự mơ hình Mơ hình cao nhất, mà tương ứng với giá trị nhỏ toàn lượng tự thép, thực q trình làm nguội tiếp tục tiến hành chậm vừa đủ Ngược lại, tình trạng kết đơng bị rơi vào trạng thái cực tiểu địa phương lượng tự Rõ ràng thuật tốn MH sử dụng cho mô biến đổi vật rắn nhiều mức nhiệt khác hướng nhiệt độ cân bằng.Giả định mơ hình thuật tốn nhiệt luyện tương tự chương trình nhiệt luyện tốn tối ưu tổ hợp Thuật tốn mơ tả sau: Giả sử mục đích ta tìm giá trị nhỏ tồn phần hàm số H (x),và gọi lượng hàm số mô nhiệt luyện Bằng cách bổ sung cho hệ thống biến ngẫu nhiên phụ trợ, gọi nhiệt độ T, giá trị nhỏ H (x) tương đương để lấy mẫu từ phân phối Boltzmann f (x, T ) ∝ exp (−H (x) |T ) giá trị nhỏ(gần tới 0) T [ Khi T dần tới 0, hầu hết tập trung phân phối f (x, T ) tập trung toàn giá trị nhỏ H (x)], trường hợp này, nói phép lấy mẫu là tối ưu hóa Để lấy mẫu cách thành cơng từ f (x, T ) giá trị nhỏ T, Kirkpatrick đề nghị mô từ dãy phân phối Boltzmann, f (x, T1 ) , , f (x, Tm ) cách tuần tự, nhiệt độ tạo thành dãy giảm T1 > T2 > > Tm với Tm ≈ T1 hợp lý rộng rãi cho hầu hết dịch chuyển dốc MH mức độ chấp nhận Tóm lại, thuật tốn mơ nhiệt luyện mơ tả sau: Định nghĩa 4.1 Thuật tốn mơ nhiệt luỵện Khởi tạo mô nhiệt độ T1 mẫu x0 Tại nhiệt độ Ti , mô phân phối f (x, Ti ) với Ni bước lặp 48 sử dụng mẫu MCMC Thông qua mẫu cuối tới mức nhiệt độ thấp mẫu khởi tạo Từ quan điểm công thức phụ trợ MCMC, mô nhiệt luyện mô phân phối mục tiêu bổ sung f (x, T ) với biến phụ trợ T lấy giá trị từ tập hữu hạn {T1 , , Tm } bậc cố định từ cao tới thấp.Khó khăn chủ yếu việc sử dụng mơ nhiệt luyện việc lựa chọn chương trình làm mát Một chương trình làm mát lợi ích lý thuyết làm lạnh logarit, Ti tập O (1/ log (Mi )) với Mi = N1 + + Ni Chương trình làm mát bảo đảm mô để hội tụ toàn giá trị ngẫu nhiên H (x) với xác suất 1.Tuy nhiên, thực hành, trình chậm khơng có đủ khả chờ khoảng thời gian chạy dài Một chương trình làm mát tuyến tính giảm chương trình làm mát hình học giảm thường sử dụng, chương trình khơng thể đảm bảo cực tiệu tồn đạt Mơ nhiệt luyện có nhiều ứng dụng việc tối ưu hóa, ví dụ toán nhân viên bán hàng lưu động 4.2 Mơ điều hồ nhiệt Giả sử ta muốn lấy mẫu từ phân phối f (x) ∝ exp (−H (x)) , x ∈ X Giống mô nhiệt luyện, mơ điều hồ nhiệt bổ sung phân phối mục tiêu cho f (x) ∝ exp (−H (x) |T ) qua việc bao bổ sung biến ngẫu nhiên phụ trợ T , gọi nhiệt độ, với giá trị hữu hạn sẵn người dùng Mơ điều hồ nhiệt thu từ mô nhiệt luyện qua việc xử lý nhiệt độ T biến ngẫu nhiên phụ trợ cho mơ đồng thời x: • Mơ điều hoà nhiệt cập nhật miền nối (x, T ) cấu thành mẫu Gibbs, nghĩa cập nhật x T phương pháp lựa chọn • Trong mơ điều hoà nhiệt, nhiệt độ thấp đặt 1, mục đích lấy mẫu từ f (x) Giả sử nhiệt độ T thu m giá trị khác T1 > T2 > > Tm , Tm ≡ gọi nhiệt độ mục tiêu 49 Đặt f (x, Ti ) = exp (−H (x) |Ti ) /Zi phân phối thử nghiệm xác định mức nhiệt độ Ti , Zi số chuẩn hóa phân phối.Đặt qij xác suất truyền đề nghị từ mức Ti tới Tj Đặt qi,i+1 = qi,i−1 = qi,i = 1 với < i < m,q1,2 = , qm,m−1 = , q1,1 = , qm,m = 23 Bắt đầu với i0 = mẫu ban đầu x0 ∈ X , mơ điều hồ nhiệt lặp lại bước sau: Định nghĩa 4.2 Mô điều hoà nhiệt Sinh số ngẫu nhiên U ∼ U nif orm [0, 1] xác định giá trị j theo ma trận truyền đề nghị (qij ) Nếu j = it đặt it+1 = it sinh từ hạch MH Kit (x, y) với thừa nhận f (x, Tit ) phân phối dừng Nếu j = it , đặt xt+1 = xt chấp nhận đề nghị với xác suất : 1, Zj Zit exp −H (x) 1 − Tj Tit qj,it qit ,j Zi ước lượng Zi Nếu chấp nhận đặt it+1 = j Ngược lại, đặt it+1 = it Cơ sở trực quan mơ điều hồ nhiệt mô mức nhiệt cao cung cấp khảo sát vùng lượng tốt cho phân phối mục tiêu, mẫu lượng thấp sinh cách truyền tới mức nhiệt độ mục tiêu qua dãy nhiệt độ cập nhật phép toán Theo báo cáo nhiều nhà nghiên cứu, mô điều hồ nhiệt thực chất hội tụ nhanh so với thuật toán MH, đặc biệt phân phối mà vùng lượng giao Bởi bổ sung hữu hiệu mơ điều hồ nhiệt, hai vấn đề cần thiết phải xem xét sau: • Lựa chọn thang nhiệt độ : Nhiệt độ cao T1 cài đặt cho hầu hết dịch chuyển dốc chấp nhận mức Nhiệt 50 độ trung gian thiết lập cách tuần tự, bắt đầu với T1 , thiết lập mức nhiệt độ thấp cho thỏa mãn: V ari (H (x)) δ = O (1) (4.3) δ = Ti+1 − T1i , V ari (.) phương sai H (x) với mối liên quan f (x, Ti ) Điều kiện tương đương yêu cầu phân phối f (x, Ti ) f (x, Ti+1 ) có chồng lấp đáng kể.Trong thực hành V ari (H (x)) ước lượng đại khái qua tính tốn sơ mẫu mức Ti • Ước lượng Zi : Đây chìa khóa tính hiệu mơ điều hồ nhiệt Nếu số chuẩn hóa giả định Zi ước lượng tốt, mô điều hồ nhiệt trình bày giống "bước ngẫu nhiên đối xứng" dọc theo thang nhiệt độ(nếu bước cập nhật x) Ngược lại mắc kẹt mức nhiệt độ biết Sự biểu diễn mô thất bại Trong tính tốn thực tế, Zi ước lượng sử dụng công thức xấp xỉ xác suất Ta ý pha trộn mơ điều hồ nhiệt cho phép từ thời gian chờ đợi song để tạo mơ điều hồ nhiệt làm việc tốt, phân phối kề f (x, Ti ) f (x, Ti+1 ) có chồng lấp đáng kể, yêu cầu phải sử dụng nhiều mức nhiệt độ trung gian Nói cách khác, chí trường hợp lý tưởng mà mơ điều hồ nhiệt thực giống "bước ngẫu nhiên đối xứng" theo thang nhiệt độ, thời gian chờ đợi kỳ vọng cho giao thang nhiệt độ có dần đến O m2 Điều đặt giới hạn khắt khe số lượng mức nhiệt độ mà ta đủ khả để sử dụng mơ Mơ điều hồ nhiệt có ứng dụng thành công nhiều hệ thống phức tạp, xếp protein thiết kế mặt sàn 4.3 Thuật tốn Moller Các khơng gian mẫu, ví dụ không gian mẫu logistic tự động, mẫu Potts mẫu tự động chuẩn tắc sử dụng việc mô hình hóa nhiều tốn kỹ thuật Ví dụ: phân tích hình ảnh, sơ đồ bệnh án,các phân tích di truyền địa lý nhiều toán khác 51 Một vấn đề chủ yếu mẫu số chuẩn hóa khó sử dụng Vấn đề mơ tả sau: giả sử ta có tập liệu X lấy từ mẫu thống kê có hàm thống kê hợp lý: f (x |θ ) = exp {−U (x, θ)} , x ∈ X , θ ∈ Θ Z (θ) (4.4) θ tham số, Z (θ) số chuẩn hóa phụ thuộc θ khơng thể sử dụng dạng đóng Đặt f (θ) hàm mật độ tiên nghiệm θ Phân phối hậu nghiệm θ với x cho xác định sau: f (θ |x) ∝ exp {−U (x, θ)} f (θ) Z (θ) (4.5) Thuật tốn MH khơng thể áp dụng trực tiếp cho mô từ f (θ |x) Z(θ) xác suất chấp nhận địi hỏi phải tính tỷ số khó Z(θ ) θ giá trị đề nghị Moller cộng có bước tiến quan trọng đề xuất bổ sung phân phối f (θ |x) biến ngẫu nhiên phụ trợ cho Z(θ) tỷ số số chuẩn hóa Z(θ ) thay đổi mơ Thuật tốn Moller mô tả sau: Đặt y biến phụ trợ, có khơng gian trạng thái với x Đặt f (θ, y |x) = f (x |θ ) f (θ) f (y |θ, x) (4.6) phân phối nối θ có điều kiện x, f (y |θ, x) phân phối biến ngẫu nhiên phụ trợ y Để mô từ (4.6) cách sử dụng thuật tốn MH, ta sử dụng phân phối đề nghị q (θ , y |θ, y ) = q (θ |θ, y ) q (y |θ ) (4.7) với tương ứng biến đổi thông thường vector tham số θ → θ qua bước lấy mẫu xác lấy mẫu y từ q ( |θ ) Nếu q (y |θ ) đặt f (y |θ ) tỷ số MH viết sau: r (θ, y, θ , y |x) = f (x |θ ) f (θ ) f (y |θ , x) q (θ |θ , y ) f (y |θ ) f (x |θ ) f (θ) f (y |θ, x) q (θ |θ, y ) f (y |θ ) (4.8) số chuẩn hóa chưa biết Z (θ) thay đổi Để tính tốn dễ dàng, Moller đề nghị đặt thêm phân phối đề nghị q (θ |θ, y ) = q (θ |θ ) q (θ |θ , y ) = q (θ |θ ) phân phối phụ trợ: f (y |θ, x) = f y θ ; f (y |θ , x) = f y θ 52 (4.9) θ ước lượng θ, ví dụ thu cách cực đại hàm thống kê hợp lý giả Tóm lại, thuật tốn Moller khởi đầu với điểm tùy ý θ(0) mẫu xác y (0) rút từ f y θ bước lặp bước thể sau: Định nghĩa 4.3 Thuật toán Moller Sinh θ từ phân phối đề nghị q (θ |θt ) Sinh mẫu xác y từ phân phối f (y |θ ) Chấp nhận (θ , y ) với xác suất (1, r) đó: f (x |θ ) f (θ ) f y θ q (θt |θ ) f (y |θt ) r= f (x |θt ) f (θt ) f y θ q (θ |θt ) f (y |θ ) Nếu điều kiện thỏa mãn đặt (θt+1 , yt+1 ) = (θ , y ), ngược lại ta đặt (θt+1 , yt+1 ) = (θt , yt ) 4.4 Thuật toán trao đổi Giống thuật toán Moller thuật toán trao đổi dành riêng cho việc lấy mẫu từ phân phối f (θ |x) (4.5) Thuật toán trao đổi mơ tả sau: Xét phân phối bổ sung: m f (y1 , , ym , θ |x) = π (θ) f (x |θ ) f (yj |θj ) (4.10) j=1 θ i cố định, y1 , , ym biến phụ trợ độc lập với m f (yj |θj ) Giả sử không gian trạng thái x phân phối đồng thời j=1 thay cho θ đề nghị với xác suất q (θi |θ ) Chắc chắn yi = x ta tráo đổi việc đặt x yi Kết tỷ số MH cho thay là: π (θi ) f (x |θi ) f (yi |θ ) r (θ, θi , yi |x) = f (yj |θj ) q (θ |θi ) j=i π (θ) f (x |θ ) f (yi |θi ) f (yj |θj ) q (θi |θ ) j=i 53 Tức là: r (θ, θi , yi |x) = π (θi ) f (x |θi ) f (yi |θ ) q (θ |θi ) π (θ) f (x |θ ) f (yi |θi ) q (θi |θ ) (4.11) Định nghĩa 4.4 Thuật toán trao đổi: Đề nghị θ ∼ q (θ |θ, x) Sinh biến phụ trợ y ∼ f (y |θ ) với xác suất {1, r (θ, θ , y |x)} đó: r (θ, θ , y |x) = π (θ ) f (x |θ ) f (y |θ ) q (θ |θ ) π (θ) f (x |θ ) f (y |θ ) q (θ |θ ) (4.12) Vì thuật tốn tập trung vào hoán vị (θ, x) (θ , y) thuật toán gọi thuật toán trao đổi Thuật toán giúp cải thiện hiệu thuật tốn Moller, thay cần thiết phải ước lượng tham số trước bắt đầu lấy mẫu.Thuật toán trao đổi dẫn tới xác suất chấp nhận cao cho mẫu xác so với thuật tốn Moller Thuật tốn trao đổi xem thuật toán biến phụ trợ MCMC với việc bổ sung phân phối đề nghị , phân phối đề nghị viết lại sau: T (θ → (θ , y)) = q (θ |θ ) f (y |θ ) ; T (θ → (θ , y)) = q (θ |θ ) f (y |θ ) 54 Kết luận Luận văn "Phương pháp MCMC số ứng dụng" trình bày số nội dung sau: • Nêu khái niệm phương pháp MCMC suy luận Bayes, tích phân Monte Carlo, xích Markov • Trình bày số phương pháp lấy mẫu quan trọng phương pháp MCMC: phương pháp lấy mẫu Gibbs thuật tốn Metropolis - Hasting • Ứng dụng thuật toán lấy mẫu Gibbs thuật toán Metropolis Hastings biến ngẫu nhiên nhiều chiều • Giới thiệu sơ lược phương pháp biến phụ trợ MCMC 55 Tài liệu tham khảo [1] Đào Hữu Hồ (1998), Xác suất thống kê, NXB Đại học Quốc gia Hà nội [2] Nguyễn Duy Tiến, Vũ Viết Yên (2006), Lý thuyết xác suất, NXB Giáo dục [3] Nguyễn Duy Tiến, Đặng Hùng Thắng (2001), Các mơ hình xác suất ứng dụng, Phần II: Quá trình dừng ứng dụng, NXB Đại học Quốc gia Hà Nội [4] Nguyễn Duy Tiến (2000), Các mơ hình xác suất ứng dụng, Phần I: Xích Markov ứng dụng, NXB Đại học Quốc gia Hà nội [5] Đặng Hùng Thắng (2012), Xác suất nâng cao, NXB Đại học Quốc gia Hà nội [6] Faming Liang, Chuanhai Liu, Raymond J.Carroll(2010), Advanced Markov chain Monte Carlo methods [7] Dani Gamerman, Hedibert F Lopez (2009), Markov chain Monte Carlo stochastic simulation for Bayesian inference(2nd edition) [8] Mark Steyvers,2011, Computational statistics with Matlab [9] Jean-Michel Marin,Christian P.Robert,2007A practical approach to computational Bayesian statistics 56 ... lượng h (x) Phương pháp tỷ số Phương pháp tỷ số phương pháp thông dụng để sinh số ngẫu nhiên nhiều phân phối thông dụng phân phối Gamma, chuẩn, student-t Ý tưởng tổng quát phương pháp tỷ số tìm cặp... Các phương pháp hiệu mô tả phần sau luận văn Sau số phương pháp thường sử dụng để lấy mẫu từ các phân phối trường hợp công thức hàm phân bố ngược áp dụng 1.3.1 Phương pháp biến đổi Phương pháp. .. Chương Phương pháp biến phụ trợ MCMC Giới thiệu mặt lý thuyết vài thuật tốn phương pháp MCMC có sử dụng biến phụ trợ: Phương pháp mô nhiệt luyện, mơ điều chỉnh nhiệt,Moller, thuật tốn trao đổi, phương