Cross-entropy optimisation of importance sampling parameters for statistical model checking

Details Cross-entropy optimisation of importance sampling parameters for statistical model checking Cross-entropy optimisation of importance sampling parameters for statistical model checking

2012-01-25

arxiv.org/abs/1201.5229v1

Computer Science

Performance

16 pages, 8 figures, LNCS style

Scientific paper

Statistical model checking avoids the exponential growth of states associated with probabilistic model checking by estimating properties from multiple executions of a system and by giving results within confidence bounds. Rare properties are often very important but pose a particular challenge for simulation-based approaches, hence a key objective under these circumstances is to reduce the number and length of simulations necessary to produce a given level of confidence. Importance sampling is a well-established technique that achieves this, however to maintain the advantages of statistical model checking it is necessary to find good importance sampling distributions without considering the entire state space. Motivated by the above, we present a simple algorithm that uses the notion of cross-entropy to find the optimal parameters for an importance sampling distribution. In contrast to previous work, our algorithm uses a low dimensional vector of parameters to define this distribution and thus avoids the often intractable explicit representation of a transition matrix. We show that our parametrisation leads to a unique optimum and can produce many orders of magnitude improvement in simulation efficiency. We demonstrate the efficacy of our methodology by applying it to models from reliability engineering and biochemistry.

Affiliated with

Also associated with

No associations

Rating

Cross-entropy optimisation of importance sampling parameters for statistical model checking does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Cross-entropy optimisation of importance sampling parameters for statistical model checking, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cross-entropy optimisation of importance sampling parameters for statistical model checking will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-683250