Is there a best curve
A coach wants an expected goals model for the team and builds it on the shots of one match: the probability of a goal from distance x is σ(b + wx), where σ(t) = 1 / (1 + e−t), and b and w are chosen by the log loss
$$L(b, w) = \sum_{i=1}^{n} \ell_i,$$where ℓi = −ln σ(b + wxi) if the shot became a goal, and ℓi = −ln(1 − σ(b + wxi)) if not. You need the pair (b, w) at which L is smallest.
An analyst warns: on one match there may be no best pair at all; the loss will keep decreasing without end and the coefficients will keep growing. Help the coach: find the best pair (b, w) or report that there is none.
Four tests are real shots of the 2017/18 season of five football leagues (Wyscout open data): the whole autumn and three individual matches.
Input
The first line holds n (1 ≤ n ≤ 10⁵). Each of the next n lines holds the distance of the shot to the middle of the goal in decimetres xi (an integer, 0 ≤ xi ≤ 10⁴) and the outcome: 1 for a goal, 0 otherwise.
Output
If the smallest value of L is attained at exactly one point, print it: b and w with an absolute or relative error of 10⁻⁶. Otherwise, if the minimum is not attained or is attained at more than one point, print none.
Examples
Example 1
6 80 1 120 0 150 1 200 0 260 0 310 0
4.30777726528 -0.0317706841831
Example 2
4 60 1 95 1 180 0 240 0
none
Example 3
4 60 1 120 1 120 0 240 0
none
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 12 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
Look at the second example: both goals are closer than 10 metres, both misses farther than 18. What happens to the loss of the curve σ(k(140 − x)) as k grows?
2Hint 2
In the third example a goal and a miss are from the same distance, 12 metres, and there is still no best pair. What is the loss of these two shots for any curve passing through 1/2 at 12 metres? And of the other two shots, as the curve gets ever steeper?
3The idea
The loss is convex, so everything depends on whether it has a minimum point. It has none exactly when goals and misses can be separated by a threshold: all goals on one side of some t, all misses on the other, with shots of both outcomes allowed on the threshold itself. In this case the curve σ(k(t − x)) with growing k presses the loss of each shot off the threshold down to zero, and that of shots on the threshold to ln 2 apiece, and the loss decreases without reaching its limit. This is complete and quasi-complete separation from the work of Albert and Anderson (1984). The cases “all shots are goals”, “not a single goal” and “all shots from one distance” belong here too: in the last a minimum exists but is not unique, as b and w enter the loss only through the sum b + wx.
The check is four numbers: the smallest and largest x among goals and among misses. There is no separation if maxmisses > mingoals and maxgoals > minmisses. Then the minimum exists and is unique, and Newton’s method finds it.
4Walkthrough
Shots from the same distance are added together: they have the same feature and enter the loss through the number of shots and the number of goals. There are at most 10⁴ distances, so a Newton step is cheap.
Two tricks make Newton reliable. The first is to centre and scale the feature: work with u = (x − x̄) / s and at the end convert back w = c / s, b = a − wx̄. In the twelfth test the shots lie around 500 metres, and without centring the intercept −290.9 and the slope 0.058 are so tightly linked that the system for the Newton step is badly conditioned. The second is a line search: if a full step increased the loss, halve it until the loss decreases. Without it Newton can overshoot the minimum when the curve is very steep, as in the eleventh test, where the separation is spoiled by a single miss.
It is convenient to start with c = 0 and a = the logit of the share of goals: the best curve without a slope. Stop when the step is below 10⁻¹³ relative to the numbers themselves.
On the whole autumn the best curve is b = 0.1051, w = −0.01483 per decimetre, that is, the odds of a goal fall by 14% with every metre. Of the 1826 matches of the season, 330 have no best curve: 184 had no goals, in 132 all goals were scored closer than all the misses were taken, in seven the other way round, all goals farther, and in seven more the farthest goal and the closest miss are from the same distance.
4+Solution
5Complexity
O(n) for reading and counting, O(m) per Newton step for m distinct distances; the steps number a few, with the line search a few dozen.
6Common mistakes
- Not checking for separation. Newton honestly decreases the loss, the coefficients grow, and after a hundred steps the program prints huge numbers, or crashes on overflow. There is no answer all the same.
- Checking only strict separation. If a goal and a miss lie at the same distance on the boundary, there is no strict threshold, but there is still no minimum: the shots on the threshold do not stop the others from becoming ever more confident. The third example and the seventh test.
- All shots from one distance. Goals and misses are mixed, and it seems there is an answer, but the scale of the feature is zero: you cannot divide by s, and the minimum is a whole line in the plane (b, w). The ninth test.
Algorithms behind it
O(n·d² + d³) per Newton step
3 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