EnergyCompress: A General Case Base Learning Strategy

1 Introduction

Case-based prediction (CBP) methods, such as the k nearest neighbor (k-NN) classifier, the AP -classifier [Bounhas et al., 2017] or CoAT [Badra, 2020], are kernel-based learning methods, insofar as they crucially depend on the choice of a similarity or distance function that takes a case base as a parameter. These methods do not learn a model of the entire decision function prior to prediction, but instead infer the decision function value for a new case by direct comparison with similar cases retrieved from the case base. This inference process depends on three parameters θ = (σS, σR, CB): the similarity measures in the input (resp. output) space σS, (resp. σR), and the case base CB. The σR measure is usually fixed depending on the task at hand (e.g. classification or regression), but σS and CB have huge ranges of possibilities.

Traditionally, knowledge-based methods were used to derive similarity measures for a given case base [Kolodner and Leake, 1996]. In the machine learning community, the metric learning task [Ghojogh et al., 2022] addresses a similar issue, although in a different context, and recent case-based reasoning (CBR) research applies machine learning methods to learning similarity [Mathisen et al., 2019]. This paper proposes taking the reverse approach: rather than assuming the case base is given and generating a similarity measure for it, it introduces a method, EnergyCompress, that learns a case base by starting from a candidate case base and selecting an appropriate subset for a given similarity measure. This can be seen as relating to Richter's [2003] observation that CBR involves multiple knowledge containers, including similarity and case knowledge, interacting such that one can compensate for the other, e.g., here, that a well-chosen case base can compensate for a suboptimal similarity measure.

The case base selection task has been studied extensively in case based reasoning research on case base maintenance by compression, which selects subsets of an original case base to retain (e.g. [Juarez et al., 2018], see more details in Sec. 2). However, such work usually makes the implicit assumption that a "bigger is better" for prediction accuracy: research on case-base compression generally aims at other benefits, such as increased efficiency. In contrast, EnergyCompress enables sculpting the decision frontier by removing cases to increase accuracy, in addition to compressing to reduce the inference time. Thus, in contrast to most existing approaches, it does not sacrifice one for the other. This is illustrated in Fig. 1, whick shows the decision regions obtained for the Iris dataset, on a 2D PCA projection, for three CBP algorithms (CoAT, CtCoAT and 3-NN, see their descriptions in Sec. 4, based on the Euclidean distance) and SVM with a radial basis function (width = 6.4×10-2 ). Both rows show the prediction regions and their associated accuracy computed on the whole case base, CB0. For each CBP algorithm, the left figure shows the results when the inference algorithm uses the whole case base CB0 while, on the right figure, it only uses CBf , extracted from CB0 by EnergyCompress. Here EnergyCompress leads to a different decision frontier that achieves a higher accuracy on CB0, for all 4 algorithms, with smaller case bases CBf , (size reduction up to 90% for the 3-NN) and thus decreases inference time.

The second main characteristic of EnergyCompress is that it is a general method: it can be applied to virtually any CBP algorithm, provided that the algorithm assigns a probability 1 to each potential outcome, to provide a tailored case base. Defining a single case base learning strategy applicable to different prediction algorithms remedies one of the main limitations of existing case base learning algorithms, which are dedicated to specific approaches (often to k-NN, see Sec. 2, or to CoAT [Marquer et al., 2023] ) .

EnergyCompress relies on an original formulation of the CBP task in the framework of energy-based models [LeCun et al., 2006]. This formulation offers a new and valuable characterization of the notion of competence, in particular at the source case level. The case base learning method then consists of removing cases from a candidate set so as to learn the underlying energy function. This constitutes a generalization of the approach proposed by [Marquer et al., 2023] for the specific case of the CoAT algorithm.

The contributions of the paper thus include a general case base learning strategy, that can be applied to a large variety of case-based prediction algorithms and that enables both decreasing inference time and increasing prediction performance, without sacrificing one for the other. Extensive experiments run on 18 UCI datasets demonstrate that EnergyCompress obtains very competitive compression ratios while leading to an accuracy (given in %) increase on average of +7.4 for k-NN, +13.3 for CoAT, +26.5 for CtCoAT, and +3.7 for SVM RBF. Although we focus in this paper on the selection of instances to include in the case base, the experimental results also support that the indicators we define lead to a valuable characterization of the competence notion (see Sec. 3.2 for a discussion).

The paper is organized as follows. Sec. 2 discusses related work, both in the domains of case-based prediction and energy-based machine learning. Sec. 3 describes the proposed EnergyCompress strategy, discussing the energy-based formulation of CBP and presenting the induced general competence model as well as the proposed case base learning strategy. Sec. 4 shows how this general case base learning strategy can be implemented for different CBP algorithms. Sec. 5 presents the experimental study of the approach. Finally, Sec. 6 concludes the paper and discusses future work.

1 If a CBP algorithm assigns a support to each potential outcome instead of a probability, a probability can be computed as the ratio of the support for each outcome compared to the total support.

2 RelatedWork

This section discusses the position of the EnergyCompress method with respect to related works, both with respect to case-based prediction and energy-based learning.

Case-based prediction. Case-based reasoning (CBR) relates to the cognitive ability of analogical reasoning and models a special kind of plausible inference principle, according to which if two situations are judged similar, then it is plausible that they will also have similar outcomes, described in CBR by the phrase "similar problems have similar solutions" [Anthony and Ratsaby, 2015; Leake and Wilson, 1999, inter alia]. Case-based prediction (CBP) algorithms implement such a transfer step for prediction tasks, which corresponds to applying analogical reasoning to classification or regression tasks in machine learning. In CBP methods, analogical transfer is used to complete the description of a new case by direct comparison with similar cases. A recent review of the literature on case-based prediction [Badra and Lesot, 2023] shows that all surveyed implementations of the inference process share a common principle: they optimize a transfer of similarity knowledge, from the situation space to the outcome space. The predicted outcome is the one that optimizes a measure of compatibility between two similarity measures on a case base, following the plausible inference principle stated above. The compatibility measure can take the form of a joint similarity measure, a set of continuity constraints, a set of rules or a global indicator. In this paper, we focus on the approaches that optimize a global indicator computed on the whole case base, showing in Sec. 3.1 that their inference process can then be interpreted as an energy-based inference.

The notations used throughout the paper are as follows: S denotes the input space, and R the output space, respectively equipped with the similarity measures σS and σR. An element of S is called a situation, and an element of R an outcome, or a result. A set CB = {(s1, r1), . . . , (sn, rn)} of elements in S ×R is called a case base. An element ci = (si, ri) ∈ CB is called a source case. Let Tref ⊂ S ×R be a set of cases called a reference set, and ct = (st, rt) ∈ Tref be a reference case. A potential case (st, ˆ r) can be constructed from a reference case by associating to the same situation st ∈ S, a different outcome ˆ r ∈ R, ˆ r ̸= rt. Let us denote by Predθ a CBP algorithm and θ = (σS, σR,CB) its parameters. The predicted outcome r∗ = Predθ(st) for a new situation st is the one that makes the new similarity relations σR(ri, r∗ ) most compatible with the new similarity relations σS(si, st).

Case base maintenance. Research in case-base maintenance has a long history (see [Juarez et al., 2018] for a survey). The origins date back to early work on case selection in the context of the condensed nearest neighbor algorithm (CNNR [Hart, 1968]), which aimed at selecting a subset of the initial set of cases still sufficient for k-NN to generate a correct categorization. This process is commonly referred to as compressing the case base. Focuses of case-base maintenance include increasing prediction accuracy, e.g., by removing noisy cases, and removing unnecessary cases to increase the efficiency of source case retrieval [Cummins, 2013]. Much research concerns competence models and competence-based deletion, which prioritizes removal of cases that make the least contribution to overall coverage, considering both their coverage (cases for which they can provide a solution) and reachability (whether they could be solved using other cases) [Smyth and McKenna, 2001]. The aim is to compress the case base while minimizing competence loss; the "gold standard" for performance is the full case base. These methods depend on the "representativeness assumption" that existing cases are a good proxy for future cases, to assess their contributions; the proposed EnergyCompress method can accommodate this assumption, but does not depend on it 2 . Besides pioneering algorithms such as RENN [Tomek, 1976] or IB3 [Aha et al., 1991], a recent literature review on instance selection for automatic text classification [Cunha et al., 2023] shows that recent density-based algorithms such as LSSm [Leyva et al., 2015] or XLDIS [Carbonera, 2017] are also effective in retaining accuracy while reducing the training set size and the training process time by discarding noisy or redundant instances.

Relationship to the knowledge containers perspective in CBR. The knowledge of CBR systems is often viewed in terms of a set of four "knowledge containers" [Richter, 2003]: the case base, the case vocabulary, 3 similarity knowledge and case adaptation knowledge, with strengths in one able to compensate for weaknesses in others. For example, having a better case base, with better coverage, may compensate for weak case adaptation knowledge. However, the value of knowledge cannot be judged in isolation; the harmonization of components such as similarity and adaptation knowledge strongly affects performance [Leake and Ye, 2021]. Much research focuses on acquiring similarity knowledge for a given case base (e.g.,[Mathisen et al., 2019]). The work in this paper investigates the contrasting approach of starting from a given similarity measure and selecting a good case base for it.

Energy-basedmodels. This section briefly summarizes the basics of the energy-based framework the paper uses to provide an original solution to the above-mentioned case-base maintenance issues. Inspired by statistical physics, energybased models [LeCun et al., 2006] specify a probability distribution p(x; θ) = e-Eθ(x) / ∫ e-Eθ(x)dx via a parameterized scalar-valued function Eθ(x) called an energy function. In its conditional version, the function Eθ : X × Y -→ R

2 In Sec. 3.2 we define the competence used by EnergyCompress, measured on a set Tref of cases distinct from the case base CB. Under the representativeness assumption, we can have Tref = CB as CB is representative of the distribution of cases.

3 Richter defines the vocabulary of "a knowledge representation system [as] which data structures and which elements of the structures are used to represent primitive notions." Generally (and here) the attribute-value representation is used, typically in tabular form.

associates each pair (x, y) ∈ X × Y with a scalar value Eθ(x, y) that represents the compatibility between the input x and the output y under the set of parameters θ. The energy function Eθ takes low values when y is compatible with x, and higher values when y and x are less compatible. The goal of the energy-based inference is to find, among a set of outputs Y, the output y∗ ∈ Y that minimizes the value of the energy function: y∗ = argminy∈Y Eθ(x, y). Given a family of energy functions Eθ(x, y) indexed by a set of parameters θ, the goal of learning the energy function 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 [Hinton et al., 2006] is a common learning strategy that, given a numerical hyperparameter λ, optimizes a contrastive loss function such as the hinge loss, which is defined, for a training sample (xk, yk) and a generated out of distribution sample (xk, ˆ y) by: ℓ(θ, xk, yk, ˆ y) = max(0, λ + Eθ(xk, yk) - Eθ(xk, ˆ y)). The hinge loss associates a loss value to a training sample (xk, yk) whenever its energy is not lower by at least a margin λ than the energy of the incorrect sample (xk, ˆ y). In CBR terms, the inputs X correspond to the situations S, and the outputs Y to the outcomes R. If we associate CBP algorithms with an energy function Eθ (we explain how in Sec. 4), the hinge loss associated with a case (sk, rk) and Eθ can be measured. This serves as the foundation for the competence measure we propose in Sec. 3.2.

3 EnergyCompress

In order to solve the problem of learning an appropriate case base for a given CBP algorithm with chosen similarity measures σS, σR, the proposed EnergyCompress strategy relies on an energy-based model of CBP. The general model is described in Sec. 3.1 below, its implementation for four reference specific algorithms is detailed in Sec. 4. This section then describes the induced competence model, which leads to the proposed case base learning strategy.

3.1 An Energy-BasedModel

A core idea proposed in [Marquer et al., 2023] is that an inference process that optimizes a global indicator of compatibility between two similarity measures on a case base can be interpreted as an energy-based inference.

The input space X is the situation space S and the output space Y is the outcome space R. The energy function EP red θ : S ×R -→ R measures, for Predθ, the compatibility of the outcome similarities with the added situation similarities when a potential new case ˆ ct = (st, ˆ r) is added to the case base. We propose to extend this definition to compute the energy of a set A ⊂ S × R of cases by taking

The goal of the energy-based inference is to find, among the set of potential outcomes ˆ r ∈ R, the outcome that minimizes the energy function, i.e.,

The energy function EPred θ is learned by minimizing on a reference set Tref the loss L = ∑ct=(st,rt)∈Tref ℓ(θ, ct), where ℓ is defined by:

3.2 AGeneral Competence Model

The notions of competence of a case or of a case base, and of the influence of a case on the prediction, can be captured in an energy-based framework. Let us denote by D ⊆ S × R a set of instances, and (x, y) ∈ D an instance of D.

Let Predθ with θ = (σS, σR,CB) be a CBP algorithm that can be expressed as an energy-based inference, i.e., that satisfies Eq. 1 for some energy function EPred θ . The competence of a case base CB is measured w. r. t. a given reference set Tref by taking the (opposite of) the hinge loss on Tref :

The competence of a source case c = (s, r) ∈ CB w. r. t. a reference set Tref can be defined as the loss of competence that would happen if this source case was deleted from CB:

This definition also allows defining a notion of competence locally as the contribution of c on each individual reference case ct ∈ Tref of the reference set:

This notion of influence of a case on the prediction can be seen as a continuous counterpart of the popular notion of case coverage introduced in [Smyth and McKenna, 2001] for k-NN. The influence of a case is computed here with respect to a reference set Tref , and not to the case base CB. The case influences are aggregated to measure the competence of a case base on the whole reference set, as well as the competence of each source case. In this paper, we focus on the application of this competence model to learn the most competent case base for a given prediction algorithm Predθ.

3.3 The Case Base Learning Strategy

The case base learning strategy consists in iteratively deleting the least competent source case from a candidate set CB0. As the competence of a case base is defined directly from the loss function of the underlying energy-based model (Eq. 2), selecting the most competent case base enables learning the energy function EP red θ by optimizing the CB parameter. The EnergyCompress case deletion procedure is described by Algorithm 1: at each iteration, the source case that contributes least to the competence of the case base CB w.r.t. the reference set Tref is deleted from the case base (line 11). In this algorithm, the returned parameter θf = (σS, σR,CBf) is the one that maximizes accuracy (function Acc, line 6) on the reference set Tref . The computational complexity of EnergyCompress is in O(|CB| × |Tref | × |R|) × O(E), where E is the computational complexity of the energy computation.

Algorithm 1 EnergyCompress case deletion procedure. C(c, θ, Tref ) depends on Pred and the associated EPred θ .

1: function ENERGY COMPRESS(σS, σR,CB0, Tref ) 2: CB = CB0 3: max acc = -1 4: repeat 5: θ = (σS , σR, CB) 6: acc = Acc(P redθ(Tref )) 7: if acc ≥ max acc then 8: max acc = acc 9: θf = θ 10: end if 11: CB = CB \ {arg minc∈CB C(c, θ, Tref )} 12: until |CB| = 0 13: return θf 14: end function

4 Application to Various CBP Algorithms

For EnergyCompress to be applicable to a given CBP algorithm Predθ, the only requirement is that Predθ can be expressed as an energy-based inference, i.e., as an algorithm that predicts the outcome that minimizes an energy function EP red θ (Eq. 1). We show in this section that each of the four CBP algorithms CoAT, CtCoAT, k-NN, and the AP-Classifier can be expressed as minimizing an energy function. Tab. 1 gives examples of such energy functions.

CoAT. The CoAT case-based prediction algorithm was introduced in [Badra, 2020] and formulated in an energy-based model in [Marquer et al., 2023]. Its energy function ECoAT θ , reported in Tab. 1, simply counts the number of new triplets that are not ordered in the same way by σS and by σR.

CtCoAT. The CtCoAT algorithm is a variant of the CoAT case-based prediction algorithm that we introduce in this paper. Its energy function ECtCoAT θ is a continuous version of the CoAT energy function where in a classification setting, each positive triplet (i.e., a triplet (i, j, k) such that σR(ri, rj) = σR(ri, rk)) contributes 12 and each negative triplet (such that σR(ri, rj) ̸= σR(ri, rk)) contributes to a value between 0 (easy negatives) and 1 (hard negatives). When σR(ri, rj) < σR(ri, rk), if σS(si, sj) ≥ σS(si, sk) (hard negative), then 1 2 (1 - [σS(si, sj) - σS(si, sk)][σR(ri, rj) - σR(ri, rk)]) ∈ [ 12 , 1] and the triplet greatly increases the energy, as in ECoAT θ under the same conditions. If σS(si, sj) < σS(si, sk) then the contribution of (i, j, k) is in [0, 1 2 [ (easy negative), and the triplet has a low contribution to the energy.

k nearest neighbors (k-NN) alg. The k-NN decision function can be written as r∗ = arg maxˆ r∈R χθ(st, ˆ r), where

is a joint similarity measure that measures the compatibility of σS with σR on CB. In this expression, 1kσS(si,·) (s) returns 1 if s belongs to the set of k nearest neighbors of st. The energy function EkNN θ measures the incompatibility of σS

with σR on CB according to χθ: its value is 1 if σS and σR are incompatible, and then decreases as χθ increases.

Analogical proportion-based classifiers. Analogical proportion-based classifiers (see e.g. [Bounhas and Prade, 2024; Couceiro et al., 2017; Couceiro et al., 2018]) can be modeled as special CBP algorithms that reason on similar differences between instances [Badra and Lesot, 2022]. The case base CB = {ci = (si, ri)} is constructed from all pairs (a, b) of instances of a set of instances D, i.e., ci = (si, ri) = (a - b, f(a) - f(b)) where f(a) is the outcome of a. A new instance (x, ˆ y) added to D leads to a set of |D| potential new cases ˆ ct = (st, ˆ r) with ˆ ct = (st, ˆ r) = (c - x, f(c) - ˆ y), formed by taking all possible triples (a, b, c) from D. The similarity measures σS and σR are chosen such that σS(a - b, c - x) = 1 iff a : b :: c : x holds, and σR(f(a) - f(b), f(c) - ˆ y) = 1 iff f(a) : f(b) :: f(c) : ˆ y holds. The transfer strategy is rule-based, and consists in predicting for a new x the value y∗ that maximizes the number of times that the rule (σS ≈ 1) → (σR = 1) can be triggered to derive y∗ . This means that the prediction y∗ is the one that maximizes a compatibility measure χθ(st, ˆ r) that counts for each potential outcome ˆ r the number of new pairs of cases (ci, ˆ ct) for which σR(ri, ˆ r) = 1 and σS(si, st) ≈ 1. The AP-Classifier [Bounhas et al., 2017] implements this transfer strategy by adding up, for each potential new case ˆ ct = (st, ˆ r), the similarity values σS(si, st) for all source cases ci = (si, ri) such that σR(ri, ˆ r) = 1. The obtained energy function EAP θ resembles the one defined for k-NN (see Tab. 1), but needs to be aggregated on the |D| new cases ˆ ct resulting from the addition of the instance (x, ˆ y). The decision function of the AP-Classifier can be written as:

Although these algorithms also maximize a global compatibility measure χθ and can be interpreted as implementing an energy-based inference, they are not included in the following experiments, due to their high computational cost.

Extension to any probability-based machine learning model. At a very general level, predictive models that provide probabilities for each possible outcome can be interpreted as energy-based models. For our purposes, given a conditional probability model P(ˆ r|s) that predicts r∗ = arg maxˆ r∈R P (ˆ r|st), we define the energy function of the model as EP θ (st, ˆ r) = 1-P (ˆ r|st). This definition follows the intuitions of energy-based models: more desirable outcomes are identified by higher probabilities and lower energies.

Support VectorMachines (SVMs). SVMs can be seen as a specific case of the previous probability-based machine learning model. To do so, their posterior can be approximated by Platt scaling [Platt, 1999].

5 Experiments

This section describes the experiments run to validate that (i) EnergyCompress substantially increases the performance of CBP algorithms for a fixed similarity measure σS, (ii) the obtained compression ratio is competitive w.r.t. the state of the art, (iii) the method is general, in that it both allows capturing competence for a variety of CBP algorithms and learning a case base tailored for each prediction algorithm 4

5.1 Protocol

The case base learning methods CNNR, ENN, XLDIS, LSSm, IB3, and EnergyCompress were tested on 18 UCI datasets against the prediction algorithms CoAT, CtCoAT, kNN (with k = 7), as well as SVMs with linear, polynomial, and radial basis function kernels.

The 18 datasets, listed in Tab. 2, are attribute-value datasets with 3 to 56 attributes and 2 to 7 classes, used in a classification setting. For each classification task, the initial parameters θ0 = (σS, σR,CB0) are chosen as follows. The outcome space R is the set of class labels ri, and σR is the class membership similarity measure, such that σR(ri, rj) = 1 if ri = rj, and 0 otherwise. For CoAT, CtCoAT, and k-NN, the similarity measure σS is chosen to be the decreasing function σS(si, sj) = e-d(si,sj) of the Euclidean distance d. The SVMs use the implementation and default parameters from scikit-learn 5 to fit the kernel and to estimate the probabilities.

4 Code for reproducing the experiments is available at: https:// github.com/EMarquer/MeATCube/tree/maintenance benchmark

All pairs (Learn, Pred) are formed, where Learn ∈ {CNNR, ENN, . . .} is a case base learning method and Pred ∈ {CoAT, CtCoAT,. . .} is a CBP algorithm. For each pair (Learn, Pred), the learning algorithm Learn is applied to learn CBf from the candidate base CB0, with a hinge margin λ = 0.1. The similarity measures σS and σR remain fixed in the process, only the case base CBf is learned.

We apply 10-fold cross validation with stratified splitting. For each dataset D, each fold is constructed by sampling three distinct subsets CB0, Tref , and Ttest fromD. The candidate base CB0 serves as the initial case base. The reference set Tref is used by EnergyCompress to learn CBf from CB0. The test set Ttest is not used for learning, but only to measure the accuracy of each CBP algorithm before and after learning took place. The sizes for these sets are taken to be |Tref | = |Ttest| = min(100, .2 × |D|), and |CB0| = min(50, |D| - (|Tref | + |Ttest|)).

Two quality criteria are considered. The accuracy increase Acc(P redθf (Ttest))-Acc(P redθ0 (Ttest)) measures the difference between the initial accuracy Acc(Predθ0 (Ttest)) and the accuracy Acc(P redθf (Ttest)) computed with the final parameters θf = (σS, σR, CBf ). The relative size |CBf | |CB0| of the learned case base is the ratio between the size of the learned case base CBf and the size of the initial case base CB0.

In order to study the extent to which EnergyCompress provides case bases that are tailored for the prediction algorithm using them, we apply the following protocol: for each pair (pred1, pred2) ∈ Pred2 (i) we learn a case base using EnergyCompress on pred1 and Tref , and (ii) we use the learned case base to train pred2 and observe its performance on Ttest. If the performance with the pair (pred1, pred2) (pred1 ̸= pred2) is significantly lower than with the pairs

5 https://scikit-learn.org/stable/modules/generated/sklearn.svm. SVC.html

(pred1, pred1) and (pred2, pred2), the case base learned with pred1 (resp. pred2) is more suitable for prediction with pred1 (resp. pred2).

5.2 Results

Increasing performance. EnergyCompress (denotedEC in the result table) always increased the performance of the CBP algorithms while substantially reducing the case base size. Tab. 3 shows the average accuracy increase and relative size after compression obtained on the 18 UCI datasets for each case base learning method and each CBP algorithm. The obtained accuracy increase was strictly positive for k-NN, CoAT, and CtCoAT on all datasets. The average accuracy increase is of +7.4 for k-NN (min 2.5, max 22.5), +13.3 for CoAT (min 3, max 39.7), and +26.5 for CtCoAT (min 8, max 65.8). The accuracy increase is less significant for SVMs but still always positive or null on all datasets, between 3.7% and 5.3% in average. The reason why CtCoAT exhibits the highest increase is probably due to the fact that for the same similarity measure σS, the average performance of CtCoAT is the lowest before case base learning (Tab. 4), which means that CtCoAT starts with the highest margin of improvement. Nonetheless, after learning, the algorithm exhibits a performance comparable to an algorithm such as k-NN.

With respect to its objective to increase accuracy, EnergyCompress far outperforms all methods of the state of the art for k-NN, CoAT, and CtCoAT: the accuracy increase is doubled compared to other methods on average. All accuracy increases provided in Tab. 3 and the more detailed results given in Tab. 4 are significant, as for each row (180 experiments each) the paired t-tests p-values are of the order of 10-4 or smaller, except for 5 cases where it is of the order of 10-3 (IB3 with SVM-poly, SVM-rbf, and CoAT, and XLDIS with SVM-rbf and kNN). The gain in case base size is also very competitive compared to the state of the art: on average EnergyCompress gives the lowest relative case base size for CoAT and SVM-poly, and is among the three lowest case base sizes for the other algorithms, even though in these experiments, the stopping criterion for compression was chosen to optimize accuracy on the reference set, not compression.

The results also demonstrate the generality of the approach. EnergyCompress can be applied to a variety of prediction algorithms and allows reducing the case base size (and thus, the inference time) for all tested algorithms. The accuracy increase is less significant for SVMs, however, perhaps because SVMs are not relying that much on a complex inference process involving the case base CB at prediction time, so tuning the CB parameter may have less effect on their performance.

Additionally, the success of the compression process and the increase in performance validate the proposed general competence model. Despite not using accuracy when computing the competence, for all the considered CBP approaches the cases selected for removal have a similar impact on performance as they have on competence. This follows what was observed for synthetic data with CoAT in [Marquer et al., 2023], and this alignment between predictive performance and the measure of case competence substantiates the intuitions behind using the hinge loss to measure competence. Additionally, the success of the compression process and the increase in performance validates the proposed general competence model.

Case base tailored learning. The case base learned by EnergyCompress is tailored for a given CBP algorithm. Fig. 2 illustrates this idea by showing for the Iris dataset the accuracies obtained according to the model used to select the cases and the model used for prediction. The best accuracy is obtained on the diagonal, when these two models coincide. The performance drop between this diagonal and the other pairs is significant (according to paired Student t-tests), with, for instance, for Iris, more than 50% of pairs with p-values under 0.031, and 25% under 0.001.

6 Conclusion and FutureWork

EnergyCompress is a general case-base learning strategy that enables increasing the performance of a wide variety of casebased prediction algorithms while reducing the size of the case base. The obtained case base is not only smaller, but it is also tailored for the prediction algorithm for which it has been learned. The method is general: it can be applied to any case base prediction algorithm, and even to training data selection for any classifier that assigns a probability (normalized or not) to each potential outcome. The underlying energybased model can be leveraged to capture various competence notions such as the competence of a case or of a case base, or the influence of a particular case on the prediction.

We believe that the obtained results (e.g.,+7.4% accuracy in average for the k-NN algorithm) constitute a breakthrough because they demonstrate that the role of the case base is not only to provide valuable knowledge on the task at hand, but a parameter that can be learned to tune the prediction algorithm to the task. These improvements were made possible by the recent progress in the modeling of the case base inference process, but work is needed to better understand this family of algorithms (e.g.,understand why the CtCoAT algorithm relies so heavily on the quality of the case base). In this paper, σS was fixed, so the next steps will include exploring how case base compression interacts with similarity learning for CBP. Other perspectives include testing on regression scenarios, exploring alternative stopping criteria in Algorithm 1 (e.g.,to favor the compression ratio instead of accuracy), developing and enriching the competence model, running a qualitative analysis of the obtained case bases.

Acknowledgements

This work has been supported by the French National Agency for Research (ANR), namely, projects ANR-22-CE23-0002 (ERIANA), ANR-22-CE23-0023 (AT2TA), and ANR-22CE23-0032 (SMeLT).