🤖 machine learning

Stage-dependent integer-binary encoding in factorization-machine black-box optimization

Dieses Paper schlägt ein stufenabhängiges Factorization-Machine-Framework mit Quadratic-optimization Annealing (FMQA) vor, das One-Hot-Encoding für das Surrogate-Learning und Domain-Wall-Encoding für die Ising-Maschinen-Suche nutzt, wobei nachgewiesen wird, dass während das One-Hot-Encoding in der Lernphase der primäre Treiber der Optimierungsleistung ist, der Wechsel zu Domain-Wall-Encoding für die Suche die Ergebnisse unter Bedingungen feiner Diskretisierung weiter verbessern kann.

Ursprüngliche Autoren: Ryo Ogawa, Mayumi Nakano, Yuya Seki, Shu Tanaka

Veröffentlicht 2026-06-23

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Ryo Ogawa, Mayumi Nakano, Yuya Seki, Shu Tanaka

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Ganze: Ein Rätsel mit zwei verschiedenen Karten lösen

Stellen Sie sich vor, Sie sind ein Detektiv, der versucht, den tiefsten Punkt in einer riesigen, nebligen Gebirgskette zu finden (das Black-Box-Optimierungsproblem). Sie können nicht die ganze Karte sehen; Sie können nur einen Scout an einen bestimmten Ort schicken, die Höhe prüfen und sich zurückmelden lassen. Ihr Ziel ist es, den absoluten Boden des Tals (das Globale Optimum) mit so wenig Reisen wie möglich zu finden, da jede Reise viel Geld und Zeit kostet.

Um dies effizient zu gestalten, erstellen Sie ein Surrogatmodell – eine grobe Skizze des Geländes basierend auf den Orten, die Sie bereits besucht haben. Dann nutzen Sie einen superschnellen Computer (eine Ising-Maschine), um Ihre Skizze zu betrachten und zu raten, wo der tiefste Punkt liegen könnte.

Die Arbeit von Ogawa, Nakano, Seki und Tanaka befasst sich mit einem spezifischen Problem bei diesem Prozess: Wie übersetzt man die reale Welt in eine Sprache, die der Supercomputer versteht?

Das Problem: Eine Sprache passt nicht für alles

In der Vergangenheit verwendeten Forscher eine einzige „Übersetzungsmethode“ (genannt Integer-Binär-Kodierung) für den gesamten Prozess. Sie nutzten dieselbe Methode, um:

Zu Lernen: Die Skizze (das Surrogatmodell) basierend auf Daten zu trainieren.
Zu Suchen: Den Supercomputer zu fragen, wo der beste Punkt auf dieser Skizze liegt.

Die Autoren erkannten, dass die „Sprache“, die am besten zum Lernen geeignet ist, eine andere sein kann als die Sprache, die am besten zum Suchen geeignet ist. Es ist wie beim Schreiben eines Romans: Man verwendet vielleicht ein bestimmtes Vokabular, um einem Schüler das Schreiben beizubringen, aber einen völlig anderen Satz von Regeln, um seine Abschlussprüfung zu bewerten.

Die Lösung: Die „stufenabhängige“ Strategie

Das Team schlug ein neues Framework namens Stage-Dependent FMQA vor. Anstatt für die gesamte Reise eine einzige Übersetzungsmethet zu verwenden, wechseln sie die Sprache auf halbem Weg.

Sie testeten zwei Haupt-„Sprachen“ zur Übersetzung von Zahlen in Binärcode (0 und 1):

One-Hot-Kodierung: Stellen Sie sich eine Reihe von Lichtschaltern vor. Um die Zahl „3“ darzustellen, schalten Sie nur den dritten Schalter ein. Es ist sehr klar und deutlich, erfordert aber viele Schalter.
Domain-Wall-Kodierung (Domänenwand-Kodierung): Stellen Sie sich eine Reihe von Dominosteinen vor. Um die „3“ darzustellen, kippen Sie die ersten drei Dominosteine um und lassen den Rest stehen. Es ist kompakter und erzeugt eine glatte „Wand“ zwischen den umgekippten und den stehenden Steinen.

Der Zaubertrick:
Die Autoren leiteten eine mathematische Formel ab, um die „Skizze“ von der One-Hot-Sprache in die Domain-Wall-Sprache (und umgekehrt) zu konvertieren, ohne Informationen zu verlieren. Dies ermöglichte es ihnen:

Zu Lernen mit One-Hot (weil dies die Skizze sehr genau macht).
Zu Suchen mit Domain-Wall (weil der Supercomputer den Punkt in diesem Format schneller und zuverlässiger findet).

Sie nannten diese spezifische Kombination die OhDw-Methode (One-Hot zum Lernen, Domain-Wall zum Suchen).

Das Experiment: Der Rastrigin-Berg

Um dies zu testen, verwendeten sie eine berühmte, schwierige Testfunktion namens Rastrigin-Funktion.

Die Analogie: Stellen Sie sich eine Landschaft vor, die mit tausenden winzigen, identischen Kratern (lokale Optima) übersät ist, die einen riesigen, tiefen Canyon (das globale Optimum) umgeben. Es ist sehr leicht, in einem kleinen Krater stecken zu bleiben und zu glauben, man habe den Boden gefunden.
Das Setup: Sie testeten dies auf Bergen unterschiedlicher Größe (Dimensionen) und mit unterschiedlichen Detailgraden (Diskretisierungsstufen).

Die Ergebnisse: Warum der Wechsel funktioniert

Die Experimente lieferten einige faszinierende Erkenntnisse:

Lernen ist entscheidend: Der wichtigste Faktor für den Erfolg war die Sprache, die während der Lernphase verwendet wurde. Die Verwendung der One-Hot-Kodierung, um die Skizze zu erstellen, lieferte konsistent bessere Ergebnisse als Domain-Wall oder die Standard-Binärkodierung. Es scheint, dass One-Hot dem KI-System hilft, das Gelände „klarer zu sehen“.
Suchen braucht einen Schub: Sobald die Skizze erstellt war, half der Wechsel zur Domain-Wall-Kodierung in der Suchphase dem Supercomputer, das Gelände besser zu navigieren, insbesondere in komplexen Szenarien mit hohem Detailgrad.
Der ideale Mittelweg:
- Für einfache Probleme mit geringem Detailgrad war es ausreichend, bei One-Hot zu bleiben.
- Für komplexe Probleme mit hohem Detailgrad (große Berge mit vielen winzigen Kratern) war die OhDw-Methode (der Sprachwechsel) der klare Gewinner. Sie fand den Boden des Canyons genauer und mit weniger Fehlern als jede andere Methode.

Das Fazit

Die Arbeit kommt zu dem Schluss, dass in der Welt der KI-Optimierung „Einheitslösungen“ nicht funktionieren.

Genau wie ein Zimmermann vielleicht eine feine Säge zum Schneiden von filigranem Holz nutzt, aber einen schweren Hammer, um Nägel einzuschlagen, legt diese neue Methode nahe, dass wir One-Hot-Kodierung zum Lernen (weil sie präzise ist) und Domain-Wall-Kodierung zum Suchen (weil sie effizient ist) verwenden sollten. Durch den Wechsel der Werkzeuge zum richtigen Zeitpunkt können wir komplexe Optimierungsprobleme viel schneller und genauer lösen.

Kurz gesagt: Nutzen Sie nicht dieselbe Karte sowohl für das Studium des Geländes als auch für die Navigation. Nutzen Sie die beste Karte für die jeweilige Aufgabe, und Sie werden Ihr Ziel schneller erreichen.

Technisches Resümee: Stufenabhängige Integer-Binär-Kodierung in der Black-Box-Optimierung mittels Faktorisierungsmaschinen

Problemstellung
Die Black-Box-Optimierung (BBO) befasst sich mit Problemen, bei denen die Zielfunktionen keine expliziten analytischen Formen besitzen und deren Auswertung kostspielig ist. Die Factorization Machine with Quadratic-optimization Annealing (FMQA) ist ein prominenter BBO-Ansatz, der ein Ersatzmodell (Surrogatmodell) mittels einer Factorization Machine (FM) konstruiert und dieses unter Verwendung einer Ising-Maschine optimiert. Eine kritische Komponente von FMQA ist die Umwandlung von ganzzahligen oder kontinuierlichen Variablen in binäre Variablen mittels Integer-Binär-Kodierung (z. B. One-Hot-, Domain-Wall- oder Binär-Kodierung), um das Problem als Modell für die quadratische unbeschränkte binäre Optimierung (QUBO) zu formulieren.

Konventionelle FMQA verwendet eine einzige Integer-Binär-Kodierungsmethode sowohl während der maschinellen Lernphase (Konstruktion des Ersatzmodells) als auch während der Lösungs-Suchphase (Optimierung durch die Ising-Maschine). Vorangegangene Forschungen deuten jedoch auf einen Zielkonflikt hin: Die Domain-Wall-Kodierung liefert oft eine überlegene Performance bei der Lösensuche in Ising-Maschinen, während die One-Hot-Kodierung beobachtet wurde, niedrigere Zielfunktionswerte im gesamten FMQA-Optimierungsprozess zu erzielen. Diese Diskrepanz impliziert, dass die Kodierung, die optimal für das Lernen der Ersatzlandschaft ist, von der Kodierung abweichen kann, die optimal für das Durchsuchen dieser Landschaft ist. Konventionelle Methoden, die eine einzige Kodierung festlegen, versäumen es möglicherweise, die unterschiedlichen Fähigkeiten der FM und der Ising-Maschine voll auszuschöpfen.

Methodik
Die Autoren schlagen ein stufenabhängiges FMQA-Framework vor, das unterschiedliche Integer-Binär-Kodierungsmethoden für die Phasen des maschinellen Lernens und der Lösungs-Suche verwendet. Der Kern dieses Ansatzes umfasst:

Dual-Encoding-Strategie: Das Framework trainiert das FM-Ersatzmodell unter Verwendung einer für das Lernen geeigneten Kodierung (speziell der One-Hot-Kodierung in der vorgeschlagenen „OhDw“-Variante) und konvertiert das resultierende Ersatzmodell anschließend in eine andere, für die Suche geeignete Kodierung (speziell die Domain-Wall-Kodierung), bevor die Optimierung durch die Ising-Maschine erfolgt.
QUBO-Matrix-Konvertierung: Um diesen Wechsel zu ermöglichen, haben die Autoren mathematische Konvertierungsformeln zwischen den QUBO-Matrizen der One-Hot- und der Domain-Wall-Kodierung hergeleitet. Diese Formeln stellen sicher, dass die Zielfunktionslandschaft des Ersatzmodells über alle zulässigen ganzzahligen Zustände hinweg bis auf eine additive Konstante erhalten bleibt.
- Die Konvertierung von One-Hot zu Domain-Wall beinhaltet die Transformation der Diagonal- und Nebendiagonalterme der QUBO-Matrix $Q^{(oh)}$ zu $Q^{(dw)}$ unter Verwendung spezifischer Summenbeziehungen (Gl. 18–20).
- Die inverse Konvertierung (Domain-Wall zu One-Hot) wurde ebenfalls hergeleitet (Gl. 22–24).
- Die Rechenkomplexität für diese wechselseitigen Konvertierungen wird mit $O(N^2q^2)$ angegeben, wobei $N$ die Eingabedimension und $q$ die Anzahl der Diskretisierungsstufen ist.
Algorithmischer Arbeitsablauf:
- Lernphase: Eine FM wird auf Eingangs-Ausgangs-Daten trainiert, die mittels One-Hot-Kodierung kodiert sind.
- Konvertierung: Das trainierte Ersatzmodell (repräsentiert als QUBE-Matrix) wird von einer One-Hot- in eine Domain-Wall-Kodierung konvertiert.
- Suchphase: Die konvertierte QUBO, ergänzt um Domain-Wall-Kodierungsbeschränkungen, wird mithilfe einer Ising-Maschine (Fixstars Amplify Annealing Engine) optimiert, um Kandidatenlösungen zu finden.
- Evaluierung: Lösungen werden dekodiert, gegen die wahre Black-Box-Funktion evaluiert und für die nächste Iteration dem Trainingsdatensatz hinzugefügt.

Zentrale Beiträge

Framework-Vorschlag: Einführung eines FMQA-Frameworks, das die Wahl der Kodierung zwischen der Lern- und der Suchphase entkoppelt, anstatt eine einzige Kodierung während des gesamten Prozesses festzulegen.
Theoretische Herleitung: Herleitung der wechselseitigen Konvertierungsformeln zwischen One-Hot- und Domain-Wall-QUBO-Matrizen, welche die Zielfunktionslandschaft des Ersatzmodells über die zulässigen Zustände hinweg bewahren und somit den Wechsel der Kodierungen ermöglichen, ohne die Treue des gelernten Modells zu verlieren.
Empirische Dekomposition: Eine numerische Dekomposition der Effekte der Integer-Binär-Kodierung in Beiträge aus der Lernphase und der Lösungs-Suchphase, wobei diese separat evaluiert werden, um deren unterschiedliche Auswirkungen auf die Performance zu verstehen.

Experimentelle Ergebnisse
Die vorgeschlagene Methode wurde auf der Rastrigin-Funktion, einem multimodalen Benchmark-Problem, mit Eingabedimensionen $N \in \{2, 5\}$ und Diskretisierungsstufen $q \in \{61, 301\}$ evaluiert. Die Performance der vorgeschlagenen „OhDw“-Methode (One-Hot für das Lernen, Domain-Wall für die Suche) wurde mit konventionellen Single-Encoding-Varianten (Oh, Dw, Bi) und Bayesian Optimization (BO) verglichen.

Dominanz der Lernphasen-Kodierung: Über alle Bedingungen hinweg war die in der Lernphase verwendete Kodierung der dominierende Faktor, der die Optimierungsleistung steuerte. Methoden, die One-Hot-Kodierung für das Lernen verwendeten (Oh und OhDw), erzielten konsistent geringere Residuenfehler als jene, die Domain-Wall- oder Binär-Kodierung für das Lernen verwendeten.
Stufenabhängige Vorteile: Der Nutzen des Wechsels zur Domain-Wall-Kodierung für die Suchphase war zustandsabhängig:
- Für $N=5$ und $q=301$ (feinere Diskretisierung, größerer Suchraum) erreichte die OhDw-Methode geringere Residuenfehler und Lösungen, die näher am globalen Optimum lagen, als die Oh-Methode (nur One-Hot).
- Für $N=5$ und $q=61$ übertraf die Oh-Methode die OhDw-Methode leicht.
- Für $N=2$ wurde kein signifikanter Leistungsunterschied zwischen Oh und OhDw beobachtet.
Suchstabilität: Eine Analyse der Lösungs-Suchphase zeigte, dass die Domain-Wall-Kodierung stabilere Übergänge zwischen zulässigen Zuständen in der Ising-Maschine ermöglicht, während die One-Hot-Kodierung durch zustandsverletzende Zustände gehen muss, was die Suchstabilität potenziell reduziert.

Bedeutung und Behauptungen
Die Arbeit behauptet, dass die Wahl der Integer-Binär-Kodierung nicht bloß eine Repräsentationsentscheidung ist, sondern ein Gestaltungselement, das in der Lern- und der Suchphase der FMQA unterschiedliche Rollen erfüllt. Der primäre Befund ist, dass die One-Hot-Kodierung in der Lernphase der Haupttreiber der Optimierungsleistung ist, was wahrscheinlich auf ihre überlegene Fähigkeit zur Konstruktion eines genauen Ersatzmodells zurückzuführen ist. Dennoch zeigt die Studie, dass der Einsatz stufenabhängiger Kodierungen – speziell die Kombination von One-Hot für das Lernen mit Domain-Wall für die Suche – weitere Verbesserungen liefern kann, insbesondere in Szenarien mit größeren Eingabedimensionen und feinerer Diskretisierung, in denen der Suchraum komplexer ist.

Die Autoren kommen zu dem Schluss, dass die Vielseitigkeit der OhDw-Methode eine weitere Validierung auf einer breiteren Palette von Benchmark-Funktionen und realen Designoptimierungsproblemen erfordert. Zudem bleibt die systematische Analyse der Sensitivität gegenüber Strafterm-Koeffizienten und Unterschieden in der QUBO-Dichte eine Richtung für zukünftige Arbeiten.