Stanford AA228V I Validation of Safety Critical Systems I Adaptive Importance Sampling

Key Concepts

• Importance Sampling: A technique to estimate the probability of rare events by sampling from a different distribution (proposal distribution) and weighting the samples.
• Proposal Distribution (q(τ)): A distribution used in importance sampling to generate samples, ideally producing more failures than the nominal distribution.
• Direct Estimation: A naive approach to failure probability estimation by sampling from the nominal trajectory distribution.
• Failure Distribution: The conditional probability distribution of trajectories given that they result in failure.
• Cross-Entropy Method: An adaptive importance sampling technique that iteratively fits a proposal distribution by minimizing the cross-entropy between the proposal and the failure distribution.
• Adaptive Importance Sampling: A class of methods that iteratively refine the proposal distribution based on the samples obtained.
• Multiple Importance Sampling (MIS): An extension of importance sampling that uses multiple proposal distributions to improve the estimation of failure probability.
• Population Monte Carlo (PMC): An adaptive importance sampling method that maintains a population of proposal distributions and iteratively refines them based on resampling and perturbation.
• Sequential Monte Carlo (SMC): A non-parametric method that moves samples from the nominal distribution to the failure distribution through a series of intermediate distributions using Markov Chain Monte Carlo (MCMC).
• Ratio of Normalizing Constants: A general problem that encompasses importance sampling as a special case, allowing for the derivation of different types of estimators.
• Robustness: A measure of the distance to failure, often used as a criterion for selecting elite samples or defining intermediate distributions.
• Smoothing: A technique used in SMC to create a series of intermediate distributions between the nominal and failure distributions by convolving the failure indicator function with a Gaussian kernel.

Importance Sampling Recap

• Problem: Direct estimation from the nominal trajectory distribution is inefficient for rare failure events due to low sample counts and high variance.
• Solution: Importance sampling involves sampling from a proposal distribution q(τ) that generates more failures.
• Weighting: Samples are weighted by the likelihood ratio p(τ)/q(τ) to correct for the bias introduced by sampling from q(τ). p(τ) is the likelihood under the nominal distribution.
• Proposal Selection: The choice of proposal distribution significantly impacts the estimator's performance. A good proposal assigns high likelihood to likely failures. A bad proposal can perform worse than direct estimation.
• Optimal Proposal: The optimal proposal distribution is the failure distribution itself, but this is generally unknown since its normalizing constant is the failure probability we are trying to estimate.
• Practical Approach: Select a proposal distribution that is as close as possible to the failure distribution and whose density is known.
• Constraint: The proposal distribution must assign non-zero density to every possible failure trajectory.

Hand-Designing vs. Adaptive Proposals

• Hand-Designing: Manually selecting a proposal distribution based on prior knowledge of the system. The fuzzing distribution from project 1 is suggested as a starting point for project 2.
• Adaptive Proposals: Automatically learning a proposal distribution from data.
• MCMC/Rejection Sampling: Using MCMC or rejection sampling to draw samples from the failure distribution (knowing only the unnormalized density).
• Fitting a Distribution: Fitting a known distribution (e.g., Gaussian) to the samples from the failure distribution using maximum likelihood estimation.
• Challenges:
  • Generating samples from the failure distribution can be difficult (requires MCMC/rejection sampling).
  • Fitting a distribution to high-dimensional, multi-modal failure distributions can be challenging.

Cross-Entropy Method

• Goal: Fit a good proposal distribution using samples from a distribution that is easier to sample from than the failure distribution.
• Process:
  1. Draw samples from an initial proposal distribution q(τ).
  2. Fit a new proposal distribution from a model class by minimizing the cross-entropy between the proposal and the failure distribution.
• Cross-Entropy Minimization: For common model classes (e.g., Gaussian), minimizing cross-entropy is equivalent to computing a weighted maximum likelihood estimate.
• Weights: Weights are based on importance weights, where non-failure samples have zero weight, and likely failures have higher weights.
• Initial Proposal: The nominal trajectory distribution (Gaussian) is a good initial proposal.
• Limitation: If failures are rare, the initial proposal may not generate any failure samples, resulting in zero weights and algorithm failure.

Adaptive Importance Sampling (Cross-Entropy Method Extension)

• Goal: Iteratively adapt the proposal distribution to move closer to the failure distribution.
• Process:
  1. Pick an initial proposal distribution (e.g., nominal trajectory distribution).
  2. Define a notion of closeness to failure f(τ), such that f(τ) ≤ 0 for all failure trajectories.
  3. Iteratively:
     • Draw samples from the current proposal.
     • Compute f(τ) for each sample.
     • Select the top m elite samples.
     • Set a threshold γ based on the highest objective value of the elite samples.
     • Minimize the cross-entropy between the proposal and p(τ | f(τ) ≤ γ).
     • Fit the next proposal distribution using weighted maximum likelihood.
• Threshold Relaxation: Instead of minimizing the cross-entropy with the failure distribution directly, minimize it with a relaxed condition f(τ) ≤ γ.
• Iteration: Repeat the process until the threshold γ becomes less than 0 (enough failure samples) or for a set number of iterations.
• Final Proposal: Perform importance sampling with the final proposal distribution.
• Threshold Capping: The threshold is capped at 0 to prevent fitting distributions to non-failure regions.
• Multimodal Distributions: If there are multiple failure modes, a multimodal distribution (e.g., Gaussian mixture) can be fitted.

Multiple Importance Sampling (MIS)

• Goal: Use multiple proposal distributions to improve failure probability estimation.
• Process:
  1. Draw samples from each of the n proposal distributions qᵢ(τ).
  2. Estimate the probability of failure using a weighted sum of the samples.
• Standard Multiple Importance Sampling (SMIS):
  • Weights are calculated as p(τ) / qᵢ(τ), where qᵢ(τ) is the proposal distribution from which the sample was drawn.
• Deterministic Mixture Model:
  • An alternative weighting scheme assumes that the samples were generated by randomly selecting a proposal distribution at each step.
  • The weights are calculated based on the mixture distribution q_mix(τ) = (1/n) Σ qᵢ(τ).
  • This approach can have lower variance than SMIS.
• Benefits: MIS can be more effective than single importance sampling, especially when there are multiple failure modes.

Population Monte Carlo (PMC)

• Goal: Adapt a population of proposal distributions to better estimate failure probability.
• Process:
  1. Start with an initial population of proposal distributions.
  2. Draw one sample from each proposal distribution.
  3. Compute the importance weight for each sample (p(τ) / q(τ)).
  4. Resample the samples based on their importance weights (more likely to resample samples with high weights).
  5. Create new proposal distributions centered at the resampled points (e.g., Gaussian with constant variance).
  6. Repeat steps 2-5 for a set number of iterations.
  7. Perform multiple importance sampling with the final set of proposal distributions.
• Initial Population: It is crucial that the initial population of proposals covers the space of possibilities as best as possible.
• Variance Selection: The variance of the new proposal distributions is a hyperparameter that balances exploration and exploitation.

Sequential Monte Carlo (SMC)

• Goal: Move samples from the nominal distribution to the failure distribution through a series of intermediate distributions using MCMC.
• Non-Parametric: SMC maintains only samples and does not require fitting parametric distributions.
• Intermediate Distributions:
  • Created using smoothing, where the failure indicator function is convolved with a Gaussian kernel.
  • The smoothing parameter (epsilon) is gradually decreased to transition from the nominal to the failure distribution.
  • Alternatively, a threshold on the distance to failure can be used and gradually decreased.
• MCMC:
  • For each intermediate distribution, an MCMC chain is initiated from each sample.
  • The density of the intermediate distribution is used as the target density for the MCMC.
• Weighting:
  • Each sample is assigned a weight that is updated at each transition.
  • The weight is multiplied by the likelihood ratio of the new and old distributions.
• Probability of Failure Estimation: The average of the final weights provides an estimate of the probability of failure.
• Resampling: A resampling step can be performed after each transition to improve MCMC efficiency.

Ratio of Normalizing Constants

• General Problem: Importance sampling is a special case of determining the ratio of normalizing constants between two distributions.
• Alternative Estimators: Viewing importance sampling as a special case of a more general problem allows for the derivation of other types of estimators, such as self-normalized importance sampling, bridge sampling, and umbrella sampling.

Conclusion

The lecture provides a detailed overview of various techniques for failure probability estimation, focusing on importance sampling and its adaptive variants. It emphasizes the importance of selecting appropriate proposal distributions and highlights the trade-offs between different methods. The lecture also introduces more advanced techniques like multiple importance sampling, population Monte Carlo, and sequential Monte Carlo, which offer improved performance and flexibility for complex systems. Finally, it briefly touches upon the general problem of estimating the ratio of normalizing constants, which provides a broader perspective on importance sampling and related methods.