CS229: обучение с учителем — линейная и логистическая регрессия, GLM, генеративные модели (конспект)

Что это за страница

Пересказ своими словами конспектов CS229 «Supervised learning» (части I–III) и «Generative learning algorithms» (часть IV) Эндрю Ына. Лицензии у конспектов нет, поэтому это не перевод: порядок тем и формулы сохранены, объяснения и пример кода — наши. Путеводитель по курсу — здесь.

Постановка: обучение с учителем

Есть обучающая выборка пар $(x^{(i)}, y^{(i)})$, $i = 1, \ldots, m$: например, площадь дома и его цена (сквозной пример конспекта — 47 домов в Портленде). Нужно найти гипотезу $h: \mathcal{X} \to \mathcal{Y}$, хорошо предсказывающую $y$ по $x$. Если $y$ непрерывен — это регрессия, если принимает немного дискретных значений — классификация.

Часть I. Линейная регрессия

Гипотеза — линейная функция признаков, $h_\theta(x) = \theta^T x$ (с договорённостью $x_0 = 1$, чтобы свободный член вошёл в $\theta$). Функция стоимости — наименьшие квадраты:

$$J(\theta) = \frac{1}{2} \sum_{i=1}^{m} \big(h_\theta(x^{(i)}) - y^{(i)}\big)^2 .$$

Алгоритм LMS (градиентный спуск)

Шаг градиентного спуска для одного примера даёт правило LMS (least mean squares, или правило Уидроу — Хоффа):

$$\theta_j := \theta_j + \alpha \big(y^{(i)} - h_\theta(x^{(i)})\big)\, x_j^{(i)} .$$

Величина обновления пропорциональна ошибке: если предсказание почти верно, параметры почти не меняются. Есть два варианта: пакетный спуск (на каждом шаге — сумма по всей выборке) и стохастический (обновление после каждого примера; быстрее начинает приближаться к минимуму и предпочтителен на больших выборках, хотя «колеблется» вокруг минимума, если не уменьшать шаг). Поскольку $J$ — выпуклая квадратичная функция, у неё один глобальный минимум.

Нормальные уравнения

Минимум можно найти и сразу. Конспект вводит матричное дифференцирование (градиент по матрице, след и его свойства), записывает $J(\theta) = \frac{1}{2} (X\theta - \vec y)^T (X\theta - \vec y)$ через матрицу плана $X$ (по строке на пример) и, приравняв градиент к нулю, получает нормальные уравнения:

$$X^T X \theta = X^T \vec y \quad \Longrightarrow \quad \theta = (X^T X)^{-1} X^T \vec y .$$

Наш небольшой пример на пяти домах из таблицы конспекта (на всех 47 домах конспект получает $\theta_0 = 71{,}27$, $\theta_1 = 0{,}1345$):

import numpy as np

area  = np.array([2104, 1600, 2400, 1416, 3000.])   # площадь, кв. футы
price = np.array([400, 330, 369, 232, 540.])         # цена, тыс. $
X = np.c_[np.ones(5), area]

theta = np.linalg.solve(X.T @ X, X.T @ price)        # нормальные уравнения
print(theta.round(4))                                # [26.7899  0.1651]

# тот же ответ градиентным спуском (признак стандартизован, чтобы шаг был устойчив)
mu, sd = area.mean(), area.std()
Xs = np.c_[np.ones(5), (area - mu) / sd]
th = np.zeros(2)
for _ in range(2000):
    th -= 0.1 * Xs.T @ (Xs @ th - price) / 5
print(np.round([th[0] - th[1] * mu / sd, th[1] / sd], 4))   # [26.7899  0.1651]

Почему именно квадраты: вероятностный смысл

Предположим, что $y^{(i)} = \theta^T x^{(i)} + \epsilon^{(i)}$, где шум $\epsilon^{(i)}$ независим и распределён нормально, $\mathcal{N}(0, \sigma^2)$. Тогда правдоподобие параметров — произведение гауссовых плотностей, а его логарифм равен константе минус $\frac{1}{\sigma^2} \cdot \frac{1}{2} \sum (y^{(i)} - \theta^T x^{(i)})^2$. Значит, метод наименьших квадратов — это оценка максимального правдоподобия при гауссовом шуме; ответ к тому же не зависит от $\sigma^2$. Это не единственное оправдание квадратов, но очень естественное.

Локально взвешенная регрессия

Выбор признаков — отдельная проблема: прямая может недообучиться (данные явно не на прямой), а полином высокой степени — переобучиться (пройти через все точки, но предсказывать нелепо). Локально взвешенная линейная регрессия (LWR) обходит выбор признаков: для каждого запроса $x$ решается своя задача наименьших квадратов с весами

$$w^{(i)} = \exp\Big(-\frac{(x^{(i)} - x)^2}{2\tau^2}\Big),$$

то есть близкие к запросу точки важнее далёких; $\tau$ — ширина окна. LWR — непараметрический алгоритм: для предсказания нужна вся обучающая выборка (в отличие от параметрической линейной регрессии, которой достаточно $\theta$).

Часть II. Классификация и логистическая регрессия

Для бинарной классификации ($y \in \lbrace 0, 1 \rbrace$) линейная регрессия плоха: предсказания выходят за $[0, 1]$. Берём логистическую (сигмоидную) функцию:

$$h_\theta(x) = g(\theta^T x) = \frac{1}{1 + e^{-\theta^T x}}, \qquad g'(z) = g(z)\big(1 - g(z)\big).$$

Считаем $P(y = 1 \mid x; \theta) = h_\theta(x)$, записываем логарифм правдоподобия $\ell(\theta) = \sum_i y^{(i)} \log h(x^{(i)}) + (1 - y^{(i)}) \log (1 - h(x^{(i)}))$ и максимизируем его градиентным подъёмом. Удивительно, но правило обновления выглядит точно так же, как LMS: $\theta_j := \theta_j + \alpha (y^{(i)} - h_\theta(x^{(i)})) x_j^{(i)}$ — только $h_\theta$ теперь нелинейна. Почему так совпало, объяснит часть III.

Отступление: перцептрон. Если вместо сигмоиды взять жёсткий порог ($g(z) = 1$ при $z \geq 0$, иначе 0), то же правило даёт алгоритм перцептрона (1960-е). Он похож на логистическую регрессию внешне, но у него нет вероятностной интерпретации и он не выводится как оценка максимального правдоподобия.

Метод Ньютона. Другой способ максимизировать $\ell(\theta)$ — искать ноль его производной методом Ньютона: $\theta := \theta - H^{-1} \nabla_\theta \ell(\theta)$, где $H$ — матрица Гессе. Он сходится квадратично (число верных знаков примерно удваивается на каждой итерации) и обычно требует гораздо меньше итераций, чем градиентный спуск, но каждая итерация дороже: нужно обратить матрицу $n \times n$. Для логистической регрессии это называют методом скоринга Фишера.

Часть III. Обобщённые линейные модели

Линейная и логистическая регрессии — частные случаи одной конструкции.

Экспоненциальное семейство — распределения вида

$$p(y; \eta) = b(y) \exp\big(\eta^T T(y) - a(\eta)\big),$$

где $\eta$ — естественный параметр, $T(y)$ — достаточная статистика (обычно $T(y) = y$), $a(\eta)$ — логарифм нормирующей константы. Бернулли и гауссово распределения сюда входят: у Бернулли с параметром $\phi$ естественный параметр $\eta = \log \frac{\phi}{1 - \phi}$, откуда $\phi = \frac{1}{1 + e^{-\eta}}$ — та самая сигмоида. Также входят мультиномиальное, пуассоновское, гамма, бета, Дирихле и другие.

Обобщённая линейная модель (GLM) строится из трёх допущений: (1) $y \mid x; \theta$ лежит в экспоненциальном семействе; (2) мы хотим предсказывать $\mathbb{E}[T(y) \mid x]$; (3) естественный параметр линеен по входу, $\eta = \theta^T x$. Выбор распределения сам задаёт модель:

Распределение $y$	Что получается	$h_\theta(x)$
Гауссово	обычные наименьшие квадраты	$\theta^T x$
Бернулли	логистическая регрессия	$1 / (1 + e^{-\theta^T x})$
Мультиномиальное ($k$ классов)	softmax-регрессия	$\operatorname{softmax}(\theta_1^T x, \ldots, \theta_k^T x)$
Пуассоновское (счётчики)	пуассоновская регрессия	$e^{\theta^T x}$

Функция, выражающая среднее через естественный параметр, называется канонической функцией отклика (обратная к ней — канонической связью). Для всех GLM правило градиентного обновления имеет один и тот же вид «ошибка × признак» — вот почему LMS и логистическая регрессия совпали. Softmax-регрессия обобщает логистическую на $k$ классов: вероятность класса $j$ равна $\frac{e^{\theta_j^T x}}{\sum_l e^{\theta_l^T x}}$, а обучение — максимизация логарифма правдоподобия, то есть минимизация кросс-энтропии (подробнее — урок 1.3.2).

Часть IV. Генеративные алгоритмы

Логистическая регрессия — дискриминативный алгоритм: моделирует $p(y \mid x)$ напрямую. Генеративный алгоритм моделирует, как устроены данные каждого класса, $p(x \mid y)$, и априорные вероятности классов $p(y)$, а затем классифицирует по формуле Байеса: $\arg\max_y p(x \mid y) p(y)$.

Гауссов дискриминантный анализ (GDA)

Допущение: признаки каждого класса распределены по многомерному нормальному закону с общей ковариационной матрицей: $y \sim \text{Bernoulli}(\phi)$, $x \mid y = 0 \sim \mathcal{N}(\mu_0, \Sigma)$, $x \mid y = 1 \sim \mathcal{N}(\mu_1, \Sigma)$. Оценки максимального правдоподобия получаются в явном виде: $\phi$ — доля класса 1, $\mu_0, \mu_1$ — средние по классам, $\Sigma$ — общая ковариация отклонений от средних своего класса. Граница решений — линейная.

GDA или логистическая регрессия? Если расписать $p(y = 1 \mid x)$ для модели GDA, получится в точности сигмоида от линейной функции $x$. Обратное неверно: из логистической формы не следует гауссовость. Значит, GDA делает более сильные допущения: если они верны (хотя бы приблизительно), GDA эффективнее по данным — ей нужно меньше примеров, и она асимптотически лучшая. Логистическая регрессия устойчивее: она верна при многих распределениях (например, когда $x \mid y$ пуассоновские), поэтому на практике её используют чаще, особенно при большом количестве данных.

Наивный Байес

Для текстов признаки дискретны и их много: $x \in \lbrace 0, 1 \rbrace^n$ — есть ли в письме каждое слово словаря (пример конспекта — фильтр спама). Моделировать полное $p(x \mid y)$ невозможно ($2^n$ значений), поэтому делаем наивное байесовское допущение: слова условно независимы при данном классе, $p(x_1, \ldots, x_n \mid y) = \prod_j p(x_j \mid y)$. Допущение заведомо неверно, но классификатор работает удивительно хорошо. Параметры — просто доли: доля спам-писем, в которых встречается слово $j$, и т. д.

Сглаживание Лапласа. Если слово ни разу не встречалось в обучающих письмах, его оценка вероятности равна нулю в обоих классах, и формула Байеса даёт $0/0$. Лечение — добавить единицу к каждому счётчику (и число исходов к знаменателю): $\phi_j = \frac{\text{count}_j + 1}{m + k}$ для признака с $k$ значениями.

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

Связь с нашим курсом

• Линейная и логистическая регрессия на практике — уроки 2.2.1 и 2.2.2.
• Максимальное правдоподобие и softmax — 1.3.2; градиентный спуск — 1.4.1 и наш перевод конспекта CS231n об оптимизации.
• Следующий конспект — SVM, ядра и теория обучения.

Словарик

EN	RU
hypothesis, cost function	гипотеза, функция стоимости
LMS / Widrow-Hoff rule	правило LMS (Уидроу — Хоффа)
normal equations, design matrix	нормальные уравнения, матрица плана
locally weighted regression	локально взвешенная регрессия
underfitting, overfitting	недообучение, переобучение
exponential family, natural parameter	экспоненциальное семейство, естественный параметр
generalized linear model, canonical link	обобщённая линейная модель, каноническая связь
discriminative vs generative	дискриминативный и генеративный
Laplace smoothing	сглаживание Лапласа