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

Pour approfondir le sujet

Sur le même thème :

Retour sur le Soph.I.A Summit 2022 : 3 jours au cœur de la recherche en intelligence artificielle à Sophia Antipolis

La cinquième édition du Soph.I.A Summit, Organisé par Université Côte d’Azur, la Communauté d’Agglomération de Sophia Antipolis et le Sophia Club Entreprises avec le...

OpenAI officialise une nouvelle version pour son modèle de langage GPT-3

L’entreprise de recherche et de déploiement d’IA OpenAI officialise son nouveau modèle ‘text-davinci-003’ qui s’ajoute à la famille de modèles GPT-3 et qui s’appuie...

Focus sur la conférence « IA et profilages : risques éthiques et juridiques » de Céline Castets-Renard

Le Centre international de criminologie comparée (CICC), rattaché à l'Université de Montréal et à l'Université du Québec à Trois-Rivières, a organisé avec l'Observatoire des...

Le Conseil National de la Refondation lance son volet numérique

Le Conseil national de la refondation (CNR), lancé début septembre par  Emmanuel Macron, porte sur 7 thématiques. La thématique consacrée au numérique explore la...

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 :
RML (Responsible Machine Learning) par Axionable

Notre solution dédiée à la réalisation de projets de machine learning responsable pour vous accompagner dans le cadrage, le développement et l'industr...

 

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

Retour sur le Soph.I.A Summit 2022 : 3 jours au cœur de la recherche en intelligence artificielle à Sophia Antipolis

La cinquième édition du Soph.I.A Summit, Organisé par Université Côte d’Azur, la Communauté d’Agglomération de Sophia Antipolis et le Sophia Club Entreprises avec le...

OpenAI officialise une nouvelle version pour son modèle de langage GPT-3

L’entreprise de recherche et de déploiement d’IA OpenAI officialise son nouveau modèle ‘text-davinci-003’ qui s’ajoute à la famille de modèles GPT-3 et qui s’appuie...

Focus sur la conférence « IA et profilages : risques éthiques et juridiques » de Céline Castets-Renard

Le Centre international de criminologie comparée (CICC), rattaché à l'Université de Montréal et à l'Université du Québec à Trois-Rivières, a organisé avec l'Observatoire des...

Le Conseil National de la Refondation lance son volet numérique

Le Conseil national de la refondation (CNR), lancé début septembre par  Emmanuel Macron, porte sur 7 thématiques. La thématique consacrée au numérique explore la...
Recevoir une notification en cas d'actualité importante    OK Non merci