Personalized Diagnosis for Over-Constrained Problems

1 Introduction

Constraint-based applications such as configurators, recommenders, and scheduling systems support users in complex decision making scenarios. Interacting with constraint-based applications often means to specify a set of requirements (e.g., when interacting with a car configurator, required components such as car type and park distance control), to adapt inconsistent requirements, and to evaluate different alternative solutions. In this paper we focus on situations where the constraint solver is not able to identify a solution and it is difficult for the user (customer) to identify minimal sets of requirements that need to be changed such that a solution for the underlying constraint satisfaction problem (CSP) can be identified. In order to improve the prediction quality of diagnosis algorithms in such contexts, we show how to exploit personalization techniques [Felfernig et al., 2007].

Existing approaches to the determination of diagnoses for inconsistent requirements are primarily focusing on minimalcardinality diagnoses [Felfernig et al., 2004] which are determined on the basis of breadth-first search. In the context of recommender systems [Felfernig et al., 2007] the complement of a diagnosis is denoted as maximally successful sub-query [Godfrey, 1997; McSherry, 2004]. Such a maximally successful subquery contains maximal sets of elements (requirements) that guarantee the identification of a solution, i.e., elements which are not part of the minimal diagnosis. In the context of constraint-based systems [Tsang, 1993] diagnoses are also interpreted as a specific type of explanation [OSullivan et al., 2007].

∗The work presented in this paper has been partially funded by the Austrian Research Promotion Agency (project 827587).

Especially in interactive settings the determination of all diagnoses is infeasible due to unacceptable runtimes of the underlying diagnosis algorithms [Felfernig, IJCAI 2009]. Furthermore, we are not able to guarantee that standard breadth-first search leads us to explanations that are acceptable for the user [OSullivan et al., 2007]. The work of [OSullivan et al., 2007] contributes to the tailoring of diagnoses in a way that makes the identification of acceptable diagnoses easier for the user - [OSullivan et al., 2007] denote this type of diagnosis representative explanations. Representative explanations are diagnosis sets that fulfill the criteria that each element contained in at least one diagnosis is also contained in the set of diagnoses presented to the user. [Felfernig et al., 2009] show how to exploit concepts of collaborative recommendation for improving diagnosis prediction quality - the concepts have been developed for a knowledge-based recommendation environment [Burke, 2000].

On the basis of this existing work, we show how to exploit different recommendation algorithms for the personalized identification of diagnoses. In our approach we exploit these algorithms for guiding best-first search in the construction of Hitting Set Directed Acyclic Graphs (HSDAGs). The major contribution of this paper is the significant improvement of diagnosis prediction quality by the integration of state-of-the-art recommendation approaches (similarity-based, utility-based, probability-based, ensemblebased) with standard model-based diagnosis [Reiter, 1987; DeKleer et al., 1992]. Furthermore, we provide an empirical evaluation on the basis of two configuration datasets.

The remainder of this paper is organized as follows. In Section 2 we introduce a working example from the domain of car configuration. In Section 3 we show how recommendation algorithms can be exploited for personalized modelbased diagnosis. In Section 4 we present the results of evaluations conducted with two datasets. In Section 5 we discuss

2 Working Example

The configuration of cars will serve for illustration purposes throughout this paper. A configuration task can be defined as a constraint satisfaction problem (CSP) [Tsang, 1993]: 1

Definition 1 (Configuration Task). A configuration task can be defined as a CSP (V, D, C). V = {v1, v2, . . . , vn} represents a set of finite domain variables. D = {dom(v1), dom(v2), . . . , dom(vn)} represents a set of variable domains dom(vk) where dom(vk) represents the domain of variable vk. C = CKB ∪ CR where CKB = {c1, c2, . . . , cq} is a set of domain specific constraints (the configuration knowledge base) that restrict the possible combinations of values assigned to the variables in V. CR = {cq+1, cq+2, . . . , ct} is a set of customer requirements also represented as constraints.

A simple example of a configuration task is the following. The variable type represents the car type, pdc is the parc distance control feature, fuel represents the average fuel consumption per 100 kilometers, a skibag supports a convenient ski stowage inside a car, and 4-wheel represents the actuation type (4-wheel supported or not supported). These variables are representing all possible user (customer) requirements. The possible combinations of customer requirements are restricted by CKB which is in our case {c1, c2, c3, c4, c5}. Finally, we assume CR to be {c6, c7, c8, c9, c10}.

• V = {type, fuel, skibag, 4-wheel, pdc}
• D = {dom(type)={city, limo, combi, xdrive}, dom(fuel) = {4l, 6l, 10l}, dom(skibag)={yes, no}, dom(4-wheel)={yes, no}, dom(pdc)= {yes, no}}
• CKB = {c1: 4-wheel = yes ⇒ type = xdrive, c2: skibag = yes ⇒ type ̸= city, c3: fuel = 4l ⇒ type = city, c4: fuel = 6l ⇒ type ̸= xdrive, c5: type = city ⇒ fuel ̸= 10l}
• CR = {c6: 4-wheel = yes, c7: fuel = 6l, c8: type = city, c9: skibag = yes, c10: pdc = yes}

On the basis of this simple example of a configuration task, we can now introduce the definition of a corresponding configuration (solution to a configuration task).

Definition 2 (Configuration). A configuration for a given configuration task (V, D, C) is an instantiation I = {v1=ins1, v2=ins2, . . . , vn=insn} where insk ∈ dom(vk).

A solution (configuration) for a given configuration task is consistent if the assignments in I are consistent with the ⋃ci ∈ C. A solution is complete if all vi ∈ V are instantiated. Finally, a solution is valid if it is consistent and complete.

3 Calculating Personalized Diagnoses

Users do not want and are not able to evaluate large sets of diagnosis alternatives. For this reason we are now introducing alternative approaches that help to systematically reduce the number of diagnosis alternatives. Our goal is to identify diagnoses that are relevant for users and thus keep the process of evaluating and selecting diagnoses as simple as possible. The first approach to reduce the number of diagnoses (which is the only non-personalized one we consider here) is to perform breadth first search which returns minimal cardinality diagnoses first [Reiter, 1987]. In addition to this breadth first search approach we will discuss four approaches to the personalized ranking of diagnoses: similarity-based, utility-based, probability-based, and ensemble-based search.

1 Note that the presented concepts are applicable to different knowledge representations such as SAT solving [Marques-Silva and Sakallah, 1996] and description logics [Friedrich and Shchekotykhin, 2005].

Cardinality-based diagnosis (not personalized). Our example configuration task (car configuration) is defined in a way which does not allow the calculation of a solution, for example, the requirements c6 and c8 are incompatible. For identifying minimal sets of constraints which have to be deleted from the given set of customer requirements we use the concepts of Model-Based Diagnosis (MBD) [Reiter, 1987; DeKleer et al., 1992]. MBD diagnosis exploits the description of a system - in our case the configuration knowledge base CKB which describes a set of possible configurations (solutions). If we detect that the behavior of the system conflicts with its intended behavior (at least one solution can be identified), the task of a diagnosis component is to determine components (constraints) in the given set of customer requirements (CR) which, when assumed to function abnormally, sufficiently explain the discrepancy between actual and expected system behavior. An identified minimal diagnosis is a minimal set of faulty constraints that need to be relaxed or deleted in order to be able to calculate a configuration.

Assuming the existence of CKB = {c1, c2, ..., cq} and CR = {cq+1, cq+2, ..., ct} which is inconsistent with CKB, breadth first search based diagnosis algorithms [Reiter, 1987; DeKleer et al., 1992] determine minimal diagnoses DIAGS = {∆1, ∆2, ..., ∆k} in the order of their cardinality such that ∀∆i ∈ DIAGS : CKB ∪ (CR - ∆i) is consistent. A User Requirements Diagnosis Problem (UR Diagnosis Problem) can be defined as follows:

Definition 3 (User Requirements (UR) Diagnosis Problem): A UR Diagnosis Problem is defined as a tuple (CKB,CR); CKB represents the constraints of the configuration knowledge base and CR is a set of user requirements.

Based on the definition of a UR Diagnosis Problem, a UR Diagnosis can be defined as follows:

Definition 4 (UR Diagnosis): A User Requirements Diagnosis (UR Diagnosis) for (CKB,CR) is a set of constraints ∆ ⊆ CR such that CKB ∪ (CR -∆) is consistent. A diagnosis ∆ is minimal iff there does not exist a diagnosis ∆′ ⊂ ∆ s.t. CKB ∪ (CR -∆′ ) is consistent.

Following the basic principles of Model-Based Diagnosis (MBD) [Reiter, 1987; DeKleer et al., 1992], the calculation of diagnoses is based on the identification and resolution of conflict sets. A conflict set in CR can be defined as follows:

Definition 5 (UR Conflict Set): A User Requirements Conflict Set (UR Conflict Set) is defined as CS ⊆ CR s.t. CS ∪ CKB is inconsistent. CS is minimal iff there does not exist a conflict set CS' with CS' ⊂ CS.

In our working configuration example, CR = {c6, .., c10} is inconsistent with CKB = {c1, .., c5}, i.e., there does not exist a configuration (solution) that completely fulfills the requirements in CR. The minimal conflict sets are CS1 = {c6, c7}, CS2 = {c8, c9}, and CS3 = {c6, c8} since each of these conflict sets is inconsistent with CKB and there do not exist conflict sets CS1', CS2', and CS3' with CS1' ⊂ CS1, CS2' ⊂ CS2, and CS3' ⊂ CS3.

In MBD [Reiter, 1987; DeKleer et al., 1992], the standard algorithm for determining minimal diagnoses is the hitting set directed acyclic graph (HSDAG). UR diagnoses ∆i ∈ DIAGS are determined by conflict resolution in the set of requirements CR. Due to its minimality property, one conflict can simple be resolved by deleting one of the elements from the conflict set. After one element has been retracted from each of the given conflict sets, we are able to present a corresponding diagnosis. The original HSDAG approach employs breadth-first search. In our example, the diagnoses derived from CS1, CS2, and CS3 are DIAGS = {∆1 : {c6, c8},∆2 : {c6, c9},∆3 : {c7, c8}}.

The HSDAG construction for our working example is shown in Figure 1. In our implementation we employ the QUICKXPLAIN conflict detection algorithm which has been developed by [Junker, 2004]. Following a strict breadth first search regime, we resolve the first conflict set (CS1) by checking whether one of its elements already represents a diagnosis. Both alternatives (c6 and c7) do not lead to a diagnosis due to the inconsistency of (CR - {c6}) ∪ CKB and (CR - {c7}) ∪ CKB. The next minimal conflict set returned by QUICKXPLAIN is CS2 = {c8, c9}. CR - ({c6} ∪ {c8})) ∪ CKB allows the determination of a solution; consequently we have identified the first minimal diagnosis: ∆1 = {c6, c8}.

Figure 1: Cardinality-based diagnosis (breadth-first): the diagnoses ranking is {∆1,∆2,∆3}. The expression [{c6, c8} ×] denotes containment, i.e., the node can be closed.

Similarity-based diagnosis. The similarity-based ranking of diagnoses is based on the idea of preferring minimal diagnoses which lead to solutions (configurations) that resemble the original set of requirements as much as possible. We exploit the information contained in already existing configurations (see, e.g., Table 1). For each configuration contained in this table we determine its similarity with the given set of requirements - the similarity values of our working example are depicted in Table 3. The similarity-based determination of diagnoses is based on Algorithm 1 - a generic algorithm (PDIAG) which is applicable with different node expansion strategies (in our case, cardinality, similarity, utility, and probability-based search). This algorithm simulates the construction of a hitting set directed acyclic graph (HSDAG) [Reiter, 1987]. The function deleteall(∆′ ,H) deletes ∆′ and all supersets of ∆′ fromH, delete(∆′ ,H) removes only ∆′ .

We determine similarity values based on three different

Algorithm 1 PDIAG(CR, CKB, crit, n): ∆

{PDIAG returns ≤ n(n ≥ 0) personalized minimal diagnoses ∆ (bag) for a given set of inconsistent user require-

ments (CR) using the preference criteria defined in crit.} {CKB: configuration knowledge base} {H: paths of the diagnosis search tree} {CS: min. conflict set returned by theorem prover (TP)}

∆ = ∅; H = ∅;

repeat

∆′ ← f irst(H); CS ← T P ((CR - ∆′ ) ∪ CKB); if isEmpty(CS) then ∆ ← ∆ ∪ ∆′ ; H ← deleteall(∆′ , H); n ← n - 1; else for all X in CS do H ← H ∪ {∆′ ∪ {X}}; end for H ← delete(∆′ , H); H ← sort(H, crit); end if until (H = ∅ or n = 0);

return ∆;

Figure 2: Similarity-based diagnosis: the diagnoses order is {∆2,∆3,∆1}. The term ¬c6 → 0.6 denotes the fact that the highest similarity between CR and the tuples of the sessions si in Table 1 consistent with ¬c6 is 0.6 (in our case i = 1).

attribute-level similarity measures which are predominantly applied in knowledge-based recommender applications [McSherry, 2004]. The attribute-level measures determine the similarity of each attribute value ai of session sk and the corresponding requirement ci (e.g., the similarity between the attribute type of session s1 and the corresponding requirement c8). Depending on the characteristics of the attribute, one of the following attribute-level similarity measures has to be selected (see Formulae 1-3): More-Is-Better (MIB), LessIs-Better (LIB) or Nearer-Is-Better (NIB) [McSherry, 2004]. The overall similiarity between c = CR and a tuple a in Table 1 is defined by Formula 4. The similarity between CR (c) and a tuple a of user interaction data is represented by the sum of weighted (w(ci) - see Table 2) attribute level similarities. 2

For attributes such as fuel, the lower the value the more satisfied the user is (LIB). When the user specifies a certain car type (no intrinsic value scale), we suppose the most similar is the preferred one. In such cases, the nearer-is-better (NIB) similarity measure is used. 3

2 Our preference (w(ci)) determination method is typically based on multi attribute utility theory [Winterfeldt and Edwards, 1986].

Utility-based diagnosis. Utility-based diagnosis prefers minimal diagnoses that are predominantly composed of requirements which are of low importance (a low w(ci) value) for the customer (user). Based on the concepts of multi attribute utility theory [Winterfeldt and Edwards, 1986], individual importance values (see Table 2) of user requirements that are part of a diagnosis are summed up - the lower this sum, the lower is the overall importance of the parameters contained in the diagnosis and the higher is the ranking of the corresponding diagnosis. The function utility(C ⊆ CR) returns a utility value for each set C which is a subset of CR (see Formula 5). Note that in the case of our working example the diagnosis ranking on the basis of the utility-based approach is the same as with the discussed similarity-based approach. The corresponding results are depicted in Figure 3.

3 For a detailed discussion of different types of similarity measures see, for example, [McSherry, 2004]. In Formulae 1 - 3, val(ci) denotes the value of user requirement ci, min(ai) denotes the minimal possible value of configuration attribute ai, and max(ai) denotes the maximal possible value of ai.

Probability-based diagnosis. Probability-based best first search for diagnoses prefers minimal diagnoses with a high probability of being selected by the user. For the determination of diagnosis probabilities we rely on joint probabilities that a particular diagnosis (or part of a diagnosis) will be selected by the user. Formula 6 is used for determining the joint probabilities for a given set of constraints C ⊆ CR. Figure 4 shows the application of this approach in the context of our working example. The probabilities are determined on the basis of user-selected diagnoses (see Table 4). The assumption of independence of failure made here is one widely made in model-based diagnosis [DeKleer, 1990].

Ensemble-based diagnosis. In the case of cardinalitybased, similarity-based, utility-based, and probability-based diagnosis search, diagnosis predictions (the rankings) are based on a single hypothesis. The idea of ensemble-based diagnosis search is to exploit a set of hypotheses (an ensemble) for making the prediction. For the ranking of diagnoses we apply a basic majority voting approach (see Table 5); assuming that the errors made by each individual prediction mechanism are not the same, ensemble-based methods can be very useful for improving the prediction quality (see Section 4). The determination of ensemble-based diagnoses is sketched in Algorithm 2 (ENSPDIAG); this algorithm activates PDIAG with each individual expansion criteria, collects the results, and determines a set of ensemble-based diagnoses. We do not

Figure 3: Utility-based diagnosis search: the order of identified diagnoses is {∆2,∆3,∆1}.

Figure 4: Probability-based diagnosis: the order of identified diagnoses is {∆3,∆1,∆2}.

provide the details of the function CreateEnsembleDiagnoses and refer to Table 5 which sketches the aggregation approach. Note that - since ENSPDIAG activates a HSDAG construction several times (in the for-loop) - conflicts determined with criteria X can be reused in follow-up PDIAG activations.

Algorithm 2 ENSPDIAG(CR, CKB, Crit, n): ∆

{ENSPDIAG returns ≤ n(n ≥ 0) personalized minimal diagnoses ∆ (bag) for a given set of inconsistent user requirements (CR) using the ensemble-based approach.}

{CKB: configuration knowledge base} {Crit: set of expansion criteria (card, sim, utility, prob)} {Γ: collection of diagnosis sets (bags)} for all X in Crit do Γ←Γ ∪ PDIAG(CR, CKB, X, n); end for ∆ ← CreateEnsembleDiagnoses(Γ); return ∆;

4 Evaluation

Prediction Quality. We now demonstrate the improvements achieved by the application of our personalized diagnosis approaches on the basis of an empirical study with two datasets.

Dataset 1: Computer Configuration. This dataset has been composed on the basis of an online user experiment conducted at the Graz University of Technology. 415 subjects participated in the study (82,4% male and 17,6% female). Participants had to define their requirements (CR) regarding a set of 12 computer properties. The task of the subjects was to define their product requirements (including requirement importance). After having completed the requirement specification phase, each participant was informed about the fact that no solution could be found. The configurator then presented a list of max. 50 different repair configurations (solution alternatives) - at least one property of each configuration was inconsistent with CR. The configurations were extracted from www.dell.at. The ranking of the solution alternatives was randomized and the subjects were enabled to navigate in order to evaluate the solution alternatives regarding criteria such as price, harddisk size or number of fulfilled requirements. The subjects then had to select one out of the presented repair configurations that appeared to be the most acceptable one for them. Since no solution has been made available for CR (only configurations inconsistent with CR were shown) we could calculate conflicts (in CR induced by the repair configurations) and the corresponding diagnoses with our diagnosis techniques (the average number of diagnoses per CR was: 5.32 (std.dev. 1.67)). Precision (see Formula 7) was measured then in terms of how often a repair configuration selected by the participant was consistent with one of the top-N ranked diagnoses.

Dataset 2: Financial Services. This dataset belongs to a financial service recommender. In this application, inconsistent states and selected diagnoses had been recorded (N=1.703 sessions out of which in 418 sessions a diagnosis process had been activated - average number of diagnoses per CR: 20.42 (std.dev. 4.51)). In the case of the financial services configurator, the importance of a user requirement (w(ci)) was (is) determined on the basis of multi attribute utility theory [Winterfeldt and Edwards, 1986].

Based on the two datasets (computer and financial services) we evaluated our diagnosis approaches w.r.t. their precision (Formula 7). The idea of this precision measure is to figure out how often a diagnosis that corresponds to a diagnosis selected by the user or leads to a repair configuration selected by a user is among the top-n (N) ranked diagnoses.

As can be seen in Table 6 and Table 7, in our two empirical settings the ensemble-based approach (majority voting) outperforms the other prediction methods in terms of precision. Breadth first search has the lowest precision. Based on a two-sample t-test we tried to figure out whether there exist statistically significant differences between the diagnosis approaches in terms of their mean square error ( 1n ∑ni=1 |(1 - diagpos(i))2 |) where diagpos denotes the position of the diagnosis selected by the user and n=#(diagnosis processes started). In both datasets we detected a significant difference between breadth-first search and all other approaches (computer: p = 2.2e-16 , financial services: p < 0.05). Furthermore, there is a significant difference between the ensemblebased and the other personalized approaches in the case of the computer dataset (p = 7.55e-6 ); in the case of the financial services dataset we can observe a tendency (p < 0.07).

Performance. The PDIAG algorithm (Algorithm 1) has been implemented on the basis of the standard hitting set algorithm introduced in [Reiter, 1987] - it is NP-hard in the general case but is applicable for interactive configuration settings (see the following evaluation). In PDIAG minimal conflict sets are determined on the basis of QUICKXPLAIN [Junker, 2004] - the worst case complexity in terms of the number of consistency checks of QUICKXPLAIN is O(2k ∗ log( nk ) + 2k) where k represents the size of the minimal conflict set and n is the number of constraints.

We conducted a performance analysis in order to show the applicability of our approach (see Table 8). The tests have been executed on a standard desktop computer (Intel R©Core TM 2 Quad CPU Q9400 CPU with 2.66GHz and 2GB RAM). In addition to our datasets we evaluated our diagnosis algorithms with the Renault configuration knowledge base part of the configuration benchmark suite. 4 Even for complex settings (Renault benchmark) we can expect a performance acceptable for interactive settings. Note that the determination of minimal cardinality diagnoses typically takes less time due to the fact that fewer conflict sets have to be determined on an average, however, in many settings minimal cardinality diagnoses are not the preferred ones.

Monotonicity Assumption. Note that the PDIAG algorithm is able to determine the best n (preferred) diagnoses under the assumption that the underlying expansion strategy fulfills the monotonicity property of best-first search ([Russell and Norvig, 2003]) which holds for the strategies we discussed in this paper: the cardinality increases, similarity, utility, and probability decrease with a growing expansion level of the HSDAG [Reiter, 1987].

5 RelatedWork

The increasing size and complexity of knowledge bases led to the application of model-based diagnosis [Reiter, 1987; DeKleer et al., 1992] to automated knowledge base debugging [Felfernig et al., 2004]. The contribution of [Felfernig et al., 2004] has a special relationship to the concepts presented in this paper: [Felfernig et al., 2004] identify faulty constraints in configuration knowledge bases, furthermore, they present a first approach to the identification of minimal sets of faulty user requirements (following a breadthfirst search regime). An approach to personalize diagnosis has been presented in [Junker, 1994] where diagnoses are determined on the basis of a HSDAG [Reiter, 1987] given a defined preferred ordering on assumptions. In a similar line, [DeKleer, 1990] show the application of probability estimates for the identification of the most relevant diagnosis. The work presented in this paper extends existing research results by demonstrating the application of recommendation algorithms for improving the prediction quality of diagnosis algorithms. In order to identify the relevant diagnoses, we have to include intelligent estimates about preferences which is one of the major contributions of this paper. One such approach to determine personalized diagnoses for inconsistent requirements has been proposed for knowledge-based recommendation scenarios [Felfernig et al., 2009] where repair proposals for inconsistent features requests are generated on the basis of the similarity between the feature requests and the items in a product table. [OSullivan et al., 2007] introduce minimal exclusion sets. On the basis of such sets, [OSullivan et al., 2007] discuss the concept of representative explanations which can be interpreted as sets of minimal diagnoses covering all constraints part of at least one of the existing diagnoses - this is an approach to take into account diversity in diagnosis recommendation and thus also an important aspect for our future work. In contrast to the work presented in this paper, the approach of [OSullivan et al., 2007] does not explicitly take into account the preferences of the current user (customer). In knowledge-based recommendation maximally successful sub-queries [Godfrey, 1997; McSherry, 2004] represent the complement to minimal diagnoses [DeKleer et al., 1992; Reiter, 1987]. Note that our work relies on the assumption of an open configuration (tradeoff exploration) based scenario where the user is free to specify preferred requirements - the configuration system then provides the corresponding feedback in terms of diagnoses.

4 www.itu.dk/research/cla/externals/clib.

6 Conclusions

We have introduced techniques that help to calculate personalized diagnoses. In this context we proposed different personalization strategies which can help to significantly increase prediction quality. Within the scope of an empirical study we compared five search strategies (cardinalitybased, similarity-based, utility-based, probability-based, and ensemble-based). The results show clear advantages of personalized diagnosis calculation in terms of precision. Thus the results presented in this paper provide a solid basis for improving existing constraint-based applications in terms of a lower number of needed interaction cycles for the user and a lower number of needed diagnosis calculations.