Les entiers et l'incertitude dans la programmation différentiable
Markus Leopoldseder (Director of Knowledge - Global Manufacturing and Supply Chain Practice at McKinsey) a soulevé deux questions pertinentes concernant l’applicabilité de Differentiable Programming (DP) aux fins de supply chain. Dans cet article assez technique, nous essaierons de fournir quelques éclairages sur la manière dont les contraintes d’entiers et l’uncertainty sont respectivement traités en DP. Ce n’est qu’un premier aperçu de l’approche de Lokad. Nous prévoyons de publier ultérieurement des recettes détaillées sur docs.lokad.com.
Comment DP s’applique-t-il aux variables entières ? En effet, si la fonction objectif prend des entiers comme entrées, elle pourrait ne pas être différentiable.
Du point de vue de la supply chain, la plupart des décisions sont discrètes : on ne peut pas commander 4.2 unités d’un produit, c’est soit 4, soit 5. Ainsi, nous recherchons – tant du point de vue de l’apprentissage que de l’optimisation – des méthodes qui fonctionnent bien avec des entiers. Comme notre lecteur l’a souligné avec perspicacité, les paramètres en DP sont des nombres, et ces paramètres ne peuvent être contraints à être des entiers, car cette approche n’est pas compatible avec le stochastic gradient descent which lies at the core of DP.
Il existe plusieurs manières d’obtenir des décisions discrètes et leurs fonctions objectif discrètes correspondantes via DP, allant d’approches naïves mais simples à des méthodes carrément compliquées mais inégalées en matière d’optimisation numérique.
L’approche la plus simple consiste à interpoler la fonction objectif au moment de l’entraînement, puis à arrondir les résultats lors de l’évaluation. Par exemple, si nous recherchons une quantité de commande – censée être un entier – la fonction objectif peut être étendue à des nombres arbitraires par interpolation. Cela fonctionne bien lorsqu’on considère des systèmes qui, malgré leur caractère discret, présentent des comportements relativement linéaires. Cependant, face à une forte non-linéarité, telle qu’une contrainte MOQ (quantité minimale de commande), cela ne fonctionne pas aussi bien.
Pour gérer de telles situations, la fonction objectif peut être remplacée par une fonction de substitution, une fonction qui approxime la fonction objectif originale, mais de manière lisse et différentiable. Par exemple, la fonction échelon habituellement associée au coût de pénalité d’une contrainte MOQ peut être remplacée par une fonction sigmoïde. Époque après époque, la fonction de substitution est progressivement déformée pour devenir numériquement plus proche de la fonction objectif originale.
Du point de vue de la supply chain, d’après notre expérience, les fonctions de substitution fonctionnent de manière surprenante. En effet, les situations où il est impossible d’itérer de manière fluide vers de bonnes solutions sont rares. Les problèmes de supply chain ne sont pas des énigmes cryptographiques où le fait de modifier un seul bit d’une solution fait tout dérailler. Par exemple, si passer une commande de 490 unités est rentable alors qu’une contrainte MOQ existe à 500, il y a de fortes chances que la commande de 500 unités soit également rentable.
Ensuite, il existe des approches plus sophistiquées inspirées des autoencodeurs variationnels : les sorties fractionnaires d’une couche (comme dans les “deep learning layers”) sont converties en une déviation aléatoire entière obtenue à partir d’une distribution arbitraire, par exemple une distribution de Poisson. Grâce à ce mécanisme, le programme, bien qu’opérant uniquement avec des paramètres fractionnaires, produit des sorties entières qui peuvent ensuite être injectées dans la fonction objectif. Le stochastic gradient descent répète le processus un grand nombre de fois, à la manière de Monte-Carlo, garantissant ainsi que les lois régissant la génération des déviations aléatoires entières sont correctement ajustées.
Enfin, les approches les plus complexes, telles qu’AlphaZero, reposent sur l’introduction d’une liste complexe de couches (par exemple, un réseau de calcul “deep”) se terminant typiquement par une couche de type Softmax afin de générer des décisions discrètes. Ces approches offrent des résultats à la pointe de la technologie sur des problèmes d’optimisation hautement non linéaires, comme l’a démontré la victoire d’AlphaGo (plus tard redéfini en tant qu’AlphaZero) contre Lee Sedol. DP peut également tirer parti de ces méthodes – il suffit de réduire la profondeur et la complexité du réseau pour maintenir le surcoût computationnel sous contrôle. Heureusement, en pratique, bien que résoudre un problème de MOQ soit relativement difficile, ce n’est pas aussi difficile que de battre un champion du monde de Go en matière de problèmes d’optimisation, et les réseaux “shallow” (par les standards du deep learning) accomplissent déjà beaucoup.
Offrir des moyens plus directs et pratiques de gérer des situations discrètes, comme on les trouve couramment dans la supply chain, fut l’une des raisons principales qui nous a conduit, chez Lokad, à concevoir notre propre pile logicielle DP plutôt qu’à modifier un cadre existant, précisément afin d’avoir plus de latitude pour introduire des constructs spéciaux conçus pour s’adapter à ces situations.
Certains de ces constructs ne sont rien de plus qu’une bibliothèque “standard” de fonctions écrites dans le langage DP lui-même – afin de réduire les tâches répétitives et d’éviter certaines classes d’erreurs. D’autres, cependant, sont plus subtils et imbriqués avec le stochastic gradient descent pour offrir des capacités spécialisées qui n’auraient pas pu être mises en œuvre par une différentiation automatique “pure”.
Comment traitez-vous l’incertitude avec DP ? En effet, DP peut optimiser n’importe quelle fonction objectif complexe en ajustant des paramètres à l’aide d’un stochastic gradient descent optimisant un réseau de neurones qui n’est rien d’autre qu’une fonction spéciale. Comment les distributions de probabilité sont-elles prises en compte ?
L’approche dominante que nous adoptons pour traiter l’incertitude en DP consiste à générer des trajectoires – des time-series générées reflétant des flux d’événements futurs – à partir de distributions de probabilité sous-jacentes, puis à laisser la fonction objectif opérer selon un schéma de Monte Carlo. Cette approche offre la possibilité de modéliser des interactions discrètes complexes au sein d’un système – comme la conséquence de cascades de BOMs (nomenclatures) même si les distributions de probabilité – utilisées comme entrées – n’étaient disponibles que pour la demande future de produits finis.
Cette approche n’est pas nouvelle. Les autoencodeurs variationnels – bien qu’ingénierés d’un point de vue quelque peu différent – emploient une stratégie similaire, prenant en entrée la paramétrisation d’une distribution (une gaussienne pour les VAE) et produisant des déviations en sortie. Comme discuté ci-dessus lorsque nous avons mentionné les autoencodeurs variationnels, nous utilisons fréquemment des distributions de counting qui produisent des déviations entières, plutôt que des distributions continues comme les gaussiennes.
Cette approche générative – où les distributions se transforment en observations (c’est-à-dire des trajectoires) – peut également être entièrement internalisée dans le processus DP. Au lieu de prendre les distributions de probabilité comme entrées et d’en optimiser les décisions, les distributions elles-mêmes peuvent être apprises pendant que l’optimisation est effectuée simultanément. Par exemple, la prévision de la demande peut être réalisée conjointement avec l’optimisation des prix, car la stratégie de tarification a un impact fort sur la demande, et ces deux aspects ne peuvent vraiment pas être analysés isolément.
La partie générative de la recette mentionnée ci-dessus se retrouve déjà dans les réseaux antagonistes génératifs qui ont rencontré un succès retentissant pour générer des images photoréalistes. Lorsqu’on considère des séries temporelles, les LSTM et GRU (un équivalent plus simple et moderne du LSTM) offrent des moyens de générer des séries temporelles complexes qui n’auraient pas pu être explicitement modélisées à travers des distributions de probabilité.
DP offre plus de flexibilité pour tirer parti de ces capacités du point de vue de la supply chain tout en traitant des objets plus hétérogènes (graphes, séries temporelles, données relationnelles) par rapport aux scénarios habituellement envisagés du point de vue du deep learning. Encore une fois, la majeure partie des efforts d’ingénierie de Lokad s’est concentrée sur la perspective supply chain, afin de s’assurer que les outils étaient alignés avec les exigences spécifiques qui se posent lors de l’optimisation des stocks, des prix, des achats, des productions, des assortiments, etc – plutôt que de se concentrer sur les images, les voix et le traitement automatique du langage naturel.
