Cost-Based Semantics for Querying Inconsistent Weighted Knowledge Bases

Resumen Técnico: Semántica Basada en Costos para la Consulta de Bases de Conocimiento Ponderadas Inconsistentes

Planteamiento del Problema
La respuesta a consultas mediada por ontologías (OMQA) se basa en bases de conocimiento (KB) de Lógica de Descripción (DL) que consisten en una TBox (ontología) y una ABox (datos). La semántica clásica de OMQA, basada en la lógica de primer orden, no logra proporcionar respuestas informativas cuando la KB es inconsistente, ya que todo se deduce de una contradicción. Si bien los enfoques existentes manejan la inconsistencia mediante reparaciones (por ejemplo, AR y semántica brave), estos típicamente asumen que la TBox es fiable y solo modifican la ABox. Además, las semánticas de reparación estándar suelen tratar todas las aserciones como igualmente fiables o dependen de la maximalidad basada en la cardinalidad, careciendo de una forma matizada de priorizar la información conflictiva basándose en distintos grados de confianza.

Este artículo aborda el desafío de consultar KBs de DL inconsistentes mediante la introducción de un marco cuantitativo. El problema central es definir respuestas ciertas y posibles significativas cuando tanto los axiomas de la TBox como las aserciones de la ABox pueden ser violados, con violaciones penalizadas según los pesos asignados.

Metodología y Marco de Trabajo
Los autores proponen un marco de Base de Conocimiento Ponderada (WKB), denotado como $K_\omega = (\langle \mathcal{T}, \mathcal{A} \rangle, \omega)$.

• Pesos: Una función de costo $\omega$ asigna un valor en $\mathbb{N}_{>0} \cup \{+\infty\}$ a cada axioma en $\mathcal{T}$ y aserción en $\mathcal{A}$. Los pesos infinitos representan restricciones "duras" que deben satisfacerse, mientras que los pesos finitos representan restricciones "blandas" donde valores más altos indican una mayor fiabilidad.
• Costo de la Interpretación: El costo de una interpretación $I$ se define como la suma de los pesos de todos los axiomas y aserciones violados. Específicamente, para una inclusión de concepto $\tau$, el costo incluye $\omega_\tau \times |vio_\tau(I)|$, donde $vio_\tau(I)$ es el conjunto de elementos del dominio que violan la inclusión. Las aserciones pueden ser violadas como máximo una vez.
• Semántica: El artículo define cuatro semánticas de entailment (implicación) de consulta basadas en el costo de las interpretaciones:
  1. Cierta con límite de costo $k$ ($K_\omega \models^k_c q$): $q$ se cumple en todas las interpretaciones con costo $\le k$.
  2. Posible con límite de costo $k$ ($K_\omega \models^k_p q$): $q$ se cumple en al menos una interpretación con costo $\le k$.
  3. Cierta de costo óptimo ($K_\omega \models^{opt}_c q$): $q$ se cumple en todas las interpretaciones con costo mínimo ($optc(K_\omega)$).
  4. Posible de costo óptimo ($K_\omega \models^{opt}_p q$): $q$ se cumple en al menos una interpretación con costo mínimo.

El marco generaliza las semánticas de reparación existentes. Específicamente, cuando los axiomas de la TBox tienen pesos infinitos, la semántica de ciertaza de costo óptimo coincide con la semántica $\le_\omega$-AR (Bienvenu, Bourgaux y Goasdoué 2014), que selecciona reparaciones que maximizan la suma de los pesos de las aserciones retenidas.

Contribuciones Clave
La contribución principal es un análisis exhaustivo de la complejidad combinada y de datos de los principales problemas de decisión en este entorno:

1. Satisfacibilidad de Costo Acotado (BCS): Determinar si existe una interpretación con costo $\le k$.
2. Reconocimiento de Respuestas Ciertas y Posibles: Decidir la implicación bajo las cuatro semánticas definidas.

El estudio cubre un rango de Lógicas de Descripción desde la ligera $\mathcal{EL}^\bot$ hasta la expresiva $\mathcal{ALCO}$ (y $\mathcal{ALCO}^\mathcal{Q}$ para las pruebas de cota superior), manejando tanto Consultas de Instancia (IQs) como Consultas Conjuntivas (CQs).

Resultados de Complejidad
El artículo establece límites de complejidad ajustados, resumidos de la siguiente manera:

• Complejidad Combinada:

  • La mayoría de los problemas son EXPTIME-completos.
  • El reconocimiento de respuestas ciertas para CQs (tanto acotadas como de costo óptimo) es 2EXPTIME-completo. Esta alta complejidad surge de la necesidad de verificar la implicación a través de todos los modelos de un costo específico, lo cual se relaciona con las KBs circunscritas.
  • Estos límites se mantienen incluso cuando los pesos y el límite de costo $k$ están codificados en binario.

• Complejidad de Datos:

  • Satisfacibilidad de Costo Acotado (BCS): NP-completo.
  • Respuesta de Costo Acotado (IQs/CQs): NP-completo (posible) y coNP-completo (cierta).
  • Respuesta de Costo Óptimo: La complejidad depende fuertemente de la codificación de los pesos:
    • Si los pesos se codifican en unario o están acotados independientemente del tamaño de la ABox, los problemas son $\Theta^p_2$-completos (resolubles en tiempo polinomial con llamadas logarítmicas a un oráculo NP).
    • Si los pesos se codifican en binario y pueden ser exponenciales respecto al tamaño de la ABox, los problemas se vuelven $\Delta^p_2$-completos (resolubles en tiempo polinomial con acceso a un oráculo NP).
  • El artículo señala que para la semántica de respuesta cierta de costo óptimo con pesos binarios, el límite superior permanece abierto, aunque los límites inferiores son $\Delta^p_2$-duros.

Significancia y Reivindicaciones
Los autores afirman proporcionar una "imagen casi completa" del panorama de la complejidad para las consultas de KBs inconsistentes bajo una semántica basada en costos. La significancia del trabajo radica en:

1. Flexibilidad Cuantitativa: Ir más allá de la consistencia binaria hacia un enfoque graduado donde las respuestas pueden ser clasificadas o filtradas según su "robustez" (es decir, si se cumplen en interpretaciones cercanas al costo óptimo).
2. Generalización: Unificar conceptos de restricciones blandas en bases de datos (Carmeli et al. 2021) y reparaciones ponderadas en ontologías, mostrando que las semánticas de costo óptimo generalizan naturalmente las semánticas de reparación preferidas.
3. Profundidad Técnica: Las pruebas de complejidad aprovechan y adaptan técnicas avanzadas de razonamiento en DL, incluyendo:
   • Filtración y propiedades de modelos acotados para establecer cotas superiores.
   • Reducciones de respuesta a consultas de cardinalidad y KBs circunscritas para establecer cotas inferiores.
   • Adaptaciones de construcciones de "entrelazado" (interlacing) y "cociente" de la literatura de consultas de conteo (Manière 2022) para manejar las restricciones específicas de las violaciones ponderadas.

El artículo concluye identificando direcciones futuras, específicamente la extensión de estos resultados a DL con roles inversos, inclusiones de roles y roles funcionales (por ejemplo, la familia DL-Lite), señalando que las técnicas actuales para las cotas superiores no se transfieren fácilmente a estos constructos. También destaca el desafío de desarrollar algoritmos prácticos para su implementación.