Programmation différentiable

La programmation différentiable est le descendant du deep learning, et représente la convergence de deux domaines algorithmiques : machine learning et optimisation numérique. La programmation différentiable ouvre la voie à une série de scénarios supply chain qui étaient considérés comme largement inextricables : optimisation conjointe des prix et des stocks, optimisation d’assortiment basée sur la fidélité, prévision de la demande pour des produits non-standard (ex. pierres précieuses, œuvres d’art), optimisation des flux multi-niveaux à grande échelle, optimisation conjointe sur plusieurs canaux, optimisation de stocks sous des valeurs électroniques de stock partiellement incorrectes, maximisation des flux à grande échelle sous de nombreuses contraintes, etc. Pour de nombreux autres scénarios déjà abordables par des méthodes alternatives, la programmation différentiable offre des résultats numériques supérieurs avec seulement une fraction des efforts, tant en termes d’investissement des data scientists que de ressources informatiques.

Programmation différentiable en Motion

No1 at the SKU-level in the M5 forecasting competition

Lead time forecasting with Differentiable Programming

Structured predictive modeling for Supply Chain

Solving Unsolvable Problems 1/3

The Origin Of A New Buzzword 2/3

Expressive Machine Learning 3/3

Application aux supply chain

Au cœur de la programmation différentiable (DP) se trouve une voie pour unifier des problèmes qui sont restés déconnectés trop longtemps et les résoudre conjointement : assortiment, tarification, prévision, planification, merchandising. Alors qu’une telle unification peut sembler incroyablement ambitieuse, la réalité est que les entreprises appliquent déjà une quantité folle de solutions bricolées à leurs propres processus pour faire face aux problèmes incessants générés par le fait que ces défis ont d’abord été mis en silo au sein de l’organisation. Par exemple, la tarification impacte évidemment la demande et pourtant la planification et la prévision sont presque toujours effectuées en ignorant complètement les prix.

DP ouvre une opportunité massive de fournir des décisions approximativement correctes en adoptant une perspective globale de l’entreprise, plutôt que d’être exactement à côté de la plaque en déplaçant les problèmes au sein de l’organisation au lieu de les résoudre.

Anecdotiquement, rechercher une correction approximative tout en prenant en compte l’entreprise dans son ensemble est exactement ce qui caractérise la plupart des organisations pilotées par des tableurs ; et, faute d’une technologie - telle que DP - capable d’adopter une perspective globale de l’entreprise, les tableurs restent l’option la moins terrible.

Le e-commerce

Pouvoir attribuer 100% des unités vendues à des clients connus représente une énorme quantité d’informations latentes sur le marché ; pourtant, lorsqu’il s’agit de tarification et d’optimisation de stocks, les informations de fidélité ne sont généralement même pas utilisées de nos jours. DP offre la possibilité de passer de la prévision des séries temporelles à la prévision par graphes temporels où chaque paire client-produit jamais observée compte ; conduisant à des décisions plus intelligentes tant pour les stocks que pour les prix.

Marques de luxe

L’optimisation de la tarification et des assortiments - jusqu’au niveau du magasin - a longtemps été considérée comme largement inextricable en raison de la rareté des données, c’est-à-dire d’un volume de ventes très faible par article par magasin - aussi bas qu’une unité vendue par produit, par magasin et par an. DP offre des approches permettant de fournir des classes de solutions fonctionnant sur des données ultra-rares, car elles sont conçues pour offrir une efficacité de données bien supérieure à celle des méthodes classiques de deep learning.

Marques de mode

L’optimisation conjointe des stocks et des prix est une exigence claire - la demande pour de nombreux articles pouvant être très sensible aux prix - cependant, l’optimisation conjointe de l’achat et de la tarification n’a pu être réalisée en raison de l’absence d’un outil capable même de saisir ce couplage - c’est-à-dire que la capacité d’acheter plus à un prix inférieur génère une demande accrue (et inversement). DP offre l’expressivité nécessaire pour relever ce défi.

Fabrication

L’optimisation numérique de réseaux multi-niveaux de grande envergure s’effondre lorsqu’elle est tentée avec des solveurs numériques classiques (voir « Beyond branch-and-cut optimization » ci-dessous). En effet, ces solveurs deviennent largement impraticables lorsqu’il s’agit de traiter des millions de variables ou des comportements stochastiques. Malheureusement, la fabrication présente les deux, avec de nombreuses variables et des comportements stochastiques. DP offre une approche pratique pour faire face au multi-niveaux sans trahir la complexité des schémas de flux réels au sein du réseau.

MRO (maintenance, repair, overhaul)

Si une pièce nécessaire à la réparation d’un système manque, alors l’ensemble du système - qui pourrait être un avion - reste en panne. Les prévisions probabilistes sont la première étape pour gérer de tels schémas de demande erratiques et intermittents, mais déterminer les subtilités de la co-occurrence des pièces requises et transformer cette analyse en recommandations de stocks exploitables était trop complexe pour être d’une utilité pratique. DP simplifie la résolution de tels problèmes.

Réseaux de distribution

Les cannibalismes au sein des réseaux de distribution - généralement entre produits mais parfois entre magasins - sont reconnus comme étant d’une importance primordiale depuis longtemps. Ce problème est amplifié par les promotions, conçues précisément pour détourner des clients d’une marque à une autre. DP offre la possibilité de traiter la cannibalisation en présence de promotions. Plutôt que de simplement « prévoir les promotions », DP offre la possibilité d’optimiser les promotions pour ce qu’elles sont : des accords rentables opérés conjointement par le canal de distribution et la marque.

Au-delà du battage médiatique de l’intelligence artificielle

L’intelligence artificielle (IA) a certainement été le mot à la mode technologique de 2018 et le battage médiatique est toujours présent en 2019. Cependant, bien que Lokad utilise largement des techniques correspondant habituellement au mot à la mode IA - par exemple le deep learning - nous avons été réticents à mettre l’accent sur la partie « IA » de la technologie de Lokad. En effet, en ce qui concerne l’optimisation quantitative de supply chain, les solutions d’IA prêtes à l’emploi ne fonctionnent tout simplement pas. Les supply chains ne ressemblent en rien, par exemple, à la vision par ordinateur : les données, les métriques et les tâches sont toutes extrêmement hétérogènes. En conséquence, les entreprises qui ont acheté des solutions d’IA supposément « clés en main » commencent à réaliser que ces solutions ne fonctionneront tout simplement jamais, sauf peut-être dans les situations les plus simples où des systèmes « idiots » basés sur des règles auraient tout aussi bien fonctionné. Au fond, les supply chains sont des systèmes complexes, fabriqués par l’homme, et il est généralement déraisonnable d’attendre que le système d’IA - basé uniquement sur les données - redécouvre par lui-même des insights fondamentaux sur le domaine tels que:

• faire des promotions pour une marque de luxe est formellement interdit.
• les commandes de vente négatives dans l’ERP sont en réalité des retours produits.
• les produits alimentaires frais doivent être transportés dans des plages de température spécifiées.
• des variantes en termes de couleurs peuvent constituer de bons substituts vestimentaires, mais pas des variantes en termes de tailles.
• la maintenance des avions est déterminée par les heures de vol et les cycles de vol.
• les ventes au Royaume-Uni sont en réalité en GBP même si l’ERP affiche l’EUR comme monnaie.
• les gens achètent des pièces détachées pour leurs véhicules, et non pour eux-mêmes.
• chaque diamant est unique, mais les prix dépendent principalement du carat, de la clarté, de la couleur et de la coupe.
• toute pièce NOGO manquante d’un avion entraîne la mise au sol de l’avion.
• de nombreuses usines chimiques mettent des semaines à redémarrer après avoir été arrêtées.

Dans un futur lointain, il pourrait arriver qu'un jour le machine learning parvienne à émuler l'intelligence humaine et obtienne des résultats face à des problèmes épineux, toutefois, jusqu'à présent, des résultats n'ont été obtenus que sur des problèmes relativement restreints. Les technologies de machine learning repoussent chaque année les limites de ce qui constitue un problème « restreint », et après des décennies d'efforts, des problèmes importants tels que la conduite autonome sécurisée et des traductions automatisées acceptables sont résolus, ou très proches de l'être. Néanmoins, comme l'illustre la liste ci-dessus, les supply chains restent désespérément trop hétérogènes pour une application directe des algorithmes de machine learning standards. Même si le deep learning offre à ce jour les capacités de généralisation les plus puissantes, il nécessite tout de même l'intervention d'un supply chain scientist pour cadrer le défi de manière suffisamment restreinte afin que les algorithmes puissent fonctionner.

À cet égard, le deep learning a connu un succès phénoménal car, contrairement à de nombreuses approches antérieures en machine learning, le deep learning est profondément compositionnel : il est possible d’adapter de façon extensive la structure du modèle pour mieux apprendre dans une situation spécifique. Adapter la structure du modèle est différent d’adapter l’entrée du modèle - une tâche connue sous le nom de feature engineering - qui était typiquement la seule option disponible pour la plupart des algorithmes de machine learning non profonds tels que les random forests.

Cependant, comme les frameworks de deep learning ont émergé des « Grands Problèmes » du machine learning, à savoir la vision par ordinateur, la reconnaissance vocale, la synthèse vocale, la traduction automatisée, ces frameworks ont été conçus et ajustés en profondeur pour des scénarios qui ne ressemblent littéralement en rien aux problèmes rencontrés dans les supply chains. Ainsi, bien qu’il soit possible de tirer parti de ces frameworks pour des objectifs d’optimisation de la supply chain, cela n’a pas été une démarche facile ni légère. En conclusion, avec les frameworks de deep learning, beaucoup peut être réalisé pour les supply chains, mais le décalage d’impédance entre les supply chains et les frameworks de deep learning existants est important ; augmentant les coûts, les délais, et limitant l’applicabilité réelle de ces technologies.

Au-delà de l’optimisation branch-and-cut

La plupart des problèmes dans les supply chains présentent à la fois un volet d’apprentissage - provoqué par une connaissance imparfaite du futur, une connaissance imparfaite de l’état actuel du marché, et parfois même une connaissance imparfaite du système de supply chain lui-même (par exemple, des inexactitudes de stocks) - mais également un volet d’optimisation numérique. Les décisions doivent être optimisées en fonction des leviers économiques tout en satisfaisant de nombreuses contraintes non linéaires (par exemple, les quantités minimales de commande lors des achats ou les tailles de lots lors de la production).

Du côté de l’optimisation numérique, la programmation en nombres entiers et ses techniques associées telles que le branch-and-cut dominent le domaine depuis des décennies. Cependant, ces algorithmes branch-and-cut et leurs solutions logicielles associées n’ont généralement pas réussi à offrir la flexibilité et l’évolutivité nécessaires pour fournir des solutions opérationnelles à de nombreux défis de supply chain, voire la plupart d’entre eux. La programmation en nombres entiers est un outil fantastiquement performant pour résoudre des problèmes serrés avec peu de variables (par exemple, le placement de composants au sein d’un appareil électronique grand public), mais elle présente des limitations drastiques lorsqu’il s’agit de problèmes de grande envergure impliquant de l’aléatoire (par exemple, le rééquilibrage des stocks entre 10 millions de SKU face à une demande probabiliste et des temps de transport probabilistes).

L’un des aspects les moins appréciés du deep learning est que son succès résulte autant d’avancées dans le domaine de l’apprentissage que d’avancées dans le domaine de l’optimisation. En effet, la communauté scientifique a découvert que des algorithmes d’une efficacité redoutable réalisent des optimisations à grande échelle. Non seulement ces algorithmes d’optimisation « deep learning » - tous basés sur la descente de gradient stochastique - sont bien plus efficaces que leurs homologues branch-and-cut, mais ils s’adaptent également beaucoup mieux au matériel informatique dont nous disposons, à savoir les CPU SIMD et les (GP)GPU, ce qui, en pratique, offre un gain de vitesse supplémentaire de deux à trois ordres de grandeur. Ces avancées en optimisation numérique pure sont d’une grande pertinence pour les supply chains afin d’optimiser les décisions. Cependant, si les frameworks de deep learning étaient déjà quelque peu inadaptés pour aborder les problèmes d’apprentissage dans les supply chains, ils le sont encore moins pour aborder les problèmes d’optimisation dans les supply chains. En effet, ces problèmes d’optimisation dépendent encore davantage de l’expressivité du framework pour permettre aux supply chain scientists d’implémenter les contraintes et les métriques à faire respecter et à optimiser respectivement.

Vers la Programmation Différentiable

En théorie, il n’y a pas de différence entre la théorie et la pratique. Mais, en pratique, il y en a une. Walter J. Savitch, Pascal: Une Introduction à l’Art and the Science of Programming (1984)

Differentiable Programming (DP) est la solution pour apporter aux supply chains le meilleur de ce que deep learning a à offrir à la fois du côté de l’apprentissage et du côté de l’optimisation numérique. Grâce à DP, les Supply Chain Scientist peuvent tirer le meilleur parti de leurs connaissances humaines pour élaborer des recettes numériques en adéquation – en profondeur – avec les objectifs commerciaux. Il n’existe pas de délimitation absolue entre deep learning et differentiable programming : c’est plutôt un continuum allant des systèmes les plus évolutifs (deep learning) aux systèmes les plus expressifs (differentiable programming) avec de nombreux concepts de programmation qui deviennent progressivement disponibles – au détriment de l’évolutivité brute – lors du passage à differentiable programming. Pourtant, notre expérience chez Lokad indique que passer d’outils principalement conçus pour la vision par ordinateur à des outils conçus pour relever les défis de supply chain fait précisément la différence entre un prototype « intéressant » qui ne voit jamais le jour en production et un système industriel déployé à grande échelle.

Le mode d’usage typique est un point subtil mais important. Du point de vue du “Big AI”, le temps d’entraînement peut être (presque) arbitrairement long : il est acceptable qu’un réseau de calcul soit entraîné pendant des semaines, voire des mois. Ensuite, le réseau de calcul résultant doit généralement être évalué en temps réel (par exemple, la reconnaissance de motifs pour la conduite autonome). Cet angle est complètement différent de celui des supply chains, où les meilleurs résultats sont obtenus en ré-entraînant le réseau à chaque fois. De plus, d’un point de vue DP, les paramètres entraînés sont fréquemment les résultats mêmes que nous cherchons à obtenir, rendant ainsi la contrainte de l’évaluation en temps réel caduque. Les attentes concernant les données d’entrée, tant en termes de granularité, de variété que de volume, sont également très différentes. Typiquement, la perspective du “Big AI” met l’accent sur une quantité quasi infinie de données d’entraînement (par exemple, toutes les pages de texte du web), où le défi principal consiste à trouver des méthodes d’une évolutivité remarquable capables d’exploiter efficacement ces ensembles de données massifs. En revanche, les problèmes de supply chain doivent être traités avec une quantité limitée de données hautement structurées mais diversifiées. Cela oriente le deep learning vers des frameworks basés sur les tenseurs, qui peuvent être massivement accélérés grâce à du matériel informatique dédié, d’abord les GPUs, et désormais de plus en plus les TPUs. Differentiable Programming, reposant sur la descente de gradient stochastique, présente également de nombreuses bonnes propriétés en matière d’accélération matérielle, mais dans une moindre mesure par rapport aux graphes statiques des opérations sur tenseurs. L’importance des recettes numériques stochastiques est double. Premièrement, ces recettes jouent un rôle important du point de vue de l’apprentissage. Les auto-encodeurs variationnels ou les dropouts sont des exemples de telles recettes numériques. Deuxièmement, ces recettes jouent également un rôle important dans la modélisation afin de prendre correctement en compte les comportements probabilistes au sein des systèmes de supply chain (par exemple, des délais de livraison variables). Inversement, il existe un énorme fossé entre differentiable programming et Mixed integer Programming : l’approche dominante au cours des dernières décennies a été de réaliser des optimisations numériques complexes.

Pour défendre les outils de Mixed integer Programming, ces outils – lorsqu’ils parviennent à s’attaquer à un problème – peuvent parfois prouver – au sens mathématique – qu’ils ont obtenu la solution optimale. Ni le deep learning ni differentiable programming ne fournissent de preuve formelle à cet égard.

Conclusions

Differentiable Programming est une avancée majeure pour les supply chains. Il est construit sur le deep learning, qui a prouvé un succès formidable pour résoudre de nombreux problèmes de “Big AI” tels que la vision par ordinateur, mais il a été reconçu en profondeur pour être adapté aux défis du monde réel auxquels sont confrontées les supply chains. Lokad s’est appuyé sur sa technologie de prévision basée sur le deep learning pour opérer la transition vers Differentiable Programming, qui constitue la prochaine génération de notre technologie prédictive. Cependant, DP est bien plus qu’une simple technologie prédictive : il unifie l’optimisation et l’apprentissage, offrant ainsi des solutions à une multitude de problèmes qui n’avaient auparavant aucune solution viable.