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 functortransmit 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 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.
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:
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.
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.
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.
If the predicate type matches, but the elements in the predicate do not match, then the match gets -0.8 evidence.
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.
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."
Related Research Articles
First-order logic—also called predicate logic, predicate calculus, quantificational logic—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over non-logical objects, and allows the use of sentences that contain variables. Rather than propositions such as "all men are mortal", in first-order logic one can have expressions in the form "for all x, if x is a man, then x is mortal"; where "for all x" is a quantifier, x is a variable, and "... is a man" and "... is mortal" are predicates. This distinguishes it from propositional logic, which does not use quantifiers or relations; in this sense, propositional logic is the foundation of first-order logic.
In mathematics, a finitary relation over a sequence of sets X1, ..., Xn is a subset of the Cartesian product X1 × ... × Xn; that is, it is a set of n-tuples (x1, ..., xn), each being a sequence of elements xi in the corresponding Xi. Typically, the relation describes a possible connection between the elements of an n-tuple. For example, the relation "x is divisible by y and z" consists of the set of 3-tuples such that when substituted to x, y and z, respectively, make the sentence true.
Analogy is a comparison or correspondence between two things because of a third element that they are considered to share.
The Standard Template Library (STL) is a software library originally designed by Alexander Stepanov for the C++ programming language that influenced many parts of the C++ Standard Library. It provides four components called algorithms, containers, functions, and iterators.
Lexical functional grammar (LFG) is a constraint-based grammar framework in theoretical linguistics. It posits two separate levels of syntactic structure, a phrase structure grammar representation of word order and constituency, and a representation of grammatical functions such as subject and object, similar to dependency grammar. The development of the theory was initiated by Joan Bresnan and Ronald Kaplan in the 1970s, in reaction to the theory of transformational grammar which was current in the late 1970s. It mainly focuses on syntax, including its relation with morphology and semantics. There has been little LFG work on phonology.
In computer programming, a function object is a construct allowing an object to be invoked or called as if it were an ordinary function, usually with the same syntax. In some languages, particularly C++, function objects are often called functors.
Theta roles are the names of the participant roles associated with a predicate: the predicate may be a verb, an adjective, a preposition, or a noun. If an object is in motion or in a steady state as the speakers perceives the state, or it is the topic of discussion, it is called a theme. The participant is usually said to be an argument of the predicate. In generative grammar, a theta role or θ-role is the formal device for representing syntactic argument structure—the number and type of noun phrases—required syntactically by a particular verb. For example, the verb put requires three arguments.
Intensional logic is an approach to predicate logic that extends first-order logic, which has quantifiers that range over the individuals of a universe (extensions), by additional quantifiers that range over terms that may have such individuals as their value (intensions). The distinction between intensional and extensional entities is parallel to the distinction between sense and reference.
Fril is a programming language for first-order predicate calculus. It includes the semantics of Prolog as a subset, but takes its syntax from the micro-PROLOG of Logic Programming Associates and adds support for fuzzy sets, support logic, and metaprogramming.
Anomalous monism is a philosophical thesis about the mind–body relationship. It was first proposed by Donald Davidson in his 1970 paper "Mental Events". The theory is twofold and states that mental events are identical with physical events, and that the mental is anomalous, i.e. under their mental descriptions, relationships between these mental events are not describable by strict physical laws. Hence, Davidson proposes an identity theory of mind without the reductive bridge laws associated with the type-identity theory. Since the publication of his paper, Davidson refined his thesis and both critics and supporters of anomalous monism have come up with their own characterizations of the thesis, many of which appear to differ from Davidson's.
Language Integrated Query is a Microsoft .NET Framework component that adds native data querying capabilities to .NET languages, originally released as a major part of .NET Framework 3.5 in 2007.
In mathematical logic, predicate functor logic (PFL) is one of several ways to express first-order logic by purely algebraic means, i.e., without quantified variables. PFL employs a small number of algebraic devices called predicate functors that operate on terms to yield terms. PFL is mostly the invention of the logician and philosopher Willard Quine.
XPath is an expression language designed to support the query or transformation of XML documents. It was defined by the World Wide Web Consortium (W3C) in 1999, and can be used to compute values from the content of an XML document. Support for XPath exists in applications that support XML, such as web browsers, and many programming languages.
A sentence word is a single word that forms a full sentence.
The syntax and semantics of Prolog, a programming language, are the sets of rules that define how a Prolog program is written and how it is interpreted, respectively. The rules are laid out in ISO standard ISO/IEC 13211 although there are differences in the Prolog implementations.
The theory of ologs is an attempt to provide a rigorous mathematical framework for knowledge representation, construction of scientific models and data storage using category theory, linguistic and graphical tools. Ologs were introduced in 2012 by David Spivak and Robert Kent.
Coupled Pattern Learner (CPL) is a machine learning algorithm which couples the semi-supervised learning of categories and relations to forestall the problem of semantic drift associated with boot-strap learning methods.
Probabilistic Soft Logic (PSL) is a statistical relational learning (SRL) framework for modeling probabilistic and relational domains. It is applicable to a variety of machine learning problems, such as collective classification, entity resolution, link prediction, and ontology alignment. PSL combines two tools: first-order logic, with its ability to succinctly represent complex phenomena, and probabilistic graphical models, which capture the uncertainty and incompleteness inherent in real-world knowledge. More specifically, PSL uses "soft" logic as its logical component and Markov random fields as its statistical model. PSL provides sophisticated inference techniques for finding the most likely answer (i.e. the maximum a posteriori (MAP) state). The "softening" of the logical formulas makes inference a polynomial time operation rather than an NP-hard operation.
In control system theory, and various branches of engineering, a transfer function matrix, or just transfer matrix is a generalisation of the transfer functions of single-input single-output (SISO) systems to multiple-input and multiple-output (MIMO) systems. The matrix relates the outputs of the system to its inputs. It is a particularly useful construction for linear time-invariant (LTI) systems because it can be expressed in terms of the s-plane.
Structure-mapping theory is a theory of analogical reasoning, developed by Dedre Gentner, and for which she was awarded the 2016 David E. Rumelhart Prize for Contributions to the Theoretical Foundations of Human Cognition.
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
