Program synthesis performance constrained by non-linear spatial relations in Synthetic Visual Reasoning Test

Lu Yihe, Scott C. Lowe, Penelope A. Lewis, Mark C. W. van RossumarXiv 2019 · OpenReview

TL;DR

This paper re-evaluates the Synthetic Visual Reasoning Test (SVRT), a benchmark for abstract visual reasoning, by proposing a novel way to compare human and machine performance. They show that program synthesis (PS) can achieve impressive few-shot learning on SVRT, but its performance is bottlenecked by the quality of image parsing, particularly for problems involving non-linear spatial relations.

What Problem Does This Paper Address?

The SVRT was designed to highlight the limitations of machines in abstract visual reasoning compared to humans. While deep learning models have made strides, they still struggle with certain SVRT problems, especially those requiring abstract reasoning beyond simple pattern matching. Previous work showed that program synthesis (PS) could perform unsupervised, few-shot learning on some SVRT tasks, outperforming traditional machine learning models. However, direct comparisons between human and machine performance were complicated by different experimental protocols and evaluation metrics. This paper aims to bridge this gap by proposing a unified framework for comparison and investigating the specific limitations of PS on SVRT.

Methods

The authors propose a quantitative reinterpretation of machine performance to make it directly comparable to human performance metrics. They also introduce a new way to group SVRT problems based on two core characteristics: shape specification (SS) and location relation (LR), each with four complexity levels. This allows for a more systematic analysis of performance across different problem types. Crucially, they improve the program synthesis classifier by correcting errors in the image parsing process, which is a critical bottleneck for PS. They then compare the performance of their improved PS classifier, AdaBoost, and state-of-the-art Convolutional Neural Networks (CNNs) against human performance on these categorized SVRT problems.

Datasets

The paper uses the original 23 problems from the Synthetic Visual Reasoning Test (SVRT) dataset. They do not introduce a new benchmark but rather re-analyze and categorize the existing SVRT problems.

Key Insights and Ideas

  • Fairer Comparison: A new method for reinterpreting machine accuracy (α) into a "success probability" (β*(α)) allows for a more direct comparison with human success rates (β), accounting for the different experimental setups.
  • Parsing is Key for PS: The performance of program synthesis on SVRT is highly sensitive to the quality of image parsing. Correcting errors in parsing significantly boosts PS performance, especially for problems with complex spatial relationships.
  • PS Struggles with Non-Linear Relations: Program synthesis, relying on symbolic computation, faces significant challenges with problems involving non-linear spatial relations (e.g., equidistance between shapes). This is due to the combinatorial complexity of verifying such relations within the PS framework.
  • CNNs Excel at Spatial Relations, PS at Abstract Rules: While CNNs are strong at detecting spatial relations, they struggle with problems requiring abstract shape identity comparisons. PS, on the other hand, excels at learning abstract rules but is limited by its parsing and symbolic verification capabilities.
  • Problem Categorization Matters: Grouping SVRT problems by shape specification and location relation reveals distinct strengths and weaknesses of different AI approaches, offering a more nuanced understanding than simply looking at overall performance.

Key Results

  • The improved PS classifier, with corrected parsings, achieved performance comparable to or even surpassing human performance on many SVRT problems.
  • However, the PS classifier still performed poorly on problems involving non-linear spatial relations (LR=3), achieving only chance-level performance.
  • CNNs, while generally strong, showed weaknesses in detecting identical shapes (SS=2) in certain problem types.
  • The authors' reinterpretation of machine performance showed that the PS classifier, with corrected parsings, achieved an average success probability of 88.99%, surpassing the 86.30% average for humans and 81.40% for the original PS.

Limitations and Future Work

  • PS Scalability: The paper acknowledges that program synthesis has a significant scalability problem, especially with complex input dimensions and non-linear computations. This limits its ability to solve problems involving intricate spatial relationships without substantial computational resources.
  • Generalization of PS: While PS can learn from few examples, its reliance on explicit parsing can make it brittle. If parsings contain even minor misleading variations, the PS program might incorrectly generalize, unlike statistical models that can balance out such errors with more data.
  • Future Work: The authors suggest that combining symbolic approaches like PS with neural approaches (like CNNs) could lead to greater machine performance. They also highlight the need to fix the PS classifier's inability to handle distance relations and develop training strategies that prevent performance decline in such cases. Further research could explore how to make PS more robust to parsing errors and how to better leverage prior knowledge in machine learning for tasks like SVRT.

Summary updated

Abstract

Despite remarkable advances in automated visual recognition by machines, some visual tasks remain challenging for machines. Fleuret et al. (2011) introduced the Synthetic Visual Reasoning Test (SVRT) to highlight this point, which required classification of images consisting of randomly generated shapes based on hidden abstract rules using only a few examples. Ellis et al. (2015) demonstrated that a program synthesis approach could solve some of the SVRT problems with unsupervised, few-shot learning, whereas they remained challenging for several convolutional neural networks trained with thousands of examples. Here we re-considered the human and machine experiments, because they followed different protocols and yielded different statistics. We thus proposed a quantitative reintepretation of the data between the protocols, so that we could make fair comparison between human and machine performance. We improved the program synthesis classifier by correcting the image parsings, and compared the results to the performance of other machine agents and human subjects. We grouped the SVRT problems into different types by the two aspects of the core characteristics for classification: shape specification and location relation. We found that the program synthesis classifier could not solve problems involving shape distances, because it relied on symbolic computation which scales poorly with input dimension and adding distances into such computation would increase the dimension combinatorially with the number of shapes in an image. Therefore, although the program synthesis classifier is capable of abstract reasoning, its performance is highly constrained by the accessible information in image parsings.
BibTeX
@misc{yihe2019program,
  author = {Lu Yihe and Scott C. Lowe and Penelope A. Lewis and Mark C. W. van Rossum},
  title = {{Program synthesis performance constrained by non-linear spatial relations in Synthetic Visual Reasoning Test}},
  year = {2019},
  eprint = {1911.07721},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1911.07721},
}

Loading related content...

Figure