Programação em Lógica Indutiva Através de Algoritmo Estimador de Distribuição e Claúsula Mais Específica
Autores
|
5400 |
1978,250
|
|
|
5401 |
1978,250
|
Informações:
Publicações do PESC
De forma geral, Programação em Lógica Indutiva (ILP) é uma área da Inteligência Artificial que investiga a construção indutiva de teorias de cláusulas de Horn, de primeira-ordem, a partir de exemplos e de um conhecimento preliminar. A construção de teorias de cláusulas de Horn é uma tarefa de acentuada dificuldade devido ao extenso tamanho do espaço de busca, e, dessa forma, os Algoritmos Genéticos (AGs) foram, em certa extensão, aplicados a tal problema. Por sua vez, os Algoritmos Estimadores de Distribuição (AEDs), embora obtenham, na maioria das vezes, resultados superiores quando comparados aos AGs tradicionais, não foram ainda aplicados à ILP. Este trabalho apresenta o AED-ILP, um sistema ILP baseado em AEDs e em implicação inversa, bem como suas (duas) extensões, a saber: o RAED-ILP, que emprega o algoritmo Reduce para reduzir seu espaço de busca, e o HAED-ILP, que usa uma abordagem de busca completamente nova para desenvolver suas teorias. Resultados experimentais em problemas do mundo real mostram que os sistemas obtêm grande êxito em relação ao sistema Aleph (considerado estado da arte) bem como em relação ao AG-ILP (outra variante do AED-ILP criada pela substituição do AED no AED-ILP, por um AG padrão). Em problemas artificiais de Transição de Fase, o AED- ILP também obteve grande êxito quando comparado ao sistema Progol (e suas variantes). Adicionalmente, verificou-se que a variante do AED-ILP, o RAED-ILP, obtém, de forma mais eficiente, teorias mais simples e tão acuradas quanto às do AED- ILP, enquanto que o HAED-ILP é capaz de obter teorias significativamente mais acuradas e em tempo computacional competitivo quando comparado ao Aleph, AED-ILP, e RAED-ILP, e claramente supera o sistema AG-ILP.
In general, Inductive Logic Programming (ILP) is an area of artificial intelligence which investigates the inductive construction of theories of Horn clauses of first-order logic from examples and a preliminary knowledge. Constructing theories of Horn clauses is a task of considerable difficulty due to the extensive size of the search space, thus, Genetic Algorithms (GAs) have been, to some extent, applied to such problem. In turn, although Estimation of Distribution Algorithms (EDAs) generally perform better than the standard GAs, they have not been applied to ILP. This work presents EDA-ILP, an ILP system based on EDA and inverse entailment, and also its extensions, REDA-ILP, which employs the Reduce algorithm in bottom clauses to considerably reduce the search space, and HEDA-ILP, which uses a new hybrid approach to develop its theories. Experiments in real-world datasets show that the proposed systems were successfully evaluated against the standard ILP system Aleph, and GA-ILP (another variant of EDA-ILP created by replacing the EDA by a standard GA). EDA-ILP was also successfully compared to Progol-QG/GA (and its other variants) in phase transition benchmarks. Additionally, we find that REDA-ILP usually obtains simpler theories than EDA-ILP, more efficiently and with equivalent accuracies, while HEDA-ILP finds significantly more accurate theories, in competitive computational time, when compared to Aleph, EDA-ILP, and REDA-ILP, while clearly outperforming GA-ILP.