Rate-Distortion Theory for Deductive Sources under Closure Fidelity

1. Problématique et Contexte

L'article aborde le problème de la compression avec perte (lossy compression) d'une source de connaissances finie générée dans un environnement déductif fixe. Contrairement à la théorie classique du taux-distorsion où la fidélité est mesurée par l'égalité symbole par symbole, ce travail propose un cadre où la fidélité est définie par la préservation de la fermeture déductive (deductive closure).

• Le Modèle de Source : La source n'est pas une simple collection de symboles, mais une base de connaissances $S_O$ équipée d'un système de preuve fixe. Les symboles de la source sont des énoncés (statements).
• La Redondance Déductive : Dans une base de connaissances, certains énoncés sont des prémisses irréductibles (le « noyau »), tandis que d'autres sont des conséquences stockées qui peuvent être ré-derivées à partir des prémisses.
• L'Objectif : Déterminer les limites fondamentales de la compression lorsque le récepteur n'a pas besoin de recevoir exactement le même énoncé, mais seulement un énoncé qui génère le même ensemble de conséquences logiques (fermeture déductive).

2. Méthodologie et Cadre Théorique

Les auteurs formalisent le problème en utilisant la théorie de l'information de Shannon, adaptée aux structures déductives.

• Définition du Noyau Irréductible (Irredundant Core) :
  Soit $S_O$ la base de connaissances. En appliquant un système de preuve et un ordre canonique, on définit un ensemble $A = \text{Atom}(S_O)$ appelé le noyau irréductible. Cet ensemble est obtenu par une procédure de suppression déterministe : un énoncé est supprimé s'il appartient à la fermeture déductive des autres énoncés restants.

  • $A$ : Noyau irréductible (prémisses essentielles).
  • $J = S_O \setminus A$ : Partie redondante (conséquences stockées).

• Fidélité par Fermeture (Closure Fidelity) :
  La distorsion n'est pas mesurée par l'erreur de Hamming, mais par la différence entre les fermetures déductives de la source et de la reconstruction.

  • Si $Cn(S)$ est la fermeture déductive de $S$, la fidélité est maximale si $Cn(S) = Cn(\hat{S})$.
  • Une conséquence clé (Proposition 2.2) est que tout état redondant $j \in J$ peut être reconstruit par n'importe quel élément de $Cn(S_O)$ sans coût de distorsion.

• Hypothèse de Disjonction :
  Pour obtenir des résultats exacts, les auteurs introduisent l'Hypothèse 3.1 : les ensembles de reconstruction à distorsion nulle pour deux symboles distincts du noyau $A$ doivent être disjoints. Cela évite le problème de confusion entre les éléments du noyau.

3. Contributions Principales

L'article apporte quatre contributions majeures à la théorie de l'information :

1. Formulation d'un modèle de source déductive :
   Le papier définit un problème de codage de source à alphabet fini où la fidélité est intrinsèquement liée à la structure logique (fermeture déductive) plutôt qu'à la similarité sémantique vague ou à l'égalité stricte.

2. Caractérisation exacte du taux à distorsion nulle :
   Sous l'hypothèse de disjonction, le taux minimal pour une reconstruction sans perte de fermeture déductive est donné par :
   $$R_{sem}(0) = P_A H(\pi_A)$$
   Où $P_A$ est la masse de probabilité du noyau $A$ et $H(\pi_A)$ est l'entropie de la distribution conditionnelle sur ce noyau.

   • Signification : Le taux ne dépend pas de la taille totale de la base de connaissances, mais uniquement de la complexité du noyau irréductible. Les états redondants sont « invisibles » pour le taux.

3. Décomposition de la fonction taux-distorsion complète :
   Pour toute distorsion $D \ge 0$, la fonction taux-distorsion complète se décompose en une contribution provenant uniquement du noyau :
   $$R_{sem}(D) = P_A \cdot R^{(A)}\left(\frac{D}{P_A}\right)$$
   Cela signifie que la partie redondante $J$ n'influence ni le taux ni la distorsion, tant que l'alphabet de reconstruction est contenu dans la fermeture déductive de la source.

4. Loi Taux-Délai-Distorsion pour inférence limitée :
   Lorsque le décodeur dispose d'un budget d'inférence limité (un nombre maximal $\delta$ d'étapes de déduction), les auteurs introduisent le concept de noyau $\delta$-irréductible ($A_\delta$).

   • Ils établissent une relation exacte entre le taux, le délai (budget d'inférence) et la distorsion.
   • À $\delta=0$, on retrouve le codage classique (égalité symbole par symbole).
   • À $\delta \ge D_d$ (profondeur maximale de déduction), on retrouve le taux de compression déductive pure.
   • Cela permet d'interpoler de manière précise entre la compression classique et la compression déductive.

4. Résultats Clés et Implications

• Gain de Compression : La compression déductive permet des gains stricts par rapport à la compression classique (Hamming). Le taux de compression peut être réduit d'un facteur proche de $\frac{\log |A|}{\log |S_O|}$, ce qui devient significatif lorsque la base de connaissances contient beaucoup de conséquences matérialisées (redondantes).
• Séparation Source-Canal : Le théorème de séparation source-canal classique s'applique toujours, mais le taux de source à utiliser est le taux déductif $R_{sem}(D)$, et non l'entropie de la source brute.
• Bornes de Converse Adaptées : Les auteurs dérivent des bornes de type Fano adaptées à la fidélité par fermeture, montrant que la complexité effective est celle du noyau, et non celle de l'ensemble complet.
• Récepteurs Hétérogènes : Le modèle est étendu aux cas où le récepteur a un vocabulaire restreint. Le taux reste inchangé tant que chaque élément du noyau possède un représentant « équivalent par fermeture » dans le vocabulaire du récepteur.

5. Signification et Impact

Cet article est fondamental car il formalise mathématiquement l'idée que la structure d'inférence partagée est une ressource qui réduit le taux de communication nécessaire.

• Au-delà de la communication sémantique : Contrairement aux approches de communication sémantique souvent basées sur des architectures spécifiques ou des similarités vectorielles, ce travail ancre la réduction de taux dans la logique formelle et la théorie de la preuve.
• Optimisation des bases de connaissances : Il fournit une justification théorique pour le stockage de bases de connaissances « matérialisées » (où les conséquences sont pré-calculées) : même si elles augmentent la taille des données stockées, elles ne devraient pas augmenter le coût de transmission si le récepteur peut effectuer les mêmes inférences.
• Nouvelles directions : L'article ouvre la voie à l'étude des sources structurées, des problèmes d'inférence distribuée et de la compression dans des environnements où la capacité de calcul du récepteur est une contrainte explicite (trade-off taux-délai).

En résumé, ce papier démontre que dans un environnement déductif, la « véritable » information à transmettre est contenue uniquement dans le noyau irréductible de la connaissance, transformant la redondance logique en opportunité de compression.