AA228V Lecture 09: Failure Distribution

p (τ ∣ τ \in / ψ)

=

1 {τ \in / ψ}

p (τ)

\int 1 {τ \in / ψ}

p (τ)

d τ

p (τ ∣ τ \in / ψ)

=

1 {τ \in / ψ}

p (τ)

\int 1 {τ \in / ψ}

p (τ)

d τ

A Simple Example

p (τ)

τ \in / ψ

τ \in ψ

p (τ ∣ τ \in / ψ)

=

1 {τ \in / ψ}

p (τ)

\int 1 {τ \in / ψ}

p (τ)

d τ

p (τ ∣ τ \in / ψ)

=

1 {τ \in / ψ}

p (τ)

\int 1 {τ \in / ψ}

p (τ)

d τ

A Simple Example

p (τ)

1 {τ \in / ψ} p (τ)

p (τ ∣ τ \in / ψ)

=

1 {τ \in / ψ}

p (τ)

\int 1 {τ \in / ψ}

p (τ)

d τ

p (τ ∣ τ \in / ψ)

=

1 {τ \in / ψ}

p (τ)

\int 1 {τ \in / ψ}

p (τ)

d τ

A Simple Example

p (τ)

1 {τ \in / ψ} p (τ)

\int 1 {τ \in / ψ} p (τ) d τ

p (τ ∣ τ \in / ψ)

=

1 {τ \in / ψ}

p (τ)

\int 1 {τ \in / ψ}

p (τ)

d τ

normally, this normalizing
constant is very difficult if not
impossible to compute

Unnormalized Probability Density

\overset{p}{ˉ} (τ ∣ τ \in / ψ)

=

1 {τ \in / ψ}

p (τ)

There are algorithms that allow us to
draw samples from an unnormalized
probability density! This way, we can
implicitly represent the failure
distribution using samples.

Unnormalized Probability Density

\overset{p}{ˉ} (τ ∣ τ \in / ψ)

=

1 {τ \in / ψ}

p (τ)

There are algorithms that allow us to
draw samples from an unnormalized
probability density! This way, we can
implicitly represent the failure
distribution using samples.

0.6

0

- 3

3

τ

h

Throw darts uniformly at the board.

a

Sample a value uniformly between

- 3

and

3

b

Sample a value uniformly between

0

and

0.6

repeat for
each dart

0.6

0

- 3

3

τ

h

Throw darts uniformly at the board.

a

Sample a value uniformly between

- 3

and

3

b

Sample a value uniformly between

0

and

0.6

repeat for
each dart

0.6

0

- 3

3

τ

h

Throw darts uniformly at the board.

a

Sample a value uniformly between

- 3

and

3

b

Sample a value uniformly between

0

and

0.6

repeat for
each dart

Reject any darts that lie
above the blue density.

0.6

0

- 3

3

τ

h

Throw darts uniformly at the board.

a

Sample a value uniformly between

- 3

and

3

b

Sample a value uniformly between

0

and

0.6

repeat for
each dart

Reject any darts that lie
above the blue density.

Move the remaining darts to
the bottom of the board.

0.6

0

- 3

3

τ

h

\overset{p}{ˉ} (τ)

Throw darts uniformly at the board.

a

Sample a value uniformly between

- 3

and

3

τ \sim q (\cdot), q (τ) = U (- 3, 3)

b

Sample a value uniformly between

0

and

0.6

repeat for
each dart

Reject any darts that lie
above the blue density.

Move the remaining darts to
the bottom of the board.

q (τ)

0.6

0

- 3

3

τ

h

\overset{p}{ˉ} (τ)

Throw darts uniformly at the board.

a

Sample a value uniformly between

- 3

and

3

τ \sim q (\cdot), q (τ) = U (- 3, 3)

b

Sample a value uniformly between

0

and

0.6

h = (c q (τ)) (r), r \sim U (0, 1)

repeat for
each dart

Reject any darts that lie
above the blue density.

Move the remaining darts to
the bottom of the board.

q (τ)

0.6

0

- 3

3

τ

h

\overset{p}{ˉ} (τ)

Throw darts uniformly at the board.

a

Sample a value uniformly between

- 3

and

3

τ \sim q (\cdot), q (τ) = U (- 3, 3)

b

Sample a value uniformly between

0

and

0.6

h = (c q (τ)) (r), r \sim U (0, 1)

repeat for
each dart

Reject any darts that lie
above the blue density.

Move the remaining darts to
the bottom of the board.

q (τ)

c

0.6

0

- 3

3

τ

h

\overset{p}{ˉ} (τ)

Throw darts uniformly at the board.

a

Sample a value uniformly between

- 3

and

3

τ \sim q (\cdot), q (τ) = U (- 3, 3)

b

Sample a value uniformly between

0

and

0.6

h = (c q (τ)) (r), r \sim U (0, 1)

repeat for
each dart

Reject any darts that lie
above the blue density.

Reject if

(c q (τ)) (r)

>

\overset{p}{ˉ} (τ)

Move the remaining darts to
the bottom of the board.

q (τ)

c

0.6

0

- 3

3

τ

h

\overset{p}{ˉ} (τ)

Throw darts uniformly at the board.

a

Sample a value uniformly between

- 3

and

3

τ \sim q (\cdot), q (τ) = U (- 3, 3)

b

Sample a value uniformly between

0

and

0.6

h = (c q (τ)) (r), r \sim U (0, 1)

repeat for
each dart

Reject any darts that lie
above the blue density.

Reject if

(c q (τ)) (r)

>

\overset{p}{ˉ} (τ)

Move the remaining darts to
the bottom of the board.

Just keep the

τ

value for each sample

q (τ)

c

0.6

0

- 3

3

τ

h

\overset{p}{ˉ} (τ)

Throw darts uniformly at the board.

a

Sample a value uniformly between

- 3

and

3

τ \sim q (\cdot), q (τ) = U (- 3, 3)

b

Sample a value uniformly between

0

and

1

h = (c q (τ)) (r), r \sim U (0, 1)

repeat for
each dart

Reject any darts that lie
above the blue density.

Reject if

(c q (τ)) (r)

>

\overset{p}{ˉ} (τ)

Move the remaining darts to
the bottom of the board.

Just keep the

τ

value for each sample

q (τ)

c

Look at all those gray darts (samples) we wasted!

0

- 3

3

τ

\overset{p}{ˉ} (τ)

Throw darts uniformly at the board.

a

Sample a value uniformly between

- 3

and

3

τ \sim q (\cdot), q (τ) = U (- 3, 3)

b

Sample a value uniformly between

0

and

0.6

h = (c q (τ)) (r), r \sim U (0, 1)

repeat for
each dart

Reject any darts that lie
above the blue density.

Reject if

(c q (τ)) (r)

>

\overset{p}{ˉ} (τ)

Move the remaining darts to
the bottom of the board.

Just keep the

τ

value for each sample

q (τ)

c

Look at all those gray darts (samples) we wasted!

What if we could make our dart board look like this instead?

0

- 3

3

τ

\overset{p}{ˉ} (τ)

Throw darts uniformly at the board.

a

Sample a value uniformly between

- 3

and

3

τ \sim q (\cdot), q (τ) = U (- 3, 3)

b

Sample a value uniformly between

0

and

0.6

h = (c q (τ)) (r), r \sim U (0, 1)

repeat for
each dart

Reject any darts that lie
above the blue density.

Reject if

(c q (τ)) (r)

>

\overset{p}{ˉ} (τ)

Move the remaining darts to
the bottom of the board.

Just keep the

τ

value for each sample

q (τ)

c

What if we could make our dart board look like this instead?

We just need to select

q (τ)

to be a distribution we can sample from
and

c

such that

c q (τ)

is always greater than

\overset{p}{ˉ} (τ)

Rejection Sampling

Sample

τ \sim q (\cdot)

q (τ)

is often referred to as a proposal distribution

Reject if

c q (τ)

r

>

\overset{p}{ˉ} (τ)

r

>

\overset{p}{ˉ} (τ)

c q (τ)

Rejection Sampling

Sample

τ \sim q (\cdot)

q (τ)

is often referred to as a proposal distribution

Reject if

c q (τ)

r

>

\overset{p}{ˉ} (τ)

r

>

\overset{p}{ˉ} (τ)

c q (τ)

Accept if

r

<

\overset{p}{ˉ} (τ)

c q (τ)

rand()

Note: we must select the proposal
distribution

q (τ)

such that

\overset{p}{ˉ} (τ) \leq c q (τ)

Rejection Sampling

Back to trying to sample from the failure distribution:

Sample

τ \sim q (\cdot)

Accept if

r

<

\overset{p}{ˉ} (τ)

c q (τ)

where

\overset{p}{ˉ} (τ) \leq c q (τ)

Rejection Sampling

Back to trying to sample from the failure distribution:

Sample

τ \sim q (\cdot)

Accept if

r

<

\overset{p}{ˉ} (τ)

c q (τ)

where

\overset{p}{ˉ} (τ) \leq c q (τ)

We can produce samples from the failure
distribution by sampling from the nominal
trajectory distribution and rejecting any samples
that are not failures!

What might be a problem with this method?
Hint: what theme seems to be coming up over and over again in this course?

It will be inefficient for systems with rare failure events!

One solution is to try to come up with a better proposal distribution.

Rejection Sampling

We can produce samples from the failure
distribution by sampling from the nominal
trajectory distribution and rejecting any samples
that are not failures!

It will be inefficient for systems with rare failure events!

One solution is to try to come up with a better proposal distribution.

Threshold

γ

-1.0

Samples

m

200

Proposal mean

μ

0.0

Scale

c

1.000

Markov Chain Monte Carlo

So how do we create the chain?

τ

Start with an initial sample

τ

At each iteration:

Sample

τ^{'} \sim g (\cdot ∣ τ)

e.g.

τ^{'} \sim N (\cdot ∣ τ, σ^{2})

Accept with probability

\frac{p ˉ ( τ ^{'} ) g ( τ ∣ τ ^{'} )}{p ˉ ( τ ) g ( τ ^{'} ∣ τ )}

(otherwise keep

τ

)

kernel

Markov Chain Monte Carlo

So how do we create the chain?

τ

Start with an initial sample

τ

At each iteration:

Sample

τ^{'} \sim g (\cdot ∣ τ)

e.g.

τ^{'} \sim N (\cdot ∣ τ, σ^{2})

Accept with probability

\frac{p ˉ ( τ ^{'} ) g ( τ ∣ τ ^{'} )}{p ˉ ( τ ) g ( τ ^{'} ∣ τ )}

(otherwise keep

τ

)

Markov Chain Monte Carlo

So how do we create the chain?

τ

Start with an initial sample

τ

At each iteration:

Sample

τ^{'} \sim g (\cdot ∣ τ)

e.g.

τ^{'} \sim N (\cdot ∣ τ, σ^{2})

Accept with probability

\frac{p ˉ ( τ ^{'} ) g ( τ ∣ τ ^{'} )}{p ˉ ( τ ) g ( τ ^{'} ∣ τ )}

(otherwise keep

τ

)

Markov Chain Monte Carlo

So how do we create the chain?

τ

Start with an initial sample

τ

At each iteration:

Sample

τ^{'} \sim g (\cdot ∣ τ)

e.g.

τ^{'} \sim N (\cdot ∣ τ, σ^{2})

Accept with probability

\frac{p ˉ ( τ ^{'} ) g ( τ ∣ τ ^{'} )}{p ˉ ( τ ) g ( τ ^{'} ∣ τ )}

(otherwise keep

τ

)

Markov Chain Monte Carlo

So how do we create the chain?

τ

Start with an initial sample

τ

At each iteration:

Sample

τ^{'} \sim g (\cdot ∣ τ)

e.g.

τ^{'} \sim N (\cdot ∣ τ, σ^{2})

Accept with probability

\frac{p ˉ ( τ ^{'} ) g ( τ ∣ τ ^{'} )}{p ˉ ( τ ) g ( τ ^{'} ∣ τ )}

(otherwise keep

τ

)

Markov Chain Monte Carlo

So how do we create the chain?

τ

Start with an initial sample

τ

At each iteration:

Sample

τ^{'} \sim g (\cdot ∣ τ)

e.g.

τ^{'} \sim N (\cdot ∣ τ, σ^{2})

Accept with probability

\frac{p ˉ ( τ ^{'} ) g ( τ ∣ τ ^{'} )}{p ˉ ( τ ) g ( τ ^{'} ∣ τ )}

(otherwise keep

τ

)

Markov Chain Monte Carlo

So how do we create the chain?

τ

Start with an initial sample

τ

At each iteration:

Sample

τ^{'} \sim g (\cdot ∣ τ)

e.g.

τ^{'} \sim N (\cdot ∣ τ, σ^{2})

Accept with probability

\frac{p ˉ ( τ ^{'} ) g ( τ ∣ τ ^{'} )}{p ˉ ( τ ) g ( τ ^{'} ∣ τ )}

(otherwise keep

τ

)

And so on…

Markov Chain Monte Carlo

So how do we create the chain?

Start with an initial sample

τ

At each iteration:

Sample

τ^{'} \sim g (\cdot ∣ τ)

e.g.

τ^{'} \sim N (\cdot ∣ τ, σ^{2})

Accept with probability

\frac{p ˉ ( τ ^{'} ) g ( τ ∣ τ ^{'} )}{p ˉ ( τ ) g ( τ ^{'} ∣ τ )}

(otherwise keep

τ

)

And so on…

This process is guaranteed to
converge to the target distribution in
the limit of infinite samples.

Markov Chain Monte Carlo

Some Intuition

Accept with probability

\frac{p ˉ ( τ ^{'} ) g ( τ ∣ τ ^{'} ) g ( τ ∣ τ ^{'} )}{p ˉ ( τ ) g ( τ ^{'} ∣ τ ) g ( τ ^{'} ∣ τ )}

This process is guaranteed to
converge to the target distribution in
the limit of infinite samples.

The kernel is often chosen to be
symmetric such that

g (τ ∣ τ^{'}) = g (τ^{'} ∣ τ)

We want to sample from areas of high density more often than areas of low density.

Two cases:

\overset{p}{ˉ} (τ^{'}) \geq \overset{p}{ˉ} (τ)

τ^{'}

is more likely under the target density than

τ

\frac{p ˉ ( τ ^{'} )}{p ˉ ( τ )} \geq 1

Always accept!

\overset{p}{ˉ} (τ^{'}) < \overset{p}{ˉ} (τ)

τ^{'}

is less likely under the target density than

τ

\frac{p ˉ ( τ ^{'} )}{p ˉ ( τ )} < 1

Accept with probability proportional to how much less likely it is.

Markov Chain Monte Carlo

This all works (converges to the target distribution) in the limit of infinite samples.

We don’t have time for that!

So we need often use some extra tricks in practice to make it perform better for a finite number of samples.

Burn in period

Thinning (e.g. only keep every 5th sample)

Deals with the fact that samples at subsequent steps are correlated

Smoothing

Markov Chain Monte Carlo

Smoothing

We may need to “help” the algorithm move between failure modes.
We can do this by “smoothing out” the failure distribution.

Define distance

Δ (τ)

for each trajectory such that:

Δ (τ) = 0

τ

is a failure

Δ (τ) > 0

otherwise

e.g.

max (ρ (τ, ψ), 0)

\overset{p}{ˉ} (τ ∣ τ \in / ψ) = 1 {τ \in / ψ} p (τ)

= 1 {Δ (τ) = 0} p (τ)

1 {Δ (τ) = 0} \approx N (Δ (τ) ∣ 0, ϵ^{2})

when

ϵ

is small

0

Δ (τ)

\approx

0

Δ (τ)

\overset{p}{ˉ} (τ ∣ τ \in / ψ) \approx N (Δ (τ) ∣ 0, ϵ^{2}) p (τ)

The smoothed distribution assigns
nonzero probability to successes with
higher probabilities for successes that
are closer to failure.

Markov Chain Monte Carlo

Define distance

Δ (τ)

for each trajectory such that:

Δ (τ) = 0

τ

is a failure

Δ (τ) > 0

otherwise

e.g.

max (ρ (τ, ψ), 0)

\overset{p}{ˉ} (τ ∣ τ \in / ψ) = 1 {τ \in / ψ} p (τ)

= 1 {Δ (τ) = 0} p (τ)

1 {Δ (τ) = 0} \approx N (Δ (τ) ∣ 0, ϵ^{2})

when

ϵ

is small

0

Δ (τ)

\approx

0

Δ (τ)

\overset{p}{ˉ} (τ ∣ τ \in / ψ) \approx N (Δ (τ) ∣ 0, ϵ^{2}) p (τ)

The smoothed distribution assigns
nonzero probability to successes with
higher probabilities for successes that
are closer to failure.

The parameter

ϵ

controls the amount of smoothing applied:

ϵ

\infty

nominal trajectory
distribution

0

no smoothing

Markov Chain Monte Carlo

🤔But won’t we now have a bunch of samples that are not failures?

Yes, but we can just reject them, and we will be left with samples from the failure distribution!

Note: you can think of it as applying
rejection sampling with the smoothed distribution
as the proposal distribution.

Tips to Scale Things Up

It is possible to apply these methods to more than just a one-dimensional Gaussian distribution 😀.

See examples 6.2 and 6.4 to show how we can apply
MCMC and smoothing to the pendulum example.

Other methods that help:

Some MCMC methods use gradients of the likelihood to define the kernel, which can
lead to better performance (e.g. MALA in section 6.3.3, HMC, NUTS)

Probabilistic programming allows us to specify probabilistic models as computer
programs in a way that allows inference to be performed automatically.

Advanced
topics

Tips to Scale Things Up

Probabilistic programming allows us to specify probabilistic models as computer
programs in a way that allows inference to be performed automatically.

😲