Une autre algorithmie de la découverte

mars 21, 2012

La Fondation Cartier organise ce jeudi 22 mars à 19h, une discussion Google Hang-Out sur curiosité et les algorithmes avec 5 ingénieurs de Google, Pierre-Yves Oudeyer et moi-même. 

L’exposition de la Fondation Cartier « Mathématiques, un dépaysement soudain » ferme ses portes cette semaine à Paris. Laurent Bolli et moi-même avons collaboré sur plusieurs projets de l’exposition :

- Le projet, finalement non retenu sous cette forme de la bibliothèque de Gromov (voir mon précédent bille « Replier les textes comme des proteines« )

- Le projet de Takeshi Kitano et David Lynch : La réponse est 2011 (voir également un autre billet sur ce sujet et sur la solution inventée par Quentin Bonnard, un des mes doctorants)

- L’application iPad de l’exposition basée sur le principe mathématique de la curiosité exploré par Pierre-Yves Oudeyer et moi-même il y a quelques années.

Je n’avais pas pris le temps à l’époque d’expliquer le principe original de ce dernier projet.


Cercle de pertinence, cercle de curiosité

L’application présente plusieurs centaines de documents provenant de l’exposition mais aussi des archives de la Fondation Cartier (Contenus sonores, Biographies, Vidéos, Concepts, Images, Evènements). Chaque document est associé à un vecteur N de k paramètres codant un identifiant, son type et des indications sur son contenu. L’espace des documents peut donc être considéré comme un espace de dimension k, relativement grand. L’utilisateur va naviguer dans cet espace grâce à deux algorithmes.

L’interface de l’application est organisée sous la forme de deux cercles concentriques. Le premier cercle de « pertinence » présente les transitions statistiquement les plus communes entre le noeud central N(t) et les autres noeuds de le l’application étant donné le chemin S(t) = Sn(t) = ((N(t), N(t-1)…. N (t-n)) récemment parcouru par l’utilisateur. Le système tente donc de prédire quel sera le prochain noeud à visiter en fonction du parcours des autres utilisateur.  Il s’agit donc d’un système de recommandations assez classique basé la maximisation de la prédiction.  A partir de l’analyse de l’ensemble des chemins des utilisateurs, l’algorithme propose les chemins qu’il a observés comme étant les plus choisis. A chaque choix d’un noeud par l’utilisateur il améliore également son modèle de transition (distribution statistique des transitions à partir d’un chemin donné). Tous les parcours des utilisateurs contribuent donc à affiner ce modèle central.

Le second cercle de « curiosité », l’algorithme propose des noeuds basés sur une adaptation des algorithmes de découverte que nous avons développés Pierre-Yves Oudeyer et moi-même il y a presque dix ans (voir les pages que Pierre-Yves Oudeyer proposent sur ce sujet, un peu plus à jour que les miennes).  Ces algorithmes apprennent un peu comme des enfants (un projet que Turing formulait déjà clairement dans les années 1950s). Ils ne tentent pas de faire des choix en fonction de critères extérieurs (ex: proposer la réponse la plus pertinente pour un utilisateur) mais pour optimiser leur propre apprentissage. A tout moment, ils se posent la question : que dois-je maintenant faire pour un apprendre le plus possible sur l’espace que j’explore ?.

Il est probable que ce soit ce même type de motivation intrinsèque qui pousse par exemple un jeune enfant à jouer avec l’emballage d’un cadeau plutôt qu’avec le jouet qu’il contient. La promesse sensorimotrice de l’emballage étant plus alléchante que celle proposée par le jouet. Nous avons également montré comme ce principe permet de faire émerger des séquences développementale organisée chez un robot apprenant (voir notre article sur ce sujet mais également la video d’AIBO apprenant à marcher grâce à ce type d’exploration ou la salle de jeux pour robot qui nous avions développée avec des designers de l’ECAL pour explorer ce même principe.). A la Fondation Cartier, Pierre-Yves Oudeyer a présenté Ergo-robots, une installation robotique  mise en scène par David Lynch qui permet de découvrir comment se comportent un groupe de robots, motivé par le principe de curiosité.

Les algorithmes de curiosité donnent des effets impressionnants en robotique, mais leur utilité est bien plus large. Ce champ de recherche rejoint d’ailleurs d’autres domaines des statistiques développées en 1972 par Fedorov sous le terme « optimal experiment design » . Des chercheurs en Machine Learning comme Jurgen Schmidhuber ont, dès les années 1990s, commencé à théoriser la pertinence de ces algorithmes pour l’exploration de grands espaces de données. En une vingtaines d’années tout une famille d’algorithmes ont vu le jour, tous construits autour  d’une même intuition : les machines doivent choisir les meilleures actions pour optimiser leur propre apprentissage. 

Un algorithme dont l’apprentissage progresse optimallement

C’est un même principe que nous avons mis en oeuvre pour le second cercle de l’application iPad de la Fondation Cartier. L’algorithme essaie de comprendre la relation entre la présentation de certains documents et le fait qu’ils soient ou non consultés par l’utilisateur dans le contexte d’un chemin de découverte particulier. L’algorithme sait déjà que certains documents sont d’ordinairement choisis (cercle de pertinence) mais il est encore ignorant de la structure de la plus grande partie de l’espace qu’il doit explorer. N’ayant pas une infinité d’essais (puisque chaque essai demande l’intervention d’un utilisateur de l’application), il doit proposer des choix qui lui permettront de progresser optimallement dans son apprentissage.

Plus formellement, il s’agit d’optimiser I(S(t), A(t)),  l’intérêt d’effectuer l’action A(t) (le choix d’un noeud) dans l’état S(t). Cet intérêt peut être approximé par la dérivée de la qualité prédictive. Si la qualité d’une prédiction d’une transition vers un noeud (N+1) est en augmentation (le système est en train de perfectionner son modèle de transition vers noeud à partir du chemin S(t)), ce noeud aura un bon score d’Intérêt).

A chaque interaction l’algorithme propose ainsi dans le cercle de curiosité 14 contenus dont l’intérêt en terme d’apprentissage est optimal. Comme de nouveaux contenus peuvent être rajoutés à l’application, nous avons également introduit un biais pour les noeuds dont l’algorithme sait très peu de chose.  Ceci aura pour effet d’introduire plus souvent dans le cercle de curiosité, les nouveaux noeuds de manière à tester rapidement leur pertinence et leur intérêt.

Jeudi 22 mars à 19h, lors d’un Hang-Out Google+ sur la page de la Fondation Cartier, nous discuterons de toutes ces questions avec cinq ingénieurs de chez GoogleMehyrar Mohri (publications), David Singleton (blog), Aaron Shon (Bayesian cognitive models for imitation), Rich Washington (homepage), Radu – Eosif Mihailescu (blog). Une retransmission simultanée entre Dublin, Zurich, Lausanne, Paris, Bordeaux et les Etats-Unis…

About these ads

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s

Suivre

Recevez les nouvelles publications par mail.

Rejoignez 217 autres abonnés

%d blogueurs aiment cette page :