(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.

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…

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 langue¹.
• 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.

Stéphane Grumbach (directeur de l’institut des systèmes complexes (IXXI) à l’ENS Lyon) est intervenu sur cette question lors d’une conférence de l’Institut des savoirs du numérique (ISN), jeudi 9 avril 2015.

Services d’intermédiation

On a vu émerger le besoin des utilisateurs de systèmes tels qu’Uber, que j’appellerai services d’intermédiation.
Contrairement aux compagnies de taxi usuelles, où en cas de problème il faut passer par une longue hiérarchie, avec Uber le client est (presque) directement en contact avec le conducteur, il a accès à sa géolocalisation, ça rassure le client.

Start-ups

Les start-ups aujourd’hui n’ont pas peur de construire des services sans se préoccuper de comment ils vont gagner de l’argent : une fois qu’on domine la planète, on peut toujours monétiser.
On compte parfois 100 000 fois plus de clients que d’employés ; 1 000 fois plus de développeurs que d’employés.
Uber a ainsi en très très peu de temps pu obtenir une capitalisation à 40 milliards de dollars.

L’État

L’État est menacé de la même disruption¹ que les sociétés classiques. Ce système de plateformes transforme le monde et les emplois :

• Les plateformes ne connaissent pas les frontières (en Europe ; certains pays ont certes des frontières numériques). La plateforme Uber est interdite sur beaucoup de territoires sur lesquels elle opère.
• Les plateformes adressent la population du pays ; Facebook est utilisé par 50 % de la population française (NDLR : ce chiffre est faux ; en fait, 63 %, mais seulement pour un échantillon de 2004 personnes qui sont des internautes, étude IFOP, Observatoire des réseaux sociaux 2013), ça veut dire qu’il est plébiscité ; les gens « votent » pour Facebook.

Je pense que bientôt, les algorithmes s’ajouteront aux lois pour encadrer notre conduite, nous devrons donc connaître et respecter non seulement les lois, mais aussi également les algorithmes. Les systèmes d’assurance se référeront à l’algorithme.

Pour citer un exemple, les autorités européennes ne disposent pas des capacités pour gérer la mise en œuvre du droit à l’oubli numérique, donc un citoyen européen voulant exercer son droit à l’oubli doit directement faire sa demande auprès du comité consultatif de Google, qui décidera d’accepter ou de rejeter la requête. J’ai peu de doutes que la santé sera également régie par une plateforme américaine ; elle sera utilisée, puis adoptée. Idem pour les visas, idem pour la fiscalité. Les consommateurs préféreront utiliser un service qui leur facilite la vie. Tout ceci constitue autant de changements dans la sphère étatique.

L’État a une capacité budgétaire très limitée, on le sait et ce sera le cas encore longtemps, tandis que les plateformes ont une capacité budgétaire illimitée. Les plateformes ont une capacité intellectuelle très supérieure à l’État puisqu’ils recrutent dans le monde entier des profils très divers.

L’Europe

Je pense que l’Europe comprend assez mal le numérique. Elle croyait par exemple que la Chine avait utilisé Internet uniquement pour exercer la censure sur les Chinois. Ça me semble peu respectueux pour le public chinois, surtout que cette censure s’exerce aussi hors de Chine. Je pense qu’en fait elle se pose les mauvaises questions.

… En complément de l’intervention de Stéphane Grumbach ci-dessus, je vous propose cette critique du fonctionnement des services d’intermédiation, sur frenchtech.co.

Aujourd’hui, nous avons eu le plaisir d’intervenir sur le plateau de La Tête au carré sur France Inter, pour parler de big data prédictif. Réécouter le podcast.

Qui sommes-nous ?

• David Bessis (@davidbessis), fondateur de tinyclues, une entreprise de marketing prédictif ;
• Gaël Varoquaux (@gaelvaroquaux), chercheur en apprentissage à l’Inria Saclay et l’un des responsables du projet scikit-learn, une bibliothèque géniale de machine learning en Python dont la documentation est claire et truffée d’exemples ;
• et moi (@jjvie), doctorant en 2e année à l’université Paris-Saclay sur les tests adaptatifs.

Trois points sur lesquels nous aimerions insister

• Le big data est partout (pour de vrai ; votre portable qui enregistre votre déplacement¹, votre passe Navigo qui enregistre vos déplacements², la reconnaissance vocale, les codes anti-robots que vous remplissez qui améliorent les outils de reconnaissance de caractères). Autre exemple : EDF optimise l’alimentation d’énergie en prédisant la consommation des foyers.

• Le big data vous rend service, par exemple lorsqu’on recherche un appartement sur Internet, on est bien content d’avoir des suggestions sur le côté en accord avec notre budget ; et lorsqu’on ne sait pas quoi voir dans l’immense masse de films, on est bien content d’avoir des recommandations.

• David, Gaël et moi sommes d’accord dans l’ensemble³. Il est important d’analyser les données pour faire émerger de l’intelligence, il est important de protéger les utilisateurs en les informant de leur utilisation.

Quelques ressources supplémentaires

• Une excellente lecture sur les méfaits du solutionnisme (penser qu’avec des algorithmes on peut sauver le monde ; je suis moi-même atteint) : Pour tout résoudre, cliquez ici⁴ d’Evgeny Morozov.

• Ils ont épluché les conditions d’utilisation pour vous et évaluent les services qui recueillent des données : Terms of Service; Didn’t Read (on peut y apprendre par exemple que sur YouTube, les vidéos supprimées ne sont pas vraiment supprimées et ce site m’a permis de découvrir DuckDuckGo, un moteur de recherche sans pistage).

• L’expérience menée par Facebook sur 689003 utilisateurs-cobayes en juin dernier. Certes, ils ont manipulé votre fil d’actualités pour savoir si des messages heureux ou malheureux pouvaient influer sur votre humeur, mais c’est ce qu’ils font en permanence (je veux dire, le fil d’actualités est toujours gouverné par un algorithme, l’expérience ne changeait rien). Avant, les conditions d’utilisation stipulaient que les utilisateurs consentaient à ce que leurs données fassent l’objet d’analyses, elles sont maintenant plus précises :

Nous menons des enquêtes et des études, testons des fonctionnalités en phase de développement et analysons les informations à notre disposition afin d’évaluer et améliorer nos produits et services, de mettre au point de nouveaux produits et de nouvelles fonctionnalités et de conduire des activités de vérification et de dépannage.

• Non, Facebook n’est pas propriétaire de vos données personnelles.

Pour toute question, n’hésitez pas à me contacter sur Twitter ou par mail : vie@jill-jenn.net