Классические алгоритмы машинного обучения

В настоящей главе рассматриваются классические алгоритмы машинного обучения: метод ближайших соседей, линейная и логистическая регрессии, деревья решений и построенные на их основе ансамбли (случайный лес, градиентный бустинг), а также методы понижения размерности и кластеризации. Разделы, опирающиеся друг на друга, целесообразно читать по порядку. Изложение носит конспективный характер: строгие выкладки приведены у Хасти [26] и Бишопа [27], рецепты, доведённые до работающего кода, — у Жерона [29].

Метод k-ближайших соседей (KNN)

Постановка задачи

Рассмотрим задачу классификации животных по двум признакам.

• Длина усов
• Длина хвоста

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

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

Гипотеза о компактности

В основе метода KNN лежит гипотеза о компактности.

Объекты одного класса расположены «близко» друг к другу в пространстве признаков, а объекты разных классов «далеко».

Гипотеза сводит классификацию к поиску близких объектов, уже размеченных в обучающей выборке.

Алгоритм KNN

Определение:
K-ближайших соседей (K Nearest Neighbors, KNN) — один из простейших алгоритмов классификации.

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

1. Для нового объекта вычислить расстояние до всех объектов обучающей выборки
2. Выбрать \(K\) объектов с наименьшим расстоянием
3. Присвоить объекту класс, чаще всего встречающийся среди \(K\) соседей (голосование большинства)

Гиперпараметр:
\(K\) — количество соседей, участвующих в голосовании.

• При малом \(K\) модель чувствительна к шуму и выбросам
• При большом \(K\) граница решений становится более гладкой, но может потерять локальные особенности

Метрики расстояния

Понятие «близости» определяется выбранной метрикой.

Манхэттенское расстояние

$$d(\mathbf{x}, \mathbf{\hat{x}}) = \sum_{i=1}^{N} |x_i - \hat{x}_i|$$

Евклидово расстояние

$$d(\mathbf{x}, \mathbf{\hat{x}}) = \sqrt{\sum_{i=1}^{N} (x_i - \hat{x}_i)^2}$$

Косинусное расстояние

$$d(\mathbf{x}, \mathbf{\hat{x}}) = 1 - \frac{\sum_{i=1}^{N} x_i \hat{x}i}{\sqrt{\sum{i=1}^{N} x_i^2} \cdot \sqrt{\sum_{i=1}^{N} \hat{x}_i^2}}$$

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

Проблемы и решения

1. Зависимость от масштаба признаков

Проблема:
Если признаки имеют разные масштабы (например, 29 признаков ∈ [0, 1], а один ∈ [0, 1000]), то в вычисленном расстоянии будет доминировать признак с большим масштабом.

Решением является нормализация признаков.

• Минимакс-нормализация приводит все значения к диапазону [0, 1]
• Стандартизация приводит их к нулевому математическому ожиданию и единичной дисперсии (\(\mu = 0, \sigma = 1\))

2. Вычислительная сложность

Проблема:
При большом объёме обучающей выборки (\(N\) объектов) поиск ближайших соседей требует \(O(N)\) операций сравнения на каждый объект.

Решением являются структуры данных, ускоряющие поиск.

• kD-tree (k-dimensional tree) строит дерево разбиения пространства, на каждом уровне разделяющее данные по одному признаку
• Ball tree — иерархическая структура из гиперсфер
• HNSW (Hierarchical Navigable Small World) — графовая структура для приближённого поиска ближайших соседей
• FRiS-Stolp отбирает эталоны, заменяющие собой целые группы объектов

3. Улучшение голосования

Вместо простого подсчёта соседей каждого класса можно применить взвешенное голосование: вес соседа обратно пропорционален расстоянию до него.

$$\text{вес}_i = \frac{1}{d(\mathbf{x}, \mathbf{x}_i)} \quad \text{или} \quad \text{вес}_i = e^{-d(\mathbf{x}, \mathbf{x}_i)}$$

Свойства модели KNN

Метод FRiS-Stolp для отбора эталонов

Для сокращения вычислительной сложности можно оставить подмножество наиболее информативных объектов — эталонов (столпов).

Критерий качества эталона:
Эталон считается хорошим при выполнении двух условий:

• Объекты его класса лежат как можно ближе к нему
• Объекты чужих классов лежат как можно дальше

Функция FRiS: $$\text{FRiS}(z, a_i, b_i) = \frac{r_2 - r_1}{r_2 + r_1}$$

где \(r_1\) — расстояние до ближайшего объекта своего класса, \(r_2\) — до ближайшего объекта чужого класса.

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

Линейная регрессия

Постановка задачи

Линейная регрессия решает задачу предсказания непрерывной целевой переменной \(y\) по одной или нескольким входным переменным (признакам) \(x\), измеренным для того же объекта.

В простейшем одномерном случае модель имеет вид

$$\hat{y} = w_1 x + w_0$$

где \(w_1\) означает вес признака (наклон прямой), а \(w_0\) — смещение (bias, свободный член).

Модель предполагает, что истинная зависимость имеет вид

$$y = w_1 x + w_0 + \varepsilon$$

где \(\varepsilon\) — случайная ошибка (шум).

Цель обучения: найти такие параметры \(w_0, w_1, \dots, w_k\), чтобы предсказания модели \(\hat{y}\) оказались максимально близки к значениям \(y\) обучающей выборки.

Функции ошибки

• SSE (Sum of Squared Errors), сумма квадратов ошибок, $$\text{SSE} = \sum_{i=1}^{N} (y_i - \hat{y}_i)^2 = |\text{error}|_2^2$$

• MSE (Mean Squared Error), среднеквадратичная ошибка, $$\text{MSE} = \frac{1}{N} \sum_{i=1}^{N} (y_i - \hat{y}_i)^2$$

• MAE (Mean Absolute Error), средняя абсолютная ошибка, $$\text{MAE} = \frac{1}{N} \sum_{i=1}^{N} |y_i - \hat{y}_i|$$

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

Матричная форма

Для многомерного случая (\(k\) признаков) модель записывается как

$$y_i = w_1 x_{1,i} + w_2 x_{2,i} + \dots + w_k x_{k,i} + w_0$$

Смещение \(w_0\) включается в вектор весов путём добавления фиктивного признака \(x_0 = 1\) ко всем объектам.

В матричной форме модель имеет следующий вид.

$$\mathbf{y} = \mathbf{X} \mathbf{w}$$

где

• \(\mathbf{y} = \begin{bmatrix} y_1 \ \vdots \ y_N \end{bmatrix}\) — вектор целевых значений,
• \(\mathbf{X} = \begin{bmatrix} x_{1,1} & \cdots & x_{1,k} & 1 \ \vdots & \ddots & \vdots & \vdots \ x_{N,1} & \cdots & x_{N,k} & 1 \end{bmatrix}\) — матрица объектов-признаков (с добавленным столбцом единиц),
• \(\mathbf{w} = \begin{bmatrix} w_1 \ \vdots \ w_k \ w_0 \end{bmatrix}\) — вектор весов.

Оптимизационная задача:

$$\hat{\mathbf{w}} = \arg\min_{\mathbf{w}} |\mathbf{X}\mathbf{w} - \mathbf{y}|_2^2$$

Аналитическое решение методом наименьших квадратов (МНК)

Квадратичная функция потерь записывается следующим образом.

$$Q(\mathbf{w}) = |\mathbf{y} - \mathbf{X}\mathbf{w}|_2^2 = (\mathbf{y} - \mathbf{X}\mathbf{w})^T (\mathbf{y} - \mathbf{X}\mathbf{w})$$

Для нахождения минимума приравняем градиент к нулю.

$$\nabla_{\mathbf{w}} Q(\mathbf{w}) = -2\mathbf{X}^T\mathbf{y} + 2\mathbf{X}^T\mathbf{X}\mathbf{w} = 0$$

Отсюда получаем аналитическое решение.

$$\hat{\mathbf{w}} = (\mathbf{X}^T \mathbf{X})^{-1} \mathbf{X}^T \mathbf{y}$$

Проблемы аналитического решения

На практике этой формулой почти не пользуются по двум причинам.

1. Матрица \(\mathbf{X}^T \mathbf{X}\) может быть необратима.

   • При линейной зависимости признаков (коллинеарность),
   • Когда число признаков \(k\) превышает число объектов \(N\) (бесконечное множество решений).

2. Вычислительная сложность. Обращение матрицы имеет сложность \(O(k^3)\); при большом числе признаков это недопустимо долго.

Градиентный спуск

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

Алгоритм:

1. Инициализировать веса случайными значениями \(\mathbf{w} \gets \text{random}()\)
2. Повторять до сходимости $$\mathbf{w} \gets \mathbf{w} - \alpha \nabla_{\mathbf{w}} Q(\mathbf{w})$$

где

• \(\alpha\) — скорость обучения (learning rate),
• \(\nabla_{\mathbf{w}} Q(\mathbf{w})\) — градиент функции потерь.

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

$$\nabla_{\mathbf{w}} Q(\mathbf{w}) = \frac{2}{N} \mathbf{X}^T (\mathbf{X}\mathbf{w} - \mathbf{y})$$

Варианты градиентного спуска

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

• Полный градиентный спуск (Batch GD): градиент вычисляется по всей выборке.
• Стохастический градиентный спуск (SGD). Градиент вычисляется по одному случайному объекту.
• Мини-батч градиентный спуск. Градиент вычисляется по небольшой случайной подвыборке (батчу).

Проблемы и улучшения

• Локальные минимумы. Для выпуклых функций (как MSE) проблемы нет: любой локальный минимум является глобальным.
• Выбор скорости обучения \(\alpha\).
  • Слишком большая \(\alpha\) приводит к расходимости алгоритма,
  • Слишком маленькая \(\alpha\) делает обучение слишком медленным.
  • Решением является адаптивное уменьшение \(\alpha\) по мере обучения.
• Momentum (инерция). $$\mathbf{v} \gets \beta \mathbf{v} + \alpha \nabla_{\mathbf{w}} Q(\mathbf{w}), \quad \mathbf{w} \gets \mathbf{w} - \mathbf{v}$$ где \(\beta \in (0, 1)\) — коэффициент инерции. Скорость, накопленная на предыдущих шагах, ускоряет сходимость и позволяет «проскакивать» пологие участки.

Проблемы линейной регрессии и их решения

1. Отсутствие линейной зависимости

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

Пример. Предсказание стоимости склада по длине и ширине. Линейная модель $$\text{цена} = w_1 \cdot \text{длина} + w_2 \cdot \text{ширина} + w_0$$ не учитывает, что значение имеет площадь (\(\text{длина} \times \text{ширина}\)). Решением является новый признак «площадь», произведение сторон.

2. Коллинеарность признаков

Если признаки линейно зависимы (\(x_2 = 2x_1\)), веса становятся неустойчивыми и неинтерпретируемыми.

$$y = 6x_1 + 8x_2 + 5 = 0x_1 + 11x_2 + 5 = 22x_1 + 0x_2 + 5 = \dots$$

Решение. Удаление признаков, дублирующих друг друга (анализ корреляции, методы отбора признаков).

3. Выбросы

Выбросы сильно влияют на MSE из-за квадратичного штрафа.

Решения.

• Фильтрация выбросов на этапе предобработки,
• Использование более устойчивых функций потерь (например, MAE или Huber loss).

4. Шумные признаки и переобучение

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

Решением является регуляризация.

Регуляризация

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

L2-регуляризация (Ridge)

$$Q_{\text{reg}}(\mathbf{w}) = \frac{1}{N} |\mathbf{X}\mathbf{w} - \mathbf{y}|_2^2 + \lambda |\mathbf{w}|_2^2$$

• «Выравнивает» веса, уменьшая их по модулю,
• Даёт более стабильное решение на линейно связанных признаках,
• Аналитическое решение имеет вид \(\hat{\mathbf{w}} = (\mathbf{X}^T \mathbf{X} + N\lambda \mathbf{I})^{-1} \mathbf{X}^T \mathbf{y}\). Множитель \(N\) появляется из-за \(1/N\) при первом слагаемом; если записывать потери без нормировки на объём выборки, останется просто \(\lambda \mathbf{I}\).

L1-регуляризация (Lasso)

$$Q_{\text{reg}}(\mathbf{w}) = \frac{1}{N} |\mathbf{X}\mathbf{w} - \mathbf{y}|_2^2 + \lambda |\mathbf{w}|_1$$

• Также уменьшает веса,
• Обнуляет веса нерелевантных признаков, выполняя автоматический отбор признаков.

Параметр регуляризации \(\lambda\)

• при \(\lambda = 0\) получается обычная линейная регрессия,
• при \(\lambda \to \infty\) все веса стремятся к нулю,
• Оптимальное значение \(\lambda\) подбирается на отложенной валидационной выборке.

Параметры и гиперпараметры

Оценка качества модели

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

1. Метрики ошибки. MSE, MAE на тестовой выборке.
2. Базовое сравнение. Сравнение с «наивной» моделью \(\hat{y} = \text{mean}(\mathbf{y})\).
3. Разделение выборки. Разбиение на обучающую и тестовую части (train/test split).
4. Кросс-валидация. Более надёжная оценка, усреднённая по нескольким разбиениям.

В следующих разделах рассматриваются логистическая регрессия (классификация), метрики качества для задач классификации и деревья решений.

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

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

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

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

Линейный классификатор строит решающую границу в виде гиперплоскости: для объекта с признаками \(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\) растут линейно.

Log loss минимизируется тем же градиентным спуском, что и MSE в линейной регрессии, а защита от переобучения обеспечивается той же регуляризацией, L1 или L2.

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

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

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\) (найдена лишь десятая часть больных).

Пример 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, тем лучше классификатор ранжирует объекты (отделяет положительный класс от отрицательного).

Деревья решений (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 (обрезка). Построить большое дерево, а затем удалить ветви, не дающие прироста качества на валидации.

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

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

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

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

Итоги по классификации

Линейная модель переходит от метки к вероятности; её качество оценивается метриками Precision, Recall, F1 и ROC-AUC. Ключевым понятием является отступ (margin), связывающий линейный отклик модели с качеством классификации и лежащий в основе log loss.

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

Деревья. Случайный лес. Градиентный бустинг

Введение

Одиночное дерево нестабильно и склонно к переобучению, тогда как ансамбли деревьев на протяжении многих лет удерживают первое место на табличных данных. В настоящем разделе рассматриваются регрессионные деревья, разложение ошибки на смещение и разброс (bias-variance) и два способа объединения моделей: бэггинг (Bagging) со случайным лесом (Random Forest) и бустинг (Boosting), включая градиентный.

1. Деревья решений

Регрессия

Для регрессии критерий разбиения тот же, меняется только мера неоднородности в узле.

• \(G_{x_i, t_j} = L_Q H_L + R_Q H_R\)
• MSE (среднеквадратичная ошибка) даёт \(H_R = \frac{1}{N} \sum_{i}^{N} (y_m - y_i)^2\), где \(y_m\) — среднее значение.
• MAE (средняя абсолютная ошибка) даёт \(H_R = \frac{1}{N} \sum_{i}^{N} |y_m - y_i|\), где \(y_m\) — медиана.

Оптимизация

• Сложность подготовки составляет \(O(N \cdot \log N \cdot d)\), где \(d\) — количество признаков, \(N\) — количество объектов: все признаки необходимо отсортировать перед вычислением ошибки на каждом разбиении.
• Сложность ошибки составляет \(O(N)\).
• Сложность нахождения оптимального разбиения составляет \(O(N^2 d)\).

Пересчёт ошибок можно ускорить: переход от суммы квадратов отклонений для \(N\) объектов к сумме для \(N-1\) объектов выполняется за \(O(1)\) по формулам преобразования сумм. Применяются и эвристики, например случайный набор признаков в каждой вершине.

2. Смещение и Разброс (Bias-Variance)

Разложение ошибки

Рассмотрим модель зависимости истинных значений от функции. $$y = f(x) + \varepsilon$$ Здесь

• \(y\) — истинные значения;
• \(f(x)\) — закон природы;
• \(\varepsilon\) — ошибка измерения (\(\varepsilon \in N(0, \sigma^2)\), математическое ожидание \(M\varepsilon = 0\)).

Таким образом, \(y \in N(f(x), \sigma^2)\), математическое ожидание \(My = f(x)\).

Рассмотрим семейство функций-регрессоров \(b = b(x)\), приближающих \(f(x)\). В конкретной точке множество регрессоров даст множество значений, а у \(b(x)\) имеются математическое ожидание и дисперсия.

Разложение среднеквадратичной ошибки (MSE) имеет следующий вид. $$MSE = M(y - b)^2 = M(y^2) + M(b^2) - 2M(by)$$

Используя свойства дисперсии \(Var(x) = Dx = M(x - Mx)^2 = Mx^2 - M[x]^2\), получаем следующее.

1. \(My^2 = Dy + M[y]^2 = \sigma^2 + f^2\)
2. \(Mb^2 = Db + M[b]^2\)
3. \(Mby = M(f + \varepsilon)b = Mfb + M\varepsilon b = fMb + M\varepsilon Mb = fMb\)

Подставляя в формулу MSE, получаем $$MSE = \sigma^2 + f^2 + Db + M[b]^2 - 2fM[b] = (f - M[b])^2 + Db + \sigma^2$$

Здесь

• \((f - M[b]) = \text{bias}\) (смещение);
• \(Db = \text{variance}\) (разброс);
• \(\sigma^2\) — неустранимая ошибка.

Итоговое разложение имеет следующий вид. $$MSE = \text{bias}^2 + \text{variance} + \sigma^2$$

Влияние сложности модели

Два слагаемых разложения действуют в противоположных направлениях: сложная модель подстраивается под конкретную выборку и накапливает variance, простая не достигает закона природы и накапливает bias. Между этими крайностями приходится выбирать; неустранимую \(\sigma^2\) не компенсирует ни одна модель, поскольку это шум измерения в самих данных.

3. Ансамбли моделей

Мудрость толпы

На ярмарке разыгрывалась лотерея, в которой требовалось на глаз угадать вес быка. Участвовало около 800 человек, бык весил 1198 фунтов, точно не угадал никто, а среднее арифметическое всех догадок составило 1197 фунтов.

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

Бэггинг (Bagging)

Предсказания нескольких классификаторов или регрессоров усредняются, а чтобы обеспечить моделям разный «опыт», их обучают на разных данных. Подвыборки формируются методом Bootstrap: элементы общей выборки выбираются случайно, и один и тот же элемент может попасть в подвыборку несколько раз.

Пусть \(b_1(x), ..., b_n(x)\) — модели регрессии, обученные на разных подвыборках, \(f(x)\) — функция истинных значений. Квадратичная ошибка \(i\)-й модели равна \(\varepsilon_i^2(x) = (b_i(x) - f(x))^2\). Если усреднить ошибку всех моделей, получим \(\frac{1}{n} M_x [\sum \varepsilon_i^2(x)]\).

Предположим, что ошибки несмещены (\(M_x \varepsilon_i(x) = 0\)) и некоррелированы (\(M_x \varepsilon_i(x)\varepsilon_j(x) = 0\) при \(i \neq j\)). Построим новую модель. $$a(x) = \frac{1}{n} \sum_{i}^{n} b_i(x)$$

Тогда среднеквадратичная ошибка новой модели равна $$M_x \left( \frac{1}{n} \sum_{i}^{n} b_i(x) - f(x) \right)^2 = M_x \left( \frac{1}{n} \sum_{i}^{n} \varepsilon_i(x) \right)^2 = \frac{1}{n^2} M_x \sum_{i}^{n} \varepsilon_i^2(x)$$

Вывод. Бэггинг снижает variance в ошибке (то есть ослабляет переобучение) примерно в \(n\) раз, если считать ошибки некоррелированными. Модели «в среднем» ошибаются одинаково, но в разные стороны, а выбросы попадают лишь в часть подвыборок.

Случайный лес (Random Forest)

Метод развивает идею бэггинга применительно к деревьям.

1. Деревья обучаются на разных подвыборках.
2. Для повышения некоррелированности деревьев при построении узла наилучшее разбиение ищется не по всем признакам, а лишь по случайно выбранной их части.

Гиперпараметры леса: число деревьев плюс гиперпараметры одного дерева. Ответы деревьев объединяются усреднением в регрессии и голосованием большинства в классификации.

Случайный лес является удобной моделью «по умолчанию»: он точен, устойчив к выбросам, менее одиночного дерева склонен к переобучению, распараллеливается (деревья независимы, каждое вычисляется на своём ядре) и, как правило, хорошо работает с настройками по умолчанию.

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

4. Бустинг

AdaBoost и решающие пни

В бустинге объекты, на которых ансамбль ошибся, получают больший вес на следующем шаге, и каждая новая модель в первую очередь исправляет ошибки предшественников. Базовые модели намеренно выбираются слабыми, часто это «пни» (decision stumps), деревья глубиной 1.

Градиентный бустинг на примере

Задача. Предсказать цену товара по возрасту (в днях). Предположим, что имеется только один признак.

Шаг 1. Начальное приближение — среднее по всей выборке. Цены равны 700, 800, 600, 400, 300. Среднее даёт \((700+800+600+400+300) / 5 = 560\).

Вычислим остатки — разность цены и приближения.

Шаг 2. Построим регрессионное дерево, предсказывающее остатки. Разбиение выполняется по признаку Возраст >= 80.

• Ветка 1 (Age < 80) даёт остатки 140, 240, 40 со средним 140.
• Ветка 2 (Age >= 80) даёт остатки -160, -260 со средним -210.

Шаг 3. Прибавим предсказание дерева к приближению (можно с коэффициентом, в примере без него).

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

Формализация градиентного бустинга

На \(t\)-м шаге модель представляет собой сумму функций, накопленных к этому моменту. $$f(x) = \sum_{i=0}^{t-1} f_i(x)$$

Параметры нового шага находятся через минимизацию функции потерь \(L\). $$\rho_t, \theta_t = \arg\min_{\rho, \theta} M_{x,y} [L(y, f(x) + \rho h(x, \theta))]$$ где \(f_t(x) = \rho_t h(x, \theta_t)\).

Остаток на \(i\)-м элементе, он же градиент, равен $$r_{i,t} = - \left[ \frac{\nabla L(y_i, f(x_i))}{\nabla f(x_i)} \right]$$ Этот остаток является целью дерева, строящегося на следующем шаге.

1. Параметры дерева находятся как \(\theta_t = \arg\min_{\theta} \sum_{i}^{n} (r_{i,t} - h(x_i, \theta))^2\)
2. Параметры «линейной регрессии», то есть шага, находятся как \(\rho_t = \arg\min_{\rho} \sum_{i}^{n} L(y_i, f(x_i) + \rho h(x_i, \theta_t))\)

Случай MSE. Для среднеквадратичной ошибки остаток равен разнице между истинным значением и предсказанием. $$r_{i,t} = - \frac{\nabla L}{\nabla f} = 2(y_i - f(x_i)) \rightarrow \text{разница между истинным значением и предсказанием}$$

Сравнение градиентного бустинга и бэггинга

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

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

Поэтому деревья в бустинге намеренно делают неглубокими, три-четыре уровня, не больше. Сила ансамбля заключается в количестве деревьев, а не в сложности каждого.

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

Понижение размерности. Кластеризация

В настоящем разделе рассматриваются две задачи обучения без учителя. Первая — сжать признаковое пространство, сохранив структуру данных; для этого применяются метод главных компонент (PCA) и t-SNE. Вторая — разделить на группы объекты, не размеченные заранее; здесь используются k-средних, иерархическая кластеризация и DBSCAN.

1. Понижение размерности

Основная идея

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

Метод главных компонент (PCA)

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

Основная концепция:

1. Предполагается, что облако данных описывается эллипсом, вытянутым вдоль главных направлений.
2. Меняется базис пространства.
3. Отрезается «новая ось» с минимальной дисперсией.
4. Чтобы вычислить «потерянную информацию», дисперсия отрезанной оси делится на сумму дисперсий по всем осям.

Вычисления. Ковариация признаков вычисляется по формуле $$cov(X_i, X_j) = M[(X_i - M[X_i])(X_j - M[X_j])] = M[X_i X_j] - M[X_i]M[X_j]$$

Выборку можно сместить так, чтобы математическое ожидание \(M[X_i] = 0\). В матричном виде ковариация записывается следующим образом. $$cov(X) = \frac{1}{N} X^T X$$

Свойства.

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

Ограничения PCA.

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

t-SNE (t-Distributed Stochastic Neighbor Embedding)

Механическая аналогия.

1. Данные из пространства размерности \(N\) помещаются в пространство меньшей размерности \(M\) (отображение).
2. Объекты «прибиваются гвоздями» к своим местам.
3. Объекты в пространстве \(M\) соединяются пружинами, сила которых зависит от того, насколько расстояние в пространстве \(M\) отличается от расстояния в пространстве \(N\).
4. Система «отпускается» (гвозди убираются).

Динамика.

• Если точки в пространстве \(M\) дальше, чем в пространстве \(N\), то они притягиваются.
• Если точки в пространстве \(M\) ближе, чем в пространстве \(N\), то они отталкиваются.

Математическое описание. Пусть \(|x_i - x_j|\) — расстояние в исходном пространстве, \(|y_i - y_j|\) — расстояние в пространстве отображения.

Условное сходство через Гауссово распределение записывается следующим образом. $$p_{j|i} = \frac{e^{-|x_i - x_j|^2 / 2\sigma_i^2}}{\sum_{k \neq i} e^{-|x_i - x_k|^2 / 2\sigma_i^2}}$$ где \(\sigma_i^2\) — дисперсия распределения Гаусса вокруг точки \(x_i\), у каждой точки своя, подобранная под плотность окрестности.

Симметричное сходство даёт $$p_{ji} = \frac{p_{j|i} + p_{i|j}}{2N}$$

В пространстве меньшей размерности используется не Гауссово распределение, а распределение Стьюдента с одной степенью свободы (t-distribution), утяжелённое на хвостах. $$q_{ij} = \frac{t(|y_i - y_j|)}{\sum_{k \neq l} t(|y_k - y_l|)}, \text{ где } t(x) = \frac{1}{1 + x^2}$$

Нормировка выполняется по всем парам сразу, а не по соседям одной точки, поскольку только так \(Q\) остаётся симметричным совместным распределением, как и \(P\).

Оптимизация. Матрица сходства в отображении приближается к матрице исходного пространства путём минимизации расстояния Кульбака-Лейблера. $$KL(P||Q) = \sum_{i,j} p_{ij} \log \frac{p_{ij}}{q_{ij}} \to \min$$

Минимизация выполняется градиентным спуском, а сам градиент даёт равнодействующую всех сил, приложенных к точке. $$\frac{\partial KL(P||Q)}{\partial y_i} = 4 \sum_j (p_{ij} - q_{ij}),(y_i - y_j),\bigl(1 + |y_i - y_j|^2\bigr)^{-1}$$ Все вычисления выполняются в пространстве отображения: разность \(y_i - y_j\) задаёт направление силы, множитель \(t(|y_i - y_j|)\) — её величину. Исходные координаты \(x\) в градиент не входят, поскольку они уже учтены в \(p_{ij}\).

Обоснование выбора t-distribution. При понижении размерности максимальные расстояния «меняются», и если использовать распределение Гаусса, то точки на плоскости расположатся очень скученно (crowding problem).

Особенности t-SNE.

• Работает со сложными структурами.
• Новые данные спроецировать невозможно: требуется либо полное переобучение, либо дополнительные приёмы (например, k-nn).
• Вычисления длительны. Можно использовать не все точки, а только ближайших соседей.
  • Если брать мало соседей, t-SNE больше учитывает локальные паттерны.
  • Если брать много соседей, t-SNE больше учитывает глобальные паттерны.

2. Кластеризация

k-средних (k-means)

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

Алгоритм.

1. Задать количество кластеров.
2. Случайным образом разместить точки (центроиды) в пространстве.
3. Для каждой точки определить, к какому центроиду она ближе.
4. Переместить каждый центроид в «центр масс» точек, приписанных ему на предыдущем шаге.
5. Повторять пункты 3-4 фиксированное число раз, или пока перемещение центроидов не станет достаточно малым (алгоритм сойдётся).

Особенности и ограничения:

• Необходимо задавать количество кластеров, а для его подбора рассматривается сумма квадратов расстояний от точек до своих центров. Как только с ростом числа кластеров она перестаёт резко падать, можно останавливаться.
• Чувствителен к начальному расположению центроидов.
• Имеются ограничения на форму кластеров.
• Требует много вычислений.

Агломеративная (иерархическая) кластеризация

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

Алгоритм «снизу-вверх» устроен следующим образом.

1. Сначала каждая точка образует центр своего кластера.
2. Вычисляются попарные расстояния между центрами кластеров.
3. Пара ближайших кластеров объединяется в новый, и центр пересчитывается.
4. Пункты 2-3 повторяются, пока все точки не будут объединены в один кластер.

DBSCAN

DBSCAN является единственным из трёх методов, помечающим точки, не относящиеся ни к одному кластеру. Кластеры он ищет как области повышенной плотности, поэтому находит кластеры произвольной формы, а их число определяет самостоятельно. Явно выделенные выбросы являются готовым инструментом поиска аномалий в данных с установки.

У метода два гиперпараметра, радиус окрестности \(\varepsilon\) и минимальное число точек \(m\) в этом радиусе, причём сама точка тоже учитывается (в scikit-learn это eps и min_samples). Соседями точки считаются все точки, которые лежат от неё не дальше \(\varepsilon\).

Алгоритм.

1. Выбирается случайная точка.
2. Если у неё меньше \(m\) точек в окрестности радиуса \(\varepsilon\), то она помечается как потенциальный выброс (noise point), и выбирается другая точка.
3. Если точек в окрестности радиуса \(\varepsilon\) не меньше \(m\), выполняется следующее.
   • Заводится новый кластер, и точка (core point) помещается в него.
   • Если сосед оказался потенциальным выбросом или у него мало соседей, то это край кластера (border point). Он заносится в кластер, и осуществляется переход к другому соседу.
   • Если у соседа достаточно собственных соседей, то он добавляется в кластер (core point), а его соседи заносятся в очередь обхода.
4. Пункты 1-3 повторяются.
5. Точки, так и не попавшие ни в один кластер, остаются выбросами, и это не «ещё один кластер». В scikit-learn они получают метку \(-1\), и общего между ними только то, что плотности вокруг каждой не хватило.

Выбор между тремя методами осуществляется следующим образом: если число кластеров известно и ожидаются компактные группы — k-средних; если число неизвестно, а выборка небольшая — агломеративная; если кластеры имеют сложную форму или необходимо отделить выбросы — DBSCAN.

Итоги по понижению размерности и кластеризации

Обе задачи решаются без учителя и необходимы, когда о данных ещё ничего не известно. PCA и t-SNE позволяют визуально оценить многомерную выборку; k-средних, агломеративная кластеризация и DBSCAN разделяют её на группы. Размеченного правильного ответа здесь нет, и сверять результат приходится с физическим смыслом.

Нейронным сетям посвящена следующая глава.