Random Thoughts

L'évaluation des systèmes complexes est depuis toujours une partie centrale de l'activité des développeurs travaillant dessus. Le sujet est extrêmement vaste ; regardez la page Software testing de la Wikipédia anglaise pour vous en rendre compte. Ce n'est pas non plus pour rien que Google recrute des Software Engineers in Test.

Quand le système est complexe mais spécifiable, il « suffit » de lister les différents cas possibles et de vérifier que le système a le bon comportement. Cela ne fonctionne pas pour les projets les plus intéressants ; les projets pour lesquels on ne sait pas quelle est la bonne réponse.

• Comment évaluer un système de reconnaissance de caractères ?
• Comment est-ce qu'un moteur de recherche peut dire que sa recherche fonctionne et s'assurer qu'il n'a pas oublié le document qui aurait répondu à la question de l'utilisateur ?
• Comment est-ce qu'on peut dire si une modification sur une IA de Go a amélioré l'efficacité du système ?
• Comment évaluer un système complexe formé comme une « pipeline » de sous-modules ?
• Comment évaluer un système de désambiguïsation du sens des mots ?

Le cas de l'apprentissage supervisé

La première question est la plus facile parce qu'un humain peut répondre à la question. Que pensez-vous faire quand vous utilisez reCAPTCHA pour compléter un formulaire ? Vous participez de manière active à l'amélioration d'un système de reconnaissance de texte qui utilise ces données (l'image et le texte correspondant) pour entraîner les algorithmes de classification. Pour savoir si le système est efficace, il faut prendre des images annotées par des utilisateurs, et vérifier que le système obtient le même résultat.

On obtient alors un unique nombre réel qui est facile à utiliser : si ce nombre augmente lors de la prochaine version du logiciel, on a certainement amélioré la situation, sinon il faut revoir sa copie.

Précision et rappel

Pour la deuxième question, la réponse est qu'on peut évaluer la précision, mais pas le rappel. C'est-à-dire qu'on peut savoir quelle proportion des documents retournés sont pertinents, mais pas savoir combien de documents on a raté (surtout quand il y a autant de documents que de pages webs). C'est bien sûr plus complexe que ça ; il y a différents degrés de pertinence, et on peut vouloir adapter la réponse à l'utilisateur. Un autre problème : les requêtes sont exprimées en langage naturel, et sont donc naturellement ambigües. Quand je fais une recherche sur « l'école de voile du port », Google me renvoie des résultats sur le port du voile à l'école.

Comparaison relative

La réponse à la troisième question est simple : on ne peut pas évaluer la performance d'une IA sans adversaire, il faut donc lui en donner, et regardant comment est-ce que notre IA se classe parmi ces adversaires, que ce soit d'autres IAs ou des joueurs humains. On utilise aussi souvent des « baselines » qui sont des systèmes représentant une « stratégie simple voire bête » que les IAs doivent savoir contrer. En chifoumi, c'est le « tout aléatoire ». Pour d'autres jeux, ça pourrait être « attaque frontale ». En Traitement Automatique des Langues et à Prologin, on est souvent surpris de l'efficacité des stratégies les plus simples.

Sous modules

Quatrième question. Les systèmes de traitement linguistique sont souvent des chaînes, qui réalisent les étapes les unes à la suite des autres. On peut commencer par découper un texte en phrase, puis les phrases en mots, puis de chercher les mots dans un dictionnaire, avant de déterminer quelle est la nature de chaque mot (porte est-il un adjectif ou un adverbe ?) pour ensuite déterminer la structure syntaxique de la phrase avant de déterminer le sens de cette même phrase.

Tous ces modules peuvent être évalués indépendamment, ce qui simplifie beaucoup la tâche. Quand c'est supervisé, on sait faire, quand ça ne l'est pas, on avise (pour la tâche de la désambiguïsation du sens des mots, voir la question suivante).

Note : une fois que ces modules sont évalués, il existe un moyen efficace de savoir sur quel module travailler. On fait la supposition qu'on pourrait choisir un des modules et de le rendre parfait (100% de bons résultats). Lequel des modules faudrait-il alors choisir ? Il faut regarder l'impact sur la précision finale. Si nous avons quatre modules, quelle est l'amélioration finale en remplaçant le premier module par un résultat parfait ? Et si on remplaçait le second ? Le troisième ? Le quatrième et dernier ? Celui pour lequel le gain est le plus important représente le module à améliorer : il a plus de potentiel que tous les autres pour améliorer le système entier. Ce n'est pas nécessairement le modèle le moins effiace dans l'absolu !

Technique du bananaphone

L'évaluation est aussi centrale en « Word Sense Disambiguation », tâche qui consiste à choisir le sens le plus probable parmi tous les sens d'un mot. Une technique consiste à considérer toutes les occurrences de deux mots, par exemple de banana et phone, puis de les concaténer. Exemple de transformation :

I talked about my banana over the phone.

devient

I talked about my bananaphone over the bananaphone.

On donne la deuxième phrase à notre système, et on examine quel sens a été choisi à chaque double mot. Si le système retourne un des sens de « banana » pour le premier mot et un des sens de « phone » pour le second, alors il a réussi. Il faut naturellement faire attention à utiliser des mots qui ont des sens bien distincts et qui ne se répètent pas trop souvent (on regarde les contextes gauche et droit pour identifier le sens, si le contexte inclut notre construction « bananaphone », c'est bof). Des gens ont vraiment travaillé sur une utilisation efficace des pseudo-mots (Nakov & Hearst, 2003).

Besoins

Il n'est pas rare d'avoir des graphes très connectés et de vouloir en extraire les informations les plus pertinentes. C'est en réalité une forme de clustering.

• J'en ai eu besoin quand j'avais créé un graphe de relations entre personnes d'un salon IRC, une relation pouvant être le fait de parler en même temps, voire quelque chose de plus fort : un hilight. Ce sont effectivement les deux indices que j'utilise quand je veux savoir qui parle à qui, et se priver d'une de ces informations m'empêcherait d'extraire les clusters voulus.
• Aujourd'hui, je retrouve ce problème dans l'induction automatique de sens de mots. On veut regrouper les utilisations d'un même mot qui partagent le même sens.

Algorithme : Shared Nearest Neighbors

Clustering : voisins communs

On commence par filtrer les arcs les moins intéressants dans un nouveau graphe. Deux éléments sont liés dans le nouveau graphe si ils partagent au moins un voisin commun dans le graphe de départ (on peut naturellement ajuster le nombre de voisins communs suivant les besoins, et sauter cette étape peut parfois produire de meilleurs résultats).

Une fois que ceci est fait, on obtient les clusters voulus.

Choix de la tête de cluster

Pour donner un nom au cluster, ou tout simplement pour obtenir un "noeud de départ" à partir duquel nous pourrons réaliser nos opérations, on choisit le noeud qui contient le plus de liaisons avec les autres du même cluster.

Un exemple

Source : Ressources et méthodes semi-supervisées pour l'analyse sémantique du texte en français - Claire Mouton

En apprentissage automatique, on veut pouvoir identifier la qualité d'un algorithme. Par exemple, on veut savoir si une application de reconnaissance de texte fait beaucoup d'erreurs ou non. Pour le savoir, il faut le comparer avec le travail d'un humain qui n'aura pas fait d'erreurs.

Ce travail d'un humain s'appelle gold standard en anglais et vérité-terrain en français, mais visiblement personne ne juge utile de le définir. Voilà qui est fait ?

Outre ses qualités rhétoriques, le zeugma peut servir aussi de test linguistique afin de déterminer si deux sens possibles d'un mot sont distincts. C'est très utile pour les lexicographes qui constituent un dictionnaire : faut-il inclure ce sens ? (En pratique, c'est plus complexe, il existe bien d'autres tests ; qui ont tous leur failles. Lire “I don't believe in word senses” (Kilgarriff ; 1997) pour les détails croustillants).

Prenons donc l'entrée du Wiktionnaire pour le verbe « courir ». Qu'est-ce qui justifie d'avoir 20 sens différents ? Certains sont-il plus proches que d'autres ? Avec le sens « être exposé à » et le sens « disputer une course », on pourrait avoir :

Il court un danger et une périlleuse carrière.

C'est bizarre, donc les sens sont distincts, non ? Pour les sens « Prolonger, aller dans une direction déterminée » et « Couler, s'écouler », comment peut-on construire un zeugma ? Les même exemples se retrouvent d'ailleurs dans les deux sens, une fois avec une montagne, et autrement avec une rivière :

Le Rhône court du nord au sud.

Ces montagnes courent du nord au sud.

C'est donc certainement une instance de polysémie : de l'hyponymie ? Les dictionnaires pourraient/devraient d'ailleurs avoir des listes imbriquées, ce qui permettrait de mieux indiquer ces relations, plutôt que de faire comme si les sens étaient clairement distincts.

Un transfuge n'est pas un simple déserteur : il a quitté son pays pour rejoindre le pays ennemi. Kim Philby semble être le transfuge le plus connu : officiellement espion du MI6, il était en réalité agent double à la solde du KGB, et s'est exilé en Russie pour éviter son procès. Il est d'ailleurs à l'origine de la section « anti-soviétiques » britannique existant pour traquer les agents doubles tels que lui, ce qui lui a longtemps permis de se placer au dessus de tout soupçon.

En Traitement Automatique des Langues, et plus particulièrement dans le domaine de la traduction automatique, le mot « transfuge » est utilisé pour désigner les mots qui partagent le même sens et la même graphie dans deux langues différentes (comme le mot transfuge en anglais et français) : ce sont nos agents doubles¹.

¹ Ceci dit, "agent double" ne semble pas être synonyme de "transfuge", pourtant Kim Philby a clairement été les deux. Où est-ce que la distinction se fait ?

Cet article a pour but d'expliquer un concept de manière simple : le but est que vous ayez une nouvelle flèche dans votre carquois à la fin de cet article. C'est pas extrêmement rigoureux, mais l'important est de retenir le principe, qui est utile au jour le jour. Ceci dit, je serai ravi de corriger les coquilles.

La complexité est un outil très puissant permettant de mesurer l'efficacité d'un algorithme donné. Prenons l'exemple du calcul de la taille d'une liste chaînée, on dit qu'il s'exécute en O(n). Cela signifie que si on double la taille de la liste en entrée, l'algorithme prendra deux fois plus longtemps pour s'exécuter. Au contraire, si la taille est stockée à un endroit particulier, la complexité devient O(1) : on peut s'assurer que quelque soit la taille de la liste, le calcul de la taille prendra le même temps à s'exécuter : on n'a plus à se soucier de la taille de notre liste. La complexité est ainsi d'une importance capitale pour les programmes manipulant de gros volumes de données (par exemple des données venant du web) : un mauvais algorithme pourra prendre des années alors qu'un bon algorithme s'exécutera dans un temps plus raisonnable (par exemples quelques minutes ou heures). C'est un sujet passionant, et je vous recommande « L'algorithmique pour l'apprenti programmeur » si vous voulez vous y initier. :)

La complexité amortie est un outil algorithmique qui permet, par exemple de passer en O(1) des algorithmes qui seraient normalement en O(n). Le terme « amorti » vient du fait que toutes les n opérations, on fait un investissement qui va s'exécuter en O(n), mais qui sera *amorti* lors des n opérations suivantes qui s'exécuteront elles en O(1). Ce n'est naturellement qu'un exemple et il y a d'autres possibilités que O(n) / O(1) mais c'est le cas le plus courant et aussi celui que je vais illustrer aussi.

Quoi de mieux qu'un exemple pour comprendre de quoi il s'agit ?

Prenons une opération courante en programmation : l'ajout d'un élément à la fin d'un tableau. C'est une opération qui est notamment « encouragée » en C++ : la classe std::vector de la librairie standard C++ comporte une opération push_back().

for (int i = 0; i < n; i++) {
	v.push_back(i);
}

Quelle est la complexité de cet algorithme ? Avec une implémentation naïve de push_back(), on obtient du O(n²). En effet, à chaque fois qu'on ajoute un élément, il faut recréer (réallouer) un nouveau tableau avec une case libre supplémentaire : c'est une opération en O(n). Le tout dans une boucle sur n, et paf, O(n²). Pourtant cet algorithme s'exécute en O(n) ! Le principe est simple : à chaque ajout en fin du tableau, au lieu d'agrandir uniquement le tableau d'une case, on double sa taille. Ainsi, la plupart du temps, il suffira de remplir une case qui n'est pas déjà inoccupée : opération qui s'exécute en O(1). Comment pourrait-être implémenté push_back() ? Considérons trois membres de la classe std::vector :

• storage, un tableau interne « C » contenant nos éléments
• capacity, la taille du tableau interne
• size, la taille du vecteur telle qu'elle est exposée à l'extérieur de la classe

void vector::push_back(const T& x) {
	if(size == capacity) {
		reserve(size * 2); // donc capacity = capacity * 2
	}

	storage[size] = x;
	size++;
}

Note : la fonction reserve() permet de réallouer le tableau interne afin de réserver de la place pour une utilisation future : elle prend en paramètre le nombre d'éléments totaux et s'exécute en O(n), n étant l'entier passé en paramètre.

Si jamais la taille (externe) est sur le point de dépasser la capacité (taille du tableau interne), alors on double la capacité. Quoiqu'il arrive, on stocke le nouvel élément à la fin du tableau (c'est-à-dire "size"). Ici, l'appel à reserve() se fait en O(n), et le reste de push_back() s'exécute en O(1). Ainsi, si l'appel à reserve se fait tous les n appels, on a gagné : n opérations tous les n appels revient à une opération à chaque appel. On passe effectivement de O(n) à O(1), étant donné que O(n)/n = 1.

En multipliant par deux la capacité à chaque fois que c'est nécessaire, on ajoute en fait n nouvelles cases vides, prêtes à être remplies. Ainsi, après chaque appel à reserve, les n prochaines opérations se feront en temps constant : c'est effectivement gagné ! L'insertion en fin de tableau s'exécute en O(1) amorti. Il est important de préciser que c'est du O(1) amorti et non du O(1) : cela explicite que certains appels se dérouleront en O(n).

Pour information, la norme C++ impose une complexite constante pour push_back(). Dans le cas de C++0x et de vector, vous pouvez aller voir au paragraphe 23.3.6.5/2 qui dit : « The complexity is linear in the number of elements inserted plus the distance to the end of the vector. ». En d'autres termes pour insérer un seul élément à la fin du vecteur, la complexité est constante. C'est à l'implémentation de choisir la méthode exacte, mais c'est très certainement toujours "on multiplie par un facteur de 2". C'est ce que fait g++, vous pouvez le vérifier. :)

Performance

J'analyse ici la performance liée à l'implémentation du tableau dynamique. Il ne faut pas généraliser à l'ensemble des algorithmes qui ont une complexité amortie meilleure que la complexité normale. Ainsi, pour l'ajout d'un élément à la fin du tableau, il y a un « coût » : la mémoire utilisée par std::vector sera, dans le pire des cas, le double de la mémoire réellement stockée par le programme. Ce n'est qu'un facteur 2. À titre de comparaison, les listes utilisent deux fois plus de mémoire que les tableaux, donc on peut considérer que c'est négligeable. Ça nous permet de gagner un facteur "n" en temps d'exécution. La classe vector peut aussi s'occuper de réduire la taille du tableau interne si vous supprimez des éléments (via pop_back()). Vous pouvez considérer que c'est trop cher payé, mais ça ne l'est pas, sauf dans des circonstances exceptionnelles. Si vous êtes vraiment inquiets et que vous connaissez à l'avance le nombre d'éléments à insérer, il est possible d'appeller reserve() vous-même avant d'insérer vos éléments. Cependant, c'est une mauvaise idée parce que cela vous apprend à optimiser prématurément quand ce n'est pas utile, ce qui est nuisible. Bjarne Stroustrup (à l'origine de C++) a d'ailleurs une entrée de sa FAQ C++ sur le sujet :

People sometimes worry about the cost of std::vector growing incrementally. I used to worry about that and used reserve() to optimize the growth. After measuring my code and repeatedly having trouble finding the performance benefits of reserve() in real programs, I stopped using it except where it is needed to avoid iterator invalidation (a rare case in my code). Again: measure before you optimize.

BeautifulSoup est en fait un parseur html. Sa particularité est d'utiliser les mêmes heuristiques que nos navigateurs web pour réussir à obtenir quelque chose de documents pourris où les tags sont pas fermés par exemple. Ça permet donc d'avoir un parser robuste et acceptable pour parser n'importe quelle page web. Comme d'habitude un petit exemple de code ; celui-ci affiche la table des matières de "Erlang Programming" en allant la chercher sur le site d'O'Reilly :

#!/usr/bin/python
# -*- coding: utf-8 -*-

from BeautifulSoup import BeautifulSoup, BeautifulStoneSoup
import re, urllib2

html = urllib2.urlopen('http://oreilly.com/catalog/9780596518189').read()
page = BeautifulSoup(html, convertEntities=BeautifulStoneSoup.HTML_ENTITIES)

titre = page.find('meta', {'name': 'book_title'})['content']
print titre

for chapitre in page.findAll('li', {'class': 'chapter'}):
    titre_raw = chapitre.find('h3').contents[1]
    titre = re.sub(r'\s+', ' ', titre_raw.strip())
    print '- %s' % titre
    for section in chapitre.findAll('li', {'class': 'sect1'}):
        print '  - %s' % section.contents[1].string

Agréable non ? Si c'est pas lisible immédiatement, un petit coup d'oeil sur le code html de la page web, et vous verrez que si, c'est pas mal. Ça permet vraiment de donner le boulot chiant à BeautifulSoup. Pour plus de détails sur la librairie, il suffit d'avoir voir la documentation, formulée de manière un peu inhabituelle mais tout de même efficace.

En plus c'est enterprise ready. :)

Je suis récemment tombé amoureux de Python. :) Il y a un tas de libraries cools écrites en ce langage, et j'aimerais aujourd'hui parler de networkx.

networkx est une simple librairie qui permet de jouer avec des graphes de manière agréable et pas trop lente.

Hello, World!

Commençons par un peu de code :

>>> import networkx as nx

>>> G=nx.Graph()
>>> G.add_node("spam")
>>> G.add_edge(1,2)
>>> print(G.nodes())
[1, 2, 'spam']
>>> print(G.edges())
[(1, 2)]

Extrêmement simple, non ? Si vous avez déjà utilisé une librairie pour gérer des graphes en objet, j'espère que les Factory ne vous manquent pas trop. :)

Visualisons

Il existe un tas de méthodes existantes pour générer des graphes avec des propriétés amusantes, je vais m'en servir ici pour ne pas avoir à le faire à la main.

import networkx as nx
import matplotlib.pyplot as plt

lollipop = nx.lollipop_graph(10, 3)
nx.draw(lollipop)
plt.show()

Algorithmes

C'est la partie la plus intéressante de networkx en terme de gain de temps. De nombreux algos sont définis, d'autres propositions sont les bienvenues, et de manière générale ça permet de faire des trucs rapidement. PageRank est notamment implémenté, mais il existe des fonctions pour jouer avec les cliques, le clustering, les composantes connexes, les graphes bipartis, etc.

Pratique

Si vous avez un graphe dans un format particulier, c'est très facile de le lire en python, mais encore plus facile d'utiliser une méthode déjà gérée par networkx, comme GraphML.

Je me demande encore l'intérêt d'un tel article, mais dans le doute, j'ai cliqué sur "Publier". :) Je pense en tout cas networkx mérite d'être connue, étant donné la facilité avec on l'utilise et l'impression de vraiment se concentrer sur ses problèmes plutôt que sur des détails d'implémentation. Je me retrouve souvent à dire "ah, mais ça existe déjà !" et c'est plutôt bon signe.

First-past-the-post

• Avantages :
  • Ce système avantage un pouvoir fort : les partis majoritaires ont plus de chance d'avoir un peu plus de voix et donc de gagner de nombreux sièges là où un deuxième tour les aurait fait perdre. Lorsqu'il n'y a pas trop de concurrence (avec principalement le parti au pouvoir et l'opposition), cela assure en général à un des partis d'avoir la majorité absolue, ce qui lui permet de faire passer un bon nombre de lois et d'avoir une politique efficace peu freinée par les négotiations potentiellement interminables avec les autres partis.
  • Les coûts sont plus faibles : en ajoutant un deuxième tour, on multiplie les coûts quasiment par deux, ce qui n'est pas négligeable étant donné le nombre de bulletins de votes
• Inconvénients :
  • Les votes ne sont simplement pas représentatifs. Le troisième parti du pays a eu 80% des voix du second mais seulement 20% des sièges. Un parti a eu près de 900 000 voix mais aucun siège, alors que certains partis ont environ 30 000 voix par siège. Certains électeurs demandent simplement que les sièges gagnés soient directement une traduction de leurs votes. En d'autres termes, ils demandent une représentation proportionnelle.
  • Il est extrêmement difficile de produire des sondages représentatifs, les scores étant très serrés, cela peut fausser les résultats. Il est très difficile d'avoir une bonne idée à l'avance du nombre de sièges, et les résultats sont souvent surprenants (le PPDA local a commenté toute la nuit les résultats).

Représentation proportionelle

• ajouter un deuxième tour ;
• demander aux partis d'allouer eux-même les sièges (mais des constituencies auraient des MPs non représentatifs) ;
• garder un seul tour mais demander de classer par préférence les candidats ;
• lire l'article "Proportional representation" sur Wikipedia.

Hung parliament

• un gourvenement minoritaire (ce qui limite sa marge de maneuvre),
• ou alors de former un "hung parliament" (gouvernement de coalition) avec d'autres partis disposant de sièges.

Liens et faits annexes

• United Kingdom general election, 2010
• Lib Dems get 80% the number of votes Labour have, yet 20% the number of seats. Care about electoral reform? Let's do something about it.
• Mend Our Voting System - 38 Degrees

• Un scandale concernant les dépenses des MPs a ébranlé la confiance des citoyens envers leur représentants (qui auraient par ailleurs essayé de censurer Wikipedia pour cacher leurs actes).
• La situation a tellement intéressé les électeurs que la participation a augmenté de trois points (de l'ordre des deux tiers des électeurs potentiels) et des centaines d'électeurs n'ont pas pu voter. Ils vont devoir porter plainte, mais ça va être long et tout.
• Un gouvernement de coalition entre les Lib Dems et les Conservatories semble compliquée depuis que les derniers ont planifié l'adoption d'une politique anti-européenne alors que les Lib Dems sont fortement pro-Europe.

Merci à amaury pour sa relecture avisée.

• FuzzyCLIPS 6.10 Sources and Executables (Linux 32 bit)
• FuzzyCLIPS Documentation
• FuzzyCLIPS Windows Version