EigenGame предлагает новый подход к решению фундаментальных проблем машинного обучения

Современные системы ИИ подходят к таким задачам, как распознавание объектов на изображениях и предсказание трехмерной структуры белков как прилежный студент готовился бы к экзамену. Тренируясь на многих примерах задач, они со временем минимизируют свои ошибки, пока не добьются успеха. Но это одиночное усилие и только одна из известных форм обучения. Обучение также происходит путем взаимодействия и игры с другими людьми. Редко когда один человек может решить чрезвычайно сложные проблемы в одиночку. Предыдущие усилия DeepMind позволяли решать проблемы приобретать эти игровые качества, обучая агентов ИИ играть Захват флага и достичь Уровень гроссмейстера в Starcraft. Это заставило нас задуматься, может ли такая перспектива, основанная на теории игр, помочь решить другие фундаментальные проблемы машинного обучения.

Сегодня в ICLR 2021 (Международная конференция по обучающим представлениям), мы представили «EigenGame: PCA как равновесие Нэша», который получил награду за выдающуюся работу. Наше исследование исследовало новый подход к старой проблеме: мы переформулировали анализ главных компонентов (PCA), тип проблема собственных значений, как конкурентную игру с несколькими агентами, которую мы называем EigenGame. PCA обычно формулируется как задача оптимизации (или задача с одним агентом); однако мы обнаружили, что многоагентная перспектива позволила нам разработать новые идеи и алгоритмы, которые используют новейшие вычислительные ресурсы. Это позволило нам масштабироваться до массивных наборов данных, которые ранее требовали слишком больших вычислительных ресурсов, и предлагает альтернативный подход для будущих исследований.

PCA как равновесие Нэша

Впервые описан в начале 1900-х гг. СПС — это давний метод для понимания структуры многомерных данных. Этот подход теперь повсеместно используется в качестве первого шага в конвейере обработки данных и упрощает кластеризацию и визуализацию данных. Это также может быть полезным инструментом для изучения низкоразмерных представлений для регрессии и классификации. Спустя более века все еще есть веские причины для изучения АКП.

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

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

Как и в случае с любой настольной игрой, чтобы заново изобрести PCA как игру, нам нужен набор правил и целей, которым должны следовать игроки. Есть много возможных способов разработать такую ​​игру; однако важные идеи исходят из самого PCA: оптимальное решение состоит из собственных векторов, которые отражают важную дисперсию данных и ортогональны друг другу.

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

С правильно оформленным Вар и Выровнять условия, мы можем показать, что:

• Если все игроки играют оптимально, вместе они достигают равновесие по Нэшу игры, которая является решением PCA.
• Этого можно достичь, если каждый игрок максимизирует свою полезность независимо и одновременно, используя градиентное восхождение.

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

Утилиты, обновления и все, что между ними

Думая о PCA с точки зрения нескольких агентов, мы смогли предложить масштабируемые алгоритмы и новые методы анализа. Мы также обнаружили удивительную связь с Хеббианское обучение — или как нейроны адаптируются при обучении. В EigenGame каждый игрок, максимизирующий свои полезности, приводит к уравнениям обновления, подобным обновить правила получена из хеббовских моделей синаптической пластичности мозга. Известно, что обновления Хебба сходятся к решению PCA, но не получаются как градиент какой-либо функции полезности. Теория игр дает нам новый взгляд на хеббовское обучение, а также предлагает целый ряд подходов к проблемам машинного обучения.

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

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

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

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

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

‍

Подробнее см. в нашей статье EigenGame: PCA как равновесие Нэша и наша дальнейшая работа EigenGame Unloaded: когда лучше играть в игры, чем оптимизировать.