Thuật toán Monte Carlo Markov Chain (MCMC) là một nhóm các phương pháp toán học sử dụng để lấy mẫu từ một phân phối xác suất phức tạp. Các thuật toán MCMC thường được sử dụng trong thống kê Bayesian, vật lý thống kê, và các lĩnh vực khác yêu cầu đánh giá các phân phối phức tạp mà không thể tính toán trực tiếp.

Nguyên lý cơ bản

Thuật toán MCMC hoạt động bằng cách xây dựng một chuỗi Markov, trong đó mỗi trạng thái của chuỗi này là một mẫu từ phân phối mục tiêu. Chuỗi này được xây dựng sao cho phân phối của các trạng thái trong chuỗi, sau một khoảng thời gian đủ dài, sẽ hội tụ đến phân phối mục tiêu. Điều này cho phép ta ước lượng các đặc trưng của phân phối mục tiêu (như kỳ vọng, phương sai, ...) bằng cách lấy mẫu từ chuỗi Markov.

Các bước cơ bản của MCMC

1. Khởi tạo: Bắt đầu từ một điểm khởi đầu tùy ý trong không gian trạng thái.
2. Lặp lại:
   • Đề xuất một trạng thái mới dựa trên trạng thái hiện tại theo một quy tắc chuyển đổi nhất định (thường là một hàm đề xuất).
   • Chấp nhận hoặc từ chối trạng thái mới theo một xác suất được xác định bởi phân phối mục tiêu và hàm đề xuất.

Các thuật toán phổ biến

• Metropolis-Hastings: Đây là một trong những thuật toán MCMC cơ bản nhất. Nó sử dụng một hàm đề xuất để đề xuất các trạng thái mới và chấp nhận trạng thái mới với một xác suất nhất định để đảm bảo chuỗi Markov hội tụ đến phân phối mục tiêu.
• Gibbs Sampling: Đây là một biến thể của MCMC, trong đó các mẫu mới được lấy bằng cách lấy mẫu tuần tự từ các phân phối điều kiện của từng biến riêng lẻ.

Thuật toán Metropolis-Hastings

 

Giả sử ta muốn lấy mẫu từ phân phối mục tiêu \( \pi(x) \). Thuật toán Metropolis-Hastings bao gồm các bước sau:

1. Khởi tạo: Chọn một điểm khởi đầu \( x_0 \).
2. Chọn một điểm khởi đầu \( x_0 \):
   • Đề xuất một trạng thái mới \( x' \) từ phân phối đề xuất \( q(x' \mid x_i) \).
   • Tính tỷ lệ chấp nhận \[ \alpha = \min\left(1, \frac{\pi(x') q(x_i \mid x')}{\pi(x_i) q(x' \mid x_i)}\right). \]
   • Sinh một số ngẫu nhiên \( u \) từ phân phối đồng nhất \( U(0, 1) \).
   • Nếu \( u < \alpha \), chấp nhận trạng thái mới: \( x_{i+1} = x' \). Ngược lại, từ chối trạng thái mới: \( x_{i+1} = x_i \).

Ưu điểm và nhược điểm

Ưu điểm:

• Hiệu quả trong việc lấy mẫu từ các phân phối phức tạp.
• Khả năng áp dụng rộng rãi trong nhiều lĩnh vực.

Nhược điểm:

• Cần thời gian "burn-in" để chuỗi hội tụ đến phân phối mục tiêu.
• Có thể gặp khó khăn trong việc xác định hàm đề xuất tốt.
• Có thể mất nhiều thời gian tính toán cho các phân phối mục tiêu phức tạp hoặc không trơn tru.

Ứng dụng

• Thống kê Bayesian: Ước lượng các tham số mô hình Bayesian bằng cách lấy mẫu từ phân phối hậu nghiệm.
• Vật lý thống kê: Nghiên cứu các hệ thống vật lý phức tạp bằng cách mô phỏng trạng thái của hệ thống theo phân phối Boltzmann.
• Học máy: Ước lượng tham số trong các mô hình xác suất phức tạp.

Thuật toán MCMC là công cụ mạnh mẽ và linh hoạt để giải quyết các bài toán lấy mẫu và tối ưu hóa trong nhiều lĩnh vực khác nhau.