2
$\begingroup$

There's many good ways to learn a distribution $p_X$ of an r.v. $X$ over $k$ symbols given many i.i.d. samples $X_1,\ldots, X_n$. The simplest is to use the sample relative frequencies $\hat{f}_X$ as your estimate of $p_X$, which is a reasonably alright way to learn the distribution.

But what if you're not sure about the samples, and are instead given a distribution for each sample, i.e. you're told $p_{X_1}, \ldots, p_{X_n}$. This might come up if each of the samples was measured noisily. You can assume the noise involved is independent and possibly differently distributed each time. How would you learn $p_X$ in this case? Bonus points if the procedure is efficient.

Things to note about the answer:

  • in the case that the $p_{X_i}$'s are a just a deltas on particular symbols (i.e. perfect samples), the procedure should gracefully reduce to the case of perfect samples.
  • as $n\to\infty$, the distribution you learn should go to $p_X$.

For my case, I actually want to find a solution to this problem in the continuous probability case (I'm starting with discrete so I can get somewhere). In particular, I want to find an analog to KDE. Here's a specific example problem: you want to learn a distribution using non-parametric methods. You're given 3 noisy length measurements from 3 different tools that make normally distributed errors: 4cm from a tool with $\sigma^2=2$, 5cm from a tool with $\sigma^2=3$, and 2cm from a tool with $\sigma^2=10$. What's your guess for what the distribution looks like? If these were exact samples, I would just plop a gaussian with appropriate bandwidth at each sample, but how should I take into account the distributions of each of the samples?

By the way, as I've been thinking about this problem for a while now, I suspect it may be ill-posed as is, and may require additional conditions on the "noise" producing the distributions on the imperfect samples. Tell me what you think.

Lastly, I don't need a proof really, just a procedure (that could simply be a heuristic) that seems half-decent and doesn't have any counterexamples to it working in the limit.

Oh, and I asked this question on mathoverflow, but now I realize this is probably the better place to ask. Hope this is alright.

$\endgroup$

closed as unclear what you're asking by kjetil b halvorsen, Sycorax, Michael Chernick, Peter Flom Jul 23 '18 at 10:53

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.

  • 1
    $\begingroup$ What does it mean to be "told" $p_{X_1}, \ldots , p_{X_n}$? If these depend on $X_i$ then what is $p_X$? It seems you just mean to estimate the distribution of $X_i$ using realizations of $X_i + \epsilon_i$ but I'm not sure. $\endgroup$ – dsaxton Mar 1 '16 at 1:36
  • 1
    $\begingroup$ There's several reasons you could be given distributions on samples instead of just samples. One, as you said, could be because there's additive noise on the samples, and you have models for the distribution of the noise. Another context could be each sample itself requiring its own estimation problem, leaving a posterior distribution on what you think each sample is. One more last context is that you have $n$ different expert statisticians each tell you a distribution on what they think their sample $X_i$ is, and you trust that these statisticians are telling you "good", not spurious, dists. $\endgroup$ – chausies Mar 1 '16 at 5:43
  • $\begingroup$ Again, what do you mean by being "given" these distributions? Do we know what they are? If you only mean that each realization has its own distribution then it's not clear what it is you want to estimate. $\endgroup$ – dsaxton Mar 1 '16 at 14:46
  • $\begingroup$ @dsaxton Of course the objective is to learn the dist on $X$. Normally, you are told exactly the samples $X_1, \ldots, X_n$. But in this case, I'm saying you are told precisely some dists on those samples, i.e. $p_{X_1}, \ldots, p_{X_n}$, because you're not sure exactly what those samples are. Here's a simple example problem to clear this up: texpaste.com/n/rulli0d . Note that in the sample problem, it focuses on the particular case that the dists on the samples arise from additive noise, whereas in general, the dists on samples could arise from a variety of places. $\endgroup$ – chausies Mar 1 '16 at 21:11
  • $\begingroup$ This still seems very vague and ill-posed. Suppose I tell you every distribution is normal$(0, \sigma^2)$, but only after I've added some unspecified amount of noise. It's clearly impossible to infer what the original distribution was. $\endgroup$ – dsaxton Mar 1 '16 at 21:18
1
$\begingroup$

Density estimation in the standard case: A standard technique for estimating distributions from observations is the kernel density estimator (KDE), which reduces down to the empirical distribution if your kernel is a Dirac delta function. A broader continuous kernel centred at the observation value is usually used to give a continuous density over the support. For the standard sampling problem you observe data $\mathbf{x} = (x_1,...,x_n)$ and you estimate the density as:

$$\hat{p}(x | \mathbf{x}) = \frac{1}{n \delta} \sum_{i=1}^n K \Big( \frac{x-x_i}{\delta} \Big),$$

where $K$ is a density centred at zero and $\delta$ is a bandwidth parameter that is usually estimated from the data (e.g., by MLE). The KDE is equivalent to estimating the density function using an empirical estimate of the characteristic function, with a damping function to prevent divergence. (The kernel in the KDE is the Fourier transform of the divergence function.)

Extension to data with errors-in-variables: If you observe densities $\mathbf{p} = (p_1,...,p_n)$ in lieu of exact observations, the natural generalisation of the KDE is to replace the kernel at the observed value with its expectation under the observed densities. This generalisation gives:

$$\hat{p}(x | \mathbf{p}) = \frac{1}{n \delta} \sum_{i=1}^n \mathbb{E} \Big[ K \Big( \frac{x-X_i}{\delta} \Big) \Big] = \frac{1}{n \delta} \sum_{i=1}^n \int \limits_\mathcal{X} K \Big( \frac{x-x_i}{\delta} \Big) p_i(x_i) dx_i.$$

Since expectation is a linear operator, we have $\hat{p}(x | \mathbf{p}) = \mathbb{E} (\hat{p}(x | \mathbf{X})) $, which is the expected KDE under the random observations $\mathbf{X} \sim \text{IID }\mathbf{p}$. So all we are really doing in this extension is finding the expected KDE given a set of densities for the data.

Convergence: The standard KDE is used in a context where you have an underlying sequence of exchangeable random variables, so you have IID data with a common distribution. In this context, the KDE is known to be uniformly convergent to the true distribution under mild assumptions (see e.g., Jiang 2017). When you extend this to replace the observations with individual densities, you no longer have an exchangeable sequence of observations, and so you will need to specify what you mean by the underlying "true" distribution, and you will also need to specify the relationships of the "true" distribution with the observed densities for the observations (@dsaxton points out this limitation in your question in the comments). Taking the "true" distribution to be an average of the sequence of observable densities would be a natural extension, and it should allow you to get convergence results similar to the standard case. This would be a larger analysis, and it is beyond the scope of what I can do in a short answer like this.

$\endgroup$

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