AA228V Lecture 10: Failure Probability Estimation

Failure Probability

Failure Distribution

p_{fail}

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

p (τ ∣ τ \in / ψ)

=

1 {τ \in / ψ}

p (τ)

\int 1 {τ \in / ψ}

p (τ)

d τ

The probability of failure is the normalizing constant of the failure distribution!

p_{fail}

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

Earlier, we noted that this normalizing constant is generally intractable to compute exactly.
In this lecture, we will discuss ways to estimate it.

Plan for Today

Part 1

Part 2

Part 3

Direct Estimation

Importance Sampling

Cross Entropy Method (Adaptive Importance Sampling)

Multiple Importance Sampling

Population Monte Carlo

Sequential Monte Carlo

Ratio of Normalizing Constants

Self-Normalized Importance Sampling

Bridge Sampling

Multilevel Splitting

This is what I would start with for Project 2!

Direct Estimation

Perform a rollout of the system

Label outcome as

1

if the trajectory is a failure and

0

otherwise

This process is equivalent to producing samples from a Bernoulli distribution defined by parameter

p_{fail}

We can use the parameter estimation techniques from chapter 2 to estimate it!

(maximum likelihood estimation or Bayesian estimation)

Quick Aside: How do we assess how good an estimator is?

Bias

Consistency

Variance

An estimator is unbiased if it
predicts the true value in
expectation:

E [\overset{p}{^}_{fail}] = p_{fail}

An estimator is consistent if it
converges to the true value in
the limit of infinite samples:

m \to \infty lim \overset{p}{^}_{fail} = p_{fail}

The variance of an estimator
quantifies the spread of the
estimates around the true value.

Direct Estimation

maximum likelihood estimator

\overset{p}{^}_{fail} = \frac{1}{m} i = 1 \sum m 1 {τ_{i} \in / ψ} = \frac{n}{m}

Unbiased

Var [\overset{p}{^}_{fail}] = \frac{p _{fail} ( 1 - p _{fail} )}{m}

What happens to the variance as

m \to \infty

Consistent

Direct Estimation

maximum likelihood estimator

\overset{p}{^}_{fail} = \frac{1}{m} i = 1 \sum m 1 {τ_{i} \in / ψ} = \frac{n}{m}

Unbiased

Consistent

Var [\overset{p}{^}_{fail}] = \frac{p _{fail} ( 1 - p _{fail} )}{m}

As the number of samples increases, the variance in the estimate decreases.

Direct Estimation

maximum likelihood estimator

\overset{p}{^}_{fail} = \frac{1}{m} i = 1 \sum m 1 {τ_{i} \in / ψ} = \frac{n}{m}

Unbiased

Consistent

Var [\overset{p}{^}_{fail}] = \frac{p _{fail} ( 1 - p _{fail} )}{m}

As the number of samples increases, the variance in the estimate decreases.

As the probability of failure decreases, the variance in the estimate increases.

Again, bad news for systems with rare failure events.

We will discuss importance sampling techniques
throughout the rest of this lecture that aim to
address this issue!

Direct Estimation

But first: one more issue with maximum likelihood estimation.

Imagine that we want to estimate the probability of failure for an aircraft collision avoidance system
from an aviation safety database that contains flight records from the month of December.
What would the maximum likelihood estimate of the probability of failure be if there were no
recorded midair collisions in December?

Zero!

We could use Bayesian estimation in this case to produce a distribution over the probability of failure.

Direct Estimation

We could use Bayesian estimation in this case to produce a distribution over the probability of failure.

Remember these fun times?

p (θ ∣ D) = \frac{p ( D ∣ θ ) p ( θ )}{\int _{θ} p ( D ∣ θ ) p ( θ ) d θ}

p (θ) = Beta (θ ∣ α, β)

p (θ ∣ D) = Beta (θ ∣ α + n, β + m - n)

θ

: probability of both frisbees landing in the same direction

n

: number of times same

m

: total number of flips

Direct Estimation

We could use Bayesian estimation in this case to produce a distribution over the probability of failure.

Remember these fun times?

p (θ ∣ D) = \frac{p ( D ∣ θ ) p ( θ )}{\int _{θ} p ( D ∣ θ ) p ( θ ) d θ}

p (θ) = Beta (θ ∣ α, β)

p (θ ∣ D) = Beta (θ ∣ α + n, β + m - n)

θ

: probability of both frisbees landing in the same direction

n

: number of times same

m

: total number of flips

Direct Estimation

We could use Bayesian estimation in this case to produce a distribution over the probability of failure.

Remember these fun times?

p (θ ∣ D) = \frac{p ( D ∣ θ ) p ( θ )}{\int _{θ} p ( D ∣ θ ) p ( θ ) d θ}

p (θ) = Beta (θ ∣ α, β)

p (θ ∣ D) = Beta (θ ∣ α + n, β + m - n)

θ

: probability of both frisbees landing in the same direction

p_{fail}

n

: number of times same

m

: total number of flips

Direct Estimation

We could use Bayesian estimation in this case to produce a distribution over the probability of failure.

Remember these fun times?

p (θ ∣ D) = \frac{p ( D ∣ θ ) p ( θ )}{\int _{θ} p ( D ∣ θ ) p ( θ ) d θ}

p (θ) = Beta (θ ∣ α, β)

p (θ ∣ D) = Beta (θ ∣ α + n, β + m - n)

θ

: probability of both frisbees landing in the same direction

p_{fail}

n

: number of times same

: number of failure trajectories

m

: total number of flips

Direct Estimation

We could use Bayesian estimation in this case to produce a distribution over the probability of failure.

Remember these fun times?

p (θ ∣ D) = \frac{p ( D ∣ θ ) p ( θ )}{\int _{θ} p ( D ∣ θ ) p ( θ ) d θ}

p (θ) = Beta (θ ∣ α, β)

p (θ ∣ D) = Beta (θ ∣ α + n, β + m - n)

θ

: probability of both frisbees landing in the same direction

p_{fail}

n

: number of times same

: number of failure trajectories

m

: total number of flips

: total number of trajectories

Plan for Today

Part 1

Part 2

Part 3

Direct Estimation

Importance Sampling

Cross Entropy Method (Adaptive Importance Sampling)

Multiple Importance Sampling

Population Monte Carlo

Sequential Monte Carlo

Ratio of Normalizing Constants

Self-Normalized Importance Sampling

Bridge Sampling

Multilevel Splitting

This is what I would start with for Project 2!

Direct Estimation

Importance Sampling

Draw samples from the nominal trajectory distribution.

Estimate the probability of failure by dividing the number of failure samples by the total number of samples.

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!

Draw samples from a proposal distribution that is more likely to produce failure trajectories.

Estimate the probability of failure by reweighing the samples.

Importance Sampling

Draw samples from a proposal distribution that is more likely to produce failure trajectories.

Estimate the probability of failure by reweighing the samples.

τ \sim q (\cdot)

\overset{p}{^}_{fail} = \frac{1}{m} i = 1 \sum m \frac{p ( τ _{i} )}{q ( τ _{i} )} 1 {τ_{i} \in / ψ}

= \frac{1}{m} i = 1 \sum m w_{i} 1 {τ_{i} \in / ψ}

w_{i} = \frac{p ( τ _{i} )}{q ( τ _{i} )}

This estimator is both unbiased and consistent.

Direct Estimation

Importance Sampling

Draw samples from

p (\cdot)

Estimate the probability of failure:

\overset{p}{^}_{fail} = \frac{1}{m} i = 1 \sum m 1 {τ_{i} \in / ψ}

Draw samples from

q (\cdot)

Estimate the probability of failure:

\overset{p}{^}_{fail}

= \frac{1}{m} i = 1 \sum m w_{i} 1 {τ_{i} \in / ψ}

w_{i} = \frac{p ( τ _{i} )}{q ( τ _{i} )}

importance
weight

Samples that are more likely under the nominal trajectory distribution will have a higher importance weight.

Importance Sampling

Draw samples from

q (\cdot)

Estimate the probability of failure:

\overset{p}{^}_{fail}

= \frac{1}{m} i = 1 \sum m w_{i} 1 {τ_{i} \in / ψ}

w_{i} = \frac{p ( τ _{i} )}{q ( τ _{i} )}

importance
weight

Importance Sampling

Draw samples from

q (\cdot)

Estimate the probability of failure:

\overset{p}{^}_{fail}

= \frac{1}{m} i = 1 \sum m w_{i} 1 {τ_{i} \in / ψ}

w_{i} = \frac{p ( τ _{i} )}{q ( τ _{i} )}

importance
weight

Importance Sampling

Draw samples from

q (\cdot)

Estimate the probability of failure:

\overset{p}{^}_{fail}

= \frac{1}{m} i = 1 \sum m w_{i} 1 {τ_{i} \in / ψ}

w_{i} = \frac{p ( τ _{i} )}{q ( τ _{i} )}

importance
weight

Importance Sampling

Samples

500

Threshold

γ

-2.00

Proposal

μ

0.0

Proposal

σ

1.0

Error

y_{m a x}

0.050

We want the proposal distribution
to sample likely failures more often
than unlikely failures or successes.

Is there an optimal proposal distribution?

Importance Sampling

Is there an optimal proposal distribution?

We will define the optimal proposal
distribution as the one that minimizes the
variance of the estimator:

Var [\overset{p}{^}_{fail}] = \frac{1}{m} E_{τ \sim q (\cdot)} [\frac{( p ( τ ) 1 { τ \in / ψ } - q ( τ ) p _{fail} ) ^{2}}{q ( τ )}]

Importance Sampling

Is there an optimal proposal distribution?

We will define the optimal proposal
distribution as the one that minimizes the
variance of the estimator:

Var [\overset{p}{^}_{fail}] = \frac{1}{m} E_{τ \sim q (\cdot)} [\frac{( p ( τ ) 1 { τ \in / ψ } - q ( τ ) p _{fail} ) ^{2}}{q ( τ )}]

q^{*} (τ) = \frac{p ( τ ) 1 { τ \in / ψ }}{p _{fail}}

Does this distribution look familiar?

It’s the failure distribution!

🤔…but it is written in terms of the
thing we want to estimate (

p_{fail}

Importance Sampling

q^{*} (τ) = \frac{p ( τ ) 1 { τ \in / ψ }}{p _{fail}}

Does this distribution look familiar?

It’s the failure distribution!

🤔…but it is written in terms of the
thing we want to estimate (

p_{fail}

Importance Sampling

q^{*} (τ) = \frac{p ( τ ) 1 { τ \in / ψ }}{p _{fail}}

Does this distribution look familiar?

It’s the failure distribution!

🤔…but it is written in terms of the
thing we want to estimate (

p_{fail}

Best we can do is select a proposal that is as close
as possible to the failure distribution.

Note: we must be able to sample from
and compute the (normalized) density of
the proposal distribution we choose.

Various importance sampling algorithms have different ways of selecting this proposal.

Another option: fit a proposal distribution to samples from the failure distribution.

Failure if

τ < - 2

· MCMC samples from the failure distribution → fit a Gaussian proposal

Various importance sampling algorithms have different ways of selecting this proposal.

Another option: fit a proposal distribution to samples from the failure distribution.

Challenges

Producing samples from the failure distribution is a nontrivial task
(as we saw in the failure distribution lecture).

It may be difficult to produce a good fit to samples from the failure
distribution for high-dimensional systems with multiple failure modes.

Various importance sampling algorithms have different ways of selecting this proposal.

Another option: fit a proposal distribution to samples from the failure distribution.

Challenges

Producing samples from the failure distribution is a nontrivial task
(as we saw in the failure distribution lecture).

What if we could still fit a good proposal using samples from
a different distribution that is easier to sample from?

It may be difficult to produce a good fit to samples from the failure
distribution for high-dimensional systems with multiple failure modes.

Plan for Today

Part 1

Part 2

Part 3

Direct Estimation

Importance Sampling

Cross Entropy Method (Adaptive Importance Sampling)

Multiple Importance Sampling

Population Monte Carlo

Sequential Monte Carlo

Ratio of Normalizing Constants

Self-Normalized Importance Sampling

Bridge Sampling

Multilevel Splitting

Cross Entropy Method

What if we could still fit a good proposal using samples from
a different distribution that is easier to sample from?

Draw samples from an initial proposal distribution that is easy sample from.

Use the samples to fit a new proposal distribution from a model class that we also know how
to sample from by selecting the parameters that minimize the cross entropy between the
proposal distribution and the failure distribution.

Cross Entropy Method

What if we could still fit a good proposal using samples from
a different distribution that is easier to sample from?

Draw samples from an initial proposal distribution that is easy sample from.

τ \sim q (\cdot)

What proposal distribution should we try?

How about the nominal trajectory distribution?

For many common model classes (e.g. Gaussian), minimizing the cross entropy is equivalent
to computing the weighted maximum likelihood estimate for the parameters with weights

w = \frac{p ( τ ) 1 { τ \in / ψ }}{q ( τ )}

Cross Entropy Method

If we sample from the nominal distribution and failures are rare,
we may not get any failures and all the weights will be zero!

Samples

500

Threshold

γ

-2.00

Start with the nominal distribution
and iteratively adapt it to move closer
to the failure distribution.

The adaptive part of adaptive importance sampling!

Cross Entropy Method

Before we start:

Pick an initial proposal to adapt
(e.g. nominal trajectory distribution)

Pick a notion of closeness to failure $f (τ)$
(e.g. robustness)

We will require that

f (τ) \leq 0

for
failure trajectories such that

p (τ ∣ τ \in / ψ) = p (τ ∣ f (τ) \leq 0)

Cross Entropy Method

Before we start:

Pick an initial proposal to adapt
(e.g. nominal trajectory distribution)

Pick a notion of closeness to failure $f (τ)$
(e.g. robustness)

We will require that

f (τ) \leq 0

for
failure trajectories such that

p (τ ∣ τ \in / ψ) = p (τ ∣ f (τ) \leq 0)

f (τ) \leq 0

Ideally, we minimize the cross entropy between the
new proposal distribution and

p (τ ∣ f (τ) \leq 0)

Cross Entropy Method

Before we start:

Pick an initial proposal to adapt
(e.g. nominal trajectory distribution)

Pick a notion of closeness to failure $f (τ)$
(e.g. robustness)

We will require that

f (τ) \leq 0

for
failure trajectories such that

p (τ ∣ τ \in / ψ) = p (τ ∣ f (τ) \leq 0)

f (τ) \leq 0

Ideally, we minimize the cross entropy between the
new proposal distribution and

p (τ ∣ f (τ) \leq 0)

…but the weights might all be zero!

Cross Entropy Method

At each iteration

Draw samples from the current proposal.

Compute

f (τ)

for each sample and pick
the top

m_{elite}

samples.

f (τ) \leq 0

Ideally, we minimize the cross entropy between the
new proposal distribution and

p (τ ∣ f (τ) \leq 0)

…but the weights might all be zero!

Cross Entropy Method

At each iteration

Draw samples from the current proposal.

Compute

f (τ)

for each sample and pick
the top

m_{elite}

samples.

Select the threshold

γ

to be the highest

f (τ)

of the elite samples.

f (τ) \leq 0

Ideally, we minimize the cross entropy between the
new proposal distribution and

p (τ ∣ f (τ) \leq 0)

…but the weights might all be zero!

Cross Entropy Method

At each iteration

Draw samples from the current proposal.

Compute

f (τ)

for each sample and pick
the top

m_{elite}

samples.

Select the threshold

γ

to be the highest

f (τ)

of the elite samples.

Compute the next proposal by minimizing
the cross entropy with

p (τ ∣ f (τ) \leq γ)

f (τ) \leq 0

Ideally, we minimize the cross entropy between the
new proposal distribution and

p (τ ∣ f (τ) \leq 0)

…but the weights might all be zero!

Cross Entropy Method

At each iteration

Draw samples from the current proposal.

Compute

f (τ)

for each sample and pick
the top

m_{elite}

samples.

Select the threshold

γ

to be the highest

f (τ)

of the elite samples.

Compute the next proposal by minimizing
the cross entropy with

p (τ ∣ f (τ) \leq γ)

f (τ) \leq 0

Ideally, we minimize the cross entropy between the
new proposal distribution and

p (τ ∣ f (τ) \leq 0)

…but the weights might all be zero!

REPEAT!

Cross Entropy Method

At each iteration

Draw samples from the current proposal.

Compute

f (τ)

for each sample and pick
the top

m_{elite}

samples.

Select the threshold

γ

to be the highest

f (τ)

of the elite samples.

Compute the next proposal by minimizing
the cross entropy with

p (τ ∣ f (τ) \leq γ)

f (τ) \leq 0

Ideally, we minimize the cross entropy between the
new proposal distribution and

p (τ ∣ f (τ) \leq 0)

…but the weights might all be zero!

REPEAT!

Cross Entropy Method

At each iteration

Draw samples from the current proposal.

Compute

f (τ)

for each sample and pick
the top

m_{elite}

samples.

Select the threshold

γ

to be the highest

f (τ)

of the elite samples.

Compute the next proposal by minimizing
the cross entropy with

p (τ ∣ f (τ) \leq γ)

f (τ) \leq 0

Ideally, we minimize the cross entropy between the
new proposal distribution and

p (τ ∣ f (τ) \leq 0)

…but the weights might all be zero!

REPEAT!

Cross Entropy Method

At each iteration

Draw samples from the current proposal.

Compute

f (τ)

for each sample and pick
the top

m_{elite}

samples.

Select the threshold

γ

to be the highest

f (τ)

of the elite samples.

Compute the next proposal by minimizing
the cross entropy with

p (τ ∣ f (τ) \leq γ)

f (τ) \leq 0

Ideally, we minimize the cross entropy between the
new proposal distribution and

p (τ ∣ f (τ) \leq 0)

…but the weights might all be zero!

REPEAT!

Cross Entropy Method

At each iteration

Draw samples from the current proposal.

Compute

f (τ)

for each sample and pick
the top

m_{elite}

samples.

Select the threshold

γ

to be the highest

f (τ)

of the elite samples.

Compute the next proposal by minimizing
the cross entropy with

p (τ ∣ f (τ) \leq γ)

f (τ) \leq 0

Ideally, we minimize the cross entropy between the
new proposal distribution and

p (τ ∣ f (τ) \leq 0)

…but the weights might all be zero!

REPEAT!

Cross Entropy Method

At each iteration

Draw samples from the current proposal.

Compute

f (τ)

for each sample and pick
the top

m_{elite}

samples.

Select the threshold

γ

to be the highest

f (τ)

of the elite samples.

Compute the next proposal by minimizing
the cross entropy with

p (τ ∣ f (τ) \leq γ)

f (τ) \leq 0

Ideally, we minimize the cross entropy between the
new proposal distribution and

p (τ ∣ f (τ) \leq 0)

…but the weights might all be zero!

REPEAT!

Cross Entropy Method

At each iteration

Draw samples from the current proposal.

Compute

f (τ)

for each sample and pick
the top

m_{elite}

samples.

Select the threshold

γ

to be the highest

f (τ)

of the elite samples.

Compute the next proposal by minimizing
the cross entropy with

p (τ ∣ f (τ) \leq γ)

f (τ) \leq 0

Ideally, we minimize the cross entropy between the
new proposal distribution and

p (τ ∣ f (τ) \leq 0)

…but the weights might all be zero!

REPEAT!

Perform importance sampling
with the final proposal.

Cross Entropy Method

At each iteration

Draw samples from the current proposal.

Compute

f (τ)

for each sample and pick
the top

m_{elite}

samples.

Select the threshold

γ

to be the highest

f (τ)

of the elite samples.

Compute the next proposal by minimizing
the cross entropy with

p (τ ∣ f (τ) \leq γ)

Ideally, we minimize the cross entropy between the
new proposal distribution and

p (τ ∣ f (τ) \leq 0)

…but the weights might all be zero!

REPEAT!

Perform importance sampling
with the final proposal.

Plan for Today

Part 1

Part 2

Part 3

Direct Estimation

Importance Sampling

Cross Entropy Method (Adaptive Importance Sampling)

Multiple Importance Sampling

Population Monte Carlo

Sequential Monte Carlo

Ratio of Normalizing Constants

Self-Normalized Importance Sampling

Bridge Sampling

Multilevel Splitting

Multiple Importance Sampling

Draw samples from the current proposals.

τ_{i} \sim q_{i} (τ)

Use the samples to estimate

p_{fail}

\overset{p}{^}_{fail} = \frac{1}{m} i = 1 \sum m w_{i} 1 {τ_{i} \in / ψ}

where

w_{i} = \frac{p ( τ _{i} )}{q _{i} ( τ _{i} )}

w_{i} = \frac{p ( τ _{i} )}{q _{i} ( τ _{i} )}

Standard Multiple Importance Sampling (s-MIS)

There is another option…

Multiple Importance Sampling

There is another option…

w_{i} = \frac{p ( τ _{i} )}{q _{i} ( τ _{i} )}

Standard Multiple Importance Sampling (s-MIS)

Deterministic Mixture Multiple Importance Sampling (DM-MIS)

Multiple Importance Sampling

There is another option…

w_{i} = \frac{p ( τ _{i} )}{q _{i} ( τ _{i} )}

w_{i} = \frac{p ( τ _{i} )}{\frac{1}{m} \sum _{j = 1}^{m} q _{j} ( τ _{i} )}

Standard Multiple Importance Sampling (s-MIS)

Deterministic Mixture Multiple Importance Sampling (DM-MIS)

Multiple Importance Sampling

Draw samples from the current proposals.

τ_{i} \sim q_{i} (τ)

Use the samples to estimate

p_{fail}

\overset{p}{^}_{fail} = \frac{1}{m} i = 1 \sum m w_{i} 1 {τ_{i} \in / ψ}

where

w_{i} = \frac{p ( τ _{i} )}{q _{i} ( τ _{i} )}

Standard Multiple
Importance Sampling (s-MIS)

w_{i} = \frac{p ( τ _{i} )}{\frac{1}{m} \sum _{j = 1}^{m} q _{j} ( τ _{i} )}

Deterministic Mixture Multiple
Importance Sampling (DM-MIS)

*DM-MIS has been shown to have lower variance.

Plan for Today

Part 1

Part 2

Part 3

Direct Estimation

Importance Sampling

Cross Entropy Method (Adaptive Importance Sampling)

Multiple Importance Sampling

Population Monte Carlo

Sequential Monte Carlo

Ratio of Normalizing Constants

Self-Normalized Importance Sampling

Bridge Sampling

Multilevel Splitting

Population Monte Carlo

Let’s adapt a whole population of proposal distributions!

Select an initial population of proposals spread
out over the space of possible trajectories.

Note: it is important for the
initial population of proposals
to cover the space of possibilities
as best as possible.

Population Monte Carlo

Let’s adapt a whole population of proposal distributions!

Select an initial population of proposals spread
out over the space of possible trajectories.

Draw a sample from each proposal.

Population Monte Carlo

Let’s adapt a whole population of proposal distributions!

Select an initial population of proposals spread
out over the space of possible trajectories.

Draw a sample from each proposal.

Compute the importance weight for each sample.

Population Monte Carlo

Let’s adapt a whole population of proposal distributions!

Select an initial population of proposals spread
out over the space of possible trajectories.

Draw a sample from each proposal.

Compute the importance weight for each sample.

Resample based on the importance weights.

Population Monte Carlo

Let’s adapt a whole population of proposal distributions!

Select an initial population of proposals spread
out over the space of possible trajectories.

Draw a sample from each proposal.

Compute the importance weight for each sample.

Resample based on the importance weights.

Create new proposal distributions
centered at the samples.

Population Monte Carlo

Let’s adapt a whole population of proposal distributions!

Select an initial population of proposals spread
out over the space of possible trajectories.

Draw a sample from each proposal.

Compute the importance weight for each sample.

Resample based on the importance weights.

Create new proposal distributions
centered at the samples.

REPEAT!

Perform multiple importance
sampling with the final
proposals.

Plan for Today

Part 1

Part 2

Part 3

Direct Estimation

Importance Sampling

Cross Entropy Method (Adaptive Importance Sampling)

Multiple Importance Sampling

Population Monte Carlo

Sequential Monte Carlo

Ratio of Normalizing Constants

Self-Normalized Importance Sampling

Bridge Sampling

Multilevel Splitting

Sequential Monte Carlo

We want to move samples from the nominal distribution to the failure distribution.

We typically move the samples through a series of intermediate distributions.

How can we get these intermediate distributions? SMOOTHING!

Sequential Monte Carlo

We want to move samples from the nominal distribution to the failure distribution.

We typically move the samples through a series of intermediate distributions.

How can we get these intermediate distributions? SMOOTHING!

We can also use the thresholding technique similar to
what we did for the cross entropy method.

Sequential Monte Carlo

We want to move samples from the nominal distribution to the failure distribution.

We typically move the samples through a series of intermediate distributions.

How can we get these intermediate distributions? SMOOTHING!

We can also use the thresholding technique similar to
what we did for the cross entropy method.

How do we move samples from one distribution to the next? MCMC!

Sequential Monte Carlo

🤔Okay but how do we estimate the probability of failure from all this?

g_{1}

g_{2}

g_{3}

g_{4}

g_{5}

Keep track of a weight for each sample:

w_{i}^{(ℓ)} = w_{i}^{(ℓ - 1)} \frac{g ˉ _{ℓ + 1} ( τ _{i}^{(ℓ)} )}{g ˉ _{ℓ} ( τ _{i}^{(ℓ)} )}

Average the weights at the final iteration:

\overset{p}{^}_{fail} = \frac{1}{m} i = 1 \sum m w_{i}^{(n - 1)}

\overset{p}{^}_{fail} = \frac{1}{m} i = 1 \sum m w_{i}^{(n - 1)}

Sequential Monte Carlo

A few other notes on SMC:

It is common to also do a resampling step similar to population Monte Carlo for each transition.

Example 7.6

This process may allow us to perform fewer MCMC steps.

SMC is nonparametric, we do everything with samples.

This feature allows it to perform well for complex, multimodal failure distributions.

Plan for Today

Part 1

Part 2

Part 3

Direct Estimation

Importance Sampling

Cross Entropy Method (Adaptive Importance Sampling)

Multiple Importance Sampling

Population Monte Carlo

Sequential Monte Carlo

Ratio of Normalizing Constants

Self-Normalized Importance Sampling

Bridge Sampling

Multilevel Splitting

Ratio of Normalizing Constants

It turns out that importance sampling is a special case of a more general problem of determining
the ratio of the normalizing constants of two distributions.

g_{1} (τ) = \frac{g ˉ _{1} ( τ )}{\int g ˉ _{1} ( τ ) d τ} = \frac{g ˉ _{1} ( τ )}{z _{1}}

g_{2} (τ) = \frac{g ˉ _{2} ( τ )}{\int g ˉ _{2} ( τ ) d τ} = \frac{g ˉ _{2} ( τ )}{z _{2}}

g_{1} (τ) = \frac{g ˉ _{1} ( τ )}{\int g ˉ _{1} ( τ ) d τ} = \frac{g ˉ _{1} ( τ )}{z _{1}}

g_{2} (τ) = \frac{g ˉ _{2} ( τ )}{\int g ˉ _{2} ( τ ) d τ} = \frac{g ˉ _{2} ( τ )}{z _{2}}

Imagine someone just came up to you and was like…

I will give you a million dollars 💰
if you can get me an accurate
estimate of

z_{1} / z_{2}

using only
samples from

g_{2}

g_{1} (τ) = \frac{g ˉ _{1} ( τ )}{\int g ˉ _{1} ( τ ) d τ} = \frac{g ˉ _{1} ( τ )}{z _{1}}

g_{2} (τ) = \frac{g ˉ _{2} ( τ )}{\int g ˉ _{2} ( τ ) d τ} = \frac{g ˉ _{2} ( τ )}{z _{2}}

I will give you a million dollars 💰
if you can get me an accurate
estimate of

z_{1} / z_{2}

using only
samples from

g_{2}

g_{1} (τ) = \frac{g ˉ _{1} ( τ )}{\int g ˉ _{1} ( τ ) d τ} = \frac{g ˉ _{1} ( τ )}{z _{1}}

g_{2} (τ) = \frac{g ˉ _{2} ( τ )}{\int g ˉ _{2} ( τ ) d τ} = \frac{g ˉ _{2} ( τ )}{z _{2}}

I will give you a million dollars 💰
if you can get me an accurate
estimate of

z_{1} / z_{2}

using only
samples from

g_{2}

\frac{z _{1}}{z _{2}} = E_{τ \sim g_{2} (\cdot)} [\frac{g ˉ _{1} ( τ )}{g ˉ _{2} ( τ )}] \approx \frac{1}{m} i = 1 \sum m \frac{g ˉ _{1} ( τ )}{g ˉ _{2} ( τ )}

I will give you a million dollars 💰
if you can get me an accurate
estimate of

z_{1} / z_{2}

using only
samples from

g_{2}

\frac{z _{1}}{z _{2}} = E_{τ \sim g_{2} (\cdot)} [\frac{g ˉ _{1} ( τ )}{g ˉ _{2} ( τ )}] \approx \frac{1}{m} i = 1 \sum m \frac{g ˉ _{1} ( τ )}{g ˉ _{2} ( τ )}

Sadly 😕, this scenario is probably
never going to happen to you.

So let’s get back to failure probability estimation…

Can we derive the importance sampling estimator from this?

\frac{z _{1}}{z _{2}} = E_{τ \sim g_{2} (\cdot)} [\frac{g ˉ _{1} ( τ )}{g ˉ _{2} ( τ )}] \approx \frac{1}{m} i = 1 \sum m \frac{g ˉ _{1} ( τ )}{g ˉ _{2} ( τ )}

g_{1} (τ) = \frac{g ˉ _{1} ( τ )}{\int g ˉ _{1} ( τ ) d τ} = \frac{g ˉ _{1} ( τ )}{z _{1}}

g_{2} (τ) = \frac{g ˉ _{2} ( τ )}{\int g ˉ _{2} ( τ ) d τ} = \frac{g ˉ _{2} ( τ )}{z _{2}}

What might be a problem with estimating this ratio using samples from

g_{2}

It doesn’t work so great if

g_{1}

and

g_{2}

have very little overlap.

The solution?

g_{1} (τ) = \frac{g ˉ _{1} ( τ )}{\int g ˉ _{1} ( τ ) d τ} = \frac{g ˉ _{1} ( τ )}{z _{1}}

g_{2} (τ) = \frac{g ˉ _{2} ( τ )}{\int g ˉ _{2} ( τ ) d τ} = \frac{g ˉ _{2} ( τ )}{z _{2}}

What might be a problem with estimating this ratio using samples from

g_{2}

It doesn’t work so great if

g_{1}

and

g_{2}

have very little overlap.

The solution?

g_{1} (τ) = \frac{g ˉ _{1} ( τ )}{\int g ˉ _{1} ( τ ) d τ} = \frac{g ˉ _{1} ( τ )}{z _{1}}

g_{2} (τ) = \frac{g ˉ _{2} ( τ )}{\int g ˉ _{2} ( τ ) d τ} = \frac{g ˉ _{2} ( τ )}{z _{2}}

The solution?

Use an umbrella!☔

\overset{g}{ˉ}_{u} (τ)

The solution?

Use an umbrella!☔

\overset{g}{ˉ}_{u} (τ)

g_{1} (τ)

g_{2} (τ)

\frac{z _{α}}{z _{β}} \approx \frac{1}{m} i = 1 \sum m \frac{g ˉ _{α} ( τ )}{g ˉ _{β} ( τ )}

Using samples from

g_{β}

The solution?

Use an umbrella!☔

\frac{z _{1}}{z _{2}} \approx \frac{\frac{1}{m} \sum _{i = 1}^{m} \frac{g ˉ _{1} ( τ )}{g ˉ _{u} ( τ )}}{\frac{1}{m} \sum _{i = 1}^{m} \frac{g ˉ _{2} ( τ )}{g ˉ _{u} ( τ )}}

Using samples from

g_{u}

🤔What’s the optimal umbrella density?

\overset{g}{ˉ}_{u}^{*} (τ) \propto \overset{g}{ˉ}_{1} (τ) - \frac{z _{1}}{z _{2}} \overset{g}{ˉ}_{2} (τ)

The solution?

Use an umbrella!☔

\frac{z _{1}}{z _{2}} \approx \frac{\frac{1}{m} \sum _{i = 1}^{m} \frac{g ˉ _{1} ( τ )}{g ˉ _{u} ( τ )}}{\frac{1}{m} \sum _{i = 1}^{m} \frac{g ˉ _{2} ( τ )}{g ˉ _{u} ( τ )}}

Using samples from

g_{u}

🤔What’s the optimal umbrella density?

\overset{g}{ˉ}_{u}^{*} (τ) \propto \overset{g}{ˉ}_{1} (τ) - \frac{z _{1}}{z _{2}} \overset{g}{ˉ}_{2} (τ)

🤔…but it is written in terms of the
thing we want to estimate (

z_{1} / z_{2}

The solution?

Use an umbrella!☔

\frac{z _{1}}{z _{2}} \approx \frac{\frac{1}{m} \sum _{i = 1}^{m} \frac{g ˉ _{1} ( τ )}{g ˉ _{u} ( τ )}}{\frac{1}{m} \sum _{i = 1}^{m} \frac{g ˉ _{2} ( τ )}{g ˉ _{u} ( τ )}}

Using samples from

g_{u}

🤔What’s the optimal umbrella density?

\overset{g}{ˉ}_{u}^{*} (τ) \propto \overset{g}{ˉ}_{1} (τ) - \frac{z _{1}}{z _{2}} \overset{g}{ˉ}_{2} (τ)

🤔…but it is written in terms of the
thing we want to estimate (

z_{1} / z_{2}

In practice, we just try to get as close as possible.

A good umbrella distribution should cover regions of high likelihood in both distributions.

\overset{g}{ˉ}_{1} (τ)

\overset{g}{ˉ}_{2} (τ)

\overset{g}{ˉ}_{u} (τ)

Plan for Today

Part 1

Part 2

Part 3

Direct Estimation

Importance Sampling

Cross Entropy Method (Adaptive Importance Sampling)

Multiple Importance Sampling

Population Monte Carlo

Sequential Monte Carlo

Ratio of Normalizing Constants

Self-Normalized Importance Sampling

Bridge Sampling

Multilevel Splitting

\frac{z _{1}}{z _{2}} \approx \frac{\frac{1}{m} \sum _{i = 1}^{m} \frac{g ˉ _{1} ( τ )}{g ˉ _{u} ( τ )}}{\frac{1}{m} \sum _{i = 1}^{m} \frac{g ˉ _{2} ( τ )}{g ˉ _{u} ( τ )}}

Using samples from

g_{u}

But what are we even doing with all of this ☔?

Turns out we can use it to estimate the probability of failure
using samples from an unnormalized proposal!

unnormalized failure
distribution

nominal trajectory
distribution

unnormalized proposal
density

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

\overset{g}{ˉ}_{2} (τ) = p (τ)

\overset{g}{ˉ}_{u} (τ) = \overset{q}{ˉ} (τ)

Turns out we can use it to estimate the probability of failure
using samples from an unnormalized proposal!

unnormalized failure
distribution

nominal trajectory
distribution

unnormalized proposal
density

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

\overset{g}{ˉ}_{2} (τ) = p (τ)

\overset{g}{ˉ}_{u} (τ) = \overset{q}{ˉ} (τ)

This process results in the self-normalized importance
sampling (self-IS) estimator:

p_{fail} \approx \frac{\frac{1}{m} \sum _{i = 1}^{m} w _{i} 1 { τ _{i} \in / ψ }}{\frac{1}{m} \sum _{i = 1}^{m} w _{i}}

This process results in the self-normalized importance
sampling (self-IS) estimator:

p_{fail} \approx \frac{\frac{1}{m} \sum _{i = 1}^{m} w _{i} 1 { τ _{i} \in / ψ }}{\frac{1}{m} \sum _{i = 1}^{m} w _{i}}

p_{fail} \approx \frac{1}{m} i = 1 \sum m w_{i} 1 {τ_{i} \in / ψ}

It is kinda like regular importance sampling — we just normalize the weights by their sum.

This process results in the self-normalized importance
sampling (self-IS) estimator:

p_{fail} \approx \frac{\frac{1}{m} \sum _{i = 1}^{m} w _{i} 1 { τ _{i} \in / ψ }}{\frac{1}{m} \sum _{i = 1}^{m} w _{i}}

It is kinda like regular importance sampling — we just normalize the weights by their sum.

HOWEVER, the optimal proposal is very different…

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

\overset{g}{ˉ}_{2} (τ) = p (τ)

\overset{g}{ˉ}_{u}^{*} (τ) \propto \overset{g}{ˉ}_{1} (τ) - \frac{z _{1}}{z _{2}} \overset{g}{ˉ}_{2} (τ)

This process results in the self-normalized importance
sampling (self-IS) estimator:

p_{fail} \approx \frac{\frac{1}{m} \sum _{i = 1}^{m} w _{i} 1 { τ _{i} \in / ψ }}{\frac{1}{m} \sum _{i = 1}^{m} w _{i}}

It is kinda like regular importance sampling — we just normalize the weights by their sum.

HOWEVER, the optimal proposal is very different…

q^{*} (τ) \propto p (τ) ∣ 1 {τ \in / ψ} - p_{fail} ∣

This process results in the self-normalized importance
sampling (self-IS) estimator:

p_{fail} \approx \frac{\frac{1}{m} \sum _{i = 1}^{m} w _{i} 1 { τ _{i} \in / ψ }}{\frac{1}{m} \sum _{i = 1}^{m} w _{i}}

It is kinda like regular importance sampling — we just normalize the weights by their sum.

HOWEVER, the optimal proposal is very different…

q^{*} (τ) \propto p (τ) ∣ 1 {τ \in / ψ} - p_{fail} ∣

It should result in half the samples coming from the failure distribution and half from the success distribution.

This process results in the self-normalized importance
sampling (self-IS) estimator:

p_{fail} \approx \frac{\frac{1}{m} \sum _{i = 1}^{m} w _{i} 1 { τ _{i} \in / ψ }}{\frac{1}{m} \sum _{i = 1}^{m} w _{i}}

It is kinda like regular importance sampling — we just normalize the weights by their sum.

HOWEVER, the optimal proposal is very different…

q^{*} (τ) \propto p (τ) ∣ 1 {τ \in / ψ} - p_{fail} ∣

It should result in half the samples coming from the failure distribution and half from the success distribution.

It can be tough to sample from this proposal though…

This process results in the self-normalized importance
sampling (self-IS) estimator:

p_{fail} \approx \frac{\frac{1}{m} \sum _{i = 1}^{m} w _{i} 1 { τ _{i} \in / ψ }}{\frac{1}{m} \sum _{i = 1}^{m} w _{i}}

It is kinda like regular importance sampling — we just normalize the weights by their sum.

HOWEVER, the optimal proposal is very different…

q^{*} (τ) \propto p (τ) ∣ 1 {τ \in / ψ} - p_{fail} ∣

It should result in half the samples coming from the failure distribution and half from the success distribution.

It can be tough to sample from this proposal though…

Plan for Today

Part 1

Part 2

Part 3

Direct Estimation

Importance Sampling

Cross Entropy Method (Adaptive Importance Sampling)

Multiple Importance Sampling

Population Monte Carlo

Sequential Monte Carlo

Ratio of Normalizing Constants

Self-Normalized Importance Sampling

Bridge Sampling

Multilevel Splitting

\frac{z _{α}}{z _{β}} \approx \frac{1}{m} i = 1 \sum m \frac{g ˉ _{α} ( τ )}{g ˉ _{β} ( τ )}

Using samples from

g_{β}

Bridge Sampling

\overset{g}{ˉ}_{1} (τ)

\overset{g}{ˉ}_{2} (τ)

\overset{g}{ˉ}_{b} (τ)

Bridge Sampling

\frac{z _{1}}{z _{2}} \approx \frac{\frac{1}{m _{2}} \sum _{i = 1}^{m_{2}} \frac{g ˉ _{b} ( τ )}{g ˉ _{2} ( τ )}}{\frac{1}{m _{1}} \sum _{i = 1}^{m_{1}} \frac{g ˉ _{b} ( τ )}{g ˉ _{1} ( τ )}}

Using samples from

g_{1}

and

g_{2}

🤔What’s the optimal bridge density?

\overset{g}{ˉ}_{b}^{*} (τ) \propto \frac{g ˉ _{1} ( τ ) g ˉ _{2} ( τ )}{m _{1} g ˉ _{1} ( τ ) + m _{2} \frac{z _{1}}{z _{2}} g ˉ _{2} ( τ )}

Bridge Sampling

\frac{z _{1}}{z _{2}} \approx \frac{\frac{1}{m _{2}} \sum _{i = 1}^{m_{2}} \frac{g ˉ _{b} ( τ )}{g ˉ _{2} ( τ )}}{\frac{1}{m _{1}} \sum _{i = 1}^{m_{1}} \frac{g ˉ _{b} ( τ )}{g ˉ _{1} ( τ )}}

Using samples from

g_{1}

and

g_{2}

🤔What’s the optimal bridge density?

\overset{g}{ˉ}_{b}^{*} (τ) \propto \frac{g ˉ _{1} ( τ ) g ˉ _{2} ( τ )}{m _{1} g ˉ _{1} ( τ ) + m _{2} \frac{z _{1}}{z _{2}} g ˉ _{2} ( τ )}

🤔…but it is written in terms of the
thing we want to estimate (

z_{1} / z_{2}

Bridge Sampling

\frac{z _{1}}{z _{2}} \approx \frac{\frac{1}{m _{2}} \sum _{i = 1}^{m_{2}} \frac{g ˉ _{b} ( τ )}{g ˉ _{2} ( τ )}}{\frac{1}{m _{1}} \sum _{i = 1}^{m_{1}} \frac{g ˉ _{b} ( τ )}{g ˉ _{1} ( τ )}}

Using samples from

g_{1}

and

g_{2}

🤔What’s the optimal bridge density?

\overset{g}{ˉ}_{b}^{*} (τ) \propto \frac{g ˉ _{1} ( τ ) g ˉ _{2} ( τ )}{m _{1} g ˉ _{1} ( τ ) + m _{2} \frac{z _{1}}{z _{2}} g ˉ _{2} ( τ )}

🤔…but it is written in terms of the
thing we want to estimate (

z_{1} / z_{2}

In practice, we just try to get as close as possible.

A good bridge distribution should bridge the gap between both distributions.

\overset{g}{ˉ}_{1} (τ)

\overset{g}{ˉ}_{2} (τ)

\overset{g}{ˉ}_{b} (τ)

See algorithm 7.8 for a
technique to estimate
this density.

Let’s get back to failure probability estimation again… what should we do now?

unnormalized failure
distribution

nominal trajectory
distribution

unnormalized proposal
density

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

\overset{g}{ˉ}_{2} (τ) = p (τ)

\overset{g}{ˉ}_{b} (τ) = \overset{q}{ˉ} (τ)

Turns out this is a horrible plan!

It ends up being no better than direct estimation.

Example 7.9

Let’s do something even crazier!

\frac{z _{1}}{z _{2}} \approx \frac{\frac{1}{m _{2}} \sum _{i = 1}^{m_{2}} \frac{g ˉ _{b} ( τ )}{g ˉ _{2} ( τ )}}{\frac{1}{m _{1}} \sum _{i = 1}^{m_{1}} \frac{g ˉ _{b} ( τ )}{g ˉ _{1} ( τ )}}

Using samples from

g_{1}

and

g_{2}

Let’s do something even crazier!

\frac{z _{1}}{z _{2}} \approx \frac{\frac{1}{m _{2}} \sum _{i = 1}^{m_{2}} \frac{g ˉ _{b} ( τ )}{g ˉ _{2} ( τ )}}{\frac{1}{m _{1}} \sum _{i = 1}^{m_{1}} \frac{g ˉ _{b} ( τ )}{g ˉ _{1} ( τ )}}

Using samples from

g_{1}

and

g_{2}

p_{fail} = \frac{z _{p (τ ∣ τ \in / ψ)}}{z _{p (τ)}} = (\frac{z _{2}}{z _{p (τ)}}) (\frac{z _{3}}{z _{2}}) \dots (\frac{z _{p (τ ∣ τ \in / ψ)}}{z _{L - 1}})

Get a bunch of intermediate distributions and apply bridge sampling to them!

\frac{z _{2}}{z _{p (τ)}}

\times \frac{z _{3}}{z _{2}}

\times \frac{z _{4}}{z _{3}}

\times \frac{z _{p (τ ∣ τ \in / ψ)}}{z _{4}}

= \frac{z _{p (τ ∣ τ \in / ψ)}}{z _{p (τ)}} = \frac{p _{fail}}{1} = p_{fail}

Plan for Today

Part 1

Part 2

Part 3

Direct Estimation

Importance Sampling

Cross Entropy Method (Adaptive Importance Sampling)

Multiple Importance Sampling

Population Monte Carlo

Sequential Monte Carlo

Ratio of Normalizing Constants

Self-Normalized Importance Sampling

Bridge Sampling

Multilevel Splitting

Pick a notion of distance to failure $f (τ)$ (e.g. robustness)

We will require that

f (τ) \leq 0

for
failure trajectories such that

p (τ ∣ τ \in / ψ) = p (τ ∣ f (τ) \leq 0)

Pick a series of thresholds

γ_{i}

for the distance to failure
ranging from

\infty

0

Multilevel Splitting

Pick a notion of distance to failure $f (τ)$ (e.g. robustness)

Pick a series of thresholds

γ_{i}

for the distance to failure
ranging from

\infty

0

p_{fail} = ℓ = 2 \prod n P (f (τ) \leq γ_{ℓ} ∣ f (τ) \leq γ_{ℓ - 1})

If these probabilities are large enough, we
can estimate them using direct sampling!

We can ensure that these probabilities are large enough by selecting them adaptively.

Multilevel Splitting

p_{fail} = ℓ = 2 \prod n P (f (τ) \leq γ_{ℓ} ∣ f (τ) \leq γ_{ℓ - 1})

γ_{1} = \infty

γ_{2} = 0.67

γ_{3} = 0.62

p (f (τ) \leq 0.67 ∣ f (τ) \leq \infty)

0.5

p (f (τ) \leq 0.62 ∣ f (τ) \leq 0.67)

=

0.5

Multilevel Splitting

p_{fail} = ℓ = 2 \prod n P (f (τ) \leq γ_{ℓ} ∣ f (τ) \leq γ_{ℓ - 1})

γ_{1} = \infty

γ_{2} = 0.67

γ_{3} = 0.62

γ_{4} = 0.59

p (f (τ) \leq 0.67 ∣ f (τ) \leq \infty)

0.5

p (f (τ) \leq 0.62 ∣ f (τ) \leq 0.67)

0.5

p (f (τ) \leq 0.59 ∣ f (τ) \leq 0.62)

=

0.5

Multilevel Splitting

p_{fail} = ℓ = 2 \prod n P (f (τ) \leq γ_{ℓ} ∣ f (τ) \leq γ_{ℓ - 1})

γ_{1} = \infty

γ_{2} = 0.67

γ_{3} = 0.62

γ_{4} = 0.59

γ_{5} = 0.56

p (f (τ) \leq 0.67 ∣ f (τ) \leq \infty)

0.5

p (f (τ) \leq 0.62 ∣ f (τ) \leq 0.67)

0.5

p (f (τ) \leq 0.59 ∣ f (τ) \leq 0.62)

0.5

p (f (τ) \leq 0.56 ∣ f (τ) \leq 0.59)

=

0.5

Multilevel Splitting

p_{fail} = ℓ = 2 \prod n P (f (τ) \leq γ_{ℓ} ∣ f (τ) \leq γ_{ℓ - 1})

γ_{1} = \infty

γ_{2} = 0.67

γ_{3} = 0.62

γ_{4} = 0.59

γ_{5} = 0.56

γ_{6} = 0.53

p (f (τ) \leq 0.67 ∣ f (τ) \leq \infty)

0.5

p (f (τ) \leq 0.62 ∣ f (τ) \leq 0.67)

0.5

p (f (τ) \leq 0.59 ∣ f (τ) \leq 0.62)

0.5

p (f (τ) \leq 0.56 ∣ f (τ) \leq 0.59)

0.5

p (f (τ) \leq 0.53 ∣ f (τ) \leq 0.56)

=

0.5

Multilevel Splitting

p_{fail} = ℓ = 2 \prod n P (f (τ) \leq γ_{ℓ} ∣ f (τ) \leq γ_{ℓ - 1})

γ_{1} = \infty

γ_{2} = 0.67

γ_{3} = 0.62

γ_{4} = 0.59

γ_{5} = 0.56

γ_{6} = 0.53

p (f (τ) \leq 0.67 ∣ f (τ) \leq \infty)

0.5

p (f (τ) \leq 0.62 ∣ f (τ) \leq 0.67)

0.5

p (f (τ) \leq 0.59 ∣ f (τ) \leq 0.62)

0.5

p (f (τ) \leq 0.56 ∣ f (τ) \leq 0.59)

0.5

p (f (τ) \leq 0.53 ∣ f (τ) \leq 0.56)

0.5

γ_{7} = 0.49

p (f (τ) \leq 0.49 ∣ f (τ) \leq 0.53)

0.5

γ_{8} = 0.45

p (f (τ) \leq 0.45 ∣ f (τ) \leq 0.49)

0.5

γ_{9} = 0.40

p (f (τ) \leq 0.40 ∣ f (τ) \leq 0.45)

0.5

γ_{10} = 0.21

p (f (τ) \leq 0.21 ∣ f (τ) \leq 0.40)

0.5

γ_{11} = 0.11

p (f (τ) \leq 0.11 ∣ f (τ) \leq 0.21)

0.5

γ_{12} = 0.02

p (f (τ) \leq 0.02 ∣ f (τ) \leq 0.11)

0.5

γ_{13} = 0.00

p (f (τ) \leq 0.0 ∣ f (τ) \leq 0.02)

=

0.92

Multilevel Splitting

p_{fail} = ℓ = 2 \prod n P (f (τ) \leq γ_{ℓ} ∣ f (τ) \leq γ_{ℓ - 1})

γ_{1} = \infty

γ_{2} = 0.67

γ_{3} = 0.62

γ_{4} = 0.59

γ_{5} = 0.56

γ_{6} = 0.53

γ_{7} = 0.49

γ_{8} = 0.45

γ_{9} = 0.40

γ_{10} = 0.21

γ_{11} = 0.11

γ_{12} = 0.02

γ_{13} = 0.00

p (f (τ) \leq 0.67 ∣ f (τ) \leq \infty)

0.5

p (f (τ) \leq 0.62 ∣ f (τ) \leq 0.67)

0.5

p (f (τ) \leq 0.59 ∣ f (τ) \leq 0.62)

0.5

p (f (τ) \leq 0.56 ∣ f (τ) \leq 0.59)

0.5

p (f (τ) \leq 0.53 ∣ f (τ) \leq 0.56)

0.5

p (f (τ) \leq 0.49 ∣ f (τ) \leq 0.53)

0.5

p (f (τ) \leq 0.45 ∣ f (τ) \leq 0.49)

0.5

p (f (τ) \leq 0.40 ∣ f (τ) \leq 0.45)

0.5

p (f (τ) \leq 0.21 ∣ f (τ) \leq 0.40)

0.5

p (f (τ) \leq 0.11 ∣ f (τ) \leq 0.21)

0.5

p (f (τ) \leq 0.02 ∣ f (τ) \leq 0.11)

0.5

p (f (τ) \leq 0.0 ∣ f (τ) \leq 0.02)

0.92

\times

\times

\times

\times

\times

\times

\times

\times

\times

\times

\times

\overset{p}{^}_{fail} = 0.00046

Plan for Today

Part 1

Part 2

Part 3

Direct Estimation

Importance Sampling

Cross Entropy Method (Adaptive Importance Sampling)

Multiple Importance Sampling

Population Monte Carlo

Sequential Monte Carlo

Ratio of Normalizing Constants

Self-Normalized Importance Sampling

Bridge Sampling

Multilevel Splitting