Structure Mapping Engine - Gmap Creation

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.