Rate-Distortion Theory for Deductive Sources under Closure Fidelity

1. Planteamiento del Problema

El artículo aborda el problema de la compresión con pérdida de una fuente de información que no es un alfabeto plano de símbolos, sino una base de conocimientos finita ($S_O$) equipada con un sistema de prueba fijo y un operador de cierre deductivo ($Cn(\cdot)$).

• Contexto: En la teoría de la información clásica, la fidelidad se mide mediante la igualdad símbolo a símbolo (distorsión de Hamming). Sin embargo, en entornos deductivos (como bases de datos lógicas o sistemas de conocimiento), si el receptor puede reconstruir las mismas consecuencias deductivas a partir de una representación diferente, la tarea de comunicación se ha completado exitosamente.
• Objetivo: Estudiar la compresión donde la fidelidad se mide por la preservación del cierre deductivo (Closure Fidelity) en lugar de la igualdad exacta de símbolos.
• Desafío Central: La fuente contiene redundancia intrínseca: algunos estados son premisas irredundantes (el "núcleo"), mientras que otros son consecuencias almacenadas que pueden rederivarse. El objetivo es cuantificar cuánto se puede reducir la tasa de transmisión aprovechando esta estructura inferencial compartida.

2. Metodología y Modelo

El autor formaliza el problema dentro de un marco de teoría de la información de Shannon, adaptado para fuentes estructuradas.

A. Modelo de Fuente Deductiva

• Definición: Una fuente deductiva es un par $(S_O, P_O)$, donde $S_O$ es una base de conocimientos finita y $P_O$ es una distribución de probabilidad sobre ella.
• Descomposición del Núcleo Irredundante: Dado un sistema de pruebas y un orden canónico, la fuente se descompone en:
  • Núcleo Irredundante ($A = \text{Atom}(S_O)$): El conjunto mínimo de premisas necesarias para generar todo el cierre deductivo de $S_O$. Se obtiene mediante un procedimiento determinista de eliminación de elementos que pueden derivarse de los demás.
  • Parte Redundante ($J = S_O \setminus A$): Consecuencias almacenadas que son deducibles a partir de $A$.
• Fidelidad de Clausura: La distorsión se define mediante la distancia de Jaccard entre los conjuntos de cierre deductivo de la fuente original y la reconstrucción. Si $Cn(S) = Cn(\hat{S})$, la distorsión es cero.

B. Distorsión y Restricciones

• Distorsión de Clausura ($d_{Cn}$): Una distorsión de un solo símbolo que penaliza la pérdida de consecuencias deductivas.
• Presupuesto de Inferencia Limitada: Se introduce un parámetro $\delta$ que limita el número de pasos de inferencia permitidos al decodificador. Esto crea una compensación entre la tasa, la distorsión y el retraso (tiempo de cómputo).

3. Contribuciones Clave

El artículo presenta cuatro contribuciones teóricas principales:

1. Formulación del Modelo de Fuente: Establece un problema de codificación de fuente de alfabeto finito donde la fidelidad es la preservación del cierre deductivo, desplazando el enfoque de arquitecturas semánticas específicas a un objeto de teoría de la información a nivel de modelo de fuente.
2. Caracterización Exacta de Tasa Cero-Distorsión: Bajo una condición de disyunción (los conjuntos de reconstrucción de distorsión cero para símbolos del núcleo no se superponen), se demuestra que la tasa mínima es:
   $$R_{sem}(0) = P_A H(\pi_A)$$
   Donde $P_A$ es la masa de probabilidad del núcleo y $H(\pi_A)$ es la entropía de la distribución condicionada al núcleo. Esto implica que la parte redundante es "invisible" para la tasa en distorsión cero.
3. Descomposición de la Función Tasa-Distorsión: Se prueba que, para alfabetos de reconstrucción contenidos en el cierre deductivo, la función completa de tasa-distorsión depende únicamente del núcleo irredundante. La fuente completa se reduce a un problema clásico de tasa-distorsión sobre el núcleo, escalado por su masa de probabilidad.
4. Ley Exacta Tasa-Delayo-Distorsión: Para decodificadores con un presupuesto de inferencia limitado ($\delta$ pasos), se introduce el concepto de $\delta$-núcleo irredundante ($A_\delta$). Se deriva una ley exacta que interpola entre la compresión de símbolos clásica ($\delta=0$) y la compresión deductiva ilimitada ($\delta \to \infty$).

4. Resultados Principales

• Reducción de la Complejidad Efectiva: La complejidad efectiva de la fuente bajo fidelidad de clausura está gobernada exclusivamente por el núcleo irredundante ($A$), no por el tamaño total de la base de conocimientos almacenada ($S_O$).
• Ganancia de Compresión: En el caso de una fuente uniforme, la tasa de distorsión cero bajo clausura es $R_{sem}(0) = \frac{|A|}{|S_O|} \log |A|$, que es estrictamente menor que la tasa clásica de Hamming $H(P_O) = \log |S_O|$ siempre que exista redundancia ($J \neq \emptyset$).
• Separación Fuente-Canal: Se demuestra que el principio de separación fuente-canal clásico se mantiene válido para estas fuentes estructuradas, siempre que la tasa de codificación de fuente (basada en el núcleo) sea menor que la capacidad del canal.
• Límites de Converse Adaptados: Se derivan cotas inferiores (tipo Fano) que utilizan la entropía del núcleo ($P_A H(\pi_A)$) en lugar de la entropía total de la fuente, proporcionando límites más ajustados que los métodos clásicos.
• Extensión a Receptores Heterogéneos: Se analiza el caso donde el receptor tiene un vocabulario restringido. La tasa cero-distorsión se mantiene inalterada siempre que cada símbolo del núcleo tenga al menos un representante en el vocabulario del receptor que preserve el cierre deductivo.

5. Significado e Impacto

• Cambio de Paradigma: El trabajo demuestra que la estructura de inferencia compartida puede tratarse como un recurso que reduce la tasa de comunicación. La redundancia deductiva no es un desperdicio, sino una oportunidad de compresión que el receptor puede explotar mediante el razonamiento.
• Puente entre Lógica e Información: Conecta la teoría de la información clásica con la lógica deductiva y la teoría de bases de datos (específicamente Datalog y Horn-clauses), ofreciendo un marco matemático riguroso para la "comunicación semántica".
• Aplicaciones Prácticas: Los resultados son relevantes para:
  • Compresión de bases de conocimientos y ontologías.
  • Sistemas de preguntas y respuestas donde la respuesta exacta no es necesaria si se puede inferir.
  • Comunicaciones en entornos con recursos computacionales limitados (trade-off entre ancho de banda y capacidad de inferencia).
• Limitaciones y Futuro: El modelo actual asume una condición de disyunción en los conjuntos de reconstrucción de distorsión cero. El artículo identifica la eliminación de esta suposición (para manejar casos de "confusión" en el núcleo) como el siguiente paso teórico necesario, sugiriendo una conexión futura con la entropía de grafos.

En resumen, el artículo cuantifica fundamentalmente cómo la capacidad de re-derivar información en el receptor reduce los límites fundamentales de la comunicación, transformando la redundancia deductiva en ahorros de tasa medibles y exactos.