Constraint-based recommendation systems are well-established in several domains like cars, computers, and financial services. Such recommendation tasks are based on sets of product constraints and customer preferences. Customer preferences reduce the number of products which are relevant for the customer. In scenarios like that it may happen that the set of customer preferences is inconsistent with the set of constraints in the recommendation system. In order to repair an inconsistency, the customer is informed about possible ways to adapt his/her preferences. There are different possibilities to present this information to the customer: a) via preferred diagnoses, b) via preferred conflicts, and c) via similar products. On the basis of the results of an empirical study we show that diagnoses, conflicts, and similar products are evaluated differently by users in terms of understandability, user satisfaction, and conflict resolution effort.
The number of e-commerce web sites and the quantity of
offered products and services is increasing enormously [1].
This triggered the demand of intelligent techniques that
improve the accessibility of complex item assortments for users.
An approach to identify relevant products for each customer
are recommendation systems [
Each recommendation approach has its own challenges.
For example, collaborative systems have to deal with the
cold-start problem [
In this paper we present four different scenarios to support the user in finding a way out of the ’no solution could be found’ dilemma. The first approach is to show which user preferences lead to an empty result set. For example, the combination of preferences of a notebook with 8GB RAM and a price which is lower than 200EUR is not satisfiable. By offering this information, the user can choose which of the preferences is less important and removes them. (1) We denote a set of preferences which is unsatisfiable (inconsistent with the given set of product-related constraints) as conflict. (2) Alternatively, the system is also able to show change operations which resolve all conflicts in the current customer preferences. Such change operations are denoted as diagnoses. (3) We can also show diagnoses and explain them by giving the information about conflicts. (4) If the user is not interested in conflicts and diagnoses, we are also able to show similar products by using a utility function which is ranking the products according to the user’s preferences.
The major goal of this paper is to analyze, in which way inconsistencies should be presented to users. Therefore, we conducted a study at the Graz University of Technology and the University of Klagenfurt. With this empirical study we provide recommendations for presenting inconsistencies in constraint-based recommendation scenarios to users.
The remainder of this paper is organized as follows. Section 2 gives an introduction into constraint-based recommendation systems, shows a working example, and provides an overview of inconsistency management techniques and utility calculation for products. Section 3 shows our online application for the empirical study, lists our hypotheses, and shows the evaluation of the hypotheses. Section 4 discusses relevant aspects and Section 5 finalizes this paper with a summary and issues for future work.
In our approach we exploit constraint satisfaction problems
(CSPs) for representing products and customer preferences
[
D is a set of domains dom(vi) where each domain describes possible assignments for a variable, for example: D = f dom(vname) = fcheap; media; easy; turbog; dom(vCP U ) = fdualcore; quadcoreg; dom(vRAM ) = f4GB; 6GB; 8GBg; dom(vHDD) = f400GB; 500GB; 750GBg, dom(vLCD) = f14; 15; 17g, dom(vprice) = f199; 399; 599gg
The set C describes constraints which are reducing the product space. Constraints can be product constraints c 2 CKB and all products are combined in a disjunctive order, such that c0 _ c1 _ ::: _ cn 2 CKB. A conjunctive set of customer preferences c 2 CR describes the customers preferences and CKB ^ CR = C. Next, we insert four products into CKB and two customer preferences into CR. c0 : vname = cheap ^ vCP U = dualcore ^ vRAM = 4GB ^vHDD = 400 ^ vLCD = 15 ^ vprice = 199 c1 : vname = media ^ vCP U = dualcore ^ vRAM = 8GB ^vHDD = 750 ^ vLCD = 17 ^ vprice = 599 c2 : vname = easy ^ vCP U = quadcore ^ vRAM = 4GB ^vHDD = 500 ^ vLCD = 14 ^ vprice = 399 c3 : vname = turbo ^ vCP U = quadcore ^ vRAM = 8GB ^vHDD = 750 ^ vLCD = 15 ^ vprice = 599 c4 : vCP U = dualcore 2 CR c5 : vRAM 6GB 2 CR
We now try to get all valid instances of the constraint-based recommendation task. A result (solution or instance) of such a recommendation task is characterized by Definition 1.
Definition 1: A complete consistent instance is a model where each variable in the knowledge base has an assignment, i.e. 8v2V v 6= ; and all assignments are consistent with the constraints in C.
In our case, the product c1 fits all customer constraints (preferences). Now, let’s assume that the customer has one more preference and adds the following constraint: c6 : vLCD = 14 2 CR
The new recommendation task leads to an inconsistency, s.t. Definition 1 cann’t be fulfilled. We only consider the constraints in CR as conflicting constraints and assume that the products in CKB have a valid representation.
Definition 2: A conflict set is a set of constraints CS CR s.t. CS CKB is inconsistent.
In the example, CR is inconsistent with CKB. Because potentially non-minimal conflict sets are not helpful for users, we try to reduce the number of constraints in conflict sets CS as much as possible (see Definition 3) and introduce the term minimal conflict set.
Definition 3: A minimal conflict set is given, iff the set CS is a minimal conflict set (see Definition 2) and there does not exist a conflict set CS0 CS with the property of being a conflict set.
There are algorithms for calculating minimal conflict sets
in inconsistent constraint sets [
Not all constraint sets have the same importance for each user. For example, if the CPU is more important for a user than the RAM, the user will probably prefer conflict sets which do not contain the CPU. We can calculate preferred minimal conflicts by ordering the constraints s.t. the preferred constraints are at the end of the list. For example, the constraint ordering fc6; c5; c4g leads to the conflict set fc6; c5g [9].
Resolving conflicts can be done in two different ways: First, we can remove constraints from a conflict set and receive further conflicts (e.g., removing the constraint c4 leads to the conflict set CS = fc5; c6g). Second, we can determine a set of constraints which resolves all conflicts in the given set of user preferences. We denote such sets diagnoses [8; 17]. By removing a set of constraints from the set of user preferences, we receive at least one valid instance (solution). A formal definition of diagnosis is the following one (see Definition 4):
Definition 4: A set of constraints CR is denoted as diagnosis if CR n [ CKB is consistent.
In our example, the removal of the set CR restores consistency since CKB is consistent. As the removal of all constraints probably doesn’t satisfy the customer, we try to detect minimal sets of diagnoses (see Definition 5) which will be used in Scenarios 1 and 3 as explanations for the inconsistency (Scenario 3 uses the minimal conflicts as an explanation of the diagnoses).
Definition 5: A set of constraints CR is denoted as minimal diagnoses iff it is a diagnosis (see Definition 4) and there does not exist a diagnosis 0 with 0 .
The example notebook recommendation system contains
two different minimal diagnoses: 1 = fc4; c5g; 2 = fc6g.
We can calculate them by using a diagnosis detection
algorithm [
Next, we calculate all minimal conflicts (Scenarios 2 and 3) and minimal diagnoses (Scenarios 1 and 3) for each customer. Currently it is not considered which of the conflict and diagnoses sets contains preference constraints that are relevant for the customer. For example, if the CPU is more important for the customer than the LCD size and the RAM (i.e., relevance(vCP U ) = 3; relevance(vLCD) = 2; relevance (vRAM ) = 1) we order the conflicts and diagnoses based on the relevance of the customer preferences. A conflict / diagnosis containing low relevances is called a preferred minimal conflict / diagnosis [8; 10]. In our example, the user has the possibility to add a relevance for each customer constraint 1 relevance(vi) n where n is the number of all variables. We used this information in our empirical study to get preferred minimal conflicts and preferred minimal diagnoses. For a detailed discussion of algorithms supporting the determination of preferred conflicts and diagnoses we refer the reader to Felfernig and Schubert [8].
We are also able to evaluate similarities between products and the customer preferences which will be used in the fourth Scenario of our empirical study. If the customer preferences can not be fulfilled, we can calculate the similarity by using the fitness function given in Equation 1.
f it(p; CR) = X u(p; c)
!(maxrelevance; c)
(1)
In Equation 1, p defines a product. CR is the set of customer
preferences. For each customer preference we calculate the
utility value u(p; c) and the weighting !(maxrelevance; c).
For the utility value, we are using McSherrys’ similarity
metrics for each variable [
product value is better (more is better) customer value and for the optical drive a nearer value is better (nearer is better) = [0; 1]. The weighting function !(maxrelevance; c) evaluates a weighting for the constraint c by calculating the relative importance relevance(c) . In the example in Figure 1 the weighing funcmaxrelevance tion for the product variable CP U is 5=6. Table 1 gives an overview about the fitness values of all example products (see Section 2). Note that the application upgraded all fitness values to a percentile value. The best value was the number of fulfilled preferences divided by the number of all the user’s preferences. In our example the product c1 matches two of three preferences ( 23 = 66%). The second best value was devaluated by the relative difference between the fitness values (0:66 00::456305 = 57%). 3
How users of recommendation systems deal with conflicts, diagnoses, and fitness values will be evaluated in this section. Therefore, we describe our online notebook recommendation system, define hypotheses, and evaluate and discuss them based on an empirical study. product In the preferences screen (see Figure 1) the user is asked for at least three preferences which are described in terms of product variables. Each of the specified preferences must be weighted on a six-point scale.
The next step was to remove all products c 2 CKB which are consistent with the user preferences CR to assure, that the participants were confronted with a situation where her preferences were inconsistent with the underlying product assortment, i.e., CR is inconsistent with CKB.
In the following, participants received a visualization of the conflict. Each participant was assigned to one of four scenarios (see Table 2). In the first scenario the participants got minimal diagnoses as change recommendations (see Figure 2). Scenario 2 presents minimal conflicts to the participants (see Figure 3). Scenario 3 contains both, minimal diagnoses and minimal conflicts, as explanations (see Figure 4). Scenario 4 shows the fitness values for all products (see Figure 5). For the differentiation between experts and novices we used two questions in the questionnaire at the end of the study. The first question asked for a self-assessment and the second question asked for expert knowledge. In our study 111 participants are experts and 90 participants are novices.
Next, we try to find the best approach for presenting inconsistencies in constraint-based recommendation systems. For the evaluation we have measured three general characteristics: a) the time which is used to repair a conflict, b) the understandability of conflicts and diagnoses, and c) the satisfaction with the ’no solution could be found’ dilemma. After having selected a diagnosis (in Scenarios 1 and 3), the participant (user) receives a list of notebooks. In Scenario 2 the user has to remove as many of her preferences in unless a product can be recommended because we removed all products which fits to the preferences. We call the number of preferences, which have to be removed until the user receives products, interaction cycles. For example, an interaction cycle of two means that the user removed two of her preferences until products could be presented. Therefore we expect that the time, which is necessary for resolving the conflict, will be lower when diagnoses are presented to the participant:
Hypothesis 1: Study participants will solve inconsistencies faster when they receive diagnoses.
The study participants received all diagnoses in a preferred order (see Section 2). We expect that the first diagnosis will be selected most frequently.
Hypothesis 2: The first diagnosis will be selected by the majority of the users for adapting their preferences.
A conflict occurs if a set of preferences can not be fulfilled (see Definitions 2 and 3). Scenario 3 uses the minimal conflict sets (see Definition 3) as a description for the minimal diagnoses (see Definition 5). We expect a positive impact on the understandability by the diagnoses:
Hypothesis 3: Participants will understand their conflicts more easily, if they receive explanations.
When the participants don’t receive products after having inserted the preferences, the satisfaction with the recommendation system will decrease, and we expect that the satisfaction with the product assortment of our recommendation system will be higher if products are offered (Scenario 4), even if they don’t fulfill all of the participants’ preferences.
Hypothesis 4: The participants will have a higher satisfaction with the product assortment when they receive fitness values (Scenario 4, see Figure 5).
Due to the stability of preferences, the participants are less willing to adapt their preferences. When the recommendation system asks for more than one adaption of preferences, the participants will have a lower satisfaction with the system. This leads to the following Hypothesis:
Hypothesis 5: More interaction cycles lead to a lower satisfaction with the anomaly support. 3.3
Evaluation For evaluating our hypotheses, we conducted a study at the TU Graz and the University of Klagenfurt. 240 users participated in our study. The students’ average age is 25 years (std. dev.: 5.52 years). The participants are studying technical sciences (117), cultural sciences (63), economics (29), and other sciences (n = 31). We’ve tested our results with a two-tailed Mann-Whitney U-test and removed all participants with contradictory answers to the SUS (system usability scale) questionnaire [2]. Finally, we divided 201 participations into the scenarios with diagnoses (n = 56), conflicts (n = 50), diagnoses and conflicts (n = 38), and the fitness function (n = 57).
Hypothesis 1 focuses on the time which is required to resolve inconsistencies. Therefore, we measured the time between the first conflict notification and the product presentation (see Table 3).
The result shows that the time for removing conflicts with diagnosis is lower (16.64 sec.) than with conflicts (21.16 sec.) or selecting the diagnoses with a corresponding explanation (20.05 sec.). This is because there is only one interaction cycle for resolving inconsistencies with a diagnosis whereas 1.66 interaction cycles are required to resolve inconsistencies with conflicts. Reading the explanation of a diagnosis also increased the time to resolve an inconsistency (20.05 sec.) compared to the diagnoses without explanations (p < 0:1). The time for resolving the conflicts is 0 in Scenario 4 since they aren’t resolved. These results confirm Hypothesis 1.
We also researched the influences of the number of conflicts and diagnoses (see Table 4).
# of presented diagnoses / conflicts 1 diagnosis: 2 diagnoses: > 2 diagnoses: 1 conflict: 2 conflicts: >2 conflicts: n 11 11 38 56 23 4 satisfaction
repair time 4.55 4.14 4.37 4.09 4.04 1.75 11.18 sec. 10.71 sec. 19.32 sec. 22.29 sec. 45.48 sec. 62.00 sec.
The time to select a product was nearly the same in the scenarios with diagnoses (Scenario 1) and conflicts (Scenario 2). The third scenario performs best in terms of the time which is required to select a product (18.72 sec.). This can be explained by the fact that dealing with diagnoses and conflicts helps to receive a deep understanding of the problem. Participants in the fourth Scenario required 43.82 sec. for selecting a product. The higher effort for selecting a product can be explained by the missing explanations of the conflict, and the participants may get confused that not all preferences are fulfilled by the offered products. All differences in the product selection time are statistically significant (p < 0:001).
Hypothesis 2 is looking at the ordering of preferred
diagnoses and conflicts. We measured the position of the selected
conflict / diagnoses (see Figure 6). Note, there are only those
participants considered from Scenarios 1 and 3 whose
number of offered diagnoses is greater than one.
We can confirm Hypothesis 2 since 81 of the participants
(82.65%) selected the first diagnosis. The second diagnosis
was selected by 11 (11.22%), the third one by 5 (5.10%)
participants and the fourth recommendation by one participant
(1.02%). Reasons for applying the first diagnosis are that
the first diagnosis contains only unimportant preferences, the
primacy-effect [5], and preference reversals [
For measuring Hypothesis 3 we asked the participants from the Scenarios 1-3 if the diagnoses/conflicts were understandable. Answers were given on a 5 point Likert-scale (5 represents the highest understandability).
Results show that the highest understandability is given when diagnoses are presented (Scenario 1) followed by diagnoses explained with conflicts (Scenario 3) and conflicts (Scenario 2, see Table 5). The difference between the understandability of conflicts (4; 4, Scenario 2) and the other Scenarios (Scenario 1 with 4:55 and Scenario 3 with 4:45) is statistically significant (p < 0:05). The degree of understandability is higher for experts than for novices (p > 0:1). We can partially confirm Hypothesis 3 since experts have a higher understanding of the conflict when conflicts and diagnoses are presented while novices can not deal with much information. Due to the cognitive processes (trial-and-error of novices versus analytical processing of experts [11]) it is easier to deal with diagnoses when the cognitive process is more analytical. When participants use a trial-and-error process and they don’t expect the visualization of conflicts, it is harder to adapt the preferences.
Hypothesis 4 evaluates the satisfaction with the recommended products. The average values are from 2.62 up to 3.3 (see Table 6) which is worse and can be explained by the removal of all valid products at the beginning of the process. The results show that conflicts (Scenario 2) and the fitness function (Scenario 4) lead to the highest satisfaction with the product assortment. A differentiation between experts and novices does not influence the significance. Because conflicts and the fitness values lead to the same satisfaction we can not confirm Hypothesis 4. An interesting result is also, that novices have an overall higher satisfaction with the product assortment compared to experts. This can be explained by the fact, that they are more happy that they get any products recommended. On the other hand, experts know, that there are products which fits to their preferences.
Hypothesis 5 will be evaluated by Table 7. There is a significant difference when participants had more than two interaction cycles. A statistically significant difference between experts and novices isn’t constituted. A differentiation between the interaction cycles of diagnoses and conflicts also doesn’t lead to a significant difference between all interaction cycles or between conflict and diagnoses visualization. We can confirm Hypothesis 5.
A comparison between the number of conflicts / diagnoses
and satisfaction, understandability, or time to resolve the
inconsistency is not statistically significant.
4
satisfaction
4.44
4.30
2.67
3.00
This paper gives an overview about conflict management in
constraint-based recommendation systems. While we can not
present products which fit to the user’s preferences the user
has to adapt her preferences. Such preference reversals
always result in a low satisfaction of users. The degree of
dissatisfaction depends on how often the preferences have been
fulfilled in the past [
If users have positive experience with their preferences, it
can happen that the participants have well-established
anchoring affects [
Another important aspect is the cognitive processing task. While novices tend to use trial-and-error processes, experts tend to use heuristic and analytic cognitive processes [11]. That means that novices tend to adapt their preferences unless they receive products. Our results confirm this process since the satisfaction of novices is high if they can adjust their preferences arbitrarily or receive similar products (see Hypothesis 4). On the other hand, experts try to understand the modifications and analyze them. Therefore, they prefer the visualization of diagnoses (see Hypothesis 3). 5
This paper shows how different visualization strategies for conflicts can be used within constraint-based recommendation systems. We’ve shown the state-of-the-art in detecting all minimal preferred diagnoses and conflicts, calculated fitness values for products, and introduced hypotheses for conflict management and evaluated them with an empirical study. The result of this evaluation is that the optimal strategy for the visualization of inconsistencies depends on the optimization strategy. The visualization of diagnoses leads to a low interaction effort, whereas the visualization of conflicts and fitness functions leads to a higher satisfaction.
A major focus of our future work will be the inclusion of different decision-psychological effects such as, for example, framing, priming, and decoy effects into our studies. In this context we want to answer the question whether these phenomena exist in the context of conflict detection and resolution scenarios, too.
Judgement
Science,