Логистическая регрессия

Удар ногой с точки пенальти — не сам пенальти, а удар с игры, когда рядом защитники, — становится голом примерно в каждом пятом случае. С двадцати пяти метров — примерно в одном из тридцати. Откуда эти числа? В сезоне 2017/18 в пяти крупнейших футбольных чемпионатах нанесли 40 461 удар с игры, и про каждый известно, откуда били и чем всё кончилось. Но с каждой отдельной точки поля били считаные разы, и долю голов «по точкам» не посчитать. Логистическая регрессия сводит всё поле к четырём числам: складывает признаки удара с весами и превращает сумму в вероятность. Ниже — модель, обученная на осенней половине сезона. Коснитесь поля, чтобы «ударить» оттуда.

Тонкие линии соединяют точки с одинаковой вероятностью гола. Это не окружности вокруг ворот: с острого угла забивают реже, чем с того же расстояния по центру, и модель знает это из признака «угол, под которым видны ворота». Выберите модель с одним расстоянием — линии станут дугами окружностей с центром в середине ворот: никакой другой формы у неё быть не может. Нажмите «учить с нуля»: метод Ньютона начинает с нулевых весов, при которых вероятность везде 50 %, и за восемь шагов приходит к ответу, причём после пятого изменения уже не разглядеть. Кружок вокруг удара — проверка на живых данных: у точки пенальти модель даёт удару ногой 21,9 %, а из 513 ударов ногой за весь сезон в круге двух метров вокруг неё забиты 114, 22,2 %. График под полем проверяет модель на весне, которую она не видела: удары, которым она давала от 5 до 10 %, в среднем 7,4 %, весной стали голами в 7,2 % случаев.

Идея

У удара два исхода, гол и не гол, — запишем их как 1 и 0. Первое, что приходит в голову, — линейная регрессия: провести прямую через эти нули и единицы по расстоянию. Прямая наименьших квадратов по осенним ударам: «вероятность» = 0,2805 − 0,00957·d, где d — расстояние в метрах. Беда видна сразу: начиная с 29,3 метра «вероятность» отрицательна, а так далеко били 11 % ударов. Вблизи ворот хуже: на двух метрах прямая обещает 26 %, а с трёх метров и ближе забили 76 % ударов. Вероятность зажата между 0 и 1 и с расстоянием меняется совсем не по прямой: сначала падает круто, потом медленно сходит на нет.

Логистическая регрессия разжимает этот отрезок. Вместо вероятности p она смотрит на шансы p / (1 − p) — вероятности 0,2 соответствуют шансы 1 к 4, — а на шансы — через логарифм. Логит ln(p / (1 − p)) пробегает все числа от −∞ до +∞, и его уже можно приравнять взвешенной сумме признаков, не боясь выйти за границы. Обратно к вероятности ведёт сигмоида:

Логистическая регрессия предсказывает не исход, а логарифм его шансов — взвешенной суммой признаков. Сигмоида превращает сумму в вероятность от 0 до 1. Веса подбирают так, чтобы исходы, которые случились на самом деле, были как можно вероятнее: это то же самое, что сделать наименьшей логарифмическую потерю.

Признаков у нашей модели три: расстояние до середины ворот в метрах, угол, под которым видны ворота (в радианах), и удар головой (1 или 0). Обученная модель такая:

logit = -1.1172 -0.1066·metres +1.5816·angle -0.9216·header
odds of a goal: x0.899 a metre farther, x0.398 for a header

Веса читаются через шансы. Каждый метр прибавляет к логиту −0,1066, то есть умножает шансы на e^−0,1066 ≈ 0,899: на десять процентов меньше за метр, в любой точке поля. Удар головой умножает шансы на 0,398 — по сравнению с ударом ногой из той же точки шансы у удара головой в два с половиной раза ниже. Это не значит, что головой бить вредно: головой бьют после навесов, в борьбе, по летящему мячу, и признак «голова» отвечает за всё это сразу. Модель описывает удары такими, какие они бывают, а не то, что случилось бы, если бы тот же игрок в той же ситуации ударил иначе.

Где модель отвечает «гол», а где «не гол»? Выберите порог, например 20 %: где p ≥ 0,2, ответ «гол». Условие p ≥ 0,2 равносильно z ≥ logit 0,2, а z — линейная функция признаков, поэтому граница решения — гиперплоскость в пространстве признаков: в осях «расстояние — угол» это прямая. На поле она изогнута, потому что сами признаки — нелинейные функции места удара. Так линейная по весам модель рисует кривые границы: всё зависит от того, какие столбцы ей дать.

Чем мерить промах

Модель с весами w назначает каждому удару вероятность гола p_i. Насколько она согласна с тем, что было на самом деле? Если удары независимы, вероятность увидеть именно такой сезон по этой модели — произведение p_i по всем голам и 1 − p_i по всем промахам. Хорошие веса делают это произведение большим. Перемножать двадцать тысяч чисел меньше единицы неудобно — произведение быстро станет меньше любого числа double, — поэтому берут логарифм, меняют знак и делят на число ударов:

где q_i — вероятность, которую модель дала тому, что случилось: p_i для гола и 1 − p_i для промаха. Это логарифмическая потеря, она же перекрёстная энтропия. Слагаемое −ln q_i — мера удивления модели исходом, с которой знакомит глава «Царицы наук» об информации. Сравните её с квадратичной потерей (p − y)², привычной по линейной регрессии, на ударе, который стал голом:

Квадратичная потеря ограничена единицей: модели всё равно, назвала она случившийся гол маловероятным или невозможным. Логарифмическая растёт без предела — за уверенность, которой не было, приходится платить. Но главная разница видна, когда веса ищут спуском. Производная логарифмической потери удара по его логиту z — просто p − y: насколько модель промахнулась. У квадратичной — 2(p − y)·p(1 − p), и множитель p(1 − p) почти ноль как раз там, где модель уверена. Уверенная и неправая модель почти не получает сигнала, что надо меняться.

Посмотрите на это вживую. Здесь модель проще — одна кривая по расстоянию, логит = b + w·(расстояние − 20 м)/10 м, — и у неё всего два веса, так что все возможные модели помещаются на плоскости. Цвет — рельеф потери, крестики — дно каждой потери. Из начальной точки градиентный спуск с одним и тем же шагом идёт по обеим потерям; под плоскостью — кривые, которые получаются по дороге, поверх настоящей доли голов на каждом метре.

Старт выбран нарочно плохой: b = −6, w = 6 — модель, по которой чем дальше удар, тем он опаснее: у самых ворот голов не бывает вовсе, а с 30 метров забивают через раз. По логарифмической потере спуск приходит ко дну за 39 шагов. По квадратичной он сначала быстро скатывается к модели «голов не бывает»: вероятность около нуля на любом расстоянии. Там её потеря равна доле голов, 0,1019, а градиент почти исчезает, потому что везде p(1 − p) ≈ 0. На этом плато спуск ползёт тысячи шагов и доходит до дна только на 7896-м. Коснитесь плоскости в других местах: по логарифмической потере спуск приходит быстро отовсюду, по квадратичной — по-разному, смотря как далеко старт от плато.

Есть и вторая разница: крестики стоят в разных местах. Это два разных ответа на вопрос «какая кривая лучше». Квадратичная потеря рисует кривую круче (w = −1,92 против −1,48). Ответ логарифмической потери — это метод максимального правдоподобия, и у него есть свойство, о котором следующий раздел.

Квадратичная потеря после сигмоиды выпуклой быть не может, и для этого даже не нужно ничего считать: она заключена между 0 и 1 на всей плоскости весов, а выпуклая функция, ограниченная сверху на всей плоскости, обязана быть постоянной. Значит, у неё есть плато и склоны, а на других данных и ложные ямы: Петер Ауэр, Марк Хербстер и Манфред Вармут в 1995 году построили примеры, где у одного нейрона с сигмоидой и квадратичной потерей локальных минимумов экспоненциально много по числу признаков. Прямая наименьших квадратов из начала статьи и спуск с двух стартов по обеим потерям — в одной программе:

Почему вероятностям можно верить

У логарифмической потери есть свойство, которого нет у прямой и у многих других моделей. В точке минимума все производные равны нулю, а производная потери по весу w_j — это Σ_i (p_i − y_i)·x_ij. Значит, у обученной модели

для каждого столбца j. Возьмём столбец единиц, при свободном члене w₀: сумма вероятностей по всем ударам равна числу голов. Возьмём столбец «голова»: сумма вероятностей по ударам головой равна числу голов головой. Модель не может систематически завышать или занижать ни в целом, ни в группе, которую выделяет её признак. Это не везение и не настройка, а следствие условия минимума:

autumn: expected goals 2094.0000, scored 2094

Такое согласие предсказанных вероятностей с частотами называют калибровкой. Проверяют её на данных, которых модель не видела: прогнозы раскладывают по корзинам и в каждой сравнивают среднее предсказание с долей голов. Вот весна, 19 912 ударов:

predicted   shots  goals  expected  scored
0.00-0.05    7103    190      2.8%    2.7%
0.05-0.10    5664    410      7.4%    7.2%
0.10-0.20    4822    725     13.8%   15.0%
0.20-0.30    1276    348     24.1%   27.3%
0.30-0.50     700    283     38.2%   40.4%
0.50-1.00     347    221     64.7%   63.7%

Удары, которым модель давала в среднем 2,8 %, стали голами в 2,7 % случаев, а удары с прогнозом 64,7 % — в 63,7 %. В середине весна чуть удачливее прогноза: по модели ожидалось 2081,8 гола, забито 2177. Это не нарушение свойства — оно выполняется на тех данных, на которых модель училась, — а напоминание, что весна не обязана быть похожей на осень: весной забивали 10,9 % ударов против 10,2 % осенью. Как одним числом поправить модель на новый сезон, разбирает вторая задача статьи.

Калибровка и делает логистическую регрессию рабочей лошадкой там, где важна сама вероятность, а не только ответ «да или нет». В поисковой рекламе вероятность клика по объявлению вместе со ставкой рекламодателя решает, что показать и в каком порядке; инженеры, описавшие такую систему в 2013 году, прямо пишут, что без точных и откалиброванных вероятностей аукцион не работает. В 2005 году Александру Никулеску-Мизил и Рич Каруана сравнили вероятности десяти методов обучения на восьми задачах: логистическая регрессия, нейросети и бэггинг деревьев оказались хорошо откалиброваны с самого начала, а наивный Байес из-за своего допущения о независимости признаков сдвигал вероятности к 0 и 1. А для методов, чьи оценки откалиброваны плохо, есть простое лекарство — метод Платта: логистическая регрессия с одним признаком, выходом исходного классификатора.

Условие минимума обещает согласие в целом и по каждому столбцу, но не в каждой корзине. Выберите в первой сцене модель по одному расстоянию: удары, которым она даёт от 30 до 50 %, в среднем 34,8 %, весной забиты в 47,8 % случаев. Одна логистическая кривая по расстоянию не может быть сразу крутой у самых ворот и пологой вдали, и у ворот она занижает. Калибровка в корзинах — проверка того, что модели хватает признаков: с углом и головой самая далёкая от диагонали корзина расходится с жизнью на три процентных пункта, 24,1 против 27,3 %.

Код

Минимум логарифмической потери формулой не записать, но функция выпуклая и гладкая, и метод Ньютона находит его за несколько шагов. Шаг Ньютона — это минимум квадратичного приближения потери: нужны градиент g = Σ(p_i − y_i)x_i и матрица вторых производных H = Σp_i(1 − p_i)x_ix_i^T, а затем решение системы Hδ = g — для четырёх признаков это система 4 × 4, которую решает метод Гаусса. Заметьте, что это нормальные уравнения взвешенной задачи наименьших квадратов с весами p_i(1 − p_i). Поэтому в статистике метод называют итеративно перевзвешенными наименьшими квадратами, IRLS: каждый шаг — линейная регрессия со своими весами строк.

Три детали в листинге важнее, чем кажутся. Сигмоида считается двумя формулами — для z ≥ 0 и z < 0, — иначе exp(-z) переполнится на большом отрицательном z. Потеря считается через softplus(z) = ln(1 + e^z) = max(z, 0) + ln(1 + e^−|z|), а не через логарифм вычисленной вероятности: при z = 40 вероятность 1 − σ(z) в double уже ноль, а честная потеря — 40. Об этом первая задача. И третья: ударов осенью 20 549, а разных сочетаний «точка, голова» — 2664. У ударов из одной точки одинаковые признаки, поэтому строку с n ударами и g голами можно учесть один раз с весом: в градиент она даёт (n·p − g)·x, в матрицу — n·p(1 − p)·xx^T. Работы почти в восемь раз меньше, а ответ тот же.

Вывод начинается с хода обучения:

step 1: log loss 0.693147, largest change 2.0e+00
step 2: log loss 0.316471, largest change 4.4e-01
step 3: log loss 0.283604, largest change 6.4e-01
step 4: log loss 0.278656, largest change 3.3e-01
step 5: log loss 0.278264, largest change 3.4e-02
step 6: log loss 0.278264, largest change 3.5e-04
step 7: log loss 0.278264, largest change 3.8e-08
step 8: log loss 0.278264, largest change below 1e-12

Первая строка — нулевые веса: вероятность 1/2 у каждого удара и потеря ln 2 = 0,693. Последние четыре шага показывают, за что любят метод Ньютона: изменение 3,4·10⁻² → 3,5·10⁻⁴ → 3,8·10⁻⁸ → меньше 10⁻¹². Число верных знаков удваивается с каждым шагом — это квадратичная сходимость, та же, что у метода Ньютона для корней уравнения: здесь он ищет корень градиента. В конце листинг сравнивает модели с разными столбцами:

columns                     autumn  spring
distance                    0.2872  0.3030
angle                       0.2892  0.3053
distance + angle            0.2834  0.2995
distance + angle + header   0.2783  0.2922

Модель «на любой удар 10,2 %» получает на весне потерю 0,3454. Одно расстояние снимает её до 0,3030, угол добавляет ещё немного, голова — заметно больше. На осени, где модель училась, потери ниже, чем на весне, у всех четырёх моделей: проверять надо на данных, которых модель не видела.

Сколько это стоит

Шаг Ньютона для n строк и d признаков стоит O(n·d²): каждая строка добавляет в матрицу H все d² попарных произведений своих признаков. Ещё O(d³) уходит на решение системы. Памяти нужно O(d²) на матрицу, а сами строки можно читать потоком: за проход копятся только g и H. Шагов обычно меньше десяти, потому что сходимость квадратичная. Шаг градиентного спуска дешевле, O(n·d), — нужен только градиент, — но шагов требуется на порядки больше, и их число зависит от того, насколько вытянут рельеф потери.

Наклоны на логарифмических осях — около единицы у шага спуска и около двух у шага Ньютона: при восьми признаках шаг Ньютона дороже в несколько раз, при ста двадцати восьми — почти в сто. Для модели xG с четырьмя признаками это неважно: восемь шагов Ньютона по 2664 строкам — доли секунды даже на Python. Но в рекламе и в текстах признаков бывают миллионы — каждое слово и каждая пара «запрос, объявление» — и матрица d × d не помещается ни в какую память. Там работают методы, которые обходятся без неё: L-BFGS помнит несколько последних шагов и то, как при них менялся градиент, и по ним приближает кривизну (это решатель scikit-learn по умолчанию), а стохастический спуск идёт по одной строке или пачке строк за раз. Система для рекламы из статьи 2013 года учится именно так — онлайн, по потоку показов, вариантом спуска FTRL-Proximal, с отдельной длиной шага для каждого признака.

Когда лучшего ответа нет

Попробуйте обучить модель по расстоянию на одном матче. В одном из весенних матчей было 18 ударов: два гола — с 4,7 и 6,3 метра, а все шестнадцать промахов — с 12,9 метра и дальше. Кривая, которая падает с единицы до нуля где-то между 6,3 и 12,9 метра, объясняет этот матч идеально, и чем круче её спуск, тем меньше потеря. Нуля потеря не достигает ни при каких конечных весах — она лишь стремится к нему, когда наклон растёт до бесконечности. Ньютон будет шагать вечно, а веса — расти.

Такую ситуацию называют разделимостью: есть гиперплоскость, по одну сторону которой только голы, а по другую только промахи. Альберт и Андерсон в 1984 году показали, что конечного минимума нет и при квазиполном разделении, когда на самой гиперплоскости лежат и голы, и промахи, а минимум существует и единствен, только когда голы и промахи перекрываются. В одном признаке это видно по четырём числам: ближайший и дальний гол, ближайший и дальний промах. Из 1826 матчей сезона лучшей кривой по расстоянию нет у 330: в 184 матчах не было голов, в 132 все голы забиты ближе всех промахов, в семи — дальше всех, и ещё в семи самый дальний гол и самый близкий промах нанесены с одного расстояния. Об этом третья задача статьи.

На целом сезоне четырём весам такое не грозит. Но стоит дать модели много признаков, и разделение возвращается по частям. Разрежем поле на клетки 4 × 4 метра и дадим каждой клетке свой вес: логит = b + w_c. Это та же логистическая регрессия, только признаки — индикаторы «удар из клетки c». В клетке, откуда осенью ни разу не забили, лучший вес — минус бесконечность: модель уверена, что оттуда не забивают. Первый же весенний гол из такой клетки обходится ей в бесконечную потерю.

Лекарство — штраф L2: к потере прибавляют λ/2·Σw_c². Теперь у каждой клетки есть причина не уходить далеко от общего b, и тем сильнее, чем меньше в ней ударов: клетке с двумя ударами нечем перевесить штраф, а клетке с тысячей — есть. Потеря со штрафом строго выпукла и растёт во все стороны, поэтому её минимум существует всегда, лишь бы среди ударов были и голы, и промахи.

Подвигайте λ. При λ = 0 клетки — это просто доли голов, и красные рамки отмечают «невозможные» клетки, из которых весной забили: на ста матчах осени таких 35. Небольшой штраф уже спасает модель, а λ около 0,5 даёт лучшую потерю на весне. Если штрафовать слишком сильно, все клетки сливаются в одну константу. Переключите число матчей: чем больше данных, тем меньше значит штраф и тем ниже вся кривая.

first 100 matches: 2263 shots in 107 cells, 58 cells without a goal; spring scores in 35 of them
  lambda 0: inf | 0.01: 0.3329 | 0.1: 0.3193 | 0.5: 0.3143 | 2: 0.3169 | 10: 0.3300 | 100: 0.3444 | 1000: 0.3468
first 909 matches: 20549 shots in 133 cells, 49 cells without a goal; spring scores in 10 of them
  lambda 0: inf | 0.01: 0.3029 | 0.1: 0.3021 | 0.5: 0.3017 | 2: 0.3019 | 10: 0.3057 | 100: 0.3273 | 1000: 0.3427

И главный урок этой сцены: даже на всей осени и с лучшим λ сто тридцать три клетки дают на весне 0,3017, а формула из расстояния и угла — 0,2995 тремя числами. Формуле хватает и первых ста матчей: обученная на них, она получает 0,3004 — сцена показывает это пунктиром. Знание о том, как устроен удар, оказалось лучшим штрафом из возможных: оно не даёт модели подстраиваться под случайности. Штраф подбирают по отложенным данным, а не по тем, на которых учились: на обучающих данных меньший штраф всегда выглядит лучше.

Чего модель не знает

• Граница — плоскость в признаках. Логистическая регрессия разделяет ответы гиперплоскостью, и всё, что сложнее, нужно заложить в признаки. Модель по одному расстоянию рисует на поле только окружности; угол — признак, придуманный человеком, — дал ей форму настоящих линий. Если вклад одного признака зависит от другого (удар головой издалека безнадёжнее, чем вблизи), нужен столбец-произведение. Когда признаки придумывать некому, берут модели, которые строят их сами: деревья и нейросети.
• Не всё видно в данных. У модели нет защитников, вратаря и того, как пришёл мяч. Пенальти бьют с той же точки, с которой удар ногой с игры по нашей модели забивают в 21,9 % случаев, — а в тех же данных Wyscout из 541 пенальти пяти чемпионатов забито 393, 73 %. Модель усредняет всё, чего не видит, по тем ситуациям, которые были в обучающих данных, и для другой ситуации её ответ неверен.
• Связь — не причина. Вес «головы» говорит, что удары головой забивают реже, но не говорит, что было бы, ударь игрок ногой: это были бы другие удары.
• Больше двух ответов. Если исходов несколько — какая из десяти цифр написана, — вместо сигмоиды берут softmax: у каждого класса своя взвешенная сумма, и вероятности пропорциональны их экспонентам. Потеря та же, −ln вероятности верного ответа. Так устроен выходной слой сети, которая читает цифры в главе курса о машинном обучении; логистическая регрессия — это такая сеть без скрытых слоёв.

История

Сама кривая старше статистики. В 1838 году Пьер Франсуа Ферхюльст опубликовал короткую заметку о том, как растёт население: сначала почти как экспонента, потом всё медленнее, упираясь в предел. В статье 1845 года он назвал эту кривую логистической и нарисовал её рядом с логарифмической — так тогда называли экспоненту. Работу забыли, и в 1920 году Рэймонд Перл и Лоуэлл Рид пришли к той же кривой заново, тоже изучая рост населения.

В статистику вероятностей кривая пришла из биологических опытов: какая доля подопытных насекомых или животных погибнет при той или иной дозе яда. В 1934 году Чарльз Блисс предложил для этого пробит — модель с нормальным распределением. В 1944 году Джозеф Берксон предложил взять вместо него логистическую функцию и по аналогии с пробитом назвал её логитом. Логит считался проще пробита, но Берксон заодно спорил с методом максимального правдоподобия, и спор с Рональдом Фишером и его сторонниками растянулся на десятилетия. Регрессию для двоичного исхода с несколькими признаками описал Дэвид Кокс в 1958 году, а в 1972 году Джон Нелдер и Роберт Веддерберн включили её в общую схему обобщённых линейных моделей и описали способ решения, которым до сих пор пользуются R и statsmodels, — итеративно перевзвешенные наименьшие квадраты. Вариант с несколькими исходами связал с теорией выбора Дэниел Макфадден, и в 2000 году он получил за работы о дискретном выборе Нобелевскую премию по экономике.

Футбольные удары логистической регрессией считали ещё в 1997 году: Ричард Поллард и Чарльз Рип оценили вероятность гола по расстоянию, углу и обстановке удара на 410 атаках, закончившихся ударом, в 22 матчах чемпионата мира 1986 года. Сегодня такие модели называют ожидаемыми голами, xG, и их часто показывают в статистике матча рядом со счётом.

Задачи

Первая задача — о том, как честно посчитать логарифмическую потерю, когда модель очень уверена. Вторая — о калибровке: как одним числом поправить модель, обученную на прошлом сезоне. Третья — о разделимости: когда у логистической регрессии вообще есть ответ.