Evaluating probabilistic forecasts of K-most-likely events from an arbitrarily large event space

Question

Suppose a populous nation has a high homicide rate and an understaffed police force. The police chief hires a statistician and together they decide to take a preventative approach by identifying would-be-murderers before they commit the crime, along the lines of Minority Report.

The police chief requires the statistician to provide the following on a daily basis:

1. A list of tomorrow's top 100 most-likely murderers. (The statistician may have information about the entire citizen population, but the chief doesn't have time to think about more than 100 cases.)
2. For each person on the list, the statistician's best estimate of the probability that the person will commit a murder (in the absence of intervention).

The police chief will regularly evaluate the statistician's forecasts and provide bonus pay for good performance. Unfortunately, the chief does not know how to score the forecasts in a way that incentivizes the statistician to honestly strive toward the objectives (1) and (2). Can you help?

Here are two basic proposals of increasing complexity:

• Score = recall = The number of people who attempt murder that the statistician included on the list. But this gives no incentive for accurate probabilities (2).
• Score = $100 - \sum_{i=1}^{100} (O_i - p_i)^2 $, similar to the Brier score. Here $p_i$ is the forecasted probability for the $i$th person on the list, and $O_i$ is the true outcome (0 or 1) for their murdership status. But the statistician can easily maximize this by selecting 100 people with no chance of being murderers and taking $p_i$ to be identically 0.

Any other ideas? I strongly suspect that this is not a new problem; a good reference may suffice.

Answer 1

I admire your commitment to world-building research for that dystopian novel you've been working on!

A possible argument that this problem is underdetermined without additional assumptions.

It seems (I lack definite proof) that we need to know at least the overall population size, and presumably some other factors as well. Consider a likelihood score.

Assume murders are committed independently randomly with some murderousness probability $\theta_i$ by each member of the population $i$ (probably not true but let's run with it). The probability space is the powerset $\Omega_n = \mathcal P(\{0, ..., n-1\})$ for population size $n$. Then outcome $X$ happens with probability

$$P(X|\theta) = \underset{i<n}\prod \theta_i^{i \in X}(1-\theta_i)^{i \notin X}$$

Then, as alluded to in your remarks, for a complete prediction $\hat\theta$ of murderousness in the population, we could appropriately score the prediction, for example with the likelihood

$$\mathcal L(\theta|X) = P(X|\theta)$$

An alternative could additionally incorporate some Bayesian prior and instead score the a-posteriori probability/credence of a particular prediction. (An appropriate choice would be a product of independent Beta distributions, one for each member of the population, which is then conjugate to the set of independent Bernoulli samples of each person's murdership).

---

But for a truncated prediction $\hat\theta_k$ of top-k-murderousness, the likelihood is undefined. For example the prediction $\hat\theta_3 = (0:0.3, 1:0.2, 2:0.1)$ might correspond to the 'full' parameterisation $\hat\theta^\star = \hat\theta_3 + (3:0.1, ..., 99:0.1)$ or to $\hat\theta^\star = \hat\theta_3 + (3:0.001, ..., 99:0.001)$, each of which assign very different probabilities to any outcome in $\Omega_{100}$ and consequently have very different likelihood or a-posteriori credibility.

I'm not completely clear from your question if the full outcome $X$ is observed, or only the truncated event $X_k$ consisting of the murdership of the named top-k-murderous members of the population.

Notice that, if we do make a particular choice of extrapolation from $\hat\theta_k$ to the full $\hat\theta^\star$, a truncated observation $X_k$ which witnesses only those individuals predicted in $\hat\theta_k$ is a well-defined event over the probability space and thus has a well-defined probability, allowing a likelihood score to be derived. But it suffers from the problem you identified for Brier score, where the statistician can control the censoring of the observations to avoid the first desideratum of naming only the most credible murderers.

If instead we have access to $X$, the full observation of murders committed, the likelihood or a-posteriori credibility of an extrapolated $\hat\theta^\star$ appears to me to be both defined and well-incentivised.

---

What remains with this picture is how to sensibly extrapolate from a truncated prediction $\hat\theta_k$ to a full prediction $\theta^\star$.

A computationally tractable approach would be to have the statistician commit to a population size $n$ and a uniform baseline murderousness $p$ for the rest of the population not identified in $\hat\theta_k$, producing a Binomial 'rest-of-population' murder-count distribution. For suitable $n$ and $p$ the 'rest-of-population' likelihood factor could be even more tractably approximated as a Poisson and you could simplify and have her propose such a Poisson parameter $\lambda$. (This Poisson case is very plausible in the motivating scenario of populations and murders, but may not transfer to other cases.)

Letting $r = |X-dom(\hat\theta_k)|$ the number of 'surprise murders',

Binomial case $$ \mathcal L(\hat\theta_k, n, p|X) = \binom {n-k} r p^r (1-p)^{n-k-r} \underset{i \in dom(\hat\theta_k)}\prod \hat\theta_k[i]^{i \in X}(1 - \hat\theta_k[i])^{i \notin X} $$

Poisson case $$ \mathcal L(\hat\theta_k, \lambda|X) = \frac {\lambda^r e^{-\lambda}} {r!} \underset{i \in dom(\hat\theta_k)}\prod \hat\theta_k[i]^{i \in X}(1 - \hat\theta_k[i])^{i \notin X} $$

A 'generous' and similarly tractable approach might be to give 'benefit of the doubt' and extrapolate to $\underset {i \in dom(\hat\theta_k)} {min} \hat\theta_k[i]$ for anyone who did in fact murder, and $0$ for anyone who did in fact not murder. This should still incentivise nominating the most plausible murderers, and giving reasonable estimates, but it might introduce some bias.

Generous case $$ \mathcal L^\star(\hat\theta_k|X) = \left(\underset {i \in dom(\hat\theta_k)} {min} \hat\theta_k[i]\right)^r \underset{i \in dom(\hat\theta_k)}\prod \hat\theta_k[i]^{i \in X}(1 - \hat\theta_k[i])^{i \notin X} $$

Answer 2

Indeed, there are many other ideas! If you call $p$ the estimated probability and $y$ the output, the following metrics are widely used:

• MAE = $\sum_i|p_i-y_i]$
• MSE = $\sum_i(p_i-y_i)^2$,
• logarithmic loss = $\sum_i(1-y_i)\log p_i+y_i\log (1-p_i)$

In these examples, a misclassification is more penalized if the associated probability is high.

Note that these approaches will be affected if you replace $p$ by $p^2$. Besides, it is hard to say if if a logarithmic loss of 0.34 is high or low - whereas an error rate of 95% is self explanatory.

A way to circumvent this is to use the AUC, which lies between 0 and 1 and focuses on the rank of the proposed probabilities.

• AUC $=\frac{S_0-n_0(n_0+1)/2}{n_0n_1}$

Where $n_0$ and $n_1$ are the number of positive and negative examples. $S_0$ is the sum of the ranks of the positive examples.

More details about AUC can be found here: http://home.cse.ust.hk/~qyang/Teaching/537/Papers/AUC-evaluation.pdf

Answer 3

There has, as you suggest, been quite a lot of discussion in various communities surrounding this point. The crux of the problem is that when you have a relatively rare event (the probability that even the most murderous person commits a murder on a given day has to be quite small- naively, for someone who commits murders on 36 days a year, it would be only ~.1 for a given day) evaluating the value of that prediction presents significant challenges. A correct prediction that the probability is .1 still only results in a 10 percent chance of the event occuring.

Luckily, there are many branches of inquiry which concentrate on rare events.

Meterology, for example, consists almost entirely of predicting relatively rare events. In this paper (1) , Marzban evaluates several metrics for evaluating models similarly in terms of the propensity of those metrics to induce the forecaster to over- or underestimate the likelihood of a given rare event.

While there are many specific model variations that are discussed in more detail in the paper, the general approaches are:

1. Some combination of the false alarm rate (0 results classified as 1 predictions) and the probability of detection (1 results classified as 0 predictions)
2. Critical Success Index
3. Skill scores
4. Custom angle metrics (Marzban 754-55)

The general results we see for a model is that some models encourage over-predicting the rare event in question and some encourage under-predicting the event.

In this case, the police chief would want to make a decision on which metric to employ to evaluate the results of the statistician's model informed by the way in which the prediction would be used. If it was, as you mention, in Minority Report, going to be used to preemtively imprison people, presumably we would want to encourage the statistician to under-predict the rare events (or, in a more authoritarian state, over-predict them into near-oblivion).

(1) Caren Marzban, 1998: Scalar Measures of Performance in Rare-Event Situations. Wea. Forecasting, 13, 753–763.

Answer 4

"You acted unwisely," I cried, "as you see
    By the outcome." He calmly eyed me:
"When choosing the course of my action," said he,
    "I had not the outcome to guide me."

(Ambrose Bierce: A Lacking Factor, from The Scrap Heap)

Great way to pose the question!

I'd like to offer a non-answer which presents the forecast problem from a different point of view.

As I see it, your way of presenting the problem portrays the statistician's goal as trying to build a "model" that's "close to the truth". Then one can speak of performance and pay.

This is a widespread way of viewing probability theory, but not the only one. I belong to those group of people (Jaynes, Jeffreys, Savage, de Finetti, and many others) who find it circular and ultimately hopeless.

The problem is that we cannot validate a forecast by comparing it to the "truth" – because we don't have the truth. If we had it, there would be no need of making forecasts. On the other hand, once we acquire knowledge of the truth, the forecast ceases to be important.

The point of a forecast is to try to guess the truth as best as possible given all information we have (and can gather). It may well happen that all info we have actually misses some crucial element, and therefore our forecast is grossly off the mark. Yet, that's the best we could do. It was impossible to use information that we didn't have – if we had had it, we would have used it! And maybe we didn't even know that some crucial info was missing. In fact, this is the whole crux of guessing and making forecasts – do the best with the info you have. We can't do our best with the info we don't have.

From this point of view, performance should be judged based on whether the information we actually had was optimally used. It may happen that the forecast was optimal, and yet quite off the mark; or vice versa, the forecast was poorly made, and yet turns out to be close to the truth.

Let me try to explain with an example.

Take a person $P$ in the population of your scenario.

Statistician $A$ examines the past history of $P$ and of $P$'s family (including, say, communications and interactions with other people) their general and mental health histories, and similar information. From this analysis, it appears that $P$ is a very pacific, altruistic, compassionate person, who would rather die than harm another person or let another person come to deadly harm, and who is generally loved by family, friends, acquaintances.

Statistician $A$ therefore gives an extremely low – but not zero – probability that $P$ would commit murder the next day.

Now comes statistician $B$. This statistician has exactly the same information as statistician $A$ – no more, no less.

Statistician $B$ gives 100% probability that $P$ will commit murder the next day. We can imagine that statistician $A$ asks $B$ why such a forecast, and statistician $B$ replies: "Because I hate $P$ – that person is meek and a good-doer; I can't stand people like that".

I imagine you'll agree with me that $B$'s reasoning and forecast are completely illogical and unreasonable. The reasoning and forecast of $A$, on the other hand, seem well-founded and reasonable. Or?

The next day comes. Arrived at work after the usual morning walk, person $P$ murders a colleague with a pair of scissors, then commits suicide.

Now, the statistician's $B$ forecast correctly "predicted" the murder. We could say that statistician $A$'s forecast was instead quite off the mark.

Should then a score function reward $B$ and penalize $A$? I want to remind you that $A$ and $B$ made their forecasts based on exactly the same information, summarized above.

We may wonder why $P$ committed murder – and the fact that we wonder confirms, in my opinion, the view that the murder was unexpected and $A$'s foracast was the most reasonable.

Here's an explanation. While person $P$ was walking on the street towards work in the morning, someone bumped into $P$ and purposely injected an allucinogen or some kind of neurology-altering drug. $P$ did not notice, maybe just checked for the wallet, in case the stranger was a pick-pocket. The stranger was actually an emissary for a secret lab that develops neurological weapons for a foreign country, and was in the nation just for the day, with the explicit purpose of testing the drug on a random citizen. The drug was designed to cause violent behaviour followed by self-violent behaviour.

I know this is a silly explanation, but you can find an alternative one of your own, maybe involving unsuspected congenital neurological problems or whatnot. The point is that unexpected events happen, and sometimes more than one in a row, as I'm sure you've experienced yourself in your life.

Yet, according to the "truth-based" reward/penalty point of view, such rare events will affect negatively a statistician who actually made a completely reasonable forecast. And I believe they shouldn't. (We cannot even exclude that many such events could happen.)

So my answer is that such the reward/penalty scheme should be based on whether the statistician does the most reasonable forecast given all the gatherable information, irrespective of whether the event happens or not. (Of course it's very difficult to come up with a score for this.)

Jaynes discusses this throughout his book, and in chapter 13 he quotes the passage by Bierce I put at the beginning, which makes the point brilliantly.

Answer 5

Before even getting to a scoring mechanism, you are going to need to deal with a fundamental problem in this setup, which is that you only get data from people who the police don't arrest for pre-crime in response to the statistician's predictions. Presumably the point of the minority-report style list is that the police will arrest the people on it so that they don't commit murder. (At least, that is what happens in the movie.) If they do this, they will never find out whether the person would or would not have committed a murder that day, so there is no data to begin with.

If you want to get around this, you are going to have to do one of two things. Either the police don't arrest some (or all) of the people on the statistician's list, to see what happens, or the list needs to be longer than the number of people arrested. You are going to need to specify this in order to be clear on the actual data that is available for the scoring mechanism.