[AstroPy] [ANN] Nestle: Nested sampling

Fri Oct 9 02:45:17 EDT 2015

Hi Anne,

You're absolutely right about the opportunity for parallelism and thanks
for the PR! (https://github.com/kbarbary/nestle/pull/13)

Regarding nested sampling taking forever to converge: Yes, this will
definitely be an issue for your problem: the constrained region shrinks by
a factor of exp(1 / N_points) on each iteration, which is quite small for
large N_points (and N_points should indeed be relatively large for
high-dimensional problems). As far as I'm aware, this shrinkage factor is a
general characteristic of nested sampling and I don't know a way around it.
My only advice would be to cheat a bit and use a different method, such as
optimization, to first narrow down the prior volume if possible (assuming
that most of the prior contributes negligibly to the evidence and that the
posterior does not have widely separated significant peaks).

Regarding covariances, you are probably aware of this, but just for
clarity: the ellipsoids are calculated in the unit cube corresponding to
the prior volume, rather than in real parameter space. So, to the extent
that the shrinkage ratio is the same in each dimension, the constrained
area will be spherical. Conversely, if one parameter is much more
constrained by the data than another, the ellipsoid will be quite skinny. I
would recommend trying classic nested sampling, where calculating the point
covariance isn't as integral to the method, but unfortunately the current
implementation of classic nested sampling in nestle does use the
covariance. That could be changed though.

Sorry I don't have better answers for you -- sounds like you have a tough
problem!

-- Kyle

On Thu, Oct 8, 2015 at 2:05 PM, Anne Archibald <archibald at astron.nl> wrote:

> Hi Kyle,
>
> I am very interested in nestle as an alternative MCMC method for a project
> I'm working on (testing general relativity with pulsar timing observations
> of a triple system; see http://adsabs.harvard.edu/abs/2014Natur.505..520R for
> more). I was considering multinest but the ability to get "under the hood"
> is really valuable. I have several concerns with using the code; maybe you
> have the experience to point me in the right direction.
>
> The first concern is that my likelihood function is really slow (seconds).
> I have access to many cores, but each evaluation can only use one. So I'd
> like to enlist some parallelism in the MCMC algorithm. As written, nestle
> is purely sequential, but I can see several places parallelism is
> available. The first and easiest is when picking a new point to replace the
> worst: if this takes many tries, you could speculatively evaluate the
> function at many new candidate points and take the first acceptable one.
> Multinest is able to do this, and I can see how one might add it to the
> code here. The second possibility is suggested by your "update_interval"
> parameter. Until the family of ellipsoids is updated, all new points are
> being generated from the same distribution, so the evaluation of their
> likelihoods can be carried out in parallel. This guarantees at least a
> factor update_interval worth of parallelism, which might be worth it even
> for expensive likelihood evaluations. Implementation would maintain a list
> of N (~ number of cores) Futures representing evaluations drawn from the
> current set of ellipsoids; every time the code needs a new point it waits
> for the first Future to finish and gets the coordinates and log-likelihood
> from that, then creates another Future for later. When the ellipsoids need
> to be changed, all unused Futures can be cancelled. The result should be
> statistically identical to the current algorithm, though it sometimes uses
> extra RNG calls, so the actual call sequence won't be the same (and will
> depend on N but nothing else).
>
> The second concern is that I'm worried my problem is going to take forever
> with nested sampling. It's a somewhat high-dimensional problem - 20-30
> parameters - and the change in parameter volume from prior to posterior is
> staggering: while the prior is a bit fuzzy, our knowledge of (say) the
> inner orbital period goes from "about 1.6 days" to "1.629401788(5) days";
> many other parameters are similarly constrained. Since nested sampling
> relies on gradually shrinking ellipses from the entire space down to the
> target region, I worry that it will take a very large number of steps (if
> the ellipse's volume shrinks by a factor 1.2 each time, that's ~3000
> steps). This appears worryingly supported by a numerical experiment I am
> running with a fast likelihood function that nevertheless puts very tight
> constraints on the result.
>
> The third concern is about covariances. Of course ellipses are intended to
> enclose potentially very skinny error regions, but I ran into problems
> where my error region was so narrow that representing it with a covariance
> matrix ran into matrix numerical headaches. I have analytically
> marginalized out the worst offenders, but even the simple problem that my
> parameters can be constrained on very different scales - a sin i is known
> about a thousand times better than a cos i - can wreck matrix algorithms. I
> guess I have to try this and see whether problems arise.
>
> Currently I am working with emcee, which has its drawbacks, but can use
> parallelism (to evaluate likelihoods for many walkers at once) and is
> fairly robust against covariances (the point coordinates themselves are
> used to generate candidates as linear combinations). But since I'm trying
> to test a hypothesis - GR is better than not-GR - it sure would be nice to
> use a tool that supports hypothesis testing!
>
> Thanks,
> Anne
>
> On Tue, Sep 29, 2015 at 8:10 PM Kyle Barbary <kylebarbary at gmail.com>
> wrote:
>
>> Yes, possibly! Nestle currently implements the basic MultiNest method,
>> but doesn't implement later improvements such as importance reweighting or
>> polychord. I'm open to contributions and improvements. (But be mindful of
>> reading the MultiNest source code due to licensing issues!)
>>
>> Best,
>> -- Kyle
>>
>> On Tue, Sep 29, 2015 at 1:03 PM, Johann Cohen-Tanugi <
>> johann.cohentanugi at gmail.com> wrote:
>>
>>> likewise!
>>> Any prospect toward the polychord extension? See
>>> http://arxiv.org/abs/1506.00171v1
>>> cheers,
>>> Johann
>>>
>>>
>>> On 09/29/2015 10:30 AM, Wolfgang Kerzendorf wrote:
>>>
>>> HI Kyle,
>>>
>>> Very nice. I'll definitely have a look at that.
>>>
>>> Cheers,
>>>    Wolfgang
>>> --
>>> Dr. Wolfgang E Kerzendorf
>>> ESO Fellow
>>> European Southern Observatory
>>> Karl-Schwarzschild Str. 2, 85748
>>> Garching bei Muenchen, Germany
>>>
>>> On Tue, Sep 29, 2015 at 6:09 AM Kyle Barbary < <kylebarbary at gmail.com>
>>> kylebarbary at gmail.com> wrote:
>>>
>>>> Hi all,
>>>>
>>>> I'm pleased to announce the initial release of Nestle, a small Python
>>>> package for nested sampling. ("Nestle" rhymes with "wrestle".) Nested
>>>> sampling is a statistical technique for parameter estimation and model
>>>> comparison, commonly used in cosmology. We've been using it in the sncosmo
>>>> package and have found it to be a robust global optimizer in addition to
>>>> its more typically cited benefits.
>>>>
>>>> Nestle implements an algorithm similar to that used in the MultiNest
>>>> software, but in an open-source (MIT) licensed and easy-to-install (pure
>>>> Python) package. (It was written based only on the literature, not the
>>>> MultiNest source code.) In addition to this algorithm, Nestle also
>>>> implements the "classic" nested sampling algorithm and the "single
>>>> ellipsoid" algorithm.
>>>>
>>>> Nestle depends on only numpy and (optionally) scipy and supports both
>>>> Python 3 and Legacy Python (formerly known as Python 2).
>>>>
>>>> docs:  <http://kbarbary.github.io/nestle>
>>>> http://kbarbary.github.io/nestle
>>>> source:  <http://github.com/kbarbary/nestle>
>>>> http://github.com/kbarbary/nestle
>>>>
>>>> I'd appreciate any feedback on this initial release, particularly about
>>>> application to real-world problems and comparisons with results from
>>>> MultiNest. Thanks!
>>>>
>>>> - Kyle
>>>> _______________________________________________
>>>> AstroPy mailing list
>>>> AstroPy at scipy.org
>>>> https://mail.scipy.org/mailman/listinfo/astropy
>>>>
>>>
>>>
>>> _______________________________________________
>>> AstroPy mailing listAstroPy at scipy.orghttps://mail.scipy.org/mailman/listinfo/astropy
>>>
>>>
>>>
>>> _______________________________________________
>>> AstroPy mailing list
>>> AstroPy at scipy.org
>>> https://mail.scipy.org/mailman/listinfo/astropy
>>>
>>>
>> _______________________________________________
>> AstroPy mailing list
>> AstroPy at scipy.org
>> https://mail.scipy.org/mailman/listinfo/astropy
>>
>
> _______________________________________________
> AstroPy mailing list
> AstroPy at scipy.org
> https://mail.scipy.org/mailman/listinfo/astropy
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/astropy/attachments/20151008/81297646/attachment.html>