Revision of Probabilistic Relational Theories through Examples with Predicate Invention

• Kate Revoredo UFRJ
• Gerson Zaverucha UFRJ

Abstract

The majority of machine learning algorithms use only the vocabulary explicitly supplied in the data for model construction. However, automatic extension of this vocabulary, with new structures that represent implicit information on objects of the domain, can enrich the learning. On the other hand, an initial model approximately correct can be provided to the learning algorithms. Therefore, a particular case of learning, called theory revision, which minimally modifies the structure of the model to correctly reflect the database, can be applied. This article investigates the benefits of vocabulary extension when applying theory revision techniques to probabilistic models. This proposal was applied successfully to artificial and realistic databases.

References

De Raedt, L., Kersting, K., Kimmig, A., Revoredo, K., and Toivonen, H. (2008). Compressing probabilistic prolog programs. Machine Learning, 70(2-3):151–168.

De Raedt, L., Kimmig, A., and Toivonen, H. (2007). Problog: A probabilistic prolog and its application in link discovery. In Proc. IJCAI-2007, pages 2462–2467.

Friedman, N. (1997). Learning belief networks in the presence of missing values and hidden variables. In 14th Int. Conference on Machine Learning, pages 1252–133.

Friedman, N. (1998). The bayesian structural EM algorithm. In UAI, pages 129–138.

Kersting, K. and De Raedt, L. (2002). Basic principles of learning bayesian logic programs. Technical Report 174, Univ. of Freiburg, Inst. for Computer Science, German.

Kohavi, R. (1995). A study of cross-validation and bootstrap for accuracy estimation and model selection. In Proc. of the IJCAI, pages 1137–1145.

Kramer, S. (1995). Predicate invention: A comprehensive view. Technical Report ÖFAITR-95-32, Austrian Research Institute for Artificial Intelligence.

Mitchell, T. (1997). Machine Learning. McGraw-Hill, New York.

Muggleton, S. (1992). Inductive logic programming. McGraw-Hill, New York.

Nadeau, C. and Bengio, Y. (2003). Inference for the generalization error. Machine Learning, 52(3):239–281.

Paes, A., Revoredo, K., Zaverucha, G., and Costa, V. S. (2005a). Further experimental results of probabilistic first-order revision of theories from exampes. In 4th Workshop on Multi-Relational Data Mining / The Eleventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, page 59, Chicago, Illinois. ACM Press.

Paes, A., Revoredo, K., Zaverucha, G., and Costa, V. S. (2005b). Probabilistic first-order theory revision from examples. In Proceedings of the 15th International Conference on Inductive Logic Programming, volume 3625 of LNAI, pages 295–311. Springer.

Paes, A., Revoredo, K., Zaverucha, G., and Costa, V. S. (2006). Pforte: Revising probabilistic fol theories. In Proceedings of the 18th Brazilian AI Symposium (SBIA-06), volume 4140 of LNAI, pages 441–450. Springer.

Revoredo, K. (2009). Revisão de Teorias Relacionais Probabilísticas através de Exemplos com Invenção de Predicados. PhD thesis, COPPE-Sistemas/UFRJ. [link].

Revoredo, K., Paes, A., Zaverucha, G., and Costa, V. S. (2006). Combining predicate invention and revision of probabilistic fol theories. In Short paper proceedings of 16th International Conference on Inductive Logic Programming (ILP-06), pages 176–178.

Revoredo, K., Paes, A., Zaverucha, G., and Costa, V. S. (2007). Combinando invenção de predicados e revisão de teorias de primeira-ordem probabilísticas. In VI ENIA.

Revoredo, K., Paes, A., Zaverucha, G., and Costa, V. S. (2009). Revisando redes bayesianas através da introdução de variáveis não-observadas. In VII ENIA.

Srinivasan, A. (2001). The Aleph Manual.