Coverage-Optimized Retrieval

1 Introduction

An advantage of case-based reasoning (CBR) in product recommendation is that if none of the available products exactly matches the user's query, she can be shown the products that are most similar to her query [Wilke et a!., 1998]. However, a known limitation of similarity-based retrieval is that the most similar case may not be the one that is most acceptable to the user [Burkhard, 1998; Smyth and McClave, 2001]. The k-NN strategy ofretrieving the k most similar cases only partially compensates for this limitation, as the number of cases that can be presented to the user is necessarily restricted in practice. So the existence of an acceptable case does not guarantee that it will be retrieved.

We present a new approach to retrieval called coverage­ optimized retrieval (CORE) which ensures that for any case that is acceptable to the user, the retrieval set contains a case that is at least as good in an objective sense and so also likely to be acceptable. Similarity to the target query is only one of several possible criteria according to which a given case might be considered at least as good as another in the approach.

2 The CORE Retrieval Set

The similarity of a given case C to a target query Q over a subset AQ of the case attributes A is typically defined as:

where for each a E AQ, Wa is a numeric weight representing the importance of a and sima(C, Q) is a measure of the similarity of 1t 0 (C), the value of a in C, to 1ta(Q) , the preferred value of a. Apart from its similarity to the target query, another factor likely to influence the acceptability of a given case is the compromises it involves, or preferences of the user that it fails to satisfy [Burkhard, 1998]. Often in e-commerce domains, one can identify attributes whose values most users would prefer to maximize or minimize [Wilke et a!., 1998]. In CORE, we assume that the value specified by the user is a preferred minimum in the case of a more-is-better attribute or a preferred maximum in the case of a less-is-better attribute.

Definition 1 For any query Q and case C we define:

So d(C, Q) is the set of attributes with respect to which C fails to satisfy the user's preferences. Below we define four dominance criteria according to which a given case C1 might be considered at least as good as another case C2:

For example, if sima(C1, Q) ~ sima(C2, Q) for all a E AQ we say that C1 dominates C2 with respect to D3. We say that a given case C2 is covered by a retrieval set RS if C2 E RS or there exists C1 E RS such that C1 dominates C2. The importance of coverage in this sense is that if an acceptable case that is not retrieved is covered by a retrieved case, then the retrieved case is also likely be acceptable. Another basic premise in our approach is that the likelihood of the retrieved case also being acceptable increases with the strength of the dominance criterion with respect to which it dominates the acceptable case. For example, dominance of the acceptable case with respect to DO (the usual similarity criterion) may not be enough to ensure that the retrieved case is also acceptable. However, if it dominates the acceptable case with respect to D3, then there is no attribute with respect to which it is less similar to the user's query.

In k-NN, all cases are dominated by the most similar case with respect to DO; so even 1-NN provides full coverage of the case library with respect to DO, the weakest of our dominance criteria. The aim in CORE is to construct a retrieval set that provides full coverage of the case library with respect to any of the dominance criteria we have identified. In Figure l, Q is the target query and Candidates is a list of candidate cases for addition to the retrieval set RS. We assume that the candidate cases, initially all cases in the case library, are sorted in order of non-increasing similarity, and that if C~> C2 are equally similar cases such that C1 dominates C2 but C2 does not dominate C~> then C1 is listed before C2 in Candidates.

algorithm CORE(Q, Candidates, RS) begin RS~~ while !Candidates! > 0 do begin C1 ~first( Candidates) RS~ {C!} uRS cover(C1) ~ {C!} for all C2 E rest( Candidates) do if C1 dominates C2 then cover(C1) ~ cover(C1) u {Cz} end

Candidates ~Candidates- cover(C1) end

We refer to the versions of CORE based on D 1, D2 and D3 as CORE-l, CORE-2 and CORE-3 respectively. It is worth noting that with DO as the dominance criterion, CORE is equivalent to 1-NN, and so CORE is in fact a generalization of similarity-based retrieval.

Theorem I The CORE retrieval set provides full coverage of the case library and no smaller retrieval set can provide full coverage of the case library.

While it can easily be shown that the maximum possible sizes of the CORE-l and CORE-2 retrieval sets for a given

query Q are JAQJ + 1 and 2IAQI respectively, the maximum possible size of the CORE-3 retrieval set is not as easily determined. In practice, CORE-l and CORE-2 retrieval sets are usually much smaller than their maximum possible sizes. Figure 2 shows the maximum, average, and minimum sizes of CORE retrieval sets for full-length queries on the Travel case library (www.ai-cbr.org). As might be expected, there is a trade-off between the strength of the dominance criterion in terms of which coverage is defined and the size of the retrieval set required to provide full coverage of the case library. Though unable to compete with CORE-l in terms of coverage efficiency, CORE-2 has an average retrieval-set size of only 7.5 cases.

3 Conclusions

Coverage-optimized retrieval (CORE) is a generalization of similarity-based retrieval which ensures that for any case that is acceptable to the user, the retrieval set contains a case that is at least as good according to a given dominance criterion. Our empirical results show that the size of the retrieval set required to provided full coverage of the case library in this sense increases with the strength of the dominance criterion in terms of which coverage is defined. However, CORE-2 offers a good compromise between strength of dominance and retrieval-set size, with an average of only 7.5 cases required to provide full coverage for full­ length queries on a case library containing over l ,000 cases.