×

Semiring programming: a semantic framework for generalized sum product problems. (English) Zbl 1490.68176

Summary: To solve hard problems, AI relies on a variety of disciplines such as logic, probabilistic reasoning, machine learning and mathematical programming. Although it is widely accepted that solving real-world problems requires an integration amongst these, contemporary representation methodologies offer little support for this.
In an attempt to alleviate this situation, we position and motivate a new declarative programming framework in this paper. We focus on the semantical foundations in service of providing abstractions of well-known problems such as SAT, Bayesian inference, generative models, learning and convex optimization. Programs are understood in terms of first-order logic structures with semiring labels, which allows us to freely combine and integrate problems from different AI disciplines and represent non-standard problems over unbounded domains. Thus, the main thrust of this paper is to view such well-known problems through a unified lens in the hope that appropriate solver strategies (exact, approximate, portfolio or hybrid) may emerge that tackle real-world problems in a principled way.

MSC:

68T01 General topics in artificial intelligence
68N19 Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.)
68T27 Logic in artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Abo Khamis, M.; Ngo, H. Q.; Rudra, A., FAQ: questions asked frequently, (Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (2016)), 13-28
[2] Andrei, N., Nonlinear Optimization Applications Using the GAMS Technology (2013), Springer · Zbl 1401.90001
[3] Apsel, U.; Kersting, K.; Mladenov, M., Lifting relational MAP-LPs using cluster signatures, (AAAI (2014)), 2403-2409
[4] Aziz, R. A.; Chu, G.; Muise, C.; Stuckey, P. J., Stable model counting and its application in probabilistic logic programming, (Twenty-Ninth AAAI Conference on Artificial Intelligence (2015))
[5] Bacchus, F.; Dalmao, S.; Pitassi, T., Solving #SAT and Bayesian inference with backtracking search, J. Artif. Intell. Res., 34, 391-442 (2009) · Zbl 1182.68294
[6] Baral, C.; Gelfond, M.; Rushton, J. N., Probabilistic reasoning with answer sets, Theory Pract. Log. Program., 9, 1, 57-144 (2009) · Zbl 1170.68003
[7] Baras, J. S.; Theodorakopoulos, G., Path problems in networks, Synth. Lect. Commun. Netw., 3, 1, 1-77 (2010) · Zbl 1270.68009
[8] Barrett, C.; Fontaine, P.; Tinelli, C., The SMT-LIB Standard: Version 2.5 (2015), Department of Computer Science, The University of Iowa, Available at:
[9] Barrett, C.; Sebastiani, R.; Seshia, S. A.; Tinelli, C., Satisfiability modulo theories, (Handbook of Satisfiability (2009), IOS Press), 825-885, chapter 26
[10] Belle, V., Open-universe weighted model counting, (Thirty-First AAAI Conference on Artificial Intelligence (2017))
[11] Belle, V., Symbolic logic meets machine learning: a brief survey in infinite domains (2020)
[12] Belle, V.; Levesque, H. J., Reasoning about discrete and continuous noisy sensors and effectors in dynamical systems, Artif. Intell., 262, 189-221 (2018) · Zbl 1451.68254
[13] Belle, V.; Passerini, A.; Van den Broeck, G., Probabilistic inference in hybrid domains by weighted model integration, (IJCAI (2015))
[14] Belle, V.; Passerini, A.; Van den Broeck, G., Towards component caching in hybrid domains, (AAAI (2016))
[15] Berre, D. L.; Lonca, E.; Marquis, P., On the complexity of optimization problems based on compiled NNF representations (2014), CoRR
[16] Bistarelli, S., Semirings for Soft Constraint Solving and Programming (2004), Springer Verlag · Zbl 1054.68136
[17] Bistarelli, S.; Montanari, U.; Rossi, F., Semiring-based constraint logic programming: syntax and semantics, ACM Trans. Program. Lang. Syst., 23, 1, 1-29 (2001)
[18] Bistarelli, S.; Montanari, U.; Rossi, F.; Schiex, T.; Verfaillie, G.; Fargier, H., Semiring-based CSPs and valued CSPs: frameworks, properties, and comparison, Constraints, 4, 3, 199-240 (1999) · Zbl 0946.68143
[19] Boerger, E.; Grädel, E.; Gurevich, Y., The Classical Decision Problem (1997), Springer Verlag · Zbl 0865.03004
[20] Brewka, G.; Delgrande, J. P.; Romero, J.; Schaub, T., asprin: Customizing answer set preferences without a headache, (AAAI (2015)), 1467-1474
[21] Brewka, G.; Eiter, T.; Truszczyński, M., Answer set programming at a glance, Commun. ACM, 54, 12, 92-103 (2011)
[22] Cadoli, M.; Mancini, T., Combining relational algebra, SQL, constraint modelling, and local search, Theory Pract. Log. Program., 7, 1-2, 37-65 (2007) · Zbl 1112.68040
[23] Chavira, M.; Darwiche, A., On probabilistic inference by weighted model counting, Artif. Intell., 172, 6-7, 772-799 (2008) · Zbl 1182.68297
[24] Chistikov, D.; Dimitrova, R.; Majumdar, R., Approximate counting in SMT and value estimation for probabilistic programs, (TACAS, vol. 9035 (2015)), 320-334 · Zbl 1420.68194
[25] Darwiche, A.; Marquis, P., A knowledge compilation map, J. Artif. Intell. Res., 17, 229-264 (2002) · Zbl 1045.68131
[26] De Raedt, L.; Kimmig, A.; Toivonen, H., Problog: A probabilistic Prolog and its application in link discovery, (Proc. IJCAI (2007)), 2462-2467
[27] Dechter, R.; Rish, I., Mini-buckets: a general scheme for bounded inference, J. ACM, 50, 2, 107-153 (2003) · Zbl 1326.68335
[28] den Broeck, G. V.; Taghipour, N.; Meert, W.; Davis, J.; Raedt, L. D., Lifted probabilistic inference by first-order knowledge compilation, (Proc. IJCAI (2011)), 2178-2185
[29] Derkinderen, V.; De Raedt, L., Algebraic circuits for decision theoretic inference and learning, (ECAI (2020))
[30] Ding, C. H.Q.; Li, T.; Jordan, M. I., Convex and semi-nonnegative matrix factorizations, IEEE Trans. Pattern Anal. Mach. Intell., 32, 1, 45-55 (Jan. 2010)
[31] Dyer, M. E.; Frieze, A. M., On the complexity of computing the volume of a polyhedron, SIAM J. Comput., 17, 5, 967-974 (1988) · Zbl 0668.68049
[32] Eisner, J.; Filardo, N. W., Dyna: extending Datalog for modern AI, (Datalog Reloaded. Datalog Reloaded, LNCS (2011), Springer), 181-220
[33] Enderton, H., A Mathematical Introduction to Logic (1972), Academic Press: Academic Press New York · Zbl 0298.02002
[34] Ensan, A.; Ternovska, E., Modular systems with preferences, (IJCAI (2015)), 2940-2947
[35] Evans, R.; Grefenstette, E., Learning explanatory rules from noisy data, J. Artif. Intell. Res., 61, 1-64 (2018) · Zbl 1426.68235
[36] Fargier, H.; Marquis, P.; Niveau, A., Towards a knowledge compilation map for heterogeneous representation languages, (IJCAI (2013)), 877-883
[37] Fargier, H.; Marquis, P.; Schmidt, N., Semiring labelled decision diagrams, revisited: canonicity and spatial efficiency issues, (IJCAI (2013))
[38] Fierens, D.; Van den Broeck, G.; Thon, I.; Gutmann, B.; De Raedt, L., Inference in probabilistic logic programs using weighted CNF’s, (UAI (2011)), 211-220
[39] Fontaine, D.; Michel, L.; Van Hentenryck, P., Model combinators for hybrid optimization, (CP (2013)), 299-314
[40] Fourer, R.; Gay, D. M.; Kernighan, B. W., AMPL: A Modeling Language for Mathematical Programming (1993), Scientific Press: Scientific Press South San Francisco
[41] Freuder, E., In pursuit of the holy grail, Constraints, 2, 1, 57-61 (1997) · Zbl 1315.68063
[42] Freuder, E. C.; Mackworth, A. K., Constraint satisfaction: an emerging paradigm, (Handbook of Constraint Programming (2006)), 13-28
[43] Friesen, A.; Domingos, P., Recursive decomposition for nonconvex optimization, (IJCAI (2015))
[44] Friesen, A.; Domingos, P., The sum-product theorem: a foundation for learning tractable models, (International Conference on Machine Learning (2016)), 1909-1918
[45] Frisch, A. M.; Harvey, W.; Jefferson, C.; Hernández, B. M.; Miguel, I., Essence: a constraint language for specifying combinatorial problems, Constraints, 13, 3, 268-306 (2008) · Zbl 1147.68424
[46] Gomes, C. P.; Sabharwal, A.; Selman, B., Model counting, (Handbook of Satisfiability (2009), IOS Press)
[47] Goodman, J., Semiring parsing, Comput. Linguist., 25, 4, 573-605 (1999)
[48] Goodman, N. D.; Mansinghka, V. K.; Roy, D. M.; Bonawitz, K.; Tenenbaum, J. B., Church: a language for generative models, (Proc. UAI (2008)), 220-229
[49] Gordon, A. D.; Henzinger, T. A.; Nori, A. V.; Rajamani, S. K., Probabilistic programming, (Proc. International Conference on Software Engineering (2014))
[50] Grant, M.; Boyd, S., Graph implementations for nonsmooth convex programs, (Recent Advances in Learning and Control. Recent Advances in Learning and Control, Lecture Notes in Control and Information Sciences (2008), Springer-Verlag Limited), 95-110 · Zbl 1205.90223
[51] Green, T. J.; Karvounarakis, G.; Tannen, V., Provenance semirings, (Proceedings of the Twenty-Sixth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (2007), ACM), 31-40
[52] Halmos, P., Measure Theory (1950), Van Nostrand Reinhold Company · Zbl 0040.16802
[53] Halpern, J., An analysis of first-order logics of probability, Artif. Intell., 46, 3, 311-350 (1990) · Zbl 0723.03007
[54] Hindi, H., A tutorial on convex optimization, (American Control Conference, vol. 4 (June 2004))
[55] Hooker, J. N.; Lama, M. A.O., Mixed logical-linear programming, Discrete Appl. Math., 96-97, 395-442 (1999) · Zbl 0945.90031
[56] Kannan, R.; Monma, C. L., On the Computational Complexity of Integer Programming Problems (1978), Springer · Zbl 0409.90066
[57] Kautz, H., Toward a universal inference engine, (LPNMR. LPNMR, LNCS, vol. 2923 (2004), Springer Berlin Heidelberg), 2 · Zbl 1122.68607
[58] Kimmig, A.; Van den Broeck, G.; De Raedt, L., An algebraic Prolog for reasoning about possible worlds, (Proc. AAAI (2011))
[59] Kimmig, A.; Van den Broeck, G.; De Raedt, L., Algebraic model counting, J. Appl. Log., 22, 46-62 (2017) · Zbl 1436.68335
[60] Kolb, S.; Martires, P. Z.D.; Raedt, L. D., How to exploit structure while solving weighted model integration problems, (Proceedings of the Thirty-Fifth Conference on Uncertainty in Artificial Intelligence. Proceedings of the Thirty-Fifth Conference on Uncertainty in Artificial Intelligence, UAI 2019, Tel Aviv, Israel, July 22-25, 2019 (2019)), 262
[61] Kolb, S.; Mladenov, M.; Sanner, S.; Belle, V.; Kersting, K., Efficient symbolic integration for probabilistic inference, (IJCAI (2018)), 5031-5037
[62] Koller, D.; Friedman, N., Probabilistic Graphical Models - Principles and Techniques (2009), MIT Press · Zbl 1183.68483
[63] Kordjamshidi, P.; Roth, D.; Kersting, K., Systems AI: a declarative learning based programming perspective, (IJCAI (2018)), 5464-5471
[64] Kowalski, R. A., Predicate logic as programming language, (IFIP Congress (1974)), 569-574 · Zbl 0297.68006
[65] Kuich, W., Semirings and formal power series: their relevance to formal languages and automata, (Handbook of Formal Languages, Vol. 1 (1997), Springer: Springer Berlin), 609-677
[66] Lacoste-Julien, S.; Huszár, F.; Ghahramani, Z., Approximate inference for the loss-calibrated Bayesian, (Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics (2011)), 416-424
[67] Li, Z.; Eisner, J., First- and second-order expectation semirings with applications to minimum-risk training on translation forests, (Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing: Volume 1-Volume 1 (2009), Association for Computational Linguistics), 40-51
[68] Lierler, Y.; Truszczynski, M., An abstract view on modularity in knowledge representation, (AAAI (2015)), 1532-1538
[69] Liu, G.; Janhunen, T.; Niemelä, I., Answer set programming via mixed integer programming, (KR (2012))
[70] Liu, G.; Janhunen, T.; Niemelä, I., Introducing real variables and integer objective functions to answer set programming, (Hanus, M.; Rocha, R., Declarative Programming and Knowledge Management. Declarative Programming and Knowledge Management, Lecture Notes in Computer Science, vol. 8439 (2014), Springer International Publishing), 118-135
[71] Marriott, K.; Nethercote, N.; Rafeh, R.; Stuckey, P.; Garcia de la Banda, M.; Wallace, M., The design of the zinc modelling language, Constraints, 13, 3, 229-267 (2008) · Zbl 1146.68352
[72] Milch, B.; Marthi, B.; Russell, S. J.; Sontag, D.; Ong, D. L.; Kolobov, A., BLOG: probabilistic models with unknown objects, (Proc. IJCAI (2005)), 1352-1359
[73] Minka, T., Divergence measures and message passing (2005), Microsoft Research, Technical report
[74] Mitchell, D. G.; Ternovska, E., A framework for representing and solving NP search problems, (AAAI (2005)), 430-435
[75] Muggleton, S.; De Raedt, L., Inductive logic programming: theory and methods, J. Log. Program., 19, 629-679 (1994) · Zbl 0816.68043
[76] Nieuwenhuis, R.; Oliveras, A., On SAT modulo theories and optimization problems, (Theory and Applications of Satisfiability Testing-SAT 2006 (2006), Springer), 156-169 · Zbl 1187.68558
[77] F. Obermeyer, E. Bingham, M. Jankowiak, D. Phan, J.P. Chen, Functional tensors for probabilistic programming, 2019.
[78] Orsini, F.; Frasconi, P.; De Raedt, L., kProbLog: an algebraic Prolog for machine learning, Mach. Learn., 106, 12, 1933-1969 (Dec 2017) · Zbl 1457.68237
[79] Poon, H.; Domingos, P., Sum-product networks: a new deep architecture, (2011 IEEE International Conference on Computer Vision Workshops (ICCV Workshops) (2011), IEEE), 689-690
[80] Richardson, M.; Domingos, P., Markov logic networks, Mach. Learn., 62, 1, 107-136 (2006) · Zbl 1470.68221
[81] Sankaranarayanan, S.; Chakarov, A.; Gulwani, S., Static analysis for probabilistic programs: inferring whole program properties from finitely many paths, ACM SIGPLAN Not., 48, 6 (2013)
[82] Sanner, S.; McAllester, D. A., Affine algebraic decision diagrams (AADDs) and their application to structured probabilistic inference, (IJCAI (2005)), 1384-1390
[83] Sebastiani, R.; Tomasi, S., Optimization modulo theories with linear rational costs, ACM Trans. Comput. Log., 16, 2, Article 12 pp. (Feb. 2015) · Zbl 1354.68233
[84] Srivastava, S.; Fang, E.; Riano, L.; Chitnis, R.; Russell, S. J.; Abbeel, P., Combined task and motion planning through an extensible planner-independent interface layer, (ICRA (2014)), 639-646
[85] Ternovska, E., An algebra of modular systems: static and dynamic perspectives, (International Symposium on Frontiers of Combining Systems (2019), Springer), 94-111 · Zbl 1435.68203
[86] Ternovska, E.; Mitchell, D. G., Declarative programming of search problems with built-in arithmetic, (Proc. IJCAI (2009)), 942-947
[87] Thrun, S.; Burgard, W.; Fox, D., Probabilistic Robotics (2005), MIT Press · Zbl 1081.68703
[88] Van Hentenryck, P., Constraint and integer programming in OPL, INFORMS J. Comput., 14, 4, 345-372 (2002) · Zbl 1238.90102
[89] Zuidberg Dos Martires, P. M.; Dries, A.; De Raedt, L., Exact and approximate weighted model integration with probability density functions using knowledge compilation, (Proceedings of the 30th Conference on Artificial Intelligence (2019), AAAI Press)
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.