Ganze Zahlen und Unsicherheit im differenzierbaren Programmieren

Joannes Vermorel

Markus Leopoldseder (Director of Knowledge - Global Manufacturing and Supply Chain Practice at McKinsey) stellte zwei relevante Fragen hinsichtlich der Anwendbarkeit von Differenzierbares Programmieren (DP) für supply chain Zwecke. In diesem technisch recht versierten Beitrag möchten wir einige Einblicke dazu geben, wie die Einschränkungen von Ganzzahlen und wie Unsicherheit jeweils im DP behandelt werden. Dies ist nur ein erster Einblick in den Ansatz von Lokad. Wir planen, zu einem späteren Zeitpunkt ausführliche Rezepte auf docs.lokad.com zu veröffentlichen.

Wie wendet DP auf ganzzahlige Variablen an? Tatsächlich, wenn die Zielfunktion Ganzzahlen als Eingaben erhält, könnte sie nicht differenzierbar sein.

Aus der supply chain-Perspektive sind die meisten Entscheidungen diskret: man kann nicht 4,2 Einheiten eines Produkts bestellen, es sind entweder 4 oder 5. Daher suchen wir – sowohl aus Lern- als auch aus Optimierungsperspektive – nach Methoden, die gut mit Ganzzahlen funktionieren. Wie unser Leser treffend anmerkte, sind Parameter im DP Zahlen, und diese Parameter können nicht auf Ganzzahlen beschränkt werden, da diese Betrachtungsweise nicht mit dem stochastischen Gradientenabstieg, der dem DP zugrunde liegt, vereinbar ist.

Es gibt mehrere Möglichkeiten, diskrete Entscheidungen und die entsprechenden diskreten Zielfunktionen durch DP zu erhalten, die von naiv, aber unkompliziert, bis hin zu ausgesprochen komplex, jedoch in Bezug auf die numerische Optimierung beispiellos reichen.

Der einfachste Ansatz besteht darin, die Zielfunktion während des Trainings zu interpolieren und die Ergebnisse bei der Evaluierung zu runden. Zum Beispiel, wenn wir eine Bestellmenge – die als Ganzzahl erwartet wird – anstreben, kann die Zielfunktion mittels Interpolation auf beliebige Zahlen erweitert werden. Dies funktioniert gut, wenn man Systeme betrachtet, die, obwohl sie diskret sind, ein weitgehend lineares Verhalten aufweisen. Bei einer starken Nichtlinearität, wie einer MOQ (Mindestbestellmenge) Einschränkung, funktioniert dies jedoch nicht so gut.

Um mit solchen Situationen umzugehen, kann die Zielfunktion durch eine Ersatzfunktion ersetzt werden, eine Funktion, die die originale Zielfunktion annähert, jedoch in einer glatt differenzierbaren Weise. Zum Beispiel kann die typischerweise mit den Strafkosten einer MOQ-Beschränkung verbundene Stufenfunktion durch eine Sigmoidfunktion ersetzt werden. Über viele Epochen hinweg wird die Ersatzfunktion schrittweise so verformt, dass sie der ursprünglichen Zielfunktion numerisch näherkommt.

Aus supply chain-Perspektive funktionieren unserer Erfahrung nach Ersatzfunktionen überraschend gut. Tatsächlich sind Situationen, in denen es nicht möglich ist, stetig zu guten Lösungen zu iterieren, selten. Supply chain-Probleme sind keine kryptografischen Rätsel, bei denen schon das Ändern eines einzelnen Bits einer Lösung die ganze Lösung entgleisen lässt. Zum Beispiel, wenn eine Bestellung von 490 Einheiten profitabel ist, während eine MOQ bei 500 liegt, ist die Wahrscheinlichkeit hoch, dass auch eine Bestellung von 500 Einheiten profitabel ist.

Anschließend gibt es ausgefeiltere Ansätze, die von variationalen Autoencodern inspiriert sind: Die fraktionalen Ausgaben einer Schicht (wie in „Deep Learning“-Schichten) werden in einen zufälligen ganzzahligen Wert umgewandelt, der aus einer beliebigen Verteilung, beispielsweise einer Poisson-Verteilung, stammt. Durch diesen Mechanismus erzeugt das Programm, obwohl es ausschließlich mit fraktionalen Parametern operiert, ganzzahlige Ausgaben, die dann in die Zielfunktion eingespeist werden können. Der stochastische Gradientenabstieg wiederholt diesen Prozess eine große Anzahl von Malen, à la Monte-Carlo, und stellt sicher, dass die Gesetze der Erzeugung zufälliger ganzzahliger Werte richtig abgestimmt sind.

Schließlich basieren die komplexesten Ansätze, wie AlphaZero, auf der Einführung einer komplexen Liste von Schichten (zum Beispiel einem „tiefen“ Berechnungsnetzwerk), das typischerweise in einer Softmax-ähnlichen Schicht endet, um diskrete Entscheidungen zu generieren. Diese Ansätze liefern modernste Ergebnisse bei hochgradig nichtlinearen Optimierungsproblemen, wie der Sieg von AlphaGo (später umbenannt in AlphaZero) gegen Lee Sedol demonstriert. DP kann ebenfalls von diesen Methoden profitieren – indem lediglich die Tiefe und Komplexität des Netzwerks reduziert wird, um den Rechenaufwand im Rahmen zu halten. Glücklicherweise ist es in der Praxis, obwohl die Lösung eines MOQ-Problems relativ anspruchsvoll ist, bei Optimierungsproblemen nicht annähernd so schwierig, wie einen Weltmeister in Go zu besiegen, und „flache“ Netzwerke (nach den Maßstäben des Deep Learning) erzielen bereits viel.

Direktere und praxisnähere Wege im Umgang mit diskreten Situationen – wie sie häufig in supply chain-Szenarien vorkommen – anzubieten, war einer der Hauptgründe, warum wir bei Lokad unseren eigenen DP-Software-Stack entwickelt haben, anstatt uns an einen bestehenden Rahmen zu halten; nämlich um mehr Spielraum zu haben, spezielle Konstrukte einzuführen, die exakt auf diese Situationen abgestimmt sind.

Einige dieser Konstrukte sind nichts weiter als eine „Standard“-Bibliothek von Funktionen, die in der DP-Sprache selbst geschrieben wurden – als Mittel zur Minderung sich wiederholender Aufgaben und zur Vermeidung bestimmter Fehlerklassen. Einige dieser Konstrukte sind jedoch subtiler und mit dem stochastischen Gradientenabstieg verflochten, um spezialisierte Fähigkeiten zu bieten, die nicht durch „reine“ automatische Differenzierung implementiert werden konnten.

Wie geht man mit Unsicherheit im DP um? Tatsächlich kann DP jede komplexe Zielfunktion optimieren, indem Parameter mittels stochastischem Gradientenabstieg optimiert werden, wobei ein neuronales Netzwerk, das im Grunde auch eine Spezialfunktion ist, verwendet wird. Wie werden Wahrscheinlichkeitsverteilungen berücksichtigt?

Der vorherrschende Ansatz, den wir zur Bewältigung von Unsicherheit im DP anwenden, besteht darin, Trajektorien zu generieren – erzeugte time-series zur Darstellung von Strömen zukünftiger Ereignisse – aus zugrundeliegenden Wahrscheinlichkeitsverteilungen, und anschließend die Zielfunktion nach einem Monte-Carlo-Muster arbeiten zu lassen. Dieser Ansatz bietet die Möglichkeit, komplexe diskrete Interaktionen innerhalb eines Systems zu modellieren – wie beispielsweise die Konsequenz von kaskadierenden BOMs (Stücklisten), selbst wenn die als Eingaben verwendeten Wahrscheinlichkeitsverteilungen nur für die zukünftige Nachfrage nach fertigen Produkten vorlagen.

Dieser Ansatz ist nicht neu. Variationale Autoencoder – obwohl aus einer recht 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 Ausgaben erzeugen. Wie oben bereits erwähnt, verwenden wir häufig Zählverteilungen, die ganzzahlige Abweichungen erzeugen, anstelle kontinuierlicher Verteilungen wie der Gaußschen.

Dieser generative Ansatz – bei dem Verteilungen in Beobachtungen (d.h. Trajektorien) umgewandelt werden – kann auch vollständig in den DP-Prozess integriert werden. Anstatt Wahrscheinlichkeitsverteilungen als Eingaben zu nehmen und daraus Entscheidungen zu optimieren, können die Verteilungen selbst erlernt werden, während gleichzeitig die Optimierung durchgeführt wird. So kann beispielsweise die Nachfrageprognose gemeinsam mit der Preisoptimierung durchgeführt werden, da die Preisstrategie einen starken Einfluss auf die Nachfrage hat und beide Aspekte kaum isoliert voneinander analysiert werden können.

Der generative Teil des oben erwähnten Rezepts findet sich bereits in generativen adversarialen Netzwerken, die im Erzeugen fotorealistischer Bilder enorm erfolgreich waren. Betrachtet man Zeitreihen, bieten LSTM und GRU (ein einfacheres, moderneres Äquivalent des LSTM) Möglichkeiten, komplexe Zeitreihen zu generieren, die nicht explizit durch Wahrscheinlichkeitsverteilungen modelliert werden konnten.

DP bietet mehr Flexibilität, um diese Fähigkeiten aus supply chain-Perspektive zu nutzen, während es mit heterogeneren Objekten (Graphen, Zeitreihen, relationale Daten) umgeht, verglichen mit den Szenarien, die üblicherweise aus der Deep Learning Perspektive betrachtet werden. Nochmals, der Großteil der ingenieurtechnischen Anstrengungen von Lokad war auf die supply chain-Perspektive konzentriert, um sicherzustellen, dass die Werkzeuge an die spezifischen Anforderungen angepasst sind, die bei der Optimierung von Beständen, Preisen, Bestellungen, Produktionen, Sortimenten usw. entstehen – statt sich auf Bilder, Stimmen und die Verarbeitung natürlicher Sprache zu konzentrieren.