Разбираемся в ML без воды: от базы до Attention. Часть 6: Логистическая регрессия

Итак мы обсудили задачу классификации и метрики качества классификационных моделей.

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

И первый кандидат у нас:

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

Логистическая регрессия (logistic regression) — это один из самых базовых и важных алгоритмов классификации, который учится проводить границу между классами и оценивать вероятность того, к какому классу принадлежит объект.

Сразу избавимся от путаницы: да, несмотря на то, что логистическая регрессия решает задачу классификации, в её названии есть слово «регрессия».
Так получилось потому, что модель не говорит: «этот объект принадлежит классу A и точка». Вместо этого она выдаёт вероятность принадлежности объекта к классу A.

Грубо говоря, результат работы модели логистической регрессии можно интерпретировать так: «с вероятностью 0.74 объект принадлежит классу A. Дальше уже решайте сами, относить его к этому классу или нет».

Теперь разберёмся, каким образом логистическая регрессия вообще получает эти вероятности, а уже потом поймём, что делать с этим самым «дальше решайте сами».

Мы уже имеем опыт работы с классом линейных функций. поэтому логично не изобретать велосипед заново, а использовать то, что уже хорошо нам знакомо.
Но при таком подходе у нас возникнет одна проблема: полученный таким методом результат — это число из $\mathbb{R}$ . Но нам нужно число на отрезке , чтобы заявить, что оно является вероятностью. Причем, нужно чтобы большие значения соответствовали «почти 1», а маленькие — «почти 0».

То есть нам нужна функция, которая:

«сжимает» всю числовую прямую;
не теряет порядок значений.

и одной из таких функций является сигмоида:

$\sigma(x) = \frac{1}{1+e^{-x}}$

Теперь, если мы пропустим результат линейной модели через сигмоиду:

$p(x) := p(x) := \sigma(\langle \omega, x \rangle) = \frac{1}{1+e^{-\langle \omega, x \rangle}}$

то получим вероятность принадлежения объекта к классу 1. Обозначим её как .

Теперь у нас есть модель, которая для каждого объекта выдаёт вероятность
Но пока непонятно, как эта модель должна «понимать», что она ошибается.

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

Значит нам нужна функция, которая будет штрафовать модель в зависимости от того, насколько её предсказанная вероятность отличается от истинного ответа.

Причём важно, чтобы этот штраф вёл себя таким образом:

если объект относится к классу 1, и модель даёт вероятность 0.99 — штраф должен быть маленьким;
если объект относится к классу 1, а модель дала вероятность 0.1 — штраф должен быть большим;
аналогично для класса 0

И такая функция действительно существует — она называется log-loss (или cross-entropy).
Но до того, как перейти к ней, вернемся к математике.

Метод максимального правдоподобия

Временно отложим всё, что говорили о машинном обучении и поймем что такое метод максимального правдоподобия (ММП, Maximum Likelihood Estimation или MLE).

Представим, что у нас есть неидеальная монета. Пусть при подбрасывании шанс выпадения орла равняется $\theta$ . Мы подбросили монету 100 раз и получили результат: 72 раза выпал орёл, 28 раз — решка.

Вероятность такого результата при фиксированном $\theta$ равна:

$p(\theta) = \theta^{72}(1-\theta)^{28}$

Итак, если упростить идею — метод максимального правдоподобия заключается в том, что мы доверяем наблюдаемым данным и говорим: «раз произошло вот так, то это наиболее правдоподобный вариант», поэтому подбираем такое значение $\theta$ , при котором вероятность наблюдаемого результата максимальна:

$\theta^* = \arg\!\max_{\theta}\theta^{72}(1-\theta)^{28}$

Это задача максимизации функции правдоподобия.
В общем виде она выглядит так:

$\theta^* = \arg\!\max_{\theta}L(\theta),$

где

$L(\theta) = \prod_{i=1}^n p_{\theta}(X_i)$ — функция правдоподобия (likelihood function);

$p_{\theta}(x)$ — плотность (или вероятность) распределения с параметром $\theta$ ;

$X_1, \dots, X_n$ — выборка независимых наблюдений.

В математике при виде произведения часто берут логарифм. Максимизировать или минимизировать произведение неудобно, а после логарифмирования получается сумма, с которой обычно проще работать. Случай с максимизацией функции правдоподобия не является исключением. Обычно делается так:

$\theta^* = \arg\!\max_{\theta}\log(L(\theta)) = \arg\!\max_{\theta}\sum_{i=1}^{n}\log(p_{\theta}(X_i)),$

В частности, для нашего примера с подбрасыванием монетки получим:

$\theta^* = \arg\!\max_{\theta}(72\log(\theta) + 28\log(1-\theta))$

Откуда, приравняв производную к нулю, получим $\theta^* = 0.72$ .

Теперь поймем зачем нам ММП.

Используя ММП, мы превращаем статистическую задачу в задачу максимизации. А любую задачу максимизации можно эквивалентно переписать как задачу минимизации: достаточно вместо «максимизировать » рассматривать «минимизировать «.

А что мы минимизируем в ML? Конечно же, функцию потерь.

Log-loss

Если взять отрицательный логарифм правдоподобия и просто переписать его в терминах машинного обучения, мы получим то, что называется log-loss. Разберем это пошагово.

Для начала обозначим $\theta$ как $\omega$ , а выражение, которое мы минимизируем, как $\mathcal{L}$ (на самом деле это функция потерь).

Тогда функция потерь имеет вид:

$\mathcal{L}(\omega) = -\sum_{i=1}^{n}\log(p_{\omega}(X_i))$

Наша задача — найти набор весов который минимизирует эту функцию:

$\omega^* = \arg\!\min_{\omega}\mathcal{L}(\omega)$

В задаче бинарной классификации выборка обозначается через пары , где $y_i \in \{0,1\}$ . Тогда модель задает вероятность $p_{\omega}(y_i | x_i)$ , которая в бинарном случае может быть переписана как

$p_{\omega}(y_i | x_i) = p_i^{y_i}(1-p_i)^{1-y_i},$

где $p_i = p_{\omega}( y = 1 | x_i)$ .

подставив данное выражение в формулу выше получим:

$\mathcal{L}(\omega) = -\sum_{i=1}^{n}\log( p_i^{y_i}(1-p_i)^{1-y_i})$

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

$\mathcal{L}(\omega) = -\sum_{i=1}^{n}\bigg{(}y_i\log( p_i) + (1-y_i)\log(1-p_i)\bigg{)}$

Кстати, если учесть факт, что — вероятность (т.е. число на отрезке ), а $y_i \in \{0,1\}$ , то можно заметить, что выражение под суммой меньше или равно нуля, значит, с учетом знака минус $\mathcal{L}(\omega) \ge 0$ . Значит, у нас не возникнет проблема «спасите, лосс отрицательный».

Остаётся одно — подставить в формулу сигмоиду, как мы уже обсуждали ранее.
Таким образом мы получаем финальный вид функции потерь для логистической регрессии:

$\mathcal{L}(\omega) = -\sum_{i=1}^{n} \left( y_i \log \sigma(\langle \omega, x_i \rangle) + (1 - y_i)\log\left(1 - \sigma(\langle \omega, x_i \rangle)\right) \right)$

Заметим одну важную деталь: получилось так, что мы не изменили наше пространство функций $\mathbb{F}$ Мы по-прежнему остаёмся в классе линейных функций, просто оборачиваем их в сигмоиду.

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

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

Решение задачи логистической регрессии

Теперь, имея loss, т.е. постановку задачи, попробуем найти его решение.

Попробуем пройтись аналитическим методом. Подставим сигмоиду в формулу лосс функции и упростим. У нас получится:

$\mathcal{L}(\omega) = \sum_{i=1}^n \left( \log(1 + e^{-z_i}) - y_i z_i \right),$

где $z_i = \langle \omega, x_i \rangle$ .

Если мы попробуем использовать условие стационарной точки $\nabla_\omega\mathcal{L}(\omega)=0$ , получим Уравнение:

$\sum_{i=1}^{n}(\sigma(\langle \omega, x_i \rangle) - y_i)x_i = 0,$

где у нас полный комплект неприятностей. И нелинейность и экспонента и $\omega$ внутри нелинейной функции. Одним словом — мрак.
Не вдаваясь в подробности, такая система в общем случае не имеет аналитического решения в замкнутом виде. Поэтому приходится отказываться от попыток получить явную формулу для $\omega$ .

Поскольку прямое решение нам ничего не дало, вернёмся к градиентному спуску.

Идея градиентного спуска остается прежней: мы начинаем с некоторого начального значения $\omega^{(0)}$ и постепенно двигаемся в сторону уменьшения функции потерь.

Параметры будут обновляться таким образом: $\omega^{(t+1)}=\omega^{(t)}−\eta\nabla_\omega \mathcal{L}(\omega^{(t)})$ .

Мы уже вычислили градиент. Подставим его в формулу обновления весов. И получим окончательный вид:

$\omega^{(t+1)}=\omega^{(t)}−\eta\sum_{i=1}^{n}(\sigma(\langle \omega^{(t)}, x_i \rangle) - y_i)x_i$

То есть, обновление весов происходит за счёт корректировки, пропорциональной ошибке предсказания вероятности относительно истинного класса, умноженной на входные признаки.
Это означает:

если модель переоценила вероятность — веса уменьшаются;
если недооценила — увеличиваются.

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

Остаются два вопроса: на что влияет выбор начальной точки $\omega^{(0)}$ и сойдётся ли градиентный спуск при данном функционале?

Для ответа на оба вопроса можно опираться на ключевое свойство — Функция $\mathcal{L}(\omega)$ является выпуклой по $\omega$ .

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

Но почему именно сигмоида?

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

сжимает всю числовую прямую;
не теряет порядок значений.

Таких функций в мире много. Поэтому давайте избавимся от «магического» появления сигмоиды и дадим ей более разумное объяснение.

Начнем с того, что вместо рассмотрении вероятности p мы рассмотрим так называемые odds(шансы):

$\frac{p}{1-p}$ , а точнее их логарифм (log-odds): $\log\frac{p}{1-p}$ . Это мера того, насколько модель

«склоняется» к классу 1.

Мы предполагаем, что не сама вероятность зависит линейно от признаков, а её лог-оддсы:

$\log\frac{p}{1-p} = \langle \omega, x \rangle \;=: z$

Почему именно так

Есть, по крайней мере, три причины:

1. Линейность в :

$\langle \omega, x \rangle$ — это самый простой способ описать зависимость от признаков.

2. Вероятность нельзя моделировать линейно

Если бы мы писали: $p(x) = \langle \omega, x \rangle$ , то могли бы выйти за пределы , тем самим нарушив смысл вероятности

3. Log-odds «растягивают» вероятность

Функция:

$p \mapsto \log \frac{p}{1-p}$

переводит в всю $\mathbb{R}$

Решаем относительно :

$\frac{p}{1-p} = e^z$ $p = \frac{e^z}{1 + e^z}$

и упрощая, получаем:

$p = \frac{1}{1+e^{-z}} = \sigma(z)$

Вот откуда на самом деле возникает сигмоида. Это следствие линейной модели для log-odds.

Cross-entropy

Выше у меня была фраза

И такая функция действительно существует — она называется log-loss (или cross-entropy).

Теперь ответим на вопрос: что такое cross-entropy и почему это то же самое, что и log-loss?

Начнем с понятия энтропии.

В теории информации энтропия распределения определяется как

$H(p) = -\sum_i p_i \log p_i$

Она измеряет степень неопределенности распределения. Чем более «размазаны» вероятности, тем больше энтропия.

Маленький пример

Опять вернемся к подбрасыванию монетки. Если у нас классическая моентка и вероятности равны по 0.5, то энтропия у нас равна $-(0.5\log(0.5) + 0.5\log(0.5)) = 1$

Далее, нам дали другую монетку, на которой орел выпадает с вероятность 0.9.

В таком случае энтропия будет равна $-(0.9\log(0.9) + 0.1\log(0.1))$ — (примерно 0.47).

Как видим, энтропия в первом случае высокая (максимальное возможное значение). И, действительно, ситуация вообще не предсказуемая, а во втором случае энотропия уже 0.47 и мы более-менее уверенно можем предположить исход броска.

Теперь предположим, что существует некоторое истинное распределение , а модель предсказывает распределение . Введем величину:

$H(q,p)= -\sum_i q_i \log p_i,$

которая как раз называется cross-entropy.

В формуле энтропии вероятности и внутри логарифма, и снаружи берутся из одного распределения, а в cross-entropy: снаружи стоит истинное распределение , а внутри логарифма — распределение модели .

В задаче бинарной классификации истинные метки задаются как, а модель предсказывает

Подставляя это в формулу cross-entropy, получаем:

$H(q,p) = -\sum_{i=1}^{n} \left( y_i \log p_i + (1-y_i)\log(1-p_i) \right)$

Что в точности и есть log-loss.

Таким образом, log-loss можно интерпретировать сразу с двух сторон: и как отрицательное лог-правдоподобие и как cross-entropy между истинным распределением и распределением модели.

Заключение

Главные плюсы логистической регрессии — интерпретируемость и устойчивость. Модель хорошо работает в задачах, где классы можно достаточно неплохо разделить линейной границей, а также в ситуациях, когда важно понимать влияние признаков на результат.

Кроме того, благодаря выпуклости log-loss, обучение логистической регрессии является относительно стабильной задачей.

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

В следующей части мы рассмотрим SVM — модель, которая подходит к задаче классификации с другой стороны и вместо вероятностной интерпретации делает акцент на геометрии разделяющей границы и максимизации отступа между классами.

ссылка на оригинал статьи https://habr.com/ru/articles/1040682/