Improving FMQA via Initial Training Data Design Considering Marginal Bit Coverage in One-Hot Encoding

Ce papier propose d'améliorer l'algorithme Factorization Machine with Quadratic-optimization Annealing (FMQA) en concevant des données d'entraînement initiales à l'aide des méthodes d'échantillonnage par hypercube latin et de Sobol' afin de garantir une couverture complète des bits marginaux dans le codage one-hot, améliorant ainsi les performances d'optimisation sur les problèmes de variables entières et continues discrétisées.

L'essentiel

Imaginez que vous cherchiez la forme parfaite pour l'aile d'un avion propulsé par l'homme. Vous voulez qu'il vole aussi vite que possible, mais les physiques en jeu sont si complexes que vous ne pouvez pas écrire une formule simple pour prédire la vitesse. À la place, vous devez construire un modèle virtuel, le tester, voir à quelle vitesse il va, puis réessayer. C'est un problème de « boîte noire » : vous insérez une conception, et une vitesse en sort, mais vous ne connaissez pas la recette secrète à l'intérieur.

Pour résoudre cela, les chercheurs utilisent un programme informatique intelligent appelé FMQA. Considérez FMQA comme une équipe de détectives en deux étapes :

1. Le Surrogate (L'Étudiant) : Un modèle d'apprentissage automatique qui tente de deviner la réponse en se basant sur les tests passés.
2. Le Chasseur (Le Chasseur) : Un ordinateur spécialisé (une « machine d'Ising ») qui utilise les hypothèses de l'Étudiant pour chasser la forme d'aile la meilleure possible.

Le Problème : Les Bits « Silencieux »

Pour que l'ordinateur comprenne la forme de l'aile, les chercheurs traduisent les variables de conception continues (comme « la longueur de l'aile ») en une chaîne d'interrupteurs binaires (0 et 1) en utilisant une méthode appelée codage one-hot.

Imaginez que vous avez 32 interrupteurs pour « la longueur de l'aile ». Pour dire que la longueur est « moyenne », vous basculez exactement un de ces 32 interrupteurs sur « ON » (1) et laissez les 31 autres sur « OFF » (0).

L'article identifie un défaut dans la façon dont ils lancent généralement ce processus. Ils choisissent habituellement les formes d'ailes de départ en lançant des dés (échantillonnage aléatoire).

• Le Problème : Si vous lancez les dés seulement 32 fois pour commencer, il y a une forte probabilité (environ 36 %) que certains de ces 32 interrupteurs ne soient jamais basculés sur « ON » durant la phase initiale.
• La Conséquence : L'« Étudiant » (le modèle d'apprentissage automatique) apprend en regardant les interrupteurs qui étaient sur ON. Si un interrupteur n'a jamais été sur ON, l'Étudiant n'apprend jamais comment ce réglage spécifique affecte la vitesse. C'est comme un enseignant essayant de noter un élève qui n'a jamais levé la main ; l'enseignant n'a aucune donnée sur les capacités de cet élève.
• Le Résultat : La « carte » du problème de l'ordinateur comporte des angles morts. Lorsque le « Chasseur » cherche la meilleure solution, il pourrait ignorer de bonnes zones parce que la carte indique : « Nous ne savons pas ce qui se passe ici. »

La Solution : La Stratégie d'« Échantillonnage Équitable »

Les auteurs proposent une nouvelle façon de choisir les formes d'ailes de départ. Au lieu de simplement lancer des dés, ils utilisent deux outils mathématiques appelés échantillonnage par hypercube latin (LHS) et séquence de Sobol'.

Considérez ces outils comme un inspecteur d'équité.

• Au lieu d'espérer que la chance fasse basculer chaque interrupteur, l'inspecteur s'assure que chacun des 32 interrupteurs est basculé sur « ON » au moins une fois durant les 32 tests initiaux.
• Cela garantit que l'« Étudiant » reçoit une leçon directe sur chaque réglage possible avant que la véritable recherche ne commence. Aucun interrupteur n'est laissé dans l'obscurité.

Les Résultats : Des Ailes Meilleures, Plus Rapides

Les chercheurs ont testé cela sur deux versions du problème de l'aile d'avion : l'une avec 17 variables de conception et une plus difficile avec 32 variables.

1. La « Vieille Méthode » (Aléatoire) : Même après avoir effectué 200 tests, environ 36 % des interrupteurs n'avaient jamais été allumés dans les données de départ. Les performances de l'ordinateur étaient correctes, mais il avait des angles morts.
2. La « Nouvelle Méthode » (LHS et Sobol') : Chaque interrupteur a été allumé au moins une fois dès le début.
   • Le Résultat : Les nouvelles méthodes ont trouvé des formes d'ailes qui volaient plus vite que l'ancienne méthode aléatoire.
   • La Différence : L'amélioration était faible pour le problème plus simple, mais est devenue beaucoup plus évidente pour le problème plus difficile à 32 variables. C'est comme si les angles morts sur la carte importaient davantage lorsque le terrain devenait plus complexe.

L'Essentiel

L'article ne prétend pas que cela fait voler l'avion à l'ordinateur lui-même, ni qu'il résout tous les problèmes d'optimisation. Il montre simplement que la façon dont vous commencez compte.

En utilisant une stratégie d'« échantillonnage équitable » pour s'assurer que chaque option possible a une chance d'être vue dans les données d'entraînement initiales, l'ordinateur apprend une meilleure carte du problème. Cela lui permet de trouver de meilleures solutions plus rapidement, surtout lorsque le problème se complique. C'est un rappel que dans l'optimisation, vous n'avez pas besoin seulement d'un moteur de recherche intelligent ; vous avez besoin d'une façon intelligente de commencer le voyage.

Résumé technique

Résumé technique : Amélioration de FMQA par la conception des données d'entraînement initiales en tenant compte de la couverture marginale des bits dans le codage one-hot

Énoncé du problème
La Machine à Facteurs avec Recuit d'Optimisation Quadratique (FMQA) est une méthode d'optimisation boîte noire (BBO) qui combine un modèle de substitution Factorization Machine (FM) avec une machine d'Ising pour la recherche. Lorsque FMQA est appliquée à des variables entières ou continues discrétisées utilisant un codage one-hot, un problème critique émerge avec l'échantillonnage initial aléatoire uniforme. Dans ce scénario, de nombreuses variables binaires (bits) dans le jeu de données d'entraînement initial peuvent ne jamais prendre la valeur « 1 ». Puisque le gradient de la sortie FM par rapport aux paramètres associés à un bit spécifique est proportionnel à la valeur de ce bit, les paramètres correspondant aux bits restant à « 0 » tout au long du jeu de données initial ne reçoivent aucune mise à jour de gradient directe à partir des réponses observées. Par conséquent, ces paramètres évoluent uniquement sur la base de l'initialisation et de la décroissance des poids, introduisant un biais dans les coefficients estimés de l'Optimisation Binaire Non Contrainte Quadratique (QUBO). Ce biais peut dégrader la qualité de la recherche de solution effectuée par la machine d'Ising, en particulier dans les problèmes de haute dimension.

Méthodologie
Les auteurs proposent une modification du cadre FMQA axée sur la conception des données d'entraînement initiales. L'objectif principal est d'atteindre une couverture marginale complète des bits, garantissant que chaque variable binaire obtenue via un codage one-hot prenne la valeur « 1 » au moins une fois dans le jeu de données initial.

Pour réaliser cela, les auteurs introduisent deux méthodes de génération de données initiales basées sur des techniques d'échantillonnage à remplissage d'espace :

1. LHS-FMQA : Utilise l'échantillonnage hypercube latin (LHS).
2. Sobol'-FMQA : Utilise la suite de Sobol' (une suite déterministe à faible discrépance).

Les deux méthodes sont configurées de telle sorte que le nombre d'échantillons initiaux ($N_0$) soit égal au nombre de valeurs discrètes par variable ($M$). Sous un codage one-hot, où chaque variable originale est représentée par $M$ bits binaires, le réglage de $N_0 = M$ permet à ces stratégies d'échantillonnage de garantir que chaque valeur discrète est sélectionnée au moins une fois. Grâce à la carte de décodage, cela assure que chaque bit binaire correspondant prend la valeur « 1 » au moins une fois. Cela garantit que tous les paramètres FM reçoivent des mises à jour de gradient dérivées directement du jeu de données pendant la phase d'entraînement initiale, atténuant ainsi le biais causé par les bits « jamais actifs ».

Contributions clés

• Identification d'un mécanisme de biais : L'article identifie formellement que l'échantillonnage aléatoire uniforme dans FMQA codée en one-hot conduit à des bits « jamais actifs », empêchant certains paramètres FM d'être informés par les réponses boîte noire observées.
• Stratégie d'initialisation proposée : Les auteurs proposent et mettent en œuvre des conceptions de données d'entraînement initiales utilisant les suites LHS et Sobol' spécifiquement pour imposer une couverture marginale des bits ($N_0 = M$).
• Validation empirique : Les méthodes sont évaluées sur le benchmark d'optimisation de la forme de l'aile d'un avion à propulsion humaine (HPA), HPA103, un problème d'ingénierie complexe avec des contraintes implicites et aucune information de gradient analytique. Des expériences ont été menées sur deux échelles de problèmes : 17 variables de conception (HPA103-1) et 32 variables de conception (HPA103-2).

Résultats
Les expériences numériques comparant les méthodes proposées (LHS-FMQA et Sobol'-FMQA) à une base Conv-FMQA (initialisation aléatoire uniforme) et à d'autres optimiseurs (GP-BO, NSGA-II, Recherche Aléatoire) ont donné les résultats suivants :

• Amélioration des performances : Les deux méthodes proposées ont atteint des vitesses de croisière finales moyennes numériquement supérieures à celles de la base Conv-FMQA.
• Dépendance à la dimensionnalité : L'avantage des méthodes proposées était plus prononcé dans le problème de plus haute dimension (HPA103-2, 32 variables). L'amélioration de la vitesse de croisière finale par rapport à la base est passée d'environ +0,135 m/s (LHS) et +0,192 m/s (Sobol') sur le problème à 17 variables à +0,333 m/s et +0,352 m/s, respectivement, sur le problème à 32 variables.
• Confirmation du mécanisme : L'analyse des distributions d'utilisation des bits a confirmé que, tandis que Conv-FMQA conservait environ 36 % de bits « jamais actifs » même après le budget d'évaluation complet, les méthodes proposées ont atteint 0 % de bits « jamais actifs ».
• Comparaison avec d'autres optimiseurs : Les méthodes proposées ont performé de manière comparable ou supérieure à GP-BO et NSGA-II. Notamment, l'amélioration par rapport à Conv-FMQA a été entraînée par le processus d'optimisation après la phase d'échantillonnage initial (un « gain » plus élevé), plutôt que simplement en partant de meilleures valeurs initiales optimales.

Signification et affirmations
L'article affirme que l'amélioration de la couverture marginale des bits dans les données d'entraînement initiales est un facteur crucial pour améliorer les performances de FMQA. En garantissant que chaque variable binaire est active au moins une fois, les méthodes proposées empêchent les coefficients QUBO d'être déterminés uniquement par l'initialisation et la décroissance des poids dans des directions spécifiques. Cela permet à la machine d'Ising d'effectuer une recherche informée sur toutes les dimensions de conception.

Les auteurs notent modestement que, bien que leurs résultats soutiennent l'hypothèse selon laquelle la couverture marginale réduit le biais, l'étude actuelle n'isole pas pleinement l'effet de la couverture marginale des propriétés de remplissage d'espace des suites LHS et Sobol'. Ils reconnaissent que les méthodes proposées atteignent simultanément ces deux propriétés. De plus, ils notent que les méthodes garantissent la couverture marginale mais pas la couverture par paires de bits (interactions entre les bits). L'étude conclut que ces stratégies d'initialisation sont particulièrement efficaces pour les problèmes de haute dimension où le nombre absolu de bits potentiellement inactifs dans un échantillonnage aléatoire serait autrement substantiel. Un travail futur est suggéré pour découpler la couverture marginale des propriétés de remplissage d'espace et pour investiguer des stratégies de couverture par paires.