Les algorithmes traditionnels alimentent des outils de calcul compliqués comme l'apprentissage automatique (machine learning). Une nouvelle approche, appelée algorithmes avec prédictions, utilise la puissance de l'apprentissage automatique pour améliorer les algorithmes.

Les algorithmes - morceaux de code qui permettent aux programmes de trier, filtrer et combiner des données, entre autres choses - sont les outils standard de l'informatique moderne. Tels de minuscules engrenages dans une montre, les algorithmes exécutent des tâches bien définies au sein de programmes plus complexes.

Ils sont omniprésents, et c'est en partie pour cette raison qu'ils ont été minutieusement optimisés au fil du temps. Lorsqu'un programmeur doit trier une liste, par exemple, il se sert d'un algorithme de "tri" standard utilisé depuis des décennies.

Aujourd'hui, des chercheurs jettent un regard neuf sur les algorithmes traditionnels, en utilisant la branche de l'IA , donc du machine learning. Leur approche, appelée "algorithmes avec prédictions", tire parti des informations que les outils d'apprentissage automatique peuvent fournir sur les données traitées par les algorithmes traditionnels. Ces outils doivent, en quelque sorte, rajeunir la recherche sur les algorithmes de base.

L'apprentissage automatique et les algorithmes traditionnels sont "deux façons très différentes de calculer, et les algorithmes avec prédictions sont un moyen de les rapprocher", a déclaré Piotr Indyk, informaticien au Massachusetts Institute of Technology. "C'est un moyen de combiner ces deux fils conducteurs assez différents".

La récente explosion d'intérêt pour cette approche a commencé en 2018 avec un article de Tim Kraska, informaticien au MIT, et d'une équipe de chercheurs de Google. Dans cet article, les auteurs ont suggéré que l'apprentissage automatique pourrait améliorer un algorithme traditionnel bien étudié appelé filtre de Bloom, qui résout un problème simple mais aussi complexe et ardu.

Imaginez que vous dirigez le service informatique de votre entreprise et que vous devez vérifier si vos employés se rendent sur des sites web présentant un risque pour la sécurité. Naïvement, vous pourriez penser que vous devez vérifier chaque site qu'ils visitent en le comparant à une liste noire de sites connus. Si la liste est énorme (comme c'est probablement le cas pour les sites indésirables sur Internet), le problème devient lourd - on ne peut vérifier chaque site par rapport à une liste énorme dans le minuscule lapts de temps qui précède le chargement d'une page Internet.

Le filtre Bloom offre une solution, en permettant de vérifier rapidement et précisément si l'adresse d'un site particulier, ou URL, figure sur la liste noire. Pour ce faire, il comprime essentiellement l'énorme liste en une liste plus petite qui offre certaines garanties spécifiques.

Les filtres Bloom ne produisent jamais de faux négatifs : s'ils disent qu'un site est mauvais, il est mauvais. Cependant, ils peuvent produire des faux positifs, de sorte que vos employés ne pourront peut-être pas visiter des sites auxquels ils devraient avoir accès. Cela s'explique par le fait qu'ils s'agit d'une forme d'échange qui implique une certaine imprécision due à cette énorme quantité de données compressées -  astuce intitulée "compression avec perte". Plus les filtres Bloom compriment les données d'origine, moins ils sont précis, mais plus ils économisent de l'espace.

Pour un simple filtre Bloom, chaque site Web est également suspect jusqu'à confirmaton qu'il ne figure pas sur la liste. Mais tous les sites Web ne sont pas égaux : Certains ont plus de chances que d'autres de se retrouver sur une liste noire, simplement en raison de détails comme leur domaine ou les mots de leur URL. Les gens comprennent cela intuitivement, et c'est pourquoi vous lisez probablement les URL pour vous assurer qu'elles sont sûres avant de cliquer dessus.

L'équipe de Kraska a mis au point un algorithme qui peut également appliquer ce type de logique. Ils l'ont appelé "filtre de Bloom instruit" et il combine un petit filtre de Bloom avec un réseau neuronal récurrent (RNN), modèle de machine learning qui apprend à quoi ressemblent les URL malveillantes après avoir été exposées à des centaines de milliers de sites web sûrs et non sûrs.

Lorsque le filtre Bloom vérifie un site web, le RNN agit en premier et utilise son apprentissage pour déterminer si le site figure sur la liste noire. Si le RNN indique que le site figure sur la liste, le filtre Bloom appris le rejette. Mais si le RNN dit que le site n'est pas sur la liste, alors le petit filtre Bloom peut à son tour, faire une recherche précise, mais irréfléchie, dans ses sites compressés.

En plaçant le filtre Bloom à la fin du processus et en lui donnant le dernier mot, les chercheurs ont fait en sorte que les filtres Bloom instruits puissent toujours garantir l'absence de faux négatifs. Mais comme le RNN préfiltre les vrais positifs à l'aide de ce qu'il a appris, le petit filtre de Bloom agit davantage comme une sauvegarde, en limitant également ses faux positifs au minimum. Un site Web bénin qui aurait pu être bloqué par un filtre Bloom de plus grande taille peut désormais passer outre le "filtre Bloom iinstruit" plus précis. En fait, Kraska et son équipe ont trouvé un moyen de tirer parti de deux méthodes éprouvées, mais traditionnellement distinctes, d'aborder le même problème pour obtenir des résultats plus rapides et plus précis.

L'équipe de Kraska a démontré que la nouvelle approche fonctionnait, mais elle n'a pas formellement expliqué pourquoi. Cette tâche a été confiée à Michael Mitzenmacher, spécialiste des filtres de Bloom à l'université de Harvard, qui a trouvé l'article de Kraska "novateur et passionnant", mais aussi fondamentalement insatisfaisant. "Ils font des expériences en disant que leurs algorithmes fonctionnent mieux. Mais qu'est-ce que cela signifie exactement ?" a-t-il demandé. "Comment le savons-nous ?"

En 2019, Mitzenmacher a proposé une définition formelle d'un filtre de Bloom INSTRUIT et a analysé ses propriétés mathématiques, fournissant une théorie qui explique exactement comment il fonctionne. Et alors que Kraska et son équipe ont montré que cela pouvait fonctionner dans un cas, Mitzenmacher a prouvé que cela pouvait toujours fonctionner.

Mitzenmacher a également amélioré les filtres de Bloom appris. Il a montré que l'ajout d'un autre filtre de Bloom standard au processus, cette fois avant le RNN, peut pré-filtrer les cas négatifs et faciliter le travail du classificateur. Il a ensuite prouvé qu'il s'agissait d'une amélioration en utilisant la théorie qu'il a développée.

Les débuts des algorithmes avec prédiction ont suivi ce chemin cyclique : des idées novatrices, comme les filtres de Bloom appris, inspirent des résultats mathématiques rigoureux et une compréhension, qui à leur tour conduisent à d'autres idées nouvelles. Au cours des dernières années, les chercheurs ont montré comment intégrer les algorithmes avec prédictions dans les algorithmes d'ordonnancement, la conception de puces et la recherche de séquences d'ADN.

Outre les gains de performance, ce domaine fait également progresser une approche de l'informatique de plus en plus populaire : rendre les algorithmes plus efficaces en les concevant pour des utilisations typiques.

À l'heure actuelle, les informaticiens conçoivent souvent leurs algorithmes pour qu'ils réussissent dans le scénario le plus difficile, celui conçu par un adversaire qui tente de les faire échouer. Par exemple, imaginez que vous essayez de vérifier la sécurité d'un site web sur les virus informatiques. Le site est peut-être inoffensif, mais il contient le terme "virus informatique" dans l'URL et le titre de la page. La confusion est telle que même les algorithmes les plus sophistiqués ne savent plus où donner de la tête.

Indyk appelle cela une approche paranoïaque. "Dans la vie réelle, dit-il, les entrées ne sont généralement pas générées par des adversaires." La plupart des sites Web que les employés visitent, par exemple, ne sont pas aussi compliqués que notre hypothétique page de virus, et il est donc plus facile pour un algorithme de les classer. En ignorant les pires scénarios, les chercheurs peuvent concevoir des algorithmes adaptés aux situations qu'ils sont susceptibles de rencontrer. Par exemple, alors qu'à l'heure actuelle, les bases de données traitent toutes les données de la même manière, les algorithmes avec prédiction pourraient conduire à des bases de données qui structurent le stockage de leurs données en fonction de leur contenu et de leur utilisation.

Et ce n'est encore qu'un début, car les programmes qui utilisent l'apprentissage automatique pour améliorer leurs algorithmes ne le font généralement que de manière limitée. Comme le filtre de Bloom, la plupart de ces nouvelles structures n'intègrent qu'un seul élément d'apprentissage automatique. M. Kraska imagine un système entier construit à partir de plusieurs pièces distinctes, dont chacune repose sur des algorithmes avec des prédictions et dont les interactions sont régulées par des composants améliorés par les prédictions.

"Tirer parti de cela aura un impact sur de nombreux domaines".

Gageons qu'avec de tels systèmes, un site comme FLP se retrouve à peu près certain de ne jamais être accepté par un filtre de Bloom - ou un filtre de Bloom instruit. Qui sont - objectivement - des instruments de contrôle, et donc de fermeture.  (Note du traducteur).