The Competence of Sub-Optimal Theories of STructure Mapping on Hard Analogies

The Competence of Sub-Optimal Theories of Structure Mapping on Hard Analogies

Tony Veale,

School of Computer Applications, Dublin City University, Dublin, Ireland.

Abstract

Structure-mapping is a provably NP-Hard problem which is argued to lie at the core of the human metaphoric and analogical reasoning faculties. This NP-Hardness has meant that early attempts at optimal solutions to the problem have had to be augmented with sub-optimal heuristics to ensure tractable performance. This paper considers various grounds for qualifying the competence of such heuristic approaches, and offers an evaluation of the sub-optimal performance of three different models of analogy, SME, ACME and Sapper.

L Introduction

Metaphor interpretation and Analogical reasoning are two, closely related, cognitive faculties which rely upon structure mapping to generate coherent and systematic correspondences between two domains of discourse. But since structure-mapping is clearly a graph-isomorphism process which must consider a combinatorial number of such correspondences to generate an optimal mapping, it is both intuitively and provably an NP-hard problem.

A variety of computational approaches to the problem have been described in the AI literature, such as the Structure Mapping Engine (SME) of [Falkenhainer et a/. 1989), the Analogical Constraint Mapping Engine (ACME) of [Holyoak and Thagard 1989) and the Sapper model of [Veale eta/ 1996a,b). The first of these, SME, provided an optimal (and thus potentially exponential) solution to the problem, followed by a heuristic, sub-

(control Composer Orchestra)

(control Composer Baton)

(part Orchestra Percussion)

~~~tr~~::e:~~eM~~~::; Concert_ Theatre) : .. ··· .. :~.>/:~.:

(attr Composer Artistic)

e.

Mark Keane,

Dept. of Computer Science, University of Dublin, Trinity College, Dublin, Ireland.

optimal greedy-merge approach (see [Oblinger and Forbus 1990)) and later, an incremental approach (see [Forbus eta/. 1994)). Falkenhainer eta/. [1989] provide a complexity analysis of SME that identifies several factors leading to factorial explosion, but argued that analogies producing such difficulties were unlikely to occur. At its heart the original SME is a forest-matching mechanism, which extends known results regarding the O(N 2 ) complexity of determining sub-tree isomorphism (e.g. , see [Garey & Johnson 1979], [Akutsu, 1992)) to forests of inter-tangled tree representations. Layered on top of this forest matcher is a factorial merge process which combines the results of the polynomial sub-tree matching phase (called partial maps, or pmaps) into larger, global mappings (gmaps) . This merge process is clearly 0(2N) where N is the number of pmaps (isomorphic sub-tree matches) involved. SME's designers state that flat representations (i.e., non-nested) that cause N to be large will cause SME to be overly factorial, but that analogies leading to this situation would be rare or incoherent jumbles of unconnected expressions' (p28, 1989).

However, this is shown not to be the case. Veale eta/. [ 1996b] demonstrate that many concepts-most notably those that underlie nouns (such as Composer and War) but also story-based or narrative-structured concepts-are essentially object-centred, and are most naturally represented as a multitude of shallow trees. These trees are highly-connected in a coherent manner by means of shared arguments (common leaves). A mapping between two such domains is illustrated in Figure 1 below:

.e

e .. ·· .. · .. ::-.=·e

0 · ·./.<. · .·

(control Musician Musical_Instrument) e. // ·· ··

(part Percussion Drum)

~~:!~o~o~~~~~=~-Score

(isa Concert_ Theatre Theatre)

(control General Battle_Plan)

(isa Theatre_of_ War Theatre)

(control General Sabre)

(perform Soldier Warfare)

(part Army Artillery)

(control General Army)

(part Army Soldier)

(part Artillery Cannon)

(attr General Ruthless)

(control Soldier Musket)

(attr Cannon Russian_Campaign)

Figure 1: Pa~tial domain descriptions relating to the concepts Composer and General. Noisy predications wh1ch do not contribute to the metaphor "Composers are Generals" are shown in italics.

· :>:::/:: .. ..... .

.:::./· ........ ·.·.·::.:

.... .·

e>.........

This type of commonly occurring metaphor exacerbates SME's original 0(2N) complexity. For example, the metaphor Surgeons are Butchers requires less that 15 seconds of processing time in Sapper, yet generates enough pmaps to keep an optimal SME busy for many billions of years. Veale eta/. report the results of Figure 2 for an empirical test involving over 100 object-centred representations (drawn from the domain of professions):

Sapper out-performs SME in these domains because it is designed to seek out structure laterally from shallow trees that are connected via common elements, while SME seeks structure vertically from the hierarchical nesting of deep trees. Sapper can also encode the kind of verb­ centred story analogues upon which SME demonstrates its strongest competence (such as the Karla the Hawk and Fortress: Tumor stories). This paper builds upon these results to show that while heuristic, sub-optimal Greedy7 SME and Jncremental-SME avoid factorial time performance, they are still very sensitive to tree organization, producing poor mappings when dealing with object-centred representations. We also apply our intuitions to the Sapper and ACME models, demonstrating that while the latter is from the outset a sub-optimal model, it also exhibits diminished competence on hard problems. This discussion will allow us to outline in greater detail exactly what we mean by a hard analogical problem.

2. Cognitive Theories of Structure Mapping

ACME approaches the structure-mapping problem from a different perspective than either SME or Sapper, pursuing what might be called a natural computation approach to analogy and metaphor. ACME models structure-mapping as a problem of parallel constraint satisfaction, in which the demands of 1-to-1 coherence and structural systematicity are coded as soft constraints, or pressures, on the system. Ultimately, it is a sub-optimal approach which offers no guarantees of mapping quality.

ACME employs a Hopfield-style connectionist networ~ to encode mapping constraints (see [Hopfield and Tank,

1985]). Every structure-mapping hypothesis-either between a source and target predicate or between a source and target entity-is coded as a distinct neuron. Likewise, structural entailments among these hypotheses are coded as bi-directional excitatory links between the corresponding nodes, while inhibitory links are used to connect mutually exclusive hypotheses.

Such an arrangement is the connectionist equivalent of a 2-CNF SAT formula, raising the question of ACME's logical soundness. Indeed, it happens that the use ofbi-directionallinkages in ACME-which makes all implications mutual implications--means that an ACME representation is logically unsound. Because argument mappings can dictate predicate mappings, ACME is sound only when the source and target structures are trees (hence argument mappings do imply predicate mappings), but as noted, structure mapping is polynomially bounded anyway in such situations.

Overall, the complexity prognosis of ACME is not good: as a feedback-based neural network, there is no guaranteed polynomial bound on its time performance. Yet, because the network size is polynomially-bounded (i .e., O(n 2 ) nodes and O(n 4 ) linkages, where n is the number of distinct symbols in the source domain), the theoretical results of [Bruck and Goodman 1990] apply, who prove that a Hopfield-style network of polynomial size can only optimally solve NP-hard problems if NP = P. So, since an ACME network realistically embodies a polynomial algorithm, why should it be allowed to consume an exponential amount of time doing so?

2.1. Sapper: A Memory-Situated Model

The Sapper model of [Veale et a/. 1996a,b] views semantic memory as a localist graph in which nodes represent distinct concepts, and arcs between those nodes represent semantic I conceptual relations between those concepts. Memory management under Sapper is pro­ active toward structure mapping, that is, it employs rules of structural similarity-<:alled Triangulation and Squaring-to determine if any two nodes may at some future time be placed in systematic correspondence in a metaphoric context. If so, Sapper notes this fact by laying down a bridge relation between these nodes, to be exploited in some future structure-mapping session.

Triangulation Rule: If memory already contains two linkages Lij and Lkj of semantic type L forming two sides of a triangle between the concept nodes CJv Ci and Cj. then complete the triangle and augment memory with a new bridge linkage Bik·

Squaring Rule: If Bjk is a bridge, and if there already exist the linkages Lij and Llk of the semantic type L, forming three sides of a square between the concept nodes Ci, Cj, Ck and C1, then complete the square and augment memory with a new bridge Bj/.

At some future time, if Sapper wishes to determine ·a structural mapping between a target domain rooted in the concept node T (for Target) and one rooted in the node S (Source), it applies the algorithm of Figure 3.

The Sapper algorithm comprises two main phases: the first of these seeks out the set <I> of all well-formed and balanced semantic pathways (of length ~ 2H) that originate at the root node of the target (T), and terminate at the root node of the source (S), crossing a single conceptual bridge (i.e., the domain cross-over point) at its mid-point. Each such pathway corresponds to a partial interpretation (a pmap in SME parlance) of the metaphor/analogy. The second phase coalesces this collection of pmaps <I> into a coherent global whole; it does this using a seeding algorithm (see [Keane and Brayshaw, 1988]) which starts with the structurally richest pmap r as its seed, and then attempts to fold each other pmap into this seed, if it is coherent to do so, in descending order of the richness of those pmaps. This seeding phase is directly equivalent to the greedy merge phase of Greedy-SME (see [Oblinger & Forbus 1990).

3. Proof: Structure-Mapping is NP-Hard

In this section we place our arguments on a solid footing by proving the NP-Hardness of the structure mapping problem. Though the known NP-complete problem LCS (Largest Common Sub-Graph) is perhaps a more immediate match, we instead employ here 3DM (3Dimensional Matching) as a proof basis, a problem which seeks to obtain a non-overlapping matching of points in a 3-D space. A consideration of 3DM will shed light on the worst case scenario as encountered by the greedy heuristics employed by greedy-SME. Garey and Johnson ([1979]) define 3DM as follows:

Unique 3-Dimensional Matching (3DM): Given a set M of points in 3-D space, i.e., M ~ XxYxZ, where X Y and Z are disjoint sets of integers and IX] =I YJ =IZI = q, find the largest set M 1 ~ M such that no two elements ofM 1 agree in any coordinate.

Proof: To reformulate 3DM as a problem of structure­ mapping, it is necessary to represent each 3-D point <Xi, Yi, Zi> e M as a pair of predicates, one in each of the source S and target T domains, such that these predicates are only allowed to map onto each other. Furthermore, any isomorphic mapping must not contain two different predicate matches that arise from two points sharing one or more coordinates. We can ensure this using the following polynomial transformation:

Now, because the predicate P is uniquely tagged with the subscript XYZ which ties it to a particular 3-D point, these two predicate structures can map only to each other. When so mapped during the analogy process, such a mapping results in the creation of the following structure (a pmap in SME parlance):

In this manner a root mapping will be created for each point in M. Note also that .Q* Xi+ Yi is unique for each pairing of Xi and Yi, thus Xi, Yi and Zi are tied together and cannot be cross-mapped with any other point coordinate. Suppose we have two such pmaps, mapi = {<Xi, Yi >, < zi, n· Xi+ Yi>} and maPk = {<Xk, Yk>, <Zk, 0* Xk + Yk>}, arising out of the two points <Xi, Yi, Zi> and <Xk, Yk, Zi> which share a Z­ coordinate Zi. These maps cannot therefore be merged to create a larger mapping as such a merge results in Zi being mapped to both n· Xi+ Yi and n· Xk + Yk, a clear violation of mapping isomorphism.

Once a maximal gmap is found for the analogy, each pair <Xi, Yi> and <Zi, n· Xi + Yi> of this gmap can then be decomposed and reassembled (in polynomial time) to recreate a point <Xi, Yi, Zi> that is added to M 1 · Since the gmap is maximal, so is M 1 · Because it solves 3DM, structure-mapping is thus NP-Hard. 0

4. Problem Reorganization for Tractability

A large body of problem instances may nevertheless be tractably amenable to an optimal Sapper variant. If an optimal Sapper solution can be obtained for a large enough body of problem examples, these solutions can be used as ceilings to measure the competence of sub­ optimal heuristics like greedy merging I seeding.

The domain descriptions in the Sapper profession corpus contain on average over 120 predications each. Test metaphors in the profession corpus thus generate too many partial mappings to make optimal evaluation tractable. Yet, some problem re-organization can be applied to reduce the number of pmaps to frequently make an Optimal-Sapper interpretation feasible, without losing the combinatorial scope of the interpretation. This reorganization process, whereby redundant areas of the combinatorial search space are pruned, is the equivalent of arc-consistency testing in satisfaction problems to a priori remove contradictory variable assignments (see [Mohr and Henderson, 1986]).

For each metaphor (whose pmap set is denoted <I>) a conflict graph is constructed in 0(1<1>1 2 ) time, by determining for each pmap the set of other pmaps with which it cannot be combined. This set is similar to the set of NoGoods calculated by the SME algorithm, though it used differently to achieve more extensive reductions in performance time. The conflict set CFi for a particular pmap 1ti E <I> is thus defined as:

Compatibility between pmaps can thus be defined as:

In contrast to SME, Optimal-Sapper uses this information to recognize any compatibility-based redundancies, and redistribute them accordingly before entering the punishing factorial merge-stage, as follows:

Given that the combinatorial merge stage of an Optimal­ Sapper algorithm is 0(21<1>1), each such pmap factored out a priori lowers the eventual cost another exponential notch. On our corpus of profession metaphors, we have found that problem reduction of this form reduces the number of pmaps for each metaphor by an average of 60%, pruning the search space of the most intractable instance, Generals are Surgeons, from 0(2 3 ~ to one more manageable by Optimal-Sapper, 0(2 17 ) .

5. Experiment: Sapper ys. Greedy-SME

We can now quantify the competence of sub-optimal heuristics such as seeding and greedy-search as a percentage of optimal performance. But first, we consider the nature of the interpretations that structure­ mapping algorithms will generate for these test metaphors. The mapping of Figure 1 is the Sapper interpretation of the metaphor Composers are Generals, while the mapping of Figure 4 is that returned by greedy-SME for the same metaphor.

Since an official implementation of greedy-SME is not yet publicly available ([Forbus, 1996]), we therefore simulate greedy-SME by feeding the pmaps generated by the available optimal-SME through the Sapper seeding stage. This a computationally equivalent process.

A selection of the mappings in Figure 4 above are displayed in an italics face to convey their 'ghost' status: 'ghosts' are essentially noisy mappings that might work in another metaphoric context but which are not systematic here. But why does greedy-SME generate so many ghosts while Sapper produces none, when both employ equivalent merge processes? To see why, consider that SME and Sapper agree on three tacit assumptions for seeding: first, that a goodness ordering can be placed upon the set of pmaps; secondly, that the pmap chosen as seed for the merge is rich enough to ju~tify its own inclusion in the global mapping; and thirdly, that this seed is rich enough to nudge the overall merge process toward a good to optimal global mapping. However, Greedy-SME-unlike Sapper-does not ~ener~te sufficiently rich (and thus differentiable) pmaps m object-centred domains to make these assumptions work. As these domains are best represented as a broad forest of many shallow trees rather than a tight forest of few, deep trees (see [Veale et a/. 1996]), the pmaps generated by SME for object-centred metaphors are equally shallow and numerous. In fact, these impoverished SME pmaps resemble the geometric pmaps generated in section 3 when reposing 3DM as structure-mapping. One clearly would not expect a greedy approach to work in this geometric context as no one pmap would have enough structure to successfully guide the merge process to a good solution.

The competence of Sapper and greedy-SME has been determined over the test corpus of I 00+ profession metaphors, where the optimal-Sapper of section 4 is used as a savant: a mapping of a sub-optimal interpretation is considered valid if it is also contained in the optimal Sapper interpretation. The sub-optimal competence of Sapper and greedy-SME is thus calculated as 100 * (No. of valid mappings) I (Total No. of mappings). If this validity criterion seems overly strict and a/l-or-nothing, it needs to be for tractability reasons. If one were to evaluate a noisy interpretation on the basis of its largest systematic subset, the partition of the interpretation into signal and noise would in itself be an intractable problem of combinatorial dimensions. Comparative results are displayed in Figure 5 below:

Greedy-SME performs disappointingly on these trials significantly· trailing even the random control trial i~ which a random merging of coherent Sapper pmap~ is generated as an interpretation for each metaphor. These results speak for the importance of structurally rich pmaps, for when these are rich enough even a random coalescence of pmaps will generate a good ~nterpre~tion . But _if the set of pmaps is structurally 1mpovenshed, as With SME in object-centred domains, not even a best-first sorting will compensate. These random trials indicate that a system's true competence is to be found in the processes which generate pmaps, more so than in those which combine them.

6. Where the Hard Analogies Are

What do the results of section 5 say about the identifiable qualities of hard analogies/metaphors? Clearly, when employing an optimal mapping algorithm, the number of distinct roots in the forest-of­ trees representation of each domain is a direct indicator of the exponential requirements of the algorithm. What can be said of the hardness of analogies as perceived by sub-optimal approaches such as Sapper and SME?

In complexity terms no problem instance is--strictly speaking--hard to a sub-optimal structure matcher, as the number of pmaps is largely irrelevant in a 0~) greedy merging I seeding process. However, if one measures hardness in terms of the likelihood of generating a quality (i.e., ghost-free and accurate) interpretation, the best indicator of hardness is the average structural richness of each pmap (i.e., the average number of mappings in each pmap). The lower this average richness, the more probable it is that any two pmaps can be coherently merged, and thus the more likely that the final interpretation will be noisy and ghost-ridden. In contrast, the higher this average, the more probable it is that a final interpretation will be near optimal, and less likely to contain ghosts (as each prnap merge operation will have a greater chance offailure).

Ifwe have side-lined ACME's sub-optimal approach to structure-mapping in this paper, it is due to the belief that ACME represents an excessive approach to the problem. Recall that ACME can be characterized as a 2SA T problem, where network nodes mirror SAT variables, and network linkages mirror SAT clauses. From the ratio of ACME nodes to linkages for any given metaphor/analogy, we can determine the equivalent SAT ratio of clauses to variables as 0~). thus making an ACME problem hugely over-constrained (see [Mitchell eta/. 1992]). Given the large networks which ACME can construct for a hard problem (> 12,000 nodes), existing relaxation techniques based on constraint prioritization do not seem practical (see [Bakker et a/. 1993]). ACME thus reduces to a difficult subclass of maximal 2-SA T, with the size of that subset of clauses it must leave unsatisfied growing exponentially with the extent of network over-constraint, which itself grows quadratically with metaphor size. In this case, sub­ optimality certainly thus not imply tractability.

In closing, we note that the profession corpus upon which our experiments are based is available from the following URL, in Sapper, ACME and SME formats:

http: I I www. compapp. dcu. ie I -tonyv I metaphor. html