English:

Markov Chain Monte Carlo (MCMC) methods are a class of algorithms used in statistics and machine learning to approximate complex probability distributions and compute expectations or integrals when direct calculation is infeasible. MCMC methods generate samples from a target probability distribution by constructing a Markov chain that has the desired distribution as its stationary distribution. These samples can then be used for inference or to estimate properties of the target distribution.

Key Concepts

1. Markov Chain:

   • A sequence of random variables $X_1, X_2, ldots$ where the distribution of $X_{t+1}$ depends only on $X_t$, satisfying the Markov property: $$P(X_{t+1} mid X_1, X_2, ldots, X_t) = P(X_{t+1} mid X_t).$$
   • The chain transitions between states based on a transition kernel $P(X_{t+1} mid X_t)$.

2. Monte Carlo:

   • Refers to the use of random sampling to estimate numerical quantities such as integrals or expectations.

3. Stationary Distribution:

   • A Markov chain is designed so that as $t to infty$, the distribution of $X_t$ approaches the target distribution $p(x)$. This property allows MCMC to generate samples from $p(x)<span\; style="font-family:\; sans-serif,\; Arial,\; Verdana,\; "\; trebuchet="">.</span>$

4. Ergodicity:

   • To ensure convergence, the Markov chain must be irreducible (can reach any state from any other state) and aperiodic (does not cycle regularly). These properties guarantee that the chain explores the entire state space.

How MCMC Works

MCMC methods create a Markov chain that satisfies:

• The chain is ergodic.
• The target distribution $p(x)$ is the stationary distribution.

Once the chain is run for a sufficient number of iterations (called the burn-in period), the samples generated are approximately distributed according to $p(x)$.

Key MCMC Algorithms

1. Metropolis-Hastings Algorithm:

   • Proposes a new sample $x'$ from a proposal distribution $q(x' mid x)$, based on the current state $x$.
   • Accepts $x'$ with a probability $A(x' mid x)$, ensuring the chain converges to $p(x)$. The acceptance probability is: $$A(x' mid x) = minleft(1, frac{p(x')q(x mid x')}{p(x)q(x' mid x)}right).$$
   • If $x'$ is rejected, the chain stays at $x$.

2. Gibbs Sampling:

   • A special case of MCMC where samples are drawn sequentially from the conditional distributions of each variable given the others.
   • For a multivariate distribution $p(x_1, x_2, ldots, x_n)$, the algorithm samples: $$x_1^{(t+1)} sim p(x_1 mid x_2^{(t)}, ldots, x_n^{(t)}),$$$$x_2^{(t+1)} sim p(x_2 mid x_1^{(t+1)}, x_3^{(t)}, ldots, x_n^{(t)}),$$ and so on.

3. Hamiltonian Monte Carlo (HMC):

   • Uses gradients of the log-probability density to propose new states, leading to more efficient exploration of the state space for high-dimensional problems.
   • Combines physics-inspired concepts like kinetic energy and momentum to simulate the evolution of the chain.

4. Slice Sampling:

   • Samples by iteratively defining and exploring "slices" of the target distribution. This avoids the need to tune a proposal distribution.

Advantages of MCMC

1. Flexibility:

   • Can handle complex, high-dimensional distributions.
   • Requires only the ability to evaluate the target distribution up to a constant.

2. Scalability:

   • Works well for Bayesian inference in models where direct sampling is impractical.

3. General Applicability:

   • Widely used in machine learning, physics, and computational biology.

Challenges

1. Convergence:

   • It can be difficult to determine when the chain has converged to the stationary distribution.
   • Poorly chosen proposals may lead to slow mixing (inefficient exploration of the state space).

2. Tuning:

   • Algorithms often require careful tuning (e.g., step size, burn-in period).

3. Computational Cost:

   • For high-dimensional or multimodal distributions, MCMC can be computationally expensive.

Applications

1. Bayesian Inference:

   • Estimating posterior distributions for complex probabilistic models.

2. Partition Function Estimation:

   • Approximating normalization constants in probability distributions.

3. Statistical Physics:

   • Simulating systems governed by the Boltzmann distribution.

4. Machine Learning:

   • Sampling latent variables in models like Variational Autoencoders (VAEs) or probabilistic graphical models.

In summary, MCMC methods provide a powerful framework for approximating complex probability distributions by leveraging the properties of Markov chains and Monte Carlo sampling. Despite their challenges, MCMC remains a cornerstone of modern probabilistic modeling and inference.

Vietnamese:

Phương pháp Markov Chain Monte Carlo (MCMC) là một nhóm các thuật toán được sử dụng trong thống kê và học máy để xấp xỉ các phân phối xác suất phức tạp và tính toán kỳ vọng hoặc tích phân khi việc tính toán trực tiếp trở nên bất khả thi. MCMC tạo ra các mẫu từ phân phối mục tiêu bằng cách xây dựng một chuỗi Markov mà phân phối dừng của chuỗi này chính là phân phối mong muốn. Các mẫu này sau đó có thể được sử dụng để suy diễn hoặc ước tính các đặc trưng của phân phối mục tiêu.

Khái niệm chính

1. Chuỗi Markov:

   • Là một chuỗi các biến ngẫu nhiên $X_1, X_2, ldots$ mà phân phối của $X_{t+1}$ chỉ phụ thuộc vào $X_t$, thỏa mãn tính chất Markov: $$P(X_{t+1} mid X_1, X_2, ldots, X_t) = P(X_{t+1} mid X_t).$$
   • Chuỗi chuyển trạng thái dựa trên một hạt nhân chuyển đổi $P(X_{t+1} mid X_t)$.

2. Monte Carlo:

   • Là việc sử dụng các mẫu ngẫu nhiên để ước tính các đại lượng số như tích phân hoặc kỳ vọng.

3. Phân phối dừng:

   • Một chuỗi Markov được thiết kế sao cho khi $t to infty$, phân phối của $X_t$ sẽ tiến tới phân phối mục tiêu $p(x)$. Điều này cho phép MCMC tạo ra các mẫu từ $p(x)$.

4. Tính chất ergodic:

   • Để đảm bảo chuỗi hội tụ, chuỗi Markov phải không bị khử giảm (irreducible) (có thể đến mọi trạng thái từ bất kỳ trạng thái nào) và không tuần hoàn (aperiodic) (không có chu kỳ đều đặn). Những tính chất này đảm bảo chuỗi khám phá toàn bộ không gian trạng thái.

Cách hoạt động của MCMC

Các phương pháp MCMC tạo ra một chuỗi Markov thỏa mãn:

• Chuỗi có tính chất ergodic.
• Phân phối mục tiêu $p(x)$ là phân phối dừng của chuỗi.

Khi chuỗi được chạy trong một khoảng thời gian đủ lâu (gọi là giai đoạn đốt nóng - burn-in), các mẫu được tạo ra sẽ xấp xỉ phân phối $p(x)$.

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

1. Thuật toán Metropolis-Hastings:

   • Đề xuất một mẫu mới $x'$ từ một phân phối đề xuất $q(x' mid x)$, dựa trên trạng thái hiện tại $x$.
   • Chấp nhận $x'$ với xác suất $A(x' mid x)$, đảm bảo chuỗi hội tụ tới $p(x)$. Xác suất chấp nhận là: $$A(x' mid x) = minleft(1, frac{p(x')q(x mid x')}{p(x)q(x' mid x)}right).$$
   • Nếu $x'$ bị từ chối, chuỗi giữ nguyên ở trạng thái $x$.

2. Gibbs Sampling:

   • Là trường hợp đặc biệt của MCMC, trong đó các mẫu được lấy lần lượt từ các phân phối điều kiện của từng biến, với điều kiện các biến khác đã được cố định.
   • Với một phân phối đa biến $p(x_1, x_2, ldots, x_n)$, thuật toán lần lượt lấy mẫu: $$x_1^{(t+1)} sim p(x_1 mid x_2^{(t)}, ldots, x_n^{(t)}),$$$$x_2^{(t+1)} sim p(x_2 mid x_1^{(t+1)}, x_3^{(t)}, ldots, x_n^{(t)}),$$ và tiếp tục như vậy.

3. Hamiltonian Monte Carlo (HMC):

   • Sử dụng gradient của mật độ log-xác suất để đề xuất các trạng thái mới, giúp khám phá không gian trạng thái hiệu quả hơn trong các vấn đề có số chiều cao.
   • Kết hợp các khái niệm từ vật lý, như năng lượng động học và động lượng, để mô phỏng sự tiến hóa của chuỗi.

4. Slice Sampling:

   • Lấy mẫu bằng cách lần lượt xác định và khám phá các "lát cắt" của phân phối mục tiêu. Phương pháp này tránh việc cần phải tinh chỉnh một phân phối đề xuất.

Ưu điểm của MCMC

1. Tính linh hoạt:

   • Có thể xử lý các phân phối phức tạp và nhiều chiều.
   • Chỉ yêu cầu khả năng đánh giá phân phối mục tiêu đến một hằng số tỷ lệ.

2. Khả năng mở rộng:

   • Hoạt động hiệu quả trong suy luận Bayesian với các mô hình mà lấy mẫu trực tiếp là không khả thi.

3. Tính tổng quát:

   • Được sử dụng rộng rãi trong học máy, vật lý và sinh học tính toán.

Thách thức

1. Hội tụ:

   • Khó xác định khi nào chuỗi đã hội tụ tới phân phối dừng.
   • Các đề xuất không phù hợp có thể dẫn đến chuỗi hội tụ chậm (khám phá không hiệu quả không gian trạng thái).

2. Điều chỉnh tham số:

   • Các thuật toán thường yêu cầu điều chỉnh cẩn thận (ví dụ: kích thước bước, giai đoạn burn-in).

3. Chi phí tính toán:

   • Với các phân phối có số chiều cao hoặc nhiều cực đại, MCMC có thể tốn kém về mặt tính toán.

Ứng dụng

1. Suy luận Bayesian:

   • Ước tính phân phối hậu nghiệm cho các mô hình xác suất phức tạp.

2. Ước tính hàm phân hoạch:

   • Xấp xỉ các hằng số chuẩn hóa trong các phân phối xác suất.

3. Vật lý thống kê:

   • Mô phỏng các hệ thống tuân theo phân phối Boltzmann.

4. Học máy:

   • Lấy mẫu các biến tiềm ẩn trong các mô hình như Variational Autoencoders (VAEs) hoặc các mô hình đồ thị xác suất.

Tóm lại, các phương pháp MCMC cung cấp một khung mạnh mẽ để xấp xỉ các phân phối xác suất phức tạp bằng cách tận dụng các tính chất của chuỗi Markov và phương pháp lấy mẫu Monte Carlo. Mặc dù có những thách thức, MCMC vẫn là nền tảng của mô hình hóa và suy luận xác suất hiện đại.