In this paper we investigate interactions between recent advances in the modeling of analogical transfer and similarity learning. Indeed, a unifying principle of case-based prediction methods was recently established, according to which the plausible inference principle of analogical transfer can be interpreted as a transfer of similarity knowledge from a situation space to an outcome space. Following this principle, the task of analogical transfer can be addressed using a global indicator of the compatibility between two similarity measures. Such an indicator can also be used to assess the quality of the situation space similarity measure with respect to the case-based prediction task. We discuss several perspectives opened by such an interpretation of the task of analogical transfer as the optimisation of the compatibility criterion: we explore interactions with similarity learning, as well as with energy function optimisation.
Analogical transfer is a cognitive process that allows to derive some new information about a
target situation by applying a plausible inference principle, according to which if two situations
are similar with respect to some criteria, then it is plausible that they are also similar with
respect to other criteria [
Recent work [
In this paper, we discuss some perspectives and directions that could be given to this line of
research. A global indicator of the compatibility between two similarity measures has already
been proposed in the CoAT method [
The paper is organized as follows. In Section 2 we recall the previous work on the CoAT method. We then briefly survey in Section 3 some approaches to learning (dis)similarities that seem relevant to CoAT, and discuss to how to leverage CoAT to obtain suitable similarity measures. We also explore techniques based on the optimisation of energy function that we propose in Section 4 and discuss further perspectives in Section 5.
In the CoAT method [
Let denote an input space, and ℛ an output space. An element of is called a situation, and an element of ℛ is called an outcome, or a result. A set = {( 1, 1), . . . , ( , )} of elements in × ℛ is called a case base. An element = (, ) ∈ is called a source case. In addition, the spaces and ℛ are respectively equipped with two similarity measures and ℛ , that respectively denote the similarity measure on situations and on outcomes.
The compatibility of ℛ with is measured globally on the case base , by introducing a global indicator Γ( , ℛ , ). This indicator measures the compatibility of ℛ with from an ordinal point of view on the whole case base , by checking if the order induced by ℛ is the same as the one induced by . The following continuity constraint is tested on each triple of cases ( 0, , ), with 0 = ( 0, 0), = ( , ), and = ( , ): if ( 0, ) ≥ ( 0, ), then ℛ ( 0, ) ≥ ℛ ( 0, ). ( )
Constraint ( ) expresses that anytime a situation is more similar to a situation 0 than situation , this order should be preserved on outcomes. A triple ( 0, , ) does not satisfy ( ) if the but less similar for outcomes, i.e., when ( 0, ) ≥ counts the total number of inversions of similarity observed on a case base Such a violation of the constraint is called an inversion of similarity. The indicator Γ( , ℛ , : ℛ ( 0, ).
) Γ( , ℛ , ) = |{(( 0, 0), ( , ), ( , )) ∈ × ×
such that
( 0, ) ≥ ( 0, ) and ℛ ( 0, ) < ℛ ( 0, )}|.
When the case base is fully known, except for the outcome of one case = ( , ), the transfer inference consists in finding the outcome that minimizes the value of the indicator: ∈ℛ = arg min Γ( , ℛ , ∪ {( , )}). 2.3. An Intrinsic Indicator of the Quality of a Similarity Measure measure The indicator Γ( , ℛ ,
with respect to the transfer task, independently of the algorithm used for the
inference. We report here some first experiments made in [
) indicator obtained for a chosen similarity measure ) can be used to assess the quality of the situation space similarity Experimental Protocol. The experiment is conducted on 200 instances extracted from the Balance Scale data set1. As the instances of these data sets are described only by numeric features, each situation can be represented by a vector of R . Let x, y ∈ R vectors. These data induce a classification task: the outcomes are categorical classes and the be two such outcome similarity measure ℛ is the class membership, i.e. ℛ (, ) = 1 if otherwise. The performance of the CoAT algorithm is measured by generating 100 diferent = , and 0 classification tasks {( , ℛ ,
)}1≤ ≤100, each of which is obtained by choosing for a decreasing function of a randomly weighted Euclidean distance. More precisely, a set of random decreasing function of the Euclidean distance computed in the ’s embedding space: linear maps { : R
−→ R }1≤ ≤100 are generated, and for each map , is defined as a (x, y) = − (x,y) with (x, y) = ‖ x − y‖2 = (x − y) (x − y).
︁√ The performance is also measured on the task (x, y) = −‖x−y‖2 is a decreasing function of the Euclidean distance, which amounts to taking as linear map the identity matrix. For each task, the performance is measured by the ( , ℛ , ), in which prediction accuracy, with 10-fold cross validation.
Results. Fig. 1 shows for each classification task the average accuracy and standard deviation of the CoAT algorithm according to the value of the Γ indicator ("Dataset complexity" axis on the figure). The blue points correspond to the randomly generated similarity measures. The red point gives the results for the similarity measure based on the standard Euclidean distance. The green line shows the result of a linear regression on the data. The Pearson’s coeficient is −0.97. The results clearly show a correlation between the value of the indicator and the performance of the CoAT algorithm. 3. Perspectives on Learning (Dis)similarity Measures While it is possible to use CoAT to quantify the suitability of a similarity measure for a CBR task, we argue that it should be possible to adapt CoAT to learn suitable similarity measures. Below we describe some existing methods to learning similarity (or dissimilarity) that appear relevant to adapt CoAT, before discussing how optimizing the indicator of CoAT relates to these (dis)similarity measure learning methodologies.
In what follows, we will not make distinction between similarity and dissimilarity measures
since they are the counterpart of one another. It is possible to define one from the other, for
instance, given a dissimilarity (, ) defined on R+ we define the similarity (, ) on [
Designing or learning (dis)similarity measures from data has long been studied [
Combining local (dis)similarities. Computing (dis)similarities in heterogeneous data can be
performed by transforming the input dataset into a homogeneous one. An interesting approach
is to consider the overall similarity measure as a weighted sum of ad-hoc measures. For instance,
the k-Prototypes algorithm [
More generally, it is possible to rely on existing similarity measures for each aspect of the
data, and combine them to obtain a global similarity. For instance, [
The main drawback of combining local dissimilarities is that it requires additional preprocessing and learning as well as supervision.
Unsupervised learning of (dis)similarities. Shi and Horvath [
The algorithm begins by creating several new training sets, each one being a bootstrap sample
of elements from the initial data set . A decision tree is built on each training set, using
a random sample of features at each split. The prediction task is then performed by a
majority vote or by averaging the results of the decision trees, according to the problem at hand
(classification or regression). This approach leads to better accuracy and generalization capacity
of the model compared to single decision trees, while reducing the variance [
The adaptation of RF to unsupervised settings was made possible by the generation of
synthetic instances, that enable a binary classification between the latter and the observed
(unlabelled) instances. The use of Unsupervised Random Forest (URF) for measuring (dis)similarity
presents several advantages. For instance, instances described by mixed types of variables as
well as missing values can be handled. In fact, this method has been successfully used in many
applications [
Albeit its appealing character, the method sufers from two main drawbacks. Firstly, the generation step is not computationally eficient: since the obtained trees highly depend on the generated instances, it is necessary to construct many forests with diferent synthetic instances and average their results, leading to a computational burden. Secondly, the synthetic instances may bias the model being constructed to discriminate instances on specific features.
More recently, Ting et al. [
Following the tracks of [
Despite of producing tailor made measures for data at hand, the main drawback of UET is that it computes similarities on each space (the situation and outcome) without establishing links between the two.
Metric learning. Learning dissimilarity measures from data has been tackled in the field
of metric learning (for an extended introduction, see [
On the one hand, contrastive loss [
On the other hand, triplet loss [
( 0, , ) = max( ( 0, ) − ( 0, ) + , 0) where the margin is used to enforce a gap between the clusters of situations.
To implement relative constraints with triplet loss, it is enough to have 0, , verify an ordinal relation of the form 0 ≤ < or 0 ≥ > . In a classification setting, the labels are classes that do not necessarily have an order defined, so the link/cannot link constraint where
ℛ is the class membership similarity measure mentioned above. 0 = ̸= is used instead. This latter constraint corresponds to ℛ ( 0, ) < ℛ ( 0, ),
Note that while metric learning was initially designed to use class labels, making it a
supervised methodology, semi-supervised and unsupervised variants have been also proposed [
Indeed, as in triplet loss methods, the CoAT method considers similarity judgements that are data triplets of the form {( 0, , ) | ℛ ( 0, ) < ℛ ( 0, )}, but then counts the number of triplets violating the constraint ( ), i.e., such that ( 0, ) ≥
ℛ ( 0, ). In triplet loss terminology, this corresponds to counting the number of hard negatives among all possible triplets formed with instances of the data set. Semi-hard negatives (i.e., triplets such that ( 0, ) + for some margin ) are excluded from this procedure. Therefore, when applied to classification ≥ ( 0, ) settings, the contribution of a triplet to the CoAT indicator Γ can be seen as a simplified version of the loss ( 0, , ) used in triplet loss methods, that would take value 1 if the triplet is a hard negative, and 0 otherwise.
However, the idea of the CoAT method is to sum up these contributions on all possible triplets
of a case base. Although in our first experiments, the case base consisted in the whole data set,
a more case-based approach would require crafting a (preferably small but informative) case
base for the task before attempting to learn a similarity measure. Moreover, one contribution
of the work done on the CoAT method has been to show that the prediction for a new case
depends only on the new similarity relations that result from the addition of the new case to
the case base [
This could lead to giving additional theoretical justification of triplet loss methods and give new
insights on how to solve the sampling issue (i.e., which training triplets to select).
4. Perspectives on Learning an Energy Function
This section discusses another perspective opened by the analogical inference interpretation
as the optimisation of the proposed Γ indicator, as established in Section 2.2. Indeed, this
view allows to exploit the formalism of energy-based models proposed for machine learning
tasks by [
. In this perspective, CoAT’s transfer strategy is an energy-based inference, that consists in completing the description of the case base in order to minimize its energy, and learning the energy function (and hence, the similarity measure) could be achieved by optimizing a contrastive loss function.
Energy-Based Models. Inspired from statistical physics, energy-based models specify a probability distribution ( ; ) =
− ( )/
︀∫ − ( )/
directly via a parameterized scalar-valued function ( ) called an energy function. In machine
learning, energy-based models are trained to be optimized on the data manifold: the energy
function is learned to give low values to training data, and higher values to data points that are
far from the data manifold [
R assumes the existence of an input space , an output space , and a set of parameters . The energy function associates to each pair (, ) ∈ × (, ) that represents the compatibility between the input and the output under the set of parameters . The energy function takes low values when is compatible with , and higher values when and are less compatible. The goal of the energy-based inference is to find, a scalar value among a set of outputs , the output * ∈ that minimizes the value of the energy function: ∈ * = arg min (, ).
Given a family of energy functions (, ) indexed by a set of parameters , the goal of learning
is to optimize the parameters in order to “push down” (i.e., assign lower energy values to) the
points on the energy surface that are around the training samples, and to “pull up” all other
points. Contrastive divergence [
ℓ(, , ) = max(0, + ( , ) − ( , ^)).
The hinge loss associates a loss value to a training sample ( , ) whenever its energy is not lower by at least a margin than the energy of the incorrect sample ( , ^). the value of the energy function:
× ℛ −→ An Energy-Based Model of Analogical Transfer. The input space (from which similarity knowledge is transferred) is the situation space . The output space (to which similarity knowledge is transferred) is the outcome space ℛ . The situation space is equipped with a similarity measure energy function : , and the outcome space is equipped with a similarity measure ℛ . The
R measures the compatibility of the outcome similarities with the added situation similarities when a potential new case ^ = (, ) is added to the case base. The energy function is parameterized by a hyperparameter = ( , ℛ , ), which includes the case base
. Indeed, assuming that and ℛ attributes, the compatibility between two similarity measures can not be evaluated per se, but only relatively to a given set of case pairs. For a new situation , the goal of the energy-based inference is to find, among a set of potential outcomes ∈ ℛ , the outcome that minimizes are defined on diferent sets of ∈ℛ = arg min (, ). measures ℛ Among the three parameters of = ( , ℛ ,
are usually fixed, so that learning amounts to learning the situation similarity measure for the task at hand. This can be done by contrastive divergence using the hinge loss defined as follows: for a training sample ( , ) ∈ × ℛ and a chosen outcome ^ ∈ ℛ , ), the case base
and the outcome similarity ℓ(, , ) = max(0,
+ ( , ) − ( , ^)).
The CoAT case-based prediction method directly implements this energy-based model by taking as energy function the global indicator Γ: CoAT(, ) = Γ( , ℛ , ∪ {(, )}).
Fig. 2 gives some examples of energy maps that are obtained for diferent synthetic data sets on a binary classification task. On each ifgure, the dataset size is the same ( |
| = 100), but the instances span diferently on the 2D description space. The instances are equally split into two classes (orange and blue). The similarity measure on situations is a decreasing function of the Euclidean distance as in Sec. 3 (i.e.,
= ), except for Fig. 2 d, where is constructed from a linear transformation of the Euclidean distance, by choosing from a set of 100 randomly generated transformations, the one that minimizes the energy of the case base. Let us denote by * the resulting similarity measure. The similarity measure on outcomes ℛ represents class membership as previously.On the figures, the colors indicate for each point of space the class that would be predicted by the CoAT algorithm : green for the blue class, and orange for the orange class. The color saturation is proportional to the diference between the energy of the predicted class and the energy of the other class.
Results In Fig. 2 a, the two classes are well separated, and no instance is more similar to an instance of a diferent class than it is to an instance of the same class, hence, ( , ℛ , 0. In Fig. 2 b, the two classes are closer, and even overlap, and some inter-class similarities ) = happen to be lower than some intra-class similarities, leading to the non-zero data set energy ( , ℛ , ) = 86, 786. Fig. 2 c and d show a data set with two linearly separable classes. In Fig. 2 c, is set to the (inverse of) the Euclidean distance, which leads to sub-optimal prediction performance: the prediction frontier does not correspond to the real class frontier, and some instances are misclassified. The energy of the case base is ( , ℛ , ) = 43, 264. In Fig. 2 d, the similarity measure is optimized by choosing a similarity measure * that minimizes the energy of the case base. The resulting prediction performance is improved: the prediction frontier corresponds to the real class frontier, and no instance of the case base are misclassified. The energy of the case base is ( *, ℛ , ) = 17, 146.
In this paper we investigated interactions between analogical transfer and similarity learning, in the framework of CoAT. In particular, we identified similarities between the Γ indicator and the triplet loss of metric learning, that may be used to obtain suitable similarities for analogical transfer. We also proposed an interpretation of the CoAT method in the formalism of energybased models, so that the similarity learning task can be expressed as the task of learning an energy function.
The established connections allow to envision other applications. For instance, it could be used for case base construction and maintenance. Indeed, if we consider the indicator as an energy function, the competence of a case should relate to its ability, when it is added to the case base, to lower the energy of other cases. Reasoning with a small but competent case base would solve one of the actual limitations of the CoAT method, which is the quadratic computational complexity of the inference procedure.
An additional direction for future works concerns the integration of expert knowledge, to promote interaction with domain experts when processing a case base. We envision this integration at two levels: the design of the similarity measure and the choice of suitable cases. We envision a semi-automatic approach to reach a suitable compromise between available data, expert input, and selection of competent cases.