Preference-Based CBR: General Ideas and Basic Principles

1 Introduction

Case-based reasoning (CBR) is a problem solving paradigm built upon a rule of thumb suggesting that "similar problems tend to have similar solutions" [Kolodner, 1993; Aamodt and Plaza, 1994]. More specifically, the idea of CBR is to exploit the experience from similar problems in the past and to adapt then successful solutions to the current situation. Thus, the core of every case-based problem solver is the case base, which is a collection of memorized "chunks of experience", called cases. Besides, the concept of similarity plays a pivotal role in every CBR system.

Despite its great practical success, work on the theoretical foundations of CBR is still under way, and a coherent and universally applicable methodological framework is yet missing. The CBR cycle proposed by Aamodt and Plaza [1994] is a commonly accepted process model, which nicely illustrates the main aspects of the case-based problem solving paradigm. Likewise, the metaphor of knowledge containers, introduced by Richter [Richter, 1995], provides a general framework for the structuring of knowledge in CBR. However, both are high-levels models and still rather far from the conceptual realization and implementation of a case-based problem solver. On the other extreme, many CBR systems have been designed for tackling concrete problems. These, however, are mostly tailored for a specific purpose and not easily applicable to a wider range of problems.

∗The paper on which this extended abstract is based was the recipient of the best paper award of the 2011 ICCBR [H¨ullermeier and Schlegel, 2011].

In-between these two extremes, conceptual models and practical systems, there is arguably a need for developing CBR methodologies [Watson, 1998]. On the one hand, a CBR methodology should be sufficiently general and abstract, so as to allow for the development of generic algorithms, for analyzing formal properties, etc. On the other hand, it should also be sufficiently concrete, so as to support the development of specific applications. To make this idea more tangible, consider as an analogy the formalism of graphical models, by now an established methodology for the design of probabilistic expert systems [Koller and Friedman, 2009]. This class of models disposes of a formal theory and generic algorithms, but also tools for supporting the design of models for concrete applications.

In [H¨ullermeier and Schlegel, 2011], we have made a first step toward a methodological framework for case-based reasoning on the basis of formal concepts and methods for knowledge representation and problem solving with preferences. The topic of preferences has recently attracted considerable attention in artificial intelligence (AI) research and plays an increasingly important role in several AI-related fields, including, e.g., agents, constraint satisfaction, decision theory, planning, machine learning, and argumentation [Doyle, 2004; Goldsmith and Junker, 2008; Domshlak et al., 2011]. Preference-based methods are especially appealing from an AI perspective, notably as they allow one to specify desires in a declarative way, to combine qualitative and quantitative modes of reasoning and to deal with inconsistencies and exceptions in a quite flexible manner. Indeed, a preference can be considered as a relaxed constraint, which, if necessary, can be violated to some degree.

The important advantage of an increased flexibility of a preference-based problem solving paradigm is nicely explained by Brafman and Domshlak [2009]: "Early work in AI focused on the notion of a goal-an explicit target that must be achieved-and this paradigm is still dominant in AI problem solving. But as application domains become more complex and realistic, it is apparent that the dichotomic notion of a goal, while adequate for certain puzzles, is too crude in general. The problem is that in many contemporary application domains ... the user has little knowledge about the set of possible solutions or feasible items, and what she typically seeks is the best that's out there. But since the user does not know what is the best achievable plan or the best available document or product, she typically cannot characterize it or its properties specifically. As a result, she will end up either asking for an unachievable goal, getting no solution in response, or asking for too little, obtaining a solution that can be substantially improved."

Our claim is that the above insights do not only apply to AI in general but to CBR in particular. In fact, as will be argued in more detail below, case-based experience can be modeled in terms of preference information in a quite convenient way and, moreover, case-based inference can be realized quite elegantly in the form of preference processing. As pointed out in the above quotation, a key advantage in comparison to the classical (constraint-based) approach [H¨ullermeier, 2007] is an increased flexibility and expressiveness, which appears to be especially advantageous for CBR.

The remainder of the paper is organized as follows. In the next section, the main ideas of our approach to preferencebased CBR are outlined in an informal way. A formal framework of preference-based CBR as well as two core components of this framework, namely inference and search, is then introduced in Section 3. The paper ends with some concluding remarks and an outlook on future work in Section 4.

2 Preference-based CBR: General Ideas

Experience in CBR is most commonly (albeit not exclusively) represented in the form of problem/solution tuples (x, y) ∈ X × Y, where x is an element of a problem space X, and y an element of a solution space Y. These two spaces can be as simple as Euclidean or categorical spaces (like in classification or regression problems), but may also be very complex; for example, in the problem of text summarization, X could be the "space" of scientific articles and Y the "space" of abstracts [Capus and Tourigny, 2003].

Despite its generality and expressiveness, the standard problem/solution representation exhibits some limitations, both from a knowledge acquisition and reuse point of view.

• Existence of correct solutions: It assumes the existence of a "correct" solution for each problem, and implicitly even its uniqueness. This assumption is often not tenable. In text summarization, for example, there is not a single "correct" abstract of an article. Instead, there will be many possible alternatives, maybe more or less preferred by the user.
• Verification of optimality: Even if the existence of a single correct solution for each problem could be assured, it will often be impossible to verify the optimality of the solution that has been produced by a CBR system. Storing a suboptimal solution y for a problem x, however, and later on reusing this solution as if it were optimal, may mislead future problem solving. This issue is less critical, though does not dissolve completely, if only "acceptable" instead of optimal solutions are required.
• Loss of information: Storing only a single solution y for a problem x, even if it can be guaranteed to be optimal, may come along with a potential loss of information. In fact, during a problem solving episode, one typically tries or at least compares several candidate solutions, and even if these solutions are suboptimal, preferences between themmay provide useful information.
• Limited guidance: From a reuse point of view, a retrieved case (x, y) only suggests a single solution, namely y, for a query problem x0. Thus, it does not imply a possible course of action in the case where the suggestion fails: If y is not a good point of departure, for example since it cannot be adapted to solve x0, there is no concrete recommendation on how to continue.

To avoid these problems, preference-based CBR replaces experiences of the form "solution y (optimally) solves problem x" by weaker information of the form "y is better (more preferred) than z as a solution for x", that is, by a preference between two solutions "contextualized" by a problem x. More specifically, the basic "chunk of information" we consider is symbolized in the form y ⪰x z and suggests that, for the problem x, the solution y is supposedly at least as good as z.

This type of knowledge representation overcomes many of the problems discussed above. As soon as two candidate solutions y and z have been tried as solutions for a problem x, these two alternatives can be compared and, correspondingly, a strict preference in favor of one of them or an indifference can be expressed. To this end, it is by no means required that one of these solutions is optimal. It is worth mentioning, however, that knowledge about the optimality of a solution y∗ , if available, can be handled, too, as it simply means that y∗ ≻ y for all y ̸= y∗ . In this sense, the conventional CBR setting can be considered as a special case of preference-based CBR.

The above idea of a preference-based approach to knowledge representation in CBR also suggests a natural extension of the case retrieval and inference steps, that is, the recommendation of solutions for a new query problem: Instead of just proposing a single solution, it would be desirable to predict a ranking of several (or even all) candidate solutions, ordered by their (estimated) degree of preference:

Obviously, the last problem mentioned above, namely the lack of guidance in the case of a failure, can thus be overcome.

In order to realize an approach of that kind, a number of important questions need to be addressed, including the following: How to represent, organize and maintain case-based experiences, given in the form of preferences referring to a specific context, in an efficient way? How to select and access the experiences which are most relevant in a new problem solving situation? How to combine these experiences and exploit them to infer a solution or, more generally, a preference order on a set of candidate solutions, for the problem at hand?

3 A Formal Framework

In the following, we assume the problem space X to be equipped with a similarity measure SX : X × X → R+ or, equivalently, with a (reciprocal) distance measure ∆X : X × X → R+. Thus, for any pair of problems x, x′ ∈ X, their similarity is denoted by SX(x, x′ ) and their distance by ∆X(x, x′ ). Likewise, we assume that the solution space Y to be equipped with a similarity measure SY or, equivalently, with a (reciprocal) distance measure ∆Y . In general, ∆Y (y, y′ ) can be thought of as a kind of adaptation cost, i.e., the (minimum) cost that needs to be invested to transform the solution y into y′ .

In preference-based CBR, problems x ∈ X are not associated with single solutions but rather with preferences over solutions, that is, with elements from a class of preference structures P(Y) over the solution space Y. Here, we make the assumption that P(Y) is given by the class of all weak order relations ⪰ on Y, and we denote the relation associated with a problem x by ⪰x. More precisely, we assume that ⪰x has a specific form, which is defined by an "ideal" solution 1 y∗ ∈ Y and the distance measure ∆Y : The closer a solution y to y∗ = y∗ (x), the more it is preferred; thus, y ⪰x z iff ∆Y (y, y∗ ) ≤ ∆Y (z, y∗ ). In conjunction with the regularity assumption that is commonly made in CBR, namely that similar problems tend to have similar (ideal) solutions, this property legitimates a preference-based version of this assumption: Similar problems are likely to induce similar preferences over solutions.

3.1 Case-based Inference

The key idea of preference-based CBR is to exploit experience in the form of previously observed preferences, deemed relevant for the problem at hand, in order to support the current problem solving episode; like in standard CBR, the relevance of a preference will typically be decided on the basis of problem similarity, i.e., those preferences will be deemed relevant that pertain to similar problems. An important question that needs to be answered in this connection is the following: Given a set of observed preferences on solutions, considered representative for a problem x0, what is the underlying preference structure ⪰x or, equivalently, what is the most likely ideal solution y∗ for x0?

Case-based Inference as Probability Estimation

We approach this problem from a statistical perspective, considering the true preference model ⪰x0 ∈ P(Y) associated with the query x0 as a random variable with distribution P(· | x0), where P(· | x0) is a distribution Pθ(·) parametrized by θ = θ(x0) ∈ Θ. The problem is then to estimate this distribution or, equivalently, the parameter θ on the basis of the information available. This information consists of a set D of preferences of the form y ≻ z between solutions.

The basic assumption underlying nearest neighbor estimation is that the conditional probability distribution of the output given the input is (approximately) locally constant, that is, P(· | x0) ≈ P(· | x) for x close to x0. Thus, if the above preferences are coming from problems x similar to x0 (namely from the nearest neighbors of x0 in the case base), then this assumption justifies considering D as a representative sample of Pθ(·) and, hence, estimating θ via maximum likelihood (ML) inference by

1 The solution y∗ could be a purely imaginary solution, which may not exist in practice.

An important prerequisite for putting this approach into practice is a suitable data generating process, i.e., a process generating preferences in a stochastic way.

A Discrete Choice Model

Our data generating process is based on the idea of a discrete choice model as used in choice and decision theory [Peterson, 2009]. Recall that the (absolute) preference for a solution y ∈ Y supposedly depends on its distance ∆Y (y, y∗ ) ≥ 0 to an "ideal" solution y∗ , where ∆(y, y∗ ) can be seen as a "degree of suboptimality" of y. As explained in [H¨ullermeier and Schlegel, 2011], more specific assumptions on an underlying (latent) utility function on solutions justify the logit model of discrete choice:

Thus, the probability of observing the (revealed) preference y ≻ z depends on the degree of suboptimality of y and z, namely their respective distances to the ideal solution, ∆Y (y, y∗ ) and ∆Y (z, y∗ ): The larger the difference ∆Y (z, y∗ ) -∆Y (y, y∗ ), i.e., the less optimal z in comparison to y, the larger the probability to observe y ≻ z; if ∆Y (z, y∗ ) = ∆Y (y, y∗ ), then P(y ≻ z) = 1/2. The coefficient β can be seen as a measure of precision of the preference feedback. For large β, P(y ≻ z) converges to 0 if ∆Y (z, y∗ ) < ∆Y (y, y∗ ) and to 1 if ∆Y (z, y∗ ) > ∆Y (y, y∗ ); this corresponds to a deterministic (error-free) information source. The other extreme case, namely β = 0, models a completely unreliable source reporting preferences at random.

Maximum Likelihood Estimation

The probabilistic model outlined above is specified by two parameters: the ideal solution y∗ and the (true) precision parameter β∗ ∈ R+. Depending on the context in which these parameters are sought, the ideal solution might be unrestricted (i.e., any element of Y is an eligible candidate), or it might be restricted to a certain subset Y0 ⊆ Y of candidates.

Now, to estimate the parameter vector θ∗ = (y∗ , β∗ ) ∈ Y0 × R∗ from a given set D = {y(i) ≻ z(i) }Ni=1 of observed preferences, we refer to the maximum likelihood estimation principle. Assuming independence of the preferences, the likelihood of θ = (y, β) is given by

The ML estimation θML = (yML, βML) of θ∗ is given by the maximizer of (3):

The problem of finding this estimation in an efficient way is discussed in [H¨ullermeier and Schlegel, 2011].

3.2 CBR as Preference-guided Search

Case-based inference as outlined above realizes a "one-shot prediction" of a promising solution for a query problem, given preferences in the context of similar problems encountered in the past. In a case-based problem solving process, this prediction may thus serve as an initial solution, which is then adapted step by step. Formally, an adaptation process of that kind can be formalized as a search process, namely a traversal of a suitable space of candidate solutions [Bergmann and Wilke, 1998].

In the spirit of preference-based CBR, we implement casebased problem solving as a search process that is guided by preference information collected in previous problem solving episodes. The type of application we have in mind is characterized by two important properties:

• The evaluation of candidate solutions is expensive. Therefore, only relatively few candidates can be considered in a problem solving episode before a selection is made. Typical examples include cases where an evaluation requires time-consuming simulation studies or human intervention (for example, the reading of a text summary).
• The quality of candidate solutions is difficult to quantify. Therefore, instead of asking for numerical utility degrees, we make a much weaker assumption: Feedback is only provided in the form of pairwise comparisons, informing about which of two candidate solutions is preferred (for example, which of two text summaries is better). Formally, we assume the existence of an "oracle" (for example, a user or a computer program) which, given a problem x0 and two solutions y and z as input, returns a preference y ≻ z or z ≻ y as output.

We assume the solution space Y to be equipped with a topology that is defined through a neighborhood structure: For each y ∈ Y, we denote by N(y) ⊆ Y the neighborhood of this candidate solution. The neighborhood is thought of as those solutions that can be produced through a single modification of y, i.e., by applying one of the available adaptation operators to y (for example, adding, removing or modifying a single sentence in an abstract).

Our case base CB stores problems xi together with a set of preferences P(xi) that have been observed for these problems. Thus, each P(xi) is a set of preferences of the form y ≻xi z, which are collected while searching for a good solution to xi.

We conceive preference-based CBR as an iterative process in which problems are solved one by one. In each problem solving episode, a good solution for a new query problem is sought, and new experiences in the form of preferences are collected. In what follows, we give a high-level description of a single problem solving episode:

• (i) Given a new query problem x0, the K nearest neighbors x1, . . . , xK of this problem (i.e., those with smallest distance in the sense of ∆X) are retrieved from the case base CB, together with their preference information P(x1), . . . , P(xK).
• (ii) This information is collected in a single set of preferences P, which is considered representative for the problem x0 and used to guide the search process.
• (iii) The search for a solution starts with an initial candidate y∗ ∈ Y, namely the "one-shot prediction" (4) based on P, and iterates L times. Restricting the number of iterations by an upper bound L reflects our assumption that an evaluation of a candidate solution is costly.
• (iv) In each iteration, a new candidate yquery is determined, again based on (4), and given as a query to the oracle, i.e., the oracle is asked to compare yquery with the current best solution y∗ . The preference reported by the oracle is memorized by adding it to the preference set P0 = P(x0) associated with x0, as well as to the set P of preferences used for guiding the search process. Moreover, the better solution is retained as the current best candidate.
• (v) When the search stops, the current best solution y∗ is returned, and the case (x0, P0) is added to the case base.

The preference-based guidance of the search process is realized in (iii) and (iv). Here, our case-based inference method is used to find the most promising candidate among the neighborhood of the current solution y∗ , based on the preferences collected in the problem solving episode so far. By providing information about which of these candidates will most likely constitute a good solution for x0, it (hopefully) points the search into the most promising direction.

For a detailed description of the above search procedure, as well as first experimental studies, we refer to [Abdel-Aziz et al., 2013].

4 Conclusion

In this paper, we have presented the idea of a preferencebased approach to CBR: Experience is represented in the form of preferences, which are "contextualized" by a previously solved problem, and these preferences are used to direct the search for a good solution to a new problem. This is an interesting alternative to conventional CBR whenever solution quality is a matter of degree and feedback is only provided in an indirect or qualitative way. We have introduced a general framework of preference-based CBR, in which prediction is realized through statistical inference and problem solving is formalized as (heuristic) search.

For future work, we plan to generalize our framework in various directions, and extend it by adding components that are essential for a complete and effective CBR system. For example, since the number of preferences collected in the course of time may become rather large, effective methods for case base maintenance ought to be developed [Smyth and McKenna, 2001]. Besides, we are of course interested in testing and evaluating our approach in different application domains.

Acknowledgments

This work has been supported by the German Research Foundation (DFG).