Black-box optimization using factorization and Ising machines

Dieser Beitrag stellt den Algorithmus „Factorization Machine with Quantum Annealing" (FMQA) vor, der Faktorisierungsmaschinen als Ersatzmodelle und Ising-Maschinen nutzt, um großskalige Black-Box-Optimierungsprobleme in verschiedenen Bereichen effizient zu lösen, und gleichzeitig die erforderlichen Werkzeuge sowie Anwendungsbeispiele bereitstellt, um seine unmittelbare Übernahme zu erleichtern.

Das Wesentliche

Stellen Sie sich vor, Sie versuchen, das perfekte Rezept für einen Kuchen zu finden, aber Sie haben kein Kochbuch, keine Zutatenliste und keine Ahnung, wie der Ofen funktioniert. Sie können nur einen Kuchen backen, ihn probieren und eine Bewertung erhalten. Ist der Kuchen trocken, erhalten Sie eine niedrige Bewertung; ist er köstlich, erhalten Sie eine hohe Bewertung. Das ist es, was Wissenschaftler als Black-Box-Optimierung bezeichnen. Sie versuchen, den besten „Eingabewert" (Zutaten) zu finden, um den besten „Ausgabewert" (Geschmack) zu erzielen, doch die Maschine (der Ofen) ist ein Rätsel.

Das Problem besteht darin, dass es Milliarden möglicher Zutatenkombinationen gibt. Sie alle einzeln auszuprobieren, würde eine Ewigkeit dauern. Zu versuchen, die nächste beste Charge zu erraten, ist schwierig, da Sie die Regeln nicht kennen.

Diese Arbeit stellt eine clevere neue Methode vor, um dieses Rätsel mit zwei Hauptwerkzeugen zu lösen: einer Intelligenten Vermutungsmaschine (genannt Factorization Machine) und einer Superschnellen Suchmaschine (genannt Ising Machine).

So funktioniert es, Schritt für Schritt:

1. Die Intelligente Vermutungsmaschine (Der Surrogat)

Anstatt jedes Mal, wenn Sie ein Rezept testen möchten, einen echten Kuchen zu backen, bauen Sie einen „digitalen Zwilling" des Ofens. Sie backen ein paar Kuchen, notieren die Ergebnisse und bringen einem Computerprogramm (der Factorization Machine) bei, vorherzusagen, wie gut ein neues Rezept basierend auf den alten sein wird.

• Die Analogie: Denken Sie daran wie an einen Food-Kritiker, der 100 Kuchen probiert hat. Wenn Sie ihm sagen: „Ich verwende 2 Eier und 3 Tassen Zucker", kann er die Bewertung erraten, ohne dass Sie ihn tatsächlich backen müssen.
• Der Haken: Selbst mit einem klugen Kritiker ist es immer noch ein gewaltiges Puzzle, das absolut beste Rezept unter Milliarden von Optionen zu finden. Wenn die Zutaten diskret sind (wie „1 Ei hinzufügen" oder „2 Eier hinzufügen", nicht „1,5 Eier hinzufügen"), explodiert die Anzahl der Möglichkeiten.

2. Die Superschnelle Suchmaschine (Die Ising Machine)

Hier wird die Arbeit spannend. Die Autoren stellten fest, dass die „Intelligente Vermutungsmaschine" in eine Sprache übersetzt werden kann, die ein spezieller Computertyp, die Ising Machine, perfekt versteht.

• Die Analogie: Stellen Sie sich die Ising Machine als einen riesigen, superschnellen Labyrinth-Löser vor. Normalerweise werden diese Maschinen verwendet, um komplexe Rätsel zu lösen, wie etwa den kürzesten Weg für einen Lieferwagen zu finden oder Magnete anzuordnen.
• Der Zaubertrick: Die Autoren fanden einen Weg, das Vorhersageproblem der „Intelligenten Vermutungsmaschine" in ein Labyrinth zu verwandeln, das die Ising Machine im Handumdrehen lösen kann. Anstatt dass der Computer langsam rät und prüft, findet die Ising Machine sofort die Kombination von Zutaten, die der „Kluge Kritiker" für die beste hält.

3. Der „FMQA"-Algorithmus

Die Arbeit nennt diesen gesamten Prozess FMQA (Factorization Machine with Quadratic-optimization Annealing).

• Der Ablauf:
  1. Ein paar Kuchen backen (Daten sammeln).
  2. Den Klugen Kritiker trainieren (Factorization Machine).
  3. Die Superschnelle Suchmaschine (Ising Machine) bitten, das beste Rezept zu finden, das sich der Kritiker vorstellen kann.
  4. Dieses spezifische Rezept backen, um die echte Bewertung zu erhalten.
  5. Diese neue Bewertung dem Kritiker zurückgeben und wiederholen.

Warum ist das eine große Sache?

Normalerweise ist es unglaublich langsam, das beste Rezept in einer riesigen Liste zu finden. Die Arbeit zeigt, dass man durch diese spezifische Kombination aus einem „Kritiker" und einer „Superschnellen Suchmaschine" viel schneller zu guten Lösungen gelangt als zuvor, selbst wenn die Liste der Optionen riesig ist.

Reale Beispiele aus der Arbeit

Die Autoren sprachen nicht nur über Theorie; sie testeten dies an realen „Rezepten" in Wissenschaft und Technik:

• Entwicklung von Super-Materialien: Sie nutzten es, um „Metamaterialien" (künstliche Materialien mit speziellen Eigenschaften) zur Kühlung zu entwerfen. Sie mussten kleine Stäbe aus verschiedenen Materialien anordnen. Der Algorithmus fand ein Muster, das besser funktionierte als zufälliges Raten.
• Aufbau besserer Schichten: Sie entwickelten Schichten von Folien für Fenster, die Licht hereinlassen, aber Hitze blockieren. Der Algorithmus ermittelte die perfekte Reihenfolge der zu stapelnden Materialien.
• Reparatur von Ampeln: Sie behandelten Ampeln wie ein Puzzle. Das Ziel war es, Autos schneller durch eine Stadt zu bewegen. Der Algorithmus passte die Timing-Phasen von Rot- und Grünlichtern an, um einen Fluss zu finden, der viel flüssiger war als die Standardeinstellungen.
• Entwurf von Flugzeugflügeln: Sie veränderten die Form eines Flügels, um ihn effizienter fliegen zu lassen (mehr Auftrieb, weniger Widerstand).
• Entwicklung neuer Medikamente (Peptide): Sie entwarfen kurze Ketten von Proteinen (Peptide), die Bakterien abtöten, aber menschliche Zellen nicht schädigen würden. Das ist wie die Suche nach einer Nadel im Heuhaufen, doch der Algorithmus fand einige, die im Labor tatsächlich funktionierten.

Das Fazit

Die Arbeit behauptet, dass Wissenschaftler durch die Kombination einer bestimmten Art von KI (der Factorization Machine) mit spezialisierter Hardware (Ising Machines) „Black-Box"-Probleme viel schneller lösen können. Es ist, als würde man einem Detektiv eine supermächtige Lupe geben, die sofort die vielversprechendsten Hinweise hervorhebt und es ihm ermöglicht, Verbrechen (oder Materialien zu entwickeln) zu lösen, die zuvor zu komplex waren, um sie zu knacken.

Die Autoren haben sogar kostenlose Software-Tools veröffentlicht, damit andere Wissenschaftler diese Kombination aus „Kluge Kritiker + Superschnelle Suchmaschine" nutzen können, um ihre eigenen schwierigen Rätsel zu lösen.

Technische Zusammenfassung

1. Problemstellung

Black-Box-Optimierung (BBO) ist eine kritische Herausforderung in Bereichen von der Materialentwicklung und Wirkstoffentdeckung bis hin zur Hyperparameter-Optimierung im maschinellen Lernen. Bei der BBO ist die Zielfunktion $y(x)$ eine „Black Box", bei der die innere Funktionsform und die Gradienten unbekannt sind; es stehen nur Eingabe-Ausgabe-Paare zur Verfügung.

• Die Herausforderung: Herkömmliche BBO-Methoden, wie die Bayessche Optimierung (BO), verlassen sich auf Surrogatmodelle (z. B. Gauß-Prozesse), um optimale Eingaben vorherzusagen. Die Optimierung der Akquisitionsfunktion (das Kriterium zur Auswahl der nächsten Eingabe) wird jedoch rechnerisch unlösbar, wenn der Eingaberaum diskret, hochdimensional oder kombinatorisch ist.
• Der Engpass: Mit zunehmender Anzahl der Kandidateneingaben ist eine erschöpfende Suche unmöglich (NP-schwer), und gradientenbasierte Methoden versagen bei diskreten Variablen. Bestehende Methoden haben Schwierigkeiten, große, diskrete Suchräume effizient zu erkunden, um globale Optima zu finden.

2. Methodik: Der FMQA-Algorithmus

Das Papier schlägt den FMQA-Algorithmus (Factorization Machine with Quadratic-optimization Annealing) vor. Dieser Ansatz kombiniert ein spezifisches Surrogatmodell des maschinellen Lernens mit Ising-Maschinen (IMs), um die Optimierung der Akquisitionsfunktion effizient zu lösen.

A. Surrogatmodell: Factorization Machine (FM)

Anstelle von Gauß-Prozessen verwendet FMQA eine Factorization Machine (FM) als Surrogatmodell.

• Struktur: Die FM modelliert die Ausgabe $\bar{y}(x)$ als linearen Term plus einen Term für paarweise Wechselwirkungen:
  $$\bar{y}(x) = w_0 + \sum w_i x_i + \sum \sum \langle v_i, v_j \rangle x_i x_j$$
• Vorteil: Die FM kann direkt in ein Quadratic Unconstrained Binary Optimization (QUBO)-Modell (oder Ising-Hamiltonian) transformiert werden. Dies ermöglicht es, das Surrogatmodell selbst als Optimierungsproblem unter Verwendung von IMs zu lösen.
• Training: FMs werden effizient mittels Gradientenabstieg mit linearer Komplexität $O(NK)$ trainiert, wobei $N$ die Anzahl der Merkmale und $K$ die latente Dimension ist.

B. Optimierungsmotor: Ising-Maschinen (IMs)

Die Kerninnovation besteht darin, IMs zu verwenden, um die Eingabe $x$ zu finden, die die Akquisitionsfunktion (oder die negative Vorhersage) der FM maximiert.

• Hardware/Software: Der Algorithmus ist unabhängig von der spezifisch verwendeten IM. Er unterstützt:
  • Quanten-Annealer: z. B. D-Wave-Systeme.
  • Digitale Annealer: z. B. Fujitsu Digital Annealer.
  • Simulierte Annealing-Engines: z. B. Fixstars Amplify Annealing Engine (GPU-basiert).
• Prozess: Die FM wird in QUBO umgewandelt → Von der IM gelöst, um den optimalen binären Vektor zu finden → Zurück in den ursprünglichen Eingaberaum decodiert.

C. Umgang mit nicht-binären Eingaben (Codierungsstrategien)

Da IMs mit binären Variablen arbeiten, beschreibt das Papier Codierungsmethoden für allgemeine Optimierungsprobleme:

1. Binäre Variablen: Direkte Abbildung (keine Codierung erforderlich).
2. Ganzzahlige Variablen:
   • Binäre Codierung: Stellt Ganzzahlen als Summen von Potenzen von 2 dar.
   • One-Hot-Codierung: Stellt Ganzzahlen als eine einzelne '1' unter $N$ Bits dar (erfordert eine Nebenbedingung $\sum x_i = 1$).
   • Domain-Wall-Codierung: Eine effizientere Codierung für Ganzzahlen, die die Bitanzahl im Vergleich zu One-Hot reduziert.
3. Komplexe Strukturen (Graphen, Strings, Bilder):
   • Verwendung eines Binary Variational Autoencoder (bVAE).
   • Der bVAE codiert komplexe Eingaben (z. B. molekulare SMILES-Strings, Bilder) in einen latenten Raum binärer Variablen.
   • Die FM wird auf diesem latenten Raum trainiert. Die IM optimiert den latenten binären Vektor, der dann zurück in die ursprüngliche Struktur decodiert wird.

3. Hauptbeiträge

1. Algorithmisches Framework: Formalisierung des FMQA-Algorithmus, der demonstriert, wie BBO über das QUBO-kompatible FM-Surrogat mit kombinatorischer Optimierungshardware (IMs) verbunden wird.
2. Skalierbarkeit: Nachweis, dass FMQA großskalige diskrete Optimierungsprobleme (bis zu Tausende von Bits) bewältigen kann, bei denen die traditionelle BO aufgrund der Schwierigkeit der Optimierung der Akquisitionsfunktion versagt.
3. Software-Ökosystem: Einführung von Open-Source-Tools zur Demokratisierung der Technologie:
   • Original FMQA Package: Eine Python-Bibliothek für die grundlegende Implementierung.
   • Amplify-BBOpt: Eine spezialisierte Bibliothek, die in das Fixstars Amplify SDK integriert ist und es Benutzern ermöglicht, kontinuierliche Variablen und Nebenbedingungen (z. B. One-Hot) ohne manuelle QUBO-Formulierung zu definieren.
4. Umfassende Benchmarking: Validierung des Ansatzes über diverse Domänen hinweg, was seine Vielseitigkeit über einfache binäre Probleme hinaus beweist.

4. Ergebnisse und Anwendungsbeispiele

Das Papier überprüft erfolgreiche Anwendungen in Physik, Chemie, Materialwissenschaft und Sozialwissenschaften:

• Binäre Optimierung (ohne Nebenbedingungen):

  • Metamaterial-Design: Optimierung von Strahlungskühlungsstrukturen (24–60 Bits) mit D-Wave 2000Q, wobei überlegene Strukturen schneller als bei der zufälligen Suche gefunden wurden.
  • Schichtmaterialien: Entwicklung von hochleistungsfähigen transparenten Strahlungskühlungsfolien (bis zu 48 Bits) und breitwinkligen Spektralfiltern; erfolgreiche Herstellung eines 10-Schicht-Materials mit Rekordleistung.
  • Polymerdesign: Optimierung von Triblockpolymeren für die Wärmeleitfähigkeit.
  • Merkmalsauswahl: Auswahl optimaler Merkmalsuntergruppen zur Vorhersage mechanischer Eigenschaften von Polymeren, wobei LASSO übertroffen wurde.

• Binäre Optimierung (mit Nebenbedingungen):

  • Magnetische Tunnelkontakte (MTJ): Optimierung atomarer Anordnungen mit einer strengen Nebenbedingung zur Anzahl spezifischer Ionen (z. B. genau 5 Mg und 5 Ge) unter Verwendung von Straftermen im QUBO.
  • Molekulare Konfiguration: Optimierung atomarer Konfigurationen in Perylenmolekülen für die Polarisierbarkeit.
  • Resonanzvermeidung: Optimierung der Positionen von Befestigungslöchern auf Leiterplatten zur Maximierung der Eigenfrequenz.

• Probleme mit ganzzahligen Variablen:

  • Photonische Kristall-Laser: Optimierung kontinuierlicher Strukturparameter (diskretisiert auf 44 Bits) für Ausgangsleistung und Strahlqualität, wobei Partikel-Schwarm-Optimierung (PSO) und Genetische Algorithmen (GA) übertroffen wurden.
  • Flügelprofil-Optimierung: Optimierung von Profilformen (100 Bits) zur Maximierung des Auftriebs-Widerstands-Verhältnisses, was eine Verbesserung von 17 % gegenüber der zufälligen Suche erzielte.
  • Verkehrslichtsteuerung: Optimierung von 960 binären Variablen (repräsentierend 16 Kreuzungen) zur Maximierung der durchschnittlichen Fahrzeuggeschwindigkeit in einer Stadtsimulation.
  • Fahrzeugkarosserie-Design: Lösung eines Multi-Objective-Benchmarks für Fahrzeugstrukturen mit 18 Nebenbedingungen, wobei mit weniger Funktionsauswertungen (900 vs. 30.000) bessere Pareto-Lösungen als mit NSGA-II erreicht wurden.

• Komplexe Strukturen (bVAE):

  • Thermische Emitter: Optimierung von 2D-topologischen Formen für Thermophotovoltaik unter Verwendung eines 500-Bit-latenten Raums.
  • Molekulares Design: Optimierung von wirkstoffähnlichen Molekülen (SMILES-Strings) für mehrere Eigenschaften (LogP, QED usw.) unter Verwendung eines 300-Bit-latenten Raums.
  • Peptid-Design: Durchführung einer Multi-Objective-Optimierung für antimikrobielle und nicht-hämolytische Peptide; erfolgreiche Synthese und Validierung zweier neuartiger Peptide.

5. Bedeutung und Ausblick

• Schlüsseltechnologie für IMs: Das Papier positioniert FMQA als „Killer-Applikation" für Ising-Maschinen und bietet einen praktischen, durchgängigen Workflow zur Lösung realer BBO-Probleme, die zuvor unlösbar waren.
• Geschwindigkeit und Effizienz: Durch die Auslagerung der Akquisitionsfunktions-Optimierung auf spezialisierte Hardware (IMs) reduziert FMQA die Rechenzeit erheblich, die zur Findung globaler Optima in diskreten Räumen erforderlich ist.
• Zukünftige Richtungen:
  • Quantenvorteil: Obwohl derzeit Quanten-Annealer und digitale Annealer verwendet werden, ist das Framework für gate-basierte Quantencomputer (unter Verwendung von QAOA) bereit, sobald die Qubit-Anzahl steigt.
  • Selbstfahrende Labore: Die Autoren schlagen vor, FMQA in automatisierte experimentelle Systeme zu integrieren, um die Materialentdeckung und Wirkstoffentwicklung zu beschleunigen.
  • Skalierbarkeit: Zukünftige Arbeiten zielen darauf ab, größere Batch-Größen zu bewältigen und höherordentliche Surrogatmodelle (HUBO) zu entwickeln, um die Vorhersagegenauigkeit und IM-Leistung weiter zu verbessern.

Zusammenfassend etabliert das Papier FMQA als ein robustes, vielseitiges und hocheffizientes Framework für die Black-Box-Optimierung, das die Lücke zwischen Surrogatmodellierung im maschinellen Lernen und kombinatorischer Optimierungshardware effektiv überbrückt.