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

Technische Samenvatting: Faseafhankelijke integer-binair codering in factorization-machine black-box optimalisatie

Probleemstelling
Black-box optimalisatie (BBO) behandelt problemen waarbij de objectieve functies geen expliciete analytische vormen hebben en kostbaar zijn om te evalueren. Factorization Machine with Quadratic-optimization Annealing (FMQA) is een prominente BBO-benadering die een surrogaatmodel construeert met behulp van een Factorization Machine (FM) en dit model optimaliseert met behulp van een Ising-machine. Een cruciaal onderdeel van FMQA is de conversie van integer- of continue variabelen naar binaire variabelen via integer-binair codering (bijv. one-hot, domain-wall of binaire codering) om het probleem te formuleren als een Quadratic Unconstrained Binary Optimization (QUBO) model.

Conventionele FMQA gebruikt één enkele integer-binaire coderingsmethode gedurende zowel de machine learning-fase (constructie van het surrogaatmodel) als de oplossingzoekfase (optimalisatie door de Ising-machine). Echter, eerder onderzoek suggereert een afruil: domain-wall codering levert vaak superieure prestaties bij het zoeken naar oplossingen in Ising-machines, terwijl one-hot codering is waargenomen om lagere objectieve functiewaarden te produceren in het algehele FMQA-optimalisatieproces. Dit verschil impliceert dat de codering die optimaal is voor het leren van het surrogaatlandschap, kan verschillen van de codering die optimaal is voor het doorzoeken van dat landschap. Conventionele methoden, door één enkele codering vast te leggen, kunnen er niet in slagen de onderscheidende capaciteiten van de FM en de Ising-machine volledig uit te buiten.

Methodologie
De auteurs stellen een faseafhankelijke FMQA-framework voor die verschillende integer-binaire coderingsmethoden gebruikt voor de machine learning- en de oplossingzoekfase. De kern van deze aanpak omvat:

1. Dual-Encoding Strategie: Het framework traint het FM-surrogaatmodel met behulp van een codering die geschikt is voor leren (specifiek one-hot codering in de voorgestelde "OhDw"-variant) en converteert vervolgens het resulterende surrogaatmodel naar een andere codering die geschikt is voor zoeken (specifiek domain-wall codering) vóór optimalisatie door de Ising-machine.
2. QUBO Matrix Conversie: Om deze wisseling mogelijk te maken, hebben de auteurs wiskundige conversieformules afgeleid tussen de QUBO-matrices van one-hot en domain-wall coderingen. Deze formules zorgen ervoor dat het surrogaat-objectievevenement behouden blijft over haalbare integer-toestanden tot een additieve constante.
   • De conversie van one-hot naar domain-wall omvat het transformeren van diagonaal- en off-diagonaaltermen van de QUBO-matrix $Q^{(oh)}$ naar $Q^{(dw)}$ met behulp van specifieke sommatierelaties (Gelijkheden 18–20).
   • De inverse conversie (domain-wall naar one-hot) is eveneens afgeleid (Gelijkheden 22–24).
   • De computationele complexiteit voor deze wederzijdse conversies is vastgesteld op $O(N^2q^2)$, waarbij $N$ de invoerdimensie is en $q$ het aantal discretisatieniveaus.
3. Algoritmische Workflow:
   • Leerfase: Een FM wordt getraind op input-output data gecodeerd met one-hot codering.
   • Conversie: Het getrainde surrogaatmodel (gerepresenteerd als een QUBO-matrix) wordt geconverteerd van one-hot naar domain-wall codering.
   • Zoekfase: De geconverteerde QUBO, aangevuld met domain-wall codering-beperkingen, wordt geoptimaliseerd met behulp van een Ising-machine (Fixstars Amplify Annealing Engine) om kandidaat-oplossingen te vinden.
   • Evaluatie: Oplossingen worden gedecodeerd, geëvalueerd tegen de ware black-box functie en toegevoegd aan de trainingsdataset voor de volgende iteratie.

Belangrijkste Bijdragen

1. Framework Voorstel: Introductie van een FMQA-framework dat de keuze van codering ontkoppelt tussen de leer- en de zoekfase, in plaats van één enkele codering gedurende het hele proces vast te leggen.
2. Theoretische Afleiding: Afleiding van wederzijdse conversieformules tussen one-hot en domain-wall QUBO-matrices die het surrogaat-objectieveven behouden over haalbare toestanden, waardoor het wisselen van coderingen mogelijk is zonder de getrouwheid van het geleerde model te verliezen.
3. Empirische Decompositie: Een numerieke decompositie van de effecten van integer-binair codering in bijdragen van de leerfase en de oplossingzoekfase, waarbij ze afzonderlijk worden geëvalueerd om hun onderscheidende impact op de prestaties te begrijpen.

Experimentele Resultaten
De voorgestelde methode werd geëvalueerd op de Rastrigin-functie, een multimodale benchmarkprobleem, met invoerdimensies $N \in \{2, 5\}$ en discretisatieniveaus $q \in \{61, 301\}$. De prestaties van de voorgestelde "OhDw"-methode (one-hot voor leren, domain-wall voor zoeken) werden vergeleken met conventionele single-encoding varianten (Oh, Dw, Bi) en Bayesiaanse Optimalisatie (BO).

• Dominantie van de Leerfase-Codering: In alle condities was de codering die in de leerfase werd gebruikt de dominante factor die de optimalisatieprestaties bepaalde. Methoden die one-hot codering gebruikten voor het leren (Oh en OhDw) bereikten consistent lagere residuele fouten dan die welke domain-wall of binaire codering gebruikten voor het leren.
• Faseafhankelijke Voordelen: Het voordeel van het overschakelen naar domain-wall codering voor de zoekfase was conditieafhankelijk:
  • Voor $N=5$ en $q=301$ (fijnere discretisatie, grotere zoekruimte), bereikte de OhDw-methode lagere residuele fouten en oplossingen dichter bij het globale optimum vergeleken met de Oh-methode (alleen one-hot).
  • Voor $N=5$ en $q=61$ presteerde de Oh-methode iets beter dan OhDw.
  • Voor $N=2$ werd geen significant prestatieverschil waargenomen tussen Oh en OhDw.
• Zoekstabiliteit: Een analyse van de oplossingzoekfase gaf aan dat domain-wall codering meer stabiele transities tussen haalbare toestanden toestaat in de Ising-machine, terwijl one-hot codering door toestanden moet gaan die de beperkingen schenden, wat de zoekstabiliteit potentieel vermindert.

Betekenis en Claims
Het artikel beweert dat de keuze van integer-binair codering niet louter een representatieve keuze is, maar een ontwerpelement dat verschillende rollen dient in de leer- en de oplossingzoekfasen van FMQA. De primaire bevinding is dat one-hot codering in de leerfase de belangrijkste drijfveer is voor de optimalisatieprestaties, waarschijnlijk vanwege de superieure bekwaamheid om een accuraat surrogaatmodel te construeren. Echter, de studie demonstreert dat het gebruik van faseafhankelijke coderingen — specifiek de combinatie van one-hot voor leren met domain-wall voor zoeken — verdere verbeteringen kan bieden, met name in scenario's met grotere invoerdimensies en fijnere discretisatie waar de zoekruimte complexer is.

De auteurs concluderen dat hoewel de OhDw-methode veelbelovend is, de algemeenheid ervan verdere validatie vereist op een breder scala aan benchmarkfuncties en real-world design optimalisatieproblemen. Daarnaast blijft de systematische analyse van de gevoeligheid voor penalty-coëfficiënten en verschillen in QUBO-dichtheid een richting voor toekomstig werk.