S’amuser avec le Machine Learning ! Part2

Se servir du machine learning afin de créer un niveau dans Super Mario

Cet article ne nécessite pas de connaissances mathématiques & informatiques.( texte original :https://medium.com/@ageitgey/machine-learning-is-fun-part-2-a26a10b68df3 )

Préface

Ayant tout d’abord voulu écrire un article sur l’Intelligence Artificielle, je me suis rendu compte qu’il en existait déjà de très bons, mais malheureusement peu accessibles à ceux ne pratiquant pas l’anglais technique. De nombreuses lectures plus tard, j’ai finalement contacté Adam Geitgey afin de savoir si je pouvais officiellement traduire sa série de papiers. Après m’avoir envoyé une réponse positive et validé mes retouches, voici ma seconde partie (d’autres suivront). Bonne lecture !

http://image.slidesharecdn.com/deepdiveinaimlventurelandscape-150831132221-lva1-app6891/95/deepdive-in-aiml-venture-landscape-by-ajit-nazre-rahul-garg-3-638.jpg?cb=1441027412

Dans la première partie, nous avions vu que le Machine Learning utilise des algorithmes génériques dans le but de transformer les données brute en un résultat concret sans avoir besoin d’écrire de code spécifique. (si vous n’avez pas encore entendu parler de la partie 1, lisez-la maintenant !).

Ici, nous allons disséquer un de ces algorithmes génériques en créant un niveau de jeu vidéo aussi complet que s’il l’avait été par un humain. Nous allons développer un réseau neuronal, en le nourrissant des niveaux de Super Mario déjà existant et en regardant ce qu’il en advient !

Un des niveaux qui sera généré par notre algorithme

Tout comme la partie 1, ce guide s’adresse à toutes les personnes intéressées par l’apprentissage automatique qui ne savent pas par où commencer. Cet article est accessible à tous — ce qui signifie qu’il y a beaucoup de généralisations et que beaucoup de détails passent à la trappe. Mais qui s’en soucie ? Si cela permet d’intéresser plus de monde au ML, alors la mission est accomplie.


Deviner avec plus de précision

Dans la partie 1, nous avons créé un algorithme simple qui estimait la valeur d’une maison basée sur certains de ses attributs. Par exemple des données telles que :

Nous en avions déduis cette fonction d’estimation basique :

def estimate_house_sales_price(num_of_bedrooms, sqft, neighborhood):
price = 0
# a little pinch of this
price += num_of_bedrooms * 0.123
# and a big pinch of that
price += sqft * 0.41
# maybe a handful of this
price += neighborhood * 0.57
return price

En d’autres termes, nous avons estimé la valeur de la maison en multipliant chacun de ses attributs par un poids. Ensuite, nous avons simplement additionné ces chiffres pour obtenir la valeur de la maison.

Au lieu d’utiliser du code, représentons la même fonction avec une image simple :

les flèches représentent les poids de notre fonction

Toutefois, cet algorithme ne fonctionne qu’avec des problèmes peu complexes, dans lesquels le résultat a une relation linéaire avec les paramètres d’entrée. Et si la vérité derrière les prix de l’immobilier n’était pas si simple? Par exemple, le voisinage attache peut-être beaucoup d’importance aux grandes et aux petites maisons, mais n’en a aucune pour les maisons de taille moyenne. Comment pourrions-nous détecter ce genre de détail dans notre modèle ?

Pour être plus précis, nous pourrions exécuter cet algorithme plusieurs fois avec différents poids, déterminant ainsi à chaque fois une estimation de prix différente.

Essayons de résoudre notre problème de quatre manières différentes

Nous avons maintenant quatre estimations de prix différentes. Combinons ces quatre estimations de prix en une estimation finale. Puis ré-exécutons les dans même algorithme (mais en utilisant un autre ensemble de poids) !

Notre nouvelle Super réponse combine les estimations de nos quatre tentatives précédentes afin de résoudre le problème. Grâce à cela, il peut modéliser plus de cas que nous pourrions en capturer avec un simple modèle.

Qu’est ce qu’un réseau neuronal ?

Combinons nos quatre tentatives en un grand diagramme:

Vous voici face à un réseau de neurones ! Chaque nœud sait comment intégrer un ensemble d’entrées, lui appliquer un poids puis calculer une valeur de sortie. En enchaînant plusieurs de ces nœuds, nous pouvons modéliser des fonctions plus complexes.

Je fais abstraction de beaucoup d’explications dans le but de rester bref (y compris la mise à l’échelle et la fonction d’activation), mais le plus important sont ces idées de base :

  • Nous avons créé une fonction d’estimation simple qui prend un ensemble d’entrées et les multiplie par des poids pour obtenir une sortie. Appelez cette fonction simple un neurone.
  • En enchaînant ainsi beaucoup de neurones, nous pouvons modéliser des fonctions trop complexes pour être modélisées par un seul.

Cela fonctionnent comme des LEGO ! Nous ne pouvons pas construire beaucoup de chose avec un seul bloc de LEGO, en revanche nous pouvons créé n’importe quoi si nous avons suffisamment de blocs à assembler.

Notre future faune sera t-elle en plastique? Seul le temps nous le dira …

Donnons une mémoire à notre réseau neuronal

Notre réseau neuronal précédent retourne toujours la même réponse lorsque nous lui donnons les mêmes entrées. Il n’a pas de mémoire. En programmation, cela s’appelle un algorithme stateless (sans état)

Dans beaucoup de cas (comme l’estimation du prix d’une maison), c’est exactement ce que l’on souhaite. Cependant, ce type de modèle ne peut pas réagir aux variations des données au fil du temps.

Imaginez que je vous ai remis un clavier et que je vous ai demandé d’écrire une histoire. Mais avant de commencer, mon travail consiste à deviner la toute première lettre que vous allez taper. Quelle lettre devrais-je choisir ?

Je peux utiliser mes connaissances en français pour augmenter mes chances de deviner la bonne. Par exemple, vous tapez probablement une lettre plus courante qu’une autre au début de vos mots. Si je lisais les histoires que vous aviez écrites dans le passé, je pourrais affiner davantage ma chance en me basant sur les mots que vous utilisez habituellement au début de vos histoires. Une fois que j’aurai toutes ces données, je pourrais l’utiliser pour construire un réseau de neurones pour modéliser la probabilité que vous commenciez avec une lettre donnée.

Notre modèle ressemblerait à ceci:

Mais complexifions le problème. Disons que j’ai besoin de deviner la lettre suivante n’importe quelle autre, n’importe où dans votre histoire. Voici un problème bien plus intéressant.

Utilisons les premiers mots de Ernest Hemingway’s The Sun Also Rises comme exemple:

Robert Cohn était un boxeur poids moy

Quelle lettre viendra après ?

Vous avez probablement deviné ’e’ — le mot va probablement être “moyen”. Nous savons cela à partir des lettres que nous avons déjà vues dans la phrase et de notre connaissance des adjectifs français. En outre, le mot «boxe» nous donne un indice supplémentaire étant donnée que le poids moyen correspond à une catégorie précise en boxe.

En d’autres termes, il est facile de deviner la lettre suivante si nous prenons en compte la séquence des lettres qui vient juste avant et que nous combinons cela avec notre connaissance des règles de français.

Pour résoudre ce problème avec un réseau de neurones, nous devons ajouter un état à notre modèle. Chaque fois que nous demandons une réponse à notre réseau de neurones, nous sauvegardons également un ensemble de nos calculs intermédiaires et les réutilisons la prochaine fois en entrée. De cette façon, notre modèle ajustera ses prédictions en fonction de l’entrée qu’il a vue précédemment.

Garder une trace de l’état dans notre modèle nous permet non plus seulement de prédire la première lettre la plus probable de l’histoire, mais également de prédire la lettre suivante la plus probable étant donné toutes les lettres précédentes.

C’est l’idée de base d’un Réseau Neuronal Récurrent. Nous mettons à jour le réseau chaque fois que nous l’utilisons. Cela lui permet de mettre à jour ses prédictions en fonction de ce qu’il a vu précédemment. Il peut même modéliser ses propres règles motifs au fur et mesure, pour peu que nous lui fournissons suffisamment de mémoire.

A quoi bon une seule lettre ?

Prédire la prochaine lettre d’une histoire peut sembler plutôt inutile. Quel est le vraie but ?

Une utilisation sympa serait de prédire un mot sur un clavier de smartphone:

La prochaine lettre la plus probable est “t”.

Mais si nous prenions cette idée à l’extrême ? Et si nous demandions au modèle de prédire le prochain personnage le plus probable encore et encore — pour toujours ? Nous lui demanderions d’écrire une histoire complète pour nous !

Générer une histoire

Nous avons vu comment nous pouvions deviner la lettre suivante dans la phrase d’Hemingway. Essayons de générer toute une histoire dans le style d’Hemingway.

Pour faire cela, nous allons utiliser l’implémentation du Réseau Neuronal Récurrent développé par Andrej Karpathy. Andrej est un chercheur en Deep-Learning à Stanford qui a également écrit une excellente introduction sur la génération de texte avec des RNN.

Nous allons créer notre modèle à partir du texte complet de The Sun Also Rises — 362,239 caractères utilisant 84 lettres uniques (y compris la ponctuation, majuscules / minuscules, etc). Cet ensemble de données est très petit par rapport aux applications typiques du monde réel. Pour générer un très bon modèle de style Hemingway, il aurait été préférable d’avoir plusieurs textes d’exemple. Mais c’est déjà suffisant ici pour jouer avec.

Au tout début, le RNN n’est pas très bon en prédiction. Voici ce qu’il génère après 100 tours d’entraînement:

hjCTCnhoofeoxelif edElobe negnk e iohehasenoldndAmdaI ayio pe e h’e btentmuhgehi bcgdltt. gey heho grpiahe.
Ddelnss.eelaishaner” cot AAfhB ht ltny
ehbih a”on bhnte ectrsnae abeahngy
amo k ns aeo?cdse nh a taei.rairrhelardr er deffijha

Vous pouvez voir qu’il a compris que parfois les mots ont des espaces entre eux, mais c’est à peu près tout.

Après environ 1000 itérations, les choses semblent plus prometteuses:

hing soor ither. And the caraos, and the crowebel for figttier and ale the room of me? Streat was not to him Bill-stook of the momansbed mig out ust on the bull, out here. I been soms
inick stalling that aid.
 “Hon’t me and acrained on .Hw’s don’t you for the roed,” In’s pair.”
 “Alough marith him.”

Le modèle a commencé à identifier les modèles dans la structure de base de la phrase. Il ajoute des points à la fin des phrases et cite même des dialogues. Quelques mots sont reconnaissables, mais il y a aussi beaucoup de bêtises.

Mais après plusieurs milliers d’itérations de formation, ça semble plutôt bien:

He went over to the gate of the café. It was like a country bed.
 “Do you know it’s been me.”
 “Damned us,” Bill said.
 “I was dangerous,” I said. “You were she did it and think I would a fine cape you,” I said.
 “I can’t look strange in the cab.”
 “You know I was this is though,” Brett said.
 “It’s a fights no matter?”
 “It makes to do it.”
 “You make it?”
 “Sit down,” I said. “I wish I wasn’t do a little with the man.”
 “You found it.”
 “I don’t know.”
 “You see, I’m sorry of chatches,” Bill said. “You think it’s a friend off back and make you really drunk.”

À ce stade, l’algorithme a capturé le modèle de base du dialogue court et direct d’Hemingway. Quelques phrases ont même un sens.

Comparez cela avec un vrai texte du livre:

There were a few people inside at the bar, and outside, alone, sat Harvey Stone. He had a pile of saucers in front of him, and he needed a shave.
 “Sit down,” said Harvey, “I’ve been looking for you.”
 “What’s the matter?”
 “Nothing. Just looking for you.”
 “Been out to the races?”
 “No. Not since Sunday.”
 “What do you hear from the States?”
 “Nothing. Absolutely nothing.”
 “What’s the matter?”

Même en ne recherchant des motifs qu’un caractère à la fois, notre algorithme a reproduit une prose à l’aspect plausible avec un formatage approprié. C’est plutôt cool !

Nous n’avons pas non plus besoin de générer du texte à partir de zéro. Nous pouvons nourrir l’algorithme en lui fournissant les premières lettres et en le laissant trouver les lettres suivantes.

Pour le fun, fabriquons une fausse couverture de livre imaginaire en générant un nouveau nom d’auteur et un nouveau titre en utilisant le texte de départ de “Er”, “He”, et “The S”:

Le vrai livre est à gauche et notre étrange livre informatisé est sur la droite.

Pas mal !

Mais la chose vraiment hallucinante est que cet algorithme peut comprendre des modèles dans n’importe quelle séquence de données. Il peut facilement générer des recettes réalistes ou de faux discours d’Obama. Mais pourquoi nous limiter au langage humain? Nous pouvons appliquer cette même idée à n’importe quel type de données séquentielles ayant un motif.

Faire Mario sans réellement faire Mario

En 2015, Nintendo a sorti Super Mario Maker ™ pour la Wii U.

Un rêve d’enfant !

Ce jeu vous permet de dessiner vos propres niveaux de Super Mario sur la console, puis de les télécharger sur Internet afin que vos amis puissent les jouer. Vous pouvez inclure dans vos niveaux tous les items classiques et les ennemis des jeux Mario originaux . C’est comme un jeu LEGO virtuel pour les gens ayant grandi en jouant à Super Mario.

Pouvons-nous utiliser le même modèle qui a généré du faux texte Hemingway afin de créer cette fois-ci de faux niveaux de Super Mario ?

Premièrement, nous avons besoin d’un ensemble de données pour la formation de notre modèle. Prenons tous les niveaux du jeu original Super Mario sorti en 1985:

Meilleur Noël du monde. Merci maman et papa!

Ce jeu a 32 niveaux et environ 70% d’entre eux ont le même style. Nous allons donc nous en tenir à ceux-là.

Afin d’obtenir la modélisation de chaque niveau, j’ai acheté une copie originale du jeu et j’ai écrit un programme permettant d’extraire tous les niveaux hors de la mémoire du jeu. Super Mario est un jeu vieux de 30 ans et il y a beaucoup de ressources en ligne qui vous aident à comprendre comment les niveaux ont été stockés dans la mémoire du jeu. Extraire des données de niveau d’un ancien jeu vidéo est un exercice de programmation amusant que vous devriez essayer un jour.

Voici le premier niveau du jeu (dont vous vous souvenez probablement si vous l’avez déjà joué):

Super Mario Bros. Level 1–1

Si vous regardez attentivement, vous remarquez que le niveau est composé d’une simple grille de cases :

Nous pourrions tout aussi bien représenter cette grille comme une séquence de caractères spéciaux représentant chaque case:

--------------------------
--------------------------
--------------------------
#??#----------------------
--------------------------
--------------------------
--------------------------
-##------=--=----------==-
--------==--==--------===-
-------===--===------====-
------====--====----=====-
=========================-

Nous avons remplacé chaque case du niveau par une lettre :

  • ‘-’ est un espace vide
  • ‘=’ est un bloc solide
  • ‘#’ est un brique cassable
  • ‘?’ est un bloc surprise

… et ainsi de suite, en utilisant une lettre différente pour chaque type de case du niveau.

Au final, voici sa représentation sous forme d’un fichier texte:

En regardant le fichier texte, vous pouvez voir que les niveaux de Mario n’ont pas vraiment de motif si vous les lisez ligne par ligne:

Ligne par ligne, il n’y a pas vraiment de modèle à capturer. Beaucoup de lignes sont complètement vides.

Les modèles du niveau n’émergent vraiment que lorsque vous considérez le niveau comme étant une série de colonnes:

En regardant colonne par colonne, il y a un vrai modèle. Chaque colonne se termine par un ‘=’ par exemple.

Donc, pour que l’algorithme trouve les modèles dans nos données, nous devons l’alimenter colonne par colonne. Déterminer la représentation la plus efficace de vos données d’entrée (appelée feature selection) est l’une des clés de l’utilisation des algorithmes d’apprentissage automatique.

Pour entraîner le modèle, j’ai eu besoin de faire pivoter mes fichiers texte de 90 degrés afin que les caractères soient introduits dans l’algorithme dans un ordre où un motif serait plus à même d’apparaître :

-----------=
-------#---=
-------#---=
-------?---=
-------#---=
-----------=
-----------=
----------@=
----------@=
-----------=
-----------=
-----------=
---------PP=
---------PP=
----------==
---------===
--------====
-------=====
------======
-----=======
---=========
---=========

Entraînons notre Modèle

Tout comme nous l’avons vu lors de la création du modèle de la prose d’Hemingway, un modèle s’améliore au et à mesure que nous l’entraînons.

Après un peu d’entrainement, notre modèle génère des déchets:

--------------------------
LL+<&=------P-------------
--------
---------------------T--#--
-----
-=--=-=------------=-&--T--------------
--------------------
--=------$-=#-=-_
--------------=----=<----
-------b
-

Il a en quelque sorte l’idée que ‘-’ et ‘=’ devraient apparaître beaucoup, mais c’est à peu près tout. Il n’a pas encore trouvé le modèle.

Après plusieurs milliers d’itérations, ça commence enfin à ressembler à quelque chose :

--
-----------=
----------=
--------PP=
--------PP=
-----------=
-----------=
-----------=
-------?---=
-----------=
-----------=

Le modèle a presque compris que chaque ligne devrait avoir la même longueur. Il a même commencé à comprendre une partie de la logique de Mario: Les tuyaux dans Mario mesurent toujours deux blocs de large et au moins deux blocs de haut, de sorte que les «P» dans les données devraient apparaître dans des groupes 2x2. Fascinant !

Avec beaucoup plus d’itérations, le modèle arrive au point où il génère des données parfaitement valides :

--------PP=
--------PP=
----------=
----------=
----------=
---PPP=---=
---PPP=---=
----------=

Faisons ainsi avec un niveau entier de données de notre modèle et retournons le horizontalement :

Un niveau entier, généré à partir de notre modèle !

Ces données sont impeccables ! Il y a plusieurs choses impressionnantes à remarquer :

  • Il a placé un Lakitu (le monstre qui flotte sur un nuage) dans le ciel au début du niveau — exactement comme dans un vrai niveau de Mario.
  • Il sait que les tuyaux qui flottent dans l’air devraient reposer sur des blocs solides et ne pas être suspendus dans les airs.
  • Il place les ennemis dans des endroits logiques.
  • Cela ne crée rien qui empêcherait un joueur d’avancer.
  • Cela ressemble à un vrai niveau de Super Mario Bros. parce qu’il est basé sur le style des niveaux originaux qui existaient dans ce jeu.

Enfin, prenons ce niveau et recréons-le dans Super Mario Maker :

Nos données de niveau après avoir été entré dans Super Mario Maker

À vous de jouer !

Si vous possédez Super Mario Maker, vous pouvez jouer ce niveau en le mettant en favori en ligne ou en le recherchant en utilisant le code de niveau 4AC9–0000–0157-F3C3.

Les jouets vs. les applications du monde réel

L’algorithme de Réseau Neuronal Récurrent que nous avons utilisé pour former notre modèle est le même type d’algorithme utilisé par les entreprises du monde réel pour résoudre des problèmes difficiles comme la détection de la parole et la traduction du langage. Ce qui fait de notre modèle un ‘jouet’ est qu’il est généré à partir de très peu de données. Il n’y a tout simplement pas assez de niveaux dans le jeu original de Super Mario pour fournir suffisamment de données pour un très bon modèle.

Si nous pouvions avoir accès aux centaines de milliers de niveaux Super Mario Maker créés par l’utilisateur que Nintendo a, nous pourrions faire un modèle incroyable. Mais nous ne pouvons pas — parce que Nintendo ne nous laissera pas les avoir. Les grandes entreprises ne donnent pas leurs données gratuitement.

Alors que l’apprentissage automatique devient plus important dans de plus en plus d’industries, la différence entre un bon programme et un mauvais programme sera défini par la quantité de données dont vous disposez pour former vos modèles. C’est pourquoi des entreprises comme Google et Facebook ont énormément besoin de vos données !

Par exemple, Google a récemment rendu opensource TensorFlow, sa boîte à outils logicielle pour la création d’applications d’apprentissage automatique à grande échelle. Cela semble incroyable que Google donne gratuitement une telle technologie. C’est sur cet outil qu’est basé Google Traduction.

Mais sans les données massive de Google dans toutes les langues, vous ne pouvez pas créer un concurrent de Google Traduction. Les données sont ce qui donne à Google son avantage. Réfléchissez à cela la prochaine fois que vous ouvrirez votre historique des positions Google Maps ou votre historique des positions Facebook et noterez qu’il stocke tous les lieux que vous avez visités.

Pour aller plus loin

Dans l’apprentissage automatique, il n’y a jamais un seul moyen de résoudre un problème. Vous disposez d’options illimitées pour décider comment pré-traiter vos données et quels algorithmes utiliser. Souvent, combiner plusieurs approches vous donnera de meilleurs résultats qu’une approche unique.

Les lecteurs m’ont envoyé des liens vers d’autres approches intéressantes pour générer des niveaux Super Mario:


Si vous avez aimé cet article, abonnez-vous à ma newsletter sur le Machine Learning (en anglais). Je ne vous enverrai un mail que si je trouve quelque chose d’intéressant à partager.

Continuer à lire Part 3, Part 4 and Part 5! (en anglais pour le moment)