Structure mapping engine

In artificial intelligence and cognitive science, the structure mapping engine (SME) is an implementation in software of an algorithm for analogical matching based on the psychological theory of Dedre Gentner. The basis of Gentner's structure-mapping idea is that an analogy is a mapping of knowledge from one domain (the base) into another (the target). The structure-mapping engine is a computer simulation of the analogy and similarity comparisons.^[1]

The theory is useful because it ignores surface features and finds matches between potentially very different things if they have the same representational structure. For example, SME could determine that a pen is like a sponge because both are involved in dispensing liquid, even though they do this very differently.

Structure mapping theory

Structure mapping theory is based on the systematicity principle, which states that connected knowledge is preferred over independent facts. Therefore, the structure mapping engine should ignore isolated source-target mappings unless they are part of a bigger structure. The SME, the theory goes, should map objects that are related to knowledge that has already been mapped.

The theory also requires that mappings be done one-to-one, which means that no part of the source description can map to more than one item in the target and no part of the target description can be mapped to more than one part of the source. The theory also requires that if a match maps subject to target, the arguments of subject and target must also be mapped. If both these conditions are met, the mapping is said to be "structurally consistent."

Concepts in SME

SME maps knowledge from a source into a target. SME calls each description a dgroup. Dgroups contain a list of entities and predicates. Entities represent the objects or concepts in a description — such as an input gear or a switch. Predicates are one of three types and are a general way to express knowledge for SME.

• Relation predicates contain multiple arguments, which can be other predicates or entities. An example relation is: (transmit (what from to)). This relation has a functor transmit and takes three arguments: what, from, and to.
• Attribute predicates are the properties of an entity. An example of an attribute is (red gear) which means that gear has the attribute red.
• Function predicates map an entity into another entity or constant. An example of a function is (joules power source) which maps the entity power source onto the numerical quantity joules.

Functions and attributes have different meanings, and consequently SME processes them differently. For example, in SME's true analogy rule set, attributes differ from functions because they cannot match unless there is a higher-order match between them. The difference between attributes and functions will be explained further in this section's examples.

All predicates have four parameters. They have (1) a functor, which identifies it, and (2) a type, which is either relation, attribute, or function. The other two parameters (3 and 4) are for determining how to process the arguments in the SME algorithm. If the arguments have to be matched in order, commutative is false. If the predicate can take any number of arguments, N-ary is false. An example of a predicate definition is: (sme:defPredicate behavior-set (predicate) relation :n-ary? t :commutative? t) The predicate's functor is “behavior-set,” its type is “relation,” and its n-ary and commutative parameters are both set to true. The “(predicate)” part of the definition specifies that there will be one or more predicates inside an instantiation of behavior-set.

Algorithm details

The algorithm has several steps.^[2] The first step of the algorithm is to create a set of match hypotheses between source and target dgroups. A match hypothesis represents a possible mapping between any part of the source and the target. This mapping is controlled by a set of match rules. By changing the match rules, one can change the type of reasoning SME does. For example, one set of match rules may perform a kind of analogy called literal similarity, and another performs a kind of analogy called true-analogy. These rules are not the place where domain-dependent information is added, but rather where the analogy process is tweaked, depending on the type of cognitive function the user is trying to emulate.

For a given match rule, there are two types of rules that further define how it will be applied: filter rules and intern rules. Intern rules use only the arguments of the expressions in the match hypotheses that the filter rules identify. This limitation makes the processing more efficient by constraining the number of match hypotheses that are generated. At the same time, it also helps to build the structural consistencies that are needed later on in the algorithm. An example of a filter rule from the true-analogy rule set creates match hypotheses between predicates that have the same functor. The true-analogy rule set has an intern rule that iterates over the arguments of any match hypothesis, creating more match hypotheses if the arguments are entities or functions, or if the arguments are attributes and have the same functor.

In order to illustrate how the match rules produce match hypotheses consider these two predicates:

transmit torque inputgear secondgear (p1)

transmit signal switch div10 (p2)

Here we use true analogy for the type of reasoning. The filter match rule generates a match between p1 and p2 because they share the same functor, transmit. The intern rules then produce three more match hypotheses: torque to signal, inputgear to switch, and secondgear to div10. The intern rules created these match hypotheses because all the arguments were entities.

If the arguments were functions or attributes instead of entities, the predicates would be expressed as:

transmit torque (inputgear gear) (secondgear gear) (p3)

transmit signal (switch circuit) (div10 circuit) (p4)

These additional predicates make inputgear, secondgear, switch, and div10 functions or attributes depending on the value defined in the language input file. The representation also contains additional entities for gear and circuit.

Depending on what type inputgear, secondgear, switch, and div10 are, their meanings change. As attributes, each one is a property of the gear or circuit. For example, the gear has two attributes, inputgear and secondgear. The circuit has two attributes, switch and circuit. As functions inputgear, secondgear, switch, and div10 become quantities of the gear and circuit. In this example, the functions inputgear and secondgear now map to the numerical quantities “torque from inputgear” and “torque from secondgear,” For the circuit the quantities map to logical quantity “switch engaged” and the numerical quantity “current count on the divide by 10 counter.”

SME processes these differently. It does not allow attributes to match unless they are part of a higher-order relation, but it does allow functions to match, even if they are not part of such a relation. It allows functions to match because they indirectly refer to entities and thus should be treated like relations that involve no entities. However, as next section shows, the intern rules assign lower weights to matches between functions than to matches between relations.

The reason SME does not match attributes is because it is trying to create connected knowledge based on relationships and thus satisfy the systematicity principle. For example, if both a clock and a car have inputgear attributes, SME will not mark them as similar. If it did, it would be making a match between the clock and car based on their appearance — not on the relationships between them.

When the additional predicates in p3 and p4 are functions, the results from matching p3 and p4 are similar to the results from p1 and p2 except there is an additional match between gear and circuit and the values for the match hypotheses between (inputgear gear) and (switch circuit), and (secondgear gear) and (div10 circuit), are lower. The next section describes the reason for this in more detail.

If the inputgear, secondgear, switch, and div10 are attributes instead of entities, SME does not find matches between any of the attributes. It finds matches only between the transmit predicates and between torque and signal. Additionally, the structural-evaluation scores for the remaining two matches decrease. In order to get the two predicates to match, p3 would need to be replaced by p5, which is demonstrated below.

transmit torque (inputgear gear) (div10 gear)(p5)

Since the true-analogy rule set identifies that the div10 attributes are the same between p5 and p4 and because the div10 attributes are both part of the higher-relation match between torque and signal, SME makes a match between (div10 gear) and (div10 circuit) — which leads to a match between gear and circuit.

Being part of a higher-order match is a requirement only for attributes. For example, if (div10 gear) and (div10 circuit) are not part of a higher-order match, SME does not create a match hypothesis between them. However, if div10 is a function or relation, SME does create a match.

Structural evaluation score

Once the match hypotheses are generated, SME needs to compute an evaluation score for each hypothesis. SME does so by using a set of intern match rules to calculate positive and negative evidence for each match. Multiple amounts of evidence are correlated using Dempster's rule [Shafer, 1978] resulting in positive and negative belief values between 0 and 1. The match rules assign different values for matches involving functions and relations. These values are programmable, however, and some default values that can be used to enforce the systematicity principle are described in [Falkenhainer et al., 1989].

These rules are:

1. If the source and target are not functions and have the same order, the match gets +0.3 evidence. If the orders are within 1 of each other, the match gets +0.2 evidence and -0.05 evidence.
2. If the source and target have the same functor, the match gets 0.2 evidence if the source is a function and 0.5 if the source is a relation.
3. If the arguments match, the match gets +0.4 evidence. The arguments might match if all the pairs of arguments between the source and target are entities, if the arguments have the same functors, or it is never the case that the target is an entity but the source is not.
4. If the predicate type matches, but the elements in the predicate do not match, then the match gets -0.8 evidence.
5. If the source and target expressions are part of a matching higher-order match, add 0.8 of the evidence for the higher-order match.

In the example match between p1 and p2, SME gives the match between the transmit relations a positive evidence value of 0.7900, and the others get values of 0.6320. The transmit relation receives the evidence value of 0.7900 because it gains evidence from rules 1, 3, and 2. The other matches get a value of 0.6320 because 0.8 of the evidence from the transmit is propagated to these matches because of rule 5.

For predicates p3 and p4, SME assigns less evidence because the arguments of the transmit relations are functions. The transmit relation gets positive evidence of 0.65 because rule 3 no longer adds evidence. The match between (input gear) and (switch circuit) becomes 0.7120. This match gets 0.4 evidence because of rule 3, and 0.52 evidence propagated from the transmit relation because of rule 5.

When the predicates in p3 and p4 are attributes, rule 4 adds -0.8 evidence to the transmit match because — though the functors of the transmit relation match — the arguments do not have the potential to match and the arguments are not functions.

To summarize, the intern match rules compute a structural evaluation score for each match hypothesis. These rules enforce the systematicity principle. Rule 5 provides trickle-down evidence in order to strengthen matches that are involved in higher-order relations. Rules 1, 3. and 4 add or subtract support for relations that could have matching arguments. Rule 2 adds support for the cases when the functors match. thereby adding support for matches that emphasize relationships.

The rules also enforce the difference between attributes, functions, and relations. For example, they have checks which give less evidence for functions than relations. Attributes are not specifically dealt with by the intern match rules, but SME's filter rules ensure that they will only be considered for these rules if they are part of a higher-order relation, and rule 2 ensures that attributes will only match if they have identical functors.

Gmap creation

The rest of the SME algorithm is involved in creating maximally consistent sets of match hypotheses. These sets are called gmaps. SME must ensure that any gmaps that it creates are structurally consistent; in other words, that they are one-to-one — such that no source maps to multiple targets and no target is mapped to multiple sources. The gmaps must also have support, which means that if a match hypothesis is in the gmap, then so are the match hypothesis that involve the source and target items.

The gmap creation process follows two steps. First, SME computes information about each match hypothesis — including entity mappings, any conflicts with other hypotheses, and what other match hypotheses with which it might be structurally inconsistent.

SME then uses this information to merge match hypotheses — using a greedy algorithm and the structural evaluation score. It merges the match hypotheses into maximally structurally consistent connected graphs of match hypotheses. Then it combines gmaps that have overlapping structure if they are structurally consistent. Finally, it combines independent gmaps together while maintaining structural consistency.

Comparing a source to a target dgroup may produce one or more gmaps. The weight for each gmap is the sum of all the positive evidence values for all the match hypotheses involved in the gmap. For example, if a source containing p1 and p6 below, is compared to a target containing p2, SME will generate two gmaps. Both gmaps have a weight of 2.9186.

Source:

transmit torque inputgear secondgear (p1)

transmit torque secondgear thirdgear (p6)

Target: transmit signal switch div10 (p2)

These are the gmaps which result from comparing a source containing a p1 and p6 and a target containing p2.

Gmap No. 1:

(TORQUE SIGNAL) (INPUTGEAR SWITCH) (SECONDGEAR DIV10) (*TRANSMIT-TORQUE-INPUTGEAR-SECONDGEAR *TRANSMIT-SIGNAL-SWITCH-DIV10) 

Gmap No. 2:

(TORQUE SIGNAL) (SECONDGEAR SWITCH) (THIRDGEAR DIV10) (*TRANSMIT-TORQUE-SECONDGEAR-THIRDGEAR *TRANSMIT-SIGNAL-SWITCH-DIV10) 

The gmaps show pairs of predicates or entities that match. For example, in gmap No. 1, the entities torque and signal match and the behaviors transmit torque inputgear secondgear and transmit signal switch div10 match. Gmap No. 1 represents combining p1 and p2. Gmap No. 2 represents combining p1 and p6. Although p2 is compatible with both p1 and p6, the one-to-one mapping constraint enforces that both mappings cannot be in the same gmap. Therefore, SME produces two independent gmaps. In addition, combining the two gmaps together would make the entity mappings between thirdgear and div10 conflict with the entity mapping between secondgear and div10.

Criticisms

Chalmers, French, and Hofstadter [1992] criticize SME for its reliance on manually constructed LISP representations as input. They argue that too much human creativity is required to construct these representations; the intelligence comes from the design of the input, not from SME. Forbus et al. [1998] attempted to rebut this criticism. Morrison and Dietrich [1995] tried to reconcile the two points of view. Turney [2008] presents an algorithm that does not require LISP input, yet follows the principles of Structure Mapping Theory. Turney [2008] state that their work, too, is not immune to the criticism of Chalmers, French, and Hofstadter [1992].

In her article How Creative Ideas Take Shape,^[3] Liane Gabora writes "According to the honing theory of creativity, creative thought works not on individually considered, discrete, predefined representations but on a contextually-elicited amalgam of items which exist in a state of potentiality and may not be readily separable. This leads to the prediction that analogy making proceeds not by mapping correspondences from candidate sources to target, as predicted by the structure mapping theory of analogy, but by weeding out non-correspondences, thereby whittling away at potentiality."

References

1. "Structure-Mapping: A computational model of analogy and similarity". Northwestern University. Retrieved 2012-01-16.
2. Brian Falkenhainer; Kenneth D. Forbus; Dedre Gentner (1989). "The Structure-Mapping Engine: Algorithm and Examples" (PDF). Artificial Intelligence. 41: 1–63. CiteSeerX 10.1.1.26.6432. doi:10.1016/0004-3702(89)90077-5. Retrieved 2012-01-16.
3. Gabora, Liane (2015). "How Creative Ideas Take Shape". arXiv:1501.04406 [q-bio.NC].

Further reading

• Papers by the Qualitative Reasoning Group at Northwestern University
• Chalmers, D. J., French, R. M., & Hofstadter, D. R.: 1992, High-level perception, representation, and analogy: A critique of artificial intelligence methodology. Journal of Experimental & Theoretical Artificial Intelligence, 4(3), 185–211.
• Falkenhainer, B: 2005, Structure Mapping Engine Implementation. sme implementation
• Falkenhainer, B, Forbus, K and Gentner, D: 1989, "The structure-mapping engine: Algorithm and examples". Artificial Intelligence, 20(41): 1–63.
• Forbus, K.D., Gentner, D., Markman, A.B., and Ferguson, R.W.: 1998, Analogy Just Looks Like High Level Perception: Why a Domain-General Approach to Analogical Mapping is Right. Journal of Experimental and Theoretical Artificial Intelligence, 10(2), 231–257.
• French, RM: 2002. "The Computational Modeling of Analogy-Making". Trends in Cognitive Sciences, 6(5), 200–205.
• Gentner, D: 1983, "Structure-mapping: A Theoretical Framework for Analogy", Cognitive Science 7(2)
• Shafer, G: 1978, A Mathematical Theory of Evidence, Princeton University Press, Princeton, New Jersey. ISBN 0-691-08175-1.
• Morrison, C.T., and Dietrich, E.: 1995, Structure-Mapping vs. High-level Perception: The Mistaken Fight Over The Explanation of Analogy. Proceedings of the Seventeenth Annual Conference of the Cognitive Science Society, 678–682.
• Turney, P.D.: 2008, The latent relation mapping engine: Algorithm and experiments, Journal of Artificial Intelligence Research (JAIR), 33, 615–655.