ggordon.MCMC-tutorial

Description

Monte Carlo MethodsGeoff [e-mail] 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, . . . ) . . .Coefficients areZ = f(x)f (x)dxi iUsed for: optimizationOptimization problem: minimize T(x) for x2XAssume unique global optimum xDefine 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 filter) 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= ...

Informations

• Publié par: Asli
• Nombre de lectures: 16
• Langue: English

Extrait

Monte

Carlo

Methods

Geoff Gordon

[e-mail]

February

9,

2006

Numerical integration problem

-1

5

4

3

2

1

0

-0.5

0

0.5 0.2 0.4 0.6 0.8 1 1 0.4  -0.2 0 X -1  0.8  -0.6 - - Y

Z x∈X f(x)dx

Used for: f

unctiaopnproximation

f(x)≈α 1 f 1 (x) +α 2 f 2 (x) +. . .

Orthonormal system: R f i (x) 2 dx= 1and R f i (x)f j (x)dx= 0

•Fourier (sinx,cosx . . ), .

•Chebyshev (1,x,2x 2 −1,4x 3 −3x . . ), .

•. . .

Coefcieanrtes

α i = Z f(x)f i (x)dx

Used for: optimization

Optimization problem: minimizeT(x)forx∈ X

Assume unique global optimumx ∗

DeneGibbs distribution with temperature1/βforβ >0:

As,ahve

P β (x) = Z( 1 β p(ex ) −βT(x))

β→ ∞E x∼P β (x)→x ∗ Simulated annealing: trackE β (x) = R xP β (x)dxasβ→ ∞

Used for: Bayes net inference

Undirected Bayes net onx=x 1 , x 2 , . . .: P 1 = Y (x) Z j φ j (x)

yTpicalinferencerpboelm:ocpmtue

E(x i )

Belief propagation is fast if argument lists ofφ j junction tree

If not, MCMC

s are small and form a

Used

for

:

SLAM

Used

for

Image segmentation

Tracking

radar/sonar

returns

Outline

Uniform sampling, importance sampling

MCMC and Metropolis-Hastings algorithm

What iff(x)has internal structure:

•IS,SIS(Raptriclelter)

•Gibbs sampler

Combining SIR w/ MCMC

A

one-dimensional

70

60

50

40

30

20

10

� 0 1

problem

�0.5

0

0.5

1

Uniform sampling

70

60

50

40

30

20

10

� 0 1

�0.5

0

0.5

1

true integral 24.0; uniform sampling 14.7 w/ 30 samples

Uniform sampling

Pick anxuniformly at random f

E(f(x)) =

whereVis volume ofX

=

SoE(V f(x)) =desired integral

rXom Z P(x)f(x)dx V 1 Z f(x)dx

Butvariancecanbebig(.iefsVp large)