Using Automatically Transcribed Dialogs to Learn User Models in a Spoken Dialog System
Umar Syed Department of Computer Science Princeton University Princeton, NJ 08540, USA usyed@cs.princeton.edu Jason D. Williams Shannon Laboratory AT&T Labs -- Research Florham Park, NJ 07932, USA jdw@research.att.com

Abstract
We use an EM algorithm to learn user models in a spoken dialog system. Our method requires automatically transcribed (with ASR) dialog corpora, plus a model of transcription errors, but does not otherwise need any manual transcription effort. We tested our method on a voice-controlled telephone directory application, and show that our learned models better replicate the true distribution of user actions than those trained by simpler methods and are very similar to user models estimated from manually transcribed dialogs.

1

Introduction and Background

When designing a dialog manager for a spoken dialog system, we would ideally like to try different dialog management strategies on the actual user population that will be using the system, and select the one that works best. However, users are typically unwilling to endure this kind of experimentation. The next-best approach is to build a model of user behavior. That way we can experiment with the model as much as we like without troubling actual users. Of course, for these experiments to be useful, a high-quality user model is needed. The usual method of building a user model is to estimate it from transcribed corpora of human-computer dialogs. However, manually transcribing dialogs is expensive, and consequently these corpora are usually small and sparse. In this work, we propose a method of building user models that does not operate on manually transcribed dialogs, but instead uses dialogs that have been transcribed by an automatic 121

speech recognition (ASR) engine. Since this process is error-prone, we cannot assume that the transcripts will accurately reflect the users' true actions and internal states. To handle this uncertainty, we employ an EM algorithm that treats this information as unobserved data. Although this approach does not directly employ manually transcribed dialogs, it does require a confusion model for the ASR engine, which is estimated from manually transcribed dialogs. The key benefit is that the number of manually transcribed dialogs required to estimate an ASR confusion model is much smaller, and is fixed with respect to the complexity of the user model. Many works have estimated user models from transcribed data (Georgila et al., 2006; Levin et al., 2000; Pietquin, 2004; Schatzmann et al., 2007). Our work is novel in that we do not assume we have access to the correct transcriptions at all, but rather have a model of how errors are made. EM has previously been applied to estimation of user models: (Schatzmann et al., 2007) cast the user's internal state as a complex hidden variable and estimate its transitions using the true user actions with EM. Our work employs EM to infer the model of user actions, not the model of user goal evolution.

2

Method

Before we can estimate a user model, we must define a larger model of human-computer dialogs, of which the user model is just one component. In this section we give a general description of our dialog model; in Section 3 we instantiate the model for a voicecontrolled telephone directory. We adopt a probabilistic dialog model (similar

Proceedings of ACL-08: HLT, Short Papers (Companion Volume), pages 121­124, Columbus, Ohio, USA, June 2008. c 2008 Association for Computational Linguistics


to (Williams and Young, 2007)), depicted schematically as a graphical model in Figure 1. Following the convention for graphical models, we use directed edges to denote conditional dependencies among the variables. In our dialog model, a dialog transcript x consists of an alternating sequence of system actions and observed user actions: x = ~ ~ (S0 , A0 , S1 , A1 , . . .). Here St denotes the system ~t the output of the ASR engine when action, and A applied to the true user action At . A dialog transcript x is generated by our model as follows: At each time t, the system action is St and the unobserved user state is Ut . The user state indicates the user's hidden goal and relevant dialog history which, due to ASR confusions, is known with certainty only to the user. Conditioned on (St , Ut ), the user draws an unobserved action At from a distribution Pr(At | St , Ut ; ) parameterized by an unknown parameter . For each user action At , the ~ ASR engine produces a hypothesis At of what the ~ user said, drawn from a distribution Pr(At | At ), which is the ASR confusion model. The user state Ut is updated to Ut+1 according to a deterministic ~ distribution Pr(Ut+1 | St+1 , Ut , At , At ). The system outputs the next system action St+1 according to its dialog management policy. Concretely, the val~ ues of St , Ut , At and At are all assumed to belong to finite sets, and so all the conditional distributions in our model are multinomials. Hence  is a vector that parameterizes the user model according to Pr(At = a | St = s, Ut = u; ) = asu . The problem we are interested in is estimating  ~ given the set of dialog transcripts X , Pr(At | At ) ~t ). Here, we assume and Pr(Ut+1 | St+1 , Ut , At , A ~ that Pr(At | At ) is relatively straightforward to estimate: for example, ASR models that rely a simple confusion rate and uniform substitutions (which can be estimated from small number of transcriptions) have been used to train dialog systems which outperform traditional systems (Thomson et al., 2007). ~ Further, Pr(Ut+1 | St+1 , Ut , At , At ) is often deterministic and tracks dialog history relevant to action selection -- for example, whether the system correctly or incorrectly confirms a slot value. Here we assume that it can be easily hand-crafted. Formally, given a set of dialog transcripts X , our goal is find a set of parameters   that maximizes the 122

DD DD DD At QQ DDDD QQQ D ?? OO QQQ DDD QQQ D!! Q(( // Ut+1 Ut OO OO

~ At D OO D

@GABCD FE

@GABCD FE
St

HOIJKL NM
St+1

Figure 1: A probabilistic graphical model of a humancomputer dialog. The boxed variables are observed; the circled variables are unobserved.

log-likelihood of the observed data, i.e.,  = arg max log Pr(X | )


Unfortunately, directly computing   in this equation is intractable. However, we can efficiently approximate   via an expectation-maximization (EM) procedure (Dempster et al., 1977). For a dialog transcript x, let y be the corresponding sequence of unobserved values: y = (U0 , A0 , U1 , A1 , . . .). Let Y be the set of all sequences of unobserved values corresponding to the data set X . Given an estimate (t-1) , a new estimate  (t) is produced by X T l , (t-1) (t) = arg max EY og Pr(X , Y | )


he expectation in this equation is taken over all possible values for Y . Both the expectation and its maximization are easy to compute. This is because our dialog model has a chain-like structure that closely resembles an Hidden Markov Model, so a forward-backward procedure can be employed (Rabiner, 1990). Under fairly mild conditions, the sequence  (0) , (1) , . . . converges to a stationary point estimate of   that is usually a local maximum.

3

Target Application

To test the method, we applied it to a voicecontrolled telephone directory. This system is currently in use in a large company with many thousands of employees. Users call the directory system and provide the name of a callee they wish to be connected to. The system then requests additional


information from the user, such as the callee's location and type of phone (office, cell). Here is a small fragment of a typical dialog with the system: S0 = First and last name? ~ A0 = "John Doe" [A0 = Jane Roe ] S1 = Jane Roe. Office or cell? ~ A1 = "No, no, John Doe" [A1 = No ] S2 = First and last name? ... Because the telephone directory has many names, ~ the number of possible values for At , At , and St is potentially very large. To control the size of the model, we first assumed that the user's intended callee does not change during the call, which allows us to group many user actions together into generic placeholders e.g. At = FirstNameLastName. After doing this, there were a total of 13 possible ~ values for At and At , and 14 values for St . The user state consists of three bits: one bit indicating whether the system has correctly recognized the callee's name, one bit indicating whether the system has correctly recognized the callee's "phone type" (office or cell), and one bit indicating whether the user has said the callee's geographic location (needed for disambiguation when several different people share the same name). The deterministic dis~ tribution Pr(Ut+1 | St+1 , Ut , At , At ) simply updates the user state after each dialog turn in the obvious way. For example, the "name is correct" bit of Ut+1 is set to 0 when St+1 is a confirmation of a name which doesn't match At . Recall that the user model is a multinomial distribution Pr(At | St , Ut ; ) parameterized by a vector . Based on the number user actions, system actions, and user states,  is a vector of (13 - 1) × 14 × 8 = 1344 unknown parameters for our target application.

~ ~ ognized At such that At = At . The probabilities ~t | At ) were then constructed by assuming that, Pr(A when the ASR engine makes an error recognizing a user action, it substitutes another randomly chosen action. 4.1 Simulated Data Recall that, in our parameterization, the user model is Pr(At = a | St = s, Ut = u; ) = asu . So in this set of experiments, we chose a reasonable, hand-crafted value for , and then generated synthetic dialogs by following the probabilistic process depicted in Figure 1. In this way, we were able to create synthetic training sets of varying sizes, as well as a test set of 1000 dialogs. Each generated dialog d in each training/test set consisted of a sequence of values for all the observed and unobserved variables: ~ d = (S0 , U0 , A0 , A0 , . . .). D For a training/test set D, let Kasu be the number of times t, in all the dialogs in D, that At = a, St = D s, and Ut = u. Similarly, let Kas be the number of ~ times t that At = a and St = s. For each training set D, we estimated  using the following three methods: 1. Manual: Let  be the maximum likelihood estimate using manually transcribed data, i.e., D asu = PKasu . KD
a asu

2. Automatic: Let  be the maximum likelihood estimate using automatically transcribed data, i.e., asu = transcription errors and assumes that user behavior depends only on the observed data. 3. EM : Let  be the estimate produced by the EM algorithm described in Section 2, which uses the automatically transcribed data and the ASR confusion model. Now let D be the test set. We evaluated each user model by calculating the normalized log-likelihood of the model with respect to the true user actions in D: a D ,s,u Kasu log asu () = |D| () is essentially a measure of how well the user model parameterized by  replicates the distribution
e KD P as D . e a Kas

This approach ignores

4

Experiments

We conducted two sets of experiments on the telephone directory application, one using simulated data, and the other using dialogs collected from actual users. Both sets of experiments assumed that all the distributions in Figure 1, except the user model, are known. The ASR confusion model was estimated by transcribing 50 randomly chosen dialogs from the training set in Section 4.2 and calculating the frequency with which the ASR engine rec123


of user actions in the test set. The normalization is to allow for easier comparison across data sets of differing sizes. We repeated this entire process (generating training and test sets, estimating and evaluating user models) 50 times. The results presented in Figure 2 are the average of those 50 runs. They are also compared to the normalized log-likelihood of the "Truth", which is the actual parameter  used to generated the data. The EM method has to estimate a larger number of parameters than the Automatic method (1344 vs. 168). But as Figure 2 shows, after observing enough dialogs, the EM method is able to leverage the hidden user state to learn a better model of user behavior, with an average normalized log-likelihood that falls about halfway between that of the models produced by the Automatic and Manual methods.
-3 Normalized log-likelihood -4 -5 -6 -7 -8 0 500 1000 Number of dialogs in training set Truth Manual EM Automatic 1500

Manual EM Automatic

Training Set () -2.87 -3.90 -4.60

Test Set () -3.73 -4.33 -5.80

Table 1: Normalized log-likelihood of each model type with respect to the training set and the test set. The EM values are the average of 50 runs. The EM models had higher normalized log-likelihood than the Automatic model in 50 out of 50 runs.

5

Conclusion

We have shown that user models can be estimated from automatically transcribed dialog corpora by modeling dialogs within a probabilistic framework that accounts for transcription errors in a principled way. This method may lead to many interesting future applications, such as continuous learning of a user model while the dialog system is on-line, enabling automatic adaptation.

References
AP Dempster, NM Laird, and DB Rubin. 1977. Maximum likelihood from incomplete data via the em algorithm. J. Royal Stat. Soc., 39:1­38. K Georgila, J Henderson, and O Lemon. 2006. User simulation for spoken dialogue systems: Learning and evaluation. In Proc ICSLP, Pittsburgh, USA. E Levin, R Pieraccini, and W Eckert. 2000. A stochastic model of human-machine interaction for learning dialogue strategies. IEEE Trans on Speech and Audio Processing, 8(1):11­23. O Pietquin. 2004. A framework for unsupervised learning of dialogue strategies. Ph.D. thesis, Faculty of Engineering, Mons (TCTS Lab), Belgium. LR Rabiner, 1990. A tutorial on hidden Markov models and selected applications in speech recognition, pages 267­296. Morgan Kaufmann Publishers, Inc. J Schatzmann, B Thomson, and SJ Young. 2007. Statistical user simulation with a hidden agenda. In Proc SIGDial, Antwerp, pages 273­282. B Thomson, J Schatzmann, K Welhammer, H Ye, and SJ Young. 2007. Training a real-world POMDP-based dialog system. In Proc NAACL-HLT Workshop Bridging the Gap: Academic and Industrial Research in Dialog Technologies, Rochester, New York, USA, pages 9­17. JD Williams and SJ Young. 2007. Partially observable Markov decision processes for spoken dialog systems. Computer Speech and Language, 21(2):393­422.

Figure 2: Normalized log-likelihood of each model type with respect to the test set vs. size of training set. Each data point is the average of 50 runs. For the largest training set, the EM models had higher normalized log-likelihood than the Automatic models in 48 out of 50 runs.

4.2 Real Data We tested the three estimation methods from the previous section on a data set of 461 real dialogs, which we split into a training set of 315 dialogs and a test set of 146 dialogs. All the dialogs were both manually and automatically transcribed, so that each of the three methods was applicable. The normalized log-likelihood of each user model, with respect to both the training and test set, is given in Table 1. Since the output of the EM method depends on a random choice of starting point  (0) , those results were averaged over 50 runs. 124