The forecasts' judge
Analysts compete over whose expected goals model is better. For each shot of the season each model outputs a logit z, a number from which the probability of a goal is obtained by the sigmoid: p = 1 / (1 + e−z). The judge scores a model by the mean log loss over shots with a known outcome:
$$L = \frac{1}{n}\sum_{i=1}^{n} \ell_i,$$where ℓi = −ln pi if the shot became a goal, and ℓi = −ln(1 − pi) if not.
The smaller L, the better the model. Some participants are very self-assured: they send logits in the thousands. A model that called a goal impossible, and it happened, must pay the full price of its error; the judge has no right either to crash or to round such an error down to “very large”.
The third and fourth tests are real shots from the second half of the 2017/18 season of five football leagues (Wyscout open data): the logits of the model from the article and of the same model multiplied by 25.
Input
The first line holds n (1 ≤ n ≤ 10⁵). Each of the next n lines holds the logit zi (a real number, |zi| ≤ 10⁴, at most six digits after the point) and the outcome yi: 1 for a goal, 0 otherwise.
Output
One number: L. The answer is checked with an absolute or relative error of 10⁻⁶.
Examples
Example 1
4 -1.200000 0 0.400000 1 -3.000000 0 -2.100000 1
0.760101149
Example 2
3 40.000000 0 -50.000000 1 3.000000 1
30.016195784
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Compute it head-on for z = 40 and a miss. What does 1 − σ(40) equal in floating point? And σ(−800)?
2Hint 2
Do not compute the probability at all. Write −ln(1 − σ(z)) directly in terms of z and see what is left of the formula at a large z.
3The idea
Both branches of the loss are the same function ln(1 + ez) of different arguments: −ln σ(z) = ln(1 + e−z), and −ln(1 − σ(z)) = ln(1 + ez). It is called softplus, and it is easy to compute without loss at any z:
$$\ln(1 + e^{z}) = \max(z, 0) + \ln\left(1 + e^{-|z|}\right).$$The main part of the answer, max(z, 0), is taken out exactly, and a number between 1 and 2 is left under the logarithm. For the small addition there is the function log1p, which loses no digits when e−|z| is tiny.
4Walkthrough
For a goal add softplus(−z), for a miss softplus(z), and divide by n at the end. The program computes not a single probability, and so it is threatened by neither overflow nor the logarithm of zero.
See what happens with the naive formula. At z = 40 the sigmoid equals 1 − 4·10⁻¹⁸, and the nearest double to it is exactly 1: the gap between neighbouring doubles near one is 1.1·10⁻¹⁶. So 1 − σ(40) is computed as 0, and ln(0) crashes the program. At z = 36 it is even worse: 1 − σ(36) comes out not as zero but as 2.2·10⁻¹⁶ instead of 2.3·10⁻¹⁶, the program does not crash and silently gives a loss of 36.04 instead of 36.00. The seventh test is made of such shots.
On real shots the model from the article gets 0.2922, the same number as in the article’s listing. The same model multiplied by 25 ranks the shots in exactly the same way, but almost all its probabilities are 0 or 1, and the loss grows to 4.54. Log loss punishes confidence that is not there.
4+Solution
5Complexity
O(n) time and O(1) extra memory if the numbers are read one at a time.
6Common mistakes
- Clipping the probability. A common defence is to replace p with min(max(p, 10⁻¹⁵), 1 − 10⁻¹⁵). The program stops crashing, but any confident error now costs at most 34.5, and a self-assured model gets a discount. In the second example the answer is 23.04 instead of 30.02.
- exp(−z) at a large negative z. In Python
math.exp(800)raises an exception, in Go it gives +Inf; in both cases everything breaks after that. Hence the two variants of the sigmoid for z ≥ 0 and z < 0 in the article’s listing. - log(1 + x) instead of log1p(x). For x below 10⁻¹⁶ the sum 1 + x rounds to 1, and the logarithm loses everything. For this problem with a tolerance of 10⁻⁶ it is not fatal, but in a sum over many confident and correct predictions digits drain away.