XD blog

blog page

2014-05


2014-05-24 Graphs and Map / Reduce

Implementing graph algorithm on map/reduce is still a challenge. But maybe because it is a challenge, people keep thinking about it. It is the purpose of GraphX which reduces the processing time for the Page Rank algorithm on a Spark environment. It is not as fast as PowerGraph which is not based on Map/Reduce but it is must faster than Mahout (see paper GraphX: A Resilient Distributed Graph System on Spark). One fact, the language Scala appears more and more. A sign: Mahout recently took the decision to stop implementing machine learning algorithm against Map/Reduce to switch to Spark.

2014-05-22 Données Vélib

En cherchant à récupérer des données Vélib pour d'autres villes que Paris, je suis tombé sur ce site : bikes.oobrien qui recense toutes les stations de vélo de toutes les villes du monde.

J'ai fini par implémenté une classe au module pyensae qui récupère les données pour les villes équipées par la société JC Decaux. Peut-être ajouterais-je d'autres sociétés comme Keolis qui gère Rennes avec vélo STAR. Un exemple de code est disponible ici.

2014-05-21 Droite poreuse

De récents articles évoque le désamour des jeunes les sciences (La recherche ne fait pas rêver les étudiants en sciences, De la "désaffection" pour les études scientifiques). Les études se placent du point de vue statistique ou économique. On manque de chercheurs et de scientifiques.

C'est aussi souvent une matière qu'on présente comme une torture. Les cancres à l'école sont la plupart du temps mauvais maths d'abord. On oublie qu'il faut être aussi créatif en mathématiques que dans les autres matières. Certes on évolue dans un monde fait d'hypothèses et de théorèmes comme un paysage est fait de vallées et de montagnes. Il arrive de remettre en cause des vérités pour découvrir que notre notion de droite était poreuse . Les devinettes mathématiques s'insèrent dans les séries télévisées (Sherlock Holmes, on en trouve dans les magazines à la même page que les mots croisés (Infinimath).

Une démonstration de mathématiques ne devrait être rien d'autre qu'une histoire. Et on découvre qu'il y a plein de manières de la raconter (Raisonnements divins).

2014-05-14 Deux ou trois choses à vérifier avant de rendre un projet informatique

Avant de remettre un programme informatique à un relecteur, il est deux ou trois petites choses qui facilitent le travail de relecture :

Lorsqu'un programme ne marche pas et qu'on a passé beaucoup de temps à chercher l'erreur, quoi de plus naturel que d'envoyer un mail à son professeur : "Monsieur, je ne comprends pas, ça ne marche pas et ça devrait marcher". Une fois sur deux, je réponds qu'il me serait utile d'en savoir un peu plus :

Bien souvent, le message d'erreur que je peux lire après avoir reproduit l'erreur est une bonne indication pour savoir où chercher. Dans le cas contraire, voici ce par quoi je commence en général : Je conçois qu'un bug récalcitrant titille un peu et suscite l'envoi d'un mail simple et concis traduisant un certain état d'agacement : ça ne marche pas et ça devrait marcher ! En pareil cas, j'ai aussi tendance à réagir de la sorte. Toutefois, étant la source de l'erreur, le programmeur est celui qui dispose des informations les plus détaillées. J'essaye de lui demander tout ce qu'il sait avant de me lancer en conjectures.

Un cas concret : un programme est censé minimiser la longueur du chemin passant par tous les noeuds d'un graphe (problème du voyageur de commerce). L'algorithme implémenté était tout-à-fait correct à ceci près que l'arc liant le dernier noeud au premier était oublié dans le calcul de la longueur du chemin (il ne bouclait pas). Je vous laisse imaginer ce que l'algorithme produisait comme solution et pourquoi ce que j'ai vu au fil des itérations m'a incité à aller inspecter le calcul de cette longueur.

2014-05-11 Evolutions Informatiques

J'écoutais l'émission On n'arrête pas l'éco du 10 mai. L'invité évoquait la formation des informaticiens dans différents pays. Je ne me souviens plus exactement en quels termes il s'est exprimé mais il mettait en avant la formation généraliste et mathématique des ingénieurs français qui leur permettrait d'apprendre plus rapidement de nouvelles techniques. Je me suis rendu compte que je m'appuyais implicitement sur ce bagage le jour où on me demanda d'expliquer ce qu'était le machine learning. Mon premier réflexe fut de partir d'un problème simple tel qu'une régression linéaire et son expression mathémtique. Comprendre voulait dire pour moi s'approprier les concepts mathématiques, passer du linéaire au continu, réduire un problème complexe à un ensemble de problèmes simples qu'on sait résoudre. Lorsqu'il s'agit de maitrîser une nouvelle technique, il me semble plus facile de s'approprier l'idée que d'apprendre à se servir des outils qui la mettent en pratique. Un nouveau langage informatique se résume souvent à une nouvelle syntaxe, un bouquin et quelques exercices.

Il est difficile de dire ce que sera le paysage informatique dans cinq ans. Il faut un à deux ans pour imaginer un nouveau concept et plusieurs années pour le faire mûrir. La page Wikipedia List of Programming Language recense un nombre impressionnant de langages informatiques parmi lesquels on trouve le LSE (syntaxe). C'est un langage informatique à syntaxe française avec lequel l'éducation national a tenté de m'apprendre à programmer. Certains langages sont très aboutis et cherchent à simplifier l'usage qu'on peut en avoir dans un contexte d'expérimentation (Social Network Analysis), d'autres comme Erlang ont été conçus dès le départ pour concevoir des programmes robustes dans un environnement de production. Ils sont en anglais.

Depuis l'avènement du Big Data, les langages fonctionnels sont en vogue. Scala, Clojure, F#, ces langages forcent le développeur à écrire différemment de telle sorte que le programme est plus facilement transposable dans un environnement Map Reduce. Un nouveau langage cherche à exprimer une idée encore plus simplement.

2014-05-04 Données financières

Chaque année, je propose des sujets financiers aux étudiants de l'ENSAE et la question qui revient systématique est celle des données. Jusqu'à présent, j'utilisais Yahoo Finance!. L'inconvénient est qu'on ne peut récupérer que les cours daily des actions. Un ami m'a suggéré le site Quandl. Les historiques ne sont parfois pas aussi conséquent mais ce site aggrège différentes sources de données et les rend disponibles selon la même interface depuis de nombreux langages (Python, R, Julia, Clojure...).

L'interface est vraiment épurée, très réactive et très agréable à utiliser. Outre la multitude de séries financières qui est accessible, le site met à disposition des séries économiques comme le PIB pour de nombreux pays ou encore le cours du Bitcoin.

Le site stipule que l'accès est gratuit. Il faut s'authentifier si on dépasse un quota de 50 requêtes par jour. Le business model n'est pas encore bien défini (coming soon) contrairement à leur concurrent Datamarket. Ma préférence va pour Quandl, simple, accessible, gratuit et des objectifs ambitieux. Si une source de données ne fait pas partie du catalogue, il est même possible de leur demander de l'intégrer.

Quelques articles :

2014-05-02 Map / Reduce

I wish sometimes bugs could let me go. I'm working on an map/reduce algorithm. The problem would be smaller I would not hesitate to avoid map/reduce but it is not. Any fast it can be, I find it very slow and impossible to run. So I polish. I wake up in the morning and a detail strikes me up. Shit, shit, shit, I should have written it that way. It works on a small sample but this sample is resistant to many mistakes. I see this algorithm working in my head from the beginning. But I missed this case, as if a train would hide another one and get me killed when I cross. That kind of stuff always happens with big data. Pruning, scaling...

Most of the time, the issue comes from skewed data. Skewness is a way to say that the data is not uniformly distributed. Precisely, when reducing a table or joining two tables, we group data sharing the same key (as we do a GROUP BY or a JOIN on SQL). People research about it: A Study of Skew in MapReduce Applications. But let's see on a example what it means: notebook on Reduce skew data.


Xavier Dupré