4
$\begingroup$

I have two histograms with equal bin size that lie in the same general range. You can imagine them looking like this example I've borrowed from https://mpatacchiola.github.io/blog/2016/11/12/the-simplest-classifier-histogram-intersection.html: two histograms

Let's say, the blue-ish histogram corresponds to true examples, while the red-ish histogram corresponds to false examples. I want to find a threshold that can be used to predict true examples or false examples in the future. If you want, this is a machine learning problem where I want to find a binary classifier for one-dimensional data.

Obviously, a naive and straight-forward choice would be to find the local minimum in the middle of the two histograms and cut right through it. How can this be solved efficiently? My first idea would be to fit two Gaussians and intersect them.

The whole thing gets more interesting if you additionally seek to fix the false positive rate (corresponding to the red-ish bins located to the right of the threshold). How can the FPR be put into the equation?

$\endgroup$
2
  • $\begingroup$ Note that for question 1, if you think the data is a gaussian mixture you still have to fit the mixing fraction as well as the individual gaussians (i.e. your histograms are un-normalized counts, and their totals need not be equal). For question 2, you would use the CDFs (either cumsum the histograms, or take the gaussian CDFs + their mixing fractons). $\endgroup$
    – GeoMatt22
    Commented Apr 25, 2017 at 21:31
  • 1
    $\begingroup$ If you think both groups are Gaussian, this becomes quadratic discriminant analysis; if you think their variance / covariance matrix (in higher dimensions) is the same, then it's linear discriminant analysis. Many posts on site discuss these and related techniques. $\endgroup$
    – Glen_b
    Commented Apr 25, 2017 at 22:37

4 Answers 4

3
$\begingroup$

Not exactly what the original question asked for...

import math
import numpy as np
import scipy.special
import scipy.stats
import matplotlib.pyplot as plt

mu_1 = -4
mu_2 = 4
sigma = 2

t = np.linspace(-10,10,1000)

# https://mathworld.wolfram.com/NormalDistribution.html
# See formulae 8,9,10 in
# Weisstein, Eric W. "Normal Distribution." 
# From MathWorld--A Wolfram Web Resource. 
# https://mathworld.wolfram.com/NormalDistribution.html
def area_under_gaussian_at_left(t,mu,sigma):
    a = t-mu
    b = math.sqrt(2)*sigma
    return .5*(1+scipy.special.erf(a/b))

def area_under_gaussian_at_right(t,mu,sigma):
    return 1-area_under_gaussian_at_left(t,mu,sigma)

false_positive = area_under_gaussian_at_right(t,mu_1,sigma)
false_negative = area_under_gaussian_at_left(t,mu_2,sigma)

threshold = t[np.argmin(false_negative+false_positive)]

print('Threshold minimizing the sum of false positives and false negatives: {0}'.format(threshold))

fig, ax = plt.subplots(1)
ax.plot(t,scipy.stats.norm.pdf(t,mu_2,sigma),
t,scipy.stats.norm.pdf(t,mu_1,sigma)
)
ax.axvline(threshold,color='black')
ax.set_title('The black vertical line is the threshold that minimizes\nthe sum of false positives and negatives: {0}'.format(threshold))
ax.set_xlabel('feature')
ax.set_ylabel('Probability density')
ax.legend(['class 1','class 2'],loc='upper right')
fig.savefig('far_vs_near.png',bbox_inches='tight')

fig, ax = plt.subplots(1)
ax.plot(
t,false_positive,
t,false_negative,
t,false_negative+false_positive
)
ax.set_xlabel('Threshold value for feature')
ax.set_ylabel('Proportion of falses (1 means 100%)')
ax.legend(['False positives','False negatives','False negatives plus false positives'],loc='upper right')
fig.savefig('falses.png',bbox_inches='tight')

enter image description here enter image description here

$\endgroup$
1
$\begingroup$

It's actually more of a problem in Statistics.

A little bit of theory:

Consider the following formulation using hypothesis testing, which you're hopefully familiar with.

In the general setting, we observe examples $x_{1},...,x_{m}\sim f\left(x\right)$ and we have two "candidates" for the density function $f$ which the examples came from: $f_1$ and $f_2$. In the language of hypothesis testing, we have $H_{1}$ and $H_{2}$ and we want to distinguish between them.

For a simple case, which suits your scenario better, consider the case of a single example (the case for a general $n$ is very similar but it's a little bit different than what you described since it assumes all examples come from either $f_1$ or $f_2$).

Given an example $x$, we would like to choose the distribution that is most probable:

$prediction = argmax_{i=1,2}\mathbb{P}\left(H_{i}\mid x\right)$

Equivalently, we can choose $H_1$ $\iff$ $ \frac{\mathbb{P}\left(H_{1}\mid x\right)}{\mathbb{P}\left(H_{2}\mid x\right)} > 1$.

Using Bayes theorem to simplify the above expression,

$ \frac{\mathbb{P}\left(H_{1}\mid x\right)}{\mathbb{P}\left(H_{2}\mid x\right)} = \frac{f_{1}\left(x\right)}{f_{2}\left(x\right)} \cdot \frac{\mathbb{P}\left(H_{1}\right)}{\mathbb{P}\left(H_{2}\right)}$

Taking logarithm of both sides gives a nice decomposition (this step is not mandatory, but usually done for further analysis of the general case):

$\log\frac{\mathbb{P}\left(H_{1}\mid x\right)}{\mathbb{P}\left(H_{2}\mid x\right)}=\log \frac{f_{1}\left(x\right)}{f_{2}\left(x\right)} + \log \frac{\mathbb{P}\left(H_{1}\right)}{\mathbb{P}\left(H_{2}\right)}$

$\log \frac{\mathbb{P}\left(H_{1}\right)}{\mathbb{P}\left(H_{2}\right)}$ is known as the log likelihood ratio; it's fixed and signifies the initial inclination (without seeing any data) to choosing $H_1$; $\log \frac{f_{1}\left(x\right)}{f_{2}\left(x\right)}$ can therefore be seen as the additional information that example $x$ gave you regarding choosing $H_1$.

(In the general case, we can go on to show that - as one would anticipate - when you see more examples, the probability of choosing the correct density goes to 1.)

Practical Usage:

  1. Use the information you have (histogram, etc) to fit a density estimator for your two candidate functions. This can be done in two lines of code in Python, R, etc.

  2. Predict: $\hat y = argmax_{i=1,2}\hat f_{i}(x)$

$\endgroup$
1
  • $\begingroup$ Thank you for this detailed elaboration, which was straight-forward and quite understandable. However, I have to admit that I am still not able to follow Step 2 of the suggested practical usage. Wouldn't that mean that y is located where the maximum of both distributions appears? This would directly contradict my naive understanding that we would like to find the threshold somewhere in the gap between both distributions... $\endgroup$
    – Michael
    Commented Apr 28, 2017 at 9:05
1
$\begingroup$

You could analyze this graphically with a ROC curve like the image below.

ROC curve

The image shows that there is not a single best point for the threshold. You can have go for a better true positive rate, but this comes at the cost of an increase in the false positive rate.

The optimal threshold will eventually depend on some quantitative expression comparing the pros and cons as a function of the threshold. Reducing the threshold will improve the sensitivity which is beneficial but at some point, the costs of the decreased accuracy will weigh stronger. Where this point is, depends on the particular function weighing the costs and benefits of the particular case (there is not a general answer).

If you have an expression for the costs/benefits of the wrong/correct classification (and also an estimate of the distribution of true/false cases among the population), then you can solve it computationally and potentially you can use some estimate of a parametric distribution but you could also use the empirical distribution.

$\endgroup$
0
$\begingroup$

We can re-frame this problem in a different way. It is a very common problem to find a threshold to distinguish two classes in a bimodal distribution like this. Even in image processing and computer vision it is a common problem to find a threshold in a bimodal distribution to make a grayscale image to a binary image.

For these kinds of problem, one of the prominent ways to find a single threshold is to use Otsu Method. This method has a limitation:

Limitations: Otsu's method performs well when the histogram has a bimodal distribution with a deep and sharp valley between the two peaks.

But as your histogram is clearly a bimodal distribution, so it is not an issue for you. You can find Otsu Method and various other thresholding techniques here: OpenCV | Image Thresholding.

$\endgroup$
1
  • $\begingroup$ Everyone is making this a difficult problem. It is a simple problem once it is recognized that the most useful output is probability of group membership. Use a direct probability model to get that, e.g., binary logistic regression. And avoid thresholds at all costs since these hide close calls/gray zones. $\endgroup$ Commented Dec 16, 2021 at 14:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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