🤖 AI

Performance-Driven QUBO for Recommender Systems on Quantum Annealers

Cet article présente PDQUBO, une méthode de sélection de caractéristiques QUBO agnostique du modèle et axée sur la performance pour les systèmes de recommandation, qui exploite l'analyse contrefactuelle pour aligner les objectifs du recuit quantique sur la qualité des recommandations, démontrant une performance supérieure aux bases de référence quantiques et classiques antérieures sur des ensembles de données réels.

Auteurs originaux : Jiayang Niu, Jie Li, Ke Deng, Mark Sanderson, Nicola Ferro, Yongli Ren

Publié 2026-05-01

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Jiayang Niu, Jie Li, Ke Deng, Mark Sanderson, Nicola Ferro, Yongli Ren

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

La Vue d'Ensemble : Choisir les Meilleurs Ingrédients

Imaginez que vous êtes un chef dirigeant un restaurant (un Système de Recommandation). Vous possédez une immense garde-manger remplie de 500 épices et ingrédients différents (ce sont les caractéristiques). Vous voulez préparer le meilleur plat possible pour vos clients, mais utiliser tous les 500 ingrédients à la fois est désordonné, coûteux et rend en réalité le goût du plat moins bon car certains ingrédients entrent en conflit.

Vous devez sélectionner le sous-ensemble parfait, disons 140 ingrédients, qui rendront le plat délicieux. C'est ce qu'on appelle la Sélection de Caractéristiques.

Le problème est que déterminer quels 140 ingrédients fonctionnent le mieux ensemble est incroyablement difficile. C'est comme essayer de trouver la combinaison parfaite de clés pour ouvrir une serrure alors qu'il existe des milliards de possibilités.

Le Nouvel Outil : Un « Dégustateur » Quantique

Les auteurs de ce document, Jiayang Niu et son équipe, ont créé une nouvelle méthode appelée PDQUBO. Ils utilisent un type spécial de superordinateur appelé Recuit Quantique pour résoudre ce problème.

Imaginez un Recuit Quantique comme un « dégustateur » magique et ultra-rapide capable d'essayer des millions de combinaisons d'ingrédients en un clin d'œil pour trouver celle qui a le meilleur goût. Cependant, pour faire fonctionner cette magie, vous devez fournir au dégustateur un ensemble d'instructions très spécifique (un problème mathématique appelé QUBO).

Le Problème avec les Anciennes Méthodes

Avant ce document, d'autres chercheurs ont essayé de donner des instructions à ces ordinateurs quantiques, mais ils étaient un peu confus.

Ancienne Méthode : Ils disaient à l'ordinateur quantique : « Choisissez des ingrédients statistiquement similaires entre eux » ou « Choisissez des ingrédients qui correspondent aux étiquettes de la recette ».
Le Défaut : Le fait que deux ingrédients semblent similaires sur le papier ne signifie pas qu'ils goûtent bien ensemble dans le plat final. Les anciennes méthodes optimisaient la mauvaise chose (comme compter combien d'épices rouges vous avez) au lieu de la bonne chose (la qualité du goût du plat).

La Solution PDQUBO : Analyse « Et Si ? »

La grande idée de l'équipe est Pilotée par la Performance. Au lieu de deviner, ils utilisent une technique appelée Analyse Contrefactuelle.

Imaginez que vous avez un plat parfait.

Le Test : Vous retirez une épice (disons le paprika) et servez à nouveau le plat. Est-ce qu'il a moins bon goût ? Si oui, le paprika est important.
Le Double Test : Vous retirez deux épices à la fois (paprika et cumin). Est-ce que le plat a goûté beaucoup moins bien que si vous n'aviez retiré qu'une seule épice ? Si oui, ces deux épices ont une « chimie » ou un partenariat spécial qui est crucial.

PDQUBO fait cela pour chaque ingrédient individuel et chaque paire possible d'ingrédients. Il mesure exactement combien le « plat » (la qualité de la recommandation) souffre lorsqu'un ingrédient manque. Il alimente ensuite ces données de « perte de goût » dans l'ordinateur quantique.

Le Résultat : L'ordinateur quantique ne cherche pas simplement des motifs aléatoires ; il reçoit explicitement l'instruction : « Trouvez la combinaison d'ingrédients qui cause la moindre perte de goût ». Cela aligne directement les mathématiques sur l'objectif : faire de meilleures recommandations.

Ce qu'ils ont Découvert (Les Résultats)

L'équipe a testé cela sur des données réelles (comme les notes de films et les habitudes d'achat) en utilisant différents types de « chefs » (algorithmes).

Meilleur Goût : PDQUBO a constamment fait de meilleures recommandations que les anciennes méthodes quantiques. C'était comme si le nouveau chef savait exactement quelles épices garder, tandis que les anciens chefs devinaient simplement en se basant sur la couleur ou la forme.
La Machine Quantique « Tremblante » : Ils ont découvert que les ordinateurs quantiques actuels sont un peu instables, comme une main tremblante. Si le problème est trop grand ou trop difficile, la machine donne parfois une réponse légèrement différente à chaque fois que vous lui posez la question. Cependant, PDQUBO était suffisamment robuste pour gérer cette « instabilité » et trouver quand même de bonnes solutions.
Vitesse : La méthode quantique était incroyablement rapide pour résoudre la partie mathématique, beaucoup plus rapide que les ordinateurs traditionnels, bien que la mise en place du « test de goût » (la préparation des données) prenne encore du temps sur des ordinateurs classiques.
Les Partenariats Comptent : Ils ont prouvé que regarder les ingrédients par paires (vérifier si le paprika et le cumin fonctionnent bien ensemble) est essentiel. Si vous ne regardez les ingrédients que un par un, vous manquez la magie de leur interaction.

La Conclusion

Ce document montre qu'en utilisant une approche « Et Si ? » pour mesurer exactement combien une recommandation souffre lorsqu'une caractéristique est retirée, nous pouvons apprendre aux ordinateurs quantiques à choisir les meilleures caractéristiques pour nous. C'est un pas vers l'utilisation de ces machines futuristes pour rendre nos suggestions Netflix, Spotify et Amazon nettement meilleures, plus rapides et plus précises.

En bref : Ils ont appris à un ordinateur quantique à arrêter de deviner et à commencer à goûter, garantissant que la recommandation finale est la meilleure possible.

1. Énoncé du problème

Les systèmes de recommandation souffrent souvent de la « malédiction de la dimensionnalité » en raison du grand nombre de caractéristiques d'articles, ce qui entraîne une redondance, une augmentation des coûts de stockage et une réduction de l'efficacité de la récupération. Bien que la sélection de caractéristiques soit cruciale, les méthodes traditionnelles échouent souvent à optimiser explicitement la performance finale de la recommandation (par exemple, les métriques de classement comme le nDCG).

Les approches existantes d'optimisation par recuit quantique (QA) pour la sélection de caractéristiques, qui formulent le problème comme une optimisation binaire quadratique sans contrainte (QUBO), présentent deux limitations principales :

Objectifs non alignés : Les méthodes actuelles basées sur QUBO (par exemple, MIQUBO, CoQUBO) construisent la matrice de coefficients $Q$ en fonction des dépendances statistiques (information mutuelle, corrélation) ou des sorties du modèle, plutôt que de l'impact direct sur la métrique de performance de recommandation.
Instabilité : La performance des recuits quantiques sur du matériel réel (ère NISQ) est sensible à la taille du problème, au nombre d'échantillons et à la difficulté du problème, ce qui conduit à des résultats inconstants.

Les auteurs posent trois questions de recherche clés :

Comment l'instabilité des recuits quantiques affecte-t-elle la performance des systèmes de recommandation ?
Dans quelle mesure les recuits quantiques sont-ils efficaces pour la sélection de caractéristiques dans ce domaine ?
Les méthodes basées sur QUBO sur du matériel quantique peuvent-elles égaler ou surpasser les références de sélection de caractéristiques classiques ?

2. Méthodologie : PDQUBO

Les auteurs proposent PDQUBO (Optimisation binaire quadratique sans contrainte pilotée par la performance), un cadre novateur qui aligne l'objectif d'optimisation QUBO directement sur la performance de recommandation en aval en utilisant une analyse contrefactuelle.

Flux de travail principal

Entraînement du modèle de base : Un modèle de recommandation ( $G_\Theta$ ) est entraîné sur l'ensemble complet des caractéristiques $F$ .
Analyse contrefactuelle : La méthode évalue l'impact des caractéristiques en créant des « instances contrefactuelles ». Elle masque systématiquement (supprime) des caractéristiques individuelles ( $f_i$ $f_{i}$ ) et des paires de caractéristiques ( $f_i, f_j$ $f_{i}, f_{j}$ ) de l'entrée et mesure la variation de la métrique d'évaluation (par exemple, le nDCG).
- $E_i$ : Chute de performance lorsque $f_i$ est supprimée.
- $E_{ij}$ : Chute de performance lorsque $f_i$ et $f_j$ sont supprimées.
- Note : Une valeur $E$ positive indique que la caractéristique est importante (la performance chute lorsqu'elle est supprimée) ; une valeur négative suggère que la caractéristique est redondante ou nuisible.
Formulation QUBO : Les valeurs contrefactuelles sont utilisées pour construire la matrice de coefficients QUBO $Q$ $Q$ :
- Éléments diagonaux ( $Q_{ii}$ ) : Fixés à $-E_i$ (représentant l'importance individuelle des caractéristiques).
- Éléments hors diagonale ( $Q_{ij}$ ) : Fixés à $-E_{ij}$ (représentant les interactions par paires de caractéristiques).
- La fonction objectif minimise l'énergie $Y = x^T Q x$ , où $x$ est un vecteur binaire indiquant la sélection de caractéristiques. Minimiser $Y$ correspond à sélectionner les caractéristiques qui maximisent la performance de recommandation.
Optimisation : Le problème QUBO construit est résolu à l'aide de solveurs classiques (Recuit simulé, Recherche tabou) ou de recuits quantiques (D-Wave).
Réentraînement : Le sous-ensemble de caractéristiques sélectionné est utilisé pour réentraîner le modèle de base pour l'évaluation finale.

Distinctions clés

Indépendant du modèle : PDQUBO fonctionne avec n'importe quel modèle de base (KNN, MLP, NCF) et n'importe quelle métrique.
Conscient des interactions : Contrairement aux méthodes « filtres » qui traitent les caractéristiques indépendamment, PDQUBO modélise explicitement les interactions par paires via les termes quadratiques dans $Q$ .

3. Contributions clés

Cadre PDQUBO : Une nouvelle formulation QUBO qui lie explicitement la sélection de caractéristiques à la performance de recommandation via l'analyse contrefactuelle, garantissant que l'orientation de l'optimisation est pilotée par la performance plutôt que par les statistiques.
Analyse complète de la stabilité : Une enquête détaillée sur l'instabilité des recuits quantiques réels, analysant comment la qualité de la solution varie en fonction de :
- La taille du problème (nombre de caractéristiques).
- La taille de l'échantillon (nombre de runs de recuit).
- La difficulté du problème (sparsité des données).
Validation empirique : Des expériences extensives sur des ensembles de données réels (ensembles de données CLEF 2024 QuantumCLEF, KuaiRec, KuaiRand, Avazu, Criteo) démontrant que PDQUBO surpasse les références QUBO existantes et rivalise avec les méthodes de sélection de caractéristiques classiques les plus avancées.
Perspectives de mise à l'échelle : Analyse du coût computationnel et proposition d'une stratégie d'élagage en deux étapes pour atténuer la complexité $O(|F|^2)$ de la construction de la matrice QUBO complète, bien que l'article conclue que la formulation quadratique complète est nécessaire pour une performance optimale.

4. Résultats expérimentaux

Les auteurs ont évalué PDQUBO par rapport à des références (CQFS, MIQUBO, CoQUBO, QUBO-Boosting) et des méthodes classiques (Lasso, GBDT, Importance par permutation) sur divers ensembles de données et modèles.

Performance par rapport aux références :
- PDQUBO a constamment obtenu les scores nDCG@10 les meilleurs ou deuxième meilleurs dans la plupart des configurations sur les ensembles de données 150_ICM et 500_ICM.
- Dans les tâches de prédiction de CTR (Avazu, Criteo), PDQUBO-Hybrid (utilisant un solveur hybride quantique-classique) a obtenu les scores AUC les plus élevés, surpassant à la fois les références classiques et les autres variantes QUBO.
- PDQUBO a nettement surpassé les autres méthodes QUBO (comme MIQUBO), prouvant que la construction pilotée par la performance est supérieure à la construction basée sur la dépendance statistique.
Constats sur la stabilité :
- Taille du problème : Les résultats du recuit quantique (QA) deviennent instables lorsque le nombre de caractéristiques dépasse la capacité des qubits logiques du matériel, tandis que les solveurs classiques (SA, TS) restent stables.
- Taille de l'échantillon : L'augmentation du nombre d'échantillons QA réduit considérablement la variance de l'énergie et améliore la performance en aval, soulignant la nécessité d'un échantillonnage suffisant sur les dispositifs NISQ.
- Difficulté : Le QA tend à montrer des gains de performance plus importants mais plus volatils sur des ensembles de données clairsemés (difficiles).
Nécessité des termes quadratiques :
- Les expériences comparant « Indiv » (diagonale uniquement) et « All » (matrice complète) ont montré que l'inclusion des interactions par paires ( $Q_{ij}$ ) est cruciale. L'approche « All » a donné des résultats nettement meilleurs, confirmant que les interactions entre caractéristiques sont vitales pour une sélection efficace dans ce contexte.
Efficacité :
- Alors que la complexité temporelle des solveurs classiques croît de manière exponentielle avec la taille du problème, le temps de recuit quantique reste relativement constant (limité par l'accès au matériel et le temps d'échantillonnage), offrant un avantage potentiel en vitesse pour les problèmes à grande échelle une fois les contraintes matérielles surmontées.

5. Importance et orientations futures

Combler le fossé : Ce travail comble avec succès le fossé entre l'optimisation quantique théorique et le déploiement pratique des systèmes de recommandation en garantissant que l'objectif d'optimisation cible directement la métrique commerciale (qualité de la recommandation).
Viabilité pratique : Les résultats suggèrent que même avec les limitations actuelles du matériel NISQ, les approches hybrides quantiques-classiques peuvent fournir une sélection de caractéristiques compétitive ou supérieure par rapport aux méthodes classiques matures.
Travaux futurs : Les auteurs suggèrent d'étendre PDQUBO pour modéliser des interactions de caractéristiques d'ordre supérieur (au-delà des paires) et d'explorer des algorithmes quantiques variationnels sur des ordinateurs quantiques à portes pour gérer des structures de caractéristiques plus complexes et à plus grande échelle.

En conclusion, PDQUBO représente une avancée significative dans l'application de l'informatique quantique aux défis réels de recommandation, démontrant que les formulations QUBO pilotées par la performance et basées sur l'analyse contrefactuelle peuvent exploiter efficacement les recuits quantiques pour une sélection de caractéristiques de haute qualité.