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

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

Пересказ своими словами конспектов CS229 «Support Vector Machines», «Learning Theory» и «Regularization and model selection» Эндрю Ына. Лицензии у конспектов нет, поэтому это не перевод: формулы и порядок тем сохранены, объяснения — наши. Предыдущий конспект — обучение с учителем, путеводитель — здесь.

Часть V. Машины опорных векторов

Зазоры

Для бинарной классификации удобно брать метки $y \in \lbrace -1, 1 \rbrace$ и классификатор $h_{w,b}(x) = \operatorname{sign}(w^T x + b)$. Интуиция: хорошо, когда классификатор не просто прав, а прав уверенно — точки далеко от разделяющей гиперплоскости.

• Функциональный зазор примера: $\hat\gamma^{(i)} = y^{(i)} (w^T x^{(i)} + b)$. Положителен, если пример классифицирован верно; чем больше, тем увереннее. Недостаток — его можно раздуть, просто умножив $w, b$ на число.
• Геометрический зазор — настоящее расстояние до гиперплоскости: $\gamma^{(i)} = \hat\gamma^{(i)} / \lVert w \rVert$. Он не меняется при масштабировании параметров.

Зазор выборки — минимальный зазор по всем примерам.

Классификатор с оптимальным зазором

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

$$\min_{w, b} \; \frac{1}{2} \lVert w \rVert^2 \quad \text{при условии} \quad y^{(i)} (w^T x^{(i)} + b) \geq 1, \; i = 1, \ldots, m .$$

Её можно решить готовым пакетом квадратичного программирования, но двойственная форма даёт больше.

Двойственность Лагранжа

Конспект напоминает общую теорию: для задачи минимизации $f(w)$ с ограничениями-неравенствами $g_i(w) \leq 0$ и равенствами $h_i(w) = 0$ строится лагранжиан $\mathcal{L}(w, \alpha, \beta)$; прямая задача — минимум по $w$ от максимума по множителям, двойственная — наоборот. Всегда $d^* \leq p^*$, а при выпуклости и выполнимости ограничений $d^* = p^*$, и решение удовлетворяет условиям Каруша — Куна — Таккера (ККТ). Важнейшее из них — дополняющая нежёсткость: $\alpha_i g_i(w) = 0$, то есть множитель $\alpha_i > 0$ только у «активных» ограничений.

Для SVM это значит: $\alpha_i > 0$ только у точек с функциональным зазором ровно 1 — у опорных векторов, ближайших к границе. Их обычно мало. Двойственная задача:

$$\max_\alpha \; \sum_i \alpha_i - \frac{1}{2} \sum_{i,j} y^{(i)} y^{(j)} \alpha_i \alpha_j \langle x^{(i)}, x^{(j)} \rangle \quad \text{при} \quad \alpha_i \geq 0, \;\; \sum_i \alpha_i y^{(i)} = 0,$$

а предсказание выражается через скалярные произведения нового $x$ только с опорными векторами: $w^T x + b = \sum_i \alpha_i y^{(i)} \langle x^{(i)}, x \rangle + b$.

Ядра

Данные входят и в обучение, и в предсказание только через скалярные произведения. Если перейти к признакам $\phi(x)$ (например, ко всем мономам степени до $d$), достаточно уметь вычислять ядро $K(x, z) = \phi(x)^T \phi(z)$ — часто гораздо дешевле, чем само $\phi(x)$. Пример: $K(x, z) = (x^T z)^2$ соответствует всем попарным произведениям признаков, $n^2$ штук, а вычисляется за $O(n)$. Гауссово ядро $K(x, z) = \exp(-\lVert x - z \rVert^2 / 2\sigma^2)$ соответствует бесконечномерному $\phi$ и интуитивно измеряет похожесть точек.

Когда функция $K$ — допустимое ядро? Теорема Мерсера: тогда и только тогда, когда для любого конечного набора точек матрица $K_{ij} = K(x^{(i)}, x^{(j)})$ симметрична и положительно полуопределена. «Трюк с ядром» применим не только к SVM, а к любому алгоритму, записанному через скалярные произведения (перцептрон, регрессия и др.).

Мягкий зазор и SMO

Если данные неразделимы или есть выбросы, разрешаем нарушения зазора с штрафом (L1-регуляризация):

$$\min \; \frac{1}{2} \lVert w \rVert^2 + C \sum_i \xi_i \quad \text{при} \quad y^{(i)} (w^T x^{(i)} + b) \geq 1 - \xi_i, \;\; \xi_i \geq 0 .$$

В двойственной задаче меняется лишь ограничение: $0 \leq \alpha_i \leq C$. Параметр $C$ задаёт компромисс между широким зазором и числом ошибок.

Решать двойственную задачу удобно алгоритмом SMO (Платт): это покоординатный подъём, но поскольку ограничение $\sum \alpha_i y^{(i)} = 0$ не даёт менять одну переменную, на каждом шаге меняют пару $\alpha_i, \alpha_j$. Для пары оптимум находится аналитически (квадратичная функция одной переменной, обрезанная до отрезка), поэтому каждый шаг очень дешёв, а выбор пары по эвристикам и проверка условий ККТ дают быструю сходимость.

Часть VI. Теория обучения

Смещение и дисперсия

Обобщающая ошибка модели складывается из двух источников. Смещение (bias) — ошибка из-за того, что класс моделей слишком прост (прямая для нелинейной зависимости): она останется даже при бесконечных данных. Дисперсия (variance) — ошибка из-за того, что модель подстраивается под случайности конкретной выборки (полином высокой степени). Цель теории — понять этот компромисс количественно.

Инструменты: оценка объединения и Хёфдинг

• Оценка объединения (union bound): вероятность хотя бы одного из $k$ событий не больше суммы их вероятностей.
• Неравенство Хёфдинга (в теории обучения его часто называют оценкой Чернова): среднее $m$ независимых бернуллиевских величин отклоняется от их математического ожидания больше чем на $\gamma$ с вероятностью не больше $2 \exp(-2 \gamma^2 m)$.

Рамка — минимизация эмпирического риска: выбираем гипотезу $\hat h$ с наименьшей ошибкой на обучающей выборке $\hat\varepsilon(h)$ и хотим гарантий на её настоящую (обобщающую) ошибку $\varepsilon(h)$.

Конечный класс гипотез

Для одной гипотезы $\hat\varepsilon(h)$ — среднее бернуллиевских величин, и Хёфдинг даёт его близость к $\varepsilon(h)$. Оценка объединения по всем $k$ гипотезам даёт равномерную сходимость: с вероятностью не меньше $1 - \delta$ все гипотезы одновременно удовлетворяют $\lvert \hat\varepsilon(h) - \varepsilon(h) \rvert \leq \gamma$, если

$$m \geq \frac{1}{2\gamma^2} \log \frac{2k}{\delta} .$$

Это сложность выборки: нужное число примеров растёт лишь логарифмически по числу гипотез. Отсюда же оценка качества выбранной гипотезы: $\varepsilon(\hat h) \leq \min_h \varepsilon(h) + 2 \sqrt{\frac{1}{2m} \log \frac{2k}{\delta}}$. Первое слагаемое играет роль смещения, второе — дисперсии: переход к большему классу гипотез уменьшает первое и увеличивает второе.

Бесконечный класс и VC-размерность

Для классов с вещественными параметрами $k$ бесконечно. Грубый приём: на компьютере параметр — это 64 бита, так что класс с $d$ параметрами конечен и содержит $2^{64d}$ гипотез; подстановка даёт сложность выборки, линейную по $d$. Строго это делается через VC-размерность: класс $\mathcal{H}$ разбивает (shatters) множество точек, если реализует на нём любую разметку; VC-размерность — размер наибольшего множества, которое класс может разбить. Например, линейные классификаторы на плоскости разбивают некоторые три точки, но никакие четыре, так что их VC-размерность равна 3. Теорема Вапника: с высокой вероятностью отклонение эмпирической ошибки от настоящей ограничено величиной порядка $\sqrt{\frac{d}{m} \log \frac{m}{d}}$, а значит, нужное число примеров линейно по VC-размерности. Для большинства моделей она примерно равна числу параметров.

Часть VII. Регуляризация и выбор модели

Кросс-валидация

Как выбрать модель (степень полинома, $C$ в SVM, ширину окна в LWR)? Ошибка на обучающей выборке не годится — она всегда предпочтёт самую сложную модель.

• Отложенная выборка (hold-out): обучаем на ~70% данных, выбираем модель по ошибке на оставшихся ~30%, затем можно переобучить выбранную модель на всех данных.
• k-кратная кросс-валидация: делим данные на $k$ частей, по очереди обучаемся на $k - 1$ и проверяем на оставшейся, усредняем. Типичный выбор — $k = 10$; данных расходуется меньше, вычислений больше.
• Leave-one-out ($k = m$) — когда данных совсем мало.

Отбор признаков

Когда признаков очень много (например, слова в тексте), а релевантных мало, полезно их отобрать.

• Обёрточные методы: прямой поиск — начинаем с пустого набора и жадно добавляем признак, который сильнее всего улучшает ошибку на кросс-валидации; обратный поиск — начинаем со всех и удаляем. Хорошо, но дорого: $O(n^2)$ запусков обучения.
• Фильтры: оцениваем каждый признак отдельно, например по корреляции или взаимной информации $MI(x_i, y)$ с меткой, и берём $k$ лучших (а $k$ выбираем кросс-валидацией). Дёшево, особенно для текстов.

Байесовский взгляд и регуляризация

Частотный подход считает $\theta$ неизвестной константой и оценивает её максимумом правдоподобия. Байесовский — считает $\theta$ случайной величиной с априорным распределением $p(\theta)$. Полное байесовское предсказание требует интеграла по апостериорному распределению, поэтому часто берут точечную MAP-оценку — максимум апостериорной вероятности:

$$\theta_{\text{MAP}} = \arg\max_\theta \prod_i p(y^{(i)} \mid x^{(i)}, \theta)\, p(\theta) .$$

С гауссовым априорным $\theta \sim \mathcal{N}(0, \tau^2 I)$ логарифм априорного распределения — это минус $\lVert \theta \rVert^2$ с коэффициентом, то есть MAP-оценка — это максимальное правдоподобие с L2-регуляризацией. Такие оценки обычно имеют меньшую норму и меньше переобучаются; байесовская логистическая регрессия, по словам конспекта, хорошо работает для классификации текстов даже при числе признаков, намного превышающем число примеров.

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

• Обобщение, переобучение и кросс-валидация на практике — урок 2.1.2, метрики — 2.2.3.
• Классические модели (деревья, kNN) — 2.3.1; SVM в scikit-learn — sklearn.svm.SVC(kernel="rbf", C=...).
• Следующий конспект — глубокое обучение и обучение без учителя.

Словарик

EN	RU
functional / geometric margin	функциональный / геометрический зазор
support vectors	опорные векторы
Lagrange duality, KKT conditions	двойственность Лагранжа, условия Каруша — Куна — Таккера
complementary slackness	дополняющая нежёсткость
kernel trick, Mercer’s theorem	трюк с ядром, теорема Мерсера
soft margin, coordinate ascent	мягкий зазор, покоординатный подъём
empirical risk minimization	минимизация эмпирического риска
union bound, Hoeffding inequality	оценка объединения, неравенство Хёфдинга
sample complexity, VC dimension, shattering	сложность выборки, VC-размерность, разбиение
hold-out, k-fold, leave-one-out	отложенная выборка, k-кратная кросс-валидация, «по одному»
forward search, filter feature selection	прямой поиск, фильтрующий отбор признаков
MAP estimate, prior	MAP-оценка, априорное распределение