Wikiszótár

Metropolis-Hastings-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈmɛtropoliʃhɒʃtiŋkʃɒlɡoritmuʃ]

Főnév

Metropolis-Hastings-algoritmus

  1. (matematika)

Metropolis-Hastings-algoritmus

A Metropolis-Hastings-algoritmus egy Markov-lánc Monte Carlo (MCMC) módszer, amelyet valószínűségi eloszlásokból történő mintavételre használnak, ha közvetlen mintavétel nem lehetséges. Az algoritmus iteratív módon hoz létre egy Markov-láncot, amelynek egyensúlyi eloszlása a célzott eloszlás lesz.


Algoritmus lépései

  1. Indítás: Válassz egy kezdő értéket ( x_0 ).
  2. Lépésjavaslat: Egy ( q(x’ | x_t) ) javaslateloszlás alapján generálj egy ( x’ ) új állapotot.
  3. Elfogadás vagy elutasítás:
    • Számítsd ki az elfogadási arányt: [ = (1, ), ] ahol ( p(x) ) a célzott valószínűségi eloszlás, ( q ) pedig a javaslateloszlás.
    • Ha egy ( u U(0, 1) ) véletlenszám kisebb, mint ( ), akkor fogadd el az új állapotot (( x_{t+1} = x’ )).
    • Egyébként maradj az aktuális állapotban (( x_{t+1} = x_t )).
  4. Iteráció: Ismételd a folyamatot elegendő számú iterációval.


Python Implementáció

Az alábbi példában egy normál eloszlásból mintavételezünk Metropolis-Hastings-algoritmussal. 

import numpy as np
import matplotlib.pyplot as plt

def target_distribution(x):
    """Célzott valószínűségi eloszlás: Normál eloszlás."""
    return np.exp(-0.5 * x**2) / np.sqrt(2 * np.pi)

def metropolis_hastings(target, proposal_std, iterations, start):
    """
    Metropolis-Hastings algoritmus.
    
    :param target: Célzott eloszlás függvénye.
    :param proposal_std: Javaslateloszlás standard deviációja.
    :param iterations: Iterációk száma.
    :param start: Kezdőérték.
    :return: Minták a célzott eloszlásból.
    """
    samples = []
    current = start
    
    for _ in range(iterations):
        # Javasolt új érték
        proposed = current + np.random.normal(0, proposal_std)
        # Elfogadási arány kiszámítása
        acceptance_ratio = target(proposed) / target(current)
        # Véletlen szám generálása az elfogadáshoz
        if np.random.uniform(0, 1) < acceptance_ratio:
            current = proposed
        samples.append(current)
    
    return np.array(samples)

# Paraméterek
iterations = 10000
proposal_std = 1.0
start = 0.0

# Algoritmus futtatása
samples = metropolis_hastings(target_distribution, proposal_std, iterations, start)

# Eredmények megjelenítése
x = np.linspace(-5, 5, 1000)
plt.hist(samples, bins=50, density=True, alpha=0.6, label="MCMC Minták")
plt.plot(x, target_distribution(x), label="Célzott eloszlás", color="red")
plt.legend()
plt.title("Metropolis-Hastings mintavételezés")
plt.show()

C++ Implementáció

A következő kód egy normál eloszlás mintavételét végzi el C++ segítségével. 

#include <iostream>
#include <vector>
#include <cmath>
#include <random>
#include <algorithm>

using namespace std;

// Célzott valószínűségi eloszlás
double target_distribution(double x) {
    return exp(-0.5 * x * x) / sqrt(2 * M_PI);
}

// Metropolis-Hastings algoritmus
vector<double> metropolis_hastings(int iterations, double proposal_std, double start) {
    vector<double> samples;
    double current = start;

    random_device rd;
    mt19937 gen(rd());
    normal_distribution<> proposal_dist(0, proposal_std);
    uniform_real_distribution<> uniform_dist(0, 1);

    for (int i = 0; i < iterations; ++i) {
        // Javasolt új érték
        double proposed = current + proposal_dist(gen);
        // Elfogadási arány kiszámítása
        double acceptance_ratio = target_distribution(proposed) / target_distribution(current);

        // Elfogadás vagy elutasítás
        if (uniform_dist(gen) < acceptance_ratio) {
            current = proposed;
        }
        samples.push_back(current);
    }

    return samples;
}

int main() {
    int iterations = 10000;
    double proposal_std = 1.0;
    double start = 0.0;

    // Mintavétel
    vector<double> samples = metropolis_hastings(iterations, proposal_std, start);

    // Alapvető statisztikák
    double mean = accumulate(samples.begin(), samples.end(), 0.0) / samples.size();
    cout << "Minták átlaga: " << mean << endl;

    return 0;
}

Magyarázat

  1. Elfogadási arány (( )):
    • Ez határozza meg, hogy egy új állapot milyen eséllyel kerül be az elfogadott minták közé.
    • Az arány ( ), biztosítva, hogy a Markov-lánc egyensúlyi eloszlása a célzott eloszlás.
  2. Javaslateloszlás (( q(x’ | x) )):
    • Leggyakrabban szimmetrikus eloszlást (pl. normál eloszlást) használnak, mivel ekkor ( q(x’ | x) = q(x | x’) ), és az arány egyszerűsödik: [ = (1, ) ]
  3. Felhasználás:
    • Valószínűségi modellek becslésében.
    • Bayesian elemzésben, amikor a posterior eloszlásból kell mintát venni.

A Metropolis-Hastings algoritmus hatékony és széles körben alkalmazható, különösen olyan helyzetekben, amikor bonyolult eloszlásokból kell mintát venni.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Metropolis-Hastings-algoritmus&oldid=3480685”