Probability, logic \ learning synthesis: formalizing prediction concept

S. O. Smerdov ; E. E. Vityaev

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 6 (2009), pp. 340-365.

Résumé

Presented paper is devoted to the question of prediction formalized in probabilistic and logical terms. The aim of investigation is to examine different methods such as based on SLD-inferences and alternative semantic approach. Prediction is introduced as a statement of abductive sort attained by inductive schemes. One of the significant problems concerns unregulated decrease of trusting estimations for regularities obtained during the process of inference organized by analogy with syntax logical systems. Suggested semantic approach generalizes the notion of inference and reveals essential advantages in many aspects without assuming rather strong constraints. In particular, a special set of probabilistic laws is synthesized inductively, this collection has an optimal ability to predict (in the context of available data). Semantic definition of prediction leads us to a new paradigm, where deduction is replaced with computability concept: it rises conditional probability during the steps of inference (in contrast to SLD) and also maximally specifies resulted prediction rule. Moreover, we prove that probabilistic estimations obtained by semantic predictions are greater or equal to those by corresponding SLD-analogical systems. In conclusion practical applications are discussed.

Détail

Keywords: prediction; explanation; probability, logic & learning synthesis; probabilistic logic programming; relational data mining; scientific discovery.

Bibliographie

[1] E. E. Vityaev, Izvlechenie znanii iz dannykh. Kompyuternoe poznanie. Modeli kognitivnykh protsessov, NGU, Novosibirsk, 2006

[2] E. E. Vityaev, “The logic of prediction”, Mathematical Logic in Asia, Proceedings of the 9th Asian Logic Conference (Novosibirsk, Russia), eds. S. S. Goncharov, R. Downey, H. Ono, World Scientific, Singapore, 2006, 263–276 | MR | Zbl

[3] E. E. Vityaev, “Sintez logiki, veroyatnosti i obucheniya v semanticheskom veroyatnostnom vyvode”, Sbornik nauchnykh trudov IV Mezhdunarodnoi nauchno-prakticheskoi konferentsii “Integrirovannye modeli i myagkie vychisleniya v iskusstvennom intellekte”, v. 1, Kolomna, Mai 2007, 133–140

[4] C. G. Hempel, Aspects of Scientific Explanation and other Essays in the Philosophy of Science, Free Press, New York, 1966

[5] C. G. Hempel, “Maximal Specificity and Lawlikeness in Probabilistic Explanation”, Philosophy of Science, 35, no. 2, The University of Chicago Press, 1968, 116–133

[6] J. W. Lloyd, Foundations of logic programming, Springer-Verlag, 1987 | MR

[7] S. S. Goncharov, Y. L. Ershov, D. I. Sviridenko, “Semantic programming”, Information processing, Proc. IFIP 10-th World Comput. Congress, v. 10, Dublin, 1986, 1093–1100 | MR

[8] S. S. Goncharov, “Computability and computable models”, Mathematical Problems from Applied Logics. New Logics for the XXIst Century, v. II, International Mathematical Series, eds. D. M. Gabbay et al., Springer, New York, 2007, 99–214 | MR

[9] R. Ng and V. S. Subrahmanian, “Probabilistic Logic Programming”, Information and Computation, 101:2 (1993), 150–201 | MR

[10] J. Y. Halpern, “An Analysis of First-Order Logics of Probability”, Artificial Intelligence, 46 (1990), 311–350 | DOI | MR | Zbl

[11] J. E. Fenstad, “The Structure of Probabilities Defined on First-Order Languages”, Studies in Inductive Logic and Probabilities, v. 2, ed. R. C. Jeffrey, University of California Press, 1980, 251–262 | MR

[12] L. De Raedt, K. Kersting, “Probabilistic Logic Learning”, special issue on Multi-Relational Data Mining, ACM-SIGKDD Explorations, 5:1 (July 2003), 31–48 | DOI

[13] L. De Raedt and K. Kersting, “Probabilistic Inductive Logic Programming”, Algorithmic learning theory, Proceedings of the 15th International Conference on Algorithmic Learning Theory (Italy October 2004), eds. S. Ben-David, J. Case and A. Maruoka, Springer, Berlin, 2004, 19–36 | MR | Zbl

[14] T. Lukasiewicz, “Probabilistic logic programming with conditional constraints”, ACM Transactions on Computational Logic (TOCL), 2:3 (2001), 264–312 | MR

[15] G. Kern-Isberner and T. Lukasiewicz, “Combining Probabilistic Logic Programming with the Power of Maximum Entropy”, Artificial Intelligence, 157:1–2 (August 2004), 139–202 | DOI | MR | Zbl

[16] R. Haenni., Progic'05, 2nd Workshop on Combining Probability and Logic, 2005

[17] R. Haenni, Progic'07, 3rd Workshop on Combining Probability and Logic, 2007

[18] M. A. Paskin, Maximum Entropy Probabilistic Logic, Technical Report UCB/CSD-01-1161, University of California, Berkeley, April 2002

[19] S. Muggleton, “Stochastic logic programs”, Advances in Inductive Logic Programming, eds. L. De Raedt, IOS Press, 1996, 254–264 | MR

[20] S. Muggleton, “Learning stochastic logic programs”, Electronic Transactions in Artificial Intelligence, 4 (2000), 041 | MR

[21] J. Vennekens and S. Verbaeten, “A General View on Probabilistic Logic Programming”, Proceedings 15th Belgian-Dutch Conference on Artificial Intelligence, 2003, 299–306

[22] K. Kersting and L. De Raedt, “Bayesian Logic Programs”, Proceedings of the Work-in-Progress Track at the 10th International Conference on Inductive Logic Programming, eds. J. Cussens and A. Frisch, 2000, 138–155

[23] D. Poole, “The Independent Choice Logic for modelling multiple agents under uncertainty”, Artificial Intelligence, 94:1–2 (1997), 7–56 | DOI | MR | Zbl

[24] L. A. Zadeh, “Fuzzy Sets”, Information and Control, 8 (1965), 338–353 | DOI | MR | Zbl

[25] B. Y. Kovalerchuk, E. E. Vityaev, Data Mining in Finance: Advances in Relational and Hybrid methods, Kluwer Academic Publishers, 2000 | Zbl

[26] E. E. Vityaev, B. Y. Kovalerchuk, “Empirical Theories Discovery based on the Measurement Theory”, Mind and Machine, 14:4 (2004), 551–573 | DOI

[27] B. Y. Kovalerchuk, E. E. Vityaev, “Symbolic Methodology for Numeric Data Mining”, special issue on “Philosophies and Methodologies for Knowledge Discovery and Intelligent Data Analysis”, Intelligent Data Analysis, 12, no. 2, eds. K. Rennolls, E. Vityaev, IOS Press, 2008, 165–188

[28] E. E. Vityaev, B. Y. Kovalerchuk, “Relational Methodology for Data Mining and Knowledge Discovery”, special issue on “Philosophies and Methodologies for Knowledge Discovery and Intelligent Data Analysis”, Intelligent Data Analysis, 12, no. 2, eds. K. Rennolls, E. Vityaev, IOS Press, 2008, 189–210

[29] E. E. Vityaev, A. A. Moskvitin, “Vvedenie v teoriyu otkrytii. Programmnaya sistema Discovery”, Vychislitelnye sistemy: Logicheskie metody v informatike, 148, Novosibirsk, 1993, 117–163 | Zbl

[30] B. Y. Kovalerchuk, E. E. Vityaev, J. F. Ruiz, “Consistent and Complete Data and “Expert” Mining in Medicine”, Medical Data Mining and Knowledge Discovery, Springer, 2001, 238–280

[31] E. E. Vityaev, B. Y. Kovalerchuk, “Data Mining For Financial Applications”, Data Mining and Knowledge Discovery Handbook: A Complete Guide for Practitioners and Researchers, eds. O. Maimon and L. Rokach, Springer, 2005, 1203–1224

[32] A. A. Borovkov, Teoriya veroyatnostei, Nauka, M., 1986 | MR | Zbl

[33] A. A. Borovkov, Matematicheskaya statistika (Otsenki parametrov. Proverka gipotez), Nauka, M., 1984 | MR

[34] G. Dzh. Keisler, Ch. Ch. Chen, Teoriya modelei, Mir, M., 1977 | MR

[35] Yu. L. Ershov, E. A. Palyutin, Matematicheskaya logika, Izd-vo “Lan”, SPb., 2004

[36] N. N. Nepeivoda, Prikladnaya logika, NGU, Novosibirsk, 2000

[37] R. Goldblatt, Logics of time and computation, CSLI Lecture Notes, 7, 1992 | MR

[38] A. Chagrov, M. Zakharyaschev, Modal logic, Oxford logic guides, 35, eds. D. Gabbay, A. Macintyre and D. Scott, Clarendon press, Oxford, 1997 | MR | Zbl

[39] D. Rutkovskaya, M. Pilinskii, L. Rutkovskii, Neironnye seti, geneticheskie algoritmy i nechetkie sistemy, Izd-vo “Goryachaya liniya-Telekom”, M., 2006

[40] A. G. Kusraev, S. S. Kutateladze, Vvedenie v bulevoznachnyi analiz, Nauka, M., 2005 | MR

[41] Scientific Discovery website, http://www.math.nsc.ru/AP/ScientificDiscovery