Un verre d'eau avec des glaçons

Physique statistique et information : le défi des données massives

Dossier : La PhysiqueMagazine N°721 Janvier 2017
Par Marc MÉZARD

Dans le cadre de la physique il y a l’in­fin­i­ment com­plexe, avec le traite­ment des don­nées mas­sives. Trois exemples :
► La tran­si­tion de phas­es d’un corps où il appa­raît un com­porte­ment col­lec­tif nou­veau dans un sys­tème à un grand nom­bre de particules.
► La trans­mis­sion de l’in­for­ma­tion où il existe un code de cor­rec­tion qui sup­prime toutes les erreurs pour un bruit de fond donné.
► La com­pres­sion du sig­nal que l’on souhaite faire à l’en­reg­istrement et non plus en post-traitement 


Un glaçon dans un verre d’eau : des molécules d’H2O organ­isées différemment.
© KATELEIGH / FOTOLIA.COM

Dès le début du vingtième siè­cle, les physi­ciens curieux s’étaient inter­rogés devant les dif­férentes phas­es de la matière. Un glaçon dans un verre d’eau ? Ce ne sont que des molécules d’H2O.

Les inter­ac­tions entre deux molécules sont tou­jours les mêmes, alors qu’est-ce qui amène ces molécules à par­fois s’aligner pour con­stru­ire un cristal bien ordon­né, ou bien au con­traire à dif­fuser dans l’eau ? La réponse est juste­ment qu’il s’agit d’un com­porte­ment collectif. 

Vous ne pou­vez ni l’observer ni le com­pren­dre en étu­di­ant cinq ou dix molécules. En revanche, lorsqu’il y en a un grand nom­bre il se pro­duit un phénomène coopératif, pure­ment sta­tis­tique, qui les amène à s’aligner dans un ordre cristallin, à une tem­péra­ture très bien définie et très pré­cise, le zéro degré de l’échelle Celsius. 

Il a fal­lu atten­dre les travaux du physi­cien norvégien Lars Onsager en 1944, pour obtenir une analyse détail­lée de ce phénomène pour­tant d’expérience quo­ti­di­enne : la tran­si­tion de phase entre un solide et un liquide. 

REPÈRES

Le domaine de la physique statistique d’aujourd’hui est celui qui explore les phénomènes « émergents », les comportements collectifs nouveaux qui apparaissent lorsqu’un système est composé d’un grand nombre de particules.
Le prix Nobel Philip Anderson l’avait résumé dans le titre d’un de ses articles célèbres : More is different.

LES SINGULARITÉS DE LA TRANSITION DE PHASE

Depuis une quar­an­taine d’années, l’attention des physi­ciens s’est déplacée vers une autre fron­tière, celle des tran­si­tions de phas­es dans les sys­tèmes très désor­don­nés, les verres. 

Pierre Weiss (1865-1940) invente en 1907 la théorie du champ moyen.
Pierre Weiss (1865–1940) invente en 1907 la théorie du champ moyen.

Un verre est en effet un état solide (au moins sur des échelles de temps pas trop longues), et pour­tant les molécules du verre ne s’alignent pas dans un ordre cristallin, mais se figent dans des posi­tions aléa­toires, un peu comme si on restreignait les mou­ve­ments molécu­laires d’un liq­uide, ne lais­sant plus à chaque molécule que la pos­si­bil­ité de petites vibra­tions dans la cage créée par ses voisines, en sup­p­ri­mant le mou­ve­ment col­lec­tif qui per­met à l’eau de couler. 

En avançant dans la com­préhen­sion de ces phas­es vit­reuses, les physi­ciens et math­é­mati­ciens ont dévelop­pé un impres­sion­nant cor­pus de con­cepts et de méth­odes. Pour saisir la dif­fi­culté, on peut trans­pos­er le prob­lème en étu­di­ant des com­porte­ments émer­gents d’agents qui déci­dent d’acheter ou ven­dre sur un marché financier. 

Si tous les agents suiv­ent la même stratégie, l’analyse est assez sim­ple : on con­sid­ère un « agent représen­tatif », et l’effet des autres agents sur le résul­tat de sa pro­pre stratégie est pris en compte en se dis­ant que, juste­ment, les autres agents sont aus­si dans le même cas que lui. Une rela­tion d’autocohérence per­met alors de com­pren­dre le fonc­tion­nement du marché. 

En physique, c’est la théorie du champ moyen, inven­tée par Pierre Weiss en 1907, qui rend compte ain­si des tran­si­tions de phas­es ordi­naires. Dans les sys­tèmes désor­don­nés c’est une tout autre affaire : chaque agent suit sa pro­pre stratégie, on ne peut pas étudi­er un seul agent représen­tatif, on doit dévelop­per une étude sta­tis­tique car le com­porte­ment moyen d’un indi­vidu n’apporte pas d’information suff­isante. C’est ce qui a été fait pour l’étude des ver­res de spin (des sys­tèmes mag­né­tiques présen­tant des phas­es vit­reuses), et les méth­odes dévelop­pées dans ce con­texte ont trou­vé des appli­ca­tions dans des domaines très var­iés, de la finance à la biolo­gie en pas­sant par l’informatique.

La théorie des ver­res de spin, motivée à l’origine par des com­porte­ments anor­maux comme le vieil­lisse­ment de ces matéri­aux dont on n’a trou­vé aucune appli­ca­tion, dévelop­pée par pure curiosité intel­lectuelle, est sou­vent com­parée à une corne d’abondance.

LA THÉORIE DE L’INFORMATION, NOUVEAU CHAMP DE RECHERCHE

Un des champs de recherche majeurs où l’on ren­con­tre ces phénomènes d’émergence et de tran­si­tions de phas­es est la théorie de l’information. Fondée par Claude Shan­non en 1948, avec en tête des ques­tions très con­crètes de télé­com­mu­ni­ca­tions, elle s’est trans­for­mée désor­mais en un champ sci­en­tifique fer­tile et pro­fond, aux ram­i­fi­ca­tions actuelles essen­tielles dans de nom­breux domaines où inter­vi­en­nent les notions de stock­age, de trans­fert et de manip­u­la­tion d’information.

Claude Shannon, né en 1916, est le père de la théorie de l’information.
Claude Shan­non, né en 1916, est le père de la théorie de l’information.

Que l’on songe par exem­ple au trans­fert d’information de la rétine au cerveau et à sa manip­u­la­tion entre les dif­férentes aires du cor­tex visuel pour extraire d’une image un con­tenu, ou bien, tou­jours en biolo­gie, à la trans­mis­sion d’information géné­tique d’une cel­lule à ses filles lors de la divi­sion cellulaire. 

Ce domaine sci­en­tifique, qui tra­verse les dis­ci­plines, devient d’importance cap­i­tale de nos jours avec l’arrivée de don­nées mas­sives et la quête de bons algo­rithmes pour en extraire l’information per­ti­nente via les tech­niques d’apprentissage machine. 

BRUIT ET INTÉGRITÉ DE L’INFORMATION

Comme pre­mier exem­ple pen­chons-nous sur un des sujets mis en avant par Shan­non lui-même : l’utilisation des codes de cor­rec­tion d’erreurs pour trans­met­tre de l’information. Dès que le canal de trans­mis­sion est bruité, ce qui est tou­jours le cas, qu’il s’agisse de récupér­er des don­nées mesurées par un satel­lite, de télé­phon­er, de stock­er un doc­u­ment sur son disque dur ou tout sim­ple­ment de par­ler à quelqu’un, pour que la per­son­ne qui reçoit le mes­sage puisse com­pren­dre le mes­sage qui lui est trans­mis, il faut utilis­er ce qu’on appelle un code cor­recteur, c’est-à-dire en pra­tique envoy­er un mes­sage redondant. 

C’est le cas lorsque je v**s p*rle ou l*rsqu* j’é*ris : le lan­gage est redon­dant (on peut mon­tr­er qu’il con­tient à peine plus d’un bit d’information par let­tre envoyée, très en dessous des 4,7 bits par let­tre cor­re­spon­dant aux pos­si­bil­ités offertes par les com­bi­naisons des 26 let­tres de l’alphabet si on n’utilisait pas les seuls mots du dic­tio­n­naire), et cette redon­dance vous per­met de cor­riger des fautes de pronon­ci­a­tion ou des fautes de frappe. 

Pour com­pren­dre le mécan­isme du codage par redon­dance, on peut con­sid­ér­er le code le plus sim­ple, dit par répéti­tion : pour trans­met­tre le « mot » 1101, on envoie trois fois chaque bit, donc 111111000111. Avec 10 % de bruit sur la ligne on va altér­er un bit sur dix, et recevoir par exem­ple 110111010111 ; le décodage (par majorité au sein de chaque triplet) est évi­dent : dans ce cas il per­met de retrou­ver l’information trans­mise, au prix d’une redon­dance d’un fac­teur 3. 

Mais un tel code, dit code par répéti­tion, ne peut pas cor­riger toutes les erreurs : il reste tou­jours une cer­taine prob­a­bil­ité que le code ne restitue pas le mot d’origine, c’est le cas si le bruit a retourné deux bits d’un même triplet. 

SUDOKU GÉANT

La grande décou­verte de Shan­non est qu’il existe des codes qui savent cor­riger toutes les erreurs, lorsque le niveau de bruit est inférieur à un seuil critique. 

Sudoku géant
Le « jeu » du décodage s’apparente à un sudoku géant. © JULIASUDNITSKAYA / FOTOLIA.COM

La con­struc­tion des meilleurs codes de cor­rec­tion d’erreurs, per­me­t­tant d’atteindre les per­for­mances idéales prévues par Shan­non, a énor­mé­ment pro­gressé ces dernières années. Ces codes sont fondés sur une redon­dance col­lec­tive impli­quant un grand nom­bre de bits à la fois. 

En un sens, le « jeu » du décodage s’apparente à un sudoku géant : il faut retrou­ver le sig­nal envoyé, à par­tir d’une ver­sion bruitée de ce sig­nal qu’on a reçue, en util­isant la con­nais­sance du code, qui se traduit en une série de con­traintes reliant les bits envoyés. La grande dif­fi­culté était de trou­ver des algo­rithmes de décodage effi­caces, alors que la dynamique à l’œuvre dans ces algo­rithmes, manip­u­lant beau­coup de bits à la fois, est juste­ment sujette à des phénomènes émer­gents et à des tran­si­tions de phas­es qui lim­i­tent leurs performances. 

C’est désor­mais chose faite, et cer­taines caté­gories de codes atteignent des per­for­mances proches du seuil idéal de Shan­non, grâce à un ensem­ble d’idées qui sont intime­ment liées à la physique des ver­res de spin : le rôle des molécules est joué par les bits d’information, leurs inter­ac­tions sont les con­traintes du code, et on cherche à accélér­er une dynamique qui est celle de l’algorithme de décodage. 

COMPRESSION DE L’INFORMATION

Un autre exem­ple récent de cette fer­til­i­sa­tion croisée entre dis­ci­plines est celui de l’acquisition com­primée en traite­ment du sig­nal. Cha­cun sait désor­mais que l’information peut être com­primée. Pour stock­er une image, on peut décider d’utiliser un algo­rithme de com­pres­sion qui certes fera per­dre un peu de réso­lu­tion, si l’on cherche un jour à zoomer sur un détail, mais qui per­me­t­tra de garder l’essentiel, en économisant l’espace mémoire. 

Dans une base appro­priée, l’image est « parci­monieuse » : un bon nom­bre de ses com­posantes sont presque nulles (par exem­ple, dans une trans­for­mée en ondelettes, on utilise la somme et la dif­férence de deux pix­els voisins, et cette dernière est sou­vent très petite, dès lors que les deux pix­els sont dans une même zone presque uniforme). 

COMPRESSION DU SIGNAL

RMN
On peut espér­er acquérir une image de RMN en accélérant le proces­sus d’un fac­teur 3 ou 4. © SFAM_PHOTO / SHUTTERSTOCK.COM

Peut-on exploiter cette pro­priété pour acquérir le sig­nal en faisant un nom­bre de mesures min­i­mal ? Pour une pho­to, cela reviendrait à se dis­penser de la dou­ble étape : mesure de chaque pix­el, puis com­pres­sion infor­ma­tique, et la rem­plac­er par une acqui­si­tion du sig­nal directe­ment sous forme com­primée. Si cela présente peu d’intérêt pour nos pho­tos de famille, on peut en revanche espér­er acquérir une image de RMN en accélérant le proces­sus d’un fac­teur 3 ou 4, aug­men­tant d’autant l’efficacité de nos dis­posi­tifs d’imagerie médi­cale, ou bien dimin­uer l’irradiation lors de l’examen par micro­scopie de molécules biologiques. 

Rien de sur­prenant à ce que l’acquisition com­primée soit dev­enue un thème majeur en traite­ment de sig­nal dans la dernière décennie. 

PLUS DE VARIABLES QUE D’ÉQUATIONS

À pre­mière vue, le prob­lème de l’acquisition com­primée peut sem­bler insur­montable : il s’agit en effet de recon­stituer un sig­nal en faisant un nom­bre de mesures inférieur au nom­bre d’inconnues. Dans le cas très étudié où les mesures sont des com­bi­naisons linéaires des com­posantes du sig­nal, on a donc affaire à un sys­tème linéaire mal con­di­tion­né : il com­porte moins d’équations (les mesures) que de vari­ables (les com­posantes du signal). 

Com­ment faire dans ce cas ? En cher­chant une solu­tion où un cer­tain nom­bre de vari­ables sont nulles. 

UN INTENSE TRAVAIL THÉORIQUE

La théorie de l’information nous enseigne que, lorsqu’on mesure des sig­naux parci­monieux, dès lors que le nom­bre de mesures est supérieur au nom­bre de vari­ables non nulles, il existe en principe une solu­tion per­me­t­tant de retrou­ver le sig­nal d’origine.

Reste à trou­ver une méthode pour attein­dre cet objec­tif. L’intense activ­ité théorique sur ce sujet a en effet porté ses fruits. Pour réus­sir à recon­stru­ire un sig­nal à par­tir d’un petit nom­bre de don­nées, il faut avant tout que chaque mesure porte sur un grand nom­bre de com­posantes du sig­nal (au lieu de regarder une image pix­el par pix­el, on utilis­era un verre dépoli), et on doit ensuite utilis­er un puis­sant algo­rithme de reconstruction. 

Dans une des approches les plus récentes, on cherche le sig­nal comme la com­bi­nai­son la plus prob­a­ble, prenant en compte les con­traintes dues aux mesures et favorisant la parcimonie. 

Galilée
Galilée est un des pères de la démarche scientifique.

SÉRENDIPITÉ

Lorsqu’ils réfléchissaient aux verres de spin il y a trente ans, jamais les physiciens n’auraient pensé que leur savante théorie des systèmes désordonnés s’appliquerait un jour à des problèmes majeurs de théorie de l’information, où la dynamique vitreuse n’est pas liée au mouvement des atomes mais à des algorithmes de reconstruction de signaux.
Bel exemple de ce qu’on appelle la sérendipité.

ANALOGIE AVEC LES ÉTATS CRISTALLINS

Le sig­nal d’origine, celui que l’on cherche à recon­stru­ire, est bien le plus prob­a­ble. Mais, dans un prob­lème typ­ique qui peut com­porter des cen­taines de mil­liers voire des mil­lions de vari­ables, le retrou­ver n’a rien de sim­ple. C’est en fait comme trou­ver un état « cristallin » dans un sys­tème physique : le rôle de la posi­tion des atom­es est ici joué par les com­posantes du sig­nal, les inter­ac­tions entre atom­es sont les con­traintes dues aux mesures ; il existe un état cristallin opti­mum, et pour le trou­ver on peut utilis­er des algo­rithmes de champ moyen, notre fameuse sta­tis­tique des « agents », appliquée ici aux com­posantes du sig­nal. L’analogie avec le sys­tème physique va très loin. 

En effet, l’application directe de ces principes se heurte à l’existence d’une phase vit­reuse : l’algorithme n’arrive pas à recon­stru­ire l’ensemble du sig­nal, au lieu de trou­ver un cristal sa dynamique se ralen­tit et il se fige dans un état vit­reux éloigné du sig­nal d’origine. Il faut alors appli­quer un autre principe physique : en util­isant une matrice de mesure struc­turée, l’algorithme parvient à créer un germe de cristal à par­tir duquel se propage une onde de cristalli­sa­tion, recon­stru­isant le sig­nal désiré, jusqu’au seuil prédit par Shannon. 

DE NOUVEAUX OUTILS STATISTIQUES

Les suc­cès dans la recon­struc­tion de « sig­naux parci­monieux » ouvrent des per­spec­tives qui vont bien au-delà de l’acquisition com­primée, et pro­posent une nou­velle évo­lu­tion de la démarche sci­en­tifique. Dans sa forme générique établie depuis, dis­ons, Galilée, celle-ci procède par hypothès­es, par con­struc­tion de mod­èle, et par véri­fi­ca­tion expéri­men­tale du modèle. 

Éléphant
Avec 5 paramètres, on peut faire bouger la trompe de l’éléphant.
© JIMLARKIN / FOTOLIA.COM

Dans cette phase de véri­fi­ca­tion, on s’appliquera à déter­min­er les divers paramètres du mod­èle, ce qui n’est pos­si­ble habituelle­ment que lorsque le nom­bre de paramètres est assez petit, en tout cas bien plus petit que le nom­bre de mesures (on se sou­vient de la boutade de John von Neu­mann : pour expli­quer un phénomène, avec un fit à qua­tre paramètres je peux fit­ter un éléphant, et avec cinq paramètres je peux lui faire bouger la trompe). 

La démarche que nous avons décrite est un peu dif­férente : même en l’absence de mod­èle, on peut intro­duire des cen­taines ou des mil­liers de paramètres, tout en exigeant du fit qu’il soit parci­monieux : il devra donc met­tre un cer­tain nom­bre de paramètres à zéro, et ne garder que les paramètres les plus per­ti­nents statistiquement. 

C’est ain­si l’analyse sta­tis­tique elle-même qui peut apporter l’information sur les paramètres à con­sid­ér­er en pri­or­ité, amenant à réfléchir ensuite sur la con­struc­tion d’un modèle. 

Con­traire­ment à ce qui est par­fois dit, l’irruption des don­nées mas­sives dans l’étude des sys­tèmes com­plex­es ne va pas se sub­stituer à la théorie. Il est tou­jours aus­si néces­saire, et de plus en plus dif­fi­cile, de com­pren­dre, analyser, con­stru­ire un mod­èle, mais le théoricien peut s’appuyer sur de nou­veaux out­ils sta­tis­tiques extrême­ment performants.

Poster un commentaire