Encoding Word Confusion Networks with Recurrent Neural Networks for Dialog State Tracking

Abstract: This paper presents our novel method to encode word confusion networks, which can represent a rich hypothesis space of automatic speech recognition systems, via recurrent neural networks. We demonstrate the utility of our approach for the task of dialog state tracking in spoken dialog systems that relies on automatic speech recognition output. Encoding confusion networks outperforms encoding the best hypothesis of the automatic speech recognition in a neural system for dialog state tracking on the well-known second Dialog State Tracking Challenge dataset.

Spoken dialog systems (SDSs) allow users to naturally interact with machines through speech and are nowadays an important research direction, especially with the great success of automatic speech recognition (ASR) systems BIBREF0 , BIBREF1 . SDSs can be designed for generic purposes, e.g. smalltalk BIBREF2 , BIBREF3 ) or a specific task such as finding restaurants or booking flights BIBREF4 , BIBREF5 . Here, we focus on task-oriented dialog systems, which assist the users to reach a certain goal.
Task-oriented dialog systems are often implemented in a modular architecture to break up the complex task of conducting dialogs into more manageable subtasks. BIBREF6 describe the following prototypical set-up of such a modular architecture: First, an ASR system converts the spoken user utterance into text. Then, a spoken language understanding (SLU) module extracts the user's intent and coarse-grained semantic information. Next, a dialog state tracking (DST) component maintains a distribution over the state of the dialog, updating it in every turn. Given this information, the dialog policy manager decides on the next action of the system. Finally, a natural language generation (NLG) module forms the system reply that is converted into an audio signal via a text-to-speech synthesizer.
Error propagation poses a major problem in modular architectures as later components depend on the output of the previous steps. We show in this paper that DST suffers from ASR errors, which was also noted by BIBREF7 . One solution is to avoid modularity and instead perform joint reasoning over several subtasks, e.g. many DST systems directly operate on ASR output and do not rely on a separate SLU module BIBREF8 , BIBREF7 , BIBREF9 . End-to-end systems that can be directly trained on dialogs without intermediate annotations have been proposed for open-domain dialog systems BIBREF3 . This is more difficult to realize for task-oriented systems as they often require domain knowledge and external databases. First steps into this direction were taken by BIBREF5 and BIBREF10 , yet these approaches do not integrate ASR into the joint reasoning process.
We take a first step towards integrating ASR in an end-to-end SDS by passing on a richer hypothesis space to subsequent components. Specifically, we investigate how the richer ASR hypothesis space can improve DST. We focus on these two components because they are at the beginning of the processing pipeline and provide vital information for the subsequent SDS components. Typically, ASR systems output the best hypothesis or an n-best list, which the majority of DST approaches so far uses BIBREF11 , BIBREF8 , BIBREF7 , BIBREF12 . However, n-best lists can only represent a very limited amount of hypotheses. Internally, the ASR system maintains a rich hypothesis space in the form of speech lattices or confusion networks (cnets).
We adapt recently proposed algorithms to encode lattices with recurrent neural networks (RNNs) BIBREF14 , BIBREF15 to encode cnets via an RNN based on Gated Recurrent Units (GRUs) to perform DST in a neural encoder-classifier system and show that this outperforms encoding only the best ASR hypothesis. We are aware of two DST approaches that incorporate posterior word-probabilities from cnets in addition to features derived from the n-best lists BIBREF11 , BIBREF16 , but to the best of our knowledge, we develop the first DST system directly operating on cnets.
Our model depicted in Figure FIGREF3 is based on an incremental DST system BIBREF12 . It consists of an embedding layer for the words in the system and user utterances, followed by a fully connected layer composed of Rectified Linear Units (ReLUs) BIBREF17 , which yields the input to a recurrent layer to encode the system and user outputs in each turn with a softmax classifier on top. INLINEFORM0 denotes a weighted sum INLINEFORM1 of the system dialog act INLINEFORM2 and the user utterance INLINEFORM3 , where INLINEFORM4 , and INLINEFORM5 are learned parameters: DISPLAYFORM0 
Independent experiments with the 1-best ASR output showed that a weighted sum of the system and user vector outperformed taking only the user vector INLINEFORM0 as in the original model of BIBREF12 . We chose this architecture over other successful DST approaches that operate on the turn-level of the dialogs BIBREF8 , BIBREF7 because it processes the system and user utterances word-by-word, which makes it easy to replace the recurrent layer of the original version with the cnet encoder.
Our cnet encoder is inspired from two recently proposed algorithms to encode lattices with an RNN with standard memory BIBREF14 and a GRU-based RNN BIBREF15 . In contrast to lattices, every cnet state has only one predecessor and groups together the alternative word hypotheses of a fixed time interval (timestep). Therefore, our cnet encoder is conceptually simpler and easier to implement than the lattice encoders: The recurrent memory only needs to retain the hidden state of the previous timestep, while in the lattice encoder the hidden states of all previously processed lattice states must be kept in memory throughout the encoding process. Following BIBREF15 , we use GRUs as they provide an extended memory compared to plain RNNs. The cnet encoder reads in one timestep at a time as depicted in Figure FIGREF4 . The key idea is to separately process each of the INLINEFORM0 word hypotheses representations INLINEFORM1 in a timestep with the standard GRU to obtain INLINEFORM2 hidden states INLINEFORM3 as defined in Equation ( EQREF7 )-() where INLINEFORM5 , and INLINEFORM6 are the learned parameters of the GRU update, candidate activation and reset gate. To get the hidden state INLINEFORM7 of the timestep, the hypothesis-specific hidden states INLINEFORM8 are combined by a pooling function (Equation ). DISPLAYFORM0 
We experiment with the two different pooling functions INLINEFORM0 for the INLINEFORM1 hidden GRU states INLINEFORM2 of the alternative word hypotheses that were used by BIBREF14 :
Instead of the system output in sentence form we use the dialog act representations in the form of INLINEFORM0 dialog-act, slot, value INLINEFORM1 triples, e.g. `inform food Thai', which contain the same information in a more compact way. Following BIBREF7 , we initialize the word embeddings with 300-dimensional semantically specialized PARAGRAM-SL999 embeddings BIBREF21 . The hyper-parameters for our model are listed in the appendix.
The cnet GRU subsumes a standard GRU-based RNN if each token in the input is represented as a timestep with a single hypothesis. We adopt this method for the system dialog acts and the baseline model that encode only the best ASR hypothesis.
In our experiments, we use the dataset provided for the second Dialog State Tracking Challenge (DSTC2) BIBREF22 that consists of user interactions with an SDS in the restaurant domain. It encompasses 1612, 506, 1117 dialogs for training, development and testing, respectively. Every dialog turn is annotated with its dialog state encompassing the three goals for area (7 values), food (93 values) and price range (5 values) and 8 requestable slots, e.g. phone and address. We train on the manual transcripts and the cnets provided with the dataset and evaluate on the cnets.
Some system dialog acts in the DSTC2 dataset do not correspond to words and thus were not included in the pretrained word embeddings. Therefore, we manually constructed a mapping of dialog acts to words contained in the embeddings, where necessary, e.g. we mapped expl-conf to explicit confirm.
In order to estimate the potential of improving DST by cnets, we investigated the coverage of words from the manual transcripts for different ASR output types. As shown in Table TABREF10 , cnets improve the coverage of words from the transcripts by more than 15 percentage points over the best hypothesis and more than five percentage points over the 10-best hypotheses.
However, the cnets provided with the DSTC2 dataset are quite large. The average cnet consists of 23 timesteps with 5.5 hypotheses each, amounting to about 125 tokens, while the average best hypothesis contains four tokens. Manual inspection of the cnets revealed that they contain a lot of noise such as interjections (uh, oh, ...) that never appear in the 10-best lists. The appendix provides an exemplary cnet for illustration. To reduce the processing time and amount of noisy hypotheses, we remove all interjections and additionally experiment with pruning hypotheses with a score below a certain threshold. As shown in Table TABREF10 , this does not discard too many correct hypotheses but markedly reduces the size of the cnet to an average of seven timesteps with two hypotheses.
We report the joint goals and requests accuracy (all goals or requests are correct in a turn) according to the DSTC2 featured metric BIBREF22 . We train each configuration 10 times with different random seeds and report the average, minimum and maximum accuracy. To study the impact of ASR errors on DST, we trained and evaluated our model on the different user utterance representations provided in the DSTC2 dataset. Our baseline model uses the best hypothesis of the batch ASR system, which has a word error rate (WER) of 34% on the DSTC2 test set. Most DST approaches use the hypotheses of the live ASR system, which has a lower WER of 29%. We train our baseline on the batch ASR outputs as the cnets were also produced by this system. As can be seen from Table TABREF11 , the DST accuracy slightly increases for the higher-quality live ASR outputs. More importantly, the DST performance drastically increases, when we evaluate on the manual transcripts that reflect the true user utterances nearly perfectly.
Table TABREF13 displays the results for our model evaluated on cnets for increasingly aggressive pruning levels (discarding only interjections, additionally discarding hypotheses with scores below 0.001 and 0.01, respectively). As can be seen, using the full cnet except for interjections does not improve over the baseline. We believe that the share of noisy hypotheses in the DSTC2 cnets is too high for our model to be able to concentrate on the correct hypotheses. However, when pruning low-probability hypotheses both pooling strategies improve over the baseline. Yet, average pooling performs worse for the lower pruning threshold, which shows that the model is still affected by noise among the hypotheses. Conversely, the model can exploit a rich but noisy hypothesis space by weighting the information retained from each hypothesis: Weighted pooling performs better for the lower pruning threshold of 0.001 with which we obtain the highest result overall, improving the joint goals accuracy by 1.6 percentage points compared to the baseline. Therefore, we conclude that is beneficial to use information from all alternatives and not just the highest scoring one but that it is necessary to incorporate the scores of the hypotheses and to prune low-probability hypotheses. Moreover, we see that an ensemble model that averages the predictions of ten cnet models trained with different random seeds also outperforms an ensemble of ten baseline models.
Although it would be interesting to compare the performance of cnets to full lattices, this is not possible with the original DSTC2 data as there were no lattices provided. This could be investigated in further experiments by running a new ASR system on the DSTC2 dataset to obtain both lattices and cnets. However, these results will not be comparable to previous results on this dataset due to the different ASR output.
The current state of the art on the DSTC2 dataset in terms of joint goals accuracy is an ensemble of neural models based on hand-crafted update rules and RNNs BIBREF16 . Besides, this model uses a delexicalization mechanism that replaces mentions of slots or values from the DSTC2 ontology by a placeholder to learn value-independent patterns BIBREF8 , BIBREF23 . While this approach is suitable for small domains and languages with a simple morphology such as English, it becomes increasingly difficult to locate words or phrases corresponding to slots or values in wider domains or languages with a rich morphology BIBREF7 and we therefore abstained from delexicalization.
The best result for the joint requests was obtained by a ranking model based on hand-crafted features, which relies on separate SLU systems besides ASR BIBREF11 . SLU is often cast as sequence labeling problem, where each word in the utterance is annotated with its role in respect to the user's intent BIBREF24 , BIBREF25 , requiring training data with fine-grained word-level annotations in contrast to the turn-level dialog state annotations. Furthermore, a separate SLU component introduces an additional set of parameters to the SDS that has to be learned. Therefore, it has been argued to jointly perform SLU and DST in a single system BIBREF8 , which we follow in this work.
As a more comparable reference for our set-up, we provide the result of the neural DST system of BIBREF7 that like our approach does not use outputs of a separate SLU system nor delexicalized features. Our ensemble models outperform BIBREF7 for the joint requests but are a bit worse for the joint goals. We stress that our goal was not to reach for the state of the art but show that DST can benefit from encoding cnets.
As we show in this paper, ASR errors pose a major obstacle to accurate DST in SDSs. To reduce the error propagation, we suggest to exploit the rich ASR hypothesis space encoded in cnets that contain more correct hypotheses than conventionally used n-best lists. We develop a novel method to encode cnets via a GRU-based RNN and demonstrate that this leads to improved DST performance compared to encoding the best ASR hypothesis on the DSTC2 dataset.
In future experiments, we would like to explore further ways to leverage the scores of the hypotheses, for example by incorporating them as an independent feature rather than a direct weight in the model.
We thank our anonymous reviewers for their helpful feedback. Our work has been supported by the German Research Foundation (DFG) via a research grant to the project A8 within the Collaborative Research Center (SFB) 732 at the University of Stuttgart.
 

Figure and table captions:
Figure 1: The proposed model with GRU-based cnet encoder for a dialog with three turns. dt are one-hot word vectors of the system dialog acts; wti correspond to the word hypotheses in the timesteps of the cnets of the user utterances; sj , uj are the cnet GRU outputs at the end of each system or user utterance.
Figure 2: Encoding k alternative hypotheses at timestep t of a cnet.
Table 1: Coverage of words from the manual transcripts in the DSTC2 development set of different batch ASR output types (%). In the pruned cnet interjections and hypotheses with scores below 0.001 were removed.
Table 2: DSTC2 test set accuracy for 1-best ASR outputs of ten runs with different random seeds in the format average maximumminimum .
Table 3: DSTC2 test set accuracy of ten runs with different random seeds in the format average maximumminimum . ? denotes a statistically significant higher result than the baseline (p < 0.05, Wilcoxon signed-rank test with Bonferroni correction for ten repeated comparisons). The cnet ensemble corresponds to the best cnet model with pruning threshold 0.001 and weighted pooling.
Table 4: Cnet from the DSTC2 development set of the session with id voip-db80a9e6df20130328 230354. The transcript is i don’t care, which corresponds the best hypothesis of both ASR systems. Every timestep contains the hypothesis that there is no word (!null).

Questions about this paper:
What type of recurrent layers does the model use?
What is a word confusion network?

Answers:
GRU
It is a network used to encode speech lattices to maintain a rich hypothesis space.