Débusquer le hasardL’incroyable efficacité des mathématiques

www.dunod.com16 € Prix France TTC

Sélection d’articles

parus dans

La Recherche

et présentés

par Jean-Michel

Ghidaglia.

NUART : 6915318EAN : 9782100562992

Débusquer le hasardL’incroyable efficacité des mathématiques

Programmer des robots pilotes, reproduire avec naturel les mouvements d’une chevelure, décrypter le génome humain et même corriger l’accent anglais d’un acteur : quel est l’outil su� samment puissant qui permet à lui seul d’accomplir toutes ces prouesses ? Derrière les ordinateurs se cache le véritable acteur, capable de comparer, modéliser, simuler ou programmer même le hasard le plus complet.

Nous pensons souvent les mathématiques

comme un jeu de constructions logiques,

domaine d’idées abstraites qui n’aboutissent

qu’à de complexes équations sans lien

avec le réel. Pourtant, elles sont aujourd’hui

plus que jamais au centre de nos vies.

Des technologies devenues indispensables

au quotidien, du téléphone portable

à Internet, sont entièrement bâties sur

le socle des mathématiques.

Cet ouvrage présente une trentaine

d’exemples où « mathématiques » rime

aussi avec « e� cacité » !

Déb

usq

uer

le

ha

sar

d

L’in

croy

ab

le e

ffic

acit

é d

es m

ath

émat

iqu

es

V

Table des matières

Présentation par Jean-Michel Ghidaglia IXTrou ver les gènes cou pables 1

Bernard PrumAllers- retours vers l’essen tiel 9

Bernard ChalmondS’arra cher les che veux au vent 15

Flo rence Bertails, Basile Audoly et Marie- Paule CaniCombattre le bruit par le bruit 21

Gérard MangianteLa combi na toire à l’assaut du spam 27

Nicolas VayatisDébus quer le hasard 33

Hervé ZwirnPour quoi Gérard Depardieu parle anglais sans accent 39

Geoffroy PeetersDomes ti quer le hasard 45

Bernard ChalmondL’art de simu ler les écou le ments 49

Roger TemamDes élec trons et des satel lites 53

Pierre DegondLa forme opti male des neu rones 57

Yannick Privat

Débusquer le hasard

VI

Géné rer des formes lisses 63Bernard Chalmond

La hié rar chie selon Google 67Jean- François Mé la

La forme mou vante des implants ocu laires 73François Jouve

L’inva sion pro gram mée de la simu la tion 79Florian de Vuyst

La juste mesure des gènes 85Stéphane Robin

Pré voir l’état de l’océan 91Laurent Bertino et Hans Wackernagel

Opti mi ser, guidé par le hasard 97Bernard Chalmond

Des agents pour pré voir l’impré vi sible 101Hervé Zwirn

Les radars en équa tions 107Daniel Bouche

Le rêve d’un réseau anti- bug 113Christophe Genolini

Les yeux de lynx de Spot 5 123Christophe Latry et Bernard Rougé

Les tra jec toires, à vol de robot 131Jean- Claude Latombe

Quand les vagues deviennent dévas ta trices 137Frédéric Dias

Ani mer vir tuel le ment les vête ments 143Michel Bercovier, Rony Goldenthal et Eitan Grinspun

Géo mé trie pul mo naire 149Ben ja min Mauroy

VII

Table des matières

Les défauts du DVD sous l’œil de l’équa tion 155Lionel Moisan et Jean- Michel Morel

Pen ser glo ba le ment, agir loca le ment 159Jean- Michel Coron, Brigitte d’Andréa- Novel, Georges Bastin

Quand le désordre est pré fé rable à l’ordre 165Jean- François Clouet

Les auteurs 169

39

Pour quoi Gérard

Depardieu parle anglais

sans accent

Au cinéma, la voix des acteurs peut être tru quée grâce à l’infor -ma tique. Des tech niques de trai te ment du son per mettent de mettre la dic tion en par titions, que l’on peut ensuite modi fi er jus qu’à cor ri ger le mau vais accent anglais d’un acteur fran -çais.

Dans le film Vatel, de Roland Joffé, le fran co phone Gérard Depardieu parle un anglais lim pide. Cours inten sifs ? Non, il s’agit d’un tru cage. Après le tour nage, l’accent de l’acteur a en effet été modi fié sur ordi na teur, mais le son de sa voix conservé. Cela, grâce aux outils infor ma tiques déve lop -pés par l’Ins ti tut de recherche et coor di na tion acous tique/ musique (Ircam), capables de chan ger, note à note, la « par -tition » du son émis par une voix.Aujourd’hui, on est capable de trai ter numé ri que ment le son d’une voix de manière suf fi sam ment fine pour en extraire le timbre – sono rité propre de la voix – ou la pro so die, c’est- à-dire la manière de par ler de l’acteur, sa pro non cia tion, son accent, et son inter pré ta tion. Par inter -pré ta tion, il faut comprendre les silences, les accen tua -

Débusquer le hasard

40

tions, les into na tions de fin de phrase, etc. Cela per met, en fin de compte, de mélan ger la dic tion d’un acteur avec la voix d’un autre.

Voyelles et consonnesComment défi nir la parole ? C’est la pres sion de l’air insuf flé par les pou mons dans le conduit bucco- nasal qui va lui don ner nais sance. D’abord, l’air passe au tra vers des cordes vocales (deux mem branes dis po sées en tra -vers du larynx). S’il s’agit d’une parole dite voisée – par exemple les voyelles –, les cordes vocales s’ouvrent et se ferment de façon cyclique. D’où un écou le ment répété de petits paquets d’air dans le conduit bucco- nasal. Le nombre d’ouver tures et de fer me tures des cordes vocales par seconde (la fré quence1 du cycle) défi nit la hau teur de la voix : quelque 300 cycles par seconde pour une voix aiguë, seule ment 80 pour une voix grave. Pour chaque paquet d’air, on peut défi nir la pres sion : la forme d’onde élé men taire.S’il s’agit d’une parole dite non voisée – pour le « s », par exemple – les cordes vocales res tent ouvertes et l’air passe libre ment. Il n’y a pas de cycle d’écou le ment de paquets, et l’on n’entend pas de hau teur du son.Le pre mier trai te ment consiste à retrou ver les formes d’ondes élé men taires dans le fichier numé rique d’un enre -gis tre ment vocal. À cet effet, on cherche d’abord la période d’un cycle en détec tant des ana logies dans le signal tem -po rel. Cela est fait à chaque ins tant puisque la fré quence de la voix peut chan ger au cours du temps. Il faut ensuite

1. La fré quence d’un signal est l’inverse de sa période (la durée d’un cycle). Une fré quence de 80 hertz (une voix mas cu line très grave) cor res -pond donc à un signal qui se répète toutes les 12,5 milli secondes.

41

Pour quoi Gérard Depardieu parle anglais sans accent

repérer à quel ins tant les cordes vocales se sont fer mées à l’inté rieur de cha cun des cycles. La fer me ture des cordes vocales pro voque une brève impul sion d’éner gie dans le conduit bucco- nasal. Appa rentes dans le signal, ces impul -sions sont faciles à détecter auto ma ti que ment.Cela fait, il s’agit main te nant de prendre en compte la façon dont la voix est pro duite, à par tir des formes d’ondes élé men taires trans for mées en pho nèmes1 par l’action du conduit bucco- nasal. Pour pro duire les voyelles, celui- ci se déforme et agit à la manière d’un filtre : il laisse pas -ser cer taines fré quences du son, les formants, et en atté nue d’autres, les antiformants.Le fil trage inter vient de manière quasi- indépendante de la lon gueur du cycle d’ouverture- fermeture des cordes vocales, ce qui explique que l’on peut obte nir dif fé rentes voyelles à dif fé rentes hau teurs.Plus complexe, la pro duc tion des consonnes fait inter ve -nir des mou ve ments de la langue, du palais, des dents, des lèvres, et de l’arrière du conduit buc cal. Cer taines consonnes sont pro duites par con stric tion du conduit buc -cal. D’autres sont pro duites par une occlu sion du conduit buc cal sui vie d’un relâ che ment brusque don nant lieu à un très bref bruit d’explo sion. Selon les cas, les cordes vocales peuvent vibrer (« z », « v », « b », etc.), ou non (« s », « f », « p », etc.).On dis pose d’un modèle mathéma tique ad hoc pour cha -cun de ces cas. D’un point de vue mathéma tique, le filtre du conduit bucco- nasal est modé lisé comme une fonc tion por tant sur le signal sor tant des cordes vocales.

1. Le pho nème est l’unité dis tinctive mini male d’un lan gage. L’alpha -bet pho né tique du fran çais contient 37 pho nèmes : 19 consonnes, 15 voyelles, 3 semi- consonnes.

Débusquer le hasard

42

Cette fonc tion dépend de coef fi cients complexes, qui déter -minent fré quences et ampli tudes des formants et des antiformants. En minimi sant la dif fé rence entre le signal réel et le modèle, on peut esti mer ces coef fi cients.

La par tition de la voixAprès ana lyse, une phrase pro non cée par un acteur est repré sen tée de façon sym bo lique un peu à la manière d’une par tition musi cale, dont les notes seraient les pho -nèmes repré sen tés par des taches colo rées. Pour chaque pho nème, on peut y lire la puis sance du signal au cours du temps, la vitesse d’ouverture- fermeture des cordes vocales et la fré quence des formants- antiformants.C’est à par tir de cette par tition que se fait le tru cage. Pour chan ger la hau teur du pho nème, on modi fie la vitesse d’ouverture- fermeture des cordes vocales. La modi fi ca -tion de la durée d’une voyelle est obte nue en aug men tant ou dimi nuant la durée pen dant laquelle les cordes vocales vibrent à une cer taine vitesse. C’est un peu plus compli -qué de trans for mer une voyelle en une autre, puis qu’il faut chan ger les formants du son. Le signal enre gis tré est passé dans un « filtre inverse » qui ôte l’effet de fil trage des formants ini tiaux. Le signal, dit blan chi, ne pré sente plus de formants. Il est ensuite passé dans un nou veau filtre afin d’obte nir les nou veaux formants cor res pon dant aux voyelles sou hai tées.On s’en doute, ce tra vail de modi fi ca tion est long et fas ti -dieux : jus qu’à plu sieurs heures pour une phrase complexe lorsque l’on opère à la main en cor ri geant pho nème par pho nème la hau teur, la durée, les formants. On peut aussi auto ma ti ser le pro cédé, ce qui per met de se livrer à quelques fan tai sies, par exemple, mélan ger le timbre de Jean Gabin avec la pro so die de Louis de Funès.

43

Pour quoi Gérard Depardieu parle anglais sans accent

Pour cela, on commence par créer les par titions à par tir d’enre gis tre ments numé riques de deux acteurs qui pro -noncent la même phrase, cha cun à sa manière. Évi dem -ment, leurs rythmes ne sont pas les mêmes, ce qui impose avant tout d’ali gner les par titions en les éti rant de manière adé quate. Il suf fit ensuite de dépla cer les notes d’un des acteurs pour que sa par tition res semble le plus pos sible à celle de l’autre.

67

La hié rar chie selon Google

Six ans séparent la thèse de deux étu diants de Stanford, Larry Page et Sergey Brin, de l’entrée en Bourse de la société qu’ils ont créée : Google. À la base du moteur de recherche, un concept fondé sur des mathéma tiques ensei gnées en licence.

En 1998, ce n’était qu’un concept mathéma tique. En 1999, il don nait lieu à la créa tion d’une start- up, rapi de ment deve nue lea der des moteurs de recherche sur Inter net. Cette année, l’entre prise a été intro duite en Bourse valeur esti mée : entre 15 et 25 milliards de dol lars. Son nom : Google. Cette success story repose sur un article, publié en 1998 par deux thé sards de Stanford : Sergey Brin et Larry Page1. Ils y déve lop paient le concept de pagerank. Le pagerank ou « indice de popu la rité » per met à Google de conce voir de façon redoutablement effi cace la hié rar -chie des réponses à une requête. Cet ordre est capi tal car l’uti li sa teur moyen se contente de consul ter les vingt pre -mières réfé rences.Deux fac teurs sont pris en compte par le moteur de recherche. D’une part, le « score de per ti nence », qui mesure l’adé qua tion du contenu du docu ment avec la requête. D’autre part, un « indice de popu la rité » de la page, le pagerank, qui ne fait inter ve nir ni son contenu, ni sa fré quence réelle de consul ta tion, mais seule ment

1. www- db.stanford.edu/~backrub/google.html

Débusquer le hasard

68

ses liens avec les autres pages Web. En d’autres termes, Google étu die la « struc ture de graphe1 » du Web. Cette inno va tion se super pose aux méthodes clas siques d’indexa tion.Sur quoi repose le cal cul de cet « indice de popu la rité » ? Sur des méthodes clas siques, ensei gnées en licence de mathéma tiques. Lorsque l’on consulte une page Web, on y trouve des « liens hyper textes » qui ren voient à d’autres pages (« liens sor tants »). Vers cette page, pointent par ailleurs des liens à par tir d’autres pages (« liens entrants »). On attri bue à chaque page un indice qui ne dépend que de ses liens. L’indice d’une page est d’autant plus élevé qu’elle a de liens entrants et que ces liens sortent de pages qui ont elles- mêmes un indice élevé.Si une page B pos sède 10 liens sor tants et si l’un de ces liens ren voie vers une page A, celle- ci « hérite » de 1/10 de l’indice de B (que l’on note PR(B)). S’il y a n pages, B1, B2, ..., Bn qui ont des liens sor tants vers la page A, la page A « hérite » de :

PR(B1)/N(B1) + PR(B2)/N(B2) + ... + PR(Bn)/N(Bn)

où N(B) désigne le nombre de liens sor tants d’une page B.

1. Un graphe orienté peut se repré sen ter comme un ensemble de points, les « som mets » (ici les pages Web), reliés entre eux par des flèches (ici les « liens hyper textes »).

69

La hié rar chie selon Google

A

CB

Figure 7. Un Web à 3 pages.

Pre nons l’exemple d’un Web à 3 pages, A, B et C. La page A contient un lien sor tant vers B et un autre vers C ; la page B un lien vers C ; et la page C un lien vers A. Ce qui nous donne un « sys tème linéaire » :

PR(A) = 0,15 + 0,85 (PR(C))PR(B) = 0,15 + 0,85 (PR(A)/2)

PR(C) = 0,15 + 0,85 (PR(A)/2 + PR(B))Pour le résoudre, on peut prendre des valeurs ini tiales quel conques, par exemple PR(A) = 1, PR(B) = 1, PR(C) = 1. Avec les for mules, on obtient de nou velles valeurs, puis on recom mence l’opé ra tion ave celles- ci. Peu à peu, on converge vers la solu tion :

PR(A) = 1,1633…PR(B) = 0,6444…PR(C) = 1,1922…

Sur 3 clics au hasard, on tom bera donc, en moyenne, 1,16 fois sur la page A, 0,64 fois sur la page B, 1,19 fois sur la page C. La somme de ces valeurs est égale à 3, c’est- à-dire au nombre total de pages consi dé rées.

Navi ga tion au hasardPour aller au- delà, il faut rai son ner en termes de pro ba bi -li tés. Ima gi nons un internaute qui se pro mène au hasard sur un Web compor tant un milliard de pages – il y en a en fait pro ba ble ment 3 à 4 milliards. Si les pages n’étaient pas reliées entre elles, l’internaute aurait une pro ba bi lité de un milliar dième de tom ber sur une page A.

Débusquer le hasard

70

En réa lité, l’internaute a deux façons de tom ber sur la page A : soit direc te ment, soit à par tir d’une autre page qui ren -voie sur A. Admet tons, comme l’ont fait les inven teurs de Google dans leur pre mier article, qu’il y arrive direc te ment dans 15 % des cas et indi rec te ment dans 85 % des cas. On peut défi nir PR(A) comme le nombre moyen de visites de la page A, sur un milliard de pages visi tées au hasard.Sur un milliard de pages visi tées, le nombre moyen de visites directes de A sera de 0,15 ; et le nombre moyen de visites indi rectes de 0,85 fois le nombre de clics sur les liens qui ren voient à la page A. Enfin, pour chaque page B qui réfère à A, le nombre de clics qui ren voient vers A est égal au nombre moyen de visites de B, PR(B), divisé par le nombre de liens sor tants de la page B, soit PR(B)/N(B). On peut donc écrire la for mule :

PR(A) = 0,15 + 0,85 (PR(B1)/N(B1) + PR(B2)/N(B2) + ... + PR(Bn)/N(Bn))

La somme des indices de toutes les pages Web est égale au nombre total de pages du Web (à condi tion de négli -ger les pages qui n’ont aucun lien sor tant). La moyenne des indices est donc égale à 1. L’indice mini mal d’une page est de 0,15, et l’indice maximal de 0,85 fois le nombre total de pages du Web. En pra tique il peut atteindre plu sieurs dizaines de mil lions pour des pages ayant des cen taines de milliers de liens entrants. Pour sim pli fier la pré sen ta tion, Google affiche des indices compris entre 0 et 10 : il ne s’agit pas de l’indice réel mais de sa conver sion dans une échelle logarithmique. À noter que, lorsque l’indice est nul, cela peut indi quer un indice réel trop faible ou une déci sion de fil trer des pages indé si rables…Comment calcule- t-on les indices ? Pour chaque page, on écrit la for mule qui lie son indice à celui des autres pages du Web. Avec un Web de 3 à 4 milliards de pages,

71

La hié rar chie selon Google

il faut résoudre un sys tème linéaire de plu sieurs milliards d’équa tions à plu sieurs milliards d’inconnues. Heu reu se -ment, il existe une méthode clas sique de cal cul par ité ra -tion qui se pro gramme faci le ment (lire ci- contre « Un Web à 3 pages »). Une cen taine d’ité ra tions est suf fi sante pour cal cu ler les indices de toutes les pages du Web. Les choses sont en réa lité un peu plus complexes car Google visite le Web et actua lise ses index en per ma nence.Si une page A ayant un indice élevé ren voie sur une page de votre site, toutes les pages ver ront leur propre indice aug men ter. L’orga ni sa tion interne de votre site (c’est- à-dire les liens exis tant entre les dif fé rentes pages) influe sur la répar tition du pagerank total entre les pages, et donc sur le béné fice que vous pou vez tirer du référencement par une page dont l’indice est élevé.A priori, les liens sor tants n’inter viennent pas dans l’expres -sion de l’indice d’une page, mais ils influ ent sur les indices des pages vers les quelles ils ren voient. Et donc sur la valeur des indices de toutes les pages. En contri buant à la popu -la rité d’un site exté rieur, on dimi nue, en valeur rela tive, la popu la rité de son propre site ! L’attractivité propre d’un site va ainsi aug men ter son indice à la fois en drai nant des liens hyper textes et en dimi nuant l’impor tance rela tive des sites d’où ils pro viennent ! D’où des stra té gies dif fé rentes pour un site uni ver si taire qui a inté rêt à signa ler des sites inté res sants (avec un espoir de réci procité), et pour un site commer cial qui, lui, n’a aucun inté rêt à ren voyer vers des concur rents.De nom breuses socié tés de ser vices pro posent d’opti mi ser le référencement par Google. Cha cun pré tend connaître les modes opé ra toires effec tifs de Google, qui sont, comme pour toute autre entre prise, des « secrets indus triels ». Sans aucun doute, les prin cipes de son fonc tion ne ment ont beau coup évo lué depuis son lan ce ment. Les bre vets les plus récents dépo sés par Google lèvent un coin du voile sur les pistes

Débusquer le hasard

72

explo rées : pro ba bi li tés ini tiales non uni formes ; prise en compte de la « visi bi lité » des liens sur une page, de la « dis -tance » des pages (par exemple selon qu’elles appar tiennent ou non à un même nom de domaine) ou de la mise à jour de la page. Au- delà, on va vers une imbri ca tion plus sophis ti quée des méthodes d’indexa tion et de la méthode du pagerank ; cepen dant, cette der nière conserve sa logique géné rale.Ce texte est tiré d’un sémi naire qui s’est tenu à la Mai son des sciences de l’homme de Paris- Nord en juin 2004.

Débusquer le hasardL’incroyable efficacité des mathématiques

www.dunod.com16 € Prix France TTC

Sélection d’articles

parus dans

La Recherche

et présentés

par Jean-Michel

Ghidaglia.

NUART : 6915318EAN : 9782100562992

Débusquer le hasardL’incroyable efficacité des mathématiques

Programmer des robots pilotes, reproduire avec naturel les mouvements d’une chevelure, décrypter le génome humain et même corriger l’accent anglais d’un acteur : quel est l’outil su� samment puissant qui permet à lui seul d’accomplir toutes ces prouesses ? Derrière les ordinateurs se cache le véritable acteur, capable de comparer, modéliser, simuler ou programmer même le hasard le plus complet.

Nous pensons souvent les mathématiques

comme un jeu de constructions logiques,

domaine d’idées abstraites qui n’aboutissent

qu’à de complexes équations sans lien

avec le réel. Pourtant, elles sont aujourd’hui

plus que jamais au centre de nos vies.

Des technologies devenues indispensables

au quotidien, du téléphone portable

à Internet, sont entièrement bâties sur

le socle des mathématiques.

Cet ouvrage présente une trentaine

d’exemples où « mathématiques » rime

aussi avec « e� cacité » !

Déb

usq

uer

le

ha

sar

d

L’in

croy

ab

le e

ffic

acit

é d

es m

ath

émat

iqu

es