Quatrième article de la série (après Intelligence artificielle : Un train peut en cacher un autre…, Quand faut-il utiliser une approche ML uniquement pour optimiser ? Réponse : jamais ! Vraiment ? Vraiment ! et Pourquoi il faut toujours privilégier l’approche prescriptive quel que soit le problème à résoudre) où je continue de développer l’approche hybride ML (machine learning ou apprentissage automatique (AA)) et OR (operations research ou recherche opérationnelle (RO)). Cet article est un peu plus technique que les trois précédents et présente 4 façons différentes de combiner l’AA et la RO.
Il y a au moins 4 façons de combiner les deux :
- Comme deux boîtes noires,
- L’utilisation de la RO pour améliorer les algorithmes en AA,
- L’utilisation de l’AA pour améliorer les algorithmes en RO,
- Une nouvelle combinaison de l’AA et de la RO avec le développement de nouveaux algorithmes.
Pour la première approche, on utilise en général d’abord l’AA pour faire des estimations qui dans un deuxième temps sont reprises comme entrants (input) pour optimiser avec de la RO. A noter qu’en 2023 et ce depuis au moins 2019, cette approche est maintenant relativement répandue et largement acceptée.
La deuxième et troisième approches sont en fait assez techniques. Quand cette combinaison est bien faite, les résultats sont assez surprenants.
Finalement, la dernière approche est la plus intéressante et n’en est qu’à ses balbutiements.
Je décris maintenant les 4 approches avec des exemples concrets et parfois un peu techniques. J’essayerai de les présenter en des termes abordables y compris pour des non experts dans le domaine.
L’AA et la RO comme deux boîtes noires
L’idée est de combiner la force de prédiction de l’AA avec la puissance de l’optimisation de la RO.
En général, on commence par utiliser des estimations trouvées avec des algorithmes en AA et puis — et de manière séparée — on utilise ces estimations comme entrants pour optimiser avec de la RO. Mon exemple favori est le suivant.
Vous êtes une compagnie de trains et vous devez réparer/remplacer vos voies. Bien sûr, vous voulez faire cela en privilégiant la sécurité et à moindre coût. Comment faire? En deux temps.
Tout d’abord, vous mettez des caméras sous vos wagons et vous laissez filer vos trains le long des voies pour prendre des photos de ces dernières. Vous recombinez les photos prises avec de l’AA et vous détectez sur ces photos les sections de voie qui demandent des réparations ou un remplacement, encore une fois avec de l’AA. Telle voie a une défectuosité de type A et nécessite une intervention d’une équipe de type α d’ici X mois. Cette première étape vous permet d’obtenir une cartographie de votre réseau mais pas un plan d’intervention. En effet, il se peut très bien que si vous envoyez une équipe pour réparer/remplacer un tronçon de voie, il y aurait moyen de faire des économies en demandant à la même équipe de réparer/remplacer une voie proche même si cette réparation/ce remplacement ne devrait être fait que plusieurs mois plus tard. Cette optimisation — faite dans un deuxième temps — se fait avec de la RO.
Dans cette approche[1], l’interaction entre l’AA et la RO est minime et on peut considérer que les deux sont utilisés de manière indépendante comme deux boîtes noires.
La RO pour améliorer l’AA
Je ne m’étendrais pas beaucoup sur l’utilisation de la RO pour améliorer les algorithmes en AA car… c’est exactement ce qui se passe en AA : on utilise des algorithmes de la RO pour optimiser les prédictions[2]. Ainsi le fameux algorithme de « gradient descent » utilisé en deep learning est en fait un algorithme issu de la RO[3].
L’AA pour améliorer la RO
La RO est essentiellement — mais pas uniquement — basée sur des règles (rule based). Quand ces règles sont applicables[4], elles sont d’une redoutable efficacité. Évidemment, on se retrouve souvent face à des situations où on ne sait pas quelle règle appliquer ou comment l’appliquer avec certitude.
Prenons un exemple : la recherche de solutions dans un arbre de recherche. Cet arbre est souvent gigantesque et si on sait que la solution optimale s’y trouve, on ne sait pas exactement où elle se trouve dans l’arbre. L’idée est alors de parcourir intelligemment seulement une partie de l’arbre en espérant pouvoir détecter très rapidement les sections de l’arbre les plus prometteuses. Ainsi on fera des « branching » à un nœud de l’arbre pour déterminer si un des sous-arbres débutant en ce nœud est intéressant ou pas. Il se peut que des règles (comme le « strong branching » par exemple) nous donnent une démarche très explicite à suivre mais il se peut aussi que nous soyons en terrain inconnu sans vraiment savoir quoi faire. Il se pourrait très bien que pour un certain type d’instances, l’AA puisse prédire comment brancher, c’est-à-dire quels sous-arbres considérer.
Le branchement est un exemple parmi tant d’autres. La grande majorité des algorithmes de recherche de solutions en RO sont basés sur des prises de décision qui peuvent dans certains cas être éclairées par des estimations de l’AA.
De nouveaux algorithmes basés sur une compréhension fondamentale de l’AA et de la RO
Finalement, après avoir considéré l’AA et la RO comme deux boîtes noires, avoir pris l’une pour améliorer l’autre, on peut combiner les deux de façon fondamentale en développant de nouveaux algorithmes. C’est à mon sens la combinaison la plus intéressante et j’irais même jusqu’à la décrire comme le futur de l’IA, du moins à court terme.
L’idée est de se rendre compte de la complémentarité des deux sciences pour les combiner de façon nouvelle : les inconvénients de l’une peuvent être — en partie — contrebalancés par les avantages de l’autre. Un exemple — maintenant classique — sont les GNN (Graph Neural Networks) qui combinent le concept de graphes (RO) à celui des réseaux de neurones (AA). Citons aussi par exemple l’excellente approche de l’équipe d’OptiCL[5] qui avec l’utilisation de l’AA permet de transformer des patterns en contraintes de la RO, ce qui permet à la fois de simplifier le processus d’inférence mais aussi de le contrôler (puisqu’on utilise des contraintes à respecter). Ces deux exemples ne sont que la pointe de l’iceberg et je m’attends à plein de développements futurs dans cette 4e façon
[1] Souvent on commence par utiliser de l’AA pour calculer des estimations et puis de la RO pour optimiser avec ces estimations mais l’inverse est parfois possible aussi.
[2] Ce n’est plus aussi simple depuis l’engouement général pour l’AA qui a amené plein de scientifiques d’horizons différents à introduire des approches différentes pour adapter, améliorer et complémenter l’AA.
[3] Et on peut imaginer améliorer cette approche avec des algorithmes de la RO encore plus puissants. Par exemple, le gradient descent est ce qu’on appelle une méthode du premier degré alors qu’il existe des méthodes dites du deuxième degré qui peuvent être plus rapides par exemple (mais qui ne sont pas aussi génériques ni faciles à implémenter).
[4] C’est-à-dire qu’on est en mesure non seulement de les appliquer mais aussi d’avoir une bonne estimation de leur efficacité.
