SpringerLink
Log in

Symbolic Logic Meets Machine Learning: A Brief Survey in Infinite Domains

  • Conference paper
  • First Online:
Scalable Uncertainty Management (SUM 2020)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 12322))

Included in the following conference series:

Abstract

The tension between deduction and induction is perhaps the most fundamental issue in areas such as philosophy, cognition and artificial intelligence (AI). The deduction camp concerns itself with questions about the expressiveness of formal languages for capturing knowledge about the world, together with proof systems for reasoning from such knowledge bases. The learning camp attempts to generalize from examples about partial descriptions about the world. In AI, historically, these camps have loosely divided the development of the field, but advances in cross-over areas such as statistical relational learning, neuro-symbolic systems, and high-level control have illustrated that the dichotomy is not very constructive, and perhaps even ill-formed.

In this article, we survey work that provides further evidence for the connections between logic and learning. Our narrative is structured in terms of three strands: logic versus learning, machine learning for logic, and logic for machine learning, but naturally, there is considerable overlap. We place an emphasis on the following “sore” point: there is a common misconception that logic is for discrete properties, whereas probability theory and machine learning, more generally, is for continuous properties. We report on results that challenge this view on the limitations of logic, and expose the role that logic can play for learning in infinite domains.

The author was supported by a Royal Society University Research Fellowship. He is grateful to Ionela G. Mocanu, Paulius Dilkas and Kwabena Nuamah for their feedback.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
EUR 29.95
Price includes VAT (Germany)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 42.79
Price includes VAT (Germany)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 53.49
Price includes VAT (Germany)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Albarghouthi, A., D’Antoni, L., Drews, S., Nori, A.V.: Quantifying program bias. CoRR, abs/1702.05437 (2017)

    Google Scholar 

  2. Bach, F.R., Jordan, M.I.: Thin junction trees. In: Advances in Neural Information Processing Systems, pp. 569–576 (2002)

    Google Scholar 

  3. Banihashemi, B., De Giacomo, G., Lespérance, Y.: Abstraction in situation calculus action theories. In: AAAI, pp. 1048–1055 (2017)

    Google Scholar 

  4. Barrett, C., Sebastiani, R., Seshia, S.A., Tinelli, C.: Satisfiability modulo theories. In: Handbook of Satisfiability, chap. 26, pp. 825–885. IOS Press (2009)

    Google Scholar 

  5. Belle, V.: Logic meets probability: towards explainable AI systems for uncertain worlds. In: IJCAI (2017)

    Google Scholar 

  6. Belle, V.: Open-universe weighted model counting. In: AAAI, pp. 3701–3708 (2017)

    Google Scholar 

  7. Belle, V.: Weighted model counting with function symbols. In: UAI (2017)

    Google Scholar 

  8. Belle, V.: Abstracting probabilistic models: relations, constraints and beyond. Knowl.-Based Syst. 199, 105976 (2020). https://www.sciencedirect.com/science/article/abs/pii/S0950705120302914

  9. Belle, V., De Raedt, L.: Semiring programming: a declarative framework for generalized sum product problems. In: AAAI Workshop: Statistical Relational Artificial Intelligence (2020)

    Google Scholar 

  10. Belle, V., Juba, B.: Implicitly learning to reason in first-order logic. In: Advances in Neural Information Processing Systems, pp. 3376–3386 (2019)

    Google Scholar 

  11. Belle, V., Levesque, H.J.: Allegro: belief-based programming in stochastic dynamical domains. In: IJCAI (2015)

    Google Scholar 

  12. Belle, V., Passerini, A., Van den Broeck, G.: Probabilistic inference in hybrid domains by weighted model integration. In: IJCAI, pp. 2770–2776 (2015)

    Google Scholar 

  13. Benedikt, M., Kersting, K., Kolaitis, P.G., Neider, D.: Logic and learning (dagstuhl seminar 19361). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2020)

    Google Scholar 

  14. Bistarelli, S., Montanari, U., Rossi, F.: Semiring-based constraint logic programming: syntax and semantics. TOPLAS 23(1), 1–29 (2001)

    Article  Google Scholar 

  15. Bueff, A., Speichert, S., Belle, V.: Tractable querying and learning in hybrid domains via sum-product networks. In: KR Workshop on Hybrid Reasoning (2018)

    Google Scholar 

  16. Bundy, A., Nuamah, K., Lucas, C.: Automated reasoning in the age of the internet. In: Fleuriot, J., Wang, D., Calmet, J. (eds.) AISC 2018. LNCS (LNAI), vol. 11110, pp. 3–18. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-99957-9_1

    Chapter  Google Scholar 

  17. Bunel, R., Hausknecht, M., Devlin, J., Singh, R., Kohli, P.: Leveraging grammar and reinforcement learning for neural program synthesis. ar**v preprint ar**v:1805.04276 (2018)

  18. Carlson, A., Betteridge, J., Kisiel, B., Settles, B., Hruschka Jr., E.R., Mitchell, T.M.: Toward an architecture for never-ending language learning. In: AAAI, pp. 1306–1313 (2010)

    Google Scholar 

  19. Chakraborty, S., Fremont, D.J., Meel, K.S., Seshia, S.A., Vardi, M.Y.: Distribution-aware sampling and weighted model counting for SAT. In: AAAI, pp. 1722–1730 (2014)

    Google Scholar 

  20. Chavira, M., Darwiche, A.: On probabilistic inference by weighted model counting. Artific. Intell. 172(6–7), 772–799 (2008)

    Article  MathSciNet  Google Scholar 

  21. Chistikov, D., Dimitrova, R., Majumdar, R.: Approximate counting in SMT and value estimation for probabilistic programs. TACAS 9035, 320–334 (2015)

    MATH  Google Scholar 

  22. Cohen, W.W.: PAC-learning nondeterminate clauses. In: AAAI, pp. 676–681 (1994)

    Google Scholar 

  23. Darwiche, A.: New advances in compiling CNF to decomposable negation normal form. In: ECAI, pp. 328–332 (2004)

    Google Scholar 

  24. Darwiche, A.: Three modern roles for logic in AI. In: Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pp. 229–243 (2020)

    Google Scholar 

  25. Darwiche, A., Marquis, P.: A knowledge compilation map. J. Artif. Intell. Res. 17, 229–264 (2002)

    Article  MathSciNet  Google Scholar 

  26. De Raedt, L., Dries, A., Thon, I., Van den Broeck, G., Verbeke, M.: Inducing probabilistic relational rules from probabilistic examples. In: Twenty-Fourth International Joint Conference on Artificial Intelligence (2015)

    Google Scholar 

  27. De Raedt, L., Kimmig, A.: Probabilistic (logic) programming concepts. Mach. Learn. 100(1), 5–47 (2015)

    Article  MathSciNet  Google Scholar 

  28. De Raedt, L., Manhaeve, R., Dumancic, S., Demeester, T., Kimmig, A.: Neuro-symbolic= neural+ logical+ probabilistic. In: NeSy 2019@ IJCAI, The 14th International Workshop on Neural-Symbolic Learning and Reasoning, pp. 1–4 (2019)

    Google Scholar 

  29. Dilkas, P., Belle, V.: Generating random logic programs using constraint programming. CoRR, abs/2006.01889 (2020)

    Google Scholar 

  30. Domingos, P.: The Master Algorithm: How the Quest for the Ultimate Learning Machine Will Remake Our World. Basic Books (2015)

    Google Scholar 

  31. Dos Martires, P.Z., Dries, A., De Raedt, L.: Exact and approximate weighted model integration with probability density functions using knowledge compilation. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, pp. 7825–7833 (2019)

    Google Scholar 

  32. Dries, A., Kimmig, A., Davis, J., Belle, V., De Raedt, L.: Solving probability problems in natural language. In: IJCAI (2017)

    Google Scholar 

  33. Eisner, J., Filardo, N.W.: Dyna: extending datalog for modern AI. In: de Moor, O., Gottlob, G., Furche, T., Sellers, A. (eds.) Datalog 2.0 2010. LNCS, vol. 6702, pp. 181–220. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-24206-9_11

    Chapter  Google Scholar 

  34. Ensan, A., Ternovska, E.: Modular systems with preferences. In: IJCAI, pp. 2940–2947 (2015)

    Google Scholar 

  35. Evans, R., Grefenstette, E.: Learning explanatory rules from noisy data. J. Artif. Intell. Res. 61, 1–64 (2018)

    Article  MathSciNet  Google Scholar 

  36. Fierens, D., Van den Broeck, G., Thon, I., Gutmann, B., De Raedt, L.: Inference in probabilistic logic programs using weighted CNF’s. In: UAI, pp. 211–220 (2011)

    Google Scholar 

  37. d’Avila Garcez, A., Gori, M., Lamb, L.C., Serafini, L., Spranger, M., Tran, S.N.: Neural-symbolic computing: an effective methodology for principled integration of machine learning and reasoning. ar**v preprint ar**v:1905.06088 (2019)

  38. Getoor, L., Taskar, B. (eds.): An Introduction to Statistical Relational Learning. MIT Press, Cambridge (2007)

    MATH  Google Scholar 

  39. Gomes, C.P., Sabharwal, A., Selman, B.: Model counting. In: Handbook of Satisfiability. IOS Press (2009)

    Google Scholar 

  40. Goodman, N.D., Mansinghka, V.K., Roy, D.M., Bonawitz, K., Tenenbaum, J.B.: Church: a language for generative models. In: Proceedings of UAI, pp. 220–229 (2008)

    Google Scholar 

  41. Grohe, M., Lindner, P.: Probabilistic databases with an infinite open-world assumption. In: Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pp. 17–31 (2019)

    Google Scholar 

  42. Grohe, M., Ritzert, M.: Learning first-order definable concepts over structures of small degree. In: 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pp. 1–12. IEEE (2017)

    Google Scholar 

  43. Gulwani, S.: Dimensions in program synthesis. In: PPDP, pp. 13–24. ACM (2010)

    Google Scholar 

  44. Gunning, D.: Explainable artificial intelligence (XAI). Technical report, DARPA/I20 (2016)

    Google Scholar 

  45. Gutmann, B., Thon, I., Kimmig, A., Bruynooghe, M., De Raedt, L.: The magic of logical inference in probabilistic programming. Theor. Pract. Logic Program. 11(4–5), 663–680 (2011)

    Article  MathSciNet  Google Scholar 

  46. Halpern, J.Y.: Reasoning about Uncertainty. MIT Press (2003)

    Google Scholar 

  47. Holtzen, S., Millstein, T.: and G. Van den Broeck. Probabilistic program abstractions, In UAI (2017)

    Google Scholar 

  48. Holtzen, S., Van den Broeck, G., Millstein, T.: Dice: compiling discrete probabilistic programs for scalable inference. ar**v preprint ar**v:2005.09089 (2020)

  49. Huang, X., Kwiatkowska, M., Wang, S., Wu, M.: Safety verification of deep neural networks. In: Majumdar, R., Kunčak, V. (eds.) CAV 2017. LNCS, vol. 10426, pp. 3–29. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63387-9_1

    Chapter  Google Scholar 

  50. Kaelbling, L.P., Lozano-Pérez, T.: Integrated task and motion planning in belief space. I. J. Robotic Res. 32(9–10), 1194–1227 (2013)

    Article  Google Scholar 

  51. Kahneman, D.: Thinking, Fast and Slow. Macmillan (2011)

    Google Scholar 

  52. Kimmig, A., Van den Broeck, G., De Raedt, L.: Algebraic model counting. J. Appl. Log. 22, 46–62 (2017)

    Article  MathSciNet  Google Scholar 

  53. Kolb, S., Mladenov, M., Sanner, S., Belle, V., Kersting, K.: Efficient symbolic integration for probabilistic inference. In: IJCAI (2018)

    Google Scholar 

  54. Kolb, S., et al.: The PYWMI framework and toolbox for probabilistic inference using weighted model integration (2019). https://www.ijcai.org/proceedings/2019/

  55. Kolb, S., Teso, S., Passerini, A., De Raedt, L.: Learning SMT (LRA) constraints using SMT solvers. In: IJCAI, pp. 2333–2340 (2018)

    Google Scholar 

  56. Koller, D., Friedman, N.: Probabilistic Graphical Models - Principles and Techniques. MIT Press (2009)

    Google Scholar 

  57. Koller, D., Levy, A., Pfeffer, A.: P-classic: a tractable probablistic description logic. In: Proceedings of the AAAI/IAAI, pp. 390–397 (1997)

    Google Scholar 

  58. Kordjamshidi, P., Roth, D., Kersting, K.: Systems AI: a declarative learning based programming perspective. In: IJCAI, pp. 5464–5471 (2018)

    Google Scholar 

  59. Lakemeyer, G., Levesque, H.J.: Cognitive robotics. In: Handbook of Knowledge Representation, pp. 869–886. Elsevier (2007)

    Google Scholar 

  60. Lamb, L., Garcez, A., Gori, M., Prates, M., Avelar, P., Vardi, M.: Graph neural networks meet neural-symbolic computing: a survey and perspective. ar**v preprint ar**v:2003.00330 (2020)

  61. Levesque, H.J.: Common Sense, the Turing Test, and the Quest for Real AI. MIT Press (2017)

    Google Scholar 

  62. Levesque, H.J., Brachman, R.J.: Expressiveness and tractability in knowledge representation and reasoning. Comput. Intell. 3, 78–93 (1987)

    Article  Google Scholar 

  63. Liang, Y., Bekker, J., Van den Broeck, G.: Learning the structure of probabilistic sentential decision diagrams. In: Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence (UAI) (2017)

    Google Scholar 

  64. Lierler, Y., Truszczynski, M.: An abstract view on modularity in knowledge representation. In: AAAI, pp. 1532–1538 (2015)

    Google Scholar 

  65. Liu, Y., Levesque, H.: Tractable reasoning with incomplete first-order knowledge in dynamic systems with context-dependent actions. In: Proceedings of the IJCAI, pp. 522–527 (2005)

    Google Scholar 

  66. Lowd, D., Domingos, P.: Learning arithmetic circuits. In: Proceedings of the 24th Conference in Uncertainty in Artificial Intelligence (UAI), pp. 383–392 (2008)

    Google Scholar 

  67. Manhaeve, R., Dumancic, S., Kimmig, A., Demeester, T., De Raedt, L.: Deepproblog: neural probabilistic logic programming. In: Advances in Neural Information Processing Systems, pp. 3749–3759 (2018)

    Google Scholar 

  68. Marcus, G., Davis, E.: Rebooting AI: Building Artificial Intelligence We Can Trust. Pantheon (2019)

    Google Scholar 

  69. Merrell, D., Albarghouthi, A., D’Antoni, L.: Weighted model integration with orthogonal transformations. In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (2017)

    Google Scholar 

  70. Milch, B., Marthi, B., Sontag, D., Russell, S.J., Ong, D.L., Kolobov, A.: Approximate inference for infinite contingent Bayesian networks. In: AISTATS, pp. 238–245 (2005)

    Google Scholar 

  71. Mitchell, D.G., Ternovska, E.: A framework for representing and solving NP search problems. In: AAAI, pp. 430–435 (2005)

    Google Scholar 

  72. Mocanu, I.G., Belle, V., Juba, B.: Polynomial-time implicit learnability in SMT. In: ECAI (2020)

    Google Scholar 

  73. Molina, A., Vergari, A., Di Mauro, N., Natarajan, S., Esposito, F., Kersting, K.: Mixed sum-product networks: a deep architecture for hybrid domains. In: Thirty-Second AAAI Conference on Artificial Intelligence (2018)

    Google Scholar 

  74. Morettin, P., Passerini, A., Sebastiani, R.: Advanced SMT techniques for weighted model integration. Artif. Intell. 275, 1–27 (2019)

    Article  MathSciNet  Google Scholar 

  75. Muggleton, S., De Raedt, L.: Inductive logic programming: theory and methods. J. Logic Program. 19, 629–679 (1994)

    Article  MathSciNet  Google Scholar 

  76. Nitti, D., Belle, V., De Laet, T., De Raedt, L.: Planning in hybrid relational mdps. Mach. Learn. 106(12), 1905–1932 (2017)

    Article  MathSciNet  Google Scholar 

  77. Nitti, D., Ravkic, I., Davis, J., Raedt, L.D.: Learning the structure of dynamic hybrid relational models. In: Proceedings of the Twenty-second European Conference on Artificial Intelligence, pp. 1283–1290. IOS Press (2016)

    Google Scholar 

  78. Niu, F., Ré, C., Doan, A., Shavlik, J.: Tuffy: scaling up statistical inference in markov logic networks using an rdbms. Proc. VLDB Endowment 4(6), 373–384 (2011)

    Article  Google Scholar 

  79. Niu, F., Zhang, C., Ré, C., Shavlik, J.W.: Deepdive: web-scale knowledge-base construction using statistical learning and inference. VLDS 12, 25–28 (2012)

    Google Scholar 

  80. Papantonis, I., Belle, V.: On constraint definability in tractable probabilistic models. ar**v preprint ar**v:2001.11349 (2020)

  81. Poole, D.: First-order probabilistic inference. In: Proceedings of the IJCAI, pp. 985–991 (2003)

    Google Scholar 

  82. Poon, H., Domingos, P.: Sum-product networks: a new deep architecture. In: UAI, pp. 337–346 (2011)

    Google Scholar 

  83. Raedt, L.D., Kersting, K., Natarajan, S., Poole, D.: Statistical relational artificial intelligence: logic, probability, and computation. Synth. Lect. Artif. Intell. Mach. Learn. 10(2), 1–189 (2016)

    Article  Google Scholar 

  84. Renkens, J., et al.: ProbLog2: from probabilistic programming to statistical relational learning. In: Roy, D., Mansinghka, V., Goodman, N. (eds.) Proceedings of the NIPS Probabilistic Programming Workshop, December 2012. Accepted

    Google Scholar 

  85. Richardson, M., Domingos, P.: Markov logic networks. Mach. Learn. 62(1), 107–136 (2006)

    Article  Google Scholar 

  86. Rudin, C., Ustun, B.: Optimized scoring systems: toward trust in machine learning for healthcare and criminal justice. Interfaces 48(5), 449–466 (2018)

    Article  Google Scholar 

  87. Russell, S.J.: Unifying logic and probability. Commun. ACM 58(7), 88–97 (2015)

    Article  Google Scholar 

  88. Sanner, S., Abbasnejad, E.: Symbolic variable elimination for discrete and continuous graphical models. In: AAAI (2012)

    Google Scholar 

  89. Shenoy, P., West, J.: Inference in hybrid Bayesian networks using mixtures of polynomials. Int. J. Approximate Reasoning 52(5), 641–657 (2011)

    Article  MathSciNet  Google Scholar 

  90. Singla, P., Domingos, P.M.: Markov logic in infinite domains. In: UAI, pp. 368–375 (2007)

    Google Scholar 

  91. Speichert, S., Belle, V.: Learning probabilistic logic programs in continuous domains. In: ILP (2019)

    Google Scholar 

  92. Sreedharan, S., Srivastava, S., Kambhampati, S.: Hierarchical expertise level modeling for user specific contrastive explanations. In: IJCAI, pp. 4829–4836 (2018)

    Google Scholar 

  93. Suciu, D., Olteanu, D., Ré, C., Koch, C.: Probabilistic databases. Synth. Lect. Data Manage. 3(2), 1–180 (2011)

    Article  Google Scholar 

  94. Valiant, L.G.: Robust logics. Artif. Intell. 117(2), 231–253 (2000)

    Article  MathSciNet  Google Scholar 

  95. Van den Broeck, G.: Lifted Inference and Learning in Statistical Relational Models. Ph.D. thesis. KU Leuven (2013)

    Google Scholar 

  96. Xu, J., Zhang, Z., Friedman, T., Liang, Y., Van den Broeck, G.: A semantic loss function for deep learning with symbolic knowledge. In: International Conference on Machine Learning, pp. 5502–5511 (2018)

    Google Scholar 

  97. Xu, K., Li, J., Zhang, M., Du, S.S., Kawarabayashi, K.-I., Jegelka, S.: What can neural networks reason about? ar**v preprint ar**v:1905.13211 (2019)

  98. Zellers, R., Bisk, Y., Schwartz, R., Choi, Y.: Swag: a large-scale adversarial dataset for grounded commonsense inference. ar**v preprint ar**v:1808.05326 (2018)

  99. Zeng, Z., Van den Broeck, G.: Efficient search-based weighted model integration. ar**v preprint ar**v:1903.05334 (2019)

  100. Zuidberg Dos Martires, P., Dries, A., De Raedt, L.: Knowledge compilation with continuous random variables and its application in hybrid probabilistic logic programming. ar**v preprint ar**v:1807.00614 (2018)

Download references

Author information

Authors and Affiliations

  1. University of Edinburgh, Edinburgh, UK

    Vaishak Belle

  2. Alan Turing Institute, London, UK

    Vaishak Belle

Authors
  1. Vaishak Belle
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Vaishak Belle .

Editor information

Editors and Affiliations

  1. KU Leuven, Heverlee, Belgium

    Jesse Davis

  2. Artois University, Lens, France

    Karim Tabia

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Belle, V. (2020). Symbolic Logic Meets Machine Learning: A Brief Survey in Infinite Domains. In: Davis, J., Tabia, K. (eds) Scalable Uncertainty Management. SUM 2020. Lecture Notes in Computer Science(), vol 12322. Springer, Cham. https://doi.org/10.1007/978-3-030-58449-8_1

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-58449-8_1

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-58448-1

  • Online ISBN: 978-3-030-58449-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation