Документ взят из кэша поисковой машины. Адрес оригинального документа : http://qfthep.sinp.msu.ru/talks/popov.aa-qfthep2010.pdf Дата изменения: Tue Sep 14 12:06:07 2010 Дата индексирования: Mon Oct 1 19:48:21 2012 Кодировка:

Prospects of Matrix Elements Integration with Markov Chain Monte Carlo
Lev Dudko1
1

Andrey Popov

2

SINP MSU 2 aa.p opov@www-hep.sinp.msu.ru, SINP MSU

QFTHEP 2010, Golitsyno, Moscow, Russia, 14.09.2010

Lev Dudko, Andrey Popov

SINP MSU aa.popov@www-hep.sinp.msu.ru, SINP MSU

Prospects of Matrix Elements Integration with Markov Chain Monte Carlo


Outline

The traditional approach to integrate the squared matrix element and some of its difficulties. What is Markov chain Monte Carlo? Its pros and cons. An illustration on integration with Markov chain Monte Carlo. Summary and conclusions. This report is rather a call to pay attention to a perspective group of methods than a completed research.

Lev Dudko, Andrey Popov

SINP MSU aa.popov@www-hep.sinp.msu.ru, SINP MSU

Prospects of Matrix Elements Integration with Markov Chain Monte Carlo


The Traditional Way of Cross-Section Calculation
The squared matrix element (SQME) is usually integrated by the means of VEGAS algorithm or other adaptive Monte Carlo (MC) techniques. VEGAS samples the probe points from a piecewise constant coordinate-wise factorable distribution which approximates the original SQME. The better this approximation is, the smaller the uncertainty. But this condition cannot be satisfied easily since the SQME is usually poorly coordinate-wise factorable because of the peak "ridges" corresponding to the propagators' denominators. To overcome the obstacle one can introduce a smart remapping of the phase space that smooths the "ridges" ("regularization").
Lev Dudko, Andrey Popov SINP MSU aa.popov@www-hep.sinp.msu.ru, SINP MSU Prospects of Matrix Elements Integration with Markov Chain Monte Carlo


Problems of the Traditional Way
In CompHEP package the phase space remapping is introduced manually which is not convenient or even trivial in case of large (say, 5 В 7) number of particles in the final state. Two possibilities to solve the issue: automatic remapping of the phase space, developing of the integration method less sensitive to the phase space remapping. The methods described in the report might be a step in the line of the second option.

Lev Dudko, Andrey Popov

SINP MSU aa.popov@www-hep.sinp.msu.ru, SINP MSU

Prospects of Matrix Elements Integration with Markov Chain Monte Carlo


What Is Markov Chain Monte Carlo?
Markov chain
Let xi be a point in the phase space of some process. Let the next point xi +1 be chosen with the conditional probability P {xi +1 | xi }, and so on. The important feature is that the probability P depends on the latest position only but not on the earlier ones. Such a stochastic sequence is called the Markov chain.

MCMC
One can relatively easily construct a Markov chain that mimics a sample from any given probability density function (ProbDF), e.g. SQME of the process of interest. The family of methods to do the job are called Markov chain Monte Carlo (MCMC).

Lev Dudko, Andrey Popov

SINP MSU aa.popov@www-hep.sinp.msu.ru, SINP MSU

Prospects of Matrix Elements Integration with Markov Chain Monte Carlo


Current Status of MCMC

Although MCMC is quite novel in high energy physics it has been used in statistics for a long time, especially for two recent decades. In Bayesian statistics MCMC is the most popular way to calculate the expectations with respect to very complicated posterior ProbDFs (as elaborate as an artificial neural network weights distribution, for example). So, MCMC techniques are well tested and understood. There is an intense current development, too.

Lev Dudko, Andrey Popov

SINP MSU aa.popov@www-hep.sinp.msu.ru, SINP MSU

Prospects of Matrix Elements Integration with Markov Chain Monte Carlo


MCMC: pro et contra
MCMC can sample points from a quite complicated ProbDF (i.e. it is less sensitive to the sharp "ridges" of the integrand). But: The points are correlated. MCMC usually needs smart tunning. I mentioned sampling, what is about integration? In the line of last point the question is whether one can estimate the cross-section given the sample (withstanding the "curse of dimensionality") and whether the method's performance is comparable to VEGAS with the phase space remapping applied.
Lev Dudko, Andrey Popov SINP MSU aa.popov@www-hep.sinp.msu.ru, SINP MSU Prospects of Matrix Elements Integration with Markov Chain Monte Carlo


Integration with MCMC (1/5)
In statistics MCMC is typically used to calculate the expectation of the form Ep [f ] = dx f (x) p (x) 1 N dy p (y)
N

f (xi ),
i =1

where points {xi } are samples from (unnormalized) ProbDF p (·) via MCMC. It is not what we want, but one can try 1 = 1 = dx p (x) dx 1 p (x) 1 = Ep p (x) dy p (y) p

with p (·) standing for the SQME. Since SQME can be close to zero, it is better to use, e.g., 1 1 = Ep , ~ +h p ~
Lev Dudko, Andrey Popov

p (x) = p (x) + h. ~
SINP MSU aa.popov@www-hep.sinp.msu.ru, SINP MSU

Prospects of Matrix Elements Integration with Markov Chain Monte Carlo


Integration with MCMC (2/5)
The method described above provides a computationally feasible way to estimate the integral given the (non-uniform) sample from the SQME. Moreover, under some natural assumptions one can deduce that this is the only possible way to estimate the cross-section by evaluating an expectation of the form dx F [p (x)] p (x) = Ep [F [p ]] . dy p (y)

Given all the other choices of F (·) this expectation cannot be a smooth non-constant function of the integral.

Lev Dudko, Andrey Popov

SINP MSU aa.popov@www-hep.sinp.msu.ru, SINP MSU

Prospects of Matrix Elements Integration with Markov Chain Monte Carlo


Integration with MCMC (3/5)
Integral estimation 0.0040

0.0035

0.0030

0.0025

0.0020

0

100

200

300

400

500

600

в10 700 800 Epoch

3

Figure: Integral estimation over several Markov chains in parallel
Lev Dudko, Andrey Popov SINP MSU aa.popov@www-hep.sinp.msu.ru, SINP MSU

Prospects of Matrix Elements Integration with Markov Chain Monte Carlo


Integration with MCMC (4/5)
However, one can prove analytically that the method demonstrates larger uncertainty than the simple uniform MC does when applied to Cauchy distribution (and therefore is expected to perform worse given a real SQME). The numerical test also reveals it as being not better than the uniform MC (see the next slide). Nevertheless, the illustration example is not the only one possibility to estimate the cross-section. One can try to calculate the empirical density of sampled points. Since the density is given by p (·)/ dy p (y), it will immediately retrieve the value of the integral. This option will be investigated in the near future.

Lev Dudko, Andrey Popov

SINP MSU aa.popov@www-hep.sinp.msu.ru, SINP MSU

Prospects of Matrix Elements Integration with Markov Chain Monte Carlo


Integration with MCMC (5/5)

Figure: Errors of MCMC-integration and uniform MC
Lev Dudko, Andrey Popov

1/2 dx -1/2 x 2 +1

SINP MSU aa.popov@www-hep.sinp.msu.ru, SINP MSU

Prospects of Matrix Elements Integration with Markov Chain Monte Carlo


Summary and Conclusions
MCMC is a well-developed family of methods that can generate a sample from an elaborate ProbDF such as a SQME which is a fascinating feature. To profit from this feature one should design a computationally efficient way to estimate the integral given a sample of the specific form. Thanks to the advantages of MCMC such an algorithm might provide a sufficiently small uncertainty with no (not all) phase space remappings applied. Of course, nothing is guaranteed and the actual performance will depend considerably on the details of the integration technique used.
Lev Dudko, Andrey Popov SINP MSU aa.popov@www-hep.sinp.msu.ru, SINP MSU

Prospects of Matrix Elements Integration with Markov Chain Monte Carlo


Backup Slides

Lev Dudko, Andrey Popov

SINP MSU aa.popov@www-hep.sinp.msu.ru, SINP MSU

Prospects of Matrix Elements Integration with Markov Chain Monte Carlo


Metropolis Algorithm
Metropolis algorithm is the simplest one of all the MCMC family, but nevertheless the most popular. Let p (·) be the (unnormalized) ProbDF to sample from, and q (· | ·) be an auxiliary ("proposal") density that is easy to sample from. The proposal ProbDF is required to be symmetric: q (x | y) = q (y | x); the Gaussian is often used: q (x | x) exp{-(x - x )2 }.

Algorithm
At step i sample a proposal point x q (· | xi ). Accept x with probability min{p (x )/p (x), 1}. If the proposal point is accepted, xi +1 = x , otherwise the current point is copied in the sample: xi +1 = xi .
Lev Dudko, Andrey Popov SINP MSU aa.popov@www-hep.sinp.msu.ru, SINP MSU

Prospects of Matrix Elements Integration with Markov Chain Monte Carlo


Uncertainty of the Illustration Method
The uncertainty of MCMC method used for illustration is [I ] I +h = I I (I + h ) dx -1 p (x) + h . N

Here I = dx p (x), N -- number of sampled points,
+

=1+2
s =1

(s )

is the number of correlated points to give an equivalent of one independent point, (·) -- the autocorrelation function: (s ) = 1 Ep f (xi ) - Ep [f ] f (x 2
i +s

- Ep [f ]) ,

and f (·) is some scalar function of the sampled point.
Lev Dudko, Andrey Popov SINP MSU aa.popov@www-hep.sinp.msu.ru, SINP MSU Prospects of Matrix Elements Integration with Markov Chain Monte Carlo