Novel Methods for Natural Language Generation
in Spoken Dialogue Systems

The main aim of this thesis is to explore the usage of statistical methods in NLG for SDSs and advance the state-of-the art in naturalness and adaptability. We focus on enabling fast reuse in new domains and languages, and we aim at adapting the generated sentences to the communication goal, to the current situation in the dialogue, and to the particular user.

This work thus not only brings a radical improvement over NLG systems based on handwritten rules or domain-specific templates, but also represents an important contribution to recent works in statistical NLG by experimenting with deep-syntactic generation, multilingual NLG, and user-adaptive models.

Our experiments, and also the main contributions of this thesis, proceed along the following key objectives:

NLG for spoken dialogue typically involves a pipeline with the following two steps:

1. Sentence planning – sentence shaping and expression selection,

2. Surface realization – linearization of the sentence plan according to the grammar of the target language.

Most NLG systems follow the pipeline, but only some of them implement it as a whole. Many generators focus only on one of the phases while using a very basic implementation of the other or leaving it out completely.

Some NLG systems choose to replace the pipeline with a joint, end-to-end architecture (e.g., Angeli et al., 2010; Mairesse et al., 2010). Both approaches can offer their own advantages: Dividing the problem of NLG into several subtasks makes the individual subtasks simpler. A sentence planner can abstract away from complex surface syntax and morphology and only concern itself with a high-level sentence structure. It is also possible to reuse third-party modules for parts of the generation pipeline (Walker et al., 2001). On the other hand, the problem of pipeline approaches in general is error propagation. In addition, joint methods do not need to model intermediate structures explicitly (Konstas and Lapata, 2013).

Traditional NLG systems are based on procedural rules (Bangalore and Rambow, 2000; Belz, 2005; Ptáček and Žabokrtský, 2007), template filling (Rudnicky et al., 1999; van Deemter et al., 2005), or grammars in various formalisms. Such rule-based generators are still used frequently today. Their main advantages are implementation simplicity and speed, but many rule-based systems struggle to achieve high coverage in larger domains (White et al., 2007) and are not easy to adapt for different domains and/or languages. Rule-based systems also tend to exhibit little variation in the output, which makes them appear repetitive and unnatural.

Various approaches were taken to make NLG output more flexible and natural as well as to simplify its reuse in new domains. While statistical methods and trainable modules in NLG are not new (cf.  Langkilde and Knight, 1998), their adoption has been slower than in most other subfields of NLP and mostly focuses just on enhancing the capabilities of an existing rule-based generator (Paiva and Evans, 2005; Mairesse and Walker, 2008). Fully trainable statistical NLG (Mairesse et al., 2010; Angeli et al., 2010) has been rare. Only in the past year or two, new fully trainable NN-based generators (e.g., Wen et al., 2015b, a, but also work described in this thesis) have been dominating the field.

The number of publicly available datasets suitable for NLG experiments is small compared to other areas of NLP. Publicly available datasets are more common in text-based NLG than in NLG for SDSs (Sripada et al., 2003; Wong and Mooney, 2007; Liang et al., 2009). However, most of text-based NLG sets assume a content selection step, which is not applicable to our work.

Publicly available corpora for NLG in SDSs have been up until now very scarce: Mairesse et al. (2010) published a dataset of 404 restaurant recommendations, which includes detailed semantic alignments (see Section 3.2). Wen et al. (2015b, a) present two similar sets for restaurant and hotel information domains, both containing over 5,000 instances but lots of repetition. Similar but larger and more diverse datasets for laptop and TV recommendation domains have been released recently by Wen et al. (2016), who focus on domain adaptation.

Throughout our experiments in this thesis, we use a version of the dialogue act (DA) meaning representation (Young et al., 2010; Jurčíček et al., 2014; Wen et al., 2015a). Here, a DA is simply a list of triplets (DA items) in the following form:

• DA type – the type of the utterance or a dialogue act per se, e.g., hello, inform, or request.

• slot – the slot (domain attribute) that the DA is concerned with, e.g., departure_time or price_range.

• value – the particular value of the slot in the DA item.

The latter two members of the triplet are optional. For instance, the DA type hello does not use any slots or values, and the DA type request uses slots but not values since it is used to request a value from the user. DA items with identical DA type are joined in figures for brevity (see Figure 3.1).

In all our experiments, we use unaligned pairs of input DAs and output sentences. This simplifies training data acquisition: Previous NLG systems usually required a separate training data alignment step (Mairesse et al., 2010; Konstas and Lapata, 2013), and this is now no longer needed since our sentence planners learn alignments jointly with learning to generate (see Figure 3.1). In addition, alignments are not decided by hard, binary decisions, which allows for a more fine-grained modeling.

In all our experiments, we use delexicalization – the replacing of some values, such as restaurant names or time constants, with placeholders (see Figure 3.2). The generator then only works with these placeholders, which are replaced with the respective values in a simple postprocessing stage. This helps to reduce data sparsity issues and improves generalization to unseen slot values since the possible number of values for some slots is unbounded in theory, and most values are only seen once or never in the training data.

Note that delexicalization is different from using full, fine-grained semantic alignments (see Section 3.2) and can easily be obtained automatically using simple string replacement rules as the values to be delexicalized occur verbatim in training data (possibly in an inflected form for Czech, see Chapter 8).

We explore both approaches to NLG sketched in Section 2.1: two-step generation with separate sentence planning and surface realization steps and joint, end-to-end, one-step direct generation. We believe that both options have their own advantages (cf. Section 2.1), and that both of them should be explored.

We opted for using sentence plans in the form of simplified deep syntactic trees (tectogrammatical trees or t-trees) based on the Functional Generative Description (Sgall et al., 1986) as the intermediate data representation between the stages (sentence plan). The t-tree sentence plan structure is a deep-syntactic dependency tree that only contains nodes for content words (nouns, full verbs, adjectives, adverbs) and coordinating conjunctions (see Figure 3.3). The nodes maintain surface word order. Each node has several attributes; the most important ones for our experiments are t-lemma or deep lemma (base word form of the content word) and formeme (a morphosyntactic label describing the word form).

Automatic intrinsic NLG evaluation typically uses metrics developed for machine translation (MT) which are based on word-by-word comparisons against reference texts, measuring word overlap. This approach is cheap and fast, but correspondence to human judgments has been disputed (Stent et al., 2005; Callison-Burch et al., 2006). Manual human evaluation provides a more accurate estimate of an NLG system’s performance, but requires much more resources. Both approaches are therefore combined in practice.

For automatic metrics, we use BLEU (Papineni et al., 2002) and NIST (Doddington, 2002) to evaluate our experiments, two of the oldest and arguably the most widely used metrics for NLG. In addition, we apply a complementary metric that is only applicable to delexicalized NLG: slot error rate which estimates the number of semantic errors based on counting DA value placeholders in the generated output (Wen et al., 2015a). For human evaluation, our task is to decide which system variant will provide outputs preferable to users. Therefore, we focus on direct comparisons of outputs generated for the same input DA, asking users which variant is better/preferred (Callison-Burch et al., 2007; Koehn, 2010, p. 220).

Our English surface realizer was developed within the Treex NLP framework (Popel and Žabokrtský, 2010), where it mostly adapts Czech realizer pipeline modules (Žabokrtský et al., 2008; Popel, 2009, p. 84ff.) and shares their language-independent code components. It starts from a copy of the input t-tree, gradually transforming it into a surface dependency tree, which is then linearized (see Figure 4.1). It handles all the important surface language phenomena: auxiliary words, inflection, word order, agreement, punctuation, and capitalization.

To evaluate the realizer on a broad domain, we ran a round-trip test: We first automatically analyzed English texts into t-trees using Treex, then ran our surface realizer to regenerate texts and evaluated the results using BLEU score (Papineni et al., 2002) against the originals. On texts from the Prague Czech-English Dependency Treebank 2.0 (Hajič et al., 2012), the realizer reached a BLEU of 77.47%. This score is relatively high given that the original is used as the only reference and even minor deviations are penalized.

Our realizer has been successfully applied in our NLG experiments in Chapters 5 and 6 as well as in TectoMT translation systems translating into English from Czech, Dutch, Spanish, and Basque (Rosa et al., 2015; Popel et al., 2015).

To simplify surface realizer development, we introduced a new statistical module for word inflection generation, i.e., deducing the inflected word form given its lemma (base form) and the desired morphological properties (see Figure 4.2). Our solution, dubbed Flect, manages to produce natural inflection and is easily trainable for different languages and capable of generalizing to unseen inputs.

Similarly to Bohnet et al. (2010) and Durrett and DeNero (2013), we reformulate the task of finding the correct word form as a multiclass classification problem. Instead of finding the desired word form directly (which would induce an explosion of possible target classes), the classifier is trained to find the correct inflection pattern: lemma-form edit scripts – rules describing how to transform the base form into the inflected form – are used as target classes.

We used the LIBLINEAR logistic regression classifier (Fan et al., 2008). The feature set, which includes lemma suffixes, allows the classifier to generalize to unknown lemmas since inflection depends mostly on suffixes in many languages.

We evaluated our Flect morphology generator on six languages using the CoNLL 2009 Shared Task data sets (Hajič et al., 2009), and compared it to a simple dictionary baseline for English and Czech (see Table 4.1). We can see that Flect is able to predict the majority of word forms correctly and significantly improves over a dictionary baseline by generalizing to word forms unseen in the training set. The lower score for German is caused partly by insufficient information in the morphological tags.

We also integrated Flect into our English surface realizer, where it replaced a handcrafted morphological dictionary (Straková et al., 2014), gaining over 3.5% BLEU improvement in the round trip test described in Section 4.1.

The sentence planner is based on a variant of the A* algorithm (Hart et al., 1968; Och et al., 2001; Koehn et al., 2003). It starts from an empty sentence plan tree and tries to find a path to the complete, optimal sentence plan by iteratively adding nodes to the currently “most promising” incomplete sentence plan. It uses the following two subcomponents to guide the search:

• a candidate generator that incrementally generates new candidate sentence plan trees (expanding incomplete sentence plans by adding new nodes),

• a scorer/ranker that scores the appropriateness of the sentence plan trees for the input DA and selects the next sentence plan tree to be expanded.

At each step, expansions of the currently best-ranking sentence plan tree are created by adding one node of all viable types and in all viable positions. The expansions are subsequently ranked. The algorithm continues as long as the best-ranking candidate sentence plan score keeps increasing.

The basic scorer for the sentence plan tree candidates is based on the linear perceptron ranker of Collins and Duffy (2002), where the score is computed as a dot product of the features and the corresponding weight vector. Features include the candidate tree shape, nodes and their combinations, as well as conjunctions with items of the input DA. During training, weight vector update is performed if the score of the top-ranking generated tree for a given DA is higher than that of the corresponding the gold-standard tree.

The basic scorer is trained to score full sentence plan trees, but it is also used to score incomplete sentence plans during the decoding, which leads to a bias towards bigger trees. To outweigh this bias, we introduced a novel modification of the perceptron updates to improve scoring of incomplete sentence plans: In addition to updating the weights using the full top-scoring candidate and the gold-standard tree, we also use their differing subtrees for extra perceptron updates.

Moreover, to further boost scores of incomplete sentence plans that are expected to further grow, we add a future promise term to the sentence plan scores, based on the expected number of children of different node types (with different lemma-formeme combinations).

We performed our experiments on the BAGEL data set (Mairesse et al., 2010) in the restaurant information domain. Note that while the data set contains fine-grained semantic alignment, we do not use it in our experiments. We use 10-fold cross-validation – same as Mairesse et al. (2010) – and evaluate our generator using the automatic BLEU and NIST scores (Papineni et al., 2002; Doddington, 2002). The results are shown in Table 5.1.

Our generator did not achieve the same performance as that of Mairesse et al. (2010) (ca. 67% BLEU). However, our task is substantially harder since the generator also needs to learn the alignment of words and phrases to DA items and determine whether all required information is present on the output (see Section 3.2). Our differing tree updates clearly bring a substantial improvement over standard perceptron updates; using future promise estimation boosts the scores even further. Both improvements on the full training set are considered statistically significant at 95% confidence level by the paired bootstrap resampling test (Koehn, 2004).

The generator learns to produce meaningful utterances which mostly correspond well to the input DA. It is able to produce original paraphrases and generalizes to previously unseen DAs. On the other hand, the outputs are not free of semantic errors (missing, repeated, or irrelevant information).

Our generator is based on the seq2seq model with attention (Bahdanau et al., 2015), a type of an encoder-decoder RNN architecture operating on variable-length sequences of tokens (see Figure 6.1). First, its encoder RNN consumes the input token by token and encodes it into a sequence of hidden states (vectors of floating-point numbers). The decoder then generates output tokens one-by-one, using as inputs its own internal state (initialized by the last encoder hidden state and updated in every step), the previously decoded token, and the attention context vector (a weighted sum of all encoder hidden states).

DAs, t-trees, and sentences are represented as sequences of tokens to enable their usage in the sequence-based generator – DAs are encoded as lists of triples “DA type – slot – value”, t-trees use a simple bracketed notation. All tokens in turn are represented by their embeddings – vectors of floating-point numbers initialized randomly and trained from data (Bengio et al., 2003).

On top of this basic seq2seq architecture, we use beam search for decoding (Sutskever et al., 2014; Bahdanau et al., 2015) and a reranker that penalizes outputs which miss some information from the input DA or add irrelevant information. The reranker uses a RNN encoder over the outputs and a final sigmoid layer which provides a binary decision on the presence of different DA items (DA types, slot-value pairs). This is compared to the items in the input DA and the number of discrepancies for a particular output is used to lower its probability on the output $n$-best list (see Figure 6.2).

Same as in Chapter 5, we perform our experiments on the BAGEL data set (Mairesse et al., 2010), without using the fine-grained semantic alignments.

The results of our experiments are shown in Table 6.1. We include BLEU and NIST scores and the number of semantic errors (missing, added, or repeated information) counted manually on a sample of the outputs. A manual inspection of the outputs shows that both tree-based and joint setup are able to produce fluent sentences in the domain style for the most part. The occasional errors are of different types in the two setups: while the joint setup confuses semantically close items such as Italian and French cuisine, the syntax-generating model produces outputs with missing or repeated information more often.

A comparison of the two approaches goes in favor of the joint setup, which offers better performance and does not need an external surface realizer. Both setups surpass the previous best results achieved in Chapter 5.¹¹The BLEU/NIST differences are statistically significant according to the pairwise bootstrap resampling test (Koehn, 2004).

We also trained our system on the larger restaurant dataset of Wen et al. (2015a) to perform a direct comparison of our system’s performance to theirs. Our system performed comparably, offering slightly lower BLEU score (72.7% vs. 73.1%) but slightly lower number of semantic errors (slot error rate of 0.41% vs. 0.46%).

We collected a new NLG dataset for SDSs that is, to our knowledge, the first dataset of its kind to include preceding context (user utterance) with each data instance (see Figure 7.1).²² To prevent data sparsity issues, we only take into account the immediately preceding user utterance, which we believe has the largest entrainment potential. Crowdsourcing was used to obtain both the contextual user utterances and the corresponding system responses to be generated. The dataset contains over 5,500 instances with more than 500 distinct context utterances from the domain of public transport information. It is released under a permissive Creative Commons 4.0 BY-SA license.³³Archival version is available at http://hdl.handle.net/11234/1-1675, development version at https://github.com/UFAL-DSG/alex_context_nlg_dataset.

To allow our seq2seq system from Chapter 6 to entrain to the user and provide naturally variable outputs, we enhanced its architecture in two alternative ways, which condition generation not only on the input DA, but also on the preceding user utterance:

1. Prepending context. The tokens of the preceding user utterance are simply prepended to the DA tokens and fed into the encoder (see Figure 7.2).

2. Context encoder. We add another, separate encoder for the context utterances. The hidden states of both encoders are concatenated (see Figure 7.2).

Furthermore, we add an $n$-gram match reranker promoting generator outputs on the $k$-best list that have a word or phrase overlap with the context utterance.

We use our collected dataset to evaluate the generator extensions described in Section 7.2, applying direct string generation only. Table 7.1 lists our results in terms of the BLEU and NIST metrics. We can see that the $n$-gram match reranker brings an improvement even if used alone. Both seq2seq model extensions result in lowered scores if used by themselves, but bring in even larger improvements in combination with the $n$-gram match reranker.

We evaluated the best-performing setting (prepending context with $n$-gram match reranker) in a blind pairwise preference test against the baseline (cf. Section 3.5) with untrained judges recruited on the CrowdFlower crowdsourcing platform. The judges preferred the context-aware system output in 52.5% cases, slightly but significantly more often than the baseline.⁴⁴Differences have been confirmed at 99% statistical significance level by pairwise bootstrap resampling (Koehn, 2004) for both BLEU/NIST scores and human judgments.

Since no suitable dataset existed for Czech NLG (same as most other non-English languages), we needed to create a new one. To reduce costs, speed up the process, and work around the lack of Czech speakers on crowdsourcing platforms (Pavlick et al., 2014), we localized an existing English set – Wen et al. (2015a)’s 5,000 instances on restaurant information – and had it translated by freelance translators. We released the data under the Creative Commons 4.0 BY-SA license.⁵⁵The set can be downloaded from http://hdl.handle.net/11234/1-2123, a development version is available at https://github.com/UFAL-DSG/cs_restaurant_dataset. The result shows that DA slot values, such as restaurant names, have more possible lexical realizations and need to be inflected (see Figure 8.1).

We use the seq2seq approach described in Chapter 6 as the base of our experiments and add the following extensions to better accommodate for Czech:

In our experiments on our restaurant datasets, all 24 system variants learned to produce mostly fluent outputs with little to no semantic errors. We could see based on BLEU/NIST that the lemma-tag and direct generation setups perform better than the tree-based setup and RNN LM outperforms other lexicalization methods. We selected 7 setups for human evaluation (see Table 8.1): the best-performing lexically-informed and delexicalized setups, plus selected contrastive setups with just one setting different from the overall best setup (lexically-informed lemma-tag generation with RNN LM lexicalization).

The human evaluation is based on subjective preference ranking, same as in Chapter 7. We used a multi-way ranking of system outputs (Bojar et al., 2016), which is converted to pairwise system comparisons and evaluated using the TrueSkill algorithm (Sakaguchi et al., 2014).

Since users preferred a different system (delexicalized joint generation with RNN LM) than the best one in terms of BLEU/NIST, we performed a small-scale expert comparison of both systems’ performance, which showed that both setups perform very comparably, but the human-preferred system fares slightly better. The results thus come out rather in favor of the simplest generator setups. On the other hand, the RNN-based surface form selection clearly pays off.

In Chapter 5, we developed an A*-search-based NLG system that is trainable from pairs of natural language sentences and corresponding dialogue acts, without the need for fine-grained semantic alignments, thus greatly simplifying training data collection for NLG. It was the first NLG system to learn alignments jointly with sentence planning. This system has then been superseded by a new, seq2seq-based one in terms of both speed and output quality, as described in Chapter 6. The seq2seq-based system reached new state-of-the-art without fine-grained alignments on the small BAGEL dataset (Mairesse et al., 2010), using much less training data than other RNN-based approaches. The two NLG systems were described in (Dušek and Jurčíček, 2015) and (Dušek and Jurčíček, 2016c), respectively.

We developed a simple, domain-independent surface realizer from the t-trees deep syntax formalism (see Section 3.4) for English, similar to an older Czech realizer (Žabokrtský et al., 2008). We simplified the creation of new t-tree realizers by creating a novel statistical morphological inflection module which generalizes to previously unseen word forms (see Chapter 4). The English realizer was described in (Dušek et al., 2015), and we reported on the morphological inflection module in (Dušek and Jurčíček, 2013). Parts of the realizer were later reused in machine translation (Popel et al., 2015; Aranberri et al., 2016).

In Chapter 8, we applied our seq2seq-based generator to Czech, addressing problems not present in English – larger vocabulary and the need to inflect proper names (DA slot values). We show that our seq2seq-based generator is able to produce mostly correct and fluent sentence structures without any significant changes, apart from proper name inflection, where our RNN-LM-based module significantly outperforms a strong baseline.

Mimicking human behavior in dialogue, where interlocutors adapt their wording and syntax to each other, we extended our seq2seq generator in Chapter 7 to reflect not only the input DA, but also the previous user request, thus enabling it to create responses appropriate in the preceding dialogue context and providing it with a natural source of variation. The context-aware generator achieved a small but statistically significant performance improvement over the context-oblivious baseline. This result has been described in (Dušek and Jurčíček, 2016b).

In Chapters 6 and 8, we compare two different NLG architectures: a two-step pipeline using separate sentence planning and surface realization modules and a joint setup generating surface strings directly. We are able to use the same seq2seq model for both setups, generating t-trees (deep syntax postprocessed by a surface realizer) or surface word forms (in an end-to-end fashion). In Chapter 8, we experiment with seq2seq generation of Czech lemma-tag sequences (base word forms and morphological categories), which are subsequently postprocessed by a morphological dictionary. We show that the seq2seq models learn to generate valid t-trees and lemma-tag sequences successfully. However, the direct, end-to-end setup reaches superior performance in our domains. Experiments for English from Chapter 6 were described in (Dušek and Jurčíček, 2016c).

To perform our experiments in Chapters 7 and 8, we have created two novel datasets for NLG, which are freely available under a permissive license:⁶⁶Available at https://github.com/UFAL-DSG/alex_context_nlg_dataset, https://github.com/UFAL-DSG/cs_restaurant_dataset under the Creative Commons 4.0 BY-SA license. the first NLG dataset for Czech, which is also the biggest freely available non-English NLG dataset, and the first NLG dataset using preceding dialogue context and specifically targeted at adapting system responses to the user. The latter set is also described in (Dušek and Jurčíček, 2016a).

In sum, our work constitutes significant advances along all of the preset objectives. In a few aspects, it leaves room for improvement in future work as some of the experiments on dialogue alignment and Czech generation were rather limited. Nevertheless, our generator is fully functional and usable in practice, within a spoken dialogue system or in a standalone setting. It is freely available for download from GitHub.⁷⁷Available at https://github.com/UFAL-DSG/tgen under the Apache 2.0 license.

In future work, we would like to widen the user adaptation experiment by taking the whole dialogue into account. We also plan to work on removing the need for delexicalizing proper names to further simplify portability of NLG systems to other domains and languages. In the long term, we see the future of NLG in interactive systems in end-to-end solutions incorporating language understanding, dialogue management, and response generation (Wen et al., 2016; Williams et al., 2017).