Урок 26. Седловые задачи, игры и устойчивость

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

Две цели, направленные друг против друга

В прошлых уроках спуск искал минимум — точку, где вокруг всё идёт вверх. Но многие задачи устроены иначе. Классификатор хочет отвечать верно; атакующий хочет незаметно его обмануть. Генератор подделок хочет обмануть эксперта; эксперт хочет отличить подделку. Это не минимизация, а игра двух сторон с противоположными целями, и её короткая запись —

\min_x\ \max_y\ F(x,y).

Один игрок выбирает $x$ , чтобы уменьшить $F$ ; другой выбирает $y$ , чтобы её увеличить. Ни один не управляет обоими рычагами. Решение такой задачи — не дно ямы, а особая точка, где интересы уравновешены.

Седловая точка

Представьте поверхность в форме седла: вдоль одной оси — низина, вдоль другой — гребень. В центре обе кривизны встречаются. Такая точка — минимум по $x$ и одновременно максимум по $y$ . Простейший пример —

F(x,y)=x^2-y^2.

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

Слева трёхмерная седловая поверхность F равно x в квадрате минус y в квадрате с отмеченной седловой точкой в центре; справа траектории одновременного спуска-подъёма: для игры F равно x на y красная спираль раскручивается и расходится, для седла F равно x в квадрате минус y в квадрате зелёная линия сходится к равновесию в начале координат — Рис. 26.1. Седло и спуск-подъём
Слева — седловая поверхность $F=x^2-y^2$ : по одной оси низина, по другой гребень. Справа — как ведёт себя одновременный спуск-подъём (об этом ниже): на седле он сходится к равновесию, а на игре $F=xy$ раскручивается в спираль и расходится.

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

УпражнениеНайдите седло

Для $F(x,y)=x^2-y^2$ найдите все точки, где обе частные производные равны нулю. Проверьте, минимум это, максимум или седло, глядя на поведение вдоль осей $x$ и $y$ .

Сверить вычисление

$\partial F/\partial x=2x=0$ и $\partial F/\partial y=-2y=0$ дают единственную стационарную точку $(0,0)$ . Вдоль оси $x$ функция $x^2$ имеет там минимум, вдоль оси $y$ функция $-y^2$ — максимум. Значит, $(0,0)$ — седловая точка: не минимум и не максимум, потому что часть направлений повышает $F$ , а часть понижает.

Минимакс: равновесие противников

У игры двух сторон с нулевой суммой есть замечательное свойство, доказанное Джоном фон Нейманом в $1928$ году. Оказывается, порядок ходов не важен: результат осторожного игрока, который минимизирует, приготовившись к худшему ответу противника, совпадает с результатом того, кто максимизирует, ожидая худшего для себя. Формально

\min_x\max_y F=\max_y\min_x F.

Это общее значение и есть цена игры, а точка, где оно достигается, — равновесие: ни одному игроку не выгодно менять свой ход в одиночку. Для гладкой функции такое равновесие как раз и есть седловая точка.

Равенство порядка не даётся даром: оно верно для игр с нулевой суммой и подходящей выпуклостью-вогнутостью. В общем случае осторожный минимизатор оказывается в невыгоде — тот, кто ходит вторым, всегда может подстроиться, поэтому $\min_x\max_y F\ge\max_y\min_x F$ . Разрыв между этими величинами измеряет, насколько игра «нечестна» к тому, кто раскрывает ход первым.

УпражнениеМинимакс и максимин

Рассмотрите $F(x,y)=(x-y)^2$ на отрезке $x,y\in[0,1]$ . Найдите $\min_x\max_y F$ и $\max_y\min_x F$ . Совпали ли они? Что это говорит о преимуществе второго хода?

Сверить рассуждение

Внутренний максимум по $y$ : при фиксированном $x$ величина $(x-y)^2$ наибольшая на дальнем конце, значение $\max(x^2,(1-x)^2)$ ; минимум этого по $x$ достигается в $x=\tfrac12$ и равен $\tfrac14$ . Значит, $\min_x\max_y F=\tfrac14$ . Наоборот: внутренний минимум по $x$ при фиксированном $y$ равен нулю (взять $x=y$ ), поэтому $\max_y\min_x F=0$ . Величины не совпали: $\tfrac14>0$ . Тот, кто ходит вторым, видит выбор соперника и подстраивается — оттого у него преимущество, а равенство минимакса здесь не выполняется.

Спуск-подъём: почему игру трудно решить

Раз равновесие — седло, нельзя ли дойти до него градиентом? Простейшая идея: пусть минимизирующий игрок делает шаг спуска, а максимизирующий — шаг подъёма, одновременно. Это метод спуска-подъёма. Беда в том, что он часто не сходится. На игре $F=xy$ шаги закручивают траекторию по спирали и уводят её всё дальше от равновесия, а не к нему. На седле $F=x^2-y^2$ спуск-подъём сходится, но стоит осям связаться — и он начинает кружить.

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

Это не мелкая неприятность, а сердце проблемы обучения состязательных систем. Там, где обычный спуск катится к минимуму почти всегда, спуск-подъём в игре легко зацикливается, и приходится изобретать хитрые поправки — усреднение ходов, разные шаги у игроков, заглядывание вперёд, — чтобы утихомирить вращение.

УпражнениеШаг спуска-подъёма

Для игры $F(x,y)=xy$ выпишите одновременные шаги: минимизирующий игрок идёт против $\partial F/\partial x$ , максимизирующий — по $\partial F/\partial y$ , оба с шагом $\eta$ . Стартуя из $(1,0)$ , сделайте два шага при $\eta=1$ и проследите, приближается ли точка к равновесию $(0,0)$ .

Сверить вычисление

$\partial F/\partial x=y$ , $\partial F/\partial y=x$ . Шаги: $x\leftarrow x-\eta y$ , $y\leftarrow y+\eta x$ . Из $(1,0)$ : первый шаг даёт $x=1-0=1$ , $y=0+1=1$ , то есть $(1,1)$ . Второй шаг: $x=1-1=0$ , $y=1+1=2$ , то есть $(0,2)$ . Расстояние до равновесия выросло с $1$ до $2$ : спуск-подъём не приближается, а раскручивается — ровно та спираль, что на рисунке.

Атака на классификатор

Самое наглядное применение седловых задач — адверсариальные атаки. Обучив классификатор, мы решали задачу минимизации: подобрать веса, уменьшающие потерю. Атакующий решает противоположную: не трогая веса, чуть-чуть сдвинуть вход, чтобы ту же потерю увеличить и ответ испортить. Веса и вход меняются местами: раньше вход был дан, а веса подбирались, — теперь веса заморожены, а свободен вход. Формально это и есть внешний максимум в игре $\min_{\text{веса}}\max_{\text{вход}}$ , только атакующий работает с уже обученной моделью.

Сдвигать нужно с умом. Градиент потери по входу $\nabla_x L$ указывает, куда толкнуть $x$ , чтобы потеря росла быстрее всего. Метод быстрого знака (FGSM) делает шаг фиксированного размера в эту сторону:

x'=x+\varepsilon\cdot\operatorname{sign}\big(\nabla_x L\big).

Здесь $\varepsilon$ — бюджет искажения: насколько сильно позволено менять каждый признак. Проверим на реальном классификаторе ирисов, обученном до $97\%$ точности. Будем понемногу растить $\varepsilon$ и считать, сколько верных ответов ломает атака.

Кривая: по горизонтали бюджет искажения эпсилон в долях стандартного отклонения, по вертикали процент сломанных верных ответов; кривая монотонно растёт, при эпсилон 0,3 сломано 27 процентов, при 0,5 — 53 процента, при 0,8 — 92 процента — Рис. 26.2. Точный, но хрупкий
Классификатор точен на $97\%$ , но легко ломается. Уже при $\varepsilon=0{,}3$ (треть стандартного отклонения) атака портит $27\%$ верных ответов, при $\varepsilon=0{,}5$ — больше половины, при $\varepsilon=0{,}8$ — почти все. Точность на честных данных ничего не говорит об устойчивости к искажению.

УпражнениеНаправление атаки

Почему FGSM двигает вход по знаку градиента, а не по самому градиенту $\nabla_x L$ ? Что это даёт при ограниченном бюджете на каждый признак?

Сверить рассуждение

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

Один цветок, уверенная ошибка

Кривая — это статистика. Заглянем в один случай, чтобы почувствовать масштаб искажения.

Слева столбцы четырёх признаков одного цветка ириса до и после атаки, сдвиги крошечные; подпись показывает сдвиг в сантиметрах порядка десятых долей; справа столбцы уверенности модели: до атаки уверенно versicolor, после атаки побеждает virginica — Рис. 26.3. Незаметное искажение, уверенная ошибка
Один цветок вида versicolor, который модель узнавала с уверенностью $90\%$ . Атака при $\varepsilon=0{,}25$ сдвинула четыре измерения на доли сантиметра — столько же наберётся от неточности линейки. Но этого хватило: модель уверенно назвала цветок virginica. Искажение, невидимое человеку, переломило ответ.

Вот что тревожит в адверсариальных примерах. Дело не в том, что модель плоха, — она точна. Дело в том, что её решение опирается на комбинации признаков, к которым человеческое зрение нечувствительно, и потому её можно обмануть сдвигом, которого мы даже не заметим. Для распознавания дорожных знаков или лиц это уже вопрос безопасности.

Робастное обучение

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

\min_{\text{веса}}\ \max_{\|\delta\|\le\varepsilon}\ L(x+\delta).

На практике внутренний максимум приближают той же атакой FGSM, добавляя искажённые примеры в обучение. Модель становится устойчивее, но обычно ценой небольшой потери точности на честных данных — плата за то, чтобы не рассыпаться от лёгкого толчка. Здесь виден общий закон седловых задач: защита от худшего случая почти всегда стоит немного среднего качества, и инженер сам выбирает точку на этом обмене под свою задачу. Для игры в шахматы хрупкость безобидна, для системы, узнающей дорожные знаки, — уже нет. Идеальной защиты пока нет; это живой край исследований, и всякая новая атака рождает новую защиту, а та — новую атаку, в бесконечной той же игре.

Состязательные сети

Та же игра лежит в основе генеративных состязательных сетей. Одна сеть, генератор, учится подделывать данные; другая, дискриминатор, — отличать подделку от настоящего. Генератор минимизирует свою потерю, дискриминатор максимизирует — снова седло, снова спуск-подъём, снова риск бесконечного кружения. Оттого GAN славятся капризностью обучения: два игрока то догоняют друг друга, то срываются в осцилляции.

Русская линия: игры в движении

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

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

Лаборатория атаки

Порядок опытов. Перед вами настоящий классификатор ирисов и три цветка, которые он узнаёт верно. Выберите цветок и медленно растите бюджет искажения $\varepsilon$ . Слева видно, как крошечно сдвигаются четыре признака (и на сколько сантиметров), справа — как перестраивается уверенность модели. Поймайте момент, когда столбец верного класса уступает первенство чужому: ответ перевернулся. Обратите внимание, что для одних цветков хватает совсем малого бюджета, а для других нужен побольше — устойчивость зависит от того, насколько близко к границе между классами лежит пример.

Сборка: равновесие вместо дна

Седловая задача — это оптимизация с двумя враждебными целями, $\min_x\max_y F$ . Её решение не дно ямы, а седловая точка равновесия, где одному игроку невыгодно менять ход в одиночку; теорема фон Неймана о минимаксе гарантирует, что такое равновесие существует. Дойти до него градиентом трудно: одновременный спуск-подъём легко срывается в кружение, как на игре $F=xy$ . Эта же математика правит адверсариальными атаками — мы своими руками сломали точный на $97\%$ классификатор сдвигом входа на доли сантиметра, — и обучением состязательных сетей, и уходит корнями к дифференциальным играм Понтрягина. Устойчивость, а не только точность, становится отдельной целью. На этом мы закрываем блок оптимизации и обучения: дальше — как из обученных сетей строят системы, которые видят изображения и понимают язык.

Седловые задачи, игры и устойчивость