-4
$\begingroup$

I am using KDE with a modified metric for the distance. The PDF is as expected (see below: color is the probability and the dot is the point used to fit the KDE). But due to the new metric, I cannot use the usual sampling methods as they suppose a gaussian kernel with $(||\textbf{x}-\textbf{x}_i||)$. Here I have like something like $1/(||\textbf{x}-\textbf{x}_i||)$. So, the new kernel would looks like:

$$K(\textbf{x}-\textbf{x}_i) = \exp\left(\frac{-1}{||\textbf{x}-\textbf{x}_i||*h}\right)$$

This kernel does not integrate to 1 so I bound it in the unit hypercube and I want to sample in this hypercube.

  • How to generate new sample in this context?

From what I read (Find CDF from an estimated PDF (estimated by KDE), for instance), I have to come up with the multivariate inverse CDF.

  • Is there a simple way to do this?

For now I just use a hack which consists in:

  1. Sample the multivariate space and get PDF values
  2. Then I use these two information with a uniform random generator to give me a sample.

It works but will get the curse of dimensionality. Something like this: https://stackoverflow.com/q/25642599

Even the CDF in a multivariate space would be enough I guess as I would be able to use some fixed point for example to do the inverse.

Multivariate PDF with new distance metric

EDIT

Here is the result of this experiment. Color is the probability, black point is the point used for fitting the KDE and red points are samples generated using Metropolis-Hasting MCMC.

Sampling the KDE

$\endgroup$

closed as unclear what you're asking by Bernhard, gung Jun 27 '18 at 14:19

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ duplicate (?) stats.stackexchange.com/questions/56700/… $\endgroup$ – kjetil b halvorsen Jun 5 '18 at 14:44
  • 2
    $\begingroup$ I'm unable to see how the duplicate doesn't answer your question. Regardless of how you develop the KDE, by definition it represents a distributional estimate as a mixture of components; and sampling from that mixture is performed as you would from any mixture. That's why I'm probing for a better understanding of the role played by this distance. $\endgroup$ – whuber Jun 5 '18 at 21:13
  • 2
    $\begingroup$ When you use a non-Gaussian kernel, you sample from that kernel, that's all. Conceptually the difference is trivial, although in practice some kernels are harder to sample from than others. $\endgroup$ – whuber Jun 5 '18 at 21:25
  • 4
    $\begingroup$ What exactly is your question? You seem to have an estimation already. Is the question now how to draw from this estimated pdf in principle? Or is this "just" a technical question on how to do this in code? In what shape/program/toolkit do you generate the pdf? The principle has been laid out very nicely by @whuber, especially in his last linked article. $\endgroup$ – cherub Jun 11 '18 at 14:17
  • 3
    $\begingroup$ Possible duplicate of Random sample using KDE or bootstrapping $\endgroup$ – ironman Jun 16 '18 at 14:05
1
+100
$\begingroup$

Rejection sampling!

Suppose you've got a distribution $P$ that you'd like to sample from, but can't, and a proposal distribution $Q$ that is kinda like $P$ which you can sample from. Then if you can find a number $M$ which bounds $p(x)/q(x)$, to sample from $Q$:

  • Draw a sample $x$ from $P$
  • Calculate a threshold $T =\frac{p(x)}{Mq(x)}$
  • Draw a random number $t \sim U(0, 1)$.
  • If $t \leq T$, return $x$
  • Else go back to the beginning

You might have to bound the support of $P$ and $Q$ in order for $M$ to exist, and the speed of this whole process hinges on how close your proposal $Q$ is to $P$. In your case, a good proposal would be the uniform distribution over the unit cube.

If that isn't fast enough, the next places to look are at adaptive rejection sampling, Metropolis-Hastings MCMC, and then maybe an advanced MCMC scheme like NUTS.

$\endgroup$
  • $\begingroup$ This is actually the first answer which does answer my questions! Will try this right away :) $\endgroup$ – Y0da Jun 14 '18 at 10:42
1
$\begingroup$

UPDATED: If I understand your question correctly, you have generated a kernel density function from a set of data $x_1,...,x_n \in [0,1]^m$ using some non-standard kernel, and now that you have generated the "density", you want to be able to sample from this in a simple way. You are using a Gaussian kernel, but with an inverse substitution of the distance; your kernel function is:

$$K(x_i-x) \propto \exp \Bigg( -\frac{\lambda}{2 (x_i-x)^2} \Bigg) \quad \text{for all }x \in [0,1]^m.$$


Sampling from a KDE: For a set of data $x_1,...,x_n$ and a (un-normalised) kernel function $K$ the kernel density estimate (KDE) $\hat{p}$ is given by:

$$\hat{p}(x) \propto \frac{1}{n} \sum_{i=1}^n K(x_i-x).$$

(This might also have some other estimated parameters for the kernel, like a bandwidth, but that does not affect this question.) Since the KDE is literally just a uniform mixture distribution, using kernels placed at the data values, the simplest way to sample from this density is via the following two-step process:

  • Step 1: Generate a random value $i \sim \text{U}\{1, ..., n\}$ representing a data point;

  • Step 2: Now sample from the density with kernel $K$ centered at $x_i$. This can be done by a variety of methods, such as rejection sampling, Metropolis-Hastings, or transformation methods.

It is trivial to show that this gives you a random value from the density $\hat{p}$. This is because the latter is just a mixture distribution of the kernels, centered at the data points. This means that the problem of generating a random variable from a KDE degenerates down to the problem of generating a random variable from the chosen kernel. In you case, I would recommend using the present algorithm, with rejection sampling to sample from your kernel.


$\endgroup$
  • $\begingroup$ As I explained in the comments, I do not see how to "sample" from the Kernel in this context. Ok for exemple let say I have a Gaussian Kernel with the following metric: $\frac{1}{x_i - x}$ instead of $(x_i - x)$ and the multivariate distribution is totally unknown. $\endgroup$ – Y0da Jun 14 '18 at 8:11
  • 2
    $\begingroup$ As I said in the answer, if you give full details of your kernel and explain how this is linked to your metric, I will try to make sense of this. With sporadic details spread across comments, I don't know what you're doing. $\endgroup$ – Ben Jun 14 '18 at 10:54
  • $\begingroup$ Well, the explanation is just above: Gaussian Kernel with an inverted distance measure. That is all. $\endgroup$ – Y0da Jun 14 '18 at 13:01
  • 1
    $\begingroup$ Just wanted to say this answer is also perfect. I cannot accept 2 but gave a +1. Thx for the maths and details, it really helps. $\endgroup$ – Y0da Jun 19 '18 at 17:32

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