Projet 2: Retour sur le projet Pac Man .... avec des algorithmes de machine learning

Objectif comparer approche "recherche par algorithmes de parcours de graphe" vs ''apprentissage automatique"

Dans ce projet nous allons réutiliser le code du projet Pac Man, que vous connaissez mieux maintenant, pour traiter le problème sous une approche différente. Dans le projet 1 nous avons traité le problème de la création d'un agent intelligent sous l'angle de la classe des problèmes de recherche (search), en utilisant en particulier des algorithmes de parcours de graphe, comme par exemple minimax, utilisé dans de nombreux problèmes de jeux.

Comment aurions nous résolu ce problème si nous ne connaissions pas ces algorithmes ? Dans certaines catégories de problèmes, il n'existe pas du tout de solutions algorithmique ou pas de solutions calculables dans un temps raisonnable. Dans ce genre de cas une approche statistique est souvent la seule solution possible, l'apprentissage automatique devient alors une solution envisageable si on possède suffisamment de données pour modéliser notre problème.

Dans ce projet, vous devez programmer un agent intelligent utilisant des algorithmes d'apprentissage automatique. Afin d'alimenter vos algorithmes, vous aurez besoin de données, que vous allez créer à partir de la partie du code qui renvoie des informations sur l'environnement de tâche du jeu.

Conseils généraux d’organisation

Identifiez des variables d'intérêt et vos labels à utiliser pour d'apprentissage
Stockez les les dans une structure de donnée tabulaire (dataframe ou array) afin de vous constituer un premier jeu de donnée
Choisissez une métrique d'évaluation
Entraînez un algorithme simple de classification et enregistrez vos résultats
Réglez les paramètres pour optimiser votre algorithme
Enrichissez vos données
Testez différents algorithmes ou des combinaisons d'algorithmes simples
Gérez le problème du sur apprentissage
Répétez les étapes précédentes ...

Partie 1: Créez votre jeu de données

Modélisation du problème

On veut prédire à chaque itération la direction à prendre pour pacman, il s'agit d'une tâche de classification.
Contrairement à l'approche de résolution de problème par recherche de graphe, dans ce projet vous devrez vous devrez modéliser par des données les caractéristiques du problème à résoudre: l'état de la situation de jeu et les actions des agents adversaires. Comment ? en constituant un jeu de données représentant le plus fidèlement possible votre problème.

Quelques pistes pour vos orienter dans la construction de votre jeu données

Quels sont les labels que vous allez choisir ?
Quelles types de parties allez vous utiliser pour constituer votre jeu de données ? Vaut il mieux en sélectionner certaines en particulier ?
Faites des tests pour évaluer la quantité de données 'optimales' pour avoir de bons résultats
Procédez de manière itérative: constituer un échantillon de données de taille modeste, tester des algorithmes, identifier des données qui pourraient vous manquer, enrichissez vos données, recommencez ...

Quelques idées de variables à extraire pour constituer votre jeu de données

position de pacman dans le labyrinthe
distance de pacman au fantômes
état des cases voisines (vide, fantôme, nourriture, ..)
résultat de votre fonction d'évaluation (état de la situation de jeu) ...

Partie 2: Choisissez, testez et adaptez vos algorithmes

Maintenant que vous avez un début de jeu de données exploitable, je vous invite à le tester en utilisant plusieurs algorithmes de machine learning et définissant une métrique d'évaluation. Je vous invite fortement à notez les résultats de vos tests pour identifier les situations ou vos algorithmes ont de mauvaises performances. Ces résultats vous permettront aussi de tenter d'identifier les données supplémentaires que vous pourriez extraire pour enrichir votre jeu de données existant et ainsi tenter d'améliorer la performance de vos algorithmes.
Voici une liste non exhaustive d'algorithmes d'apprentissage supervisé pour la classification que vous pouvez tester en particulier:
- la régression logistique multi-classe
- la régression ridge
- les Support Vector Machines (SVM)
- la Descente de gradient stochasitque
- un réseau de neurone simple, le Perceptron multi-couche
- les k-Nearest neighbours (kNN) - les arbres de décisions
- le classifieur naif bayesien

Bien entendu, comme vous découvrez probablement ces algorithmes, il est possible que vous n'en saisissiez pas les principes généraux. N'hésitez pas à me solliciter ;-)

critères de choix

De manière générale, voici quelques critères qui pourront influencer le choix des algorithmes à utiliser:

leur perfomance moyenne (au travers de plusieurs métriques)
leur temps d'éxécution
leur complexité: un algorithme complexe aura beaucoup de paramètres à régler et sera plus soumis au problème de sur apprentissage

Partie 3: Vérifier si vous gérez les limitations de l'apprentissage automatique

Une fois que vous avez généré et testé des jeux de données pour votre problème, vous pouvez revenir en détail sur certaines notions fondamentales du machine learning afin de mieux les comprendre. Faites attention, certaines de ces notions concernent des limitations inhérentes au machine learning que vous aurez peut être à considérer dans la résolution de votre problème. Vous pouvez lire les chapitres suivants pour avoir plus de détails sur ces limitations:

Le compromis biais-variance et généralisation

Le "réglage" d'un bon compromis entre le biais et la variance de votre modèle va grandement conditionner la capacité de votre modèle à généraliser, c'est-à conserver de bonnes performances lorsque l'on applique sur un jeu de donnée qu'il n'a jamais traité. Pour vous en faire une idée plus précise de ces deux concepts vous pouvez lire les chapitres correspondants, sur le compromis biais-variance et la notion de généralisation. Remarque: ces deux chapitres prennent l'exemple de l'algorithme K-Neirghest Neigbour (KNN) qui est expliqué dans un chapitre précédent

Le fléau de la dimension

Si vous souhaitez avoir des explications illustrées de ce phénomène, rendez-vous dans ce chapitre

Le théorème no free lunch et la notion d'intractabilité

Ces deux notions sont un peu moins importantes dans le cadre de votre projet. Vous pouvez néanmoins avoir des explications plus détaillés en suivant ce chapitre

Lexique et documentation

Lexique

Pour vous aidez, vous pouvez retrouvez une description vulgarisée des notions importantes dans la section Ressources additionnelles du cours

Documentation de scikit-learn

Dans le cadre de ce cours, nous allons utiliser principalement la librairie scikit-learn dont la documentation vous sera très utile pour comprendre, implémenter et tester vos algorithmes.