Imaginez que vous essayez de résoudre un nœud massif et emmêlé d'un problème. Dans le monde de l'informatique, plus précisément dans un domaine appelé apprentissage automatique (machine learning), nous demandons souvent aux ordinateurs de trouver la « meilleure » façon de faire des prédictions, comme deviner si un client achètera un produit ou si un patient présente une certaine condition. Pendant longtemps, les scientifiques ont cru qu'il y avait généralement une seule réponse unique, une réponse parfaite — un « modèle doré » qui est absolument le meilleur. Mais il existe un rebondissement fascinant dans cette histoire appelé l'effet Rashomon. Nommé d'après un film célèbre où quatre témoins racontent des versions différentes du même événement, cet effet décrit une réalité où de nombreux modèles complètement différents peuvent obtenir des performances presque identiques. Ils sont tous « assez bons », mais ils peuvent utiliser des indices différents ou regarder les données de manières totalement différentes.

Pourquoi cela importe-t-il ? Parce que si vous ne cherchez que ce modèle « doré » unique, vous pourriez passer à côté d'une foule entière d'alternatives tout aussi bonnes. Certaines de ces alternatives pourraient être plus sûres, plus faciles à comprendre ou plus équitables. Pour étudier cela, les chercheurs recherchent un ensemble de Rashomon : une collection de tous les modèles qui sont presque parfaits. Le défi, c'est que trouver cet ensemble revient à essayer de compter chaque grain de sable sur une plage. C'est un travail colossal et désordonné, surtout quand les données ne sont pas de simples réponses par « oui ou non » (comme rouge ou bleu) mais incluent des caractéristiques continues — des nombres qui peuvent être n'importe quoi, comme la température, la taille ou le prix, et qui peuvent être divisés en des millions de points différents.

C'est ici qu'une nouvelle étude intervient, introduisant un nouvel outil ingénieux appelé ArborEnum. Voyez les chercheurs comme des explorateurs tentant de cartographier une forêt dense et brumeuse. Auparavant, s'ils voulaient cartographier la forêt, ils devaient la découper en de neat carrés de grille (un processus appelé binarisation) juste pour la rendre gérable. Mais en faisant cela, ils manquaient souvent des sentiers cachés, des arbres rares et des raccourcis importants qui existaient dans le paysage continu et sauvage. Les auteurs de cet article ont construit un nouveau type de boussole qui leur permet d'explorer la forêt exactement telle qu'elle est, avec toutes ses courbes lisses et continues, sans la découper au préalable. Ils ont découvert qu'en ignorant la fluidité des données, les anciennes méthodes manquaient de larges pans de « bons » modèles. Leur nouvelle méthode peut lister ces modèles beaucoup plus rapidement — parfois des centaines de fois plus vite — que les méthodes précédentes. Mieux encore, ils ont créé une version « intelligente » qui commence par un croquis grossier de la forêt et l'affine de plus en plus, devenant plus détaillé à mesure qu'on la laisse tourner, de sorte que vous puissiez vous arrêter dès que vous avez assez d'informations. Ils ont prouvé, par des expériences sur des données réelles, que cette approche permet non seulement de gagner du temps, mais aussi de trouver des caractéristiques importantes et des variations de modèles que les anciennes méthodes basées sur la grille avaient totalement ignorées.

L'histoire de la forêt et de la grille

Imaginez que vous êtes un détective essayant de résoudre un mystère. Vous avez un tas d'indices et vous devez construire un arbre de décision — un organigramme de questions — pour découvrir qui l'a commis. Habituellement, vous poseriez des questions telles que : « Le suspect est-il plus grand que 1m80 ? » ou « Le suspect porte-t-il un chapeau ? ». Dans les vieilles époques, les informaticiens devaient transformer chaque indice en une simple question de type « oui ou non » avant de pouvoir commencer à construire leur arbre. Si un indice était un nombre, comme « La taille du suspect est de 1m80 », ils devaient le diviser en compartiments : « Est-il de moins de 1m70 ? », « Est-il entre 1m70 et 1m85 ? », « Est-il de plus de 1m85 ? ».

Ce processus de découpage est appelé binarisation. C'est comme prendre une rivière fluide et la forcer dans une série de canaux en béton carrés. Le problème est qu'en forçant l'eau dans ces boîtes rigides, vous pourriez manquer un petit remous parfait ou un courant caché qui coule juste entre les fissures. Dans le monde de l'apprentissage automatique, cela signifie que vous pourriez manquer une division parfaite des données parce que votre « grille » n'avait pas de ligne exactement là où les données en avaient besoin.

L'effet Rashomon est l'idée qu'il n'existe pas un seul organigramme parfait. Il existe des dizaines, voire des centaines de différents organigrammes qui résolvent tous le mystère avec la même précision. Certains utiliseront la taille, d'autres le poids, ou une combinaison des deux. L'ensemble de Rashomon est la collection de tous ces organigrammes tout aussi bons. Trouver cet ensemble est extrêmement utile car cela aide à comprendre quels indices sont réellement importants et lesquels ne sont que des coups de chance. Si un indice apparaît dans presque tous les bons organigrammes, c'est probablement une véritable clé du mystère. S'il n'apparaît que dans un seul, il peut s'agir d'un simple hasard.

Le problème des anciennes cartes

Pendant longtemps, la seule façon de trouver cet ensemble de Rashomon était d'utiliser la méthode des « canaux en béton » (la binarisation). Les chercheurs divisaient les nombres continus en quelques compartiments, puis essayaient de trouver tous les bons arbres. Mais cela présentait deux problèmes majeurs. Premièrement, l'espace de recherche était déjà immense ; avec seulement 20 caractéristiques binaires, il y avait déjà plus d'arbres que de grains de sable sur Terre. Deuxièmement, en découpant les données, ils jetaient de l'information. Ils pouvaient manquer une division qui se produisait à un nombre très précis, comme 1m79, parce que leurs compartiments étaient seulement à 1m75 et 1m85.

Le papier montre que cette binarisation « grossière » est comme chercher une aiguille dans une botte de foin en ne regardant que la couche supérieure de foin. Vous pourriez trouver une aiguille, mais vous manquerez celles qui sont enfouies plus profondément ou celles qui ont des formes légèrement différentes. Les auteurs ont constaté qu'en forçant les données dans ces compartiments rudimentaires, ils manquaient de nombreux arbres importants, de caractéristiques importantes et de la véritable variété des solutions (la multiplicité prédictive).

La nouvelle boussole : ArborEnum

Entrez dans l'ère d'ArborEnum. Les auteurs ont construit le premier algorithme capable d'explorer la « forêt continue » sans la découper au préalable. Au lieu de forcer les données dans des compartiments carrés, ArborEnum respecte l'ordre naturel des nombres. Il traite les données comme une ligne lisse et cherche les meilleurs endroits pour la couper, sachant qu'il existe des milliers de points de coupure possibles.

Pour ce faire, ils ont utilisé une astuce ingénieuse. Imaginez que vous cherchiez le meilleur endroit pour couper une corde. Vous n'avez pas besoin de tester chaque millimètre. Si vous savez que couper à 10 pouces est mauvais, et que couper à 11 pouces est également mauvais, vous pouvez probablement deviner que couper à 10,5 pouces ne sera pas génial non plus. Les auteurs ont développé une manière d'utiliser ces « bornes » pour sauter par-dessus de vastes sections de la corde qui n'ont pas besoin d'être testées. Ils appellent cela l'élagage (pruning). C'est comme avoir une carte qui vous dit : « Ne vous donnez pas la peine de regarder dans toute cette vallée ; le trésor n'est pas là. »

Ils ont également introduit un système de « proxy ». Voyez un proxy comme une estimation rapide et grossière. Avant de faire le travail difficile de vérifier chaque possibilité, l'algorithme fait une estimation rapide et approximative pour voir si un chemin vaut la peine d'être exploré. Si l'estimation dit « pas question », il saute tout le segment. Si l'estimation dit « peut-être », il creuse davantage. Cela permet à l'algorithme de fonctionner incroyablement vite. Dans leurs tests, cette méthode était 270 fois plus rapide que les méthodes existantes en moyenne, et dans certains cas, la différence était encore plus spectaculaire.

La caractéristique « Anytime » : Un croquis qui s'améliore

L'une des parties les plus cool d'ArborEnum est son algorithme « anytime » (à tout instant). Habituellement, si vous voulez une carte parfaite, vous devez attendre que l'ordinateur termine tout son travail. Mais et si vous avez besoin d'une réponse maintenant ? La version « anytime » d'ArborEnum commence par un croquis très grossier de la forêt. Il peut ne regarder que quelques points de coupure clés. Il vous donne une liste de bons arbres basés sur ce croquis rudimentaire.

Ensuite, au fur et à mesure que vous le laissez tourner, il ajoute de plus en plus de points de coupure à sa carte. Il affine le croquis, comblant les lacunes. Plus vous lui donnez de temps, plus la liste des arbres devient détaillée et précise. Finalement, si vous le laissez tourner assez longtemps, il trouve la liste exacte et parfaite de tous les bons arbres. Le meilleur dans tout ça ? Vous pouvez l'arrêter à tout moment. Si vous avez besoin d'une réponse en 5 minutes, vous obtenez une approximation. Si vous avez 5 heures, vous obtenez une réponse quasi parfaite. Les auteurs ont trouvé que même avec ce « départ brut », la méthode récupérait presque tous les arbres importants, et le temps supplémentaire nécessaire pour affiner la carte était minime — seulement environ 2,7 % de temps en plus que l'exécution de la version non raffinée sur l'ensemble des points finaux.

Ce qu'ils ont trouvé et ce que cela signifie

Les expériences ont été menées sur 20 ensembles de données réels, allant de la prédiction des locations de vélos aux défauts de cartes de crédit. Les résultats sont clairs :

1. La binarisation grossière manque beaucoup de choses : Lorsqu'ils ont comparé l'ancienne méthode de « découpage » à la nouvelle méthode continue, l'ancienne méthode manquait de nombreux arbres et de caractéristiques importantes. C'était comme regarder une photo à travers une fenêtre embrumée ; on voyait la forme générale, mais on manquait les détails.
2. La vitesse est réelle : La nouvelle méthode est des ordres de grandeur plus rapide. Sur un ensemble de données appelé « Bike », la nouvelle méthode optimale a terminé 63 fois plus vite que la seule autre méthode capable de terminer le travail.
3. La précision est élevée : Même en utilisant la méthode « proxy » rapide et approximative, ils ont récupéré 94,5 % à 100 % des arbres que la méthode parfaite a trouvés. Cela signifie que vous pouvez obtenir presque tous les avantages de l'ensemble de Rashomon sans attendre une éternité.
4. L'approche « Anytime » fonctionne : La méthode qui commence de manière brute et s'améliore s'est révélée très efficace. Elle a trouvé des caractéristiques importantes très tôt, ce qui signifie que vous pouvez obtenir des informations utiles rapidement sans attendre le calcul complet.

L'article ne prétend pas avoir résolu tous les problèmes de l'apprentissage automatique. Il ne dit pas que les caractéristiques continues sont le seul moyen de faire les choses, ni que cette méthode fonctionne pour chaque type de modèle. Mais il démontre, avec des preuves solides issues d'expériences, que pour les arbres de décision, traiter les données continues comme des données continues change la donne. Cela nous permet de voir l'image complète de l'« ensemble de Rashomon » sans perdre la raison (ou nos ordinateurs) face à la complexité.

En résumé, ArborEnum est une nouvelle façon d'explorer le paysage des bonnes solutions. Cela nous empêche de forcer le monde dans une grille qui ne lui correspond pas, et nous permet plutôt de parcourir les sentiers lisses et continus où les vraies réponses se cachent souvent. Que vous soyez un scientifique des données cherchant le meilleur modèle ou simplement une personne curieuse de savoir comment les ordinateurs prennent des décisions, ce travail suggère qu'il y a plus de bonnes réponses qu'on ne le pensait, et que nous avons désormais un meilleur moyen de les trouver.