Теория игр для машинного обучения: перспектива

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

Эта область получила прочную основу, когда знаменитый математик Джон Нэш, часто известный своим биографическим фильмом Игры разума, доказал идею о том, что равновесие Нэша существует для каждой конечной игры. Это утверждение можно упростить до , в каждой игре с конечным числом игроков и возможными ходами существует по крайней мере один набор стратегий, когда все игроки играют, что приводит к противостоянию, когда ни один игрок не может улучшить свою позицию самостоятельно. . Классические примеры теории игр включают Дилемму заключенного, где Нэш кажется таким противоречащим интуиции, потому что единственная стратегия, в которой доминирует Парето, — это равновесие Нэша. Это означает, что единственная стратегия, которая не позволяет получить выигрыш ни одному игроку, не причиняя вреда другим, — это единственный способ гарантировать, что оба игрока также сохранят свои текущие выигрыши. Следует отметить, что теорема говорит только о существовании, а не о каком-либо способе нахождения равновесия Нэша в игре. Это проблема, охватывающая весь класс сложности сама по себе (класс сложности PPAD).

Теория игр приобрела актуальность в машинном обучении, когда были введены такие методы, как Генеративно-состязательные сети (GAN), в которых несколько нейронных сетей оптимизируют свои собственные функции потерь, чтобы конкурировать или обманывать других. Эти модели чрезвычайно эффективны и открыли совершенно новые возможности для генеративного моделирования — области машинного обучения, связанной с созданием, а не с классификацией. Однако они также создали серьезные новые проблемы. Общеизвестно, что GAN сложно обучать, и они подвержены всевозможным эксцентричностям, таким как коллапс режима, когда генератор просто решает изучить один способ умело обмануть дискриминатор вместо всех типов данных, которые мы хотим, чтобы он узнал. Набор данных, состоящий из всех животных, может иметь генератор, производящий только кошек и только коричневых кошек, если вы попадаете в канаву режима коллапса.

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

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

Уравнение для обновления параметров может быть представлено в матричной форме, как показано ниже:

Где f и g — функции потерь дискриминатора и генератора соответственно.

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

Интересная последующая работа «Неявная конкурентная регуляризация в GAN» бросает вызов минимаксной интерпретации, которая была представлена ​​в исходной статье GAN. Согласно Гудфеллоу и др., дискриминатор учится, пытаясь свести к минимуму свои потери за счет правильной идентификации поддельных точек данных, в то время как генератор пытается максимизировать потери дискриминатора, генерируя выборки, которые действительно похожи на распределение, которое мы пытаемся изучить. Эта минимаксная оптимизация, по мнению авторов, является основой успеха GAN.

Шефер и др. отмечают, что это не может быть единственной причиной. Они указывают на следующие недостатки в этом рассуждении. Если GAN обучаются без регуляризации функции потерь, как в исходной статье, сеть дискриминатора всегда может перетренироваться на наборе данных, заставляя генератор также изучать очень мало конкретных примеров из набора данных, если они вообще могут генерировать что-либо. Это особенно плохо для генеративных моделей. Они должны иметь возможность создавать новые образцы из дистрибутива, который они пытаются изучить. Однако мы знаем, что такие GAN работают при создании обобщенных выборок данных. Хотя, с другой стороны, если применяются ограничения регуляризации, метод регуляризации является серьезной проблемой в объяснении того, как GAN работают так хорошо. Дискриминатор GAN переводит изображение из его пиксельной формы в оценку того, насколько оно реалистично. Принятие евклидовой нормы градиентов такой функции является мерой только того, насколько похожи пиксели на двух изображениях, а не того, насколько визуально похожи два изображения. То же самое можно сказать и о большинстве других используемых методов регуляризации. Однако этот метод работает на удивление хорошо, а также устраняет некоторые проблемы нестабильности, которые мешают GAN, не зависящим от метрики.

Это оставляет вопрос о том, как GAN могут создавать изображения такого замечательного качества. В статье авторы представляют понятие неявной конкурентной регуляризации (ICR), то есть регуляризации дискриминатора, возникающей из процедуры оптимизации обучения двух моделей вместе, а не из каких-либо добавленных членов регуляризации в функции потерь. Хорошо известно, что нейронные сети получают индуктивные смещения из-за своей структуры. Нейронные сети являются универсальными аппроксиматорами функций и теоретически могут изучать любую функцию между входами и выходами, но некоторые сети лучше работают с определенными типами данных, например, рекуррентные нейронные сети работают лучше, чем полностью связанные системы для моделей последовательностей (например, звуковых или волновых паттернов). потому что архитектура впитывает его с уклоном на изучение таких отношений из данных. Точно так же неявная регуляризация является предвзятостью, возникающей в результате процедуры оптимизации. Обучение одной и той же модели этим разным процедурам может привести к разным результатам. Некоторые могут предпочесть одни минимумы данных другим и, таким образом, получить более обобщаемые результаты. ICR играет эту роль в мультиагентной настройке. В документе утверждается, что ICR сводит сети к точкам на ландшафте, которые можно рассматривать как равновесия Нэша, и дает образцы отличного качества, а также показано, как конкурентный градиентный спуск может увеличить ICR и стабилизировать обучение GAN даже без явной регуляризации.

Еще одна интересная работа на стыке теории игр и глубокого обучения — Интерпретация и усиление отсева с точки зрения теории игр Чжана и др. Работа направлена ​​на объяснение и доказательство эффективности регуляризации отсева, широко используемого метода, позволяющего избежать переобучения в нейронных сетях, рассматривая процесс как игру. Бумага моделирует отсев с использованием значений Шепли — теоретико-игровой концепции, получившей Нобелевскую премию в 2012 году. Ценности Шепли — это справедливая мера распределения полезности игры. Он описывает распределение вознаграждения за игру между группой игроков в коалиции в соответствии с их вкладом в получение упомянутого вознаграждения для своей коалиции.

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

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

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

Eigengames: PCA as a Nash Equilibrium Гемпа и др. представляет собой еще одно увлекательное место работы. Как следует из названия статьи, они моделируют Основной Компонентный анализ как игру, в которую играют собственные векторы матрицы ковариации данных. Взаимодействия между различными возможными собственными векторами подавлены в формулировке, так что первый игрок пытается зафиксировать только максимальную дисперсию, в то время как каждый из последовательных собственных векторов также должен пытаться ортогонализовать свое выравнивание относительно своих предшественников. Эта переформулировка приводит к набору функций потерь, которые почти независимы, и каждая из них может быть вычислена параллельно с передачей некоторого сообщения между вычислительными узлами, что позволяет использовать масштабируемый подход для вычисления PCA на огромных наборах данных. Также доказано, что равновесие Нэша этой конкретной установки является главным компонентом данных.

Авторы продолжают доказывать это, пытаясь найти 32 основных вектора активаций ResNet-200 размером почти 200 ТБ, что почти невозможно для более ранних алгоритмов примерно за 9 часов с использованием проприетарного оборудования Google TPU. Кроме того, алгоритм также имел доказуемые гарантии результатов независимо от инициализации, что является фатальным недостатком некоторых из более ранних подходов.

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

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