← Expertisebereiche/Discrete Choice · Schätzung/2025

BHAMSLE: +17,2 % Log-Likelihood-Gewinn auf London-Mode-Choice-Mischung, in halber Laufzeit von Multistart-Biogeme

Ein Breakpoint Heuristic Algorithm für Maximum Simulated Likelihood Estimation fortgeschrittener Discrete-Choice-Modelle — nutzt dieselbe kombinatorische Struktur, die unsere OR-Spectrum-Pricing-Algorithmen angetrieben hat

Die Schätzung moderner Latent-Class- und Discrete-Continuous-Mischungs-Choice-Modelle ist ein stiller rechentechnischer Albtraum. Hunderte lokale Maxima, Simulationsrauschen, Likelihood-Oberflächen, die aussehen wie die Alpen. Standard-Solver finden einen Gipfel, meist den falschen.

Wir haben die Breakpoint-Struktur, die wir für choice-basiertes Pricing entdeckt haben, auf das Schätzproblem übertragen. Das Ergebnis, BHAMSLE, findet höhere Log-Likelihoods, interpretierbarere Latent-Segmente und bessere Recovery wahrer Parameter als CMA-ES, der bestehende MILP-basierte Schätzer und sogar Multistart-Biogeme mit 50 zufälligen Restarts.

+17,2 %

Log-Likelihood-Gewinn auf der London-Mode-Choice-Discrete-Continuous-Mischung

Halbe Laufzeit

von Multistart-Biogeme M=20, die minimale Restart-Anzahl, die die BHAMSLE-Lösung erreicht

7,7×

schneller als Multistart-Biogeme M=100 bei identischer finaler Log-Likelihood

Findet Wahrheit

Latent-Class-Split (0,69, 0,31), wo Default-Biogeme bei uniform (0,50, 0,50) stecken bleibt

Die Herausforderung

Maximum Simulated Likelihood Estimation fortgeschrittener DCMs, Latent-Class-Modelle mit kontinuierlichen Mischungen, eingeschränkten Choice-Sets und flexiblen Nutzenspezifikationen, leidet unter Multimodalität und simulationsinduziertem Rauschen. Die Likelihood-Oberfläche selbst eines Zwei-Klassen-Logit kann mehrere getrennte Hoch-Likelihood-Becken zeigen; Newton-Typ-Schätzer konvergieren in dasjenige, das dem Startpunkt zufällig am nächsten liegt.

Der einzige strukturbewusste Ansatz in der Literatur ist die MILP-Reformulierung von Fernández Antolín (2018), die im Prinzip globale Optimalität garantiert, aber nicht über winzige Instanzen hinaus skaliert. Standard-Praktiker-Workarounds, Multistart aus zufälligen Initialisierungen, CMA-ES, PSO, bezahlen die Multimodalität mit Brute Force und konvergieren regelmässig in interpretierbaren Unsinn (eine Klasse mit 100 % Wahrscheinlichkeit, Null-Varianz-‘Verteilungen’, kollabierte Mischungsparameter).

Unser Vorgehen

Wir haben beobachtet, dass simulationsbasiertes MSLE dasselbe kombinatorische Rückgrat wie choice-basiertes Pricing teilt: Per-Person-Indikatorvariablen ω_inr, die an endlich vielen parameter-abhängigen Breakpoints umschalten, mit einer Zielfunktion (Log-Likelihood hier, Umsatz dort), die zwischen Sprüngen stückweise konstant ist.

Auf dieser Beobachtung haben wir BHAMSLE gebaut: einen Koordinatenaufstiegs-Algorithmus, der den Parameterraum Breakpoint für Breakpoint abläuft und die simulierte Log-Likelihood exakt an jedem Umschalter auswertet, Struktur ausnutzend, gegen die CMA-ES, PSO und Gradientenmethoden blind sind. Zwei Breakpoint-Quellen werden getrennt behandelt: Nutzen-Parameter-Breakpoints (wo ω flippt, wenn β sich ändert, bei fester Klassenzuweisung) und Scoring-Funktions-Breakpoints (wo die Klassenmitgliedschaft selbst flippt, wenn α oder γ sich ändern).

BHAMSLE ist nicht als finaler Schätzer positioniert, sondern als Initialisierungsstrategie: Schalten Sie es vor Biogemes Standard-Newton-Typ-Routine, und beobachten Sie, wie sich die Endlösung verbessert, die strukturausnutzende Suche kostet Minuten statt der Stunden, die Multistart-Biogeme braucht.

Das Ergebnis

Deliverable: BHAMSLE, ein Breakpoint-Heuristik-Initialisierungsschema für Maximum Simulated Likelihood Estimation fortgeschrittener Discrete-Choice-Modelle (Latent Classes, kontinuierliche Mischungen, Discrete-Continuous-Mischungen). Die Methode nutzt dieselbe kombinatorische Struktur, die unsere OR-Spectrum-Pricing-Algorithmen angetrieben hat, hier angewandt auf Log-Likelihood statt Umsatz.

Auf der London-Mode-Choice-Discrete-Continuous-Mischung (N = 500, R = 500) erreicht mit BHAMSLE initialisiertes Biogeme LL = −243,68 vs. −294,38 mit Default-Initialisierung, eine Verbesserung von +17,2 %, in 3,8 Stunden. Multistart-Biogeme braucht 20 Restarts (7,4 Stunden, rund 2× die BHAMSLE-Laufzeit), um das zu erreichen; mit 100 Restarts braucht es 7,7× die BHAMSLE-Laufzeit für dieselbe finale Qualität. Auf dem diskreten Latent-Class-Test erkennt mit BHAMSLE initialisiertes Biogeme den wahren Class-Split (0,69, 0,31), wo Default-Biogeme bei uniform (0,50, 0,50) stecken bleibt.

Technischer Deep Dive

Das Modell hinter dem Ergebnis.

Das Modell

Maximum Simulated Likelihood Estimation eines fortgeschrittenen DCM hat eine grundlegend andere Struktur als das Lehrbuch-Logit. Die Choice-Wahrscheinlichkeiten haben keine geschlossene Form (Mischungsmodelle integrieren über kontinuierliche Verteilungen von Geschmacksparametern), also approximieren wir per Monte Carlo. Das bringt R simulierte Szenarien pro Person, und an jedem Parameterwert hat jedes (n, r)-Paar einen deterministischen Indikator ‘beobachtete Alternative gewinnt’, der je nachdem, ob der Parameter über oder unter einer kunden-szenario-spezifischen Schwelle liegt, ein- oder ausgeschaltet wird. Die Breakpoint-Struktur, die BHAMSLE ausnutzt, ist genau die Menge der Parameterwerte, an denen einer dieser Umschalter geschieht.

β, π max n \in N \sum ln (s \in S \sum π_{n s} P_{y_{n} n}^{s} (β)), P_{in}^{s} = P (U_{in}^{s} \geq U_{j n}^{s} \forall j \in C_{n}^{s}) .

Das MSLE-Problem in stochastischer Form. Summe über Personen des Logarithmus eines wahrscheinlichkeits-gewichteten Mittels der Per-Klasse-Choice-Wahrscheinlichkeiten. Entscheidungsvariablen sind die Nutzenkoeffizienten β (oft klassenabhängig) und die Klassenmitgliedschafts-Wahrscheinlichkeiten π. Für kontinuierliche Mischungen ist P^s_in ein Integral über eine Normalverteilungsdichte der verteilten Geschmacksparameter, weshalb Simulation nötig ist.

U_{in r}^{s} = k \in K_{s} \sum x_{ink} β_{k} + ε_{in r}, ω_{in r}^{s} = 1 [U_{in r}^{s} = j \in C_{n}^{s} max U_{j n r}^{s}] .

Simulationsrahmen. Für jedes Szenario r und Person n wird der Nutzen von Alternative i unter Klasse s deterministisch, sobald der Fehlerterm ε_inr gezogen ist. Der Choice-Indikator ω^s_inr ist 1 genau dann, wenn i das Arg-Max für (n, s, r) gewinnt. Das Mittel von ω über die R Draws ist ein erwartungstreuer Schätzer von P^s_in (Train 2003).

s LL (β, π) = - N ln R + n \in N \sum ln (Σ_{n} (β, π)), Σ_{n} := r \in R \sum s \sum 1_{class assignment} \cdot ω_{y_{n} n r}^{s} .

Simulierte Log-Likelihood nach Monte Carlo. Σ_n zählt, wie viele der R Szenarien die beobachtete Alternative y_n für Person n wählen (unter der Klassenzuweisung des Szenarios). Die Zielfunktion ist die Summe der log-Σ_n über die Personen, eine stückweise-konstante Funktion in β und π, die an jedem Breakpoint springt, an dem ein ω flippt.

[s_{1}, s_{2}] : U_{y_{n} n r}^{s} (β_{j}) \geq U_{in r}^{s} (β_{j}) \forall i \in C_{n}^{s} . (entry breakpoint s_{1}, exit breakpoint s_{2})

Breakpoint-Konstruktion für einen Nutzenparameter β_j. Wir frieren alle anderen Parameter ein, dann ist das Segment von β_j, für das die beobachtete Alternative y_n für Person n in Szenario r unter Klasse s dominant bleibt, durch zwei Indifferenzpunkte begrenzt. Die untere Schranke s_1 ist ein ‘Entry’-Breakpoint (ω flippt an, wenn β_j darüber wächst); die obere Schranke s_2 ist ein ‘Exit’. Über alle (n, r, s) erhalten wir höchstens 2NRS Breakpoints pro Parameter.

At an entry breakpoint: Δ s LL = ln (Σ_{n} + 1) - ln (Σ_{n}); at an exit: Δ s LL = ln (Σ_{n} - 1) - ln (Σ_{n}) .

Inkrementelle Log-Likelihood-Updates. Beim Durchlaufen der Breakpoints in sortierter Reihenfolge entlang der j-ten Koordinate ist die Änderung der simulierten Log-Likelihood an jedem nur die Differenz zweier Log-Zählungen, O(1)-Arbeit pro Breakpoint, statt der O(NR)-Kosten, die ein Blackbox-Optimierer für eine volle Neuberechnung zahlen würde. Das ist, was BHAMSLE skalieren lässt: Ein voller Koordinatenpass kostet O(NRS) statt O((NR)²) für naive Liniensuche.

β_{j}^{(t + 1)} = ar g β_{j} \in B_{j} (β_{- j}^{(t)}) max s LL (β_{- j}^{(t)}, β_{j}), j (t + 1) = (j (t) mod (K + S)) + 1.

Äussere BHAMSLE-Schleife. Koordinatenaufstieg über die K Nutzenparameter und die S − 1 Klassenwahrscheinlichkeits-Parameter. An jedem Schritt frieren wir K + S − 2 Parameter ein, zählen die Breakpoints für die aktive Koordinate auf und wählen denjenigen, der die simulierte Log-Likelihood maximiert. Wir terminieren, wenn ein voller K + S-Koordinatenpass keine Verbesserung über τ = 10⁻⁶ liefert.

T_{BHAMSLE} = O (C \cdot (K + S) \cdot N R S) ≪ T_{Multistart Biogeme} = O (M \cdot T_{Newton}) .

Komplexitätsvergleich. C ist die Anzahl äusserer Koordinatenaufstiegs-Zyklen (empirisch < 20 auf Benchmark-Instanzen); der innere Term NRS ist die Breakpoint-Enumeration und das inkrementelle Update. Multistart-Biogeme muss eine volle Newton-Konvergenz pro Restart M bezahlen, und M muss mit der Anzahl lokaler Optima wachsen, die bei Discrete-Continuous-Mischungen in den Hunderten liegt. Auf der Test-4-London-Mischung trifft BHAMSLE Multistart-Biogeme bei M = 20 in etwa halber Wall-Clock-Zeit und übertrifft M = 10.

Was wir hier getan haben: eine strukturelle Beobachtung aus einer völlig anderen Problemklasse, Pricing, übernommen und festgestellt, dass sie sich auf die Schätzung überträgt, weil beide Probleme eine äussere Zielfunktion über simulierten Discrete-Choice-Indikatoren berechnen. Dieselbe Breakpoint-Enumeration, die BEA und BHA in den Pricing-Papern getrieben hat, treibt hier BHAMSLE, mit zwei neuen Falten: (1) Die Zielfunktion hat einen Log statt einer Summe, also nutzen wir inkrementelle ln-Updates statt Additionen, und (2) die Latent-Class-Parameter leben innerhalb von Indikatorfunktionen für die Klassenzuweisung, nicht für die Alternativenwahl, brauchen also eigene Breakpoint-Logik. Der Payoff ist über jeden Test im Paper konsistent: BHAMSLE-initialisiertes Biogeme findet höhere Log-Likelihoods als Default-Initialisierung, schneller als CMA-ES oder PSO und mit weniger Rechenbudget als der Lehrbuch-Multistart-Workaround.

Benchmark

Test 4 aus dem Paper: Discrete-Continuous-Mischung von Logit auf dem London-Mode-Choice-Datensatz (4 Alternativen: Gehen, Velo, ÖV, Fahren; N = 500, R = 500; wahre Klassenaufteilung 0,70/0,30; Kosten-Sensitivität normalverteilt). Jede Methode wird als Initialisierung für Biogemes Newton-Typ-Schätzer verwendet; wir berichten die erreichte Log-Likelihood (höher ist besser, also weniger negativ) und die gesamte Wall-Clock-Zeit. MSB = Multistart-Biogeme mit M zufälligen Restarts in [-12, 12].

Initialisierungsmethode	Endgültige Log-Likelihood	ΔLL vs. Default	Gesamtzeit (s)	ΔZeit vs. Default
Biogeme (default)	−294,38	-	583	-
Biogeme + BHAMSLE (unser)	−243,68	+50,69 (+17,2 %)	13 796	+13 212 s (+2 265 %)
MSB (M = 10)	−243,78	+50,60 (+17,2 %)	15 003	+14 419 s (+2 472 %)
MSB (M = 20)	−243,69	+50,69 (+17,2 %)	26 706	+26 122 s (+4 478 %)
MSB (M = 50)	−243,68	+50,69 (+17,2 %)	68 062	+67 479 s (+11 568 %)
MSB (M = 100)	−243,68	+50,69 (+17,2 %)	106 438	+105 854 s (+18 151 %)

Zwei Punkte stechen heraus. Erstens: Die Default-Biogeme-Initialisierung bleibt in einem lokalen Optimum stecken, das 17 % schlechter ist als das globale, und Newton-Typ-Methoden können das nicht erkennen. BHAMSLE’s strukturbewusste Suche behebt das, indem sie den Schätzer am schlechten Becken vorbeiführt, bevor er anfängt. Zweitens: BHAMSLE trifft die Endlösung, die Multistart mit M = 20 Restarts findet, bei etwa halber Wall-Clock-Zeit. Mit M = 10 Restarts liegt Multistart sogar leicht unter BHAMSLE in der Qualität und über ihm in der Laufzeit. Die Implikation: Brute-Force-Restarts zahlen eine steile Steuer dafür, nicht zu wissen, wo zu suchen, BHAMSLE weiss es, weil die Problemstruktur es sagt. Dasselbe Muster wiederholt sich in allen vier experimentellen Setups im Paper: diskrete Mischungen mit beobachteten und synthetischen Wahlen, Discrete-Continuous-Mischungen mit beiden, auf Swiss-Metro- und London-Mode-Choice-Daten.

Aus den Unterlagen

Abschnitt 2.1 des Papers: Setup des Latent-Class-Choice-Modells. Jede Person n soll einer von S latenten Klassen angehören; jede Klasse hat ihren eigenen Parametervektor β^(s) und ihr Choice Set C_n^s. Die Klassenmitgliedschafts-Wahrscheinlichkeiten π_ns werden ihrerseits aus Daten geschätzt, entweder direkt oder über Scoring-Funktionen f_ns. Die Likelihood-Oberfläche selbst dieses Zwei-Klassen-Einzel-Erklärungsvariable-Beispiels zeigt mehrere getrennte Hoch-Likelihood-Becken, die Motivation für alles, was folgt.

Formulierung (1)–(6) aus dem Paper: das MSLE-Problem als beschränkte Maximierung über Nutzenkoeffizienten β, Klassen-Scoring-Koeffizienten α, Choice-Wahrscheinlichkeiten P^s und Klassenmitgliedschafts-Wahrscheinlichkeiten π. Das nicht-geschlossen-formig ℙ(U_in^s ≥ U_jn^s) in der dritten Constraint ist genau dort, wo Simulation eingreift, für fortgeschrittene DCMs hat dieses Integral keine geschlossene Lösung, also ersetzen wir es durch ein Monte-Carlo-Stichprobenmittel, und das Problem wird ein MILP.

Algorithmus-Schritte 1–4 von BHAMSLE: Beginnend mit einem initialen Parametervektor fixieren wir alle Koordinaten ausser β_j, iterieren dann über alle (Person, Szenario)-Paare und berechnen das Intervall [s_1, s_2] der β_j-Werte, für die die beobachtete Alternative nutzendominant bleibt. Die Endpunkte dieses Intervalls sind ein Entry- und ein Exit-Breakpoint für die simulierte Likelihood. Die Menge aller Breakpoints über (n, r, s) ergibt die Kandidatenzüge für diese Koordinate.

Algorithmus-Schritt 4 fortgesetzt: Wenn die aktive Koordinate ein Klassenwahrscheinlichkeits-Parameter γ_g ist (statt eines Nutzenkoeffizienten), ändert sich die Breakpoint-Logik. Hier fragt der Algorithmus, welche Klassenzuweisung für jedes (n, r) aktuell gewinnt, und berechnet dann das Segment der γ_g-Werte, für die diese Zuweisung weiter gewinnt, und registriert Entry/Exit-Breakpoints entsprechend. Diese duale Breakpoint-Konstruktion (Nutzen vs. Klassenmitgliedschaft) ist eine der zwei nicht-trivialen Verallgemeinerungen, die BHAMSLE gegenüber dem originalen BHA aus den Pricing-Papern leistet.

Techniken

Breakpoint-Enumeration für simulationsbasierte Likelihood
Koordinatenaufstieg über MSLE-Parameter
Latent-Class- / Mischungsmodell-Schätzung
Inkrementelle ln(Σ ± 1) − ln(Σ)-Updates
Vergleich mit CMA-ES, Multistart-Biogeme

Stack

Python
Biogeme 3.2.14
Julia (CMA-ES via Evolutionary.jl)
Gurobi (für MILP-Baseline)

Ein Problem wie dieses?

Wir würden gerne davon hören.

contact@optimally.ch