Veille artificielle #2 – Voitures autonomes

Le véhicule autonome est un véhicule « capable de rouler automatiquement et en toute autonomie dans le trafic réel et sur une infrastructure non spécifique sans l’intervention d’un être humain. ». Le véhicule complètement autonome n’est pas encore d’actualité, mais il existe de plus de systèmes autonomes intégrés dans les véhicules produits. Progressivement, les véhicules seront de plus en plus automatisés jusqu’au développement de véhicules complètement autonomes d’ici 15-20 ans.

Des véhicules autonomes dès demain ?

Dixit Thomas Schmid, patron de Hyundai en Europe, la voiture autonome sur nos routes n’est pas pour demain. Dans une interview récente accordée à la TV danoise,  le PDG de Tesla, Elon Musk estime que beaucoup de systèmes autonomes existeront d’ici 2020, qu’il faudra encore attendre quelques années pour avoir des systèmes parfaitement autonomes et que d’ici 20 ans, la plupart des véhicules produits seront autonomes (« if civilization still exists » – l’art du spectacle par Elon Musk) . Au Japon, Robot Taxi (collaboration ZMP – véhicules autonomes – et DeNa – internet mobile) mettra en service dès 2016  un système de transport rapide de proximité vers des commerces locaux pour les habitants de la ville de Fujisawa. Si le test est concluant, le Japon prévoit d’utiliser des véhicules autonomes pour transporter les spectateurs pendant les Jeux Olympiques de 2020. Dès 2015, au Pays-Bas, le véhicule autonome WEpod (créés par la société française easymile – voir la vidéo ci-dessous) circulera sur les routes néerlandaises pour relier les villes de Wageningen et Ede, distantes d’environ 10km. Lire la suite

Veille artificielle #1

 

Sur le front de l’IA, le deep learning est toujours le grand sujet d’actualité.

Facebook veut en savoir toujours plus sur votre personnalité (en)

Google Voices veut améliorer son système de reconnaissance vocale (en)

On peut également tenter de générer des fictions grâce au deep learning (en)

Watson (IBM) cherche à diagnostiquer des cancers en analysant des radios et des IRM (en)

Microsoft essaye d’apprendre le sens de l’humour à un bot (fr)

D’autres news du côté de l’Intelligence Artificielle

Un robot fabrique et sélectionne ses enfants (fr)

Le premier épisode (audio) de la série Ethical Machines (série consacrée aux liens entre humains, machines et les questions d’éthique). Le premier invité est Mark Riedl, professeur d’IA / digital storytelling à Georgia Tech (en) Lire la suite

Sérendipité, du conte au concept (fiche de lecture)

Voici une fiche de lecture à propos du livre « Sérendipité, du conte au concept » de Sylvie Catellin.

Vous retrouvez cette fiche dans la lettre n°8 de la Chaire Modélisation des Imaginaires, Innovation et Création.

————-

Note de l’auteur : je ne parle pas encore de moi à la troisième personne, la note a été légèrement modifiée par les éditeurs de la lettre, en particulier la fin.

Dans son livre, Sérendipité, du conte au concept, Sylvie Catellin, Maître de conférences HDR en sciences de l’information et de la communication à l’Université de Versailles Saint-Quentin-en-Yvelines, retrace l’histoire du concept de sérendipité, un mot né de la fiction qui s’est propagé dans le champ de la découverte scientifique. Inventée par l’écrivain et homme politique Horace Walpole en 1754, qui forme le terme à partir d’un conte racontant le voyage des Princes de Serendip, la sérendipité est définie par ce dernier comme la découverte par hasard et sagacité de ce que l’on ne cherchait pas. Or, le hasard, qui ne joue qu’un rôle mineur, occulte trop souvent la sagacité qui est le cœur du raisonnement sérendipien. En retraçant l’histoire du concept de sérendipité, de son invention, de ses origines, de son oubli, de sa redécouverte et de sa propagation, Sylvie
Catellin redonne au mot sérendipité sa vraie signification et montre comment le raisonnement créatif sérendipien a fortement influencé la recherche scientifique et la littérature.

L’histoire des Princes de Serendip (nom ancien de Ceylan) est celle de trois princes en voyage qui rencontrent un chamelier à la recherche d’un chameau égaré. Les princes ayant vu des traces d’un animal semblable sur leur chemin disent l’avoir croisé et décrivent précisément un chameau qu’ils n’ont pas vu en interprétant des indices observés. Voici donc la base du raisonnement sérendipien : une situation surprenante est observée et la sagacité des princes leur permet de former une explication plausible. Le hasard ne joue ici qu’un rôle mineur, c’est la sagacité des princes qui est au cœur du raisonnement sérendipien. Cette sagacité, Sylvie Catellin relève qu’elle est proche du concept d’abduction au sens du philosophe et logicien Charles Peirce (1839-1914). L’abduction est un processus argumentatif qui consiste, à partir d’effets observés, à générer une hypothèse explicative satisfaisante.

C’est un raisonnement imaginatif qui fait appel à nos connaissances implicites. Le mécanisme de l’abduction est également un processus créatif dans le sens où il est générateur de nouvelles connaissances. Toutefois, il ne faut pas oublier que le résultat du processus d’abduction, bien que plausible, reste imprévu et incertain. Le mécanisme d’abduction ne fait que suggérer que quelque chose peut être. Naturellement, le mécanisme d’abduction qui est au cœur du raisonnement sérendipien se rapproche du processus de la découverte scientifique. Il faut, pour qu’il y ait découverte, que des faits surprenants soient observés par une personne capable de les détecter et de les interpréter.

Mais ce qui frappe à la lecture du livre de Sylvie Catellin, c’est la très grande proximité entre le raisonnement sérendipien et la production d’œuvres de fiction. En effet, il faut ici se souvenir que le raisonnement sérendipien est né de la fiction. Il s’est ensuite propagé comme motif littéraire dans un grand nombre d’œuvres de fiction. Le raisonnement sérendipien, en tant que processus abductif visant à expliquer des évènements surprenants, est à rapprocher de l’enquête judiciaire ou du diagnostic médical. De Sherlock
Holmes à Docteur House en passant par la Comédie humaine, de nombreux récits sont construits sur le modèle d’un raisonnement sérendipien. On retrouve d’ailleurs dans la notion de sérendipité les éléments classiques de la narration : le conflit inattendu, l’incertitude sur les évènements et leur explication ou encore la nécessaire résolution des conflits dans le récit.

Le livre de Sylvie Catellin nous amène donc à penser les liens entre les mécanismes cognitifs du raisonnement et la production des fictions. La fiction y apparaît comme un objet qui invite son lecteur à raisonner pour résoudre un conflit initial. Un auteur de fiction aurait alors pour objectif de perdre, tromper, duper ce lecteur pour le forcer à explorer des voies sans issues ou erronées. À la lecture de ce livre, la fiction semble apparaître comme une forme d’abduction, parsemée d’inattendu, dont la finalité consiste à résoudre un conflit initial surprenant. Cela ouvre des perspectives intéressantes en terme de modélisation cognitive pour la génération de fictions.

En retraçant l’histoire du concept de sérendipité, Sylvie Catellin lève le voile sur ce mot intriguant, cette notion souvent mal comprise. La sérendipité, c’est le raisonnement créatif provoqué par le hasard, c’est l’imaginaire à l’œuvre. Dans sa thèse Antoine Saillenfest rejoint Sylvie Catellin. Dans le cadre de ses travaux sur la modélisation des récits de fiction, il étudie la perception de l’inattendu et l’abduction. Ses premiers résultats sont très prometteurs dans l’optique de générer automatiquement des scénarios.

serendipite

————-

Je vous conseille vivement la lecture de ce livre « Sérendipité, du conte au concept » de Sylvie Catellin.

En bonus, vous pouvez aussi écouter une présentation de ce livre par Sylvie Catellin ainsi que son intervention sur France Inter dans la Tête au carré du 11 février 2014.

(image en-tête : Horace Walpole par John Giles Eccardt, circa 1755. )

La loterie et la surprise, un problème de complexité

Breaking news : Surprise lors du tirage du loto ce soir. La combinaison gagnante est 1-2-3-4-5-6. Un responsable de la Française des Jeux a affirmé que c’est une situation totalement inédite. Interrogé sur un possible bug dans le système de tirage, il a opposé un démenti ferme, assurant que le système a fonctionné normalement et que le résultat est bien le fruit d’un processus aléatoire.

L’exemple (fictif) ci-dessus illustre l’intérêt qu’ont les être humains pour les situations où « le hasard » semble jouer des tours. La plupart des tirages du loto sont parfaitement inintéressants pour ceux à qui ils ne font pas gagner d’argent. Cependant, certains tirages seraient surprenants au point de faire la Une des journaux s’ils devaient sortir un jour. En effet, les humains sont très sensibles aux combinaisons chiffrées qui présentent des régularités identifiables « inattendues ». Cela peut être un compteur kilométrique de voiture qui affiche 111111 km parcourus ou encore un nombre d’abonnés Twitter égal à 123321. Ces situations sont inattendues car elles ne correspondent pas au prototype (ou à l’idée) que l’on se fait de ce genre de situations.
Dans le cas du loto, chaque tirage devrait correspondre à l’image que l’on a d’un tirage aléatoire, c’est-à-dire un tirage sans régularité facilement observable. Les tirages 1-2-3-4-5-6 ou encore 5-10-15-20-25-30 nous semblent éloignés du prototype de tirage aléatoire et leur probabilité subjective d’occurrence (c’est-à-dire la probabilité qu’ils sortent) nous apparaît comme faible. Cela les rend, par conséquent, surprenants. C’est cet effet de surprise auquel je m’intéresse dans cette note de blog. Je vais introduire la notion de complexité cognitive, montrer qu’elle peut servir à modéliser l’effet de surprise et que ce modèle permet de faire des prédictions intéressantes sur le plan empirique.

—————————————-

Avant de parler de la surprise, je dois commencer par vous familiariser avec la notion de complexité. En sciences cognitives, la notion de complexité a été introduite pour rendre compte de biais perceptifs vers la simplicité (Chater, 2009). Parmi un ensemble de motifs possibles pour représenter une information, un humain va avoir tendance à choisir celui qui offre la représentation la plus simple de l’ensemble de l’information disponible, c’est ce que l’on appelle le principe de simplicité. L’exemple de la partie cachée ci-dessous donne une bonne idée du principe de simplicité.

partie_cachee

La notion de complexité cognitive est héritée de la notion de complexité algorithmique introduite en théorie de l’information dans les années 1960 de manière conjointe par les mathématiciens Ray Solomonoff, Andrei Kolmogorov et Gregory Chaitin (Li & Vitányi, 2008). Cette complexité, dite de Kolmogorov, mesure la taille minimale du « programme » (en nombre de bits d’information) qui permet de produire une certaine structure donnée (cf. note 1).  En particulier, des chaînes binaires « simples » (par exemple 01010101010101010101010101010101010101010101) peuvent être produites par un programme génératif court (« écrire ’01’ 22 fois »), ce qui n’est pas le cas pour des chaînes plus complexes (par exemple 01100011011101001010011111010101110100101011). Dans le pire des cas, il faut épeler la chaîne entièrement et le programme le plus court est donc au moins aussi long que la chaîne elle-même. C’est généralement ce qui se passe pour les chaînes binaires générées aléatoirement. La complexité d’une chaîne binaire générée aléatoirement est donc généralement de l’ordre de la taille de ladite chaîne. Ainsi, la complexité de Kolmogorov constitue une forme de « mesure de l’aléatoire ».

La notion de complexité algorithmique peut être utilisée pour définir la notion de probabilité algorithmique. Dans les travaux de Solomonoff, la probabilité algorithmique p(s) d’une structure s dépend de la taille de sa description minimale C(s) via la formule p(s) = 2^{-C(s)} (cf. note 2).  La formule traduit ainsi l’idée qu’un objet plus simple qu’un autre objet est un objet dont la probabilité est plus grande que celle de l’autre objet.

Revenons maintenant à l’exemple des tirages de loterie surprenants. La formule de probabilité précédente ne rend pas compte de l’attitude d’un être humain face à une telle situation. Cela reviendrait à dire que l’occurrence d’un tirage simple à décrire (i.e. la taille de la description minimale est petite) tel que 1-2-3-4-5-6 nous apparaît comme plus « probable » qu’un tirage plus complexe à décrire tel que 9-20-26-27-34-45, ce qui entre en contradiction avec l’effet de surprise face aux tirages qui présentent de fortes régularités numériques.

Le problème de la formule de la probabilité algorithmique est qu’elle ne prend en compte que les aspects de génération (ou production) d’un objet. Dans le cas des loteries qui est un processus génératif aléatoire, chaque tirage a, a priori, la même probabilité de sortir, ce qui veut dire que leur complexité de production est égale (et très élevée car cela revient à générer aléatoirement chaque nombre du tirage parmi les nombre possibles restants). Pour rendre compte de l’effet de surprise face aux tirages de loterie surprenants, il faut distinguer la production du tirage de son observation. Bien qu’ils soient le produit d’un même processus aléatoire, certains tirages sont plus simples à décrire (ou observer) que d’autres. Ainsi l’effet de surprise vient d’une différence entre la complexité attendue pour produire la situation et une anormale simplicité pour la décrire. Les tirages anormalement simples à décrire sont perçus comme surprenants. En théorie de l’information, cela se rapproche de la notion de randomness deficiency qui mesure l’écart entre la complexité maximale d’un objet dans un ensemble d’objets (par exemple l’ensemble des tirages possibles) et la complexité d’un objet particulier de l’ensemble.

Pour rendre compte de l’effet de surprise devant une situation de tirage surprenant, il nous faut donc considérer  la différence entre la complexité C_w pour générer un tirage et la complexité C_d pour le décrire. On peut ainsi définir l’inattendu U (pour unexpectedness) d’une situation par la formule U = C_w - C_d. En utilisant la formule de l’inattendu on peut définir une probabilité subjective d’occurrence d’un tirage par la formule p = 2^{-U}, ce qui peut être écrit sous la forme :

    \[p = 2^{-C_w + C_d}\]

Dans le pire des cas, la description du tirage consiste à décrire sa génération (on épelle chaque nombre du tirage l’un après l’autre). Ainsi, l’observation est aussi complexe qu’attendue (le tirage correspond bien à notre prototype mental de tirage aléatoire), C_w = C_d et p = 1, il n’y a donc pas de surprise. Si le tirage est particulièrement simple à décrire, alors C_w(s) >> C(s) et p(s) << 1, le tirage est donc surprenant. Dans le cas des tirages de loterie, la complexité attendue est la même pour tous les tirages, seule la description varie d’un tirage à l’autre. Les tirages les plus simples à décrire apparaissent comme étant les moins probables, ce qui est cohérent avec l’observation.

Cette modélisation n’est pas que théorique malgré l’objection classique qui consiste à rappeler que la complexité est non-calculable. Les calculs de complexité sont des calculs de compression de l’information, on peut donc proposer des méthodes de calcul, certes approximatives, mais qui rendent compte des phénomènes que l’on désire modéliser. C’est ce que je vais montrer à travers la présentation de deux études qui ont testé l’influence de la taille de la description minimale des tirages de loteries sur la manière dont elles sont perçues. Ces deux études poursuivent un but similaire qui est de montrer que la probabilité intuitive (ou subjective) face à un tirage remarquable de loterie dépend effectivement de la taille de sa description minimale, c’est à dire la compression maximale de l’information pour décrire le tirage.

La première étude dont je vais parler est celles de Dessalles (2006). Son modèle pour le calcul de la complexité de description est basé sur la Generative Theory of Shape (voir Leyton (2001)). Dans ce modèle, la reconstruction d’une structure est basée sur le transfert de « groupes fibres » via des « groupes de transfert ». Pour vous donner une idée du mécanisme, voici comment est produite la description du tirage 23-24-25-26-27-28 :

Étape 1 : Tout d’abord il y a un chiffre non instancié
Résultat : *
Étape 2 : Ce chiffre est transféré via une translation
Résultat : * * * * * *
Étape 3 : Le chiffre est dupliqué pour obtenir des nombres à deux chiffres
Résultat : ** ** ** ** ** **
Étape 4 : Le premier chiffre est instancié
Résultat : 2* 2* 2* 2* 2* 2*
Étape 5 : L’opérateur de transfert est dissocié, il devient un opérateur conjoint de transfert et d’incrémentation de 1
Résultat : 2* 2* 2* 2* 2* 2* (cela n’a pas d’effet immédiat)
Étape 6 : Le second chiffre des nombres est instancié (en commençant à 3)
Résulat : 23-24-25-26-27-28

À partir de cette analyse, il est possible de calculer une complexité de description de la séquence 23-24-25-26-27-28 en détaillant le coût en bits de chaque étape. Pour simplifier, les opérateurs de transfert et de duplication seront considérés comme ayant le même coût C_o (en bits). Les étapes 2 et 3 coûtent chacune C_o bits, l’étape 4 coûte C_2 = \log_2(3) bits (note 3), l’étape 5 coûte C_o + C_{+1} = C_o + \log_2(2) bits (note 3) et enfin l’étape 6 coûte C_3 = \log_2(4) bits. Ainsi, le coût total est 3C_o + \log_2(24) bits. Ce mode d’analyse permet de calculer des complexités et de ranger les divers tirages d’une loterie en fonction de leur complexité.

Sur le plan empirique, l’article de Dessalles (2006) contient une étude préliminaire. Cette étude a consisté à proposer à des personnes prises au hasard dans un café de jouer gratuitement au loto. La seule contrainte est de jouer une combinaison parmi 14 combinaisons proposées. Ces 14 combinaisons sont de complexités variables. Cette étude préliminaire révèle que les personnes ne choisissent pas les combinaisons dont la complexité est strictement inférieure à 12 (en utilisant le modèle de calcul ci-dessus). Cette étude tend à confirmer l’idée que les combinaisons les moins complexes sont perçues comme les moins « probables ».

Une seconde étude, celle de Maguire et al. (2013), s’est également intéressé au lien entre la description minimale d’un tirage de loterie et sa probabilité subjective d’occurence. Les auteurs utilisent un autre mécanisme de compression (je rappelle que le calcul de complexité est une compression de l’information). Il s’agit du codage de Huffman. Je ne vais pas détailler ici le calcul car il me semble moins intéressant sur le plan cognitif. En revanche, je vais détailler l’expérience de l’article de Maguire et al. (2013) qui prolonge l’étude préliminaire de l’article de Dessalles (2006).

Dans l’article de Maguire et al. (2013), l’expérience a consisté à présenter aux participants 5 séquences de nombres. L’une d’entre elle correspondait à un vrai ticket de loterie sélectionné aléatoirement (la complexité de la combinaison était de 30 ou 31 bits selon les participants). Les 4 autres séquences était générées aléatoirement en utilisant l’algorithme de compression basé sur le code de Huffman. Ces séquences avaient des complexités comprises entre 15 et 18 bits, 19 et 22 bits, 23 et 26 bits et enfin 27 et 29 bits. Chaque participant devait classer les séquences, de celle qui, selon eux, était le plus probablement le vrai tirage à celle qui l’était le moins probablement. Leurs résultats sont les suivants (copié/collé depuis l’article original) :

Results_Maguire

Ces résultats sont intéressants à deux niveaux. Ils tendent non seulement à confirmer que l’être humain est bien sensible à la complexité de description des tirages mais également que l’être humain réalise effectivement ce calcul de complexité pour déterminer les probabilités subjectives d’occurrence d’une situation.

—————————————-

Ainsi, l’étude des tirages de loterie surprenants illustre l’influence de la complexité d’une situation sur notre réaction face à l’occurrence de ladite situation. Les situations dont la description est anormalement simple sont perçues comme surprenantes. En termes probabilistes, cela consiste à dire qu’une situation anormalement simple à décrire est perçue comme peu probable. Ce genre de modélisation basée sur la notion de compression minimale ouvre la voie à de nombreuses applications. En particulier, cela ouvre la possibilité de calculer l’intensité de la surprise, en tant que réponse émotionnelle, face à des situations anormalement simples. Cependant, comme il s’agit de probabilités subjectives, la simplicité d’un tirage ne dépend pas seulement d’une régularité mathématique que l’on peut détecter. Si le tirage à un sens particulier pour vous (par exemple si ce tirage correspond à votre numéro de téléphone), alors il vous apparaîtra surprenant, mais sera sans intérêt pour votre voisin ou votre boulanger. Le modèle théorique prend en compte ces effets mais pas les modèles calculatoires décrits.

 

Notes :

1. Cette mesure de complexité est cependant non-calculable. Pour couper court à tout débat sur sa calculabilité, considérons dans la suite que le mot de complexité (cognitive) va faire référence à la taille de la plus petite description connue de la structure considérée. Sa non-calculabilité n’empêche pas, sur des cas concrets, de l’approximer.

2. C(s) mesure la taille minimale du programme qui produit s, c’est donc le nombre de bits de ce programme écrit en binaire. La probabilité qu’un bit soit entré dans la machine par hasard est 1/2. Ainsi, la probabilité que ce programme soit produit « par hasard » est (1/2)^{C(s)} = 2^{-C(s)}.

3. La complexité pour instancier un nombre est C_n = \log_2(n+1). C’est l’information minimale nécessaire pour localiser le chiffre en utilisant son rang dans l’ordre usuel. On considère ici que la complexité d’un opérateur d’incrémentation de n est la même que la complexité pour instancier n. Ainsi C_{+n} = C_n

Références principales :
Dessalles, J.-L., 2006, A Structural Model of Intuitive Probability
Maguire, P.; Moser, P.; Maguire, R. & Keane, M., 2013, A computational theory of subjective probability [Featuring a proof that the conjunction effect is not a fallacy]

Références secondaires :
Chater, N., 1999, The Search for Simplicity : A Fundamental Cognitive Principle ?
Li, M. & Vitányi, P., 2008, An Introduction to Kolmogorov Complexity and its Applications
Leyton, Michael, 2001, A Generative Theory of Shape

crédits photo en-tête : Bartosz Senderek (Travail personnel) [CC-BY-SA-2.5 (http://creativecommons.org/licenses/by-sa/2.5)], via Wikimedia Commons

Hello world

print(« Hello world »)

Un premier article inutile pour vous souhaiter la bienvenue sur ce blog.