Using Program Synthesis and Inductive Logic Programming to solve Bongard Problems

Atharv Sonwane, Sharad Chitlangia, Tirtharaj Dash, Lovekesh Vig, Gautam Shroff, Ashwin Srinivasan

TL;DR

This paper proposes a novel end-to-end system that combines program synthesis (Dreamcoder) with inductive logic programming (ILP) to solve Bongard problems. By generating programs that reconstruct images and then learning abstract concepts from these programs, the system demonstrates an interpretable approach to analogical reasoning, achieving success on a subset of challenging visual reasoning tasks.

What Problem Does This Paper Address?

The paper tackles the challenge of analogical reasoning and concept learning, particularly in the context of visual puzzles like Bongard problems. Bongard problems are designed to test a system's ability to identify abstract concepts from a limited number of positive and negative examples of shapes. Traditional machine learning approaches, especially those relying on massive datasets like deep convolutional neural networks (CNNs), often struggle with these few-shot learning scenarios and the need for interpretable, human-like abstractions. The authors aim to bridge this gap by exploring how program synthesis, which generates explicit programs to create the visual examples, can provide a more suitable representation for learning these abstract concepts.

Methods

The proposed system employs a three-stage approach:

  1. Program Synthesis with Dreamcoder: Dreamcoder, a program induction system, is used to synthesize functional programs (represented as λ-expressions) that generate each image in a Bongard problem. This stage leverages a "generative mode" to discover higher-level program abstractions.
  2. Transducer: This module converts the synthesized functional programs into a first-order logic (FOL) representation. It achieves this by creating a decorated state transition diagram for each program. The "decoration" involves extracting state information, such as positional coordinates and orientation, from the program's execution.
  3. Inductive Logic Programming (ILP): ILP is used to learn a classification theory from the FOL facts generated by the transducer. This learned theory aims to differentiate between positive and negative examples of the Bongard problem's concept. The system uses the Aleph ILP learner and provides comparison-style predicates as background knowledge.

Datasets

The authors synthetically created a dataset of 14 Bongard problems, each consisting of 12 images (6 positive, 6 negative). These problems were designed to be representative of those used in recent studies and include some that have proven difficult for convolutional neural networks.

Key Insights and Ideas

  • Programs as Representations for Analogy: The core idea is that programs generated to reconstruct images can serve as effective intermediate representations for analogical reasoning, offering a "point of view" that simplifies concept learning.
  • Bridging Program Synthesis and ILP: The paper demonstrates a successful integration of Dreamcoder's program synthesis capabilities with ILP's theory learning, creating an end-to-end system for concept abstraction.
  • Interpretable Theories: The ILP component allows for the generation of human-readable theories, which is a significant advantage over black-box models.
  • Few-Shot Learning Success: The approach shows promise in solving problems with limited examples, a key characteristic of analogical reasoning and a weakness of many data-intensive ML methods.

Key Results

The system was able to solve 8 out of the 14 synthetically created Bongard problems. These included simpler tasks like identifying the presence of a circle or clockwise spirals, as well as more complex ones that have challenged CNNs. For instance, problems like BP #21 and BP #60, where CNNs failed even with 20,000 examples, were addressed by this approach. The paper also provides examples of the learned theories, which are interpretable and explain the learned concepts.

Limitations and Future Work

The authors acknowledge several limitations and suggest future directions:

  • Direct Image Input: The current system cannot directly process hand-drawn images; it relies on programs that generate images. Future work could involve comparing program outputs with hand-drawn images using learned metrics.
  • Complexity of Drawings: The system struggles with generating figures that involve a large number of elements. Improving the program synthesis search strategy, perhaps by guiding it with partial program evaluation, could help.
  • State Decoration Augmentation: The current state decoration is limited to positional and orientation information. Augmenting this with learned features from Dreamcoder programs or images, or incorporating more sophisticated feature extractors, could enhance performance.
  • Meta-Rule Learning: The paper suggests investigating the use of multiple learned theories to invent new clauses via inverse-resolution, potentially leading to more generalized and simpler theories for subsequent problems. This could involve meta-rules that allow quantification over predicates, moving towards second-order logic.
  • Integration with Deep Learning: The authors believe there are opportunities for marrying their approach with deep learning techniques.

Summary updated

Abstract

The ability to recognise and make analogies is often used as a measure or test of human intelligence. The ability to solve Bongard problems is an example of such a test. It has also been postulated that the ability to rapidly construct novel abstractions is critical to being able to solve analogical problems. Given an image, the ability to construct a program that would generate that image is one form of abstraction, as exemplified in the Dreamcoder project. In this paper, we present a preliminary examination of whether programs constructed by Dreamcoder can be used for analogical reasoning to solve certain Bongard problems. We use Dreamcoder to discover programs that generate the images in a Bongard problem and represent each of these as a sequence of state transitions. We decorate the states using positional information in an automated manner and then encode the resulting sequence into logical facts in Prolog. We use inductive logic programming (ILP), to learn an (interpretable) theory for the abstract concept involved in an instance of a Bongard problem. Experiments on synthetically created Bongard problems for concepts such as 'above/below' and 'clockwise/counterclockwise' demonstrate that our end-to-end system can solve such problems. We study the importance and completeness of each component of our approach, highlighting its current limitations and pointing to directions for improvement in our formulation as well as in elements of any Dreamcoder-like program synthesis system used for such an approach.
BibTeX
@misc{sonwane2021using,
  author = {Atharv Sonwane and Sharad Chitlangia and Tirtharaj Dash and Lovekesh Vig and Gautam Shroff and Ashwin Srinivasan},
  title = {{Using Program Synthesis and Inductive Logic Programming to solve Bongard Problems}},
  year = {2021},
  eprint = {2110.09947},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2110.09947},
}
Figure