Nicolas Hug

Henri Prade

Gilles Richard

Mathieu Serrurier

Analogical Classifiers: A Theoretical Perspective

In recent works, analogy-based classifiers have been proved quite successful. They exhibit good accuracy rates when compared with standard classification methods. Nevertheless, a theoretical study of their predictive power has not been done so far. One of the main barriers has been the lack of functional definition: analogical learners have only algorithmic definitions. The aim of our paper is to complement the empirical studies with a theoretical perspective. Using a simplified framework, we first provide a concise functional definition of the output of an analogical learner. Two versions of the definition are considered, a strict and a relaxed one. As far as we know, this is the first definition of this kind for analogical learner. Then, taking inspiration from results in k-NN studies, we examine some analytic properties such as convergence and VCdimension, which are among the basic markers in terms of machine learning expressiveness. We then look at what could be expected in terms of theoretical accuracy from such a learner, in a Boolean setting. We examine learning curves for artificial domains, providing experimental results that illustrate our formulas, and empirically validate our functional definition of analogical classifiers.

Introduction

Analogical reasoning is widely recognized as a powerful ability of human intelligence. It can lead to conclusions for new situations by establishing links between apparently unrelated domains. One well known example is the Bohr's model of atom where electrons circle around the kernel, which is analogically linked to the model of planets running around the sun. It is not surprising that this kind of reasoning has generated a lot of attention from the artificial intelligence community. We can cite for instance [START_REF] Gentner | Structure-mapping: A theoretical framework for analogy[END_REF][START_REF] Gentner | The Analogical Mind: Perspectives from Cognitive Science, Cognitive Science, and Philosophy[END_REF][START_REF] Hofstadter | The Copycat project: A model of mental fluidity and analogy-making[END_REF][START_REF] Sowa | Analogical reasoning[END_REF][START_REF] Hofstadter | Surfaces and Essences: Analogy as the Fuel and Fire of Thinking[END_REF] where the power of analogical reasoning is emphasized. The interested reader may find in [START_REF]Computational Approaches to Analogical Reasoning: Current Trends[END_REF] a survey of current trends. More recently, using analogy as a basis for the automatic solving of IQ tests [START_REF] Correa | When intelligence is just a matter of copying[END_REF][START_REF] Ragni | Solving Raven's IQ-tests: An AI and cognitive modeling approach[END_REF] or for machine learning tasks [START_REF] Hinrichs | Transfer learning through analogy in games[END_REF][START_REF] Wang | Transfer learning by structural analogy[END_REF] got more attention. In the case of classification, analogical classifiers are mainly based on a particular variant of analogy, namely analogical proportions and they have been proved successful [START_REF] Bayoudh | Learning by analogy: A classification rule for binary and nominal data[END_REF][START_REF] Prade | Enforcing regularity by means of analogy-related proportions-a new approach to classification[END_REF][START_REF] Bounhas | Analogical classification: A new way to deal with examples[END_REF], at least from an empirical viewpoint.

But analogy, as an essential ingredient of Artificial Intelligence, has also attracted theoretical investigations. In [START_REF] Davies | A logical approach to reasoning by analogy[END_REF], a thorough investigation of analogical reasoning from a first order logic viewpoint has been done, leading to clearly specify safe conditions of usage of the analogical jump. More recently, in [START_REF] Gust | Metaphors and heuristicdriven theory projection (HDTP)[END_REF], an higher order logic framework has been developed, providing another logical theory for analogical reasoning in artificial intelligence and cognitive science. Instead of being described as an inference rule, the analogy-making process is described in terms of generalisation and anti-unification.

On top of this work, a full implementation has been done leading to the so-called Heuristic-Driven Theory Projection (HDTP).

From another viewpoint, we have to mention the work of [START_REF]Hofstadter and The Fluid Analogy Research Group, Fluid Concepts and Creative Analogies: Computer Models of the Fundamental Mechanisms of Thought[END_REF] which is an attempt to consider analogy-making as a particular case of machine learning where very few data are available. In the limit case, only one pair (a, f (a)) (a is the source) is available and one has to guess f (b) for another element b, the target. This work describes a model which minimizes the computational cost of producing (b, f (b)) from (a, f (a)). This computational cost can be estimated via Kolmogorov complexity [7], a measure which is wellknown to be hard to compute (but can be estimated via compression).

Finally, we can also recall the work of [START_REF] Barbot | La proportion analogique dans les groupes: applications aux permutations et aux matrices[END_REF] where the particular case of analogical proportion is investigated in lattices and other algebraic structures, leading to elegant theoretical results and implementations.

Nevertheless, all these theoretical investigations are not directed to provide an analytical view of analogy-based learners. In that sense, they are not really helpful if we want to characterize the behaviour of an analogical classifier for instance. One of the reasons could be that, unlike the k-NN rule, the analogical learning rule is not easily amenable to a functional definition. In fact, each implemented algorithm provides a clean description of how to compute but we definitely miss a clean description of what do we actually compute. Since such a definition, even a simplified one, is paramount to investigate theoretical properties, we suggest here a concise functional definition and we prove that it fits with the main implementations of analogical classifiers.

Our paper is organized as follows. In Section 2, we recall the fundamentals about analogical proportions as a particular case of analogy. Then, in Section 3, we explain how such proportions underlie analogical classifiers and the principle of their implementations. Then we provide a unified functional view establishing the formal framework allowing to investigate their mathematical properties. In Section 4, we examine some general properties such as convergence and VC-dimension of analogical learners, considering only minimal constraints on the underlying domain. In Section 5, we investigate, from a probabilistic viewpoint, the expected accuracy of an analogical learner in the Boolean case. We empirically validate our formulas in Section 6 with a complete batch of experiments. We provide our final remarks in Section 7, linking the known results about analogical classifiers with their mathematical properties, noting some limitations of our study and suggesting directions for future research.

Analogical proportions

Given a set X, an analogical proportion4 over X is a quaternary relation A over X satisfying 3 axioms [START_REF] Dorolle | Le Raisonnement par Analogie[END_REF][START_REF] Lepage | De l'analogie rendant compte de la commutation en linguistique[END_REF]:

1. ∀a, b, A(a, b, a, b) 2. ∀a, b, c, d, A(a, b, c, d) =⇒ A(c, d, a, b) (symmetry) 3. ∀a, b, c, d, A(a, b, c, d) =⇒ A(a, c, b, d) (central permutation)
A(a, b, c, d) is often denoted with infix notation a : b :: c : d when there is no ambiguity over the relation A and its domain X. When dealing with natural language words, the third axiom may be debatable [START_REF] Bayoudh | Evaluation of analogical proportions through kolmogorov complexity[END_REF]. There are a lot of ways to define an analogical relation over a set X, depending on the available structure and operators.

When [START_REF] Miclet | Handling analogical proportions in classical logic and fuzzy logics settings[END_REF][START_REF] Prade | From analogical proportion to logical proportions[END_REF]:

X = R,
a : b :: c : d iff (a ∧ d ≡ b ∧ c) ∧ (a ∨ d ≡ b ∨ c)
In fact, as soon as we have a proportion A over a set X, it is straightforward to build a proportion A m over X m with:

∀a, b, c, d ∈ X m , A m (a, b, c, d) ⇐⇒ ∀i ∈ [1, m], A(ai, bi, ci, di).
Still, A m will often be denoted A when there is no ambiguity. In [START_REF] Miclet | Relation d'analogie et distance sur un alphabet défini par des traits[END_REF][START_REF] Stroppa | Analogical learning and formal proportions: Definitions and methodological issues[END_REF][START_REF] Miclet | Analogical dissimilarity: Definition, algorithms and two experiments in machine learning[END_REF], examples are given where X is equipped with some algebraic structure (words over an alphabet, lattices, sets, Boolean vectors, matrices, etc.).

Analogical equation

When an analogical proportion is defined on a set X, given 3 elements a, b, c of X and a variable x, a relation a : b :: c : x turns into an equation that we may write a : b :: c : x = 1 where we have to find an element x ∈ X such that the proportion holds. Depending of the set X, the proportion A and a, b, c, one may encounter one of the three situations: the equation is not solvable, has a unique solution, or has multiple solutions. When there is at most one solution, we say that A is univocal. For instance:

• When X = 2 U (i.e. X is the powerset of a given universe) and a : b :: c : x is defined as: • With X = B m , the previous definition can still be used since B m ⊆ R m . But B m is not closed for addition and subtraction, so the equation does not always have a solution in B m . For instance, the equation (0, 0) : (0, 1) :: (1, 0) : x has a unique solution (1, 1) whereas the equation (0, 1) : (0, 0) :: (1, 0) : x has no solution in B 2 (since in B, 1 : 0 :: 0 : x has no solution), despite the fact that there exists a solution x = (1, -1) in R 2 . Another way to put it is to say the 4th summit of the parallelogram, which always exists in R m , does not necessarily belong to B m .

(a ∪ x = b ∪ c) and (a ∩ x = b ∩ c), the equation is solvable iff b ∩ c ⊆ a ⊆ b ∪ c and the unique solution is then x = ((b ∪ c) \ a) ∪ (b ∩ c). • With X = R m
In the following section, we investigate how the equation solving process can be used as the underlying principle to infer unknown information.

Inference principle

It is recognised that analogical reasoning provides plausible conclusions only [START_REF] Davies | A logical approach to reasoning by analogy[END_REF]. The analogical inference principle can be stated as [START_REF] Stroppa | Analogical learning and formal proportions: Definitions and methodological issues[END_REF] (where a = (a1, a2, • • • an)):

∀j ∈ J ⊂ [1, n], aj : bj :: cj : dj ∀i ∈ [1, n] \ J, ai : bi :: ci : di (analogical inf erence)
In words, this inference principle states that given four vectors a, b, c, d, if a proportion holds on a sufficient number of components (the J components), then it should also hold for the remaining ones. This principle leads to a prediction rule in the following context: ∀i ∈ [1, n] \ J, ai : bi :: ci : di.

In the case where the items are such that their last component is just a label, applying this principle to a new element d whose label is unknown leads to predict a candidate label for d. This prediction technique has been successfully applied to classification problems in both Boolean [START_REF] Bayoudh | Learning by analogy: A classification rule for binary and nominal data[END_REF][START_REF] Bounhas | Analogical classification: A new way to deal with examples[END_REF] and numerical settings [START_REF] Prade | Enforcing regularity by means of analogy-related proportions-a new approach to classification[END_REF].

In the next section, we describe the diverse ways this inference rule is implemented for classification purposes. This leads us to a unified functional definition of analogical classification.

Analogical classification

In the context of classification, items are represented as elements of a universe X having a (unique) label belonging to Y . For any x ∈ X, ẋ denotes the ground truth label associated to x. The goal of a classifier is, given a sample set S (i.e. a set of elements x ∈ X for which ẋ is known), to correctly predict the label of other elements x that do not belong to the sample set. We call x the predicted label of x: this is the output of the classifier.

Conservative classifier

Let us first consider what we call a conservative classifier. Such a classifier is called conservative because it is not able to output a prediction for any x in X, but only for a subset of X. We need to define two crucial concepts: the analogical extension of a sample set S, and the analogical root of an element x.

Let A be an analogy relation over X and B an analogy relation over Y , the set of labels. The notion of analogical equation allows us to define the so-called analogical extension of S denoted as: An intuitive interpretation of A Y E (S) is to see it as the set of all x ∈ X that are solutions of the analogical equations which can be built over the sample set S, provided that the equation related to the associated labels is also solvable. We have the following properties:

A Y E (S) = {x ∈ X|∃(a, b, c) ∈ S 3
1. S ⊆ A Y E (S), since x : x :: x : x always holds ; 2. A Y E (∅) = ∅, A Y E (X) = X ; 3. S1 ⊆ S2 =⇒ A Y E (S1) ⊆ A Y E (S2). The dual concept of the analogical extension is the so-called ana- logical root of a given element x ∈ X, denoted R Y S (x): R Y S (x) = {(a, b, c) ∈ S 3 |a : b :: c : x and ∃y ∈ Y, ȧ : ḃ :: ċ : y} R Y S (x)
is the set of 3-tuples in S which are analogically linked to x and which provide a prediction for the label. It is clear that R Y S (x) may contain more than one 3-tuple: for example in R m , x may be the summit of more than one parallelogram.

For any element x of A Y E (S), we define the analogical label of x as:

x = ẋ if x ∈ S Mode{y| ȧ : ḃ :: ċ : y ∀(a, b, c) ∈ R Y S (x)} if x / ∈ S
where Mode(Σ) returns the most frequent element of the multiset Σ.

In case of a tie, the returned element is chosen at random between the most frequent elements.

The analogical label will be used to estimate the label of every element. Obviously, in the first case, we do not want to change the label of the elements of S. For elements in A Y E (S)\S (i.e. the second case), the analogical label is the most frequent label out of all the labels inferred from the solution of the analogical equations that one can build from R Y S (x). It is quite clear that, for these elements, we do not necessarily have x = ẋ. To summarize, for a given element x ∈ X, we may potentially associate 3 labels:

• its true label ẋ ; • in the case where x ∈ A Y E (S), its analogical label x ; • its predicted label x.

Conservative classifiers set the prediction of an element

x ∈ A Y E (S) as x as follows: if x ∈ A Y E (S), x = x else x is undefined This kind of classifier cannot predict a label for an element which is not in A Y E (S).
In Algorithm 1, we provide the corresponding algorithm.

Let us note that A Y E (S) is never explicitly computed. Instead, we look for every 3-tuple in S and check if they belong to R Y S (x). Clearly, this is a supervised learning setting, where sample instances are stored for future use, without any generalization process. Conservative classifiers are Instance Based Learners as described in [START_REF] Aggarwal | Data Classification: Algorithms and Applications, Data Mining and Knowledge Discovery Series[END_REF].

Such a conservative learner cannot generalize to any new input and is restricted to elements in A Y E (S). This is not the case for instancebased learner like k-NN. This is why other options have been implemented to overcome this problem and to extend in some sense the generalization ability of analogical learner, as we will see in the next section.

Algorithm 1 Conservative classifier

Input: A sample set S and an element x ∈ X for which ẋ is unknown.

Output: x, an estimation of ẋ Init: C = ∅ // multiset of candidate labels for all (a, b, c) ∈ S 3 such that a : b :: c : x do if ∃y ∈ Y such that ȧ : ḃ :: ċ : y then // we are sure (a, b, c) ∈ R Y S (x) compute the solution y of ȧ : ḃ : ċ :

y C = C ∪ y end if end for x = x = Mode(C) // undefined if C = ∅

Extended classifier

To relax the previous option, we need to be able to predict a label for elements outside A Y E (S) i.e. elements which do not constitute a perfect analogy with elements in S. To this end, we can try to measure to what extent such elements are far from building a perfect analogy with those in S. The concept of analogical dissimilarity, first defined in [START_REF] Bayoudh | Learning by analogy: A classification rule for binary and nominal data[END_REF], will be useful to quantify in some sense how far a relation a : b :: c : d is from being a valid analogy. We keep the initial notation AD(a, b, c, d) to denote the analogical dissimilarity between 4 elements. Some minimal properties have to be satisfied by such a dissimilarity AD : X 4 -→ R + to fit with the intuition:

• ∀a, b, c, d, AD(a, b, c, d) = 0 iff a : b :: c : d • ∀a, b, c, d, AD(a, b, c, d) = AD(c, d, a, b) = AD(a, c, b, d) • ∀a, b, c, d, e, f, AD(a, b, e, f ) ≤ AD(a, b, c, d) + AD(c, d, e, f )
As the definition of an analogy strongly relies on the structure and operators available on X, we have the same situation for AD: there are a lot of possibilities. For instance: As a measure of how poorly an analogical proportion holds, the analogical dissimilarity will help to define more flexible classifiers. The main underlying idea is to consider approximate analogies which are not valid stricto sensu, but not too far to be valid. In [START_REF] Bayoudh | Learning by analogy: A classification rule for binary and nominal data[END_REF], after defining analogical dissimilarity, the authors build an extended classifier allowing classification of elements that do not belong to A Y E (S). Algorithm 2 gives a description of their classifier. This algorithm is similar to the conservative one but, instead of looking for pure analogies, we allow for some analogies not to be perfect when we need to. In their implementation [START_REF] Bayoudh | Learning by analogy: A classification rule for binary and nominal data[END_REF], the authors actually look for all the 3-tuples that have the same analogical dissimilarity as the kth one: this allows them to fit with the previous conservative approach. For the sake of simplicity, we have chosen to ignore this small detail in our explanation.

• When X = R m
In [START_REF] Bayoudh | Learning by analogy: A classification rule for binary and nominal data[END_REF], the authors evaluated this classifier on a Boolean setting B m over 8 benchmarks from the UCI repository. This approach led to remarkable results in terms of accuracy, when compared to offthe-shelf standard classifiers.

Nonetheless, this algorithm does not allow us to grasp its inherent working behaviour and it is difficult to extract theoretical properties. The aim of the next subsection is to give a functional translation of this algorithmic description. c,d) simply is the L1 distance from d to this 4th vertex. Note that as B m is not closed for addition, d ′ might not belong to B m but to R m : this happens when one of the terms AD(ai, bi, ci, di) is equal to 2, as further discussed later.

Analogical classifier: a functional definition

As we have seen, for a given x ∈ X, algorithm 2 tries to minimise AD(a, b, c, x) over all the 3-tuples (a, b, c) ∈ S 3 . In the light of what has just been explained, we see that this is equivalent to finding the closest vertex

d ′ = c -a + b from x for any (a, b, c) ∈ S 3 . Denoting δ the L1 distance, AD(a, b, c, d) = δ(a -b, c -d) = δ(d, d ′ )
, it is then natural to consider what we call the nearest analogical neighbour (or nan) of x from a sample S as the element of A Y E (S) defined as:

∀x ∈ X, ∀S ⊆ X, 1-nan(x, S) def = arg min d ′ ∈A Y E (S) δ(x, d ′ )
When there is more than one nan, one can either proceed to a majority vote procedure among all their analogical labels, or randomly select one of these. This last option is the one we chose in our implementation.

Property 1 We have the following equality:

1-nan(x, S) = 1-nn(x, A Y E (S)).
The analogical classification rule simply is:

x = 1-nan(x, S).

In words, the predicted label of an element x is the analogical label of its nearest neighbour in A Y E (S). In some sense, an analogical classifier behaves as a NN classifier but on an extended sample set.

Obviously if x belongs to A Y E (S) then x is its own nearest analogical neighbour:

1-nan(x, S) = x iff x ∈ A Y E (S)
. Therefore, it is easy to see that this rule is a generalisation of the conservative approach. Instead of using only one nearest analogical neighbour, we can consider the set of the k nearest analogical neighbours, and implement a majority vote as it is done in [START_REF] Miclet | Analogical dissimilarity: Definition, algorithms and two experiments in machine learning[END_REF].

The above definition leads to understand the process of analogical classification as follows:

1. First, extend the sample set S to its analogical extension A Y E (S). A Y E (S) can be viewed as an extended sample set that has class noise: the label associated with elements in A Y E (S) \ S is their analogical label (as defined in 3.1), which may not be correct. 2. Then just apply a classical k-NN strategy over this extended sample set.

Figure 2 gives an illustration of the classification process: the label of x ∈ X is unknown, and we set it to that of d ′ ∈ A Y E (S) (a circle), which is its nearest analogical neighbour. To show that the analogical label of d ′ has itself been inferred, it is depicted as transparent instead of plain black. Let us note that topologically speaking, Figure 2 is not representative of a real case: even if we always have S ⊆ A Y E (S) ⊆ X, this does not mean that these sets are embedded into one another as shown in the drawing. Actually, elements of S (and thus of A Y E (S)) are usually scattered over the whole universe. As far as we know, this is the first time a functional definition of analogy-based classifiers is given. This definition clearly fits with the known algorithms but obviously, some implementation details cannot be exactly caught up by such a high level description. It is indeed possible to find a few edge cases where this functional definition may not output the same result as algorithm 2: this is the case for example when the nan of x is not unique. It is also the case when the closest vertex d ′ does not belong to B m . However, as we will see in Section 6 these cases are not likely to occur and both approaches produce very similar results, thus empirically validating this functional definition.

Since we now have a clear functional definition of analogical classifiers, we are in position to examine some general properties such as convergence and VC-dimension of analogical learners. This is the purpose of the next section.

Let us consider the case where X = R m , δ any distance issued from a norm, AD(a, b, c, d) = δ(ab, cd) and x ∈ X. In any case, just because S ⊆ AE(S), we have the following inequality: δ(x, 1-nan(x, S)) ≤ δ(x, 1-nn(x, S))

Study of convergence

Now, let us consider x (i) an i.i.d. sequence of random variables in R m , where R m is equipped with a probability measure denoted P . As the set Sn = {x (i) , i ∈ [1, n]} is random, then 1-nan(x, Sn) can also be considered as a random element of X. We then are in the exactly same context as the work of Cover & Hart ( [START_REF] Cover | Nearest neighbor pattern classification[END_REF]), and we obtain the same result:

Property 2 plimn→∞(1-nan(x, Sn)) = x almost surely,
where plim is the probability limit operator.

Proof: Exactly the same proof as in [START_REF] Cover | Nearest neighbor pattern classification[END_REF] could be applied. But it is simpler to remember that δ(x, 1-nan(x, Sn)) ≤ δ(x, 1-nn(x, Sn)). Then, for a given x, the convergence in probability of δ(x, 1-nn(x, Sn)) to 0 implies the convergence in probability of δ(x, 1-nan(x, Sn)) to 0 which exactly means what needs to be proven. The subset of X where plimn→∞(1-nan(x, Sn)) = x is included into the subset of X where plimn→∞(1-nn(x, S)) = x: Cover & Hart lemma tells us that this set has probability 0. Thus the final result.

Let us note the following points:

1. The lemma of Cover and Hart is more general than the one above.

They have proven the result for any separable metric space, without any additional information. In fact, we cannot follow these lines here just because there is no known way to define an analogical dissimilarity on a metric space, without the help of other structure or operator (see [START_REF] Miclet | Analogical dissimilarity: Definition, algorithms and two experiments in machine learning[END_REF] for a detailed discussion on this issue). 2. This result does not say anything regarding the prediction accuracy of 1-nan prediction rule as it is rather different than the 1-nn rule. Such consideration will be investigated in Section 5. 3. We have to be careful about the interpretation of this property in terms of machine learning. Indeed, a stronger property is proved in [START_REF] Cover | Nearest neighbor pattern classification[END_REF]: for an integrable function f over R m w.r.t. the probability measure P , the expectation of f (1-nn(x, Sn))f (x) converges to 0 when n goes to infinity. This means that asymptotically, the nearest neighbour of x has the same properties as x, and then the same label. Such a property has not yet been proven for 1-nan(x, Sn). 4. Finally, it is clear that when n goes to infinity, the behavior of an analogical classifier tends to that of a nearest neighbours classifier. Indeed, when Sn is very big, the nearest analogical neighbour of an element x simply is its nearest neighbour, in most cases. Moreover, when the nan and the nn are too close, paying the price of the noise related to the nan may not be worth it. This supports the common acknowledgement that analogical reasoning is mostly useful when very few data are available. In this later case extending a small sample set with its analogical extension may be particularly beneficial.

VC-dimension

The notion of VC-dimension was originally defined by Vapnik and Chervonenkis [START_REF] Vapnik | Statistical Learning Theory[END_REF], and introduced into learnability theory by Blumer et al. [START_REF] Blumer | Learnability and the vapnik-chervonenkis dimension[END_REF]. Roughly speaking, the VC-dimension of a class of learners is a numerical measure of their discrimination power. It appears that this number is strongly linked to the confidence interval between the empirical risk (i.e. the error a learner makes on the sample set) and the true risk (the error a learner makes on the whole universe X). As such, the VC-dimension of a class of learners is an essential element of their theoretical study. We consider a universe X (usually a Cartesian product to represent the data) and a family H = {hi ⊆ X|i ∈ I} of subsets of X. The elements of H will be referred as hypothesis or models. Given a subset A of X, we can consider the new family of subsets tr(H, A) = {hi ∩ A ⊆ X|i ∈ I}: this family is called the trace of H over A. This is obviously a subset of the power set of A, 2 A i.e. tr(H, A) ⊆ 2 A . We say that H shatters A iff tr(H, A) = 2 A . V C-dim(H) is then the size of the largest finite subset which can be shattered by H:

Definition 1 V C-dim(H) = {|A| H shatters A},
where is the least upper bound operator. In the case where ∀n ∈ N, ∃A ⊂ X, |A| = n such that H shatters A, we simply say that:

V C-dim(H) = ∞.
As a binary classifier c over X defines a subset of X with c -1 (1) = {x ∈ X|c(x) = 1}, we can associate to a class C of classifiers a family of subsets {c -1 (1)|c ∈ C} and then the V C-dimension of a set of classifiers is as below:

Definition 2 V C-dim(C) = V C-dim({c -1 (1)|c ∈ C})
For instance with X = R n and with C the family of the k-NN classifiers:

CNN = {k-NN classifiers, k ∈ N * }, then V C-dim(CNN) = ∞.
Let us now consider the family of analogical binary classifiers AC k whose classification rule is as below (where a majority vote is implemented):

AC k (x, S) = k-nan(x, S)
In fact, an immediate result comes, derived from the core definition of an analogical proportion:

Property 3 V C-dim(AC k ) = ∞
Proof: Given any x, the analogical proportion x : x :: x : x always holds so that 1-nan(x, S) = x then the label x allocated to x by AC1 is just x, which by definition equals ẋ. It means any set of items can be exactly labelled, thus the infinite V C-dim.

Regarding Property 3, the AC k class behaves exactly as the k-NN class. Let us note that this is a very general result, which does not rely on any definition of distance. This is directly coming from a core property of analogical proportions.

Accuracy analysis in the Boolean case

In this section, we study the accuracy of an analogical classifier, and more particularly that of the 1-nan classifier (NaN). To do so, we restrict our view to a Boolean setting: elements to be classified belong to X = B m and the label space is Y = B. As explained in Section 3.3, for a given x ∈ X and a sample set S ⊂ X, we have:

x = 1-nan(x, S) = 1-nn(x, A Y E (S)), (1)
where A Y E (S) is the analogical extension of S, that we will simply denote by AE in what follows for notational brevity. We also denote A * E def = AE \ S as the set of elements that belong AE but not to S. We now equip the set X with a probability distribution denoted P . The accuracy of the NaNS classifier5 over all the elements of X is defined as: Acc(NaNS, X)

def = P (x = ẋ x ∈ X)
By observing that for any x, its 1-nan either belongs to S or to A * E , the above equation can be split into two distinct parts as follows:

P x = ẋ x ∈ X = P 1-nan(x, S) = ẋ = P [1-nan(x, S) = ẋ] ∧ [1-nan(x, S) ∈ S] + P [1-nan(x, S) = ẋ] ∧ [1-nan(x, S) ∈ A * E ] = P [1-nn(x, AE) = ẋ] ∧ [1-nn(x, AE) ∈ S] + P [1-nn(x, AE) = ẋ] ∧ [1-nn(x, AE) ∈ A * E ] = P [1-nn(x, AE) = ẋ] [1-nn(x, AE) ∈ S] × P ([1-nn(x, AE) ∈ S]) + P [1-nn(x, AE) = ẋ] [1-nn(x, AE) ∈ A * E ] × P ([1-nn(x, AE) ∈ A * E ])
Let us denote α def = P (1-nn(x, AE) ∈ S) 6 . The formula becomes:

Acc(NaNS, X) = P [1-nn(x, AE) = ẋ] [1-nn(x, AE) ∈ S] * α + P [1-nn(x, AE) = ẋ] [1-nn(x, AE) ∈ A * E ] * (1 -α).
Let us focus on the first term (discarding the factor α):

P [1-nn(x, AE) = ẋ] [1-nn(x, AE) ∈ S]
It is easy to see that the event [1-nn(x, AE) ∈ S] is equivalent to the event [1-nn(x, AE) = 1-nn(x, S)]. As a result, we can transform the first term to get a better grasp of its meaning:

P [1-nn(x, AE) = ẋ] [1-nn(x, AE) ∈ S] = P [1-nn(x, AE) = ẋ] [1-nn(x, AE) = 1-nn(x, S)] = P [1-nn(x, S) = ẋ] [1-nn(x, AE) ∈ S] .
In this form, the first term is just the accuracy of the NNS algorithm over the elements that have their nearest analogical neighbour in S. As for the second term, the same process can be applied by observing that the event

[1-nn(x, AE) ∈ A * E ] is equivalent to the event [1-nn(x, AE) = 1-nn(x, A * E )]
. This leads to

P [1-nn(x, AE) = ẋ] [1-nn(x, AE) ∈ A * E ] = P [1-nn(x, A * E ) = ẋ] [1-nn(x, AE) ∈ A * E ] .
This second term is then the accuracy of the NN A * E algorithm over the elements that have their nearest analogical neighbour in A * E . In the light of these interpretations, one can rewrite the accuracy formula in a concise form, using a few more definitions:

• A def = {x ∈ X, 1-nan(x, S) ∈ S}: the elements that have their nan in S. • B def = {x ∈ X, 1-nan(x, S) ∈ A * E }: the elements that have their nan in A * E .
Naturally, A ∪ B = X and A ∩ B = ∅. Also, α = P (x ∈ A) and 1α = P (x ∈ B). Therefore, the accuracy of NaNS over X can be understood as the weighted sum of the accuracy of NN over A and B, using a different sample set each time (respectively S and

A * E ): Acc(NaNS, X) = Acc(NNS, A) • α + Acc(NN A * E , B) • (1 -α). (2)
The value Acc(NNS, A) is the accuracy of NNS over all the elements in A. A theoretical study of this accuracy has been done in [START_REF] Langley | Average-case analysis of a nearest neighbor algorithm[END_REF] when the size of A is known. Regarding Acc(NN A * E , B), this is the accuracy of 1-nn when the sample set is noisy, and has been studied in [START_REF] Okamoto | An average-case analysis of the k-nearest neighbar classifier for noisy domains[END_REF]. This last formula leads to the consistent facts:

1. The smaller A * E (i.e. analogical reasoning does not bring much more labels), the closer α is to 1, the closer A is to X and the more the accuracy of NaNS tends towards the accuracy of NNS over X. 2. In return, if AE is much bigger than S, α is then small, B is close to X and the accuracy of NaNS greatly depends on the quality of AE, which can be measured by the value ω defined as:

ω P (x = ẋ x ∈ A * E ).
Note that the value 1ω corresponds to the class noise of AE.

As we will see in the next section, this situation where AE is big with respect to S is actually extremely likely to occur.

Experiments and empirical validation

In order to get an empirical validation of our formulas, we have developed a set of experiments that we describe in the next subsection.

Validation protocol

Working with Boolean vectors, we have computed the accuracies of the NaN and NN algorithms over X = B m for different values of m (namely 8 and 10). The ground truth label of elements of X is defined by different Boolean functions f in such a way that the ∀x = (x1,

• • • , xm), ẋ = f (x).
The different functions we have worked with are:

• f (x) = xm: in that case, we can consider the m -1 first parameters are a kind of noise since they have no influence on the final label ; • f (x) = 1 iff at least l components are equal to 1 (this kind of function is usually called l-of-m). We chose to set l to m Regarding the size of the training set, to be sure to fit with the size of the universe, we have investigated various sizes between 3 and 100. When dealing with a training set of size 100, the cubic complexity of the analogical classifier leads to explore a set of approximately 100 3 elements: as a consequence, we limit our investigation to a maximum of 100 elements in the training set in order to get realistic execution time.

All the accuracy (and other metrics) computations are averaged over a set of 100 experiments. The interested reader may find the Python source code that has generated all our plots and detailed results on Github7 . For lack of space, we only provide a few examples which are representative of the global behavior. Please note that our implementation of the NaN algorithm is not that of algorithm 2, but is instead that of the functional definition of the analogical classifier developed in Section 3.3: we first construct the analogical extension set of S, and then proceed to a nearest neighbour strategy over this noisy extended training set. We have estimated probabilities by frequencies, thus implicitly assuming a uniform distribution on X.

In addition to these Boolean functions, we have also run the NaN algorithm over the Monk datasets over the UCI repository 8 . They are datasets of 432 binarized elements, among which exactly 169 of them have been used for training. : the size of the analogical extension set with respect to that of the whole universe.

Experiments

Table 1 shows the same metrics for the Monk datasets and also report the results of the Analogical Proportion Classifier (APC) from [START_REF] Miclet | Analogical dissimilarity: Definition, algorithms and two experiments in machine learning[END_REF], which corresponds to algorithm 2 with k = 100.

Comments and discussion

The experiments shown in figure 3 allow us to draw interesting conclusions about the behaviour of the NaN algorithm. We can observe one of the two cases: • either the analogical labels are always correctly predicted 9 (ω = 1, i.e. there is no class noise) as it is the case for f1, f (x) = xm and (almost) for the Monk datasets ; • or there is some class noise in A Y E (S) (ω = 1). In this case, we always observe that the NaN algorithm is outperformed by NN for small values of |S|, but eventually takes advantage once analogical prediction becomes more important than the nearest neighbour one, as we are going to see.

The theoretical accuracy seems to fit perfectly with the empirical accuracy of the NaN algorithm, thus validating our theoretical study that led to equation (2) 10 .

An interesting observation is that the value of ω always converges to that of the theoretical accuracy (and therefore to the actual accuracy) of NaN. This can be easily explained by paying attention to the value of γ, the proportion of elements of X that belong to A Y E (S). We see that in any setting, γ converges to 1 as |S| grows. This means that when |S| is big enough (but not necessarily that big with re- 9 Note that for small values of |S|, it seems that ω = 1. This is due to the fact that for such small values, it is sometimes impossible to construct A Y E (S), thus leading to a value of ω = 0 (which will be averaged afterwards over the 100 experiments). 10 The maximal difference we observed between the theoretical accuracy and its actual value is of about 10 -10 . spect to X), the analogical extension of S covers the whole universe X 11 : every element x is then its own nearest analogical neighbour and x = x. It is therefore straightforward to see that in this case,

ω = P (x = ẋ x ∈ A * E ) = P (x = ẋ x ∈ A * E ) = Acc(NaNS, A * E )
When γ = 1, the only elements x we want to classify belong to A * E (otherwise they would be in S), so this last term exactly corresponds to the accuracy of the classifier. Another way to see it is to observe that the first term of equation ( 2) Acc(NNS, A) • α is null because α = 0. Only the second term Acc(NN A * E , B) • (1α) is of importance, and its value corresponds to ω. This observation allows us to state that estimating the value of ω is paramount to have a precise idea of the accuracy of an analogical classifier. We will provide in the next subsection a method to accurately estimate this quantity ω with the only help of the training set S.

Regarding the Monk datasets (Table 1), we note that the functional NaN approach (almost) achieves the same results as the somewhat more complex algorithm described in Section 3.2, and that here again the analogical extension set covers the whole universe: this means that a conservative approach would have been sufficient! Actually, this raises the following question: why would we want to look for more than one analogical neighbour when every element of the universe is already in A Y E (S), and therefore analogically linked to those in S? Our experiments tend to show that this becomes superfluous, provided that the training set is big enough.

Estimation of the prediction accuracy

We have seen in the previous subsection that the value ω is that of the actual accuracy of an analogical classifier when S is big enough. This leads to the following question: how can we get a precise estimation of this value ω ? Answering this would allow us to have a very precise idea of the accuracy we can expect from our classifier.

The method we propose for estimating ω only relies on the training set S and is very simple: it consists of applying the conservative algorithm to all the elements of S, and compute the fraction of these elements that have been correctly classified. A small yet important modification to the algorithm needs to be added: we only want to construct analogical proportions of the form a : b :: c : x where a, b, c and x are all distinct elements. Indeed, the proportions x : x :: x : x and x ′ : x :: x ′ : x are always true, and the solution label related to these proportions would bias the final majority vote procedure in a significant way towards the real label ẋ.

We have applied this estimation protocol to all of the Boolean settings we have considered, and it has shown to be very accurate. Figure 4 illustrates a few of these settings (already considered in Figure 3). We can see that the estimation ω converges to ω when S is big enough. For small values of S, this estimation is indeed imprecise as it is difficult to find a lot a 3-tuples such that an analogical proportion holds for every element.

Conclusion

In this paper, we have provided a functional definition of analogical learners. Starting from this definition, we are in a position to prove an analytic convergence result, similar to that of the nearest neighbour algorithm. Obviously, this is not enough to conclude regarding the 11 Obviously, the bigger the dimension m, the slower the convergence occurs. predictive ability of analogy-based classifiers. We have also shown that their VC-dimension is infinite. It should not come as a surprise, as a very particular case of analogical rule (when the analogical proportion is trivial) is the k-NN rule.

In terms of accuracy in a Boolean setting, we have found a strong link between the accuracy of the NaNS algorithm and that of the NNS algorithm. At a first glance, we can consider the NaN algorithm as a NN strategy on an extended and noisy sample set: the analogical extension of S. In the end, we have seen that this extended sample set covers the entire universe provided that S is big enough, simplifying and bringing back the accuracy of the classifier to the value ω which corresponds to the quality of the analogical extension. We have also provided a method to accurately estimate the value of ω that only relies on elements of the S, thus allowing beforehand to have a precise idea of the accuracy of any analogical classifier in a Boolean setting. Some important points remain to be investigated, such as:

• What can we expect in terms of speed convergence from an analogical learner? In other words, what is the minimum size needed from a sample set to get a fixed accuracy threshold? • If a clever learning strategy can (at least partially) overcome the problem of infinite VC-dimension, can we overcome the issue of the cubic complexity of analogical learners? • Leaving the field of classification, can we provide a clear strategy for transfer learning with analogy? Indeed, the central goal of transfer learning is to identify and exploit analogies between source and target domains [START_REF] Pan | A survey on transfer learning[END_REF].

These points definitely constitute interesting challenges for future works. Nevertheless, we have to remember that analogical reasoning brings its whole power in the case where few data are available. If a lot of data are available, it is very likely that we have elements similar to the one at hand and, in that case, a k-NN style reasoning is natural. In the opposite case, when we only have a few relevant cases at hand, applying analogical proportion-based predictions appears to be a meaningful option.

  some of the most well known examples are the arithmetic proportion a : b :: c : d iff ab = cd, and the geometrical proportion a : b :: c : d iff a b = c d iff a * d = b * c. When X = B = {0, 1}, the previous definitions still work and have a logical translation as

  and a : b :: c : x iff ab = cx, the equation has always a solution x = ca + b. When m = 2 and a, b, c, x are considered as points in R 2 , it simply means that starting from 3 points, we can always find a fourth one to build up a parallelogram as shown in Figure 1 [26]. In fact, from three non aligned points a, b, c, one can build two other parallelograms which correspond to the following equations: b : a :: c : x ′ and c : a :: b : x ′′ .

Figure 1 .

 1 Figure 1. Three parallelograms issued from a, b, c.

• 4

 4 vectors a, b, c, d are given where d is partially known: only the components of d with indexes in J are known. • Using analogical inference, we can predict the missing components of d by solving (w.r.t. di) the set of equations (in the case they are solvable):

  , a : b :: c : x and ∃y ∈ Y, ȧ : ḃ :: ċ : y}.

  and a : b :: c : d iff ab = cd, AD(a, b, c, d) = ||(ab) -(cd)||p is an analogical dissimilarity for any p, where ||.||p denotes the standard p norm in R m . • When X = B and a : b :: c : d iff (a ∧ b ≡ c ∧ d) ∧ (a ∨ b) ≡ (c ∨ d), one can define an analogical dissimilarity AD(a, b, c, d) as the number of values that have to be switched to get a proper analogy. For instance, AD(0, 1, 0, 0) = 1 and AD(0, 1, 1, 0) = 2. The codomain of AD is just {0, 1, 2}. When extended to X = B m with AD(a, b, c, d) = m i=1 AD(ai, bi, ci, di), we get an analogical dissimilarity whose co-domain is [0, 2m]. In fact, this definition is just the restriction to B m of the one coming from R m , when considering that B m ⊆ R m and using the L1 norm, i.e. AD(a, b, c, d) = ||(ab) -(cd)||1.

Algorithm 2

 2 Extended classifier Input: A sample set S, an element x ∈ X for which ẋ is unknown, a constant k. Output: x, an estimation of ẋ Init: C = ∅ // multiset of candidate labels for all (a, b, c) ∈ S 3 such that ∃y ∈ Y with ȧ : ḃ :: ċ : y do compute AD(a, b, c, x) and store it end for for all k least values of AD(a, b, c, x) do compute the solution y of ȧ : ḃ : ċ : y C = C ∪ y end for x = Mode(C)

  As we have seen in the previous section, in the case of a Boolean setting, AD(a, b, c, d) = ||(ab) -(cd)||1. A simple rewriting leads to: AD(a, b, c, d) = ||d -(ca + b)||1 = ||dd ′ ||1, where d ′ = ca + b. Actually, d ′ is nothing but the 4th vertex of the parallelogram abcd ′ so this means that AD(a, b,

Figure 2 .

 2 Figure 2. A graphical view of A Y E (S) and the classification process.

2 ;

 2 • f (x) = x1 ⊕ x2 (xor): we here have m -2 useless attributes ; • f (x) = 1 iff xi = 2: all the attributes are relevant in that case ; • f (x) = 1 iff xi = m -1: an extreme case of the previous one ; • f (x) = 1 iff x1 • xm = 1: only the first and the last elements are relevant.

Figure 3

 3 Figure 3 shows the accuracies (left column) of the NaN and NN over six different Boolean settings with values of |S| varying from 3 to 100. In the right column, we have plotted three different values that will help us analyse and validate the behaviour of the NaN algorithm: • the theoretical accuracy as defined by equation (2) in Section 5. The probability α = P (x ∈ A) has been estimated by the frequency: |A| |X| ; • the quality of A Y E (S), measured by ω as defined in Section 5 which is estimated by the frequency: |{x∈A * E x= ẋ}| |A * E | ;

Figure 3 .

 3 Figure 3. Accuracies of the NaN and NN algorithms over different Boolean settings and training set sizes, with corresponding values of ω, γ, and theoretical accuracy. The x axis corresponds to the size of the training set.

Figure 4 .

 4 Figure 4. Values of ω and its estimation ω for f 1 , f 2 and f 3 in B 10 .

Table 1 .

 1 Accuracies of the NaN, APC and NN algorithms over the Monk datasets

		NaN	APC	NN	ω	γ
	Monk 1	.961	.98	.787 .961	1
	Monk 2	.998	1	.738 .996	1
	Monk 3	.963	.96	.829 .963	1

For the remaining of this paper, the term analogy always means analogical proportion.

The S subscript is here to specify that the training set of the NaN algorithm is S. The same notation is used for the nearest neighbour algorithm: NN Σ is the NN algorithm trained on the set Σ.

[START_REF] Bounhas | Analogical classification: A new way to deal with examples[END_REF] Obviously, we also have α = P (1-nan(x, S) ∈ S).

https://github.com/Niourf/nan study

https://archive.ics.uci.edu/ml/datasets/MONK's+Problems


Nicolas Hug
email: nicolas.hug@irit.fr

Henri Prade
email: henri.prade@irit.fr

Gilles Richard
email: gilles.richard@irit.fr

Experimenting Analogical Reasoning in Recommendation

Recommender systems aim at providing suggestions of interest for end-users. Two main types of approach underlie existing recommender systems: content-based methods and collaborative filtering. In this paper, encouraged by good results obtained in classification by analogical proportion-based techniques, we investigate the possibility of using analogy as the main underlying principle for implementing a prediction algorithm of the collaborative filtering type. The quality of a recommender system can be estimated along diverse dimensions. The accuracy to predict user's rating for unseen items is clearly an important matter. Still other dimensions like coverage and surprise are also of great interest. In this paper, we describe our implementation and we compare the proposed approach with well-known recommender systems.

Introduction

In a world of information overload, automatic filtering tools are essential to extract relevant information from basic noise. In the field of e-commerce, recommender systems play the role of search engines when surfing the entire web: they filter available items to provide relevant suggestions to customers.

Besides, analogical reasoning is widely acknowledged as an important feature of human intelligence [START_REF] Gentner | The Analogical Mind: Perspectives from Cognitive Science[END_REF][START_REF] Melis | Analogy in problem solving[END_REF]. It is a powerful way for establishing parallels between apparently non related objects, and then guessing relations, properties, or values, on the basis of the observed similarities and dissimilarities. As a consequence, we may consider an analogy-based system as a suitable candidate for providing a user with relevant, and possibly surprising, recommendations. Indeed, providing the user with both accurate and surprising recommendation has become a key challenge. This is the option that we investigate in this paper.

Our paper is organized as follows. In the next section, we provide a brief survey of recommender system technologies. We also review diverse dimensions along which such a system can be evaluated. In Sect. 3, we provide the necessary background about analogical proportions and how they can be the basis of an inference process. In Sect. 4, we investigate how analogical proportions may provide a clean underlying framework to design a recommender system. In Sect. 5, we report the results obtained on a benchmark and we compare them to those of well-known existing approaches. Finally, we conclude and provide lines for future research in Sect. [START_REF] Kaminskas | Measuring surprise in recommender systems[END_REF].

The aim of a recommendation system is to provide users with lists of relevant personalized items. Let us now formalize the problem.

Problem Formalization

Let U be a set of users and I a set of items. For some pairs (u, i) ∈ U × I, a rating r ui is supposed to have been given by u to express if he/she likes or not the item i. It is quite common that r ui ∈ [1, 5], 5 meaning a strong preference for item i, 1 meaning a strong rejection, and 3 meaning indifference, or just an average note. Let us denote by R the set of ratings recorded in the system. It is well known that, in real systems, the size of R is very small with regard to the potential number of ratings which is |U | × |I|, as a lot of ratings are missing. In the following, U i denotes the set of users that have rated item i, and I u is the set of items that user u has rated.

To recommend items to users, a recommender system will proceed as follows:

1. Using a prediction algorithm A, estimate the unknown ratings r ui (i.e. r ui / ∈ R). This estimation A(u, i) is usually denoted rui . 2. Using a recommendation strategy S and in the light of the previously estimated ratings, recommend items to users. For instance, a basic yet common strategy is to suggest to user u the items i / ∈ I u with the highest rui .

The two main prediction techniques are commonly referred to as content-based and collaborative filtering, that we both briefly review below.

Content-Based Techniques

Content-based algorithms use the metadata of users and items to estimate a rating. Metadata are external information that can be collected. Typically:

-for users: gender, age, occupation, location (zip code), etc.

-for items: it depends on the type of items, but in the case of movies, it could be their genre, main actors, film director, etc.

Based on these metadata, a content-based system will try to find items that are similar to the ones for which the target user has already expressed a preference (for instance by giving a high rating). This implies the need for a similarity measure between items. A lot of options are available for such metrics. They will not be discussed here as our method is of a collaborative nature.

Indeed, a well-known drawback of content-based techniques is their tendency to recommend only items that users may already know, and therefore the recommendations lack in novelty, surprise and diversity. In the following, we only use collaborative filtering techniques, so we do not consider the use of any metadata.

Collaborative Filtering Techniques

By collaborative filtering, we mean here algorithms that only rely on the set of known ratings R to make a prediction: to predict r ui / ∈ R, the algorithm A will output rui based on R or on a carefully chosen subset. The main difference between collaborative and content-based method is that in the former, metadata of items and users are not used, and in the latter the only ratings we may take into account are that of the target user. A popular collaborative filtering technique is neighbourhood-based, that we describe here in its simplest form.

To estimate the rating of a user u for an item i, we select N k i (u), the set of k users that are most similar to u and that have rated i. Here again, there is a need for a similarity measure (between users, and based on their respective ratings). The estimation of r ui is computed as follows: rui = aggr

v∈N k i (u) r vi ,
where the aggregate function aggr is usually a mean weighted by the similarity between u and v. A more sophisticated prediction, popularized by [START_REF] Bell | Lessons from the netflix prize challenge[END_REF] is as follows: rui = b ui + aggr

v∈N k i (u) (r vi -b vi ),
where b ui is a baseline (or bias) related to user u and item i. It is supposed to model how u tends to give higher (or lower) ratings than the average of ratings µ, as well as how i tends to be rated higher or lower than µ. As it uses the neighbourhood of users to output a prediction, this technique tends to model local relationships in the data. Note that it is perfectly possible to proceed in an item-based way. Indeed, rather than looking for users similar to u, one may look for items similar to i, which leads to formulas dual of the above ones.

Recommender System Evaluation

Providing an accurate measure of the overall quality of a recommender system is not a simple task and diverse viewpoints have to be considered (see [START_REF] Ricci | Recommender Systems Handbook[END_REF] for an extensive survey).

Accuracy. The performance of the algorithm A is usually evaluated in terms of accuracy, which measures how close the rating prediction rui is to the true rating value r ui , for every possible prediction. To evaluate the accuracy of a prediction algorithm, one usually follows the classical machine learning framework: the set of ratings R is divided into two disjoint sets R train and R test , and the algorithm A has to predict ratings in R test based on the ones belonging to R train .

The Root Mean Squared Error (RMSE) is a very common indicator of how accurate an algorithm is, and is calculated as follows:

RMSE(A) = 1 |R test | r ui ∈R test (r ui -r ui ) 2
To better reflect the user-system interaction, other precision-oriented metrics are generally used in order provide a more informed view.

Precision and Recall. Precision and recall help measuring the ability of a system to provide relevant recommendations. In the following, we denote by I S the set of items that the strategy S will suggest to the users using the predictions coming from A. For ratings in the interval [START_REF] Barbot | La proportion analogique dans les groupes. applications à l'apprentissage et à la génération[END_REF][START_REF] Herlocker | Evaluating collaborative filtering recommender systems[END_REF], a simple strategy could be for example to recommend an item i to user u if the estimation rating rui is greater than 4.

I S = {i ∈ I|∃u ∈ U, rui ≥ 4}.
Let I relev be the set of items that are actually relevant to users (i.e. the set of items that would have been recommended to users if all the predictions made by A were exact). The precision of the system is defined as the fraction of recommended items that are relevant to the users:

Precision = |I S ∩ I relev | |I S | ,
and the recall as the fraction of recommended items that are relevant to the users out of all possible relevant items:

Recall = |I S ∩ I relev | |I relev | ,
If accurate predictions are crucial, it is widely agreed that it is insufficient for deploying an effective recommendation engine. Indeed, still other dimensions are worth estimating in order to get a complete picture of the performance of a system. [START_REF] Herlocker | Evaluating collaborative filtering recommender systems[END_REF][START_REF] Kaminskas | Measuring surprise in recommender systems[END_REF][START_REF] Mcnee | Being is not enough: how accuracy metrics recommender systems[END_REF]. For instance, one may naturally expect from a recommender system not only to be accurate, but also to be surprising, and to be able to recommend a large number of items. When evaluating the recommendation strategy, one must keep in mind that its performance is closely related to that of the algorithm A, as the recommendation strategy S is based on the predictions provided by A.

Coverage. Coverage, in its simplest form, is used to measure the ability of a system to recommend a large amount of items: it is quite easy indeed to create a recommender system that would only recommend very popular items. Such a recommender system would drop to zero added value. Coverage can be defined as the proportion of recommended items out of all existing items:

Coverage = |I S | |I| .
Surprise. Users expect a recommender system to be surprising: recommending an extremely popular item is not really helpful. Following the works of [START_REF] Kaminskas | Measuring surprise in recommender systems[END_REF], surprise of a recommendation can be evaluated with the help of the pointwise mutual information (PMI). The PMI between two items i and j is defined as follows:

P M I(i, j) = -log 2 p(i, j) p(i)p(j) / log 2 p(i, j),
where p(i) and p(j) represent the probabilities for items to be rated by any user, and p(i, j) is the probability for i and j to be rated together :

p(i) = |U i | |U | and p(i, j) = |U i ∪U j | |U |
. PMI values fluctuate between the interval [-1, 1], -1 meaning that i and j are never rated together and 1 meaning that they are always rated together. To estimate the surprise of recommending an item i to a user u we have two choices:

-either to take the maximum of the PMI values for i and all other items rated by u, with Surp max (u, i) = max

j∈I u P M I(i, j)
-or to take the mean of these PMI values with Surp avg (u, i) = j∈I u P M I(i,j)

|I u |
Then the overall capacity of a recommender to surprise its users is the mean of the surprise values for all predictions.

Background on Analogical Proportions

An analogical proportion "a is to b as c is to d" states analogical relations between the pairs (a, b) and (c, d), as well as between the pairs (a, c) and (b, d). It is only rather recently that formal definitions have been proposed for analogical proportions, in different settings [START_REF] Lepage | De l'analogie rendant compte de la commutation en linguistique[END_REF][START_REF] Miclet | Handling analogical proportions in classical logic and fuzzy logics settings[END_REF][START_REF] Yvon | Formal models of analogical proportions[END_REF]. In this section, we provide a brief account of a formal view of analogical relations that underlie their use in the proposed algorithm. For more details, see [START_REF] Prade | Analogical proportions and multiple-valued logics[END_REF][START_REF] Prade | From analogical proportion to logical proportions[END_REF][START_REF] Prade | Homogenous and heterogeneous logical proportions[END_REF].

c : d iff (a ∧ d ≡ b ∧ c) ∧ (a ∨ d ≡ b ∨ c) -Domain B n : a : b :: c : d iff ∀i ∈ [1, n], a i : b i :: c i : d i .
Other definitions are available when dealing with matriceces, formal concepts or lattices, etc. (see [START_REF] Lepage | De l'analogie rendant compte de la commutation en linguistique[END_REF][START_REF] Yvon | Formal models of analogical proportions[END_REF] for other options). In this paper, we are interested in evaluating analogical proportions between ratings, which might be Boolean (like/dislike), or in our case study, integer-valued (using the scale {1, 2, 3, 4, 5}). Equation Solving. Starting from such an analogical proportion, the equation solving problem to a fourth element x to make the incompletely stated proportion a : b :: c : x to hold. As expected, the solution of this problem depends on the domain on which the analogy is defined. For instance, in the case of extended arithmetic proportions, the solution always exists and is unique: x = ba + c. In terms of geometry, this simply tells us that given 3 points, we can always find a fourth one to build a parallelogram.

The existence of a unique solution is not always granted: for instance in the Boolean setting, the solution may not exist [START_REF] Miclet | Handling analogical proportions in classical logic and fuzzy logics settings[END_REF].

Analogical Inference. In this perspective, analogical reasoning can be viewed as a way to infer new plausible information, starting from observed analogical proportions. The analogical jump is an unsound inference principle postulating that, given 4 vectors a, b, c, d such that the proportion holds on some components, then it should also hold on the remaining ones. This can be stated as (where

a = (a 1 , a 2 , • • • a n ), and J ⊂ [1, n]): ∀j ∈ J, a j : b j :: c j : d j ∀i ∈ [1, n] \ J, a i : b i :: c i : d i (analogical inf erence)
This principle leads to a prediction rule in the following context: In the case where the items are such that their last component is a label, applying this principle to a new element d whose label is unknown leads to predict a candidate label for d.

Analogical Recommendation

The main idea is that if an analogical proportion stands between four users a, b, c, d, meaning that for each item j that they have commonly rated, the analogical proportion r aj : r bj :: r cj : r dj holds, then it should also hold for an item i that a, b, c have rated but d has not (i.e. r di is the missing component). This leads us to estimate r di as the solution x = rdi of the following analogical equation:

r ai : r bi :: r ci : x.
Given a pair (u, i) such that r ui / ∈ R (i.e. there is no available rating from user u for item i), the main procedure is as follows:

1. find the set of 3-tuples of users a, b, c such that an analogical proportion stands between a, b, c, and u and such that the equation r ai : r bi :: r ci : x is solvable.

2. solve the equation r ai : r bi ci : x and consider the solution x as a candidate rating for r ui . 3. set rui as an aggregate of all candidate ratings. The first step simply states that users a, b, c and u, considered as vectors of ratings, constitute a parallelogram. This condition is a bit strong and we may want to relax it by allowing some deformation of this parallelogram. This can be done by choosing another condition, such as ||(a -b) -(c -d)|| ≤ λ where λ is a suitable threshold and ||.|| denotes the Euclidean norm.

Another modification to the algorithm would be to only search for the users a, b, and c in a subset of U . One may consider the set of the k-nearest neighbours of d, using the assumption that neighbours are the most relevant users to estimate a recommendation for d.

Obviously, analogical proportion may be applied in an item-based way rather than in a user-based way, as in the case of standard techniques. Both views will be considered in the experimentation.

Implementation. In our implementation, we consider the basic definition of analogy using the arithmetic definition in R n : a : b ::

c : d ⇐⇒ a -b = c -d.
Given 4 users, they are represented as real vectors of dimension m, where m is the number of item they have rated in common. This dimension can change with the 4-tuples of users that we consider. Then, the threshold λ has to be a function of this dimension m, as the range of values that ||.|| may take depends on it. Using cross-validation, we have found that λ = 3 2 • √ m showed the best results and acts as a kind of normalization factor. Our pseudo-code is described in Algorithm 1.

Experiments and Results

Our algorithm Analogy (k = 20) is compared to the neighbourhood-based algorithms described in Sect. 2.3, referred to as kNN for the basic model and Bsln-kNN for the extended model using a baseline predictor (with k = 40). For each of the algorithms, we have estimated the metrics described in Sect. 2.4. The recommendation strategy S is to recommend i to u if rui ≥ 4.

Dataset. We have tested and compared our algorithm on the Movielens-100K dataset1 , composed of 100,000 ratings from 1000 users on 1700 movies. Each rating belongs to the interval [START_REF] Barbot | La proportion analogique dans les groupes. applications à l'apprentissage et à la génération[END_REF][START_REF] Herlocker | Evaluating collaborative filtering recommender systems[END_REF].

Evaluation Protocol. In order to obtain meaningful measures, we have run a fivefolds cross-validation procedure: for each of the five steps, the set of ratings R is split into two disjoint sets R train and R test , R train containing five times more ratings than R test . The reported measures are averaged over the five steps.

Results and Comments. Table 1 shows the performances of the algorithms applied in a user-based way. Similar experiments have been led in a movie-based setting, exhibiting very similar results, slightly worse for RMSE (about 5 higher).

Algorithm 1. Analogy

Input: A set of known ratings R, a user u, i such that r ui / ∈ R. Output: rui , an estimation of r ui Init: C = ∅ // list of candidate ratings for all users a, b, c such that As expected, the Bsln-kNN algorithm is more accurate than the basic collaborative filtering method (KNN). The two classical collaborative algorithms perform better than the new proposed analogy-based method in terms of RMSE. Still, there seems to be some room for improvement for the analogical approach, with the help of a careful analysis of the behaviour of the algorithm.

1. r ai ∈ R, r bi ∈ R, r ci ∈ R 2. r ai -r bi = r ci -x is solvable // i.e. the solution x ∈ [1, 5] 3. ||(a -b) -(c -d)|| ≤ λ //
As for performances other than RMSE, we see that the figures obtained by the three algorithms are quite close. Regarding surprise, which is a delicate notion to grasp, one may also wonder if the used measure is fully appropriate.

As usual, analogy-based algorithms suffer from their inherent cubic complexity. In the case of recommender systems where millions of users/items are involved, this is also a serious issue.

Conclusion and Future Research

This is clearly a preliminary study of an analogical approach to prediction in recommendation, a topic that has never been addressed before. First results are not better than the ones obtained with standard approaches. Even if they do not look that far, the difference is still significant enough to have a genuine impact on the users' experience. However, it is interesting to observe that approaches based on quite different ideas may lead to comparable results.

Besides, it should be recognized that the prediction part of the recommendation problem, somewhat similar to a classification problem analogical proportion-based classifiers are successful), presents major differences, since grades on items (playing here the role of descriptive features) may be both quite redundant and somewhat incomplete for providing a meaningful profile of a user. This may explain that the application of an analogical proportion-based approach is less straightforward in recommendation than in classification.

Analogical proportion-based methods have also been used recently for predicting missing Boolean values in databases [START_REF] Correa Beltran | Estimating null values in relational databases using analogical proportions[END_REF]. The recommendation problem can be also viewed as a problem of missing values, but here the proportion of unknown data is very high, and data are not Boolean. This again suggests that the recommendation task is more difficult.

There are quite a number of issues to further explore, such as understanding on what types of situation an analogical proportion-based approach would perform better, and when another view is preferable. Another basic issue is the fact that users likely use the rating scale {1, 2, 3, 4, 5} in an ordinal way rather than in an absolute manner, since the meaning of a rating may change with users. This calls for the use of analogical proportion between ordinal data [START_REF] Barbot | La proportion analogique dans les groupes. applications à l'apprentissage et à la génération[END_REF].

Lastly, the ideas of the exploitation of the creative power of analogy for (i) proposing items never considered by a user, but having some noticeable common features with items (s)he likes [START_REF] Sakaguchi | Recommendation system with multi-dimensional and parallel-case four-term analogy[END_REF], (ii) of the explanation power of analogy for suggesting to the user why an item may be of interest for him, are still entirely to explore.

Formal Framework.

  It has been agreed, since Aristotle time, that an analogical proportion T , as a quaternary relation, satisfies the three following characteristic properties: 1. T (a, b, a, b) (reflexivity) 2. T (a, b, c, d) =⇒ T (c, d, a, b) (symmetry) 3. T (a, b, c, d) =⇒ T (a, c, b, d) (central permutation) There are various models of analogical proportions, depending on the target domain. When the underlying domain is fixed, T (a, b, c, d) is simply denoted a : b :: c : d. Standard examples are: -Domain R: a : b :: c : d iff a/b = c/d iff ad = bc (geometric proportion) -Domain R: a : b :: c : d iff a -b = c -d iff a + d = b + c (arithmetic proportion) -Domain R n : a : b :: c : d iff ab = cd. This is just the extension of arithmetic proportion to real vectors. In that case, the 4 vectors a, b, c, d build up a parallelogram. -Domain B = {0, 1}: a : b ::

- 4

 4 vectors a, b, c, d are given where d is partially known: only the components of d with indexes in J are known. -Using analogical inference, we can predict the missing components of d by solving (w.r.t d i ) the set of equations (in the case they are solvable): ∀i ∈ [1, n] \ J, a i : b i :: c i : d i .

Table 1 .

 1 Performance of algorithms RMSE Prec Rec Cov Surp max Surp avg Time

			Analogy almost stands between a, b, c, d considered
	as real vectors
	do
	x ← r ci -r ai + r bi
	C ← C ∪ {x} // add x as a candidate rating
	end for
	rui = aggr
	Analogy .898	89.1 43.3 31.2 0.433	0.199	2 h
	kNN	.894	89.1 44.1 27.8 0.432	0.198	10 s
	Bsln-kNN .865	88.4 44.0 44.7 0.431	0.199	10 s

x∈C

x

http://grouplens.org/datasets/movielens/.