WME: Extending CDCL-based Model Enumeration with Weights

Each language version is independently generated for its own context, not a direct translation.

Imaginez que vous êtes un détective chargé de résoudre une énigme complexe. Vous avez une liste de suspects (les variables) et une série de règles strictes (la formule logique) que le coupable doit respecter. Votre mission n'est pas seulement de trouver un coupable, mais de trouver les meilleurs coupables selon un critère de "gravité" ou d'importance (les poids).

C'est exactement ce que fait cette recherche, appelée WME (Énumération de Modèles Pondérés). Voici une explication simple de comment cela fonctionne, en utilisant des analogies du quotidien.

1. Le Problème : Trouver l'or, pas juste de la pierre

Dans le monde de l'informatique classique, les détectives (les solveurs) ont deux modes principaux :

Le mode "Tout trouver" (AllSAT) : Ils listent tous les suspects possibles, même ceux qui sont totalement innocents ou peu probables. C'est fastidieux et inutile si vous cherchez juste le coupable principal.
Le mode "Le meilleur" (MaxSAT) : Ils ne vous donnent que le seul coupable le plus probable. Mais si vous voulez les 5 meilleurs suspects pour avoir une meilleure idée de ce qui s'est passé, ils sont bloqués.

Le WME, c'est comme un détective qui a une boussole magique. Il ne cherche pas n'importe qui, ni seulement le tout premier. Il cherche les meilleurs (les plus lourds en "poids" de culpabilité) et s'arrête dès qu'il a trouvé ce qu'il vous faut (les top-k) ou tous ceux qui dépassent un certain seuil de gravité.

2. La Mécanique : Comment le détective évite les impasses

Le cœur de la recherche est une technique appelée CDCL (une méthode très intelligente pour explorer les possibilités). Le WME ajoute une couche de "poids" à cette méthode.

A. La Boussole de l'Espoir (Propagation des poids)

Imaginez que vous êtes dans un labyrinthe. À chaque intersection, vous devez choisir une direction.

Sans WME : Vous continuez jusqu'au bout du couloir pour voir si c'est une impasse.
Avec WME : Vous avez une boussole qui vous dit : "Même si tu prends le chemin le plus prometteur qui reste, tu n'arriveras jamais à atteindre le score de 100 points."
Dès que la boussole le dit, vous coupez court (vous "élaguez" la branche). Vous ne perdez pas de temps à explorer un chemin qui ne mène jamais à un bon résultat. C'est ce qu'on appelle la taille de la branche.

B. Le Carnet de Notes Intelligent (Analyse des conflits)

Quand le détective se rend compte qu'il a pris un mauvais chemin (un "conflit de poids"), il ne se contente pas de faire demi-tour. Il écrit dans son carnet : "Ne refais jamais ce chemin précis, car il est trop léger."
C'est ce qu'on appelle l'apprentissage de clauses. Le détective devient plus intelligent à chaque erreur, évitant de rejouer les mêmes scénarios inutiles.

3. Les Deux Stratégies de Marche (Backtracking)

Les chercheurs ont testé deux façons de se déplacer dans ce labyrinthe pondéré :

Stratégie A : La Marche Chronologique (Le pas régulier)

Comment ça marche : Vous avancez pas à pas. Si vous bloquez, vous reculez d'un seul pas, vous changez de direction, et vous continuez.
L'analogie : C'est comme un promeneur qui explore un parc. Il ne saute pas en arrière. Il garde une trace mentale de ce qu'il a déjà vu.
Avantage : Il utilise très peu de mémoire (pas besoin de porter un gros sac à dos).
Inconvénient : Si vous faites un mauvais choix au début, vous pouvez mettre beaucoup de temps à trouver les meilleurs trésors.

Stratégie B : La Marche Non-Chronologique (Le saut de puce)

Comment ça marche : Si vous trouvez un trésor, vous écrivez une règle : "Ne reviens jamais ici". Ensuite, vous faites un grand saut en arrière (parfois très loin) pour essayer une tout autre approche, en vous fiant à vos règles écrites.
L'analogie : C'est comme un joueur d'échecs qui, après avoir perdu une partie, rejoue immédiatement une autre partie en évitant les erreurs passées, en sautant par-dessus les étapes inutiles.
Avantage : Il trouve les meilleurs trésors très vite, surtout s'il y a beaucoup de fausses pistes.
Inconvénient : Il a besoin de beaucoup de mémoire pour garder toutes ses règles écrites.

4. Le Verdict : Quelle stratégie choisir ?

Les chercheurs ont découvert qu'il n'y a pas de "meilleure" stratégie universelle, tout dépend de la situation :

Si vous cherchez les "Top 10" (Top-k) : La Stratégie B (Saut de puce) est souvent la gagnante. Elle est très agressive pour trouver les meilleurs scores rapidement et coupe les mauvaises branches très tôt.
Si vous devez lister tous les suspects au-dessus d'un seuil (Énumération par seuil) : La Stratégie A (Pas régulier) est souvent meilleure. Comme il y a beaucoup de solutions à trouver, la Stratégie B s'essouffle avec trop de règles écrites, tandis que la Stratégie A reste légère et efficace pour tout parcourir.

En résumé

Ce papier présente un nouveau type de détective informatique capable de trier les solutions non seulement par "vrai ou faux", mais par "bon ou meilleur". Il utilise une boussole pour éviter les impasses inutiles et deux styles de marche différents selon qu'il doit trouver le "meilleur" ou "tout ce qui est bon".

C'est une avancée majeure pour des domaines comme l'intelligence artificielle, la médecine (trouver les diagnostics les plus probables) ou la finance (évaluer les risques les plus critiques), où l'on ne veut pas juste une réponse, mais les meilleures réponses possibles.

Each language version is independently generated for its own context, not a direct translation.

1. Problématique : L'Énumération de Modèles Pondérés (WME)

L'article introduit et formalise le problème de l'Énumération de Modèles Pondérés (Weighted Model Enumeration - WME). Contrairement aux problèmes classiques de satisfaction de contraintes (SAT), où l'objectif est de trouver un modèle satisfaisant, ou à l'énumération complète (AllSAT), qui liste tous les modèles sans distinction, le WME vise à énumérer les modèles d'une formule booléenne en tenant compte d'une fonction de poids associée à chaque affectation.

Définition formelle :
Étant donné une formule CNF $F$ sur des variables $V$ et une fonction de poids $w$ sur les littéraux, le but est de calculer l'ensemble des affectations satisfaisantes $\eta$ accompagnées de leur poids agrégé $w(\eta) = \prod_{\ell \in \eta} w(\ell)$ .

Ce cadre généralise deux variantes contraintes :

WME à seuil (Threshold WME) : Énumérer tous les modèles dont le poids est supérieur ou égal à un seuil $\theta$ .
WME Top-k : Énumérer les $k$ modèles ayant les poids les plus élevés.

Limites des approches existantes :
Les auteurs soulignent que les outils actuels sont inadéquats pour cette tâche native :

AllSAT : Ignore les poids et énumère de manière aveugle.
Comptage de modèles pondérés (WMC) : Calcule des agrégats globaux mais ne fournit pas les modèles individuels.
MaxSAT : Ne retourne qu'une seule solution optimale (ou nécessite des appels itératifs coûteux pour obtenir plusieurs solutions).
Compilation (d-DNNF) : Peut être efficace mais souffre de la complexité de la compilation et ne s'adapte pas naturellement aux vérifications de théorie dans le cadre SMT.

2. Méthodologie : Intégration du Raisonnement Pondéré dans CDCL

L'approche proposée étend le cadre CDCL (Conflict-Driven Clause Learning) standard en y intégrant un raisonnement numérique pour la gestion des poids. L'algorithme maintient la structure de boucle CDCL tout en ajoutant des mécanismes de propagation, de pruning (élagage) et d'analyse de conflits spécifiques aux poids.

A. Propagation et Élagage Pondérés (Weight Pruning)

Le solveur maintient deux valeurs pour l'affectation partielle courante $\mu$ :

Poids partiel $w(\mu)$ : Le produit des poids des littéraux déjà assignés.
Borne résiduelle optimiste $I_{max}(\mu)$ : Le produit des meilleurs poids possibles ( $best(A) = \max(w(A), w(\neg A))$ ) pour toutes les variables non assignées.

Le solveur vérifie continuellement si $w(\mu) \cdot I_{max}(\mu) < \theta$ . Si cette condition est vraie, même l'extension la plus optimiste de l'affectation courante ne peut atteindre le seuil. La branche est alors élaguée (pruned) et un conflit de poids est signalé.

B. Analyse de Conflits de Poids (Weight Conflict Analysis)

Lorsqu'un conflit de poids est détecté, le solveur ne se contente pas de revenir en arrière ; il apprend une clause de conflit pondéré.

Une stratégie gloutonne sélectionne un sous-ensemble de littéraux $S \subseteq \mu$ dont l'assignation empêche d'atteindre le seuil.
Une clause $C_w = \bigvee_{\ell \in S} \neg \ell$ est apprise pour empêcher le solveur de revisiter cette région infeasible.
Cela permet de propager les contraintes de poids à travers l'espace de recherche, similaire à l'analyse de conflits booléens classiques.

C. Backtracking Adaptatif et Priorité des Variables

Backtracking résiduel (Residual-Aware Backtracking) : Dans le cadre Top-k, lorsqu'un nouveau meilleur modèle est trouvé, le seuil $\theta$ est mis à jour. Le solveur utilise la borne résiduelle pour déterminer à quel niveau de décision revenir immédiatement, évitant de continuer des recherches inutiles.
Variables pertinentes vs non pertinentes : Pour les encodages Tseitin ou Plaisted-Greenbaum, certaines variables ajoutées peuvent être "pondérativement non pertinentes" (leurs deux polarités ont le même poids). Le solveur priorise l'assignation des variables pertinentes pour le poids afin d'optimiser le tri.

3. Contributions Clés

Formalisation du WME : Définition d'un problème unifiant AllSAT, WMC et MaxSAT sous une approche d'énumération pondérée native.
Nouveaux algorithmes CDCL : Développement de règles de propagation et de clauses d'apprentissage spécifiques aux poids.
Deux architectures de backtracking :
- Chronologique (WME-CB) : Utilise un backtracking chronologique avec blocage implicite. Moins gourmand en mémoire, efficace pour les espaces denses.
- Non-chronologique (WME-NCB) : Utilise le backtracking non-chronologique avec apprentissage de clauses de blocage explicites et redémarrages. Plus robuste à l'ordre de décision, idéal pour trouver rapidement les meilleurs modèles (Top-k).
Implémentation et Évaluation : Mise en œuvre de ces deux variantes sur la base de code CaDiCaL et comparaison sur des benchmarks synthétiques et réels.

4. Résultats Expérimentaux

Les auteurs ont évalué leurs solveurs (WME-CB et WME-NCB) sur trois familles de benchmarks :

Synthétiques (rnd3sat-1.5) : Formules aléatoires avec un grand nombre de solutions.
Difficiles (uf200-860) : Formules SATLIB stressant l'élagage pondéré.
Bayésiens (bayes-basic/or) : Réels, issus de réseaux bayésiens, utilisés pour l'inférence MPE (Most Probable Explanation).

Constats principaux :

Top-1 (Recherche du meilleur modèle) : WME-NCB surpasse systématiquement WME-CB et les solveurs de référence (DPO, MaxHS). La capacité à apprendre des clauses de blocage et à redémarrer permet de converger plus vite vers les solutions à haut poids.
Énumération Top-k native vs itérative : L'approche native Top-k réutilise efficacement les informations accumulées (bornes, clauses apprises), évitant le coût de la répétition de la recherche Top-1 avec blocage de modèles.
Énumération à seuil (Threshold) : Dans ce scénario où l'objectif est de lister tous les modèles au-dessus d'un seuil (souvent un grand nombre), WME-CB (chronologique) est supérieur. L'accumulation de clauses de blocage explicites dans WME-NCB alourdit la propagation et consomme trop de mémoire, rendant l'approche chronologique plus efficace pour les espaces de solutions denses.
Études d'ablation : La désactivation de l'élagage pondéré entraîne une dégradation massive des performances, confirmant que l'intégration native du raisonnement pondéré est essentielle.

5. Signification et Conclusion

Cet article établit le WME comme une tâche de raisonnement de niveau solveur à part entière. Il démontre qu'il n'est pas nécessaire de combiner des solveurs distincts (un pour l'énumération, un pour le comptage) pour gérer les poids.

Impact principal :

Il fournit une base algorithmique solide pour les applications d'IA nécessitant des explications multiples et pondérées (inférence probabiliste, diagnostic de pannes, apprentissage interprétable).
Il clarifie le compromis fondamental : l'approche non-chronologique est préférable pour l'optimisation et l'extraction de top-k (recherche de "pics"), tandis que l'approche chronologique est supérieure pour l'énumération exhaustive sous contraintes de seuil (exploration de "régions denses").
L'approche est conçue pour être extensible vers le cadre SMT (CDCL(T)), permettant une énumération pondérée dans des théories plus riches, ce qui ouvre la voie à de nouvelles applications en vérification formelle et en intelligence artificielle.