CS229: нейросети и обучение без учителя — backprop, k-средних, EM, PCA (конспект)

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

Пересказ своими словами конспектов CS229 Эндрю Ына о глубоком обучении, кластеризации k-средних, смеси гауссиан, EM-алгоритме и PCA (часть о обучении с подкреплением — кратко в конце). Лицензии у конспектов нет, поэтому это не перевод: формулы и порядок тем сохранены, объяснения — наши. Предыдущий конспект — SVM и теория обучения, путеводитель — здесь.

Глубокое обучение

Нейросеть «по кирпичику»

Конспект строит нейросеть из знакомой задачи о ценах домов. Прямая может предсказать отрицательную цену; запретим это: $f(x) = \max(ax + b, 0)$. Это один нейрон с функцией активации ReLU. Дальше добавляем признаки (площадь, число спален, почтовый индекс, благосостояние района) и промежуточные нейроны, каждый из которых вычисляет что-то осмысленное — «размер семьи, которая поместится», «пешая доступность», «качество школ», — а выходной нейрон объединяет их в цену. Главная мысль: такие промежуточные признаки не задают вручную — сеть получает только вход $x$ и ответ $y$, а скрытые признаки выучивает сама. Поэтому сети часто называют чёрными ящиками и говорят об сквозном обучении (end-to-end).

Дальше — второй пример (есть ли на картинке футбольный мяч) и обозначения слоёв: $z^{[l]} = W^{[l]} a^{[l-1]} + b^{[l]}$, $a^{[l]} = g(z^{[l]})$. Конспект подчёркивает: без нелинейных функций активации композиция слоёв осталась бы линейной функцией, и глубина ничего бы не дала. Используются сигмоида, $\tanh$ и ReLU.

Векторизация

Вычислять нейроны циклом медленно; вместо этого слой — это одно умножение матрицы на вектор, а пакет из $m$ примеров — умножение матрицы на матрицу, где примеры сложены столбцами ($X \in \mathbb{R}^{n \times m}$). Сдвиг $b^{[l]}$ прибавляется ко всем столбцам — это транслирование (broadcasting), как в NumPy.

Обратное распространение

Для обучения нужны градиенты потерь по всем $W^{[l]}, b^{[l]}$. Конспект выводит их по цепному правилу для трёхслойной сети с бинарной кросс-энтропией, начиная с последнего слоя (он ближе к выходу, его влияние на потери проще), и показывает, что для каждого слоя достаточно знать «ошибку» следующего:

$$\frac{\partial \mathcal{L}}{\partial W^{[l]}} = \delta^{[l]} \big(a^{[l-1]}\big)^T, \qquad \delta^{[l]} = \big(W^{[l+1]}\big)^T \delta^{[l+1]} \odot g'\big(z^{[l]}\big),$$

где для выходного слоя с сигмоидой и кросс-энтропией $\delta^{[L]} = a^{[L]} - y$. Значения $z^{[l]}, a^{[l]}$ сохраняются при прямом проходе (кэшируются) и переиспользуются при обратном. Интуицию «потока градиентов» подробно разбирает наш перевод конспекта CS231n о backprop.

Как обучать

• Инициализация. Нулями нельзя: все нейроны слоя получат одинаковые градиенты и выучат одно и то же (нарушится симметрия); то же при одинаковых ненулевых значениях. Берут малые случайные значения или схему, сохраняющую дисперсию сигналов от слоя к слою. Конспект называет её «Xavier/He» и даёт формулу с дисперсией $\frac{2}{n^{[l]} + n^{[l-1]}}$.
• Оптимизация. Полный градиентный спуск точен, но дорог; стохастический — шумный; на практике используют мини-батчи. Ускорение — момент: скорость $v$ — экспоненциальное среднее градиентов, $v := \beta v + (1 - \beta) \nabla J$, а шаг делается по $v$, как машина, которая продолжает ехать по инерции.
• Анализ и регуляризация. Пример конспекта: 96% точности на обучении и 64% на тесте — переобучение. Лекарства: больше данных, регуляризация, менее глубокая модель. L2-регуляризация добавляет $\frac{\lambda}{2} \lVert W \rVert^2$, и шаг превращается в $W := (1 - \alpha\lambda) W - \alpha \nabla J$ — веса на каждом шаге «усыхают» (weight decay).
• Разделение параметров. Логистическая регрессия на пикселях учит отдельный вес для каждой позиции: если мяч ни разу не встречался в левом верхнем углу, его там не найдут. Свёрточный фильтр, скользящий по картинке с одними и теми же весами, решает проблему — это идея CNN (наш перевод конспекта CS231n о свёрточных сетях).

Примечание о формуле инициализации

Формула из конспекта, $\mathcal{N}\big(0, \frac{2}{n^{[l]} + n^{[l-1]}}\big)$, — это инициализация Глоро (Xavier). Инициализация Хэ (He), рассчитанная на ReLU, использует дисперсию $\frac{2}{n^{[l-1]}}$ (по числу входов). В PyTorch это nn.init.xavier_normal_ и nn.init.kaiming_normal_ соответственно. Подробнее — урок 3.4.1.

Обучение без учителя

k-средних

Даны точки без меток; нужно разбить их на $k$ групп. Алгоритм: случайно выбрать $k$ центроидов $\mu_j$ (например, $k$ случайных точек выборки), затем повторять до сходимости два шага:

1. назначение: каждую точку отнести к ближайшему центроиду, $c^{(i)} := \arg\min_j \lVert x^{(i)} - \mu_j \rVert^2$;
2. обновление: каждый центроид сдвинуть в среднее своих точек.

Алгоритм — это покоординатный спуск по функции искажения $J(c, \mu) = \sum_i \lVert x^{(i)} - \mu_{c^{(i)}} \rVert^2$: шаг 1 минимизирует её по $c$ при фиксированных $\mu$, шаг 2 — по $\mu$ при фиксированных $c$. Значит, $J$ монотонно убывает и алгоритм сходится, но только к локальному минимуму: функция невыпукла. Поэтому k-средних запускают несколько раз с разной инициализацией и берут результат с наименьшим $J$.

Смесь гауссиан и EM

Мягкая версия кластеризации — смесь гауссиан: у каждой точки есть скрытая метка $z^{(i)} \sim \text{Multinomial}(\phi)$, а при данной метке $x^{(i)} \mid z^{(i)} = j \sim \mathcal{N}(\mu_j, \Sigma_j)$. Если бы метки $z$ были известны, оценка параметров свелась бы к GDA из первого конспекта. Но они скрыты, поэтому EM-алгоритм чередует:

• E-шаг: для каждой точки вычислить «ответственность» каждой компоненты — апостериорную вероятность $w_j^{(i)} = p(z^{(i)} = j \mid x^{(i)}; \phi, \mu, \Sigma)$ по формуле Байеса;
• M-шаг: пересчитать параметры как в GDA, но со взвешенными точками: $\phi_j$ — средняя ответственность, $\mu_j$ — взвешенное среднее, $\Sigma_j$ — взвешенная ковариация.

Это похоже на k-средних, только вместо «жёсткого» назначения точки одному кластеру — «мягкое». И, как k-средних, EM может застрять в локальном оптимуме.

EM в общем виде

Общая задача: максимизировать правдоподобие $\ell(\theta) = \sum_i \log \sum_{z} p(x^{(i)}, z; \theta)$ при скрытых $z$. Логарифм суммы неудобен. Ключ — неравенство Йенсена: для выпуклой $f$ выполняется $\mathbb{E}[f(X)] \geq f(\mathbb{E}X)$ (для вогнутого логарифма — наоборот), с равенством, когда величина постоянна. Вводим для каждой точки любое распределение $Q_i(z)$ и получаем нижнюю оценку правдоподобия (сейчас её называют ELBO):

$$\ell(\theta) \geq \sum_i \sum_{z} Q_i(z) \log \frac{p(x^{(i)}, z; \theta)}{Q_i(z)} .$$

Оценка точна, если $Q_i(z) = p(z \mid x^{(i)}; \theta)$. Отсюда EM: E-шаг — сделать оценку точной в текущей точке, выбрав $Q_i$ равным апостериорному распределению скрытых переменных; M-шаг — максимизировать оценку по $\theta$. Поскольку оценка касается правдоподобия в текущей точке и лежит ниже него везде, правдоподобие на каждой итерации не убывает. С другой стороны, EM — это покоординатный подъём по нижней оценке $J(Q, \theta)$. Для смеси гауссиан эта общая схема в точности даёт формулы выше. Та же нижняя оценка — основа вариационных автокодировщиков (урок 9.1.3).

Анализ главных компонент (PCA)

PCA ищет подпространство малой размерности $k$, в котором «живут» данные. Подготовка: центрировать данные (вычесть среднее) и, если признаки в разных единицах, нормировать каждый на его стандартное отклонение. Первая главная компонента — направление $u$ (единичный вектор), проекции на которое имеют наибольшую дисперсию:

$$\max_{\lVert u \rVert = 1} \; \frac{1}{m} \sum_i \big(x^{(i)T} u\big)^2 = u^T \Sigma u ,$$

где $\Sigma$ — выборочная ковариационная матрица. Максимум достигается на главном собственном векторе $\Sigma$; $k$ компонент — это $k$ собственных векторов с наибольшими собственными числами, а новое представление точки — её координаты $(u_1^T x, \ldots, u_k^T x)$. Эквивалентная формулировка — минимизировать ошибку реконструкции (сумму квадратов расстояний от точек до подпространства). Применения из конспекта: сжатие и визуализация данных, предобработка перед обучением (меньше признаков — меньше переобучения), подавление шума, «собственные лица» (eigenfaces) для распознавания лиц. На практике собственные векторы считают через сингулярное разложение матрицы данных (см. наш перевод MIT 18.06 о SVD).

Коротко: обучение с подкреплением (часть XIII)

Последний большой конспект вводит марковские процессы принятия решений (состояния, действия, вероятности переходов, награды, коэффициент дисконтирования), уравнения Беллмана, алгоритмы итерации по ценности и итерации по стратегии, обучение модели переходов по опыту и непрерывные состояния — дискретизацию и приближение функции ценности (fitted value iteration). Эти темы подробно разобраны в уроке 6.0.1 «MDP и уравнения Беллмана».

Словарик

EN	RU
end-to-end learning	сквозное обучение
vectorization, broadcasting	векторизация, транслирование
symmetry breaking (initialization)	нарушение симметрии (при инициализации)
momentum, weight decay	момент, затухание весов
parameter sharing	разделение параметров
k-means, distortion function	k-средних, функция искажения
mixture of Gaussians, responsibility	смесь гауссиан, ответственность компоненты
Jensen’s inequality, lower bound (ELBO)	неравенство Йенсена, нижняя оценка (ELBO)
principal components, reconstruction error	главные компоненты, ошибка реконструкции
value iteration, policy iteration	итерация по ценности, итерация по стратегии