Increasing Dialogue Efficiency in Case-Based Reasoning Without Loss of Solution Quality

1 Introduction

In conversational case-based reasoning (CCBR), a query is incrementally elicited in an interactive dialogue with the user [Aha et a!. , 2001]. Attribute-selection strategies that aim to minimize the length of such dialogues have recently attracted much research interest [Doyle and Cunningham, 2000; Kohlmaier eta!., 2001; McSherry, 2001; Schmitt et a!., 2002]. Potential benefits include avoiding frustration for the user, reducing network traffic in e-commerce domains, and simplifying explanations of how conclusions were reached [Breslow and Aha, 1997; Doyle and Cunningham, 2000]. While our focus in this paper is on incremental query elicitation in recommender systems, it is worth noting that the ability to solve problems by asking a small number of questions has been a major factor in the success of help­ desk applications ofCBR [Aha eta!., 2001; Watson, 1997].

An advantage of information gain [Quinlan, 1986] as a basis for attribute selection is that it tends to produce small decision trees, thus helping to reduce the length of problem­ solving dialogues [Doyle and Cunningham, 2000; McSherry, 2001]. However, concerns about its suitability in e-commerce domains include the fact that no use is made of the system's similarity knowledge [Kohlmaier eta!., 2001 ;

Schmitt et a!., 2002). Any importance weights associated with the case attributes are also ignored. As a result, it is possible for a case to be recommended simply because no other case has the preferred value for an attribute of low importance, even if its values for other attributes are unacceptable to the user.

Kohlmaier et a!. [200 1] propose a similarity-based approach to attribute selection in which the best attribute is the one that maximizes the expected variance of the similarities of candidate cases. In domains in which cases are indexed by different features, another alternative to information gain is to rank questions in decreasing order of their frequency in the most similar cases [Aha eta!. , 2001].

To address the trade-off between dialogue efficiency and solution quality, a CBR system must also be capable of recognizing when the dialogue can be terminated while minimizing the risk of commitment to a sub-optimal solution. Existing approaches include terminating the dialogue when the similarity of any case reaches a predefined threshold, or the achievable information gain is less than a predefined level, or the set of candidate cases has been reduced to a manageable size [Aha eta!., 2001 ; Doyle and Cunningham, 2000; Kohlmaier eta!., 2001].

However, a limitation of these approaches is that there is no guarantee that a better solution would not be found if the dialogue were allowed to continue. Whether it is possible to identify more reliable criteria for termination of problem­ solving dialogues is an issue that has received little attention, if any, in CBR research.

In Section 2, we examine the trade-off between dialogue efficiency and solution quality in recommender systems. In Section 3, we present empirical techniques for identifying cases that can never emerge as the "best" case and can thus be eliminated. In Section 4, we identify necessary and sufficient conditions for the dialogue to be terminated without loss of solution quality. In Section 5, we evaluate a number of attribute-selection strategies in terms of dialogue efficiency given the requirement that there must be no loss of solution quality. Our conclusions are presented in Section 6.

2 CCBR in Product Recommendation

A generic algorithm for CCBR in product recommendation is shown in Figure 1. In this context, the elicited query, or partial query, represents the preferences of the user with respect to the attributes of the available products. At each stage of the recommendation dialogue, the system selects the next most useful attribute, asks the user for the preferred value of this attribute, and retrieves the case (or product) that is most similar to the query thus far elicited. The dialogue continues until the termination criteria are satisfied, or until no further attributes remain. At this point, the case that is most similar to the current query is presented to the user as the recommended case.

algorithm CCBR begin end Q+-0 repeat select the next most useful attribute a ask the user for the preferred value v of a Q +- Q u {a= v} retrieve the case C that is most similar to Q until termination criteria are satisfied recommend C

2.1 Similarity Measures

The similarity of a given case C to a query Q over a set of case attributes A is typically defined as:

where for each a E A, Wa is a numeric weight representing the importance of a, and sima(C, Q) is a measure of the similarity of 7t 0 (C), the value of a in C, to 1ta(Q), the preferred value of a. As usual in practice, we assume that for all a E A, 0 :S sima(x, y) :S 1 and sima(x, y) = 1 if and only ifx = y. Often in practice, Sim(C, Q) is divided by I W 0 to aeA

give an overall similarity score between 0 and 1, though this has no affect on the ranking of the retrieved cases. We will say that Sim is a regular similarity measure if for each a E A, the distance measure da(x, y) = 1 - sima(x, y) satisfies the triangle inequality: da(x, z) :S da(x, y) + da(y, z) for all x, y, z.

At each stage of the CCBR process, retrieval is based on an incomplete query Q in which preferred values are specified for a subset AQ of the case attributes A. The similarity of a given case C to an incomplete query Q is:

In practice, the full-length query Q* that represents the preferences of the user with respect to all the case attributes may never be known, and is only one of the many possible completions of Q in the sense of the following definition.

Definition 1 Given an incomplete query Q, we say that a full-length query Q+ is a completion of Q if 1ta(Q) = 1ta(Q) for all a E AQ.

Proposition 1 If Q is an incomplete query, then for any case C and completion Q+ of Q,

2.2 Measures of Retrieval Performance

Often in recommender systems, cases other than those that are maximally similar to a target query are presented as alternatives that the user may wish to consider [e.g. McGinty and Smyth, 2002]. However, in measuring retrieval performance, we assume that the retrieval set for a given query Q is the set of cases C for which Sim(C, Q) is maximal; that is, no case is more similar to Q.

Definition 2 Given a query Q, we define the retrieval set for Q to be:

Often in practice, rs(Q) contains a single case; if not, we assume that the user is shown all cases that are maximally similar to her final query. A simple measure of dialogue efficiency is the number of questions, on average, that the user is asked before a recommendation is made. We measure precision and recall for an incomplete query Q relative to the full-length query Q* that represents the preferences of the user with respect to all the case attributes.

Definition 3 Given an incomplete query Q, we define:

2.3 Similarity Thresholds

We now use an example recommender system in the PC domain to illustrate the trade-off between dialogue efficiency and solution quality in CCBR with termination based on similarity thresholds. The case library contains the descriptions of 120 personal computers [McGinty and Smyth, 2002]. The attributes in the case library and weights assigned to them in our experiments are type (8), price (7), manufacturer (6), processor (5), speed (4), monitor size (3), memory (2), and hard disk capacity (1). In this initial experiment, attributes are selected in decreasing order of their importance weights and the dialogue is terminated when the similarity of any case reaches a predefined threshold.

We use a leave-one-out approach in which each case is temporarily removed from the case library and used to represent the preferences of the user in a simulated recommendation dialogue. We measure dialogue length as the percentage of the 8 possible questions the user is asked before the dialogue is terminated. Average dialogue length, precision and recall over all simulated dialogues are shown in Figure 2 for similarity thresholds in the range from 0.4 to I. In this case library, there is never more than a single case in the retrieval set for the full-length query that provides the baseline for our evaluation of retrieval performance. It follows that for each threshold, recall is the percentage of dialogues in which this "best" case is recommended.

The similarity threshold of 0.7 can be seen to have reduced average dialogue length by almost 50%. This equates to about 4 out of 8 questions, on average, being asked before a recommendation is made. However, the trade-off is a reduction of more than 20% in both precision and recall. This means that the best case is recommended in less than 80% of dialogues. As precision is less than recall for the 0. 7 threshold, there are also occasions when the system recommends the best case along with one or more other cases that are equally similar to the final query. It is also worth noting that even a threshold of 0.9, though providing a reduction in dialogue length of 17%, does not ensure that the best case is always recommended.

2.4 When Can the Dialogue be Safely Terminated?

The potentially damaging effects of similarity thresholds on solution quality highlight the need for more reliable criteria for terminating CCBR dialogues. An incomplete query Q gives perfect precision and recall if and only if rs(Q) = rs(Q*), but the problem is that Q* is unknown. One can imagine an approach to CCBR that relies on exhaustive search to determine when the dialogue can be safely terminated; that is, in the certain knowledge that there can be no loss of precision or recall. The dialogue would be terminated only if all possible completions Q+ of the current query Q yielded the same retrieval set as Q. However, this approach is unfeasible in practice as the number of possible completions of a given query is often very large.

In Section 4, we identify criteria for safely terminating the dialogue that require minimal computational effort in comparison with exhaustive search. The approach is based on the concept of case dominance that we now introduce.

Definition 4 We say that a given case C2 is dominated by another case C1 with respect to an incomplete query Q if Sim(C2, Q) < Sim(C~> Q) and Sim(C2, Q+) < Sim(C~> Q}for all possible completions Q+ ofQ.

The importance of case dominance can easily be seen. Any case that is dominated with respect to the current query can be eliminated as it can never emerge as the best case regardless of the preferences of the user with respect to the remaining attributes. In the following section, we present empirical techniques for identifying dominated cases that can easily be applied in practice.

3 Identifying Dominated Cases

We now present 3 alternative criteria for identifying cases that are dominated with respect to an incomplete query. We will refer to the dominance criteria identified in Theorems I, 2 and 3 as DCl, DC2 and DC3 respectively. DCl and DC2 are sufficient but not necessary conditions for a given case to be dominated by another case, while DC3 is both a necessary and a sufficient condition. DC 1 and DC2 have the advantage of not relying on the triangle inequality, but only DC3 is guaranteed to detect all dominance relationships.

Theorem 1 A given case C2 is dominated by another case cl with respect to an incomplete query Q if:

A limitation of DCl is that it fails to recognize that the similarity of the more similar case C1 is a moving target for the less similar case C2, and that the latter may be dominated even if it can equal or exceed the current similarity of C1· For example, if C1 and C2 have the same values for one of the remaining attributes, then any increase in similarity gained by c2 with respect to this attribute is also gained by C1· Our second dominance criterion, DC2, ignores attributes for which cl and c2 have the same values, thus making it less susceptible to this problem.

Theorem 2 A given case C2 is dominated by another case cl with respect to an incomplete query Q if:

Proof If A2 = {a E A - AQ: na(CJ) = 1ta(C2)}, then for any completion Q+ of Q:

However, the moving target problem is only partially addressed by disregarding attributes for which C1 and C2 have the same values. Any increase in similarity gained by c2 with respect to an attribute for which they have different values may also be gained in equal or greater measure by C1· Our third dominance criterion addresses this issue by taking account of the similarity between C1 and C2 with respect to each of the remaining attributes.

Lemma 1 If Sim is a regular similarity measure, then for any cases C1, C2, query Q, and a E A:

Proof By the triangle inequality, 1 - sima(C1, sim 0 (C1, Cz) + 1 - sima(Cz, Q). The required easily follows. Q) ::; 1 - inequality 0

Theorem 3 If Sim is a regular similarity measure, then a given case C2 is dominated by another case C1 with respect to an incomplete query Q if and only if

Proof If the latter condition holds then it follows from Lemma 1 that for any completion Q+ of Q:

So C2 is dominated by C1 as required. It remains to show that if:

then C2 is not dominated by C1. Let Q+ be the completion of Q such that 1ta(Q} = 1ta( C2) for all a E A - AQ. It can be seen that sim 0 (Cz, Q+) = 1 and sima(CJ. Q+) = sima(CJ. C2) for all a E A -AQ, and so:

Figure 3 shows the numbers of dominated cases, on average, according to DCl, DC2 and DC3 after each question in simulated dialogues based on the PC case library [McGinty and Smyth, 2002]. The experimental setup is the same here as in Section 2.3, except that the dialogue is allowed to continue until no further attributes remain.

The results clearly show the inferiority of DC 1 as a basis for detecting dominance relationships. It fails to detect any dominance relationships until three questions have been asked, while it can be seen from the results for DC3 that more than 70% of cases, on average, are in fact dominated after the second question. The results also show DC2 to be much more effective in detecting dominance relationships than DC1 , though unable to compete with DC3.

4 Safely Terminating the Dialogue

We now identify conditions in which a recommender system dialogue can be terminated without loss of precision or recall. We also show that these conditions must be satisfied in order for the dialogue to be safely terminated. That is, termination on the basis of any other criterion runs the risk of some loss of solution quality.

Lemma 2 If Q is an incomplete query such that two cases C1, C2 E rs(Q) have the same values for all a E A - AQ, then Sim(CJ. Q+) = Sim(C2, Q+) for any completion Q+ of Q. Moreover, any case C3 that is dominated by C1 is also dominated by C2·

Proof It easily follows from Proposition 1 that Sim(C1, Q+) = Sim(C2, Q+) for any completion Q+ of Q. If C 3 is dominated by C~> then Sim(C3, Q) < Sim(C~> Q) = Sim(C2, Q) and for any completion Q+ of Q, Sim(C3, Q+) < Sim(CI> Q+) = Sim(C2, Q+). So C3 is dominated by C2 as required.

Theorem 4 The dialogue can be safely terminated if and only if the current query Q is such that: (a) all cases in rs(Q) have the same values for all a E A - AQ and (b) for all cl E rs(Q) and c2 (<: rs(Q). cl dominates C2.

Proof If (a) and (b) are true, then for any completion Q+ of Q, all cases in rs(Q) are equally similar to Q+ by Lemma 2. On the other hand, if C3 fi!: rs(Q), then (b) ensures that C3 is less similar to Q+ than any case in rs(Q). It follows that rs(Q+) = rs(Q) for all completions Q+ of Q, and so the dialogue can be safely terminated.

If (a) is not true, then there exist C), c2 E rs(Q) and a 0 E A- AQ such that 1tao(CJ) ::1: 1tao(C2). It follows that if Q+ is the completion of Q such that 1ta(Q+) = 1ta(C1) for all a E A- AQ, then sima'(C2, Q) < sima"(CI> Q+) = 1, and so Sim(C2, Q) < Sim(C~> Q+). Thus C2 fi!: rs(Q). It follows that (a) is a necessary condition for the dialogue to be safely terminated.

If (b) is not true, then there exist C1 E rs(Q) and C2 fi!: rs(Q) such that C2 is not dominated by C1. As Sim(C~> Q) > Sim(C2, Q), there must be a possible completion Q+ of Q such that Sim(C2, Q) 2: Sim(CI> Q+). It follows that rs(Q+) ::1: rs(Q), so the dialogue cannot be safely terminated. Thus (b) is also a necessary condition for the dialogue to be safely terminated. 0

The cost of testing condition (a) of Theorem 4 increases only linearly with the size of the retrieval set. At first sight, condition (b) may seem expensive to test, particularly in the early stages of query elicitation when lrs(Q)I may be large. However, it can be seen from Lemma 2 that if(a) is true and C1 is any case selected from rs(Q), then (b) is true if and only if C1 dominates C2 for all C2 fi!: rs(Q). Since (b) need only be tested if (a) is true, this reduces the cost of testing whether or not the dialogue can be safely terminated to one that increases only linearly with the size of the case library.

It is worth noting that failure of the underlying similarity measure to respect the triangle inequality does not affect the ability of a CCBR algorithm that uses the termination criteria presented in Theorem 4 to provide perfect precision and recall. However, the use ofDC2 (which does not rely on the triangle inequality) as the dominance criterion is likely to affect retrieval performance in terms of dialogue efficiency. In the rest of this paper, we assume that the underlying similarity measure is regular, thus permitting the use ofDC3 in the identification of dominance relationships.

5 Attribute-Selection Strategies

We now examine the effects on dialogue efficiency of four approaches to attribute selection in CCBR algorithms that use the termination criteria we have shown to be essential to ensure perfect precision and recall. Two of our algorithms are goal driven in that attribute selection is based on the hypothesis that the preferred values of the remaining attributes are the values in a target case C, initially selected at random and revised if necessary as the user's preferences are elicited. No change is needed as long as C, E rs(Q), which means that no case is more similar to the current query Q than the target case. If C, fi!: rs(Q), then the target case is replaced by another case selected at random from rs(Q).

The algorithms compared in our evaluation are:

CCBR I: Select attributes in random order

CCBR2: Select attributes in order of decreasing importance

CCBR3: Select the attribute that maximizes the similarity variance of cases not currently dominated by the target case

CCBR4: Select the attribute that maximizes the number of cases dominated by the target case

Attribute selection in CCBR3 is adapted from the approach proposed by Kohlmaier et al. [2001] . However, an expected similarity variance over all values of each attribute is not computed in our approach. Instead, the impact on similarity variance of each attribute is evaluated only for its value in the target case; this greatly reduces the computational effort involved in attribute selection.

Our experimental method is designed to compare average dialogue length for each attribute-selection strategy with the optimal dialogue length that can be achieved by any CCBR algorithm that always gives perfect precision and recall. Any such algorithm, like the algorithms in our evaluation, must use the termination criteria identified in Theorem 4. As in our previous experiments, each case is temporarily removed from the case library and used to represent the preferences of the user. To determine the optimal dialogue length for a left-out case, we simulate all possible dialogues based on that case; that is, with the available attributes selected in every possible order. The optimal dialogue length is the minimum number of questions asked over all such dialogues. For each left-out case, we also record the dialogue length for each of our attribute-selection strategies.

For each strategy, Figure 4 shows the maximum, minimum, and average number of questions asked over all simulated dialogues. Similar statistics are shown for the optimal dialogues determined as described above. CCBR4 gave the best performance, reducing the number of questions asked by up to 63% and by 35% on average relative to a full-length query. Its average dialogue length of 5.2 is only 4% higher than the lowest possible average that can be achieved by any CCBR algorithm that guarantees perfect precision and recall.

Attribute selection based on similarity variance (CCBR3) also performed well on this case library, with an average dialogue length of 5.4 compared with 7.4 for the random strategy (CCBRl). With an average dialogue length of 5.8, selecting attributes in order of decreasing importance (CCBR2) was also more effective in reducing average dialogue length than the random strategy.

The case library used in our final experiment (www.ai­ cbr.org) contains over 1,000 holidays and their descriptions in terms of 8 attributes such as price, region, duration, and season. The experimental setup is the same as in our previous experiment except that we do not attempt to determine the optimal length of each dialogue. The results are shown in Figure 5. Once again, CCBR4 gave the best performance, reducing dialog length by up to 63% and by 25% on average. On this occasion CCBR3, though reducing average dialogue length more effectively than CCBR1, was outperformed by CCBR2.

0 Max · Avg 0 Min

6 Conclusions

Recognizing when problem-solving dialogues can be terminated while minimizing the impact on solution quality is an important issue that has received little attention in CBR research. Focusing on incremental query elicitation in recommender systems, we have identified necessary and sufficient conditions for the dialogue to be terminated without loss of solution quality. We have also evaluated several attribute-selection strategies in terms of dialogue efficiency given the requirement that there must be no loss of solution quality. The best results were obtained with a goal-driven strategy in which the selected attribute is the one that maximizes the number of cases dominated by the target case. In spite of its low computational cost (linear in the size of the case library) this strategy gave close to optimal performance on the PC case library. It was also more effective in reducing average dialogue length than the other strategies evaluated on the Travel case library, a standard benchmark containing over 1,000 cases.

A feature of CBR recommender systems on which the techniques presented in this paper depend is that each outcome class (a unique product or service) is represented by a single case [McSherry, 2001]. Investigation of criteria for safe termination of problem-solving dialogues in other areas of CBR is an important objective for further research.