CS
Problems Base course RU

Problem

A correction for the season

classification binary search root finding games

An expected goals model was trained on the autumn matches. In spring it still tells dangerous shots from hopeless ones well, but more goals are scored than it promises: by the model from the article, 2081.8 goals were expected from 19,912 spring shots, and 2177 were scored.

The simplest correction is to shift all logits by the same number c: a shot to which the model gave the logit zi gets the probability σ(zi + c), where σ(t) = 1 / (1 + e−t). The order of shots by danger does not change. Find the shift after which there are exactly as many expected goals as were scored:

$$\sum_{i=1}^{n} \sigma(z_i + c) = \text{the number of goals}.$$

The third and fourth tests are real shots of the 2017/18 season of five football leagues (Wyscout open data) with the logits of the model from the article: the spring ones and the autumn ones on which the model learned.

Input

The first line holds n (1 ≤ n ≤ 5·10⁴). Each of the next n lines holds the logit zi (|zi| ≤ 50, at most six digits after the point) and the outcome: 1 for a goal, 0 otherwise.

Output

The shift c with an absolute or relative error of 10⁻⁶. If no such shift exists, print -.

Examples

Example 1

Input
3
0.000000 1
0.000000 0
0.000000 0
Output
-0.693147181

Example 2

Input
2
-1.500000 1
0.250000 1
Output
-

Limits

Time · Python
4000 ms
Time · Go
1000 ms
Memory
256 MB
Judging
11 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

How does the left-hand side of the equation change as c grows? What happens to it as c → −∞ and as c → +∞?

2Hint 2

When is there no root? And if there is one, in which interval is it certain to lie, given |zi| ≤ 50?

3The idea

The function f(c) = Σσ(zi + c) strictly increases: each term is a sigmoid shifted to the left. As c → −∞ it tends to 0, as c → +∞ to n, and it is continuous. So the equation f(c) = G for the number of goals G has exactly one root if 0 < G < n, and none if there are no goals at all or every shot became a goal: the expected number of goals can be arbitrarily close to 0 or to n, but never equal to them.

A monotone function and a target value call for binary search on the answer. With |zi| ≤ 50 the root lies in [−100, 100]: at c = −100 each term is below σ(−50) ≈ 2·10⁻²², and the whole sum is below one goal, and at c = 100 symmetrically.

4Walkthrough

Sixty halvings of the interval are more than enough, but each is a pass over all the shots, and with fifty thousand shots that is three million sigmoids. Newton’s method is faster: the derivative f′(c) = Σσ(1 − σ) is computed in the same pass, and near the root each step doubles the number of correct digits. To keep Newton from flying off on a flat stretch, keep an interval [lo, hi] that certainly contains the root: a step that leaves the interval is replaced with halving. On real shots four passes are enough, on the test with a single goal among fifty thousand hopeless predictions, nine.

Why this equation, and not just a convenient rule? Look at the log loss of the model σ(zi + c) as a function of the single number c. Its derivative is Σ(σ(zi + c) − yi), and at the minimum it is zero. So the shift found is a logistic regression with one weight on a constant feature, trained on the spring on top of the old model. This is what is done in practice when data “drifts”: the intercept is retrained and the rest is left alone.

The answer on the spring shots is 0.0573: the odds of each shot are multiplied by e0.0573 ≈ 1.06. On the autumn ones it is −0.0004, almost zero, as the article promises: with exact weights it would be exactly zero, but here the weights are rounded to four digits.

4+Solution
5Complexity

O(n) per pass, O(log(1/ε)) passes with halving and far fewer with Newton.

6Common mistakes
  • A shift by the means. Take the logit of the share of goals and subtract the logit of the mean probability: logit(G/n) − logit(Σσ(zi)/n). This is right only if all zi are equal, as in the first example. On the spring shots it gives 0.0497 instead of 0.0573: the mean of sigmoids is not the sigmoid of the mean, as the sigmoid is curved.
  • Multiplying the probabilities by G / Σpi. There will be as many expected goals as needed, but it is a different correction, not a shift of logits, and for a shot with probability 0.95 it may give more than one.
  • Forgetting the cases without a root. If there are no goals or every shot became a goal, the logarithm of the share of goals is undefined, and the search will “converge” to the edge of the interval.

Algorithms behind it

ML Algorithm Logistic regression Estimates the probability of a “yes”: a weighted sum of features passed through a sigmoid. O(n·d² + d³) per Newton step 3 problems SRT Technique Binary search on the answer If checking an answer is easier than finding it, and the check is monotone, search for the answer by halving. O(log D · cost of a check) 2 problems NUM~ Algorithm Bisection and Newton's method A root of an equation: halving an interval is reliable, Newton's tangents are fast. bisection: log₂((b − a)/ε) steps; Newton: about log₂ of the number of digits 2 problems
The algorithms catalogue