3
$\begingroup$

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

$\endgroup$
3
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the response. Can you say anything about precision? $\endgroup$ – Alexandre Apr 3 '16 at 15:28
  • $\begingroup$ @Alexandre Welcome! Updated, try that on. $\endgroup$ – Sean Easter Apr 4 '16 at 21:23
  • $\begingroup$ Hi Sean, thanks for the reply. Can you have a look at the comment I posted above in response to caveman ? If we assume conditional independence we can reach some conclusions by looking at the agreement between classifiers, and if we (unrealistically) assume independence, we can reach even more conclusions. $\endgroup$ – Alexandre Apr 4 '16 at 21:32
  • $\begingroup$ Is there anything particular you'd like me to look at? If you assume more, you can certainly conclude more :) $\endgroup$ – Sean Easter Apr 4 '16 at 21:46
  • $\begingroup$ Can you consider these two cases: 1) two independent classifiers each with precision > 0.5 2) two conditionally independent classifiers each with precision > 0.5 . Ultimately, I'd like to know under what circumstances combining classifiers via unanimous voting guarantees higher precision. $\endgroup$ – Alexandre Apr 4 '16 at 21:49
1
$\begingroup$

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.
$\endgroup$
  • 1
    $\begingroup$ Cab you clarify/formalize what you mean by the classifiers being independent? I believe two good classifiers are dependent but conditionally independent given an instance. $\endgroup$ – Alexandre Apr 3 '16 at 15:34
  • $\begingroup$ When $\Pr(A=answer1, B=answer1) = \Pr(A=answer1) \Pr(B=answer1)$, which I think is the same to say $\Pr(A=answer1|B=answer1) = \Pr(A=answer1)$. Hmm is it possible to have two good classifiers that are not dependent? $\endgroup$ – caveman Apr 4 '16 at 14:05
  • $\begingroup$ I guess I should say "for any answer1"... $\endgroup$ – caveman Apr 4 '16 at 14:15
  • $\begingroup$ As expected and proven by Sean Easter, $Re_{A,B} <= Re_A,Re_B$. Although your experiments show that precision $Pr_{A,B} > Pr_A, Pr_B$, I don't see a proof that this is always the case. Even by looking at your last formula, this is not evident. Additionally, the independence assumption seems faulty considering we're considering good classifiers. $\endgroup$ – Alexandre Apr 4 '16 at 20:15
  • 1
    $\begingroup$ One of the two $P(D)$ in the denominator canceled out with the none in the numerator, leaving only a single $P(D)$ in the equation. You can either assume (just like you did, unrealistically) independence, giving $2 \times Precision1 \times Precision2$, or only conditional independence, giving $\frac{2 \times Precision1 \times Precision2}{Agreement}$. $\endgroup$ – Alexandre Apr 5 '16 at 12:58

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.