Reasoning by analogy is essential to provide new conclusions helpful to solve a problem. Here we present the definition of a new operator aimed at reasoning by analogy. The proposed reasoner relies on the Roles Mapping Engine. It finds analogous roles encoded in descriptions that use domain-specific terminology, overcoming syntactical constraints that limit the relations to have the same name. We employ also a structural similarity function to face cases affected by ambiguity. We evaluate our approach using examples proposed in other works, producing comparable results.
As pointed out by [
This proposal consists in the definition of a new operator aimed at reasoning by analogy. The reasoner relies on the Roles Mapping Engine (RME), that finds common roles across descriptions. The long term objective is to embed in such definition a strategy for the cooperation with other reasoning operators.
The remainder of this work is organized as follow: in Section 2 related works are presented with related criticisms, in Section 3 some considerations about the analogy process are reported, then we present the proposed mapping procedure in details, presenting an evaluation in the successive section, finally we conclude with some considerations and future works.
Plenty of works studied an operator aimed to perform reasoning by analogy.
The most popular line of thought regards the research of identities between
predicates across domain, using as representation formalism propositional or first
order logic. In particular, in [
Similar assumption can be found in [
Again the same assumption is kept into account in [
A different approach has been proposed in [
In [
In a general view, the attempt is to produce analogies searching identities between predicates across domains, we must underline that, despite the reliability of these works (shown by the experimental results), the research of identical predicates alone could be not enough to generate useful analogies. 3
In this Section we will present our approach. For the sake of clarity, the description used as prior knowledge is referred as base domain, whereas the description of the current problem is referred as target domain.
We introduce some assumptions that limit our scopes: (1) we assume that all the descriptions are encoded using the same abstraction level, (2) this work does not keep into account the formalization of the goal, suggesting then all plausible analogies.
Retrieving oldest useful knowledge We want to face the retrieval of potentially analogues experiences. A good starting point can be an evaluation of common knowledge, that provides hints about potential points of contact between descriptions. Furthermore, the evaluation of the subnet of common knowledge relations allows to include the direct dependences between common statements. The addition of relational dimension allows the soundness check of the results.
In [
For this reason, we decided to evaluate the similarity using the structural
measure proposed in [
Input: A pair of Horn clauses < C0, C00 >.
Output: Two sets: term mappings θt and predicate mappings θp.
θp = ∅ H =< h0, h00 >| h0 is the head of C0, h00 is the head of C00 θt ← θt ∪ {term mappings in H} RA = literals having the same predicate in C0 and C00 θt ← θt ∪ {term mappings in RA} θrpep←eaθtp ∪ {predicate mappings in RA} where L = arg maxC∈S |C|. Such a trick could avoid obvious or useless analogies between too short or too unbalanced descriptions.
Roles Mapping Engine Reasoning by analogy cannot be reduced to looking for equal predicates across domains, because the derived inference could be useless or trivial. In this section our mapping strategy is presented through the RME.
Each concept is represented in Horn clause logic. Telling our strategy in a nutshell, starting points are sought, then the mapping is expanded in breadth. Both steps are executed keeping consistency requirements.
We will discuss the RME approach using the Algorithm 1. In particular, such algorithm presents iterations on three levels: the external level has an iteration enclosing the whole life cycle of the analogical mapping; the middle level has an iteration that checks whether one of the inner researches for mappings of identical and non-identical predicates produce novel mappings or not; the internal level has an iteration which aims to search for mappings of identical predicates and another one aimed to research mappings of non-identical predicates.
Such phases will be described in a formal notation and they will be equipped with a running example. Such example refers to the analogy between a proverb stating that “when the fox cannot reach the grapes, he says they are not ripe.” and a life context in which “a man cannot have a girl, he spreads a bad opinion about her”. We propose such example in order to clarify each step of our proposal.
Example 1 (Proverb and life context).
proverb(fox, grape) :- wants(fox, grape), cannot take(fox, grape, fox does not reach grape), is(fox, crafty), cause(fox does not reach grape, bad opinion), says(fox, grape is not ripe), is(grape, not ripe, grape is not ripe), have(john, bad opinion).
situation(john, carla) :- loves(john, carla), cannot have(john, carla, john cannot have carla), says(john, carla is bad), is(carla, bad, carla is bad), uses(jealous, craftiness).
In order to understand the mapping procedure, we need to define what are starting points and how to map terms and predicates as well.
Definition 1 (Starting point). Given two clauses C0 and C00, a starting point S is a binding S = [e0/e00] where (e0 ∈ predicates(C0) ∧ e00 ∈ predicates(C00)) ∨ (e0 ∈ terms(C0) ∧ e00 ∈ terms(C00)).
Definition 2 (Term mapping). Given two clauses C0 and C00, two sets of literals L0 ⊆ C0 and L00 ⊆ C00, a pair of terms t0 and t00, a consistent term association θ ⊆ terms(C0) × terms(C00); then t0/t00 is a term mapping if – {t0/t00} ∪ θ is a consistent term association; – either ∀l0 ∈ L0 s.t. t0 is a term of l0, ∀l00 ∈ L00 s.t. t00 is a term of l00, both t0 and t00 have position p; or ∃l0, l00 ∈ L0 × L00 s.t. t0 is a term of l0, t00 is a term of l00 and both t0 and t00 have name n and position p.
A term association θ is said to be consistent if it is a bijection, inconsistent otherwise.
Definition 3 (Predicate mapping). Given two clauses C0 and C00, two sets of literals L0 ⊆ C0 and L00 ⊆ C00 where ∀l0 ∈ L0, l0 = p0(t01, ..., t0a) and ∀l00 ∈ L00, l00 = p00(t010, ..., t0a0), a consistent predicate association θp ⊆ predicates(C0) × predicates(C00), a consistent term association θt ⊆ terms(C0)×terms(C00); then p0/p00 is a predicate mapping if – {p0/p00} ∪ θp is a consistent predicate association; – either p0 = p00; or a matching association defined as θl0/l00 = {t01/t010, ..., t0a/t0a0} s.t. ∀i = 1, ..., a, t0i/t0i0 is a term mapping, holds (i.e. θl0/l00 ⊆ θt). A predicate association θp is said to be consistent if it is a bijection, inconsistent otherwise. Definition 4 (Compatibility under term and predicate mapping). Two term mappings θ0 and θ00 are t-compatible iff θ0 ∪ θ00 is consistent. Two literals, or two sequences of literals, are p-compatible iff all their predicate mappings are defined and consistent.
Suppose given two clauses C0 = p0(t01, ..., t0n) :- l10, ..., lk0 and C00 = p00(t010, ..., t0m0) :- l100, ..., lh00 that the Algorithm 1 takes in input. Initially, we have an empty global term mapping θt and an empty global predicate mapping θp.
The heads mapping could be a good starting point. Since an analogy is sought between the descriptions of the concepts represented by the heads, this choice reflects the intrinsic strength of the heads relationship. More formally, if n = m, then θt0 = {t01/t010, ..., t0n=m/t0n0=m} is a term mapping. Since θt is empty, θt and θt0 are t-compatible, then θt ← θt ∪ θt0.
Although the entities in the descriptions will play specific roles (likely using a domain specific terminology), it is plausible that part of explanations are encoded using common sense, providing potential points of contact. Then a research of equal predicates across descriptions makes sense. The underlying idea is that two domains in the same knowledge share the representation formalism (implying the common sense as intersection between any pair of descriptions).
The first iteration of the internal level in the Algorithm 1 can be formalized as follow. Using Definitions 2, 3 and 4, we carry on our mappings searching for shared knowledge. Given two subsets L0 ⊆ C0 and L00 ⊆ C00 s.t. ∀l0 ∈ L0, l0 = p(t01, ..., t0a) and ∀l00 ∈ L00, l00 = p(t010, ..., t0a0), then θp0 = {p/p} is a predicate mapping. If θp and θp0 are p-compatible, then θp ← θp ∪ θp0.
Example 2 (Proverb and life context). Firstly, the heads are mapped, since they have the same arity, obtaining <grape, carla>, <fox, john>. At this point the literals having a predicate used by both clauses are isolated, in order to search for deterministic alignment. Then we have {says(fox, grape is not ripe)} and {says(john, carla is bad)}, from which <says/2, says/2> becomes a mapped predicate and <grape is not ripe, carla is bad> becomes a mapped term. Going on, the sets {is(grape, not ripe, grape is not ripe)} and {is(carla, bad, carla is bad)} are isolated, in which some terms are mapped, and from which we can add to the mapped predicates <is/3, is/3> and to the mapped terms <not ripe, bad>.
In Algorithm 1, the second iteration of the internal level tries to map nonidentical predicates expanding in breadth the previous mappings to those concepts that are syntactically different but that play an analogous role. The research of predicates and terms association goes on until new mappings are done. More formally, suppose given two subsets of literals L0 ⊆ C0 and L00 ⊆ C00 for which ∃t0/t00 ∈ θt s.t. ∀l0 ∈ L0, t0 is a term of l0 and ∀l00 ∈ L00, t00 is a term of l00. If exists a term mapping θt0 s.t. ∀t0/t00 ∈ θt0, t0 is a term of l0 ∈ L0 in position w, t00 is a term of l00 ∈ L00 in position w, θt and θt0 are t-compatible, then θt ← θt ∪ θt0. Moreover, if exists a predicate mapping θp0 s.t. ∀p0/p00 ∈ θp0, ∀l0 ∈ L0, l0 = p0(t01, ..., t0a), ∀l00 ∈ L00, l00 = p00(t010, ..., t0a0), ∀i = 1, ..., a then ∃t0i/t0i0 ∈ θt, θp and θp0 are p-compatible, then θp ← θp ∪ θp0. Example 3 (Proverb and life context). In the Example 2 a set of mapped predicates and a set of mapped terms have been obtained. Since {<grape, carla>, <fox, john>} ⊂ θt (see Algorithm 1), the expansion in breadth produces the pair of sets {wants(fox, grape)} and {loves(john, carla)}, from which <wants/2, loves/2> is added to θp. Consequently, {cannot take(fox, grape, fox does not reach grape)} and {cannot have(john, carla, john cannot have carla)} is found, allowing to map <cannot take/3, cannot have/3> that can be added to θp and <fox does not reach grape, john cannot have carla> that can be added to θt.
The middle level iteration in Algorithm 1 ensures that the internal iterations are repeated until at least one of them extends the mappings. Then, the middle level performs all deterministic mappings based on previous ones.
Unfortunately, it could be the case in which common knowledge does not exist, or cannot be used as starting point, or deterministic mappings are not available. A strategy relying on the structure analysis becomes a primary issue, in order to suggest starting points that do not share the representation. Then a structural similarity is exploited in order to obtain a reliability score between literals (denoted as rs). In such a way we design a pair of literals as new starting point, if it is the most similar, it is not already mapped and its literals have the same arity. This is the reason for which the external level exists. It attempts to restart the mappings expansion using such evaluation to overcome the absence of deterministic mappings. This attempt can be seen as the last opportunity to make novel deterministic mappings after the end of the algorithm.
More formally, we obtain a pair l0/l00 ∈ C0 × C00 s.t. l0 = p0(t01, ..., t0a), l00 = p00(t010, ..., t0a0), rs(l0, l00) is the maximum score, l0/l00 has not been fully mapped through term and predicate mappings. Then θt0 = {t01/t010, ..., t0a/t0a0} and θp0 = {p0/p00}. If θt ∪θt0 is t-compatible, then θt ← θt ∪θt0. If θp and θp0 are p-compatible, then θp ← θp ∪ θp0.
Example 4 (Proverb and life context). At this point, the mapping expanded in breadth pursued in the Example 3 (see Table 1) cannot be carried on because there are not novel deterministic bindings. The similarity function suggests {is(fox, crafty)} and {uses(jealous, craftiness)}. Here, only <crafty, craftiness> is a deterministic mapping. Since fox is already in θt as <fox, john>, jealous cannot be mapped, impeding the association of the respective predicates. Ranking of hypotheses A known problem is the ranking of the hypotheses to learn. Such problem affects reasoning by analogy, since each new mapping relies on previous ones, and so on. In this proposal, the hypotheses ranking problem has been faced using relative frequencies.
Given a clause C and a literal l ∈ C, the score of l is obtained averaging the relative frequencies for each term t in l, then:
Pa rfμ(l) = i=1 oi n ∗ a where o is the number of literals in C in which the t appears, n is the total number of literals in C, a is the arity of l. The idea behind the rfμ(l) scores is to represent the centrality of l in its clause. Then, given two literals l0 and l00, the reliability score rs(l0, l00) for their hypothesis of mapping is computed as: rs(l0, l00) = rfμ(l0) ∗ rfμ(l00) Mappings hypotheses are ranked using a descendant rs(l0, l00) score. A ranking so defined means that each new mapping maximizes the coverage of literals in both clauses.
Making inference During the mapping phase, the attention has been focused
on the recognition of analogous roles cross-domains (both for objects and
relations). As highlighted in [
Giving a more practical view of the procedure, after the filtering out of the one-to-one correspondences, the procedure seeks base knowledge that could be novel in the target domain. Consistently with the assumption that common knowledge is fundamental for analogical inference, it is possible that the lacking mappings are part of common knowledge, then it is projected using a Skolem function. An inference having Skolem functions is a hypothesis having an unreliability degree directly proportional to the number of Skolem functions. Example 5 (Proverb and life context). The expected explanation of the phenomena sounds like: “John has a bad opinion about Carla because he cannot have the love of Carla, then he uses his craftiness in order to do not appear rejected from the girl”. Let us examine the inference hypotheses from the proverb to the life context: 1. skolem is(john, craftiness) 2. skolem cause(john cannot have carla, skolem bad opinion) 3. skolem has(john, skolem bad opinion)
These hypotheses fully satisfy the expected interpretation. Meta-Pattern formalization Using the RME we can carry out an analogical mapping between each pair of clauses representing experiences, contexts or concepts. From such a mapping we can outline a pattern.
Let us to give a formal view of a pattern. Given two clauses C0 = h0 :l10, ..., ln0 and C00 = h00 :- l100, ..., lm, a set θt containing the mapped terms and a set θp containing the mapped predicates, we can outline a generalized pattern C = h :- l1, ..., lk with k ≤ min(n, m), s.t. ∀l ∈ C, ∃l0/l00 s.t. l0 ∈ C0, l00 ∈ C00, l0 = p0(t01, ..., t0a), l00 = p00(t010, ..., t0a0), p0/p00 ∈ θp and t0i/t0i0 ∈ θt (∀i = 1, ..., a). Moreover, l = p(t1, ..., ta) where: if p0 = p00, then p = p0 = p00, otherwise p = p∗, where p∗ is a new predicate; if t0i = t0i0, then ti = t0i = t0i0, otherwise ti = t∗i, where t∗i is a new term.
Since each analogy has a reason to exist with respect to a specific perspective, we cannot expect that each pattern will become general. Conversely, very often analogies remain specific. Then each refinement of a pattern needs to be consider a new pattern, because we have not any reason to consider too specific or useless the older pattern. In any case, we can say that trying an analogical mapping between a pattern and a third description (or another pattern), if the pattern(s) is not fully mapped, a novel and more general meta-pattern arises.
The reason behind such a choice is that if the pattern is used to make a novel analogy, many domains can support a mapping or suggest the argument of the relative Skolem function. To note that for each use or refinement of a pattern, the novel domain contributes to support each survived mapping in the pattern, giving further confirmation that the mappings in which the name of the original predicate or term has been preserved are effectively common sense expressions.
The story of each predicate/term in the pattern can be recognized, since the origin of each predicate/term in the pattern is stored using the formalism: db(head, type, pattern name, original name) where ‘head’ stands for the head of the original clause, ‘type’ indicates if we are storing a predicate or a term, ‘pattern name’ represents the name reported in the pattern and the ‘original name’ reports the name in the original clause. Example 6 (Proverb and life context). The mappings presented in Table 1 bring to the literals alignment in Table 2, from which we obtain the following pattern.
pattern(proverb(fox, grape), situation(john, carla)) :wants OR loves(fox OR john, grape OR carla), cannot take OR cannot have(fox OR john, grape OR carla,
fox does not reach grape OR john cannot have carla), says(fox OR john, grape is not ripe OR carla is bad), is(grape OR carla, not ripe OR bad, grape is not ripe OR carla is bad). What is an analogy? In order to provide a formal definition of analogy, we need to formalize what is the role that an object plays in a description. Keeping in mind that an object is an abstract entity that can be materialized differently in each description, let us to define a role.
Definition 5 (Role). Given a clause C, and a literal l = p(t1, ..., ta) s.t. l ∈ C, then the role of a term ti(1 ≤ i ≤ a) is a set Rti = {l1, ..., lk} s.t. ∀l0 ∈ Rti , l0 ∈ C and ti appears in l0. Such a set refers to the role that the term ti plays with respect to the other terms involved in the relations in which it is involved.
In any situation a task can be recognized. Any task requests a focus, i.e. the set of objects and relations necessary and sufficient to carry out the current task. Sometimes objects or relations lack, then an analogy could represent a way to hypothesize them from previous experiences. We need to retrieve the experience having an alignable focus, in order to derive hypotheses. In the light of such premises, we define the analogical perspective.
Definition 6 (Analogical perspective). Given two descriptions < D0, D00 > representing respectively base and target domain, K0 and K00 denote the aligned knowledge among D0 and D00, T 0 and T 00 denote the aligned knowledge among D0 and D00 that solves the current task, an analogical perspective holds if either
T 0 ⊆ K0 ⊆ D0 ∧ T 00 ⊆ K00 ⊆ D00
T 0 ⊆ K0 ⊆ D0 ∧ T 00 ⊆ (K00 ∪ I) ⊆ D00 or Where I is the inference obtained from the base domain.
Definition 7 (Analogy). Given two relational descriptions < D0, D00 > representable as sets of roles < RD0 , RD00 > and a perspective P , we say that D0 and D00 are analogous if there exist two subsets SD0 ⊆ RD0 and SD00 ⊆ RD00 s.t. a bijective function f : SD0 → SD00 holds, and f satisfies P . f satisfies P if for each role r ∈ RD0 ∨ RD00 necessary to explain P , f holds (i.e., r ∈ SD0 ∨ SD00 ). Remark 1 (Analogy). Given a description, each object plays a specific role with respect to each other. Common roles across descriptions are essential to the analogy, relations analysis is fundamental for roles identification, common objects can be a clue for relations analysis.
We present a qualitative evaluation, in such a way we can further clarify our
proposal. In [
RME assessment Let us give details about the stories and the relative expected solution. The base story follows.
A fortress was located in the center of the country. Many roads radiated out from the fortress. A general wanted to capture the fortress with his army. The general wanted to prevent mines on the roads from destroying his army and neighbouring villages. As a result the entire army could not attack the fortress along one road. However, the entire army was needed to capture the fortress. So an attack by one small group would not succeed. The general therefore divided his army into several small groups. He positioned the small groups at the heads of different roads. The small groups simultaneously converged on the fortress. In this way the army captured the fortress.
The base story is translated in a Horn clause having as head conquer(fortress). Each item in the following list encodes a sentence in the story. 1. located(fortress,center), partof(center,country), 2. radiated(oneroad,fortress), radiated(roads,fortress), partof(oneroad,roads), 3. capture(general,fortress), use(general,army), 4. prevent(general,mines), located(mines,oneroad), located(mines,roads), destroy(mines,army), destroy(mines,villages), 5. couldnotuse(army,oneroad), 6. capture(army,fortress), 7. couldnotuse(subgroup,oneroad), 8. splittable(army,subgroups), partof(subgroup,subgroups), partof(subgroups,army), destroy(mines,subgroup), notenough(subgroup), 9. distribute(subgroups,roads), 10. converge(subgroups,fortress), 11. capture(subgroups,fortress).
The target story follows.
A tumor was located in the interior of a patient’s body. A doctor wanted to destroy the tumor with rays. The doctor wanted to prevent the rays form destroying healthy tissue. As a result the high-intensity rays could not be applied to the tumor along one path. However, high-intensity rays were needed to destroy the tumor. So applying one low-intensity ray would not succeed. The target story becomes a Horn clause having the head heal(tumor). The last item encodes implicit knowledge. In particular such item says that the cancer can be reached from one or many directions. It encodes also that a slit is one of many slits, that the rays can be splitted and that healthy tissue can be damaged and/or destroyed from rays or sub-rays.
The expected result must contain the lacking knowledge of the target story, that is: “The doctor therefore divided the rays into several low-intensity rays. He positioned the low-intensity rays at multiple locations around the patient’s body. The low intensity rays simultaneously converged on the tumor. In this way the rays destroyed the tumor.”
Given the mapping in Table 3, the inference hypotheses from base to target domain are: 1. defeat(subrays,tumor) 2. splittable(rays,subrays) 3. skolem distribute(subrays,slits) 4. skolem converge(subrays,tumor) 5. aredestroyed(healthytissue,skolem villages) The hypothesis 1 can be identified as the goal of the problem, it is made of fully mapped components, making it a conclusive inference. The hypotheses 2, 3 and 4 represent the procedure useful to reach the goal, their predicates are not mapped, then skolem has been added (i.e. a Skolem function), in order to emphasize that the relation could be common sense knowledge, making it projectable without further elaborations. In any case, this type of inference needs to be considered contingent instead of conclusive. The hypothesis 5 does not make sense, then it is a case of fake inference. It is straightforward to highlight that all these statements was absent in the target domain, and have been completely obtained using the base domain. Finally, it is easy to note the consistency with the expected analogical reasoning.
In order to evaluate the similarity of the relational structure, the similarity
between the clauses has been evaluated using the fs measure [
Patterns assessment The proposed approach has been evaluated using a qualitative experiment that carries on the running example of analogical reasoning between military and medical domains, that produced a pattern as described in Section 3. We chosen a third domain telling about the purchase of a medicine for which an offertory is needed. We refer to this story as Pharmaceutical.
A medicine is located in the warehouse of a pharmacy. A patient needs to purchase the medicine. The patient must face the problem that his money is not enough. As a result the patient cannot purchase the medicine paying the total price. However, the total amount is needed to purchase the medicine. So applying a minor amount cannot succeed.
The clause encoding such concepts has the head get(medicine).
In the light of the mappings in Table 4, the RME suggests analogous domains using the stored original mappings, reported in Table 5. For the predicates use/2, located/2, couldnotuse/2 and partof/2 there is no novelty. Instead, the predicates mustface/2 and purchase/2 are more interesting because the suggestion indicates that mustface/2 is the “difficulty” that the protagonist must solve, whereas purchase/2 stands for the main action on which Pharmaceutical story is built.
The term mapping suggestions have not shared knowledge, then each term is traced to different terms in base domains. For instance patient is traced to the main actors in the other domains (general and doc), such as medicine that is the target object in the story is traced to fortress and tumor, and so on.
As for the analogy between Military and Medical domains, also here the fs measure has been exploited to evaluate the gain in the alignment of the portion of the structure for which the analogy holds. The original clauses score is 0.4, whereas the score after the RME is 0.74. Then the 34% of the structure that appeared not related in the original clauses, has been aligned in order to bring out the analogy.
The evaluation of the inference step is important in turn. Since the projection of knowledge is not empty, we can conclude that the analogy with Pharmaceutical domain is well represented by another pattern. The consequence is that a novel pattern has been produced. In this work we propose a strategy aimed to recognize analogies and to build meta-patterns for further reasoning, generalizing the analogical schemas. Our proposal differs from the existing literature since it allows to learn patterns representing both the intuition to know any potential solution to the problem, and a computational trick that allows to reuse analogies computed in the past. Moreover, the RME captures non-syntactic alignments without meta-descriptions.
Future improvements will regard relations with opposite sense (perhaps using a common sense knowledge). Another interesting direction could be the use of a probabilistic approach to mappings of non identical predicates. We plan also to face the factual validity using the abductive procedure, in order to check if the inferred knowledge (mapped or projected) is consistent with the constraints of the world. Last but not least, we will equip the solution with an abstraction operator, in order to shift the representation if needed.