Xây dựng HATECH
Facebook dự án
Đăng nhập / Đăng ký

Markov Chain Monte Carlo (MCMC)

Mục lục

  1. Giới thiệu
  2. Markov Chain (Chuỗi Markov)
  3. Phương pháp Monte Carlo
  4. Suy luận Bayesian (Bayesian Inference)
  5. Markov Chain Monte Carlo (MCMC)
  6. Ứng dụng thực tế
  7. Tóm tắt tính toán Mô phỏng (Jupyter Notebook)
  8. Tài liệu tham khảo

Giới thiệu

Markov Chain Monte Carlo (MCMC) là một lớp các 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 cân bằng (equilibrium distribution) mong muốn, ta có thể lấy mẫu từ phân phối đó để xấp xỉ các tích phân phức tạp hoặc hiểu rõ hơn về tính chất của phân phối hậu nghiệm (posterior) trong thống kê Bayes.

Markov Chain (Chuỗi Markov)

Chuỗi Markov là một mô hình ngẫu nhiên mô tả một chuỗi các biến cố khả dĩ, trong đó xác suất của mỗi biến cố chỉ phụ thuộc vào trạng thái đạt được trong biến cố trước đó.

  • Tính chất Markov (Markov Property): Tương lai chỉ phụ thuộc vào hiện tại, không phụ thuộc vào quá khứ. P(Xn+1∣Xn,Xn−1,...,X0)=P(Xn+1∣Xn)P(X_{n+1} | X_n, X_{n-1}, ..., X_0) = P(X_{n+1} | X_n).
  • Ma trận chuyển trạng thái (Transition Matrix): Mô tả xác suất chuyển từ trạng thái này sang trạng thái khác.
  • Trạng thái cân bằng (Equilibirum): Sau một số bước đủ lớn, phân phối xác suất của trạng thái hội tụ về một phân phối ổn định, không thay đổi qua các bước tiếp theo.

Phương pháp Monte Carlo

Phương pháp Monte Carlo là một nhóm các thuật toán tính toán dựa vào việc lấy mẫu ngẫu nhiên lặp lại để thu được các kết quả số.

  • Nguyên lý: Sử dụng tính ngẫu nhiên để giải quyết các bài toán có thể xác định (deterministic) về nguyên tắc.
  • Quy luật số lớn: Khi số lượng mẫu thử nghiệm tăng lên, kết quả trung bình của mẫu sẽ hội tụ về giá trị kỳ vọng thực sự.

Suy luận Bayesian (Bayesian Inference)

Suy luận Bayes là phương pháp thống kê trong đó xác suất được sử dụng để định lượng sự không chắc chắn. Định lý Bayes cập nhật xác suất cho một giả thuyết khi có thêm bằng chứng hoặc thông tin mới.

P(θ∣D)=P(D∣θ)P(θ)P(D)P(\theta | D) = \frac{P(D | \theta) P(\theta)}{P(D)}

Trong đó:

  • P(θ∣D)P(\theta | D): Posterior (Phân phối hậu nghiệm) - xác suất của tham số θ\theta khi đã biết dữ liệu DD.
  • P(D∣θ)P(D | \theta): Likelihood (Hàm khả năng) - xác suất quan sát dữ liệu DD nếu tham số là θ\theta.
  • P(θ)P(\theta): Prior (Phân phối tiên nghiệm) - niềm tin ban đầu về θ\theta trước khi thấy dữ liệu.
  • P(D)P(D): Evidence (Bằng chứng) - hằng số chuẩn hóa (thường rất khó tính toán trực tiếp trong không gian nhiều chiều).

Markov Chain Monte Carlo (MCMC)

Tại sao cần MCMC?

Trong thống kê Bayes, việc tính toán trực tiếp phân phối hậu nghiệm P(θ∣D)P(\theta | D) thường gặp khó khăn do mẫu số P(D)P(D) đòi hỏi tích phân qua toàn bộ không gian tham số (vốn có thể có số chiều rất lớn).

MCMC giải quyết vấn đề này bằng cách lấy mẫu từ phân phối hậu nghiệm mà không cần tính hằng số chuẩn hóa P(D)P(D).

Cách thức hoạt động

MCMC kết hợp hai phương pháp:

  1. Monte Carlo: Lấy mẫu ngẫu nhiên để ước lượng phân phối.
  2. Markov Chain: Tạo ra các mẫu phụ thuộc nhau sao cho phân phối giới hạn của chuỗi chính là phân phối mục tiêu (posterior).

Hay nói cách khác, ta thiết kế một "con robot" nhảy ngẫu nhiên trong không gian tham số. Con robot có xu hướng ở lại lâu hơn tại những vùng có xác suất cao và ít ghé thăm những vùng có xác suất thấp. Dấu vết bước chân của robot chính là các mẫu từ phân phối cần tìm.

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

  1. Metropolis-Hastings (MH): Thuật toán tổng quát, đề xuất bước nhảy và chấp nhận/từ chối dựa trên tỷ lệ mật độ xác suất.
  2. Gibbs Sampling: Trường hợp đặc biệt của MH, cập nhật từng biến một khi cố định các biến khác.
  3. Hamiltonian Monte Carlo (HMC) / NUTS: Sử dụng đạo hàm (gradient) của hàm mật độ để đề xuất các bước nhảy hiệu quả hơn, tránh "bước đi ngẫu nhiên" (random walk) kém hiệu quả trong không gian nhiều chiều. (Thường được dùng trong Stan, PyMC3).
  4. Affine Invariant Ensemble Sampler (emcee): Sử dụng nhiều "walkers" song song, hiệu quả cho các phân phối méo mó.

Ứng dụng thực tế

Kỹ thuật Xây dựng & Quản lý Dự án

  • Phân tích rủi ro dự án (Project Risk Analysis): Mô phỏng thời gian hoàn thành dự án (PERT/CPM) khi thời gian từng tác vụ là biến ngẫu nhiên. MCMC giúp ước lượng phân phối xác suất của ngày hoàn thành (probability of deadline overrun).
  • Độ tin cậy kết cấu (Structural Reliability): Đánh giá xác suất phá hủy của kết cấu chịu tải trọng ngẫu nhiên (gió, động đất) và đặc trưng vật liệu không chắc chắn. Cập nhật độ tin cậy khi có dữ liệu quan trắc mới (Structural Health Monitoring).
  • Tối ưu hóa thiết kế: Tìm kiếm các tham số thiết kế tối ưu trong không gian phức tạp.

Tài chính, Kinh tế & Đầu tư

  • Danh mục đầu tư (Portfolio Optimization): Ước lượng phân phối lợi nhuận và rủi ro (VaR - Value at Risk). MCMC cho phép mô hình hóa các phân phối lợi nhuận đuôi dày (fat-tailed) phi chuẩn, thực tế hơn so với giả định phân phối chuẩn truyền thống.
  • Mô hình hóa biến động (Stochastic Volatility): Dự báo biến động giá tài sản, định giá quyền chọn (options pricing).
  • Giao dịch thuật toán (Algorithmic Trading): Phát hiện sự thay đổi chế độ thị trường (regime switching models) để điều chỉnh chiến lược giao dịch tự động.

Tóm tắt tính toán Mô phỏng (Jupyter Notebook)

Phần này tóm tắt quá trình thực hiện thuật toán Metropolis-Hastings đơn giản để khớp mô hình đường thẳng (y=mx+cy = mx + c) vào dữ liệu nhiễu.

  • Script: /home/hha/work/github-guide/obsidian_haah/6-vault/scripts/Monte-Carlo/mcmctutorial.py
  • Dữ liệu: Tạo dữ liệu giả định y=1.5x+4y = 1.5x + 4 cộng thêm nhiễu chuẩn N(0,1)\mathcal{N}(0, 1).

1. Dữ liệu giả định

Dữ liệu được tạo ra với 30 điểm. Các thanh sai số thể hiện độ không đảm bảo đo (σ=1\sigma=1). Data

2. Quá trình chạy chuỗi (Chains)

Thuật toán chạy 100,000 bước. Biểu đồ dưới đây (Trace plot) cho thấy giá trị của Slope và Intercept qua các bước lặp. Phần đầu (Burn-in) cho thấy chuỗi di chuyển từ điểm khởi đầu tùy ý về vùng cân bằng. Chains

3. Phân phối Hậu nghiệm (Posterior Distributions)

Sau khi loại bỏ 1000 bước đầu (burn-in), ta thu được phân phối tần suất (Histogram) của các tham số.

  • Kết quả ước lượng:
    • Slope: xấp xỉ 1.40 (Thực tế: 1.5)
    • Intercept: xấp xỉ 4.29 (Thực tế: 4.0)

Histograms

4. Tương quan tham số

Biểu đồ phân tán cho thấy sự phụ thuộc giữa Slope và Intercept. Có sự tương quan âm: khi độ dốc tăng, hệ số chặn có xu hướng giảm để đường thẳng vẫn khớp với đám mây dữ liệu. Correlation

5. Corner Plot

Biểu đồ "Corner" thể hiện đồng thời phân phối biên (marginal distribution) trên đường chéo và phân phối đồng thời (joint distribution) ngoài đường chéo. Corner Plot

6. Kết quả Khớp mô hình (Best Fit)

Đường thẳng từ bộ tham số có Likelihood cao nhất (Best-fit model) được vẽ chồng lên dữ liệu. Best Fit

7. Độ không đảm bảo của mô hình

Bằng cách vẽ ngẫu nhiên 100 đường thẳng từ chuỗi MCMC, ta hình dung được "chùm" các giải pháp khả dĩ, phản ánh độ không chắc chắn của mô hình. Uncertainty

Tài liệu tham khảo

  1. Wikipedia - Markov chain Monte Carlo: https://en.wikipedia.org/wiki/Markov_chain_Monte_Carlo
  2. Stanford CS109 - Mathematical Foundations: https://web.stanford.edu/class/archive/cs/cs109/cs109.1218/files/student_drive/9.6.pdf