Catégorie : Mathématiques

  • Science du qubit, science des données

    Un nouvel « Entretien autour de l’informatique ». Serge Abiteboul et Claire Mathieu interviewent Julia Kempe. Julia est une brillante mathématicienne, physicienne, et informaticienne. C’est une des meilleures spécialistes mondiales en informatique fondamentale et, en particulier, en informatique quantique. A partir de l’automne, elle dirigera le Center for Data Science de New York University. Cet article est publié en collaboration avec The Conversation.
    Julia Kempe, CDS

    Binaire : tu es une scientifique très cosmopolite. Peux-tu nous raconter un peu d’où tu viens ?

    Je suis née en Allemagne de l’Est, d’origine russe et allemande. Je suis allée dans une école spécialisée en maths en Allemagne de l’Est à l’âge de 14 ans. Nous avions déjà des cours de programmation. Quand le mur est tombé, je suis allée en Autriche et j’ai étudié les maths et la physique à Vienne, avec un semestre en Australie dans un programme d’échange. Puis je suis allée en France où j’ai fait un DEA d’Algèbre à Paris 6, en géométrie algébrique. Mais mes intérêts ont toujours été pluridisciplinaires, et j’ai enchainé avec un DEA de physique théorique à l’École Normale Supérieure. Et puis, il y a eu la découverte par Peter Shor du premier algorithme quantique. Dans les années 90, j’ai passé deux thèses en même temps, une en maths à Berkeley, et l’autre en informatique à Télécom Paris avec Gérard Cohen, toutes les deux sur des aspects des calculs quantiques. Ensuite, j’ai eu un poste au CNRS en informatique. J’ai eu la chance de travailler dans l’équipe de Miklos Santha à Orsay. À l’époque, l’informatique quantique était encore un domaine tout nouveau. En 2007, je suis partie pour 4 ans en Israël comme professeur d’informatique à l’université de Tel-Aviv. Puis je suis rentrée en France, et un peu plus tard j’ai rejoint un fonds d’investissement américain. Ma culture scientifique générale y a été très utile même si mes compétences en informatique quantique ne servaient pas. Récemment, j’ai pris un poste de professeur d’informatique à New York University ; je serai directrice du Centre de Sciences des Données.

    B : tu es mathématicienne, informaticienne, physicienne. Si on te demandait de choisir entre les trois ?

    Je n’ai pas à choisir. Ce qui m’a attiré à l’informatique, c’est la rigueur, la précision que cela exige, comme en mathématiques. En informatique, on réalise des choses concrètes, des calculs, et j’aime ça. Et puis, les méthodes que l’on développe et les problèmes que l’on traite viennent de domaines très divers. C’est une grande aide pour moi que d’avoir des connaissances dans plusieurs disciplines. D’une part ça m’aide à comprendre les domaines d’application dans lesquels je travaille, et d’autre part, j’ai plus de facilité à travailler avec des personnes de ces domaines, qui ont toutes des cultures différentes.

    Représentation d’un qubit par une sphère de Bloch.

    B : pourrais-tu expliquer simplement l’informatique quantique ?

    L’informatique classique est fondamentalement basée sur le traitement de signaux binaires. L’état d’un interrupteur ou d’un bit en mémoire est soit 0 soit 1. En mécanique quantique, les particules quantiques se trouvent dans un état qu’on appelle « superposé », c’est un peu 0 et un peu 1. On appelle qubit ces bits quantiques qui sont à la fois dans l’état 0 et dans l’état 1. Quand on cherche à observer un qubit, on va trouver soit un 0 ou un 1. L’observation a changé l’état de la particule en choisissant entre les deux.

    B : le but c’est d’arriver à réaliser beaucoup de calculs en parallèle ?

    Avec un vecteur de n qubits, on a en même temps 2n valeurs. Si on arrive à faire des calculs avec de tels vecteurs, on arrive en quelque sorte à faire tous les calculs en même temps. C’est comme si on réalisait 2n calculs « en parallèle ». Le problème c’est qu’à la fin, il se peut qu’il n’y ait qu’un seul de ces calculs qui ait réussi, et c’est son résultat qui nous intéresse . Ce résultat est quelque part et la difficulté, c’est de l’isoler. L’art des algorithmes quantiques est d’effacer de façon judicieuse tous les calculs qui n’ont pas abouti.

    B : est-ce que, avec le quantique, on pourrait arriver à réaliser rapidement des calculs comme la factorisation ?

    L’algorithme de Shor explique comment factoriser de grands nombres en facteurs premiers de manière efficace. On ne sait pas faire cela avec l’informatique classique. Les algorithmes qu’on connaît prennent un temps exponentiel. D’ailleurs, une grande partie de la cryptographie très utilisée dans nos vies quotidiennes est basée sur le fait qu’on ne sait pas factoriser rapidement un nombre premier. Ce problème de factorisation, on arrive à le résoudre dans le modèle quantique avec l’algorithme de Shor. Évidemment, pour que cela devienne réalisable en pratique, il faudrait savoir construire un ordinateur quantique qui manipule des grands nombres de qubits. On n’y est pas encore.

    P, NP, PSPACE sont des classes de problèmes de complexité classiques BQP : problèmes qui peuvent être résolus en temps polynômial par un algorithme quantique avec une erreur bornée

    B : est-ce que l’informatique quantique remet en cause la théorie de la complexité traditionnelle de l’informatique ?

    La théorie de la complexité étudie ce qu’on peut faire avec un ordinateur étant donné des ressources limitées en temps et en espace. On peut faire des études comparables à partir d’un modèle quantique. Un travail de recherche passionnant actuellement, c’est que certaines classes de complexité quantique sont équivalentes à des classes classiques. On obtient aussi des résultats de réductions passionnants comme : « si un problème peut être résolu dans modèle classique avec une complexité particulière, alors il peut aussi l’être dans le modèle quantique avec telle complexité. » Il y a tout un panorama de classes de complexité. C’est vrai que, comme en complexité classique, ce n’est pas simple de « séparer » les classes de complexité.

    B : voit-on arriver ces ordinateurs quantiques ? Y a-t-il des résultats concrets pratiques ?

    Quand j’ai commencé, à la fin des années 90, les expérimentateurs prédisaient un ordinateur quantique dans 10 ans ; les plus prudents parlaient de 20 ans. Il s’est déjà passé vingt ans et on attend toujours ! En réalité, dans le monde de la recherche, quand on vous dit dans 10 ans, il faut souvent comprendre : « je n’en sais rien ». Malheureusement il y a eu beaucoup de survente. Les ordinateurs quantiques ne savent même pas encore factoriser des chiffres autour de 10 000 à cause de l’accumulation des erreurs. Nous avons encore des problèmes à régler avant d’arriver à quelque chose d’intéressant. On est encore très loin de pouvoir utiliser l’algorithme de Shor.

    B : mais est-ce qu’on avance ?

    Oui ! Vraiment. Nous sommes dans une période de transition car nous assistons à des tentatives concrètes de Google, d’IBM… Avec des machines à 50 qubits. C’est passionnant car, à partir de grosso modo 50, nous arrivons à des phénomènes qu’on ne peut plus simuler avec des ordinateurs classiques ; 250, c’est à peu près leur limite.
    Si on ne sait pas encore faire un ordinateur quantique général, on pourrait utiliser les machines quantiques qu’on sait construire pour simuler des phénomènes physiques qu’on ne sait pas simuler autrement actuellement.

    B : qu’est-ce qui t’a fait choisir de vivre aux USA ?

    Il y avait beaucoup de paramètres. J’aime vivre en France mais je voulais faire quelque chose de nouveau, travailler dans un fonds d’investissement, et pour cela, New York, c’était le bon endroit. Je ne pensais pas y rester six ans. J’avais de jeunes enfants et avec de jeunes enfants, c’est difficile de faire une recherche qui demande de s’immerger dans des problèmes complexes de façon prolongée. Je n’exclus pas de revenir en France, mais pour l’instant l’occasion ne s’est pas présentée.

    B : ce travail dans les fonds d’investissement est–il aussi un travail scientifique ?

    Nous utilisons une approche « quantitative » des fonds d’investissement. Nous partons de téraoctets de données financières. Nous remplaçons les intuitions des traders des années 80 par de l’analyse scientifique de données. Nous développons des théories, des modèles, et nous les testons pour détecter des signaux qui nous permettent de prédire les évolutions des marchés financiers. La difficulté est que les données dont nous disposons ne sont jamais parfaites. C’est tout un art de les nettoyer pour en extraire les informations pertinentes. C’est de la science des données. Cela ressemble beaucoup à un travail universitaire mais nous ne publions pas et le critère ultime de succès pour nous, c’est si ça rapporte de l’argent. Mes collègues sont, pour beaucoup, mathématiciens ou physiciens, et c’est une grande aide pour moi que d’avoir fait des études pluri­dis­ci­plinaires.

    B : ce genre de travail existe-t-il aussi en France ?

    Oui, en France il y a en particulier CFM, un fonds d’investissement dirigé par un physicien, Jean-Philippe Bouchaud, avec de nombreux employés qui viennent du monde de la physique statistique. Ils retrouvent finalement des méthodes assez semblables à celles qu’ils utilisaient en physique, avec les expérimentations, la définition de modèles mathématiques, l’analyse de données, la simulation, la validation des résultats à la lumière de la réalité des données, etc.

    Un problème particulier assez classique que nous rencontrons est celui du « sur-apprentissage » (overfitting en anglais). Avec suffisamment de paramètres, je peux ajuster les paramètres du modèle de façon à correspondre exactement aux données disponibles. Seulement, le modèle peut être trop exactement ajusté aux exemples et ne pas s’adapter aux données futures. On est un peu comme les astrophysiciens : ils ont une seule donnée, l’univers tel qu’il existe, et nous n’avons que les données financières sur une seule réalisation du monde financier tel qu’on l’observe. Comme les astrophysiciens, il faut faire avec. Et si on a fait du sur-apprentissage, on va juste rater une évolution du marché qui ne s’est pas passée exactement comme dans le passé…

    C’est facile de se tromper. Le temps de demi-vie d’un fonds d’investissement est de 18 mois en moyenne, parce que des erreurs sont faites, souvent à cause de sur-apprentissage.

    B : que vas-tu faire à NYU ?

    Je vais faire de la recherche en science des données. Je vais essayer d’appliquer, par exemple, mes compétences sur le traitement du bruit à des données autres que financières.

    B : quelle est la présence féminine dans ces domaines ?

    Dans le fonds d’investissement, nous étions 2 femmes chercheuses sur 55. Au CDS (centre de sciences des données), nous sommes entre 1/4 et 1/3 de femmes. Il y a un nombre relativement élevé de femmes en sciences des données, plus que dans d’autres domaines de l’informatique. Je crois que l’aspect pluridisciplinaire attire les femmes. Et comme les chercheurs en data science sont habitués à une diversité de disciplines scientifiques, cela les rend peut-être plus ouverts à une diversité des genres.

    B : as-tu un conseil à donner aux étudiants ?

    Nous vivons un temps où il y a beaucoup de données numériques, de plus en plus de calculs sur ces données. Chacun doit apprendre à se servir de ces données, et en même temps à être prudent avec elles. Il faut par exemple être conscient des problèmes de biais qui peuvent exister dans des données dont on se sert dans des domaines critiques.

    Je pense que les étudiants dans toutes les disciplines devraient avoir une solide expérience de programmation et maitriser la compréhension des données numériques.

    Entretien réalisé par Serge Abiteboul et Claire Mathieu

    Références

  • Les selfies de binaire : Antoine

    Nous poursuivons notre série de selfies de l’équipe de binaire pour que vous puissiez découvrir la diversité des parcours qui sont les nôtres et avoir ainsi une meilleure connaissance de celles et ceux qui s’adressent à vous. Après Thierry, Pascal, c’est au tour d’Antoine Rousseau de se présenter.

    AntoineAntoine Rousseau
    Chercheur en mathématiques appliquées

     

    Ton parcours

    J’ai grandi du côté de Cherbourg avant de partir à Nantes pour mes classes préparatoires (j’avais la trouille d’aller à Paris), puis à Orsay pour la suite (et la fin !) de mes études. J’ai fait deux belles rencontres au cours de ces années : mon prof de maths spé, Hubert Caparros, et mon directeur de thèse Roger Temam. Je leur dois beaucoup ! Issu d’une famille de musiciens et de médecins, je suis arrivé un peu par hasard aux mathématiques. Comme j’étais plutôt bon élève, on peut donc dire que j’ai fini 1er dans un concours de circonstances. Je suis du genre à me laisser porter : c’est comme ça qu’on m’a proposé un post-doc à l’INRIA en 2005 ; et j’y suis resté (jusqu’à aujourd’hui en tout cas !)

    Ton domaine de recherche

    Quelques processus en sciences de l’environnement. Source : P. Rekacewicz, Le Monde Diplomatique

    Je suis mathématicien. En France, les mathématiques sont « rangées » en 10 catégories : les maths pures et les maths appliquées. Même si je n’aime pas trop cette distinction, je me place clairement dans la seconde catégorie. Et moi les maths, je les applique en sciences de l’environnement. En fait, c’est un domaine à l’interface de beaucoup de disciplines : on traduit en équations des phénomènes naturels (ou pas) en discutant avec des physiciens, on étudie les propriétés de ces équations avec les matheux et puis on transforme ces équations en logiciels de simulation avec les informaticiens. Du coup je suis un mathématicien très proche du numérique, c’est pourquoi j’ai beaucoup de points communs avec les co-éditeurs de ce blog. Mes contributions sont essentiellement autour du couplage entre les modèles, qui ont lieu à différentes échelles spatiales et temporelles.

    Quelle est l’évolution de ton domaine ?

    C’est toujours difficile d’estimer l’évolution actuelle du domaine. Ce que je peux dire, c’est qu’il y a 20 ans, nous avons vécu une première révolution autour des données. Grâce à des méthodes d’optimisation développées notamment en France par François-Xavier Le Dimet, on a permis aux prédictions des modèles de s’améliorer sensiblement en intégrant des corrections effectuées grâce aux données : ça s’appelle l’assimilation de données. En gros, avant, on ne faisait confiance qu’aux modèles, maintenant c’est un mélange modèles + données. Bien sûr avec les outils récents de machine learning on peut se demander si les données ne vont pas bientôt permettre de tout faire : ça serait une seconde révolution, mais je n’y crois qu’à moitié. On pourra peut-être prédire beaucoup de choses mais pour comprendre les phénomènes, on aura toujours besoin de modèles…

    Le plus et le moins dans ton activité de recherche

    Le plus : sans aucun doute l’interdisciplinarité. C’est génial de pouvoir dialoguer et collaborer avec des femmes et des hommes de disciplines aussi variées, avec les maths au milieu.
    Le moins : sans aucun doute l’interdisciplinarité 😉 Quand on est à l’interface de deux domaines (ou plus !) on ne peut pas être « à moitié bon » dans chacun des domaines. Il faut, comme le disait Jacques-Louis Lions, être bon dans les deux. Lui l’était sans aucun doute !

     

  • Coïncidences surprenantes, mais banales

    © Pour la Science où Jean-Paul écrit régulièrement.

    Nous avons publié récemment un article expliquant pourquoi les pics de naissances se rencontrent en septembre. Les chercheurs avaient exploité, de façon pertinente, des corrélations entre évènements en utilisant des informations issues de Google trends. Cependant, il nous arrive de voir dans certaines coïncidences des phénomènes incroyables et à leur rechercher d’impossibles explications. L’introduction généralisée des méthodes et des outils d’extraction d’information a amplifié ce risque et il convient donc de les utiliser avec clairvoyance. Jean-Paul Delahaye va nous aider à décrypter ce phénomène. Ce texte est extrait d’un article plus long publié dans Pour la Science (novembre 2017, n° 481, pp. 108-113) et que nous vous invitons à lire. Pascal Guitton & Thierry Viéville.

    Il est vrai que, en moyenne dans une école primaire, plus les élèves lisent rapidement, plus ils sont grands. En conclurons-nous qu’apprendre à lire fait grandir ? Plus sérieusement, une étude statistique de Franz Messerli, de l’université Columbia, menée avec toute la rigueur méthodologique nécessaire et publiée en 2012 dans la revue New England Journal of Medicine, a établi qu’il existe une étroite corrélation entre la consommation de chocolat par habitant d’un pays et le nombre de prix Nobel obtenus par ce pays par million d’habitants. En déduirons-nous que les chercheurs doivent manger du chocolat pour augmenter leurs chances de se voir attribuer le fameux prix ?

    L’explication ne serait-elle pas plutôt que le système social et éducatif des pays riches favorise la bonne recherche et donc l’attribution des prix Nobel, et que cette même richesse favorise l’achat par tous de chocolat ? Les deux faits sont bien liés, mais seulement parce qu’ils sont la conséquence d’une même cause, pas parce que l’un implique l’autre. Quand deux faits sont corrélés, cela ne signifie pas que l’un est la conséquence de l’autre, mais parfois seulement qu’un troisième facteur les entraîne tous les deux. La recherche des liens de causalité entre faits doit être menée avec précaution (voir l’article d’Isabelle Drouet, « Des corrélations à la causalité », Pour la Science n°  440, juin 2014).

    Du hasard pur ?

    Hormis ces situations où, malgré tout, la corrélation repérée a une explication satisfaisante faisant intervenir un troisième facteur, tel que l’âge ou la richesse économique, il existe des cas où, en définitive, la seule explication est le hasard. Les quelques exemples donnés par la figure ci-dessous permettent de comprendre ce que cela signifie. Ces corrélations illusoires ont été minutieusement collectées par Tyler Vigen quand il était étudiant à la faculté de droit de Harvard, à Cambridge dans le Massachusetts. Il travaille aujourd’hui au Boston Consulting Group et a publié un livre avec ses amusantes découvertes (voir la bibliographie et les sites http://www.tylervigen.com/spurious-correlations ou http://tylervigen.com/old-version.html).

    L’observation sur un même graphique de la courbe indiquant année après année le nombre de suicides aux États-Unis par pendaison ou suffocation et de la courbe indiquant année après année les dépenses de recherches scientifiques américaines est particulièrement troublante. Quand l’une des courbes baisse ou monte, l’autre la suit en parallèle. La synchronisation est presque parfaite. Elle se traduit en termes mathématiques par un coefficient de corrélation de 0,992082, proche de 1, le maximum possible. Cela établit-il qu’il existe un lien véritable entre les deux séries de nombres ?

    Des corrélations étonnantes mais fortuites, aux états-unis © Pour la Science

    Cela est si peu vraisemblable qu’il faut se rendre à l’évidence : c’est uniquement le fait du hasard, ou comme on le dit, une coïncidence. La seule façon raisonnable d’expliquer le parallélisme des deux courbes et des nombreux cas du même type proposés par Tyler Vigen est la suivante :
    –  Il a collecté un très grand nombre de séries statistiques.
    – Il a su les comparer systématiquement, ce qui lui a permis d’en trouver ayant des allures similaires, d’où des coefficients de corrélation proches de 1.
    – On ne doit pas s’en étonner : c’était inévitable du fait du très grand nombre de séries numériques pris en compte.

    La quantité de données de base est l’explication et Tyler Vigen a détaillé sa méthode : après avoir réuni des milliers de séries numériques, il les a confiées à son ordinateur pour qu’il recherche systématiquement les couples de séries donnant de bons coefficients de corrélation ; il a ensuite fait appel aux étudiants de sa faculté pour qu’ils lui indiquent, par des votes, les couples de courbes jugés les plus spectaculaires parmi ceux présélectionnés par l’ordinateur.

    Cette façon de procéder porte en anglais le nom de data dredging, que l’on peut traduire par « dragage de données ». Il est important d’avoir conscience des dangers que créent de tels traitements, surtout aujourd’hui où la collecte et l’exploitation de quantités colossales d’informations de toutes sortes sont devenues faciles et largement pratiquées. La nouvelle discipline informatique qu’est la fouille de données (en anglais, data mining) pourrait être victime sans le savoir de ces corrélations illusoires : sans précaution, elle peut prendre ces dernières pour de véritables liens entre des séries de données en réalité totalement indépendantes.

    Une victime : la recherche médicale.

    La recherche médicale est fréquemment confrontée au problème de telles corrélations douteuses. Dans un article de 2011, Stanley Young et Alan Karr, de l’Institut américain d’études statistiques, citaient 12 études publiées qui établissaient de soi-disant liens entre la consommation de vitamine et la survenue de cancers. Ces études avaient parfois été réalisées en utilisant un protocole avec placebo et mesure en double aveugle, et semblaient donc sérieuses. Pourtant, quand elles ont été reprises, dans certains cas plusieurs fois, les nouveaux résultats ont contredit les résultats initiaux. Outre que la tentation est grande d’arrondir un peu les chiffres pour qu’ils parlent dans un sens bien clair et permettent la publication d’un article, il se peut simplement que les auteurs de ces travaux aux conclusions impossibles à reproduire aient été victimes d’une situation de mise en corrélation illusoire, comme Tyler Vigen en a repéré de nombreuses.

    Ce hasard trompeur provenant de l’exploration d’un trop grand nombre de combinaisons est une erreur de jugement statistique. On se trompe en croyant qu’une observation est significative et doit donc être expliquée, alors qu’elle devait se produire (elle ou une autre du même type) du fait du grand nombre d’hypothèses envisagées, parfois collectivement par l’ensemble des équipes de recherche, dans la quête de régularités statistiques.

    Data snooping

    Cette illusion est proche de celle dénommée data snooping (« furetage discret de données ») que l’on peut utiliser pour des tromperies délibérées. Pour en illustrer le fonctionnement, Halbert White, de l’université de Californie à San Diego, a suggéré la méthode suivante permettant à un journal financier d’augmenter le nombre de ses abonnés.

    La première semaine, le journal envoie un exemplaire gratuit à 20 000 personnes ; dans la moitié des numéros envoyés, il est écrit que l’indice boursier (par exemple le Dow Jones) va monter, dans l’autre moitié le journal affirme que l’indice va baisser. Selon que l’indice a effectivement monté ou baissé, le journal envoie la semaine suivante, aux 10 000 adresses qui ont reçu la bonne prévision, un second numéro gratuit, avec dans la moitié des exemplaires l’annonce pour la semaine suivante que l’indice va monter et dans l’autre moitié qu’il va baisser. La troisième semaine, le journal envoie 5 000 numéros gratuits à ceux qui ont reçu la bonne anticipation deux semaines de suite, etc.

    À chaque fois, le journal insiste sur le fait qu’il a correctement prévu la tendance depuis plusieurs semaines et propose un bulletin d’abonnement. Au bout de 10 semaines, il ne restera qu’une vingtaine d’envois à faire, mais pour être persuadé que le journal sait prédire la bonne tendance de l’indice boursier, rares sont les lecteurs potentiels qui attendent une prévision exacte 10 fois de suite. Par conséquent, un bon nombre de nouveaux abonnements auront été souscrits à mesure du déroulement des envois.

    Une autre situation de data snooping dans le traitement des données financières conduit à une navrante désillusion. On cherche des règles du type « Si aujourd’hui le cours de l’action A monte et que le cours de l’action B baisse et que…, alors le cours de l’action X montera demain ». On en écrit un grand nombre, voire on écrit toutes les règles de ce type comportant 10 éléments dans leurs prémisses. On sélectionne ensuite, à l’aide d’une série de données provenant du passé, les meilleures règles. On élimine toutes les règles qui se sont trompées avec les données passées, et on retient seulement celles qui ont toujours fourni une bonne prédiction, ou celles qui ont eu raison le plus souvent. On disposera alors inévitablement d’une série réduite de règles qui, si elles avaient été appliquées sur les données du test, auraient permis de gagner beaucoup d’argent… et qui pourtant ne rapporteront rien dans les semaines qui suivront leur mise en œuvre pour faire des achats et des ventes.

    Bien sûr, le piège est connu des chercheurs et des méthodes ont été mises au point pour ne pas être victime de l’illusion. On cherchera par exemple à évaluer, avant de mener la recherche des bonnes règles, la probabilité que lorsque les données sont tirées au hasard l’une des règles de la liste envisagée fonctionne avec ce hasard, et on s’assurera que cette probabilité est proche de zéro.

    Loterie truquée ?

    Qui peut considérer comme normal qu’à quelques jours de distance, la même série de 6 numéros sorte d’un tirage du Loto ? C’est pourtant ce qui se produisit le 10 septembre 2009 pour le Loto bulgare. La série 4, 15, 23, 24, 35, 42 n’a rien d’extraordinaire, sauf qu’elle avait déjà été tirée 6 jours auparavant, le 4 septembre, par le même Loto bulgare. Une coïncidence incroyable, au point que le ministre des Sports Svilen Neïkov demanda l’ouverture d’une enquête. Aucune tricherie n’a été détectée, et d’ailleurs les deux tirages avaient eu lieu devant les caméras de la télévision. La chose fut considérée si extraordinaire que la presse dans le monde entier rapporta l’événement.

    Plus étonnant peut-être, un an après, à un mois d’intervalle, le 21 septembre et le 16 octobre 2010, le Loto israélien sortit la série 13, 14, 26, 32, 33, 36, provoquant là encore l’étonnement mondial. Comme l’expliquait David Hand dans son article « Des coïncidences pas si étranges » (Pour la Science n°438, avril 2014), si l’on prend en compte le nombre de jeux de Loto dans le monde, et le nombre de tirages que chacun d’eux opère, souvent plusieurs fois par semaine, notre étonnement doit cesser.

    Plus précisément, considérons le Loto bulgare où l’on tire 6 numéros entre 1 et 49, ce qui donne une probabilité de gagner de 1/13 983 816. Demandons-nous combien de tirages sont nécessaires pour que l’événement « deux d’entre eux donnent le même résultat » ait une probabilité supérieure à 50 % de se produire. La réponse est 4 404.

    Le calcul est analogue à celui fait pour le célèbre paradoxe des anniversaires, selon lequel dès que 23 personnes sont réunies, la probabilité que deux d’entre elles aient la même date anniversaire dépasse 50 %. Cela montre que les événements ressentis comme extraordinaires pour les loteries bulgare et israélienne sont en fait nécessaires. Ce n’est pas la survenue des tirages identiques qui est improbable, mais l’inverse : si tous les tirages étaient toujours différents, nous devrions nous en étonner et en rechercher l’explication. Une autre source d’étonnements provient des séries rapprochées d’événements rares, tels que les accidents d’avion. Les journalistes aiment mentionner une prétendue «  loi des séries », pourtant inconnue des mathématiciens, qui expliquerait ces rapprochements jugés à la fois fortement improbables et explicables par cette introuvable loi. Jacques Chirac disait simplement : « Les emmerdes, ça vole toujours en escadrille !» Certaines analyses tentent d’en identifier l’origine en parlant d’une « attente excessive d’étalement » (voir mon article « Notre vision du hasard est bien hasardeuse », Pour la Science n°  293, mars  2002) : notre intuition nous souffle à tort que, par exemple, les dates des accidents d’avion doivent être régulièrement espacées, alors que les statistiques nous montrent autre chose. Cette attente excessive d’étalement a été clairement analysée dans les cas précis des accidents d’avions par Élise Janvresse et Thierry de la Rue, de l’université de Rouen.

    En août 2005, une série de cinq catastrophes aériennes s’est produite dans un intervalle de 22 jours, faisant plusieurs centaines de morts au total. Cela nous semble extraordinaire, mais l’est-ce vraiment ? Élise Janvresse et Thierry de la Rue proposent une belle analyse du problème dans leur petit livre La Loi des séries, hasard ou fatalité ? (Le Pommier, 2007). Ils concluent que la probabilité que, durant une année donnée, il se produise 5 accidents aériens graves ou plus dans une fenêtre de 22 jours est 11 %. C’est assez faible, mais cela rend la série malheureuse de 2005 peu étonnante, d’autant plus que le calcul mené ne prend pas en compte les variations saisonnières du trafic aérien qui, en concentrant les vols sur certaines périodes, augmentent le 11 % obtenu.

    Des séries très différents mais ayant la même statistique.

    Notre bon sens est défaillant pour traiter les probabilités et nous sommes surpris dans des cas où il n’y a pas lieu de l’être. Utiliser le mot « coïncidence » n’explique rien ou alors cela introduit des idées étranges comme la synchronicité de Carl Gustav Jung ou les champs morphiques de Rupert Sheldrake, dont les scientifiques ont vainement cherché à prouver l’existence (voir par exemple www.sceptiques. qc.ca/dictionnaire/).

    Simple et inattendu.

    Toujours afin de comprendre et de classifier les situations où notre esprit s’étonne alors qu’il ne devrait pas, détaillons à présent un cas moins connu, car lié à une théorie assez récente. La mauvaise compréhension de ce qui est probable, car simple, conduit à percevoir certains événements comme étonnants alors qu’ils ne le sont pas, et donc à croire être en présence de coïncidences miraculeuses sans bonne explication, alors que la situation est banale.

    La notion la plus générale de simplicité est celle qui provient de la théorie algorithmique de l’information. Comme nous n’en avons pas toujours une bonne compréhension, cela nous conduit à voir des choses complexes et inattendues quand il n’y a en fait que des choses simples. Cette théorie algorithmique de l’information, ou théorie de la complexité de Kolmogorov, mesure la complexité d’un objet par la taille du plus petit programme qui l’engendre. Elle s’applique aux objets numériques, ou susceptibles d’être représentés numériquement, tels que les images, les sons, les films, et à la plupart des objets du monde réel, si l’on ne prend en compte que leur apparence.

    La théorie suggère que parmi les objets utilisant le même nombre de bits d’information (par exemple des images d’un million de pixels), les plus simples, c’est-à-dire ceux ayant la plus faible complexité de Kolmogorov, sont ceux qu’on rencontrera le plus fréquemment.

    Une étoile est sphérique, comme le sont beaucoup de fruits. La section d’un tronc d’arbre est circulaire, comme le sont aussi les roues qui équipent nos véhicules. Une tige de blé est parfaitement rectiligne, comme les arêtes d’un cristal. La surface d’un lac est plane comme l’est, regardée de près, la peau de nombreux animaux. Tout cela correspond à des formes simples au sens de la théorie de Kolmogorov. Dans ces cas-là, nous ne cherchons donc pas à trouver une origine commune à deux objets sphériques, ou rectilignes, ou plans. Les formes simples n’ont pas nécessairement une origine commune, leur simplicité suffit à expliquer qu’on les retrouve partout. Jusqu’ici, tout va bien.

    En revanche, certains objets ou formes que la théorie de la complexité de Kolmogorov identifie comme simples ne sont pas perçus comme tels par notre jugement immédiat. De nombreuses structures fractales (dont le fameux triangle de Siepinski), nous apparaissent complexes alors qu’elles ne le sont pas puisque des programmes courts les engendrent. Rencontrer ces formes dans la nature (c’est le cas du triangle de Sierpinski qu’on trouve à la surface de certains coquillages) ne doit donc pas nous étonner plus que de rencontrer dans la nature des droites ou des cercles.
    Nous ne devons donc pas nous émerveiller de ces rencontres multiples sans lien, ni surtout imaginer qu’elles proviennent d’une sorte de fonctionnement secret de l’Univers qui resterait à comprendre. Comme pour la sphère, leur simplicité est l’explication de leur fréquente apparition.

    Il est normal que les objets de faible complexité de Kolmogorov se retrouvent partout. Rechercher une explication profonde à la présence multiple de la suite de Fibonacci dans toutes sortes d’objets naturels ou artificiels est aussi naïf que rechercher une explication commune à la présence de longs segments rectilignes dans les arbres, dans les tracés dessinés par les couches géologiques, les stalagmites ou dans le ciel quand une météorite pénètre l’atmosphère terrestre.

    Nous percevons facilement la simplicité de certaines formes, mais pour d’autres, il nous faut réfléchir à la théorie qui permet de comprendre la simplicité. Si nous réussissons, nous serons moins enclins à vouloir expliquer ce que nous percevons comme des coïncidences. Ici, comme pour les doubles tirages identiques au Loto, ou les courbes parallèles montrant des corrélations illusoires, nous devons éviter de rechercher des causes communes à ce qui, logiquement, n’en a pas besoin.

    Jean-Paul Delahaye, Professeur émérite à l’université de Lille et chercheur au Centre de recherche en informatique, signal et automatique de Lille (Cristal)

  • Les fluides : une histoire de calcul scientifique

    Quel est le point commun entre les battements de mon cœur, un avion qui vole grâce à ses réacteurs et l’évacuation d’une salle de cinéma ?  C’est ce que vont nous expliquer Jean-Antoine Désidéri et Alain Dervieux (Inria, Sophia Antipolis Méditerranée) en nous accompagnant  à travers un demi-siècle de calcul scientifique, du point de vue de l’étude des fluides. Pascal Guitton et Thierry Viéville.

    Bonjour, vous êtes des spécialistes de calcul scientifique et de mécanique des fluides numériques. Pourriez-vous nous préciser le contour de ces disciplines ?

    On peut dire que tous les scientifiques s’impliquent dans une forme de “calcul sur ordinateur”, mais classiquement on emploie le terme de calcul scientifique (et celui de numéricien·ne pour celles et ceux qui le pratiquent) pour désigner les activités de modélisation physique, mathématique et informatique de systèmes complexes issus de la physique théorique ou de l’ingénierie.

    Les équations qui régissent l’évolution temporelle de ces systèmes sont dites « équations différentielles » et celles qui tiennent compte aussi des aspects spatiaux sont dites « équations aux dérivées partielles« . Calculer des solutions approchées de ces équations aux dérivées partielles est l’objet de la simulation numérique. Le problème doit être réduit à un nombre raisonnable d’inconnues. Pour cela, on construit un maillage en décomposant l’espace en un assez grand nombre de petits éléments géométriques. Chaque élément porte les valeurs locales des inconnues. L’art du numéricien consiste à établir des relations entre ces inconnues de manière à approcher finement l’équation aux dérivées partielles.
    Lorsque ces méthodes sont appliquées à la simulation d’écoulements de fluides (liquides, gaz, plasmas), on parle de mécanique des fluides numérique.

    Vous avez rejoint l’INRIA au début des années 80. Quelle y était alors la situation du calcul scientifique ?

    En mathématiques appliquées, la culture scientifique était celle des Éléments Finis (EF) et de la Théorie du Contrôle. Sur ces sujets, l’INRIA entretenait un lien très étroit avec l’Université Pierre et Marie Curie (Paris 6) et l’École Polytechnique notamment grâce à l’implication des Professeurs P.G. Ciarlet, R. Glowinski, J.L. Lions et P.A. Raviart. Ce lien est toujours vivace, mais bien d’autres ont été créés depuis, comme en témoigne la diversité thématique d’Inria aujourd’hui.

    Nous allons nous concentrer sur les thématiques de la simulation et aborderons peu ici les thématiques du contrôle qui sont pourtant très importantes, notamment pour leurs applications à la robotique.

    Dans cet environnement, en matière de simulation, le calcul scientifique côté INRIA était porté par trois équipes-projets. L’une développait une bibliothèque de calcul par éléments finis très généraliste, bien que fortement orientée vers la problématique de la mécanique du solide, typiquement le calcul des structures (utilisés par exemple pour construire un pont, un avion…). L’autre développait des méthodes par éléments finis pour la simulation des ondes et les problèmes inverses, notamment en recherche pétrolière. La troisième se focalisait sur la méthodologie numérique, et comportait un volet particulier en mécanique des fluides. Nous sommes des héritiers plus particulièrement de cette équipe, alors dirigée par R. Glowinski qui est associé aujourd’hui à l’Université de Houston.

    En mécanique des fluides, le développement numérique portait sur les équations de la vitesse de ce fluide. Une réalisation particulièrement marquante a été le calcul d’un écoulement aérodynamique tridimensionnel autour d’un avion complet sur un maillage de quelques milliers de points, en collaboration avec Dassault-Aviation:

     Écoulement potentiel autour d’un avion complet en maillage non structuré [1]. Cliquer pour zoomer.

    En calcul scientifique, une estimation des capacités d’un code est fournie par le nombre de points de maillage qu’il permet de traiter en une nuit avec le plus puissant ordinateur disponible. Début 80, grâce au calcul vectoriel (ordinateur Cray), les “gros calculs” sont passés de quelques dizaines de milliers de points à plusieurs millions.

    Quelle était la motivation à poursuivre des recherches en mécanique des fluides numérique et quels étaient les sujets difficiles de l’époque?

    En mécanique des fluides, la méthodologie dominante (notamment utilisée à la NASA ou à l’ONERA en France) était issue de techniques classiques d’approximation des équations continues par des calculs pas à pas, dit aux différences finies (DF). Ces schémas d’approximation sont simples à construire, et se généralisent aisément. Pour des objets courbes, il faut construire au préalable d’un maillage régulier, qui est ensuite déformé.

    On parle de maillage régulier ou structuré quand les sommets des facettes sont organisés de façon structurée (par exemple avec uniquement des parallélépipèdes) et qu’il est donc possible de les stocker et de les traiter avec une matrice. Une règle de construction simple permet alors d’obtenir les positions des sommets et l’organisation des facettes.
    Dans le cas contraire, le maillage a une forme libre, ce qui est plus souple mais plus lourd à manipuler.

    Cette approche se justifiait tant qu’on abordait des problèmes de mécanique des fluides pour des géométries relativement simples. Mais avec l’ambition impérieuse de l’industrie aéronautique de traiter le “problème mythique » de l’avion complet, c’est-à-dire de résoudre les équations de la mécanique des fluides dans le domaine tridimensionnel défini par l’extérieur de la véritable géométrie d’un avion (sa forme), il fallait adopter une autre démarche. Le défi technologique a été de générer d’un maillage non structuré, plus souple, avec moins d’éléments tout en conservant la même précision. Par contre, cette perte de structuration dans le maillage entraine d’avoir à stocker dans l’ordinateur un grand volume d’informations pour connecter des points avec leurs voisins. Au tout début, ce stockage était en butée avec les limites de mémoire des ordinateurs dont nous disposions. Mais la communauté française des mathématiques appliquées avait aussi changé de méthode de calcul: la méthode des éléments finis que nous citions se rattache aux maillages non structurés. Ce travail sur les méthodes numériques en maillages non structurés fut pionnier.

    Simultanément, la communauté internationale cherchait à développer des schémas d’approximation plus sophistiqués pour ces problèmes afin de traiter de manière plus savante les cas où les solutions attachées à ces problèmes devenaient singulières: lors de chocs. Un choc est une discontinuité dans la solution. Par exemple, lorsqu’un avion franchit le « mur du son’’, il crée un saut de pression qui peut gravement endommager le tympan. En régime de croisière d’un avion de transport moderne présente un saut de la pression de l’air, un choc sur la voilure, à la limite. L’optimisation aérodynamique consiste pour une grande part à réduire l’intensité de ce choc. Mais avant d’optimiser, il faut développer la capacité de simuler l’écoulement avec précision, donc à capturer les chocs.
    En cette matière, un schéma dit conservatif permet de calculer avec précision les sauts des grandeurs physiques au travers d’un choc. Cependant, généralement, la solution numérique présente aussi localement des oscillations parasites qu’il convient de maitriser au mieux. Ces questions sont centrales en matière d’équations aux dérivées partielles pour la mécanique des fluides.
    Certains de nos collègues comme Harten et van Leer ont proposé des solutions numériques qui présentent moins d’oscillations parasites. Un défi pour nous était alors de construire de tels schémas dans notre contexte avec les éléments finis et les maillages non structurés. Un autre défi – toujours d’actualité – était de développer des techniques de résolution les plus économiques possibles en mémoire et temps calcul, afin d’aborder efficacement des problèmes de grande taille. Nos efforts ont porté sur la stabilité des schémas de calcul numériques. Nous sommes heureux d’avoir pu  contribuer à étendre ces méthodes et de les partager très largement en enseignant à travers l’Europe, comme à l’Institut Von Karman de mécanique des fluides de Bruxelles.

    Écoulement supersonique autour d’un cylindre; approximation de type volumes finis en maillage non structuré adapté à l’écoulement [2]. A gauche le maillage utilisé vu d’ensemble (en haut) et détaillée (en bas). À droite on représente le flot du fluide. Cliquer pour zoomer.

    Pour illustrer cela, observons grâce à la figure un cas-test dans lequel les équations d’Euler (fluide compressible) ont été résolues en deux dimensions d’espace dans le domaine extérieur à un cylindre. Ces résultats sont tirés d’un atelier international tenu à Rocquencourt en 1985. C’est un écoulement supersonique, à Mach 3, autour d’un cylindre, de gauche à droite. On voit devant le cylindre une ligne de choc au niveau du flot et on voit à gauche que le maillage s’est adapté au mieux au phénomène observé. Derrière le cylindre, la zone triangulaire est de vitesse nulle (on parle d’eau morte), et dans le sillage du cylindre l’écoulement s’accompagne d’autres phénomènes complexes.

    Nos techniques d’approximation en maillage non structuré avaient alors permis, grâce à l’adaptation de maillage par déplacement des nœuds et division des éléments, de mettre en évidence de telles structures physiques avec précision.

    Vous avez donc atteint dans les années 80 une certaine maîtrise des schémas d’approximation de type volumes-finis en maillages non-structurés. Quelles ont été les évolutions dans la décennie suivante?

    La décennie 90 a été marquée par l’extension des méthodes de simulation à des cas de physique des fluides plus complexes, notamment motivés par certains programmes spatiaux européens. Le programme de fusée Ariane a soutenu une activité de recherche dans le domaine de la combustion. Dans certains laboratoires du CNRS, la recherche a porté sur la modélisation physique des phénomènes. À l’INRIA et dans d’autres laboratoires, les méthodes d’approximation ont été étendues pour traiter la cinétique chimique liée à la combustion, et le suivi de solutions instationnaires (propagation de flammes).

    Le projet européen de navette spatiale Hermès a été un formidable moteur pour la recherche et le développement en matière de modélisation physique, d’expérimentation en soufflerie, de modélisation mathématique et de simulation numérique. Il a regroupé une soixantaine de laboratoires travaillant en émulation sur un ensemble de problématiques liées aux défis que soulève la validation du calcul des caractéristiques de vol de rentrée atmosphérique de l’engin. Sans être exhaustif, ni trop détaillé, notons au moins deux types de phénomènes physiques qui ont motivé l’extension des méthodes standards de simulation numérique en mécanique des fluides

    1. l’atmosphère raréfiée à très haute altitude, disons 80 km;
    2. les gaz hors équilibre thermodynamique, avec un point critique à 75 km d’altitude.

    En atmosphère raréfiée, les modèles de mécanique des fluides sont de nature statistique. Cette situation a justifié le développement d’outils de simulation d’évolution d’un gaz hors équilibre (équations de Boltzmann), notamment en utilisant des méthodes aléatoires (simulation par la méthode de Monte-Carlo), ou ne pouvant décrire exhaustivement les éléments, on les sélectionne au hasard et de manière pertinente.

    En pénétrant les premières couches de l’atmosphère lors de la phase de rentrée, l’engin est encore à très grande vitesse (25 fois la vitesse du son, soit 7 km/s). L’intensité du choc en amont du nez arrondi est alors suffisante pour dissocier les molécules d’air et le fluide est le siège d’un phénomène chimique qui absorbe en partie seulement le choc thermique. Pour cette raison, la paroi de l’engin est revêtue de dispositifs de protection spéciaux, dont les fameuses tuiles de la navette spatiale américaine. Plus généralement, le fluide, dans la couche de choc, subit différentes formes de déséquilibre thermodynamique. Dans l’enveloppe de vol de la navette, le point le plus critique vis-à-vis du choc thermique survient à 75 km d’altitude. Dans la simulation, on doit alors compléter les équations de la mécanique des fluides (équations de Navier-Stokes) par d’autres équations aux dérivées partielles dont chacune modélise une variable physique en déséquilibre, et tenir compte de manière complexe du mélange gazeux. Pour “valider” les calculs qui en résultent, il faut confronter les codes numériques entre eux, c’est la “vérification”, et les résultats de codes à ceux d’expériences en soufflerie. Cette validation est particulièrement difficile car en laboratoire, on ne peut reproduire la totalité des conditions du vol réel, et on procède par vérifications croisées de vérification et validation. Pour illustrer cette problématique, on montre ci-dessous un calcul de température autour d’une géométrie de double-ellipse utilisée pour représenter la partie avant de la navette.

    Écoulement hors-équilibre chimique du mélange gazeux autour d’une double-ellipse; à droite un zoom du champ de température [3]. Cliquer pour zoomer.

    Outre les simulations de physique des fluides complexes, on a vu apparaître des simulations couplant plusieurs physiques, chacune associée à un modèle relativement classique. Notons en particulier les simulations de couplage fluide-structure dont voici une illustration :

    Maillage tridimensionnel d’environ 100,000 points utilisé pour le calcul couplé fluide-structure d’un écoulement dans un inverseur de poussée du réacteur d’un avion de ligne. L’axe du réacteur de forme cylindrique se distingue en bas. L’écoulement va de gauche à droite. À droite, son chemin est barré par la cloison verticale. Il est à nouveau dévié vers la gauche par le volet élastique bleu dont on observe la forte déformation. Le but de l’étude était d’analyser la vibration parasite de ce volet. (R. Lardat, B. Koobus, E. Schall, A. Dervieux C. Farhat: Analysis of a possible coupling in a thrust inverter, Revue Européenne des Eléments Finis, 9:6-7,2000). Cliquer pour zoomer.

    De votre point de vue quelles ont été les principales avancées méthodologiques de votre domaine apparues dans les années 2000?

    Les grands programmes spatiaux précédemment cités étaient nés de la volonté des autorités de maintenir la communauté scientifique européenne à un niveau scientifique et technologique compétitif au plan international. Au tournant du siècle cette volonté est devenue moins impérative, et les soutiens à la recherche appliquée ont davantage été trouvés dans le cadre des projets et réseaux de la commission européenne, notamment en aéronautique civile, à nouveau.

    Les innovations méthodologiques les plus marquantes concernent les schémas d’approximation des calculs et les problématiques d’optimisation pour trouver les meilleures solutions approchées.

    Mais c’est aussi l’ouverture de ces méthodes vers des applications hors du champ de la Défense Nationale : notamment en biologie, par exemple dans une  action collaborative entre plusieurs équipes sur la modélisation de l’activité cardiaque (CardioSense). Voici une illustration de la simulation de l’onde électrique dans le cœur.

    Onde électrique dans le cœur, premiers travaux dans le cadre du projet Icema : on modélise la diffusion entre deux domaines avec leur  potentiel électrique, en tenant compte de la structure membranaire permettant les échanges ioniques (Y. Coudière, 2000). Cliquer pour animer.

    Voici maintenant la représentation d’un écoulement visqueux autour d’un profil très effilé. Ce calcul (récent) allie une méthode ancienne dite d’approximation de Galerkin discontinue combinée à une technique de représentation par des petites portions de courbes.

     
    Écoulement autour d’un profil d’aile par la résolution des équations de la mécanique des des fluides (R. Duvigneau, 2017). Cliquer pour zoomer.

    Ces progrès réalisés, quelles sont les tendances actuelles dans vos domaines de recherche ?

    Tout d’abord, on observe une prise en compte de plus en plus systématique des incertitudes et de l’utilisation du hasard dans plusieurs types d’approche, pour résoudre les équations avec des approximations qui utilisent des tirages aléatoires.

    Par ailleurs, on note également le haut degré de sophistication atteint aujourd’hui par les générateurs de maillages, et les logiciels d’adaptation. On note aussi dans ce domaine des progrès notoires dans l’étude de phénomènes avec des ruptures ou des changements rapides. Pour illustrer ce dernier point voici une animation montrant l’évolution d’un maillage tridimensionnel modélisant une zone urbaine dans laquelle se produit une détonation.

    Maillage évolutif suivant une onde de détonation en milieu urbain (F. Alauzet, 2017). Cliquer pour animer.

    Voici maintenant une illustration des progrès réalisés en matière d’approximation, y compris dans ces cas instationnaires, et du volume de calcul que l’on peut traiter sur nos architectures. Il s’agit d’un problème classique de résolution d’instabilité atmosphérique (dit de Kelvin-Helmholtz). Les équations de la mécanique des fluides sont résolues avec 4 millions de degrés de liberté sur une architecture machine à 256 cœurs. Le schéma d’approximation dont on a besoin est sophistiqué et le calcul dure 3 jours.

    Calcul d’une instabilité de Kelvin-Helmholtz (R. Duvigneau, 2017). Cliquer pour animer.

    Notons également l’implication d’une vaste communauté interdisciplinaire (physiciens et mathématiciens) dans le grand projet international ITER pour mettre au point un équipement mettant en oeuvre une fusion nucléaire. Au niveau du calcul, il s’agit de résoudre des équations de magnéto-hydro-dynamique, qui combinent plusieurs domaines de la physique. Voici une illustration de cette activité et les moyens informatiques développés actuellement. En haut les travaux de M. Becoulet. En bas les travaux de M. Futanami.

    Résolution des équations de magnéto-hydro-dynamique, dans le cadre du Projet ITER (B. Nkonga, 2016). Le flux magnétique, le courant, le tourbillon, le potentiel électrique, la vitesse parallèle, la densité, et la température sont prises en compte. Le plasma est en rotation dans le Tokamak (illustration du haut). Ce plasma est notamment contrôlé par un dispositif situé en bas de l’anneau (illustration du bas).

    Il est remarquable que la communauté aborde aujourd’hui des champs nouveaux en dehors des applications plus classiques à la physique ou à l’ingénierie. La modélisation mathématique et la simulation numérique du trafic routier ou piétonnier qui s’y rattache en offrent un exemple assez proche de la mécanique des fluides. Citons ici les travaux de P. Goatin. On illustre ci-dessous une simulation d’évacuation de salle par deux issues dont la première est rapidement congestionnée. L’objectif à terme de ce type de simulation est de mieux concevoir la salle afin d’une évacuation plus rapide en cas d’alerte.

     
    Simulation de l’évacuation d’une salle en cas d’alerte. Cliquer pour animer (P.Goatin, 2013). Vue aérienne. Les personnes sont initialement massées à proximité du mur à gauche. Lorsque l’alerte est donnée, elles se dirigent vers l’issue la plus proche, qui, assez vite, se congestionne. Une partie du groupe se dirige alors vers l’issue de droite.

    Enfin, notons que les travaux initiés en 2000 sur la modélisation de la circulation sanguine cités précédemment ont pris de l’ampleur, comme en témoigne la figure ci-dessous qui illustre la montée en puissance du calcul (1 s de temps physique exige 500 000 pas de temps de simulation, soit 83 mn de temps calcul sur 24 cœurs du Mésocentre Régional Aquitaine, MCIA, en 2014), et la sophistication du modèle physico-numérique actuel (potentiel de membrane sur les ventricules, modèle géométrique du patient, hypothèses de structure des tissus; calcul: intégrateurs exponentiels pour la réaction).

     
    Simulation de l’activité cardiaque dans le cadre du Projet CardioSense [4]. Cliquer pour animer.

    Après de tels succès, comment imaginez-vous les futurs progrès de votre discipline ?

    Oui il y a eu des succès, grâce à beaucoup de travail et de trouvailles par les chercheur.e·s, et en même temps, on aurait bien aimé aller beaucoup plus vite !

    Aujourd’hui nous avons conscience d’un certain nombre de défis vitaux pour l’humanité, dans les domaines de l’évolution de la planète (la préserverons nous ?), dans le domaine de la santé (les progrès de la médecine sont-ils pour tous ?), et de l’énergie (comment la décarboner ?). Les numéricien·ne·s ont un rôle important à jouer pour relever ces défis, mais cela implique de pouvoir transmettre leurs mathématiques et leurs algorithmes vers les sciences de la terre, la biologie, la médecine, etc.

    On prévoit un plus grand impact de la modélisation de notre environnement et une exigence accrue en matière de sécurité des systèmes et d’environnement pour une régulation plus efficace des processus industriels et la conformité des produits à la réglementation, notamment en matière de contrôle de la pollution.

    Aujourd’hui les plus gros calculs en termes de volumes d’opérations sont conduits par les grands industriels, souvent de l’industrie du transport ou de la défense. Le principe général est de décomposer le calcul global en blocs indépendants a priori plus simples à résoudre, de calculer chacun d’entre eux (éventuellement de façon parallèle), puis de fusionner l’ensemble. Les calculs moins volumineux mais complexes sont le plus souvent exécutés par des sociétés de service.

    La sophistication de nos méthodes va s’accélérer, avec plus de mathématiques (précision, algorithmes de résolution, adaptation de maillage, identification, optimisation), la prise en compte de plus de lois physiques, couplant des phénomènes divers, la prise en compte des aléas.

    Il faudra aussi que la programmation sur les futures architectures d’ordinateurs soit efficace, mais en proposant des outils pour lesquels les mécanismes trop complexes à guider (le maillage, le parallélisme, notamment) seront transparents pour l’ingénieur utilisateur ou des non-spécialistes: pourquoi-pas ne pas envisager des travaux de science participative impliquant des citoyen·ne·s ?

    Jean-Antoine Désidéri & Alain Dervieux.

    [1] M.O. Bristeau, 0. Pironneau, R. Glowinski, J. Périaux, P. Perrier, and G. Poirier: On the numerical solution of nonlinear problems in fluid dynamics by least squares and finite element methods (II). Application to transonic flow simulations, Computer Methods in Applied Mechanics and Engineering 51, 1985

    [2] A. Dervieux, J.-A. Désidéri, F. Fezoui, B. Palmerio, J.P. Rosenblum, B. Stoufflet: Euler calculations by upwind Finite Element Methods and adaptive mesh algorithm, GAMM Workshop on the Numerical Simulation of Compressible Euler Flows, Rocquencourt (F), June 10-13 1986, Notes in Numerical Fluid Dynamics 26, Vieweg , Braunshweig-Wiesbaden

    [3] M.V. Salvetti, M.C. Ciccoli and J.-A. Désidéri: Non-equilibrium external flows including wall-catalysis effects by adaptive upwind finite elements, Russian Physics Journal, 36:4, 1993

    [4] S. Labarthe, J. Bayer, Y. Coudière, J. Henry, H. Cochet, P. Jaıs and E. Vigmond: A bilayer model of human atria: mathematical background, construction, and assessment, Europace 16:4, The Oxford University Press, 2014

    Notes:

    La notion de stabilité. Les solutions produites par simulation numérique résultent de la somme de deux composantes. La première, dite composante convergente, approche la solution exacte des équations aussi précisément que nécessaire par raffinement du maillage, quitte à augmenter le coût du calcul. La seconde est dite composante parasite. Lorsque le schéma d’approximation est « stable’’, la composante parasite reste à un niveau faible, intimement lié à la précision arithmétique des opérations élémentaires sur l’ordinateur. À l’inverse, si le schéma est instable, la composante parasite s’amplifie exponentiellement dans le déroulé de l’algorithme jusqu’à noyer complètement le résultat. Il est donc impérieux en analyse numérique d’établir de manière fiable les propriétés de stabilité des schémas d’approximation.

  • La malédiction de la grande dimension

    Stéphane Mallat est le titulaire de la chaire « Sciences des données » du Collège de France où il présente le cours « L’apprentissage face à la malédiction de la grande dimension » (leçon inaugurale le 11 janvier 2018). Il a été professeur d’informatique à l’École normale supérieure de la rue d’Ulm de 2012 à 2017. En 2001, il a cofondé une start-up, Let It Wave, qu’il a dirigé jusqu’en 2007.  Les algorithmes d’apprentissage peuvent nous émerveiller par leurs résultats, nous effrayer aussi parce qu’ils sont mal compris. Le cours de Stéphane Mallat devrait permettre de mieux les appréhender. Serge Abiteboul.
    Cet article est publié en collaboration avec The Conversation.
    Voir la page binaire sur l’informatique au Collège de France

    Nous assistons à un déluge de données numériques, sous la forme d’images, de sons, de textes, de mesures physiques ainsi que toutes les informations disponibles sur Internet. L’analyse automatique de ces données est devenue un enjeu industriel, sociétal et scientifique majeur. La performance des algorithmes d’analyse de données a fait un bond ces dernières années, grâce à l’augmentation des capacités de calcul et des masses de données, mais aussi grâce à l’évolution rapide des algorithmes d’apprentissage. Ce bond est à l’origine de la renaissance de l’Intelligence Artificielle. En particulier, les réseaux de neurones ont récemment obtenu des résultats spectaculaires pour la classification d’images complexes, la reconnaissance vocale et de musique, pour la traduction automatique de textes ou la prédiction de phénomènes physiques et même pour battre le champion du monde de Go. Ils sont utilisés dans des applications industrielles et médicales, y compris pour les voitures autonomes. La chaire de sciences des données présentera les algorithmes et les principes mathématiques permettant de comprendre la nature des connaissances acquises par ces algorithmes d’apprentissage.

    Un algorithme d’apprentissage prend en entrée des données, par exemple une image, et estime la réponse à une question, par exemple trouver le nom de l’animal dans l’image. Ces algorithmes d’apprentissage ne sont pas entièrement déterminés à l’avance. Ils incluent de nombreux paramètres qui sont optimisés avec des exemples, lors de la phase d’apprentissage. Pour la reconnaissance d’animaux, on donne à l’algorithme des exemples d’images et le nom des animaux dans chaque image. L’apprentissage assure que l’algorithme ne fasse pas d’erreur sur les exemples d’entrainement. Cependant cela ne présente aucun intérêt en soit. Il faut garantir que ce résultat se généralise et donc que l’algorithme soit capable de prédire le bon résultat sur des données qu’il n’a jamais vues au préalale. Cette généralisation est liée à l’existence de régularités, que l’algorithme utilise pour relier le résultat sur une donnée inconnue avec les exemples connus.

    La complexité de ce problème vient du très grand nombre de variables dans chaque donnée. Ainsi une image a typiquement plus d’un million de pixels, et donc plus d’un million de variables dont il faut tenir compte pour répondre à une question. L’interaction de ces variables produit un nombre gigantesque de possibilités. C’est la malédiction de la dimensionnalité. Pour faire face à cette malédiction, il est nécessaire d’avoir des informations à priori qui sont utilisées par les algorithmes.  Comprendre la nature de cette régularité en grande dimension est un enjeu fondamental qui fait appel à de nombreuses branches des mathématiques, dont les statistiques, les probabilités, l’analyse et la géométrie.

    Sciences des Données et Mathématiques Appliquées

    La chaire s’intitule « sciences des données » par opposition au singulier « la science des données » car ce domaine est une auberge espagnole, où cohabitent des approches et des cultures scientifiques totalement différentes, qui s’enrichissent mutuellement. Cela comprend les mathématiques et notamment les statistiques, mais aussi l’informatique et l’intelligence artificielle, le traitement du signal et la théorie de l’information, et toutes les sciences comme la physique, la biologie, l’économie ou les sciences sociales, qui traitent et modélisent des données. Apporter une vision et un langage commun au-delà des spécificités de chaque domaine est la vocation des mathématiques. C’est ce point de vue qui sera développé, tout en restant enraciné dans les applications qui sont sources de problèmes nouveaux, de créativité et d’idées. Cet aller-retour entre mathématiques et applications, qui efface progressivement les frontières entre expérimentations et théorie, est au cœur de la démarche des mathématiques appliquées. La beauté des concepts qui se dégagent ne s’enracine pas seulement dans leur pureté, comme celle d’un diamant qui se suffirait à lui-même, mais dans la beauté des correspondances entre domaines aussi différents que la reconnaissance d’images, la neurophysiologie, la chimie quantique, la cosmologie ou l’économie. Révéler ces correspondances est aussi l’ambition des mathématiques appliquées.

    En sciences des données il s’agit de comprendre le lien entre les applications, l’algorithmique, les expérimentations numériques et la compréhension mathématique du traitement de masses de données. Les mathématiques sont importantes pour garantir la robustesse des résultats, notamment pour des usages critiques comme la conduite de voitures autonomes. Le cours offrira la possibilité de participer à des challenges de données, organisés par mon équipe de recherche à l’École Normale Supérieure. Ces challenges proviennent de start-ups, d’hôpitaux ou des laboratoires scientifiques, et permettent à chacun de développer ses propres idées, et ainsi comparer la performance de différents types d’algorithmes sur de vrais problèmes. Ces challenges sont disponibles sur cette page web.

    Cette chaire a aussi pour objectif de mieux faire comprendre les avancées des algorithmes et des mathématiques de l’apprentissage et de l’intelligence artificielle, à un plus large public. Diffuser la connaissance dans ce domaine est important car ces technologies auront probablement un impact croissant sur l’industrie, la médecine mais aussi sur certains aspects de notre organisation économique et sociale. Il faut y réfléchir bien au-delà des cercles scientifiques.

    Face à la Malédiction de la Dimensionnalité

    Le cours de cette année introduira les outils algorithmiques et mathématiques liés à la généralisation pour des données incluant un grand nombre de variables. Il approfondira la notion de régularité qui est centrale dans ce domaine, et son utilisation par des différents types d’algorithmes, y compris des réseaux de neurones. Le cours commencera par la notion de régularité pour des données en basse dimension, à travers la transformée de Fourier et la transformée en ondelettes, avec des applications pour le débruitage et la compression de signaux. Il considérera ensuite l’apprentissage supervisé, les algorithmes à noyaux, et la performance des réseaux de neurones à une couche cachée.

    Chaque séance de cours sera suivie par un séminaire présentant l’état de l’art dans différents domaines d’applications. Des challenges de données seront proposés aux participants et présentés lors des premières séances. Au menu de cette année, plus de 10 challenges, pour l’économie d’énergie, le diagnostic de cancer à partir de données génomiques, la prédiction en finance, l’analyse de questionnaires, la reconnaissance d’images de célébrités ou la prédiction de scores de football.

    Stéphane Mallat, Professeur au Collège de France

     

  • Algorithmes

    Claire Mathieu est Directrice de Recherche au Centre National de la Recherche Scientifique. Elle travaille au Département d’Informatique de L’École Normale Supérieure et à l’Irif, Université Paris-Diderot. Elle est la toute nouvelle titulaire de la Chaire « Informatique et sciences numériques » du Collège de France où elle présente un cours intitulé « Algorithmes » (leçon inaugurale le 16 novembre 2017). Les algorithmes fascinent, peuvent inquiéter, prennent une place considérable dans nos vies. Il nous faut mieux les comprendre pour qu’ils fassent ce que nous voulons. Entrons avec Claire Mathieu, parmi les meilleurs spécialistes mondiaux du domaine, dans leur monde merveilleux .  Serge Abiteboul. Cet article est publié en collaboration avec The Conversation.

    Claire est également une éditrice invitée fidèle de Binaire.

    Claire Mathieu

    Les algorithmes, quand ils sont bien conçus car bien compris, contribuent au bien social et sont un outil de transformation de la société. Ils y prennent une place grandissante, que ce soit pour des applications informatiques telles que gérer efficacement des données, pour les transmettre rapidement et de façon fiable, pour faire des calculs, pour optimiser l’allocation de tâches, ou de plus en plus pour des usages en société comme le calcul d’itinéraire, les recommandations de lectures ou de films, l’affectation des étudiants avec APB, etc.

    Très souvent, ces algorithmes sont opaques, mystérieux, voire effrayants. Comment marchent-ils ? Quelles sont les étapes du calcul ou de la prise de décision ? Pourquoi marchent-ils ? Quelles sont les propriétés mathématiques qui expliquent leurs performances ? Le “comment” et le “pourquoi” sont les deux facettes de l’étude des algorithmes : la conception (comment ça marche) et l’analyse (pourquoi ça marche).

    En général, l’analyse d’algorithmes sert d’abord à montrer qu’un algorithme résout correctement un problème, puis qu’il le fait en un temps raisonnable, de façon fiable et en restant économe en ressources.

    Un sous-domaine fondamental largement développé depuis une vingtaine d’années concerne les algorithmes d’approximation. Un tel algorithme, plutôt que de rechercher une solution exacte et précise, se contente d’une solution approchée. On les utilise pour résoudre les problèmes trop difficiles pour être résolus complètement en un temps raisonnable. On s’autorise alors à accepter des solutions dont la valeur serait, disons, à 5% de la valeur optimale. Par exemple, prenons le problème de la livraison de marchandises. Comment optimiser les trajets d’un camion qui doit livrer des marchandises, connaissant le lieu de l’entrepôt, les lieux et volumes des commandes des clients, ainsi que la capacité du camion ? C’est un problème difficile lorsque le nombre de clients est élevé et on ne sait le résoudre que dans des cas particuliers qui ne correspondent pas toujours aux applications réelles rencontrées : aujourd’hui, même dans les cas les plus simples, calculer une solution approchée à 1% prend un temps déraisonnable. L’un de nos axes de recherche est donc de continuer à développer et d’améliorer ces algorithmes d’approximation.

    Claire et Le point de vue algorithmique, #tembelone

    Modélisation mathématique et évolutions technologiques

    Pour les chercheurs qui comme moi travaillent en informatique théorique, l’élément non-négociable est la recherche du théorème. Les problèmes sont variés, les méthodes de résolution aussi, mais à la fin, ce qui est produit, ce qui apparaît dans le paragraphe intitulé “nos résultats” dans nos introductions, est toujours un théorème. La rigueur mathématique prime. C’est un principe de base.

    Cependant, avec les évolutions technologiques, de nouvelles problématiques surgissent et se traduisent de façon naturelle par des évolutions des questions mathématiques étudiées. Ainsi, les modèles de calcul évoluent, avec par exemple de plus en plus de modèles de calcul ou de communication qui limitent l’accès aux données (par exemple, dans le modèle du flux de données, l’utilisateur voit toute une suite d’informations défiler devant lui, par exemple des paquets transitant sur un réseau. Bien qu’il n’ait pas suffisamment de place en mémoire pour garder toutes les informations vues, il souhaite cependant calculer des informations statistiques sur ce flux), ou dont les données évoluent de façon dynamique, ou encore avec une incertitude sur les données (par exemple, les avis lus sur internet sur la qualité d’un restaurant, d’un hôtel ou d’un médecin sont notoirement peu fiables, et contiennent pourtant des informations précieuses.)

    Il nous faut donc non seulement travailler sur des problèmes reconnus du domaine, mais également proposer des problèmes algorithmiques nouveaux. Il s’agit de définir une question algorithmique de façon formelle, qui soit suffisamment simple dans sa structure pour que l’on puisse l’étudier avec un espoir de démontrer des résultats rigoureux. C’est ainsi qu’on peut rigoureusement démontrer l’effet de « petit monde » dans les réseaux sociaux (soit le nombre limité de degrés de séparation entre tous ses membres) : bien que leur taille aille grandissant, il demeure toujours possible à un membre du réseau social de prendre contact avec presque n’importe quel autre membre grâce à une courte chaîne de connaissances. Ici, la démonstration mathématique se fait sur un modèle simplifié, inspiré du modèle dit “de feu de forêt”. C’est en passant par ce type de modèles simplifiés que l’on peut espérer arriver à des intuitions pour une meilleure compréhension du monde.

    Claire jongle avec problèmes algorithmiques et techniques mathématiques, #tembelone

    “Pourquoi” et “Dans quel but” : des questions d’éthique

    Par ailleurs, comme les algorithmes agissent de plus en plus non seulement sur de simples octets mais également sur les personnes, les questions d’éthique comme l’équité ou la transparence deviennent prégnantes.

    Une constante du domaine est qu’un algorithme est développé dans un but précis et analysé en relation avec la façon dont il atteint son but. Mais ces années dernières ont vu apparaître des algorithmes qui résolvent un problème imprécis, et qui ne “marchent” que dans un sens très flou — le choix d’informations à présenter au lecteur en ligne ou les recommandations de produits à acheter, par exemple. Qu’est-ce qui fait qu’une sélection donnée est le meilleur choix ? Un résultat donné est-il, ou non, satisfaisant ? Quel est le but recherché ? Ces questions sont à la périphérie de l’algorithmique classique et en même temps centrales pour l’évolution du domaine dans la décennie à venir.

    Un des nouveaux enjeux de l’algorithmique est donc comprendre le “pourquoi” et le “dans quel but” des algorithmes de la famille des méthodes d’ « apprentissage profond », qui se retrouvent appliqués un peu partout avant qu’on ait vraiment compris leurs aspects fondamentaux. Ici, la théorie a pris du retard sur la pratique, et ce retard de compréhension induit des risques de manipulation sans contrôle.

    Il ne faut pas avoir peur des algorithmes, mais il faut apprendre à les connaître pour les apprivoiser : c’est la mission de l’algorithmique.

    Dans le cadre de la chaire annuelle “Informatique et sciences numériques”, leçon inaugurale au Collège de France le jeudi 16 novembre 2017 à 18h, cours les mardis à 10h à partir du 24 novembre.

    Claire Mathieu, CNRS, Paris