3
$\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?

Improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – chausies Feb 27 '16 at 3:44
  • $\begingroup$ You definitely need some assumption on how each $p_{X_i}$ relates to the true distribution $p_{X}$. At least you'd hope that $\mathbb{E} p_{X_i} = p_{X}$. But in this case just averaging the $p_{X_i}$ is probably a fine strategy, right? $\endgroup$ – usul Feb 27 '16 at 14:58
  • $\begingroup$ But you can't dare to hope that $\mathbb{E}\left(p_{X_i}\right)=p_X$, right? For example, if $X_1$ is a sample from $X$ measured with an instrument with some additive gaussian noise, then $\mathbb{E}\left(p_{X_1}\right)$ will be $p_X$ convolved with a gaussian. Similarly, if $X_2$ is measured with some other type of noise, its expected distribution will be $p_X$ convolved with something else, etc.. So averaging won't really get you the right thing. There's some..."impedance matching" step that's missing before averaging, I think.... $\endgroup$ – chausies Feb 28 '16 at 20:24
  • $\begingroup$ To make sure I understand, $p_{X_i}$ is a probability distribution over the $k$ symbols, right? And this probability distribution is itself drawn randomly somehow? $\endgroup$ – usul Mar 1 '16 at 0:57
  • $\begingroup$ $p_{X_i}$ is a distribution over the $k$ symbols, and it's been given to you from some third party I'd like to assume nothing about. It could be given to you by different experts, it could be found through trying to estimate posteriors on the samples, or it could come from having a model on the additive noise when measuring the samples. If this can't be solved in this kind of generality, then you can make any assumptions on the $p_{X_i}$'s you need. I'm hoping that the only assumption you need, however, is just that the $p_{X_i}$'s are "good" and not spurious or misleading. $\endgroup$ – chausies Mar 1 '16 at 6:14
1
$\begingroup$

The exact results really depend on all the particularities of your model (how do you allow errors, can you ask for specific samples, the nature of the noise, etc, etc). It may be a feasible task or not; [0] classifies a number of such models.

In [1], a framework is given working with arbitrary noise.

[0] Shahin Jabbari, Robert C. Holte, Sandra Zilles, "PAC-Learning with General Class Noise Models"

[1] Adam Tauman Kalai, Varun Kanade, "Potential-Based Agnostic Boosting"

Improve this answer
$\endgroup$

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.