Interval Orders, Biorders and Credibility-limited Belief Revision

1. Énoncé du problème

Le papier aborde les limitations du cadre standard de révision de croyances AGM (Alchourrón, Gärdenfors et Makinson). L'approche AGM repose sur des préordres totaux sur les mondes possibles pour modéliser les croyances d'un agent. Ce cadre impose deux postulats fondamentaux :

• Succès : La nouvelle information est toujours acceptée.
• Cohérence : L'ensemble des croyances résultant est toujours cohérent (à condition que l'entrée soit cohérente).

Les auteurs soutiennent que ces postulats sont trop idéalisés pour des agents réalistes. Les agents réels peuvent rencontrer des informations déstabilisantes (provoquant un effondrement des croyances actuelles) ou incroyables (initialement rejetées mais potentiellement acceptées avec un contexte supplémentaire). Le papier vise à explorer des opérateurs de révision de croyances basés sur des structures d'ordre plus générales permettant :

1. Instabilité/Dissonance : Des scénarios où l'acceptation de nouvelles informations conduit à un ensemble vide de modèles optimaux (incohérence).
2. Révision non priorisée : Des scénarios où l'agent rejette les nouvelles informations pour préserver la cohérence, ou où le postulat de « Succès » est abandonné.

2. Méthodologie

Les auteurs généralisent la structure sémantique sous-jacente de la révision de croyances, passant des préordres totaux à deux classes plus larges d'ordres étudiées en théorie du choix rationnel : les ordres d'intervalles et les biordres.

A. Ordres d'intervalles (IOB)

• Définition : Une relation binaire satisfaisant la réflexivité et la condition de Ferrers.
• Sémantique : Représentée par une interprétation basée sur les intervalles $\mathcal{I} = \langle L, U \rangle$, où chaque monde $v$ se voit attribuer un intervalle $[L(v), U(v)]$ d'entiers non négatifs.
• Règle de révision : Un monde $v$ est préféré à $u$ si $L(v) \leq U(u)$.
• Comportement : Ces opérateurs satisfont le postulat de Succès mais échouent à satisfaire la Vacuité et la Sous-expansion (postulats AGM standards) en général. Ils maintiennent la Cohérence.

B. Biordres (BOB)

• Définition : Une généralisation des ordres d'intervalles qui satisfait la condition de Ferrers mais ne requiert pas la réflexivité.
• Sémantique : Représentée par une interprétation basée sur les biordres $\mathcal{B} = \langle L, U \rangle$. Crucialement, la longueur de l'intervalle $U(v) - L(v)$ peut être négative.
  • Un intervalle négatif ($U(v) < L(v)$) signifie une valuation dissonante, représentant une forme d'« impossibilité » ou d'instabilité.
• Règle de révision : $v \preceq_{bi} u$ si et seulement si $L(v) \leq U(u)$.
• Comportement : Ces opérateurs satisfont le Succès mais violent la Cohérence. Si la nouvelle information $\alpha$ est « déstabilisante » (c'est-à-dire que l'ensemble optimal de modèles pour $\alpha$ est vide car tous les modèles de $\alpha$ sont dissonants), la révision produit un ensemble de croyances incohérent (vide).

C. Sous-classes et transitivité

Les auteurs définissent deux sous-classes de biordres pour imposer des propriétés structurelles plus fortes :

1. ZTBOB (z-transitif) : Satisfait une forme affaiblie de transitivité impliquant des éléments dissonants. Cela assure la Monotonie prudente cohérente.
2. TBOB (Transitif) : Satisfait la transitivité complète. Cela permet de retrouver le postulat de Sous-expansion (un postulat AGM supplémentaire clé) mais autorise toujours l'incohérence.

D. Révision non priorisée (NPR)

Pour résoudre le problème d'incohérence dans la révision basée sur les biordres, les auteurs définissent des opérateurs de Révision non priorisée ($\circ$).

• Mécanisme : Si une révision basée sur les biordres ($\bullet$) de $\alpha$ aboutit à un ensemble incohérent, l'opérateur NPR rejette l'entrée et retourne l'ensemble de croyances original $KB$.
• Crédibilité : Une entrée $\alpha$ est jugée crédible si $KB \bullet \alpha$ est cohérent ; sinon, elle est incroyable.
• Lien avec la Révision limitée par la crédibilité (CLR) : Les auteurs cartographient ces opérateurs NPR sur le cadre de la Révision limitée par la crédibilité (Hansson et al.), mais avec une modification cruciale : ils rejettent la propriété de fermeture par phrase unique.
  • CLR standard : Si $\alpha$ est crédible, toute conséquence logique est crédible.
  • CLR proposée : Un agent peut rejeter $\alpha$ initialement mais accepter $\alpha \land \beta$ si $\beta$ fournit le contexte nécessaire (par exemple, « Le roi Charles a visité une école » rend « Le neveu a déjeuné avec le roi Charles » crédible).

3. Contributions clés

1. Extension de la sémantique de révision :

   • Introduction de la révision basée sur les ordres d'intervalles (IOB), complétant le tableau initié par Rott (2014) pour la contraction.
   • Introduction de la révision basée sur les biordres (BOB), utilisant des longueurs d'intervalle négatives pour modéliser la « dissonance » et l'instabilité, un concept précédemment inexploré en révision de croyances.

2. Caractérisations axiomatiques :

   • Fourniture de théorèmes de représentation pour les opérateurs IOB, ZTBOB et TBOB.
   • Identification que les opérateurs TBOB satisfont tous les postulats AGM sauf la Cohérence, plus la Rationalité disjonctive.
   • Caractérisation des opérateurs NPR résultants (BOB-NPR, ZTBOB-NPR, TBOB-NPR) à l'aide d'un ensemble de postulats incluant le Succès relatif (Succès ou aucun changement) et une Rationalité disjonctive modifiée.

3. Révision limitée par la crédibilité avec fermeture contextuelle :

   • Formulation des opérateurs NPR comme opérateurs de Révision limitée par la crédibilité.
   • Proposition d'un assouplissement de la condition de Fermeture par phrase unique (remplacée par une fermeture plus faible pour les disjonctions). Cela permet une crédibilité dépendante du contexte, où une phrase est rejetée isolément mais acceptée lorsqu'elle est combinée avec un contexte explicatif.

4. Gestion des entrées déstabilisantes :

   • Définition de phrases déstabilisantes, irréconciliables et précaires.
   • Démonstration que les biordres peuvent modéliser des scénarios où un agent entre en « mode maintenance » (rejet de l'entrée) jusqu'à ce qu'une explication supplémentaire stabilise l'état de croyance.

4. Résultats

• Théorèmes 1-3 : Établissement de la correspondance entre les préordres totaux, les ordres d'intervalles et les biordres, et leurs opérateurs de révision respectifs.
• Théorèmes 4 & 5 : Démonstration que les opérateurs ZTBOB et TBOB satisfont des ensembles spécifiques de postulats renforcés (par exemple, TBOB satisfait la Sous-expansion).
• Théorèmes 6-8 : Fourniture de caractérisations axiomatiques pour les versions non priorisées de ces opérateurs, introduisant des postulats comme P12+ (si une disjonction est crédible et qu'un disjonctif ne l'est pas, le résultat est équivalent à la révision avec le disjonctif crédible seul).
• Théorèmes 9 & 10 : Preuve que les opérateurs ZTBOB-NPR et TBOB-NPR sont équivalents à des opérateurs de Révision limitée par la crédibilité où la révision sous-jacente est basée sur les ordres d'intervalles et AGM (préordres totaux), respectivement.
• Contre-exemples : Démonstration que les postulats AGM standards comme la Vacuité et la Sous-expansion échouent pour les biordres généraux, et que la Cohérence échoue pour la révision BOB sauf si les entrées sont filtrées.

5. Signification

• Réalisme en IA : Le papier rapproche la révision de croyances du comportement réel des agents en permettant l'instabilité et l'acceptation conditionnelle de l'information. Il modélise le processus cognitif de rejet d'informations « trop belles pour être vraies » ou « trop étranges » jusqu'à ce qu'elles soient contextualisées.
• Nouveauté théorique : Il comble le fossé entre la théorie du choix rationnel (spécifiquement les biordres et les ordres d'intervalles) et la révision de croyances, introduisant des concepts tels que les « intervalles négatifs » et la « dissonance » dans la logique du changement de croyance.
• Flexibilité : En assouplissant la condition de Fermeture par phrase unique, le cadre soutient un raisonnement plus nuancé où la crédibilité d'une affirmation dépend de sa conjonction avec d'autres affirmations (contexte), plutôt que de sa seule forme logique.
• Perspectives futures : Ce travail ouvre des voies pour l'étude de la révision itérée avec des biordres, du raisonnement non monotone et du raisonnement normatif, suggérant que la structure supplémentaire des biordres (au-delà de ce qui est nécessaire pour une seule étape de révision) peut être cruciale pour gérer des séquences de mises à jour.

En résumé, le papier propose un cadre théorique robuste où la révision de croyances n'est pas une acceptation aveugle de la vérité, mais un processus sélectif régi par les propriétés structurelles de l'ordre de croyance de l'agent, capable de gérer l'instabilité et la crédibilité dépendante du contexte.