CS
Задачник Базовый курс EN

Задача

Поправка на сезон

классификация двоичный поиск поиск корня игры

Модель ожидаемых голов обучили на матчах осени. Весной она по-прежнему хорошо отличает опасные удары от безнадёжных, но голов забивают больше, чем она обещает: по модели из статьи на 19 912 весенних ударов ожидалось 2081,8 гола, а забито 2177.

Самая простая поправка — сдвинуть все логиты на одно и то же число c: удар, которому модель давала логит zi, получает вероятность σ(zi + c), где σ(t) = 1 / (1 + e−t). Порядок ударов по опасности от этого не меняется. Найдите сдвиг, после которого ожидаемых голов ровно столько, сколько забито:

$$\sum_{i=1}^{n} \sigma(z_i + c) = \text{число голов}.$$

Третий и четвёртый тесты — настоящие удары сезона 2017/18 пяти футбольных чемпионатов (открытые данные Wyscout) с логитами модели из статьи: весенние и те осенние, на которых модель училась.

Вход

В первой строке n (1 ≤ n ≤ 5·10⁴). В каждой из следующих n строк — логит zi (|zi| ≤ 50, не больше шести знаков после точки) и исход: 1 — гол, 0 — нет.

Выход

Сдвиг c с абсолютной или относительной погрешностью 10⁻⁶. Если такого сдвига не существует, выведите -.

Примеры

Пример 1

Вход
3
0.000000 1
0.000000 0
0.000000 0
Выход
-0.693147181

Пример 2

Вход
2
-1.500000 1
0.250000 1
Выход
-

Ограничения

Время · Python
4000 мс
Время · Go
1000 мс
Память
256 МБ
Проверка
11 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Как меняется левая часть уравнения, когда c растёт? Что с ней при c → −∞ и при c → +∞?

2Подсказка 2

Когда корня нет? А если он есть — в каком отрезке его заведомо искать, если |zi| ≤ 50?

3Идея

Функция f(c) = Σσ(zi + c) строго возрастает: каждое слагаемое — сигмоида, сдвинутая влево. При c → −∞ она стремится к 0, при c → +∞ — к n, и непрерывна. Поэтому уравнение f(c) = G для числа голов G имеет ровно один корень, если 0 < G < n, и ни одного, если голов нет вовсе или голами стали все удары: ожидаемое число голов бывает сколь угодно близко к 0 или к n, но не равно им.

Монотонная функция и нужное значение — это двоичный поиск по ответу. При |zi| ≤ 50 корень лежит в [−100, 100]: при c = −100 каждое слагаемое меньше σ(−50) ≈ 2·10⁻²², и вся сумма меньше одного гола, а при c = 100 — симметрично.

4Разбор

Шестидесяти делений отрезка пополам хватит с запасом, но каждое — проход по всем ударам, и при пятидесяти тысячах ударов это три миллиона сигмоид. Быстрее метод Ньютона: производная f′(c) = Σσ(1 − σ) считается в том же проходе, и вблизи корня каждый шаг удваивает число верных знаков. Чтобы Ньютон не улетел на пологом участке, храним отрезок [lo, hi], в котором заведомо лежит корень: шаг, выводящий за отрезок, заменяем делением пополам. На настоящих ударах хватает четырёх проходов, на тесте с единственным голом среди пятидесяти тысяч безнадёжных прогнозов — девяти.

Почему это уравнение, а не просто удобное правило? Посмотрите на логарифмическую потерю модели σ(zi + c) как на функцию одного числа c. Её производная — Σ(σ(zi + c) − yi), и в минимуме она равна нулю. Значит, найденный сдвиг — это логистическая регрессия с одним весом при постоянном признаке, обученная на весне поверх старой модели. Так поступают на практике, когда данные «плывут»: дообучают свободный член, а остальное оставляют.

Ответ на весенних ударах — 0,0573: шансы каждого удара умножаются на e0,0573 ≈ 1,06. На осенних — −0,0004, почти ноль, как и обещает статья: с точными весами было бы ровно ноль, а здесь веса округлены до четырёх знаков.

4+Решение
5Сложность

O(n) на проход, проходов O(log(1/ε)) при делении пополам и гораздо меньше у Ньютона.

6Типичные ошибки
  • Сдвиг по средним. Взять логит доли голов и вычесть логит средней вероятности: logit(G/n) − logit(Σσ(zi)/n). Это верно, только если все zi одинаковы, как в первом примере. На весенних ударах выходит 0,0497 вместо 0,0573: среднее сигмоид — не сигмоида среднего, сигмоида кривая.
  • Умножить вероятности на G / Σpi. Ожидаемых голов станет сколько нужно, но это другая поправка — не сдвиг логитов, и у удара с вероятностью 0,95 она может дать больше единицы.
  • Забыть про случаи без корня. Если голов нет или голами стали все удары, логарифм доли голов не определён, а поиск «сойдётся» к краю отрезка.

Алгоритмы задачи

ML Алгоритм Логистическая регрессия Оценивает вероятность ответа «да»: взвешенная сумма признаков, пропущенная через сигмоиду. O(n·d² + d³) на шаг Ньютона 3 задачи SRT Приём Двоичный поиск по ответу Если проверить ответ легче, чем найти, и проверка монотонна, — ищем ответ делением пополам. O(log D · стоимость проверки) 2 задачи NUM~ Алгоритм Бисекция и метод Ньютона Корень уравнения: деление отрезка пополам надёжно, касательные Ньютона — быстро. бисекция — log₂((b − a)/ε) шагов; Ньютон — около log₂ от числа знаков 2 задачи
Каталог алгоритмов