Теоретико-игровой подход к состязательному машинному обучению

Теоретико-игровой подход к состязательному машинному обучению

Как использовать теорию игр для снижения рисков соперничества?

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

И все же они небезупречны.

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

Рассмотрим простой пример: обнаружение спама в электронной почте. Сначала стандартные классификаторы, такие как наивный байесовский классификатор, были чрезвычайно эффективны с точки зрения точности. Однако спамеры быстро научились их вводить в заблуждение, изменяя миры «спам» на их синонимы и добавляя больше «неспамовых» миров. Следовательно, для обнаружения этих уловок были изменены спам-фильтры. Но спамеры ответили новыми. Следовательно, это приводит к бесконечной игре между защитником и атакующим, пока не будет достигнуто состояние равновесия.

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

В частности, модели, основанные на теории игр, позволяют нам учитывать:

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

Таким образом, модели, основанные на теории игр, могут определить, какая подходящая стратегия необходима для уменьшения потерь защитника от атак противника.

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

В этой статье я поделюсь с вами своими ключевыми выводами о том, как использовать теорию игр для состязательного машинного обучения.

Прочитав эту статью, вы узнаете:

• Как теорию игр можно использовать в машинном обучении?
• Как теория игр может помочь в решении проблем состязательного обучения?
• Как сделать алгоритмы машинного обучения устойчивыми к злоумышленникам?

Пример подхода, основанного на теории игр

Начнем с простого примера: обнаружение спама.

В следующем разделе описывается теоретико-игровая модель, разработанная для состязательного обучения В. Лю и С. Чавалем в статье.

Общие настройки

Его можно смоделировать как игру вдвоем между Спамером (S) и Защитником (D).

• Спамер может выбрать 1), чтобы атаковать классификатор, изменяя спам-сообщения и пропуская их через фильтр спама, или 2) не атаковать, зная что некоторые спам-сообщения могут пройти.
• Защитник может выбрать 1), чтобы переобучить классификатор, чтобы поддерживать низкий уровень ошибочной классификации, или 2), чтобы не переобучать классификатор, несмотря на потенциальную увеличение количества неверно классифицированных спам-писем.

Предположим, что спаммер сделает первый шаг.

Как показано на графике ниже, существует 4 возможных результата. Можно связать каждый сценарий с выигрышем для обоих игроков, чтобы отразить относительный рейтинг с точки зрения окончательного результата.

Например, сценарий 2 - наихудший сценарий для Защитника и лучший для Спамера, поскольку его атаки на непереобученный классификатор приведут к большому количеству неправильно классифицированных спам-писем .

Определение модели

Ситуацию можно смоделировать как игру Штакельберга, то есть последовательную игру, в которой есть лидер (здесь спамер) и последователь ( Защитник D).

Игры Штакельберга обычно используются для моделирования стратегических взаимодействий между рациональными агентами на рынках, на которых существует иерархическая конкуренция.

В этом контексте каждый игрок реагирует на ход другого, выбирая действие из набора возможных действий U и V для S и D соответственно. Эти множества считаются ограниченными и выпуклыми.

Каждый результат связан с функцией выплаты Js, и Jd. Функции выплаты Ji представляют собой дважды дифференцируемое отображение Ji (U, V) → R, где R - реакция.

Следовательно, можно ожидать, что реакция Ri игрока i максимизирует его выигрыш, т.е.

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

Это означает, что первое действие спамеров - решение следующей задачи оптимизации:

И поэтому Защитник подберет оптимальное решение:

Это решение (u, v) является равновесием Штакельберга.

Обратите внимание, что оно отличается от равновесия по Нэшу, где два игрока действуют одновременно, а решение одновременного уравнения равно (0,0) , т.е. никакой реакции со стороны обоих игроков.

Спецификация модели

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

Для упрощения сначала рассмотрим только один атрибут. Затем его можно легко обобщить на несколько атрибутов, предполагая, что они условно независимы с учетом их метки класса.

Во-первых, каково влияние действий игроков?

Определим следующие распределения:

• P (μ ’, σ): распространение спама.
• Q (μ, σ): распространение электронных писем без спама

с μ ’‹ μ, поскольку электронных писем, не являющихся спамом, больше, чем спама

Противник атакует, перемещая μ ’ в μ’ + u (то есть в сторону μ). Защитник реагирует перемещением границы с 1/2 (μ ’+ μ’) в (также в сторону μ)

Во-вторых, каковы выплаты игроков?

Чтобы оценить важность преобразования u для данных, можно использовать KLD расхождение Кульбака – Лейблера (также называемое относительной энтропией). Он измеряет, чем распределение вероятностей отличается от другого эталонного распределения вероятностей.

Выплата спамера. Поскольку его цель - увеличить количество ошибочно классифицированных спам-писем, его выгода может быть выражена следующим образом:

где FNR - увеличение ложноотрицательной ставки. Таким образом, α представляет собой силу штрафа.

Выплата защитнику: поскольку его цель - повысить точность классификации, его выигрыш можно выразить следующим образом:

Где TPR и TNR представляют собой увеличение истинно положительных и истинно отрицательных ставок. Таким образом, β контролирует силу стоимости переобучения классификатора.

В этом контексте приведенное ниже уравнение можно решить с помощью генетического алгоритма:

Авторы статьи применили эту методологию для поиска равновесия между синтетическими и реальными данными. В зависимости от важности затрат, понесенных для создания атаки и переобучения классификатора (смоделированного с помощью α и β), они находят различные равновесия.

Другие варианты подходов, основанных на теории игр

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

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

Игра с нулевой суммой и ненулевой суммой

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

Одновременная игра против последовательной игры

В играх с одновременным ходом игроки выбирают одновременно свою стратегию, не наблюдая за стратегиями друг друга. В последовательных играх они выбирают ход один за другим.

Состязательное обучение в основном моделировалось как последовательная игра, в которой защитник является лидером. Фактически, часто предполагается, что как только защитник выбирает классификатор, атакующий может наблюдать за ним и выбирать свою собственную стратегию.

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

Байесовская игра

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

Джон К. Харсани, известный экономист, внесший большой вклад в теорию игр, особенно в контексте неполной информации, описывает байесовскую игру следующим образом:

Каждый игрок в игре связан с набором типов, причем каждый тип в наборе соответствует возможной функции выплаты для этого игрока. Помимо самих игроков в игре есть специальный игрок под названием Природа. Природа случайным образом выбирает тип для каждого игрока в соответствии с распределением вероятностей по типам игроков. Это распределение вероятностей известно всем игрокам («общее предварительное предположение»). Такой подход к моделированию превращает игры с неполной информацией в игры с неполной информацией.

Источник: Википедия

Как сделать состязательное обучение устойчивым?

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

Но что, если исходная модель уже была устойчивой к атакам противника?

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

В этом разделе мы рассмотрим 3 основных метода, используемых для генерации состязательных данных: методы возмущения, передача состязательных примеров, генеративные состязательные сети (GAN).

Методы возмущений

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

Большинство этих методов основано на добавлении небольшого количества шума или возмущения к действительному примеру. Давайте посмотрим на несколько хорошо известных примеров:

L-BFGS

Отметим:

• f: отображение классификатора, которое принимает для данного наблюдения x, состоящее из m функций, и возвращает метку класса.
• потеря: связанная функция непрерывных потерь.
• r: возмущение

Если целью злоумышленника является создание примера, который неправильно классифицируется как l, он должен решить следующую задачу оптимизации:

Это можно сделать, выполнив поиск в строке, чтобы найти минимальное c ›0, для которого минимизатор r следующей задачи удовлетворяет условию f (x + r) = l:

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

Метод быстрого градиентного знака (FGSM)

Отметим:

• X: чистое наблюдение
• ∇J (X, y): градиент функции потерь модели относительно X.
• ϵ: параметр , контролирующий важность враждебного возмущения.

Метод генерирует состязательные возмущения за счет увеличения значения функции потерь следующим образом:

Обратите внимание, что добавление возмущения в направлении градиента позволяет намеренно изменить наблюдение, так что модель его неправильно классифицирует.

Этот метод быстр и более осуществим с вычислительной точки зрения, чем предыдущий. Однако его вероятность успеха ниже.

Goodfellow et al. статья, описывающая этот метод, также привела к интересным наблюдениям, таким как:

• Использование направления возмущения, а не количества возмущения, более эффективно при создании противостоящих примеров.
• Обучение классификатора на примерах противоборства аналогично регуляризации классификатора.

Итеративный знак быстрого градиента

Также можно применить FGSM несколько раз с небольшим размером шага и обрезать итоговую сумму, при этом искажение между чистым и состязательным примером будет меньше.

Пример передачи состязательной стороны

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

Итак, к каким методам обычно прибегает злоумышленник?

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

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

Обратите внимание, что использование состязательных примеров, созданных с помощью модели, для обмана модели черного ящика возможно и зависит от передачи свойства.

Генеративные состязательные сети (GAN)

Генеративные состязательные сети (GAN) полностью полагаются на подход теории игр. В этих моделях возмущенные примеры генерируются злоумышленником и одновременно используются для обучения модели учащегося, как показано на графике ниже.

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

Дискриминатор и генератор взаимодействуют посредством игры с нулевой суммой, поскольку оба стремятся оптимизировать другую и противоположную целевую функцию или функцию потерь.

В этом контексте дискриминатор и генератор постоянно адаптируют свои механизмы прогнозирования и искажения данных соответственно.

Заключение

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

Поэтому важно не недооценивать их слабые стороны, когда они могут столкнуться с враждебными атаками во враждебной среде.

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

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

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

использованная литература

[1] В. Лю и С. Чавла, Теоретическая модель игры для состязательного обучения, 2009 г. Международная конференция IEEE по семинарам по интеллектуальному анализу данных, Майами, Флорида, 2009 г., стр. 25–30.

[2] П. Дасгупта, Дж. Б. Коллинз, Обзор теоретико-игровых подходов к состязательному машинному обучению в задачах кибербезопасности, Отделение архитектур управления информацией и принятия решений (IMDA), Отдел информационных технологий, Военно-морские исследования США. Лаборатория, Вашингтон, округ Колумбия, США, декабрь 2019 г.

[3] Н. Далви и др., Adversarial Classification, Департамент компьютерных наук и инженерии, Вашингтонский университет, Сиэтл, август 2004 г.

[4] П. Л. Баджо, Состязательное машинное обучение: как атаковать и защищать модели машинного обучения

[5] К. Молнар, Интерпретируемое машинное обучение, Руководство по созданию объяснимых моделей черного ящика, апрель 2020 г.

[6] С. Саксена, Игра (теория) для ИИ? Иллюстрированное руководство для всех , ноябрь 2019 г.