Entiers et incertitude en programmation différentiable
Markus Leopoldseder (Directeur des connaissances - Pratique mondiale de la fabrication et de la gestion de la chaîne d’approvisionnement chez McKinsey) a soulevé deux questions pertinentes concernant l’applicabilité de la programmation différentiable (DP) à des fins de chaîne d’approvisionnement. Dans ce billet assez technique, nous essaierons de fournir des informations sur la manière dont les contraintes des entiers et l’incertitude sont respectivement traitées dans la DP. Il s’agit seulement d’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 la DP s’applique-t-elle aux variables entières ? En effet, si la fonction objectif prend des entiers en entrée, elle peut ne pas être différentiable.
Du point de vue de la chaîne d’approvisionnement, la plupart des décisions sont discrètes : nous ne pouvons pas commander 4,2 unités d’un produit, c’est soit 4, soit 5. Ainsi, nous recherchons - tant d’un point de vue d’apprentissage que d’optimisation - des méthodes qui fonctionnent bien avec les entiers. Comme notre lecteur l’a souligné avec acuité, les paramètres de la DP sont des nombres, et ces paramètres ne peuvent pas être contraints à des entiers, car cette perspective n’est pas compatible avec la descente de gradient stochastique qui est au cœur de la DP.
Il existe plusieurs façons d’obtenir des décisions discrètes et leurs fonctions objectif discrètes correspondantes grâce à la DP, allant de naïves mais simples à des méthodes compliquées mais inégalées en termes d’optimisation numérique.
L’approche la plus simple consiste à interpoler la fonction objectif lors de l’apprentissage, et à 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’il s’agit de systèmes qui, bien qu’étant discrets, présentent des comportements assez linéaires. Cependant, lorsque l’on est confronté à une forte non-linéarité telle qu’une contrainte de quantité minimale de commande (MOQ), cela ne fonctionne pas aussi bien.
Pour faire face à de telles situations, la fonction objectif peut être remplacée par une fonction de substitution, une fonction qui approxime la fonction objectif d’origine, mais de manière lisse et différentiable. Par exemple, la fonction étape généralement associée au coût de pénalité d’une contrainte MOQ peut être remplacée par une fonction sigmoïde. Au fil des époques, la fonction de substitution est progressivement déformée pour devenir numériquement plus proche de la fonction objectif d’origine.
Du point de vue de la chaîne d’approvisionnement, dans notre expérience, les fonctions de substitution fonctionnent étonnamment bien. En effet, les situations où il n’est pas possible d’itérer en douceur vers de bonnes solutions sont rares. Les problèmes de chaîne d’approvisionnement ne sont pas des énigmes cryptographiques où changer un seul bit d’une solution déraille complètement la solution. Par exemple, si passer une commande d’achat de 490 unités est rentable alors qu’il y a une MOQ à 500, il est fort probable que la commande d’achat 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 “couches d’apprentissage profond”) sont converties en un déviateur entier aléatoire obtenu à partir d’une distribution arbitraire, par exemple une distribution de Poisson. Grâce à ce mécanisme, le programme, tout en n’opérant qu’avec des paramètres fractionnaires, produit des sorties entières qui peuvent ensuite être injectées dans la fonction objectif. La descente de gradient stochastique répète le processus un grand nombre de fois, à la manière de Monte-Carlo, en veillant à ce que les “lois” régissant la génération de déviations entières aléatoires soient 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 computationnel “profond”) se terminant généralement par une couche de type Softmax afin de générer des décisions discrètes. Ces approches offrent des résultats de pointe sur des problèmes d’optimisation hautement non linéaires, comme en témoigne la victoire d’AlphaGo (plus tard redéfini en AlphaZero) contre Lee Sedol. DP peut également tirer parti de ces méthodes - en réduisant simplement la profondeur et la complexité du réseau pour maîtriser les coûts de calcul. Heureusement, en pratique, résoudre un problème MOQ est relativement difficile, mais cela n’a rien à voir avec la difficulté de battre un champion du monde de Go en ce qui concerne les problèmes d’optimisation, et les réseaux “peu profonds” (selon les normes de l’apprentissage profond) obtiennent déjà de très bons résultats.
Offrir des moyens plus directs et pratiques de traiter les situations discrètes, comme on en trouve couramment dans les situations de chaîne d’approvisionnement, était l’une des principales raisons qui nous ont poussés chez Lokad à concevoir notre propre pile logicielle DP plutôt que de plier un framework existant ; précisément afin d’avoir plus de latitude pour introduire des constructions spéciales conçues pour s’adapter à ces situations.
Certaines de ces constructions ne sont rien de plus qu’une bibliothèque “standard” de fonctions écrites à travers le langage DP lui-même - comme moyen d’atténuer les tâches répétitives et d’éviter certaines erreurs. Certaines de ces constructions, cependant, sont plus subtiles et entrelacées avec la descente de gradient stochastique afin d’offrir des capacités spécialisées qui n’auraient pas pu être mises en œuvre par une simple différentiation automatique.
Comment gérez-vous l’incertitude avec DP ? En effet, DP peut optimiser n’importe quelle fonction objectif complexe en ajustant les paramètres à l’aide d’une descente de gradient stochastique optimisant un réseau neuronal qui n’est rien d’autre qu’une fonction spéciale également. Comment les distributions de probabilité sont-elles prises en compte ?
L’approche dominante que nous adoptons pour traiter l’incertitude dans DP consiste à générer des “trajectoires” - des séries temporelles 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 - telles que les conséquences des nomenclatures en cascade (bills of materials) même si les distributions de probabilité - utilisées en tant qu’entrées - n’étaient disponibles que pour la demande future de produits finis.
Cette approche n’est pas nouvelle. Les auto-encodeurs variationnels - bien que conçus selon une perspective assez différente - utilisent une stratégie similaire, prenant la paramétrisation d’une distribution (une gaussienne pour les VAE) en tant qu’entrée et produisant des déviations en tant que sorties. Comme mentionné précédemment lorsque nous avons déjà mentionné les auto-encodeurs variationnels, nous utilisons fréquemment des distributions de comptage qui produisent des déviations entières, plutôt que des distributions continues comme les gaussiennes.
Cette approche générative - où les distributions sont transformées en observations (c’est-à-dire en trajectoires) - peut également être entièrement intégrée dans le processus DP. Au lieu de prendre des distributions de probabilité en tant qu’entrées et d’optimiser les décisions à partir de celles-ci, les distributions elles-mêmes peuvent être apprises pendant que l’optimisation est effectuée en même temps. 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 important sur la demande, les deux aspects ne pouvant pas vraiment être analysés de manière isolée l’un de l’autre.
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 connu un énorme succès dans la génération d’images photoréalistes. Lorsqu’il s’agit de séries temporelles, les LSTM et les GRU (une version plus simple et plus moderne des LSTM) offrent des moyens de générer des séries temporelles complexes qui ne pourraient pas avoir été explicitement modélisées à l’aide de distributions de probabilité.
DP offre une plus grande flexibilité pour exploiter ces capacités d’un 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 généralement considérés d’un point de vue de l’apprentissage profond. Encore une fois, la majeure partie des efforts d’ingénierie de Lokad a été concentrée sur la perspective de la supply chain, afin de s’assurer que les outils étaient alignés sur les exigences spécifiques qui se posent lors de l’optimisation des stocks, des prix, des achats, des productions, des assortiments, etc. - au lieu de se concentrer sur les images, les voix et le traitement du langage naturel.
