On Computational Aspects of Maximal Specificity in Probabilistic Explanation

S. O. Speranski

Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 11 (2011) no. 4, pp. 78-93

Résumé

In the present paper the computational aspects of the formal requirement of maximal specificity are investigated. This requirement is imposed on rules in the language of propositional classical logic when given a computable rational-valued probability measure over the language. We prove undecidability for several general problems of discovering maximally specific rules and probability measures for which the collection of all specific rules is computable; establish decidability of the set of maximally specific rules if certain natural conditions are met; study the question whether it is possible to uniformly obtain decision procedures in case these conditions hold; estimate the complexity of introduced subclasses of measures in the arithmetical hierarchy.

Détail

Keywords: inductive and probability logic, maximal specificity, decidability, computability, complexity.

Bibliographie

[1] Speranskii S. O., “O logicheskoi neprotivorechivosti veroyatnostnykh predskazanii”, Vestn. Novosib. gos. un-ta. Seriya: Matematika, mekhanika, informatika, 11:1 (2011), 99–115 | Zbl

[2] Smerdov S. O., Vityaev E. E., “Sintez logiki, veroyatnosti i obucheniya: formalizatsiya predskazaniya”, Sibirskie elektronnye matematicheskie izvestiya, 9 (2009), 340–365

[3] Vityaev E. E., Smerdov S. O., “On the Problem of Prediction”, Knowledge Processing and Data Analysis, KONT/KPP 2007, LNAI, 6581, eds. K. E. Wolff, D. E. Palchunov et al., Springer, 2011, 280–296

[4] Vityaev E. E., “The Logic of Prediction”, Mathematical Logic in Asia 2005, Proceedings of the $9^\text{th}$ Asian Logic Conference (August 16–19, Novosibirsk, Russia), eds. S. Goncharov, R. Downey, H. Ono, World Scientific Publisher, 2006, 263–276 | MR | Zbl

[5] Vityaev E. E., Kovalerchuk B. Ya., “Relational Methodology for Data Mining and Knowledge Discovery”, Intelligent Data Analysis, 12, no. 2, eds. K. Rennolls, E. Vityaev, IOS Press, 2008, 189–210

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

[7] Goncharov S. S., Ershov Yu. L., Sviridenko D. I., “Semantic Programming”, Information Processing'86, Proceedings of the IFIP $10^\text{th}$ World Computer Congress (Dublin, Ireland, September 1–5, 1986), North-Holland, 1986, 1093–1100 | MR

[8] Hempel C. G., “Maximal Specificity and Lawlikeness in Probabilistic Explanation”, Philosophy of Science, 35:2 (1968), 116–133 | DOI

[9] Hempel C. G., “Deductive-Nomological versus Inductive-Statistical Explanation”, Minnesota Studies in the Philosophy of Science, 3, eds. H. Feigl, G. Maxwell, University of Minnesota Press, Minneapolis, 1962, 98–169

[10] Scott D., Krauss P., “Assigning Probabilities to Logical Formulas”, Aspects of Inductive Logic, eds. J. Hintikka, P. Suppes, North-Holland Publishing Company, Amsterdam, 1966, 219–264 | DOI | MR

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

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

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