Integers und Unsicherheit im differenzierbaren Programmieren
Markus Leopoldseder (Director of Knowledge - Global Manufacturing and Supply Chain Practice bei McKinsey) hat zwei relevante Fragen zur Anwendbarkeit des differenzierbaren Programmierens (DP) für Supply Chain-Zwecke aufgeworfen. In diesem recht technischen Beitrag werden wir versuchen, einige Einblicke zu geben, wie die Einschränkungen von Ganzzahlen und die Unsicherheit jeweils im DP behandelt werden. Dies ist nur ein erster Einblick in den Ansatz von Lokad. Wir planen, zu einem späteren Zeitpunkt erweiterte Anleitungen auf docs.lokad.com zu veröffentlichen.
Wie lässt sich DP auf Ganzzahlvariablen anwenden? Tatsächlich kann die Zielfunktion, wenn sie Ganzzahlen als Eingabe verwendet, möglicherweise nicht differenzierbar sein.
Aus Sicht der Supply Chain sind die meisten Entscheidungen diskret: Wir können keine 4,2 Einheiten eines Produkts bestellen, es sind entweder 4 oder 5. Daher suchen wir - sowohl aus Lern- als auch aus Optimierungssicht - nach Methoden, die gut mit Ganzzahlen funktionieren. Wie unser Leser treffend bemerkt hat, sind die Parameter im DP Zahlen, und diese Parameter können nicht auf Ganzzahlen beschränkt werden, da diese Perspektive nicht mit dem stochastischen Gradientenabstieg vereinbar ist, der im Kern des DP liegt.
Es gibt verschiedene Möglichkeiten, diskrete Entscheidungen und ihre entsprechenden diskreten Zielfunktionen durch DP zu erhalten, von naiv, aber einfach, bis hin zu kompliziert, aber unübertroffen in Bezug auf die numerische Optimierung.
Der einfachste Ansatz besteht darin, die Zielfunktion zur Trainingszeit zu interpolieren und die Ergebnisse zur Auswertungszeit zu runden. Wenn wir beispielsweise eine Bestellmenge suchen - die voraussichtlich eine Ganzzahl sein soll - kann die Zielfunktion durch Interpolation auf beliebige Zahlen erweitert werden. Dies funktioniert gut, wenn Systeme betrachtet werden, die zwar diskret sind, aber relativ lineares Verhalten aufweisen. Wenn jedoch eine starke Nichtlinearität wie eine Mindestbestellmenge (MOQ) vorliegt, funktioniert dies nicht so gut.
Um mit solchen Situationen umzugehen, kann die Zielfunktion durch eine Ersatzfunktion ersetzt werden, eine Funktion, die die ursprüngliche Zielfunktion in einer glatten, differenzierbaren Weise approximiert. Beispielsweise kann die Schritt-Funktion, die typischerweise mit den Strafkosten einer MOQ-Beschränkung assoziiert ist, durch eine Sigmoid-Funktion ersetzt werden. Im Laufe der Epochen wird die Ersatzfunktion allmählich verformt, um numerisch näher an die ursprüngliche Zielfunktion heranzukommen.
Aus Sicht der Supply Chain funktionieren Ersatzfunktionen in unserer Erfahrung überraschend gut. Tatsächlich sind Situationen, in denen es nicht möglich ist, sich reibungslos zu guten Lösungen hin zu entwickeln, selten. Supply Chain-Probleme sind keine kryptografischen Rätsel, bei denen eine einzige Bitänderung von einer Lösung abweicht. Wenn beispielsweise eine Bestellung von 490 Einheiten rentabel ist, während es eine MOQ von 500 gibt, ist es sehr wahrscheinlich, dass die Bestellung von 500 Einheiten ebenfalls rentabel ist.
Dann gibt es noch anspruchsvollere Ansätze, die von variationalen Autoencodern inspiriert sind: Die fraktionalen Ausgaben einer Schicht (wie in “Deep Learning-Schichten”) werden in eine zufällige Ganzzahlabweichung umgewandelt, die aus einer beliebigen Verteilung stammt, zum Beispiel einer Poisson-Verteilung. Durch diesen Mechanismus erzeugt das Programm, während es nur mit fraktionalen Parametern arbeitet, Ganzzahlausgaben, die dann in die Zielfunktionen eingespeist werden können. Der stochastische Gradientenabstieg wiederholt den Prozess eine große Anzahl von Malen, ala Monte-Carlo, um sicherzustellen, dass die Gesetze, die die Erzeugung von zufälligen Ganzzahlabweichungen steuern, ordnungsgemäß abgestimmt sind.
Schließlich beruhen die komplexesten Ansätze, wie zum Beispiel AlphaZero, auf der Einführung einer komplexen Liste von Schichten (z. B. einem “tiefen” Berechnungsnetzwerk), das in der Regel mit einer Softmax-ähnlichen Schicht endet, um diskrete Entscheidungen zu generieren. Diese Ansätze bieten Spitzenleistung bei hochgradig nichtlinearen Optimierungsproblemen, wie durch den Sieg von AlphaGo (später als AlphaZero neu definiert) gegen Lee Sedol gezeigt wurde. DP kann auch von diesen Methoden profitieren - indem die Tiefe und Komplexität des Netzwerks reduziert werden, um den Rechenaufwand unter Kontrolle zu halten. Glücklicherweise erreichen bereits “flache” Netzwerke (nach den Standards des Deep Learning) in der Praxis viel.
Eine der Hauptgründe, warum wir bei Lokad unsere eigene DP-Software-Plattform entwickelt haben, anstatt ein vorhandenes Framework anzupassen, war die Bereitstellung direkterer und praktischerer Möglichkeiten zur Bewältigung diskreter Situationen, wie sie in der Supply Chain häufig vorkommen. Dies ermöglichte es uns, spezielle Konstrukte zu entwickeln, die auf diese Situationen zugeschnitten sind.
Einige dieser Konstrukte sind nichts weiter als eine “Standard” -Bibliothek von Funktionen, die mit der DP-Sprache selbst geschrieben wurden - als Möglichkeit, repetitive Aufgaben zu reduzieren und Fehler zu vermeiden. Einige dieser Konstrukte sind jedoch subtiler und werden mit dem stochastischen Gradientenabstieg verflochten, um spezialisierte Fähigkeiten anzubieten, die nicht durch “reine” automatische Differentiation implementiert werden konnten.
Wie gehen Sie mit Unsicherheit bei DP um? Tatsächlich kann DP jede komplexe Zielfunktion optimieren, indem Parameter mit Hilfe eines stochastischen Gradientenabstiegs optimiert werden, der ein neuronales Netzwerk optimiert, das nichts anderes als eine spezielle Funktion ist. Wie werden Wahrscheinlichkeitsverteilungen berücksichtigt?
Der vorherrschende Ansatz, den wir bei DP zur Bewältigung von Unsicherheit anwenden, besteht darin, Trajektorien zu generieren - erzeugte Zeitreihen, die zukünftige Ereignisströme widerspiegeln - aus zugrunde liegenden Wahrscheinlichkeitsverteilungen zu generieren und dann die Zielfunktion nach einem Monte-Carlo-Muster zu betreiben. Dieser Ansatz bietet die Möglichkeit, komplexe diskrete Interaktionen innerhalb eines Systems zu modellieren - wie zum Beispiel die Auswirkungen von kaskadierenden BOMs (Stücklisten), auch wenn die Wahrscheinlichkeitsverteilungen - die als Eingabe verwendet werden - nur für die zukünftige Nachfrage nach fertigen Produkten verfügbar waren.
Dieser Ansatz ist nicht neu. Variational Autoencoder - obwohl aus einer eher anderen Perspektive entwickelt - verwenden eine ähnliche Strategie, indem sie die Parametrisierung einer Verteilung (eine Gaußverteilung für VAE) als Eingabe nehmen und Abweichungen als Ausgabe erzeugen. Wie bereits erwähnt, verwenden wir häufig Zählverteilungen, die Ganzzahlabweichungen erzeugen, anstatt kontinuierliche Verteilungen wie Gaußverteilungen.
Dieser generative Ansatz - bei dem Verteilungen in Beobachtungen (d. h. Trajektorien) umgewandelt werden - kann auch vollständig in den DP-Prozess internalisiert werden. Anstatt Wahrscheinlichkeitsverteilungen als Eingabe zu nehmen und Entscheidungen daraus zu optimieren, können die Verteilungen selbst während der Optimierung gelernt werden. Zum Beispiel kann die Nachfrageprognose gemeinsam mit der Preisoptimierung durchgeführt werden, da die Preisstrategie einen starken Einfluss auf die Nachfrage hat und die beiden Aspekte nicht isoliert voneinander analysiert werden können.
Der generative Teil des oben genannten Ansatzes findet sich bereits in generativen adversarialen Netzwerken, die bei der Erzeugung fotorealistischer Bilder enorm erfolgreich waren. Bei der Betrachtung von Zeitreihen bieten LSTM und GRU (eine einfachere, modernere Entsprechung des LSTM) Möglichkeiten zur Generierung komplexer Zeitreihen, die nicht explizit durch Wahrscheinlichkeitsverteilungen modelliert werden konnten.
DP bietet mehr Flexibilität, um diese Fähigkeiten aus einer Supply-Chain-Perspektive zu nutzen, während gleichzeitig mit heterogeneren Objekten (Graphen, Zeitreihen, relationalen Daten) umgegangen wird im Vergleich zu den Szenarien, die normalerweise aus einer Deep Learning-Perspektive betrachtet werden. Auch hier konzentrierten sich die meisten Entwicklungsanstrengungen von Lokad auf die Supply-Chain-Perspektive, um sicherzustellen, dass das Werkzeug den spezifischen Anforderungen entspricht, die bei der Optimierung von Beständen, Preisen, Einkäufen, Produktionen, Sortimenten usw. auftreten - anstatt sich auf Bilder, Stimmen und die Verarbeitung natürlicher Sprache zu konzentrieren.
