Intelligence artificielle

Théorie des jeux en intelligence artificielle

Théorie des jeux en intelligence artificielle


Une introduction à la théorie des jeux et à son application aux différents domaines de l'intelligence artificielle.

(Source: https://www.thegreatcourses.com/media/catalog/product/cache/1/plus_image/800x451/0f396e8a55728e79b48334e699243c07/1/4/1426.1549051731.jpg)

La théorie des jeux est une branche des mathématiques utilisée pour modéliser les interactions stratégiques entre différents acteurs dans un contexte avec des règles et des résultats prédéfinis.

La théorie des jeux peut être appliquée à différents domaines de l'intelligence artificielle:

  • Systèmes IA multi-agents.
  • Apprentissage par imitation et renforcement.
  • Formation d'adversaire dans les réseaux génératifs d'adversaire (GAN).

La théorie des jeux peut également être utilisée pour décrire de nombreuses situations de notre vie quotidienne et des modèles d’apprentissage automatique (Figure 1).

Par exemple, un algorithme de classification tel que SVM (Support Vector Machines) peut être expliqué en termes de jeu à deux joueurs dans lequel un joueur met au défi l'autre de trouver le meilleur hyper-plan en lui donnant les points les plus difficiles à classer. Le jeu convergera ensuite vers une solution qui constituera un compromis entre les capacités stratégiques des deux joueurs (par exemple, comment le premier joueur défie-t-il le second pour classer les points de données difficiles et quelle est la qualité pour le second la meilleure limite de décision).

La théorie des jeux peut être divisée en 5 types principaux de jeux:

  • Jeux coopératifs et non coopératifs: Dans les jeux coopératifs, les participants peuvent établir des alliances afin de maximiser leurs chances de gagner le jeu (par exemple, des négociations). Dans les jeux non coopératifs, les participants ne peuvent pas former des alliances (par exemple, des guerres).
  • Jeux symétriques vs asymétriques: Dans un jeu symétrique, tous les participants ont les mêmes objectifs et seules les stratégies mises en œuvre pour les atteindre détermineront le vainqueur du jeu (par exemple, les échecs). Dans les jeux asymétriques, les participants ont des objectifs différents ou contradictoires.
  • Perfect vs Imperfect Jeux d'information: Dans les jeux Perfect Information, tous les joueurs peuvent voir les mouvements des autres joueurs (par exemple, les échecs). Au lieu de cela, dans les jeux à information imparfaite, les mouvements des autres joueurs sont cachés (par exemple, les jeux de cartes).
  • Jeux simultanés ou séquentiels: Dans les jeux simultanés, les différents joueurs peuvent effectuer des actions simultanément. Dans les jeux séquentiels, chaque joueur est informé des actions précédentes des autres joueurs (par exemple, les jeux de société).
  • Jeux à somme nulle et non à somme nulle: Dans les jeux à somme nulle, si un joueur gagne quelque chose qui cause une perte aux autres joueurs. Dans les jeux à somme non nulle, plusieurs joueurs peuvent profiter des gains d'un autre joueur.

Différents aspects de la théorie des jeux sont couramment utilisés dans l’intelligence artificielle. Je vais maintenant vous présenter l’équilibre de Nash, la théorie des jeux inverses, et vous donner quelques exemples pratiques.

Si vous souhaitez implémenter des algorithmes de théorie des jeux en Python, la bibliothèque Nashpy est un bon point de départ.

Équilibre de Nash

L'équilibre de Nash est une condition dans laquelle tous les joueurs impliqués dans le jeu s'accordent à dire qu'il n'y a pas de meilleure solution au jeu que la situation actuelle dans laquelle ils se trouvent. Aucun des joueurs n’aurait l’avantage de changer de stratégie (sur la base des décisions prises par les autres joueurs).

Suivant notre exemple d'avant, un exemple d'équilibre de Nash peut être lorsque le classifieur SVM convient de l'hyper-plan à utiliser pour classer nos données.

L’un des exemples les plus couramment utilisés pour expliquer l’équilibre de Nash est le dilemme du prisonnier. Imaginons que deux criminels soient arrêtés et qu’ils soient détenus sans pouvoir communiquer entre eux (Figure 2).

  • Si l'un des deux prisonniers avoue que l'autre a commis un crime, le premier sera libéré, tandis que l'autre passera 10 ans en prison.
  • Si aucun d’eux n’avoue qu’ils ne passent chacun qu’un an de prison.
  • S'ils avouent tous les deux, ils passent tous deux cinq ans en prison.
Figure 2: Matrice des gains [2]

Dans ce cas, l'équilibre de Nash est atteint lorsque les deux criminels se trahissent.

Un moyen simple de savoir si un jeu a atteint l'équilibre de Nash peut être de révéler votre stratégie à vos adversaires. Si, après votre révélation, aucun d’entre eux ne change de stratégie, l’équilibre de Nash est démontré.

Malheureusement, un équilibre de Nash est plus facile à atteindre dans Symmetric que dans les jeux asymétriques. Les jeux asymétriques sont en fait les plus courants dans les applications du monde réel et dans l'intelligence artificielle.

Théorie des jeux inverse

La théorie des jeux vise à comprendre la dynamique d'un jeu afin d'optimiser les résultats possibles de ses joueurs. Inverse Game Theory vise plutôt à concevoir un jeu basé sur les stratégies et les objectifs des joueurs. La théorie des jeux inverse joue un rôle important dans la conception des environnements des agents IA.

Formation d'adversaire aux réseaux génératifs d'adversaire (GAN)

Le GAN consiste en deux modèles différents: un modèle génératif et un discriminant modèle (figure 3).

Figure 3: Architecture du GAN [3]

Les modèles génératifs prennent en entrée certaines fonctionnalités, examinent leurs distributions et tentent de comprendre comment elles ont été produites. Quelques exemples de modèles génératifs sont les modèles de Markov cachés (HMM) et les machines de Boltzmann restreintes (RBM).

Les modèles discriminants utilisent plutôt les entités en entrée pour prédire à quelle classe notre échantillon pourrait appartenir. Les machines à vecteurs de support (SVM) sont un exemple de modèle discriminatif.

Dans les GAN, le modèle génératif utilise les entités en entrée pour créer de nouveaux échantillons qui visent à ressembler assez étroitement aux caractéristiques principales des échantillons d'origine. Les échantillons nouvellement générés sont ensuite transférés avec les originaux au modèle discriminant, qui doit reconnaître quels échantillons sont authentiques et lesquels sont des faux. [4].

Un exemple d’application de GAN peut consister à générer des images, puis à faire la distinction entre les vraies et les fausses (Figure 4).

Figure 4: Images générées par NVIDIA GAN! [5]

Ce processus ressemble assez étroitement à la dynamique d'un jeu. Dans ce jeu, nos joueurs (les deux modèles) se défient. Le premier crée de faux échantillons pour confondre l’autre, tandis que le second essaie de mieux en mieux pour identifier les bons échantillons.

Ce jeu est ensuite répété de manière itérative et, à chaque itération, les paramètres d’apprentissage sont mis à jour afin de réduire la perte globale.

Ce processus se poursuivra jusqu'à ce que l'équilibre de Nash soit atteint (les deux modèles deviennent compétents dans l'exécution de leurs tâches et ne sont plus en mesure de s'améliorer).

Apprentissage par renforcement multi-agents (MARL)

L’apprentissage par renforcement (RL) vise à faire apprendre à un agent (notre «modèle») par l’interaction avec un environnement (qu’il soit virtuel ou réel).

RL a d'abord été développé pour adhérer aux processus de décision de Markov. Dans ce cadre, un agent est placé dans un environnement stochastique stationnaire et essaie d'apprendre une politique par le biais d'un mécanisme de récompense / punition. Dans ce scénario, il est prouvé que l'agent convergera vers une politique satisfaisante.

Toutefois, si plusieurs agents sont placés dans le même environnement, cette condition n'est plus vraie. En fait, avant que l'apprentissage de l'agent dépende uniquement de l'interaction entre l'agent et l'environnement, il dépend désormais également de l'interaction entre les agents (Figure 5).

Imaginons que nous essayons d’améliorer la circulation dans une ville en utilisant un groupe de voitures autonomes alimentées par l’IA. Chacune des voitures peut à elle seule parfaitement interagir avec l'environnement extérieur, mais les choses peuvent devenir plus compliquées si nous voulons que les voitures pensent en groupe. Par exemple, une voiture peut entrer en conflit avec une autre car il est plus pratique pour les deux de suivre un certain itinéraire.

Cette situation peut être facilement modélisée en utilisant la théorie des jeux. Dans ce cas, nos voitures représenteraient les différents acteurs et l’équilibre de Nash le point d’équilibre entre la collaboration entre les différentes voitures.

Figure 5: Tennis d'apprentissage du renforcement multi-agents [6]

La modélisation de systèmes avec un grand nombre d'agents peut devenir une tâche très difficile. C’est parce qu’augmenter le nombre d’agents augmente de façon exponentielle le nombre de façons possibles pour les différents agents d’interagir.

Dans ces cas, la modélisation des modèles d'apprentissage par renforcement multi-agents avec scénarios de champ moyen (MFS) pourrait être la meilleure solution. En fait, les scénarios de champ moyen peuvent réduire la complexité des modèles MARL en supposant a priori que tous les agents ont des fonctions de récompense similaires.

Si vous voulez rester au courant de mes derniers articles et projets, suivez-moi sur Support et inscrivez-vous à ma liste de diffusion. Voici quelques-unes de mes coordonnées:

[1] Théorie des jeux et décisions optimales. Consulté à: http://euler.fd.cvut.cz/predmety/game_theory/

[2] Modèles probabilistes quantiques revisités: le cas des effets de disjonction dans la cognition. Catarina Moreira et al. Researchgate. Consulté à: https://www.researchgate.net/publication/304577699_Quantum_Probabilistic_Models_Revisited_The_Case_of_Disjunction_Effects_in_Cognition/figures?lo=1

[3] GAN Deep Learning Architectures - revue, Sigmoidal. Consulté à: https://sigmoidal.io/beginners-review-of-gan-architectures/

[4] Vue d'ensemble: Réseaux d'adversaires génératifs - Quand l'apprentissage en profondeur rencontre la théorie des jeux. AHMED HANI IBRAHIM. Consulté à: https://ahmedhanibrahim.wordpress.com/2017/01/17/generative-adversarial-networks-when-deep-learning-meets-game-theory/comment-page-1/

[5] Nvidia AI génère de faux visages basés sur de vraies stars - Geek.com. Consulté à: https://www.geek.com/tech/nvidia-ai-generates-fake-faces-based-on-real-celebs-1721216/

[6] David Brown, Tennis Environment - Apprentissage par renforcement multi-agents. Consulté à: https://github.com/david-wb/marl

Afficher plus

SupportIvy

SupportIvy.com : Un lieu pour partager le savoir et mieux comprendre le monde. Meilleure plate-forme de support gratuit pour vous, Documentation &Tutoriels par les experts.

Articles similaires

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Bouton retour en haut de la page
Fermer