3.1 Domain and task

The domain of our system is physical exercise. The system is set up as an exercise advisor that asks the user what is preventing him/her from exercising more. After the user has worded his/her exercise barrier, the system will provide motivational advice for how to overcome this barrier. The main task of the system is to successfully identify the user's exercise barrier and provide appropriate, satisfactory advice. As an illustration, Figure 1 shows a sample dialogue with the system. In this particular conversation, the system first greets the user and immediately asks the user's name. The motivation behind this is that we can use the name in subsequent system prompts in order to personalize the dialogue. The next question (4) continues building a trusting relationship by suggesting that the system cares about the user. The system then prompts the main question of the dialogue (7). After the user has formulated his exercise barrier, it is classified by the system. Subsequently, the system asks the user to confirm the correctness of its classification (9). The system then presents (one of the) pre-defined solutions for the relevant exercise barrierFootnote ¹ and verifies its usefulness with the user. Finally, the system closes with an encouragement (14).

Fig. 1.

A sample dialogue with the exercise advisor.

3.2 System architecture and process flow

This section gives a global view of the system's main components and how they work together. Figure 2 shows a block diagram representation of the system's overall concepts and its main process flow. Note that the system lacks a speech-recognition component: both the system's input channel and output channel are text based. The user types his/her utterances in a text box at the bottom of a simple graphical interface. The system utterances appear in a larger, central text boxFootnote ².

Fig. 2.

A block diagram showing the process flow of the dialogue system. After the user types an utterance (1), the dialogue manager (DM) sends it to the parser/classifier (2) which assigns a category. In some cases, information is extracted from the utterance (3). The DM then looks up the possible next actions (4) in the dialogue component library (DCL). Subsequently, the DM lets the policy decide which action should be taken (5) and performs it. The next system utterance is then presented to the user (6).

The dialogue system is set up in a client--server architecture (multiple clients can be served at the same time). The central component of the server is the dialogue manager. After a user utterance is sent to the server, the dialogue manager sends it to the utterance parser and classifier (see Section 3.5 for a detailed description). Depending on the state, the utterance will then be sent to an extraction module, which uses simple rules to extract information like the user's name (see, for example, utterance 3 and 4 in Figure 1). The category assigned by the classifier, representing the user's reaction, forms the first step in determining the continuation of the dialogue. That is, given this category, the dialogue manager can look up the possible next action(s) that the system can take in the current state of the dialogue. This information resides in the DCL, which contains the full dialogue structure and all system utterances, encoded in various interconnected dialogue components (see Section 3.4 for an extensive description of the DCL). In the second step, the dialogue manager decides which of these possible actions will actually be performed (see Section 3.3 for a detailed explanation of how this is done). Finally, the dialogue state is updated and the dialogue is continued by presenting the next system utterance to the user.

3.3 State/action management

The dialogue state is unique at every stage of the dialogue and is represented as a vector of feature values. We use only a limited set of features because, as also noted in Singh et al. (Reference Singh, Litman, Kearns and Walker2002) and Levin et al. (Reference Levin, Pieraccini and Eckert2000), it is important to keep the state space as small as possible (but with enough distinctive power to support learning) so we can construct a non-sparse Markov decision process (see Section 5) based on our limited training dialogues. The state features we used are listed in Table 1. We should note here that we did not empirically compare the effects of each individual feature on policy learning, nor did we experiment with other features than the ones listed in Table 1. As Tetreault and Litman (Reference Tetreault and Litman2006) show, incorporating more or different information into the state representation might, however, result in different policies.

Table 1.

Features for dialogue state representation

As already mentioned in the previous section, in each state of the dialogue the dialogue manager looks up the possible next action(s) that can be performed. In our system, an action is either a system utterance or a transition to another nodeFootnote ³ in the dialogue structure (see Section 3.4). Dialogue states in which the system can choose among several possible actions are called choice states. For example, immediately after greeting the user, our system's dialogue structure allows for different directions: the system can first try to build a trusting relationship with the user by asking some personal questions, or it can immediately jump to the main question of the dialogue without any digressions. Utterance actions may also require a choice (e.g. using a directive versus an open formulation of a certain question). Both the structural and the prompt choices are governed by the same mechanism: the dialogue manager decides which of the possible actions in a certain state will be performed by following the next steps:

1. (a) there is only one possible action a _k:

   • → a _k is performed;

2. (b) there are more than one possible actions {a ₁,. . .,a _i}:

   • → the system is running in random mode: the dialogue manager chooses an action from {a ₁,. . .,a _i} randomly;

   • → the system is running in policy mode: the dialogue manager performs the action that is prescribed by the dialogue policy.

3.4 Dialogue structure and component library

The DCL contains generic as well as task-specific dialogue content. Table 2 lists all components of the library that were used in our system. The DCL encodes both the dialogue content and the dialogue structure.

Table 2.

Components in the dialogue component library

A dialogue component is basically a coherent set of dialogue nodes with a certain dialogue function, i.e., a subgraph of the complete dialogue structure. The library is set up in a flexible, generic way: new components can easily be plugged in to test their usefulness in different dialogue contexts. Note that the dialogue components need to be constructed and linked to other components manually. More specifically, in this architecture, a dialogue system engineer first designs the basic dialogue components (e.g. relation building or small talk subdialogues, entertaining parts, confirmation loops). Each component has an entry node and an exit node (which can be the same, if the component is of a single node). An outgoing link (transition) of a node can only point to another node of the same component or the entry node of another component. The way the nodes (and the dialogue components) are interconnected thus determines the structure of the dialogue.

A dialogue node represents one or more actions. In our system, an action is either a system utterance or a transition to another node in the dialogue structure. For the sake of clarity, Figure 3 shows the XML encoding of one of the nodes in our DCL. This particular node, representing the core question of the dialogue, contains two actions (Action element): one of type utterance, and one of type transition. The utterance action contains one utterance (encoded in the Utterance element). The value of the turn property denotes that after this system utterance is presented, the turn will be given to the user. The utterance action element contains multiple Template elements. This means that for this utterance, the system can make a choice from several different formulations (in this case a directive formulation, a directive formulation that also prepares the user for what the system will do next and an open formulation). After the choice is made and the action is performed, the system will classify the user's reaction. The assigned category (called trigger in the XML) is then used to select one of the Transition elements in the transition action block. For example, in Figure 3, the first transition is selected if the user actually formulates an exercise barrier, the second transition is selected if the user refuses to cooperate and so on). The first transition contains two NextNode elements. Again, this means that the system has to make a choice. In this case, the system's options are to first confirm the detected exercise barrier with the user before proposing a solution, or to assume that the detected barrier is correct and immediately give a solution for that barrier. For the other three ‘user reaction categories’, only one possible NextNode is defined, so in those cases, the proper action to take is clear.

Fig. 3.

XML encoding of a dialogue node (containing the exercise barrier question).

Let us now explain the relation between states and nodes in our architecture. In Figure 3, just before the system chooses from the options of the first action, it has a certain dialogue state s ₁. This state s ₁ therefore is a choice state. Immediately after the system performed the first action (including user utterance classification), the dialogue state changes to s ₂. However, the system is still on the same node in the dialogue structure. Then, after performing the transition action, the dialogue state changes to s ₃ and the system visits another node in the dialogue structure. So, after each action, the dialogue state s _i changes to the next state s _i+1, but only after performing a transition action, the system also jumps to another node.

The dialogue structure for our exercise advisor was designed carefully, so that each possible combination of choices made in the choice states results in a sensible dialogue. We also defined ‘fixed’ actions that occur in all dialogues because they are essential for task completion (e.g. asking the exercise barrier, giving a solution, closing the session).

3.5 Utterance parsing and classification

The type of reasoning embodied in the user utterance classifier is memory based. The basic idea behind this family of algorithms is that new cases can be treated like known cases that are similar (see, e.g. Daelemans and van den Bosch Reference Daelemans and van den Bosch2005) for an extensive overview of memory-based learning algorithms. When a user utterance is sent to the parser/classifier, it is transformed to a vector of feature values and matched against a fixed set of examples stored in memory. The most similar training instances (nearest neighbours) are returned and the classification of the user utterance is based on their labels.

The classifier uses a rich set of features for accurate user utterance classification including words, phrases, regular expressions, domain-specific word-relations and syntactically motivated expressions. For parsing we used a memory-based shallow parser called MBSP (Daelemans, Buchholz and Veenstra Reference Daelemans, Buchholz and Veenstra1999). This parser provides part of speech labels, chunk brackets and subject–verb–object relations. We extended the parser with negation scope and clause boundary detection. As an illustration, Table 3 contains the parser's output for the utterance ‘I do not have the right gear’.

Table 3.

Output of the parser for the utterance ‘I do not have the right gear’

The columns respectively contain the utterance tokens, their part-of-speech tags, chunk tags, prepositional noun phrase tags, subject–verb–object relations, negation scope tags, clause boundary tags, subject strings, vp strings, and object strings.

Given such a parse, the feature-matching mechanism of the classifier can match terms or phrases at specified positions in the token stream of the utterance, also in combination with syntactic and semantic class labels. This allows us to define features that are particularly useful for resolving confusing linguistic phenomena like ambiguity and negation (see Section 3.5.1). A base feature set was generated automatically, but quite a number of features were manually tuned or added to cope with certain common dialogue situations.

3.5.2 Vocabulary expansion by hypernym mapping

The parser has access to a handmade taxonomy of domain-specific hyponym–hypernym relations which functions as a vocabulary expansion mechanism. The taxonomy can contain any category of related words. As an illustration, Figure 4 shows some example relations from the taxonomy that was set up for our exercise advisor. So, when a user utterance contains a word that is unknown in the training data, let's say ‘arthritis’, it can be matched to semantically similar training instances by defining it in the taxonomy. Thus, the user utterance ‘I have arthritis’ will be generalized to ‘I have health problems (long-term)’. In essence, expanding the taxonomy with new words has the same effect as expanding the training set, but it does not require retraining of the classifier.

Fig. 4.

Example relations from the exercise advisor's hyponym–hypernym taxonomy.

4.1 The reward model

When a dialogue has reached its final state, a survey is presented to the user for dialogue evaluation. The survey consists of five statements that can each be rated on a five-point Likert scale (Likert Reference Likert1932). The Likert scale is the most widely used response scale in survey research and traditionally a five-point scale is used. Test items are typically statements and respondents are asked to indicate their degree of agreement with these statements. The responses are usually strongly disagree, disagree, neither agree nor disagree, agree and strongly agree. We also used a five-point scale, but to keep the survey interface as simple as possible, we only put the indicators disagree and agree on the left and right side of the scale, respectively. Using a five-point scale rather than a three-point or seven- or nine-point scale gives us enough granularity, but on the other hand keeps the responses fairly consistent. The responses are mapped to rewards of −2 to 2 (the middle scale point is considered a neutral response and is mapped to a reward of 0). The statements we used are partly based on the user survey that was used in (Singh et al. Reference Singh, Litman, Kearns and Walker2002). We considered these statements to reflect the most important aspects of conversation that are relevant for learning a good dialogue policy. The five statements we used are listed in Figure 5.

Fig. 5.

The five evaluation measures in the dialogue survey.

4.2 Training subjects and set-up

Eight subjects carried out a total of 572 complete dialogues with the system. There were four-male and four-female subjects. All subjects were university students in their early twenties and fluent (four of them native) english speakers. They were paid a regular hourly fee and were completely unfamiliar with the research and the dialogue system.

Because of the variety of possible exercise barriers known by the system (fifty two in total) and the fact that some of these barriers are more complex or harder to detect than others, the system's classification accuracy depends largely on the user's barrier. To prevent classification accuracy distorting the user evaluations too much, we asked the subjects to act as if they had one of five pre-defined exercise barriers (shown in Figure 6).

Fig. 6.

The five pre-defined exercise barriers.

5.1 Markov decision processes

We follow past lines of research, such as Liven et al. and (Reference Levin, Pieraccini and Eckert2000) and Singh et al. (Reference Singh, Litman, Kearns and Walker2002), by representing a dialogue as a trajectory in the state space, determined by the system actions and user responses:

1. (1)

where means that the system performed action a _i in state s _i, receivedFootnote ⁵ reward r _i and changed to state s _i+1. In our system, a state is a dialogue context vector of feature values (see Section 3.3). This feature vector contains the available information about the dialogue so far that is relevant for deciding what action to take next in the current dialogue state. We want the system to learn the optimal decisions, i.e. to choose the actions that maximize the expected reward.

5.2 Q-value iteration

The field of reinforcement learning includes many algorithms for finding the optimal policy in an MDP (see Sutton and Barto, Reference Sutton and Barto1998 for an overview). Our objective is not to provide an extensive discussion or comparison of reinforcement learning algorithms. We applied the same algorithm as in Singh et al. (Reference Singh, Litman, Kearns and Walker2002), as their experimental set-up is similar to ours, constisting of: generation of (limited) exploratory dialogue data, using a training system; creating an MDP from these data and the rewards assigned by the training users; off-line policy learning based on this MDP.

The Q-function for a certain action taken in a certain state describes the total reward expected between taking that action and the end of the dialogue. For each state–action pair (s, a), we calculated this expected cumulative reward Q(s, a) of taking action a from state s, with the following equation (Sutton and Barto Reference Sutton and Barto1998; Singh et al. Reference Singh, Litman, Kearns and Walker2002):

1. (2)

where P(s′|s, a) is the probability of a transition from state s to state s′ by taking action a, and R(s, a) is the expected reward obtained when taking action a in state s. γ is the weight (0 ≤ γ ≤ 1) that discounts rewards obtained later in time when it is set to a value lower than 1. In our system, γ was set to 1. Equation (2) is recursive: the Q-value of a certain state is computed in terms of the Q-values of its successor states. The Q-values can be estimated to within a desired threshold using Q-value iteration (Sutton and Barto Reference Sutton and Barto1998), formally described in Figure 7. Once the value iteration process is completed, by selecting the action with the maximum Q-value (the maximum expected future reward) at each choice state, we can obtain the optimal dialogue policy π.

Fig. 7.

Q-value iteration.

6.1 Reward analysis

Figure 8 shows a graph of the distribution of the five different evaluation measures in the training data (see Figure 5 for the statement wordings). M1 is probably the most important measure of success. The distribution of this reward is quite symmetrical, with a slightly higher peak in the positive area. The distribution of M2 shows that M1 and M2 are related. From the distribution of M4 we can conclude that the majority of dialogues during the training phase were not very engaging. Users obviously had a good feeling about what they could say at each point in the dialogue (M3), which implies that the system prompts were of a good quality. The judgement about the usefulness of the provided advice is pretty average, tending a bit more to negative than to positive. We do think that this measure might be distorted by the fact that we asked the subjects to imagine that they have the given exercise barriers. Furthermore, they were sometimes confronted with advice that had already been presented to them in earlier conversations.

Fig. 8.

Reward distributions in the training data.

6.1.1 Dialogue length

In our analysis of the users' rewarding behaviour, we found several significant correlations. Table 4 contains a reward versus dialogue length (in number of turns of the user) distribution for each feedback statement (M1,. . .,M5). The cells of this table contain the percentage of dialogues of length l (the row) that got reward r (the column). Figure 9 shows the dialogue length distribution in the training corpus.

Table 4.

Relationship between dialogue length and given reward

Fig. 9.

Dialogue length distribution (in number of user turns).

In the distributions in Table 4, the independent variable (dialogue length) is collapsed to the category set short (l < 4 turns), medium (3 < l < 6) and long (l > 6). The dependent variable is collapsed to negative reward (< 0), neutral reward (0) and positive reward (> 0). We used chi ² to compute the significance levels of these distributions. The distributions for M1, M3, and M4 are significant at significance levels of 0.025, 0.001 and 0.01 respectively. All distributions show the same trend: longer dialogues are appreciated more than (very) short ones. This seems rather logical, as dialogues in which the user barely gets to say anything are not very natural or engaging.

6.1.2 Verification

Our intuition is that the choice of barrier verification is one of the most essential choices the system can make in the dialogue. The distributions in Table 5 show that it is much better to verify the detected barrier than to immediately give advice. The percentage of appropriate advice provided in dialogues with barrier verification is of course much higher than in dialogues without verification. All distributions in Table 5 are significant.

Table 5.

Relationship between verification of the exercise barrier and given reward

6.1.3 Directive versus open question

In several states of the dialogue, we let the system choose from different wordings of the system prompt. One of these choices is whether to use an open question to ask the user's barrier (How can I help you?) or a directive question (Tell me what is preventing you from exercising more.). The motivation behind the open question is that the user gets the initiative and is basically free to talk about anything he/she likes (Singh et al. Reference Singh, Litman, Kearns and Walker2002). The advantage of the directive question is that the chance of making classification errors is much lower than that with the open question. Furthermore, contrary to when the system uses the open question, the user will know what the system expects when it uses the directive question. Table 6 shows the relationship between question type and reward. All distributions are significant. Dialogues in which the key-question (asking the user's barrier) was directive were rewarded more positively than dialogues with the open question.

Table 6.

Relationship between question type and given reward

6.2 Learned dialogue policies

We learned a different policy for each evaluation measure separately (by only using the rewards given for that particular measure), and a policy based on the combination (sum) of the rewards for all evaluation measures. We found that the learned policy based on the combination of all measures, and the policy based on measure M1 alone (Overall, this conversation went well) were nearly identical. Table 7 compares the most important decisions of the different policies. For convenience of comparison, we only listed the main, structural choices.

Table 7.

Comparison of the most important decisions made by the learned policies

Note that, for the sake of clarity, the state descriptions in Table 7 are basically ‘summaries’ of a set of more specific states since a state is a specific representation of the dialogue context at a particular moment (composed of the values of the features listed in Table 1). For instance, in the p _a policy, the decision in the last row of the table (give a joke or not), depends on whether or not there has been a classification failure (i.e. a communication problem earlier in the dialogue). If there has been a classification failure, the policy prescribes the decision not to give a joke, as it was not appreciated by the training users in that context. Otherwise, if there were no communication problems during the conversation, the users did appreciate a joke. Figure 10 shows a typical dialogue that would be generated by either policy p ₁ or policy p _a, which we think are the most reliable policies.

Fig. 10.

Example dialogue generated by the learned policy. The action choices that are preceded by a checked box are prescribed by the policy in the given dialogue situation.

7.1 Comparison with an expert policy

We compared the learned dialogue policy with a policy which was independently hand designed by expertsFootnote ⁶ for this system. The decisions made in the learned strategy were very similar to the ones made by the experts, with only a few differences, indicating that the automated method would indeed perform as well as an expert. The main differences were the inclusion of a personal questionnaire for relation building at the beginning of the dialogue and a commitment question at the end of the dialogue. Another difference was the more restricted use of the humour element, described in Section 6.2 which turns out to be intuitively better than the expert's decision to simply always include a joke.

As some additional evidence against the possibility that the learned policy was generated by chance, we performed a simple experiment in which we took several random samples of 300 training dialogues from the complete training set. We learned a policy for each sample. We then mutually compared these policies and found that they were very similar: only in 15–20 percent of the states, the policies disagreed on which action to take next. On closer inspection we found that this disagreement mainly concerned states that were poorly visited (one to ten times) in these samples. These results suggest that the learned policy is unreliable at infrequently visited states. Note, however, that all main decisions listed in Table 7 are made at frequently visited states. The only disagreement in frequently visited states concerned system-prompt choices. We might conclude that these particular (often very subtle) system-prompt choices (e.g. careful versus direct formulation of the exercise barrier) are harder to learn than the more noticeable dialogue structure-related choices.

7.2 Empirical evaluation with real test users

Of course, we can only draw conclusions with regard to the effectiveness of the learned policy if we empirically compare it with the hand-designed policy in a test with human users. For this test, we ran the dialogue system in policy mode, i.e. the mode in which the system follows a given policy. For each dialogue, we let the system choose randomly between the expert policy and the learned policy. Eight subjectsFootnote ⁷ then performed the same five tasks used during training, resulting in 469 complete dialogues (229 based on the expert policy, 240 based on on the learned policy). After each dialogue, the subjects reviewed it by filling in the same survey used for training (see Section 4.1). Table 8 shows the reward distributions over the two policies for the five different evaluation measures (see Section 5). None of the distributions is significant, which implies that the two policies are comparable. For measures M1 (Overall, this conversation went well) and M4 (I found this conversation engaging), the given rewards are better for the learned policy, for M2 (The system understood what I said) the results are better for the expert policy. For M3 and M5 the rewards for the two policies are very similar. This empirical comparison indicates that the automatically learned dialogue policy performs at least as well as the manually constructed expert policy.

Table 8.

Relationship between policy (expert or learned) and given reward. The cells contain the percentage of dialogues with the reward of the concerning column (negative, neutral, positive), following the policy of the concerning row (expert or policy).