Почему устойчивую классификацию так сложно обучить эффективно

С чего начинается проблема

Возьмите обученный классификатор изображений. Он уверенно отличает панду от гиббона. Теперь прибавьте к пикселям панды шум амплитудой в доли процента — глаз разницы не заметит, а сеть с вероятностью 99% скажет «гиббон». Это не гипотетика: подобные состязательные примеры¹ воспроизводятся на моделях любого масштаба, от учебных до промышленных.

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

Что значит «устойчивость» формально

Обычная задача обучения: найти гипотезу, которая ошибается редко на распределении. Робастная версия добавляет противника. Для каждого примёра он может сдвинуть вход в пределах заданного радиуса (например, по метрике L∞ — покоординатно не больше epsilon) и хочет вызвать ошибку. Алгоритм должен выдать классификатор, который остаётся точным после худшего допустимого сдвига.

Разница между этими двумя постановками невелика на словах и огромна по сложности. Появляется вложенный максимум внутри минимума — так называемая min-max задача, — и именно он делает обучение тяжёлым.

Где именно возникает вычислительная стена

Есть классы гипотез, для которых обычное (неробастное) обучение решается за полиномиальное время, а робастное — вычислительно неразрешимо при стандартных криптографических предположениях. То есть данных достаточно, статистически задача решаема, но никакой эффективный алгоритм не найдёт ответ быстрее, чем перебором.

Это разделение — ключевое. Оно говорит, что устойчивость стоит дорого не из-за инженерных недоработок, а принципиально. Три источника сложности стоит держать в голове:

• Разрыв статистики и вычислений. Выборки хватает, чтобы устойчивый классификатор в принципе существовал, но найти его за полиномиальное время нельзя.
• Цена внутреннего максимума. Оценить худшую атаку на каждую точку — сама по себе задача оптимизации, часто невыпуклая. Точное решение недостижимо, приближённое даёт слабые гарантии.
• Хрупкость сертификатов. Даже если модель обучили, доказать её устойчивость (сертификация) — отдельная тяжёлая задача, и эвристики здесь регулярно рушатся под адаптивными атаками.

Устойчивость к атакам — не переключатель, который включают на последнем слое. Это требование, меняющее сложность самой задачи обучения, а не только её решение.

Win-win: когда тупик оказывается развилкой

Самое интересное начинается там, где вычислительная трудность перестаёт быть только плохой новостью. В теории обучения такие результаты называют win-win: любой исход задачи полезен.

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

Более сильная версия win-win связывает робастность с другими свойствами. Например: либо задачу можно решить устойчиво, либо из невозможности следует конструкция криптографического примитива (скажем, односторонней функции). Невозможность обучения превращается в строительный материал для криптографии.

Почему это не игра в слова

Практический смысл в том, что win-win результаты дают ориентир, куда не надо вкладывать инженерные усилия. Если известно, что робастное обучение для вашего класса моделей эквивалентно взлому предположительно стойкого шифра, то никакая новая архитектура и никакой объём GPU не помогут: вы бьётесь не о недостаток идей, а о криптографический барьер.

Что с этим делать на практике

Полная гарантированная устойчивость для произвольных моделей недостижима, но есть подходы с честными, пусть и ограниченными, гарантиями. Порядок разумных шагов при построении устойчивого пайплайна:

1. Определите модель угрозы. Метрика (L∞, L2), радиус epsilon, доступ атакующего к весам. Без этого «устойчивость» — пустое слово.
2. Выберите между эвристикой и сертификатом. Состязательное обучение (adversarial training) даёт эмпирическую стойкость без доказательства; сертифицированные методы (например, randomized smoothing) дают гарантию, но для меньшего радиуса и ценой точности на чистых данных.
3. Тестируйте адаптивными атаками. Проверка одной фиксированной атакой почти ничего не значит — атакующий подстроится под вашу защиту.
4. Заложите цену устойчивости в бюджет. Робастное обучение дороже по времени в разы; сертификация — ещё дороже. Это ожидаемо, а не признак ошибки.

Randomized smoothing здесь показателен: вместо того чтобы бороться с невыпуклым внутренним максимумом напрямую, метод усредняет предсказания по зашумлённым копиям входа и получает вероятностный сертификат устойчивости в L2. Гарантия честная, но радиус ограничен, и на чистых данных точность падает — ровно та плата за устойчивость, о которой говорит теория.

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

¹ Состязательный пример (adversarial example) — вход, специально изменённый на малую, часто незаметную человеку величину так, чтобы модель выдала неверный ответ, сохраняя при этом исходный смысл для наблюдателя.