Workshop 2011

In spring semester of 2011, I collaborated with Prof. Nachum Dershowitz. Dr. Roni Katzir, and Dr. Kfir Bar to lead a NLP workshop (0368-3500-49) for undergrad students in Computer Science at Tel Aviv University.

I led a team of students on a project that aimed to create a basic version of a system that can understand texts of logic puzzles and solve them correctly. Essentially, reproduce some of the work I did for the PULC project. Since the programming required to create such a system is extensive, the aim was to get to a point where the system can solve one textual logic puzzle, but do it in a generic way that can be extended to other puzzles. The following is some material from that workshop.

Project Description

In this project, you will work on programming a system that can solve logic puzzles given their textual descriptions (an example puzzle is shown here).

Constructing such a system is a major and interesting challenge in the fields of Natural Language Processing (NLP), Artificial Intelligence (AI), and Automated Reasoning (AR), and depends on knowledge from Linguistics, Logic, and Knowledge Representation. For a human, the easy part is reading and understanding the English description and the hard part is solving the puzzle (that’s why such puzzles are given on exams such as LSAT and formerly the GRE). For a computer, it’s the reverse – once a puzzle is formalized as a simple Constraint-Satisfaction Problem (CSP), it is quickly solved, but the hard part is programming the computer to understand the English text and translate it to the CSP.

An interesting thing about this task is that significant progress can be made on it because the puzzles are logical. A lot of precise linguistic knowledge of English is needed (mostly of functional words), but relatively little world knowledge is required (although some may still be needed — for exampe, the sculptures puzzle does not explicitly mention that no sculpture may be exhibited in more than one room at the same time, but this piece of knowledge is crucial for getting the right answer. Humans reading the text know this kind of “commonsense knowledge” naturally but a computer must be given such knowledge explicitly).

While a system that solves logic puzzles is not a real-world application in itself, there are useful applications that are expansions of it, including NL queries to databases (imagine writing an English question instead of an SQL query), understanding of regulation texts, and more. The logic puzzles system necessarily requires a high-level of precision in representing the text’s meaning (only “slightly wrong” interpretations yield completely wrong answers to the puzzle). This level of precision can then be combined with formalized knowledge about a specific domain/topic (such as: engines, or chemistry) so that the computer can read documents about that topic, answer complex questions about the information in those documents (i.e. not merely retrieving a few sentences based on keyword searching), summarize the documents in a useful manner, and even translate them to other languages with a much higher quality than is possible without a precise level of language analysis and use of domain knowledge.

In the workshop, the students will learn about and program (in Java) the various components required for the system, including: morphological, syntactic, semantic, anaphoric, and logical analysis levels. The students will test the components on real logic puzzle texts, and also perform some interesting linguistic analysis of the texts.

Prerequisites: Object-Oriented Programming in Java, Logic for Computer Science. Recommended but not necessary: Introduction to Artificial Intelligence. All necessary knowledge will be given in the workshop.

Link: Powerpoint Presentation

Further reading:
Automatic Solving of Textual Logic Puzzles – an overview of issues and solutions
Logic Puzzles: A New Test-Suite for Compositional Semantics and Reasoning
PULC website

Interim report submitted by the students: link