Rate-Distortion Theory for Deductive Sources under Closure Fidelity

Titolo

Teoria della Taratura-Distorsione per Fonti Deduttive sotto Fedeltà di Chiusura

1. Il Problema

Il lavoro affronta il problema della compressione con perdita (lossy compression) di una fonte di conoscenza finita (una base di conoscenza) all'interno di un ambiente deduttivo fisso.

• Contesto: A differenza della teoria dell'informazione classica, dove l'alfabeto della fonte è una collezione piatta di simboli e la fedeltà è misurata dall'uguaglianza simbolo-per-simbolo, qui la fonte è una base di conoscenza dotata di un sistema di prova condiviso.
• Obiettivo: L'obiettivo non è riprodurre esattamente i simboli trasmessi, ma preservare la chiusura deduttiva (deductive closure) della conoscenza. Se il ricevitore può derivare le stesse conseguenze logiche da una rappresentazione diversa, il compito di comunicazione è considerato completato.
• Sfida: Come quantificare i limiti fondamentali della compressione quando la ridondanza non è statistica, ma logica (conseguenze dedotte da premesse)?

2. Metodologia e Modello

Gli autori formulano un modello di sorgente finito-alphabet basato su tre pilastri fondamentali:

• Sistema Deduttivo Fisso: Viene fissato un universo finito di affermazioni $S_O$ e un sistema di prova efficace con un operatore di chiusura deduttiva $Cn(\cdot)$.
• Decomposizione della Sorgente: Una volta fissato il sistema di prova e un ordine canonico, la base di conoscenza $S_O$ viene decomposta in due parti:
  1. Nucleo Irredundante ($A = \text{Atom}(S_O)$): L'insieme delle premesse essenziali che non possono essere derivate dalle altre.
  2. Parte Ridondante ($J = S_O \setminus A$): Le conseguenze memorizzate che possono essere ri-derivate una volta note le premesse del nucleo.
• Criterio di Fedeltà (Closure Fidelity): La distorsione non è l'errore Hamming, ma una misura basata sulla similarità Jaccard tra le chiusure deduttive della sorgente originale e della ricostruzione.
  • $d_{Cn}(s, \hat{s}) = 0$ se e solo se $Cn(S_O) = Cn((S_O \setminus \{s\}) \cup \{\hat{s}\})$.
  • Questo implica che gli stati ridondanti ($J$) possono essere ricostruiti con distorsione zero anche se non trasmessi fedelmente, purché il nucleo sia preservato.

3. Contributi Chiave

A. Caratterizzazione Esatta del Tasso a Distorsione Zero

Sotto un'ipotesi di disgiunzione sui set di ricostruzione a distorsione zero (Assunzione 3.1), gli autori dimostrano che il tasso minimo per una ricostruzione a distorsione zero è determinato esclusivamente dal nucleo irredundante:
$$R_{sem}(0) = P_A H(\pi_A)$$
Dove:

• $P_A$ è la massa di probabilità della sorgente sul nucleo $A$.
• $H(\pi_A)$ è l'entropia della distribuzione condizionata al nucleo.
• Significato: La parte ridondante è "invisibile" al tasso di compressione a distorsione zero. Il tasso è strettamente inferiore all'entropia classica della sorgente $H(P_O)$ se $J \neq \emptyset$.

B. Decomposizione della Funzione Tasso-Distorsione Completa

Il paper estende il risultato a qualsiasi livello di distorsione $D \geq 0$. La funzione tasso-distorsione completa si decompone in un contributo che dipende solo dal nucleo:
$$R_{sem}(D) = P_A \cdot R^{(A)}\left(\frac{D}{P_A}\right)$$
Questo dimostra che gli stati ridondanti non influenzano né il tasso né la distorsione per l'intera curva, riducendo il problema a una codifica classica (ma con distorsione logica) sul solo nucleo.

C. Legge Tasso-Ritardo-Distorsione per Inferenza Limitata

Quando il ricevitore ha un budget di inferenza limitato (può eseguire al massimo $\delta$ passi di deduzione), viene introdotto il concetto di nucleo $\delta$-irredundante ($A_\delta$).

• Gli stati che possono essere derivati entro $\delta$ passi diventano ridondanti.
• Viene ottenuta una caratterizzazione esatta: $R_{sem}(0, \delta) = P_\delta H(\pi_\delta)$.
• Questo crea un'interpolazione precisa tra la compressione classica (a $\delta=0$, dove nulla è ridondante) e la compressione deduttiva illimitata (a $\delta \geq D_d$, dove tutto ciò che è derivabile è ridondante).

D. Estensioni e Conseguenze

• Separazione Sorgente-Canale: Viene dimostrato che il principio di separazione classico vale anche per questo modello strutturato.
• Limiti di Converse (Bound): Vengono derivati limiti inferiori di tipo Fano adattati alla chiusura, che sono più stretti dei limiti classici perché basati sulla complessità del nucleo e non sull'intera sorgente.
• Ricevitori Eterogenei: Il modello viene esteso a ricevitori con vocabolari limitati, mostrando che la fattibilità della distorsione zero dipende dalla presenza di rappresentanti "zero-distorsione" per ogni simbolo del nucleo nel vocabolario del ricevitore.

4. Risultati Principali

1. Riduzione della Complessità: La complessità della fonte deduttiva è governata dal nucleo irredundante, non dalla base di conoscenza completa.
2. Guadagno di Compressione: In scenari con basi di conoscenza materializzate (dove molte conseguenze sono pre-calcolate e memorizzate), il tasso di compressione può essere drasticamente inferiore rispetto alla codifica Hamming classica.
3. Trade-off Ritardo-Rate: Esiste una relazione quantitativa precisa tra il numero di passi di inferenza consentiti al ricevitore e il tasso di compressione necessario: più inferenza è consentita, meno dati devono essere trasmessi.
4. Indipendenza dall'Ordine: Sebbene la costruzione del nucleo dipenda dall'ordine canonico, il tasso di distorsione zero è intrinseco al modello deduttivo. Sotto condizioni di robustezza (insieme essenziale), anche il nucleo stesso diventa invariante.

5. Significato e Impatto

Questo lavoro rappresenta un passo fondamentale verso una teoria dell'informazione semantica strutturata.

• Cambio di Paradigma: Sposta l'attenzione dalle architetture specifiche di comunicazione semantica alla definizione di un oggetto informativo a livello di modello sorgente.
• Ridondanza come Risorsa: Dimostra che la struttura inferenziale condivisa può essere trattata come una risorsa che riduce il tasso di comunicazione, poiché la ridondanza logica è "gratuita" se il ricevitore possiede le capacità di calcolo per ri-derivarla.
• Applicazioni: Il modello è rilevante per la compressione di basi di dati logici, sistemi di conoscenza, agenti intelligenti che comunicano tramite token semantici e scenari di comunicazione task-oriented dove l'obiettivo è preservare il significato (conseguenze) piuttosto che i dati grezzi.

In sintesi, il paper formalizza matematicamente come la logica e l'inferenza condivisa modifichino i limiti fondamentali della comunicazione, fornendo formule esatte per il tasso di compressione in presenza di ridondanza deduttiva.