Xích Markov Monte Carlo

Xích Markov Monte Carlo (tiếng Anh: Markov chain Monte Carlo, viết tắt MCMC) là một thuật toán để lấy mẫu từ phân phối xác suất. Bằng cách xây dựng một chuỗi Markov có phân phối mong muốn là phân phối cân bằng của nó, người ta có thể có được một mẫu phân phối mong muốn bằng cách ghi lại các trạng thái từ chuỗi. Càng thực hiện nhiều bước, phân phối của mẫu sẽ càng khớp với phân phối mong muốn thực tế. Có nhiều phương pháp và thuật toán khác nhau để xây dựng chuỗi, bao gồm cả thuật toán Metropolis - Hastings.

Lĩnh vực ứng dụng

Phương pháp MCMC chủ yếu được sử dụng để tính toán xấp xỉ của tích phân nhiều chiều, ví dụ trong thống kê Bayesian, vật lý tính toán, sinh học máy tính và ngôn ngữ học tính toán.

Riêng với thống kê Bayesian, nhờ sự phát triển gần đây của các phương pháp MCMC đã làm cho nó có thể tính toán các mô hình phân cấp lớn đáp ứng yêu cầu tích hợp trên hàng trăm đến hàng nghìn tham số chưa biết.

Nguyên lý chung

Phương pháp Markov chain Monte Carlo tạo ra các mẫu từ một biến ngẫu nhiên liên tục, với mật độ xác suất tỷ lệ với một hàm đã biết. Những mẫu này có thể được sử dụng để đánh giá một tích phân đối với biến đó như là giá trị hoặc phương sai mong đợi của nó.

Trên thực tế, một tập hợp các chuỗi thường được phát triển, bắt đầu từ một tập hợp các điểm được chọn tùy ý và đủ cách xa nhau. Phương pháp đi bộ ngẫu nhiên cung cấp một phép ẩn dụ tốt cho việc xây dựng chuỗi mẫu Markov, các chuỗi này được ví như là các quá trình ngẫu nhiên của "người đi bộ" di chuyển xung quanh một cách ngẫu nhiên theo một thuật toán nhằm tìm kiếm những vị trí có đóng góp hợp lý cao cho tích phân để chuyển sang bước tiếp theo, gán cho chúng xác suất cao hơn. Có nhiều thuật toán Markov chain Monte Carlo chủ yếu xác định các cách khác nhau để xây dựng Markov Chain khi thực hiện mỗi mẫu Monte Carlo.

Phương pháp Monte Carlo đi bộ ngẫu nhiên là một loại mô phỏng ngẫu nhiên hoặc phương pháp Monte Carlo. Tuy nhiên, trong khi các mẫu ngẫu nhiên của tích phân được sử dụng trong tích hợp Monte Carlo thông thường là độc lập về mặt thống kê, còn các mẫu được sử dụng trong MCMC là tự tương quan (autocorrelated). Mối tương quan của các mẫu cho thấy sự cần thiết phải sử dụng định lý giới hạn trung tâm chuỗi Markov khi ước tính sai số của các giá trị trung bình.

Các thuật toán này tạo ra các chuỗi Markov sao cho chúng có phân bố cân bằng tỷ lệ với hàm đã cho.

Độ hội tụ

Hội tụ của giải thuật Metropolis–Hastings. Xích Markov Monte Carlo đang cố tính xấp xỉ phân phối đường màu xanh với phân phối đường màu cam.

Thông thường, không khó để xây dựng một chuỗi Markov với các đặc tính mong muốn. Vấn đề khó khăn hơn là xác định có bao nhiêu bước cần thiết để hội tụ đến phân phối tĩnh trong một sai số chấp nhận được. Một xích (chuỗi) tốt sẽ có tốc độ trộn nhanh, phân phối tĩnh đạt được nhanh chóng bắt đầu từ một vị trí tùy ý. Một phương pháp thực nghiệm tiêu chuẩn để đánh giá sự hội tụ là chạy một số xích Markov được mô phỏng độc lập và kiểm tra xem tỷ lệ phương sai giữa các xích và các phương sai trong xích cho tất cả các tham số được lấy mẫu là gần bằng 1 hay không.

Thông thường, lấy mẫu Monte Carlo chuỗi Markov chỉ có thể gần đúng với phân phối mục tiêu vì luôn có hiệu ứng dư (residual effect) của vị trí bắt đầu.

Nhiều phương pháp Monte Carlo theo phương pháp đi bộ ngẫu nhiên, di chuyển xung quanh phân phối cân bằng theo các bước tương đối nhỏ, không có xu hướng, cho các bước tiến hành theo cùng một hướng. Những phương pháp này dễ thực hiện và dễ phân tích, nhưng tiếc là có thể mất nhiều thời gian để "người đi bộ" khám phá hết không gian mẫu.

Các phương pháp và giải thuật MCMC

Phương pháp đi bộ ngẫu nghiên

• Giải thuật Metropolis–Hastings
• Lấy mẫu cắt lát
• Thử Metropolis nhiều lần
• Bước nhảy có thể đảo ngược
• Hamiltonian Monte Carlo (HMC)

Phần mềm

Có nhiều phần mềm sử dụng MCMC cho việc lấy mẫu, ví dụ như:

• ParaMonte đây là thư viện phần mềm Monte Carlo hỗ trợ cho nhiều ngôn ngữ lập trình khác nhau C, C++, Fortran, MATLAB, và Python.
• Các gói phần mềm sử dụng phương ngữ của ngôn ngữ mô hình BUGS:
  • WinBUGS / OpenBUGS / MultiBUGS
  • JAGS
• MCSim
• Các gói phần mềm hỗ trợ ngôn ngữ Julia như Turing.jl, DynamicHMC.jl, AffineInvariantMCMC.jl, và StanJulia.
• Các gói phần mềm hỗ trợ ngôn ngữ Python như emcee, ParaMonte, PyMC3, và vandal.
• Các gói phần mềm hỗ trợ ngôn ngữ R như adaptMCMC, atmcmc, BRugs, mcmc, MCMCpack, ramcmc, rjags, rstan...
• Stan
• TensorFlow Probability (thư viện xác xuất thống kê có sẵn trên TensorFlow)

Xem thêm

• Diaconis, Persi (tháng 4 năm 2009). “The Markov chain Monte Carlo revolution” (PDF). Bull. Amer. Math. Soc. 46 (2): 179–205. doi:10.1090/s0273-0979-08-01238-x. S 0273-0979(08)01238-X. Bản gốc (PDF) lưu trữ ngày 28 tháng 3 năm 2022. Truy cập ngày 25 tháng 3 năm 2022.
• Press, W.H.; Teukolsky, S.A.; Vetterling, W.T.; Flannery, B.P. (2007), “Section 15.8. Markov Chain Monte Carlo”, Numerical Recipes: The Art of Scientific Computing (ấn bản 3), Cambridge University Press, ISBN 978-0-521-88068-8, Bản gốc lưu trữ ngày 11 tháng 8 năm 2011, truy cập ngày 25 tháng 3 năm 2022
• Richey, Matthew (tháng 5 năm 2010). “The Evolution of Markov Chain Monte Carlo Methods” (PDF). The American Mathematical Monthly. 117 (5): 383–413. CiteSeerX 10.1.1.295.4478. doi:10.4169/000298910x485923. S2CID 13630404. Bản gốc (PDF) lưu trữ ngày 20 tháng 10 năm 2021. Truy cập ngày 25 tháng 3 năm 2022.
• Bản hòa tấu dữ liệu xã hội. Nhà xuất bản khoa học xã hội. 2021.