Логистическая регрессия и Деревья решений

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

3.1. Линейные классификаторы и Логистическая регрессия

От линейной функции к вероятности

Линейный классификатор строит решающую границу в виде гиперплоскости. Для объекта с признаками $x$ модель вычисляет линейную комбинацию:

$$ f(x) = w_1 x_1 + w_2 x_2 + ... + w_0 = w^T x $$

В простейшем случае класс предсказывается через знак функции: $$ \hat{y}_i = \text{sign}(f(x_i)) = \begin{cases} 1, & f(x_i) \geq 0 \ -1, & f(x_i) < 0 \end{cases} $$

Однако для многих задач важно получить не просто класс, а вероятность принадлежности к классу. Возникает проблема: значение $f(x)$ лежит в диапазоне $(-\infty, +\infty)$, а вероятность $p$ должна быть в диапазоне $[0, 1]$.

Чтобы преобразовать линейный отклик в вероятность, используется следующая цепочка рассуждений:

1. Рассмотрим вероятность положительного класса $p_+ = P(y=1|x)$.
2. Преобразуем вероятность в шанс (Odds Ratio): $$ OR = \frac{p_+}{1 - p_+} \in [0, +\infty) $$
3. Прологарифмируем шанс, чтобы получить диапазон $(-\infty, +\infty)$: $$ \log(OR) = \log\left(\frac{p_+}{1 - p_+}\right) = f(x) $$

Выразим вероятность $p_+$ из этого уравнения: $$ \frac{p_+}{1 - p_+} = e^{f(x)} \implies p_+ = e^{f(x)} - p_+ e^{f(x)} \implies p_+(1 + e^{f(x)}) = e^{f(x)} $$

Итоговая формула для вероятности (сигмоида): $$ p_+ = \frac{e^{f(x)}}{1 + e^{f(x)}} = \frac{1}{1 + e^{-f(x)}} = \sigma(f(x)) $$

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

Понятие отступа (Margin)

Для анализа качества классификации вводится понятие отступа (margin) на $i$-м объекте:

$$ M_i = y_i f(x_i) = y_i w^T x_i $$

где $y_i \in {-1, +1}$ — истинная метка класса.

Интерпретация отступа:

• $M_i > 0$ — объект классифицирован верно ($y_i = \hat{y}_i$)
• $M_i \leq 0$ — объект классифицирован неверно ($y_i \neq \hat{y}_i$)

Примеры:

Чем больше положительный отступ, тем более «уверенно» модель относит объект к правильному классу. Это понятие лежит в основе многих функций потерь, включая log loss.

Задача оптимизации: Log Loss

Для обучения модели необходимо подобрать веса $w$, максимизирующие правдоподобие данных. Предположим, что объекты независимы и одинаково распределены (i.i.d.).

Вероятность правильного предсказания для объекта $i$ с меткой $y_i \in {-1, 1}$: $$ P(y_i | x_i, w) = \sigma(y_i w^T x_i) = \sigma(M_i) $$

Функция правдоподобия для всей выборки: $$ P(Y | X, w) = \prod_{i=1}^{N} \sigma(y_i w^T x_i) \to \max $$

Для удобства оптимизации перейдем к логарифму правдоподобия: $$ \sum_{i=1}^{N} \log \sigma(y_i w^T x_i) \to \max $$

Подставив определение сигмоиды $\sigma(z) = \frac{1}{1 + e^{-z}}$, получим: $$ \sum_{i=1}^{N} \log \frac{1}{1 + e^{-y_i w^T x_i}} = - \sum_{i=1}^{N} \log (1 + e^{-y_i w^T x_i}) \to \max $$

Задача максимизации логарифма правдоподобия эквивалентна задаче минимизации функции потерь (Log Loss): $$ \mathcal{L}(w) = \sum_{i=1}^{N} \log (1 + e^{-y_i w^T x_i}) = \sum_{i=1}^{N} \log (1 + e^{-M_i}) \to \min $$

Связь с отступом: Функция log loss штрафует малые и отрицательные отступы. При $M_i \to +\infty$ потери стремятся к нулю, при $M_i \to -\infty$ — растут линейно.

Методы оптимизации:

• Градиентный спуск
• Регуляризация (L1, L2) для борьбы с переобучением, аналогично линейной регрессии

3.2. Метрики качества классификации

Выбор правильной метрики критически важен, особенно при несбалансированных классах.

Accuracy и её ограничения

Accuracy (Доля правильных ответов): $$ \text{Accuracy} = \frac{\text{Число верных предсказаний}}{\text{Общее число объектов}} $$

Проблема: Accuracy может вводить в заблуждение на несбалансированных данных.

• Пример: Диагностика редкой болезни.
  • 100 000 здоровых, 10 больных.
  • Если классификатор всегда предсказывает «здоров», Accuracy = $100000 / 100010 \approx 99.99%$.
  • При этом модель бесполезна, так как не находит ни одного больного.

Матрица ошибок (Confusion Matrix)

Для детального анализа используется матрица ошибок:

• TP: Сколько больных назвали больными.
• TN: Сколько здоровых назвали здоровыми.
• FP: Сколько здоровых назвали больными (Ошибка I рода).
• FN: Сколько больных назвали здоровыми (Ошибка II рода).

$$ \text{Accuracy} = \frac{TP + TN}{TP + TN + FP + FN} $$

Precision и Recall

Для задач с дисбалансом классов чаще используют Precision и Recall.

1. Precision (Точность): Какая доля объектов, названных положительными, действительно является положительными. $$ \text{Precision} = \frac{TP}{TP + FP} $$
2. Recall (Полнота): Какая доля реальных положительных объектов была найдена моделью. $$ \text{Recall} = \frac{TP}{TP + FN} $$

Пример 1: Если модель нашла только 1 больного из 10, но не ошиблась на здоровых:

• Precision = $1 / (0 + 1) = 1$ (все найденные — действительно больные).
• Recall = $1 / (1 + 9) = 0.1$ (найден только 10% больных).

Пример 2: Поменяем целевой класс — будем искать здоровых (100 000 здоровых, 10 больных):

• Precision = $100000 / (100000 + 9) \approx 0.99991$
• Recall = $100000 / (100000 + 0) = 1$

Это демонстрирует, что выбор положительного класса влияет на интерпретацию метрик.

F-мера (F-score)

Для баланса между Precision и Recall используется гармоническое среднее — $F_\beta$-мера:

$$ F_\beta = (\beta^2 + 1) \frac{\text{Precision} \times \text{Recall}}{\beta^2 \text{Precision} + \text{Recall}} $$

Наиболее популярна F1-мера ($\beta = 1$): $$ F_1 = 2 \frac{\text{Precision} \times \text{Recall}}{\text{Precision} + \text{Recall}} $$

ROC-кривая и AUC

Многие классификаторы (включая логистическую регрессию) выдают вероятность $p_+ \in [0, 1]$. Порог классификации можно варьировать.

• TPR (True Positive Rate): То же самое, что Recall. $$ \text{TPR} = \frac{TP}{TP + FN} $$
• FPR (False Positive Rate): Доля здоровых, ошибочно названных больными. $$ \text{FPR} = \frac{FP}{FP + TN} $$

ROC-кривая (Receiver Operating Characteristic): Зависимость TPR от FPR при изменении порога классификации.

AUC (Area Under Curve): Площадь под ROC-кривой.

• AUC = 1: Идеальный классификатор.
• AUC = 0.5: Случайное угадывание.
• Чем больше AUC, тем лучше классификатор ранжирует объекты (отделяет положительный класс от отрицательного).

3.3. Деревья решений (Decision Trees)

Дерево решений — это непараметрический метод, который строит последовательность правил для классификации объектов.

Принцип построения

Представим, что у нас есть один признак. Мы сортируем объекты по нему и выбираем порог $t$, разделяющий выборку на две части: $L$ (left) и $R$ (right).

Формально, для признака $x_i$ и порога $t_j$: $$ Q \xrightarrow{x_i < t_j} \begin{cases} L \ R \end{cases} $$

Цель разделения — уменьшить разнородность (гетерогенность) в дочерних узлах. Качество разделения оценивается функцией: $$ G(x_i, t_j) = \frac{|L|}{|Q|} H(L) + \frac{|R|}{|Q|} H(R) $$ где $H(R)$ — функция неопределенности (impurity) в узле.

Критерии неопределенности

Пусть $p_0$ и $p_1$ — доли объектов классов 0 и 1 в узле.

1. Misclassification (Доля ошибок): $$ H(R) = 1 - \max(p_0, p_1) $$
2. Entropy (Энтропия): $$ H(R) = -p_0 \log_2 p_0 - p_1 \log_2 p_1 = - \sum_k p_k \log_2 p_k $$
3. Gini (Индекс Джини): $$ H(R) = 1 - p_0^2 - p_1^2 = 1 - \sum_k p_k^2 $$

Когда останавливаться? (Регуляризация)

Если не ограничивать рост дерева, оно переобучится (запомнит каждый объект). Критерии остановки:

• Ограничить максимальную глубину дерева.
• Ограничить минимальное количество объектов в узле для дальнейшего деления.
• Ограничить минимальное количество объектов в листе.
• Pruning (Обрезка): Построить большое дерево, а затем «постричь» ветви, которые не дают прироста качества на валидации.

Плюсы и минусы деревьев решений

Плюсы:

• Интерпретируемость: Правила легко понять и визуализировать.
• Масштаб: Устойчивы к разным масштабам признаков (не требуют нормировки).
• Пропуски: Некоторые реализации могут работать с пропусками в данных.
• Параметры: Мало гиперпараметров для настройки.

Минусы:

• Шум: Чувствительны к шуму в данных (склонность к переобучению).
• Границы: Разделяющая граница кусочно-линейная (перпендикулярна осям признаков).
• Нестабильность: Малое изменение данных может сильно изменить структуру дерева.
• Экстраполяция: Не умеют экстраполировать (предсказывать за пределами диапазона обучающей выборки), только интерполируют.

3.4. Заключение

В этой лекции мы рассмотрели логистическую регрессию как способ получения вероятностных оценок в линейных моделях и разобрали ключевые метрики для оценки качества классификации, такие как Precision, Recall и ROC-AUC. Важным понятием оказался отступ (margin), который связывает линейный отклик модели с качеством классификации и лежит в основе функции потерь log loss.

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

Что дальше? В следующих главах мы рассмотрим:

• Ансамбли деревьев (Random Forest, Gradient Boosting).
• Методы улучшения стабильности и качества деревьев.