6
$\begingroup$

I am interested in new generating samples to approximate some unknown distribution X, where each new sample is a real-valued vector.

The purpose it to be able to create a new (arbitrary large) stream of new samples from this approximate distribution that will be distributed in the same way, or as close as possible, to the original sampled data.

Some additional points:

  • I will have a large number of samples from X, e.g. in the millions, and possibly too large to fit in memory.
  • The probability distribution X could be either discrete or continuous. It is likely to be multi-modal. Very extreme values are unlikely.
  • If needed I can normalise the data or scale it to fit some bounds.
  • Dimensionality of each sample is reasonably large (say 1000)
  • Samples can be assumed to be independent
  • Samples can be assumed to be almost identically distributed, although they represent a time series so it is possible that the underlying distribution may be changing very slowly. This change is unlikely to be large enough to
  • Ideally I'd like the algorithm to be online, i.e. the model distribution can be updated incrementally as new real samples become available.

What is the best algorithm to "learn" how to generate new samples with a probability distribution that approximates X as closely as possible?

$\endgroup$
  • $\begingroup$ How large a number of samples do you have, roughly? Millions? Billions? $10^{1000}$? $\endgroup$ – onestop Nov 21 '11 at 10:47
  • $\begingroup$ Millions probably (I'm developing it for external clients so can't be totally certain in advance, however I know many clients have data sets at least that big). Question updated. $\endgroup$ – mikera Nov 21 '11 at 10:58
  • 2
    $\begingroup$ To get useful, relevant answers, it will help to specify two additional things: (1) anything you are willing to assume about the distribution of $X$ and (2) the reason for generating the samples, so that we will share your understanding of what makes a good approximation to the distribution. For example, a good approximation for making decisions about extreme values of the distribution may be very different than a good approximation for making decisions about average values. $\endgroup$ – whuber Nov 21 '11 at 14:28
  • $\begingroup$ Thanks for the comments, I've updated the question. The purpose is to be able to generate new samples on demand with a distribution as close as possible to the distribution that produced the original samples. $\endgroup$ – mikera Nov 25 '11 at 1:14
3
$\begingroup$

Basically, it sounds like you want to bootstrap your data: http://en.wikipedia.org/wiki/Bootstrapping_%28statistics%29

A good (and relatively cheap) reference is: "Bootstrap Methods and Their Applications" by A. C. Davison and D. V. Hinkley (1997, CUP).

which has an associated R package, "boot".

BUT... there's a lot that can go wrong in bootstrapping and it's very easy to get misleading results if you don't know what you're doing (which, to be blunt, sounds likely). It would help a lot if you explained exactly what the problem is that you're trying to solve.

$\endgroup$
  • $\begingroup$ thanks for the links! I'm not sure it solves the problem though, as it looks to me that bootstrapping only produces new samples that were in the original data set (or perhaps with some added noise). Can bootstrapping help with creating completely new samples? $\endgroup$ – mikera Nov 25 '11 at 1:21
  • $\begingroup$ The bootstrap, and really any approach, makes completely new samples from a distribution that approximates the original distribution. Say we knew that the original data come from a normal dist. with unknown mean and variance. We could estimate the mean and variance (call the estimates $\bar x$ and $s^2$) and then make random draws from the $N(\bar x, s^2)$ distribution (this is a parametric bootstrap). This isn't exactly the original distribution but will get arbitrarily close to the original dist. as the number of observations gets larger. Nonparametric bootstraps behave similarly. @mikera $\endgroup$ – Gray Nov 28 '11 at 22:35
0
$\begingroup$

I have recently faced a similar problem in my research. I did not generate a new function to approximate X. The solution I applied is the following (I used MATLAB to program it):

Obtain the histogram for the distribution of your samples (with as many bins as you can, within reasonable limits) and the cumulative density function.

On the vertical axis of your CDF there are values that range between 0 and 1. Randomly generate numbers between 0 and 1; track them down to the horizontal axis; take the value of the histogram at that bin and you have a new generated value for your new samples.

The whole point of this method is that from the generation of (almost) random equiprobable numbers, you obtain a non-equiprobable distribution that is in accord with your first distribution X.

$\endgroup$
  • $\begingroup$ that doesn't sound like it's gonna scale to high dimension easily. $\endgroup$ – Memming Aug 5 '13 at 18:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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