Performance-Driven QUBO for Recommender Systems on Quantum Annealers

1. Enunciato del Problema

I sistemi di raccomandazione soffrono spesso della "maledizione della dimensionalità" a causa dell'ampio numero di caratteristiche degli elementi, portando a ridondanza, costi di archiviazione aumentati e ridotta efficienza di recupero. Sebbene la selezione delle caratteristiche sia fondamentale, i metodi tradizionali spesso non riescono a ottimizzare esplicitamente le prestazioni finali della raccomandazione (ad esempio, metriche di ranking come nDCG).

Gli approcci esistenti di Ricottura Quantistica (QA) per la selezione delle caratteristiche, che formulano il problema come Ottimizzazione Binaria Quadratica Senza Vincoli (QUBO), affrontano due limitazioni principali:

1. Obiettivi non allineati: I metodi basati su QUBO attuali (ad esempio, MIQUBO, CoQUBO) costruiscono la matrice dei coefficienti $Q$ basandosi su dipendenze statistiche (informazione reciproca, correlazione) o output del modello, piuttosto che sull'impatto diretto sulla metrica di prestazione della raccomandazione.
2. Instabilità: Le prestazioni dei ricottori quantistici sull'hardware reale (era NISQ) sono sensibili alla dimensione del problema, al numero di campioni e alla difficoltà del problema, portando a risultati incoerenti.

Gli autori pongono tre domande di ricerca chiave:

• Come influisce l'instabilità dei ricottori quantistici sulle prestazioni dei sistemi di raccomandazione?
• Quanto sono efficaci i ricottori quantistici per la selezione delle caratteristiche in questo dominio?
• I metodi basati su QUBO sull'hardware quantistico possono eguagliare o superare i baseline di selezione delle caratteristiche classici?

2. Metodologia: PDQUBO

Gli autori propongono PDQUBO (Ottimizzazione Binaria Quadratica Senza Vincoli Guidata dalle Prestazioni), un nuovo framework che allinea l'obiettivo di ottimizzazione QUBO direttamente alle prestazioni di raccomandazione a valle utilizzando analisi controfattuale.

Flusso di Lavoro Principale

1. Addestramento del Modello Base: Un modello di raccomandazione ($G_\Theta$) viene addestrato sull'insieme completo di caratteristiche $F$.
2. Analisi Controfattuale: Il metodo valuta l'impatto delle caratteristiche creando "istanze controfattuali". Maschera sistematicamente (rimuove) singole caratteristiche ($f_i$) e coppie di caratteristiche ($f_i, f_j$) dall'input e misura la variazione della metrica di valutazione (ad esempio, nDCG).
   • $E_i$: Calo delle prestazioni quando $f_i$ viene rimossa.
   • $E_{ij}$: Calo delle prestazioni quando entrambe $f_i$ e $f_j$ vengono rimosse.
   • Nota: Un $E$ positivo indica che la caratteristica è importante (le prestazioni calano quando viene rimossa); un $E$ negativo suggerisce che la caratteristica è ridondante o dannosa.
3. Formulazione QUBO: I valori controfattuali sono utilizzati per costruire la matrice dei coefficienti QUBO $Q$:
   • Elementi diagonali ($Q_{ii}$): Impostati su $-E_i$ (rappresentando l'importanza individuale della caratteristica).
   • Elementi fuori diagonale ($Q_{ij}$): Impostati su $-E_{ij}$ (rappresentando le interazioni a coppie delle caratteristiche).
   • La funzione obiettivo minimizza l'energia $Y = x^T Q x$, dove $x$ è un vettore binario che indica la selezione delle caratteristiche. Minimizzare $Y$ corrisponde a selezionare le caratteristiche che massimizzano le prestazioni della raccomandazione.
4. Ottimizzazione: Il problema QUBO costruito viene risolto utilizzando sia solver classici (Ricottura Simulata, Ricerca Tabù) sia Ricottori Quantistici (D-Wave).
5. Riaddestramento: Il sottoinsieme di caratteristiche selezionato viene utilizzato per riaddestrare il modello base per la valutazione finale.

Distinzioni Chiave

• Modello-Agnostico: PDQUBO funziona con qualsiasi modello base (KNN, MLP, NCF) e qualsiasi metrica.
• Consapevole delle Interazioni: A differenza dei metodi "filter" che trattano le caratteristiche in modo indipendente, PDQUBO modella esplicitamente le interazioni a coppie tramite i termini quadratici in $Q$.

3. Contributi Chiave

1. Framework PDQUBO: Una nuova formulazione QUBO che collega esplicitamente la selezione delle caratteristiche alle prestazioni della raccomandazione tramite analisi controfattuale, assicurando che la direzione di ottimizzazione sia guidata dalle prestazioni e non dalle statistiche.
2. Analisi Completa della Stabilità: Un'indagine dettagliata sull'instabilità dei ricottori quantistici reali, analizzando come la qualità della soluzione varia in base a:
   • Dimensione del problema (numero di caratteristiche).
   • Dimensione del campione (numero di esecuzioni di ricottura).
   • Difficoltà del problema (sparsità dei dati).
3. Validazione Empirica: Esperimenti estensivi su dataset reali (dataset CLEF 2024 QuantumCLEF, KuaiRec, KuaiRand, Avazu, Criteo) che dimostrano che PDQUBO supera i baseline QUBO esistenti e compete con i metodi di selezione delle caratteristiche classici all'avanguardia.
4. Insights sulla Scalabilità: Analisi del costo computazionale e proposta di una strategia di potatura a due stadi per mitigare la complessità $O(|F|^2)$ della costruzione della matrice QUBO completa, sebbene il documento concluda che la formulazione quadratica completa sia necessaria per prestazioni ottimali.

4. Risultati Sperimentali

Gli autori hanno valutato PDQUBO rispetto ai baseline (CQFS, MIQUBO, CoQUBO, QUBO-Boosting) e ai metodi classici (Lasso, GBDT, Importanza per Permutazione) su vari dataset e modelli.

• Prestazioni vs Baseline:

  • PDQUBO ha costantemente ottenuto i punteggi migliori o secondi migliori nDCG@10 nella maggior parte delle configurazioni sui dataset 150_ICM e 500_ICM.
  • Nei task di previsione CTR (Avazu, Criteo), PDQUBO-Hybrid (utilizzando un solver ibrido quantistico-classico) ha ottenuto i punteggi AUC più alti, superando sia i baseline classici che le altre varianti QUBO.
  • PDQUBO ha superato significativamente altri metodi QUBO (come MIQUBO), dimostrando che la costruzione guidata dalle prestazioni è superiore alla costruzione basata su dipendenze statistiche.

• Risultati sulla Stabilità:

  • Dimensione del Problema: I risultati della Ricottura Quantistica (QA) diventano instabili quando il numero di caratteristiche supera la capacità di qubit logici dell'hardware, mentre i solver classici (SA, TS) rimangono stabili.
  • Dimensione del Campione: Aumentare il numero di campioni QA riduce significativamente la varianza dell'energia e migliora le prestazioni a valle, evidenziando la necessità di un campionamento sufficiente nei dispositivi NISQ.
  • Difficoltà: QA tende a mostrare guadagni di prestazioni maggiori ma più volatili su dataset sparsi (difficili).

• Necessità dei Termini Quadratici:

  • Esperimenti che confrontano "Indiv" (solo diagonale) con "All" (matrice completa) hanno mostrato che includere le interazioni a coppie ($Q_{ij}$) è cruciale. L'approccio "All" ha prodotto risultati significativamente migliori, confermando che le interazioni tra caratteristiche sono vitali per una selezione efficace in questo contesto.

• Efficienza:

  • Mentre la complessità temporale dei solver classici cresce esponenzialmente con la dimensione del problema, il tempo di ricottura quantistica rimane relativamente costante (limitato dall'accesso all'hardware e dal tempo di campionamento), offrendo un potenziale vantaggio di velocità per problemi su larga scala una volta superati i vincoli hardware.

5. Significato e Direzioni Future

• Colmare il Divario: Questo lavoro colma con successo il divario tra l'ottimizzazione quantistica teorica e il dispiegamento pratico dei sistemi di raccomandazione assicurando che l'obiettivo di ottimizzazione miri direttamente alla metrica aziendale (qualità della raccomandazione).
• Fattibilità Pratica: I risultati suggeriscono che, anche con le attuali limitazioni hardware NISQ, gli approcci ibridi quantistico-classici possono fornire una selezione delle caratteristiche competitiva o superiore rispetto ai metodi classici maturi.
• Lavori Futuri: Gli autori suggeriscono di estendere PDQUBO per modellare interazioni di ordine superiore delle caratteristiche (oltre le coppie) e di esplorare algoritmi quantistici variazionali su computer quantistici basati su gate per gestire strutture di caratteristiche su larga scala e più complesse.

In conclusione, PDQUBO rappresenta un passo significativo in avanti nell'applicazione del calcolo quantistico alle sfide reali della raccomandazione, dimostrando che formulazioni QUBO guidate dalle prestazioni e basate su controfattuali possono sfruttare efficacemente i ricottori quantistici per una selezione delle caratteristiche di alta qualità.