Суть метода: Интервалы как сертификаты
Команда авторов (Merkouris Papamichail, Konstantinos Varsos, Giorgos Flouris, João Marques-Silva) предложила новый подход к проблеме адверсариальной устойчивости (adversarial robustness). Вместо традиционных методов они свели задачу к проблеме обхода решетки (lattice traversal). Каждый элемент этой решетки представляет собой интервал — осевую гипер-призму, содержащую входную точку x.
В работе вводятся два ключевых понятия:
- Звуковая сертификация (Sound certification): Интервал I является звуковым, если точка x ∈ I и любое возмущение внутри I не меняет предсказание MLP.
- Полная сертификация (Complete certification): Интервал I является полным, если выход за его пределы гарантирует изменение предсказания модели.
Асимметрия вычислительной сложности
Авторы провели глубокий анализ оптимизационных задач для обоих типов сертификации и обнаружили фундаментальную асимметрию. Полная сертификация (поиск минимального интервала) решается за полиномиальное число оракульных вызовов, тогда как звуковая сертификация (поиск максимального интервала) обладает свойствами сильной вычислительной неосуществимости (strong intractability).
Результаты и система ParallelepipedoNN
Для практической реализации предложен итеративный метод "refine & verify" (уточнение и проверка) с использованием формальных верификаторов MLP. Это гарантирует звуковую максимальность и полную минимальность интервалов. Для симметричных интервалов (сфер l∞) разработаны логарифмические алгоритмы оптимизации.
| Тип сертификации | Цель | Сложность (оркульные вызовы) | Статус в литературе |
|---|---|---|---|
| Звуковая (Sound) | Максимизация интервала | Сильная неосуществимость | Хорошо изучена |
| Полная (Complete) | Минимизация интервала | Полиномиальная | Ранее не исследовалась |
Эмпирическая оценка проведена с использованием новой системы ParallelepipedoNN, демонстрирующей эффективность предложенного теоретического фреймворка на практике.
Источник: arXiv cs.AI ↗