Алгоритм Passive-Aggressive

Материал из MachineLearning.

Статья написана с использованием LLM GPT-5.6 Sol xhigh и проверено участником Aleksandr Iakovlev 09:34, 17 июля 2026 (MSD)

Содержание

1 Постановка бинарной классификации
2 Идея и вывод обновления
3 Варианты PA, PA-I и PA-II
4 Псевдокод
5 Пошаговый пример
6 Регрессионная модификация
7 Многоклассовый случай
8 Вычислительная сложность
9 Свойства и теоретические гарантии
10 Чувствительность к шуму и практическое применение
11 Сравнение с родственными методами
12 См. также
13 Литература

Алгоритм Passive-Aggressive (PA, пассивно-агрессивный алгоритм) — семейство основанных на отступе алгоритмов онлайнового обучения. На каждом шаге базовый PA меняет текущую модель ровно настолько, насколько нужно для правильной классификации нового объекта с заданным отступом; мягкие варианты допускают нарушение этого условия. Если требуемый отступ уже достигнут, алгоритм остаётся «пассивным»; если нет — выполняет «агрессивное» обновление. Семейство предложено К. Краммером, О. Декелем, Й. Кешетом, Ш. Шалевом-Шварцем и Й. Сингером и охватывает бинарную и многоклассовую классификацию, регрессию и более общие задачи предсказания.

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

Постановка бинарной классификации

Онлайновое обучение идёт по раундам $t=1,2,\ldots$ . На раунде $t$ алгоритм получает вектор признаков $x_t\in\mathbb R^d$ , предсказывает метку

$\hat y_t={\rm sign}(w_t^\top x_t),$

затем узнаёт правильную метку $y_t\in\{-1,+1\}$ и, при необходимости, строит $w_{t+1}$ . Величина

$m_t=y_t w_t^\top x_t$

называется знаковым отступом. Положительный отступ означает правильный знак ответа, но PA требует более сильного условия $m_t\geq 1$ . Нарушение измеряется кусочно-линейной функцией потерь (hinge loss):

$\ell_t=\max\{0,\,1-y_t w_t^\top x_t\}.$

Если $\ell_t=0$ , текущий пример не вызывает обновления. Свободный член можно включить в модель, добавив к каждому $x_t$ постоянную координату; при этом эта координата также входит в норму в формулах шага.

Идея и вывод обновления

Базовый PA выбирает среди всех векторов, дающих нулевую потерю на текущем примере, ближайший к прежнему вектору весов:

$w_{t+1}=\arg\min_{w\in\mathbb R^d}\frac12||w-w_t||^2,$

при ограничении $y_t w^\top x_t\geq 1.$

Геометрически это евклидова проекция $w_t$ на полупространство допустимых весов. Близость к $w_t$ сохраняет накопленную ранее информацию, а ограничение обеспечивает единичный отступ на новом объекте.

При положительной потере лагранжиан задачи имеет вид

$L(w,\tau)=\frac12||w-w_t||^2+\tau(1-y_t w^\top x_t),\quad \tau\geq 0.$

Из условия стационарности следует

$\nabla_w L=0\quad\Longrightarrow\quad w=w_t+\tau y_t x_t.$

Подстановка этого выражения в активное ограничение даёт при $||x_t||>0$

$\tau_t=\frac{1-y_t w_t^\top x_t}{||x_t||^2}=\frac{\ell_t}{||x_t||^2}.$

С учётом случая нулевой потери закрытая формула обновления такова:

$w_{t+1}=w_t+\tau_t y_t x_t,\qquad \tau_t=\frac{\ell_t}{||x_t||^2}.$

Таким образом, отдельный график скорости обучения не задаётся: размер шага определяется текущей потерей и нормой объекта.

Варианты PA, PA-I и PA-II

Базовый PA требует полностью исправить нарушение на каждом раунде. Ошибочная метка поэтому может вызвать чрезмерно большое изменение. Два мягких варианта вводят переменную послабления $\xi$ и параметр агрессивности $C>0$ .

Для PA-I решается задача

$\min_{w,\xi}\ \frac12||w-w_t||^2+C\xi,\quad \ell(w;(x_t,y_t))\leq\xi,\quad \xi\geq0.$

Для PA-II штраф квадратичен:

$\min_{w,\xi}\ \frac12||w-w_t||^2+C\xi^2,\quad \ell(w;(x_t,y_t))\leq\xi.$

Во всех трёх случаях направление обновления одинаково, а шаг равен:

PA: $\tau_t=\frac{\ell_t}{||x_t||^2}.$
PA-I: $\tau_t=\min\left(C,\frac{\ell_t}{||x_t||^2}\right).$
PA-II: $\tau_t=\frac{\ell_t}{||x_t||^2+\frac{1}{2C}}.$

В PA-I параметр $C$ непосредственно ограничивает шаг сверху. В PA-II он плавно меняет знаменатель. В обоих вариантах увеличение $C$ делает обновление более агрессивным; универсального значения $C$ нет.

Псевдокод

Вход: поток размеченных объектов; вариант PA, PA-I или PA-II;
      C > 0 для PA-I и PA-II.
Инициализировать вектор весов нулями.

Для каждого раунда:
    получить объект x;
    выдать знак скалярного произведения весов и x;
    получить правильную метку y;
    вычислить hinge loss и квадрат нормы x;
    если loss равен нулю:
        оставить веса без изменения;
    иначе:
        вычислить tau по формуле выбранного варианта;
        прибавить к весам tau * y * x.

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

Пошаговый пример

Рассмотрим базовый PA без свободного члена, начиная с $w_1=(0,0)$ .

Раунд	$(x_t,y_t)$	Отступ $m_t$	Потеря $\ell_t$	Шаг $\tau_t$	Новые веса
1	$((2,1),+1)$	$0$	$1$	$1/5$	$w_2=(0{,}4,0{,}2)$
2	$((1,-1),-1)$	$-0{,}2$	$1{,}2$	$0{,}6$	$w_3=(-0{,}2,0{,}8)$
3	$((0,1),+1)$	$0{,}8$	$0{,}2$	$0{,}2$	$w_4=(-0{,}2,1{,}0)$

Например, на втором раунде $w_2^\top x_2=0{,}2$ , поэтому знаковый отступ равен $(-1)\cdot0{,}2=-0{,}2$ . После обновления получаем $w_3^\top x_2=-1$ и новый отступ ровно $1$ . То же происходит на каждом раунде с положительной потерей: базовый PA достигает границы ограничения для текущего объекта.

Регрессионная модификация

Для онлайновой регрессии прогноз имеет вид $\hat y_t=w_t^\top x_t$ , а вместо классификационной потери используется $\varepsilon$ -нечувствительная функция

$\ell_t^{\varepsilon}=\max\{0,\,|w_t^\top x_t-y_t|-\varepsilon\},\quad \varepsilon>0.$

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

$w_{t+1}=w_t+{\rm sign}(y_t-\hat y_t)\tau_t x_t.$

Шаг $\tau_t$ задаётся теми же тремя формулами, если заменить $\ell_t$ на $\ell_t^{\varepsilon}$ . В первоисточнике показано, что бинарные границы потерь переносятся на эти регрессионные варианты через аналогичную основную лемму.

Многоклассовый случай

Пусть для каждого из $K$ классов хранится вектор $w_{t,k}$ . Предсказание выбирается по наибольшей оценке:

$\hat y_t=\arg\max_{k\in\{1,\ldots,K\}} w_{t,k}^\top x_t.$

После получения истинной метки $y_t$ выбирается самый сильный неверный конкурент

$s_t=\arg\max_{k\ne y_t} w_{t,k}^\top x_t$

и вычисляется потеря

$\ell_t=\max\{0,\,1+w_{t,s_t}^\top x_t-w_{t,y_t}^\top x_t\}.$

Специализация общей редукции из исходной работы даёт виртуальный объект с квадратом нормы $2||x_t||^2$ . Поэтому для базового варианта

$\tau_t=\frac{\ell_t}{2||x_t||^2},$

для PA-I шаг ограничивается сверху величиной $C$ , а для PA-II знаменатель дополняется слагаемым $1/(2C)$ . Меняются только два прототипа:

$w_{t+1,y_t}=w_{t,y_t}+\tau_t x_t,\qquad w_{t+1,s_t}=w_{t,s_t}-\tau_t x_t.$

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

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

Для плотного бинарного линейного классификатора вычисление оценки, нормы и обновления занимает $O(d)$ времени на объект и $O(d)$ памяти. Для разреженного объекта стоимость равна $O({\rm nnz}(x_t))$ , если операции выполняются только по ненулевым признакам.

В многоклассовой реализации прямой поиск максимальной оценки требует $O(Kd)$ времени (или $O(K{\rm nnz}(x_t))$ для разреженных данных), а само обновление двух прототипов — $O(d)$ . Память составляет $O(Kd)$ .

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

Свойства и теоретические гарантии

Ниже приведены именно детерминированные границы для произвольной последовательности из исходной статьи, а не утверждения о вероятности обобщения. Пусть $u$ — произвольный фиксированный линейный предиктор, выбранный для сравнения задним числом,

$\ell_t^*=\max\{0,1-y_tu^\top x_t\},\qquad ||x_t||\leq R,$

а $M$ — число ошибок классификации.

Если существует $u$ с нулевой потерей на всех раундах, то для базового PA

$\sum_{t=1}^{T}\ell_t^2\leq||u||^2R^2.$

Поскольку при ошибке $\ell_t\geq1$ , эта же правая часть ограничивает $M$ .

Для PA-I на произвольной, не обязательно разделимой последовательности доказано

$M\leq\max\left\{R^2,\frac1C\right\}\left(||u||^2+2C\sum_{t=1}^{T}\ell_t^*\right).$

Для PA-II при тех же обозначениях доказана граница квадратичной накопленной потери

$\sum_{t=1}^{T}\ell_t^2\leq\left(R^2+\frac1{2C}\right)\left(||u||^2+2C\sum_{t=1}^{T}(\ell_t^*)^2\right).$

Эти результаты сравнивают PA с одним фиксированным предиктором и применимы как к разделимым, так и к неразделимым данным в указанных формулировках. Они не означают автоматической сходимости к решению пакетного SVM и сами по себе не являются оценкой качества на независимой случайной выборке.

Чувствительность к шуму и практическое применение

Базовый PA исправляет текущий пример полностью, поэтому ошибочная метка может резко сдвинуть разделяющую гиперплоскость и вызвать ошибки на следующих раундах. PA-I ограничивает величину шага, а PA-II смягчает её непрерывно. В экспериментах исходной работы мягкие варианты превосходили базовый PA при высоком уровне искусственно добавленного шума, но это наблюдение не является универсальной гарантией для любых данных.

Норма объекта входит в знаменатель шага, поэтому масштабирование признаков существенно. На практике признаки нормируют согласованным способом, а $C$ и, для регрессии, $\varepsilon$ выбирают по отдельному валидационному потоку или по проверке, сохраняющей временной порядок. Малый $C$ означает осторожные, но более медленные изменения; большой $C$ приближает поведение к базовому PA и повышает влияние отдельных наблюдений.

PA удобен, когда объекты поступают последовательно и модель требуется обновлять без повторного обучения на всей истории: при фильтрации и тематической классификации текстовых потоков, классификации событий и сигналов, распознавании образов, а регрессионный вариант — при последовательном прогнозировании числовых величин. Исходная работа демонстрирует многоклассовые варианты на USPS и MNIST, а также формулирует расширения для ранжирования меток и предсказания последовательностей. При изменении распределения во времени базовый PA продолжает адаптироваться, но специальные гарантии для дрейфа концепции требуют дополнительных методов забывания или окон.

Линейный PA выдаёт отступ, а не калиброванную вероятность класса. Если приложению нужны вероятности, требуется отдельная процедура калибровки на данных, не использованных для текущего обновления.

Сравнение с родственными методами

Метод	Когда обновляется	Как выбирается шаг	Основное отличие
Персептрон	Обычно только при ошибке знака	Постоянный или заранее заданный шаг	Правильный ответ с малым отступом не обязан вызывать обновление
SGD с hinge loss	При положительной потере	По заданному расписанию скорости обучения; часто вместе с глобальной регуляризацией	SGD — общий способ оптимизации выбранного функционала
SVM	Пакетный SVM решает общую задачу по выборке; онлайновая реализация зависит от оптимизатора	Определяется выбранным методом оптимизации	Максимизирует отступ в глобальной регуляризованной постановке
Passive-Aggressive	При отступе меньше единицы	Аналитическое решение локальной задачи проекции	Минимально меняет текущую модель, удовлетворяя или смягчая ограничение нового примера

Итак, сходство PA с персептроном состоит в аддитивном обновлении $w_t$ вдоль $y_tx_t$ , а с SVM — в hinge loss, отступе и переменной послабления. Различие задаётся не названием, а оптимизационной постановкой: PA последовательно решает по одной малой задаче для текущего примера.

См. также

Литература

Crammer K., Dekel O., Keshet J., Shalev-Shwartz S., Singer Y. Online Passive-Aggressive Algorithms // Journal of Machine Learning Research. — 2006. — Vol. 7, No. 19. — P. 551–585.
Crammer K., Singer Y. Ultraconservative Online Algorithms for Multiclass Problems // Journal of Machine Learning Research. — 2003. — Vol. 3. — P. 951–991.
Cesa-Bianchi N., Lugosi G. Prediction, Learning, and Games. — Cambridge University Press, 2006.

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_Passive-Aggressive»

Категории: Классификация | Машинное обучение