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

Есть ли лучшая кривая

классификация регрессия итерации точность вычислений игры

Тренер хочет модель ожидаемых голов для своей команды и строит её на ударах одного матча: вероятность гола с расстояния x — σ(b + wx), где σ(t) = 1 / (1 + e^−t), а b и w подбираются по логарифмической потере

$$L(b, w) = \sum_{i=1}^{n} \ell_i,$$

где ℓ_i = −ln σ(b + wx_i), если удар стал голом, и ℓ_i = −ln(1 − σ(b + wx_i)), если не стал. Нужна пара (b, w), при которой L наименьшая.

Аналитик предупреждает: на одном матче лучшей пары может не оказаться вовсе — потеря будет уменьшаться без конца, а коэффициенты расти. Помогите тренеру: найдите лучшую пару (b, w) или сообщите, что её нет.

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

Вход

В первой строке n (1 ≤ n ≤ 10⁵). В каждой из следующих n строк — расстояние удара до середины ворот в дециметрах x_i (целое, 0 ≤ x_i ≤ 10⁴) и исход: 1 — гол, 0 — нет.

Выход

Если наименьшее значение L достигается ровно в одной точке, выведите её: b и w с абсолютной или относительной погрешностью 10⁻⁶. Иначе — если минимум не достигается или достигается не в одной точке — выведите none.

Примеры

Пример 1

Вход

Выход

4.30777726528 -0.0317706841831

Пример 2

Вход

Выход

none

Пример 3

Вход

Выход

none

Ограничения

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

Разбор

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

1Подсказка 1

Посмотрите на второй пример: оба гола ближе 10 метров, оба промаха дальше 18. Что происходит с потерей кривой σ(k(140 − x)), если увеличивать k?

2Подсказка 2

В третьем примере гол и промах с одного расстояния, 12 метров, — и всё равно лучшей пары нет. Какая потеря у этих двух ударов при любой кривой, проходящей через 1/2 на 12 метрах? А у остальных двух ударов, если кривая всё круче?

3Идея

Потеря выпукла, поэтому всё решает, есть ли у неё точка минимума. Её нет ровно тогда, когда голы и промахи можно разделить порогом: все голы с одной стороны от некоторого t, все промахи с другой, причём на самом пороге могут лежать удары обоих исходов. В этом случае кривая σ(k(t − x)) с растущим k прижимает потерю каждого удара вне порога к нулю, а ударов на пороге — к ln 2 за штуку, и потеря убывает, не достигая предела. Это полное и квазиполное разделение из работы Альберта и Андерсона (1984). Сюда же попадают «все удары — голы», «ни одного гола» и «все удары с одного расстояния»: в последнем случае минимум есть, но не единственный — b и w входят в потерю только в сумме b + wx.

Проверка — четыре числа: наименьшее и наибольшее x среди голов и среди промахов. Разделения нет, если max_{промахов} > min_голов и max_голов > min_{промахов}. Тогда минимум существует и единственный, и его находит метод Ньютона.

4Разбор

Удары с одного расстояния складываем: у них одинаковый признак, и в потерю они входят числом ударов и числом голов. Расстояний не больше 10⁴, так что шаг Ньютона дешёвый.

Два приёма делают Ньютона надёжным. Первый — центрировать и масштабировать признак: считать по u = (x − x̄) / s, а в конце пересчитать w = c / s, b = a − wx̄. В двенадцатом тесте удары лежат около 500 метров, и без центрирования свободный член −290,9 и наклон 0,058 связаны так тесно, что система для шага Ньютона плохо обусловлена. Второй — поиск вдоль направления: если полный шаг увеличил потерю, делим его пополам, пока она не уменьшится. Без него Ньютон может перескочить минимум, когда кривая очень крутая, как в одиннадцатом тесте, где разделение испорчено единственным промахом.

Начать удобно с c = 0 и a = логит доли голов: это лучшая кривая без наклона. Останавливаемся, когда шаг меньше 10⁻¹³ относительно самих чисел.

На всей осени лучшая кривая — b = 0,1051, w = −0,01483 на дециметр, то есть шансы гола падают на 14 % с каждым метром. Из 1826 матчей сезона у 330 лучшей кривой нет: в 184 не было голов, в 132 все голы забиты ближе, чем били все промахи, в семи — наоборот, все голы дальше, и ещё в семи самый дальний гол и самый близкий промах — с одного расстояния.

4+Решение

5Сложность

O(n) на чтение и подсчёт, O(m) на шаг Ньютона для m различных расстояний; шагов — единицы, с поиском вдоль направления — десятки.

6Типичные ошибки

Не проверять разделение. Ньютон честно уменьшает потерю, коэффициенты растут, и через сотню шагов программа печатает огромные числа — или падает на переполнении. Ответа при этом нет.
Проверять только строгое разделение. Если гол и промах лежат на одном расстоянии на границе, строгого порога нет, но минимума всё равно нет: удары на пороге не мешают остальным становиться всё увереннее. Третий пример и седьмой тест.
Все удары с одного расстояния. Голы и промахи перемешаны, и кажется, что ответ есть, но масштаб признака нулевой: делить на s нельзя, а минимум — целая прямая в плоскости (b, w). Девятый тест.

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

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