Tue Apr 3 10:25:47 CEST 2012

SMT Versus AI Redux: How Semantic Frames Evaluate MT More Accurately

SMT Versus AI Redux: How Semantic Frames Evaluate MT More Accurately, Chi-kiu Lo and Dekay Wu, 2011 (PDF)

Ce papier traite de l'évaluation de la traduction automatique et propose une nouvelle solution : HMEANT. Traditionnellement, l'évaluation est faite par rapport à une ou plusieurs références humaines en utilisant le score BLEU.

Le score BLEU

Sans rentrer dans des détails que je maîtrise mal moi-même, le score BLEU compare des suites de mots (n-grams) obtenus dans la traduction qu'on évalue et les traductions de références en utilisant une précision (pourcentage de vrais positifs) modifiée. Selon Wikipédia¹, le score BLEU a longtemps été employé en raison de sa "forte corrélation avec les jugements humains" ; mais ce n'est pas toujours vrai et les systèmes ont tendance à faire du sur-apprentissage. En effet, les systèmes sont conçus uniquement pour obtenir un bon score BLEU et n'ont pas de moyen de savoir si le résultat correspond vraiment à une bonne traduction. Toujours selon Wikipédia, SYSTRAN (un système basé sur des règles qui ne prend pas en compte le score BLEU) aurait été manuellement jugé meilleur que d'autres systèmes statistiques obtenant un meilleur score BLEU.

¹ Les articles Wikipédia liés à la recherche scientifique sont ceux pour lesquels j'ai le moins de confiance a priori, étant donné qu'il est difficile pour un chercheur de rester neutre et de ne pas avantager son "courant de recherche" ou sa "vision des choses". Naturellement, il suffirait de vérifier dans les liens donnés, les papiers concernés, les papiers citant les papiers concernés, etc.

De meilleures évaluations

Quoiqu'il en soit, le score BLEU ne prend en compte que des suites de mots et ne donne aucune garantie de validité syntaxique ou sémantique. Il n'est pas pour autant possible d'utiliser une représentation profonde du type logique du premier ordre pour établir si le sens est préservé : il faudrait un humain pour obtenir de tels prédicats logiques, ce qui est contraire à la volonté de garder l'évaluation peu coûteuse. Chi-kiu Lo et Dekai Wu proposent d'utiliser les rôles sémantiques pour évaluer la qualité de la traduction : qui a fait quoi à qui, quand, où, pourquoi et comment ? C'est une représentation sémantique "de surface" qu'il est possible d'acquérir automatiquement (section 7), ou même rapidement par des annotateurs non qualifiés (section 6).

HMEANT

Le principe est d'évaluer la similarité entre l'annotation en rôles sémantiques de la traduction initiale par rapport à l'annotation en rôles sémantiques de la traduction. Il s'agit de compter les rôles qu'on retrouve dans la traduction automatique et la correspondance de la traduction de ces rôles (traduction du rôle correcte, incorrecte ou partiellement correcte). Les poids attribués à chaque rôle sont appris automatiquement à partir de scores donnés par des humains. Les poids sont donc choisis pour maximiser la correspondance entre des scores humains et le score HMEANT.

Il faut annoter :

  • les rôles sémantiques de la référence et de la traduction proposée (possible automatiquement) ;

  • la correspondance entre la traduction du texte compris dans ces rôles (fait manuellement dans ce papier).

Remarques

"Although preserving semantic frames across translations may intuitively sound like a good idea, the history of SMT is littered with surprising failures in attempts to incorporate "obvious" candidates for syntactic models and, more recently, semantic models, so caution is warranted." Un certain nombre de garanties sont données quant à la validité de cette métrique par rapport à ses concurrents.

Il est intéressant d'examiner les poids appris : ils montrent très simplement l'intérêt apporté par chaque rôle (qui, quoi, où, etc.). L'agent (qui) et le thème (quoi) sont les plus importants. Le patient (à qui) n'est pas important, mais c'est probablement du à la difficulté de le différencier avec le thème (quoi) de manière consistante : si les annotateurs humains n'ont pas proposé d'annotation consistante sur ce rôle, il est normal qu'il soit peu improtant.

Ce qui m'a personnellement attiré dans ce papier est l'utilisation de l'annotation en rôles sémantique pour une application concrète et très utilisée. Ce n'est ici que de l'évaluation, mais c'est la porte ouverte à l'utilisation de l'annotation en rôles sémantiques (SRL) pour la traduction automatique (ça a déjà été fait par quelques auteurs). Naturellement, la question d'un sur-apprentissage se pose tout autant qu'avec BLEU, mais il est plus souhaitable de faire un "sur-apprentissage" sémantique que sur des n-grams : on est assuré de préserver la structure du sens.

De telles évaluations plus sémantiques/profondes pour la traduction automatique sont l'objet d'une attention particulière à SSST-6 (organisé par les auteurs de ce papier, et d'autres faisant des travaux allant dans le même sens), on peut donc attendre de nouvelles avancées dans ce sens dans les mois qui suivent.


Posted by cygal | Permanent link

Fri Feb 24 18:16:23 CET 2012

S'inspirer de l'apprentissage sémantique humain pour nos pauvres algorithmes

Je viens d'écouter une présentation passionante de Josh Tenenbaum intitulée « Towards More Human-like Machine Learning of Word ». L'idée est de s'inspirer de l'apprentissage du vocabulaire par les enfants pour mieux apprendre la sémantique des mots en Traitement Automatique des Langues.

Points intéressants ici :

  • On utilise le vocabulaire du machine learning pour parler de faits étudiés jusque-là en psychologie. Celà montre encore une fois le bénéfice tiré des échances entre différents domaines a priori différents.
  • En particulier, les deux domaines peuvent profiter l'un de l'autre. Le Machine Learning profite des idées d'algorithmes, et la psychologie a besoin d'algorithmes d'inférences efficaces.
  • Finalement, c'est surtout de l'apprentissage non-supervisé ; ce qui montre tous les progrès possibles dans le domaine.

Différentes observations prouvent que le cerveau humain fonctionne en partie avec des statistiques. Nous ne citerons ici que The Brain as a Statistical Inference Engine, Eugene Charniak, 2011 (PDF), qui est à la base un discours donné par Charniak au moment de recevoir une récompense prestigieuse en TAL. De manière générale, il semble que les "bayésiens" et les gens qui utilisent des modèles graphiques probabilistes soutiennent cette thèse.

Quoiqu'il en soit, l'objectif de Josh Tenenbaum est ici de montrer en quoi on peut s'inspirer de l'apprentissage tel qu'il est fait par les enfants pour développer des algorithmes plus efficaces en apprentissage automatique. Différents exemples d'apprentissage sont donnés. Dans de nombreux domaines, on reconnaît que vouloir copier directement le fonctionnement humain n'est pas possible.

  • dans le jeu vidéo, une IA doit souvent être mauvaise exprès, et pas jouer "comme un humain"
  • le but de l'apprentissage automatique n'est pas de raisonner comme les humains, mais au contraire de résoudre des problèmes que des humains ne pourraient pas forcément résodure
  • les réseaux de neurones sont inspirés du cerveau humain, mais restent extrêmement différents

Celà étant dit, c'est une source d'information comme une autre, et il n'y a pas de raison de la négliger. Traitons ici deux exemples donnés au cours de la présentation :

  • apprentissage des adjectifs ;
  • apprentissage des nombres entiers ;

Apprentissage des adjectifs

Qu'est-ce que l'adjectif "grand" veut dire ? Son sens dépend fortement du contexte. En effet, un homme grand et un grand bâtiment sont probablement deux notions différentes de « grand ». Des expériences ont étés menées où on a demandé à des gens de dire si telle ou telle instance d'une classe était grande ou non. Il y a différents modèles qui semblent correspondre à ces observation (une version qui a bien marché était de faire un clustering des instances observées, puis de prendre le cluster le plus "grand"). De manière générale, l'enfant finit par apprendre une règle pour de tels adjectifs en utilisant un modèle donné, par exemple « par rapport à des exemples connus d'arbres, un arbre grand est au moins aussi grand que les 10% d'arbres les plus grands ».

Une fois qu'un adjectif est appri, il devient beaucoup plus facile de l'étendre à d'autres adjectifs. Une fois qu'une règle est apprise, on peut l'appliquer partout. Typiquement, l'enfant est ensuite capable d'appliquer cette même règle en faisant varier :

  • la classe considérée (ex. arbre, bâtiment, hamburger) ;
  • l'adjectif considéré (ex. grand, bon, joli) ;
  • le pourcentage à atteindre (ex. 10%) ;

Note : on est très mauvais pour estimer des pourcentages, ici 10% est simplement un moyen de le représenter en machine. Ça fait partie de l'effort « appliquer le vocabulaire de l'apprentissage automatique à un problème jusque-là étudié beaucoup en psychologie.

Par exemple, l'enfant peut ensuite apprendre très vite que bon a un sens appliqué à la classe « nourriture », la dimension « goût », et un pourcentage quelconque. Mais qu'il a un autre sens quand appliqué à la classe « jouet », où la dimension sera plutôt « à quel point il m'amuse ». On retrouve la notion ultra-classique du sens qui dépend du contexte.

Ainsi, l'enfant apprend à apprendre, ce qui lui permet ensuite avec beaucoup moins d'exemples concrets de déduire beaucoup de choses. Il apprend bien plus de mots entre un an et demi et deux ans qu'il en avait appris jusque-là. Le temps était passé jusque-là à apprendre à apprendre. Ce n'est donc pas un processus linéaire où on apprend tant de mots par jours. Cette technique est sûrement une solution aux manques d'exemples d'entraînement en désambiguïsation lexicale. Peut-être qu'on les utilise mal ?

Apprentissage des nombres naturels

Une expérience consistait à demander à un enfant de donner une partie des ballons présents au sol à un adulte. Si je demande un enfant un, deux, trois ou quatre ballons, il ne va pas forcément être capable de m'en donner le nombre exact. En effet, suivant l'âge de l'enfant, il ne connaît que le concept "un ballon", ou alors il connaît aussi le concept "deux ballons", etc. Ainsi, quand on lui demande trois ballons, il ne sait pas combien il en faut, et n'en donne pas que trois. À partir de quatre, une procédure récursive rentre en jeu, et tout d'un coup ça marche pour n ballons.

Pour vérifier cette hypothèse, les chercheurs ont utilisé de l'inductive programming (avec des primitives comme "un-ballon?", "deux-ballons?", etc. et ont regardé le programme renvoyé au fur et à mesure de l'augmentation du nombre d'exemples. Effectivement, leur programme acquiert, un, deux, trois ballons, puis la fonction récursive.

Autres exempels

Avec moins de détails, il explique que les enfants apprennent aussi des quantifieurs tels que "la plupart", "tous", "aucun". Enfin, des théories générales permettent de rendre plus tractable la découverte de lins dans un modèle graphique. En pratique, ça augmente directement l'efficacité de l'algorithme (en terme du nombre d'exemples nécessaires). (désolé, c'est pas clair, mais il fallait que ça sorte).


Posted by cygal | Permanent link

Fri Jan 20 14:45:53 CET 2012

Évaluation de systèmes complexes : quelques pistes

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


Posted by cygal | Permanent link

Wed Jan 18 17:25:44 CET 2012

Extraire les connexions les plus fortes d'un graphe

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

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


Posted by cygal | Permanent link

Mon Jan 16 16:02:49 CET 2012

Vérité-terrain et gold standard

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 ou ground truth en anglais et vérité-terrain en français, mais visiblement personne ne juge utile de le définir. Voilà qui est fait ?

Edit 9 février : Bon OK, c'était défini en anglais et français. Je me cache.


Posted by cygal | Permanent link

Mon Jan 16 15:10:43 CET 2012

Utilité du zeugma

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.


Posted by cygal | Permanent link

Fri Jan 13 10:41:36 CET 2012

Humour en « traduction automatique »

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 ?


Posted by cygal | Permanent link

Mon Aug 22 10:48:49 CEST 2011

La complexité amortie pour l'apprenti programmeur

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.

Ceci n'était qu'une introduction, et « Introduction à l'algorithmique » de Monsieur Cormen (chapitre 17 en l'occurence) vous donnera bien plus d'informations sur le sujet. Cependant, l'apprenti programmeur peut se contenter de cette introduction rapide pour comprendre le concept et ne plus s'inquiéter lors des appels à push_back (ou de l'équivalent dans son langage préféré).

Posted by cygal | Permanent link

Tue Dec 14 00:20:19 CET 2010

BeautifulSoup

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. :)


Posted by cygal | Permanent link

Tue Nov 30 16:26:27 CET 2010

NetworkX, The Missing Graph Library

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. :)

Lollipop graph

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()
Il est bien sûr facile d'utiliser les autres formats de sortie comme dot.

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.


Posted by cygal | Permanent link