Improving FMQA via Initial Training Data Design Considering Marginal Bit Coverage in One-Hot Encoding

Dieser Beitrag schlägt vor, den Faktorzerlegungs-Maschinen-Algorithmus mit quadratischer Optimierung und Temperung (FMQA) zu verbessern, indem durch Latin-Hypercube- und Sobol'-Abtastverfahren initiale Trainingsdaten entworfen werden, um eine vollständige Abdeckung der marginalen Bits in der One-Hot-Codierung sicherzustellen und damit die Optimierung auf Probleme mit ganzzahligen und diskretisierten kontinuierlichen Variablen zu verbessern.

Das Wesentliche

Stellen Sie sich vor, Sie versuchen, die perfekte Form für den Flügel eines von Menschen angetriebenen Flugzeugs zu finden. Sie möchten, dass es so schnell wie möglich fliegt, aber die beteiligten physikalischen Zusammenhänge sind so komplex, dass Sie keine einfache Formel aufschreiben können, um die Geschwindigkeit vorherzusagen. Stattdessen müssen Sie ein virtuelles Modell erstellen, es testen, sehen, wie schnell es ist, und es dann erneut versuchen. Dies ist ein „Black-Box"-Problem: Sie geben ein Design ein, und eine Geschwindigkeit kommt heraus, aber Sie kennen das geheime Rezept im Inneren nicht.

Um dies zu lösen, verwenden Forscher ein intelligentes Computerprogramm namens FMQA. Stellen Sie sich FMQA als ein zweistufiges Detektivteam vor:

1. Der Surrogat (Der Schüler): Ein maschinelles Lernmodell, das versucht, die Antwort basierend auf früheren Tests zu erraten.
2. Der Sucher (Der Jäger): Ein spezialisierter Computer (eine „Ising-Maschine"), der die Vermutungen des Schülers nutzt, um nach der bestmöglichen Flügelform zu suchen.

Das Problem: Die „stummen" Bits

Um dem Computer die Flügelform verständlich zu machen, übersetzen die Forscher die kontinuierlichen Designvariablen (wie „Flügellänge") in eine Zeichenkette aus binären Schaltern (0 und 1) unter Verwendung einer Methode namens One-Hot-Codierung.

Stellen Sie sich vor, Sie haben 32 Schalter für die „Flügellänge". Um zu sagen, die Länge sei „mittel", schalten Sie genau einen dieser 32 Schalter auf „EIN" (1) und lassen die anderen 31 auf „AUS" (0).

Die Arbeit identifiziert einen Fehler darin, wie sie diesen Prozess normalerweise starten. Sie wählen die startenden Flügelformen typischerweise durch Würfeln (zufällige Stichproben) aus.

• Das Problem: Wenn Sie nur 32 Mal würfeln, um zu starten, besteht eine hohe Wahrscheinlichkeit (etwa 36 %), dass einige dieser 32 Schalter während der Anfangsphase niemals auf „EIN" geschaltet werden.
• Die Folge: Der „Schüler" (das maschinelle Lernmodell) lernt, indem er sich die Schalter ansieht, die EIN waren. Wenn ein Schalter niemals EIN war, lernt der Schüler nie, wie diese spezifische Einstellung die Geschwindigkeit beeinflusst. Es ist wie ein Lehrer, der versucht, einen Schüler zu benoten, der nie die Hand gehoben hat; der Lehrer hat keine Daten über die Fähigkeiten dieses Schülers.
• Das Ergebnis: Die „Karte" des Problems im Computer hat blinde Flecken. Wenn der „Jäger" nach der besten Lösung sucht, ignoriert er möglicherweise gute Bereiche, weil die Karte sagt: „Wir haben keine Ahnung, was hier passiert."

Die Lösung: Die Strategie des „fairen Stichprobenziehens"

Die Autoren schlagen eine neue Art vor, die startenden Flügelformen auszuwählen. Anstatt nur zu würfeln, verwenden sie zwei mathematische Werkzeuge namens Latin-Hypercube-Sampling (LHS) und die Sobol'-Folge.

Stellen Sie sich diese Werkzeuge als einen Fairness-Inspektor vor.

• Anstatt darauf zu hoffen, dass das Glück jeden Schalter umschaltet, stellt der Inspektor sicher, dass jeder einzelne der 32 Schalter während der ersten 32 Tests mindestens einmal auf „EIN" geschaltet wird.
• Dies garantiert, dass der „Schüler" vor Beginn der eigentlichen Suche eine direkte Lektion über jede einzelne mögliche Einstellung erhält. Kein Schalter bleibt im Dunkeln.

Die Ergebnisse: Bessere Flügel, schneller

Die Forscher testeten dies an zwei Versionen des Flügelproblems: einer mit 17 Designvariablen und einer schwierigeren mit 32 Variablen.

1. Der „alte Weg" (Zufall): Selbst nach 200 Tests waren etwa 36 % der Schalter in den Startdaten niemals eingeschaltet worden. Die Leistung des Computers war in Ordnung, aber sie hatte blinde Flecken.
2. Der „neue Weg" (LHS und Sobol'): Jeder Schalter wurde von Anfang an mindestens einmal eingeschaltet.
   • Das Ergebnis: Die neuen Methoden fanden Flügelformen, die schneller flogen als die alte zufällige Methode.
   • Der Unterschied: Die Verbesserung war beim einfacheren Problem gering, wurde aber beim schwierigeren Problem mit 32 Variablen deutlich offensichtlicher. Es ist, als ob die blinden Flecken auf der Karte wichtiger wurden, wenn das Gelände komplexer wurde.

Das Fazit

Die Arbeit behauptet nicht, dass dies den Computer das Flugzeug selbst fliegen lässt, noch behauptet sie, dass dies alle Optimierungsprobleme löst. Sie zeigt lediglich, dass wie man startet, wichtig ist.

Durch die Verwendung einer Strategie des „fairen Stichprobenziehens", um sicherzustellen, dass jede mögliche Option in den initialen Trainingsdaten eine Chance hat, gesehen zu werden, lernt der Computer eine bessere Karte des Problems. Dies ermöglicht es ihm, schneller bessere Lösungen zu finden, insbesondere wenn das Problem kompliziert wird. Es ist eine Erinnerung daran, dass man bei der Optimierung nicht nur eine intelligente Suchmaschine braucht, sondern auch eine intelligente Art, die Reise zu beginnen.

Technische Zusammenfassung

Technische Zusammenfassung: Verbesserung von FMQA durch das Design initialer Trainingsdaten unter Berücksichtigung der marginalen Bitabdeckung in der One-Hot-Kodierung

Problemstellung
Die Factorization Machine mit quadratischer Optimierungs-Annealing (FMQA) ist eine Black-Box-Optimierungsmethode (BBO), die ein Factorization-Machine- (FM) Surrogatmodell mit einer Ising-Maschine für die Suche kombiniert. Wenn FMQA auf ganzzahlige oder diskretisierte kontinuierliche Variablen unter Verwendung einer One-Hot-Kodierung angewendet wird, tritt bei einer gleichmäßigen zufälligen initialen Stichprobenziehung ein kritisches Problem auf. In diesem Szenario nehmen viele binäre Variablen (Bits) im initialen Trainingsdatensatz möglicherweise niemals den Wert „1" an. Da der Gradient des FM-Ausgangs bezüglich der mit einem bestimmten Bit verknüpften Parameter proportional zum Wert dieses Bits ist, erhalten Parameter, die Bits entsprechen, die im gesamten initialen Datensatz den Wert „0" behalten, keine direkten Gradientenupdates aus den beobachteten Antworten. Folglich entwickeln sich diese Parameter ausschließlich basierend auf der Initialisierung und dem Gewichtsverfall, was eine Verzerrung in die geschätzten Koeffizienten der quadratischen ungebundenen binären Optimierung (QUBO) einführt. Diese Verzerrung kann die Qualität der vom Ising-Maschine durchgeführten Lösungssuche beeinträchtigen, insbesondere bei Problemen höherer Dimension.

Methodik
Die Autoren schlagen eine Modifikation des FMQA-Rahmens vor, die sich auf das Design der initialen Trainingsdaten konzentriert. Das Hauptziel ist die Erreichung einer vollständigen marginalen Bitabdeckung, wodurch sichergestellt wird, dass jede binäre Variable, die durch One-Hot-Kodierung erhalten wird, im initialen Datensatz mindestens einmal den Wert „1" annimmt.

Um dies zu realisieren, führen die Autoren zwei Methoden zur Generierung initialer Daten ein, die auf raumfüllenden Stichprobenverfahren basieren:

1. LHS-FMQA: Nutzt die Latin-Hypercube-Sampling-Methode (LHS).
2. Sobol'-FMQA: Nutzt die Sobol'-Folge (eine deterministische Folge mit geringer Diskrepanz).

Beide Methoden sind so konfiguriert, dass die Anzahl der initialen Stichproben ($N_0$) der Anzahl der diskreten Werte pro Variable ($M$) entspricht. Unter der One-Hot-Kodierung, bei der jede ursprüngliche Variable durch $M$ binäre Bits dargestellt wird, ermöglicht die Einstellung von $N_0 = M$, dass diese Stichprobenstrategien garantieren, dass jeder diskrete Wert mindestens einmal ausgewählt wird. Durch die Dekodierungskarte wird sichergestellt, dass jedes entsprechende binäre Bit mindestens einmal den Wert „1" annimmt. Dies garantiert, dass alle FM-Parameter während der initialen Trainingsphase direkte, aus dem Datensatz abgeleitete Gradientenupdates erhalten, wodurch die durch „nie-aktive" Bits verursachte Verzerrung gemildert wird.

Hauptbeiträge

• Identifikation eines Verzerrungsmechanismus: Die Arbeit identifiziert formal, dass eine gleichmäßige zufällige Stichprobenziehung in der One-Hot-kodierten FMQA zu „nie-aktiven" Bits führt, wodurch bestimmte FM-Parameter nicht durch beobachtete Black-Box-Antworten informiert werden.
• Vorgeschlagene Initialisierungsstrategie: Die Autoren schlagen und implementieren Designs für initiale Trainingsdaten vor, die LHS- und Sobol'-Folgen verwenden, um speziell die marginale Bitabdeckung durchzusetzen ($N_0 = M$).
• Empirische Validierung: Die Methoden wurden am Benchmark für die Optimierung der Flügelgeometrie eines von Menschen angetriebenen Flugzeugs (HPA) (HPA103) evaluiert, einem komplexen ingenieurwissenschaftlichen Problem mit impliziten Einschränkungen und ohne analytische Gradienteninformationen. Experimente wurden an zwei Problemskalen durchgeführt: 17 Designvariablen (HPA103-1) und 32 Designvariablen (HPA103-2).

Ergebnisse
Numerische Experimente, die die vorgeschlagenen Methoden (LHS-FMQA und Sobol'-FMQA) mit einer Baseline Conv-FMQA (gleichmäßige zufällige Initialisierung) und anderen Optimierern (GP-BO, NSGA-II, Random Search) verglichen, ergaben Folgendes:

• Leistungsverbesserung: Beide vorgeschlagenen Methoden erreichten numerisch höhere mittlere Endkreuzgeschwindigkeiten als die Baseline Conv-FMQA.
• Dimensionsabhängigkeit: Der Vorteil der vorgeschlagenen Methoden war beim Problem höherer Dimension (HPA103-2, 32 Variablen) ausgeprägter. Die Verbesserung der Endkreuzgeschwindigkeit gegenüber der Baseline stieg von etwa +0,135 m/s (LHS) und +0,192 m/s (Sobol') beim 17-Variablen-Problem auf +0,333 m/s bzw. +0,352 m/s beim 32-Variablen-Problem.
• Mechanismusbestätigung: Die Analyse der Bitverwendungverteilungen bestätigte, dass Conv-FMQA selbst nach dem gesamten Evaluierungsbudget noch etwa 36 % „nie-aktiver" Bits behielt, während die vorgeschlagenen Methoden 0 % „nie-aktive" Bits erreichten.
• Vergleich mit anderen Optimierern: Die vorgeschlagenen Methoden schnitten vergleichbar mit oder besser als GP-BO und NSGA-II ab. Bemerkenswert ist, dass die Verbesserung gegenüber Conv-FMQA durch den Optimierungsprozess nach der initialen Stichprobenphase (höherer „Gewinn") getrieben wurde und nicht einfach durch einen Start von besseren initialen Bestwerten.

Bedeutung und Behauptungen
Die Arbeit behauptet, dass die Verbesserung der marginalen Bitabdeckung in den initialen Trainingsdaten ein entscheidender Faktor für die Leistungssteigerung von FMQA ist. Durch die Sicherstellung, dass jede binäre Variable mindestens einmal aktiv ist, verhindern die vorgeschlagenen Methoden, dass die QUBO-Koeffizienten ausschließlich durch Initialisierung und Gewichtsverfall in bestimmten Richtungen bestimmt werden. Dies ermöglicht der Ising-Maschine eine informierte Suche über alle Designdimensionen hinweg.

Die Autoren vermerken bescheiden, dass ihre Ergebnisse zwar die Hypothese stützen, dass marginale Abdeckung die Verzerrung reduziert, die aktuelle Studie den Effekt der marginalen Abdeckung jedoch nicht vollständig von den raumfüllenden Eigenschaften der LHS- und Sobol'-Folgen isoliert. Sie erkennen an, dass die vorgeschlagenen Methoden beide Eigenschaften gleichzeitig erreichen. Darüber hinaus stellen sie fest, dass die Methoden die marginale Abdeckung garantieren, aber nicht die paarweise Bitabdeckung (Interaktionen zwischen Bits). Die Studie kommt zu dem Schluss, dass diese Initialisierungsstrategien insbesondere für Probleme höherer Dimension wirksam sind, bei denen die absolute Anzahl potenziell inaktiver Bits bei zufälliger Stichprobenziehung andernfalls erheblich wäre. Als zukünftige Arbeiten wird vorgeschlagen, die marginale Abdeckung von den raumfüllenden Eigenschaften zu entkoppeln und Strategien zur paarweisen Abdeckung zu untersuchen.