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
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: Conversing with the User
Up: The ADAPTIVE PLACE ADVISOR
Previous: The User Model
Cindi Thompson
2004-03-29