Association francophone pour la recherche et l'enseignement en sciences et technologies de l'information   Abonnement/Désabt.    Accueil Asti    Accueil Gerbert    Numéros précédents   Dictionnaire  Stic-Hebdo

Sommaire : Trois questions à Jean-Paul Delahaye| L'actualité de la semaine | Théories et concepts | Enseignement | La recherche en pratique | Dans les entreprises et les administrations : | Manifestations | Bibliographie | Détente

"En matière de complexité, l'exemple pour moi le plus remarquable des problèmes d'aujourd'hui et de l'intérêt d'algorithmiques propres, c'est la fonction page rank de Google."

Trois questions à Jean-Paul Delahaye

Professeur. LIFL, équipe Smac (Systèmes multi-agents et comportements)

Stic Hebdo : La complexité est, me semble-t-il, au coeur de vos réflexions, comme en témoigne votre ouvrage Information complexité et hasard (Hermès. 2eme édition 1999). A la mode à partir des années 1970, sous l'influence notamment de systémiciens comme Jean-Louis Le Moigne, de sociologues-philosophques comme Edgar Morin, sans parler de ses aspects techniquement informatiques (complexité algorithmique), vous en avez montré le volet mathématique, notamment avec la complexité de Kolmogorov et la profondeur de calcul de Bennett. Comment voyez-vous ce concept se développer aujourd'hui ?

Jean-Paul Delahaye. Je ne pense pas qu'on puisse parler d'une théorie générale de la complexité. Il y a de nombreuses théories parlant des divers aspects de la complexité et elles se rattachent à des disciplines variées : mathématiques, physique, etc. On peut reprocher à certains auteurs de manquer de précision sur le plan formel, voire de faire quelques confusions. Pour ma part, j'ai toujours défendu l'idée que la mathématisation était utile dans ce domaine comme partout, et j'en trouve constamment de nouvelles preuves dans le champ des Stic.

Pour moi un exemple très remarquable aujourd'hui, c'est la fonction page rank de Google,  l'algorithme que ce moteur utilise pour attribuer une note de notoriété aux pages et choisir celles qui apparaîtront en premier (NDLR : Le meilleur document facilement accessible sur cette fonction est l'article ad hoc  de Wikipedia). Cet algorithme ne fait pas tout le travail mais il est crucial dans le succès de ce moteur de recherche. Ce système est une sorte d'hyperdémocratie : tous les mois à peu près, le calcul est refait, et chacune des pages vote pour les autres. En outre, le système a des propriétés de robustesse. On peut démontrer qu'une tentative de manipulation du page rank (par exemple par l'introduction de pages artificielles créées uniquement pour servir d'autres pages) est forcément coûteuse.

Or il est basé sur  la théorie des chaînes de Markov, et finalement (pour simplifier) attribuer les notes de notoriété aux pages, c'est résoudre un système de 8 milliards d'équations. La résolution est ici approximative, certes, mais procède par un système d'itérations assez classique, bien fondé, clair, propre (même si les tentatives de manipulation obligent son prestataire à le "triturer" un peu.  On retrouve ici la dialectique du glaive et du bouclier.)

Le page rank ne relève pas directement de la complexité au sens de Kolmogorov, mais simplement au sens quantitatif : huit milliards de pages, et donc un nombre encore beaucoup plus élevé de liens.

S.H. : Ainsi, c'est l'énormité du web qui serait aujourd'hui significative en matière de complexité ? Comment cela peut-il devenir un thème de recherche ?

J.-P.D. Il faut signaler ici, par exemple, les travaux menés par Paul Vitanyi et ses collègues (on trouve facilement des références sur la Toile).  Il utilise le concept de "distance informationnelle" entre deux objets, définie formellement, à la Kolmogorov, comme la taille du plus petit programme qui permet d'obtenir le second à partir du premier. Ce concept comporte un grand nombre de variantes, toutes reliées à la complexité. On peut considérer la distance de Hamming comme un cas particulier très simple. 

La distance informationnelle est un moyen efficace pour classer des séquences génétiques, des morceaux de musique, ou des textes d'auteurs différents (Victor Hugo, Lamartine... Houellebecq) . De là on peut calculer des arbres, comparables à ceux de la philogénie.

Dans le même esprit, Vitanyi propose d'utiliser le moteur Google pour calculer une distance sémantique entre mots. Sommairement, on compare le nombre de réponses obtenues avec deux mots, par exemple informatique et ordinateur, et l'on apprécie l'importance des réponses communes. De là on peut aller jusqu'à construire des définitions répondant aux  positions dans l'arbre,  comme dans un livre de botanique.

Ainsi,  le fait de disposer aujourd'hui d'une énorme base de données (l'ensemble des pages Internet, accessibles aisément et pré-travaillée par des moteurs de recherche) permet d'accéder à une information quasiment sémantique. La masse des textes produit un effet de codage des paradigmes. La quantité efface, d'une certaine façon, l'imperfection de chaque document. On contourne ainsi ce qu'on croyait nécessaire jusqu'à présent pour accéder au sens : une approche conceptuelle et syntaxique . Ces méthodes, assez récentes d'ailleurs, ne résoudront sans doute pas tous les problèmes. Mais il peut y avoir une complémentarité avec les méthodes traditionnelles.

Méfions nous de la science-fiction et des promesses trop faciles, surtout en ce qui concerne l'intelligence artificielle. Peut-être saurons nous un jour faire des machines d'une intelligence équivalente à la nôtre. Mais l'important c'est que, sur le chemin qui nous y mènera peut-être, nous aurons construit (et nous avons déjà construit) quelque chose qui change complètement le monde.

J'aime beaucoup la comparaison du problème de l'IA avec celui du vol des oiseaux. Nous ne savons pas faire des oiseaux mécaniques indiscernables par exemple des mouettes (encore moins pour les mouches). Y parviendra-t-on un jour ? Le fait important, c'est qu'en cherchant à les imiter, nous avons développé des machines qui sont capables de voler plus vite, plus haut, plus longtemps, avec des charges beaucoup plus grandes que les oiseaux. De plus, nous avons mis en place tout un système de transport aérien qui a changé la vie des hommes. Pour l'imitation de l'intelligence humaine, la situation est la même, il n'est pas certain que nous puissions y arriver mais, même si nous n'y arrivons pas aujourd'hui, nous avons déjà créé d'autres formes d'intelligence et elles changent le monde. ¨

S.H. : Comment se situent ces réflexions dans votre environnement de recherche ?

J.-P.D. Mes travaux portent sur la théorie computationnelle des jeux et elle se déroule dans le cadre de l'équipe Smac (Systèmes multi-agents et comportements), dirigée par Philippe Mathieu. Nous étudions les conséquences de l'interaction dynamique d'une multitude de stratégies complexes. Nous opérons grâce à des simulations à grande échelle, le tout en gardant des modèles mathématiques les plus simples possibles.

En matière de jeux, par exemple, un des nos outils préférés est le modèle les jeux "itérés". Tout part de l'idée de la confrontation de stratégies qui s'opposent et obtiennent à l'issue d'une série d'échanges des biens plus ou moins importants. Ces stratégies peuvent être multipliées et ainsi représenter des univers complexes. On peut étudier, par exemple, l'effet sur une société du comportement d'un voisinage plus ou moins agressif, ou la diffusion d'un modèle social (très simplifié, bien sûr) d'une société à une autre.  Les modèles construits par la théorie computationnelle des jeux sont utilisés aussi bien par les biologistes préoccupés par la théorie de l'évolution que par les économistes, les psychologues, les tacticiens militaires ou les spécialistes de l'économie politique.

Propos recueillis par Pierre Berger

Actualité de la semaine

Partage de données électroniques médicales des victimes de Katrina

Sur une initiative du gouvernement fédéral après l'ouragan Katrina, les bases de données informatiques de différentes pharmacies et fournisseurs de soins ont été rassemblées dans une base de données centralisée. Les secours aux victimes peuvent accéder à cette base de données à la recherche des prescriptions de médicaments concernant plus de 800 000 sinistrés, pour lesquels ils ne disposeraient sinon d'aucune information.

C'est une étape dans la reconstruction des dossiers médicaux de ces personnes, actuellement séparées de leur médecins et de leur pharmacies habituels. Beaucoup craignent en effet que les dossiers médicaux, et en particulier ceux qui n'étaient pas informatisés, aient été perdus lors de la tempête. Il a fallu une dizaine de jours pour organiser le système, en réunissant une soixantaine d'officiels gouvernementaux, de représentants de compagnies de soins, d'assurance et de logiciel médical, des pharmacies et des conseillers juridiques. Le respect de la vie privée a évidemment suscité des questions lors de la mise en place du système et des Etats ont suspendu certaines lois pour rendre possible ce partage de données. D'après le Washington Post. (Communiqué par l'ambassade de France).

Un pionnier de l'IA nous quitte

Nous apprenons avec tristesse la mort de Jean-Louis Laurière, un des pionniers de l'Intelligence Artificielle en France, la dernière semaine d'août 2005. Ancien professeur d’informatique de l’Université Pierre et Marie Curie (Paris VI), il est décédé subitement le jeudi 25 août, dans sa 60ème année.

Il a été un pionnier de la recherche en Intelligence artificielle (IA), notamment dans les domaines de la résolution de problèmes et de la représentation des connaissances. Son système général de résolution de problèmes, Alice, est toujours d’actualité, après 30 ans. Son moteur d’ inférence, Snark, a marqué l’histoire des systèmes à base de règles.

Il a été le premier en France à introduire un module d’enseignement de l’IA au sein de la maîtrise d’informatique. Des générations d’étudiants ont bénéficié de son charisme et de ses qualités pédagogiques exceptionnelles. Son départ dans l’industrie, en 1987, a interrompu sa carrière d’enseignant. En revanche, il a poursuivi ses activités de recherche jusqu’à ces dernières années.

Théories et concepts

Définition des Stic

Le portail Interstices a mis en ligne au titre de débat, dans une belle présentation, la définition des Stic qu'a validée l'Asti en printemps dernier sur une proposition de Pierre Berger.

Move 36 : Deep blue vue par un artiste

Eduardo Kac, en expositions personnelle, du 28 septembre au 26 octobre à la galerie Biche de Bere, présente notamment “Move 36”, qui fait référence au coup porté par l’ordinateur nommé Deep Blue contre le champion du mode d’échec Gary Kasparov en 1997. Cette compétition peut être caractérisée comme un match entre le plus grand joueur d’échecs qui n’ait jamais vécu et le plus grand joueur d’échec qui ne vivra jamais. L’installation met en évidence les limites de l’esprit humain et les capacités toujours plus grandes développées par les ordinateurs et les robots, êtres inanimés dont les actions acquièrent souvent une force comparable au comportement subjectif humain.

L’installation présente un échiquier fait de terre (les cases noires) et de sable blanc (les cases blanches) au milieu d’une pièce. Il n’y a pas de pièces d’échec sur l’échiquier. Posée exactement à l’endroit où Deep Blue fit son « coup 36 » se trouve une plante dont le génome comprend un nouveau gène que j’ai spécifiquement créé pour cette œuvre. Le gène utilise l’ASCII (le code numérique universel pour représenter les chiffres binaires comme des caractères romains) pour traduire la citation de Descartes : “Cogito ergo sum” (Je pense donc je suis) dans les quatre lettres du code génétique. La présence de ce “gène cartésien” dans la plante enracinée précisément là où l’humain a perdu devant la machine, révèle la frontière ténue entre l’humanité, les objets inanimés ayant des caractéristiques proches de la vie et les organismes vivants qui contiennent des informations codées numériquement.

Un jeu pour des joueurs fantasmatiques, une déclaration philosophique exprimée par une plante, un processus sculptural qui explore la poésie de la vie réel et de l’évolution. L’installation est dans la continuité de mes interventions aux frontières entre le vivant (humain, animaux non-humains) et le non vivant (machines, réseaux). Faisant échec et mat aux notions traditionnelles, « Move 36 » montre la nature comme une arène pour la production de conflits idéologiques et les sciences physiques comme un lieu de création de fictions scientifiques. (Communiqué des organisateurs).

Télécharger le dossier.

Le cerveau humain, toujours en évolution ?

Deux études menées par la même équipe et parus dans la revue Science suggèrent que l'évolution du cerveau humain pourrait s'être poursuivie après l'avènement de l'Homo sapiens. Bruce Lahn, de l'Université de Chicago (Illinois), et ses collègues ont séquencé l'ADN d'environ 90 cellules humaines tirées des collections du Coriell institute for medical research de Camden, dans le New Jersey. Ils ont ainsi mis en évidence, pour deux gènes particuliers dont on pense qu'ils régulent la croissance cérébrale, deux allèles dont la fréquence statistique ne devrait rien au hasard, indiquant l'intervention d'une sélection naturelle.

Selon les estimations des chercheurs, ces deux allèles favorables auraient émergé il y a 37 000 ans pour l'un (avec un intervalle de confiance allant de 14 000 à 60 000 ans) et 5800 ans pour l'autre (avec un intervalle possible de 500 à 14 100 ans). La sélection naturelle aurait donc maintenu son influence sur le cerveau jusqu'à très récemment. T

Toutefois cette conclusion est encore loin de faire l'unanimité. Si les allèles découverts par l'équipe de Bruce Lahn semblent bien portés la marque de la sélection naturelle, il n'est pas prouvé que celle-ci se soit exercée sur le cerveau (les gènes concernés sont exprimés dans d'autres tissus du corps humain) ni même que l'avantage cognitif conféré, s'il existe, soit très marqué. De plus amples recherches devraient permettre de répondre à ces questions. Communiqué par l'Ambassade de France, selon le New York Times et Science Magazine.

Enseignement

Espaces numériques de travail

Une consultation publique Sdet (Schéma directeur des espaces numériques de travail) est ouverte, afin d'alimenter la réflexion qui aura lieu au cours de l'année 2005-2006, à l'ensemble des acteurs (industriels, communautés éducatives, collectivités, ...). Envoyez vos contributions du 15 septembre au 31 octobre.
Renseignements sur les site Educnet.

Démocratie et citoyenneté à l'ère numérique : les nécessités d'un enseignement

Jean-Pierre Archambault (chargé de mission veille technologique au CNDP-CRDP de Paris) lance, dans la revue de l'EPI : "Rare est l'approche qui s'intéresse à la formation des citoyens aux TIC, composante de la culture générale de « l'honnête homme » du XXIeme siècle. Et là, le rôle de l'école est irremplaçable pour l'appropriation de notions scientifiques et techniques, pour former des utilisateurs « intelligents » s'étant construit des représentations mentales opérationnelles. Et des citoyens éclairés percevant et comprenant les problématiques et les enjeux de société liés aux TIC." Selon L'EPI.

Rubrique réalisée avec la collaboration de Jacques Baudé

La recherche en pratique

Valorisation des mémoires de recherche

Xavier Perrot signale l'initiative prise par l'Ecole du Louvre pour valoriser ses mémoires de recherches Le site.

Dans les entreprises et administrations

Modernisation de l'Etat

A la demande de Jean-François Copé, Frank Mordacq doit prochainement rendre publiques ses conclusions sur l'organisation et les missions de la nouvelle Direction générale de la modernisation de l'Etat, à laquelle est désormais rattachée l'Adaé (Agence pour le développement de l'administration électronique).

Les technologies de l'information seront incontournables pour parvenir à la "nouvelle ambition pour la réforme de l'Etat" présentée au Conseil des ministres de fin juillet. L'administration est confrontée à de nombreux enjeux pour mener à bien ses chantiers reposant sur les technologies de l'information et de la communication (TIC) : budgets serrés, croissance du nombre de projets, temps d'exécution raccourcis, manque d'expertise, objectifs de performance renforcés, etc. Autant de raisons qui motivent un recours accru à des prestataires externes, indique Markess International dans son étude Externalisation IT dans l'administration française, 2005-2007.

Malgré un rebond de l'industrie des télécommunications, l'Internet lance de nouveaux défis

L'OCDE note que l'industrie des télécommunications a renoué avec la rentabilité, mais l'évolution des technologies Internet remet en question le rôle et le modèle économique traditionnels ... Le site.

Manifestations

Consultez le site des associations membres de l'Asti, où vous trouverez les manifestations qu'elles organisent.

Pour les manifestations TIC en rapport avec l'enseignement et la formation, consulter le site Educnet.

Diffusion, circulation des savoirs, handicap et TIC

Deux journées préparatoires au SMSI (Tunis, novembre 2005) sont organisées par la délégation gouvernementale française pour le Sommet mondial sur la société de l'information. Elles se tiendront à Paris les 4 et 5 octobre, avec objectif de dresser un état des lieux de l'offre française (notamment qui fait quoi) sur deux sujets : la diffusion et la circulation du savoir, et l'apport des TIC aux handicapés. Programme et inscription: Le formulaire.

Détente

Mathématiques françaises

L'histoire des mathématiques ne relève pas du travail des sticiens. C'est pourquoi nous présentons dans cette rubrique l'ouvrage "Cinq siècles de mathématiques en France", que vient de signer le mathématicien Marcel Berger aux éditions de l' ADPF. Sur ce site, le livre peut aussi bien être commandé sous forme papier (17 euros) que téléchargé (en PDF, globalement ou par parties). Rédigée volontairement sous une forme très lisible par les non-mathématiciens, cette promenade n'esquisse pas les difficultés d'aller jusqu'aux contemporains, mathématiciens vivants compris. Avec en ouvre une sorte d'annuaire pratique "carrières et lieux".

Leibniz et les autres

Le troisième tome de la "trilogie baroque" de Neal Stephenson est récemment paru chez Arrow Books. Après Quicksilver et The Confusion, le troisième volet est intitulé The system of the world. Entre cent autres personnages évoqués par ces aventures picaresques, on y apprend (si on ne le savait pas encore, ce qui était mon cas), que Leibniz eut une conception très vaste de l'informatique et des systèmes d'information, depuis la mécanique et le système binaire jusqu'aux bases de connaissances. On en trouve confirmation en consultant par exemple l'article de la Wikipedia (la version anglaise, car le texte français est surtout orienté vers la philosophie). Une nourrissante lecture de détente malgré quelques longueurs (quelque 800 ou 800 pages selon les tomes).

Ce prolifique auteur de science-fiction (futuriste ou historique) combine une culture encyclopédique avec une imagination débordante et souvent hilarante. Il nous a déjà donné :
- Interface (avec Frederick George), Arrow Books 2002. (thème : biochip cérébral).
- La trilogie "Turing" : Cryptonomicon. I. Le code Enigma (Payot SF 1999), II Le réseau Kinakuta (Payot SF 1999), III Golgotha (Payot SF 2001). Thème : réécriture fantastique des activités anglaises de cryptographie pendant la deuxieme guerre mondiale.
- Le samouraï virtuel. Laffon 1996. (Original : Snow crash, 1992). Thème : mondes virtuels, virus, prothèses informationnelles.
- L'age de diamant. Editions Rivages, 1996. Thème : nanotechnologies, EAO.

L'équipe de Stic-Hebdo : Directeur de la publication : Jean-Paul Haton. Rédacteur en chef : Pierre Berger. Secrétaire général de la rédaction : François Louis Nicolet, Collaborateurs : Mireille Boris, Claire Rémy et Armand Berger. Stic-Hebdo est hébergé par le LRI et diffusé par l'Inist.