Un escargot à Manhattan

Deep Learning au Collège de France

Ou pourquoi vous auriez dû être au Collège de France jeudi 4/2 au soir. Par David Lambert et JJ Vie.

Update 13/02. Rassurez-vous, la vidéo est déjà disponible sur le site du Collège de France !

Update 18/04. Google a fait une super page pour introduire à leur outil de deep learning, TensorFlow ! http://playground.tensorflow.org

Préambule

NLDR/TLDR. Le deep learning est une méthode d’apprentissage automatique. Vous en avez peut-être déjà entendu parler sous le nom de réseaux de neurones artificiels. En fait, les modèles existent depuis les années 80, mais ont réellement explosé en 2012, voir plus bas. Yann LeCun est un des pionniers de ce domaine, notamment pour avoir créé les réseaux convolutionnels (ConvNets), décrits plus bas.

S’inspirer du cerveau est-il légitime ?

En extrapolant à partir de l’état actuel de l’électronique, on peut supposer que les processeurs seront aussi performants qu’un cerveau humain en 2045 (si la loi de Moore ne se heurte pas entre-temps aux limites de la miniaturisation).

Mais en recherche, la vraie question n’est pas simplement d’égaler sa puissance de calcul, mais de comprendre comment marche le cerveau. Il s’agit de saisir l’essence de son fonctionnement, plutôt que de chercher à le reproduire dans ses moindres détails. Les avions n’ont pas de plumes, et n’en ont pas besoin ; l’avion III de Clément Ader, trop proche physiquement de la chauve-souris, n’était pas une franche réussite.

Trois types d’apprentissage automatique

Apprentissage par renforcement

Méthode façon « la carotte et le bâton » ; on pénalise l’algorithme s’il aboutit à une mauvaise solution, on le récompense s’il fait les bons choix.

C’est un processus lent, mais dans les jeux vidéo, c’est relativement facile, car on peut simuler des parties très vite (NDLR, cf. les travaux de Deep Mind sur les jeux Atari en février 2015 ou bien AlphaGo bat un champion européen le 27 janvier 2016, publié dans Nature).

Apprentissage supervisé

On imagine ici qu’on a accès à des étiquettes sur les données qu’on considère (« ceci est une voiture », « ceci est une blonde aux yeux bleus »).

La classification d’objets est donc un bon exemple. Dans tout ce qui suit, on va parler d’apprentissage supervisé, domaine de la recherche en perception artificielle, sous-domaine de la recherche en intelligence artificielle.

Apprentissage non supervisé

NDLR. Là, on suppose qu’on n’a pas accès à des étiquettes. Ainsi, les approches usuelles consistent à regrouper les données en clusters, ou tenter de visualiser les données selon certains angles (analyse en composantes principales). Par exemple, en recommandation de films, on essaie de rapprocher des utilisateurs d’autres en fonction de ce qu’ils ont aimé, pour essayer de visualiser certains profils-types.

Pour en savoir plus, l’excellent tutoriel scikit-learn (en anglais) : An introduction to machine learning with scikit-learn.

Le perceptron (1957)

Principe : on cherche à distinguer deux catégories d’images, par exemple distinguer les A des B, en les soumettant à la machine. Chaque image est composée de pixels noirs ou blancs (1 ou 0) et on souhaite qu’à la sortie on ait :

  • une valeur positive si l’image est un A ;
  • une valeur négative si l’image est un B.

En fait, chaque pixel participe à la valeur de sortie de la machine selon un certain poids, et la somme pondérée de toutes les entrées donne une valeur globale qui indique si la machine « pense » que l’image est un A ou un B. Si la machine s’est trompée, les poids sont corrigés (on pénalise les poids des pixels qui l’ont induite en erreur) ; la machine apprend ainsi par tatônnements (trial and error), on appelle cela la phase d’entraînement. On itère le processus jusqu’à ce que la fonction d’erreur du système soit convenable.

Les poids relatifs des sorties de chaque cellule sont modifiés comme seraient modifiées les connexions entre neurones dans le cerveau, en fonction de la conformité du résultat.

Un perceptron efficace possèdera la propriété de généralisation : identifier correctement une image qu’il n’a alors jamais vue !

NDLR. Si la reconnaissance de chiffres vous intéresse, voici un code Python tiré d’un tutoriel de scikit-learn par Gaël Varoquaux (qui utilise une SVM plutôt qu’un perceptron).

Deep learning

L’idée du deep learning, c’est de brancher des perceptrons entre eux, regroupés en couches, de façon hiérarchique. Et d’entraîner toutes les couches en même temps.

Chaque couche est responsable d’un certain niveau d’abstraction :

  • un module de niveau 1 détecte l’état d’un pixel (noir ou blanc, présence ou absence) ;
  • un module de niveau 2 s’occupe des conjonctions de pixel et détecte ainsi les contours ;
  • un module de niveau 3 détecte les motifs dans les contours, et ainsi de suite.

Tout ça, ça marche parce que le monde est compositionnel – je ne sais pas si c’est un mot français mais je l’utilise. Un ami dit plutôt, de manière amusante : « Soit le monde est compositionnel, soit Dieu existe. »

Cette hiérarchie des caractéristiques (pixel, contour, motif de contours) on la retrouve dans d’autres objets d’étude des réseaux de neurones, comme les langues par exemple (caractère → phonème → syllabe → mot → phrase → livre).

Réseaux convolutionnels

Je les appelle ConvNets pour éviter qu’on les appelle CNN (convolutional neural networks)…

Lecture automatique de chèques (1996)

Yann LeCun a développé un modèle sur le même principe, qui permet entre autres de :

  • reconnaître un chiffre à n’importe quel endroit de l’image (invariant par translation, NDLR) ;
  • faire le tri entre motif et fond de l’image.

Première application : une machine de lecture automatique de chèques (Bell Labs), déployée aux États-Unis en 1996. 20 % de tous les chèques américains sont passés par cette machine, qui rejetait 50 % du tas mais ne faisait qu’1 % d’erreur, ce qui est convenable en pratique.

Le dataset ImageNet (2012)

Mais dans la communauté scientifique, personne ne s’est intéressé aux réseaux convolutionnels avant 2012, lorsque le dataset ImageNet (1,2 millions d’images, classées dans un millier de catégories) est sorti. Là, en 18 mois, il y a eu un revirement mondial, qui a eu pour conséquence la « redécouverte » de certains concepts par des nouveaux venus, ce qui brouille la visibilité des travaux des équipes précédentes :

Détection de piétons ou d’obstacles (scene parsing / labeling)

Les ConvNets ont été appliqués à l’interprétation d’image par étiquetage de chaque pixel en fonction de la partie de l’image à laquelle il appartient (façade, chaussée, passant, voiture). Chaque sortie tient compte du contexte du pixel d’entrée (NDLR, par analogie avec un puzzle, la machine a la possibilité de distinguer le bleu du ciel et le bleu du reflet du ciel dans le lac si elle détecte une rive).

Cela a fait progresser les travaux en vision robotique à longue distance, cf. cette vidéo (DARPA LAGR/NYU/NetSCALE, 2005-2008), voir à 4:08 :

La première fois que mon étudiant s’est jeté devant le robot, j’ai failli avoir une attaque. Il faut vraiment avoir confiance en son code pour se jeter devant un robot de 120 kilos qui peut vous casser la jambe s’il ne s’arrête pas à temps. D’ailleurs maintenant quand des étudiants veulent travailler avec moi, d’abord je leur fais écrire un peu de code du robot, je les fais sauter devant ; s’ils survivent, je les prends.

Reconnaissance vocale

Avant, les ConvNets étaient principalement utilisés pour la reconnaissance d’images, mais ça s’est propagé à d’autres domaines de l’intelligence artificielle.

Le service de reconnaissance vocale OK Google utilise des ConvNets. Des travaux récents sur les ConvNets polyglottes, entraînés à la reconnaissance vocale dans plusieurs langues, montrent que ceux-ci sont ensuite plus performants dans chacune des langues individuelles (NDLR, ça fait penser au fait que certains conseillent d’apprendre l’espéranto pour apprendre plus vite les autres langages ; il y a des études, mais je ne sais plus où elles sont).

Légendes automatiques

À partir d’une photo, un algorithme peut en décrire le contenu.

On développe [ces systèmes] chez Facebook, en particulier pour aider les malvoyants à avoir une idée de ce qui se passe dans leur flux d’informations.

À noter que la fonctionnalité de reconnaissance des visages de Facebook est désactivée en Europe.

Modèles génératifs

On peut aussi prendre le réseau à l’envers et de demander à afficher quelque chose d’inédit à partir de nombres aléatoires. Par exemple :

  • certains génèrent des phrases ;
  • d’autres des photos de chambres ;
  • d’autres des personnages de mangas !

Jetez un œil au repo GitHub associé : Unsupervised Representation Learning with Deep Convolutional Generative Adversarial Networks.

Memory Networks

La plupart des modèles ont un peu une mémoire de poisson rouge (NDLR). Ils fonctionneraient mieux s’ils avaient l’équivalent de l’hippocampe pour le cerveau (NDLR, ou de la RAM pour les ordis), une mémoire partagée. C’est ainsi qu’on a créé le paradigme des Memory Networks.

Ainsi, on pourrait attendre d’un algorithme qu’il soit capable de répondre à la question : « Brian est dans la cuisine. Brian prend du lait. Brian va dans la salle de bains. Où est le lait ? »

(NDLR : je vous laisse imaginer ce qu’un tel outil est capable de faire si on lui donne accès aux données de Facebook.)

Traitement des langages naturels (par ex., word2vec)

Effet secondaire de l’entraînement du système : celui-ci fait spontanément émerger des structures à partir des données qu’il a ingurgitées.

Du coup, on peut demander à la machine : « Qu’est-ce qui est à l’Allemagne ce que Paris est à la France ? » et elle est capable de répondre « Berlin ».

Autant faire la même chose avec des photos de visages : on peut demander à l’ordinateur de générer une photo de femme avec des lunettes en effectuant l’opération : « homme avec lunettes – homme sans lunettes + femme sans lunettes ».

Conclusion

Que ne sait-on pas faire ?

Les quatre chaînons manquants de l’intelligence artificielle :

  • une compréhension théorique de l’apprentissage profond : ça marche, mais on ne sait pas pourquoi ça marche aussi bien ;
  • une intégration de ces méthodes d’analyse des représentations (apprentissage profond) aux quatre autres composantes de l’intelligence, qui seraient le raisonnement, l’attention, la planification et la mémoire ;
  • une théorie unifiée de l’apprentissage : un système qui déploierait à la fois des capacités d’apprentissage par renforcement, d’apprentissage supervisé et d’apprentissage non supervisé ;
  • une modélisation efficace de l’apprentissage non supervisé.

Métaphore du gâteau

Actuellement, sur les trois formes d’apprentissage chez les humains :

  • Apprentissage par renforcement : c’est la cerise, c’est facile, on sait faire.
  • Apprentissage supervisé : le glaçage (NDLR, pour lequel le deep learning s’est révélé très efficace).
  • Apprentissage non supervisé : 90 % restants du gâteau, qu’on ne sait pas faire de façon satisfaisante.

L’apprentissage non supervisé pourrait être effectué par un algorithme prédictif dont les résultats seraient pondérés en fonction de la conformité des prévisions avec ce qui s’est produit. C’est l’apprentissage via un modèle prédictif du monde qui nous enseigne le bon sens : quand on lit la phrase « Gérard prend son sac et quitte la pièce », on en déduit que Gérard prend son sac avec sa main, qu’il quitte la pièce par la porte et pas par la fenêtre, ni en volant ni en se téléportant, etc. Pourquoi ? Parce qu’on a appris tout cela au préalable, en observant le monde.

Certains font de la prédiction de frame de film, mais cela ne fonctionne pas très bien, ne serait-ce que parce qu’on ne connaît pas l’état du monde, seulement ce qui est observé à l’écran (NDLR, un T-Rex qui apparaîtrait soudainement dans Jurassic Park).

Et la domination des machines sur l’homme, alors ?

La différence entre l’intelligence humaine et l’intelligence machine est que nous sommes soumis à un ensemble d’instincts, dont la programmation est le résultat du processus d’évolution dont nous sommes le fruit, et que ce sont ces instincts (territorialité, jalousie, …) qui nous font faire n’importe quoi.

Il n’y a aucune raison de construire ces pulsions de base dans les robots : on peut construire des robots qui ne sont pas dangereux.

(NDLR, les algorithmes reflètent déjà aujourd’hui les biais de leurs concepteurs.)

Quelques liens

Le Garçon et la Bête

À gauche, l’affiche originale. À droite, la version française. Je ne ferai pas plus de commentaire.

Sortie le 13 janvier 2016, avant-première le 24 novembre 2015 ! Au Gaumont Opéra Premier, en ouverture de la 10e édition du festival Kinotayo à Paris. (Et à Londres les 16-17 octobre.)

Mamoru Hosoda, le réalisateur du succès Les Enfants loups, Ame et Yuki dont je parlais dans un précédent post a mis la barre encore plus haut avec son dernier film, Le Garçon et la Bête (Boy and the Beast, Bakemono no ko バケモノの子).
Ça raconte l’histoire d’un jeune solitaire qui erre dans le quartier de Shibuya et « tombe » dans le monde des monstres. Il y rencontre le maître de sabre Kumatetsu, qui en fait son disciple et lui donne le nom de Kyūta.

À Japan Expo 2015, les premières images en ont été présentées, laissant penser à un clin d’œil à tous ses précédents films (un nuage1, une musique envoûtante2, une confrontation3, une bête4). Encore une fois, Mamoru a choisi le thème de la famille, qui lui est cher. À noter que contrairement à ses trois films précédents, le personnage principal n’est ici pas féminin.

Au Japon, le film entame au 2 octobre 2015 sa 13e semaine, avec 5 milliards de yens au box-office pour 4 millions d’entrées ! Mamoru Hosoda avait dit (à l’avant-première de Summer Wars en février 2010) qu’au Japon, avoir un succès donnait un ticket pour faire le film suivant. Comme il l’annonce dans une interview émouvante sur ses débuts :

Mamoru Hosoda avoue aussi que l’attente du public japonais n’a jamais été aussi forte pour l’un de ses films, surtout depuis l’annonce de la retraite à la réalisation de longs-métrages d’un certain Hayao Miyazaki…

… On parle quand même de celui qui a failli réaliser Le Château ambulant !

La bande-annonce de Le Garçon et la Bête :

(D’ici l’avant-première le 24 novembre, vous avez le temps de vous faire plaisir avec Avril et le monde truqué qui sort le 4 novembre prochain ! C’est le film français qui a remporté le Cristal du long métrage à Annecy en juin dernier, et c’est vraiment une pépite.)

Et en attendant que j’adapte la BO, voici le thème de Summer Wars !

  1. TOUS, notamment La Traversée du temps 

  2. Summer Wars et Les Enfants loups 

  3. Digimon et Summer Wars 

  4. Les Enfants loups 

Relaxations pendant les vacances

(Ne vous méprenez pas, par « relaxation » j’entends la définition au sens de la théorie des graphes.)

Je me pose le problème suivant : si j’essaie d’aller d’une ville A à une ville B, existe-t-il une ville X par laquelle il serait intéressant de passer pour casser le prix ? (Car, au risque de vous surprendre, les tarifs des vols ne respectent pas l’inégalité triangulaire.)

Update 29/08. Ryan Lahfa m’a fait découvrir le site allemand Tripdelta qui accomplit cette tâche merveilleusement ! Mais ce n’est pas une raison pour ne pas coder quelque chose nous-mêmes !

Update 30/08. Tripdelta c’est une équipe basée à Cologne, 2 développeurs + 1 business dev. Ça fait 4 mois qu’ils existent, ils ont le calendrier des prix et la carte des prix sur la to-do list. Actuellement ils utilisent l’API Skyscanner (comme Kenweego et sûrement la majorité des sites du genre). Je vais leur proposer des missions :-)

Par exemple, le 9 septembre 2015 :

46 + 32 = 78 € au lieu de 138 €, ça les vaut ! Certes, c’est plus long. Mais même un vol de Paris à Édimbourg s’arrêtant 3 h 45 à Manchester coûte 115 € (Air France puis FlyBE).

Google Flights

Ça faisait un bail que je voulais coder un script qui pour un budget donné indique les destinations possibles : on ne dit pas où on veut aller, seulement combien on est prêt à mettre.

En fait, Google Flights fait déjà ça.

Carte des prix

Visiblement, ça ne coûtait pas cher de voyager en Europe le 19 août 2015.

Calendrier des prix

Il indique aussi selon le jour où on part quel est le meilleur prix. C’est plus puissant que le « ± 3 jours » que l’on voit habituellement sur les sites de comparateurs de vol.

Tiens, ça ne coûte que 32 $ d’aller de Marseille à Édimbourg le 12 octobre !

API

Il n’en existe pas (encore) d’API, mais on peut interroger le serveur RPC avec des requêtes POST. Par exemple :

$ gnutls-cli google.com

POST /flights/rpc HTTP/1.1
Host: www.google.com
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
Content-Type: application/json; charset=utf-8
X-GWT-Permutation: XXX
Content-Length: 304
Connection: keep-alive
Pragma: no-cache
Cache-Control: no-cache

[,[[,"fs","[,[,[[,[\"CDG\",\"ORY\",\"BVA\",\"XPG\"],,\"2015-09-14\"]],,,,,,,1,,,,,,,,,1,[[,3,1]]],[]]","1518231496671724",9]],[,[[,"b_al","no:64"],[,"b_ahr","no:s"],[,"b_ca","52:67383"],[,"f_ut","search;f=CDG,ORY,BVA,XPG;d=2015-09-14;r=2015-09-18;tt=o;mc=e"],[,"b_am","fs"],[,"b_qu","0"],[,"b_qc","1"]]]]

Réponse :

[,[[,"fs","[,[[,\"CDG\",\"Paris-Charles De Gaulle\",\"Paris\",\"PAR\",\"France\",49.0097222,2.54777778,,\"FR\"],[,\"ORY\",\"Paris Orly\",\"Paris\",\"PAR\",\"France\",48.7233333,2.37944444,,\"FR\"],[,\"BVA\",\"Paris Beauvais-Tille\",\"Paris\",\"PAR\",\"France\",49.4544444,2.11277778,,\"FR\"],[,\"XPG\",\"Paris Gare du Nord Railway Station\",\"Paris\",\"PAR\",\"France\",48.8808333,2.35527778,,\"FR\"]],,[[,\"PAR\",\"Paris\",48.856614,2.3522219000000004,[\"CDG\",\"ORY\",\"BVA\",\"XCR\",\"XPG\",\"LBG\",\"POX\",\"VIY\"],[\"CDG\",\"ORY\",\"BVA\",\"XPG\"],\"France\",,\"FR\"]],,\"\",,,,,[[,6,,0]],,,,,,,,,,0]",,1]],[,[[,"b_sshk","wl_467279cc"],[,"b_ssfgip","hIymy7tx8nKn7sfxANtGtg"]]]]

Trop aimable. En gros, je lui ai envoyé quelque chose contenant « CDG », il m’a envoyé quelque chose contenant « Paris-Charles De Gaulle ». On va dire que c’est un début.

Un type a rédigé un post de blog où il essaie de comprendre comment fonctionne l’API.

Si ça vous dit de m’aider à construire ce petit script, votre aide est la bienvenue. Je suis tellement persuadé qu’on serait capables de trouver des vols Paris → X → Marseille moins chers que les tarifs de la SNCF !

Sites similaires

  • Liligo a une carte des prix, très discrète (merci Alexis Descamps).
  • Kenweego aussi, c’est fait par un Français.
  • Momondo c’est danois, ils ont une API (merci Luc Rocher).

Et sinon un peu de méta, vous voulez voir quelle gueule a le code de ce post de blog ? Merci Octopress.

Paul Duan, non-profit data scientist

J’aimerais vous parler de Paul Duan.

Apparemment le gars a un visa O-1A, attribué aux personnes relevant d’une compétence extraordinaire en sciences, éducation, business ou sport. En savoir plus sur le délire des visas auxquels il a postulé.

Il a remporté un challenge Kaggle lancé par Amazon, puis lancé une ONG où il utilise le machine learning pour sauver le monde.

Comme dit sur techmeup.co :

Au début, Bayes Impact, c’était juste une petite page web avec l’idée de ce qu’on voulait faire, pendant que j’étais encore chez Eventbrite. Trois semaines plus tard, YCombinator nous a appelé sans qu’on s’y attende, parce qu’ils cherchaient à inclure une non-profit pour la prochaine promo, qui commençait dans 3 jours !! J’ai pris mon après-midi, j’ai tout préparé, et… on a été pris ! J’ai quitté Eventbrite du jour au lendemain, c’était pas très cool pour eux, d’ailleurs… Mon pote a quitté son job aussi. Ça fait 6 mois, et maintenant, on est 15, on a des projets plutôt cools, et on recrute que des gens avec des backgrounds solides en data science, qui viennent de chez Google, Facebook…

Pour citer un autre extrait :

L’ambition, c’est d’être une ONG qui conseille les gouvernements pour les aider à optimiser leurs problèmes critiques avec des algorithmes (allocation d’organes, optimisation de la distribution d’ambulances, …) ; un peu comme la World Bank conseille les gouvernements sur des sujets financiers. Il y a d’autres gens qui font de la data science non-profit, mais souvent sur des petits projets ; nous, on veut directement conseiller les gouvernements. C’est pour ça qu’on ne recrute que des gens solides ; on veut résoudre les problèmes depuis en haut.

D’autres pistes de résolution dans une interview par healthdatachallenges.com.

Et ils recrutent. Mhhh…

Duolingo

Update 29/06. Leur article, Mixture Modeling of Individual Learning Curves a remporté le Best Paper Award de la conférence !

La keynote de bienvenue à la conférence Educational Data Mining 2015 (26 juin, Madrid) a été donnée par Luis von Ahn, créateur de reCAPTCHA, ESP game et co-fondateur de Duolingo et Matt Streeter.

C’était impressionnant. Luis a parlé 20 minutes, Matt a parlé 20 minutes, puis les questions ont fusé pendant les 50 dernières minutes.

Historique et méthodes, par Luis von Ahn

Quelques chiffres

  • Aujourd’hui, 1,2 milliards de personnes apprennent une deuxième langue1.
  • Duolingo vient de fêter (en 2015) ses 3 ans.
  • Ils ont 15 millions d’utilisateurs actifs.

Quelques citations

In the past two days I’ve learned more from Duolingo than in four years of high school in Spanish.

Et puis…

This is probably the single greatest thing currently on the Internet.

Après avoir montré cette citation, Luis a dit : « That’s from my mother. » Effet assuré.

Démarche et principe

Au départ, ils voulaient travailler avec les écoles pour définir leur programme scolaire. Mais la 1re école voulait qu’ils fassent exactement comme elle le leur disait ; une autre école voulait également qu’ils fassent exactement comme ils le voulaient (mais différemment, évidemment), puis quand les écoles allaient les voir ils répondaient « Sorry, we don’t talk to schools » et aujourd’hui, ce sont les écoles qui adaptent leur programme scolaire en fonction de Duolingo.

Le principe est simple : le langage est découpé en un arbre de compétences, les gens doivent remplir une jauge (dorée une fois remplie) pour chaque nœud qui leur permet de débloquer de nouveaux mondes.

Chaque leçon représente 20 exercices, et ils ont une sorte de barre de progression intelligente qui augmente et diminue d’un certain montant selon la difficulté de l’exercice en cours.

Ils estiment que 34 heures de Duolingo équivaut à un semestre d’école de langues. Ils souhaitent être aussi bons qu’un vrai cours.

Culture de l’addiction

La jauge d’un monde diminue lorsqu’on ne s’est pas connecté depuis longtemps (c’est leur manière de modéliser l’oubli). Les gens reviennent sur le système parce qu’ils souhaitent garder des jauges dorées sur leurs mondes.

Ils ont même testé d’envoyer des mascottes en larmes par mail pour dire « Ça fait longtemps qu’on ne vous a pas vu » et ils testaient via A/B testing la mascotte qui faisait le plus culpabiliser.

En fait, ils ont tellement d’utilisateurs qu’ils peuvent A/B tester n’importe quoi (par exemple, est-ce qu’il vaut mieux faire Food ou Plurals en premier dans l’arbre de compétences ?) : ça ne leur prend que 6 heures pour avoir 50 000 nouveaux inscrits.

Aspects plus techniques, par Matt Streeter

Comme fonctionnalités, ils ont la détection de faute de frappe. Ils sont très contents de leur modèle d’apprentissage pour la barre de progression.

Vérification de réponse

Le problème principal qu’ils se posent : étant donné une phrase donnée A et une phrase tapée B, comment déterminer si B est une traduction correcte de A ? C’est d’autant plus compliqué que par exemple, en japonais il y a plus de 200 000 manières de dire « Je t’aime » (le registre de langue pour chacun des sujets, la capacité à ajouter des superlatifs, etc.). Et les faux négatifs énervent les utilisateurs.

Le souci, c’est que la traduction à base de règles est difficile à mettre en place et la traduction purement statistique n’est pas assez précise. Leur solution : beaucoup d’entrées manuelles, plus quelques règles générales.

En fait, leur idée géniale (que j’imagine hyper classique mais qui était très bien expliquée) : construire un automate (étiqueté par des mots) qui va reconnaître plusieurs réponses correctes (en cas de contraction, de nombre écrit en chiffres, d’orthographe alternative color-colour), et reconnaître des erreurs fréquentes (mot manquant : ε-transition empruntée, mot manquant, accent manquant, grammaire incorrecte).

Détection de faute de frappe

Pour ce problème, ils ont également un automate étiqueté par des lettres. Un algorithme de programmation dynamique (que je devine similaire au calcul de la distance de Levenshtein) permet de déterminer un chemin passant par au plus une erreur.

Barre de progression

Leurs objectifs :

  • La barre de progression doit être mise à jour de manière intuitive.
  • La leçon ne doit pas se terminer tant que l’utilisateur n’a pas appris tous les mots de la leçon.
  • L’utilisateur ne doit pas être découragé par ses erreurs.

Leur but est de modéliser la probabilité que l’utilisateur connaisse tous les mots traités dans la leçon. Ils ont un modèle qui est un mélange de Bernoulli (expliqué dans le papier Mixture Modeling of Individual Learning Curves) : c’est une généralisation du modèle de Bayesian Knowledge Tracing qui est une chaîne de Markov cachée modélisant la variable (« L’utilisateur connaît-il le mot X ? »).

Leur business model

À la fin d’une leçon ils proposent parfois : « Si vous souhaitez mettre en pratique votre apprentissage, vous pouvez nous aider à traduire ce document. » CNN leur envoie des news à traduire et les paie pour ça.

Une perle :

En fait, notre business model est simple. On a un financement par capital-risque, puis on attend et ça grossit tout seul.

Ils souhaitent valoriser leur certification, qui est leur autre source de revenus. Harvard commence tout juste à l’accepter.

  1. J’ai galéré à trouver, mais ça vient de Play at Work: How Games Inspire Breakthrough Thinking de Adam L. Penenberg.