La compilación de conocimiento es una familia de enfoques en inteligencia artificial que aborda la intratabilidad computacional del razonamiento con modelos proposicionales. En lugar de responder consultas directamente sobre un modelo potencialmente complejo, el modelo se transforma en una fase fuera de línea en una representación compilada que soporta consultas específicas en tiempo polinomial. Este proceso de dos etapas - compilación seguida de respuesta a consultas - intercambia esfuerzo computacional inicial por una inferencia más rápida y predecible en tiempo de ejecución.
El desafío central radica en elegir una representación compilada adecuada, ya que diferentes representaciones ofrecen diferentes compensaciones. Las tres propiedades principales que caracterizan una representación compilada son su compacidad (cuán sucintamente representa el modelo original), el conjunto de consultas que soporta en tiempo polinomial y las transformaciones que se pueden realizar sobre ella en tiempo polinomial. Ninguna representación única sobresale en las tres, por lo que los profesionales seleccionan una representación basándose en las consultas que necesitan responder y las restricciones de tamaño de su aplicación.
Clases de Representaciones
Las representaciones compiladas se dividen en varias categorías amplias. Las clases de diagramas incluyen árboles de decisión, diagramas de decisión binarios ordenados (OBDDs), diagramas de decisión binarios libres (FBDDs), OBDDs no deterministas y diagramas de decisión multivaluados (MDDs). Estas estructuras gráficas representan funciones booleanas como grafos acíclicos dirigidos, donde cada camino corresponde a una asignación de variables.
Las clases de fórmulas incluyen la forma normal disyuntiva (DNF) y la forma normal conjuntiva (CNF). Mientras que la CNF es un formato de entrada común para muchas tareas de razonamiento, no soporta todas las consultas de manera eficiente, lo que motiva la compilación en otras formas. Las clases de circuitos incluyen la forma normal de negación (NNF), la NNF descomponible (DNNF), la DNNF determinista (d-DNNF) y los diagramas de decisión sentenciales (SDD). Estos circuitos imponen restricciones estructurales que habilitan operaciones en tiempo polinomial para ciertas consultas, como la verificación de consistencia o el conteo de modelos.
Compiladores de Conocimiento
Se han desarrollado varias herramientas de software para realizar la compilación de conocimiento automáticamente. El compilador c2d soporta la compilación a d-DNNF, una representación que permite el conteo de modelos y la verificación de consistencia en tiempo polinomial. El compilador d4 también apunta a d-DNNF y es conocido por su eficiencia en instancias grandes. miniC2D compila a SDD, una representación más reciente que soporta un rango más amplio de consultas y transformaciones. KCBox soporta la compilación a OBDD, OBDD[AND] y CCDD, ofreciendo flexibilidad entre diferentes clases de diagramas.
Estos compiladores se utilizan en aplicaciones como el razonamiento probabilístico, la planificación y la gestión de configuración, donde se requiere responder consultas repetidamente. Al compilar un modelo una vez, los sistemas pueden responder muchas consultas rápidamente, lo cual es crítico en entornos de tiempo real o interactivos.
Compensaciones y Criterios de Selección
La elección de una representación compilada depende de los requisitos específicos de la aplicación. Por ejemplo, los OBDDs son compactos para muchas funciones prácticas y soportan pruebas de equivalencia en tiempo polinomial, pero pueden explotar exponencialmente para algunas funciones. DNNF y d-DNNF son más sucintos en general pero soportan menos consultas. SDD ofrece un punto intermedio, soportando tanto el conteo de modelos como el condicionamiento en tiempo polinomial mientras mantiene propiedades estructurales que facilitan la compilación.
Las transformaciones también importan. Algunas aplicaciones requieren modificar la representación compilada, como condicionar sobre evidencia o conjuntar con restricciones adicionales. Las representaciones que soportan estas transformaciones en tiempo polinomial son preferidas en entornos dinámicos, incluso si son menos compactas que las alternativas.
Relación con el Aprendizaje Automático
La compilación de conocimiento es conceptualmente distinta del aprendizaje automático y el aprendizaje profundo, que se centran en aprender patrones a partir de datos en lugar de transformar modelos lógicos. Sin embargo, las representaciones compiladas se han explorado como una forma de hacer que los modelos aprendidos sean más interpretables o de integrar el razonamiento simbólico con enfoques neuronales. Por ejemplo, los diagramas de decisión se pueden utilizar para representar los límites de decisión de una red neuronal entrenada en una forma que soporte la verificación formal.
Trabajos recientes también han examinado conexiones con el razonamiento de modelos de lenguaje grandes, donde las bases de conocimiento compiladas podrían proporcionar conocimiento de fondo estructurado para aumentar los modelos generativos. Aunque estos esfuerzos aún son incipientes, destacan la relevancia continua de la compilación de conocimiento como una herramienta para unir la IA simbólica y la subsimbólica.
Direcciones Actuales
La investigación en compilación de conocimiento continúa centrándose en desarrollar nuevas clases de representaciones con mejores compensaciones, mejorar la escalabilidad de los compiladores y extender la compilación a lenguajes lógicos más ricos más allá de la lógica proposicional. También hay interés en aprender representaciones compiladas directamente de los datos, lo que difuminaría la línea entre la compilación y el aprendizaje automático. A medida que los sistemas de IA crecen en complejidad, la capacidad de razonar eficientemente sobre conocimiento estructurado sigue siendo un desafío crítico, y la compilación de conocimiento ofrece un marco principista para abordarlo.
Referencias
- Darwiche, A., & Marquis, P. (2002). A knowledge compilation map. Journal of Artificial Intelligence Research, 17, 229-264.
- Huang, J., & Darwiche, A. (2007). On compiling system models to faster SAT solvers. In Proceedings of the National Conference on Artificial Intelligence.
- Muise, C., McIlraith, S., Beck, J. C., & Hsu, E. (2012). Dsharp: Fast d-DNNF compilation with sharpSAT. In Canadian Conference on Artificial Intelligence.