Information Recommendation is a conversational approach aimed at suggesting to the user how to reformulate his queries to a product catalogue in order to nd the products that maximize his utility. In previous work, it was shown that, by observing the queries selected by the user among those suggested, the system can make inferences on the true user utility function and eliminate from the set of suggested queries those retrieving products with an inferior utility (dominated queries). The computation of the dominated queries was based on the solution of several linear programming problems, which represented a major computational bottleneck for the e ciency of the proposed solution. In this paper we propose a new technique for the computation of the dominated queries. It relies on the assumption that the set of possible user utility functions is nite. We show that under this assumption the computation of the query suggestions is simpli ed and the number of query suggestions is strongly reduced.
Recommender Systems (RS) are intelligent tools and applications designed to support users in nding information, products or services that suit their needs and preferences [8]. Recommender system technologies are rooted in Machine Learning and Information Retrieval [4]. The core computational problem of a RS is to predict the user's preferences, e.g. expressed as ratings for items, and recommend the items with maximal predicted preference [8]. Classical RS techniques, such as collaborative and content-based ltering, collect the user's preferences in the form of ratings for items to meet the goals mentioned before. Their major limitation is that they present the recommendations in a single shot, and the user can either accept one of these recommendations or enter new preferences and restart the process. Conversely, Conversational Recommender Systems (CRS) [2, 5, 6] not only rank and suggest products to users, but also guide them during the human-computer interaction to nally select the products that they may like. This guidance process is composed of several actions that depend on the underlying conversational technology (e.g., critiquing [7, 6]).
In [1, 9] the authors rst introduce and then extend a new conversational technique relying on the idea of \Information Recommendation". In this approach the user is supposed to query a product catalogue by issuing simple queries, such as \I want an hotel with AC and parking". The system, rather than recommending immediately the products that satisfy this query, assumes that the user may have also other needs and suggests some query revisions. These new queries, for instance, may add an additional feature to the query, e.g., the system may say: \are you interested also in a sauna?". Products with more features, if available, will surely increase the user utility. But not all features are equally important for the user. So the goal of the system is to make \informed" suggestions, i.e., to suggest features that are likely to increase more the user utility. In fact, the system, observing the user queries, can deduce that certain features are more important than others, i.e., can infer constraints on the de nition of the user utility function, even without knowing it. Hence, using this knowledge, it can suggest that the user try a query from a well-selected and small set of candidate queries . A similar idea, i.e., using a utility function estimation to select the more user relevant critiques (new queries), is described in [10].
In [1][9] it is shown that this approach is e ective and provides good query suggestions and nal recommendations. It guides the user to the query that selects the products with maximal utility in a short number of query revision interactions. The quoted papers describe the details of the approach: the query language, the possible preference models of the user, the inferences made by the system on observing the user's query revisions, and the computation of the query suggestions for the user. Nevertheless some questions mostly related to the e ciency of the query suggestions computation and the size of the advice set are still open and require further investigation. In fact, the computational cost of query suggestion is playing a critical role in this approach. In [1] linear programming techniques were used for computing the query suggestions. Even if the computational complexity of that algorithm is polynomial, it must be invoked numerous times (to compare each pair of candidate queries), and in practice it takes too much time for a real online application. Moreover, the average size of the advice set, i.e., the queries suggested by the system to the user at each interaction step, remains large in many cases (more than 20). This is a critical issue for implementing a real application based on the proposed technique.
In this paper we re ne the proposed model by making the assumption that the user utility function is drawn from a set of nite possibilities. This set of \user pro les" represents the possible \di erent" users that the system may interact with. We will show that this assumption has a strong e ect: it simpli es the search process for the query suggestions and reduces the average number of query suggestions made at each interaction step. This nite model assumption is realistic, as users tend to cluster in groups with similar preferences. Moreover, considering an increasingly large number of user pro les one can approximate all the possible ones. 2
In our model a product p is represented by an n-dimensional Boolean feature
vector p = (p1; : : : ; pn). pi = 1 means that the i-th feature (e.g., Air
Conditioning) is present in the product, whereas pi = 0 means that p does not have
feature i. A catalogue is a set of products fp(
Queries are represented similarly as Boolean vectors: q = (q1; : : : ; qn). qi = 1 means that the user is interested in products that have the i-th feature. On the other hand qi = 0 does not mean that the user is not interested in products with that feature, but simply that he has not yet declared his interest on it. A query is said to be satis able if there exists a product in the catalogue such that all the features expressed in the query as desired (qi = 1) are present in that product. For example if the product p = (1; 1; 0; 1; 0) is present in the catalog then query q = (0; 1; 0; 1; 0) is satis able.
We are considering a scenario where the user may be interested in re ning an initial query. Moreover, we assume that the user is not likely to radically modify this query. This may also be a constraint imposed by the GUI of the query system, where the user can be o ered with only a small number of easily understood editing operations. In the following we list the query editing operations that we assume the user can make when revising the current query: { add(q; i), where i 2 idx0(q) { trade(q; i; j; k), where i 2 idx1(q) and j; k 2 idx0(q) where idx0(q) and idx1(q) are the set of indexes with value 0 and 1 in q respectively. The rst operation generates a new query by requesting one additional feature. For example, (1; 1; 0; 0; 1) = add((1; 1; 0; 0; 0); 5) is extending a query where only the rst two features were requested by adding also the fth feature to the set of requested ones. The second operation generates a new query by discarding a feature, the i-th, in favor of two new ones, the j-th and k-th features. For example, (0; 1; 0; 1; 1) = trade((1; 1; 0; 0; 0); 1; 4; 5)
Using the above-mentioned operators the system can generate a set of next queries and ask the user to select the preferred one. In our approach, the goal of the system is not to suggest all these possible next queries, as a standard \query by example" interface may implement, but rather only queries that could retrieve products with the largest utility. Hence, rst of all, the unsatis able queries must not be suggested. This can be easily implemented with standard query processing techniques. But, as it will be shown later, also other types of queries can be discarded: those that can be proved to retrieve products with a smaller utility than those retrieved by another query in the suggestion list (dominated queries). 3
User preferences for products are represented here as a vector of weights: w = (w1; : : : ; wn); 0 wi 1 wi is the importance that a particular user, one having that set of preference weights, assigns to the i-th feature of a product. So if wi = 0, then the user has no desire for the i-th feature. If wi > wj , then the i-th feature is preferred to the j-th one. If wi wj then the i-th feature is at least as desired as the j-th one. If wi = wj , i 6= j then the user is indi erent between these two features. The user utility for a particular product p = (p1; : : : ; pn) is given by the following: U tilityw(p) = n X wi i=1 pi
A product p with a higher utility than another product p0 is always assumed to be preferred by the user, i.e., we assume that users are rational. We also de ne the potential utility of a query q = (q1; : : : ; qn) for the user as: U tilityw(q) = Pin=1 wi qi. We call this utility \potential" if we do not know wether a product with the features speci ed in the query does exist, i.e., if the query is satis able. In case such a product exists, this potential utility is also a true utility.
A user accessing the system may have any of the possible utility functions that can be de ned by varying the feature weights wi. So, in principle, the set of all possible utility functions is in nite. But observing the queries selected by the user among those that he can make (i.e., those suggested by the system), the system can infer constraints on the de nition of his utility function. Generally speaking, features present in the selected query can be considered as more desired by the user than features that are present in the alternative queries. The constraints deduced by the system on the user utility function w = (w1; : : : ; wn) are illustrated below.
Initial query. If the current query q is the initial query, then the advisor may infer that wi wj , 8i 2 idx1(q) and 8j 2 idx0(q), unless q, with the i-th feature set to 0 and the j-th feature set to 1, is unsatis able. This means that if the user issued a query that requests the presence of a feature then the potential utility of this query is assumed to be larger than or equal to that of another query where this feature is not requested. But only if this \alternative query" is satis able.
Adding a feature. If the current query q0 results from an add() operation on
the previous query, that is, q0 = add(q; i), then the advisor infers wi wj , 8j 2
idx0(q), i 6= j, unless add(q; j) results in an unsatis able query. The rationale
of this deduction is similar to the previous one. We assume that the user has
(
Trading one feature for two. If the current query results from a trade operation on the previous query, i.e., q0 = trade(q; i; j; k), the advisor may infer: 1. wj + wk wi, 2. wj +wk wj0 +wk0 , 8j0; k0 2 idx0(q), fj; kg 6= fj0; k0 g unless trade(q; i; j0; k0) is unsatis able.
The rst constraint says that the current query does not have a utility inferior to the previous one. While the second constraint says that the selected trade operation must obtain a utility that is not inferior to that of alternative trade operations that the user may have applied (and are satis able).
We note that unsatis able queries are never suggested, and therefore we never deduce that a query has a potential utility larger than that of a failing query. In the previous work [1], we called this \play safe" because we considered that the user might know that a query will fail and therefore he does not try it, hence we cannot assume that the potential utility of the query that was actually tried is larger than that of a query that the user did not try because he knew it would fail. In the current work we generalize and rephrase it by saying that the system can deduce only that the potential utility of the query that is tried is greater than or equal to the (potential) utility of the other queries that were suggested, or equivalently that the user could have tried (either because the system suggested them or because the user knows they are satis able). 4
The advisor is the intelligent entity in charge of observing the interaction process, the user movements (queries issued), and making inferences on the user preferences. As mentioned before, the user preferences are not known at the beginning of the interaction between the user and the advisor. The advisor, after the user's rst query, will generate a set of next candidates queries and will suggest only those with a utility that cannot be proved to be inferior to one of the other queries (undominated queries).
At each user-system interaction step, the advisor accumulates some
constraints on the user utility function (see Section 3). We denote this set of
constraints by . Moreover, given a set of next possible queries C = fq(
A query q 2 C is dominated if there exists another query q0 2 C such that for all the possible weight vectors that are compatible with the set of constraints this relation holds: U tilityw(q0) > U tilityw(q). A weight vector w is said to be compatible with the set of constraints in if and only if all the constraints in are satis ed when the variables w1; : : : ; wn take the values speci ed in w.
Removing the dominated queries is meaningful because their utility is lower
than the utility of another query (that is suggested) for all the possible user
utility functions that are compatible with the preferences induced by observing
the user behavior. In this paper we solve this problem under the assumption
that the user's true utility function is de ned by one (unknown) vector among
a nite set of weights vectors considered by the system. We call this nite set of
all the possible utility function or \user pro les" P = fw(
With this assumption, having the set we can prune from the set P the
\incompatible pro les", i.e., those not satisfying the constraints . Then, the
computation of the undominated queries proceeds as follow. Let's assume that
the set of user pro les compatible with the accumulated constraints is P 0 =
fw(
Example. Assume that = fw1 w3; w2 + w3 w4g, P 0 = fw(
Finally, the algorithm for query suggestions using a nite set of user pro les is described as follows: 1. = ;, P = all possible pro les, AdviceSet = all possible queries 2. Do 3. Present AdviceSet to the user; 4. currentQuery = query selected by the user in AdviceSet; 5. Infer constraints analyzing the currentQuery and add them to ; 6. Remove incompatible pro les from P ; 7. Compute candidate queries; 8. Remove dominated queries from candidate ones and generate AdviceSet; 9. while ((AdviceSet 6= null) and (user wants advice))
The advisor presents to the user a possible set of queries. At the beginning these are all the possible ones, i.e., the user is free to enter the rst query. Then the advisor infers the constraints according to the rules mentioned in section 3. The advisor then removes the user pro les that do not satisfy these constraints. Afterwards the set of candidate queries are generated from the current query, applying the operators mentioned in Section 2 and those that are not satis able are removed. Finally, the advisor identi es the AdviceSet by removing the dominated queries and suggests the remaining ones to the user as potential new moves. If the user selects one from this advice and the AdviceSet is not empty then the selected query becomes the current query and the process is repeated. If the user does not want further advice then the system will suggest the products that satisfy the last query selected by the user. 5
We performed some experiments in order to compare the performance of the proposed approach with the results obtained in [1]. We simulated several interactions between a user and the advisor. We varied the following parameters in the simulations: the product database and the number and format of the user pro les. Three di erent product databases were used, each one describing real hotels by their amenities expressed as Boolean features. Details of the product databases are given in the Table 2; here an hotel may have the same product description in terms of features as another, which is why the number of distinct products is smaller than the number of hotels.
We considered two kinds of user pro les as typical models of user preferences: \random-shape user pro les" and \exponential-shape user pro les". A \user's pro le shape" refers to the distribution of the weights of the features in a user pro le. Random-shape user pro les are created by rst generating one initial user pro le (weights vector) sampling the weights from a uniform distribution in [0,1]. Then the other pro les, in the same set P , are created by a random permutation of the feature weights of the initial user pro le. Note that if the weights are sorted into decreasing order, the resulting sequence will decrease near linearly. This is because there is no special `preference' for any number when you randomly select them. Conversely, the set of exponential-shape user pro les is created by generating rst one initial user pro le with an exponentially decreasing importance for the weights: e i, with a selected 2 [1; 4] and i = 1; : : : ; n. The other user pro les are again obtained with random permutations of the initial user pro le. Here we wanted to simulate users with a few important features and many less important ones. For each experiment, we generated three sets of user pro les P : small (24 pro les), medium (120 pro les) and large (720 pro les). We wanted to observe the e ect of the assumed variability of the user pro les on the user-advisor interaction length and the size of the advice set.
We assumed that the user is \Optimizing" [1], that is, one who con nes his queries to the advice set provided by the advisor and he will always try the query with the highest utility in the advice set. The simulated interaction between a virtual user and the advisor is done considering the algorithm described in the previous section. One element of the set of prede ned user pro les is randomly selected and considered as the user's true pro le (user's utility). This is not revealed to the advisor, which interacts with the simulated user using the proposed methodology. The advisor deductions about the user's true utility function are based only on the observation of the user queries submitted at each interaction step. The initial query submitted by the simulated user is created in accordance to his true utility function; thus, the initial query includes up to the k most important features for the user.
In total, 18 experiments were performed corresponding to the combination of the variables mentioned before (product database, user pro le shape and number of user pro les). In every experiment we ran 50 dialogues between a simulated user and the advisor. The observed measures were: the average number of queries issued per dialogue, the average size of the advice set and the average utility shortfall. The utility shortfall is the di erence between the utility of the best query (selecting the product with the highest utility for the user) and the last query suggested by the system to the user. In this way we could measure if the system suggestions are close to the best query according to the user's true utility function.
Table 3 shows the values of the observed measures. We can observe that the average number of queries issued by the virtual user (interaction length) ranges between 3 and 7 almost independently from the \User Pro le shape" and \User Pro le set size". The interaction length seems to be related to the number of product features and the available products in the data set. The higher the number of product's features the longer will be the interaction. This happens because the user at each query editing step adds one feature to the previous query. In fact, the query suggestions are generated by the add() and trade() operations that extend the previous query by setting one additional feature to Trentino 1. Hence, assuming that the best query has a certain number of features set to 1, then the user needs to pass through that number of steps (minus the number of features set to 1 in the initial query) in order to reach it, or to reach another query that does not provide the maximal utility but still cannot be further extended without reaching a failing query. Another factor to take into account is the number of products in the database. The smaller the number of products is, the more likely the process is to stop, because the current query cannot be further extended without building a failing query. The most important aspect of these values is that the interaction length is typically low and quite reasonable for real online applications.
The \Average size of the advice set" is sub-linearly correlated to the pro le set size, that is, to the number of prede ned user pro les. The higher the number of prede ned user pro les, the (slightly) higher is the number of query suggestions in the advice set on average. In fact, if there are more user pro les, the more di cult it is to nd dominated queries, thus the set of undominated queries (the advice set) is more likely to be larger. In general the average advice set size ranges between 1 and 6. This number of query suggestions represents an acceptable value for real applications. The \Average size of the advice set" doesn't seem to be related to the variables \User Pro le shape" and \Product database". In general the \User pro le shape" doesn't seem to in uence either the \Interaction length" or the \Average size of the advice set".
The utility shortfall is very close to 0 on average. This cannot be 0 because the query suggestions are searched in a greedy way (always expanding the previous query), hence the advisor can fall into local maxima paths while searching for the best query suggestion [1]. Thus we cannot assure that the Advice Set will always contains the query with the largest utility that can be obtained by using the current query editing operations. Hence, limiting the query editing to the add(: : :) and trade(: : :) operators does not assure the user to reach the best query. Nevertheless at the end of the process the nal query is very close to the best attainable given the user preferences.
Figure 1 shows the evolution of the Advice Set size (averaged over 50 dialogues) in the experiment that produces the highest number of average advices per suggestion (5.73 queries in table 3). That experiment corresponds to: Product Database = Marriott NY, Pro le Shape = Exponential, and User Pro le set size = 720. The curve labeled as \average" shows the average number of advices given to the user at the rst three interaction steps. At the rst step, the number of queries suggested is on average 10:4 8:2(avg: stdv:); at the next interaction step, it is 5:3 3:9; and nally the system suggests only 1 0:7 queries (the best). The curves labeled as \Maximum" and "Minimum" correspond to the maximum and minimum number of queries suggested at each interaction step to the user. In general we can see that the number of advices falls quickly in a short number of interactions. Still, it is clear that there are certain dialogues with a rather large number of advices, and this is an issue to consider in the application of this technique.
We now compare our results with those presented in [1]. Table 4 shows the values of the variables \Average number of queries issued per Dialogue", \Average size of the Advice Set", \Average Utility shortfall" obtained in the previous work, where an in nite number of pro les was considered and the query dominance relation was computed using linear programming techniques. It is clear that the average number of queries per dialogue is low in both approaches and very similar. This is due to the fact that the actual query editing operations are the same in the two approaches, and the dialogues converge to optimal queries with similar operations. The utility shortfall in the current approach is a bit larger than that measured previously. This is what one has to pay for the limiting assumption that the number of possible user utility functions (pro les) is nite. The major bene cial e ect of the proposed approach is the signi cant reduction in the number of queries suggested by the advisor to the user by more than 10 times. This makes it much more suitable in real applications. Obviously this is again related to the assumption that the variability of the user utility functions is assumed to be smaller. We believe that in real scenarios approximating the set of all possible utility functions with a smaller, nite set, is a reasonable assumption and the small cost paid in terms of increased utility shortfall is compensated by the strong reduction in the size of the advice set, making it feasible for the user to browse the advice set and pick up his best query. 6
In this paper we have described and analyzed the performance of a new type of conversational recommender system that suggests query revisions to a user searching for products in a catalogue. The products are described by Boolean features. They can be for instance tags or keywords found in the product descriptions. In this paper we assume that the user utility function is one among a nite set of possible functions that are known to the system, but the system does not know which is the true utility function of the user.
The results of our experiments showed that this assumption has a strong e ect on the process of nding the best query suggestions that guide the user to the products that maximize his utility. In particular the number of useradvisor interaction steps (number of queries issued by the user) and the utility shortfall are low (as in our previous work where the user pro les were not limited to be nite). But, di erently from the previous case, we have now observed a signi cant reduction in the number of advices provided at each user-advisor interaction step. We have also showed that having a good number of prede ned user pro les is an important ingredient for improving the system performance and producing an e ective support.
In future work we will consider the case when the true utility function of the user is not one of those assumed by the system. This is the true general situation when a totally unknown user is approaching the system and the system has no knowledge about his preferences. In particular, we will measure how this impacts on the utility shortfall. Additionally we will implement this approach on a real online and mobile application, which will undoubtedly help to give a better understanding of user behavior and the true e ectiveness of the proposed approach.