8

Given only observations of a binary signal perturbed by Gaussian noise with unknown prior information, how can I estimate the optimal decision threshold?

( No, this is not a homework question)

Specifically, I am think about the following model: $Y$ is a two-state $(H_0,H_1)$ Random variable :

  • $P(Y|H_0) \sim \mathcal N(\mu_0,\sigma)$
  • $P(Y|H_1) \sim \mathcal N(\mu_1,\sigma),\quad \mu_0 < \mu_1$
  • $P(H_0) = \pi_0$
  • $P(H_1) = 1-\pi_0$

with unknown parameters: $\mu_0, \mu_1, \sigma, \pi_0$.

The Maximum a Posteriori Log-likelihood threshold could be computed from those parameters if I knew them. I was originally thinking about how to estimate the parameters first in order to get to the threshold $Y_t$. But I'm thinking it may be more robust to directly estimate $Y_t$.

Thoughts: Normalizing the observations (subtracting the sample mean and dividing by standard deviation) reduces the parameter space into 2 dimensions: $\pi_0$ and $\frac \sigma{\mu_1-\mu_0}$.

Royi
  • 19,608
  • 4
  • 197
  • 238
Mark Borgerding
  • 3,020
  • 19
  • 26
  • This problem would be a lot easier if you could assume that Pi0 was 0.5. :-) – Jim Clay Apr 07 '12 at 18:53
  • Might this question be somewhat related to these: http://stackoverflow.com/questions/1504378/fitting-a-bimodal-distribution-to-a-set-of-values or http://stackoverflow.com/questions/5451089/bimodal-distribution-characterization-algorithm – hotpaw2 Apr 10 '12 at 09:42
  • Is a training sequence of observations available for estimating the means, variances, etc.? Or are you simply given a data sequence in which some values are from $H_0$ and some from $H_1$ but you don't know which is which? – Dilip Sarwate Jun 24 '12 at 19:03

3 Answers3

6

My intuition is that it would be difficult to derive the right decision threshold you expect to find:

$$\tau = \frac{1}{2}\left(\mu_0 + \mu_1\right) - \frac{\sigma^2}{\lVert\mu_0 - \mu_1\rVert^2} \log \frac{\pi}{1 - \pi}\left(\mu_0 - \mu_1\right)$$

From the global statistics you are considering (sample mean: $\pi \mu_0 + (1 - \pi) \mu_1$ ; standard deviation: more complex expression but I doubt it would involve a log).

I would approach the problem this way:

  1. If the assumption that $\sigma$ is small can be made

    I'm mentioning that, because keep in mind that the decision threshold is affected by $\pi$ only if $\sigma$ is sufficiently high to allow both classes to overlap. If the $\mu$s are distant by more than a few $\sigma$, class prior probabilities have nothing to say in the decision process!

    • Run k-means on your observations ($\sigma$ is small and is shared by both classes, so k-means is in this case EM for the mixture model). If you just want to binarize these observations and no other data, you can stop here.
    • If you have new observations to binarize, and you know they are generated by the same process, you can use the class centroids found by k-means on your training data as estimates of $\mu$, and use the middle as a decision threshold.

  2. If no assumption about $\sigma$ can be made

    • Run the EM algorithm (with pooled, diagonal covariance) on your training data. Use the inferred "soft class membership" variables to binarize your observations.
    • Compute the decision threshold $\tau$ from the parameters given by EM to binarize new data generated by the same process.
Gilles
  • 3,386
  • 3
  • 21
  • 28
pichenettes
  • 19,413
  • 1
  • 50
  • 69
2

To summarize you have two distributions with unknown parameters and a measurement which may have originated from either stochastic process. This is typically referred to as a data association problem and it is very common, and widely studied, within the tracking community. You might consider using a Probability Data Association Filter (PDAF) or Multi-Hypothesis Tracking (MHT) algorithm. This should provide you with estimates of the mean and variance for each distribution.
Alternatively, since your noise is white and Gaussian, the ML, MAP and MMSE are all equivalent and can be found by minimizing the mean squared error (cost function), as is effectively described by the previous response. I would use a dynamic programming approach to find the minimum of the cost function. This should be less complex (computationally) than the previously described EM/clustering methods. One more comment: the PDAF is recursive. Given the simple signal model it should work very effectively and at what I expect is a fraction of the computational complexity of the EM algorithm. Good luck, -B

Brant Jameson
  • 21
  • 1
1

There is an algorithm from the mid 1980s by Kittler and Illingworth called "Minimum Error Thresholding" that solves this problem for Gaussian distributions. Recently Mike Titterington (University of Glasgow) and J-H Xue (now at UCL) have put this in more formal statistics framework, see their joint journal publications.

helpfulHougher
  • 11
  • 1