An Overview of Logic in AI and Machine Learning
TL;DR: Logic can help AI and ML in complex domains or in domains with very little data.
In this post, we will go through an overview of logic in AI and ML and look at the ways it’s used in AI/ML.
By logic we mean symbolic, knowledge-based, reasoning and other similar approaches to AI that differ, at least on the surface, from existing forms of classical machine learning and deep learning. It is crucial to keep in mind just as there are many forms of machine learning; there are many different forms of logic-based approaches to AI with their own sets of tradeoffs.
Very briefly, logic-based AI systems can be thought of as high-level programming systems that can easily encode human knowledge in a compact and usable manner.
A quick of overview of classical logic
Starting with the simplest of logic systems, we have propositional logic (sometimes called zero-order logic). Within propositional logic, we have objects known as sentences or formulae that encode information. They denote some statement about the world. For building blocks, we have basic sentences known as atoms, usually denoted by “P, Q, R, S, …..” For example, P might stand for “It is raining” and is an atom.
Atoms can combine with logical connectives such as “and, or, if then” to form more sentences called compound formulae.
Formulae give us a way to represent information. Then, how do we go from information we already have to new information? We do this through reasoning or inference. Propositional logic comes equipped with a set of schemes called inference methods. Inference methods can be thought of as little programs that take a set of sentences as input and spit out one or more sentences. The figure below shows a very straightforward inference method that takes in a formula that represents “Q and R” and produces as output a formula R. For example, if the input is “It is sunny, and It is warm,” the output will be “It is sunny.”
All logics come equipped with a set of inference methods like the above. These primitive inbuilt methods of a logic play a role similar to that of the standard library in any programming language. Given these methods, we can combine them to form even more sophisticated methods such as the one shown below, just like you can create large programs from a few simpler primitives.
Propositional logic is a good starting place for pedagogical reasons but is unwieldy for modeling domains with a large number of objects. For example, let us say we want to write down the constraints that a Sudoku puzzle should satisfy. Let us say we have for each number k and each row i and column j an atom A_ijk that stands for “row i and column k contain number k”. With this, we can quickly write down constraints for Sudoku in propositional logic [8]. For example, the sentence in the figure below states that the number 5 should appear in the first row.
We can similarly write down other constraints for other numbers [8]. We will have a total of 9³ = 729 atoms in our constraints. Each atom can be true or false, giving us a total of possible 2⁷²⁹ states (much much greater than the number of physical atoms in our universe).
First-order logic improves upon propositional logic by introducing atoms that can take in arguments that stand in for objects in a domain. In first-order logic, instead of having an atom A_ijk for every combination of i, j and k, we will have a single atom that takes in those variables as arguments. For example, A(1,3,5) says that row 1 and column 3 has a 5 in it. The figure below says that one column exists in row 1 that has the number 5 in it. As you can see, the representation for “Row 1 has a 5 in some column” is much more compact in first-order logic.
Other logics
First-order logic forms the basis of many modern logic systems used in research and industry. Many other logic systems build upon and extend first-order logic (e.g., second-order logic, third-order logic, higher-order logic, and modal logic). Each logic adds new a dimension or feature that makes it easy to model some aspect of the world. For example, logics that are known as temporal logics are used to model time and change.
Now that we have gone through a very very quick overview of logic, what are some modern uses of logic in areas that overlap with AI and ML?
Applications of Logic in AI and ML
1. Automated Discovery in Science
One of the most successful uses of logic has been in the scientific domain to represent structured scientific knowledge. In 2007, a group in Wales and England created a system named Adam (Automated Discovery and Analysis Machine) [9].
Adam can automatically form scientific hypotheses, perform experiments to test hypotheses, and record results of experiments. This was the first automated system to discover non-trivial scientific information. Adam successfully identified the function of some genes in yeast. In this system, the hypotheses, the results of the experiments, and the conclusions were all expressed in a logic.
When the time comes for the history of artificial intelligence (AI) to be written, the algorithm that gets the job is likely to flag 12 June 2007 as worthy of note. That was the day that a robot called Adam ended humanity’s monopoly on the discovery of scientific knowledge — by identifying the function of a yeast gene
— Nick Fleming, May 2018, Nature Spotlight
More recently, Eve, a system similar to Adam, has been used to speed up drug discovery.
(Read more here: https://www.cam.ac.uk/research/news/artificially-intelligent-robot-scientist-eve-could-boost-search-for-new-drugs)
2. Inductive Programming
In inductive programming, the goal is to learn a computer program given a small set of input and output examples. For example, let us say we need to learn a function for deciding whether an input number is even or odd. Our examples might be just the handful shown below:
0, 2, 4, 8, 12: Yes
1, 3, 7, 9: No
Inductive programming deals with producing systems that can learn from such examples. Such systems are usually formulated using logic. State-of-the-art inductive programming systems can learn complex recursive programs from just a few examples. Consider the two input/output examples shown below. The goal here is to learn a program that finds the first character in an input string that is duplicated.
Metaopt [1] can find an efficient and recursive Prolog program that can solve this task. The program is shown below:
Where is this useful? It is estimated that data scientists spend a large portion of their time writing programs for transforming data. Inductive programming methods have been used to learn data cleaning and transformation programs [6].
3. Automation of Mathematical Reasoning
We showed with the Sudoku example above how first-order logic is more expressive than propositional logic. Is there a limit to what we can model with it? First-order logic alone is quite powerful. It is powerful enough to model almost all of classical mathematics. If you are working within the confines of standard mathematics, then you can state any goal that you want to prove (a conjecture) and have your work (a mathematical proof) automatically checked by a machine. For examples of this in action, see the Journal of Formalized Mathematics, a journal that publishes results in math that have been machine verified. Reasoning and inference systems have also been used to prove previously unproven results, rather than just simply check proofs produced by a human. One of the most impressive feats of machine reasoning occurred when a first-order logic reasoner was able to prove an open math conjecture that was unsolved for 60 years.
4. Verification of Computer Systems (including Machine Learning Systems)
Beyond mathematics, logics rooted in first-order logic and similar systems are employed in verifying computer systems. This field is known as formal verification. In formal verification, you have a computer system S, a property P and you have to verify in a relatively iron-clad manner that the property is valid. For example, see ACL2 (http://www.cs.utexas.edu/users/moore/acl2/), an industrial-strength system used to verify hardware and software systems. In recent years, similar approaches have been used to verify and provide guarantees for deep learning systems. In [5], Huang et al. use logic-based reasoning tools to check for the presence of adversarial inputs in feed forward multi-layer neural networks.
4. Logic-like Systems along with Machine Learning Models
Along with the growing number of applications and domains that use machine learning models, there are still some scenarios that require the use of logic-like systems along with ML models. For example, many fraud detection systems, employ one or more machine learning models along with a large body of hand-crafted rules. These rules are necessary for many reasons. In the fraud detection domain, these rules may capture new and evolving patterns for fraud for which there may not be enough data to train new models [7]. For some recent research that looks at different ways of incorporating logic with deep learning systems see: [2], [3], and [4].
This concludes our brief overview of logic and its applications in AI and ML. As mentioned before, we have just scratched the surface of a vast research area. To keep the post relatively short, we omitted many systems and applications. In future posts, we will dive deeper into specific applications and systems and look at some ways that you can incorporate logic into your deep learning models.
References
[1] Cropper, A. and Muggleton, S.H., 2019. Learning Efficient Logic Programs. Machine Learning, 108(7), pp.1063–1083. http://andrewcropper.com/pubs/mlj18-metaopt.pdf
[2] Xu, J., Zhang, Z., Friedman, T., Liang, Y. and Broeck, G., 2018, July. A Semantic Loss Function for Deep Learning with Symbolic Knowledge. In International Conference on Machine Learning (pp. 5498–5507). Vancouver https://arxiv.org/abs/1711.11157
[3] Manhaeve, R., Dumancic, S., Kimmig, A., Demeester, T. and De Raedt, L., 2018. DeepProblog: Neural Probabilistic Logic Programming. In Advances in Neural Information Processing Systems (pp. 3749–3759). http://papers.nips.cc/paper/7632-deepproblog-neural-probabilistic-logic-programming
[4] Cohen, W.W., Yang, F. and Mazaitis, K.R., 2017. Tensorlog: Deep Learning Meets Probabilistic DBs. arXiv preprint arXiv:1707.05390. https://arxiv.org/abs/1707.05390
[5] Huang, X., Kwiatkowska, M., Wang, S. and Wu, M., 2017, July. Safety Verification of Deep Neural Networks. In International Conference on Computer Aided Verification (pp. 3–29). Springer, Cham. https://arxiv.org/pdf/1610.06940.pdf
[6] Raza, M. and Gulwani, S., 2017, February. Automated data extraction using predictive program synthesis. In Thirty-First AAAI Conference on Artificial Intelligence.
[7] https://stripe.com/radar/guide#rules-and-manual-reviews
[8] https://www.cs.ox.ac.uk/people/james.worrell/lec2-2015.pdf
[9] King, R.D., Rowland, J., Oliver, S.G., Young, M., Aubrey, W., Byrne, E., Liakata, M., Markham, M., Pir, P., Soldatova, L.N. and Sparkes, A., 2009. The Automation of Science. Science, 324(5923), pp.85–89.
