Customers are commonly not able to provide preferences that are technical enough to be used in the internal algorithms of knowledge-based recommender systems. In this paper, we present an approach to use a Bayesian network to infer technical preferences from customer answers obtained through a conversational elicitation process. The inferred preferences can be used in conjunction with a variety of common database ranking technologies to generate product recommendations.
When recommending complex products to customers, a knowledge-based recommender system has to base its reasoning on the mostly technical product properties that can be obtained using datasheets or similar sources of information. To this end, several well-known techniques exist, such as database ranking based on multi-attribute utility-theory or preference-based databases. However, as a prerequisite for applying these techniques, customers would need to be able to specify their wishes in technical terms. Experience reveals that this is far more than what can be expected from the average customer, in particular for complex technical product damains.
In this paper, we present a way to elicit preferences from customers by asking them \soft" questions about their needs and expectations. From their answers, preferences that serve as inputs to the afore-mentioned recommendation algorithms can be inferred by using a Bayesian network. We describe a utility-based approach to obtain product recommendations and provide a method to use the inferred knowledge as pareto-preferences.
The rest of this paper is organized as follows:
In section 2, we present a use case and describe the requirements arising from it. The process of inferring utility values for technical product attributes from customer answers is detailed in section 3. In section 4, we elaborate on how to make use of the inferred knowledge by employing a MAUT-based approach as well as other techniques such as pareto-based preferences. We review some related work in section 5 before concluding in section 6. Today's cellphones are complex technical devices, ful lling a wide range of functions beyond the classic \make a phone call away from home" scenario, such as navigation aid, MP3 player, digital camera, web / messaging client and many more. Very few customers are able to make completely well-informed buyingdecisions in this eld without a signi cant need for consultation. The situation is made even worse by the frequently changing product domain. Retailers are forced to permanently release new products to expand their share in a rather saturated market. Also, the domain itself sees frequent technical innovations, creating new products and sometimes even new business models (think of, e.g., location-based services made possible by the recent integration of GPS receivers into many mobile phones). Therefore, even once-acquired domain knowledge ages rapidly, for customers and salespersons alike.
Cellphones di erentiate themselves primarily through their technical properties, whereas customers' whishes commonly consist of \softer" needs that the desired phone is supposed to satisfy. Salespersons bridge this discrepancy in a natural way, translating the customers' wishes into appropriate technical requirements before recommending cellphones based on these requirements.
However, many current online-recommenders for mobile phones, despite being aimed at end-users, e.g., in web stores, cannot handle this abstraction. Commonly, many online applications are merely product con gurators that require their users to specify technical constraints which are then used to restrict the set of available products accordingly. To bridge the gap between a customer's wishes and technically evaluable preferences, an electronic recommender system must be prepared to accept fuzzy user input and use an internal model to infer the technical criteria. At the same time, the inference mechanism must be exible enough to be used in a dynamic dialogue environment, i.e., it cannot rely on a particular order answers are given in. Some questions may well remain unanswered throughout the dialogue, and for some questions the customers may change their opinion at a later point in the dialogue. 3
Our approach to infer technically useful information from customer answers is
based on a Bayesian network (cf., e.g., chapter 14 in [
Fig. 1 shows a UML diagram of a portion of the domain metamodel which is relevant to the process of eliciting preferences. The Articles in the targetted
Influence -positive : Boolean -weight : Integer
Article -name : String 1 described_by4 «interface» Influencer * * «interface»
Influenceable *
Attribute -name : String -weight : Integer 1
Need -name : String -questiontext : String -answeroptions : List<String>
Value -name : String allowed_values4 * domain are described by an explicit aggregation of their technical Attributes. To be able to distinguish the relative importances of Attributes during the recommendation process, they are assigned a numerical weight (cf. de nition 4 for a detailed explanation). Also, each Attribute explicitly lists its allowed Values, de ning the possible characteristics of the products in the target domain. Recommendations will then be obtained based on the modeled description of the technical properties of the target domain. The implied restriction to nite, discrete value ranges for Attributes has proven to be not a signi cant limitation, since, for our purpose, the value ranges of typically continuous Attributes (e.g., prices or sizes) can easily be classi ed into discrete ranges.
The dialogue used to obtain information from the customer is speci ed by modelling a number of Needs. The Need entity contains properties that are used to formulate a speci c question that can be asked during the course of the elicitation process, including the possible answer options.
Connecting the answers about Needs with the desired technical product properties that are required to obtain recommendations is accomplished by modelling a number of In uences that represent the causal interdependencies between Needs and other Needs, as well as between Needs and attribute Values. Inuences can be positive, i.e., have a strengthening e ect, or not, i.e., have an attenuating e ect. The numerical weight of an In uence denotes the \strength" of the In uence as we will detail further below.
Linking Needs with each other by means of an In uence is based on the notion that answers to questions regarding one Need may in uence answers that the customer is likely to give when asked questions about other Needs in the model, as can be observed in example 1. In uences between Needs and Values model the in uence an answer to a question has on the perceived utility of a product, as we will show in de nition 1.
Note that the diagram in Fig. 1 displays a metamodel, which must be instantiated to a domain model with concrete Needs, Attributes, and In uences. Examples 1, 2, and 3 will illustrate this process for a simpli ed mobile communications domain. Example 1 (Needs). Let us consider a simpli ed example from the mobile communications domain where the metamodel could have been instantiated by specifying the following exemplary Needs:
Need name Question text
\Will you use your new phone to... multimedia ...play multimedia content?" business ...use business functions?" music ...listen to music?" internet ...access the internet?"
It is immediately apparent that causal in uences exist between some of these Needs, which can be represented using In uences (cf. Fig. 1), as we show below.
For many questions it turns out in practice that they should be written in
a way so that they can be answered by customers on a Likert scale [
Example 2 (Attributes and Values). A current real-life model instantiation for the mobile telecommunications domain comprises about 70 technical Attributes with about 500 possible attribute Values. In this paper, we focus on three exemplary attributes and their possible values: Does the cellphone have an integrated MP3 player, does it have broadband internet connectivity via UMTS, and what size has its internal memory?
Attribute Allowed values mp3 yes / no umts yes / no memory small / medium / large
While mp3 and umts are examples of boolean value ranges, memory illustrates a discretized value range where the actual amount of memory has been mapped to discrete values (using, e.g., <1GB / 1-4GB / >4GB as a classi cation rule). Example 3 (In uences). Let our sample domain model contain In uences as shown in table 1 connecting the model elements of examples 1 and 2. For simplicity, assume further that all of them have an equal weight of 1.
Using In uences, arbitrary hierarchies of Needs may be speci ed, although a real-life evaluation revealed that the hierarchy remains rather at in the considered use case. In fact, there are merely three tiers, i.e., one tier of Needs that in uence other Needs on a middle tier which, in turn, in uence the technical Attributes that form the bottom tier.
From an instance of the domain metamodel, a corresponding Bayesian network can be automatically generated. Needs and attribute Values are represented as random variables (i.e., nodes of the graph representing the network). Need -variables have outcomes that correspond to the possible answers of the corresponding questions in the elicitations dialogue, so that a customer's answers can easily be represented in the Bayes net by introducing evidence for the appropriate outcomes. On the other hand, each Value is represented by a random variable with the outcomes of \true" and \false" that model the likelihood that a certain Value ful lls the customer's Needs. Modelling Values in this way (and not, e.g., by representing one Attribute as a single variable with all Values as possible outcomes) is necessary to model the fact that Values may be satisfying independently of each other.
The In uences form the edges of the Bayesian network. Modeled causal
dependencies between source nodes (In uencers ) and a target node (In uenceable)
are expressed by the entries in the conditional probability table (CPT) of the
target node. The CPTs are constructed in such a way that, for positive In uences,
if the customer agreed to the question corresponding to the source's Need, the
likelihood that he/she will also agree to the target Need is increased, weighted
relatively against other In uences by using the speci ed weight. If the target
node corresponds to a Value, the probability for \true" of that particular Value
is increased (i.e., it is more likely that products with this attribute value will be
acceptable for the customer). Negative In uences have the opposite e ects.
For a detailed description of the overall generation method see [
De nition 1 (Utility of a Value). We de ne the utility uav of an attribute Value av as the posteriori-probability of the outcome \true" of the random variable rav in the Bayesian network that corresponds to av :
uav := p(rav = true j : : :)
It immediately follows that all utility values are normalized between 0 and 1. Also, the advantage of representing attribute Values as separate booleans becomes apparent: It is reasonable that more than one Value for an Attribute can get a utility of 1.0 (i.e., is useful with 100% probability). This situation can be taken into account in a Bayes net as described above.
Example 4 (Utility). Consider an (early) point in the preference elicitation dialogue where the customer has given the answer \I strongly agree." to the question for the Need business. The answer is entered as evidence into the Bayesian network, leading to the posteriori probability-distributions shown in Fig. 3. Evaluating the In uences as described above, the elicitation algorithm infers that the customer will need to access the internet using the cellphone which makes UMTS connectivity a necessity, i.e., we have uumts yes = 1:0 and uumts no = 0:0
On the other hand, needing business functionality does not allow any conclusions towards multimedia support, which leads to ambivalent utilities for an MP3 player:
ump3 yes = ump3 no = 0:5
As for the memory capacity, the system reasons that a too small capacity is inacceptable in a business context, while a medium capacity is probably su cient (depending on whether additional storage is required for multimedia content).
As we have seen, the primary goal of the inference engine in our context is
to infer technical values from user needs according to the in uence relations and
given conditional probabilities. However, it can also process direct user input to
allow for short-cuts by simply inserting a submitted value as evidence for the
node of the Bayesian network that corresponds to the appropriate Value-entity.
Thus, the preference elicitation dialogue is inherently adaptable to di erent levels
of customer expertise. Further uses of the described inference approach, e.g., to
control the dialogue ow by estimating the importance of unanswered Needs and
to predict a customer's answers are presented in a broader context in [
As shown above, the Bayesian network provides us with estimations about the utility of every possible attribute value in the product domain. To use these estimations to elicit preferences, we also need a notion of the relative importance of the attributes relative to each other. In our approach, the importance of an attribute depends on three factors:
(1) Those attributes customers show signi cant interest in should be regarded as more important than others. In our model, \signi cant interest" is derived from the fact that more distinctive predictions for the attribute values exist.
(2) The dialogue situation has in uence on the importance of an attribute for the elicitation process. Attributes that are not connected to any already answered question, should not have any in uence at all.
(3) A domain expert may assign a static numerical weight to each attribute (cf. Fig. 1). Marketing research shows that some attributes are inherently more important than others in a buying decision. Experiments indicate that it is su cient to classify attributes into a small number of weight \classes", which is considered to be rather simple for suitably knowledgeable experts. De nition 2 (Distinctiveness of an Attribute). The Distinctiveness da of Attribute a is de ned as the average of the distances of the utilities of all possible attribute values of a from the \indi erent" utility of 0:5, normalized to [0::1]: da := 2
Pv2dom(a)(juv jdom(a)j 0:5j) Example 5 (Distinctiveness). To calculate the distinctiveness dmemory of the attribute \memory", assume that the following utilities have been inferred (cf. Fig. 3): umemory small = 0:0 umemory medium = 0:75 umemory large = 0:5 dmemory = 2 j0:0 0:5j+j0:75 0:5j+j0:5 0:5j = 0:5 3
The result ts our intuition: We are not yet sure about the customer's opinion regarding memory size at this point of the dialogue. Therefore, values derived for this attribute should not be taken too seriously. De nition 3 (Situation Factor of an Attribute). Let Qanswered be the set of all questions already answered in the current dialogue. For an Attribute a let P (a) denote the set of all In uence-ancestors of a, i.e., the Needs connected directly or transitively with a Value of a via an In uence-path in the network. The Situation factor sa of a is de ned as follows: sa := 0 if 8q 2 Qanswered : q 2= P (a) 1 otherwise De nition 4 (Importance of an Attribute). Let a be an Attribute and wa be the weight of a as speci ed in the particular model under consideration. Let da be the distinctiveness of a according to de nition 2 and sa be the situation factor of a (de nition 3). The Importance ia of a is de ned as ia := da sa wa Example 6 (Importance). Extending example 5, we determine imemory based on the following parameters: dmemory = 0:5 (example 5 ) smemory = 1:0 (memory is connected to the answered question ; Fig : 3 ) wmemory = 2:0 (taken from the domainmodel ) imemory = 0:5 1:0 2:0 = 1:0
Note that distinctiveness and situation factor depend on the preferences learned during the course of the elicitation dialogue. Therefore, they are updated after each dialogue step to account for newly acquired knowledge.
The approach to preference elicitation described here is based on
MultiAttribute Utility-Theory (MAUT { cf., e.g., [
The utility function can be formulated as a standard SQL query. For the sake of simplicity, we assume that all relevant data for an article is available in a single table with one column for each technical attribute (cf. Fig. 1) and an additional column containing the product's name. Every tuple in this table represents one concrete product (e.g., in the sample domain, one concrete cellphone). The following SELECT query computes a numerical UTILITY value for each tuple and orders the answer set accordingly:
SELECT *, ($utilityfunction) AS UTILITY FROM cellphones ORDER BY UTILITY DESC
$utilityfunction calculates the overall utility of a given cellphone by summing up the utility of each attribute value uvalue (cf. de nition 1), weighted by that attribute's importance iattribute (cf. de nition 4). To this end, our implementation uses a set of CASE-WHEN clauses for each attribute. Example 7 (Preference Order by MAUT). Assume that the current product catalogue contains the entries as shown in table 2. The utility and distinctiveness values are derived from the dialogue situation shown in Fig. 3: uumts yes = 1:0 uumts no = 0:0 dumts = 1:0 umemory small = 0:0 umemory medium = 0:75 umemory large = 0:5 dmemory = 0:5 ump3 yes = 0:5 ump3 no = 0:5 dmp3 = 0:0
For simplicity, assume situation factors of 1.0 for all attributes. For this constellation, the following ranking of catalogue entries according to the utility values computed as shown above results: 1) MobileC (Utility: 1.375) 2) MobileA (Utility: 0.375) 3) MobileB (Utility: 0.25) 4) MobileD (Utility: 0.0)
Since UMTS capability is the most important feature for our sample business customer, it is decisive in producing the utility-based rank (\MobileC" is the only UMTS-capable device in table 2). In contrast, support for MP3 does not play a role since the course of the dialogue did not yet allow any conclusions about the customer's wishes in this respect.
The structure of the query is known at the time of domain model design. Therefore, the query can be implemented as a stored procedure that can be called with the current importances and utility values as parameters. In our experiments, the actual query execution times were only a few millliseconds. It should be noted, however, that there are less than 1,000 di erent cellphones on the market today, leading to a rather small product catalogue and thus a small domain size. It is worth noting that, in general, the calculated utility for a product does not have an absolute meaning (i.e., a statement about how useful the product is, cannot be made). The value can only be interpreted in a relative way, i.e., a higher utility means greater usefulness and hence a higher rank.
The method described so far can also be used to provide the necessary inputs
for more general approaches to rank query answers using boolean predicates,
such as the one presented in [
PreferenceSQL supports \LAYERED" preferences (cf. [
Since the semantics of our approach relies on the notion that the customer is
generally indi erent about attribute values with the same utility (i.e., all values
with the same value are mutually substitutable), we annotate each LAYERED
preference with the additional \regular" keyword (cf. section 4 in [
Example 8 (PreferenceSQL). We re-use the dialogue situation of example 7 to formulate a query in PreferenceSQL. Using the pattern described above leads to the following statement:
SELECT * FROM cellphones PREFERRING umts LAYERED (('yes'), ('no'), others) regular AND memory LAYERED (('medium'), ('large'), ('small'), others) regular AND mp3 LAYERED (('yes', 'no'), others) regular
Executing this statement against the product catalogue of table 2 yields \MobileC " as the query result, which is the pareto-optimal tuple of the relation and therefore the only result according to the \Best-Matches-Only" semantics of PreferenceSQL. Successively re-executing the query with added WHERE-clauses to exclude the already-retrieved tuples yields the following results which are ordered exactly as those obtained using our MAUT-approach in example 7 (NB: in general, the orderings de ned by both approaches are not equivalent): 1) MobileC 2) MobileA (WHERE name <> 'MobileC') 3) MobileB (AND name <> 'MobileA') 4) MobileD (AND name <> 'MobileB')
Generated in this straight-forward way, the PreferenceSQL query would consist of a very large number of pareto-preferences. To reduce the number of preferences, the importance of an attribute (cf. de nition 4) may be exploited to limit the preferences to a xed number or to consider only preferences for attributes having an inportance that exceeds a certain threshold.
The knowledge-based elicitation approach described here is notably di erent
from collaborative ltering methods (cf., e.g., [
Ardissono et al. [
In [
An approach similar to ours is presented in [
We presented an approach to inferring utility estimations usable for preferencebased or ranking-based database queries, which is accomplished by using a Bayesian network that can be generated from a domain model. The approach described in this paper has been implemented in a joint project together with an industry partner. Their business experts designed a domain model comprising about 25 needs and more than 100 technical attributes. The model is considered to adequately represent the marketing-relevant aspects of the mobile communications domain from the industry point of view. Although the e ort for this rst real-life instantiation of the model was signi cant, the task was regarded as feasible and the routine model maintenance has turned out to be inexpensive under operational conditions. Evaluations of the overall recommendation concept by marketing research experts have shown convincing results concerning the adequacy of the model and the acceptance of the overall approach.
Our current work focuses on conducting a thorough eld evaluation of the system with a larger number of volunteers to obtain more statistical evidence about the quality of the derived preferences and related product rankings. Another eld of ongoing research is the design of an explanation component which is able to explain the reasoning that led to the generated recommendations and to exploit user feedback about the recommendations to automatically adjust some parts of the domain model.