EigenGame предлагает новый подход к решению фундаментальных проблем машинного обучения
Современные системы искусственного интеллекта подходят к таким задачам, как распознавание объектов на изображениях и предсказание трехмерной структуры белков, как прилежный студент готовится к экзамену. Тренируясь на многих примерах задач, они со временем минимизируют свои ошибки, пока не добьются успеха. Но это одиночное усилие и только одна из известных форм обучения. Обучение также происходит путем взаимодействия и игры с другими людьми. Редко когда один человек может решить чрезвычайно сложные проблемы в одиночку. Предыдущие усилия DeepMind позволили решению проблем приобрести эти игровые качества и научили агентов ИИ играть в «Захват флага» и достигать уровня гроссмейстера в Starcraft. Это заставило нас задуматься, может ли такая перспектива, основанная на теории игр, помочь решить другие фундаментальные проблемы машинного обучения.
Сегодня на ICLR 2021 (Международная конференция по представлениям обучения) мы представили «EigenGame: PCA как равновесие Нэша», получившую награду за выдающуюся работу. Наше исследование исследовало новый подход к старой проблеме: мы переформулировали анализ основных компонентов (PCA), тип проблемы собственных значений, в виде конкурентной игры с несколькими агентами, которую мы назвали EigenGame. PCA обычно формулируется как задача оптимизации (или задача с одним агентом); однако мы обнаружили, что многоагентная перспектива позволила нам разработать новые идеи и алгоритмы, которые используют новейшие вычислительные ресурсы. Это позволило нам масштабироваться до массивных наборов данных, которые ранее требовали слишком больших вычислительных ресурсов, и предлагает альтернативный подход для будущих исследований.
PCA как равновесие Нэша
Впервые описанный в начале 1900-х годов, PCA — это давний метод для понимания структуры многомерных данных. Этот подход теперь повсеместно используется в качестве первого шага в конвейере обработки данных и упрощает кластеризацию и визуализацию данных. Это также может быть полезным инструментом для изучения низкоразмерных представлений для регрессии и классификации. Спустя более века все еще есть веские причины для изучения АКП.
Во-первых, данные изначально записывались вручную в бумажные блокноты, а теперь они хранятся в дата-центрах размером со склады. В результате этот знакомый анализ стал вычислительным узким местом. Исследователи изучили рандомизированные алгоритмы и другие направления для улучшения масштабирования PCA, но мы обнаружили, что эти подходы трудно масштабировать до массивных наборов данных, потому что они не могут в полной мере использовать последние достижения в области вычислений, ориентированные на глубокое обучение, а именно доступ ко многим параллельным графическим процессорам или ТПУ.
Во-вторых, PCA имеет общее решение со многими важными задачами машинного обучения и инженерии, а именно разложение по сингулярным числам (SVD). При правильном подходе к проблеме PCA наши идеи и алгоритмы более широко применяются во всех ветвях дерева машинного обучения.
Как и в случае с любой настольной игрой, чтобы заново изобрести PCA как игру, нам нужен набор правил и целей, которым должны следовать игроки. Есть много возможных способов разработать такую игру; однако важные идеи исходят из самого PCA: оптимальное решение состоит из собственных векторов, которые отражают важную дисперсию данных и ортогональны друг другу.
В EigenGame каждый игрок управляет собственным вектором. Игроки увеличивают свой счет, объясняя различия в данных, но наказываются, если они слишком тесно связаны с другими игроками. Мы также устанавливаем иерархию: Игрок 1 заботится только о максимизации дисперсии, в то время как другие игроки также должны беспокоиться о том, чтобы свести к минимуму их соответствие с игроками, находящимися выше их в иерархии. Эта комбинация наград и штрафов определяет полезность каждого игрока.
С правильно оформленным Вар и Выровнять условия, мы можем показать, что:
- Если все игроки играют оптимально, вместе они достигают равновесия Нэша в игре, которое является решением PCA.
- Этого можно достичь, если каждый игрок максимизирует свою полезность независимо и одновременно, используя градиентное восхождение.
Это свойство независимости одновременного восхождения особенно важно, поскольку оно позволяет распределять вычисления между десятками TPU Google Cloud, обеспечивая параллелизм данных и моделей. Это позволяет нашему алгоритму адаптироваться к действительно крупномасштабным данным. EigenGame за считанные часы находит основные компоненты для наборов данных размером в сотни терабайт, содержащих миллионы признаков или миллиарды строк.
Утилиты, обновления и все, что между ними
Думая о PCA с точки зрения нескольких агентов, мы смогли предложить масштабируемые алгоритмы и новые методы анализа. Мы также обнаружили удивительную связь с Hebbian Learning — или с тем, как нейроны адаптируются при обучении. В EigenGame каждый игрок, максимизирующий свою полезность, приводит к уравнениям обновления, которые аналогичны правилам обновления, полученным из хеббовских моделей синаптической пластичности мозга. Известно, что обновления Хебба сходятся к решению PCA, но не получаются как градиент какой-либо функции полезности. Теория игр дает нам новый взгляд на хеббовское обучение, а также предлагает целый ряд подходов к проблемам машинного обучения.
На одном конце континуума машинного обучения находится хорошо проработанный путь предложения целевой функции, которую можно оптимизировать: используя теорию выпуклой и невыпуклой оптимизации, исследователи могут рассуждать о глобальных свойствах решения. С другой стороны, чисто коннекционистские методы и правила обновления, вдохновленные нейронаукой, указываются напрямую, но анализ всей системы может быть более сложным, часто требуя изучения сложных динамических систем.
Теоретико-игровые подходы, такие как EigenGame, находятся где-то посередине. Обновления игроков не ограничиваются градиентом функции, а только лучшим ответом на текущие стратегии других игроков. Мы можем разрабатывать утилиты и обновления с желаемыми свойствами — например, указывать обновления, которые являются беспристрастными или ускоренными, — при этом гарантируя, что свойство Нэша по-прежнему позволяет нам анализировать систему в целом.
EigenGame представляет собой конкретный пример разработки решения задачи машинного обучения на выходе большой многоагентной системы. В более общем плане разработка задач машинного обучения в виде игр с несколькими агентами является сложной задачей. конструкция механизма проблема; однако исследователи уже использовали класс игр с нулевой суммой для двух игроков для решения задач машинного обучения. В частности, успех генеративно-состязательных сетей (GAN) как подхода к генеративному моделированию вызвал интерес к взаимосвязи между теорией игр и машинным обучением.
EigenGame выходит за рамки этого и переходит к более сложной настройке с общей суммой для многих игроков. Это обеспечивает более очевидный параллелизм для большего масштаба и скорости. Он также представляет собой количественный ориентир для тестирования новых многоагентных алгоритмов сообщества наряду с более широкими областями, такими как дипломатия и футбол.
Мы надеемся, что наш план разработки утилит и обновлений побудит других исследовать это направление для разработки новых алгоритмов, агентов и систем. Мы с нетерпением ждем возможности увидеть, какие другие проблемы можно сформулировать в виде игр, и помогут ли полученные нами идеи еще больше улучшить наше понимание мультиагентной природы интеллекта.
Для получения более подробной информации см. нашу статью EigenGame: PCA as a Nash Equilibrium и нашу последующую работу EigenGame Unloaded: когда играть в игры лучше, чем оптимизировать.