Markov Chain Monte Carlo

Markov chain Monte Carlo lấy mẫu từ một phân bố mục tiêu phức tạp bằng cách mô phỏng một chuỗi Markov được thiết kế để có phân bố đó làm luật dừng duy nhất của nó.

Definition

Markov chain Monte Carlo là một họ thuật toán ước tính các kỳ vọng dưới một phân bố xác suất mục tiêu bằng cách chạy một chuỗi Markov ergodic có phân bố dừng là mục tiêu và tính trung bình một hàm trên đường đi của chuỗi.

Scope

Chủ đề này bao gồm thiết kế các hạt nhân chuyển đổi với một phân bố dừng được quy định trước, thuật toán Metropolis-Hastings và quy tắc chấp nhận của nó, bộ lấy mẫu Gibbs cho các cập nhật có điều kiện, chẩn đoán hội tụ và giai đoạn khởi động (burn-in), ảnh hưởng của tự tương quan đến phương sai ước lượng, và mối liên hệ giữa thời gian trộn và chi phí tính toán của việc lấy mẫu.

Core questions

• Một chuỗi Markov được xây dựng như thế nào để có một phân bố dừng mong muốn?
• Tại sao quy tắc chấp nhận Metropolis-Hastings tạo ra luật dừng chính xác?
• Bộ lấy mẫu Gibbs khai thác các phân bố có điều kiện như thế nào?
• Một chuỗi phải chạy bao lâu trước khi các mẫu của nó có thể sử dụng được, và điều này được đánh giá như thế nào?

Key theories

Cấu trúc Metropolis-Hastings

Đề xuất các bước di chuyển từ một hạt nhân tùy ý và chấp nhận chúng với một xác suất được xây dựng từ tỷ lệ mật độ mục tiêu tạo ra một chuỗi thuận nghịch có phân bố dừng chính xác là mục tiêu, chỉ yêu cầu mục tiêu lên đến một hằng số chuẩn hóa.

Trung bình ergodic và ước lượng Monte Carlo

Vì chuỗi là ergodic với mục tiêu là luật dừng của nó, các trung bình thời gian của một hàm dọc theo chuỗi hội tụ hầu như chắc chắn đến kỳ vọng mục tiêu, biện minh cho việc sử dụng các đường dẫn mô phỏng làm mẫu.

Clinical relevance

Markov chain Monte Carlo là công cụ chủ lực của thống kê Bayes hiện đại, vật lý thống kê và học máy, cho phép suy luận trên các phân bố hậu nghiệm đa chiều, hàm phân hoạch và cảnh quan năng lượng không thể tích phân giải tích; độ tin cậy của nó phụ thuộc vào việc chuỗi cơ bản trộn đủ nhanh.

History

Chuỗi chấp nhận-từ chối có nguồn gốc từ thuật toán Metropolis năm 1953 cho vật lý thống kê, được Hastings tổng quát hóa vào năm 1970, và được tái cấu trúc cho thống kê thông qua bộ lấy mẫu Gibbs của Geman và Geman vào năm 1984 và các ứng dụng Bayes có ảnh hưởng của Gelfand và Smith vào khoảng năm 1990, đã khởi xướng cuộc cách mạng Bayes tính toán.

Key figures

• Nicholas Metropolis
• W. Keith Hastings
• Stuart Geman
• Donald Geman

Seminal works

• robertCasella2004
• hastings1970

Frequently asked questions

Tại sao sử dụng chuỗi Markov để lấy mẫu?

Đối với các phân bố mục tiêu đa chiều hoặc không chuẩn hóa, việc lấy mẫu trực tiếp là không khả thi; một chuỗi Markov hội tụ đến mục tiêu cho phép bạn tạo ra các mẫu phụ thuộc nhưng được phân bố chính xác sau khi nó đạt đến trạng thái cân bằng.

Giai đoạn khởi động (burn-in) là gì?

Đó là phần ban đầu của chuỗi bị loại bỏ vì chuỗi chưa hội tụ đến phân bố dừng của nó, do đó các trạng thái ban đầu đó sẽ làm sai lệch các ước tính.