Apprendre quand utiliser ces algorithmes et comment les personnaliser
Utiliser ces connaissances pour optimiser la performance et/ou la consommation de ressources => efficacité
Dans ce cours nous aborderons uniquement les pistes de départ de cette matière. Il faudrait des semaines de cours pour aborder plus solidement cette matière.
Rendre le travail réaliser le 31/10/2020 au soir + test en ligne
Bonus: possible d'aller plus loin jusqu'au 16/11/2020 08h00 pour des points bonus.
Quelle est la différence entre l'automatisation et l'intelligence artificielle?
Automatisation: ce qu'on sait faire avec une machine
Intelligence artificielle: ce qu'on voudrait faire avec une machine
Figure 1: L'intelligence artificielle
Questions irrésolues:
Comment une machine peut-elle:
optimiser un jeu de paramètres?
s'adapter a son environnement?
choisir entre plusieurs option?
fournir des solutions à des questions posées?
Renforcement d'apprentissage
Renforcement d'apprentissage: une autre manière d'apprendre.
Généralités
Questions
Comment peut on faire a meilleure action possible au bon moment?
D'abord:
Qu'est ce que la meilleure action?
qu'est ce que le bon moment?
Notre environnent change en permanence donc l'algorithme et/ou les paramètres choisis peuvent devenir faux.
Peut-être pourrait on tirer parti de l’expérience passée
Comment apprendre?
L'apprentissage supervisé est une tâche d'apprentissage automatique consistant à apprendre une fonction de prédiction à partir d'exemples annotés.
Source: Wikipédia
Figure 2: Apprentissage supervisé
Dans le domaine informatique et de l'intelligence artificielle, l'apprentissage non supervisé désigne la situation d'apprentissage automatique où les données ne sont pas étiquetées. Il s'agit donc de découvrir les structures sous-jacentes à ces données non étiquetées.
Source: Wikipédia
Figure 3: Apprentissage non supervisé
En intelligence artificielle, plus précisément en apprentissage automatique, l'apprentissage par renforcement consiste, pour un agent autonome (robot, etc.), à apprendre les actions à prendre, à partir d'expériences, de façon à optimiser une récompense quantitative au cours du temps. L'agent est plongé au sein d'un environnement, et prend ses décisions en fonction de son état courant. En retour, l'environnement procure à l'agent une récompense, qui peut être positive ou négative.
Source: Wikipédia
Figure 4: Apprentissage par récompense
Pourquoi un automate?
- Pour fixer un but a atteindre pour l'agent
- ou bien pour appliquer des règles simples, sans but réel (comportement émergent)
Il est essentiel de pouvoir valoriser un action qui nous fait passer d'un état a un autre.
Figure 5: Valorisation d'action
Pour la valorisation il est essentiel de se référer au gain a court terme et au gain a long terme. Il faut pouvoir prendre en compte plus que ce que je peux voir maintenant. Exemple: aux échecs le sacrifice de la reine car on sait que plus tard qu'on obtiendra un avantage ou une victoire. Il faudrait pouvoir prendre en compte toutes les conséquences de toutes les actions possibles.
En pratique c'est complexe et coûteux (en temps de calcul) pour des systèmes qui peuvent avoir des milliards d'états différents
et peut-être que l'on ignore des éléments
itérer pour approximer la solution optimale
Agent
Agent: de la théorie à la pratique
Pour décider l'action a réaliser on va s'appuyer sur des calculs probabilistes:
Figure 6: Tableau de choix d'action
Cette méthode permet d'obtenir une fonction d'utilité qui nous guidera sur la meilleure action à réaliser. Cette fonction nous donne la meilleure espérance de gain dans le futur. Dans notre cas c'est l'action 2 qui permettra le meilleure gain immédiat mais aussi dans le futur. Alors que l'action 3 nous donne peu de gain a court terme mais un gain conséquent a long terme.
On qualifie cette fonction:
Avec une somme finie:
utility(state_t, action)=E(reward(state_t, action)+max \sum{future\_reward})
Avec une somme infinie:
utility(state_t, action)=E(reward(state_t, action)+max \sum_{i=1}^{\infty}{attenuate^i.future\_reward_i})
Le terme utility_{t+1}(state_t,action) représente la progression itérative
Le terme step représente le taux d'apprentissage
Le terme attenuate.max_{action}utility(state_{t+1},action)) représente la capacité de "deviner le futur"
On va pouvoir changer la probabilité de faire une action dans un état donnée.
Exemple du moustique
Figure 7: Relation action/état du moustique
Figure 8: Tableau d'action/état du moustique
On va tester le programme fourni dans une VM, est nécessaire d'installer la librairie freeglut3-dev: sudo apt install freeglut3-dev.
Pour lancer la simulation il suffit de make le projet puis ./reinflearn
en tapant 0, 1, 2, 3 ,4 ,5 ,6 on peut choisir le facteur d'apprentissage du moustique.
On remarque qu'a 0 il se comporte comme un "marcheur ivre".
En tapant "a" il est possible de faire varier la position de la zone de confort du moustique.
Figure 9: Tableau d'action/état du moustique
Exemple du Jeu de Nim
En résolvant ce jeu on peut "expliquer" comment jouer a un automate.
Figure 10: Programme du moustique
Algorithme génétiques
Comment une machine peut-elle optimiser un jeu de paramètres?
Les algorithmes génétiques appartiennent à la famille des algorithmes évolutionnistes. Leur but est d'obtenir une solution approchée à un problème d'optimisation, lorsqu'il n'existe pas de méthode exacte (ou que la solution est inconnue) pour le résoudre en un temps raisonnable. Les algorithmes génétiques utilisent la notion de sélection naturelle et l'appliquent à une population de solutions potentielles au problème donné. La solution est approchée par « bonds » successifs, comme dans une procédure de séparation et évaluation (branch & bound), à ceci près que ce sont des formules qui sont recherchées et non plus directement des valeurs.
Source: Wikipédia
Exemple d'utilisation:
Générer des paramètres pour choisir la meilleure configuration d'automates logiciels;
Résoudre l'optimisation de conditions de frittage dans un espace de solutions de dimension 17;
Résoudre un "problème inverse mal posé" sur la reconstruction de volumes à partir d'images 2D.
On part d'un jeu de solutions possibles, on sélectionne 2 solutions possible que l'on va croiser. On décide de garder ou non cette solution, et on recommence en ajoutant ou non cette solution dans les solutions possibles.
Figure 11: Système de croisement de solutions
Fonction de fitness
Fonction de fitness: La fitness mesure la qualité de l'individu exprimée sous forme d'un nombre ou d'un vecteur. On dit qu'un individu i est meilleur que l'individu j quand i est plus proche de la solution que j.
Trouver la bonne métrique est parfois difficiles. Parfois changer la fonction de fitness après un moment. Elle doit être suffisamment sélective sans l'être trop.
La sélection probabiliste des individus est très importante.
Exemple
Cet exemple se penche sur un programme permettant de trouver le max d'un sinus.
Pour lancer la simulation il suffit de make le projet puis ./genalgo.
On peut choisir le spectre a étudier, 179° ou 719°. On remarque que pour 2 max sont possible. On peut donc se demander comment va réagir le programme.
Figure 12: Programme de recherche de max de cosinus
Robustesse de l’algorithme génétique
Si notre pire élément est remplacé par un élément meilleur que lui, notre population tend vers une meilleure forme.
Si notre pire élément est remplacé par un élément moins bon que lui, il sera remplacé le tour suivant par un autre élément. La probabilité qu'ils soient toujours remplacé par un plus mauvais est infime.
Donc la populations s'améliorera dans tous les cas.
Réseaux de neurones
Introduction
Le neurone est la brique de base.
Un neurone artificiel plus ou moins inspiré du neurone biologique (variante d'implémentation).
Il n'a réellement d’intérêt qu'intégré a un réseau.
Un humain a environ 100 milliards de neurones biologiques.
Figure 13: Cheminement dans un neurone artificiel
Figure 14: Représentation mathématique d'un neurone artificiel
On peut déduire la probabilité: y= \frac{1}{1+\exp(-x)}
Figure 15: Comment apprendre de manière supervisée?
Figure 16: Comment apprendre de manière non-supervisée?
Forger un neurone reviens a adapter ses poids synaptiques.
Pour être considéré robuste, un neurone doit être capable d'apprendre en résistant au bruit.
On parle de "deep-learning" au delà de 3 couches cachées.
Lorsque l'on va de la couche d'entrée vers celle de sortie, on parle d'"inférence".
Lorsque l'on va de la couche de sortie vers celle d'entrée, on parle d’"apprentissage".
dans l'archive neurone.tgz on récupère 2 fichiers: neurone.c et neurone.java. Ces programmes sont identiques mais nous nous concentrerons sur le programe en Java.
Pour l'exécuter:
javac neurone.java #création de neurone.class
jar cvf neurone.jar neurone.class #création de neurone.jar
touch MANIFEST.MF #création du manifestecho"Main-Class: neurone" > MANIFEST.MF #définition de la main-class
jar cvmf MANIFEST.MF neurone.jar neurone.class #ajout de MANIFEST.MF a neurone.jar
java -jar neurone.jar #exécution du programme
Mini-projet
Sujet
En se basant sur l'exemple en langage C fourni en cours, faire une implémentation du jeu de Nim (en C, C++, Java ou Python), où l'intelligence artificielle de jeu apprendra à jouer en s'affrontant elle-même.
Règles du jeu de Nim:
On dispose d'un tas de 20 allumettes.
A tour de rôle les 2 joueurs vont prendre 1, 2, ou 3 allumettes.
Celui qui prend la dernière allumette perd.
Stratégie est de laisser un nombre d'objets multiple de 4
Blague
