What can be said about Precision-Recall when combining binary classifiers using unanimous voting?

Question

Suppose I combine binary classifiers $A$ and $B$, having precisions $Pr_A$ and $Pr_B$ respectively, where $Pr = \frac{True Positives}{True Positives + False Positives}$, and recall $Re_A$ and $Re_B$ respectively, where $Re = \frac{True Positives}{True Positives + False Negatives}$, yielding classifier $C$ with precision $Pr_C$ and recall $Re_C$.

Each training instance $i$ consists of an input vector $v_i$ with $k$ dimensions and an output label $y_i$.

Both classifiers are trained using the same training instances, and tested using the same test instances.

We combine both classifiers using unanimous voting, where $C$ predicts the label $0$ if either $A$ or $B$ predict $0$, else it predicts $1$. $0$ = negative example, $1$ = positive example.

What can be said about the Precision-Recall of $C$ when compared to $A$ and $B$?

Answer 1

Since $C$ only classifies instances as positive when $A,B$ agree, $TP_C \le TP_A$ and $TP_C \le TP_B$. ($TP$ meaning the count of true positives for a classifier.) An analogous pair of inequalities holds for $FP_C$, e.g $FP_C \le FP_A$.

Applying that fact:

$$TP_C \le TP_A \\ \frac{TP_C}{TP_C + FN_C} \le \frac{TP_A}{TP_C + FN_C} = \frac{TP_A}{TP_A + FN_A}$$

(The equality at right is true because the sum represents the total positive instances, and this sum is the same across classifiers.)

Since a similar inequality holds for $B$, we've shown that the recall is upper-bounded by the lesser of $Re_A, Re_B$. This should make intuitive sense: Recall captures how many positives we "caught," and a conjunction of classifiers can only catch, at most, as many as the lower-recall of the two classifiers.

Building the same equations for precision gives you much less to say. We know

$$ TP_C \le TP_A \\ TP_C \le TP_B \\ FP_C \le FP_A \\FP_C \le FP_B $$

and want to show something about $\frac{TP_C}{TP_C + FP_C}$. $FP_C = 0$ and $TP_C=0$ will both satisfy these equations—regardless of the metrics for the base classifiers—and yield respective precisions of $1,0$.

This too makes intuitive sense: If the second classifier classifies none of the first classifiers false positives, the conjunction will have no false positives. If it classifies none of the first classifier's true positives, it will have no true positives. In sum, without more information or assumptions, it doesn't seem to me that much can be said about precision of the conjunction.

Conditional probabilities

If you'd like to interpret precision as an estimate of $p(x_+|a_+, b_+)$, let's start by decomposing that probability, per Bayes' rule:

$$ p(x_+|a_+, b_+) = \frac{p(a_+, b_+ | x_+)p(x_+)}{p(a_+, b_+)} = \frac{p(a_+, b_+ | x_+)p(x_+)}{p(a_+, b_+|x_+)p(x_+) + p(a_+, b_+|x_-)p(x_-)} $$

This alone should lend a few helpful intuitions:

• Precision grows with the prior probability of $x_+$. Sensible, since it's easier to be right when more instances are positive.
• It grows as $p(a_+,b_+|x_-)$ declines, confirming the intuition from the equalities above.

In other words, precision of the conjunction is best when the classifiers are differently incorrect, i.e. their incorrect classifications are different instances. (This should sound like a violation of conditional independence.)

But, let's assume conditional independence:

$$ p(x_+|a_+, b_+) = \frac{p(a_+|x_+)p(b_+ | x_+)p(x_+)}{p(a_+|x_+)p( b_+|x_+)p(x_+) + p(a_+|x_-)p( b_+|x_-)p(x_-)} $$

Then compare to either of the classifiers:

$$\frac{p(a_+|x_+)p(b_+ | x_+)}{p(a_+|x_+)p( b_+|x_+)p(x_+) + p(a_+|x_-)p( b_+|x_-)p(x_-)} \stackrel{?}{\ge} \frac{p(a_+|x_+)}{p(a_+|x_+)p(x_+) + p(a_+|x_-)p(x_-)} \\ p(b_+|x_+) \stackrel{?}{\ge} p(b_+|x_-)$$

Naturally, to outperform both classifiers, this would have to be true of both. (By the way, the false discovery rate would estimate the quantity at right.)

But remember that this inequality applies to the unobservable distributions: Applying it to the analogous estimates of any given pair of classifiers doesn't guarantee improved precision over a given dataset.

Answer 2

UPDATE: My simulation code below disagrees with my analytical expectations only with respect to the positives rate (which affects the precision calculation) when models $A$ and $B$ are both better than random chance guessing. I think this has to do with violating the assumption that $A$ and $B$ are independent. I think if the assumptions are honoured, my predictions are correct.

DISCLAIMER: while this looks good to me, I have a high brain fart rate; you need to scrutinize.

---

Summary

If:

• The classifiers/models $A$ and $B$ are independent,
• And if the probability that there exists a positive test problem in the evaluation set is known (which is usually $1/2$ for a binary classification task in most evaluation sets, unless you deal with imbalanced evaluation datasets, then it's something else),

Then, given how the unanimous ensemble is defined, you can find both:

• $P_{A,B}$ (the precision of the ensemble.
• $R_{A,B}$ (the recall of the ensemble).

Proof

Let $x$ be some testing sample, and let $c$ be some classifier/model (could be $A$ or $B$).

So the precision $P_c$ of classifier $c$ is essentially the empirically measured probability $\Pr_c(\text{$x$ is pos}|\text{$x$ pred pos})$

And the recall $R_c$ of classifier $c$ is essentially the empirically measured probability $\Pr_c(\text{$x$ pred pos}|\text{$x$ is pos})$

Let's assume that $\Pr(\text{$x$ is pos})$ is known. Usually, this is $1/2$ in a binary classification dataset (unless one wants to deal with the class imbalance problem).

By chaining rule we know that: \begin{equation}\begin{split} \Pr_c(\text{$x$ is pos, $x$ pred pos}) &= \Pr(\text{$x$ is pos}) \Pr_c(\text{$x$ pred pos}|\text{$x$ is pos})\\ &= \Pr_c(\text{$x$ pred pos}) \Pr_c(\text{$x$ is pos}|\text{$x$ pred pos})\\ \end{split}\end{equation}

Therefore: \begin{equation}\begin{split} \Pr_c(\text{$x$ pred pos}) = \frac{\Pr(\text{$x$ is pos}) \Pr_c(\text{$x$ pred pos}|\text{$x$ is pos})}{\Pr_c(\text{$x$ is pos}|\text{$x$ pred pos})}\\ \end{split}\end{equation}

So basically when we know precision and recall of model $c$, and know percentage of true positives in the dataset, we can also know the positive rate of model $c$.

Also, assuming that models $A$ and $B$ are independent, then by the definition of the unanimous ensemble, then: \begin{equation}\Pr_{A,B}(\text{$x$ pred pos}) = \Pr_A(\text{$x$ pred pos})\Pr_B(\text{$x$ pred pos}) \end{equation}

Also, by the definition of the unanimous ensemble, the ensemble returns a true positive only when both of the models $A,B$ return positive and are both are correct. Therefore the recall rate of the ensemble is: \begin{equation}\begin{split} \Pr_{A,B}(\text{$x$ pred pos}|\text{$x$ is pos}) =& \Pr_A(\text{$x$ pred pos}|\text{$x$ is pos})\Pr_B(\text{$x$ pred pos}|\text{$x$ is pos}) \end{split}\end{equation}

Then, identifying the precision of the ensemble can be done by the Bayes rule: \begin{equation} \Pr_{A,B}(\text{$x$ is pos}|\text{$x$ pred pos}) = \frac{\Pr_{A,B}(\text{$x$ pred pos}|\text{$x$ is pos}) \Pr(\text{$x$ is pos})}{\Pr_{A,B}(\text{$x$ pred pos})} \end{equation}

Simulation code

import random

def get_problem(pr):
    if random.random() <= pr:
        return 1
    else:
        return 0

def evaluate(problems, answers, v=False):
    true_positives_num = 0
    true_negative_num = 0
    false_positives_num = 0
    false_negatives_num = 0
    for i in range(0,len(answers)):
        if problems[i] == 0:
            if answers[i] == 0:
                true_negative_num += 1
            elif answers[i] == 1:
                false_positives_num += 1
        elif problems[i] == 1:
            if answers[i] == 0:
                false_negatives_num += 1
            elif answers[i] == 1:
                true_positives_num += 1

    if (true_positives_num + false_positives_num):
        precision = float(true_positives_num) / (true_positives_num + false_positives_num)
        recall = float(true_positives_num) / (true_positives_num + false_negatives_num)
    else:
        precision = 0
        recall = 0

    if v == True:
        print('    precision: '+str(precision)+'     recall: '+str(recall) + ' (simulated)')

    return [precision, recall]

def get_ans(problems,precision,recall):
    answers = dict()
    answers_done = []
    problems_done = []
    problems_i = range(0, len(problems))
    random.shuffle(problems_i)

    for p in problems_i:
        # measure current precision/recall
        [precision_cur,recall_cur] = evaluate(problems_done,answers_done)

        # adjust precision to match target
        if problems[p] == 0:
            if precision_cur <= precision:
                answers[p]=0
                answers_done.append(0)
                problems_done.append(0)
            else:
                answers[p]=1
                answers_done.append(1)
                problems_done.append(0)

        # adjust recall to match target
        if problems[p] == 1:
            if recall_cur <= recall:
                answers[p]=1
                answers_done.append(1)
                problems_done.append(1)
            elif recall_cur > recall:
                answers[p]=0
                answers_done.append(0)
                problems_done.append(1)

    return [answers[i] for i in range(0, len(problems))]

def unanimous_vote(A_answers, B_answers):
    AB_answers = []
    for i in range(0, len(A_answers)):
        if A_answers[i] == B_answers[i] == 1:
            AB_answers.append(1)
        else:
            AB_answers.append(0)
    return AB_answers

# simulate
tests = 10000
pr = 0.5
A_precision = 0.6
A_recall = 0.4
B_precision = 0.6
B_recall = 0.6

problems = [get_problem(pr) for i in range(0, tests)]
pr_sim = sum(problems)/float(len(problems))
A_answers = get_ans(problems,A_precision,A_recall)
B_answers = get_ans(problems,B_precision,B_recall)
AB_answers = unanimous_vote(A_answers, B_answers)

print('dataset positives rate=%s (configured)' % pr)
print('dataset positives rate=%s (simulated)' % pr_sim)
print(' A: precision=%s recall=%s (configured)' %(A_precision, A_recall))
[A_precision_sim, A_recall_sim] = evaluate(problems, A_answers, v=True)
print(' B: precision=%s recall=%s (configured)' %(B_precision, B_recall))
[B_precision_sim, B_recall_sim] = evaluate(problems, B_answers, v=True)

# analytically find precision and recall of the ensemble
A_pr = pr_sim*A_recall_sim/A_precision_sim
B_pr = pr_sim*B_recall_sim/B_precision_sim
AB_pr = A_pr*B_pr
AB_recall = A_recall_sim * B_recall_sim
AB_precision = AB_recall*pr_sim/AB_pr

print(' A: expected positives=%s     simulated positives=%s' %(A_pr, sum(A_answers)/float(len(A_answers))))
print(' B: expected positives=%s     simulated positives=%s' %(B_pr, sum(B_answers)/float(len(B_answers))))
print('AB: expected positives=%s     simulated positives=%s' %(AB_pr, sum(AB_answers)/float(len(AB_answers))))

print('AB: precision=%s recall=%s (expected)' %(AB_precision, AB_recall))
evaluate(problems, AB_answers, v=True)

Simulation results (almost pass):

All predictions are correct except the positives rate of the ensemble; I think this is the primary reason the expected precision value differs than the simulated. If you manually overwrite that the values get closer.

Results:

dataset positives rate=0.5 (configured)
dataset positives rate=0.4966 (simulated)
 A: precision=0.6 recall=0.4 (configured)
    precision: 0.599939613527     recall: 0.400120821587 (simulated)
 B: precision=0.6 recall=0.6 (configured)
    precision: 0.600080547725     recall: 0.600080547725 (simulated)
 A: expected positives=0.3312     simulated positives=0.3312
 B: expected positives=0.4966     simulated positives=0.4966
AB: expected positives=0.16447392     simulated positives=0.174
AB: precision=0.72495387009 recall=0.240104721774 (expected)
    precision: 0.7     recall: 0.245267821184 (simulated)
               ^^^
               This value (0.7) is mismatching against 0.72.
               If you try using two highly accurate classifiers, 
               the error will increase even further. I think this
               must be due to violating the assumption of independence
               between models A and B.