Stanford AA228V I Validation of Safety Critical Systems I Importance Sampling

Key Concepts

• Failure Distribution: The probability distribution over all possible failure trajectories of a system.
• Unnormalized Density: A function proportional to the probability density function of a distribution, but without the normalizing constant.
• Markov Chain Monte Carlo (MCMC): A class of algorithms for sampling from a probability distribution by constructing a Markov chain that has the desired distribution as its equilibrium distribution.
• Burn-in Period: An initial period in MCMC sampling that is discarded to allow the Markov chain to converge to its stationary distribution.
• Thinning: A technique used in MCMC to reduce correlation between samples by keeping only every nth sample.
• Smoothing: A technique used to modify the failure distribution to make it easier to sample from, by assigning non-zero probabilities to success trajectories that are close to failure.
• Rejection Sampling: A method for generating random samples from a probability distribution by proposing samples from another distribution and accepting or rejecting them based on a certain criterion.
• Kernel: A probability distribution used to propose the next sample in MCMC.
• Nominal Trajectory Distribution: The probability distribution over all possible trajectories of a system under normal operating conditions.
• Direct Estimation: Estimating the probability of failure by directly sampling from the nominal trajectory distribution and counting the number of failures.
• Importance Sampling: A variance reduction technique used for estimating properties of a distribution by sampling from a different distribution (proposal distribution) and weighting the samples appropriately.
• Proposal Distribution: A distribution used in importance sampling to generate samples that are more likely to be in the region of interest (e.g., failure region).
• Maximum Likelihood Estimation (MLE): A method for estimating the parameters of a statistical model by finding the parameter values that maximize the likelihood function.
• Bayesian Estimation: A method for estimating the parameters of a statistical model by combining prior knowledge with observed data to obtain a posterior distribution over the parameters.
• Bernoulli Distribution: A discrete probability distribution that models the probability of success or failure of a single trial.
• Unbiased Estimator: An estimator whose expected value is equal to the true value of the parameter being estimated.
• Consistent Estimator: An estimator that converges to the true value of the parameter being estimated as the sample size increases.
• Variance: A measure of the spread or dispersion of a set of values.
• Effective Sample Size: A measure of the number of independent samples in a set of correlated samples, such as those obtained from MCMC.
• Probabilistic Programming: A programming paradigm that allows users to specify probabilistic models as computer programs and then automatically perform inference on those models.

Sampling from Failure Distributions and Estimating Failure Probability

Smoothing for MCMC

• Problem: Naive MCMC can get stuck in one failure mode of a bimodal failure distribution due to low likelihood assigned to other modes by the kernel.
• Solution: Smooth the failure distribution to allow the algorithm to move between failure modes.
• Distance Function (delta): Defined as zero for failures and positive otherwise, representing a trajectory's distance to failure (e.g., max(robustness, 0)).
• Smooth Approximation: Replace the indicator function (1 for failure, 0 otherwise) with a normal distribution centered at zero with a small variance (epsilon).
• Epsilon Parameter: Controls the amount of smoothing.
  • Epsilon = 0: No smoothing, collapses back to the original indicator function.
  • Epsilon = Infinity: Uniform distribution, approaches the nominal trajectory distribution.
• Rejection Sampling Post-Smoothing: Reject non-failure samples to ensure the final sample set represents the failure distribution. This is equivalent to rejection sampling with the smooth distribution as the proposal.
• Practical Considerations: Epsilon needs to be tuned for the specific system. Too little smoothing results in getting stuck in one mode; too much wastes samples on non-failures.
• Scaling Up: Smoothing can be applied to high-dimensional problems like the pendulum (50 dimensions). Samples become full trajectories (initial state and disturbances).
• Gradient-Based Kernels: Use gradients of the likelihood to define the kernel, guiding the random walk towards increasing likelihood regions. Examples include Hamiltonian Monte Carlo (HMC) and No-U-Turn Sampler (NUTS).
• Probabilistic Programming: Specify probabilistic models as computer programs, allowing automatic inference. Example: Using Turing.jl to sample from a smoothed failure distribution.

Estimating Probability of Failure

• Definition: The probability of failure is defined as the expectation over trajectories from the nominal trajectory distribution of whether or not they are a failure. Mathematically, this is the integral over all possible trajectories of whether or not they're a failure weighted by their likelihood under the nominal distribution.
• Connection to Failure Distribution: The probability of failure is the normalizing constant of the failure distribution.
• Direct Estimation:
  • Produce samples from the nominal system.
  • Label each outcome as 1 (failure) or 0 (success).
  • Treat this as sampling from a Bernoulli distribution with parameter p_fail.
  • Use parameter estimation techniques (MLE or Bayesian) to estimate p_fail.
• Maximum Likelihood Estimation (MLE):
  • Estimate p_fail as the number of failure trajectories divided by the total number of trajectories.
  • Properties:
    • Unbiased: The expectation of the estimate is the true probability of failure.
    • Consistent: Converges to the true value in the limit of infinite samples.
    • Variance: (p_fail * (1 - p_fail)) / m, where m is the number of samples.
  • Limitations:
    • High variance for rare failure events.
    • Can result in an estimate of zero if no failures are observed in the sample.
• Bayesian Estimation:
  • Produce a distribution over the probability of failure.
  • Use a beta distribution as the posterior distribution over p_fail.
  • Allows quantifying confidence in the estimate (e.g., probability that p_fail is less than 0.01).
  • Can be updated as more samples are collected.
• Importance Sampling:
  • Motivation: Direct estimation is inefficient for rare failure events.
  • Key Idea: Draw samples from a proposal distribution (Q) that is more likely to produce failure trajectories.
  • Reweighting: Correct for the bias introduced by sampling from Q by reweighting the samples.
  • Importance Weight (Wi): p(tau_i) / Q(tau_i), where p is the nominal trajectory distribution and Q is the proposal distribution.
  • Estimate of p_fail: Weighted sum of failure indicators, where the weights are the importance weights.
  • Properties: Unbiased and consistent estimator of the true probability of failure.
  • Algorithm:
    1. Draw samples from Q.
    2. Evaluate the PDFs of p and Q for each sample.
    3. Compute the importance weights.
    4. Estimate p_fail as the weighted sum of failure indicators.
  • Effective Sample Size: A measure of the number of independent samples in the importance sampling estimate.
  • Optimal Proposal Distribution: The one that minimizes the variance of the estimator. It is equal to the failure distribution, but this is generally unknown.
  • Practical Approach: Select a proposal distribution that is as close as possible to the failure distribution, while being able to draw samples from it and compute its normalized density.
  • Adaptive Importance Sampling: Fit a distribution (e.g., Gaussian) to samples from the failure distribution and use that as the proposal distribution.

Conclusion

The lecture covers techniques for sampling from failure distributions and estimating the probability of failure. Smoothing is introduced as a method to improve MCMC sampling from complex failure distributions. Direct estimation, MLE, and Bayesian estimation are discussed for estimating the probability of failure, highlighting their limitations for rare failure events. Importance sampling is presented as a more efficient technique for rare failures, involving sampling from a proposal distribution and reweighting the samples. The concept of an optimal proposal distribution is introduced, and a practical approach of fitting a distribution to samples from the failure distribution is suggested. The lecture emphasizes the importance of selecting a proposal distribution that is both easy to sample from and has a computable normalized density.