next up previous
Next: Conversing with the User Up: The ADAPTIVE PLACE ADVISOR Previous: The User Model

   
The Retrieval Engine

Once in place, the user model affects the behavior of the system through the Retrieval Engine, which interacts with a database to retrieve the items, if any, that satisfy the currently agreed upon constraints. This module also interacts with the query to determine how similar those items are to the user's preferences and to determine the best ordering of the attributes for constraining or relaxing, as appropriate. Both types of interactions with the user model support the goal of quickly narrowing down the search for a satisfactory item. Similar to the way a human advisor bases assumptions regarding the inquirer on their previous interactions, our system uses its cumulative experience, reflected in the user model, as a basis for its computation. The Retrieval Engine represents the user's preferences and requirements in the expanded query, a partial, probabilistic item specification determined by both the conversation and the user model. The query is initialized from the user model, and thus contains preference-based probabilities for the attributes and values the user has not yet explicitly specified along with the user's item preferences. In the course of the conversation, the system updates the query to reflect the values the user specifies. For each attribute, it sets the ``probability'' for each value agreed upon in the conversation to 1.0, and all other probabilities to zero. For example, if the user says ``Chinese or Italian,'' the system sets the value probabilities for both Chinese and Italian to 1.0, and all other cuisine probabilities to zero. This is equivalent to a disjunction of probabilistic queries, one for each value combination specified by the user.5 The first main aspect of the Retrieval Engine that is personalized is its item ranking technique. Unlike a typical case-based similarity computation, which retrieves items beyond those that match a query exactly, the computation used by the system restricts the retrieved items to those most desirable to the user. The system filters the items to be included in the current case base according to the characteristics explicitly specified by the user and sorts the remaining items according to their similarity to items the user liked in the past. Thus, the Engine first queries the database to retrieve all items that match the current constraints exactly.6 Then, the PLACE ADVISOR uses the probability distributions in the query to compute how likely the user is to choose an item. The system calculates the similarity between the current query, Q, and an item, I using

\begin{displaymath}Sim(Q,I) = R_I \times \sum_{j=1}^{n} w_j \times P(V_j) ~ ,
\end{displaymath}

where RI is the user's item preference ratio for item I, n is the number of attributes, wj is the weight of attribute j in Q, Vj is the value of attribute j in I, and P(Vj) is the value preference (probability in Q) for this value. Similarity in this formula is based on the user model and the search state. Thus, for each unconstrained attribute, it estimates the probability that the user will accept the item's value for that attribute. Once the system calculates the similarity of each item, it compares an item's similarity to a constant similarity threshold, and only retains those items that exceed the threshold. The second main personalized aspect of the Retrieval Engine is its ranking of attributes in under- and over-constrained situations. This helps assure that the user is more likely to respond informatively to the system's questions in under-constrained situations, and to allow the suggested attribute to be relaxed in over-constrained situations. For both situations, one option is to order attributes randomly, which is a technique used in some simple dialogue systems. Another option is to use a conditional entropy measure to select attributes (see Section 6.1). A third is to rank attributes in order by their desirability to the user, as reflected in the user model, and we take this option. In addition to using the long term user model to rank attributes, the system also uses the attribute weights that are reflected in the query. We will see see later that the query's attribute weights, while initialized from the user model, are also influenced by the conversation. In an over-constrained situation, the attribute ranking order is from highest to lowest, and in an under-constrained situation, it is the reverse.7 Using the attribute weights rather than the conditional entropy avoids pitfalls that arise from the continuously changing value distribution in the data (new restaurants, restaurants going out of business, etc.). If this did affect attribute rankings, the users may be confused by the resulting variability. But even worse, it would not reflect the user's preferences. Further, not every question that has a high information gain is of high relevance for a user selecting a destination (e.g., ``parking options'' may have a very high score but should only be asked after the user has decided on cuisine and location.) In summary, the user model influences item retrieval, item ranking, and attribute ranking, which in turn influence the system's utterances during the conversation.
next up previous
Next: Conversing with the User Up: The ADAPTIVE PLACE ADVISOR Previous: The User Model
Cindi Thompson
2004-03-29