ggordon.MCMC-tutorial

pages

English

Documents

Lire

Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres

pages

English

Documents

Lire

Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres

Publié par

Asli

Nombre de lectures

Langue

English

Monte Carlo MethodsGeoff Gordonggordon@cs.cmu.eduFebruary 9, 2006Numerical integration problem543210−1−0.5010.50.80.60.40.20−0.2−0.4−0.61−0.8−1XYZf(x)dxx2Xf(X,Y)Used for: function approximationf(x) f (x) + f (x) + : : :1 1 2 2R R2Orthonormal system: f (x) dx = 1 and f (x)f (x)dx = 0i i j Fourier (sin x, cos x, . . . )2 3 Chebyshev (1, x, 2x 1, 4x 3x, . . . ) . . .Coefﬁcients areZ = f(x)f (x)dxi iUsed for: optimizationOptimization problem: minimize T(x) for x2XAssume unique global optimum xDeﬁne Gibbs distribution with temperature 1= for > 0:1P (x) = exp( T(x))Z()As !1, have E (x)! xxPRSimulated annealing: track E (x) = xP (x)dx as !1 Used for: Bayes net inferenceUndirected Bayes net on x = x ; x ; : : ::1 2Y1P(x) = (x)jZjTypical inference problem: compute E(x )iBelief propagation is fast if argument lists of s are small and form ajjunction treeIf not, MCMCUsed for: SLAMUsed forImage segmentationTracking radar/sonar returnsOutlineUniform sampling, importance samplingMCMC and Metropolis-Hastings algorithmWhat if f(x) has internal structure: SIS, SIR (particle ﬁlter) Gibbs samplerCombining SIR w/ MCMCA one-dimensional problem706050403020100−1 −0.5 0 0.5 1Uniform sampling706050403020100−1 −0.5 0 0.5 1true integral 24.0; uniform sampling 14.7 w/ 30 samplesUniform samplingPick an x uniformly at random fromXZE(f(x)) = P(x)f(x)dxZ1= ...

Voir

Publié par

Asli

Langue

English