×

An overview of algorithmic approaches to compute optimum entropy distributions in the expert system shell MECore (extended version). (English) Zbl 1436.68341

Summary: The expert system shell MECore provides a series of knowledge management operations to define probabilistic knowledge bases and to reason under uncertainty. To provide a reference work for MECore algorithmics, we bring together results from different sources that have been applied in MECore and explain their intuitive ideas. Additionally, we report on our ongoing work regarding further development of MECore’s algorithms to compute optimum entropy distributions and provide some empirical results. Altogether this paper explains the intuition of important theoretical results and their practical implications, compares old and new algorithmic approaches and points out their benefits as well as possible limitations and pitfalls.

MSC:

68T35 Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence
60E05 Probability distributions: general theory
68T30 Knowledge representation

Software:

SPIRIT; L-BFGS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bacchus, F., Representing and Reasoning with Probabilistic Knowledge: A Logical Approach to Probabilities (1990), MIT Press: MIT Press Cambridge, MA
[2] Bacchus, F.; Grove, A. J.; Koller, D.; Halpern, J. Y., From statistics to beliefs, (Proceedings of the 10th AAAI Conference on Artificial Intelligence (1992)), 602-608
[3] Beierle, C.; Finthammer, M.; Potyka, N.; Varghese, J.; Kern-Isberner, G., A case study on the application of probabilistic conditional modelling and reasoning to clinical patient data in neurosurgery, (van der Gaag, L. C., Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 12th European Conference, ECSQARU 2013, Utrecht, The Netherlands, July 8-10, Proceedings (2013), Springer), 49-60
[4] Beinlich, I. A.; Suermondt, H. J.; Chavez, R. M.; Cooper, G. F., The ALARM monitoring system: a case study with two probabilistic inference techniques for belief networks, (Proceedings of the 2nd European Conference on Artificial Intelligence in Medicine (1989), Springer-Verlag), 247-256
[5] Berger, A. L.; Pietra, V. J.D.; Pietra, S. A.D., A maximum entropy approach to natural language processing, Comput. Linguist., 22, 39-71 (1996)
[6] Broecheler, M.; Simari, G. I.; Subrahmanian, V., Using histograms to better answer queries to probabilistic logic programs, (Logic Programming (2009), Springer), 40-54 · Zbl 1251.68052
[7] Csiszar, I., I-divergence geometry of probability distributions and minimization problems, Ann. Appl. Probab., 3, 146-158 (1975) · Zbl 0318.60013
[8] Csiszar, I., A geometric interpretation of Darroch and Ratcliff’s generalized iterative scaling, Ann. Stat., 17, 1409-1413 (1989) · Zbl 0681.62010
[9] Darroch, J. N.; Ratcliff, D., Generalized iterative scaling for log-linear models, Ann. Math. Stat., 43, 1470-1480 (1972) · Zbl 0251.62020
[10] De Bona, G.; Cozman, F. G.; Finger, M., Towards classifying propositional probabilistic logics, J. Appl. Log., 12, 349-368 (2014) · Zbl 1352.03032
[11] De Raedt, L.; Kersting, K., Probabilistic inductive logic programming, (Raedt, L. D.; Kersting, K.; Landwehr, N.; Muggleton, S.; Chen, J., Probabilistic Inductive Logic Programming. Probabilistic Inductive Logic Programming, Lect. Notes Comput. Sci., vol. 4911 (2008), Springer), 1-27 · Zbl 1137.68530
[12] Domingos, P.; Lowd, D., Markov Logic: An Interface Layer for Artificial Intelligence, Synth. Lect. Artif. Intell. Mach. Learn. (2009), Morgan and Claypool: Morgan and Claypool San Rafael, CA · Zbl 1202.68403
[13] Finthammer, M.; Beierle, C., Using equivalences of worlds for aggregation semantics of relational conditionals, (Glimm, B.; Krüger, A., KI 2012: Advances in Artificial Intelligence, 35th Annual German Conference on AI, Saarbrücken, Germany, September 24-27, 2012, Proceedings (2012), Springer), 49-60
[14] Finthammer, M.; Beierle, C.; Berger, B.; Kern-Isberner, G., Probabilistic reasoning at optimum entropy with the MEcore system, (Lane, H. C.; Guesgen, H. W., Proceedings 22nd International FLAIRS Conference. Proceedings 22nd International FLAIRS Conference, FLAIRS’09 (2009), AAAI Press: AAAI Press Menlo Park, California), 535-540
[15] Fletcher, R., Practical Methods of Optimization (1987), Wiley-Interscience: Wiley-Interscience New York, NY, USA · Zbl 0905.65002
[16] Ganapathi, V.; Vickrey, D.; Duchi, J. C.; Koller, D., Constrained approximate maximum entropy learning of Markov random fields, (Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence (UAI). Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence (UAI), Helsinki, Finland, July 9-12, 2008 (2008)), 196-203
[17] (Getoor, L.; Taskar, B., Introduction to Statistical Relational Learning (Adaptive Computation and Machine Learning) (2007), The MIT Press) · Zbl 1141.68054
[18] Hailperin, T., Boole’s Logic and Probability, Stud. Logic Found. Math., vol. 85 (1986), Elsevier · Zbl 0611.03001
[19] Halpern, J., Reasoning About Uncertainty (2005), MIT Press
[20] Halpern, J. Y., An analysis of first-order logics of probability, Artif. Intell., 46, 311-350 (1990) · Zbl 0723.03007
[21] Jaumard, B.; Hansen, P.; Poggi, M., Column generation methods for probabilistic logic, ORSA J. Comput., 3, 135-148 (1991) · Zbl 0800.68864
[22] Kern-Isberner, G., Conditionals in Nonmonotonic Reasoning and Belief Revision, Lect. Notes Artif. Intell., vol. 2087 (2001), Springer · Zbl 0978.03014
[23] Kern-Isberner, G., Linking iterated belief change operations to nonmonotonic reasoning, (Brewka, G.; Lang, J., Proceedings 11th International Conference on Knowledge Representation and Reasoning. Proceedings 11th International Conference on Knowledge Representation and Reasoning, KR’2008 (2008), AAAI Press: AAAI Press Menlo Park, CA), 166-176
[24] Kern-Isberner, G.; Lukasiewicz, T., Combining probabilistic logic programming with the power of maximum entropy, Special Issue on Nonmonotonic Reasoning. Special Issue on Nonmonotonic Reasoning, Artif. Intell., 157, 1-2, 139-202 (2004) · Zbl 1085.68170
[25] Koller, D.; Friedman, N., Probabilistic Graphical Models: Principles and Techniques (2009), MIT Press
[26] Liu, D. C.; Nocedal, J.; Liu, D. C.; Nocedal, J., On the limited memory BFGS method for large scale optimization, Math. Program., 45, 503-528 (1989) · Zbl 0696.90048
[27] Lukasiewicz, T., Probabilistic logic programming, (Proc. of the 13th European Conf. on Artificial Intelligence. Proc. of the 13th European Conf. on Artificial Intelligence, ECAI 1998 (1998), J. Wiley & Sons), 388-392
[28] Lukasiewicz, T., Probabilistic deduction with conditional constraints over basic events, J. Artif. Intell. Res., 10, 380-391 (1999)
[29] Malouf, R., A comparison of algorithms for maximum entropy parameter estimation, (Proceedings of the 6th Conference on Natural Language Learning, vol. 20 (2002), Association for Computational Linguistics: Association for Computational Linguistics Stroudsburg, PA, USA), 1-7
[30] Meyer, C. H., Korrektes Schließen bei unvollständiger Information (1998), Peter Lang Verlag
[31] Minka, T. P., A comparison of numerical optimizers for logistic regression (2003), Microsoft Research, (rev. 2007)
[32] Ng, R.; Subrahmanian, V. S., Probabilistic logic programming, Inf. Comput., 101, 150-201 (1992) · Zbl 0781.68038
[33] Nilsson, N. J., Probabilistic logic, Artif. Intell., 28, 71-88 (1986) · Zbl 0589.03007
[34] Nocedal, J.; Wright, S. J., Numerical Optimization (2006), Springer: Springer New York · Zbl 1104.65059
[35] Pápai, T.; Ghosh, S.; Kautz, H., Combining subjective probabilities and data in training Markov logic networks, (Flach, P.; Bie, T.; Cristianini, N., Machine Learning and Knowledge Discovery in Databases. Machine Learning and Knowledge Discovery in Databases, Lect. Notes Comput. Sci., vol. 7523 (2012), Springer: Springer Berlin Heidelberg), 90-105
[36] Paris, J.; Vencovska, A., In defence of the maximum entropy inference process, Int. J. Approx. Reason., 17, 77-103 (1997) · Zbl 0939.68118
[37] Potyka, N., Some notes on the factorization of probabilistic logical models under maximum entropy semantics, (Proc. 26th International FLAIRS Conference. Proc. 26th International FLAIRS Conference, FLAIRS-26 (2013), AAAI Press: AAAI Press Menlo Park, California)
[38] Potyka, N.; Beierle, C.; Kern-Isberner, G., Changes of relational probabilistic belief states and their computation under optimum entropy semantics, (Timm, I. J.; Thimm, M., KI 2013: Advances in Artificial Intelligence - 36th Annual German Conference on AI, Koblenz, Germany, September 16-20, 2013, Proceedings (2013), Springer), 176-187
[39] Potyka, N.; Marenke, D.; Mittermeier, E., An overview of algorithmic approaches to compute optimum entropy distributions in the expert system shell mecore, (Beierle, C.; Kern-Isberner, G., 4th Workshop on Dynamics of Knowledge and Belief. 4th Workshop on Dynamics of Knowledge and Belief, DKB-2013 (2013), FernUniversität in Hagen), 61-74
[40] Richardson, M.; Domingos, P., Markov logic networks, Mach. Learn., 62, 107-136 (2006) · Zbl 1470.68221
[41] Rödder, W.; Meyer, C., Coherent knowledge processing at maximum entropy by SPIRIT, (Proceedings Uncertainty in AI. Proceedings Uncertainty in AI, UAI 1996 (1996)), 470-476
[42] Rödder, W.; Reucher, E.; Kulmann, F., Features of the expert-system-shell spirit, Log. J. IGPL, 14, 483-500 (2006) · Zbl 1109.68653
[43] Schramm, M.; Ertel, W., Reasoning with probabilities and maximum entropy: the system PIT and its application in LEXMED, (Symposium on Operations Research. Symposium on Operations Research, SOR’99 (1999)) · Zbl 1015.90506
[44] Spiegelhalter, D. J.; Cowell, R. G., Learning in probabilistic expert systems, Bayesian Stat., 4, 447-465 (1992)
[45] Thimm, M., Measuring inconsistency in probabilistic knowledge bases, (Bilmes, J.; Ng, A., Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence. Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, UAI’09, Montreal, Canada (2009))
[46] Yue, A.; Liu, W.; Hunter, A., Measuring the ignorance and degree of satisfaction for answering queries in imprecise probabilistic logic programs, (Scalable Uncertainty Management (2008), Springer), 386-400
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.