This paper proposes to view analogical proportion-based classification as a special type of case-based prediction algorithm, in which (i) cases are diferences between two instances, and (ii) only maximally similar cases are compared. It then proposes to tweak the CoAT case-based prediction algorithm in order to implement these two key design principles. The resulting analogical proportion-based classifier CoAT-APC shows a performance comparable to state-of-the-art analogical proportion-based classifiers, while implementing a diferent transfer strategy, based on the minimization of a dataset complexity measure, as opposed to a rule-based approach. Experimental results show the usefulness of combining these two design principles and suggest that the rule-based transfer strategy of analogical proportionbased classifiers has comparatively little impact on the performance of the system.
Case-based prediction [
On the other hand, analogical proportion-based classification (abbreviated APC in the rest of
the paper, see e.g. [
This paper proposes to compare these two classification paradigms and to study APC from the point of view of case-based prediction. More precisely, it shows that APC can be interpreted as a special kind of case-based prediction method, that applies a rule-based transfer strategy and implements the two following design principles: [P1] Cases are diferences between two instances of the considered instance set. [P2] Only maximally similar cases are compared.
The second principle can be relaxed to comparing only the most similar cases, beyond the maximally similar ones, as discussed later in the paper.
The paper then investigates why analogical proportion-based classifiers exhibit better
performance compared to other case-based prediction methods. To do so, a new case-based
prediction method is proposed, called CoAT-APC, that tweaks the CoAT case-based prediction
algorithm [
Experiments conducted on a variety of benchmark data sets, both of Boolean and numerical types, show that CoAT-APC ofers performances comparable to state-of-the-art analogical proportion-based classifiers, and that complying with the two principles [P1] and [P2] significantly improves the performance of the original CoAT algorithm. This suggests that the two principles [P1] and [P2] do play a major role in their success, whereas their rule-based transfer strategy has little impact on their eficiency, and can be replaced without harm with another transfer strategy.
The paper is structured as follows: Section 2 recalls the main definitions about analogical
proportion-based classifiers. Section 3 considers case-based prediction methods and in particular
reviews their main prediction strategies. Section 4 shows that APC can be formulated as a
case-based prediction method with rule-based transfer strategy. Section 5 presents the proposed
exploitation of this view in the CoAT-APC algorithm, that modifies the CoAT case-based
prediction method with optimization transfer strategy [
Analogical proportion-based classifiers have shown competitive results in classification and
recommendation tasks, see e.g. [
This section recaps the general principles of case-based prediction methods and reviews the main transfer strategies they rely on, proposing to distinguish between four categories discussed in turn in Sections 3.2 to 3.5.
Case-based prediction typically considers the following setting: denotes 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 finite set = {(1, 1), . . . , (, )} of elements in × is called a case base.
For legibility, and abusing the notation, cases and outcomes are sometimes denoted with their
corresponding situation as subscript: an element = (, ) ∈ is called a source case. In
addition, and respectively denote similarity measures on situations and on outcomes.
For a new case = (, ) whose outcome is to be predicted, a common decomposition of
the case-based inference involves three main tasks [
In the transfer task, as illustrated in the diagram of Fig. 1, a plausible inference is triggered in order to estimate the similarity (, ) on outcomes from the similarity (, ) on situations: it applies the principle according to which if two situations are similar, then it is plausible that their outcomes are also similar.
For a new situation , case-based prediction is then a search, among all potential outcomes ∈ , for the outcome that makes the plausible inference most likely to succeed when the used to estimate new case is added to the source case to build the augmented case base ∪ {(, )}. To find this outcome, case-based prediction methods express the plausible inference as a compatibility requirement on the resulting similarity relations: when the new case is compared to the retrieved cases, the outcome similarities should be compatible with the observed situation similarities. In the following, ^ = (, ) denotes a potential new case formed by choosing the outcome ∈ for the new case.
Diferent prediction strategies can be found in the literature to express this compatibility requirement between the two similarity measures. The next sections propose to distinguish between four categories of transfer strategies, respectively named transfer by rule-based voting, by constraint, by evidence support and by optimization.
A first type of transfer strategy relies on rules providing information on relations between the
similarity measures and , expressing that when takes value , the resulting similarity
level for is : these rules can be written ( = ) → ( = ) and can be expressed in
various forms, such as adaptation rules [
The proposed outcome is obtained by a majority vote on the set of outcomes derived
from the rules. Triggering a rule consists in performing a similarity-based inference (SBI),
applying variants of the modus ponens schema [
It can be noted that it is often the case that the similarity measures and are unknown, or
dificult to assess globally on the training data. One strategy then consists in working with some
local approximations ̃︁ of and ̃︁ of that are known to be compatible for some pairs of
cases of the case base. The resulting rules (̃︁ = ) → ( ̃︁ = ) are adaptation rules, that may
be acquired from an expert [
Another strategy consists in expressing the compatibility requirement between the two similarity
measures and as a set of continuity constraints à la Lipschitz [
A more data-driven type of approach consists in using a joint similarity measure to estimate for
each pair of cases (, ^) how compatible the similarity relation (, ) is with the similarity
relation (, ). Examples include the -Nearest Neighbor algorithm or the possibilistic
instance-based learning approach [
In most case-based prediction approaches, the compatibility of with is evaluated on the
pair of cases (, ^) for each retrieved case , and the results are combined in order to find
the most plausible outcome for the new case. A recent work [
(a) : (b)
c : used to estimate = (a − b, (a) − (b)) ^ = (c − , (c) − )
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 Γ( , , ∪ {(, )})
∈
This section proposes to establish a correspondence between APC and case-based prediction, showing the former can be viewed as a special kind of the latter. This correspondence is illustrated by the diagram given in Fig. 2 that represents the APC in a similar view as casebased prediction, whose diagram is given in Fig. 1. More precisely, APC can be considered as applying a specific transfer by rule-based voting method: first, cases are diferences between two instances (principle [P1]), and a single rule is triggered, that states that maximally similar situations (principle [P2]) should be associated with maximally similar outcomes. This section makes explicit all components of the case-based prediction configuration that can be associated to a given analogical proportion-based classifier, discussing successively the considered case base and similarity measures, as well as the applied transfer strategy.
When seen as a case-based prediction method, APC works by comparing some ratios a : b and (a) : (b) between the instances and their respective labels. Assuming that both instances and labels are vectors, these ratios are represented by the diferences = a − b and = (a) − (b) between two vectors. Let us denote by ∈ a new instance for which the class () is to be predicted. Let be the set of potential classes for (), and ∈ . The source case and potential new case ^ are of the following form: where a, b, c are instances of , and (a), (b), (c) their associated classes, represented as one-hot encoding vectors. APC implements the [P1] principle: cases are diferences between instances of the data set . (1)
The two similarity measures and are constructed from the analogical dissimilarity , by noticing that measures a distance (a, b, c, d) = (a − b, c − d) between two diferences a− b and c− d. The similarity measures and are obtained by applying a strictly decreasing function to the distance , e.g., by choosing = = − . The similarity measure is such that the four instances a, b, c, d form an analogical proportion if (a − b, c − d) = 1. The similarity measure is such that the four instances (a), (b), (c), (d) form an analogical proportion if ( (a) − (b), (c) − (d)) = 1.
When APC is viewed as a case-based prediction method, its transfer strategy is a rule-based
voting strategy [
This decision procedure thus considers all pairs (, ^) that can be obtained from a triple (a, b, c), and searches for potential solutions that can be inferred by applying the following similarity-based inference on a pair (, ^): ( = 1) → ( = 1) (, ) = 1
(, ) = 1 The analogical root of corresponds to the set of triples (a,b,c) for which the similarity-based inference allows to infer a solution . The predicted solution () is the solution that was inferred on the maximal number of pairs (, ^) by triggering the rule.
If the analogical root of is empty, analogical classifiers extend the search to triples with lowest analogical dissimilarity, i.e., with highest value for the similarity . This amounts to relaxing the condition (, ) = 1 to the condition (, ) ≈ 1. The similarity-based inference becomes: ( = 1) → ( = 1) (, ^) ≈ 1
(, ^) = 1 Only the solutions that were derived from the rule ( = 1) → ( = 1) with the highest values of (, ^) are added to the solution set. Therefore, when viewed as case-based prediction methods, analogical proportion-based classifiers implement the relaxed form of the [P2] principle (only most similar cases are compared). Algorithm 1 CoAT-APC inputs: (data set), (additional instance), (set of potential classes for ()), , (situation and outcome similarity measures), (number of neighbor instances), (size of the case base). output: the predicted value () for the new instance ℓ ← { : 0 for ∈ } () ← the instances c ∈ that maximize (c, ) for c ∈ () do ← c − (c) ← the source cases = (, ) that maximize (, ) for all ∈ do ← (c) − ℓ[] ← ℓ[] + Γ( , , (c) ∪ {(, )})) end for end for () ← arg min∈ ℓ[] return ()
The CoAT case-based prediction algorithm is modified in order to implement the two key principles [P1] and [P2] in its relaxed form. The resulting analogical proportion-based classifier, called CoAT-APC, implements a transfer strategy based on the minimization of a dataset complexity measure instead of being rule-based. Algo. 1 provides the pseudo-code description of the resulting CoAT-APC algorithm.
Regarding the case base, the source cases and potential new cases ^ are defined as in the previous section (Eq. 1) as diferences between instances of the data set (principle [P1]).
Regarding the transfer strategy, CoAT-APC selects a set of instances c ∈ , and for each of them applying the CoAT method to evaluate the plausibility of each potential outcome (i.e., class diference) = (c) − associated with the target situation = c − . The plausibility estimations obtained for each ∈ are then aggregated to propose a solution (). The decision procedure thus consists in successively: 1. finding the instances c that maximize (c, ), and for each one of them, 2. forming a case base (c) with the source cases = (, ) that maximize (, ), with = a − b and = c − (principle relaxed [P2]), 3. computing and storing Γ( , , (c) ∪ {(, )}) formed with = c − and = (c) − , for each potential solution ∈ ,
Type
Discrete Continuous
Dataset balance
car monks1 monks2 monks3 spect voting breastw iris pima user wine 4. aggregating the plausibility estimations by summing over c: () = arg min ∑︁ Γ( , , (c) ∪ {(c − , (c) − )})
∈ c
The first step (finding the instances c that maximize (c, )) is in line with [
This section describes the experiments run to validate the proposed CoAT-APC algorithm and the strategy it relies on, and to determine the impact that the principles [P1] and [P2] have on the performance of the proposed case-based prediction instantiation of analogical proportion-based classification. Algorithm 2 CoAT inputs: (data set), (additional instance), (set of potential classes for ()), , (situation and outcome similarity measures). output: the predicted value () for the new instance ← () ← arg min∈ Γ( , , ∪ {(, )})) return ()
The data sets used for classification are taken from the UCI repository 1, their characteristics are summarized in Table 1. They include 8 data sets with only nominal features and 4 data sets with only numerical features, in both cases associated with classification tasks with 2 to 4 classes. In all experiments, the two similarity measures and are fixed: • = − , where = ‖·‖ 2 is the standard Euclidean distance; • (, ) = 1 if = , and 0 otherwise.
Four algorithms are considered for comparison, applied to each data set :
• CoAT: the case-based prediction algorithm, as of [
The source cases are instances of , but the case base contains only the instances ∈ that maximize (, ) (see Algorithm 3). • CoAT-APC: a combination of the two previous approaches. The source cases = (a − b, (a) − (b)) are diferences between instances of the data set , and the case base (c) contains the source cases that maximize (a − b, c − ).
For each task, the performance is measured by the prediction accuracy, with 10-fold cross validation. The algorithm CoAT+[P2] is tested on each data set with a parameter (the size of the case base ) varying between 5 and ||, by steps of 5. The algorithms CoAT+[P1] and CoAT-APC are tested on each data set for all pairs (, ) with varying between 3 and 51, by steps of 2, and varying between 5 and 50 by steps of 5.
Table 2 gives the classification results. For each data set, the best results considering standard deviations are marked in bold. When the two principles [P1] and [P2] are combined (algorithm Algorithm 3 CoAT+[P2] inputs: (data set), (additional instance), (set of potential classes for ()), , (situation and outcome similarity measures), (size of the case base). output: the predicted value () for the new instance ← the instances = (, ()) ∈ that maximize (, ) () ← arg min∈ Γ( , , ∪ {(, )})) return ()
CoAT-APC), the resulting system ofers a very good performance, and gives the best results for all data sets. This allows to validate the proposed approach and the integration of the analogical proportion principles into case-based predictions. When applied independently, the design principles [P1] and [P2] seem to have diferent impacts on the performance. Running CoAT with a case base restricted to the cases that are most similar with the target situation (algorithm CoAT+[P2]) generally improves the performance, but not for all data sets (see e.g., breastw, wine, or monks2). Working on cases defined as diferences between instances of but with a random case base (algorithm CoAT+[P1]) often improves the performance as well, but for some data sets the performance results are surprisingly low (see e.g., user, wine, breastw, or even monks2). All tests were run using a fixed similarity measure , based on the Euclidean distance, which may not be optimal for all data sets. This may explain why the CoAT algorithm sometimes gives rather poor results. However, applying [P1] and [P2] design principles (CoAT-APC) greatly improves the performance of the classifier, even with this non-optimal similarity measure. In addition, it can be observed that the CoAT-APC algorithm obtains the best results for fairly low values of , usually lower than 20. This parameter determines the size of the case base (c). The computing time remains moderate: for the Balance Scale data set, with = 39 and = 20, predicting the class of a new instance takes 11.5 seconds on a current PC.
This paper proposes an approach to bridge the gap between analogical proportion-based classifiers and case-based prediction algorithms, by showing that analogical proportion-based classification can be interpreted as a special kind of case-based prediction algorithm in which cases are diferences between two instances of the data set, and maximally similar cases are compared to predict the class of a new instance. Results show that if these two design principles taken independently have an impact on the prediction performance of the case-based prediction system, they are especially powerful when combined, even when the prediction is done with a non-optimal similarity measure. On the contrary, the rule-based transfer strategy of analogical proportion-based classifiers seems to have a little impact on their eficiency: replacing it with a diferent transfer strategy, such as the CoAT’s optimization strategy, leads to excellent performance results.
Future works will include comparing the CoAT-APC algorithm with state-of-the-art analogical proportion-based classification algorithms, both in terms of performance and computing time. More generally, there is a need for a shared implementation of the main case-based prediction algorithms, so that their performance can be compared on controlled benchmarks. The study also shows that as a case-based prediction algorithm, analogical proportion-based classifiers use a similarity measure constructed from the Euclidean distance. Future works will include learning a similarity measure that is more adequate to each considered case-based prediction task.