3
$\begingroup$

I am using the principle of maximum entropy to fit a density to a given set of samples. I want to generate new set of samples from the approximated density. Is there any way to draw samples from a density obtained by maximum entropy approach?

$\endgroup$
2
  • $\begingroup$ When you "fit" a density, how is the output expressed? $\endgroup$
    – whuber
    Jan 11, 2012 at 13:18
  • $\begingroup$ It would help to say more about those "feature functions." If, for instance, they form a mixture distribution, then the sampling process is reduced to choosing one of those functions randomly and then sampling from it. This could be hugely more efficient than attempting to sample from the density using, say, rejection sampling. $\endgroup$
    – whuber
    Jan 13, 2012 at 14:27

2 Answers 2

1
$\begingroup$

Construct a piecewise probability distribution curve to fit the data and then use rejection sampling (e.g. see Ziggurat Algorithm to see how to implement rejection sampling).

$\endgroup$
2
  • $\begingroup$ The output is expressed in terms of feature functions defined over the space of the samples and their corresponding coefficients. Locster could you please explain a little bit more. What do you mean by piecewise probability distribution curve to the data? Note that my data is multi-dimenstional. $\endgroup$
    – Beh
    Jan 11, 2012 at 18:53
  • $\begingroup$ Ok so you have a set of functions that define the [relative] density for any given point in the space. For rejection sampling to work you will need the densities to be normalized (for the purposes of this explanation let's say we determine the maximum density observed across the space). So my suggestion then is to generate coordinates in the space randomly (and uniformly distributed), for each generated point generate another uniform random value V in the range [0, maxDensity]. If V is <= the density described by your function then accept the point as a valid sample, otherwise reject it. $\endgroup$
    – redcalx
    Jan 13, 2012 at 11:50
1
$\begingroup$

As Iocster said, you can use rejection sampling if you have an appropriate proposal density. Here is another approach that is a rather computationally intensive answer to the question that you can use for any density estimate, regardless of whether it was fit by maximum entropy:

If you have an estimated density, $\hat{f}$, you can get an estimated cumulative distribution function

$$ \hat{F}(y) = \int_{-\infty}^{y} \hat{f}(x) dx $$

this integral can be estimated numerically using, for example, the integrate() function in R. Next, you can numerically estimate the inverse cumulative distribution function (i.e. the quantile function)

$$ \hat{Q}(x) = \hat{F}^{-1}(x) = \inf \{ y : \hat{F}(y) = x \} $$

Assuming $\hat{F}$ is monotonically increasing, the intermediate value theorem applies, and $Q(x)$ can be calculate using any standard root finding algorithm. Once you have $\hat{Q}$, you can apply Inverse Transform Sampling, which says $\hat{Q}(U)$, where $U \sim {\rm Uniform}(0,1)$, is a draw from a distribution with CDF $\hat{F}$ (and therefore density $\hat{f}$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.