A General Similarity Framework for Horn Clause Logic

• Autorzy: Ferilli S. , Basile T.M.A. , Biba M. , Di Mauro N. , Esposito F.
• Języki publikacji: EN

Abstrakty

EN

First-Order Logic formulć are a powerful representation formalism characterized by the use of relations, that cause serious computational problems due to the phenomenon of indeterminacy (various portions of one description are possibly mapped in different ways onto another description). Being able to identify the correct corresponding parts of two descriptions would help to tackle the problem: hence, the need for a framework for the comparison and similarity assessment. This could have many applications in Artificial Intelligence: guiding subsumption procedures and theory revision systems, implementing flexible matching, supporting instance-based learning and conceptual clustering. Unfortunately, few works on this subject are available in the literature. This paper focuses on Horn clauses, which are the basis for the Logic Programming paradigm, and proposes a novel similarity formula and evaluation criteria for identifying the descriptions components that are more similar and hence more likely to correspond to each other, based only on their syntactic structure. Experiments on real-world datasets prove the effectiveness of the proposal, and the efficiency of the corresponding implementation in the above tasks.

Słowa kluczowe

EN

first-order logic; Logic Programming (LP); Similarity/Distance Measures

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 90, nr 1-2
• Strony: 43--66
• Opis fizyczny: bibliogr. 32 poz., tab.

Twórcy

autor

Ferilli S.

autor

Basile T.M.A.

autor

Biba M.

autor

Di Mauro N.

autor

Esposito F.

• Dipartimento di Informatica Universita di Bari via E. Orabona, 4 - 70125 Bari, Italia,

Bibliografia

• [1] Biba, M., Esposito, F., Ferilli, S., Mauro, N. D., Basile, T. M. A.: Unsupervised Discretization Using Kernel Density Estimation., in: Veloso [31], 696-701.
• [2] Bisson, G.: Conceptual clustering in a first order logic representation, ECAI -92: Proceedings of the 10th European conference on Artificial intelligence, JohnWiley & Sons, Inc., 1992.
• [3] Bisson, G.: Learning in FOL with a similarity measure, Proc. of AAAI-92 (W. Swartout, Ed.), 1992.
• [4] Blockeel, H., Raedt, L. D., Ramon, J.: Top-down induction of clustering trees, Proceedings of the 15th International Conference on Machine Learning (J. Shavlik, Ed.), Morgan Kaufmann, 1998.
• [5] Bock, H.: Analysis of Symbolic Data: ExploratoryMethods for Extracting Statistical Information from Complex Data, Springer-Verlag, 1999.
• [6] Ceri, S., Gottlob, G., Tanca, L.: Logic Programming and Databases, Springer, 1990.
• [7] Domingos, P.: Rule induction and instance-based learning: a unified approach, Proc. of IJCAI-95, Morgan Kaufmann, 1995.
• [8] Emde, W., Wettschereck, D.: Relational instance based learning, Proc. of ICML-96 (L. Saitta, Ed.), 1996.
• [9] Esposito, F., Fanizzi, N., Ferilli, S., Semeraro, G.: A GeneralizationModel Based on OI-implication for Ideal Theory Refinement., Fundam. Inform., 47(1-2), 2001, 15-33.
• [10] Esposito, F., Ferilli, S., Fanizzi, N., Basile, T., Mauro, N. D.: Incremental Multistrategy Learning for Document Processing, Applied Artificial Intelligence Journal, 17(8/9), 2003, 859-883.
• [11] Esposito, F., Malerba, D., Semeraro, G.: Classification in Noisy Environments Using a Distance Measure Between Structural Symbolic Descriptions, IEEE Transactions on PAMI, 14(3), 1992, 390-402.
• [12] Ferilli, S., Basile, T., Mauro, N. D., Biba, M., Esposito, F.: Similarity-Guided Clause Generalization, AI*IA-2007: Artificial Intelligence and Human-Oriented Computing (R. Basili, M. Pazienza, Eds.), 4733, Springer, 2007.
• [13] Fisher, D. H.: Knowledge Acquisition Via Incremental Conceptual Clustering, Machine Learning, 2(2), 1987, 139-172.
• [14] Gennari, J. H., Langley, P., Fisher, D.: Models of incremental concept formation, Artificial Intelligence, 40(1-3), 1989, 11-61.
• [15] Jain, A. K., Murty, M. N., Flynn, P. J.: Data clustering: a review, ACM Computing Surveys, 31(3), 1999, 264-323.
• [16] Kodratoff, Y., Ganascia, J.-G.: Improving the Generalization Step in Learning, in: Machine Learning: An Artificial Intelligence Approach: Volume II (R. S. Michalski, J. G. Carbonell, T. M. Mitchell, Eds.), Kaufmann, Los Altos, CA, 1986, 215-244.
• [17] Li, M., Chen, X., Li, X., Ma, B., Vitanyi, P.: The similarity metric, 2003.
• [18] Lin, D.: An information-theoretic definition of similarity, Proc. 15th International Conf. on Machine Learning, Morgan Kaufmann, San Francisco, CA, 1998.
• [19] Lloyd, J. W.: Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, USA, 1987, ISBN 3-540-18199-7.
• [20] Michalski, R. S., Stepp, R. E.: Learning from Observation: Conceptual Clustering, in: Machine Learning: An Artificial Intelligence Approach (R. S. Michalski, J. G. Carbonell, T.M. Mitchell, Eds.), Springer: Berlin, 1984, 331-363.
• [21] Muggleton, S.: Inductive Logic Programming, New Generation Computing, 8(4), 1991, 295-318.
• [22] Nienhuys-Cheng, S.: Distances and limits on herbrand interpretations, Proc. of ILP-98 (D. Page, Ed.), 1446, Springer, 1998.
• [23] Plotkin, G. D.: A Note on Inductive Generalization, Machine Intelligence, 5, 1970, 153-163.
• [24] Ramon, J.: Clustering and instance based learning in first order logic, Ph.D. Thesis, Dept. of Computer Science, K.U.Leuven, Belgium, 2002.
• [25] Ramon, J., Dehaspe, L.: UpgradingBayesian Clustering to First Order Logic, Proceedings of the 9th Belgian-Dutch Conference on Machine Learning, Department of Computer Science, K.U.Leuven, 1999.
• [26] Rouveirol, C.: Extensions of Inversion of Resolution Applied to Theory Completion, in: Inductive Logic Programming, Academic Press, 1992, 64-90.
• [27] Sebag, M.: Distance Induction in first order logic, Proc. of ILP-97 (N. Lavra˘c, S. Džeroski, Eds.), 1297, Springer, 1997.
• [28] Srinivasan, A., Muggleton, S., King, R., Sternberg,M.: Mutagenesis: ILP experiments in a non-determinate biological domain, 1994.
• [29] Thompson, K., Langley, P.: Incremental concept formation with composite objects, Proceedings of the sixth international workshop on Machine learning,Morgan Kaufmann Publishers Inc., 1989.
• [30] Tversky, A.: Features of Similarity, Psychological Review, 84(4), 1977, 327-352.
• [31] Veloso, M. M., Ed.: IJCAI 2007, Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, January 6-12, 2007, 2007.
• [32] Wieczorek, S., Bisson, G., Gordon, M. B.: Guiding the Search in the NO Region of the Phase Transition Problem with a Partial Subsumption Test, Machine Learning: ECML 2006, 4212, Springer, 2006.