# WenetSpeech: A 10000+ Hours Multi-domain Mandarin Corpus for Speech
Recognition

###### Abstract

In this paper, we present WenetSpeech, a multi-domain Mandarin corpus
consisting of 10000+ hours high-quality labeled speech, 2400+ hours weakly
labeled speech, and about 10000 hours unlabeled speech, with 22400+ hours in
total. We collect the data from YouTube and Podcast, which covers a variety of
speaking styles, scenarios, domains, topics and noisy conditions. An optical
character recognition (OCR) method is introduced to generate the audio/text
segmentation candidates for the YouTube data on the corresponding video
subtitles, while a high-quality ASR transcription system is used to generate
audio/text pair candidates for the Podcast data. Then we propose a novel end-
to-end label error detection approach to further validate and filter the
candidates. We also provide three manually labelled high-quality test sets
along with WenetSpeech for evaluation – Dev for cross-validation purpose in
training, Test_Net, collected from Internet for matched test, and
Test_Meeting, recorded from real meetings for more challenging mismatched
test. Baseline systems trained with WenetSpeech are provided for three popular
speech recognition toolkits, namely Kaldi, ESPnet, and WeNet, and recognition
results on the three test sets are also provided as benchmarks. To the best of
our knowledge, WenetSpeech is the current largest open-source Mandarin speech
corpus with transcriptions, which benefits research on production-level speech
recognition.

Index Terms—  automatic speech recognition, corpus, multi-domain

##  1 Introduction

In the past decade, the performance of automatic speech recognition (ASR)
systems have been significantly improved. On the one hand, the development of
neural networks has increased the capacity of models, pushing the dominant
framework from the hybrid hidden Markov models [1, 2] to end-to-end models,
like CTC [3, 4], RNN-T [5, 6, 7, 8], and encoder-decoder based models [9, 10,
11, 12, 13]. To simply implement such advanced models and obtain state-of-the-
art reproducible results, researchers also release several open source
toolkits, including Kaldi [14], Sphinx [15], Fariseq [16], ESPnet [17], and
recently WeNet [18], etc. On the other hand, self-supervised speech
representation learning methods are proposed to make better use of a large
amount untranscribed data, such as wav2vec [19], wav2vec 2.0 [20], Hubert
[21], and wav2vec-U [22], etc. In addition to these algorithm-level efforts,
the development of open source corpora is also crucial to the research
community, especially for academia or small-scale research groups.

Most of the current open source speech corpora for ASR benchmark in the
literature remain small size and lack of domain diversities. For example, the
commonly used English speech corpus - Librispeech [23], which includes about
1000 hours reading speech from audiobook, currently has a word error rate
(WER) of 1.9% on its test-clean benchmark. However, industrial ASR systems are
usually trained with tens of thousands of hours of data with acoustic
diversity and domain coverage. To close the gap between industrial system and
academic research, we notice that several large-scale multi-domain English
corpora, including The People’s Speech [24], MLS [25] and GigaSpeech [26], are
made available recently. The representative GigaSpeech consists of 10000 hours
of high quality transcribed English speech for supervised ASR training and
40000 hours audio in total for semi-supervised or unsupervised training,
contributing to the research community for developing more generalized ASR
systems. Comparing with those English corpora, the largest open source
Mandarin speech data is AIShell-2 [27], including 1000 hours speech recorded
in a quiet environment and having a state-of-the-art character error rate of
5.35%. It is too simple to do further research and ASR systems developed based
on it may be susceptible to performance degradation in the complex real-world
scenarios. In addition, current open source Mandarin corpora are also unable
to train a well generalized pre-trained model, since both the Wav2vec 2.0
large model [20] and the XLSR-53 model [28] are trained based on more than
50000 hours of English speech data.

In this work, we release WenetSpeech, a large multi-domain Mandarin corpus
licensed for non-commercial usage under CC-BY 4.0. “We” means connection and
sharing, while “net” means all of the data are collected from the Internet
which is repository for diversity. The key features of WenetSpeech include:

  * •

Large scale. 10000+ hours labeled data, 2400+ hours weakly labeled data, and
about 10000 hours unlabeled data are provided, resulting in 22400+ hours audio
in total.

  * •

Diverse. The data are collected from multiple speaking styles, scenarios,
domains, topics, and noisy conditions.

  * •

Extensible. An extensible metadata is designed to extend the data in the
future.

To the best of our knowledge, WenetSpeech is the current largest open source
Mandarin speech corpus with domain diversity to satisfy various speech
recognition tasks. In Section 2, we first introduce the construction procedure
of WenetSpeech with a reliable pipeline to obtain high-quality transcriptions,
including OCR-based caption recognition on Youtube video, ASR-based automatic
transcription on Podcast audio, as well as a new end-to-end label error
detection approach. The corpus composition is described in Section 3 and
baseline benchmarks built on Kaldi, ESPnet and WeNet toolkits are introduced
in Section 4. We believe our corpus will bring benefit to research community
for developing more generalized ASR systems.

##  2 Creation Pipeline

In this section, we introduce the detailed creation pipeline of our
WenetSpeech corpus, including original audio collection, audio/text
segmentation candidate generation, and candidate calibration.

###  2.1 Stage 1: Audio Collection

In the beginning, we manually define the domains into 10 categories, which
including audiobook, commentary, documentary, drama, interview, reading, talk,
variety, and others. Then, we collected and tagged the audio files from
YouTube and Podcast playlists according to our selected categories.
Especially, for the YouTube data, the videos are also downloaded for preparing
the audio/text segmentation candidates with our OCR system. For Podcast, since
the manually transcribed Mandarin data is limited, we only considered the
category information and prepared to transcribed it by a high-quality ASR
system.

###  2.2 Stage 2: Candidates Generation

In this part, we introduce the specific pipelines to obtain the audio/text
segmentation candidates from YouTube data by an OCR system and Podcast data by
a high-quality ASR system. At last, text
normalization111https://github.com/speechio/chinese_text_normalization
technique is applied to all the candidates.

####  2.2.1 YouTube OCR

As Figure 1 shown, an OCR-based pipeline is applied for generating candidates
from embedded subtitles on YouTube videos.

  1. 1.

Text Detection: apply CTPN [29] based text detection on each frame image in
the video.

  2. 2.

Subtitle Validation: mark frame $t$ as the start point of a specific subtitle
phrase, when a phrase of text is detected at the bottom of the screen for
subtitles at frame $t$.

  3. 3.

Subtitle Change Detection: compute the structural similarity (SSIM) of
subtitle area frame by frame until a change is detected at frame $t+n$. Then,
the frame $t+n-1$ is marked as the the end point of this subtitle phrase.

  4. 4.

Text Recognition: a CRNN-CTC [30] based text recognition approach is used to
recognize the detected subtitle area.

  5. 5.

Audio/Text Pair: prepare each audio/text pair segmentation candidate with the
corresponding (start point, end point, subtitle phrase) tuple.

Fig. 1: OCR based YouTube data collection pipeline

To verify whether the proposed OCR-based pipeline is reliable, we randomly
extracted 5000 subtitle transcriptions from the YouTube data with different
themes and manually annotated them as benchmarks by professionals for testing
the Text Recognition module. Finally, we obtain 98% accuracy on the test set
and confirm the reliability of our OCR-based pipeline for WenetSpeech corpus.

(a) Audiobook

(b) Game commentary

(c) Drama

(d) Lecture

Fig. 2: Example outputs of the OCR pipeline

Figure 2 shows 4 typical examples of our OCR-based system. The results of the
Text Detection module are marked with boxes. If the box is in a reasonable
subtitle area, it will be marked as red, and then, the subtitle box is further
processed by the Text Recognition module. At last, the recognition result is
shown above each subtitle box.

In addition, we find that some annotators prefer to split a long subtitle
phrase into many pieces for a video, so that the problem of audio and subtitle
asynchronous is introduced. This leads an inaccurate subtitle boundary
detection problem to our OCR system. To alleviate it, we merge the consecutive
video phrases until the audio is over 8 seconds.

####  2.2.2 Podcast Transcription

We use a third-party commercial ASR transcription system to transcribe all the
Podcast data. The transcription system is one of the best system on the public
benchmark platform222https://github.com/SpeechColab/Leaderboard, and more than
95% accuracy rates have been achieved in most of the testing scenarios,
including news, reading, talk show, conversation, education, games, TV, drama,
and so on.

The transcription system first segments the original audio into short segments
by a VAD module, and then the audio/text pair segmentation candidates are
generated by speech recognition.

###  2.3 Stage 3: Candidates Validation

Although the used OCR system and transcription system are high-quality enough,
the errors from candidate generation, such as subtitle annotation error,
timestamp inaccuracy, OCR mistake, transcription word error, and text
normalization error, are still unavoidable. To further improve the quality of
our WenetSpeech corpus, we apply the following validation approach to classify
the YouTube OCR and Podcast transcription candidates according to their
confidences and filter out the extremely bad candidates.

####  2.3.1 Force Alignment Graph

Here, we propose an novel CTC-based end-to-end force alignment approach to
detect the transcription error. The transcription is first segmented by the
model unit of CTC, and then a force alignment graph (L) is built for each
candidate as shown in Figure 3. The key features of the alignment graph are:

  1. 1.

The oracle transcription alignment path is included.

  2. 2.

Arbitrary deletion operation at any position is allowed through tag ⟨del⟩ with
penalty $p_{1}$.

  3. 3.

Arbitrary insertion or substitution at any position is allowed. From each
reasonable position, a start tag ⟨is⟩ and a end tag ⟨/is⟩ are connected to a
global filler state. On this filler state, each CTC modeling unit has a
corresponding self-loop arc with penalty $p_{2}$, which is presented by tag
⟨gbg⟩.

This makes it possible to capture the error between the audio and the
corresponding transcription through decoding technique.

Compared with traditional hybrid validation approach which is used in
Librispeech, our proposed approach is a pure end-to-end approach. There is no
need for HMM typologies, lexicon, language model components, or careful design
of the filler state. So the proposed novel approach simplifies the whole
pipeline a lot. The force alignment graph is implemented by the WeNet toolkit,
and it is publicly available
333https:github.com/wenet-e2e/wenet/blob/main/runtime/core/bin/
label_checker_main.cc.

Fig. 3: An example force alignment graph L of ”不忘初心”

####  2.3.2 Label Error Detection

After defining the force alignment graph L, it is further composed with the
CTC topology graph T [31] to build the final force decoding graph
$\textit{F}=\textit{T}\circ\textit{L}$ for label error detection and
validation.

In addition, we assign confidence for each candidate by it’s reference (ref)
and the force decoding hypothesis (hyp). The confidence $c$ is computed as

$c=1-\frac{\text{EditDistance}(ref,hyp)}{\max(\text{len}(ref),\text{len}(hyp))}.\vspace{-0.5em}$

With the confidence, we classify the audio/text segmentation candidates of our
WenetSpeech corpus into Strong Label and Weak Label sets and even filter out
the extremely ones to Others set. Figure 4 shows two real examples that we
find by applying label error detection. In Case 1, human subtitle error was
successfully detected. In Case 2, OCR error was successfully detected.

Please note the model used in the transcription system and force alignment
system are developed and trained with different model methods and data.
$p_{1}$ is set to 2.3 and $p_{2}$ is set to 4.6 in our pipeline.

Fig. 4: Examples of label error detection

##  3 The WenetSpeech Corpus

In this section, we describe the metadata, audio format, partition by
confidence, data diversity, and training and evaluation set design of our
WenetSpeech corpus. Instructions and scripts are available at WenetSpeech
GitHub repo444https://github.com/wenet-e2e/WenetSpeech.

###  3.1 Metadata and Audio Format

We save all the metadata information to a single JSON file. Local path,
original public URL, domain tags, md5, and segments are provided for each
audio. And timestamp, label, confidence, subset information are provided for
each segment. The design is extensible, and we are planning to add more
diverse data in the future.

The original audio files are downloaded and converted to 16k sampling rate,
single-channel, and 16-bit signed-integer format. Then Opus compression is
applied at an output bit rate of 32 kbps to reduce the size of the WenetSpeech
corpus.

###  3.2 Size and Confidence

Table 1: WenetSpeech partition Set | Confidence | Hours
---|---|---
Strong Label | [0.95, 1.00] | 10005
Weak Label | [0.60, 0.95) | 2478
Others | / | 9952
Total(hrs) | / | 22435

We assign confidence for each valid segment which measures the label quality,
where the confidence in defined in Section 2.3.2. As shown in Table 1, we
select 10005 hours Strong Label data, whose confidence is greater than 0.95,
as the supervised training data. The 2478 hours Weak Label data, whose
confidence is between 0.60 and 0.95, is reserved in our metadata for semi-
supervised or other usage. At last, Others represent all invalid data (i.e.
the confidence of data is less than 0.6 or unrecognized) for speech
recognition task. In summary, WenetSpeech has 22435 hours of raw audio.

###  3.3 Training Data Diversity and Subsets

We tag all the training data with its source and domain. All of the training
data is from Youtube and Podcast. As shown in Table 2, we classify the data
into 10 groups according to its category. Please note about 4k hours of data
is from drama, which is a special domain with a wide range of themes, topics
and scenarios, which may cover any kind of other categories.

Table 2: Training data in different domains with duration (hrs) Domain | Youtube | Podcast | Total
---|---|---|---
audiobook | 0 | 250.9 | 250.9
commentary | 112.6 | 135.7 | 248.3
documentary | 386.7 | 90.5 | 477.2
drama | 4338.2 | 0 | 4338.2
interview | 324.2 | 614 | 938.2
news | 0 | 868 | 868
reading | 0 | 1110.2 | 1110.2
talk | 204 | 90.7 | 294.7
variety | 603.3 | 224.5 | 827.8
others | 144 | 507.5 | 651.5
Total | 6113 | 3892 | 10005

As shown in Table 3, we provide 3 training subsets, namely S, M and L for
building ASR systems on different data scales. Subsets S and M are sampled
from all the training data which have the oracle confidence 1.0.

Table 3: The training data subsets Training Subsets | Confidence | Hours
---|---|---
L | [0.95, 1.0] | 10005
M | 1.0 | 1000
S | 1.0 | 100

###  3.4 Evaluation Sets

We will release the following evaluation datasets associated with WenetSpeech,
and the major information is summarized in Table 4.

  1. 1.

Dev, is specifically designed dataset for some speech tools which require
cross-validation in training.

  2. 2.

Test_Net, is a matched test set from the internet. Compared with the training
data, it also covers several popular and difficult domains like game
commentary, live commerce, etc.

  3. 3.

Test_Meeting, is a mismatched test set since it is a far-field,
conversational, spontaneous, and meeting speech dataset. It is sampled from
197 real meetings in a variety of rooms. Its topics cover education, real
estate, finance, house and home, technology, interview and so on.

The three evaluation sets are carefully checked by professional annotators to
ensure the transcription quality.

Table 4: The WenetSpeech evaluation sets Evaluation Sets | Hours | Source
---|---|---
Dev | 20 | Internet
Test_Net | 23 | Internet
Test_Meeting | 15 | Real meeting

##  4 Experiments

In this section, we introduce the baseline systems and experimental results on
three popular speech recognition toolkits, Kaldi [14], ESPnet [17] and WeNet
[18].

###  4.1 Kaldi
Benchmark555https://github.com/wenet-e2e/WenetSpeech/tree/main/toolkits/kaldi

The Kaldi baseline implements a classical chain model [32] using various
amounts of WeNetSpeech data (i.e. S, M, L). We choose the open source
vocabulary, BigCiDian666https://github.com/speechio/BigCiDian, as our lexicon.
And we segment our transcriptions with the open source word segmentation
toolkit, jieba [33]. First, we train a GMM-HMM model to obtain the training
alignments. Then, we train a chain model, which stacks 6 convolutional neural
network (CNN) layers, 9 factored time-delay neural network (TDNN-F) layers
[34], 1 time-restricted attention layer [35] ($H=30$), 2 projected long short-
term memory (LSTMP) with TDNN-F blocks. We feed the 40 dimensional filterbank
(FBank) features and 100 dimensional i-vector features as the input. In order
to be consistent with the other systems, we only use SpecAugment [36]
technique and abandon the speed/volume perturbation techniques. The chain
model is trained by LF-MMI criterion with cross-entropy loss (10 epochs for
subset S, and 4 epochs for subset M and L). A 3-gram language model (LM) is
used for decoding and generating the lattice. Finally, a recurrent neural
network LM (RNNLM) is further adopted to rescore the lattices. The 3-gram and
RNNLM are both trained on all the WenetSpeech transcriptions.

###  4.2 ESPnet
Benchmark777https://github.com/wenet-e2e/WenetSpeech/tree/main/toolkits/espnet

The ESPnet baseline employs a Conformer model [13, 37] which is designed to
capture the global context with the multi-head self-attention module and learn
the local correlations synchronously with the convolution module. Our
Conformer model consists of a 12-block Conformer encoder
($d^{\text{ff}}=2048,H=8,d^{\text{att}}=512,\text{CNN}_{\text{kernel}}=15$)
and a 6-block Transformer [38] decoder ($d^{\text{ff}}=2048,H=8$). A set of
5535 Mandarin characters and 26 English letters is used as the modeling units.
The objective is a logarithmic linear combination of the CTC ($\lambda=0.3$)
and attention objectives. Label smoothing is applied to the attention
objective. During data preparation, we generate 80-dimensional FBank features
with a 32ms window and a 8ms frame shift. SpecAugment with 2 frequency masks
($F=30$) and 2 time masks ($T=40$), and global CMVN technique are used as data
pre-processing. During training, we choose the Adam optimizer with the maximum
learning rate of $0.0015$. The Noam learning rate scheduler with 30k warm-up
steps is used. The model was trained with dynamic batching skill for 30
epochs. At last, the last 10 best checkpoints were averaged to be the final
model. For decoding, the ESPNet system follows the joint CTC/Attention beam
search strategy [39].

###  4.3 WeNet
Benchmark888https://github.com/wenet-e2e/WenetSpeech/tree/main/toolkits/wenet

The WeNet baseline implements a U2 model [18], which unifies streaming and
non-streaming end-to-end (E2E) speech recognition in a single model. The basic
setup of our WeNet model is same as the ESPnet model except the following
minor points: 1) We prepare 80-dimensional FBank features with a 25ms window
and a 10ms frame shift. SpecAugment with 2 frequency masks ($F=30$) and 3 time
masks ($T=50$) and global CMVN technique are applied on the top of our
features. 2) The max trainable epoch is 25. Models of the last 10 epochs were
averaged to be the final model. The key difference between WeNet and ESPNet is
different decoding strategies. Specifically, different from ESPNet’s auto-
regressive decoding strategy, Wenet generates the N-Best hypotheses by the CTC
branch and rescores them by the attention branch.

Table 5: Results (MER%) on different test sets for baseline systems trained using WenetSpeech training subset L Toolkit | Dev | Test_Net | Test_Meeting | AIShell-1
---|---|---|---|---
Kaldi | 9.07 | 12.83 | 24.72 | 5.41
ESPNet | 9.70 | 8.90 | 15.90 | 3.90
WeNet | 8.88 | 9.70 | 15.59 | 4.61
Table 6: Kaldi baseline results (MER%) for different WenetSpeech training subsets SubSet | Dev | Test_Net | Test_Meeting | AIShell-1
---|---|---|---|---
L | 9.07 | 12.83 | 24.72 | 5.41
M | 9.81 | 14.19 | 28.22 | 5.93
S | 11.70 | 17.47 | 37.27 | 7.66

###  4.4 Experimental Results

We must announce that the results listed here are purely for the purpose of
providing a baseline system for each toolkit. They might not reflect the
state-of-the-art performance of each toolkit.

In Table 5, we report the experimental results in Mixture Error Rate (MER)
[40], which considers Mandarin characters and English words as the tokens in
the edit distance calculation, on three designed test sets and one well-known,
publicly available test set (i.e. AIShell-1 [41] test) with Kaldi, ESPNet and
WeNet toolkits respectively. The good performance on AIShell-1 reflects the
diversity and reliability of our WenetSpeech corpus. And the results on our
designed test sets reflect they are quite challenging. In Table 6, we provide
the Kaldi baseline results for difference scale WenetSpeech subsets. As the
growth of the data amount, the performance goes up steadily.

##  5 Acknowledgements

We thank Jiayu Du and Guoguo Chen for their suggestions on this work. We thank
Tencent Ethereal Audio Lab and Xi’an Future AI Innovation Center for providing
hosting service for WenetSpeech. We also thank MindSpore for the support of
this work, which is a new deep learning computing
framwork999https://www.mindspore.cn/. Our gratitude goes to Lianhui Zhang and
Yu Mao for collecting some of the YouTube data.

## References

  * [1] Geoffrey Hinton, Li Deng, Dong Yu, George E. Dahl, Abdel-rahman Mohamed, Navdeep Jaitly, Andrew Senior, Vincent Vanhoucke, Patrick Nguyen, Tara N. Sainath, Brian Kingsbury,  “Deep neural networks for acoustic modeling in speech recognition,”  in IEEE Signal Processing Magazine, 2012, vol. 29, no. 6, pp. 82–97.
  * [2] George E Dahl, Dong Yu, Li Deng, Alex Acero,  “Context-dependent pre-trained deep neural networks for large-vocabulary speech recognition,”  in IEEE Transactions on Audio, Speech, and Language Processing (TASLP), 2012, vol. 20, no. 1, pp. 30–42.
  * [3] Alex Graves, Santiago Fernández, Faustino Gomez, Jürgen Schmidhuber,  “Connectionist temporal classification: Labelling unsegmented sequence data with recurrent neural networks,”  in ACM International Conference on Machine Learning (ICML), 2006, pp. 369–376.
  * [4] Dario Amodei, Sundaram Ananthanarayanan, Rishita Anubhai, Jingliang Bai, Eric Battenberg, Carl Case, Jared Casper, Bryan Catanzaro, Qiang Cheng, Guoliang Chen, et al.,  “Deep speech 2: End-to-end speech recognition in English and Mandarin,”  in ACM International Conference on Machine Learning (ICML), 2016, pp. 173–182.
  * [5] Alex Graves,  “Sequence transduction with recurrent neural networks,”  in ACM International Conference on Machine Learning Representation Learning Workshop (ICML), 2012.
  * [6] Alex Graves, Abdel-rahman Mohamed, Geoffrey Hinton,  “Speech recognition with deep recurrent neural networks,”  in IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2013, pp. 6645–6649.
  * [7] Xiong Wang, Zhuoyuan Yao, Xian Shi, Lei Xie,  “Cascade rnn-transducer: Syllable based streaming on-device mandarin speech recognition with a syllable-to-character converter,”  in IEEE Spoken Language Technology Workshop (SLT), 2021, pp. 15–21.
  * [8] Xiong Wang, Sining Sun, Lei Xie, Long Ma,  “Efficient conformer with prob-sparse attention mechanism for end-to-endspeech recognition,”  in ISCA Conference of the International Speech Communication Association (Interspeech), 2021, pp. 4578–4582.
  * [9] Jan K Chorowski, Dzmitry Bahdanau, Dmitriy Serdyuk, Kyunghyun Cho, Yoshua Bengio,  “Attention-based models for speech recognition,”  in Annual Conference on Neural Information Processing Systems (NIPS), 2015, pp. 577–585.
  * [10] William Chan, Navdeep Jaitly, Quoc Le, Oriol Vinyals,  “Listen, attend and spell: A neural network for large vocabulary conversational speech recognition,”  in IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2016, pp. 4960–4964.
  * [11] Suyoun Kim, Takaaki Hori, Shinji Watanabe,  “Joint CTC-attention based end-to-end speech recognition using multi-task learning,”  in IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2017, pp. 4835–4839.
  * [12] Linhao Dong, Shuang Xu, Bo Xu,  “Speech-Transformer: A no-recurrence sequence-to-sequence model for speech recognition,”  in IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2018, pp. 5884–5888.
  * [13] Anmol Gulati, James Qin, Chung-Cheng Chiu, Niki Parmar, Yu Zhang, Jiahui Yu, Wei Han, Shibo Wang, Zhengdong Zhang, Yonghui Wu, Ruoming Pang,  “Conformer: Convolution-augmented transformer for speech recognition,”  in ISCA Conference of the International Speech Communication Association (Interspeech), 2020, pp. 5036–5040.
  * [14] Daniel Povey, Arnab Ghoshal, Gilles Boulianne, Lukáš Burget, Ondřej Glembek, Nagendra Goel, Mirko Hannemann, Petr Motlíček, Yanmin Qian, Petr Schwarz, Jan Silovský, Georg Stemmer, Karel Veselý,  “The Kaldi speech recognition toolkit,”  in IEEE Workshop on Automatic Speech Recognition and Understanding (ASRU), 2011.
  * [15] K-F Lee, H-W Hon, Raj Reddy,  “An overview of the SPHINX speech recognition system,”  in IEEE Transactions on Acoustics, Speech, and Signal Processing (TASLP), 1990, vol. 38, no. 1, pp. 35–45.
  * [16] Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, Michael Auli,  “Fairseq: A fast, extensible toolkit for sequence modeling,”  in The Annual Conference of the North American Chapter of the Association for Computational Linguistics (NAACL), 2019, pp. 48–53.
  * [17] Shinji Watanabe, Takaaki Hori, Shigeki Karita, Tomoki Hayashi, Jiro Nishitoba, Yuya Unno, Nelson Enrique Yalta Soplin, Jahn Heymann, Matthew Wiesner, Nanxin Chen, Adithya Renduchintala, Tsubasa Ochiai,  “ESPnet: End-to-end speech processing toolkit,”  in ISCA Conference of the International Speech Communication Association (Interspeech), 2018, pp. 2207–2211.
  * [18] Zhuoyuan Yao, Di Wu, Xiong Wang, Binbin Zhang, Fan Yu, Chao Yang, Zhendong Peng, Xiaoyu Chen, Lei Xie, Xin Lei,  “WeNet: Production oriented streaming and non-streaming end-to-end speech recognition toolkit,”  in ISCA Conference of the International Speech Communication Association (Interspeech), 2021, pp. 4054––4058.
  * [19] Steffen Schneider, Alexei Baevski, Ronan Collobert, Michael Auli,  “wav2vec: Unsupervised pre-training for speech recognition,”  in ISCA Conference of the International Speech Communication Association (Interspeech), 2019, pp. 3465––3469.
  * [20] Alexei Baevski, Henry Zhou, Abdelrahman Mohamed, Michael Auli,  “wav2vec 2.0: A framework for self-supervised learning of speech representations,”  in Annual Conference on Neural Information Processing Systems (NeurIPS), 2020, vol. 33, pp. 12449–12460.
  * [21] Wei-Ning Hsu, Yao-Hung Hubert Tsai, Benjamin Bolte, Ruslan Salakhutdinov, Abdelrahman Mohamed,  “HuBERT: How much can a bad teacher benefit ASR pre-training?,”  in IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2021, pp. 6533–6537.
  * [22] Alexei Baevski, Wei-Ning Hsu, Alexis Conneau, Michael Auli,  “Unsupervised speech recognition,”  in Annual Conference on Neural Information Processing Systems (NeurIPS), 2021, vol. 34.
  * [23] Vassil Panayotov, Guoguo Chen, Daniel Povey, Sanjeev Khudanpur,  “Librispeech: An ASR corpus based on public domain audio books,”  in IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2015, pp. 5206–5210.
  * [24] Daniel Galvez, Greg Diamos, Juan Manuel Ciro Torres, Juan Felipe Cerón, Keith Achorn, Anjali Gopi, David Kanter, Max Lam, Mark Mazumder, Vijay Janapa Reddi,  “The people’s speech: A large-scale diverse english speech recognition dataset for commercial usage,”  in Annual Conference on Neural Information Processing Systems (NeurIPS), 2021.
  * [25] Vineel Pratap, Qiantong Xu, Anuroop Sriram, Gabriel Synnaeve, Ronan Collobert,  “Mls: A large-scale multilingual dataset for speech research,”  in ISCA Conference of the International Speech Communication Association (Interspeech), 2020, pp. 2757–2761.
  * [26] Guoguo Chen, Shuzhou Chai, Guan-Bo Wang, Jiayu Du, Wei-Qiang Zhang, Chao Weng, Dan Su, Daniel Povey, Jan Trmal, Junbo Zhang, Mingjie Jin, Sanjeev Khudanpur, Shinji Watanabe, Shuaijiang Zhao, Wei Zou, Xiangang Li, Xuchen Yao, Yongqing Wang, Zhao You, Zhiyong Yan,  “Gigaspeech: An evolving, multi-domain ASR corpus with 10,000 hours of transcribed audio,”  in ISCA Conference of the International Speech Communication Association (Interspeech), 2021, pp. 3670–3674.
  * [27] Jiayu Du, Xingyu Na, Xuechen Liu, Hui Bu,  “Aishell-2: Transforming mandarin ASR research into industrial scale,”  in arXiv preprint arXiv:1808.10583, 2018.
  * [28] Alexis Conneau, Alexei Baevski, Ronan Collobert, Abdelrahman Mohamed, Michael Auli,  “Unsupervised cross-lingual representation learning for speech recognition,”  in ISCA Conference of the International Speech Communication Association (Interspeech), 2021, pp. 2426–2430.
  * [29] Zhi Tian, Weilin Huang, Tong He, Pan He, Yu Qiao,  “Detecting text in natural image with connectionist text proposal network,”  in Springer European Conference on Computer Vision (ECCV), 2016, pp. 56–72.
  * [30] Baoguang Shi, Xiang Bai, Cong Yao,  “An end-to-end trainable neural network for image-based sequence recognition and its application to scene text recognition,”  in IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 2016, vol. 39, no. 11, pp. 2298–2304.
  * [31] Yajie Miao, Mohammad Gowayyed, Florian Metze,  “EESEN: End-to-end speech recognition using deep RNN models and WFST-based decoding,”  in IEEE Workshop on Automatic Speech Recognition and Understanding (ASRU), 2015, pp. 167–174.
  * [32] Daniel Povey, Vijayaditya Peddinti, Daniel Galvez, Pegah Ghahremani, Vimal Manohar, Xingyu Na, Yiming Wang, Sanjeev Khudanpur,  “Purely sequence-trained neural networks for ASR based on lattice-free MMI,”  in ISCA Conference of the International Speech Communication Association (Interspeech), 2016, pp. 2751–2755.
  * [33] J Sun,  “Jieba chinese word segmentation tool,” 2012.
  * [34] Daniel Povey, Gaofeng Cheng, Yiming Wang, Ke Li, Hainan Xu, Mahsa Yarmohammadi, Sanjeev Khudanpur,  “Semi-orthogonal low-rank matrix factorization for deep neural networks,”  in ISCA Conference of the International Speech Communication Association (Interspeech), 2018, pp. 3743–3747.
  * [35] Daniel Povey, Hossein Hadian, Pegah Ghahremani, Ke Li, Sanjeev Khudanpur,  “A time-restricted self-attention layer for ASR,”  in IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2018, pp. 5874–5878.
  * [36] Daniel S Park, William Chan, Yu Zhang, Chung-Cheng Chiu, Barret Zoph, Ekin D Cubuk, Quoc V Le,  “SpecAugment: A simple data augmentation method for automatic speech recognition,”  in ISCA Conference of the International Speech Communication Association (Interspeech), 2019, pp. 2613–2617.
  * [37] Pengcheng Guo, Florian Boyer, Xuankai Chang, Tomoki Hayashi, Yosuke Higuchi, Hirofumi Inaguma, Naoyuki Kamo, Chenda Li, Daniel Garcia-Romero, Jiatong Shi, Jing Shi, Shinji Watanabe, Kun Wei, Wangyou Zhang, Yuekai Zhang,  “Recent developments on ESPnet toolkit boosted by conformer,”  in IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2021, pp. 5874–5878.
  * [38] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, Illia Polosukhin,  “Attention is all you need,”  in Annual Conference on Neural Information Processing Systems (NeurIPS), 2017, pp. 5998–6008.
  * [39] Takaaki Hori, Shinji Watanabe, John R Hershey,  “Joint CTC/attention decoding for end-to-end speech recognition,”  in Annual Meeting of the Association for Computational Linguistics (ACL), 2017, pp. 518–529.
  * [40] Xian Shi, Qiangze Feng, Lei Xie,  “The ASRU 2019 mandarin-english code-switching speech recognition challenge: open datasets, tracks, methods and results,”  in IEEE Workshop on Automatic Speech Recognition and Understanding (ASRU), 2020.
  * [41] Hui Bu, Jiayu Du, Xingyu Na, Bengu Wu, Hao Zheng,  “Aishell-1: An open-source mandarin speech corpus and a speech recognition baseline,”  in IEEE Conference of the Oriental Chapter of the International Coordinating Committee on Speech Databases and Speech I/O Systems and Assessment (O-COCOSDA), 2017, pp. 1–5.


# Towards Large-Scale Interpretable Knowledge Graph Reasoning for Dialogue
Systems

Yi-Lin Tuan1, Sajjad Beygi2, Maryam Fazel-Zarandi2
Qiaozi Gao2, Alessandra Cervone2, William Yang Wang1
1 University of California, Santa Barbara 2 Amazon Alexa AI
{ytuan<EMAIL_ADDRESS>
{beygi, fazelzar, qzgao<EMAIL_ADDRESS>

###### Abstract

Users interacting with voice assistants today need to phrase their requests in
a very specific manner to elicit an appropriate response. This limits the user
experience, and is partly due to the lack of reasoning capabilities of
dialogue platforms and the hand-crafted rules that require extensive labor.
One possible way to improve user experience and relieve the manual efforts of
designers is to build an end-to-end dialogue system that can do reasoning
itself while perceiving user’s utterances. In this work, we propose a novel
method to incorporate the knowledge reasoning capability into dialogue systems
in a more scalable and generalizable manner. Our proposed method allows a
single transformer model to directly walk on a large-scale knowledge graph to
generate responses. To the best of our knowledge, this is the first work to
have transformer models generate responses by reasoning over differentiable
knowledge graphs. We investigate the reasoning abilities of the proposed
method on both task-oriented and domain-specific chit-chat dialogues.
Empirical results show that this method can effectively and efficiently
incorporate a knowledge graph into a dialogue system with fully-interpretable
reasoning paths.

##  1 Introduction

Nowadays, dialogue systems are ubiquitous in customer service and voice-based
assistants. One of the main uses of this technology is supporting humans in
accomplishing tasks that might require accessing and navigating large
knowledge bases (e.g., movies search). A dialogue system architecture is
typically composed of a natural language understanding (NLU) module, a
dialogue management (DM) module, and a natural language generation (NLG)
module Jurafsky and Martin (2009); Williams et al. (2016). First, the NLU
component extracts a meaning representation from the user utterance based on
which the DM generates the next system action by reasoning over the meaning
representation and communicating with external applications if necessary. For
example, the DM may retrieve information from external knowledge graphs (KG)
to answer the user’s query based on the dialogue history. This process
requires the DM to convert the output of NLU to a query to be issued to the
backend. Given the difficulty of this step, which is often domain-dependent,
the DM component might require the design of hand-crafted rules. However, such
rules are usually not scalable to different applications. They could require
considerable effort to cover all possible cases/dialogue flows, leading to
expensive costs to design new applications. Moreover, in several cases, users
interacting with such assistants are forced to formulate specific queries in
order to accomplish their objective, which might break user engagement.

To alleviate the problem of having to design expensive hand-crafted rules and
breaking user experience, recent works have explored the possibility of
building end-to-end dialogue systems Wen et al. (2017) and all-in-one response
generation models Serban et al. (2016). Among them, since graph is one of the
main structure to store knowledge, recent research (Ghazvininejad et al.,
2018; Zhou et al., 2018; Moon et al., 2019; Tuan et al., 2019; Yang et al.,
2020) has proposed methods to generate natural language responses according to
both the dialogue history and external knowledge graph. Despite these
innovative and inspiring methods, there are some shortcomings. For instance,
these methods are either not fully-interpretable or limited to small-scale
knowledge graphs.

In this paper, we propose a novel dialogue differentiable knowledge graph
model (DiffKG). The DiffKG is a single transformer model that directly (1)
generates a sequence of relations to perform multi-hop reasoning on a reified
KG representation proposed by Cohen et al. (2019), and then (2) generates
responses using the retrieved entities. To the best of our knowledge, this is
the first dialogue model that can directly walk on a large-scale KG with
flexibility and interpretability. DiffKG allows having flexible entity values
in the KG and handling novel entity values with an arbitrarily defined number
of tokens. The reasoning path of DiffKG consists of the predicted relations,
thus allowing for transparency.

We run extensive experiments to test DiffKG performance on KG-grounded
dialogues. We select Stanford Multi-domain Dialogues (SMD) Eric et al. (2017)
and propose a new dataset, SMD-Reasoning, to simulate scenarios requiring
multiple reasoning types and select the OpenDialKG Moon et al. (2019) to
simulate scenarios requiring large-scale KG reasoning without preprocessing.
We then compare DiffKG with state-of-the-art models on SMD and OpenDialKG and
an additional baseline that flattens KGs into a textual form from which
transformers can learn. Empirically, our experiments show that DiffKG can
effectively be trained on large-scale KGs and demonstrate its robustness with
modified triplets in a KG. From the perspective of computation, DiffKG leads
to relatively low extra time and memory usage compared to transformer models
not using any KG information.

In summary, our contributions are: 1) We propose DiffKG, a novel method that
can effectively and flexibly incorporate large-scale KG; 2) We demonstrate
that DiffKG is a model-agnostic method and can be applied to different model
architectures; 3) We show that DiffKG is an interpretable method with low add-
on latency at inference time. Our code and processed datasets are released in
https://github.com/Pascalson/DiffKG-Dialog.

Reasoning Type | Example | Related Info. in KG
---|---|---
Semantic Form | KG reasoning | U: I need unleaded gas. |
R: inform Valero, 4 miles
5pt. |  Logical Reasoning | True/False | U: Is it going to snow this week at Corona? |
|  |  | R: Yes |
5pt. | Selection | U: give me the direction to the nearest shopping mall. |
|  |  | R: inform Stanford Shopping Center, 3 miles |
5pt. | Extraction | U: What gas stations are here? |  No gas station in the available KG
|  |  | R: include poi_type gas station |
NL Form | KG reasoning | U: Have you listen to any of the singer Kesha’s song? |
R: I do enjoy in her music, especially “Your Love Is My Drug”

Table 1: Example of different reasoning types and output formats (semantic and
natural language forms) in a dialogue system with the related information in
the accessible KGs.

##  2 Related Work

Recent years have seen a surge of new methods proposing end-to-end models that
try to both understand natural language input text and search information. Two
of the widely explored tasks are question-answering (QA) and dialogue
generation.

#### QA.

Multiple QA methods Weston et al. (2015); Yin et al. (2016); Hao et al.
(2017); Rajpurkar et al. (2018); Verga et al. (2020); Eisenschlos et al.
(2021) have been proposed to tackle tasks that go beyond what is explicitly
stated in the linguistic context Storks et al. (2019). For example, the
benchmarks Mihaylov et al. (2018); Reddy et al. (2019); Khot et al. (2020);
Lin et al. (2021) are particularly useful for the model to extract information
from external knowledge bases to answer questions. Nonetheless, these studies
mostly take the retrieved information from KG as the answer to a single
question, while in dialogue we have to formulate an informative response to
multi-turn dialogue history.

#### Dialogue Generation.

Recent works have investigated the grounded dialogue generation. These methods
can be divided into three main categories. First, Dinan et al. (2018); Zhao et
al. (2019); Tuan et al. (2020); Kim et al. (2020) extract useful knowledge
from unstructured data to generate responses, such as information contained in
passages and speaker’s profiles. Second, Sordoni et al. (2015); Long et al.
(2017); Zhu et al. (2017); Ghazvininejad et al. (2018); Zhou et al. (2018);
Veličković et al. (2018); Joshi et al. (2020); Hosseini-Asl et al. (2020);
Wang et al. (2021) utilize information from knowledge bases (either graphs or
tables) to enhance the dialogue system. They usually train the entities and
relations embeddings of the knowledge bases and incorporate these embeddings
into the input representation to predict the response. Third, Moon et al.
(2019); Tuan et al. (2019); Jung et al. (2020) formulate the reasoning process
more explicitly, as a path traversal over knowledge graphs. These methods
further improve the transparency and explainability of the conversational
agent and share the most similar idea with us. However, they either only
predict the reasoning path without generating responses or need subgraph
sampling to reduce the scale of KG. In this work, our approach uses a
transformer model to jointly predict explicit reasoning paths over a large-
scale knowledge graph and generate dialogue responses based on the reasoning
results.

##  3 Background

###  3.1 Knowledge Graph for Dialogue System

We assume that the knowledge of the system can be represented by a knowledge
graph (KG) $\mathcal{G}=\\{\mathcal{E},\mathcal{R}\\}$, where $\mathcal{E}$
denotes the entities and $\mathcal{R}$ denotes the relations. The knowledge
graph $\mathcal{G}$ contains multiple triples describing the connections among
entities and relations. We denote the $k$-th triple of this graph as
$(e_{k}^{h},r_{k},e_{k}^{t})$ , where $e_{k}^{h}$, $r_{k}$, $e_{k}^{t}$ are
respectively the head entity, relation, and tail entity. The total numbers of
triples, entities, and relations are denoted as $N_{\mathcal{T}}$,
$N_{\mathcal{E}}$, $N_{\mathcal{R}}$, respectively.111An example of the
triples in $\mathcal{G}$ is a triple $e_{k}^{h}=\text{gas station}$,
$r_{k}=\text{IsTypeOf}$, and $e_{k}^{t}=\textrm{Chevron}$. That is, “gas
station is the type of Chevron” to this system.

###  3.2 Response Generation in Dialogue System

If we define the dialogue history as a sequence of tokens that occurred during
the user and system interactions, then a flattened dialogue history can be
written as:

$\displaystyle\mathbf{x}=(x_{1},x_{2},...,x_{m},...,x_{M})$ (1)

where $x_{m}$ is the $m$-th token in the dialogue history with $M$ tokens. In
an end-to-end dialogue system, we assume a dialogue system parameterized by
$\theta$ exists that can predict a probability distribution of responses
$P_{\theta}(\cdot|\mathbf{x},\mathcal{G})$. The generated responses are
sampled from this probability distribution.

Figure 1: The illustration of proposed DiffKG, which leverages a pretrained
transformer model (T5 or GPT2) and the Reified KG. The model generates the
response depending on the predicted relation sequence $[r_{1};...;r_{H}]$,
thus being fully interpretable in terms of the used reasoning path.

##  4 Problem Statement

We focus on understanding the ability of language models in performing
reasoning during a conversation. We consider two tasks that are usually
required in dialogue scenarios and call them semantic form and natural
language (NL) form in Table 1. First, given a dialogue history and a user’s
query, the task of semantic form is to predict the next system action,
corresponding to the output of the DM module, based on the available
knowledge. In this case, we assume the expected output is the essential
knowledge for an NLG module. We argue that this task could help better
evaluate if the response is correct or not and which type of reasoning can be
more successfully handled. Second, given a dialogue history and a user’s
query, the task of the NL form could be to directly output the response given
by the system. This setting with annotated reasoning path can shed light on
understanding if the model can learn to support chit-chat and reasoning at the
same time.

Moreover, we aim to understand models’ reasoning capability both in the form
of logical reasoning and over the provided knowledge. As illustrated in Table
1, by KG reasoning, we refer to the ability of the model to retrieve
information from an arbitrary scaled KG in multiple hops. Meanwhile, we refer
to logical reasoning as the ability of the model to conduct operations such as
evaluating whether a statement is true or false, selecting min/max from a list
of alternatives, and extracting constraints.

We formulate the task that we focus on as follows: given the dialogue history
$\mathbf{x}$ and currently accessible KG $\mathcal{G}$, can we extend a
transformer model to predict a correct response $y$ in either semantic or NL
form? As illustrated in Table 1, this task not only requires the model to
accurately retrieve information from the KG, but also needs to do further
logical operations on the information. To solve this task, a model should also
be able to effectively integrate the dialogue history $\mathbf{x}$ with the KG
$\mathcal{G}$.

##  5 Proposed Approach

Figure 1 illustrates our proposed architecture which contains four main parts:
a dialogue history encoder, a differentiable KG reasoning module, a learnable
logical operations module, and a response decoder (the transformer model).
Note that we experiment with two types of transformers: a causal language
model GPT2 Radford et al. (2019) and an encoder-decoder model T5 Raffel et al.
(2020). For GPT2, we reuse the same encoder that is used at the beginning of
the process, i.e., $f_{enc}$ in Figure 1, as the final transformer that
generates the response token by token. For T5, we reuse the same encoder as
the encoder of the final transformer with a separate decoder that generates
the response. Therefore, this method contains a single transformer model. In
following sections we present each module in detail.

###  5.1 Dialogue History Encoder

We use encoder model to project $\mathbf{x}$ and obtain the dialogue history
embedding through $\tilde{\mathbf{x}}=f_{enc}(\mathbf{x})\in{\rm I\\!R}^{d}$,
where $d$ is the hidden size of the encoder. The embedding
$\tilde{\mathbf{x}}$ is first fed into an operation layer with parameters
$\mathbf{W}_{o}\in{\rm I\\!R}^{d\times d}$. The operation layer predicts the
operation vector $\mathbf{a}=\mathbf{W}_{o}^{T}\tilde{\mathbf{x}}\in{\rm
I\\!R}^{d}$. At the same time, the embedding $\tilde{\mathbf{x}}$ is also fed
into a relation layer with parameters $\mathbf{W}_{r}\in{\rm I\\!R}^{d\times
N_{\mathcal{R}}H}$. The relation layer predicts the concatenation of a
sequence of relations $\mathbf{r}=\\{\mathbf{r}_{h}|1\leq h\leq H\\}$, where
$\mathbf{r}_{h}\in{\rm I\\!R}^{N_{\mathcal{R}}}$ is the relation to be used at
the $h$-th hop in the programmed walking block and $H$ is the maximum number
of hops. The embedding $\tilde{\mathbf{x}}$ is also fed into a checkpoints
layer with parameters $\mathbf{W}_{c}\in{\rm I\\!R}^{d\times 2H}$. This layer
produces the concatenation of a sequence of walk-or-check vectors
$\mathbf{c}=\\{c_{h}|1\leq h\leq H\\}$, where $c_{h}\in{\rm I\\!R}^{2}$ is the
walk-or-check vector at the $h$-th hop to determine the weights of the
programmed walking module and the operation vector.

$\begin{split}&\tilde{\mathbf{x}}=f_{enc}(\mathbf{x})\,,\\\
&\mathbf{a}=\mathbf{W}_{o}^{T}\tilde{\mathbf{x}}\,,\\\
&\mathbf{r}=\mathbf{W}_{r}^{T}\tilde{\mathbf{x}}\,,\\\
&\mathbf{c}=\texttt{softmax}(\mathbf{W}_{c}^{T}\tilde{\mathbf{x}})\,.\\\
\end{split}$ (2)

###  5.2 Differential Knowledge Graph Reasoning

To ensure that our model can scale to larger KGs, we adopt the reified KG
representation proposed by Cohen et al. (2019). The reified KG represents the
graph $\mathcal{G}$ using three sparse matrices: head matrix
$\mathbf{M}_{h}\in{\rm I\\!R}^{N_{\mathcal{T}}\times N_{\mathcal{E}}}$,
relation matrix $\mathbf{M}_{r}\in{\rm I\\!R}^{N_{\mathcal{T}}\times
N_{\mathcal{R}}}$, and tail matrix $\mathbf{M}_{t}\in{\rm
I\\!R}^{N_{\mathcal{T}}\times N_{\mathcal{E}}}$. An entry $(i,e)$ in
$\mathbf{M}_{h}$ or $\mathbf{M}_{t}$ with value $1$ indicates that the $i$-th
triple in the KG has entity $e$ as the head or the tail; an entry $(i,r)$ in
$\mathbf{M}_{r}$ with value $1$ indicates that the $i$-th triple in the
knowledge graph has the relation $r$. Since often in practical settings most
entries in the three matrices are zero, saving them into sparse matrices can
significantly reduce memory consumption Cohen et al. (2019).

After predicting the relation sequence $\mathbf{r}$, we start the graph
traversal from a given set of initial entities
$\mathcal{E}_{0}\subseteq\mathcal{E}$. We first map the initial entities into
a vector $\mathbf{e}_{1}=[\mathbbm{1}(e\in\mathcal{E}_{0}),\forall
e\in\mathcal{E}]$. That is, each entry of $\mathbf{e}_{1}\in{\rm
I\\!R}^{N_{\mathcal{E}}}$ has value 1 if that entity is in the initial
entities list $\mathcal{E}_{0}$, otherwise, the entry is zero. We then predict
the next (temporary) entity vector $\mathbf{e}_{2}$ by conducting a Next
module:

$\mathbf{e}^{r}_{h+1}=\texttt{Next}(\mathbf{e}_{h},\mathbf{r}_{h})\,,$ (3)

where

$\texttt{Next}(\mathbf{e}_{h},\mathbf{r}_{h})=\frac{\mathbf{M}_{t}^{T}(\mathbf{M}_{h}\mathbf{e}_{h}\odot\mathbf{M}_{r}\mathbf{r}_{h})}{||\mathbf{M}_{t}^{T}(\mathbf{M}_{h}\mathbf{e}_{h}\odot\mathbf{M}_{r}\mathbf{r}_{h})||_{2}+\epsilon}\,,$
(4)

Here $\epsilon$ is an arbitrary small number to offset the denominator and
prevent division by zero. We introduce the normalized Next to solve the issue
with the method proposed by Cohen et al. (2019) for knowledge graph completion
defined as
$\texttt{Follow}(\mathbf{e}_{h},\mathbf{r}_{h})=\mathbf{M}_{t}^{T}(\mathbf{M}_{h}\mathbf{e}_{h}\odot\mathbf{M}_{r}\mathbf{r}_{h})$;
since in a dialogue model, we can seldom predict the relation vectors that
perfectly match the entity vectors. That is, if directly using the Follow
module in Cohen et al. (2019), the $||\mathbf{e}_{h}||_{2}$ will not be one
and will vanish as the hop number $h$ increases. Specifically, note that in
our proposed module, the predicted relations $\mathbf{r}_{h}$ are independent
of the traversed entities $\mathbf{e}_{h}$. For instance, finding the
“distance” of “the nearby gas station” is independent of whether the nearby
gas station is “Chevron” or “Shell”.

To allow the model to dynamically select the number of reasoning hops, we add
a relation type “ToSelf” into $\mathcal{R}$ and connect each entity to itself
by “ToSelf”. More specifically, the KG will contain triples
$(e^{h}_{k},r_{k},e^{t}_{k})$ for all $e^{h}_{k}=e^{t}_{k}\in\mathcal{E}$ and
$r_{k}=\texttt{ToSelf}$.

###  5.3 Entity Embeddings

At each hop, we further conduct the operation vectors $\mathbf{a}$ on the
entities weighted by the entity vector $\mathbf{e}_{h}$. First, we tokenize
each entity and represent it by the concatenation of its token embeddings.
This step allows (1) representing entities with longer texts such as phrases
and sentences, and (2) eliminating the effort to retrain entity embeddings
whenever new entity values are added. The entity embeddings can then be
represented as a tensor $\mathbf{E}\in{\rm I\\!R}^{N_{\mathcal{E}}\times
d\times m}$, where $m$ is the maximum number of tokens of entities222In our
experiments, we compute the maximum length of all entities and pad shorter
entities to the length of $m$..

###  5.4 Learnable Logical Operation and Checkpoints

We compute the transformed entity embeddings by element-wise multiplication of
the entity embeddings $\mathbf{E}$ with the entity vector $\mathbf{e}_{h}$ at
the $h$-th hop. Next, the dot product of the operation vectors and the
transformed entity embeddings is passed to a softmax layer as the entity
vector at the next hop:

$\mathbf{e}^{a}_{h+1}=\texttt{softmax}\left(\mathbf{a}(\mathbf{E}\odot\mathbf{e}_{h})\right)\,,$
(5)

Further, at the $h$-th hop we use the walk-or-check vector $\mathbf{c}_{h}$ to
combine the Next and operation modules above. The combined entity vector is
given by:

$\begin{split}\mathbf{e}_{h+1}&=\mathbf{c}_{h}^{T}\left[\begin{array}[]{c}\mathbf{e}^{r}_{h+1}\\\
\mathbf{e}^{a}_{h+1}\end{array}\right]\\\
&=\mathbf{c}_{h}^{T}\left[\begin{array}[]{c}\texttt{Next}(\mathbf{e}_{h},\mathbf{r}_{h})\\\
\texttt{softmax}\left(\mathbf{a}(\mathbf{E}\odot\mathbf{e}_{h})\right)\end{array}\right]\,,\end{split}$
(6)

###  5.5 Response Decoder

After $H$ hops reasoning is done, the entities with top-$k$ values in the
entity vector $\mathbf{e}_{H}$ are selected, indicating that they have the
highest probability to be retrieved from the graph. These entities are
converted into their embeddings in $E$ and multiplied by their values in
$\mathbf{e}_{H}$. These entity embeddings are then concatenated with the
dialogue history $\mathbf{x}$. The concatenated vectors are fed as the input
into the transformer model to predict the response token by token. The
predicted probability distribution over the output space can be written as
$P(\cdot|\mathbf{x},\mathbf{M}_{h},\mathbf{M}_{r},\mathbf{M}_{t})$. Since all
components are differentiable, all modules can be trained end-to-end with the
dialogue history $\mathbf{x}$ and the reified KG representation
$\\{\mathbf{M}_{h},\mathbf{M}_{r},\mathbf{M}_{t}\\}$ using the cross-entropy
loss with the ground-truth output $y$ as the labels.

$L=\sum_{(\mathbf{x},y)}-\log
P(y|\mathbf{x},\mathbf{M}_{h},\mathbf{M}_{r},\mathbf{M}_{t})\,.$ (7)

During the inference time, the reasoning modules (relation layer, operation
layer, and checkpoints layer) work exactly the same as the training stage, the
only difference is that the response decoder is fed with predicted tokens in
previous time steps (inference stage) instead of the ground-truth output
(training stage).

##  6 Experiments

###  6.1 Datasets

We evaluate our proposed approach on three datasets. Among them, we use
Stanford Multi-domain Dialogues (SMD) Eric et al. (2017) and OpenDialKG Moon
et al. (2019) to test the methods generalizability on different dialogue types
(task-oriented / chit-chat) and scales of structured knowledge (pairwise
database / universal KG). To further analyze the reasoning ability, we propose
a new dataset, SMD-Reasoning, by modifying the output of SMD dataset from
natural language responses to actions paired with their reasoning types.

#### Stanford Multi-domain Dialogues (SMD)

The SMD dataset Eric et al. (2017) is composed of two-speaker conversations,
where a driver talks with the car assistant to tackle tasks in three domains:
scheduling, navigation, and weather forecasting. Each dialogue focuses on one
domain and is paired with a database having the related information. We
convert the original database into two formats: (1) the natural language
descriptions (NLD) and (2) the KG. The NLD form allows us to investigate the
ability of the model to interpret unstructured knowledge, while the KG form
could be a more extensible structured knowledge compared to tables.

#### OpenDialKG

OpenDialKG dataset Moon et al. (2019) is composed of two-speakers
recommendation and chit-chat style conversations. Each turn in a dialogue is
annotated with the reasoning path on the provided KG, which is filtered from
Freebase Bollacker et al. (2008). The resulting KG has 1,190,658 triples,
100,813 entities and 1,358 relations. We randomly split 70/15/15% for
train/valid/test sets as described in Moon et al. (2019); Jung et al. (2020)
since they do not release their splits.

#### SMD-Reasoning

To make SMD dataset suitable for more precise evaluation of reasoning
abilities, we manually label and convert it to the SMD-Reasoning dataset. We
first remove the natural language part from the original responses and only
leave the action word (e.g., inform) along with the information being
conveyed. We divide the dataset into three main reasoning types: informing
items, selecting min/max, and evaluating true/false. To validate if the models
can identify whether the needed knowledge is in the database, we add a new
reasoning type for extracting constraints, by removing the needed knowledge
from the database and changing the output to “include [knowledge description]”
as shown in Table 1. See Appendix A,B for statistics of these datasets.

###  6.2 Evaluation Metrics

We use different evaluation methods for the three datasets. For SMD, we follow
prior work Yang et al. (2020) and use BLEU Papineni et al. (2002), and Entity
F1 scores on each domain. For OpenDialKG, we follow the descriptions in prior
works Moon et al. (2019); Jung et al. (2020) to evaluate the path@k scores,
i.e., if the ground-truth path is ranked top-k in the predicted paths
probabilities. Moreover, since our method not only can predict the reasoning
path as prior works but also can predict the response, we also use the BLEU
score to get the approximated evaluation of the response quality compared to
ground-truth. Note that prior work has discussed that BLEU scores may not
match human intuition Liu et al. (2016), but we use them here as an
approximated evaluation for reference.

For SMD-Reasoning, the output is more deterministic and does not include
diverse sentence structures. Therefore, we compute the F1 score and the exact
match (EM) score of prediction and the ground-truth. The EM score is
calculated by removing the order of the prediction since the labels of SMD-
Reasoning dataset follow the order of knowledge description appearing in the
original ground-truth responses and may not have the same order as generated
outputs. The EM score can be written as:

$\texttt{EM}=\frac{1}{T}\sum\mathbbm{1}(\texttt{sort}(\hat{y})=\texttt{sort}(y))\,.$
(8)

where $\hat{y}$ is inferred from the model using argmax sampling and $T$ is
total number of examples.

###  6.3 Implementation Details

Since the proposed method is model-agnostic, we implement it on GPT2 Radford
et al. (2019) and T5 Raffel et al. (2020). Specifically for the T5 model, we
use the unifiedQA-T5 model Khashabi et al. (2020) which is pretrained on
question answering tasks that also need to do reasoning. However, we
empirically find that T5 generally has better performance than GPT2, thus
using T5 model in most experiments. For OpenDialKG, since the ground-truth
relations exist, we take them as an additional supervision signal as Moon et
al. (2019). Also, since we observe that there is only KG reasoning type in
OpenDialKG, we do not use operation layer and checkpoints layer for the
dataset. The hyperparameter settings are in Appendix C.

###  6.4 Baselines

We compare our proposed DiffKG model with the state-of-the-art models on
OpenDialKG reported in Moon et al. (2019); Jung et al. (2020) and the state-
of-the-art graph-based model on SMD Yang et al. (2020); Gou et al. (2021) with
their reported baselines including sequence-to-sequence models with and
without attention (S2S and S2S+Attn) Luong et al. (2015), pointer to unknown
(Ptr-Unk) Gulcehre et al. (2016), GraphLSTM Peng et al. (2017), BERT Devlin et
al. (2019), Mem2Seq Madotto et al. (2018) and GLMP Wu et al. (2019). We follow
their metrics and train our model on their preprocessed data for fair
comparisons. To further analyze the reasoning ability, we propose two more
baselines based on different ways of leveraging pretrained language models.
(1) NoInfo model does not take any format of knowledge as the input, aiming to
test the performance of a fine-tuned vanilla transformer model on each
dataset. (2) FlatInfo model constructs the input by concatenating the dialogue
history with the NLD form of knowledge as Beygi et al. (2022), allowing us to
investigate the ability of the model to interpret unstructured knowledge.

Model | BLEU | Entity F1
---|---|---
All | Sche. | Wea. | Nav.
S2S | 8.4 | 10.3 | 9.7 | 14.1 | 7.0
S2S+Attn | 9.3 | 19.9 | 23.4 | 25.6 | 10.8
Ptr-Unk | 8.3 | 22.7 | 26.9 | 26.7 | 14.9
GraphLSTM | 10.3 | 50.8 | 69.9 | 46.6 | 43.2
BERT | 9.13 | 49.6 | 57.4 | 47.5 | 46.8
Mem2Seq | 12.6 | 33.4 | 49.3 | 32.8 | 20.0
GLMP | 12.2 | 55.1 | 67.3 | 54.1 | 48.4
GraphDialog | 13.7 | 57.4 | 71.9 | 59.7 | 48.6
COMET-graph | 14.4 | 56.7 | 71.6 | 48.7 | 50.4
T5-DiffKG | 16.04 | 56.2 | 67.2 | 61.5 | 46.7
Table 2: The results on SMD dataset. S2S, S2S+Attn, Ptr-Unk, GraphLSTM, BERT, Mem2Seq, GLMP, GraphDialog are reported from Yang et al. (2020) and COMET-graph from Gou et al. (2021). Our DiffKG achieves the highest BLEU and comparable F1 scores with baselines. Model | path@1 | path@5 | path@10 | BLEU
---|---|---|---|---
Seq2Seq | 3.1 | 29.7 | 44.1 | -
Tri-LSTM | 3.2 | 22.6 | 36.3 | -
EXT-ED | 1.9 | 9.0 | 13.3 | -
DialKG | 13.2 | 35.3 | 47.9 | -
Seq2Path | 14.92 | 31.1 | 38.68 | -
AttnFlow | 17.37 | 30.68 | 39.48 | -
AttnIO-AS | 23.72 | 43.57 | 52.17 | -
T5-NoInfo | - | - | - | 14.51
T5-DiffKG | 26.80 | 54.33 | 61.75 | 15.37
Table 3: The results on OpenDialKG dataset. The four baselines from Seq2Seq to
DialKG Walker are reported from Moon et al. (2019) and the other three
baselines from Seq2Path to AttnIO-AS are reported from Jung et al. (2020). Our
DiffKG achieves the highest path@k scores and is the only one that can
simultaneously generate responses.

###  6.5 Results

The results on SMD and OpenDialKG are shown in Table 2 and Table 3. On SMD
dataset, we observe that DiffKG outperforms the baselines on BLEU by 11.4%
(relative change of 16.04 and 14.4) and achieves comparable entity F1 scores
with GLMP, GraphDialog and COMET-graph. DiffKG might not improve the entity F1
scores because that prior works group the text inside an entity together
(e.g., “road block nearby” becomes a single word “road_block_nearby” in
vocabularies). In contrast, we use a universal tokenizer so as to prevent
heavy preprocessing and specialized vocabularies. This means that DiffKG can
perform similarly with state-of-the-art to retrieve knowledge without a
tokenizer specified for each dataset. On OpenDialKG dataset, we observe that
DiffKG outperforms the baselines in terms of path@k scores and can
simultaneously outperform T5 in terms of Entity F1 and BLEU. These demonstrate
that DiffKG can retrieve accurate paths for reasoning and effectively
incorporate reasoning into response generation.

Test KG | Method | EM | F1
---|---|---|---
Fixed | GPT2-NoInfo | 10.71 | 43.78
GPT2-FlatInfo | 14.08 | 47.57
GPT2-DiffKG | 16.39 | 51.06
T5-NoInfo | 10.50 | 44.27
T5-FlatInfo | 28.99 | 66.15
T5-DiffKG | 27.52 | 63.93
Shuffled | T5-FlatInfo | 17.02 | 54.51
T5-DiffKG | 27.52 | 64.00
Table 4: The results on SMD-Reasoning dataset.

We also investigate the results of SMD-Reasoning dataset as shown in Table 4.
We find that DiffKG improves NoInfo by 16.6% and 44.4% F1 scores respectively
on GPT2 and T5 models. This demonstrates that DiffKG can utilize knowledge
effectively to improve the generation without access to information. In
contrast, although FlatInfo gives similar performances as DiffKG on the SMD-
Reasoning dataset, it cannot be run on OpenDialKG due to computational costs.
More specifically, FlatInfo requires the knowledge graph to be transformed
into sentences, which will result in at least a million tokens as the model
inputs for OpenDialKG (since the number of triples is a million without
designed subgraph sampling), which is not a practical number.

Method | Domains | Reasoning Types
---|---|---
5pt. | Schedule | Navigation | Weather | Inform | Selection | Extraction | True/False
| EM | F1 | EM | F1 | EM | F1 | EM | F1 | EM | F1 | EM | F1 | EM | F1
GPT2-NoInfo | 3.49 | 45.7 | 4.63 | 41.6 | 27.5 | 46.8 | 5.03 | 45.2 | 1.45 | 47.4 | 3.06 | 24.0 | 68.6 | 68.6
GPT2-DiffKG | 9.30 | 53.0 | 9.65 | 47.6 | 34.4 | 56.5 | 8.04 | 50.8 | 0.00 | 48.5 | 31.6 | 53.5 | 56.9 | 56.9
T5-NoInfo | 0.00 | 44.6 | 4.63 | 40.9 | 29.0 | 50.7 | 3.02 | 44.9 | 8.70 | 49.1 | 1.02 | 25.2 | 70.6 | 70.6
T5-DiffKG | 20.9 | 63.8 | 19.3 | 61.9 | 48.1 | 68.1 | 18.1 | 61.7 | 11.6 | 62.4 | 50.0 | 73.5 | 70.6 | 70.6
Table 5: Detailed Evaluation Results of SMD-Reasoning dataset SMD-Reasoning | User: check the date and time of my doctor’s appointment
---|---
(Reasoning Path: Doctor Appointment $\xrightarrow[]{\text{HasDate, HasTime,
ToSelf}}$ Tuesday, 11am, doctor appointment)
DiffKG: inform 11 am tuesday doctor appointment
User: Car I need to get to a gas station, please show me the nearest one
Assistant: There is Valero 7 miles away with moderate traffic on our way
User: Alright, where is it located?
(Reasoning Path: Gas Station $\xrightarrow[]{\text{IsTypeOf}}$ Valero
$\xrightarrow[]{\text{ HasAddress, ToSelf}}$ 200 Alester Ave, Valero)
DiffKG: inform 200 Alester Ave Valero
OpenDialKG | Speaker A: Do you have any info on Toni Kroos?
(Reasoning Path: Toni Kroos $\xrightarrow[]{\text{$\sim$Player Statistics}}$
Germany national football team)
DiffKG: Toni Kroos is German footballer who plays for the Germany national
football team.
Table 6: Generated examples and the reasoning path. Error Type |  Example
---|---
Unclear Information Requirement |  User: What gas stations are here?
Ground-truth: inform Chevron
DiffKG: inform 5 miles, Chevron
(Our comment: Although this prediction is considered wrong for the EM metric,
the “5 miles” of DiffKG output is the correct distance from “Chevron” and
might be needed in a good response.)
Incomplete Reasoning but Faithful Response |  User: Where is the closest grocery store?
Ground-truth: Inform 4 miles, Whole Foods, Safeway.
DiffKG: inform 4 miles, grocery store, 819 Alma St, Whole Foods
(Our comment: The 4 miles, grocery store, 819 Alma St are all correct entities
about Whole Foods. Nonetheless, this reasoning process neglects another
grocery store Safeway which is also 4 miles away.)
Correct Reasoning but Wrong Response |  Speaker A: Do you know Don Hall?
Ground-truth: Don Hall wrote the Princess and the Frog a romance story
starring Jenifer Lewis. Do you like Romance?
Reasoning Path: Don Hall $\xrightarrow[]{\text{$\sim$written by}}$ The
Princess and the Frog
DiffKG: Yes, he wrote The Little Dolls.
(Our comment: The reasoning path is correct to find out the script written by
Don Hall. However, the generation process fails to properly utilize the
retrieved entity.)
Table 7: The error analysis with three major error types across datasets.

###  6.6 Quantitative Analysis

To test the robustness of the methods towards accurately locating information,
we shuffle the information order. This evaluation is to simulate the cases
that extra information is arbitrarily added when deploying a dialogue system.
Specifically, the order of the knowledge context for FlatInfo and the order of
knowledge triples are changed during inference time. As shown in the last two
rows in Table 4, the performance of FlatInfo drops while DiffKG remains about
the same. This indicates that the slight superior performance of FlatInfo with
the original order can come from the blackbox tricks to group the nearby
knowledge in the inputs. When this implicit trick is broken down, the DiffKG
shows much better robustness and performance.

To investigate the difficulty of each domain and reasoning type, we divide the
results accordingly in Table 6.5. As presented in the domains part, the models
achieve the highest EM and F1 on the weather domain. We conjecture the reason
is that the weather domain includes more reasoning types (weather:4,
navigate:3, schedule:2 as in Appendix A Table 9), thus reflecting more
balanced reasoning ability. In the reasoning types part, we observe that
true/false is less well coped by DiffKG; however, DiffKG improves the
extraction. This shows that DiffKG can effectively check the existence of
required knowledge and then query the database.

Regarding to the computational costs (on SMD-Reasoning dataset using T5
model), we found that DiffKG requires about 5.85GB memory during training and
has 30ms inference latency. This could be an acceptable add-on memory usage
and inference time compared to a model without knowledge reasoning (3.13GB;
30ms). Especially when a baseline like FlatInfo consumes much more (18.56GB;
50ms).

###  6.7 Qualitative Analysis

We visualize the generated examples and the symbolic reasoning path by DiffKG
on SMD-Reasoning and OpenDialKG datasets in Table 6. The examples show that
DiffKG can capture some naturally occurring phenomena in this dataset: (1) the
KG reasoning path can be 1 to multiple hops; (2) the reasoning will diffuse to
multiple paths (e.g., DiffKG simultaneously applies
“HasDate”,“HasTime”,“ToSelf” to “Doctor Appointment”). Along with analyses in
previous subsections, we observe that DiffKG can extract interpretable
reasoning paths and generate corresponding outputs using reasonable
computational costs.

However, even though DiffKG can maintain or improve performance while doing
interpretable reasoning on any scaled KG, errors might happen in some cases.
As listed in Table 7, we found that across the datasets, the three main error
types of DiffKG are: (1) unclear information requirement in the dataset, (2)
incomplete reasoning ability but faithful response generation, and (3) correct
reasoning but hallucinated response prediction. We argue that the first error
type mainly comes from the mismatch among data points in the dataset and may
not be able to be dealt with by models. The second error type indicates that
the KG reasoning module sometimes cannot retrieve all the needed information.
The third error type indicates that the module producing final output may not
fully utilize the retrieved information. These three points might provide a
direction for further improvement.

##  7 Conclusion and Future Work

For a dialogue system, an effective reasoning method over structured databases
is important. In this work, we proposed DiffKG, an end-to-end model-agnostic
method that does symbolic reasoning on any scale of KGs to enhance response
generation. Experiments demonstrated that using DiffKG, models are able to
generate responses with interpretable KG reasoning paths at a modest extra
cost.

This work can be extended in various ways. While we solely consider efficient
large-scale KG reasoning in dialogue generation, future work can incorporate
domain fusion methods to consider the generalizability over domains or
simultaneously use relation information. Moreover, since DiffKG is a simple
large-scale structured knowledge-empowered transformer with flexible entity
values, future work can extend it to dialogue generation that needs to do
table and text mixed reasoning and that needs to do both KG reasoning and
other goals such as personalized dialogues, storytelling, etc.

## References

  * Beygi et al. (2022) Sajjad Beygi, Maryam Fazel-Zarandi, Alessandra Cervone, Prakash Krishnan, and Siddhartha Reddy Jonnalagadda. 2022.  Logical reasoning for task oriented dialogue systems.  _arXiv preprint arXiv:2202.04161_.
  * Bollacker et al. (2008) Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. 2008\.  Freebase: a collaboratively created graph database for structuring human knowledge.  In _Proceedings of the 2008 ACM SIGMOD international conference on Management of data_.
  * Cohen et al. (2019) William W Cohen, Haitian Sun, R Alex Hofer, and Matthew Siegler. 2019.  Scalable neural methods for reasoning with a symbolic knowledge base.  In _International Conference on Learning Representations_.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  Bert: Pre-training of deep bidirectional transformers for language understanding.  In _NAACL-HLT (1)_.
  * Dinan et al. (2018) Emily Dinan, Stephen Roller, Kurt Shuster, Angela Fan, Michael Auli, and Jason Weston. 2018.  Wizard of wikipedia: Knowledge-powered conversational agents.  In _International Conference on Learning Representations_.
  * Eisenschlos et al. (2021) Julian Martin Eisenschlos, Maharshi Gor, Thomas Müller, and William W Cohen. 2021.  Mate: Multi-view attention for table transformer efficiency.  _arXiv preprint arXiv:2109.04312_.
  * Eric et al. (2017) Mihail Eric, Lakshmi Krishnan, Francois Charette, and Christopher D Manning. 2017\.  Key-value retrieval networks for task-oriented dialogue.  In _Proceedings of the 18th Annual SIGdial Meeting on Discourse and Dialogue_.
  * Ghazvininejad et al. (2018) Marjan Ghazvininejad, Chris Brockett, Ming-Wei Chang, Bill Dolan, Jianfeng Gao, Wen-tau Yih, and Michel Galley. 2018.  A knowledge-grounded neural conversation model.  In _Thirty-Second AAAI Conference on Artificial Intelligence_.
  * Gou et al. (2021) Yanjie Gou, Yinjie Lei, Lingqiao Liu, Yong Dai, and Chunxu Shen. 2021.  Contextualize knowledge bases with transformer for end-to-end task-oriented dialogue systems.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, EMNLP 2021, Virtual Event / Punta Cana, Dominican Republic, 7-11 November, 2021_. Association for Computational Linguistics.
  * Gulcehre et al. (2016) Caglar Gulcehre, Sungjin Ahn, Ramesh Nallapati, Bowen Zhou, and Yoshua Bengio. 2016\.  Pointing the unknown words.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_.
  * Hao et al. (2017) Yanchao Hao, Yuanzhe Zhang, Kang Liu, Shizhu He, Zhanyi Liu, Hua Wu, and Jun Zhao. 2017.  An end-to-end model for question answering over knowledge base with cross-attention combining global knowledge.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , volume 1.
  * Hosseini-Asl et al. (2020) Ehsan Hosseini-Asl, Bryan McCann, Chien-Sheng Wu, Semih Yavuz, and Richard Socher. 2020.  A simple language model for task-oriented dialogue.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 20179–20191. Curran Associates, Inc.
  * Joshi et al. (2020) Rishabh Joshi, Vidhisha Balachandran, Shikhar Vashishth, Alan Black, and Yulia Tsvetkov. 2020.  Dialograph: Incorporating interpretable strategy-graph networks into negotiation dialogues.  In _International Conference on Learning Representations_.
  * Jung et al. (2020) Jaehun Jung, Bokyung Son, and Sungwon Lyu. 2020.  Attnio: Knowledge graph exploration with in-and-out attention flow for knowledge-grounded dialogue.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_.
  * Jurafsky and Martin (2009) Dan Jurafsky and James H. Martin. 2009.  _Speech and language processing: an introduction to natural language processing, computational linguistics, and speech recognition, 2nd Edition_.  Prentice Hall series in artificial intelligence. Prentice Hall, Pearson Education International.
  * Khashabi et al. (2020) Daniel Khashabi, Sewon Min, Tushar Khot, Ashish Sabharwal, Oyvind Tafjord, Peter Clark, and Hannaneh Hajishirzi. 2020.  Unifiedqa: Crossing format boundaries with a single qa system.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: Findings_.
  * Khot et al. (2020) Tushar Khot, Peter Clark, Michal Guerquin, Peter Jansen, and Ashish Sabharwal. 2020\.  Qasc: A dataset for question answering via sentence composition.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 8082–8090.
  * Kim et al. (2020) Seokhwan Kim, Mihail Eric, Karthik Gopalakrishnan, Behnam Hedayatnia, Yang Liu, and Dilek Hakkani-Tur. 2020.  Beyond domain apis: Task-oriented conversational modeling with unstructured knowledge access.  In _Proceedings of the 21th Annual Meeting of the Special Interest Group on Discourse and Dialogue_.
  * Lin et al. (2021) Bill Yuchen Lin, Haitian Sun, Bhuwan Dhingra, Manzil Zaheer, Xiang Ren, and William Cohen. 2021.  Differentiable open-ended commonsense reasoning.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_.
  * Liu et al. (2016) Chia-Wei Liu, Ryan Lowe, Iulian Serban, Mike Noseworthy, Laurent Charlin, and Joelle Pineau. 2016.  How not to evaluate your dialogue system: An empirical study of unsupervised evaluation metrics for dialogue response generation.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_.
  * Long et al. (2017) Yinong Long, Jianan Wang, Zhen Xu, Zongsheng Wang, Baoxun Wang, and Zhuoran Wang. 2017.  A knowledge enhanced generative conversational service agent.  In _Proceedings of the 6th Dialog System Technology Challenges (DSTC6) Workshop_.
  * Luong et al. (2015) Thang Luong, Hieu Pham, and Christopher D Manning. 2015.  Effective approaches to attention-based neural machine translation.  In _EMNLP_.
  * Madotto et al. (2018) Andrea Madotto, Chien-Sheng Wu, and Pascale Fung. 2018.  Mem2seq: Effectively incorporating knowledge bases into end-to-end task-oriented dialog systems.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_.
  * Mihaylov et al. (2018) Todor Mihaylov, Peter Clark, Tushar Khot, and Ashish Sabharwal. 2018.  Can a suit of armor conduct electricity? a new dataset for open book question answering.  _arXiv preprint arXiv:1809.02789_.
  * Moon et al. (2019) Seungwhan Moon, Pararth Shah, Anuj Kumar, and Rajen Subba. 2019.  Opendialkg: Explainable conversational reasoning with attention-based walks over knowledge graphs.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th annual meeting of the Association for Computational Linguistics_.
  * Peng et al. (2017) Nanyun Peng, Hoifung Poon, Chris Quirk, Kristina Toutanova, and Wen-tau Yih. 2017\.  Cross-sentence n-ary relation extraction with graph lstms.  _Transactions of the Association for Computational Linguistics_ , 5\.
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. 2019.  Language models are unsupervised multitask learners.  _OpenAI blog_ , 1(8):9.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. 2020.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _Journal of Machine Learning Research_ , 21(140):1–67.
  * Rajpurkar et al. (2018) Pranav Rajpurkar, Robin Jia, and Percy Liang. 2018.  Know what you don’t know: Unanswerable questions for squad.  _arXiv preprint arXiv:1806.03822_.
  * Reddy et al. (2019) Siva Reddy, Danqi Chen, and Christopher D Manning. 2019.  Coqa: A conversational question answering challenge.  _Transactions of the Association for Computational Linguistics_ , 7:249–266.
  * Serban et al. (2016) Iulian V Serban, Alessandro Sordoni, Yoshua Bengio, Aaron Courville, and Joelle Pineau. 2016.  Building End-to-End Dialogue Systems Using Generative Hierarchical Neural Network Models.  In _Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI-16)_.
  * Sordoni et al. (2015) Alessandro Sordoni, Michel Galley, Michael Auli, Chris Brockett, Yangfeng Ji, Margaret Mitchell, Jian-Yun Nie, Jianfeng Gao, and Bill Dolan. 2015.  A neural network approach to context-sensitive generation of conversational responses.  In _Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_.
  * Storks et al. (2019) Shane Storks, Qiaozi Gao, and Joyce Y Chai. 2019.  Recent advances in natural language inference: A survey of benchmarks, resources, and approaches.  _arXiv preprint arXiv:1904.01172_.
  * Tuan et al. (2019) Yi-Lin Tuan, Yun-Nung Chen, and Hung-Yi Lee. 2019.  Dykgchat: Benchmarking dialogue generation grounding on dynamic knowledge graphs.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_.
  * Tuan et al. (2020) Yi-Lin Tuan, Wei Wei, and William Yang Wang. 2020.  Knowledge injection into dialogue generation via language models.  _arXiv preprint arXiv:2004.14614_.
  * Veličković et al. (2018) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2018.  Graph attention networks.  _International Conference on Learning Representation_.
  * Verga et al. (2020) Pat Verga, Haitian Sun, Livio Baldini Soares, and William W Cohen. 2020.  Facts as experts: Adaptable and interpretable neural memory over symbolic knowledge.  _arXiv preprint arXiv:2007.00849_.
  * Wang et al. (2021) Qingyue Wang, Yanan Cao, Junyan Jiang, Yafang Wang, Lingling Tong, and Li Guo. 2021\.  Incorporating specific knowledge into end-to-end task-oriented dialogue systems.  In _2021 International Joint Conference on Neural Networks (IJCNN)_ , pages 1–8. IEEE.
  * Wen et al. (2017) Tsung-Hsien Wen, Milica Gasic, Nikola Mrksic, Lina M Rojas-Barahona, Pei-Hao Su, Stefan Ultes, David Vandyke, and Steve Young. 2017.  A network-based end-to-end trainable task-oriented dialogue system.  In _European Association for Computational Linguistics (EACL)_ , pages 438–449.
  * Weston et al. (2015) Jason Weston, Antoine Bordes, Sumit Chopra, Alexander M Rush, Bart van Merriënboer, Armand Joulin, and Tomas Mikolov. 2015.  Towards ai-complete question answering: A set of prerequisite toy tasks.  _arXiv preprint arXiv:1502.05698_.
  * Williams et al. (2016) Jason Williams, Antoine Raux, and Matthew Henderson. 2016.  The dialog state tracking challenge series: A review.  _Dialogue & Discourse_, 7(3):4–33.
  * Wu et al. (2019) Chien-Sheng Wu, Richard Socher, and Caiming Xiong. 2019.  Global-to-local memory pointer networks for task-oriented dialogue.  In _International Conference on Learning Representations_.
  * Yang et al. (2020) Shiquan Yang, Rui Zhang, and Sarah Erfani. 2020.  Graphdialog: Integrating graph knowledge into end-to-end task-oriented dialogue systems.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_.
  * Yin et al. (2016) Jun Yin, Xin Jiang, Zhengdong Lu, Lifeng Shang, Hang Li, and Xiaoming Li. 2016.  Neural generative question answering.  In _Proceedings of the Workshop on Human-Computer Question Answering_.
  * Zhao et al. (2019) Xueliang Zhao, Wei Wu, Chongyang Tao, Can Xu, Dongyan Zhao, and Rui Yan. 2019.  Low-resource knowledge-grounded dialogue generation.  In _International Conference on Learning Representations_.
  * Zhou et al. (2018) Hao Zhou, Tom Young, Minlie Huang, Haizhou Zhao, Jingfang Xu, and Xiaoyan Zhu. 2018\.  Commonsense knowledge aware conversation generation with graph attention.  In _IJCAI_.
  * Zhu et al. (2017) Wenya Zhu, Kaixiang Mo, Yu Zhang, Zhangbin Zhu, Xuezheng Peng, and Qiang Yang. 2017\.  Flexible end-to-end dialogue system for knowledge grounded conversation.  _arXiv preprint arXiv:1709.04264_.

##  Appendix A Dataset Details

The statistics of datasets are in Table 8 and Table 9. The OpenDialKG dataset
is under CC-BY-NC-4.0 license. These datasets can be used for research
purposes.

Data | Train | Validation | Test
---|---|---|---
SMD | 2425 | 302 | 304
OpenDialKG | 10971 | 2351 | 2351
Table 8: The number of dialogues in each data split. | Schedule | Navigation | Weather
---|---|---|---
Inform | 364 | 1133 | 236
Selection | - | 686 | 39
True/False | - | - | 543
Extraction | 173 | 474 | 214
Table 9: The statistics of SMD Reasoning dataset with respect to domains and
reasoning types. Note that since reasoning types are classified on turn-level,
the total number in this table is larger than in Table 8 that counted on
dialogue-level.

##  Appendix B SMD KG Construction

We write a simple, automatic program to construct KGs for SMD dataset mapped
from the original annotated tables.

For the schedule and navigation domains in SMD, we directly map their table
attributes to the relations $\mathcal{R}$ in our constructed KG. For the
weather domain, we split each weather report into low temperature, high
temperature, and weather. The resulting number of relations is 29, and the
relations are listed in Table 10.

Domain |  Relations
---|---
Schedule |  HasTime, HasDate, HasParty, HasRoom, HasAgenda, IsTimeOf, IsDateOf, IsPartyOf, IsRoomOf, IsAgendaOf
Navigation |  HasAddress, HasType, HasTraffic, HasDistance, IsAddressOf, IsTypeOf, IsTrafficOf, IsDistanceFrom
Weather |  IsEqualTo, HasLocation, HasWeather, HasLowTemp, HasHighTemp, HasDate, IsWeatherOf, IsLowTempOf, IsHighTempOf, IsLocationOf, IsDateOf
Table 10: The relations used in each domain in SMD dataset.

In the schedule and navigation domain, each item in the original database with
multiple attributes are transformed to KG triples as (event/point-of-interest,
attribute, attribute value), e.g., (tennis activity, HasTime, 7pm) in schedule
domain or (Chevron, HasType, gas station) in navigation domain.

In the weather domain, we add additional entities named “ReportID$digits$”,
where $digits$ will be replaced with an ID number. Each item in the original
database is in the format: (item, location, $location), (item, $date,
$weather_report), where the $weather_report contains multiple information not
simultaneously needed. To make the KG of weather consistent with the KGs of
schedule and navigation, we transform each item into (ReportID, location,
$location), (ReportID, HasDate, $date), (ReportID, HasWeather, $weather),
(ReportID, HasLowTemp, $low_temparature), (ReportID, HasHighTemp,
$high_temparature).

##  Appendix C Experiment Details

The hyperparameters we set for DiffKG are $d$=the hidden size of the used
pretrained trasnformer (T5-small: $d$=512; GPT2:$d$=768), $H$=5, max
norm=$1.0$, batch size=$16$, and gradient accumulation steps=$2$ for at most
$50$ epochs and train the model learning rate$\in\\{5\times 10^{-5},6.25\times
10^{-5}\\}$ (found that $6.25\times 10^{-5}$ is better) without learning rate
decay. Our experiments were single runs with random initialization and were
not further fine-tuned.

##  Appendix D Computational Cost Analysis

Figure 2: The comparison of the consumed training memory and inference
latency.

As plotted in Figure 2, on SMD-Reasoning dataset, the consumed memory of
FlatInfo is thrice the memory needed for DiffKG at training time, and its
latency is about twice at inference time. The difference in inference latency
is even larger with GPT2 as the backbone model. The reason is that the
computational cost of a causal language model such as GPT2 largely depends on
the input sequence length, which is one of the main issues of FlatInfo.