Логистическая регрессия: главное – не перепутать

Это статья из цикла про основы машинного обучения.

• Часть 1. О машинном обучении простым языком
• Часть 2. Линейная регрессия проще некуда
• Часть 3. О чем думают деревья?
• Часть 4. Логистическая регрессия: главное – не перепутать

В прошлой статье мы начали рассматривать задачу классификации. И разобрали, наверное, самый интуитивно понятный алгоритм – решающие деревья. В этой статье мы рассмотрим применение регрессии для задач классификации.

Что не так с деревьями?

При чтении прошлой статьи могло показаться, что решающие деревья – это идеальный вариант для классификации. Действительно, они умеют находить сложные зависимости, их внутренняя логика понятна, а процесс обучения достаточно быстрый. Но на самом деле они не идеальны. Есть несколько фундаментальных недостатков.

В первую очередь – это переобучение. Дерево слишком хорошо запоминает мелкие детали, но при этом не может понять более глубоких зависимостей. В итоге дерево показывает великолепные результаты на знакомых данных, но качество резко падает, как только дерево сталкивается с данными, которых в обучающей выборке не было. В итоге приходится искусственно ограничивать рост дерева, что приводит к ухудшению работы в целом, но это единственный способ заставить дерево не «зазубрить» правильные ответы, а именно постараться решить задачу в общем виде.

Во-вторых, дерево – это жадный алгоритм. Оно принимает лучшее решение для каждого шага, а не в общем виде. При этом в какой-то момент построение дерева принудительно завершается в рамках борьбы с переобучением, что приводит к неполному решению задачи.

И, в-третьих, дерево имеет фундаментальные ограничения по типу зависимостей. Оно очень хорошо работает с отдельными «островками» данных, но крайне плохо обрабатывает непрерывные зависимости. Это связано с тем, что дерево разбивает данные вдоль осей координат.

На рисунках выше показаны удачный и неудачный случаи распределения данных. На первом рисунке все хорошо, всего три разбиения. А вот на втором их уже семь. Хотя, если посмотреть на данные, видно, что хватило бы одной диагональной линии, однако решающее дерево так не умеет, оно строит разбиения только вдоль осей.

Как быть?

На самом деле есть несколько способов справиться с недостатками решающих деревьев. Первая группа способов подразумевает их улучшение. Один из вариантов – использовать не одно дерево, а несколько. Причем в момент обучения каждое дерево учится на своей части данных. В итоге получается множество («лес») разных деревьев. И, когда надо дать ответ, мы показываем данные каждому дереву по отдельности, а потом устраиваем голосование. Победивший результат мы и выдаем на выход. Такой подход (он называется «случайный лес» или «random forest») существенно снижает влияние переобучения. Этот метод используется в некоторых случаях даже сейчас, в эпоху доминирования нейросетей.

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

Второй способ решения проблемы – уйти от решающих деревьев и подобных им алгоритмических моделей.

Что там с регрессией?

Давайте вспомним, как работает линейная регрессия. Она работает очень просто: каждое входное значение умножается на соответствующий вес, все эти произведения суммируются, к сумме прибавляется смещение, и все это и есть результат:

Давайте попробуем использовать такой же подход для классификации. Что нам мешает это сделать? В первую очередь – диапазон выходных значений. Это регрессия, следовательно, выход модели – это любое число. Мы же решаем задачу классификации и ожидаем только два значения: 0 или 1.

Первым на ум приходит вариант просто выставить порог. Например, если выходное значение положительное – это 1, отрицательное – 0. Но пороговый подход будет крайне нестабильным. Например, минус одна тысячная дает один ответ, а одна тысячная – уже другой. Это значит, что все выходные значения будут сосредоточены очень близко к нулю, и малейшее изменение входных данных может повлиять на результат. Еще одна проблема, что пороговая функция не дифференцируема, то есть у нее нет производной. Производные очень важны при обучении любых регрессионных моделей, поэтому отсутствие производной – это очень серьезная проблема.

На самом деле лучший способ использовать регрессию для классификации – это каким-то образом привести значения из диапазона $\lbrack - \infty,\ + \infty\rbrack$ в диапазон $\lbrack 0,\ 1\rbrack$. Почему это сработает, ведь нам нужны всего два значения, а не диапазон? Дело в том, что непрерывное значение из диапазона $\lbrack 0,\ 1\rbrack$ можно рассматривать как вероятность одного из ответов. Например, если мы получили значение $0.6$, это можно интерпретировать как вероятность ответа 1 в 60%.

Это хорошо еще и тем, что порог мы можем задавать сами в зависимости от задачи. Например, представим себе систему, которая автоматически покупает акции на бирже, если считает их выгодными. В такой ситуации хотелось бы обойтись без лишнего риска, поэтому порог можно поставить повыше, например 90%. Это значит, что система купит акции только если будет очень уверена в их рентабельности.

В других ситуациях, напротив, лучше ставить более низкий порог. Представим себе систему, которая отслеживает переводы в банке и проверяет, не мошеннические ли они. В этом случае лучше сделать систему более чувствительной. Например, чтобы она срабатывала при 30% уверенности, что операция мошенническая. При этом не обязательно сразу блокировать перевод. Можно передать решение человеку. Таким образом, ничего важного не будет пропущено, а человек уже примет финальное решение.

Осталось понять, как нам сделать нужное преобразование диапазонов. Такое преобразование должно быть гладким, без разрывов и скачков, чтобы оно не мешало вычислению производных. На самом деле есть большое количество функций, которые могут в этом помочь, но самая распространенная из них – сигмоида или логистическая функция, которая и дала название этому методу классификации.

Разбираемся с сигмоидой

Сама функция выглядит очень просто:

Если значение $x$ стремится к минус бесконечности, знаменатель дроби, наоборот, устремляется в бесконечность, что дает значение всей функции очень близким к нулю. При очень больших значениях $x$ значение $e^{- x}$ устремляется к нулю, знаменатель близок к единице, как и итоговое значение функции. В итоге ее график выглядит так:

Видно, что функция мягко и без разрывов преобразует любое входное значение в диапазон от нуля до единицы.

Нам теперь осталось только применить эту функцию к результату регрессии и получить вероятность положительного ответа:

Как и в обычной линейной регрессии нам теперь нужно вычислить все коэффициенты $k_{i}$ и смещение $b$.

Обучаем

Любое обучение – это минимизация функции потерь между предсказанным результатом и реальным:

Точнее, мы минимизируем функцию не для одной пары значений, а сразу сумму всех пар:

Для линейной регрессии, где результаты были непрерывные, функция потерь была просто квадратом разности:

Здесь же у нас результат дискретный (только 0 или 1). Следовательно, нужно использовать другую функцию.

Здесь может появиться вопрос, а почему нельзя использовать квадрат разности? Ведь у нас на выходе вероятность, то есть обычное число. На этот вопрос сейчас будет ответить сложно, так как мы еще не знаем детали процесса обучения. Пока можно просто сказать, что при использовании квадрата разности обучение может происходить, но оно будет долгим, а результат может быть достаточно посредственным.

Для задачи классификации используется другая функция, а именно – бинарная кросс-энтропия. Эта функция выглядит более сложно, чем простая разность квадратов:

Несмотря на кажущуюся сложность, кросс-энтропия гораздо лучше работает для задачи классификации. В итоге нам нужно сделать сумму функций для каждой пары значений как можно меньше. Для этого нужно подобрать коэффициенты $k_{i}$ и $b$.

И вот тут нас ждут не очень хорошие новости. Дело в том, что, если простую линейную регрессию мы могли обучить очень быстро, решив одну систему уравнений, здесь аналитического решения нет. Это связано с тем, что наши формулы теперь нелинейные. Поэтому придется искать другие способы найти нужные коэффициенты. Такие способы есть, и их даже несколько. Мы рассмотрим самый популярный из них – градиентный спуск.

Давайте максимально упростим модель. У нас, как и в статье про регрессию останется только одна входная переменная $x$ и два коэффициента: $k$ и $b$. Ответ мы будем считать по формуле:

или

Теперь распишем функцию потерь:

Как уже говорилось выше, минимизируем мы не функцию потерь, а сумму функций потерь для всех наших данных:

Итоговое выражение выглядит достаточно страшно, и, как уже говорилось выше, аналитически не оптимизируется. Поэтому основная идея тут – не пытаться достичь минимума сразу, а делать много небольших шагов, постепенно приближаясь к минимуму.

Путешествие по поверхностям

Если визуализировать функцию потерь, мы увидим длинный узкий желоб. Дно этого желоба и есть минимум функции потерь:

Обратите внимание – минимум здесь – не точка, а линия. Это значит, что есть много пар $k$ и $b$, которые нас устраивают. Нужно найти любую из них.

Нам нужно спуститься со стены желоба (случайное место, где мы начинаем обучение) на его дно. По сути, нам нужно следовать следующему алгоритму:

1. Находим направление движения в сторону минимума
2. Делаем небольшой шаг в сторону минимума (меняем $k$ и $b$ на некоторую величину)
3. Повторяем шаги 1 и 2 пока не дойдем до минимума

В этом алгоритме и кроется главное отличие от того, что мы использовали для обычной линейной регрессии: там мы сразу аналитически находили параметры, для которых функция потерь находится в минимуме. А здесь мы начинаем со случайных значений и постепенно меняем параметры, приближаясь к решению. То есть, такой метод итеративный, мы многократно повторяем одни и те же действия, постепенно улучшая результат. Осталось понять, как найти направление на минимум.

И вот здесь на первый план выходят производные. Если вспомнить их свойства, то мы увидим, что частная производная по одному параметру показывает, насколько быстро растет функция при маленьком увеличении этого параметра. И вот здесь ключевая идея: нужно сделать шаг в противоположную сторону от роста. Что делать, если переменных несколько? В этом случае мы должны посчитать производные по каждой из переменных и изменить каждую переменную против роста ее производной. В нашем случае математически это будет выглядеть так:

Параметр $\rho$ в этой записи – это просто небольшое число (например, 0.01), которое мы добавляем, чтобы сделать шаг небольшим. Так как это число управляет скоростью шагов, а, следовательно – и скоростью обучения, его называют learning rate. Про то, как такое число подбирать и что от него зависит, кроме скорости обучения, расскажу позже.

Аналогично мы будем действовать, если параметров не два, а больше. В этом случае просто считаем производные по каждому из параметров. Вектор из таких производных называют градиентом, отсюда и название метода – градиентный спуск. Под спуском подразумевается движение в сторону минимума функции.

Осталось разобраться, а как понять, что мы уже пришли в минимум. Тут можно вспомнить, что в минимуме производные по всем параметрам станут равными нулю и мы остановимся. На самом деле такой подход обычно не работает. Дело в том, что чаще всего градиентный спуск перескакивает точку минимума, потом возвращается назад, снова перескакивает минимум, теперь уже в обратном направлении и так далее. Поэтому обычно на изменение производных смотрят менее строго. Чаще всего смотрят даже не на производные, а на саму функцию потерь $L$. Если после очередного шага она почти не изменилась ($\mathrm{\Delta}L < \ \varepsilon$), мы считаем, что находимся очень близко к минимуму и обучение можно заканчивать. Опять же, есть множество нюансов, но про них будет отдельная статья.

Считаем производные

Теперь, когда мы разобрались, как нам обучить логистическую регрессию, осталось только посчитать производные.

Нам нужно посчитать производные функции потерь по двум параметрам. Но, как мы уже успели убедиться, итоговое выражение достаточно внушительное, и считать производную будет достаточно сложно. Поэтому разумно будет разбить вычисление на части. Давайте посмотрим, из чего состоит итоговая функция.

Процесс умножения входных данных на веса и прибавления смещения называют сумматорной функций. Обозначим ее буквой $z$:

Далее к этому результату мы применяем сигмоиду. Этот процесс называют активационной функцией. Обозначим ее буквой $a$:

И в конце мы вычисляем функцию потерь между нашим предсказанием и правильным ответом. Саму функцию обозначим как $L$. В нашем случае:

Нам нужно посчитать две производные: $\frac{\partial L}{\partial k}$ и $\frac{\partial L}{\partial b}$. И тут мы, как и в статье про линейную регрессию, можем воспользоваться цепным правилом:

Аналогично и для $b$. Согласитесь, что считать производные по частям гораздо удобнее, чем целиком.

Начнем считать с последней функции:

Дополнительно приведем к общему знаменателю и упростим:

Теперь считаем производную сигмоидальной активации:

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

Что такое первая дробь? Это же наша исходная функция! Поэтому можем сделать такое преобразование:

Но и это еще не все. Преобразуем вторую часть:

Остался еще один трюк. К числителю прибавим и сразу же отнимем $e^{z}$:

Теперь последнее преобразование. Делим дробь на $e^{z}$. Это равносильно умножению числителя и знаменателя на $e^{- z}$:

Что мы видим? Снова нашу исходную функцию! В итоге производная сигмоиды полностью выражается через саму сигмоиду:

Но и на этом красота не заканчивается. Посчитаем теперь произведение двух производных, которые мы уже нашли:

В итоге от громоздкого выражения у нас осталась крохотная строчка. И почти все готово, чтобы посчитать итоговые производные. Осталось только посчитать производную сумматорной функции по $k$ и $b$:

Все готово. Итоговые формулы для производных:

Еще один очень приятный момент состоит в том, что если взять не одномерные входные данные, а многомерные, то почти ничего в формулах не изменится. Нужно будет просто посчитать еще несколько производных по формуле:

Долгожданный спуск

Теперь у нас есть все, чтобы вывести алгоритм обучения. Изначально коэффициенты $k$ и $b$ мы инициализируем случайными числами. Обычно числа берут достаточно маленькими, в пределах от нуля до одной сотой. Дальше начинается сам процесс обучения:

1. Для каждой пары входных данных и правильного ответа считаем производные по всем параметрам $k$ и $b$
2. Когда посчитано для всех примеров, усредняем каждую производную, то есть суммируем производные для каждого примера и делим на количество примеров
3. Делаем шаг градиентного спуска: $k_{i} = k - \ \rho \bullet \frac{1}{n} \bullet \sum_{}^{}{x_{ij}\left( a_{j} - y_{j} \right)}$. Аналогично для $b:b = b - \rho \bullet \frac{1}{n} \bullet \sum_{}^{}\left( a_{j} - y_{j} \right)$
4. Повторяем пункты 1-3 до тех пор, пока не дойдем до минимума (точнее, не окажемся рядом с ним)

После окончания обучения наша модель готова к использованию. Для этого мы сначала вычисляем взвешенную сумму:

А затем применяем сигмоиду:

Итоговое значение $\widehat{y}$ – это вероятность того, что класс объекта равен 1. Эту вероятность, как уже говорилось выше, мы можем интерпретировать по-разному в зависимости от задачи.

И снова проблемы

Несмотря на то, что логистическая регрессия кажется очень хорошим вариантов, она тоже не лишена проблем. С одной стороны, да, она лучше решающих деревьев в плане переобучения. Но с другой, у нее проблема ровно противоположная. Напомню, что решающие деревья очень хорошо работали с отдельными «островками» данных, но плохо обрабатывали непрерывные распределения. Здесь ситуация обратная.

Логистическая регрессия проводит ровно одну линию разделения, хоть и под любым углом. Таким образом, если данные можно разделить одной линией, логистическая регрессия будет работать идеально. А вот если такое разделение невозможно, обучиться не получится ни в каком случае.

На рисунке 2 показана хорошая для регрессии ситуация, данные линейно разделимы. А вот в первом случае как бы мы ни проводили линую, часть объектов всегда будет классифицирована неверно.

Что же делать в таком случае? В идеале нам хотелось бы провести всего одну линию, как в логистической регрессии, но при этом не прямую, а произвольной формы. Это бы позволило разделять любые данные, то есть решило бы проблемы как логистической регрессии, так и решающих деревьев.

И способ сделать так существует. Нужно всего лишь объединить несколько логистических регрессий: выходы одних должны быть входами других. Возможно, кто-то уже узнал в этой конструкции нейронную сеть. Но о нейронных сетях и том, как они обучаются, я расскажу в следующей статье.

Продолжение следует…