Судья прогнозов
Аналитики соревнуются, чья модель ожидаемых голов лучше. Каждая модель для каждого удара сезона выдаёт логит z — число, из которого вероятность гола получается сигмоидой: p = 1 / (1 + e−z). Судья оценивает модель средней логарифмической потерей по ударам с известным исходом:
$$L = \frac{1}{n}\sum_{i=1}^{n} \ell_i,$$где ℓi = −ln pi, если удар стал голом, и ℓi = −ln(1 − pi), если не стал.
Чем меньше L, тем лучше модель. Среди участников есть очень самоуверенные: они присылают логиты в тысячи. Модель, которая назвала гол невозможным, а он случился, должна заплатить полную цену своей ошибки — судья не имеет права ни упасть, ни округлить такую ошибку до «очень большой».
Третий и четвёртый тесты — настоящие удары второй половины сезона 2017/18 пяти футбольных чемпионатов (открытые данные Wyscout): логиты модели из статьи и той же модели, увеличенные в 25 раз.
Вход
В первой строке n (1 ≤ n ≤ 10⁵). В каждой из следующих n строк — логит zi (вещественное число, |zi| ≤ 10⁴, не больше шести знаков после точки) и исход yi: 1 — гол, 0 — нет.
Выход
Одно число — L. Ответ проверяется с абсолютной или относительной погрешностью 10⁻⁶.
Примеры
Пример 1
4 -1.200000 0 0.400000 1 -3.000000 0 -2.100000 1
0.760101149
Пример 2
3 40.000000 0 -50.000000 1 3.000000 1
30.016195784
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Посчитайте «в лоб» для z = 40 и промаха. Чему в числах с плавающей точкой равно 1 − σ(40)? А σ(−800)?
2Подсказка 2
Не вычисляйте вероятность вовсе. Запишите −ln(1 − σ(z)) через z напрямую и посмотрите, что останется от формулы при большом z.
3Идея
Обе ветки потери — одна и та же функция ln(1 + ez) от разных аргументов: −ln σ(z) = ln(1 + e−z), а −ln(1 − σ(z)) = ln(1 + ez). Её называют softplus, и её легко вычислить без потерь при любом z:
$$\ln(1 + e^{z}) = \max(z, 0) + \ln\left(1 + e^{-|z|}\right).$$Большая часть ответа, max(z, 0), выносится точно, а под логарифмом остаётся число от 1 до 2. Для малой добавки есть функция log1p, которая не теряет знаков, когда e−|z| совсем мало.
4Разбор
Для гола прибавляем softplus(−z), для промаха — softplus(z), в конце делим на n. Ни одной вероятности программа не вычисляет, и поэтому ей не грозят ни переполнение, ни логарифм нуля.
Посмотрите, что происходит с наивной формулой. При z = 40 сигмоида равна 1 − 4·10⁻¹⁸, а ближайшее к этому число double — ровно 1: расстояние между соседними double около единицы — 1,1·10⁻¹⁶. Значит, 1 − σ(40) вычисляется как 0, и ln(0) роняет программу. При z = 36 ещё хуже: 1 − σ(36) получается не нулём, а 2,2·10⁻¹⁶ вместо 2,3·10⁻¹⁶, программа не падает и молча выдаёт потерю 36,04 вместо 36,00. Седьмой тест собран из таких ударов.
На настоящих ударах модель из статьи получает 0,2922 — то же число, что в листинге статьи. Та же модель, увеличенная в 25 раз, ранжирует удары точно так же, но её вероятности почти все равны 0 или 1, и потеря вырастает до 4,54. Логарифмическая потеря наказывает за уверенность, которой нет.
4+Решение
5Сложность
O(n) времени и O(1) дополнительной памяти, если читать числа по одному.
6Типичные ошибки
- Обрезать вероятность. Частая защита — заменить p на min(max(p, 10⁻¹⁵), 1 − 10⁻¹⁵). Программа перестаёт падать, но любая уверенная ошибка теперь стоит не больше 34,5, и самоуверенная модель получает поблажку. Во втором примере ответ 23,04 вместо 30,02.
- exp(−z) при большом отрицательном z. В Python
math.exp(800)бросает исключение, в Go даёт +Inf; в обоих случаях дальше всё ломается. Отсюда два варианта сигмоиды для z ≥ 0 и z < 0 в листинге статьи. - log(1 + x) вместо log1p(x). При x меньше 10⁻¹⁶ сумма 1 + x округляется до 1, и логарифм теряет всё. Для этой задачи с допуском 10⁻⁶ это не смертельно, но в сумме по многим уверенным и правым прогнозам знаки уходят.