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

Sintesi Tecnica: Codifica intero-binaria dipendente dallo stadio nell'ottimizzazione black-box di Factorization Machine

Definizione del Problema
L'ottimizzazione black-box (BBO) affronta problemi in cui le funzioni obiettivo mancano di forme analitiche esplicite e sono costose da valutare. Il Factorization Machine with Quadratic-optimization Annealing (FMQA) è un approccio BBO prominente che costruisce un modello surrogato utilizzando una Factorization Machine (FM) e lo ottimizza tramite una macchina Ising. Una componente critica di FMQA è la conversione di variabili intere o continue in variabili binarie tramite codifica intero-binaria (ad esempio, one-hot, domain-wall o binary encoding) per formulare il problema come un modello di Ottimizzazione Binaria Quadratica Non Vincolata (QUBO).

La FMQA convenzionale impiega un singolo metodo di codifica intero-binaria durante sia la fase di apprendimento automatico (costruzione del modello surrogato) che la fase di ricerca della soluzione (ottimizzazione della macchina Ising). Tuttavia, ricerche precedenti suggeriscono un compromesso: la codifica domain-wall spesso produce prestazioni di ricerca della soluzione superiori nelle macchine Ising, mentre la codifica one-hot è stata osservata produrre valori di funzione obiettivo inferiori nell'intero processo di ottimizzazione FMQA. Questa discrepanza implica che la codifica ottimale per l'apprendimento del paesaggio surrogato può differire da quella ottimale per la ricerca in tale paesaggio. I metodi convenzionali, fissando una singola codifica, possono non riuscire a sfruttare appieno le distinte capacità della FM e della macchina Ising.

Metodologia
Gli autori propongono un framework FMQA dipendente dallo stadio che utilizza diversi metodi di codifica intero-binaria per le fasi di apprendimento automatico e di ricerca della soluzione. Il nucleo di questo approccio prevede:

1. Strategia di Doppia Codifica: Il framework addestra il modello surrogato FM utilizzando una codifica adatta all'apprendimento (specificamente la codifica one-hot nella variante "OhDw" proposta) e successivamente converte il modello surrogato risultante in una codifica diversa adatta alla ricerca (specificamente la codifica domain-wall) prima dell'ottimizzazione da parte della macchina Ising.
2. Conversione della Matrice QUBO: Per consentire questo passaggio, gli autori hanno derivato formule di conversione matematica tra le matrici QUBO delle codifiche one-hot e domain-wall. Queste formule garantiscono che il paesaggio dell'obiettivo del surrogato sia preservato sugli stati interi ammissibili fino a una costante additiva.
   • La conversione da one-hot a domain-wall comporta la trasformazione dei termini diagonali e fuori diagonale della matrice QUBO $Q^{(oh)}$ in $Q^{(dw)}$ utilizzando specifiche relazioni di sommatoria (Eq. 18–20).
   • Anche la conversione inversa (domain-wall a one-hot) è derivata (Eq. 22–24).
   • La complessità computazionale per queste conversioni reciproche è stabilita come $O(N^2q^2)$, dove $N$ è la dimensione di input e $q$ è il numero di livelli di discretizzazione.
3. Workflow Algoritmico:
   • Fase di Apprendimento: Una FM viene addestrata su dati di input-output codificati tramite codifica one-hot.
   • Conversione: Il modello surrogato addestrato (rappresentato come una matrice QUBO) viene convertito dalla codifica one-hot alla codifica domain-wall.
   • Fase di Ricerca: Il QUBO convertito, aumentato con i vincoli di codifica domain-wall, viene ottimizzato utilizzando una macchina Ising (Fixstars Amplify Annealing Engine) per trovare soluzioni candidate.
   • Valutazione: Le soluzioni vengono decodificate, valutate rispetto alla vera funzione black-box e aggiunte al dataset di addestramento per l'iterazione successiva.

Contributi Chiave

1. Proposta di Framework: Introduzione di un framework FMQA che scinde la scelta della codifica tra le fasi di apprendimento e di ricerca della soluzione, invece di fissare una singola codifica durante tutto il processo.
2. Derivazione Teorica: Derivazione di formule di conversione reciproca tra le matrici QUBO one-hot e domain-wall che preservano il paesaggio dell'obiettivo del surrogato sugli stati ammissibili, consentendo il passaggio tra le codifiche senza perdere la fedeltà del modello appreso.
3. Decomposizione Empirica: Una decomposizione numerica degli effetti della codifica intero-binaria nelle contribuzioni della fase di apprendimento e della fase di ricerca della soluzione, valutandole separatamente per comprenderne i distinti impatti sulle prestazioni.

Risultati Sperimentali
Il metodo proposto è stato valutato sulla funzione di Rastrigin, un problema benchmark multimodale, con dimensioni di input $N \in \{2, 5\}$ e livelli di discretizzazione $q \in \{61, 301\}$. Le prestazioni del metodo "OhDw" proposto (one-hot per l'apprendimento, domain-wall per la ricerca) sono state confrontate con le varianti convenzionali a codifica singola (Oh, Dw, Bi) e con l'Ottimizzazione Bayesiana (BO).

• Dominanza della Codifica della Fase di Apprendimento: In tutte le condizioni, la codifica utilizzata nella fase di apprendimento è stata il fattore dominante nel governare le prestazioni di ottimizzazione. I metodi che impiegano la codifica one-hot per l'apprendimento (Oh e OhDw) hanno costantemente ottenuto errori residui inferiori rispetto a quelli che utilizzano la codifica domain-wall o binary per l'apprendimento.
• Benefici Dipendenti dallo Stadio: Il beneficio dello switch alla codifica domain-wall per la fase di ricerca è dipendente dalle condizioni:
  • Per $N=5$ e $q=301$ (discretizzazione più fine, spazio di ricerca più ampio), il metodo OhDw ha ottenuto errori residui inferiori e soluzioni più vicine all'ottimo globale rispetto al metodo Oh (solo one-hot).
  • Per $N=5$ e $q=61$, il metodo Oh ha leggermente superato l'OhDw.
  • Per $N=2$, non è stata osservata alcuna differenza significativa di prestazione tra Oh e OhDw.
• Stabilità della Ricerca: L'analisi della fase di ricerca della soluzione ha indicato che la codifica domain-wall consente transizioni più stabili tra stati ammissibili nella macchina Ising, mentre la codifica one-hot richiede il passaggio attraverso stati che violano i vincoli, riducendo potenzialmente la stabilità della ricerca.

Significatività e Rivendicazioni
L'articolo sostiene che la scelta della codifica intero-binaria non è meramente una scelta di rappresentazione, ma un elemento di design che serve ruoli distinti nelle fasi di apprendimento e di ricerca della soluzione di FMQA. Il risultato primario è che la codifica one-hot nella fase di apprendimento è il driver principale delle prestazioni di ottimizzazione, probabilmente a causa della sua superiore capacità di costruire un modello surrogato accurato. Tuttavia, lo studio dimostra che l'impiego di codifiche dipendenti dallo stadio — specificamente combinando la one-hot per l'apprendimento con la domain-wall per la ricerca — può fornire ulteriori miglioramenti, in particolare in scenari con dimensioni di input maggiori e discretizzazione più fine dove lo spazio di ricerca è più complesso.

Gli autori concludono che, sebbene il metodo OhDw mostri potenziale, la sua generalità richiede ulteriori validazioni su una più ampia varietà di funzioni benchmark e problemi di ottimizzazione del design del mondo reale. Inoltre, l'analisi sistematica della sensibilità ai coefficienti di penalità e alle differenze di densità QUBO rimane una direzione per il lavoro futuro.