Click or drag to resize

RareEventProbabilityEstimator Class

Represents a Cross-Entropy program designed to provide the estimation of rare event probabilities.
Inheritance Hierarchy
SystemObject
  Novacta.Analytics.AdvancedCrossEntropyProgram
    Novacta.Analytics.AdvancedRareEventProbabilityEstimator

Namespace:  Novacta.Analytics.Advanced
Assembly:  Novacta.Analytics (in Novacta.Analytics.dll) Version: 2.0.0
Syntax
public sealed class RareEventProbabilityEstimator : CrossEntropyProgram

The RareEventProbabilityEstimator type exposes the following members.

Constructors
  NameDescription
Public methodRareEventProbabilityEstimator
Initializes a new instance of the RareEventProbabilityEstimator class
Top
Properties
  NameDescription
Public propertyPerformanceEvaluationParallelOptions
Gets or sets options that configure the operation of the Parallel class while computing performance evaluations.
(Inherited from CrossEntropyProgram.)
Public propertySampleGenerationParallelOptions
Gets or sets options that configure the operation of the Parallel class while generating sample points.
(Inherited from CrossEntropyProgram.)
Top
Methods
  NameDescription
Public methodEquals
Determines whether the specified object is equal to the current object.
(Inherited from Object.)
Public methodEstimate
Runs this Cross-Entropy program designed to estimate the probability of the specified rare event context.
Protected methodEvaluatePerformances
Evaluates the performance of the points in the sample drawn in the current iteration.
(Inherited from CrossEntropyProgram.)
Protected methodFinalize
Allows an object to try to free resources and perform other cleanup operations before it is reclaimed by garbage collection.
(Inherited from Object.)
Public methodGetHashCode
Serves as the default hash function.
(Inherited from Object.)
Public methodGetType
Gets the Type of the current instance.
(Inherited from Object.)
Protected methodMemberwiseClone
Creates a shallow copy of the current Object.
(Inherited from Object.)
Protected methodRun
Runs this Cross-Entropy program in the specified context.
(Inherited from CrossEntropyProgram.)
Protected methodSample
Draws a sample having the specified size from a distribution defined in the given context and characterized by the designated parameter.
(Inherited from CrossEntropyProgram.)
Public methodToString
Returns a string that represents the current object.
(Inherited from Object.)
Top
Remarks

The Cross-Entropy method for rare event simulation

The current implementation of the RareEventProbabilityEstimator class is based on the main Cross-Entropy program for rare event simulation proposed by Rubinstein and Kroese (Algorithm 2.3.1)[1] .

A Cross-Entropy estimator is designed to evaluate the probability of rare events regarding the performance of complex systems. It is assumed that such probability must be evaluated with respect to a specific density function, member of a parametric family

LaTeX equation

where LaTeX equation is a vector representing a possible state of the system, and LaTeX equation is the set of allowable values for parameter LaTeX equation. Let LaTeX equation be the specific parameter value under which the probability must be evaluated. This is referred to as the nominal parameter.

A given event is eligible for being targeted by a RareEventProbabilityEstimator if it can be defined as

LaTeX equation

or

LaTeX equation

where LaTeX equation is the state space of the system, LaTeX equation is the function returning the system performance at state LaTeX equation and LaTeX equation is a performance value, which is referred to as the threshold level of the event under study, such that the set is rare under LaTeX equation.

The target probability can thus be represented as

LaTeX equation

where LaTeX equation is LaTeX equation or LaTeX equation, and LaTeX equation is the indicator function of LaTeX equation. In principle, one can base its estimation on a sample LaTeX equation drawn from LaTeX equation by evaluating the crude Monte Carlo estimator

LaTeX equation

However, if LaTeX equation is rare under LaTeX equation, a large number of indicator functions will evaluate to zero, leading to inefficiencies. To overcome such difficulty, the Cross-Entropy method suggests to exploit a likelihood ratio estimator: instead of sampling from LaTeX equation, the method select another density in LaTeX equation by identifying a parameter LaTeX equation that guarantees the most accurate estimate of the target probability for a specified simulation effort, or sample size LaTeX equation. Given a sample LaTeX equation from LaTeX equation, the probability is thus estimated as

LaTeX equation

where

LaTeX equation

is the likelihood ratio of LaTeX equation to LaTeX equation evaluated at state LaTeX equation.

The idea behind the Cross-Entropy method is to select LaTeX equation by taking into account the estimator based on the ratio

LaTeX equation

where

LaTeX equation

is the density of LaTeX equation conditional on LaTeX equation. Such estimator is unusable, since it depends on the target probability. However, it is ideally optimal because its variance is equal to zero. For this reason, it is proposed to select the parameter LaTeX equation such that the corresponding density LaTeX equation is the closest to the optimal one, the difference between two densities, say LaTeX equation and LaTeX equation, being measured as a Kullback–Leibler divergence:

LaTeX equation

The selection is thus obtained by minimizing the divergence between the generic density in LaTeX equation, say LaTeX equation, and the ideal density LaTeX equation:

LaTeX equation

Such minimization corresponds to the maximization

LaTeX equation

where LaTeX equation is the expectation operator under LaTeX equation, or, equivalently, to

LaTeX equation

for every parameter LaTeX equation. This implies that, given a sample LaTeX equation from LaTeX equation, a solution to such optimization can be estimated through the solution to the program:

LaTeX equation

where

LaTeX equation

and

LaTeX equation

In this context, LaTeX equation is said the sampling reference parameter, while the elements in set LaTeX equation are referred to as the elite sample positions, and the corresponding sample points LaTeX equation, for LaTeX equation, as the elite sampled states. The interest in such an approach is due to the possibility of choosing a parameter LaTeX equation under which the event LaTeX equation is less rare under density LaTeX equation than under density LaTeX equation. In this way, in order to obtain a good estimation, a smaller simulation effort would be required.

The selection of the optimal reference parameter is an iterative multi step procedure, in which, at each iteration LaTeX equation, a new level LaTeX equation and a new reference parameter LaTeX equation are identified. The goal being to obtain, after a number of iterations LaTeX equation, a reference parameter very close to the optimal one and set LaTeX equation. The algorithm has two main steps.

Sampling step

The first one, the sampling step, is responsible for generating diverse candidate states of the system. Let LaTeX equation be the reference parameter at iteration LaTeX equation, with LaTeX equation, and let LaTeX equation be the sample drawn from LaTeX equation.

Updating step

To avoid the difficulties due to the rareness of LaTeX equation under LaTeX equation, the sample drawn in the sampling step is not exploited to estimate LaTeX equation. Instead, an iteration specific target event is defined in terms of a new iteration level LaTeX equation, which is set as follows.

The sample performances, LaTeX equation, are computed and sorted in increasing order, say obtaining the following ordering:

LaTeX equation

Let LaTeX equation be the sampled state such that LaTeX equation, LaTeX equation, and consider a constant, referred to as the rarity of the program, say LaTeX equation, set to a value in the interval LaTeX equation.

If LaTeX equation then the points LaTeX equation occupying a position greater than or equal to LaTeX equation are the elite sampled states, with LaTeX equation being the ceiling function. In this case, the current iteration is said to reach a performance level equal to LaTeX equation.

Otherwise, if LaTeX equation then elite sampled states can be defined as those points occupying a position less than or equal to LaTeX equation, where LaTeX equation is the floor function. Such points are thus LaTeX equation, and the current iteration is said to reach a performance level equal to LaTeX equation.

Once that the elite states have been identified, the joint distribution from which the states will be sampled in the next iteration is updated by estimating its parameters using the elite states only.

The iteration parameter LaTeX equation is chosen to be the optimal one for estimating LaTeX equation by solving the program

LaTeX equation

In this way, new reference parameters are selected so that the target event becomes more and more probable than under the nominal distribution of interest. As discussed in the remarks about the CrossEntropyProgram class, these operations correspond to the updating step of a Cross-Entropy program.

The algorithm stops iterating when the iteration level reaches the event level, i.e. when LaTeX equation if LaTeX equation; otherwise, when LaTeX equation.

Executing a Cross-Entropy estimator

Class RareEventProbabilityEstimator follows the Template Method pattern[2] by defining in an operation the structure of a Cross-Entropy algorithm aimed to estimate the probability of a rare event. Estimate is the template method, in which the invariant parts of a Cross-Entropy estimator are implemented once, deferring the implementation of behaviors that can vary to a RareEventProbabilityEstimationContext instance, that method Estimate receives as a parameter.

RareEventProbabilityEstimationContext inherits or defines abstract or virtual methods which represent some primitive operations of the template method, i.e. those varying steps that its subclasses will override to define the concrete behavior of the algorithm. See the documentation of class RareEventProbabilityEstimationContext for examples of how to implement a context for rare event simulations.

Bibliography
[1] Rubinstein, R.Y. and Kroese, D.P., The Cross-Entropy Method, A unified Approach to Combinatorial Optimization, Monte-Carlo Simulation, and Machine Learning, Springer, New York. (2004)
[2] Gamma, E., Helm, R., Johnson, R. and Vlissides, J., Design Patterns, Elements of Reusable Object-Oriented Software, Addison-Wesley, Reading, MA. (1995)
See Also