Machine Discovery Based on Numerical Data Generated in Computer Experiments

AAAI 1996

TL;DR

This paper introduces EXPEDITION, a novel system for discovering mathematical theorems in plane geometry by generating and analyzing figures. Unlike previous systems that rely heavily on pre-existing knowledge, EXPEDITION uses simple heuristics to draw figures and identify emergent relationships, successfully rediscovering known theorems and uncovering new ones.

What Problem Does This Paper Address?

The discovery of new theorems and formulas in science has historically relied heavily on experimentation to gather data. While many AI systems aim to mimic this discovery process, they often require substantial domain-specific knowledge to interpret experimental results or plan experiments. This creates a barrier for discovering knowledge in domains where such initial knowledge is scarce or for systems that need to operate with minimal pre-programmed understanding. The authors highlight that mathematical discovery, particularly in geometry, is unique because systems can generate their own data (figures) internally, rather than relying on external, real-world experiments. However, even in this context, existing systems often need pre-defined experimental plans or extensive background knowledge. This paper addresses the challenge of building a discovery system that can acquire useful theorems from experimental data without relying on significant pre-existing domain knowledge, specifically focusing on plane geometry.

Methods

EXPEDITION employs a "generate-and-test" approach centered around computer experimentation. The core methodology involves:

  • Figure Generation: The system automatically generates geometric figures by drawing lines one by one on a base figure (initially a circle). This process is guided by simple heuristics that define "focus points" (e.g., circle center, points on the circumference) and rules for drawing lines between them.
  • Data Acquisition: After drawing each line, the system observes the figure and extracts numerical data, specifically the lengths of line segments and measures of angles.
  • Theorematic Candidate Acquisition: Expressions representing relationships between these numerical data points (e.g., equality of lengths, sums of angles) are generated. These are termed "theorematic candidates."
  • Selection of Useful Candidates: To avoid combinatorial explosion and focus on novel discoveries, the system prioritizes expressions that involve line segments and angles newly generated by the last added line. This heuristic assumes that relationships involving these new elements are more likely to represent new insights.
  • Verification: Theorematic candidates are verified by re-drawing the original figure multiple times, introducing slight variations. A candidate that holds true across all these re-drawn figures is considered a general and useful theorem. This process is analogous to human scientists testing hypotheses across multiple experimental conditions.

Datasets

Not discussed in the paper. The system generates its own data through computer experiments (drawing figures).

Key Insights and Ideas

  • Experimentation as a Knowledge Acquisition Engine: The paper strongly advocates for experimentation as a fundamental mechanism for AI discovery, particularly when initial knowledge is limited. It shows how generating and analyzing data from internal "computer experiments" can lead to significant insights.
  • The Power of Emergent Properties: By drawing figures incrementally and observing the relationships that emerge, EXPEDITION leverages the "emergent property" of visual information, similar to how humans use diagrams.
  • Heuristics for Efficiency: The system's success hinges on two simple, domain-independent heuristics: drawing figures by adding lines and focusing on newly generated geometric elements. These heuristics effectively manage complexity and guide the discovery process without requiring deep domain knowledge.
  • Inductive Discovery in Mathematics: While mathematical theorems are often derived deductively, EXPEDITION demonstrates a powerful inductive approach by inferring general rules from specific numerical observations of generated figures.
  • Internal Experimentation for Verification: The ability to re-draw figures and test candidates internally provides a robust verification mechanism, analogous to scientific validation, without needing external resources.

Key Results

EXPEDITION successfully rediscovered several well-known theorems, including:

  • The relationship between a tangential line and a circle's radius.
  • The equality of two line segments from an external point to a circle's contact points.
  • The angle bisector property in inscribed triangles.
  • Power theorems.
  • Thales' theorem.
  • The property of opposite angles in inscribed quadrilaterals summing to 180 degrees.
  • Equality of inscribed angles subtended by the same arc.

Furthermore, the system discovered several new, non-trivial theorems that were not found in conventional geometry texts, demonstrating its ability to go beyond rediscovery. The paper notes that even with a large number of initial theorematic candidates, the verification process efficiently filters out invalid ones. For instance, after hypothesizing 23 candidates from one figure, only 10 were invalidated by observing a single re-drawn figure, with the rest being true theorems.

Limitations and Future Work

  • Limitations:
    • The current system is limited to the domain of plane geometry.
  • The discovery of theorems relies on the specific heuristics used for figure generation and candidate selection.
  • While the paper mentions that re-drawing figures a few times is sufficient for verification, the exact number and nature of variations needed for robust verification across all possible theorems are not deeply explored.
  • Future Work:
    • The authors suggest that this inductive discovery approach is desirable for various domains where computer-controlled experimentation is feasible.
  • Extending the system to other mathematical domains or even scientific domains where data can be generated computationally would be a natural next step.
  • Further research into more sophisticated heuristics for figure generation and candidate selection could enhance the system's discovery capabilities.

Summary updated

BibTeX
@inproceedings{1996machine,
  title = {{Machine Discovery Based on Numerical Data Generated in Computer Experiments}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure