Samplingsalgoritmer

Samplingsalgoritmer är algoritmer som genererar prov från sannolikhetsfördelningar eller urval ur större dataset. De används inom statistik, simulering och maskininlärning för att uppskatta förväntningar, sannolikheter och integraler som är svåra att beräkna exakt.

En mycket använda familj är Monte Carlo-sampling, där man från en given fördelning genererar många slumpmässiga prover och använder medelvärden av proverna som uppskattningar. Under denna rubrik ingår tekniker som rejection sampling, där ett prov accepteras endast om det uppfyller ett villkor, samt importance sampling, där prover tas från en bekvämare fördelning och vikter används för att justera resultatet.

Markov-kedja Monte Carlo (MCMC) är en annan viktig grupp där prover genereras av en Markov-kedja som har målfördelningen som sin stationära fördelning. Vanliga metoder är Metropolis-Hastings och Gibbs-sampling. Dessa är särskilt användbara i högdimensionella problem där oberoende prover inte är praktiska.

Andra tekniker inkluderar användning av kvasi-slumpmässiga sekvenser för mer jämn fördelning (low-discrepancy) och sekventiell Monte Carlo eller partikel-filter i dynamiska modeller.

Praktiska överväganden omfattar konvergensdiagnoser, burn-in-tid, effektivt antal prover och autokorrelation, eftersom beroende prover kräver längre körningar för liknande noggrannhet. Beräkningskostnader och dimensionen på problemet påverkar valet av metod.

Användningsområden inkluderar bayesiansk inferens, fysik och kvantsimulering, finans och riskbedömning samt maskininlärning och optimeringsproblem.