Revisando Teorias Lógicas de Primeira-ordem a partir de Exemplos usando Busca Local Estocástica
Resumo
Revisão de teorias lógicas de Primeira-ordem (LPO) é o processo de melhorar teorias geradas automaticamente ou definidas pelo usuário, dado um conjunto de exemplos. A utilização de sistemas de revisão de teorias tem sido limitada pelo custo de buscar em um grande espaço de hipóteses. Esta é uma dificuldade geral no aprendizado de teorias LPO, mas trabalhos recentes mostram que técnicas de busca local estocástica (SLS) são efetivas ao menos quando as teorias são aprendidas a partir do zero. Motivados por estes resultados, propomos neste artigo estratégias de busca baseadas em SLS para revisar teorias LPO a partir de exemplos. Resultados experimentais mostram que utilizar SLS conduz a um tempo de execução melhor sem diminuir a acurácia.Referências
Bratko, I. (1999). Refining complete hypotheses in ILP. In Proc. of the 9th ILP, volume 1634 of LNAI, pages 44–55. Springer.
Chisholm, M. and Tadepalli, P. (2002). Learning decision rules by randomized iterative local search. In Proc. of the 19th ICML, pages 75–82.
Dietterich, T. (1998). Approximate statistical tests for comparing supervised classification learning algorithms. Neural Computation, 10:1895–1924.
Paes, A., Železný, F., Zaverucha, G., Page, D., and Srinivasan, A. (2007). Ilp through propositionalization and stochastic k-term DNF learning. In to appear in Proc. of the 16th ILP, volume 4455 of LNAI. Springer.
Richards, B. L. and Mooney, R. J. (1995). Automated refinement of first-order horn-clause domain theories. Machine Learning, 19(2):95–131.
Rückert, U. and Kramer, S. (2003). Stochastic local search in k-term DNF learning. In Proc. of the 20th ICML, pages 648–655.
Selman, B., Kautz, H. A., and Cohen, B. (1996). Local search strategies for satisfiability testing. Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11-13, 1993. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 26:521–532.
Selman, B., Levesque, H. J., and Mitchell, D. G. (1992). A new method for solving hard satisfiability problems. In Proc. of the 10th AAAI, pages 440–446.
Srinivasan, A. (2001). The Aleph Manual. [link].
Srinivasan, A., Muggleton, S., Sternberg, M. J. E., and King, R. D. (1996). Theories for mutagenicity: A study in first-order and feature-based induction. Artificial Intelligence, 85(1-2):277–299.
Železný, F., Srinivasan, A., and Page, D. (2006). Randomised restarted search in ILP. Machine Learning, 64(1-3):183–208.
Wogulis, J. and Pazzani, M. (1993). A methodology for evaluationg theory revision systems: results with Audrey II. In Proc. of 13th IJCAI, pages 1128–1134.
Wrobel, S. (1996). First-order theory refinement. In Raedt, L. D., editor, Advances in Inductive Logic Programming, pages 14–33. IOS Press.
Chisholm, M. and Tadepalli, P. (2002). Learning decision rules by randomized iterative local search. In Proc. of the 19th ICML, pages 75–82.
Dietterich, T. (1998). Approximate statistical tests for comparing supervised classification learning algorithms. Neural Computation, 10:1895–1924.
Paes, A., Železný, F., Zaverucha, G., Page, D., and Srinivasan, A. (2007). Ilp through propositionalization and stochastic k-term DNF learning. In to appear in Proc. of the 16th ILP, volume 4455 of LNAI. Springer.
Richards, B. L. and Mooney, R. J. (1995). Automated refinement of first-order horn-clause domain theories. Machine Learning, 19(2):95–131.
Rückert, U. and Kramer, S. (2003). Stochastic local search in k-term DNF learning. In Proc. of the 20th ICML, pages 648–655.
Selman, B., Kautz, H. A., and Cohen, B. (1996). Local search strategies for satisfiability testing. Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11-13, 1993. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 26:521–532.
Selman, B., Levesque, H. J., and Mitchell, D. G. (1992). A new method for solving hard satisfiability problems. In Proc. of the 10th AAAI, pages 440–446.
Srinivasan, A. (2001). The Aleph Manual. [link].
Srinivasan, A., Muggleton, S., Sternberg, M. J. E., and King, R. D. (1996). Theories for mutagenicity: A study in first-order and feature-based induction. Artificial Intelligence, 85(1-2):277–299.
Železný, F., Srinivasan, A., and Page, D. (2006). Randomised restarted search in ILP. Machine Learning, 64(1-3):183–208.
Wogulis, J. and Pazzani, M. (1993). A methodology for evaluationg theory revision systems: results with Audrey II. In Proc. of 13th IJCAI, pages 1128–1134.
Wrobel, S. (1996). First-order theory refinement. In Raedt, L. D., editor, Advances in Inductive Logic Programming, pages 14–33. IOS Press.
Publicado
30/06/2007
Como Citar
PAES, Aline; ZAVERUCHA, Gerson; COSTA, Vítor Santos.
Revisando Teorias Lógicas de Primeira-ordem a partir de Exemplos usando Busca Local Estocástica. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 6. , 2007, Rio de Janeiro/RJ.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2007
.
p. 1252-1261.
ISSN 2763-9061.
