A Dataset Complexity Measure for Analogical Transfer

1 Introduction

Computational analogy is a subfield of computer science that aims at designing computational models of psychological and intellectual processes of analogical thinking [Gust et al., 2008]. Contrary to machine learning approaches, no pre-trained model of the task at hand is required in computational analogy methods. Instead, the system solely relies on a structured memory and a proper similarity measure. Among the different tasks that computational analogy systems implement, the transfer task consists in using a measure of the similarity between two situations as a proxy to estimate the amount of similarity between their outcomes. Analogical transfer operates a special kind of plausible inference, according to which two situations that are judged similar are likely to have similar outcomes.

The choice of a similarity measure is critical for the success of a prediction task performed by analogical transfer. But designing a similarity measure for analogical transfer is not easy. Consider for example a simple regression task, the goal of which is to predict the price of an apartment given its characteristics. Suppose we have four apartments s1, s2, s3, and s4 of which the prices are known, and we want to predict the price of a new apartment t, knowing that it has two rooms, and is in downtown area (Tab. 1). Predicting the price of the new appartment t by analogical transfer consists in applying a similarity principle, according to which similar apartments have similar prices. The similarities between the situation t and each of the situations si are thus taken as proxies to estimate the similarities between the price of t and the prices of each si. A price for t is predicted from these estimations. If the description of the apartment t were judged similar to the description of an apartment si, then the price of t should be similar to the price of si. But then, is t more similar to s2 (which price is 600) than to s4 (which price is 900)? As s2, t has two rooms (nb rooms = 2), but as s4, the apartment t is located in downtown area (area = downtown). What is the importance of each criterion in the assessment of similarity? Which similarity metric should be used?

In computational analogy, the most common solution is to use a hand-crafted similarity measure, but it can be difficult and time-consuming [Jaiswal and Bach, 2019]. Another solution is to automate the construction of a similarity measure using machine learning [Mathisen et al., 2019]. This strategy has some drawbacks. One of them is that it requires enough data to obtain a good predicting power. Similarity acquisition also depends on the algorithm used to perform the prediction, since the optimal similarity measure is chosen by comparing the predictive power of a particular prediction algorithm on the given task. Moreover, the obtained similarity measure is often a blackbox i.e., no clue is given to a human observer on why two situations should be considered as similar [Gabel and Godehardt, 2015]. To be psychologically grounded, the learned similarity metric should verify some basic rationality principles [Coletti and Bouchon-Meunier, 2019], and metric learning methods learn distance functions from the data, whereas the mathematical notion of distance does not capture well psychological similarity measurements, since similarity judgements in practice often violate the basic distance axioms of minimality, symmetry, and triangular inequality [Tversky, 2013]. Many of these difficulties come from the fact that similarity is a psychological notion that takes its root in human perception: similarity is the result of a judgement, it is highly dependent on the context and the knowledge and goals of the observer.

This paper explores another research direction, which consists in introducing some qualitative knowledge in the similarity acquisition process by making explicit some properties that the desired similarity measure should enforce, from the point of view of a rational agent. The most commonly used constraint in computational analogy, the similarity principle, is modeled as a qualitative continuity constraint. In qualitative terms, it says that a similarity measure on situations will be a good proxy for a similarity measure on outcomes if it orders the cases in the same manner: anytime a situation si is more similar to a situation s0 than the situation sj, this order should be preserved on outcomes. If it is not the case, we will say that there is an inversion of similarity. Consider for example the situation s0 depicted in Fig. 1. The case base is divided into two sets of points, the red squares and the blue circles. The similarity on situations is measured by the (inverse of the) Euclidian distance, and the similarity on outcomes is measured by the class membership (two points of the same class being more similar than two points of different classes). In this example, there is an inversion of similarity in s0 since the situation si is more similar to s0 than the situation sj for situations, but less similar for outcomes. The complexity of the dataset is measured by counting the number of inversions of similarity on the dataset.

Our contribution is two-fold: (i) we show that the proposed dataset complexity measure is an intrinsic indicator of the quality of the similarity measure that can be used to select an optimal similarity measure for a transfer task, and (ii) we show how the complexity measure can be used to actually perform the transfer: among the potential outcomes of a new situation, the most plausible is the one which minimizes the dataset complexity.

The paper is organised as follows. The next section introduces some notions and notations. Sec. 3 reviews some related work. Sec. 4 introduces the dataset complexity measure, which is the main contribution of the paper, along with three applications: selecting an optimal similarity measure, optimizing weights in a weighted sum, and performing analogical transfer. Sec. 5 presents some experiments to validate the approach, and Sec 6 concludes and presents future work.

2 Preliminaries

This section introduces some notions and notations that will be used throughout the paper.

Computational analogy. A typical design setting of a computational analogy system is as follows. Let S be a set of situations and O a set of outcomes. A function f associates to each situation si an outcome f(si) ∈ O. A subset CB = {(s1, f(s1), (s2, f(s2)), . . . , (sn, f(sn))} of S ×O is called a case base. An element (si, f(si)) ∈ CB is called a source case. An element of the square product S × S represents a pair of situations, and is denoted (si, sj), or simply sisj . Let us denote by σS a similarity measure on situations, and σR a similarity measure on outcomes. For a new situation t, three main tasks are commonly implemented by a computational analogy system [Gust et al., 2008]:

• Retrieval: retrieve from CB a set of source cases (si, f(si)) to compare to the target situation t;
• Mapping: estimate the similarity σS(t, si) between the target situation t and each of the retrieved situations si;
• Transfer: estimate the similarity σR(f(t), f(si)) on outcomes from the similarity σS(t, si) on situations.

Analogical transfer can be used to (indirectly) predict the outcome f(t) of a new situation t, since f(t) can be predicted from the estimated similarity σR(f(t), f(si)). Most approaches of analogical transfer rely on a caracterization of the form of the function φ : σS -→ σR that relates the two functions σS and σR1 . Such characterization is known as a similarity principle.

Qualitative modeling. Qualitative models [Forbus, 2011] capture how people reason about dynamical systems. A qualitative representation of similarity consists in dropping numerical values in similarity assessment, which is justified by the fact that actual values of distance between two cases are less significant than the ability to compare two similarities. In this paper, we assume that the set of values of each similarity measure is totally ordered, which amounts to making a hypothesis of rationality regarding the way an agent makes a similarity judgement. A scale is a homomorphism, i.e., a mapping that preserves all relations and operations. A similarity scale (called a variation in [Badra et al., 2018]) is a scale on S × S which set of values is totally ordered. A similarity scale σ specifies a similarity relation ⪰σ on pairs of situations: for si, sj, sk, sℓ ∈ S, σ(sisj) ≥ σ(sksℓ) ⇔ sisj ⪰σ sksℓ. The similarity relation ⪰σ such that ab ⪰σ cd iff a and b are more similar than c and d for σ (or incomparable) is a total preorder (reflexive, transitive, and ab ⪰σ cd or cd ⪰σ ab for all a, b, c, d ∈ S). The complementary relation ≺σ such that ab ≺σ cd iff a and b are strictly less similar than c and d for σ is then a strict partial order (transitive and asymetric or areflexive) in which the relation of incomparability is transitive. Making the complementary relation ≺σ

1 As a misuse of language, we use the names of the similarity functions to denote their images.

be a strict partial order amounts to making a rationality hypothesis [Yao, 2000]. A human observer will judge that if two situations a and b are strictly less similar than two situations c and d, then c and d cannot be strictly less similar than a and b. Likewise, if a and b are not strictly less similar than c and d, and if c and d are not stricly less similar than e and f, then a and b can not be strictly less similar than e and f. Examples of similarity scales on a set of values include polynomial scales. Their form is as follows:

Polynomial scales associate to each pair of integers of the interval [0,L] a value in the interval [0,1]. Another useful similarity scale is the scale = defined by:

Feature scales are similarity scales that order the pairs of values taken by a given feature. A feature is a variable on the set S that is defined for a particular dimension of interest (e.g., price, or number of rooms). It can be modeled as a function ϕ : S -→ V. As shown in [Badra et al., 2018], assuming that there exists a total preorder on the set L of values taken by a feature ϕ : S -→ V, one can define, for any scale o : V × V -→ L on the values of ϕ, the similarity scale

For example, the similarity scale σnb rooms pn,L can be defined from the nominal feature ϕ = nb rooms and the scale pn,L as follows: σnb rooms pn,L (ab) = pn,L(nb rooms(a), nb rooms(b)). The scale σarea = (ab) can be defined from the nominal feature ϕ = area and the scale = as follows:

3 RelatedWork

This section reviews some related work in the literature.

Analogical transfer. Since the pioneering work of [Davis and Russell, 1987], which introduces a logical formulation of analogical transfer, many formalizations were proposed. A first type of approach consists in searching where the two similarity measures σS and σR align locally, and reason by similarity on the found alignments [Miclet et al., 2008; Onta˜n´on and Plaza, 2012; Hug et al., 2016; Badra et al., 2018]. The main difficulty with this kind of approach is to establish which relations must be generalized. A method was proposed in [Badra, 2016] to learn generalizations (called co-variations), but finding a general rule is rare. For example, apartment prices usually increase with the number of rooms, but not always: it might not be the case for two apartments located in different areas. A strategy could be to compare only identical situations ceteris paribus, but then a very large training set would be required to find valid rules. Besides, learning generalization rules is sensitive to noise: the presence of outliers in the data may prevent from learning the rules. Another type of approach consists in expressing the similarity principle as a continuity constraint [Hullermeier, 2007], which is a negative constraint on the set of possible states according to which it is not plausible to observe situations very dissimilar for σR when they are similar for σS. This principle can be expressed in probability theory by stating that if two situations are above a similarity level α for σS, it is likely that their similarity for σR is greater or equal than a value β. The function β : [0, 1] -→ [0, 1] which associates to each similarity level α for σS a similarity level β for σR is called a similarity profile. It is defined as β(α) = infs,s′ :σS(ss′ )=α σR(f(s)f(s′ )). Assuming that β is known, one can compute for a new situation s0 a set C(s0) = ⋂s {f(s) : σR(f(s0), f(s)) ≥ β(σS(s0s))} of credible solutions by taking, for each retrieved source case s, the set of solutions f(s) of the situations s in the neighborhood of s0 that satisfy the similarity principle. The problem is then to learn β. In [Hullermeier, 2007], this function is approximated by a step function, which is learned from the data. In [Anthony and Ratsaby, 2015], each hypothesis for β is a multi-category classifier. Determining the levels β of a similarity profile from the data is a task that is very sensitive to outliers. Besides, enough data is needed to learn the profiles, and two global similarity measures σS and σR must be available. When the similarity principle is expressed as a continuity constraint, a complementary approach consists in measuring the evidential support of each potential outcome f(s0), i.e., the extent to which the rule σS -→ σR is supported by the data when s0 is compared to other cases [Dubois et al., 2000; H¨ullermeier, 2003; Beringer and Hullermeier, 2008]. This rule is usually expressed as a possibility rule, and combined for all s ∈ CB with a principle of maximum informativeness, leading to the possibility distribution δ(s0, f(s0)) = max(s,f(s))∈CB min{σS(s0s), σR(f(s0)f(s))}.

Dataset complexity. Dataset complexity measures were originally introduced to evaluate the intrinsic difficulty of a classification problem [Ho and Basu, 2000]. The goal of a binary classification problem is to accurately predict on which side of the class boundary a new instance lies, so the complexity of the class boundary has a direct impact on the difficulty of the classification problem: the more complex the actual boundary is, the more difficult it is to learn a representation of this boundary from the data. Complexity measures have extensively been used for case-based maintenance [Cummins, 2013] or to optimize retrieval (see for example [Smyth and Keane, 1995; Lamontagne, 2006; Lieber et al., 2019]), but none of these measures are designed to find an optimal similarity measure or to perform the transfer task. Some measures evaluate the extent to which the similarity principle is verified locally. The Friend/Enemy ratio [Massie et al., 2007] compares the average similarity of a case to the k nearest cases of the same class with its average similarity to the k nearest cases of a different class. It detects at most one similarity inversion for each case, and uses this information to identify potential noisy cases. In [Leake and Wilson, 1999], the quality of the retrieval phase is measured by evaluating if the similarity principle is enforced in the neighborhood of each source case. In [Dileep and Chakraborti, 2014], fractals are used in the context of binary classification to detect which cases are the closest to the decision boundary, by noticing that those are the ones for which the similarity principle is less enforced.

4 ADataset ComplexityMeasure

This section shows how to measure the complexity of a case base with respect to the transfer task.

Definition of the measure. Let σS be a similarity scale on situations, σR be a similarity scale on outcomes, and CB ⊆ S × O a case base. The values of the similarity measures σS and σR are assumed to be totally ordered. To measure the extent to which the similarity principle is enforced in a case base CB, we use a qualitative version of the continuity constraint that is commonly used in the literature. This constraint formalizes the idea that the function φ : σS -→ σR should preserve the orderings on similarity values: for three situations s0, si and sj, if si is judged more similar to s0 than sj for σS, then it should also be more similar to s0 than sj for σR. More formally, let ⪰σS (resp., ⪰σR ) be the similarity relation specified by σS (resp., σR) . The continuity constraint expresses that ∀si, sj ∈ S, s0si ⪰σS s0sj ⇒ s0si ⪰σR s0sj . Let us denote by Inv(s0) the set of pairs sisj for which the constraint is not verified. The set Inv(s0) is defined by:

If sisj ∈ Inv(s0), we will say that there is an inversion of similarity in s0. In the example of Fig. 1, let S = R2 , σS(uv) = (1 + ‖ ⃗ uv‖2 )-1 be the similarity scale that returns a value inversely monotonic to the norm of the vector ⃗ uv, and σR = σcolor = be the scale constructed from the nominal attribute color : S -→ {blue, red}. The situations s0, si and sj verify σS(s0si) ≥ σS(s0sj) and σR(s0si) < σR(s0sj), showing an inversion of similarity in s0. Let γ(s0) denote the complexity of the source case (s0, f(s0)). It measures the extent to which the similarity principle is locally enforced in s0, and is defined as the number of inversions of similarity that can be observed in s0:γ(s0) = |Inv(s0)|

The complexity Γ(σS, σR,CB) of the case base CB is defined as the sum of the complexities of all source cases:

Selecting an optimal similarity measure. From the point of view of a rational agent, the optimal similarity measure σS is the one that minimizes the case base complexity Γ. The key idea here is that similarity acquisition does not depend on the algorithm used to perform the transfer. Instead, it relies on an indicator (the complexity measure Γ) that quantifies the extent to which the similarity principle would be verified for each source case of the case base. In usual similarity evaluation methods, the optimal similarity measure is chosen by comparing the predictive power of a particular prediction algorithm for different similarity measures. One potential limitation however, is that the similarity principle may not always be enforced in a real dataset, and when it is not the case, such similarity acquisition method may lead to suboptimal solutions. As an example, suppose we want to determine an optimal global similarity measure σS when the case base CB is the set of apartment descriptions given in the introduction (Tab.1). We choose σR = σprice p2,1000 and the similarity measure σS is assumed to be a weighted sum of the similarity σnb rooms p2,6 according to the number of rooms and the similarity σarea = according to the location area:

The goal is to determine the weight w ∈ [0, 1] to set in order to obtain for σS an optimal similarity measure. Fig. 2 shows the case base complexity Γ for different values of w. The optimal similarity measure σS is obtained for w ∈ [0.01, 0.64].

Optimizing weights in a weighted sum. Complexity can also be used for feature scoring when constructing a similarity measure. A popular similarity scale σS is the weighted sum of n similarity scales σ1, σ2, . . . , σn:

To determine optimal values for the weights wk, we apply the method of [Jaiswal and Bach, 2019], which consists in ranking the similarity scales σk according to an indicator, and then setting each wk to be the rank of the corresponding scale σk in the ordered set of indicator values. The chosen indicator is the complexity measure Γ. The similarity scales σk are ranked in decreasing order of complexity, and the weights wk are set accordingly. In the example of apartments, the method gives equal weights, which amounts to setting w = 0.5.

Algorithm 1 Optimize weights in a weighted sum

Inputs : Σ = {σ1, σ2, . . . , σn}, σR, CB Output : a list of weights [w1,w2, . . . ,wn] ℓ ← [ ] for σk ∈ Σ do ℓ.append(Γ(σk, σR, CB)) end for ℓ ← ℓ.sort in decreasing order() return [1+ℓ.index(e) for e in ℓ]

Algorithm 2 Complexity-based analogical transfer

Inputs : t,O, σS, σR,CB

Output : a predicted outcome for the new situation t

ℓ ← [ ]

for o ∈ O do

change outcome(t, o)

ℓ.append(Γ(σS , σR, CB ∪ {t}))

end for

return O[ℓ.index(min(ℓ))]

Complexity-based analogical transfer. The complexity measure can be used to perform analogical transfer: the most plausible outcome of a new situation t is the one which leads to the lowest case base complexity Γ. This approach to transfer will be referred to as Complexity-based Analogical Transfer (CoAT). Suppose that we want to predict the price of the apartment t presented in the introduction (Tab.1). The similarity measure σS is a weighted sum of the two feature scales σnb rooms p2,6 and σarea = , and weights are determined using the method presented in the previous paragraph. Fig. 3 shows the case base complexity computed for different values of the potential price of apartment t. Results show that the optimal price for t is 800 (Γ = 5), which is consistent since 800 is the value given by a simple regression on this dataset. But we also obtain an estimation of the plausibility of other prices in the interval [400, 1200].

5 Experiments

Three experiments were run. The first one tests the hypothesis that the complexity measure Γ is an indicator of the quality of the similarity measure σS. The second one evaluates the performance of CoAT on a regression task, and the third one evaluates the performance of CoAT on classification tasks.

Experiment #1. The PIMA indian diabetes dataset 2 includes data about 768 native American women. The prediction task consists in predicting if a person suffers from diabetes (taken as a binary class) from the value of 8 continuous attributes. The similarity scale σman (taken from [Jaiswal and Bach, 2019]) is the weighted sum of a set of polynomial similarity scales, with feature weights given by a domain expert, computed by including all features. From this similarity scale, a set of similarity scales was generated by assigning for each weight of σman a random value between 0 and 8, and then renormalizing the weights so that they sum up to 1. The similarity scale σΓ was constructed from the same set of polynomial similarity scales using the feature scoring method proposed in Sec. 4. The quality of each similarity scale is estimated by the accuracy of the k-Nearest Neighbor (k-NN) algorithm, with k = 5, computed using 10-fold cross validation 3 . Fig. 4 shows the relation between complexity and accuracy. Each grey point represents a similarity scale. The green triangle represents the σman similarity scale given by the expert. The blue square represents the σΓ similarity scale. Results show a strong correlation between the dataset complexity Γ and the quality (performance) of the similarity measure. Pearson's correlation coefficient is -0.8 for the 188 randomly generated similarity scales. The similarity measure σman given by the expert shows both the highest performance (72% accuracy) and the lowest complexity (9763). The σΓ similarity scale is nearly optimal: its complexity is among the lowest (9905), and its performance nearly as high as σman (70%). These results validate the hypothesis that for a given algorithm, complexity is a good indicator of the quality of the similarity measure σS .

2 https://kaggle.com/uciml/pima-indians-diabetes-database

Experiment #2. The Automobile dataset 4 includes data about 205 automobiles, from which were kept only the 159 instances that contain no missing values. The task consists in predicting the price of a car. Following [Dubois et al., 2000], in each source case (s0, f(s0)) the source situation s0 describes a car with the 2 continuous attribues horsepower and engine size, and the associated outcome f(s0) is given by the price attribute. Car similarity σS is computed using a weighted sum of Σ = {σhorsepower p2,240 , σengine size p2,265 }, with weights optimized as in Sec. 4, and σR = σprice p2,40282 . Fig. 5 compares for each instance the price predicted by CoAT (thick blue line) to the price obtained by a simple regression (dashed green line), as well as the real price (red line). Although our first implementation does not stricly surpass the performance of linear regression in this example (the root mean squared error is 4035 for CoAT, and 3166 for simple regression), the results demonstrate the pertinence of using complexity minimization for analogical transfer. In this example, no model of the data was learned prior to achieving the prediction task, and similarity learning was reduced to the acquisition of a few similarity scales. Each outcome is recovered from all others from the similarity measures alone, by taking the value that results in the lowest dataset complexity.

3 Due to current limitations in our implementation, the training sets of each pass were restricted to 50 randomly chosen instances, and the test sets to 77 instances.

4 https://archive.ics.uci.edu/ml/datasets/Automobile

Experiment #3. The performance of CoAT was compared to well-known machine learning algorithms on 6 classical datasets of the UCI repository 5 (Tab. 2): the Monks datasets (monks1, monks2, and monks3), the User Modeling dataset (user), the Iris dataset (iris), and the Zoo dataset (zoo). The similarity measure σS is a weighted sum of n feature scales. The feature scale σϕ= was used for each binary feature ϕ, and a polynomial scale was used for each continuous feature. The weights are set by the method proposed in Sec. 4. Results show excellent prediction performance (Tab. 3): CoAT equals or outperforms state of the art algorithms on the monks2, the iris, and the zoo datasets. On monks1, both classes often resulted in the same complexity value, and could not be discriminated, hence the poor results.

5 https://archive.ics.uci.edu/ml/

6 Conclusion and FutureWork

This paper opens a new research direction for analogical transfer, which consists in making explicit a set of qualitative constraints that a rational agent would want enforced. Two constraints were applied: a rationality hypothesis (similarity values are totally ordered) and a continuity constraint (anytime a situation si is more similar to a situation s0 than a situation sj, this order should be preserved on outcomes). A dataset complexity measure was proposed to measure the extent to which the continuity constraint is enforced on the whole dataset. This constraint expresses the wellknown similarity principle. We demonstrated the usefulness of such measurement, either (i) to optimize the choice of the similarity measure, by choosing a measure that best enforces the constraint, or (ii) to find the most plausible transfer, by choosing the potential outcome which best preserves the constraint on the augmented dataset. First results are very encouraging. Complexity appears to be a good indicator of the quality of a similarity measure (similarity measures of lower complexity are in average of better quality), and we showed that complexity minimization can be used to perform analogical transfer on regression and classification tasks.

Future work includes providing more theoretical justifications of the approach, and improving the implementation in order to make it scale to datasets that are larger than a few hundred instances. Complexity measurement is currently in O(n3 ), but huge improvements could be expected since computation could be run in parallel for each instance of the case base, thus reducing it to O(n2 ). More qualitative constraints could also be added to refine the method, such as attribute independence or monotonicity.