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

Résumé technique : Encodage entier-binaire dépendant des étapes dans l'optimisation boîte noire par machine de factorisation

Énoncé du problème
L'optimisation boîte noire (BBO) traite des problèmes où les fonctions d'objectif ne possèdent pas de formes analytiques explicites et sont coûteuses à évaluer. La méthode FMQA (Factorization Machine with Quadratic-optimization Annealing) est une approche de BBO de premier plan qui construit un modèle substitut à l'aide d'une machine de factorisation (FM) et l'optimise à l'aide d'une machine d'Ising. Un composant critique de la FMQA est la conversion de variables entières ou continues en variables binaires via un encodage entier-binaire (par exemple, one-hot, domain-wall ou encodage binaire) afin de formuler le problème sous la forme d'un modèle d'optimisation binaire quadratique non contrainte (QUBO).

La FMQA conventionnelle utilise une méthode d'encodage entier-binaire unique tout au long de la phase d'apprentissage automatique (construction du modèle substitut) et de la phase de recherche de solution (optimisation par machine d'Ising). Cependant, des recherches antérieures suggèrent un compromis : l'encodage domain-wall offre souvent une performance de recherche de solution supérieure dans les machines d'Ising, tandis qu'il a été observé que l'encodage one-hot produit des valeurs de fonction objectif plus basses dans le processus d'optimisation globale de la FMQA. Cette divergence implique que l'encodage optimal pour l'apprentissage du paysage substitut peut différer de l'encodage optimal pour la recherche dans ce paysage. Les méthodes conventionnelles, en fixant un encodage unique, peuvent échouer à exploiter pleinement les capacités distinctes de la FM et de la machine d'Ising.

Méthodologie
Les auteurs proposent un cadre FMQA dépendant des étapes qui utilise différentes méthodes d'encodage entier-binaire pour les phases d'apprentissage automatique et de recherche de solution. Le cœur de cette approche repose sur :

1. Stratégie de double encodage : Le cadre entraîne le modèle substitut FM en utilisant un encodage adapté à l'apprentissage (spécifiquement l'encodage one-hot dans la variante « OhDw » proposée), puis convertit le modèle substitut résultant en un encodage différent adapté à la recherche (spécifiquement l'encodage domain-wall) avant l'optimisation par la machine d'Ising.
2. Conversion de matrice QUBO : Pour permettre ce basculement, les auteurs ont dérivé des formules de conversion mathématiques entre les matrices QUBO des encodages one-hot et domain-wall. Ces formules garantissent que le paysage de l'objectif du substitut est préservé sur les états entiers réalisables, à une constante additive près.
   • La conversion du one-hot vers le domain-wall implique la transformation des termes diagonaux et hors diagonaux de la matrice QUBO $Q^{(oh)}$ vers $Q^{(dw)}$ en utilisant des relations de sommation spécifiques (Éqs. 18–20).
   • La conversion inverse (domain-wall vers one-hot) est également dérivée (Éqs. 22–24).
   • La complexité computationnelle pour ces conversions mutuelles est établie à $O(N^2q^2)$, où $N$ est la dimension d'entrée et $q$ est le nombre de niveaux de discrétisation.
3. Flux de travail algorithmique :
   • Phase d'apprentissage : Une FM est entraînée sur des données d'entrée-sortie encodées en one-hot.
   • Conversion : Le modèle substitut entraîné (représenté par une matrice QUBO) est converti d'un encodage one-hot vers un encodage domain-wall.
   • Phase de recherche : Le QUBO converti, augmenté des contraintes d'encodage domain-wall, est optimisé à l'aide d'une machine d'Ising (moteur d'annealing Fixstars Amplify) pour trouver des solutions candidates.
   • Évaluation : Les solutions sont décodées, évaluées par rapport à la véritable fonction boîte noire, et ajoutées au jeu de données d'entraînement pour l'itération suivante.

Principales contributions

1. Proposition de cadre : Introduction d'un cadre FMQA qui découple le choix de l'encodage entre les phases d'apprentissage automatique et de recherche de solution, plutôt que de fixer un encodage unique tout au long du processus.
2. Dérivation théorique : Dérivation de formules de conversion mutuelle entre les matrices QUBO one-hot et domain-wall qui préservent le paysage de l'objectif du substitut sur les états réalisables, permettant ainsi le changement d'encodage sans perdre la fidélité du modèle appris.
3. Décomposition empirique : Une décomposition numérique des effets de l'encodage entier-binaire en contributions de la phase d'apprentissage et de la phase de recherche de solution, en les évaluant séparément pour comprendre leurs impacts distincts sur la performance.

Résultats expérimentaux
La méthode proposée a été évaluée sur la fonction de Rastrigin, un problème de référence multimodal, avec des dimensions d'entrée $N \in \{2, 5\}$ et des niveaux de discrétisation $q \in \{61, 301\}$. La performance de la méthode « OhDw » proposée (un one-hot pour l'apprentissage, un domain-wall pour la recherche) a été comparée aux variantes conventionnelles à encodage unique (Oh, Dw, Bi) et à l'optimisation bayésienne (BO).

• Dominance de l'encodage de la phase d'apprentissage : Dans toutes les conditions, l'encodage utilisé dans la phase d'apprentissage a été le facteur dominant régissant la performance d'optimisation. Les méthodes employant l'encodage one-hot pour l'apprentissage (Oh et OhDw) ont systématiquement obtenu des erreurs résiduelles plus faibles que celles utilisant l'encodage domain-wall ou binaire pour l'apprentissage.
• Bénéfices dépendants des étapes : Le bénéfice du passage à l'encodage domain-wall pour la phase de recherche était dépendant des conditions :
  • Pour $N=5$ et $q=301$ (discrétisation plus fine, espace de recherche plus large), la méthode OhDw a obtenu des erreurs résiduelles plus faibles et des solutions plus proches de l'optimum global par rapport à la méthode Oh (uniquement one-hot).
  • Pour $N=5$ et $q=61$, la méthode Oh a légèrement surpassé la méthode OhDw.
  • Pour $N=2$, aucune différence de performance significative n'a été observée entre Oh et OhDw.
• Stabilité de la recherche : L'analyse de la phase de recherche de solution a indiqué que l'encodage domain-wall permet des transitions plus stables entre les états réalisables dans la machine d'Ising, tandis que l'encodage one-hot nécessite de passer par des états violant les contraintes, ce qui peut réduire la stabilité de la recherche.

Signification et affirmations
L'article affirme que le choix de l'encodage entier-binaire n'est pas simplement un choix de représentation, mais un élément de conception qui remplit des rôles distincts dans les phases d'apprentissage et de recherche de solution de la FMQA. La principale conclusion est que l'encodage one-hot dans la phase d'apprentissage est le principal moteur de la performance d'optimisation, probablement en raison de sa capacité supérieure à construire un modèle substitut précis. Cependant, l'étude démontre que l'utilisation d'encodages dépendants des étapes — spécifiquement la combinaison du one-hot pour l'apprentissage et du domain-wall pour la recherche — peut apporter des améliorations supplémentaires, particulièrement dans les scénarios avec des dimensions d'entrée plus grandes et une discrétisation plus fine où l'espace de recherche est plus complexe.

Les auteurs concluent que bien que la méthode OhDw soit prometteuse, sa généralité nécessite une validation supplémentaire sur une plus grande variété de fonctions de référence et de problèmes d'optimisation de conception du monde réel. De plus, l'analyse systématique de la sensibilité aux coefficients de pénalité et aux différences de densité des matrices QUBO reste une direction pour les travaux futurs.