Livres en anglais

L'algorithmique est un vaste domaine, auquel les étudiants sont vite confrontés dans leur cursus informatique, sans les lâcher jusqu'à la fin des cours sur la complexité. Cette quatrième et dernière partie d'Algorithms Illuminated plonge dans les méandres des algorithmes pour les problèmes les plus complexes (du moins, selon la théorie de la complexité). L'auteur continue son approche pragmatique, claire et progressive, malgré la technicité du sujet. Bien qu'étant un livre introductif, l'auteur se permet de présenter des évolutions récentes dans la théorie de la complexité.

En tant que livre d'algorithmique, la présentation de la théorie de la complexité n'est pas habituelle. L'auteur préfère une vue proche de la pratique algorithmique : l'objectif est que le lecteur sache reconnaître un problème difficile pour éviter de partir à la recherche d'un algorithme polynomial qui n'existe probablement pas. De là, l'ouvrage présente des techniques de résolution de ces problèmes (des techniques classiques — algorithme glouton, programmation dynamique — et plus spécifiques — solveurs de satisfiabilité et en nombres entiers). Les algorithmes ne sont pas les plus classiques, mais l'objectif est toujours d'entraîner à la recherche d'algorithmes intelligents.

Les problèmes difficiles présentés dans ce quatrième tome ne sont pas abstraits, ils sont régulièrement présents dans la pratique. Ainsi, chacun est toujours mis en contexte. Le dernier chapitre est une étude de cas, pour montrer comment un problème réel (des mises aux enchères de canaux de fréquences pour les télécommunications sans fil aux États-Unis) doit être abordé avec finesse. Cette partie fait appel à tous les outils développés dans les quatre tomes de la série.

Les mathématiques appliquées sont partout, y compris quand il s'agit de concevoir des scénarios d'évacuation de bâtiment ou de simuler le comportement de piétons dans un jeu vidéo. Ce livre aborde ces questions sous un angle microscopique, comme son nom l'indique : comment se déplace chaque personne dans une foule ? Ce livre répond à cette question en expliquant les principes de modélisation de ces situations, selon l'état actuel des connaissances scientifiques (les techniques proposées sont néanmoins implémentées dans un paquet Python, pour une mise en pratique rapide). Les auteurs développent, tout le long de l'ouvrage, le cas d'étude d'une évacuation de bâtiment, mais indiquent aussi les changements à effectuer pour simuler, par exemple, des flots de voitures.

Comme le titre l'indique assez clairement, le contenu est matheux : pour chaque modèle, les auteurs proposent une mise en équation (en vue d'effectuer des simulations numériques), mais analysent aussi ses propriétés mathématiques (existence et unicité de la solution, par exemple). Ces propriétés sont régulièrement remises en contexte (impact lors d'une simulation d'une non-unicité de solution, par exemple). Ils discutent aussi des phénomènes qui peuvent être mis en évidence par ces modèles, comme le fait que ralentir une foule peut augmenter le nombre de personnes que l'on fait passer par une sortie de secours par seconde (l'effet slower is faster). Les modèles abstraits utilisent un certain nombre de paramètres, mais des valeurs habituelles pour la simulation de piétons sont données. Un chapitre fait le lien entre les expériences du domaine (où l'on demande à une foule de se déplacer), les observations faites sur des situations réelles et les modèles mathématiques : il s'agit réellement de mathématiques appliquées, en lien direct avec la pratique.

Le niveau mathématique requis pour les lecteurs est assez élevé : sans connaissances de base en analyse réelle et en équations différentielles, par exemple, on ne profitera pas beaucoup du contenu. Les analyses des méthodes font souvent appel à des notions de stabilité (fonction de Liapounov) ou à la méthode des perturbations infinitésimales, des sujets qui ne sont presque pas abordés dans l'annexe ou explicités comme prérequis.

On peut toutefois reprocher des notations pas toujours limpides (comme un même symbole qui désigne un scalaire ou un vecteur, selon la section, voire des quantités sans aucun rapport : distance entre deux personnes ou distance par rapport à une situation d'équilibre). Le code fourni avec le livre n'a été développé que dans le contexte de cet ouvrage, il ne s'agit pas d'une bibliothèque utilisée au jour le jour par des chercheurs ou praticiens du domaine.

Comment fonctionnent les systèmes de gestion de base de données actuels ? Bon nombre de gens les utilisent sans vraiment vouloir entrer dans les détails, mais ceux qui veulent lever le voile n'ont pas vraiment une pléthore de ressources pour le faire. C'est un manque que l'auteur vient ici combler, avec une présentation générale de toutes les techniques utilisées actuellement pour implémenter de tels systèmes, qu'ils soient relationnels ou pas. Deux grands sujets sont explorés : le stockage de données sur disque et les systèmes distribués, chacun occupant approximativement la moitié de l'ouvrage.

L'auteur considère simultanément deux points de vue, celui de l'utilisateur (comment le système fonctionne-t-il ?) et celui du développeur (comment concevoir un nouveau système de base de données ?). Il explicite ainsi les choix à faire lors du développement et donne les avantages et inconvénients des décisions posées par des systèmes existants.

Les bases de données ont une structure particulière pour obtenir une très bonne performance, puisque la conception d'un tel système requiert de penser à un très haut niveau d'abstraction (le type de requête habituel), mais aussi à un très bas niveau (le fonctionnement des disques durs et des SSD pour optimiser la représentation physique des données). L'auteur passe avec aisance d'un niveau d'abstraction à l'autre et explicite les liens nécessaires.

Bien évidemment, tous les concepts utilisés dans l'implémentation des bases de données actuelles ne sont pas passés en détail, notamment la gestion des requêtes et leur optimisation (un sujet déjà traité dans la littérature sur les compilateurs, par exemple). L'auteur a préféré étudier en profondeur les sujets pour lesquels il n'existe pas encore d'ouvrage de référence.

Les chapitres sont organisés de telle sorte qu'on puisse les utiliser comme une référence, mais aussi découvrir ces sujets progressivement. Pour approfondir, l'auteur n'hésite pas à fournir une abondante bibliographie (y compris du code source de certains logiciels de base de données).

Les algorithmes de flot sont très utilisés en recherche opérationnelle. Souvent, le domaine est perçu comme statique, alors que les développements théoriques et pratiques continuent sans cesse. Cet ouvrage assez succinct présente néanmoins le sujet de recherche dans ses aspects fondamentaux. L'auteur a fait le choix de ne traiter que les algorithmes polynomiaux (exacts ou approchés), afin de garder un livre assez bref. Par ailleurs, un autre choix posé est celui des preuves incluses : elles peuvent toutes être expliquées en moins d'une heure de cours (l'auteur en ayant fait l'expérience). On peut aussi remarquer le soin apporté pour indiquer les structures de données les plus efficaces pour implémenter les algorithmes donnés.

Le premier chapitre démarre sur les chapeaux de roues, avec directement des algorithmes de calcul de plus court chemin dans un graphe, afin d'expliciter des notions qui reviendront régulièrement dans la suite, comme l'étiquetage des nœuds ou la détection de cycle. Par conséquent, le livre est réservé à un public déjà averti des algorithmes sur des graphes… et ouvert aux mathématiques. De fait, l'ouvrage comporte un nombre très élevé de preuves (déjà une vingtaine dans le premier chapitre, une cinquantaine dans le second !), qui en constituent le cœur. Il n'empêche que l'auteur a toujours à cœur de d'abord passer par des raisonnements intuitifs avant de formaliser. Aussi, le contenu reste, en bonne partie, très abstrait : il s'agit de raisonner sur des graphes génériques, pas sur des applications particulières, a priori en totale déconnexion avec la pratique du domaine (sauf en début et fin de livre).

On peut regretter que certains sujets ne soient pas abordés, comme les plus courts chemins avec des contraintes de ressources ces derniers sont extrêmement utiles pour la résolution de problèmes réels de logistique ou de réseau (avec des techniques de génération de colonnes), mais restent à peine abordés. L'utilité de la dualité n'est pas vraiment explicitée, alors qu'elle revient très régulièrement (bon nombre d'algorithmes travaillent sur le dual du problème présenté). De même, les méthodes de point intérieur sont très souvent citées, parfois très légèrement abordées dans les notes de fin de chapitre, mais jamais vraiment décrites dans l'ouvrage, alors que bon nombre de résultats récents les utilisent abondamment.

L'algorithmique est un sujet indispensable pour toute formation de développeur informatique. Ce troisième tome s'intéresse à la manière de concevoir de nouveaux algorithmes selon deux paradigmes : les algorithmes gloutons et la programmation dynamique. Ce livre se place dans la lignée des deux premiers de la série, avec un approfondissement des sujets : par exemple, le deuxième tome abordait les graphes, le troisième présente l'algorithme de Bellman-Ford pour le calcul de plus courts chemins. La lecture des deux premiers ouvrages n'est pas absolument nécessaire, si toutefois vous en avez acquis les bases (aucune annexe ne résume les éléments essentiels) ; certaines connaissances en algorithmique sont requises pour profiter de ce livre.

L'auteur continue avec son parti pris d'un texte clair, épuré, accessible au plus grand nombre. Malgré le niveau technique plus avancé que dans les deux premiers tomes, les explications restent claires et faciles à suivre. Cette troisième partie de la série contient presque exclusivement des exemples des deux techniques de conception d'algorithmes, notamment avec les algorithmes les plus connus et utiles (on a déjà cité Bellman-Ford, il ne faut pas oublier les codes de Huffman, les algorithmes de Prim, de Kruskal, de Floyd-Warshall pour les graphes). Elle s'oriente encore plus vers des applications, mais aussi de la recherche (avec quelques références vers des articles parfois très récents — 2018).

Ce livre fait partie d'une série de quatre et il est extrait de cours en ligne donnés par l'auteur. Tim Roughgarden en a réutilisé certaines ressources pour le compléter. On y retrouve donc l'un ou l'autre quiz (avec des solutions très détaillées) et des problèmes (la plupart ayant une solution explicitée dans le livre), mais aussi des tests plus compliqués en ligne ainsi que des vidéos.

L'algorithmique est un sujet indispensable pour toute formation de développeur informatique, notamment sa partie sur les structures de données. Ce deuxième tome se focalise sur cette notion (ainsi que sur les graphes) et montre à quel point un bon choix de structure de données permet de réduire la complexité d'un algorithme. Il suit de manière très naturelle le premier (bases de l'algorithmique), sans toutefois en nécessiter la lecture : si vous avez de vieilles bases en algorithmique, vous pourrez probablement passer directement à ce deuxième volume pour vous remettre à jour (au cas où vos souvenirs seraient trop émoussés, une annexe résume — forcément brièvement — les éléments essentiels). Les plus débutants devraient cependant plutôt débuter par le premier livre, avec des explications des concepts de complexité bien plus poussées. Cette division en deux volumes fait d'ailleurs que certains éléments sont répétés par rapport au premier tome (comme la justification du pseudocode ou la définition du tri, ainsi que certains traits d'humour).

Comme dans le premier tome, l'auteur prend le parti d'un texte clair, épuré, accessible au plus grand nombre (on peut apprécier la quantité d'illustrations pour les algorithmes de traversée de graphes, pas toujours les plus intuitifs quand on débute dans le domaine). À nouveau, il se focalise sur les éléments les plus importants du sujet. Notamment, seul l'algorithme de Dijkstra pour les plus courts chemins est détaillé dans le livre (pas de Bellman-Ford ou d'A*). Un autre exemple, peut-être plus litigieux, est celui des structures de données de base, puisque l'auteur considère que le lecteur est parfaitement au courant des propriétés et de la manipulation des tableaux, des listes liées, des files et des piles.

Plus que le premier tome, ce deuxième volume se rapproche des applications pratiques. Les algorithmes présentés semblent moins utiles, mais seulement à première vue. L'auteur met toujours les algorithmes en contexte, justifie leur besoin réel. Ainsi, les algorithmes travaillant sur des graphes sont présentés en même temps que leurs applications dans les réseaux ou la planification. Ce côté appliqué se montre aussi dans la structure des chapitres sur les structures de données : le praticien doit surtout connaître les opérations principales des structures de données, leur complexité, mais pas forcément leur implémentation. L'auteur sépare ainsi la spécification de la structure de données des techniques d'implémentation.

L'organisation des chapitres peut sembler un peu contre-intuitive, avec d'abord les graphes et puis les structures de données. Elle a le grand avantage de justifier le besoin en structures de données par la pratique, par la recherche d'algorithmes efficaces pour des besoins concrets (pas vraiment académiques). On peut regretter que ce tome soit autant lié à la série pour certains aspects : l'algorithme de Dijkstra n'est pas l'algorithme le plus générique pour les plus courts chemins, mais il est le seul présenté ici. Il faudra attendre le troisième tome pour découvrir l'algorithme de Bellman-Ford, dans le cadre de la programmation dynamique (peu après avoir lié celui de Dijkstra aux algorithmes gloutons).

Ce livre fait partie d'une série de quatre et il est extrait de cours en ligne donnés par l'auteur. L'auteur en a réutilisé certaines ressources pour le compléter. On y retrouve donc l'un ou l'autre quiz (avec des solutions très détaillées) et des problèmes (la plupart ayant une solution explicitée dans le livre), mais aussi des tests plus compliqués en ligne ainsi que des vidéos.

L'algorithmique est un sujet indispensable pour toute formation de développeur informatique et c'est (malheureusement ou non) souvent un sujet testé lors des interviews de code des grandes entreprises. Cependant, la matière est souvent enseignée de manière très rigide et rarement accessible au plus grand nombre, y compris en début de cursus (l'algorithmique est parfois considérée comme un sujet éliminatoire par les enseignants).

Ce livre propose un autre angle de vue sur le sujet : le texte est clair, pas encombré de termes techniques inutiles. Le contenu est abordé de manière progressive et intégrée (les notations asymptotiques ne sont pas détaillées de manière abstraite, mais dans le concret d'un algorithme). L'auteur a fait le choix de présenter relativement peu d'algorithmes (aucun algorithme de tri ne nécessite de structure de données comme le monceau), ce qui lui permet d'entrer dans les détails. Chacun est d'ailleurs placé dans un vrai contexte avec des problèmes réels où cet algorithme peut être utilisé. Chaque chapitre est terminé par un petit encadré résumant les notions les plus importantes abordées dans ce chapitre.

L'un des choix posés lors de la rédaction a été une complète indépendance vis-à-vis du langage de programmation. D'un côté, cela rend le livre plus abstrait et légèrement moins accessible. De l'autre, cela permet d'éviter les complexités liées à la syntaxe d'un langage de programmation (le lecteur est d'ailleurs supposé déjà savoir programmer dans un langage, c'est presque le seul prérequis — avec un petit peu de mathématiques). Les intrications mathématiques sont limitées au maximum, afin d'élargir le public visé. Certains sujets nécessitent plus d'écritures mathématiques, mais ils sont clairement indiqués comme tels et ne sont pas nécessaires à la bonne compréhension globale de l'ouvrage.

Ce livre fait partie d'une série de quatre et il est extrait de cours en ligne donnés par l'auteur. Ce premier tome parle d'algorithmique en général, sans entrer dans les détails de structures de données : il se limite à quelques algorithmes de tri (le tri rapide ayant droit à son propre chapitre bien détaillé). L'auteur a d'ailleurs réutilisé certaines des ressources de ces cours pour compléter le livre. On y retrouve donc l'un ou l'autre quiz (avec des solutions très détaillées) et des problèmes (la plupart ayant une solution explicitée dans le livre), mais aussi des données de test plus compliquées en ligne ainsi que des vidéos.

En résumé, je trouve que ce livre est une très bonne introduction au sujet de l'algorithmique. Il conviendra très bien aux plus débutants et à ceux que le domaine rebute. Par contre, il faudra le compléter par d'autres livres pour approfondir.

Cet ouvrage montre comment mettre en œuvre PyTorch, bibliothèque Python d’apprentissage machine, au travers du traitement du langage naturel humain. Il s’adresse à un public assez large et à la recherche d’une initiation, mais une solide connaissance du langage Python est requise.

Le livre se compose de 9 chapitres organisés de sorte à rendre la lecture progressive.

Une bonne moitié du livre concerne un tour d’horizon de la structure du langage naturel puis de l’apprentissage par réseau de neurones, perceptron, perceptron multicouches, réseau de neurones à convolution, sachant que la théorie mathématique sous-jacente n’est pas abordée, il s’agit ici de montrer comment l’on se sert de Pytorch.

Puis viennent les chapitres traitant de la vectorisation des mots dans une phrase, des méthodes d’optimisation pour l’apprentissage supervisé ou non, du séquençage des données, de leur prédiction et de leur étiquetage et enfin, des perspectives et limites du thème.

Le sujet est bien expliqué et les exemples de code suffisamment nombreux pour permettre de bien assimiler les principes. On se sent vraiment guidé jusqu’à la fin. J’ai trouvé intéressant le parallèle fait avec le langage naturel et en résumé, je dirai que le livre est un bon complément aux tutoriels qu’on retrouve sur internet et qu’il apporte un plus, notamment parce qu’il permet de s’inspirer de la méthode employée par les auteurs.

Tous les extraits de code publiés dans le livre sont disponibles sur un github.

Le titre de cet ouvrage promet une belle partie appliquée, c'est effectivement ce que l'on ressent à sa lecture : on ne compte plus les lignes de code pour bien montrer ce que l'auteur fait, notamment dans ses graphiques (le code les générant étant présent dans le livre in extenso). Tout le code est d'ailleurs écrit avec Python 3, en utilisant les dernières versions des bibliothèques, afin de rester utilisable aussi longtemps que possible. Ce côté appliqué est présent tout au long du livre, l'auteur cherche toujours à présenter une utilité aux algorithmes qu'il aborde, il ne se contente pas d'un inventaire à la Prévert, le lien avec les applications réalistes est toujours présent.

L'ouvrage est construit progressivement, avec des techniques de plus en plus avancées, en présentant d'abord brièvement les concepts théoriques (sans mathématiques, car tel n'est pas le but du livre), les algorithmes, puis en plongeant dans la pratique. Les approches sont bien souvent comparées sur un même exemple, afin d'en voir les avantages et inconvénients. Cependant, l'apprentissage non supervisé n'est vu que sous un seul angle : l'exploitation de données sans étiquettes dans l'objectif d'effectuer des prédictions, c'est-à-dire comme une approche entièrement supervisée. Ce faisant, tous les aspects d'analyse de données sont négligés : il aurait été agréable, par exemple, de voir une application de partitionnement de données pour comprendre ce qu'elles contiennent (comme déterminer, sans a priori, les différentes manières de participer à un jeu). Au contraire, dans les exemples de partitionnement, on sait d'avance le nombre de classes que l'on cherche.

Au niveau de la présentation, une grande quantité de code et parfois d'images est redondante. Dans les premiers exemples, qui montrent plusieurs algorithmes d'apprentissage supervisé, la validation croisée est présentée à chaque fois, au lieu de se focaliser sur les différences entre les algorithmes. Chaque chapitre commence par une bonne page d'importation de modules Python (y compris des modules qui ne sont pas utilisés dans ce chapitre !). Certaines parties présentent une grande quantité d'images disposées de telle sorte qu'elles prennent un maximum de place (six images de taille raisonnable présentées sur trois pages, alors qu'en les réduisant un peu on aurait pu tout faire tenir sur une seule face…). Par ailleurs, toutes les images sont en noir et blanc, mais ont été conçues en couleurs : il est souvent difficile de s'y retrouver, car l'information de couleur est très exploitée (notamment pour présenter plusieurs courbes : elles ont sûrement des couleurs très différentes, mais les niveaux de gris se ressemblent trop pour que l'on arrive à faire la distinction entre les courbes).

Le côté technique m'a vraiment déçu. Les algorithmes sont présentés très rapidement, leurs paramètres sont quelque peu vus comme des boîtes noires ou simplement ignorés : comment peut-on en comprendre l'impact sur la solution ? Le chapitre sur la détection d'anomalies n'est vu que comme une application de la réduction de dimensionnalité, on ne trouve aucune discussion des algorithmes spécifiquement prévus pour cette tâche (forêts d'isolation, SVM à une classe, etc.), ce qui est assez réducteur. On ne trouve aucune mention des plongements (comme word2vec pour la représentation de mots) dans la section sur les autoencodeurs, alors que c'en est une application très importante.

Le public ciblé semble n'avoir qu'une assez faible expérience en apprentissage automatique. Le livre sera surtout utile à ceux qui veulent une introduction rapide et pas trop poussée au domaine de l'apprentissage non supervisé, un survol du domaine en abordant toutes ses facettes principales. Ceux qui se demandent à quoi l'apprentissage non supervisé peut bien être utile seront servis, mais n'en verront pas toutes les possibilités.

La visualisation de données est un besoin de plus en plus pressant, notamment dans un contexte de mégadonnées : c'est bien de disposer de données, c'est mieux d'arriver à les exploiter correctement. La visualisation est un outil très utile pour cela, mais seulement quand elle est appliquée à bon escient. C'est ce que ce livre propose : des techniques de visualisation, un lien avec les statistiques, des principes de conception d'une bonne visualisation, mais aussi toute une série d'exemples. L'auteur a comme but d'enseigner la manière de réaliser des graphiques qui ont un impact.

L'auteur est un statisticien et cela se ressent dans la manière d'aborder les sujets : pas question d'afficher des barres d'erreur sans expliciter ce qu'elles représentent (écart type, erreur standard, intervalle de confiance ?), par exemple. Ce n'est pas une raison pour abrutir le lecteur de mathématiques, puisque l'ouvrage ne comporte aucune formule, vraiment aucune. Quelques outils statistiques sont présentés, mais assez brièvement, uniquement en expliquant les principes généraux (des références sont là pour compléter). Ce choix est parfois limitant : pour le bootstrap, notamment, l'auteur répète maintes fois l'utilité de la technique, mais ne l'explique pas vraiment.

Les mises en situation constituent l'épine dorsale du livre, en ce sens que chaque chapitre dispose d'une ou plusieurs visualisations réalistes, parfois comparées : quels sont les avantages de telle manière de représenter les données, quelles sont les interprétations plus faciles à réaliser sur tel graphique, quelle visualisation ne peut pas fonctionner (sans oublier le pourquoi, qu'il soit plutôt statistique ou visuel). Cette manière de procéder rend l'ouvrage très lisible et attirant.

Pour la mise en pratique, l'auteur met à disposition sur son site le code source de chaque graphique qu'il a réalisé pour le livre (surtout en R) — même si le livre en lui-même ne présente pas une seule ligne de code, ce n'est pas un tutoriel R ou Stata.

L'apprentissage automatique est un champ extrêmement développé, mais uniquement pour la découverte de corrélations entre variables. Il est parfois facile de déduire un lien entre des symptômes et une pathologie, mais les algorithmes d'apprentissage ne peuvent pas déterminer qui implique qui : est-ce à cause des symptômes que la maladie est présente ou est-ce l'inverse ? L'apprentissage causal cherche à répondre à ce genre de question, le livre ne porte que sur ce sujet.

Les trois auteurs présentent l'essentiel de ce domaine trop peu connu de la science des données, d'une manière progressive : les premières explications se font « avec les mains », la formalisation suit (à deux variables aléatoires pour commencer, puis dans le cas général). Notamment, les analyses contrefactuelles sont abordées en détail. Les auteurs n'hésitent pas à parsemer leur texte de bouts de code pour faciliter la compréhension des concepts et la mise en pratique des algorithmes. À ce sujet, ils considèrent que le lecteur connaît les bases de R et de quelques bibliothèques pour comprendre ces morceaux de code, aucune explication syntaxique n'étant donnée. Autant que possible, les liens entre les concepts présentés et l'apprentissage automatique sont explicités.

Le style est austère et académique. Des renvois vers des articles scientifiques – y compris ceux des auteurs eux-mêmes dont la modestie ne semble pas souffrir – sont faits à de nombreuses reprises pour approfondir les sujets : la présentation d'un algorithme se limite bien souvent aux idées principales sous-jacentes, le reste étant disponible dans la littérature. Globalement, l'ouvrage n'est pas toujours aussi facile à suivre que l'on espérerait : il est plutôt destiné à des gens qui connaissent déjà les bases de l'inférence de causalité, mais cherchent à approfondir le sujet ou à découvrir d'autres axes de recherche dans le domaine.

À noter : le livre est aussi disponible gratuitement au format PDF.

L'apprentissage automatique est un domaine aux multiples facettes. Ce livre dépoussière l'une d'entre elles qui n'est que trop peu explorée dans la littérature : l'étude des flux de données, où les algorithmes doivent effectuer des prédictions, mais surtout s'adapter en temps réel à des données disponibles au compte-gouttes (même si ce dernier peut avoir un très bon débit !). Les auteurs font la part belle aux spécificités de ce paradigme : les calculs doivent être effectués très rapidement, on n'a presque pas de temps disponible par échantillon, ni de mémoire d'ailleurs.

Structurellement, on retrouve trois parties bien distinctes :

• une introduction très générale au domaine, qui montre néanmoins l'essentiel de MOA, un logiciel dédié aux tâches d'apprentissage dans les flux ;
• une présentation plus détaillée des algorithmes applicables à des flux, que ce soit pour les résumer, pour en dériver des modèles de prédiction ou pour explorer les données. Cette partie devrait plaire aux étudiants, professionnels et chercheurs qui souhaitent se lancer dans le domaine, notamment avec ses nombreuses références (pour les détails de certains algorithmes moins intéressants ou trop avancés : on sent un vrai lien entre le livre et la recherche actuelle dans le domaine). Les algorithmes sont détaillés avec un certain niveau de formalisme mathématique, pour bien comprendre ce qu'ils font (et pourquoi ils garantissent une certaine approximation de la réalité) ;
• finalement, un guide d'utilisation assez succinct de MOA, avec un bon nombre de captures d'écran du logiciel (imprimées en couleurs !), qui détaille les différents onglets de l'interface graphique (à l'aide de listes très descriptives, mais liées aux autres chapitres de l'ouvrage) et passe rapidement sur les interfaces en ligne de commande et de programmation (ces deux derniers chapitres sont brefs et doivent être complémentés par celui sur l'interface graphique, qui contient les éléments essentiels).

On peut néanmoins reprocher quelques références vers la suite du livre (la section 4.6.2 considère parfois le contenu de la 4.9.2 intégré, par exemple), mais aussi l'omniprésence de MOA : on a l'impression que les auteurs se sont focalisés sur les algorithmes disponibles dans cette boîte à outils, plutôt que de présenter les algorithmes les plus intéressants en général. Cette remarque est toutefois assez mineure, au vu de l'exhaustivité de MOA.

À noter : le livre est aussi disponible gratuitement au format HTML, les auteurs répondant aux commentaires qui leur sont laissés.

Écrit par Marco Dorigo, fondateur des algorithmes de colonie de fourmis, et Thomas Stützle, expert en optimisation, ce livre est une des références dans le domaine des algorithmes de colonie de fourmis dont il donne un aperçu très complet tout en restant accessible pour les néophytes. De bonnes notions en mathématiques discrètes seront néanmoins nécessaires pour bien comprendre certains passages, l'attachement à la formalisation mathématique étant une des caractéristiques de l'ouvrage.

Le premier chapitre met en exergue les liens entre fourmis réelles et artificielles en s'appuyant sur les interactions entre entomologie, mathématiques et informatique. Le deuxième chapitre situe les algorithmes de colonie de fourmis par rapport aux autres métaheuristiques ainsi qu'aux différentes catégories de problèmes auxquels ils s'appliquent, en l'occurrence des problèmes classiques d'optimisation combinatoire, fournissant ainsi aux lecteurs une superbe vue d'ensemble. Le troisième chapitre présente un exemple simple et détaillé d'application des algorithmes de colonie de fourmis au problème du voyageur de commerce ; diverses variantes de l'algorithme sont exposées et des ajouts majeurs, nommément la parallélisation et la recherche locale, sont introduits.

Ces trois premiers chapitres se lisent facilement et avec le chapitre de conclusion donnent les idées principales. Les autres chapitres sont essentiellement des chapitres d'approfondissement. Le quatrième chapitre explore la théorie sous-jacente aux algorithmes de colonie de fourmis, en détaillant entre autres choses les preuves de convergence et en introduisant le concept de recherche par modèle, par opposition à la recherche par solutions. Il n'existe cependant aucune preuve mathématique sur les vitesses de convergence, absence malheureusement assez répandue dans le monde des métaheuristiques en dépit des tentatives. Le cinquième chapitre est un catalogue de problèmes NP-difficiles auxquels ont été appliqués les algorithmes de colonie de fourmis : la mise en place de l'algorithme, autrement dit la définition de la correspondance entre le problème traité et la métaheuristique, puis les résultats sont présentés pour chaque problème. Le sixième chapitre se concentre sur un problème précis, le routage de données, et se penche sur les similarités avec l'apprentissage par renforcement et la méthode de Monte-Carlo, comparaison très pertinente. Les auteurs terminent sur un chapitre de conclusions et perspectives très diverses allant de la parallélisation algorithmique à la division du travail au sein des agents computationnels inspirée par la nature.

En conclusion, ce livre mérite tout à fait son titre de référence du domaine. Ses explications détaillées, aussi bien expérimentales que théoriques, ainsi que ses nombreuses ouvertures rendent sa lecture palpitante. Chaque chapitre s'achève par une très courte bibliographie et des exercices orientés informatique ou mathématiques. À noter que l'ouvrage date toutefois de 2004, ce qui est ancien étant donné la vitesse d'évolution de la recherche dans le domaine des métaheuristiques : il faut donc l'utiliser pour acquérir des bases solides et non comme un état de l'art exhaustif de la recherche actuelle.

Ce livre est une excellente introduction à la programmation génétique. En seulement 150 pages sans compter la bibliographie fournie, il offre une vue complète du domaine et se lit très facilement.

Après avoir présenté les bases de la programmation génétique, les auteurs exposent dans un chapitre entier un exemple simple pour illustrer concrètement le déroulement d'un tel algorithme. Les concepts avancés sont ensuite présentés de façon assez développée pour pouvoir bien les comprendre, mais pas trop pour ne pas noyer le lecteur dans les détails, le livre étant avant tout une introduction.

Chose intéressante, le livre propose également un chapitre théorique, ce qui est appréciable car la programmation génétique est souvent abordée sous un angle empirique, à défaut d'un modèle mathématique sous-jacent très développé, nonobstant les tentatives. Cette approche théorique permet en particulier de donner une piste d'explication mathématique des méthodes pour contrôler le phénomène de bloat, phénomène correspondant à l'augmentation de la taille du code des solutions sans amélioration de leur fitness, ce qui constitue un des problèmes majeurs de la programmation génétique à l'heure actuelle. Les auteurs poursuivent en donnant un aperçu synoptique des applications de la programmation génétique, ce qui permet de voir concrètement dans quels domaines elle a été mise en œuvre.
Le pénultième chapitre est consacré aux conseils pratiques pour mettre en place et mener à bien des expérimentations. C'est un concentré de l'expérience des auteurs, qu'il sera très utile d'avoir sous la main surtout lors des premières expérimentations. Enfin, les auteurs concluent l'ouvrage par une liste de ressources ainsi qu'un exemple de code source implémentant une expérimentation de programmation génétique.
Je conseille donc ce livre à toute personne souhaitant une introduction rapide ou un
e révision sur la programmation génétique. À noter que, contrairement à d'autres ouvrages tels Essentials of Metaheuristics et Introduction to Evolutionary Computing, ce livre ne permet pas de situer la programmation génétique par rapport aux autres algorithmes d'optimisation, mais se concentre exclusivement sur la programmation génétique. Également, aucun exercice n'est proposé.

Le livre est téléchargeable gratuitement à l'adresse http://www.gp-field-guide.org.uk (licence CC-BY-NC-ND).

Ce livre était à l'origine une compilation de notes de cours pour des étudiants au niveau licence. Son auteur, Sean Luke, chercheur et professeur à l'Université George Mason, a décidé de le publier sous licence CC-BY-ND, donc disponible gratuitement ici afin de le rendre accessible au plus grand nombre. Sean Luke est également un des auteurs de ECJ, une bibliothèque open source parmi les plus utilisées pour les algorithmes évolutionnistes en Java : le livre peut donc être considéré comme son pendant théorique.

Comme le titre l'indique, le livre traite des métaheuristiques, en se focalisant sur les algorithmes évolutionnistes. Une des caractéristiques appréciables du livre réside dans le fait que l'auteur explique très clairement l'enchaînement et les liens entre les différentes métaheuristiques, en soulignant notamment leurs limites ayant conduit à l'élaboration de nouvelles métaheuristiques, ce qui permet au lecteur de sentir l'évolution de la recherche dans ce domaine. Il montre ainsi l'enchaînement entre l'algorithme du gradient, le recuit simulé, la recherche tabou, les algorithmes évolutionnistes, l'optimisation par essaims particulaires, GRASP et l'algorithme de colonies de fourmis. L'avant-dernier chapitre introduit à l'optimisation de stratégies (policy optimization), en présentant entre autres l'apprentissage par renforcement et les learning classifier systems. Le dernier chapitre intitulé "Miscellany" est une mine d'or contenant des conseils très importants et probablement pas assez respectés sur la méthodologie à suivre pour conduire des expériences ainsi qu'un ensemble de tests usuels pour évaluer une métaheuristique, puis se conclut sur une liste de ressources très utiles (sites Web, livres, librairies, conférences, mailing lists, etc.) pour trouver davantage d'informations.

Chaque algorithme est accompagné d'un pseudocode commenté, soulignant par exemple la particularité de l'algorithme au regard des algorithmes précédents. Les 222 pages du livre contiennent 135 pseudocodes, ce qui montre bien l'accent mis sur l'explication concrète des algorithmes en plus des considérations intuitives ou théoriques. Le livre propose également plus de 70 figures qui permettent de mieux comprendre les algorithmes. Le ton général du livre est direct et les phrases sont formulées de façon très accessible. Pour chaque chapitre, les dépendances avec les chapitres précédents sont indiquées. Tous ces éléments rendent le livre facile et agréable à lire. À noter que le livre ne contient pas d'exercice et ne présente que peu d'applications hormis les exemples abstraits : il faudra donc utiliser ECJ ou une autre bibliothèque pour mettre en œuvre les algorithmes expliqués dans le livre. Le guide d'utilisateur de ECJ est complet et traite sous l'angle technique de la quasi-totalité des concepts du livre touchant aux algorithmes évolutionnistes.
Je conseille donc ce livre à toute personne souhaitant une introduction rapide ou une révision sur les métaheuristiques.

Dans ce livre, l'auteur et chercheur en intelligence artificielle Moshe Sipper présente un état de l'art de la programmation génétique appliquée aux jeux, domaine dans lequel l'auteur et son groupe de recherche ont gagné de nombreuses récompenses. Loin de réduire l'ouvrage à une simple énumération de résultats, il se concentre sur certains jeux qu'il a personnellement étudiés. À travers ces études de cas, il a réussi à structurer le livre de manière à montrer une progression dans l'utilisation de la programmation génétique : après avoir commencé à l'utiliser en tant que générateur et optimisateur d'heuristique, il l'applique directement aux algorithmes de recherche, tout en introduisant les notions de coévolution ainsi que d'évolution en îles asynchrones.
Les jeux étudiés au cours de ce livre se classent en trois catégories :

• les jeux de société : une variante du jeu de dames (lose checkers), les échecs et le backgammon ;
• les jeux de simulation : Robocode et le jeu de course RARS ;
• les casse-têtes : Rush Hour et FreeCell.
  

Les résultats présentés sont palpitants car hautement compétitifs avec les humains ainsi que les bots existants. Les solutions sont analysées en profondeur, notamment pour essayer d'entrevoir si l'évolution a fait apparaître des phénomènes d'émergence parmi les individus évolués. Une particularité du livre est son attachement à souligner les liens entre les algorithmes évolutionnistes et les principes de biologie moléculaire afin d'acquérir une compréhension plus intime de l'évolution. Tout au long de l'ouvrage, une myriade de conseils précieux sont donnés sur l'utilisation de la programmation génétique.
Bien que l'auteur aurait pu aisément faire publier le livre chez un éditeur classique tel Springer, il a fait le choix de la générosité et a décidé de rendre le livre téléchargeable gratuitement à l'adresse http://www.moshesipper.com/etw (licence CC-BY-ND).

Utilisé par plus d'une centaine de cours dans le monde et disponible gratuitement en ligne à l'adresse http://www.nltk.org/book (licence CC BY-NC-ND), ce livre offre une excellente introduction au traitement automatique des langues naturelles en expliquant les théories par des exemples concrets d'implémentation. Il se veut donc une introduction pratique au domaine, par opposition à une introduction purement théorique. Chaque chapitre du livre se termine par une série d'exercices classés par ordre de difficulté, mais malheureusement non corrigés.

La particularité principale du livre est qu'il présente de nombreux exemples de code, en se basant sur la bibliothèque open-source et gratuite NLTK (http://www.nltk.org) écrite en Python par notamment les auteurs de ce livre. Très bien documentée, la bibliothèque NLTK offre de nombreuses fonctionnalités de traitement des langues (analyse lexicale, étiquetage grammatical, analyse syntaxique, etc.) tout en interfaçant aussi bien des bases de données tel WordNet que des bibliothèques et logiciels tiers tels l'étiqueteur grammatical Stanford Tagger et le prouveur automatisé Prover9. Un grand nombre de corpus est également disponible via NLTK, ce qui est très appréciable pour mettre en œuvre des processus d'entraînement ainsi que pour réaliser des tests, notamment des tests de performance. Comme le livre présente les nombreuses facettes du traitement automatique des langues naturelles, il parcourt au travers de ses exemples une grande partie des fonctionnalités de NLTK.

La limite principale de la bibliothèque NLTK est les performances de Python en termes de vitesse de calcul. L'utilisation de Python permet toutefois au lecteur de ne pas être trop gêné par la barrière du langage, Python étant à ce jour sans conteste un des langages les plus simples d'accès. Pour ceux n'ayant aucune ou peu d'expérience en Python, certaines sections du livre sont dédiées uniquement à l'explication du langage Python, ce qui permet de rendre l'ouvrage accessible à tout public.

Néanmoins, bien que donnant un aperçu excellent et concret de l'ensemble du traitement automatique des langues naturelles, le focus du livre sur les exemples en Python fait que mécaniquement le livre consacre moins de place aux considérations théoriques. En ce sens, il est un complément idéal au livre de référence Speech and Language Processing (écrit par Daniel Jurafsky et James H. Martin) dont l'approche est beaucoup plus théorique.

Ce livre sur NLTK est réellement bien écrit, il n'est pas nécessaire d'avoir une expérience en traitement automatique du langage pour pouvoir aborder cet ouvrage, il vous apprendra tout ce dont vous avez besoin pour comprendre chaque chapitre. La seule obligation est d'avoir une connaissance du langage Python.
Les exemples sont non seulement simples, mais aussi très utiles, car ce sont des choses dont on pourrait avoir besoin dans une application. J'ai principalement aimé les chapitres sur les extractions d'entités nommées, l'apprentissage pour la création d'un classifieur et l'analyse du sens d'une phrase qui sont particulièrement bien faits et expliqués.
La seule remarque que je ferais est le manque de détails sur toutes les possibilités de création et d'utilisation d'une grammaire via les expressions régulières NLTK ou non.

Ce livre est une des références pour s'initier aux algorithmes évolutionnistes : assez court (à peine 300 pages facilement lisibles) et bien conçu pour une première approche du domaine sans avoir à y investir une quantité de temps considérable, tout en étant plutôt complet et sans se perdre dans des détails inutiles, ce qui donne au lecteur un nombre important de pistes de réflexion essentielles pour une bonne compréhension des différentes problématiques rencontrées le plus souvent dans le domaine.
Il est aussi un des premiers ouvrages présentant une vue d'ensemble sur l'évolution artificielle (EA) et il contient notamment les dernières nouveautés du domaine. Les chapitres alternent introductions théoriques, exemples, algorithmes et exercices, et même si les fondements théoriques ne sont pas négligés, l'accent est davantage mis sur la mise en oeuvre concrète des algorithmes et techniques d'évolution artificielle.
Bref, que ce soit pour découvrir le domaine ou se remettre les idées-clefs en mémoire, je conseille vivement la lecture de ce livre ! Pour les enseignants, des supports de présentation sont disponibles sur le site officiel.
Seul bémol notable, les exercices ne sont pas corrigés et certaines parties potentiellement intéressantes du site officiel sont toujours en construction ou ne sont pas terminées.

Tout d'abord, après avoir présenté dans les grandes lignes le fonctionnement ainsi que les caractéristiques d'un algorithme évolutionniste (chapitres 1 et 2), le livre se penche sur ses quatre variantes usuelles : algorithmes génétiques, stratégies d'évolution, programmation évolutionniste et programmation génétique (chapitres 3 à 6).
En deuxième partie, le livre présente diverses améliorations aux quatre classes d'algorithmes classiques vues précédemment :

• les LCS (Learning Classifier System - chapitre 7), qui sont un système d'apprentissage automatique basé sur le concept d'ensemble de règles conditions-actions et qui permettent d'introduire la notion de coopération parmi les individus d'une même population, contrairement aux algorithmes évolutionnistes classiques dans lesquels les individus sont simplement en compétition. ZCS et XCS sont des variantes ;
• le "parameter control" (chapitre 8), dont l'objectif est d'adapter certains paramètres structurants des algorithmes évolutionnistes, telles la taille de la population ou la probabilité des mutations/croisements, au cours de l'exécution de l'algorithme, contrairement au "parameter tuning" utilisé habituellement, consistant à fixer ces paramètres au début de l'exécution de l'algorithme sans pouvoir les modifier après, ce qui rend l'algorithme beaucoup moins performant ;
• le maintien d'une certaine diversité au sein de la population (chapitre 9), afin de faire face à la convergence vers un optimum local (genetic drift) souvent constaté, à l'instar de la sélection naturelle qui a vu se former des sous-groupes grâce aux contraintes géographiques. On peut de cette manière trouver autant d'optima locaux que de sous-groupes, permettant ainsi d'obtenir de meilleurs résultats sur les problèmes multimodaux en se rapprochant ainsi de l'optimum global ;
• le multiobjectif (chapitre 9), qui repose sur le concept de dominance au sens de Pareto : beaucoup de problèmes ont en effet plusieurs objectifs, les scalariser en un seul objectif comporte des inconvénients, et les résultats montrent que les MOEA (MultiObjective Evoluationary Algorithms) sont en général les meilleurs algorithmes pour résoudre des MOP (MultiObjective Problems) ;
• les algorithmes mémétiques (chapitre 10), qui permettent d'effectuer des améliorations (local search) non génétiques propres à un seul individu, améliorations se basant sur des connaissances expertes spécifiques au problème, en faisant attention à maintenir une certaine diversité au sein de la population. Les résultats ainsi obtenus par rapport à l'EA classique sont généralement meilleurs sur le problème étudié, mais moins bons pour la plupart des autres problèmes.
  

En troisième partie, les auteurs exposent quelques bases de la théorie sous-jacente à l'EA (chapitre 11), puis expliquent comment y inclure des contraintes, comme par exemple en définissant des pénalités dans la fitness fonction (chapitre 12). Ils présentent également des formes d'évolution (chapitre 13) basées sur la coévolution interactive ou compétitive, formes plus proches de la sélection naturelle où les espèces évoluent ensemble et les critères de sélection sont relatifs (telle l'opposition proies vs prédateurs).
Les auteurs concluent sur les bonnes pratiques de mesure de performance d'une EA (chapitre 14), soulignent que le plus important lors de l'utilisation d'une EA est de trouver une bonne représentation ainsi qu'un choix d'opérateurs de variation et de sélection judicieux, et donnent des pistes de réflexion non étudiées dans le livre, tels les colonies de fourmis ou les systèmes immunitaires artificiels.

Cet ouvrage reprend l'intégralité de la thèse de Chris Okasaki avec tous ses points forts, à commencer par les nouvelles techniques algorithmiques avancées (eliminated amortization, lazy rebuilding, data-structural bootstrapping, implicit recursive slowdown). Les systèmes de numération y sont utilisés comme des moules pour fabriquer des TADs sur le modèle des opérations élémentaires d'incrémentation et d'addition. Le système de typage est poussé aussi loin que possible avec les nested data types (polymorphic recursion), les modules paramétrés et les modules paramétrés récursifs.
En plus du contenu de la thèse qui fait déjà autorité, la valeur ajoutée de ce livre réside dans :
- une introduction à la persistence et au path-copying
- un rappel sur l'implantation des structures de données élémentaires (listes,piles,queues,arbres binaire de recherche, arbres rouge-noir)
- des exercices qui explorent des alternatives connues (arbres de Arne Andersson,...) ou des variantes du mécanisme de mise à jour (batched-rebuilding)
- un répertoire d'implantations des structures de tas, assez consistant (leftist heaps, pairing heaps, binomial heap, skew binomial heap, structural-bootstrapped skew binomial heap) sans être exhaustif (il manque le Braun heap et le maxiphobic heap)
En bref il s'agit d'une référence à posséder absolument.
Un seul regret: l'ouvrage n'a pas la prétention d'être une bible. Il ne fait pas le tour complet du sujet puisque par exemple, ne sont pas abordés les thèmes suivants:

- le Finger-tree
- l'implantation efficace des graphes inductifs
- l'implantation efficace de l'Union-Find persistent
Cependant, pour les personnes intéressées, de la documentation sur ces sujets est facilement trouvable en ligne.