Computing the Similarity of Structured Objects By Means of a Heuristic Search for Correspondences.
Paul Kline · Deep Blue (University of Michigan) · 1983
One way to determine if two structured objects are similar is to find the correspondences that exist between their component parts. The computer programs for detecting similarities that currently exist in the field of artificial intelligence all rely on fairly restrictive assumptions in order to simplify their search for correspondences. Informal examination of the similarities that junior-high school students detect between simple geometry problems suggests that those students will often put a single component of one object into correspondence with two or more components of a related object. These one-to-many mappings contradict the one-to-one assumptions adopted by existing computer programs. The RELAX program was developed in order to find correspondences between structured objects without the need for any one-to-one assumptions. RELAX relies on a small number of heuristic principles to decide when to permit one-to-many mappings in its correspondences. The power of these heuristics is demonstrated by the program's ability to detect a wide range of similarities in the domain of elementary geometry. RELAX also forms generalizations to record the common features of similar objects. The presence of one-to-many mappings in the correspondences between objects leads to exclusive disjunctions in the generalization. RELAX's use of disjunctions avoids the problems encountered by generalization programs that have tried to use variables instead. Two concept-learning experiments were conducted to test psychological predictions derived from RELAX's heuristics. As expected, the order in which training items were presented had substantial impact on subjects' choices on transfer items. The finding that concept learning is not commutative conflicts with any theory of induction based on logical disproof of hypotheses. This finding also conflicts with existing theories of prototype formation. By contrast, the details of the results were in relatively good agreement with the RELAX theory of generalization. Three other concept-learning experiments were conducted to test RELAX's claim that disjunctions of phrases, rather than disjunctions of full propositions, should be employed in generalizations. While no firm conclusion can be drawn from the results of these experiments, the tentative conclusion is that RELAX's claim is false.