2.1 POMDP-based dialogue management

A POMDP is defined by a tuple 〈S, A, Z, T, O, R〉, where S is the set of states of the environment (usually called state space), A is the set of the agent's actions, Z is the set of observations the agent can experience of its environment, T is the state-transition function, O is the observation function, and R is the reward function.

In a dialogue management context (Figure 1), the agent is the system (i.e. the dialogue manager) and a part of the POMDP environment represents the user's state and user's action.Footnote ² Because the user's state cannot be directly observed, the system uses a state estimator (SE) to compute its internal belief (called belief state) about the current user's state and selects next action based on a policy π. The SE takes as its input the previous belief state, the most recent action, and the most recent observation, and returns an updated belief state. The policy π selects actions based on the system's current belief state. Two main tasks of the system are: computing belief states and finding an optimal dialogue policy. These two tasks are described in detail in Kaelbling, Littman and Cassandra (Reference Kaelbling, Littman and Cassandra1998).

Fig. 1.

Modularized view of the interaction between the SYSTEM and the USER in a dialogue management context.

2.2 Approaches

In this section, we focus on describing the POMDP-based dialogue management approaches. Reviews of other dialogue management approaches for spoken and multimodal dialogue systems are reviewed in McTear (Reference McTear2002 and Bui (Reference Bui2006), respectively.

In Section 2.1, we explained the basic activity of a POMDP-based dialogue management system. Young et al. (Reference Young, Williams, Schatzmann, Stuttle and Weilhammer2005) have argued that nearly all existing dialogue management systems, especially those based upon the information state approach (Traum and Larsson Reference Traum, Larsson, Kuppevelt and Smith2003), can be considered as direct implementations of the POMDP-based model with a deterministic (i.e. handcrafted) dialogue policy. These systems have a number of ‘severe weaknesses’ such as using unreliable confidence measures, having difficulty coping with the dynamic changing of the user's goal and intention. Moreover, tuning the dialogue policy is labor extensive, based on off-line analysis of the system logs (Young et al. Reference Young, Williams, Schatzmann, Stuttle and Weilhammer2005).

The first work that applies POMDP for the dialogue management problem was proposed by Roy et al. (Reference Roy, Pineau and Thrun2000) for building a nursing home robot application. In this application, a flat POMDP model is used where the states represent the user's intentions; the observations are the user's speech utterances; and the actions are the system responses. They show that the POMDP-based dialogue manager copes well with noisy speech utterances, for example their POMDP-based dialogue manager makes fewer mistakes than a MDP-based dialogue manager, and it automatically adjusts the dialogue policy when the quality of the speech recognition degrades. Zhang et al. (Reference Zhang, Cai, Mao and Guo2001) extended Roy's model in several dimensions: (1) a factored POMDP (Boutilier and Poole Reference Boutilier and Poole1996) is deployed for the state and observation sets, (2) the states are composed of the user's intentions and ‘hidden system states,’ (3) the observations are the user's utterances and other observations being inferred from lower-level information of the speech recognizer, robust parser, and from other input modalities. Williams, Poupart and Young (Reference Williams, Poupart and Young2005a; Reference Williams, Poupart and Young2005b) further extended Zhang's model by adding the state of the dialogue from the perspective of the user which is hidden from the system's view (called user's dialogue state) to the state set and adding the confidence score into the observation set. All these approaches have shown that POMDP-based dialogue strategies outperform MDP counterparts (e.g. Pietquin Reference Pietquin2004). Furthermore, these strategies cope well with different types of errors in a spoken dialogue system, especially with speech recognition errors. However, finding an optimal dialogue policy, either using exact or approximate POMDP algorithms, is computationally expensive. Therefore, this work is limited to dialogue problems with the size of only a few slots (e.g. two slots in Williams, Poupart and Young Reference Williams, Poupart and Young2005c, three slots in Zhang et al. Reference Zhang, Cai, Mao and Guo2001, and four slots in Roy et al. Reference Roy, Pineau and Thrun2000) (Table 1).

Table 1.

Characteristics of some POMDP-based dialogue managers

* N: number of slots.

† See AMDP (Roy and Thrun Reference Roy and Thrun1999), QMDP (Littman, Cassandra and Kaelbling Reference Littman, Cassandra and Kaelbling1995); FIB (Hauskrecht Reference Hauskrecht2000), Perseus (Spaan and Vlassis Reference Spaan and Vlassis2005).

Recently, Williams and Young (Reference Williams and Young2006) proposed a scaled-up POMDP method called CSPBVI to deal with the multi-slot problem. The dialogue manager is decomposed into two POMDP levels, a master POMDP and a set of summary POMDPs. Each summary POMDP corresponds to a slot. The optimization or planning step of this method is conducted off-line by simplifying the user behavior (assuming that when the users are asked about a certain slot, they only provide a value for that slot) and reducing the size of the POMDP structure (e.g. approximating the number of values of each slot by only two values best and rest). However, the affective dialogue model requires a more complex POMDP structure than that of the spoken counterpart. Compressing the POMDP structure prevents us to incorporate a rich model of the user's affect into the state space and might loose dependencies among the user's emotion, goal, and other hidden state variables.

Looking beyond the POMDP framework, another technique to deal with partially observable situations is to use DDNs. A DDN is an extension of the Dynamic Bayesian Network (DBN) with decision and utility nodes. DDNs provide a concise representation for large POMDPs and can be used as inputs for any POMDP algorithm such as value-iteration- and policy-iteration-based algorithms (Russell and Norvig Reference Russell and Norvig2003). A special case of the DDNs (selecting actions based on immediate reward) was used to model real-world dialogue management systems (Paek and Horvitz Reference Paek and Horvitz2000; Young et al. Reference Young, Schatzmann, Weilhammer and Ye2007). DBNs and DDNs are also suitable for use in developing the affective user model (Zhou and Conati Reference Zhou and Conati2003; Li and Ji Reference Li and Ji2005; de Rosis et al. Reference de, Novielli, Carofiglio, Cavalluzzi and de2006).

3.1 Slot-level dialogue manager

We represent each slot as a factored POMDP (Boutilier and Poole Reference Boutilier and Poole1996). The state set and observation set are composed of six features. The state set is composed of the user's goals for the slot i (Gu _i), the user's emotional states Footnote ³ (Eu), the user's actions for the slot i (Au _i), and the user's grounding states for the slot i (Du _i). The observation set is composed of the observation of the user's actions for the slot i (OAu _i) and the observation of the user's emotional states (OEu). Two of these six features (Eu and OEu) are identical for all slots. The action set defines the system actions for slot i (A _i).

Figure 2(b) shows the structure of slot i of our route navigation example (Section 4.1). The features of the state set, action set, observation set, and their dependencies form a two time slice Dynamic Bayesian Network (2TBN). Implicitly, some assumptions are made in this model: the user's goal only depends on the user's goal in the previous slice and the system action from the previous slice only influences the user's emotion, the user's action, and the grounding state. We can easily modify this model for representing other dependencies, for example the dependency between the user's emotion and the observation of the user's action. Parameters p _gc, p _ae, p _ec, p _e, p _oa, and p _oe are used to produce handcrafted transition and observation models in case no real data is available (e.g. at the initial phase of the system development), where p _gc is the probability of the user goal change; p _ae is the probability of the user emotion change because of the influence of the system action such as when the system confirms an incorrect user's goal (represented by two causal links from the system action and user's goal to the user's emotional state); p _ec is the probability that the user emotion change is due to the emotion decay and other causes; p _e is the probability of an error in the user's action being induced by emotion; p _oa and p _oe are the probabilities of the observed action and observed emotional state errors. The reward function is in principle different for each particular application. Therefore it is not specified in our general slot-level dialogue manager.

Fig. 2.

(a) Standard POMDP; (b) two time slice of the factored POMDP for slot i, where state set S is factored into four features Gu _i, Eu, Au _i, and Du _i, observation set Z is factored into two features OAu _i and OEu

Suppose the user's goal set of slot f _i has m _i values which are represented by Gu _i={v ₁, v ₂, . . ., v _{m i}}, the above features and the action set A _i are formulated as follows:

• • Eu = {stress, frustration, anger, happiness, . . .}.

  Note that we can extend the representation of the user's emotion by adding more relevant features into the state space. For example, if the user's emotion is described by two dimensions like valence and arousal. E _u then becomes a sub-network with two continuous variables. In general, solving POMDPs with continuous hidden variables is more difficult than for their discrete counterparts.

• • Au _i = {answer(x), {yes, no, . . .}, where x ∈ Gu _i.

  The abstract format of Au _i is userSpeechAct(x), where userSpeechAct is an element of the set of the user's speech acts.

• • Du _i = {notstated, stated, confirmed, . . .}.

• • OAu _i = {answer(x), yes, no, . . .}, where x ∈ Gu _i.

  The value y ∈ OAu _i depends on the level of abstraction of the observation of the user's action. For example if the observation of the user's action is sent by the ASR module, y is the word-graph or N-best hypotheses of the user's utterance. In our model, we assume a high level of abstraction for the observation of the user's action such as the output from a dialogue act recognition module or the intention level in the simulated user model (Eckert, Levin and Pieraccini Reference Eckert, Levin and Pieraccini1997). In the latter case OAu _i has the same set of values as Au _i.

• • OEu = {stress, frustration, anger, happiness, . . .}.

  Similar to the observation of the user's action, the observation of the user's emotional state can be represented by a set of observable effects such as response speech, speech pitch, speech volume, posture, and gesture features (Ball Reference Ball, Petta, Trappl and Payr2003). In our current model, we assume that the observation of the user's emotional states are the output of an emotion recognition module, and therefore OEu has the same set of values as Eu.

• • A _i = {ask, confirm(x), . . .}, where x ∈ Gu _i.

  The abstract format of A _i is systemSpeechAct(x), where systemSpeechAct is an element of the set of the system speech acts.

Let us consider a simple example: ‘A rescue worker needs to get a route description to evacuate victims from an unsafe tunnel. To achieve this goal, he communicates the location of the victims (one of three locations) to the system. The system can infer the user's stressed state and uses this information to adapt its dialogue policy.’Footnote ⁴ The factored POMDP model SP _i for this example is represented by

• • S = 〈Gu _i × Au _i × Eu × Du _i〉 ∪ end, where end is an absorbing state.

  1. (1) Gu _i = {v ₁, v ₂, v ₃}

  2. (2) Au _i = {answer(v ₁), answer(v ₂), answer(v ₃), yes, no}

  3. (3) Eu = {nostress, stress}

  4. (4) Du _i = {notstated, stated}

• • A = {ask, confirm(v ₁), confirm(v ₂), confirm(v ₃), ok(v ₁), ok(v ₂), ok(v ₃), fail}.

• • Z = 〈OAu _i × OEu〉.

  1. (1) OAu _i = answer(v ₁), answer(v ₂), answer(v ₃), yes, no}

  2. (1) OEu = {nostress, stress}

We are interested in finding an optimal dialogue policy for our POMDP-based dialogue systems. One intuitive approach is to compute a near-optimal dialogue policy using a good approximate POMDP algorithm and to use the result, usually in the form of a policy graph or value function table,Footnote ⁵ for selecting the appropriate system action. Exact POMDP algorithms such as the Witness (Cassandra, Kaelbling and Littman Reference Cassandra, Kaelbling and Littman1994) cannot be applied even for the above slot-POMDP because of the computational intractability. We used Perseus (Spaan and Vlassis Reference Spaan and Vlassis2005), which is one of the current best approximate Point-Based Value Iteration POMDP algorithms, to find a near-optimal dialogue policy for the above SP _i (Bui et al. Reference Bui, Zwiers, Poel and Nijholt2006). However, this approach is only tractable for a small number of slot values (m _i < 15).

Therefore, to maintain the tractability and allow real-time belief state update for applications having a large number of slot values, we approximate each slot-POMDP by a k-step look-ahead Dynamic Decision Network (kDDN) (k ≥ 0). The kDDN has (k + 2) slices. The first two slices are similar to the 2TBN showed in Figure 2(b), the next k slices are used to predict the user behavior in order to allow the dialogue manager to select the appropriate system action. Because the dialogue manager only needs to update its current belief state relevant to the system's last action, each kDDN (of slot i) can be converted to a set of DDNs (called action DDNs and denoted by kDDNAs), one for each action for slot i to simplify the computability in implementing the system. Figure 3 shows a structure of the kDDN and kDDNA (k = 1) used for SP _i of our route navigation example (Section 4.1). The connections from the action nodes to immediate reward nodes in the next slices are used to model that when a system slot action is selected that leads to the absorbing end state (such as ok or fail), the reward in all next slices are equal to 0.

Fig. 3.

The structure of (a) kDDN and (b) kDDNA with one-step look-ahead (k = 1). Shaded-round nodes are hidden, clear-round nodes are observable, rectangular nodes are decision nodes, diamond-shaped nodes are reward nodes. Both networks have similar structures except the kDDNA does not have the action node in the first slice. In our implemented prototype dialogue manager we use the simpler network kDDNA (to gain the computation time for the belief update process) directly because the ADM can keep track of the last system action, therefore it can update directly on the relevant kDDNA instead of kDDN.

Conceptually, this approximation gains the tractability by limiting the number of look-ahead steps (an infinite-horizon POMDP is equivalent to a kDDN with k = ∞). Notice that the approximate POMDP planning is performed off-line, while the DDN–POMDP planning is performed in real time. The real-time planning is not a critical issue for the off-line POMDP solution. On the other hand, it is easy to adapt the transition and observation models online with the DDN–POMDP method, while one needs to recalculate the approximate POMDP policy when there are changes in these models. Of course, limiting the number of look-ahead steps might lead to a suboptimal policy. To improve the quality of the DDN–POMDP policy, we propose to use an internal reward function to maximize the long-term goal. That is to say, we distinguish two types of reward models. The first one, called the external reward model or simply reward model, is described in Section 4.2.1. The second one, called internal reward model (Sutton and Barto Reference Sutton and Barto1998), is placed inside the agent or the dialogue manager. The idea behind this technique was originated from our practical experience in tweaking the reward model for POMDP-based dialogue managers. See Section 4.3.2 for further discussion about the internal reward tuning and optimization.

3.2 Global dialogue manager

The global dialogue manager is composed of two components: the dialogue information state (DIS) and the action selector (AS).

The DIS component is considered as the active memory of the dialogue manager. It updates and memorizes the current probability distributions of the user's goal, the user's emotional state, the user's action, the user's grounding state of all slots, the previous system action, and the recent observations of the user's action and emotional state. The DIS is formally defined by a tuple 〈P(Gu), P(Eu), P(Au), P(Du), hlsa, a, oau, oeu〉, where

• • P(Gu) is an n-tuple where each element i represents the current probability distribution of the user's goal for the slot i. Similarly, P(Au) and P(Du) are n-tuples where each element i represents the current probability distribution of the user's action and the user's grounding state for the slot i, respectively;

• • P(Eu) is the probability distribution of the user's emotional state;

• • hlsa is an n-tuple where each element i is the most recent local action nominated by slot i. hlsa is used by the action selector component to determine the global system action;

• • a ∈ A is the previous system action, where A is described in Equation 1;

• • oau ∈ OAu and oeu ∈ OEu are the recent observations of the user's action and emotional state, where OAu = {userSpeechAct(I)|I ⊂ {f _i,(f _i=x)|i ∈ [1, n], x ∈ Gu _i}}, Eu and OEu are defined in Section 3.1.

Table 2 shows a snapshot of the DIS component of a two-slot dialogue system taken from our current prototype dialogue manager. The first slot has two values, the second slot has three values. The previous system action is askopen. The current observation is oau = answer(f ₁=v ₁) and oeu = low. Only the probability distributions of the first slot are updated based on the observation of the user's action.

Table 2.

An example of the DIS for a two-slot case, slot f₁ has two values, slot f₂ has three values

The dialogue manager selects relevant kDDNAs based on the last system action a and the recent observation of the user's action oau. When a kDDNA for the slot i is selected, the element i of tuples P(Gu), P(Au), and P(Du) are used to initialize the kDDNAs.

The action selector component is responsible for aggregating the system's slot actions nominated by slot-POMDPs. The system action set generated by the AS component is represented by

(1)

where giveSolution and stop are two special system actions that lead to the absorbing end state. The giveSolution action aims to provide a solution to the user's request. The stop action terminates the current dialogue session.

The action selector is heuristic and application dependent. An example of a set of rules to select a global system action is described in Section 4.2.

The idea of splitting the dialogue manager into two levels was inspired by our previous work (Bui et al. Reference Bui, Rajman and Melichar2004). The factored POMDP model for each slot is extended from Williams's model (Williams et al. Reference Williams, Poupart and Young2005a). Two dialogue management frameworks using DDNs (Paek and Horvitz Reference Paek and Horvitz2000; Young et al. Reference Young, Schatzmann, Weilhammer and Ye2007) are comparable to the special case of our method with zero-step look-ahead DDN (k = 0). The observation currently does not take into account a confidence score. However, it is straightforward to incorporate this feature by adding a confidence score variable into the observation set similar to the one used in Williams's model.

3.3 Affective dialogue manager activity process

When the dialogue manager is initialized, it loads n slot-POMDP parameter files and creates a set of kDDNAs (|A _i| kDDNAs are created from the slot-POMDP parameter file i). The entire process of the affective dialogue manager is explained in this section by a cycle of four steps (Figure 4).

• • Step 1

  When the dialogue manager starts, the kDDNAs nominate greedy actions (i.e. actions associated with the highest immediate utilities) to the global dialogue manager based on the set of prior probability distributions specified in the slot-POMDP parameter files. These actions are combined by the action selector. The output is sent to the user (through the output generation module).

• • Step 2

  The global dialogue manager then receives the observations of the user's action and affective state (oau ∈ OAu and oeu ∈ OEu) (sub-step 2a). The kDDNAs relevant to oau are activated to compute the next slot action (sub-step 2b). The relevant previous belief and current observation (taken from Z and S) are then updated to these kDDNAs (sub-step 2c). The result computed by the kDDNAs is propagated back to the dialogue information state DIS (sub-step 2d).

• • Step 3

  All new actions computed by the selected kDDNAs are updated to variable hsla. The action selector AS then produces a new system action.

• • Step 4

  The process repeats from step 2 until the GDM selects either giveSolution or stop action.

Fig. 4.

Activity process of the ADM. The DIS component is represented by three nodes Z, S, and A. Node Z is composed of oau and oeu. Node S is composed of P(Gu), P(Eu), P(Au), P(Du). Node A is composed of hlsa and a. The process is explained through four steps from 1 to 4. Step 2 is composed of four sub-steps: 2a, 2b, 2c, and 2d. We assume that slot POMDPs SP ₁, . . ., SP _n are independent.

3.4 User simulation

The dialogue manager that we have described is a statistical dialogue manager. Dialogue corpora can be used to train this type of dialogue manager. However, the (PO)MDP-based dialogue manager has a huge number of states, therefore it is almost impossible to learn an optimal policy directly from a fixed corpus, regardless of its size (Schatzmann et al. Reference Schatzmann, Weilhammer, Stuttle and Young2006). To solve this problem, user simulation techniques have been used (Levin, Pieraccini and Eckert Reference Levin, Pieraccini and Eckert2000; Pietquin Reference Pietquin2004). The main idea is a two-phase approach. A simulated user is first trained on a small human–computer dialogue corpus to learn responses of a real user given the dialogue context. The learning dialogue manager then interacts with this simulated user in a trial-and-error manner to learn an optimal dialogue strategy. Experimental results show that a competitive dialogue strategy can be learnt even with handcrafted user model parameters (Young et al. Reference Young, Schatzmann, Weilhammer and Ye2007).

Our simulated user, constructed based on the POMDP environment, is shown in Figure 5. It is composed of a slot selection module, an observation generation module, a global reward function module, and an n-tuple of DBNs (one for each slot). The slot selection module determines which slots will be included into the user's response based on the system action and a slot probability distribution P _sd. P _sd can be estimated from a dialogue corpus as illustrated in Section 4.3.3. The observation generation and global reward function modules simply combine observations and rewards from the selected slots, respectively. Note that it is sufficient to generate the observation of the user's emotional state from the first selected slot. The structure of each DBN (Figure 5) is similar to the structure of the POMDP model for each slot (Figure 2b), except that the state features nodes (i.e. Gu _i, Eu, Au _i, and Du _i) in the simulated user model are observable from the user's perspective.

Fig. 5.

Simulated user model using DBNs. The user's state, action at each time-step are generated from the DBNs. Only the observation of the user's action, the observation of the user's affective state, and reward are sent to the dialogue manager. The structures of slot DBNs are identical, therefore only one DBN is shown.

The process to generate observations of the user's actions and affective states is as follows. First, the value a from the dialogue manager is sent to the slot selection module. This module randomly selects a subset of slots being included to the user's response based on the probability distribution P _sd. If no slot is selected, then the user's action is null. Second, the slot action extracted from a is then updated on node A _i of the time slice t−-1, the reward r ₁ is identified from node A _i of time slice t−1. Third, the user's goal, affective state, action, and dialogue state are randomly generated based on the probability distribution of the nodes Gu _i, E _u, Au _i, and Du _i (of time slice t), respectively. Fourth, the network is updated, and the observation of the user's action oau'₁ and the observation of the user's affective state oeu' are randomly selected based on the probability distribution of nodes OAu _i and OEu. The observations and the rewards are then sent to the observation generation and the global reward function modules. Other selected slots are processed in the same manner as the first one. Finally, the tuple < r, oau', oeu' > from the observation generation and the global reward function modules is sent back to the dialogue manager.

Our user simulation model is goal oriented. The user's action is consistent with the user's goal except when the user is stressed, then he might make an error. The technique used is similar to the Pietquin model which is one of the best user simulation models described in Schatzmann et al. (Reference Schatzmann, Weilhammer, Stuttle and Young2006). Schatzmann et al. (Reference Schatzmann, Weilhammer, Stuttle and Young2006) also showed that a strategy learnt with a good user model still performs well when tested on a different user model. Therefore, we expect that our dialogue policy is still robust when tested with different user simulators.

4.1 Example: route navigation in an unsafe tunnel

The hypothetical scenario example to illustrate our proposed DDN–POMDP framework is as follows: ‘A serious accident has happened in the Benelux tunnel, Rotterdam, The Netherlands. A rescue team is sent to the tunnel to evacuate a large number of victims. The rescue members are currently at n different locations in and around the tunnel. Each location might have one or more rescuers. The team leader (denoted by ‘the user’) needs a route description to coordinate with all other team members. He communicates with the dialogue system to get this information. The system is able to produce the route description when it knows the n locations of the rescue members. The current situation in the tunnel is very noisy.’ In this scenario, the user might be in a highly stressed situation, and can make errors in communicating with the system about the locations. Therefore, the dialogue manager of the system needs to be robust to cope with errors from the user's mistakes and the system's input recognition and fusion modules (Bui Reference Bui2006; Fitrianie et al. Reference Fitrianie, Poppe, Bui, Chitu, Datcu, Dor, Hofs, Wiggers, Willems, Poel, Rothkrantz, Vuurpijl and Zwiers2007).

4.2 Implementation

The route navigation example in Section 4.1 can be formulated as n slots (f ₁, f ₂, . . ., f _n) where Gu ₁ = Gu ₂ = ⋅ ⋅ ⋅ = Gu _n = V = {v ₁, v ₂, . . ., v _m} (the set of all locations in and around the tunnel).Footnote ⁶ The user's goal is represented as a function findRoute(g ₁, g ₂, . . ., g _n), with g _i = v _j, i ∈[1, n], j ∈[1, m] and g _i ≠ g _k if i ≠ k. In a frame-based dialogue system, the user's goal states can be simplified as a set of n-tuple 〈g ₁, g ₂, . . ., g _n〉. The user's affective states are five levels of the user's stressed situation: no stress (no), low stress (low), moderate stress (moderate), high stress (high), and extreme stress (extreme). We assume that the user only uses a limited set of main actions, that is to say that the set of user's speech acts is answer, yes, and no. Note that various combinations of the user's speech acts are allowed such as the user can respond no for some slots and respond answer for some other slots in one turn. The user's grounding state is composed of two values notstated and stated. The set of system's speech acts is ask, confirm, ok, fail, giveSolution, and stop. The combination of these speech acts and the slots and slot values forms a complete system action such as ask(f ₁) or confirm(f ₂ = v ₃). The two last special system acts (giveSolution and stop) are only used at the global dialogue manager level as being defined in Sectio 3.2. The user's objective is to find out the route description for n locations (the locations are known by the user). The system aims at showing the user the correct route navigation as soon as possible.

4.2.1 Slot-level dialogue manager representation

Using the formal formulation described in Section 3.1, the remaining features of slot f _i are represented by Eu = {no, low, moderate, high, extreme}, Au _i = {answer(x), yes, no|x ∈ Gu _i}, Du _i = {notstated, stated}, OAu _i = Au _i, OEu = Eu, A _i = {ask, confirm(x), ok(x), fail|x ∈ Gu _i}. The flat POMDP model for this slot (including a special end state) is composed of 10m ²+20m+1 states, 2m+2 actions, and 5m+10 observations, where m is the number of locations in the tunnel.

We use two criteria to specify the reward model for each slot, helping the user obtain the correct route description as soon as possible and maintaining the dialogue appropriateness (Williams et al. Reference Williams, Poupart and Young2005a). Concretely, if the system confirms when the user's grounding state is notstated, the reward is −2, the reward is −3 for action fail, the reward is 10 when slot i nominates a correct slot value (i.e. the system action is ok(x) where x = g _i), otherwise the reward is −50. The reward for any action taken in the absorbing end state is 0. The reward for any other action is −1. The high negative reward for selecting the incorrect slot value (−50) is used to motivate the dialogue manager agent to verify the information provided by the user when the user's stress level is high. Designing a reward model that leads to a good dialogue policy is a challenging task. It requires both expert knowledge and practical debugging as mentioned in Bui et al. (Reference Bui, van Schooten and Hofs2007).

The probability distributions for each kDDNA are generated using the parameters p _gc, p _ec, p _e, p _oa, p _oe defined in Section 3.1 and two other parameters K _ask and K _confirm, where K _ask and K _confirm are the coefficients associated with the ask and confirm actions (i.e. p _e(ask) = p _e/K _ask; p _e(confirm) = p _e/K _confirm). We assume that when the user is stressed, he makes more errors in response to the system ask action than the system confirm action because in our current model, the number of possible user actions in response to ask (m possible actions: answer(v ₁), answer(v ₂), . . ., answer(v _m)) is greater than to confirm (two actions: yes, no). We also assume that the system action does not influence the user's stress. It means that, in the structure of kDDNAs, there are no links from nodes A _i and Gu _i to nodes Eu _i (see Figure 3b). We will discuss further about the tractability of the kDDNA belief updating process for both cases (i.e. with and without the stress influence assumption) in Section 4.3.1.

An example of the user's stress model with p _ec = 0.1 is shown in Table 3. This model is consistent with the empirical work of stress recognition and modeling reported in Liao et al. (Reference Liao, Zhang, Zhu, Ji and Wayne2006). The user's stress level changes gradually during the system–user interaction process. We simplified the influence of factors such as workload, trait, and context (Liao et al. Reference Liao, Zhang, Zhu, Ji and Wayne2006) to stress by parameter p _ec.

Table 3.

Handcrafted user's stress model with p_ec=0.1, eu is the user's stress at time t-1 and eu' is the user's stress state at time t

4.3 Evaluation

In this section, we evaluate our DDN–POMDP approach on several important issues for building a realistic dialogue system. Section 4.3.1 is about the tractability of the belief monitoring and action selection processes. The benchmark of the DDN–POMDP, approximate POMDP, and handcrafted policies for a one-slot case is described in Section 4.3.2. The evaluation of the DDN–POMDP approach for a multi-slot case is presented in Section 4.3.3.

4.3.1 Tractability

Three computational tractability issues are tackled in this section: (i) scaling up the number of slots; (ii) scaling up the number of slot values; and (iii) comparison of the belief updating time with different kDDNA structures.

We conducted various experiments with different numbers of slots. In a 1000 slots test case, our DDN–POMDP dialogue manager is able to handle the information provided by the user in real time. This is because the number of slots does not influence the complexity of the kDDNAs. To our knowledge, the ability to handle such a large number of slots is sufficient for developing all practical frame-based dialogue problems.

A detailed description of the 1000-slot test case (each slot has 10 values) is as follows. First, 1000 POMDP parameter files are generated. Each file contains a compact representation of a slot POMDP problem (S, A, Z, T, O, R, γ). Although the POMDP parameter files are identical, we treat them as if they are different to guarantee that the test is applicable to frame-based dialogue problems of which slots' structures might be different. Second, when the system starts, the dialogue manager reads these files and creates kDDNAs. Each slot has 11 kDDNAs (only kDDNAs for ask and confirm actions are sufficient because when the system selects ok or fail action, no further belief updates are required). The total number of the created kDDNAs is 11000. The time taken to create, initialize probability distributions, and store these 11000 kDDNAs (using the SMILE library) in the computer memory is only 14 s.Footnote ⁹ Third, the initial belief states of slots are taken from the POMDP parameter files and updated into the DIS. Fourth, all slots nominate greedy action (ask action) and the askopen action is sent to the output module. Note that we have not yet executed any kDDNA belief update at this moment. Finally, when the dialogue manager receives the observations of the user's action and emotion, only relevant kDDNAs are activated for the belief update and online action selection tasks. With k = 0, the time taken to update 200 different kDDNAs simultaneously is around 1 s.

Scaling up the number of slot values increases the complexity of the kDDNAs. Using the SMILE library, our DDN–POMDP dialogue manager (k = 0) can handle problems of up to 500 slot values in real time (belief update time for one slot is smaller than 1 s, Figure 6). Note that the kDDNA belief update is a combined process: computing the belief stateFootnote ¹⁰ and selecting the best slot action. Figure 6 also shows that the kDDNA belief update time is longer when the number of slots being processed simultaneously increases. A solution for many simultaneous slots update is to deploy more computers and to divide the belief update task over these computers. This solution is not expensive, because in reality, the information provided from the user is usually relevant to a small number of slots. Because we make this kind of independence assumption between slots, when the system gains information of a slot, the probability distributions of the slot values of the other slots (slots that are not addressed in the previous user's action) are not updated. This assumption does help to reduce the belief updating time for many-slots dialogue problems. However, assuming that slots (even with distinct sets of values) are conditionally independent might lead to redundant system actions. For example, in a restaurant information seeking application (Rajman et al. Reference Rajman, Bui, Rajman, Seydoux, Trutnev and Quarteroni2004), assuming that all Chinese restaurants near the center only open in the evening, when the user provides the values ‘Chinese’ for slot ‘Type of cuisine’ and ‘Center’ for slot ‘Location’, the system might not need to ask about slot ‘Opening time.’Footnote ¹¹

Fig. 6.

Average kDDNA belief updating time over 10 runs in seconds with different numbers of slot values using the SMILE library. The best result is found using the Pearl exact inference algorithm and the Find Best Policy update (see http://genie.sis.pitt.edu/).

Unfortunately, the kDNNA belief updating time increases exponentially with the number of look-ahead steps (Figure 7). This suggests that when k ≥ 2, it is better to conduct policy search off-line and integrate the result (either in the form of a policy graph or an alpha file) into the dialogue management module for action selection. Further details about the off-line policy search issue will be explored in the future.

Fig. 7.

Average kDDNA belief updating time over 10 runs with different look-ahead steps.

We also computed the belief updating time on two different kDDNA's structures: kDDNA1 and kDDN2. The kDDNA1's structure is the simplified structure used for our next experiments (without linkage from the user's action and user's goal nodes to the user's emotion node). The kDDNA2's structure is described in Figure 3b. The maximum additional computation of the belief updating time for the kDDNA2 (comapred with kDDNA1) was 5% when tested with k = 0, m ∈ [100, 900] and k = 1, m ∈ [3,40].

When a slot has thousands of values (called many-value slot), one solution is to bundle slot values into partitions and to update the belief directly on these partitions as proposed by Young et al. (Reference Young, Schatzmann, Weilhammer and Ye2007). In our previous work (Bui et al. Reference Bui, Rajman and Melichar2004), we formulated the many-value slot as a list processing slot. This is based on our practical experience of building real-world frame-based dialogue systems. For some slots, we cannot determine all possible values at the design time such as the type of foods in the restaurant search application or the title of movies to be recorded in a smart-home application. Therefore, values of these slots are defined as ordinal numbers such as one, two, . . ., ten, previous, and next. The dialogue manager and the user then only work with these list-processing values. A mapping between these values and the real values is done automatically by the dialogue manager. However, whether this idea is useful for statistical dialogue management models, where slot values are represented as a probability distribution, is still an open issue. We defer the study of this representation in the future.

4.3.2 DDN–POMDP versus approximate POMDP and handcrafted policies

The performance of the DDN–POMDP dialogue policy depends on both the global dialogue manager and the slot-level dialogue manager (Section 3). In this section, we evaluate the performance of the slot-level dialogue manager by comparing the DDN–POMDP dialogue policy with an approximate POMDP policy and three handcrafted dialogue strategies HC1, HC2, and HC3 (Figure 8) for the one-slot case. HC1 is also the optimal dialogue policy when p _gc = p _e = p _oa = 0 (the user's goal does not change; stress has no influence to the user's action and no error in observing the user's action, i.e. the speech recognition and spoken language understanding errors are equal to 0).

Fig. 8.

Three handcrafted dialogue strategies for the one-slot case (x is the slot value): (a) first ask and then select ok action if userSpeechAct = answer (otherwise ask), (b) first ask, then confirm if userSpeechAct = answer (otherwise ask) and then select ok action if userSpeechAct = yes (otherwise ask), (c) first ask, then confirm if userSpeechAct = answer & oeu = high or extreme and select ok action if userSpeechAct = yes.

The evaluation is conducted by letting each dialogue policy interact with the same simulated user (the simulated user model is constructed using the DBN described in Figure 5). We conducted a large number of dialogue episodes (10000) to guarantee the statistical significance. Error bars in Figures 9, 11, and 12 show the 95% confidence level.

Fig. 9.

Average return of the DDN–POMDP and approximate POMDP policies for a one-slot, three values case. Error bars show the 95% confidence level. The caption ‘*’ at the end of a policy title indicates that the internal reward function of the dialogue manager associated with the policy is optimized.

Figure 9 shows the average return of the DDN–POMDP policies and a best approximate POMDP policy computed using Perseus for a simple dialogue problem (one slot, three values). The probability distributions and the internal reward models of the DDN–POMDP and DDN–POMDP* models are similar to the one used in the simulated user except that in the DDN–POMDP* model, we set a lower internal reward when the dialogue manager gives an incorrect solution (rOkIncorrect = −200). However, Figure 9 also shows that the performance of the DDN–POMDP policy is significantly improved (close to the standard POMDP policy) when we tune its internal reward model. The idea to tune the DDN–POMDP internal reward model is based on our practical experience. The behavior of the DDN–POMDP policy is sensitive to its internal reward model. When the rOKIncorrect value is low, the DDN–POMDP dialogue manager is more sensitive in confirming the information provided by the user before giving a solution. It is clear that, when the number of slots and slot values is small, the POMDP dialogue policy is the best solution, because the policy computed by the approximate POMDP solver is similar to the DDN–POMDP policy with k = ∞. Note that when computing the average return of all three cases, we do not change the reward model of the simulated user which is defined in Section 4.2.1. The average return of the DDN–POMDP is low when p _e = 0.1 or 0.2. We looked at the behavior of this policy in case p _e = 0.1 and found that it uses the confirm action when the observation of the user's emotional state is high or extreme (similar to the HC3 policy). On the other hand, both DDN–POMDP* and POMDP policies use the confirm for all observation of the user's emotional state (similar to the HC2 policy). It means that in this case, it is better to confirm after the user provides a location no matter what the observation of the user's emotion state is.

We also conducted experiments with different internal reward values of providing incorrect solutions (rOkIncorrect ∈ [−10⁷, −10], Figure 10). At the beginning, the average return increases monotonically with the absolute value of rOkIncorrect. The DDN–POMDP policy performs best when rOkIncorrect ∈ [−1000, −200]. When rOkIncorrect < −1000, the average return degrades. Interestingly, there is a correlation between the high negative value of rOkIncorrect and the number of times the system selects confirm action before giving a solution to the user.

Fig. 10.

Internal reward optimization for a one-slot, three values case. We conducted experiments with p _e in the range from 0 to 0.8. All average returns are optimal in the range [−1000, −200]. Only three lines are shown for the purpose of clarity. Error bars show the 95% confidence level.

Figure 11 shows the average return of five dialogue strategies when the probability of the user's action error being induced by stress p _e changes from 0 (stress has no influence on the user action selection) to 0.8 (stress has high influence on the user action selection). The results of the average return (Figure 11) show that with a 95% confidence level the DDN–POMDP dialogue policy outperforms all other remaining dialogue strategies when p _e ≥ 0.1.Footnote ¹² The DDN–POMDP copes well when the user's action error being induced by stress increases. An example of the interaction between the DDN–POMDP dialogue manager and the simulated user (three dialogue episodes) is shown in Appendix A.

Fig. 11.

Average return versus the user's action error being induced by stress (p _e). Error bars show the 95% confidence level.

Figure 12 shows that the DDN–POMDP dialogue policy also copes well with the observation of the user's action error p _oa. When the observation of the user's action error is too high (p _oa ≥ 0.6), the DDN–POMDP dialogue manager always selects the fail action therefore the average return is a constant (equal to −4). The fail action in this example means that the system stops the dialogue and transfers the user's request to a human operator. Note that whether the system selects the fail action or not depends on the negative reward associated with this action. In the above example, selecting the fail action at the beginning is equivalent to getting the correct location after 13 turns (in both cases, the system receives the same amount of reward). One interesting point is that although dialogue policy HC2 copes well with the change of p _e (Figure 11), its performance decreases rapidly when p _oa increases (Figure 12).

Fig. 12.

Average return versus the observation of the user's action error p _oa. Error bars show the 95% con.dence level.

We also evaluated the performance of the DDN–POMDP dialogue policy with a number of different setups: (1) the transition and observation probability distributions of the DDN–POMDP and the simulated user are the identical (source model) and (2) the probability distributions of the DDN–POMDP is fixed with p _e = 0.15, 0.45, and 0.6, respectively. Figure 11 shows that the DDN–POMDP dialogue policy can cope robustly with variation in the user's model (the POMDP policy is shown as an upperbound of the performance). Note that the performance of the DDN–POMDP policy in this Figure is different when compared with the one in Figure 11 because we use a different reward model.Footnote ¹³ Reward for selecting the incorrect slot value is −10, and −5 for action fail. The user's affective states are classified simply as nostress and stress. We also conducted the robustness test (similar to the one shown in Figure 13) of the DDN–POMDP and DDN–POMDP* policies for the reward model presented in Section 4.2.1 and K _confirm = 10. Both policies can still cope robustly with variation in the user's model, except the case of the DDN–POMDP policy with fixed p _e = 0.15. The average return of this policy (with fixed p _e = 0.15) degrades rapidly when p _e ≥ 0.4. Looking at the simulation corpus we found that the DDN–POMDP policy with fixed p _e = 0.15 only starts to confirm the slot value provided by the user when the observation of the user's stress is high. Meanwhile, the DDN–POMDP and DDN–POMDP* policies for the remaining cases start to confirm when the observation of the user's stress is low.

Fig. 13.

The performance of the DDN–POMDP policy with fixed p _e.

The reward function used in Figures 11–13 is not tuned except that we set the internal reward for confirm action on the user's goal to −0.99 (instead of −1). The modified internal reward function helps the DDN–POMDP dialogue manager avoid a pitfall with the confirm action. We detected that when incorporated the external reward model into the DDN–POMDP dialogue manager, the system might use repeatedly the confirm(v ₁) action. Using the modified internal reward, the DDN–POMDP dialogue manager confirms on the most likely user's goal (instead of v ₁).

4.3.3 DDN–POMDP versus enhanced handcrafted policies (two-slot case)

This section evaluates the performance of the DDN–POMDP versus enhanced handcrafted policies for a two-slot case. The user's model at the global level is adapted from the SACTI training corpus (Williams and Young Reference Williams and Young2007). The model is shown in Table 4.

Table 4.

User's model for slot selection adapted from the training model of the SACTI corpus with several extensions

Note that we extend several user's options from the original model to illustrate the ability of our method to cope with different variabilities of the user's response. For example, when the user is asked on a slot, he might answer on another slot. Similarly, when the system confirms a slot (Do you mean the second location is A?), the user might respond to both slots (No, A is the first location.).

Based on the three one-slot handcrafted dialogue strategies presented in Figure 8 we implemented three multi-slot handcrafted dialogue strategies HC1+, HC2+, and HC3+ (Table 5). All three strategies start with the askopen action. Every time the dialogue manager receives an observation it filters the incoherent responses before the action selection process to minimize the unnecessary dialogue turns. For example, if two slots have the same value, only the slot relevant to the last system action is selected. Further, based on the experience with the one-slot case, we improve the performance of all three handcrafted strategies by selecting stop action when the observation of the user's emotion is extreme and p _e > 0, similar to the behavior of the DDN–POMDP policy (not show in Table 5). In addition, the inter-turn inconsistency is also handled to prevent the system to provide incoherent solutions such as giveSolution(f ₁ = x, f ₂ = x). Note that the updateUserState function of the HC3+ algorithm is similar to the one of the HC2+ algorithm except the updateUserState function of the HC3+ changes the dialogue state du from −1 to 1 when the observation of the user's action is answer and the observation of the user's emotion is no or low or moderate stress.

Table 5.

High-level description of the three handcrafted strategy algorithms for a two-slots case

Figure 14 shows the average return of the DDN–POMDP* (the best internal reward rOkIncorrect for k = 0 is −250)Footnote ¹⁴ and handcrafted strategies. It is still valid that when the error rate is high, the DDN–POMDP* strategy performs better than the enhanced version of the handcrafted counterparts. Because the behavior of the handcrafted strategies does not depend on the numeric value of the reward function, we further compare the average number of turns and the percentage of correct goals. Table 6 shows that the percentage of achieved goals of the policy HC2+ is high as expected. The DDN–POMDP* policy gained a higher number of achieved goals with fewer number of turns comparing to the HC2+ policy.

Fig. 14.

Average return versus the user's action error being induced by stress (p _e) for a two-slots case. Error bars show the 95% confidence level.

Table 6.

Percentage of achieved goals and average number of turns per episode (bold numbers show the highest percentage of achieved goals for each p_e)

In Section 4.3.1 we addressed the 1000 slots and 10 slot values case and showed that our prototype system works in real time. Although the number of slots does not influence the kDDNA belief update, the system would need a large amount of memory to store all kDDNAs when we increase both number of slots n and number of slot values m (the total number of kDDNAs generated is n × (m+1)). Furthermore, the SMILE package conducts the kDDNA belief update by first converting the kDDNA to a set of Bayesian networks and then operating on these Bayesian networks. This also consumes a lot of memory space. To solve this problem, we implemented the action selection procedure directly in our Java code and use the SMILE package only for standard belief updating as in POMDPs (the kDDNA structure is now greatly simplified, for example, for k = 0, nodes A _i and R _i are excluded). We performed tests with a 200 slots and 500 slot values dialogue problem and our prototype system worked in real time. It would be interesting to compare the quality of the DDN–POMDP policy and handcrafted policies on this level. However, this requires a substantial modification of the user simulation model. For example, if we assume that the maximum number of slots mentioned in each user's turn is two, then it would need more than 200 turns to collect all the slot values information for the 200-slot case. We observed that a large number of episodes end up with a stop action because eventually when the observation of the user's stress level is extreme, all policies select stop action. We therefore plan to report this evaluation in our future work with a more realistic user model for many slots case.