La théorie des jeux comme moteur de l'analyse de données à grande échelle

EigenGame décrit une nouvelle approche pour résoudre les problèmes fondamentaux de ML

Les systèmes d’IA modernes gèrent des tâches telles que la reconnaissance d’objets dans des images et la prédiction de la structure 3D des protéines pendant que l’étudiant assidu se prépare à un examen. En s’entraînant avec de nombreux exemples de problèmes, ils réduisent leurs erreurs au fil du temps jusqu’à ce qu’ils réussissent. Mais c’est une entreprise individuelle et ce n’est qu’une des formes connues d’apprentissage. L’apprentissage passe également par l’interaction et le jeu avec les autres. Il est rare qu’un seul individu soit capable de résoudre seul des problèmes très complexes. En permettant à la résolution de problèmes d’avoir ces qualités de jeu, les efforts précédents de DeepMind ont formé des agents d’IA pour jouer à Capture the Flag et atteindre le niveau Grandmaster dans Starcraft. Cela nous a amenés à nous demander si une telle perspective de type théorie des jeux pouvait aider à résoudre d’autres problèmes fondamentaux d’apprentissage automatique.

Aujourd’hui à l’ICLR 2021 (International Conference on Learning Representations), nous avons présenté “Eigen’s Game: PCA as a Nash Equilibrium”, qui a reçu un Outstanding Paper Award. Notre recherche a exploré une nouvelle approche d’un vieux problème : nous avons recadré l’analyse en composantes principales (ACP), un type de problème aux valeurs propres, comme un jeu multifactoriel compétitif que nous appelons EigenGame. L’ACP est généralement formulée comme un problème d’optimisation (ou un problème à facteur unique); Cependant, nous avons constaté que la perspective multi-agents nous permettait de développer de nouvelles idées et algorithmes qui tirent parti des dernières ressources de calcul. Cela nous a permis de développer d’énormes ensembles de données qui étaient auparavant exigeants en termes de calcul et fournit une approche alternative pour l’exploration future.

PCA comme équilibre de Nash

Décrite pour la première fois au début du XXe siècle, l’ACP est une méthode de longue date pour comprendre la structure des données de grande dimension. Cette approche est désormais omniprésente en tant que première étape du pipeline de traitement des données et facilite l’agrégation et la visualisation des données. Il peut également être un outil utile pour apprendre des représentations à faible dimension de la régression et de la classification. Plus d’un siècle plus tard, il existe encore des raisons impérieuses d’étudier l’APC.

Premièrement, les données étaient à l’origine enregistrées manuellement dans des cahiers papier, et maintenant elles sont stockées dans des centres de données de la taille d’entrepôts. En conséquence, cette analyse familière est devenue un goulot d’étranglement informatique. Les chercheurs ont exploré des algorithmes stochastiques et d’autres directions pour améliorer les mesures de l’ACP, mais nous avons constaté que ces approches ont du mal à s’adapter à d’énormes ensembles de données car elles ne peuvent pas tirer pleinement parti des récentes avancées en matière d’apprentissage en profondeur, c’est-à-dire accès à de nombreux GPU parallèles ou TPU. .

Deuxièmement, l’ACP partage une solution commune avec de nombreux problèmes importants de ML et de géométrie, qui est la décomposition en valeurs singulières (SVD). En abordant le problème PCA de la bonne manière, nos idées et nos algorithmes s’appliquent plus largement à toutes les branches de l’arbre ML.

Figure 1. Avec ses racines dans SVD, l’arbre de connaissances comprend de nombreuses idées de base dans l’apprentissage automatique, notamment l’ACP, les moindres carrés, le regroupement spectral, les fonctions de valeur brute, l’indexation sémantique latente et le tri.

Comme pour tout jeu de société, afin de réinventer PCA en tant que jeu, nous avons besoin d’un ensemble de règles et d’objectifs à suivre par les joueurs. Il existe de nombreuses manières possibles de concevoir un tel jeu ; Cependant, des informations importantes proviennent de l’ACP elle-même : la solution optimale consiste en des vecteurs propres qui capturent la variance importante dans les données et sont perpendiculaires les uns aux autres.

Figure 2. Chaque joueur veut s’aligner sur la direction de la variance maximale (plus grande dispersion des données) mais aussi rester perpendiculaire aux joueurs en haut de la hiérarchie (tous les joueurs avec le numéro le plus bas).

Dans EigenGame, chaque joueur contrôle un vecteur propre. Les joueurs augmentent leur score en expliquant la variance dans les données mais sont pénalisés s’ils se rapprochent trop des autres joueurs. Nous créons également une hiérarchie : le joueur 1 ne se soucie que de maximiser la variance, tandis que les deux autres joueurs doivent également se soucier de minimiser leur alignement avec les joueurs au-dessus d’eux dans la hiérarchie. Cette combinaison de récompenses et de punitions détermine le bénéfice de chaque joueur.

Figure 3. Résumant les avantages de chaque joueur ci-dessus.

Avec la conception appropriée souris Et alignement conditions, nous pouvons montrer ce qui suit :

• Si tous les joueurs jouent de manière optimale, alors ensemble, ils atteignent l’équilibre de Nash du jeu, qui est la solution au PCA.
• Ceci peut être réalisé si chaque joueur augmente son utilité indépendamment et en même temps en utilisant des ascensions en gradient.

Figure 4. EigenGame guide chaque joueur le long d’un champ unitaire des cercles vides aux flèches en parallèle. Bleu est le joueur 1. Rouge est le joueur 2. Vert est le joueur 3.

Cette propriété d’indépendance de l’ascension simultanée est particulièrement importante car elle permet de répartir les calculs sur des dizaines de Google Cloud TPU, ce qui permet à la fois le parallélisme des données et des modèles. Cela permet à notre algorithme de s’adapter à des données à très grande échelle. EigenGame trouve des composants clés en quelques heures dans des ensembles de données de cent téraoctets de millions de fonctionnalités ou de milliards de lignes.

Figure 5. Chaque carré de couleur est un appareil distinct. (L) Chaque joueur vit et calcule les mises à jour sur un seul appareil. (r) chaque joueur est mis en miroir sur plusieurs machines et calcule les mises à jour à l’aide d’ensembles de données indépendants ; Ensuite, les différentes mises à jour sont moyennées pour former une tendance de mise à jour plus robuste.

Utilitaires, mises à jour et tout le reste

En considérant l’ACP dans une perspective multi-agents, nous avons pu proposer des algorithmes évolutifs et de nouvelles analyses. Nous avons également découvert une corrélation surprenante avec l’apprentissage hebbien – ou comment les neurones s’adaptent lors de l’apprentissage. Dans EigenGame, chaque joueur maximisant ses installations l’amène à mettre à jour des équations qui ressemblent aux règles de mise à jour dérivées des modèles hebbiens de plasticité synaptique dans le cerveau. Les mises à jour Hebbian sont connues pour converger vers une solution PCA mais ne sont pas dérivées en tant que gradient d’une fonction d’assistance. La théorie des jeux nous donne une nouvelle perspective pour voir l’apprentissage hebbien et propose également un continuum d’approches aux problèmes d’apprentissage automatique.

À une extrémité du continuum ML se trouve une voie évolutive pour proposer une fonction objective qui peut être optimisée : en utilisant la théorie de l’optimisation convexe et non convexe, les chercheurs peuvent considérer les propriétés globales d’une solution. D’autre part, les méthodes de communication pures et les règles de mise à jour inspirées des neurosciences sont directement définies, mais l’analyse du système entier peut être plus difficile, nécessitant souvent l’étude de systèmes dynamiques complexes.

Les approches théoriques des jeux comme le jeu d’Eigen se situent quelque part entre les deux. Les mises à jour des joueurs ne sont pas seulement une gradation d’un travail, elles sont simplement la meilleure réponse aux stratégies actuelles des autres joueurs. Nous sommes libres de concevoir des utilitaires et des mises à jour avec des caractéristiques souhaitables – par exemple, spécifier des mises à jour impartiales ou accélérées – tout en veillant à ce que la propriété Nash nous permette toujours d’analyser le système dans son ensemble.

Figure 6 : De nombreux utilitaires permettent de combler le fossé entre les méthodes d’optimisation et les systèmes dynamiques.

EigenGame est un exemple concret de conception d’une solution de problème d’apprentissage automatique en tant que sortie d’un grand système multi-agents. En général, modéliser les problèmes d’apprentissage automatique en tant que jeux multi-agents est un défi Conception du mécanisme problème; Cependant, les chercheurs ont déjà utilisé la catégorie des jeux à deux joueurs à somme nulle pour résoudre des problèmes d’apprentissage automatique. En particulier, le succès des réseaux antagonistes génératifs (GAN) en tant qu’approche de la modélisation générative a conduit à un intérêt accru pour la relation entre la théorie des jeux et l’apprentissage automatique.

Eigen va bien au-delà de cela avec la configuration multijoueur et de pool générale la plus complexe. Cela permet un parallélisme plus apparent d’une plus grande échelle et d’une plus grande vitesse. Il fournit également une référence quantitative à la communauté pour tester de nouveaux algorithmes multi-agents ainsi que des domaines plus riches, tels que la diplomatie et le football.

Nous espérons que notre modèle de conception d’utilitaire et nos mises à jour encourageront d’autres personnes à explorer cette direction pour concevoir de nouveaux algorithmes, agents et systèmes. Nous sommes impatients de voir quels autres problèmes peuvent être modélisés comme des jeux et si les informations que nous recueillons amélioreront notre compréhension de la nature de l’intelligence multifactorielle.

‍

Pour plus de détails, consultez l’article EigenGame : PCA as a Nash Equilibrium et notre travail de suivi EigenGame Unloaded : When Playing Games is Better Than Optimizing.