Der Löser als Treppe verständlich erklärt

Der Löser, das Rechenprogramm, das aus vorhergesagten Fahrzeiten die schnellste Route wählt, verhält sich wie eine Treppe: Ändert man die Vorhersage ein wenig, bleibt die Route gleich, bis eine Kante erreicht ist, und dann springt sie. Ein Modell, das an der Qualität der gewählten Route lernen soll, braucht aber eine Rampe. Diese Seite zeigt, wie man sie baut und wann sie zu steil oder zu flach wird.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Das Bild: eine Treppe im Nebel

Stellen Sie sich vor, Sie stehen im dichten Nebel auf einer breiten Treppe und wollen nach unten. Sie sehen nichts und spüren nur den Boden unter den Füßen. Auf der Stufe ist er eben. Solange Sie auf der Stufe bleiben, sagt Ihnen nichts, in welcher Richtung es abwärts geht. Erst an der Kante spüren Sie einen Sprung, aber auch der verrät nicht, wie es danach weitergeht.

Auf einer Rampe wäre das anders. Der Boden ist geneigt, und schon bei einem kleinen Schritt spüren Sie, wo es abwärts geht. Genau diese Neigung braucht ein Verfahren, das schrittweise lernt: Es ändert sich ein wenig, prüft, ob es besser wurde, und geht in die Richtung weiter, die sich bewährt hat. Der Fachbegriff für die Neigung ist der Gradient.

Wo die Treppe in der Planung steht

Ein Modell sagt für ein Wegenetz die Fahrzeiten voraus, ähnlich wie ein Navi. Danach wählt ein Rechenprogramm, der Löser, aus diesen Zeiten die schnellste Route. Gemessen wird das Modell daran, wie viel länger die gewählte Route in Wahrheit dauert als die beste. Diese Mehrkosten heißen Regret.

Wer das Modell auf genau diesen Regret trainieren will, also seine Einstellzahlen schrittweise so ändern, dass der Regret sinkt, steht auf der Treppe. Ändert man die vorhergesagten Zeiten ein wenig, bleibt die gewählte Route dieselbe, und mit ihr bleibt der Regret gleich. Er springt erst, wenn eine andere Route vorn liegt.

Wie breit die Stufen sind, zeigt ein Programm zum Ausprobieren (die Demo) an einem erfundenen Gitter-Wegenetz mit 70 möglichen Wegen. Die Kosten hängen dort nicht geradlinig, sondern krumm von den Merkmalen eines Falls ab. Ändert man jede vorhergesagte Zeit zufällig um höchstens 1 %, bleibt die gewählte Route in mehr als neun von zehn Testfällen dieselbe. Bei höchstens 20 % sind es noch rund sechs von zehn. Gemeint ist jeweils der mittlere Wert aus 20 Läufen mit je 1000 Testfällen.

Warum das Lernen stockt

In der Demo hat das Modell 240 Einstellzahlen. Dreht man eine ein wenig, ändern sich die vorhergesagten Zeiten ein wenig, die Route bleibt, und der Regret bleibt. Das Verfahren spürt keine Neigung und weiß nicht, in welche Richtung es drehen soll: Der Gradient des Regrets ist fast überall null. Nur an den Kanten, wo zwei Routen gleich schnell erscheinen, springt der Wert, und ein Sprung nennt keine Richtung.

Die Rampe: alle Routen zählen mit

Die Abhilfe zählt nicht nur die eine schnellste Route: Jede Route bekommt ein Gewicht, und je schneller sie vorhergesagt wird, desto mehr Gewicht, aber auch langsamere zählen ein wenig mit. Der Regret wird dann als Durchschnitt über alle Routen mit diesen Gewichten gerechnet. Er reagiert auf eine kleine Änderung der Vorhersage, solange mehr als eine Route nennenswert Gewicht hat. Aus der Treppe ist eine Rampe geworden, und das Lernen spürt wieder eine Richtung. Gemessen wird danach weiter mit dem harten Löser: Die Rampe dient nur dem Training.

Wie stark die schnellste Route bevorzugt wird, stellt ein Regler ein, die Temperatur. Ist sie niedrig, also viel kleiner als die Kostenunterschiede zwischen den Routen, zählt praktisch nur die schnellste Route: Die Rampe ist wieder eine Treppe, und das Lernen stockt. Ist sie hoch, also viel größer, zählen alle Routen fast gleich: Die Rampe ist so flach, dass gute und schlechte Wege verwischen.

Was die Demo gemessen hat

Ausprobiert wurden sieben Temperaturen, jede eine Zehnerpotenz größer als die vorige. Ausgangspunkt ist ein Modell, das nur darauf trainiert ist, die Fahrzeiten möglichst genau vorherzusagen. Verglichen wurde der Regret nach dem Lernen mit dem dieses Modells, kleiner ist besser. Bei krummen Kosten und 1000 Trainingsfällen brachte die kleinste Temperatur nichts: Der Regret war im mittleren Lauf so hoch wie beim Ausgangsmodell, bei verrauschten Kosten höher. Bei den vier mittleren war er kleiner, bei den zwei größten größer.

Die passende Temperatur gehört zum Maßstab der Kosten. Multipliziert man alle Kosten mit 10, wandert die gute Zone um eine Zehnerpotenz mit.

Häufige Missverständnisse

• „Dann ist der Löser kaputt.“ Nein. Er tut, was er soll: die beste Route wählen. Nur als Lernsignal taugt sein Regret nicht.
• „Mehr Glättung hilft mehr.“ Nein. Die zwei größten Temperaturen der Demo lagen über dem Ausgangsmodell.
• „Mit der richtigen Temperatur gewinnt man immer.“ Nein. Bei Kosten, die geradlinig von den Merkmalen abhängen, gab es nichts zu gewinnen, und bei krummen Kosten, 100 Trainingsfällen und Rauschen lag keine Temperatur im mittleren Lauf unter dem Ausgangsmodell.

Woran Sie das Muster erkennen

Im laufenden Betrieb sehen Sie die Treppe nicht direkt, denn dort wählt der Löser nur Routen. Sichtbar wird sie in zwei Fällen:

• Man ändert die Vorhersagen testweise leicht zufällig und zählt, in wie vielen Fällen dieselbe Route bleibt. Dieser Anteil ist die Breite der Treppe; je näher er an 100 % liegt, desto weniger Richtung steckt im Lernsignal.
• Man trainiert ein Modell auf den Regret, und die Trainingskurve bleibt flach, obwohl sich die Einstellzahlen ändern. Nach dem Glätten deutet eine zu niedrige Temperatur auf Stillstand, eine zu hohe auf Verwischen; beides hängt von der Kostenskala ab.

Wie ernst ist das Modell zu nehmen?

Das Wegenetz ist ein erfundenes Gitter mit erzeugten Kosten und einem linearen Modell; für echte Netze ist nichts gemessen, und wie man dort die passende Temperatur findet, zeigt die Demo nicht. Die Zahlen gelten für diese Welt und diese Kostenskala.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er behandelt eine erzeugte Welt, in der ein Modell aus Merkmalen die Kosten der Bögen eines Gitters vorhersagt und ein exakter Löser daraus den billigsten Weg wählt. Gefragt ist, warum sich das Modell nicht direkt auf den Regret dieses Weges trainieren lässt und was eine Glättung des Lösers mit einer Gibbs-Verteilung über alle Wege daran ändert. Alle Aussagen sind Messungen in dieser Welt, keine Aussagen über echte Netze.

• Welt: Gitter \(5 \times 5\), Wege von links oben nach rechts unten, 40 Bögen, 70 Wege mit je 8 Bögen. Merkmale \(x \sim \mathcal N(0, I_5)\), eine Gewichtsmatrix \(B \in \{0,1\}^{40 \times 5}\) aus fairen Münzwürfen, mittlere Kosten \(m_j(x) = ((Bx)_j/\sqrt{5} + 3)^{\deg} / 3{,}5^{\deg} + 1\) und beobachtete Kosten \(c_j = m_j(x)\,\varepsilon_j\) mit \(\varepsilon_j \sim U[1 - e, 1 + e]\). Der Grad \(\deg\) (1, 2, 4 oder 6) steuert die Abweichung von der Linearität: Grad 1 ist linear in \(x\), die anderen weichen zunehmend davon ab. Die Rauschstufe \(e\) ist 0 oder 0,5. Das Orakel kennt \(m(x)\). Das Gitter und die Kostenformel stammen aus einer früheren Demo zum kürzesten Weg und sind dort aus dem Gedächtnis nach dem Schema der SPO-Literatur nachgebaut, nicht gegen sie geprüft.
• Harter Löser: Rückwärtsrechnung über die 25 Knoten des azyklischen Gitters; bei Gleichstand gewinnt am Knoten „rechts“ vor „unten“.
• Training: lineares Modell \(\hat c = \theta^\top (1, x)\) mit Achsenabschnitt, 240 Parameter, Start bei der Lösung der Kleinsten Quadrate (KQ), Adam mit Lernrate 0,05, Vollbatch, 300 Schritte, \(n\) = 100, 300 oder 1000 Trainingsfälle. Beim geglätteten Training gilt der Parameter nach dem letzten Schritt. Die Vergleichsspalte SPO+ (konvexer Ersatzverlust für den Regret, der in jedem Schritt den Löser auf allen Trainingsfällen aufruft) nimmt den Parameter mit dem kleinsten Trainingsverlust unter den besuchten.
• Messung: immer mit dem harten Löser auf 1000 Testfällen. Normierter Regret ist die Summe der Regrets geteilt durch die Summe der besten Wegkosten, in Prozent. Angegeben sind Median [Minimum; Maximum] über 20 Zufalls-Seeds (0 bis 19, Startwerte der Zufallsquelle SplitMix64). Gerechnet wird über die Aufzählung der 70 Wege mit log-sum-exp, stabil bei kleinem \(T\).
• Zweiter Rechenweg: Auf dem azyklischen Gitter lassen sich dieselben Gewichte auch ohne Wegliste durch eine Vorwärts-Rückwärts-Rechnung (Summe-Produkt) bestimmen. Die Demo nutzt sie nur in Tests.

Die Formeln

Regret des harten Lösers. Sei \(w(\hat c)\) der Weg mit den kleinsten vorhergesagten Kosten und \(z^*(c) = \min_{w \in W} c^\top w\) die besten wahren Kosten:

\[\ell(\hat c, c) = c^\top w(\hat c) - z^*(c)\]

Er ändert sich nur, wenn sich der gewählte Weg ändert: In \(\hat c\) ist er stückweise konstant, sein Gradient ist, wo er existiert, null.

Gibbs-Glättung. Jeder Weg bekommt ein Gewicht, das mit seinen vorhergesagten Kosten fällt; der geglättete Regret ist der erwartete Regret unter diesen Gewichten:

\[\pi_T(w \mid \hat c) = \frac{\exp(-\hat c^\top w / T)}{\sum_{w' \in W} \exp(-\hat c^\top w' / T)}, \qquad \ell_T(\hat c, c) = \sum_{w \in W} \pi_T(w \mid \hat c)\, c^\top w - z^*(c)\]

Für \(T \to 0\) geht \(\pi_T\) auf den billigsten Weg, für \(T \to \infty\) auf die Gleichverteilung über die Wege. \(T\) hat die Einheit der Kosten.

Gradient. Mit \(\mathbb E\) und \(\operatorname{Cov}\) unter \(\pi_T\) ist der Gradient von \(\ell_T\) nach der Vorhersage die Kovarianz von Wegkosten und Weg, geteilt durch \(-T\):

\[\frac{\partial \ell_T}{\partial \hat c} = -\frac{1}{T}\,\operatorname{Cov}\big(c^\top w,\; w\big) = -\frac{1}{T}\Big( \mathbb E[(c^\top w)\, w] - \mathbb E[c^\top w]\, \mathbb E[w] \Big)\]

Für das lineare Modell \(\hat c = \theta^\top (1, x)\) folgt der Gradient nach \(\theta\) aus der Kettenregel, gemittelt über die Fälle.

Herleitungen Schritt für Schritt

Die folgenden Herleitungen und das Rechenbeispiel sind Rechnungen dieser Seite, keine Messungen.

Warum der Regret eine Treppe ist.

• Schritt 1: Der harte Löser vergleicht nur die vorhergesagten Wegkosten \(\hat c^\top w\). Solange derselbe Weg der billigste bleibt, bleibt \(w(\hat c)\) gleich.
• Schritt 2: Dann ist \(\ell(\hat c, c) = c^\top w(\hat c) - z^*(c)\) konstant, denn \(c\) und \(z^*(c)\) hängen nicht von \(\hat c\) ab. Der Gradient nach \(\hat c\) ist dort null.
• Schritt 3: Springen kann \(\ell\) nur dort, wo zwei Wege dieselben vorhergesagten Kosten haben und der gewählte Weg wechselt (ein Gleichstand), und auch dort nur, wenn die beiden Wege verschiedene wahre Kosten haben. Gleicher Weg heißt gleicher Regret; die Umkehrung gilt nur bei Wegen mit gleichen wahren Kosten.

Warum der Gradient der Glättung die Kovarianz ist.

• Schritt 1: Aus \(\pi_T(w) \propto \exp(-\hat c^\top w / T)\) folgt \(\partial \pi_T(w) / \partial \hat c = -\tfrac{1}{T}\, \pi_T(w)\,(w - \mathbb E[w])\): Der Exponent liefert \(-w/T\), der Nenner \(+\mathbb E[w]/T\).
• Schritt 2: \(z^*(c)\) hängt nicht von \(\hat c\) ab. Summiert man \(c^\top w\) mit diesen Ableitungen über alle Wege, entsteht \(-\tfrac{1}{T} \sum_w \pi_T(w)\,(c^\top w)\,(w - \mathbb E[w])\), und das ist die Kovarianz von \(c^\top w\) und \(w\), geteilt durch \(-T\).
• Schritt 3: Liegt fast das ganze Gewicht auf einem Weg, ist die Kovarianz fast null: Für \(T \to 0\) kehrt die Treppe zurück. Für \(T \to \infty\) bleibt \(\pi_T\) fast gleichverteilt, und der Faktor \(1/T\) macht den Gradienten klein: Die Rampe wird flach.

Durchgerechnet: zwei Wege mit je einem Bogen. Rechnung dieser Seite. Die wahren Kosten sind \(c = (3, 5)\), die Vorhersage ist \(\hat c = (4, 3)\), also \(\Delta = \hat c_1 - \hat c_2 = 1\). Der harte Löser wählt Weg 2; der Regret ist \(5 - 3 = 2\) und bleibt 2, solange \(\Delta > 0\). Das Gewicht von Weg 2 ist \(\sigma(\Delta / T)\) mit \(\sigma(u) = 1/(1 + e^{-u})\), der geglättete Regret also \(2\,\sigma(\Delta/T)\) und seine Steigung nach \(\hat c_1\) gleich \(\tfrac{2}{T}\,\sigma'(\Delta/T) > 0\).

Temperatur \(T\)	Gewicht von Weg 2	Erwartete Kosten
0,1	ungefähr 1,0000	4,9999
1	0,7311 (Weg 1: 0,2689)	4,4621
10	0,5250	4,0500

Bei kleinem \(T\) liegt fast das ganze Gewicht auf dem gewählten Weg, die erwarteten Kosten nähern sich den Kosten dieses Weges, 5, und die Steigung verschwindet fern von \(\Delta = 0\). Bei großem \(T\) nähern sich beide Gewichte der Hälfte und die erwarteten Kosten dem Mittel von 3 und 5, also 4.

Warum die Temperatur zum Kostenmaßstab gehört. Multipliziert man \(c\), \(\hat c\) und \(T\) mit demselben Faktor, bleibt \(\hat c^\top w / T\) und damit \(\pi_T\) unverändert; der Regret skaliert mit dem Faktor, der normierte Regret in Prozent nicht. Das ist keine neue Erkenntnis, sondern die Eigenschaft, dass \(\hat c\) und \(T\) gemeinsam skalieren.

Befunde

Alle Zahlen stammen aus einer eigenen Messung dieser Demo: 20 Zufalls-Seeds (0 bis 19), 300 Adam-Schritte, Lernrate 0,05, 1000 Testfälle. Regret in Prozent der besten Wegkosten, Median [Minimum; Maximum] über die 20 Zufalls-Seeds. Die Zahlen sind trainiert und plattformabhängig; die Messung gilt nur für die genannten Welten.

Wie oft ändert eine kleine Störung den Weg? Anteil der Testfälle mit gleichem gewählten Weg (in Prozent), wenn jeder Eintrag der KQ-Vorhersage um einen zufälligen Bruchteil bis zur genannten Größe verändert wird. Die Störung ist je Eintrag eine eigene Zufallszahl, gleichverteilt in \([-1, 1]\) mal der Größe, in derselben Richtung für alle Größen.

Welt	±0,1 %	±1 %	±5 %	±20 %
Grad 6, n = 1000, Rauschstufe 0,0	99,7 [99,5; 100,0]	97,6 [95,1; 98,4]	88,1 [78,6; 90,7]	60,9 [49,3; 66,2]
Grad 6, n = 1000, Rauschstufe 0,5	99,8 [99,4; 100,0]	97,6 [95,5; 98,6]	88,4 [80,6; 90,5]	60,1 [50,8; 65,4]
Grad 1, n = 1000, Rauschstufe 0,0	98,4 [77,4; 99,4]	86,5 [68,9; 89,7]	50,3 [40,7; 59,5]	11,2 [9,5; 16,0]
Grad 6, n = 100, Rauschstufe 0,5	99,7 [99,5; 100,0]	97,8 [95,8; 98,7]	89,3 [84,1; 92,6]	63,1 [51,1; 71,7]

Der Anteil mit gleichem Regret ist in jedem Seed und bei jeder Größe mindestens so groß wie der mit gleichem Weg. Bei Grad 1 ist der Anteil kleiner und streut stark über die Seeds; eine Erklärung dafür ist nicht gemessen.

Regret nach 300 Schritten. Grad 6, n = 1000, in Prozent; „besser als KQ“ zählt die Seeds, in denen das Verfahren unter KQ liegt. Das Orakel erreicht ohne Rauschen 0,0 [0,0; 0,0] und mit Rauschen 10,5 [9,3; 12,3]; der Rest ist unvermeidbares Rauschen.

Verfahren	Rauschstufe 0,0	besser als KQ	Rauschstufe 0,5	besser als KQ
KQ	2,0 [1,4; 3,0]	–	13,1 [11,3; 14,5]	–
SPO+ (300 Schritte)	0,5 [0,4; 0,8]	20 von 20	12,3 [10,7; 13,4]	20 von 20
geglättet, \(T = 0{,}001\)	2,0 [0,9; 3,0]	9 von 20	15,3 [13,1; 17,1]	0 von 20
geglättet, \(T = 0{,}03\)	0,5 [0,4; 0,8]	20 von 20	12,5 [10,6; 14,4]	19 von 20
geglättet, \(T = 0{,}1\)	0,5 [0,3; 0,8]	20 von 20	12,1 [10,7; 13,7]	19 von 20
geglättet, \(T = 0{,}3\)	0,5 [0,3; 0,7]	20 von 20	11,9 [10,5; 13,0]	20 von 20
geglättet, \(T = 1\)	0,5 [0,3; 0,7]	20 von 20	11,7 [10,6; 13,5]	20 von 20
geglättet, \(T = 3\)	0,6 [0,4; 0,9]	20 von 20	11,6 [10,5; 13,3]	20 von 20

Temperatur und Kostenmaßstab. Grad 6, n = 1000, Regret in Prozent nach 300 Schritten. Bei „Kosten mal 10“ sind alle Kosten (Training und Test) mit 10 multipliziert, die Lernrate ist mit 10 multipliziert, und \(T\) bleibt in Kosteneinheiten. KQ liegt bei 2,0 [1,4; 3,0] (Rauschstufe 0,0) und 13,1 [11,3; 14,5] (Rauschstufe 0,5).

Temperatur \(T\)	Rauschstufe 0,0, Kosten mal 1	Rauschstufe 0,0, Kosten mal 10	Rauschstufe 0,5, Kosten mal 1	Rauschstufe 0,5, Kosten mal 10
0,001	2,0 [0,9; 3,0]	5,7 [3,9; 11,4]	15,3 [13,1; 17,1]	21,0 [17,3; 25,1]
0,01	0,7 [0,4; 1,0]	1,9 [0,9; 3,7]	12,2 [11,1; 13,8]	15,2 [13,1; 20,6]
0,1	0,5 [0,3; 0,8]	0,7 [0,4; 1,2]	12,1 [10,7; 13,7]	12,1 [10,6; 13,4]
1	0,5 [0,3; 0,7]	0,5 [0,3; 0,8]	11,7 [10,6; 13,5]	12,1 [10,7; 13,7]
10	1,0 [0,8; 1,5]	0,5 [0,3; 0,7]	11,8 [10,4; 13,5]	11,7 [10,6; 13,5]
100	4,8 [3,0; 8,2]	1,0 [0,8; 1,5]	16,5 [13,2; 20,0]	11,8 [10,4; 13,5]
1000	6,5 [4,3; 10,0]	4,8 [3,0; 8,2]	17,9 [16,0; 21,6]	16,5 [13,2; 20,0]

Frage	Befund
Bringt die kleinste Temperatur etwas?	Nein, im Median nicht. \(T = 0{,}001\) liegt ohne Rauschen bei 2,0 % wie KQ (in 9 von 20 Seeds besser); mit Rauschen ist es in allen 20 Seeds schlechter als KQ (15,3 gegen 13,1 %), bei n = 100 ebenfalls (21,4 gegen 14,0 %).
Gibt es eine Rangfolge unter den mittleren Temperaturen?	Nein. Für \(T = 0{,}03\) bis 3 liegen die Mediane bei Grad 6, n = 1000 zwischen 0,5 und 0,6 % (ohne Rauschen) und zwischen 11,6 und 12,5 % (mit Rauschen); die Bänder von je zwei dieser fünf Temperaturen überlappen sich in beiden Zellen.
Schlägt die Glättung SPO+?	Nicht eindeutig. Ohne Rauschen ist der Median für \(T = 0{,}3\) und \(T = 1\) gleich dem von SPO+ (0,5 %). Mit Rauschen liegen die Mediane für \(T = 0{,}3\), 1 und 3 (11,9, 11,7 und 11,6 %) unter dem von SPO+ (12,3 %), die Bänder überlappen. SPO+ ruft in jedem Schritt den Löser auf allen Trainingsfällen auf; die Glättung braucht keinen Löser in der Schleife, dafür die Aufzählung aller 70 Wege.
Was bringt die Glättung bei linearer Wahrheit?	Nichts. Bei Grad 1 ohne Rauschen ist keine Variante in einem Seed besser als KQ (0 von 20).
Und bei wenig Daten mit Rauschen?	Bei Grad 6, n = 100, Rauschstufe 0,5 liegt kein \(T\) im Median unter KQ (14,0 %; bestes \(T = 1\) mit 14,7 %, in 5 von 20 Seeds besser). SPO+ ist in 10 von 20 Seeds besser; in einer Stabilitätsprobe mit 100 weiteren Seeds nur in 29 von 100.
Verschiebt der Kostenmaßstab die gute Zone?	Ja. Bei Kosten mal 1 liegt der Median-Regret unter KQ für \(T\) von 0,01 bis 10 (beide Rauschstufen), bei Kosten mal 10 für \(T\) von 0,1 bis 100 (Rauschstufe 0,5); ohne Rauschen liegt auch \(T = 0{,}01\) bei Kosten mal 10 mit 1,9 gegen 2,0 % im Median praktisch gleichauf. \(T = 100\) und \(T = 1000\) bei Kosten mal 1 liegen über KQ.
Ist die Verschiebung genau der Faktor?	Wo \(T\) nicht sehr klein ist, ja: Für \(T = 1, 10, 100\) und 1000 bei Kosten mal 10 stimmen die Regret-Werte jedes einzelnen Seeds mit denen bei Kosten mal 1 und \(T\) geteilt durch 10 überein (Unterschied höchstens \(10^{-4}\) Prozentpunkte). Bei sehr kleinem \(T\) weichen die Läufe je Seed voneinander ab (\(T = 0{,}1\) bei mal 10 gegen \(T = 0{,}01\) bei mal 1: Mediane 0,7 gegen 0,7 % ohne und 12,1 gegen 12,2 % mit Rauschen); die Ursache, vermutlich Rundung, von Adam verstärkt, ist nicht untersucht.
Wie viele Trainingsfälle liefern am Start einen Gradienten?	In der Grundeinstellung (Grad 6, n = 1000, ohne Rauschen, Zufalls-Seed 0) haben am KQ-Start bei \(T = 0{,}001\) etwa 1 % der Trainingsfälle (1,3 % im gemessenen Lauf) mehr als einen Weg mit über 1 % Gewicht, bei \(T = 0{,}1\) etwa 70 % (69,9 %), bei \(T = 1\) und \(T = 3\) alle (100 %).

Grenzen und was die Messung zeigt

Was sie belegt:

• Die Treppe ist in dieser Welt bei stark gekrümmten Kosten breit und bei linearer Wahrheit schmaler. Bei Rauschstufe 0,5 liegen die Anteile gleicher Wege in der Messung innerhalb von 1 Prozentpunkt der Werte ohne Rauschen.
• Die kleinste getestete Temperatur bringt im Median kein Lernen; die mittleren unterbieten KQ in mindestens 19 von 20 Seeds, die größten verlieren wieder. Die gute Zone gehört zur Kostenskala und wandert mit ihr, wo \(T\) nicht sehr klein ist.
• Das Rechenbeispiel mit zwei Wegen stimmt auf die angegebenen Stellen.

Was sie nicht belegt, und die Grenzen:

• Eine Welt: nur das Gitter \(5 \times 5\), nur diese Kostenformel, nur ein lineares Modell, Adam mit fester Lernrate und 300 Schritten, nur Gibbs-Glättung (keine quadratische Regularisierung des LP). Aussagen über andere Netze, Modelle, Löser oder Lernraten sind nicht gemessen.
• Der Bereich der Temperaturen: Die Messung liegt auf einem Raster mit je einer Zehnerpotenz Abstand und gilt für Kosten mit 5. bis 95. Perzentil 1,0 bis 3,9. Dass \(T\) im Bereich von 0,01 bis 10 (drei Zehnerpotenzen, vier Rasterwerte) unter KQ liegt, \(T = 0{,}001\) und \(T\) ab 100 nicht, ist auf dieses Raster und diese Kostenskala bezogen. Mit fester statt mitskalierter Lernrate würden sich die Kurven zusätzlich verändern; das ist nicht gemessen.
• Streuung: Es gibt keinen Signifikanztest; die Spanne zwischen Minimum und Maximum ist keine Konfidenzaussage. Eine Rangfolge unter \(T = 0{,}03\) bis 3 folgt aus der Messung nicht.
• Plattform: Die Zahlen sind unter Windows gemessen; unter Linux können einzelne Werte um Zehntelpunkte abweichen.
• Deutung zu \(T = 0{,}001\): Dass dort nur der Gradient weniger Fälle nahe an einem Gleichstand eingeht und Adam diese kleinen Gradienten auf volle Schrittlänge normiert, passt zum Befund, ist aber nicht gemessen; gemessen ist nur, wie viele Fälle am Start überhaupt einen Gradienten liefern.
• Aufzählung der Wege: Die Wegzahl wächst mit der Gittergröße \(h\) wie \(\binom{2(h-1)}{h-1}\): 70 bei \(h = 5\), 252 bei \(h = 6\), 924 bei \(h = 7\). Auf dem azyklischen Gitter liefert die Summe-Produkt-Rechnung Wert und Randverteilungen ohne Wegliste; für den Gradienten ohne Aufzählung gibt es auf dem Gitter Wege, etwa die Ableitung dieser Rechnung, die die Demo nicht baut. Für allgemeine Polytope (Wege mit Nebenbedingungen) fehlt die Struktur; das ist die eigentliche Grenze.
• Frühere Vormessung: Sie reproduziert sich nicht auf die Stelle (andere Zufallsquelle, 300 statt 600 Adam-Schritte). Es gilt die neue Messung; die Rangfolge „kleinste Temperatur wie KQ oder schlechter, \(T = 0{,}03\) bis 3 darunter“ blieb. Die frühere Annahme, die Temperatur müsse nur von null verschieden sein, gilt nicht: zu große Temperaturen verlieren.
• Nachprüfung: Die Prüfung von Löser, Gewichten, Randverteilungen und Gradient über 300 Zufallsinstanzen stammt aus einem Lauf außerhalb des Repositories; belastbar ist nur die Größenordnung der Abweichungen. Im Repository läuft eine kleine Fassung davon.
• Ableitung am Ergebnis: Die implizite Differentiation am Optimum (Kegelprogramme) setzt nach der README der zugehörigen Demo eine eindeutige, reguläre Lösung voraus; an Gleichständen hat die Lösung einen Knick, bei nicht eindeutigen Lösungen ist das System singulär. Dass die Lösung eines Kürzeste-Wege-LP in den Kosten stückweise konstant ist, ist hier eine eigene Überlegung, in der Messung zur Treppe belegt, nicht aus jener Demo übernommen.

Quellen

• Elmachtoub, A. N.; Grigas, P.: Arbeit zum SPO+-Verlust, Management Science 68(1), 2022. Nur die Zusammenfassung wurde gelesen.
• Hu, Y.; Kallus, N.; Mao, X.: Fast Rates for Contextual Linear Optimization, Management Science 68(6), 2022, arXiv 2011.03030. Die Arbeit nennt als Bedingung für schnelle Raten, wie oft die Lücke zwischen bestem und zweitbestem Extrempunkt klein ist; diese Lücke wird hier nicht gemessen, die Messung zählt nur, wie oft eine kleine Störung den Weg ändert.
• Für die Gibbs-Glättung selbst wurde keine Quelle gelesen: Formeln und Gradient sind selbst hergeleitet und in den Tests nachgerechnet.

Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen; die Angaben stammen aus der Beschreibung der Demo. Dort ist vermerkt, dass die Arbeit von Hu, Kallus und Mao im Volltext gelesen wurde, Beweise und Anhänge aber nicht, und die von Elmachtoub und Grigas nur auf der Ebene der Zusammenfassung. Die Herleitungen und das Rechenbeispiel sind Rechnungen dieser Seite.