Utilizando a Cláusula Mais Específica e Declaração de Modos de Revisão de Teorias de Primeira Ordem a Partir de Exemplos
Autores
|
6160 |
2588,250
|
|
|
6161 |
2588,250
|
Informações:
Publicações do PESC
Sistemas de revisão de teorias são desenvolvidos para melhorar a acurácia de uma teoria inicial dada, tornando-as mais acuradas e compreensíveis do que as geradas por métodos puramente indutivos. Estes sistemas partem da teoria inicial fornecida e a modifica nos pontos onde há uma falha na classificação dos exemplos. Uma das modificações possíveis é a adição de antecedentes à cláusula sendo revisada. Um conhecido sistema de revisão de teorias é o FORTE, cuja operação de adição de antecedentes é baseada no FOIL, e considera todos os literais da base de conhecimento como possíveis antecedentes a serem adicionados na cláusula. Tal fato acarreta em um espaço de busca muito grande, o que domina o custo do processo de revisão. O estado da arte dos algoritmos de aprendizado em ILP restringem a busca de antecedentes aos literais relevantes para um determinado exemplo positivo. Tais literais compõem a cláusula mais específica, gerada por uma busca direcionada a modos. Visando melhorar a eficiência da operação de adição de antecedentes no FORTE, propomos a utilização da cláusula mais específica como espaço de busca de antecedentes, e a declaração de modos para validar os literais da cláusula mais específica sendo adicionados à cláusula revisada. Resultados experimentais mostram que o processo de revisão passou a ser três ordens de magnitude mais rápido do que o que é feito no FORTE, e teorias mais compreensíveis foram geradas sem prejuízo da acurácia. A abordagem proposta também melhora significativamente a acurácia de teorias geradas a partir do sistema Aleph, o mais utilizado sistema de ILP.
Theory revision systems are designed to improve the accuracy of an initial theory, producing more accurate and comprehensible theories than purely inductive methods. Such systems start from an initial theory and modify it on points where some example is misclassified. One of the possible modifications is the addition of antecedents to the clause been revised. A known theory revision system is FORTE. The adding antecedents operation of FORTE is based on FOIL, and therefore considere a11 the literals of background knowledge as possible antecedents to be added to the the clause. This fact implies in a huge search space which dominates the cost of the revision process. The state of the art of learning algorithms in ILP restrict the search of antecedents to literals that are relevant to a positive example. These literals form the most specif clause, which is generated through a mode directed search. Aiming to impove the efficiency of the antecedent adding operation in FORTE, we propose the use of the most specif clause as antecedent search space. Besides that, we also propose the use of modes to define which literals of the most specif clause can effectively be added to the clause been revised. Experimental results show that the runtime of the revision process is on average three orders of magnitude faster than the one that is done on FORTE, and generate more comprehensible theories without decreasing the accuracy. The proposed approach also significantly improves predictive accuracy over theories generated by Aleph system, the most used system in ILP.