Plausible Repairs for Inconsistent Requirements

1 Introduction

Knowledge-based recommenders [Burke, 2000; Felfernig et al., 2007] support the effective identification of interesting items from large and complex assortments. Examples for such items are different types of financial services, computers, or digital cameras. In contrast to collaborative filtering [Konstan et al., 1997] and content-based filtering approaches [Pazzani and Bilsus, 1997], knowledge-based recommenders rely on an explicit representation of item and advisory knowledge. Those systems exploit two different types of knowledge sources: on the one hand explicit knowledge about the given set of customer requirements (in this paper denoted as R={r1, r2, …, rm}), on the other hand deep knowledge about the underlying items (denoted as I={i1, i2, …, in}). Recommendation knowledge is represented in the form of explicit constraints that relate requirements to the corresponding item properties. For simplicity, in this paper requirements will be directly tested on the item properties in the form of conjunctive queries. Interacting with a knowledge-based recommender application typically means to answer a set of questions (requirements elicitation phase), repairing inconsistent requirements (if no recommendation could be found), and evaluating recommendations. In this paper we focus on situations where no recommendation could be found. In order to deal with such situations, we propose an algorithm for the automated and personalized repair of inconsistent requirements that can improve the overall quality and acceptance of recommender interfaces.

/The work presented in this paper has been developed within the scope of the research projects WECARE, V-KNOW (both are funded by the Austrian Research Agency, FFG/FWF), and Softnet Austria that is funded by the Austrian Federal Ministry of Economics (bm:wa), the province of Styria, the Steirische Wirtschaftsförderungsgesellschaft mbH (SFG), and the city of Vienna in terms of the center for innovation and technology (ZIT).

Existing approaches to the handling of inconsistent requirements are focusing on low-cardinality diagnoses [Felfernig et al., 2004; Jannach, 2006; Junker, 2004] respectively explanations [O'Sullivan et al., 2007] (where diagnoses/explanations are computed in order-increasing cardinality [Reiter 1987]), or high-cardinality sets of maximally successful sub-queries [Godfrey, 1997; McSherry, 2004]. Such diagnoses resp. successful sub-queries indicate potential areas for changes but do not propose concrete repair actions. Furthermore, it definitely cannot be guaranteed that lowcardinality diagnoses lead to the most interesting repair actions for a user [O'Sullivan et al., 2007]. In order to tackle this challenge, we propose an approach that integrates knearest neighbor algorithms typically applied in case-based [Burke, 2000] and collaborative recommendation [Konstan et al., 1997] with the Hitting Set Directed Acyclic Graph (HSDAG) algorithm used for the calculation of diagnoses [Reiter, 1987]. Thus, our major contribution is to enhance model-based diagnosis with collaborative problem solving and thus to support the calculation of individualized repairs.

The remainder of this paper is organized as follows. In Section 2 we introduce a working example from the domain of financial services. In Section 3 we sketch the basic concepts behind non-personalized repair actions for inconsistent requirements. In Section 4 we introduce our algorithm for calculating personalized repairs. The results of evaluations are presented in Section 5. In Section 6 we provide an overview of related work. With Section 7 we conclude the paper.

2. Example Domain: Financial Services

The following (simplified) assortment of financial services will serve as working example throughout the paper (see Table 1). The set of financial services {i1, i2, …, i8} is stored in the item table I. Let us assume that our example customer has specified the following requirements that cannot be satisfied by the items of I: R = {r1:return-rate >= 5.5, r2:runtime = 3.0, r3:accessibility = yes, r4:bluechip = yes}. The feasibility of those requirements can simply be checked by a relational query �[R]I where �[R] represents the selection criteria of the query. For example, �[return-rate >= 5.5]I would result in the financial services {i6, i7, i8}.

Note that �[r1:return-rate >= 5.5, r2:runtime = 3.0, r3:accessibility = yes, r4:bluechip = yes]I = ⇓, i.e., no solution could be found for the set of requirements. In such situations customers ask for the recommendation of possible repairs which restore consistency between the requirements in R and the underlying item assortment I. State-of-the-art knowledge-based approaches [Felfernig et al., 2004; Jannach, 2006; Felfernig et al., 2007; O'Sullivan et al., 2007] calculate minimal sets of faulty requirements which should be changed in order to find a solution. We show how to extend those approaches by introducing an algorithm for the calculation of personalized repairs.

3. Calculating Non-Personalized Repairs

We exploit the concepts of Model-Based Diagnosis (MBD) [Reiter 1987; de Kleer et al., 1992] which allows the automated identification of minimal sets of faulty requirements ri ∨ R [Felfernig et al., 2004]. Model-based diagnosis starts with the description of a system which is in our case the predefined item assortment I. If the actual behaviour of the system conflicts with its intended behaviour (recommendation can be found), the diagnosis task is to determine those components (in our case the requirements in R) which, when assumed to be functioning abnormally, explain the discrepancy between the actual and the intended system behaviour. A diagnosis represents a minimal set of faulty components (in our case requirements) whose adaptation (repair) will allow the identification of a recommendation.

On a more technical level, minimal diagnoses for faulty requirements are identified as follows. Given I = {i1, i2, …, in} (item set) and a set R = {r1, r2, …, rm} of requirements which is inconsistent with I, i.e., �[R]I = ⇓. In such a situation, state-of-the-art recommenders [Felfernig et al., 2004; Felfernig et al., 2007] calculate a set of minimal diagnoses D = {d1, d2, …, dk}, where #di ∨ D: �[R - di]I ♦ ⇓, i.e., each di is a minimal set of requirements which have to be changed in order to make recommendations feasible. Minimality means that #di ∨ D: not & di'∉di s.t. �[R - di']I ♦ ⇓.

A corresponding Customer Requirements Diagnosis Problem (CRQ Diagnosis Problem) can be defined as follows:

Definition 1 (CRQ Diagnosis Problem): A CRQ Diagnosis Problem (Customer Requirements Diagnosis Problem) is defined as a tuple (R, I) where R={r1, r2, …, rm} is a set of requirements and I={i1, i2, …, in} is an item assortment.

Based on this definition of a CRQ Diagnosis Problem, a CRQ Diagnosis (Customer Requirements Diagnosis) can be defined as follows:

Definition 2 (CRQ Diagnosis): A CRQ Diagnosis (Customer Requirements Diagnosis) for (R, I) is a set d={r1, r2, …, rl} ∧ R, s.t. �[R - d]I ♦ ⇓.

Following the basic principles of Model-Based Diagnosis (MBD), the calculation of diagnoses di ∨ D is based on the determination and resolution of conflict sets. A conflict set can be defined as follows (see, e.g., [Junker, 2004]):

Definition 3 (Minimal Conflict Set CS): A Conflict Set CS is defined as a subset {r1, r2, …, rq} ∧ R, s.t. �[CS]I = ⇓. A conflict set CS is minimal iff there does not exist a conflict set CS' with CS' ∉ CS.

As already mentioned, the requirements ri ∨ R in our working example are inconsistent with the given assortment I of financial services, i.e., there does not exist one financial service in I that completely fulfills the requirements R = {r1, r2, r3, r4}. The conflict sets are CS1:{r1,r2}, CS2:{r1,r4}, CS3:{r2,r3} since �[CS1]I = ⇓, �[CS2]I = ⇓, and �[CS3]I = ⇓. Furthermore, the identified conflict sets are minimal, since there do not exist CS1'∉ CS1, CS2' ∉ CS2, CS3' ∉ CS3 with �[CS1']I = ⇓, �[CS2']I = ⇓, and �[CS3']I = ⇓.

Diagnoses di ∨ D can be calculated by resolving conflicts in requirements. Due to its minimality property, one conflict can be easily resolved by deleting one of the elements from the conflict set. After having deleted at least one element from each of the conflict sets we are able to present a minimal diagnosis. Diagnoses derived from {CS1, CS2, CS3} are D = {d1:{r1,r2}, d2:{r1,r3}, d3:{r2,r4}}. A discussion of the algorithm for calculating diagnoses is given in [Reiter, 1987; Friedrich and Shchekotykhin, 2006]. A personalized version of this algorithm will be presented in Section 4.

After having identified the set of possible minimal diagnoses (D), we have to propose repair actions for each of those diagnoses, i.e., we have to identify possible adaptations to the existing set of requirements such that the user is able to find a solution. The number of repair actions could potentially become very large which makes the identification of acceptable repair actions a very tedious task for the user (see, e.g., [Felfernig et al., 2007; O'Sullivan et al., 2007]).

Alternative repair actions can be derived by querying the item table I with �[attributes(d)](�[R-d]I). This query identifies all possible repair alternatives for a single diagnosis d ∨ D where �[attributes(d)] is a projection and �[R-d]I is a selection of tuples from I which satisfy the criteria in R-d. Executing this query for each of the identified diagnoses produces a complete set of possible repair alternatives. Table 2 depicts the complete set of repair alternatives REP = {rep1, …, rep5} for our working example where �[attributes(d1)](�[R-d1]I) = �[return-rate, runtime](�[r3:accessibility = yes, r4:bluechip = yes]I) = {<return-rate=4.7, runtime=3.5>, <return-rate=4.8, runtime=3.5>, <return-rate=4.3, runtime=3.5>}. Furthermore, �[attributes(d2)](�[R-d2]I) = �[return-rate, accessibility](�[r2:runtime = 3.0, r4:bluechip = yes]I) = {<return-rate=4.2, accessibility=no>} and �[attributes(d3)](�[R-d3]I) = �[runtime,bluechip](�[r1:returnrate>=5.5, r3:accessibility=yes]I) = {<runtime=6.0, bluechip=no>}.

Note that in real-world scenarios (see, e.g., [Felfernig et al., 2007]), the number of potential repairs could become very large and it is crucial to propose representative ones in order to avoid drawing false conclusions [O'Sullivan et al., 2007].

4. Calculating Personalized Repairs

The above repair alternatives would be presented to the customer without taking into account the initially defined set of requirements. Important to be mentioned in this context is the fact that the repair alternatives in our example are at least partially ignoring the originally defined requirements and it is unclear which of those alternatives would be the most interesting for the customer.

In order to systematically reduce the number of repair candidates we need to integrate personalization concepts. Our approach is to identify those repair actions which resemble the original requirements of the customer. In order to derive such repair actions, we exploit the existing item definitions (see Table 1) for identifying alternatives which are near the originally defined requirements in R. 1

From the item data in Table 1 we calculate the n-nearest neighbors (in our case, n = 5), i.e., those entries of the item table which are (most) similar to the given set of requirements in R. In our case, the determination of nearest neighbors is based on a simple similarity metric that calculates the individual similarities between the m given customer requirements in R (in our case m = 4) and the attribute settings in the item table. For the purpose of our example we use the following similarity function sim(R, ij) where R represents a set of requirements and ij is the j th item in I. 2 Furthermore, max(k) denotes the maximum value in the domain of attribute k, and w(k) denotes the importance (weight) of attribute k for the customer - see Formula (1).

1 Alternatively, customer interaction logs (or cases) can be exploited for the personalized recommendation of repair actions.

The similarity between the customer requirements of our working example and item i1 in the item table is calculated as follows: sim(R, i1) = (1-|5.5-4.2|/3.7)*1/4 + (1-|3.03.0|/4)*1/4 + (1-|1-0|/1)*1/4 + (1-|1-1|/1)*1/4 = 0.66. Note that we assume w(1) = 1/4, w(2) = 1/4, w(3) = 1/4, and w(4) = 1/4 (∆w(j) = 1). 3 Using Formula (1) we can determine the n-nearest neighbors which are those n items with the highest similarity to ri ∨ R. The 5-nearest neighbors used in our example are shown in Table 3, the corresponding similarity values between R and ij ∨ I are shown in Table 4.

On the basis of the entries in Table 4, we now show step-bystep how our algorithm (Algorithm 1) calculates a personalized repair. The requirements in R are inconsistent with the nearest neighbors NE = {i1,i2,i3,i5,i7} (i.e., �[R]NE = ⇓). Consequently, our algorithm activates a conflict detection component which returns one conflict set per activation. We determine minimal conflicts using a QuickXPlain [Junker, 2004] type algorithm. For the requirements in R and the items in NE the following conflict sets are derived: CS1:{r1,r2}, CS2:{r1,r4}, CS3:{r2,r3}. Note that the reduction of the considered items from I to NE could change the set of calculated conflicts - in our case the set remains the same.

Let us assume that CS1:{r1,r2} is returned as the first conflict set. A Hitting Set Directed Acyclic Graph (HSDAG) [Reiter

2 Note that different metrics (e.g., similarity, diversity, selection probability) could be applied in this context, for simplicity we only use the nearer-is-better (NIB) similarity. An overview of related metrics can be found, for example, in [Wilson and Martinez, 1997; McSherry 2003].

3 Different approaches are possible for the determination of importance weights, for example, direct specification by the customer or preference learning [Biso et al., 2000].

1987] is now instantiated (see Figure 1) with two outgoing paths from the root: [r1] and [r2]. These paths indicate which elements of the identified conflict set have been used to resolve the conflict. Since it is our goal to identify repairs similar to the original requirements, we have to analyze which repairs are possible after eliminating one element from a conflict set (requirement ri ∨ R). For example, eliminating r1 would allow repairs supported by {i1,i2,i3,i5} since (�[¬r1]NE) = {i1,i2,i3,i5}, furthermore, (�[¬r2]NE) = {i2,i3,i5,i7}. We compute the average similarity value for the first k items (in our case k=3). The first three items in {i2,i3,i5,i7} have a higher average similarity than those in {i1,i2,i3,i5}, therefore we decide to extend the path [r2] to [r2,r1] and [r2,r4].

The most promising paths (candidates) are leading to diagnoses accepting those items in NE that are most similar to the original set of requirements in R. Again, for each of the resulting paths ([r2,r1] and [r2,r4]) we have to analyze which are the supporting items: (�[¬r2,¬r1]NE) = {i2,i3,i5} and (�[¬r2,¬r4]NE) = {i7}. The idea is to follow a best-first regime which expands the most promising candidate paths. Following our best-first strategy, we decide to extend the path [r2,r1]. However, since �[R-{r2,r1}]NE, i.e., �[r3:accessibility=yes, r4:bluechip=yes]NE, results in a non-empty set, {r1,r2} is already a diagnosis (d). This diagnosis directly leads to repairs that are most similar to the original set of customer requirements (the fringe of the HSDAG does not contain any candidate paths with better combinations of repair alternatives). The set of possible repair actions for d can be simply determined by executing the query �[attributes(d)](� [R-d]NE) = �[return-rate, runtime](�[accessibility=yes, bluechip=yes]NE). Executing this query results in the set of repairs {<return-rate=4.7, runtime=3.5>, <returnrate=4.8, runtime=3.5>, <return-rate=4.3, runtime=3.5>}.

Figure 1: Personalized diagnosis d ∨ D calculated using the n-nearest neighbors. d = {r1,r2} is selected as basis for the derivation of personalized repairs

The algorithm for calculating personalized repair alternatives is the following (Algorithm 1 - CRQ Repairs). We keep the description of the algorithm on a level of detail which has been used in the description of the original HSDAG algorithm [Reiter, 1987]. In Algorithm 1, the different paths of the HSDAG are represented as separate elements in the bag structure H which is initiated with ⇓. H stores all paths of the search tree in a best-first fashion, where the currently best path (h) is the one with the most promising potential repair alternatives (those repair alternatives most similar to the original requirements in R). If the theorem prover (TP) call (TP(R-h,NE)) does not detect any further conflicts for the elements in h (isEmpty(CS)), a diagnosis is returned and the corresponding repair alternatives can be calculated with �[attributes(d)](�[R-d]NE). The major role of the theorem prover is to check whether there exists a recommendation for R minus the already resolved conflict set elements in h. If the TP call TP(R-h,NE) returns a nonempty conflict set CS, h is expanded to paths each containing exactly one element of CS (in this case no recommendation could be found). In the case that h is expanded, the original h must be deleted from H (delete(h,H)). Finally, if new elements have been inserted to H, it has to be sorted in order to determine the h with the most nearest repair candidates (SimilaritySort(H,k)). 4 This function calculates a set of supporting items for each hi ∨ H (�[∃(¬rj)]NE, rj ∨ hi) and ranks each hi ∨ H conform to the highest item similarity (see Table 4) in its set of supporting items. 5

Note that the function CRQ-Diagnosis in Algorithm 1 returns exactly one diagnosis d at a time (for which in the following potentially more than one repair is returned by CRQRepairs). Since NE ∧ I, the detected conflict sets could differ for TP(R-h,NE) and TP(R-h,I) and some minimal diagnoses could be detected by CRQ-Diagnosis(R,NE,⇓,k) which are not contained in CRQ-Diagnosis(R,I,⇓,k) 6 .

Algorithm 1 - CRQ-Repairs

• /* R: set of customer requirements
• I: set of items
• n: number of nearest neighbours
• k: k most similar items to be used by SimilaritySort(H,k) */

CRQ-Repairs (R�,I�,n�,k�):Repair Set REP�

1. { NE � GetNearestNeighbors(R,I,n)

CRQ-Diagnosis(R�,NE�,H�,k�): Diagnosis h�

1. { h � first(H)

1. if (isEmpty(CS))

(4)

{return h}

1. else
2. {foreach X in CS:H � H ⇒ {h ⇒ {X}}
3. H � delete(h,H)
4. H � SimilaritySort(H,k)
5. CRQ-Diagnosis(R,NE,H,k)} }

4 Note that the necessary HSDAG pruning is implemented by the functionalities of SimilaritySort(H,k).

5 Many different quality measures are possible in this context. A simple one is the highest average of the k most similar items ij (in our working example k = 3).

6 In this case, Algorithm 1 takes into account all items in I.

5. Evaluation

Although our proposed repair functionalities do not significantly change the design of a recommender user interface, they clearly contribute to a more intelligent behavior of recommender applications and have the potential to trigger increased trust and satisfaction of users. The personalization approach as it is presented in this paper is definitely not restricted to conjunctive query based recommender applications but as well applicable with constraint [Junker, 2004] and configuration technologies [Felfernig et al., 2004].

Performance. Algorithm 1 has been implemented on the basis of the standard hitting set algorithm proposed by [Reiter, 1987]. The algorithm is NP-hard in the general case [Friedrich et al., 1991] but is applicable in interactive recommendation settings (see below). In our implementation, the calculation of minimal conflict sets is based on a QuickXPlain type algorithm [Junker, 2004]. QuickXPlain needs O(2k*log(n/k)+2k) consistency checks (worst case) to compute a minimal conflict set of size k out of n constraints in R. Consistency checks in our implementation are represented as conjunctive queries on I (Hypersonic SQL database). A performance evaluation (time effort depending on the number of calculated diagnoses) clearly shows the applicability of Algorithm 1 for interactive settings. On the basis of a test set of 5000 items with 10 associated properties we can observe the following calculation times for |D| diagnoses (see Table 5). These performance results confirm the results of our previous evaluations of financial service recommender applications.

Empirical evaluation. In order to demonstrate the improvements achieved by our approach we conducted an empirical study. In this study we compared two different algorithms for the calculation of repairs. The first (Type 1) supported repairs based on the algorithm proposed in [Reiter, 1987], where diagnoses and corresponding repair alternatives are ranked according to their cardinality (standard breadth-first search). The second approach (Type 2) supported the calculation of personalized repair actions on the basis of Algorithm 1 (best-first search).

The used item assortment (90 items) has been selected from a dataset of an e-Commerce platform (digital cameras). In the scenario, the study subjects interacted with the recommender in order to identify a pocket-camera that best suits their needs. In the case of inconsistent requirements, subjects were confronted with a list of repair alternatives from which they had to select the most interesting one. N=493 subjects participated in the study. In order to systematically induce conflicts (no recommendation could be found), we filtered out items from the assortment that fulfilled requirements posed by the subject. On an average, 2.63 items (std.dev. 1.68) were filtered out per recommendation session. Subjects were informed about the fact that the item which had been specified was not available and they had to select a repair action from a proposed list of alternatives. With the remaining set a corresponding repair process was triggered. Thus each subject was confronted with a conflict situation where a repair alternative had to be selected. In order to keep the cognitive efforts realistic and acceptable, we set the upper limit of the number of repair actions to 5 in both recommender versions (Type 1 and Type 2).

Our hypothesis was that subjects will select higher ranked repair actions significantly more often if the Type 2 repair algorithm was used. For both recommender versions (Type 1 and Type 2) we measured in each session the normalized distance between the position of the selected repair action and position 1 (position of selected repair / #repair alternatives). On the basis of a two-sample t-test, a significant difference between the two repair approaches in terms of prediction quality can be observed. We detected significant higher deviation values (t-score=4.859, p <0.001) for Type 1 recommenders. The average deviation for Type 1 recommenders was 0.599 (std.dev. 0.279), the value for Type 2 recommenders was significantly lower: 0.474 (std.dev. 0.274). Consequently, the above hypothesis can be confirmed. Furthermore, repair alternatives with the highest ranking (position) have been selected significantly more often in Type 2 recommenders (�2=17.746, p<0.001). The precision (#correctly predicted repair actions / #predicted repair actions) of Type 2 recommenders was 0.551 whereas for Type 1 recommenders the precision was lower: 0.307. Correct prediction is interpreted as ranking a repair on position 1 that has been selected then.

6. Related Work

[Felfernig et al., 2004] have developed concepts for the diagnosis of inconsistent customer requirements in the context of configuration problems. The idea was to apply the concepts of Model-based Diagnosis [Reiter, 1987] (MBD) in order to be able to determine minimal cardinality sets of requirements which have to be changed in order to be able to find a solution - repairs were not supported in this context. In [O'Sullivan et al., 2007] such minimal cardinality sets are called minimal exclusion sets, in [Godfrey, 1997; McSherry, 2004] the complement of such a set is denoted as maximally successful sub-query. The calculation of a diagnosis for inconsistent requirements relies on the existence of minimal conflict sets. Such conflict sets can be determined, for example, on the basis of QuickXPlain [Junker, 2004], a divide-and-conquer algorithm. The approach presented in [Felfernig et al., 2004] follows the standard breadth-first search regime for the calculation of diagnoses [Reiter, 1987]. The major contribution of our paper in this context is the extension of this algorithm with collaborative problem solving concepts. This approach improves the prediction quality for repair alternatives and thus contributes to higherquality recommender user interfaces. [O'Sullivan et al., 2007] introduce the concept of representative explanations. Representative explanations follow the idea of generating diversity in alternative diagnoses - informally, constraints which occur in conflicts should as well somehow be included in diagnoses presented to the user. [Jannach, 2006] introduces the concept of preferred relaxations for conjunctive queries that help to select diagnoses on the basis of predefined utility functions. Compared to those previous approaches, the work presented in this paper first introduces an approach that exploits nearest neighbors concepts for the determination of personalized repair actions. Finally, casebased recommender systems [Burke, 2000] profit from the work presented in this paper since in addition to intelligent case retrieval, personalized and (if needed) minimal diagnoses and repairs can be calculated systematically.

7. Conclusions

In this paper we have introduced an algorithm that calculates personalized (plausible) repairs for inconsistent requirements. The algorithm integrates the concepts of modelbased diagnosis (MBD) with the ideas of collaborative problem solving and thus significantly improves the quality of repairs in terms of prediction accuracy. We have evaluated our approach with a recommender application based on realworld items. The results of the study clearly demonstrate the improvements induced by personalized repair actions. Future work will include the evaluation of different alternative metrics (e.g., similarity, diversity, and selection probability) w.r.t. their impact on diagnosis/repair prediction accuracy.