In this series of posts, I am going to explain step-by-step how to create a computer program that can understand textual logic puzzles and correctly solve them.
What are textual logic puzzles?
Here is an example of a logic puzzle text (only the first two questions are shown). More examples are shown here.
Six sculptures -- C, D, E, F, G, and H -- are to be exhibited in rooms 1, 2, and 3 of an art gallery.
* Sculptures C and E may not be exhibited in the same room.
* Sculptures D and G must be exhibited in the same room.
* If sculptures E and F are exhibited in the same room,
no other sculpture may be exhibited in that room.
* At least one sculpture must be exhibited in each room,
and no more than three sculptures may be exhibited in any room.
1. If sculpture G is exhibited in room 2 and sculpture E is exhibited in room 3,
which of the following MUST be true?
(A) Sculpture C is exhibited in room 1.
(B) No more than two sculptures are exhibited in room 3.
(C) Sculptures F and H are exhibited in the same room.
(D) Three sculptures are exhibited in room 2.
(E) Sculpture H is exhibited in room 3.
2. If sculptures C and G are exhibited in room 1, which of the following
may NOT be a complete list of the sculpture(s) exhibited in room 2?
(A) Sculpture D
(B) Sculpture E
(C) Sculpture F
(D) Sculptures E and H
(E) Sculptures F and H
Source: Karl Weber, "The Unofficial Guide to the GRE Test", 2000 edition, ARCO Publishing.
These texts consist of two parts:
- A preamble, which is a series of assumptions about relationships between several entities (such as people, objects, locations, and times)
- Multiple-choice questions, each adding some additional assumption, and usually asking which of the given choices must be true, i.e. can be logically inferred from the assumptions.
What is the challenge?
Sometimes a question asks which of the choices may be true, or must/may be false, or which choice describes a complete list of objects that satisfy some conditions, etc.
We can easily understand the meaning of such texts, i.e. the described situations and their constraints, as well as the subsequent questions and possible answers. However, solving them is not trivial for us because that requires logical reasoning: taking into account the given information and constraints, considering all possibilities, and correctly inferring from them the right conclusions. That’s why such logic puzzles are given in some university entry exams (such as the logic games section of LSAT, and previously in the GRE).
In contrast, the opposite is true for computers, or more precisely: for people who program them. Computers can execute millions of operations per second, so a computer program could easily breeze through all potential solutions to a logic puzzle. However, such a program requires an input it can understand, i.e. a formalized version of the puzzles in some precise language. The problem is that computers have no direct understanding of human languages (like English or Spanish). Creating a program that can understand what logic puzzle texts mean, and automatically translating them to a formalized version to be solved, is actually a very big challenge, beyond the state-of-the-art in the field of Natural Language Understanding.
Why is it so challenging? The main reason is that there is no simple one-to-one correspondence between the puzzle texts and their formalization. A computer program that can automatically translate a puzzle text to its formalized version must rely on intricate linguistic knowledge of syntax and semantics. While part of this knowledge has already been developed during the last few decades in fields such as structural semantics and computational semantics, much work remains to be done on extending the scope of this knowledge to support the large variety of linguistic phenomena that appear in puzzle texts.
The following posts describe my project called: Understanding Natural Language Logic Puzzles (UNLLP). The goal of this project is to create a computer system that can understand Natural Language texts of logic puzzles and correctly solve them. This effort originated in my dissertation, and I recently started re-implementing the system with some simplifications and posting its code as open source – you can find it on GitHub. I would like to invite you to join me on this fascinating and fun journey of expanding the abilities of this system, and thereby also expanding our scientific and technical knowledge of the structural semantics of natural language.
Motivation
Why am I doing this? The overall motivation is to advance the state-of-the-art in Natural Language Understanding, specifically pertaining to the development of the required knowledge of Structural Semantics (aka “Formal Semantics” or “Compositional Semantics”). This is the branch of linguistics which, roughly speaking, deals with the literal meaning of sentences after abstracting away the specific concepts of non-functional terms (such as nouns and verbs). It specifies how the structural meaning of a sentence is related to the syntactic structure of the sentence and the meaning of functional expressions (such as “and”, “every”, “each other”, “more than”). See this post for an explanation.
Why is this important? See this post for a survey of why Structural Semantics is needed for NLU applications, and this paper for more about why working on textual logic puzzles is particularly suited for pushing the envelope of this knowledge. For a broader motivation regarding precise understanding of NL texts, see this post.
Content
Here is a general outline of the posts about the project and the system’s code on GitHub. (The links below will be updated once the posts are ready.)
- Background
- System Overview
- System Components
- Tokenization and Morphology
- Syntactic analysis
- Semantic analysis
- Pragmatic analysis
- Logical analysis
- Puzzle Solver
- Linguistic Phenomena
- Events
- Prepositional Phrases
- Relative Clauses
- Quantifiers
- Anaphoric Expressions
- Ellipsis
- Comparative Expressions
- Plurality
- Reciprocals
- “Same” and “Different”
To be continued…