06 Fév Poser la Question la plus Simple

Le Professeur Robert Krauthgamer apporte des preuves mathématiques qui aident à expliquer pourquoi certains algorithmes informatiques sont meilleurs que d’autres pour les grands flux de données.

Dans les très gros flux de données, revenir en arrière pour obtenir des informations est quasi impossible.

Les ordinateurs ont beau devenir de plus en plus petits et performants, la quantité d’information en circulation dépasse toujours la capacité de traitement machine. Ces dernières décennies, les informaticiens et les mathématiciens se sont attaqués à l’analyse de très gros jeux de données – par exemple, les flux continus d’informations provenant de capteurs ou de satellites.
Les scientifiques cherchent notamment à identifier et caractériser des algorithmes qui seraient efficaces pour traiter de telles quantités de données. Les grands ensembles de données sont souvent linéaires – c’est-à-dire qu’ils arrivent en un flux continu, un fragment d’information à la fois – ce qui rend difficile voire impossible un retour en arrière pour obtenir les informations précédentes.

Le Professeur Robert Krauthgamer du Département Informatique et Mathématiques Appliquées de l’Institut Weizmann des Sciences explique  que les questions que l’on se pose aujourd’hui sur les flux de données – et auxquelles on espère répondre avec des algorithmes informatiques – peuvent être classées en celles auxquelles il est pratiquement impossible de répondre – elles utiliseraient  une quantité de mémoire de calcul rédhibitoire – et celles qui sont simples, ou au moins traitables. Parfois, deux problèmes peuvent sembler très proches mais la réponse à l’un peut être simple à trouver tandis que pour l’autre, cela peut être très difficile.

Le Professeur Robert Krauthgamer : utiliser les maths pour prouver qu’un algorithme efficace existe ou pas.

Le Professeur Krauthgamer donne un exemple concret pour clarifier les questions auxquelles on peut répondre : pour identifier une attaque par « déni de service distribué » (en anglais « distributed denial of service » ou DDOS), au cours de laquelle un serveur est saturé par trop de demandes, les techniciens peuvent vouloir connaître le nombre d’ordinateurs différents qui ont contacté le serveur sur une période de 24 heures, et quel ordinateur a fait le plus de demandes. Pour le savoir, l’utilisation de l’identité digitale – l’adresse IP – de chaque ordinateur peut-être très peu efficace si le serveur doit scanner tout son historique. Mais un algorithme intelligent peut estimer le nombre d’ordinateurs concernés avec une marge d’erreur d’environ 1%. Alors qu’il est difficile de trouver avec certitude l’adresse IP qui apparait le plus souvent dans le jeu de données, un algorithme peut choisir scrupuleusement des échantillons aléatoires pour créer une liste très précise des « gros perturbateurs ».

Il y a un principe mathématique inhérent qui peut décrire ce comportement
Un signes qui permet de dire qu’un algorithme est bon est qu’il utilise une plus petite quantité de mémoire que le jeu de données lui-même, afin que le calcul soit rapide et efficace. Dans des études récentes, le Professeur Krauthgamer et ses collègues apportent des critères probants pour identifier les problèmes faciles et difficiles. Si on revient à l’exemple de l’attaque par DDOS à titre d’explication, le Professeur Krauthgamer dit que n’importe quel algorithme pour trouver le plus gros perturbateur – ou simplement sa fréquence – dans le flux de données est inefficace. Mais une autre question est plus simple – et plus importante dans ce cas : peut-on estimer combien d’adresses distinctes ont une fréquence supérieure à 0 (c’est-à-dire qui apparaissent plus d’une fois) ?

De tels calculs impliquent un type de fonction communément utilisé appelée norme L^P, dans laquelle l’exposant P est un nombre. Quand P=0, la fonction est facile à estimer ; quand p = ∞, c’est extrêmement difficile. Qu’est-ce qui se passe entre 0 et l’infini ? Il s’avère que tout ce qui se situe au-dessus de p=2 est complexe tandis que tout ce qui est compris entre 0 et 2 inclus est simple ; et il y a une transition brusque entre les deux – ressemblant à une sorte de transition de phase en physique. Comment expliquer ça ? Jusqu’ici, on pensait que tout ce qui se situait au-dessus de 2 était similaire à l’infini. Mais dans le cadre de la caractérisation d’une classe plus générale de toutes les fonctions symétriques, le Professeur Krauthgamer et ses collègues ont apporté deux preuves qui expliquent cette frontière abrupte, montrant qu’il y a un principe mathématique inhérent qui peut caractériser ce comportement. « Ce que je trouve le plus convaincant dans ces preuves, » dit le Professeur Krauthgamer, « est le fait que nous utilisions des maths qui n’ont rien à voir avec les algorithmes pour prouver qu’un algorithme efficace existe ou non. »

Existe-t-il un algorithme efficace pour le nouveau problème?
Dans une autre étude, le Professeur Krauthgamer s’est intéressé à une classe élargie de problèmes, se demandant s’il était possible de déterminer si un nouveau problème avait un algorithme de résolution efficace. La méthode, probablement la plus fondamentale en informatique, est de convertir mathématiquement le nouveau problème en un problème canonique connu, comme le L^P de l’exemple précédent, puis de s’appuyer sur l’algorithme connu pour résoudre le problème canonique. Mais si cette méthode échoue – c’est-à-dire que le nouveau problème ou la nouvelle question ne peut être converti en un problème canonique – peut-on trouver un algorithme efficace avec une méthode différente ? Le Professeur Krauthgamer et ses collègues ont prouvé que si une nouvelle question ne peut être convertie, alors il ne peut y avoir de bon algorithme. Leur preuve est basée sur un domaine classique des mathématiques, nommé d’après le mathématicien polonais Stefan Banach qui le développa dans les années 1920.

« La logique basique nous dit à présent que s’il existe un bon algorithme aussi sophistiqué ou astucieux soit-il, alors le nouveau problème peut être converti en un problème canonique, » dit le Professeur Krauthgamer. « Notre contribution a été de démontrer que quelque chose est algorithmiquement possible si et seulement si une simple conversion mathématique existe. »

Le Professeur Krauthgamer ajoute : « Nous expliquons un phénomène de calcul par quelque chose qui ne semble pas lié, par exemple, par une branche des maths qui ne contient rien d’informatique ou d’algorithmique. Cette caractérisation permet de remonter à la source de problèmes tels que pourquoi p>2 est si complexe, nous donnant une explication globale, holistique, de pourquoi il en est ainsi. »

Bien que le travail du Professeur Krauthgamer soit théorique, il guide le monde des informaticiens qui travaillent avec des flux de données complexes, qui existent dans tous les domaines, depuis les réseaux de communication jusqu’à l’enregistrement des données de chaînes de magasins, ou encore les expériences biologiques ou l’astrophysique.