Problem 582527 · medium · Level 05 Advanced Algorithms & Graphs

Is the New Model Really Better?

paired test · sign-flip permutation test · exact binomial test · model comparison · seeded simulation

Two spam filters were run on the same test messages. correct_a[i] is 1 if filter A labelled message i correctly and 0 if not; correct_b[i] the same for filter B. B has the higher accuracy. Is that a real improvement or luck on this particular test set?

Only the messages where the filters disagree carry information about which is better. For those, let d_i = correct_b[i] - correct_a[i] (+1 when only B was right, -1 when only A was right), and let S be the sum of the d_i. If the filters were equally good, each d_i would be equally likely to be +1 or -1.

Write compare_models(correct_a, correct_b, trials, seed) that returns a dict:

  • "accuracy_a", "accuracy_b": the two accuracies,
  • "discordant": the number m of messages on which they disagree,
  • "p_flip": a sign-flip p-value. Create rng = random.Random(seed); repeat trials times: go through the disagreements in message order, and for each one call rng.random() once and flip the sign of d_i if the value is < 0.5; count the trials whose flipped sum s has |s| >= |S|. The p-value is (count + 1) / (trials + 1).
  • "p_exact": the exact version of the same p-value: with every sign a fair coin, the probability that |2k - m| >= |S|, where k counts the +1 signs among m (binomial with probability 1/2),
  • "p_unpaired": for comparison, the two-sided p-value of the usual two-proportion z-test that ignores the pairing: with n messages, accuracies pa, pb and pbar = (pa + pb) / 2, z = (pb - pa) / sqrt(pbar (1 - pbar) · 2 / n) and p = erfc(|z| / sqrt(2)); if pbar is 0 or 1, p = 1.0.

The setup provides two_models(n, acc_a, acc_b, overlap, seed), which returns the pair (correct_a, correct_b) for n simulated messages; overlap between 0 and 1 says how often the two filters find the same messages hard.

Examples

Input:  correct_a = [1, 1, 0, 1, 0, 1, 1, 0], correct_b = [1, 1, 1, 1, 1, 1, 0, 1], trials = 8, seed = 1
Output: {"accuracy_a": 0.625, "accuracy_b": 0.875, "discordant": 4, "p_flip": 1.0,
         "p_exact": 0.625, "p_unpaired": 0.2482130789899236}
Explanation: the disagreements are messages 2, 4, 6, 7 with d = +1, +1, -1, +1, so S = 2.
Ten of the 16 equally likely sign patterns have |s| >= 2.

Input:  correct_a, correct_b = two_models(500, 0.80, 0.84, 0.8, 1), trials = 4000, seed = 2
Output: {"accuracy_a": 0.8, "accuracy_b": 0.864, "discordant": 46, "p_flip": 0.00024993751562109475,
         "p_exact": 1.831543272601266e-06, "p_unpaired": 0.006796386225389965}
Explanation: none of the 4000 sign flips was as extreme as the real data; the exact value
shows how rare it is.

Constraints

  • 1 <= len(correct_a) == len(correct_b) <= 10**4, entries 0 or 1, 1 <= trials
  • m * trials <= 10**6
  • floats are compared with a tolerance of 1e-6; use no randomness other than rng

Goals

  • Compare two classifiers on the same test items with a paired test
  • Carry out a sign-flip permutation test and the matching exact binomial calculation
  • See how much stronger the paired comparison is than treating the accuracies as independent
Starting Python…