Lorsque vous demandez à une application de covoiturage de vous trouver une voiture, les ordinateurs de l'entreprise se mettent au travail. Ils savent que vous souhaitez atteindre votre destination rapidement. Ils savent que vous n'êtes pas le seul utilisateur à avoir besoin d'un trajet. Et ils savent que les conducteurs veulent minimiser le temps d'inactivité en prenant quelqu'un à proximité. Le travail de l'ordinateur, explique Saket Navlakha, professeur associé au Cold Spring Harbor Laboratory, est de mettre en relation les conducteurs et les passagers d'une manière qui maximise le bonheur de tous.
Les informaticiens comme Navlakha appellent cela la mise en correspondance bipartite. C'est la même tâche que celle effectuée par les systèmes qui associent les donneurs d'organes aux candidats à la transplantation, les étudiants en médecine aux programmes de résidence et les annonceurs aux espaces publicitaires. C'est donc l'objet d'études approfondies.
« C'est probablement l'un des 10 problèmes les plus célèbres de l'informatique. »
Saket Navlakha, professeur agrégé, CSHL
Aujourd'hui, il a trouvé un moyen de faire mieux en s'inspirant de la biologie. Navlakha a identifié un problème de correspondance bipartite dans le câblage du système nerveux. Chez les animaux adultes, chaque fibre musculaire du corps est associée à un seul neurone qui contrôle son mouvement. Cependant, au début de la vie, chaque fibre est ciblée par de nombreux neurones. Pour qu'un animal puisse se déplacer efficacement, les connexions excédentaires doivent être éliminées. Alors, quelles correspondances sont faites pour durer ?
Le système nerveux a une solution efficace. Navlakha explique que les neurones initialement connectés à la même fibre musculaire se font concurrence pour maintenir leur adéquation, en utilisant les neurotransmetteurs comme ressources de « surenchère ». Les neurones qui perdent cette enchère biologique peuvent prendre leurs neurotransmetteurs et enchérir sur d'autres fibres. De cette façon, chaque neurone et chaque fibre finissent par se retrouver avec un partenaire.
Navlakha a imaginé une méthode pour mettre en œuvre cette stratégie de mise en correspondance en dehors du système nerveux. « C'est un algorithme simple », explique-t-il. « Il ne s'agit que de deux équations. La première est la compétition entre les neurones connectés à la même fibre, et la deuxième est la réaffectation des ressources. »
Testé par rapport aux meilleurs programmes de jumelage bipartite existants, l'algorithme inspiré des neurosciences s'est révélé très performant. Il crée des appariements presque optimaux et laisse moins de parties sans correspondance. Dans les applications quotidiennes, cela pourrait se traduire par des temps d'attente plus courts pour les passagers des covoiturages et par moins d'hôpitaux sans résidents en médecine.
Navlakha souligne un autre avantage : le nouvel algorithme préserve la confidentialité. La plupart des systèmes de mise en correspondance bipartite nécessitent que les informations pertinentes soient transmises à un serveur central pour traitement. Mais dans de nombreux cas, des enchères en ligne à la mise en correspondance des organes des donneurs, une approche distribuée peut être préférée. Avec d'innombrables applications potentielles, Navlakha espère que d'autres adapteront le nouvel algorithme à leurs propres outils.
« C’est un excellent exemple de la manière dont l’étude des circuits neuronaux peut révéler de nouveaux algorithmes pour résoudre d’importants problèmes d’IA », ajoute-t-il.
