《电子商务 E-business》阅读文献：interactive assessment of user preference models the automated travel assistant

Interactive assessment of user preference models: The automated Travel assistant Greg Linden, Steve Hanks, Neal Lesh Department of Computer Science and Engineering, University of Washington, Seattle, WA, USA Abstract: This paper presents the candidate/critique model of interactive problem solving, which an automated problem solver communicates candidate solutions to the user and the user critiques those solutions. The system starts with minimal information about the user's preferences, and preferences are elicited and inferred incrementally by analyzing the critiques. The system's goal is to present"good"candidates to the user, but to do so it must learn as much as possible about his preferences in order to improve its choice of candidates in subsequent iterations. This system contrasts with traditional decision- analytic and planning frameworks in which a complete model is elicited beforehand or constructed by a human expert. The paper presents the Automated Tranel Assistant, an implemented prototype of the model that interactively builds flight itineraries using real ime airline information. The ata is available on the world wide web and has had over 4000 users between May and October 1996 1 Introduction Building an accurate user model is essential to decision making and decision-support tasks,a model of the user s preferences is required to make good decisions or to suggest good alternatives. Representations for preference models have been studied extensively in the literature on multi-attribute utility theory (e.g. Keeney and Raiffa, 1976), which provides compact representations and elicitation techniques for preference models, but generally assumes that the model is built by a human expert. Problem solvers like Al planning algorithms generall assume that the complete preference model is provided as an input, but this is not a good approach to interactive problem solving in complex domains. Ahead-of-time elicitation demands a tremendous amount of information from the user, most of which will be irrelevant to solving the particular problem at hand. An alternative approach has been to infer a user model automatically over multiple interactions with the user that is used to support decision making and information filtering(e.g. Thomas and Fischer, 1996, McCalla et al., 1996, and Mukhopadhyay nd Mostafa, 1996). But, there is also a class of problems for which a user model must be built up quickly and without previous problem-solving episodes, thus requiring the direct participati of the user. Consider, for example, the following interaction between a travel agent and a client This work was supported in part by ARPA/Rome Labs grant F30602-95-1-0024. Thanks to Oren Etzioni, Dan Weld, Adam Carlson, Marc Friedman, Keith Golden, Nicholas Kushmerick, and the anonymous reviewers for good comments and suggestion

Interactive Assessment of User Preference Models: The Automated Travel Assistant Greg Linden, Steve Hanks, Neal Lesh * Department of Computer Science and Engineering, University of Washington, Seattle, WA, USA Abstract: This paper presents the candidate/critique model of interactive problem solving, in which an automated problem solver communicates candidate solutions to the user and the user critiques those solutions. The system starts with minimal information about the user’s preferences, and preferences are elicited and inferred incrementally by analyzing the critiques. The system’s goal is to present “good” candidates to the user, but to do so it must learn as much as possible about his preferences in order to improve its choice of candidates in subsequent iterations. This system contrasts with traditional decision￾analytic and planning frameworks in which a complete model is elicited beforehand or is constructed by a human expert. The paper presents the Automated Travel Assistant, an implemented prototype of the model that interactively builds flight itineraries using real￾time airline information. The ATA is available on the World Wide Web and has had over 4000 users between May and October 1996. 1 Introduction Building an accurate user model is essential to decision making and decision-support tasks; a model of the user' s preferences is required to make good decisions or to suggest good alternatives. Representations for preference models have been studied extensively in the literature on multi-attribute utility theory (e.g. Keeney and Raiffa, 1976), which provides compact representations and elicitation techniques for preference models, but generally assumes that the model is built by a human expert. Problem solvers like AI planning algorithms generally assume that the complete preference model is provided as an input, but this is not a good approach to interactive problem solving in complex domains. Ahead-of-time elicitation demands a tremendous amount of information from the user, most of which will be irrelevant to solving the particular problem at hand. An alternative approach has been to infer a user model automatically over multiple interactions with the user that is used to support decision making and information filtering (e.g. Thomas and Fischer, 1996, McCalla et al., 1996, and Mukhopadhyay and Mostafa, 1996). But, there is also a class of problems for which a user model must be built up quickly and without previous problem-solving episodes, thus requiring the direct participation of the user. Consider, for example, the following interaction between a travel agent and a client: ——— * ———— This work was supported in part by ARPA/Rome Labs grant F30602-95-1-0024. Thanks to Oren Etzioni, Dan Weld, Adam Carlson, Marc Friedman, Keith Golden, Nicholas Kushmerick, and the anonymous reviewers for good comments and suggestions

Client:"I want to fly from Seattle to Newark next Tuesday afternoon .gent:"Ive got a United flight at 3: 30pm for $500 and an American flight at 12:30 pm for$520. Client:"I cant leave before 3: 00pm but I do prefer American gent:"I have another American flight through Denver at 4: 00pm for $530 lient:"Thats pretty expensive. I'd be willing to go on a later flight or another airline if it 'd be much cheaper ent:"The cheapest flight is US Air at 8pm for $490 Client: "In that case the american flight is fine Figure 1: Example dialogue between a travel agent and client. Note that as the interaction progresses, the travel agent learns more and more about the client 's preferences. The travel agent learns that the client prefers to fly on American Airlines, is somewhat price-sensitive, and has both hard and soft time constraints. Additionally, the client preferences are rather complex and reflect complicated tradeoffs between cost of the flight, airline, and departure time. Our system aspires to this sort of interaction, where the system provides information about available options and the user provides information about the quality of those options. The systems user model and thus the quality of the proposed options improves over time, ultimately resulting in an option that is acceptable to the user. We consider a specific class of these models called candidate/critique, in which communication from the system is in the form of candidate solutions to the problem, and communication from the user is in the form of critiques of those solutions The main goal of the system is to present the user with an"acceptable" solution, but to de he candidate critique agent(CCA)must balance several competing needs. First, the CCa must attempt to display the optimal solution available in the dataset by suggesting optimal and near optimal solutions based on its current model of the users preferences. Second, the CCA must try to elicit and refine the user model. This may involve displaying"bad" candidates; the critique of bad candidate can indicate which attributes are the most important. Third, the CCa must also escribe the range of available solutions in the dataset to the user. Note, in the above interaction, that the client does not accept the optimal solution as soon as it is presented but only after he is convinced that it is the optimal solution by being told that the cheapest possible flight is $490 c In this paper, we present a general framework for building candidate/critique agents and we escribe the implemented Automated Travel Assistant(ATA) system, a CCA for assisting users with planning airline travel that provides real, current information from the Internet Travel Network world wide web service. In a typical interaction with ATA, the user initially provides some preferences over itineraries- perhaps only the departure and destination cities and the pproximate dates of travel -an that satisfy those preferences. After examining the itineraries offered by the system, the user notes favorable or

Client: “I want to fly from Seattle to Newark next Tuesday afternoon.” Agent: “I’ve got a United flight at 3:30pm for $500 and an American flight at 12:30pm for $520.” Client: “I can’t leave before 3:00pm but I do prefer American.” Agent: “I have another American flight through Denver at 4:00pm for $530.” Client: “That’s pretty expensive. I’d be willing to go on a later flight or another airline if it’d be much cheaper.” Agent: “The cheapest flight is USAir at 8pm for $490.” Client: “In that case, the American flight is fine.” Figure 1: Example dialogue between a travel agent and client. Note that as the interaction progresses, the travel agent learns more and more about the client’s preferences. The travel agent learns that the client prefers to fly on American Airlines, is somewhat price-sensitive, and has both hard and soft time constraints. Additionally, the client’s preferences are rather complex and reflect complicated tradeoffs between cost of the flight, airline, and departure time. Our system aspires to this sort of interaction, where the system provides information about available options and the user provides information about the quality of those options. The system’s user model — and thus the quality of the proposed options — improves over time, ultimately resulting in an option that is acceptable to the user. We consider a specific class of these models called candidate/critique, in which communication from the system is in the form of candidate solutions to the problem, and communication from the user is in the form of critiques of those solutions. The main goal of the system is to present the user with an “acceptable” solution, but to do so, the candidate critique agent (CCA) must balance several competing needs. First, the CCA must attempt to display the optimal solution available in the dataset by suggesting optimal and near￾optimal solutions based on its current model of the user’s preferences. Second, the CCA must try to elicit and refine the user model. This may involve displaying “bad” candidates; the critique of a bad candidate can indicate which attributes are the most important. Third, the CCA must also describe the range of available solutions in the dataset to the user. Note, in the above interaction, that the client does not accept the optimal solution as soon as it is presented but only after he is convinced that it is the optimal solution by being told that the cheapest possible flight is $490. In this paper, we present a general framework for building candidate/critique agents and we describe the implemented Automated Travel Assistant (ATA) system 1 , a CCA for assisting users with planning airline travel that provides real, current information from the Internet Travel Network world wide web service. In a typical interaction with ATA, the user initially provides some preferences over itineraries — perhaps only the departure and destination cities and the approximate dates of travel — and the system provides several itineraries that satisfy those preferences. After examining the itineraries offered by the system, the user notes favorable or ——— 1 ———— Available at http://www.cs.washington.edu/homes/glinden/TravelSoftBot/ATA.html

unfavorable characteristics. The system responds to the user's actions, offering new flight information, and the interaction continues until the user finds a satisfactory itinerary Many tasks besides making travel plans fit the candidate/critique model, such as assisting people find information on the Web, selecting merchandise, or graphical layout problems where the person is searching for the layout which best satisfies their preferences The contributions of this paper are an exploration of the use of candidate/critique models to elicit and refine user models, the design and implementation of a complete system for performing candidate/critique interactions in a travel domain, and four techniques that are effective in improving these interactions. These techniques are incorporating default preferences into the user model, suggesting trips that lie on the extreme spectrum of available trips(e.g. the cheapest trip) introducing variety into the suggested trips based on a definition of when one trip is significantly different than another, and a criterion for determining when one trip is dominated by another The rest of this paper is organized as follows. In 2, we give a formal problem specification and discuss the abstract candidate/critique model, then in 3 we describe the design of our CCA, including the four techniques mentioned above. In 4, we briefly describe the Automated Travel ssistant system, a prototype CCA, and discuss an extended example of how a typical interaction between a person and our system. In 5, we discuss related work. In 6, we discuss future work, We conclude and summarize in 7 2 Problem Specification In this section, we first discuss the candidate/critique model in general, define key terms and present simplifying assumptions, describe our user model, and specifying the input/output of the CCA agent 2.1 General Architecture We ultimately aspire to produce automated decision support systems that produce dialogues like the hypothetical interaction between travel agent and user presented in 1. In that case, a free-form natural-language dialogue allows solution information to be communicated concisely from the system to the user and allows arbitrary information about the user's preferences to be communicated from user to system Ithough we do not attempt to implement a natural language inter face, we would still like to capture the essence of this problem-solving process. In these problems, the system has access to a large dataset and problem-solving methods unavailable to the user. The user has access to preference information not directly available to the system. The basic mode of interaction is iterative and cooperative, where the system and the user both attempt to convey only relevant knowledge. The problem is considered solved when the user is presented with a solution he considers acceptable A candidate/critique agent(CCA) implements this style of problem solving but restricts the way in which information is communicated between the agent and the user. The agent presents a short, carefully selected list of candidate solutions to the user. The user responds by either accepting one of these options, or by critiquing one or more of them. Critiques provide additional information about the user s actual preferences, which in turn lead to new and better candidates

unfavorable characteristics. The system responds to the user’s actions, offering new flight information, and the interaction continues until the user finds a satisfactory itinerary. Many tasks besides making travel plans fit the candidate/critique model, such as assisting people find information on the Web, selecting merchandise, or graphical layout problems where the person is searching for the layout which best satisfies their preferences. The contributions of this paper are an exploration of the use of candidate/critique models to elicit and refine user models, the design and implementation of a complete system for performing candidate/critique interactions in a travel domain, and four techniques that are effective in improving these interactions. These techniques are incorporating default preferences into the user model, suggesting trips that lie on the extreme spectrum of available trips (e.g. the cheapest trip), introducing variety into the suggested trips based on a definition of when one trip is significantly different than another, and a criterion for determining when one trip is dominated by another. The rest of this paper is organized as follows. In 2, we give a formal problem specification and discuss the abstract candidate/critique model, then in 3 we describe the design of our CCA, including the four techniques mentioned above. In 4, we briefly describe the Automated Travel Assistant system, a prototype CCA, and discuss an extended example of how a typical interaction between a person and our system. In 5, we discuss related work. In 6, we discuss future work,. We conclude and summarize in 7. 2 Problem Specification In this section, we first discuss the candidate/critique model in general, define key terms and present simplifying assumptions, describe our user model, and specifying the input/output of the CCA agent. 2.1 General Architecture We ultimately aspire to produce automated decision support systems that produce dialogues like the hypothetical interaction between travel agent and user presented in 1. In that case, a free-form natural-language dialogue allows solution information to be communicated concisely from the system to the user and allows arbitrary information about the user’s preferences to be communicated from user to system. Although we do not attempt to implement a natural language interface, we would still like to capture the essence of this problem-solving process. In these problems, the system has access to a large dataset and problem-solving methods unavailable to the user. The user has access to preference information not directly available to the system. The basic mode of interaction is iterative and cooperative, where the system and the user both attempt to convey only relevant knowledge. The problem is considered solved when the user is presented with a solution he considers acceptable. A candidate/critique agent (CCA) implements this style of problem solving but restricts the way in which information is communicated between the agent and the user. The agent presents a short, carefully selected list of candidate solutions to the user. The user responds by either accepting one of these options, or by critiquing one or more of them. Critiques provide additional information about the user' s actual preferences, which in turn lead to new and better candidates

The format of both candidate solutions and critiques will depend on the details of the particular problem domain. In their most general forms, preferences can amount to an explici total order over all candidate solutions, and critiques would be a pairwise comparison between two candidates where nothing more could be inferred about the user's preference ordering. The model is intractable and unrealistic in its full generality, however, so we present a common pecial case below We conclude this discussion of the abstract CCA model by posing the questiss on criteria. evaluation: what constitutes a good CCA problem solver? We consider two evaluation criteria First, the CCa should lead the user to find an acceptable solution quickly. Second, the CCa should lead the user to find a solution that has high quality relative to the users preferences This second criterion might be considered controversial because it is only necessary if the user sometimes accepts a low quality solution 2.2 Terms and Assumptions In this section, we introduce the particular simplified model of the general CCA architecture. In this model, the domain can be described using attribute/value pairs, preferences can be described using soft constraints over these attributes, and preferences over constraint violations are additive Problem domains are commonly defined using a predefined set of attributes A each of which takes on values from an underlying set dom(Ai=(vi, l,Vi,2,_Vik). In this case,a candidate solution can be described using a tuple of the form(V1, V2,, vn). For example, in the travel domain, the dataset might describe all currently available flights and each flight might be represented by a set of attributes including the cost of the flight, airline, departure and arrival cities. and time and date of travel We describe the user's preferences in terms of soft constraints on the values of attributes. A onstraint is a function C(v): dom(A -[0, 1. We use the convention that Ci(v)=0 means the constraint is fully satisfied and Ci(v)=l means the constraint is fully unsatisfied. Values in the open interval represent partial satisfaction of the constraint. An assumption we make that is not inherent to the candidate/critique model, but does make the problem more tractable, is that the preferences are additive independent( Keeney and Raiffa, 1976), meaning that preferences over the individual attributes do not depend on the level at which the other attributes are achieved. For example, we would assume a person's preferences over price(e.g. the person strongly prefers cheaper flights) do not depend on whether or not the flight is a nonstop or how close to the desired arrival time it lands 2.3 User model The purpose of the user model is to describe a persons preferences over a set of solutions. In the most general form, the preferences can be arbitrary formulas that impose a total order over solutions. Under the assumption of additive independence, we can represent the user's preference over candidate tuples as a weighted sum of constraint functions. The user model consists of a set of constraints and a weighting indicating the importance of each constraint. Formally, the user model is a pair (C1. Cn,( w1,,Wn)) where Ci is a constraint and wi is the weight, a real The actual definition of additive independence is slightly stronger, but this does not affect our analysis

The format of both candidate solutions and critiques will depend on the details of the particular problem domain. In their most general forms, preferences can amount to an explicit total order over all candidate solutions, and critiques would be a pairwise comparison between two candidates where nothing more could be inferred about the user’s preference ordering. The model is intractable and unrealistic in its full generality, however, so we present a common special case below. We conclude this discussion of the abstract CCA model by posing the question of evaluation: what constitutes a good CCA problem solver? We consider two evaluation criteria. First, the CCA should lead the user to find an acceptable solution quickly. Second, the CCA should lead the user to find a solution that has high quality relative to the user’s preferences. This second criterion might be considered controversial because it is only necessary if the user sometimes accepts a low quality solution. 2.2 Terms and Assumptions In this section, we introduce the particular simplified model of the general CCA architecture. In this model, the domain can be described using attribute/value pairs, preferences can be described using soft constraints over these attributes, and preferences over constraint violations are additive. Problem domains are commonly defined using a predefined set of attributes A1 , A2 , _, An , each of which takes on values from an underlying set dom(Ai ) = {vi,1 , vi,2 , _, vi,k}. In this case, a candidate solution can be described using a tuple of the form (v1 , v2 , _, vn ). For example, in the travel domain, the dataset might describe all currently available flights and each flight might be represented by a set of attributes including the cost of the flight, airline, departure and arrival cities, and time and date of travel. We describe the user’s preferences in terms of soft constraints on the values of attributes. A constraint is a function Ci (v): dom(Ai ) → [0,1]. We use the convention that Ci (v) = 0 means the constraint is fully satisfied and Ci (v) = 1 means the constraint is fully unsatisfied. Values in the open interval represent partial satisfaction of the constraint. An assumption we make that is not inherent to the candidate/critique model, but does make the problem more tractable, is that the preferences are additive independent (Keeney and Raiffa, 1976), meaning that preferences over the individual attributes do not depend on the level at which the other attributes are achieved. For example, we would assume a person’s preferences over price (e.g. the person strongly prefers cheaper flights) do not depend on whether or not the flight is a nonstop or how close to the desired arrival time it lands. 2 2.3 User Model The purpose of the user model is to describe a person’s preferences over a set of solutions. In the most general form, the preferences can be arbitrary formulas that impose a total order over solutions. Under the assumption of additive independence, we can represent the user’s preference over candidate tuples as a weighted sum of constraint functions. The user model consists of a set of constraints and a weighting indicating the importance of each constraint. Formally, the user model is a pair ({C1..Cn}, {w1,..,wn}) where Ci is a constraint and wi is the weight, a real ——— 2 ———— The actual definition of additive independence is slightly stronger, but this does not affect our analysis

number in [0, 1], of constraint Ci. A user model provides a partial ordering over all solutions. We will call this the error of the candidate solution which is of the form E(v1,V2→vn)=∑Civi)*w Note that assuming additive independence simplifies the model specification, reducing it to n oft constraints and n weighting coefficients, and simplifies the notion of what a critique is. If the assumption holds, the quality of a candidate solution can be incorrectly computed for only one of two reasons: either the soft constraint for one of the attributes is incorrect, or one of the attributes is weighted improperly. In our implementation in the travel domain, the user is allowed to adjust both of these model parameters directly A user model can either completely or partially describe a user's preferences. In our system the user model initially describes only a few of the user's preferences. As weights are adjusted or constraints are added or updated, the user model becomes a more accurate reflection of the users true preferences 2.4 Candidate/Critique Interaction In this section, we describe the interaction between a candidate/critique agent and a user and specify the input/output behavior of the CCa On each iteration, the CCA uses the current user model to suggest a set of annotated olutions. In our implementation, a solution is annotated if it has the best value in a particular attribute of all the candidate solutions with respect to the current user model. For example, in the travel domain, the cheapest trip of all trips considered by the system would be labeled cheapest". Formally, the CCa is a function from a partial user model and a set of solutions to a small set of suggested solutions. The system calls the CCa with the current user model, and then presents the suggested solutions After a set of solutions has been suggested the user can either choose one and end the interaction, or add a new constraint, modify an existing constraint, or adjust the weighting of a constraint. This can be accomplished, as in our implementation, though the use of a graphical user interface that allows the user to critique the solutions suggested by the CCA. After the user critiques the suggested candidates, the CCa is called with the updated user model, which results n a new set of solutions being suggested 3 CCA Design In this section we first discuss general design principles of a CCA and then describe four general- purpose techniques for building CCA. In the process of describing these techniques, we show how we instantiated them within the travel domain In our implementation, five solutions are suggested in each iteration

number in [0,1], of constraint Ci . A user model provides a partial ordering over all solutions. We will call this the error of the candidate solution, which is of the form E((v1 , v2 , _, vn )) = i = 1 n ∑ Ci (vi )*wi Note that assuming additive independence simplifies the model specification, reducing it to n soft constraints and n weighting coefficients, and simplifies the notion of what a critique is. If the assumption holds, the quality of a candidate solution can be incorrectly computed for only one of two reasons: either the soft constraint for one of the attributes is incorrect, or one of the attributes is weighted improperly. In our implementation in the travel domain, the user is allowed to adjust both of these model parameters directly. A user model can either completely or partially describe a user’s preferences. In our system, the user model initially describes only a few of the user’s preferences. As weights are adjusted or constraints are added or updated, the user model becomes a more accurate reflection of the user’s true preferences. 2.4 Candidate/Critique Interaction In this section, we describe the interaction between a candidate/critique agent and a user and specify the input/output behavior of the CCA. On each iteration, the CCA uses the current user model to suggest a set of annotated solutions. In our implementation, a solution is annotated if it has the best value in a particular attribute of all the candidate solutions with respect to the current user model. For example, in the travel domain, the cheapest trip of all trips considered by the system would be labeled as “cheapest”. Formally, the CCA is a function from a partial user model and a set of solutions to a small set 3 of suggested solutions. The system calls the CCA with the current user model, and then presents the suggested solutions. After a set of solutions has been suggested the user can either choose one and end the interaction, or add a new constraint, modify an existing constraint, or adjust the weighting of a constraint. This can be accomplished, as in our implementation, though the use of a graphical user interface that allows the user to critique the solutions suggested by the CCA. After the user critiques the suggested candidates, the CCA is called with the updated user model, which results in a new set of solutions being suggested. 3 CCA Design In this section we first discuss general design principles of a CCA and then describe four general￾purpose techniques for building CCA. In the process of describing these techniques, we show how we instantiated them within the travel domain. ——— 3 ———— In our implementation, five solutions are suggested in each iteration