Intelligence artificielle Quand faut-il utiliser une approche ML uniquement pour optimiser ? Réponse :...

Pour approfondir le sujet

Sur le même thème :

META AI dévoile BlenderBot 3, un projet de recherche sur l’IA conversationnelle

Après avoir présenté BlenderBot en 2020, la mouture BlenderBot 2.0 en 2021, META a dévoilé BlenderBot 3 le 5 août dernier. Comme pour ses...

Reconnaissance faciale : la plateforme « From Numbers to Name » aide à identifier les victimes de l’Holocauste

Le deep learning est aujourd'hui utilisé dans de nombreux domaines, il l'est de plus en plus dans celui de l'histoire. Daniel Patt, un ingénieur...

Lancement de l’appel à candidatures de la phase V des pôles de compétitivité

Alors que la phase IV (2019-2022) des pôles de compétitivité prendra fin en décembre 2022, Bruno Le Maire, Ministre de l’Economie, des Finances et...

Focus sur SMART, programme de l’IARPA visant à identifier et surveiller les constructions à grande échelle grâce au machine learning

L'IARPA (Intelligence Advanced Research Projects Activity), la branche de recherche de la communauté du renseignement aux Etats-Unis, a lancé le programme SMART (Space-based Machine...

Quand faut-il utiliser une approche ML uniquement pour optimiser ? Réponse : jamais ! Vraiment ? Vraiment !

Dans un premier article, j’ai parlé de l’approche hybride ML et OR (Machine Learning et Operations Research). Il s’agit d’une série d’articles où j’explique pourquoi cette approche hybride est nettement supérieure. Dans cet article, je développe l’efficacité de l’optimisation.

On entend souvent parler de projets qui ont été optimisés par du ML (par exemple DeepMind AI Reduces Google Data Centre Cooling Bill by 40%). Pour quelqu’un qui n’y connaît rien, il est bien tentant de croire qu’il s’agit d’une bonne idée. Il n’en est rien comme l’indique le titre de cet article. Ce n’est pas le cas. Du tout.

Prenons le PVC (Problème du Voyageur de Commerce) plus connu sous le nom de TSP (Travelling Salesman Problem). C’est sans doute le problème le plus étudié en recherche opérationnelle. Le but de ce problème est de déterminer une tournée complète qui passe une seule fois par chaque ville et ce pour un coût minimal (distance minimale, temps minimal…). C’est un exemple typique de problèmes NP-difficiles, c’est-à-dire un problème qui même avec un super ordinateur ou des ordinateurs en parallèle ne se résout pas aisément. C’est un problème qui se résout en machine learning (voir par exemple Learning TSP requires rethinking generalization) mais mal jusqu’à présent. Prenons la résolution exacte, c’est-à-dire la recherche d’une solution optimale (avec preuve d’optimalité). Pour autant que je sache, les meilleures approches en ML peuvent résoudre ce problème avec des instances d’environ 100 villes. C’est pas mal mais un étudiant en recherche opérationnelle de première année recevrait un F ou un 0/20 pour un tel résultat ! En effet, en recherche opérationnelle, les meilleures approches (Concorde, voir Certification of an optimal TSP tour through 85,900 cities) peuvent résoudre ce problème exactement avec environ… 100 000 villes ! Et l’on parle d’un problème NP-difficile! Ce qui veut dire que si vous avez un algorithme pour résoudre le TSP avec 100 villes et que vous aimeriez résoudre le problème avec 120 villes… vous allez sans doute devoir changer d’algorithme ! 100 versus 100 000 ! Cela donne le vertige.

Il ne faut pas abandonner la voie du machine learning pour autant mais au lieu de vouloir réinventer la roue, il faudrait sans doute mieux reprendre ce qui se fait en recherche opérationnelle et y ajouter du machine learning. Encore faut-il savoir comment le faire… mais ce sera le sujet d’un autre article !

Ce que j’ai présenté pour le TSP est en fait valide pour tous les problèmes combinatoires, jusqu’à présent en tout cas.

Une dernière chose, on reproche souvent à la recherche opérationnelle d’être lente. En effet, il faut parfois des heures voire des jours ou même des semaines pour obtenir une solution. Mais j’aimerais attirer l’attention sur le fait que tout d’abord, on n’a pas forcément besoin d’une solution optimale ou d’une solution avec preuve d’optimalité. Ensuite, il existe des techniques pour faire de l’optimisation en temps réel. Tout dépend ce que l’on cherche et si l’on veut une solution avec preuve d’optimalité, cela a un coût…


1ère Marketplace de l'IA et de la transformation numérique vous recommande :
 

Contributeur expert

Nikolaj Van Omme

Ttulaire d’un MSc en mathématiques pures, d’un MSc en informatique théorique et d&#

Partager l'article

META AI dévoile BlenderBot 3, un projet de recherche sur l’IA conversationnelle

Après avoir présenté BlenderBot en 2020, la mouture BlenderBot 2.0 en 2021, META a dévoilé BlenderBot 3 le 5 août dernier. Comme pour ses...

Reconnaissance faciale : la plateforme « From Numbers to Name » aide à identifier les victimes de l’Holocauste

Le deep learning est aujourd'hui utilisé dans de nombreux domaines, il l'est de plus en plus dans celui de l'histoire. Daniel Patt, un ingénieur...

Lancement de l’appel à candidatures de la phase V des pôles de compétitivité

Alors que la phase IV (2019-2022) des pôles de compétitivité prendra fin en décembre 2022, Bruno Le Maire, Ministre de l’Economie, des Finances et...

Focus sur SMART, programme de l’IARPA visant à identifier et surveiller les constructions à grande échelle grâce au machine learning

L'IARPA (Intelligence Advanced Research Projects Activity), la branche de recherche de la communauté du renseignement aux Etats-Unis, a lancé le programme SMART (Space-based Machine...
Recevoir une notification en cas d'actualité importante    OK Non merci