[Перевод] Теория игр как механизм для анализа крупномасштабных данных31.05.2021 18:01

Современные системы искусственного интеллекта подходят к решению таких задач, как распознавание объектов на изображениях и прогнозирование трёхмерной структуры белков, как прилежный студент готовится к экзамену. Тренируясь на многих примерах решения аналогичных задач, они со временем сводят к минимуму собственные ошибки и в конце концов добиваются успеха. Но приведённый пример — лишь частный случай и лишь одна из известных форм обучения. К старту курса «Machine Learning и Deep Learning» делимся переводом статьи о том, как в DeepMind создали многоагентную систему при помощи нового подхода EigenGame, то есть компромисса между чистой оптимизацией и динамической системой.

Обучение также происходит при взаимодействии и играх с другими людьми. Перед человеком могут вставать чрезвычайно сложные проблемы, и решить их в одиночку ему вряд ли удастся. DeepMind попыталась решать проблемы с использованием определённых игровых приёмов, и у неё это прекрасно получилось — она обучила агентов ИИ играть в Capture the Flag, а один из её агентов даже набрал гроссмейстерскую норму в Starcraft [мы писали об этом вчера, в статье о том, как StarCraft II может помочь экологам]. Это заставило нас задуматься, сможет ли теория игр помочь в решении других фундаментальных проблем машинного обучения.

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

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

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

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

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

Рис. 1. Дерево знаний на базе SVD охватывает многие фундаментальные идеи машинного обучения, включая методы PCA, наименьших квадратов, спектральной кластеризации, функции условных значений, латентно-семантическое индексирование и сортировку

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

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

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

Рис. 3. Определение полезности каждого игрока выше в иерархии

С помощью надлежащим образом определённых Var и Align можно показать, что:

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

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

Рис. 4. EigenGame параллельно направляет каждого игрока вдоль единичной сферы от пустых окружностей к стрелкам. Синий — игрок 1. Красный — игрок 2. Зелёный — игрок 3

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

Рис. 5. Каждый цветной квадрат представляет собой отдельное устройство. (L) Каждый игрок живёт и вычисляет обновления на одном устройстве. ^® Каждый игрок копируется на несколько устройств и вычисляет обновления, используя независимые наборы данных; различные обновления затем усредняются, и определяется более надёжное направление обновления

Полезность, обновления и всё, что с ними связано

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

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

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

Рис. 6. Возможность использования нескольких функций полезности устраняет разрыв между оптимизационными подходами и динамическими системами

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

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

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

Более подробная информация приведена в нашей работе EigenGame: метод PCA как равновесие по Нэшу и последующей работе EigenGame Unloaded: когда играть лучше, чем оптимизировать. Данная запись в блоге основана на совместной работе с Туром Грейпелом, руководителем исследовательской группы в DeepMind и заведующим кафедрой машинного обучения в Университетском колледже Лондона.

Машинное обучение продолжает развиваться, приобретая гибкость, необходимую для решения проблем всё более широкого спектра, а значит её проблемы и решения будут актуальны ещё долгое время по меркам не только быстро изменяющихся информационных технологий, но и других областей знаний, где новые методы будут применяться. Если вам интересна сфера глубокого и машинного обучения, вы можете обратить внимание на курс «Machine Learning и Deep Learning» — широкое и глубокое введение в область искусственного интеллекта.

Узнайте, как прокачаться и в других специальностях или освоить их с нуля:

Другие профессии и курсы