Machine Learning

Le site CS 188: Artificial Intelligence (Berkeley) propose des projets informatiques qui ont la particularité de partir d’un squelette existant. Ce sont des problèmes de machines learning très guidés où l’essentiel de l’effort est tourné vers les algorithmes.

Apprentissage par renforcement

Un problème souvent évoqué lorsqu’on parle d’apprentissage par renforcement est celui du tic tac toe. L’objectif de ce projet est de résoudre ce problème en utilisant l’apprentissage par renforcement. Quelques liens :

Remarque :

L’apprentissage par renforcement repose sur la connaissance de l’ensemble des états possibles du problèmes et ce nombre est souvent très grand. Trop grand. Le jeu du morpion ou tic-tac-toe peut être résolu sans optimisation de l’algorithme initiale. C’est le jeu utilisé par le surdoué dans WarGame pour démontrer à une intelligence artificielle que, bien joués, certains finissent toujours par une partie nulle. Pour d’autres jeux, le plus simple est souvent de chercher à réduire l’espace des états et des stratégies. Quelques applications envisageables dans le cadre de ce projets :

On peut envisager des contextes différents tels que le jeu de Pacman ou de Pong :

Autres pistes Reinforcement Learning, Multi Agent Reinforcement Learning (MARL).

Algorithme de Chow-Liu

Cet algorithme Chow Liu. Il sert à construire des relations entre des variables aléatoires. On pourra procéder en deux étapes :

  • implémentation de l’algorithme et vérification sur un jeux de données synthétiques

  • application sur un jeu de données plus conséquent

Ressources

Reconnaissance des visages de ses amis

La librairie OpenCV permet d’effectuer des traitements d’images assez complexes comme localiser le visage d’une personne prise en photo. L’image suivante est extraite de Face Detection in Static Images With Python.

http://s3.amazonaws.com/static.creatingwithcode.com/wp-content/uploads/2009/02/output.jpg

La tâche qu’on veut pouvoir accomplir à l’aide d’un programme python est la suivante :

  • On suppose qu’on dispose d’une vingtaine de photos de personnes, chacun distincte et identifiée. On suppose que les photos ont été prises avec le même appareil, un téléphone portable par exemple.

  • On prend une nouvelle photo avec ce même appareil. On veut automatiquement ranger cette photo dans un répertoire associé à la personne reconnue.

On pourra lire les articles suivant :

La version OpenCV pour Python 3 est très récente et la version finale devrait être prête pour fin 2014 / début 2015.

Deux outils pour annoter des images si vous n’en avez pas :

Deep et Extreme Machine Learning

C’est assez ambitieux comme premier projet. MNIST est le premier problème mentionnant le Deep Learning. Ce site recense les différentes performances obtenues jusqu’à présent sur ce modèle.

Sujet à préciser en fonction des attentes des élèves.

Librairies, modules :

Alignement de mots dans l’optique de constuire un traducteur automatique

L’algorithme est présentée dans l’article : Word Alignment via Quadratic Assignment de Simon Lacoste-Julien, Ben Taskar, Dan Klein, Michael I. Jordan. On pourra commencer sur un jeu de données petit et fabriqué manuellement. On pourra ensuite s’attaquer à des sites web qui proposent des traductions anglais/français de leur contenu. Autres liens intéressants proposés par les élèves qui ont travaillé sur ce sujet :

Fast k-NN (2016)

L’algorithme des k plus proches voisins est un des plus simples algorithmes d’apprentissage mais très coûteux. L’article suivent propose une façon d’optimiser le calcul dans des espaces de grande dimension.

Fast k-NN search

Accélération de la descente de gradient dans le cadre d’une optimisation convexe (2016)

La descente de gradient est une technique d’optimisation très connue utilisée lorsqu’on ne sait pas exprimer de façon explicite la solution d’un problème d’optimisation : on cherche le minimum ou le maximum de la fonction.

Si l’algorithme converge lorsque la fonction à optimiser est convexe, il existe des cas particuliers où on peut accélérer la convergence comme dans le cas de cet article qui propose une façon intuitive de le faire : A geometric alternative to Nesterov’s accelerated gradient descent.

L’objectif est d’implémenter cet algorithme puis de le comparer avec d’autres méthodes.

On pourra également regarder : Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent et Revisiting Nesterov’s Acceleration.

Construction d’un estimateur du caractère éthique d’un moteur de recherche (2017)

On se pose de plus en plus la question du caractère éthique des algorithmes : Tous algorithmés, tous concernés, Google, democracy and the truth about internet search. On se place dans le cas ici d’un site qui proposent des contenus à partir d’une requête (moteur de recherche, vente en ligne, publicité). Comment exprimer le fait que les résultats produits par le site ne sont pas biaisés éthiquement, comment mesurer le caractère éthique des résultats ? Le sujet est assez libre mais implique certainement la manipulation de texte. Côté scientidique, on pourra s’inspirer de l’article FairTest: Discovering Unwarranted Associations in Data-Driven Applications.

Détection de fumée dans les images (2017)

C’est une idée extraite de l’article : Early Fire Detection Using HEP and Space-time Analysis. Elle ne requiert pas nécessaire de machine learning mais s’appuie plus simplement sur des indicateurs construits à partir des images. Le projet devra commencer par récupérer des images sur Internet (via un moteur de recherche par exemple).

Ecrire une librairie pour représenter des modèles de machine learning (2018)

Supposons qu’une forêt aléatoire a été appris pour classifier un jeu de données, est-il possible de la représenter de façon à faciliter son interprétation. On pourra s’inspirer du module animl. On choisira de limiter le nombre de dépendance au minimum.

Implémenter un algorithme des plus proches voisins amélioré (2018)

Le sujet s’appuie sur l’article Neighbourhood Components Analysis qui propose d’apprendre un modèle des plus proches voisins tout en apprenant également une distance dite de Malahanobis qui permet de pondérer différemment chaque dimension. Il faudra comparar cet algorithme à d’autres approche de machine learning voire apporter sa propre contribution.