Compilação de conhecimento é uma família de abordagens em inteligência artificial que aborda a intratabilidade computacional do raciocínio com modelos proposicionais. Em vez de responder consultas diretamente em um modelo potencialmente complexo, o modelo é transformado em uma fase off-line em uma representação compilada que suporta consultas específicas em tempo polinomial. Esse processo de duas etapas - compilação seguida de resposta a consultas - troca esforço computacional inicial por inferência mais rápida e previsível em tempo de execução.
O desafio central está em escolher uma representação compilada apropriada, pois diferentes representações oferecem diferentes trade-offs. As três principais propriedades que caracterizam uma representação compilada são sua compactação (quão sucintamente ela representa o modelo original), o conjunto de consultas que ela suporta em tempo polinomial e as transformações que podem ser realizadas nela em tempo polinomial. Nenhuma representação única se destaca em todas as três, então os profissionais selecionam uma representação com base nas consultas que precisam responder e nas restrições de tamanho de sua aplicação.
Classes de Representações
Representações compiladas se enquadram em várias categorias amplas. Classes de diagramas incluem árvores de decisão, diagramas de decisão binários ordenados (OBDDs), diagramas de decisão binários livres (FBDDs), OBDDs não determinísticos e diagramas de decisão multivalorados (MDDs). Essas estruturas gráficas representam funções booleanas como grafos acíclicos direcionados, onde cada caminho corresponde a uma atribuição de variáveis.
Classes de fórmulas incluem forma normal disjuntiva (DNF) e forma normal conjuntiva (CNF). Embora CNF seja um formato de entrada comum para muitas tarefas de raciocínio, ela não suporta todas as consultas de forma eficiente, o que motiva a compilação em outras formas. Classes de circuitos incluem forma normal de negação (NNF), NNF decomponível (DNNF), DNNF determinística (d-DNNF) e diagramas de decisão sentenciais (SDD). Esses circuitos impõem restrições estruturais que permitem operações em tempo polinomial para certas consultas, como verificação de consistência ou contagem de modelos.
Compiladores de Conhecimento
Várias ferramentas de software foram desenvolvidas para realizar compilação de conhecimento automaticamente. O compilador c2d suporta compilação para d-DNNF, uma representação que permite contagem de modelos e verificação de consistência em tempo polinomial. O compilador d4 também tem como alvo d-DNNF e é conhecido por sua eficiência em instâncias grandes. miniC2D compila para SDD, uma representação mais recente que suporta uma gama mais ampla de consultas e transformações. KCBox suporta compilação para OBDD, OBDD[AND] e CCDD, oferecendo flexibilidade entre diferentes classes de diagramas.
Esses compiladores são usados em aplicações como raciocínio probabilístico, planejamento e gerenciamento de configuração, onde é necessária resposta repetida a consultas. Ao compilar um modelo uma vez, os sistemas podem responder muitas consultas rapidamente, o que é crítico em ambientes de tempo real ou interativos.
Trade-offs e Critérios de Seleção
A escolha de uma representação compilada depende dos requisitos específicos da aplicação. Por exemplo, OBDDs são compactos para muitas funções práticas e suportam teste de equivalência em tempo polinomial, mas podem crescer exponencialmente para algumas funções. DNNF e d-DNNF são mais sucintos em geral, mas suportam menos consultas. SDD oferece um meio-termo, suportando tanto contagem de modelos quanto condicionamento em tempo polinomial, mantendo propriedades estruturais que facilitam a compilação.
Transformações também importam. Algumas aplicações exigem modificar a representação compilada, como condicionar em evidências ou conjugar com restrições adicionais. Representações que suportam essas transformações em tempo polinomial são preferidas em ambientes dinâmicos, mesmo que sejam menos compactas que alternativas.
Relação com Aprendizado de Máquina
Compilação de conhecimento é conceitualmente distinta de aprendizado de máquina e aprendizado profundo, que focam em aprender padrões a partir de dados em vez de transformar modelos lógicos. No entanto, representações compiladas foram exploradas como uma forma de tornar modelos aprendidos mais interpretáveis ou de integrar raciocínio simbólico com abordagens neurais. Por exemplo, diagramas de decisão podem ser usados para representar as fronteiras de decisão de um rede neural treinado em uma forma que suporta verificação formal.
Trabalhos recentes também examinaram conexões com raciocínio de modelos de linguagem de grande escala, onde bases de conhecimento compiladas poderiam fornecer conhecimento de fundo estruturado para aumentar modelos generativos. Embora esses esforços ainda estejam em estágio inicial, eles destacam a relevância contínua da compilação de conhecimento como uma ferramenta para unir IA simbólica e subsimbólica.
Direções Atuais
A pesquisa em compilação de conhecimento continua focando no desenvolvimento de novas classes de representação com melhores trade-offs, na melhoria da escalabilidade dos compiladores e na extensão da compilação para linguagens lógicas mais ricas além da lógica proposicional. Há também interesse em aprender representações compiladas diretamente a partir de dados, o que borraria a linha entre compilação e aprendizado de máquina. À medida que os sistemas de IA se tornam mais complexos, a capacidade de raciocinar eficientemente sobre conhecimento estruturado permanece um desafio crítico, e a compilação de conhecimento oferece uma estrutura principiada para abordá-lo.
Referências
- 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.