#  DeepCopy: Grounded Response Generation with
Hierarchical Pointer Networks

Semih Yavuz
University of California, Santa Barbara
<EMAIL_ADDRESS>
&Abhinav Rastogi
Google AI
<EMAIL_ADDRESS>
Guan-Lin Chao
Carnegie Mellon University
<EMAIL_ADDRESS>
&Dilek Hakkani-Tür
Amazon Alexa AI
<EMAIL_ADDRESS>
Work done while interning at Google AI.

###### Abstract

Recent advances in neural sequence-to-sequence models have led to promising
results for several language generation-based tasks, including dialogue
response generation, summarization, and machine translation. However, these
models are known to have several problems, especially in the context of chit-
chat based dialogue systems: they tend to generate short and dull responses
that are often too generic. Furthermore, these models do not ground
conversational responses on knowledge and facts, resulting in turns that are
not accurate, informative and engaging for the users. In this paper, we
propose and experiment with a series of response generation models that aim to
serve in the general scenario where in addition to the dialogue context,
relevant unstructured external knowledge in the form of text is also assumed
to be available for models to harness. Our proposed approach extends pointer-
generator networks See et al. (2017) by allowing the decoder to hierarchically
attend and copy from external knowledge in addition to the dialogue context.
We empirically show the effectiveness of the proposed model compared to
several baselines including Ghazvininejad et al. (2018); Zhang et al. (2018)
through both automatic evaluation metrics and human evaluation on ConvAi2
dataset.

##  1 Introduction

Recently, deep neural networks have achieved state-of-the-art results in
various tasks including computer vision, natural language and speech
processing. Specifically, neural sequence-to-sequence models (Sutskever et
al., 2014; Bahdanau et al., 2015) have led to great progress in important
downstream NLP tasks like text summarization (Rush et al., 2015; Nallapati et
al., 2016; See et al., 2017; Tan et al., 2017; Yavuz et al., 2018), machine
translation (Cho et al., 2014; Sutskever et al., 2014; Luong et al., 2015;
Bahdanau et al., 2015), and reading comprehension (Xiong et al., 2017).
However, achieving satisfactory performance on dialogue still remains an open
problem. This is because dialogues can have multiple valid responses with
varying semantic content. This is vastly different from the aforementioned
tasks, where the generation is more conveniently and uniquely constrained by
the input source.

Although neural models appear to generate meaningful responses when trained
with sufficiently large datasets in the chit-chat setting, such generic chit-
chat models reveal several weaknesses that were reported by previous research
Serban et al. (2016); Vinyals and Le (2015). Most common problems include
inconsistency in personality, dull and generic responses, and unawareness of
long-term dialogue context.

To alleviate these limitations, we turn our focus on a different problem
setting for dialogue response generation where the model is provided a set of
relevant textual facts (speaker persona descriptions) and is allowed to
harness this knowledge when generating responses in a multi-turn dialogue. To
handle the personality inconsistency issue, we ground our dialogue generation
model on external knowledge facts which are a list of persona descriptions in
our application (Li et al., 2016a; Zhang et al., 2018). We explicitly use the
dialogue history as memory for the model to condition on which potentially
encourages a more natural conversation flow. Towards encouraging generation of
more specific and appropriate responses while avoiding generic and dull ones,
we use a hierarchical pointer network in our model such that it can copy
content from two sources: current dialogue history and persona descriptions.

In this work, we propose a novel and general architecture DeepCopy that
extends the attentional sequence-to-sequence model with a hierarchical pointer
network that enables the decoder to jointly attend and copy tokens from any of
the facts available as external knowledge in addition to the dialogue context
(encoder input). This is achieved entirely in an end-to-end fashion through
factoring the whole copy mechanism into following three
hierarchies/components: (i) a token-level attention mechanism over the
dialogue context to determine the probability of copying a token from the
dialogue context, (ii) A hierarchical pointer network to determine the
probability of copying a token from each fact, and (iii) An inter-source meta
attention over the input sources dialogue context and external knowledge,
which combines the two copying probabilities. Using these components, a single
copying probability distribution over the unique tokens appearing in the model
input is computed exploiting the well-defined hierarchy among them. In
addition, the model is equipped with a soft switch mechanism between copying
and generation modes similar to See et al. (2017), which allows us to softly
combine the copying probabilities with the decoder’s generation probabilities
over a fixed vocabulary into a final output probability distribution over an
extended vocabulary. We empirically show the effectiveness of the proposed
DeepCopy model compared to several baselines including Ghazvininejad et al.
(2018); Zhang et al. (2018) on ConvAi2 challenge.

##  2 Related Work

Earlier work on data-driven, end-to-end approaches to conversational response
generation treated the task as statistical machine translation, where the goal
is to generate a response given the previous dialogue turn (Ritter et al.,
2011; Vinyals and Le, 2015). While these studies resulted in a paradigm change
compared to earlier work, they do not include mechanisms to represent
conversation context. To tackle this problem and have a better representation
of conversation context as input to generation, (Serban et al., 2016) proposed
hierarchical recurrent encoder-decoder (HRED) networks. HRED combines two
RNNs, one at the token level, modeling individual turns, and one at the
dialogue level, inputting turn representations from the token-level RNNs.
However, utterances generated by such neural response generation systems are
often generic and contentless (Vinyals and Le, 2015). To improve the diversity
and content of generated responses, HRED was later extended with a latent
variable that aims to model the higher level aspects (such as topic) of the
generated responses, resulting in the VHRED approach (Serban et al., 2017).

Another challenge for dialogue response generation is the integration of
knowledge into the generated responses. (Liu et al., 2018) extracted facts
relevant to a dialogue from knowledge using string matching, named entity
recognition and linking, found additional entities from knowledge that are
most relevant to the facts by a neural similarity scorer, and used these as
input context features for the dialogue generation RNN. (Ghazvininejad et al.,
2018) used end-to-end memory networks to base the generated responses on
knowledge, where an attention over the knowledge relevant to the conversation
context is estimated, and multiple knowledge representations are included as
input during the decoding of responses. In this work, we use end-to-end memory
networks as a baseline.

Although much research has focused on response generation in a chit-chat
setting, models trained on large datasets of human-human interactions of
diverse speaker characteristics often tend to generate responses which are too
vague and generic (common for most speakers) or inconsistent in personality
(switching between different speakers’ characteristics). Recently, (Zhang et
al., 2018) presented the ConvAi2 challenge containing persona descriptions and
over 10K real human chit-chats where speakers were required to converse based
on their assigned persona. Li et al. (2016a) learned speaker persona
embeddings from a single-speaker setting (e.g. Twitter posts) or a speaker-
address style (human-human conversations) to generate personalized responses
given a single utterance input. Another related work Raghu et al. (2018)
applies hierarchical memory network for task oriented dialog problem. In this
work, we compare our model with (Zhang et al., 2018) which uses a memory-
augmented sequence-to-sequence response generator grounded on the dialogue
history and persona.

##  3 Model

In this section, we first set up the problem, and then briefly revisit the
baseline models using memory networks Sukhbaatar et al. (2014) and pointer-
generator networks (See et al., 2017). Subsequently, we introduce the proposed
DeepCopy model with a hierarchical pointer network and our training process.

###  3.1 Problem Setup

Let $\mathbf{x}=(x_{1},x_{2},\ldots,x_{n})$ denote the tokens in the dialogue
history. The dialogue is accompanied by a set of $K$ relevant supporting
facts, where
$\mathbf{f}^{(i)}=(f^{(i)}_{1},f^{(i)}_{2},\ldots,f^{(i)}_{n_{i}})$ is the
list of tokens in the $i$-th fact. Our goal is to generate the response as a
sequence of tokens $\mathbf{y}=(y_{1},y_{2},\ldots,y_{m})$ using the dialogue
history and supporting facts. Note here that we are not interested in
retrieval/ranking based models Weston et al. (2018) which rely on a set of
candidate responses. Generative models are essential for this problem because
we want to incorporate content from new facts during inference which may not
be present in the training set. Hence, using a predefined set of candidates
may not ensure high coverage.

###  3.2 Baseline Models

In this section, we describe several baseline response generation models
including the ones from existing work Ghazvininejad et al. (2018); Zhang et
al. (2018) and the in-house ones we propose as additional baselines.

####  3.2.1 Seq2Seq

In a sequence-to-sequence model with attention Bahdanau et al. (2015), a
sequence of input tokens is encoded using an LSTM encoder. At decoder step
$t$, the decoder state $h_{t}$, a context vector $c_{t}$ and the previous
decoder output $y_{t-1}$ are used together to output a distribution over a
fixed vocabulary of tokens obtained from the training set using a non-linear
function. The context vector $c_{t}$ is an attention-weighted combination of
the encoder outputs. In the following baseline models, we use different
features as inputs to the encoder. The underlying model remains the same.

Seq2Seq + NoFact. Only the dialogue context tokens $\mathbf{x}$ are used as
input to the encoder.
Seq2Seq + BestFactContext. We select the fact $\mathbf{f}^{(c)}$ whose tokens
have highest unigram tf-idf similarity to the dialogue context tokens.
$[\mathbf{x}||\mathbf{f}^{(c)}]$ is then used as input to the encoder, where
$||$ denotes concatenation.
Seq2Seq + BestFactResponse. We select the fact $\mathbf{f}^{(r)}$ whose tokens
have highest unigram tf-idf similarity to the ground truth response.
$[\mathbf{x}||\mathbf{f}^{(r)}]$ is used as input to the encoder. The aim of
this experiment is to have a better understanding of the effect of fact
selection on response generation, since using the ground truth for fact
selection is not fair.

####  3.2.2 Memory Network

Our variations of Seq2Seq models described in Section 3.2.1 incorporate facts
by concatenating them to the dialogue context. Memory networks Ghazvininejad
et al. (2018); Zhang et al. (2018) are a more principled approach to
incorporating external facts. Similar to Ghazvininejad et al. (2018), we use a
context encoder to embed the context tokens $\mathbf{x}$ and obtain a list of
outputs and final hidden state $u\in\mathbb{R}^{d}$. As outlined in
Ghazvininejad et al. (2018), a fact $\mathbf{f}^{(i)}$ is embedded into key
and value vectors $k_{i}$ and $m_{i}$, respectively. A summary
$o\in\mathbb{R}^{d}$ of facts is then computed as an attention weighted
combination of $(m_{1},m_{2},\ldots,m_{K})$ by conditioning on $u$ and
$(k_{1},k_{2},\ldots,k_{K})$. We then combine the two summaries into
$\hat{u}=u+o$, and use it to initialize the decoder state. We report results
on the following variants:

Figure 1: Overview of our proposed approach as described in Section 3.3. The
decoder state $d_{t}$ is used to attend over dialogue context and knowledge
source to generate distributions for copying tokens from these sources. The
decoder outputs a distribution over a fixed vocabulary. The three
distributions are combined to yield the final distribution over tokens at each
step $t$.

MemNet. This is equivalent to the model used in Ghazvininejad et al. (2018),
described above. This is essentially a sequence to sequence model without
attention at every decoder step, except using the combined summary $\hat{u}$
to initialize the decoder.
MemNet+ContextAttention. At each decoder step, the decoder state attends over
the encoder outputs and obtains a context vector $c_{t}^{(c)}$. This is
equivalent to Seq2Seq + NoFact model from Section 3.2.1, except using the fact
summary $\hat{u}$ to initialize the decoder state.
MemNet+FactAttention. At each decoder step, we use the decoder state to attend
over the value embeddings $(m_{1},m_{2},\ldots,m_{K})$ corresponding to facts,
and obtain a context vector $c_{t}^{(f)}$. This model is similar to the
generative profile memory network Zhang et al. (2018), where we apply
attention only on facts, and we set the decoder’s initial state to the
combined summary $\hat{u}$.
MemNet+FullAttention. This model employs attention over both facts and
dialogue context at each decoder step. The two attention modules are combined
by concatenating $c_{t}^{(c)}$ and $c_{t}^{(f)}$ Zoph and Knight (2016).

####  3.2.3 Seq2Seq with Copy Mechanism

Seq2seq models can only generate tokens present in a fixed vocabulary obtained
from the training set. Pointer-generator network See et al. (2017) extends the
attentional sequence-to-sequence model Bahdanau et al. (2015) by employing a
pointer network Vinyals et al. (2015). It has two decoding modes, copying and
generating, which are combined via a soft switch mechanism, allowing it to
copy tokens from source in addition to generating from vocabulary. We report
the results for the following additional baselines obtained by equipping the
corresponding Seq2Seq model in Section 3.2.1 with copy mechanism: Seq2Seq +
NoFact + Copy, Seq2Seq + BestFactContext + Copy, Seq2Seq + BestFactResponse +
Copy.

Figure 2: Illustration of hierarchical pointer network. The decoder state
$d_{t}$ is used to attend over tokens for each fact and also over the fact-
level context vectors obtained by weighted average of token-level
representations (w.r.t token-level attention weights) for each fact. The
token-level attention weights are then combined with the attention
distribution over facts (Equation 11) to generate the probability of copying
each token in all the facts.

###  3.3 DeepCopy with Hierarchical Pointer Networks

Pointer-generator network See et al. (2017) can only copy tokens from the
encoder input. In this section, we present our proposed DeepCopy model that
extends pointer-generator network See et al. (2017) using a novel hierarchical
pointer network. Our model allows copying tokens from multiple input sources
(facts $\mathbf{f}^{(i)},1\leq i\leq K$), besides the encoder input (dialogue
context $x$).

A high-level overview of the proposed approach is illustrated in Figure 1. At
decoder step $t$, the decoder state $h_{t}$ is used to attend over the
dialogue context tokens and fact tokens to give a distribution over the tokens
present in context and facts respectively. These distributions are then
combined with the distribution output by the decoder over the fixed vocabulary
to obtain the overall distribution.
Encoding a sequence.  Let $\mathbf{w}=(w_{1},w_{2},\ldots w_{n})$ be a
sequence of tokens. We first obtain a trainable embedded representation of
each token in the sequence and then use a LSTM cell to encode the sequence of
embedding vectors. We define $e,\mathbf{s}=\texttt{Encode}(\mathbf{w})$, where
$e$ denotes the final state of the LSTM and $\mathbf{s}=(s_{1},s_{2},\ldots
s_{n})$ denotes the outputs of the LSTM cell at all steps.
Attention.  Let $\mathbf{u}=(u_{1},u_{2},\ldots u_{n})$ be a sequence of
vectors where $u_{i}\in\mathbb{R}^{p},1\leq i\leq n$ and $v\in\mathbb{R}^{q}$
be a conditioning vector. The attention module generates a linear combination
$c$ of elements in $\mathbf{u}$ by conditioning them on $v$ as defined by the
equations below. We define $\alpha,c=\texttt{Attention}(\mathbf{u},v)$, where
$\alpha_{i}\in\mathbb{R}^{n}$ is the weight assigned to $u_{i}$, and
$c\in\mathbb{R}^{p}$ is a vector representation of the sequence $\mathbf{u}$
conditioned on $v$. In the equations below, $w_{1}$ and $W_{2}$ are parameters
of appropriate dimension. In our setup, we use $p=q,w_{1}\in\mathbb{R}^{p}$,
and $W_{2}\in\mathbb{R}^{p\times 2p}$.

$\displaystyle e_{i}$ $\displaystyle=w_{1}^{T}\tanh(W_{2}[u_{i};v])$ (1)
$\displaystyle\alpha_{i}$
$\displaystyle=\dfrac{\exp(e_{i})}{\sum_{j=1}^{n}\exp(e_{j})}$ (2)
$\displaystyle c$ $\displaystyle=\sum_{i=1}^{n}\alpha_{i}u_{i}$ (3)

Copying from Dialogue Context.  Similar to our baseline models, we encode the
dialogue context tokens $\mathbf{x}$ (Equation 4) and apply attention to the
encoder outputs at a decoder step $t$ (Equation 5). This outputs attention
weights $\alpha^{(x)}_{t}$ and a representation of the entire context
$c^{(x)}_{t}$. The attention weights are aggregated to obtain the distribution
over context tokens $p_{t}^{(x)}(w)$ (Equation 6),

$\displaystyle e^{(x)},\mathbf{s}^{(x)}$
$\displaystyle=\texttt{Encode}(\mathbf{x})$ (4)
$\displaystyle\alpha^{(x)}_{t},c^{(x)}_{t}$
$\displaystyle=\texttt{Attention}(\mathbf{s}^{(x)},h_{t})$ (5) $\displaystyle
p_{t}^{(x)}(w)$ $\displaystyle=\sum_{\\{i:x_{i}=w\\}}\alpha^{(x)}_{t,i}$ (6)

Copying from Facts: Hierarchical Pointer Network.  We introduce the
hierarchical pointer network (Figure 2) as a general methodology for enabling
token-level copy mechanism from multiple input sequences or facts. Each fact
$\mathbf{f}^{(i)}$ is encoded (Equation 7) to obtain token level
representations $\mathbf{s}^{(f)(i)}$ and overall representation $e^{(f)(i)}$.
The decoder state $h_{t}$ is used to attend over token level representations
(Equation 8) and the overall fact-level representations of each fact (Equation
9) by

$\displaystyle e^{(f)(i)},\mathbf{s}^{(f)(i)}$
$\displaystyle=\texttt{Encode}(\mathbf{f}^{(i)})$ (7)
$\displaystyle\alpha_{t}^{(f)(i)},c_{t}^{(f)(i)}$
$\displaystyle=\texttt{Attention}(\mathbf{s}^{(f)(i)},h_{t})$ (8)
$\displaystyle\beta_{t},c^{(f)}_{t}$
$\displaystyle=\texttt{Attention}(\\{c^{(f)(i)}_{t}\\}_{i=1}^{K},h_{t})$ (9)

to compute the probability of copying a word $w$ from facts as

$\displaystyle p^{(f)}_{t}(w)$ $\displaystyle=\sum_{j=1}^{K}\
p^{(f)}_{t}(\mathbf{f}^{(j)})\cdot p^{(f)}_{t}(w|\mathbf{f}^{(j)})$
$\displaystyle=\sum_{j=1}^{K}\
\beta_{t,j}\sum_{\\{l:f^{(j)}_{l}=w\\}}\alpha^{(f)(j)}_{t,l}$ (10)

Inter-Source Attention Fusion  We now present the mechanism to fuse the two
distributions $p_{t}^{(x)}(w)$ and $p_{t}^{(f)}(w)$ representing the
probabilities of copying tokens from dialogue context and facts respectively.
We use the decoder state $h_{t}$ to attend over dialogue context
representation $c^{(x)}_{t}$ and overall fact representation $c^{(f)}_{t}$
(Equation 11). The resulting attention weight
$\gamma_{t}^{\prime}=[\gamma_{t},1-\gamma_{t}]$ is used to combine the two
copying distributions as shown in Equation 12.

$\displaystyle\gamma_{t},c_{t}$
$\displaystyle=\texttt{Attention}([c^{(x)}_{t},c^{(f)}_{t}],h_{t})$ (11)
$\displaystyle p^{\text{copy}}_{t}(w)$ $\displaystyle=\gamma_{t}\
p^{(x)}_{t}(w)+(1-\gamma_{t})\ p^{(f)}_{t}(w)$ (12)

Similar to Seq2Seq models, the decoder also outputs a distribution
$p^{\text{vocab}}_{t}$ over the fixed training vocabulary at each decoder step
using the overall context vector $c_{t}$ and decoder state $h_{t}$. Having
defined the copy probabilities $p^{\text{copy}}_{t}$ for tokens that appear in
the model input, either the dialogue context or the facts in external
knowledge source, we combine $p^{\text{vocab}}_{t}$ and $p^{\text{copy}}_{t}$
using the mechanism outlined in See et al. (2017), except we use $c_{t}$
defined in Equation 11 as the context vector instead.

To better isolate the effect of copying, a key component of the proposed
DeepCopy model, we also conduct experiments with MultiSeq2Seq model that
incorporates the knowledge facts in the same way (by encoding each fact
separately with LSTM, and attending on each by the decoder as in Zoph and
Knight (2016)), but relies completely on generation probabilities without a
copy mechanism.

###  3.4 Training

We train all the models described in this section using the same loss function
optimization. More precisely, given a model $M$ that produces a probability
$p_{t}(w|y_{<t})$ of generating token $w$ at decoding step $t$, we train the
whole network end-to-end with the negative log-likelihood loss function of

$\displaystyle
J_{\text{loss}}(\mathbf{\Theta})=-\dfrac{1}{|\mathbf{y}|}\sum_{t=1}^{|\mathbf{y}|}\log(p_{t}(y_{t}|y_{<t},\mathbf{x},\\{\mathbf{f}^{(i)}\\}_{i=1}^{K}))$

for a training sample
$(\mathbf{x},\mathbf{y},\\{\mathbf{f}^{(i)}\\}_{i=1}^{K})$ where
$\mathbf{\Theta}$ denotes all the learnable model parameters.

##  4 Experiments

In this section, we describe the details of dataset, training process,
evaluation metrics, and the performance results of DeepCopy model in
comparison to proposed and existing baselines.

###  4.1 Dataset

We perform experiments for our problem setup on the recently released ConvAi2
conversational AI challenge dataset, which is an extended version of
PersonaChat Zhang et al. (2018). The conversations in ConvAi2 are obtained by
asking a pair of crowdworkers to chat with each other naturally based on their
randomly assigned personas (from a set of 1155 personas) towards getting to
know each other. Personas are created by a different set of crowdworkers, and
they consist of ~5 natural language sentences, each describing an aspect of a
person that can range from common hobbies like "I like to play basketball" to
very specific facts like "I have a pet parrot named Tasha", reflecting a wide
range of different personalities. The dataset contains ~11000 dialogues with
~160000 utterances, and 2000 dialogues with non-overlapping personas are used
for validation and test. For our setting, we use personas as external
knowledge sources that models can ground on while generating responses.

###  4.2 Training and Implementation Details

In all the models explored in this paper, we set the dialogue context to
concatenation of the last two dialogue turns separated by a special CONCAT
token. The models are supplied with the persona facts of the side generating
the response at the current turn, while the persona of the other side is
concealed. We use a vocabulary of 18650 most frequent tokens and all the
remaining tokens are replaced with a special UNK token. Embeddings of size 100
are randomly initialized and updated during training. We set the size of LSTM
hidden layer to 100 for both encoder and decoder. The encoder and decoder
vocabularies and embeddings are shared. A shared LSTM encoder is used for
encoding both dialogue context and facts of external knowledge source. The
model parameters are optimized using Adam Kingma and Ba (2015) with a batch
size of 32, a fixed learning rate of 0.001. We apply gradient clipping to 5
when its norm exceeds this value. During inference, we generate responses by
employing a beam search of width 4. Our models are implemented in TensorFlow
Abadi et al. (2016).

###  4.3 Main Results

In this section, we present the experimental results in terms of both
automatic measures and human evaluation.

####  4.3.1 Automatic Evaluation

Model Perplexity BLEU ROUGE-L CIDEr Appropriateness [M-1] MemNet 61.30 3.07
59.10 10.52 3.14 (0.51) [M-2] MemNet + ContextAttention 57.37 3.24 59.20 11.79
3.41 (0.54) [M-3] MemNet + FactAttention 61.50 2.43 59.34 9.65 1.45 (0.25)
[M-4] MemNet + FullAttention 59.64 3.26 59.18 12.25 3.20 (0.49) [S2S-1]
Seq2Seq + NoFact 60.48 3.38 59.46 11.41 3.12 (0.52) [S2S-2] Seq2Seq +
BestFactContext 58.68 3.35 59.13 10.77 3.08 (0.45) [S2S-3] Seq2Seq +
BestFactResponse* 49.74 4.02 60.04 16.15 2.97 (0.51) [S2SC-1] Seq2Seq + NoFact
+ Copy 58.84 3.25 59.18 11.15 3.64 (0.54) [S2SC-2] Seq2Seq + BestFactContext +
Copy 60.25 3.17 59.46 11.17 3.60 (0.51) [S2SC-3] Seq2Seq + BestFactResponse +
Copy* 38.60 4.54 60.96 21.47 3.83 (0.46) [M-S2S] MultiSeq2Seq (no Copy) 57.94
2.88 59.10 10.92 3.32 (0.44) $\textbf{{DeepCopy}}^{\dagger}$ 54.58 ${\bf
4.09}$ 60.30 15.76 3.67 (0.59) G.Truth N/A N/A N/A N/A 4.40 (0.45)

Table 1: Main results on Convai2 dataset. Evaluation metrics on last three
columns are better the higher. Perplexity is lower the better. The results of
the proposed approach are presented in bold. * indicates that the
corresponding model should be considered as a kind of ORACLE because it has
access to the fact that is most relevant to the ground-truth response during
the inference/test time as defined in Section 3.2.1. $\dagger$ indicates that
the improvement of DeepCopy in automatic evaluation metrics over each of the
other models (except S2SC-3) is statistically significant with p-value of less
than 0.001 on the paired t-test.

In Table 1, we present our results in comparison with the existing and
proposed baseline models. We report the performance of each model across
several metrics commonly used for evaluation of text generation models
including perplexity, corpus BLEU Papineni et al. (2002), ROUGE-L Lin and Och
(2004), CIDEr Vedantam et al. (2014).

As expected, Seq2Seq + BestFactResponse model and its +COPY version outperform
all the other models across all the evaluation metrics. This model pinpoints
the importance of selecting the most suitable fact in the persona for the
response to be generated at each turn, justifying our underlying motivation
for conducting this experiment as highlighted in Section 3.2.1. However, the
most suitable fact for the response is not available in the real application
scenario, where the models are responsible for picking the useful pieces of
information pertaining to the current dialogue turn to generate meaningful
responses. Our proposed Seq2Seq + BestFactContext model and its +COPY version,
on the other hand, are valid baselines for this scenario where the best fact
is selected completely based on the dialogue context without relying on the
ground-truth response. This model outperforms the previously proposed memory
network based model MemNet Ghazvininejad et al. (2018) for knowledge grounded
response generation on all the evaluation metrics, demonstrating its
effectiveness despite the fact that it does not have access to all the facts
unlike Ghazvininejad et al. (2018). However, this approach has the following
potential weaknesses: (i) if the best persona fact selected w.r.t dialogue
context is wrong (irrelevant) for the ground-truth response, the generated
response might be drastically misinforming, and furthermore it is difficult
for model to recover from this error because it has no access to other facts,
(ii) selecting the best fact w.r.t dialogue context based on tf-idf similarity
may result in poor fact selection when the lexical overlap between context and
response is small which might be a common case especially for the ConvAi2
dataset as the focus of conversation may often change swiftly across the
dialogue turns. The latter might be the reason why copying does not help much
for this model since it might end up copying irrelevant tokens in the scenario
mentioned above.

Diversity Fact-Inclusion Agreement Model Distinct-2 / 3 / 4 F.Inc F.Per F.Hal
F.Inc / F.Per M-1 .004 / .006 / .010 0.41 0.01 0.40 0.99 / 0.99 M-2 .010 /
.019 / .031 0.43 0.01 0.42 0.97 / 0.99 M-3 .001 / .001 / .002 0.06 0.04 0.02
0.99 / 0.99 M-4 .054 / .010 / .156 0.51 0.09 0.42 0.98 / 0.98 S2S-1 .012 /
.022 / .036 N/A N/A N/A N/A / N/A S2S-2 .012 / .022 / .035 0.54 0.04 0.50 0.97
/ 0.99 S2S-3 .026 / .043 / .061 0.79 0.16 0.63 0.97 / 0.97 S2SC-1 .039 / .069
/ .104 N/A N/A N/A N/A / N/A S2SC-2 .035 / .067 / .109 0.73 0.36 0.37 0.99 /
0.99 S2SC-3* .058 / .111 / .178 0.73 0.55 0.18 0.98 / 0.96 M-S2S .035 / .065 /
.104 0.47 0.05 0.42 0.96 / 0.98 DeepCopy .059 / .121 / .201 0.62 0.23 0.39
0.95 / 0.97 G.Truth 0.35 / 0.66 / 0.84 0.76 0.49 0.27 0.93 / 0.96

Table 2: Lexical diversity and fact inclusion analysis results. Model names
are abbreviated according to Table 1. F.Inc denotes the ratio of responses
that include factual information. F.Per and F.Hal denote the ratio of
responses where the included fact is consistent with the persona or a
hallucinated one, respectively. Agreement column corresponds to Cohen’s
$\kappa$ statistic measuring inter-rater agreement on binary factual
evaluation metrics for F.Inc and F.Per. * indicates the ORACLE model.

Our proposed DeepCopy model is designed to effectively address the
aforementioned issues, where it has access to the entire set of persona facts
per dialogue from which it is expected to include the useful pieces of
information in the response. DeepCopy model outperforms all the models
reported in Table 1 except for Seq2Seq + BestContextResponse models, which we
already deem as kind of an upper bound because it has access to the most
relevant fact to the response. This justifies the effectiveness of DeepCopy
model compared to the existing works Ghazvininejad et al. (2018); Zhang et al.
(2018) and the additional baselines we explored in this work. On the other
hand, MultiSeq2Seq performs considerably worse than the DeepCopy model despite
the fact they both have access to the entire set of facts and employ the same
encoder-decoder architecture except for the copy mechanism. This further
justifies the effectiveness of incorporating the proposed hierarchical pointer
networks in DeepCopy because integrating the external knowledge simply by
employing multi-source attention as in Zoph and Knight (2016) does not yield
to a good solution with competitive results, performing even worse than
Seq2Seq + NOFACT on 3 of the metrics.

####  4.3.2 Human Evaluation

Although automatic metrics provide tangible information regarding the
performance of the models, we augment them with human evaluations for a more
comprehensive analysis of the resulting model generated responses. Towards
this end, we randomly sample 100 examples from test data and ask human raters
to evaluate the candidate model generated responses in terms of
appropriateness. Each example is rated by 3 raters, who are shown a dialog
history along with a set of persona facts (of the person in turn), and asked
to rate each response based on its appropriateness in the dialogue context
with a score from 1 (worst) to 5 (best).

In Table 1, we present the results of human evaluation under the
appropriateness column. Since each response is rated by $3$ different human
raters, we report the average rating along with the standard deviation in
parenthesis. We observe that DeepCopy outperforms both the existing memory-
network baselines and the proposed sequence-to-sequence baselines on the
appropriateness evaluation. It also achieves a performance that is close to
the oracle model (S2SC-3), which has a leverage of having an access to the
fact that is most relevant to the ground-truth response during the inference
time. Overall, human evaluation of the responses in terms of appropriateness
further justifies the promise and effectiveness of our proposed DeepCopy
model.

Appropriateness scores also demonstrate the advantage of incorporating the
soft copy mechanism. Comparing S2S (and M-S2S) models to their copy-equipped
counterparts (S2SC) (and DeepCopy) in Table 1 immediately reveals a
significant gain in appropriateness score. Another significant observation to
note here is that ground-truth responses obtain an average appropriateness
score of $4.4/5$, which reflects both the noise in ConvAI2 dataset and the
difficulty of generating the perfect response even for humans.

###  4.4 Further Analysis and Discussion

Lexical Diversity Analysis. In Table 2, we report the lexical diversity
results using the distinctness metric introduced in Li et al. (2016b).
distinct-$n$ score corresponds to the number of distinct $n$-grams divided by
total number of generated $n$-grams. We can clearly observe that DeepCopy
generates the most diverse responses among all the models including the copy-
augmented oracle model (S2SC-3). Hence, diversity results further show that
our proposed model is promising in addressing the most commonly observed
generic response problem more effectively than existing models by generating
more diverse responses.

Fact Inclusion Analysis. We also conduct an analysis on the kinds of factual
information included in the model-generated responses. More precisely, our
goal is to understand how often the generated response includes a factual
information (F.Inc), and whether this information is consistent with the
persona facts (F.Per) or a hallucinated one (F.Hal). A good model can
naturally include available facts from the persona and hallucinate others when
the conversation context requires them. Towards this end, we ask $3$ human
raters to label responses with 1 (or 0) based on whether a fact is included,
and if so, whether this fact is a persona-fact or not.

In Table 2, we present an analysis for the kinds of factual information
included in model generated responses. As can be seen from this analysis,
models that have a copy mechanism include more facts from the persona than the
ones that do not. Another important observation is that the ground-truth
responses include facts from persona only in 49% of the times, which indicates
that the provided persona facts remain insufficient to cover the complexity of
the high entropy open-ended person-to-person conversations.

In Table 2, we present Cohen’s $\kappa$ score for each model and fact analysis
metric pair using the scores from 3 raters for each example. We observe for
each model and metric pair a $\kappa$ statistic of greater than 0.9, which
indicates a near perfect agreement among raters. Note that the ratio of
hallucinated facts (F.Hal) is derived directly from human labels for fact
inclusion (F.Inc) and persona-fact (F.Per). That is why, there is no separate
labelling process for hallucinated facts (F.Hal). Hence, there is no $\kappa$
statistic for F.Hal in Table 2.

Error Analysis. A deeper analysis of the examples where DeepCopy is assigned a
worse appropriateness score than the best performing memory-network based
baselines (M-2 and M-4) reveals the following further insights: (i) Some of
these examples are corresponding to the cases where a generic response (e.g.,
"I’ve a dog named radar", one of the frequent generic responses, completely
independent of persona facts) is rated much higher (5 to 1) than factual but
slightly off (by a single word in this example) responses (e.g., "I have a dog
for a living." coming from the persona fact "I walk dogs for a living."), (ii)
In another subset of the analyzed examples, DeepCopy model generates a
response (e.g., "yes, but I want to become a lawyer.") by incorporating a fact
that has already been used in the previous turn of the dialog whereas M-2
produces a generic response (e.g., "that’s great. do you have any hobbies?",
again irrelevant to facts) which is rated higher. (iii) And most of the
remaining cases fall into the class of examples where incorporating knowledge
facts breaks the conversation flow, which is a crucial observation specific to
this dataset that can also be supported by the low persona-fact inclusion
ratio (49%) of ground-truth responses.

###  4.5 Qualitative Observations

Figure 3: Example dialogue where the previous two turns from Person1 and
Person2 along with the responses generated by the models acting as Person1 are
shown on the right. Persona facts for Person1 are provided on the left, among
which the one in bold is the best fact w.r.t response. MemNet*, Seq2Seq*,
Seq2Seq** are abbreviations for MemNet + FullAttention, Seq2Seq +
BestFactResponse, Seq2Seq + BestFactResponse +COPY models, respectively.

In Figure 3, we present an example dialogue where DeepCopy model generates a
meaningful and fluent response by effectively mixing copy and generate modes.
We can observe that it is able to attend on the right persona fact by taking
the dialogue context (especially the question at the end of Person2’s turn)
into consideration. Furthermore, attending to the tokens of this fact, it
produces a fluent and valid answer to yes/no question by generating "yes" and
copying the rest (and most) of the tokens from the fact. Although it copies
most of the tokens from the fact, it is good to observe that it copies exactly
the relevant pieces instead of just copying the entire fact. Seq2Seq +
BestFactResponse + Copy model’s response is also meaningful and fluent
although it may not be as engaging for the continuation of dialog. However,
the quality of the response by Seq2Seq + BestFactResponse quickly degrades
compared to its +Copy version. Although the response is still fluent and
relevant to the dialogue context, it becomes rather irrelevant to the persona
as the model seems to have difficulty of picking the useful information from
even the best persona fact it is provided with when the copy mechanism is
disabled. Lastly, the response generated by MemNet+FullAttention model seems
to still suffer from repetition, semantic consistency, and relevancy problems
that were observed and reported by previous work.

##  5 Conclusion and Future Work

We propose a hierarchical pointer network for knowledge grounded dialogue
response generation. Our approach extends the pointer-generator network to
enable the decoder to simultaneously copy tokens from the available set of
relevant external knowledge in addition to dialogue context. We demonstrate
the effectiveness of our approach through various automatic and human
evaluations in comparison with several baselines on the ConvAi2 dataset.
Furthermore, we conduct diversity, fact inclusion, and error analysis
providing further insights into model behaviors. In the future, we plan to
apply our model to datasets of the same fashion where the dialogue is
accompanied by a much larger set of knowledge facts (e.g., Wikipedia articles)
Galley et al. (2018). This could be done by adding a retrieval component which
identifies a few contextually relevant facts Ghazvininejad et al. (2018) to be
used as input to DeepCopy.

## References

  * Abadi et al. (2016) Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, Manjunath Kudlur, Josh Levenberg, Rajat Monga, Sherry Moore, Derek G. Murray, Benoit Steiner, Paul Tucker, Vijay Vasudevan, Pete Warden, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. 2016.  Tensorflow: A system for large-scale machine learning.  In _12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16)_.
  * Bahdanau et al. (2015) Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2015.  Neural machine translation by jointly learning to align and translate.  In _International Conference on Learning Representations (ICLR)_.
  * Cho et al. (2014) Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. 2014.  Learning phrase representations using rnn encoder-decoder for statistical machine translation.  _arXiv preprint arXiv:1406.1078_.
  * Galley et al. (2018) Michel Galley, Chris Brockett, Xiang Gao, Bill Dolan, and Jianfeng Gao. 2018.  End-to-end conversation modeling: Moving beyond chitchat.  http://workshop.colips.org/dstc7/proposals/DSTC7-MSR_end2end.pdf.  Online; accessed 23 October 2018.
  * 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 _AAAI Conference on Artificial Intelligence (AAAI)_.
  * Kingma and Ba (2015) Diederik P. Kingma and Jimmy Ba. 2015.  Adam: A method for stochastic optimization.  In _International Conference on Learning Representations (ICLR)_.
  * Li et al. (2016a) Jiwei Li, Michel Galley, Chris Brockett, Georgios Spithourakis, Jianfeng Gao, and Bill Dolan. 2016a.  A persona-based neural conversation model.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 994–1003. Association for Computational Linguistics.
  * Li et al. (2016b) Jiwei Li, Michel Galley, Jianfeng Brockett, Chris ad Gao, and Bill Dolan. 2016b.  A diversity-promoting objective function for neural conversation models.  In _The North American Chapter of the Association for Computational Linguistics (NAACL)_.
  * Lin and Och (2004) C.Y. Lin and Franz Josef Och. 2004.  Automatic evaluation of machine translation quality using longest common subsequence and skip-bigram statistics.  In _Annual Meeting of the Association for Computational Linguistics (ACL)_.
  * Liu et al. (2018) Shuman Liu, Hongshen Chen, Zhaochun Ren, Yang Feng, Qun Liu, and Dawei Yin. 2018\.  Knowledge diffusion for neural dialogue generation.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1489–1498. Association for Computational Linguistics.
  * Luong et al. (2015) Minh-Thang Luong, Hieu Pham, and Christopher D. Manning. 2015.  Effective approaches to attention-based neural machine translation.  In _Empirical Methods on Natural Language Processing (EMNLP)_.
  * Nallapati et al. (2016) Ramesh Nallapati, Bowen Zhou, Cicero dos Santos, Caglar Gulcehre, and Bing Xiang. 2016.  Abstractive text summarization using sequence-to-sequence rnns and beyond.  In _Computational Natural Language Learning (CoNLL)_.
  * 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 _Annual Meeting of the Association for Computational Linguistics (ACL)_.
  * Raghu et al. (2018) Dinesh Raghu, Nikhil Gupta, and Mausam. 2018.  Hierarchical pointer-generator network for task oriented dialog.  _arXiv preprint arXiv:1805.01216_.
  * Ritter et al. (2011) Alan Ritter, Colin Cherry, and William B Dolan. 2011.  Data-driven response generation in social media.  In _Proceedings of the conference on empirical methods in natural language processing_ , pages 583–593. Association for Computational Linguistics.
  * Rush et al. (2015) M. Alexander Rush, Sumit Chopra, and Jason Weston. 2015.  A neural attention model for abstractive sentence summarization.  In _Empirical Methods on Natural Language Processing (EMNLP)_.
  * See et al. (2017) Abigail See, Peter J. Liu, and Christopher D. Manning. 2017.  Get to the point: Summarization with pointer-generator networks.  In _Annual Meeting of the Association for Computational Linguistics (ACL)_.
  * Serban et al. (2016) Iulian Vlad Serban, Alessandro Sordoni, Yoshua Bengio, Aaron C Courville, and Joelle Pineau. 2016.  Building end-to-end dialogue systems using generative hierarchical neural network models.  In _AAAI Conference on Artificial Intelligence (AAAI)_.
  * Serban et al. (2017) Iulian Vlad Serban, Alessandro Sordoni, Ryan Lowe, Laurent Charlin, Joelle Pineau, Aaron C Courville, and Yoshua Bengio. 2017.  A hierarchical latent variable encoder-decoder model for generating dialogues.  In _AAAI Conference on Artificial Intelligence (AAAI)_.
  * Sukhbaatar et al. (2014) Sainbayar Sukhbaatar, Arthur Szlam, Jason Weston, and Fergus Rob. 2014.  End-to-end memory networks.  In _Advances in Neural Information Processing Systems (NIPS)_.
  * Sutskever et al. (2014) Ilya Sutskever, Oriol Vinyals, and Quoc V Le. 2014.  Sequence to sequence learning with neural networks.  In _Advances in Neural Information Processing Systems (NIPS)_.
  * Tan et al. (2017) Jiwei Tan, Xiaojun Wan, and Jianguo Xiao. 2017.  Abstractive document summarization with a graph-based attentional neural model.  In _Annual Meeting of the Association for Computational Linguistics (ACL)_.
  * Vedantam et al. (2014) Ramakrishna Vedantam, C. Lawrence Zitnick, and Devi Parikh. 2014.  Cider: Consensus-based image description evaluation.  _arXiv preprint arXiv:1411.5726_.
  * Vinyals et al. (2015) Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. 2015.  Pointer networks.  In _Advances in Neural Information Processing Systems (NIPS)_.
  * Vinyals and Le (2015) Oriol Vinyals and Quoc Le. 2015.  A neural conversational model.  _arXiv preprint arXiv:1506.05869_.
  * Weston et al. (2018) Jason Weston, Emily Dinan, and Alexander H. Miller. 2018.  Retrieve and refine: Improved sequence generation models for dialogue.  _arXiv preprint arXiv:1808.04776v2_.
  * Xiong et al. (2017) Caiming Xiong, Victor Zhong, and Richard Socher. 2017.  Dynamic coattention networks for question answering.  In _International Conference on Learning Representations (ICLR)_.
  * Yavuz et al. (2018) Semih Yavuz, Chung-Cheng Chiu, Patrick Nguyen, and Yonghui Wu. 2018.  CaLcs: Continuously approximating longest common subsequence for sequence level optimization.  In _Empirical Methods on Natural Language Processing (EMNLP)_.
  * Zhang et al. (2018) Saizheng Zhang, Emily Dinan, Jack Urbanek, Arthur Szlam, Douwe Kiela, and Jason Weston. 2018.  Personalizing dialogue agents: I have a dog, do you have pets too?  In _Annual Meeting of the Association for Computational Linguistics (ACL)_.
  * Zoph and Knight (2016) Barret Zoph and Kevin Knight. 2016.  Multi-source neural translation.  In _The North American Chapter of the Association for Computational Linguistics (NAACL)_.


# Homology-constrained vector quantization entropy regularizer

Ivan Volkov

<EMAIL_ADDRESS>
Homology-constrained vector quantization entropy regularizer

Abstract

This paper describes an entropy regularization term for vector quantization
(VQ) based on the analysis of persistent homology of the VQ embeddings. Higher
embedding entropy positively correlates with higher codebook utilization,
mitigating overfit towards the identity and codebook collapse in VQ-based
autoencoders [1]. We show that homology-constrained regularization is an
effective way to increase entropy of the VQ process (approximated to input
entropy) while preserving the approximated topology in the quantized latent
space, averaged over mini batches. This work further explores some patterns of
persistent homology diagrams of latents formed by vector quantization. We
implement and test the proposed algorithm as a module integrated into a sample
VQ-VAE. Linked code repository provides a functioning implementation of the
proposed architecture, referred to as homology-constrained vector quantization
(HC-VQ) further in this work.

## Introduction

VQ-VAE and derived autoencoders [2] [3] can efficiently compress high-
dimensional data while preserving the discrete nature of compressed features.

Vector quantization VAEs are prone to codebook collapse, a phenomenon of
vanishing codebook utilization and vanishing entropy, which has negative
effects on robustness of dimensionality reduction and number of features
learned [4]. In some works it is addressed by random restarts of dead
(inactive) codes [1]. In this paper we propose a controlled entropy
regularization mechanism through topology adjustments of the quantized latent
space.

As described previously, periods of decreased VQ entropy appear commonly
throughout training. The phenomenon is similar in nature to posterior collapse
observed in VAEs. This constitutes the unwanted convergence of latent space
$q_{\phi}(z\mid x)$ towards the prior such that a VAE effectively stops
receiving any new informative features from the input data: $\exists i$ s.t.
$\forall\mathbf{x}q_{\phi}\left(z_{i}\mid\mathbf{x}\right)\approx
p\left(z_{i}\right)$

Heuristically, overly large latent entropy with a high $\sigma$ over an
interval may be a good indicator that the model is not converging, and
struggling to find effective gradients for parts of the computation graph.
Hence it makes sense to explore approaches of deriving entropy-inducing
mechanism that would be structural, upper-bounded and would not undermine
overall learning stability.

The research was motivated by the theory of entropy coding, which was
developed in the context of data compression. A classical work in signal
processing that made the relation between entropy coding and vector
quantization - ECVQ [5] \- proposed entropy-constrained vector quantization
for the analog signal. We found the core idea behind this analog signal
algorithm can be translated to dimensionality reduction performed in modern
autoencoder architecture. In that regard, parts of data compression theory
(specifically, entropy coding and source coding theorem) are applied to VQ
while dimensionality reduction itself is interpreted as a stochastic data
compression process in this context.

More formally, entropy coding is a process of compressing data while
minimizing code (representational unit) length within limit of the lower bound
of Shannon source coding theorem [6] that defines bounds of lossless
compression wrt the entropy of the source data:

$\mathbb{E}_{x\sim P}[l(d(x))]\geq\mathbb{E}_{x\sim
P}\left[-\log_{b}(P(x))\right]$

where $d$ is the coding function, $l$ is the number of symbols in a code word,
$b$ is the number of symbols used in output codes, and $P$ is the probability
of the source symbol.

We make an assumption that we can generalize the theorem to the VQ codebook
$\mathcal{X}$ utilization rate as opposed to individual code length (as each
element of the codebook has a fixed representational capacity), given that
$l(d(x))\in\mathcal{X}$. In other words, when we project the source coding
theorem from entropy coding to VQ, our assumptions are: (1) higher codebook
entropy corresponds to a more feature-rich (lossless) dimensionality reduction
but can lead to decreased learning speed, while (2) lower codebook entropy
corresponds to a faster learning rate (faster reconstruction convergence in
VQ-VAE) but can lead to a lossier dimensionlaity reduction.

However, we found that simply targeting increased codebook entropy undermines
learning stability and meaningful gradient computation. While experimenting
with various constrained entropy regularization methods we came to observe
some persistent patterns linking entropy to particular topological features
found in derived persistent homology. We found that a differentiable
implemention of PH can be used to define topological parameters which invoke
consistent entropy feedback without undermining the general stability of
learning wrt to autoencoder reconstruction loss.

Subsequently, in this work we explore an entropy regularization term for VQ
process in the context of VQ-VAE, based on the analysis of generated
persistent homology features.

##  1 Related work

One of the major relevant works is the topological autoencoder [7], where a
loss term wrt $\left(\mathbf{A}^{X},\mathbf{A}^{Z},\pi^{X},\pi^{Z}\right)$ was
proposed, corresponding to the distance matrices $A$ and topologically
relevant persistent pairings $\pi$ of input space $X$ and latent space $Z$,
respectively. Proposed topological autoencoder has proven to find consistent
patterns in observed persistent homology (PH) of constructed Vietoris-Rips
filtrations, strengthening the assumption that persistent homology can be
applied to dimensionality reduction.

The research was also motivated by a work that researched PH learning [8],
investigating whether neural networks are able learn PH features of
$F\circ\mathrm{PH}:\mathcal{X}\rightarrow\mathcal{D}\rightarrow\mathcal{Y}$
directly, where $\mathcal{X}$ is the space of inputs, $\mathcal{D}$ is the
space of persistence diagrams, and $\mathcal{Y}$ is the space of PH features.
The results indicated that a CNN can efficiently approximate various types of
persistence diagrams.

Two works addressing VQ codebook collapse - referred to as wav2vec [4] and
Jukebox [1] after their model labels - pushed the research to further link
codebook collapse and VQ entropy. We also make an assumption that higher
entropy of VQ latents correlates inversely with (unwanted) overfit towards the
identity [9], systemically observed in autoencoders, usually addressed by
entropy-inducing measures such as dropout and denoising mechanism.

Ideas of correlating entropy coding to analog signal quantization, as
mentioned, are presented in the ECVQ work that was published as early as 1989
[5]. Success of the ECVQ design - where minimum distortion was effectively
subjected to entropy constraints - sets the theoretical basis of our entropy-
constrained VQ design.

Finally, we borrow an analytical term (with the corresponding formula) from a
work that defined persistent entropy [10]. Persistent entropy refers to the
Shannon entropy of the filtration $\mathcal{D}$, in other words it’s an
entropy measure of the persistent homology itself. Persistent entropy is
interpreted as the degree of topological order in persistent homology, useful
for discerning between a noisy diagram and a diagram containing structural
topological features.

##  2 HC-VQ Entropy Regularization

Persistent homology of latent space Johnson-Lindenstrauss lemma (JL-lemma) is
central to theory backing dimensionality reduction. JL-lemma defines a
practical distortion limit of $(1\pm\varepsilon)$ for any Euclidean point
cloud of n points when embedded into a space with $O\left(\varepsilon^{-2}\log
n\right)$ dimensions.

It has been shown that persistent homology of a point cloud can also be
approximately preserved with similar constraints: random projections
approximately preserve persistent homology up to $1\pm\epsilon$ for
$\varepsilon\in[0,1]$ [11] [12], assumption tested in practice in the
topological autoencoder experiment [7].

Assumption of preserved persistent homology becomes foundational for this
work, as we can induce that a compressed representation (less generally,
quantized latents) can be equipped with an “optimal” persisent homology which
would be representative of features of the higher-dimensional data.

Constructing persisent homology for embeddings We examined vector quantization
as implemented in a VQ-VAE, thus many aspects are best understood in the
context of autoencoders and deep learning. However, the algorithm can be
generalized to vector quantization independent of deep learning process.

On a higher level, it makes sense to apply topological analysis to deeper
autoencoder layers, as dim. reduction moves representations from input-
specific perturbations of the “shallow layers” (e.g. image noise) to more
general feature layers of the bottleneck.

VQ layers are situated at or close to autoencoder bottleneck, working on data
preprocessed by shallow layers and use k-NN algorithm to quantize their
latents in the following fashion:

$z_{q}(x)=e_{k},\quad\text{ where }\quad
k=\operatorname{argmin}_{j}\left\|z_{e}(x)-e_{j}\right\|_{2}$ (1)

As per classical VQ-VAE implementation, an embedding table weight serves as a
map of 1-nearest neighbors, to which tensors of input are quantized. We
perform our topological analysis on the embedding table domain wrt the entropy
of the embeddings, constructing a Vietoris-Rips filtration with respective
persistent homology as follows.

Let $(\mathcal{X},d)$ be the assigned metric space of the $\mathcal{X}$
embedding table point cloud. The associated Vietoris-Rips complex of
$\mathcal{X}$ is defined as $VR_{s}(\mathcal{X})$ with a distance threshold of
$\epsilon$:

$VR_{s}(\mathcal{X})=\left\\{\left[v_{0},\ldots,v_{n}\right]\mid\forall
i,jd\left(v_{i},v_{j}\right)\leq\epsilon\right\\}.$

The persistent simplicial cohomology of the constructed VR complex
$H^{*}(\mathcal{X}(\epsilon))$ is obtained by assembling a disjoint set of
simplicial complexes (filtration) at various $\epsilon$ in (0, $k$) dimensions
- for the purposes of this work we define $k$ at 1:

$K_{\epsilon_{0}}\longrightarrow K_{\epsilon_{1}}\longrightarrow
K_{\epsilon_{n-2}}\rightleftarrows K_{\epsilon_{n-1}}$ $\displaystyle
H^{k}\left(K_{\epsilon_{0}}\right)\longrightarrow
H^{k}\left(K_{\epsilon_{1}}\right)\longrightarrow\cdots\longrightarrow
H_{k}\left(K_{\epsilon_{n-2}}\right)\longrightarrow
H_{k}\left(K_{\epsilon_{n-1}}\right)$

Homology signature Having obtained $H^{k}(\mathcal{X}(\epsilon))$ and it’s
corresponding persistent homology diagram $\mathcal{D}$, we can investigate
correlations of some aspects of $\mathcal{D}$ wrt selected entropy parameters
emerging during VQ-VAE training. For our choice of $k$, we found two
particularly sensitive features of $\mathcal{D}$, which will define the
partial persistent diagram signature $\mathcal{S^{\mathcal{D}}}$ for the
purposes of this work:

$\mathcal{S^{\mathcal{D}}}:=\\{\beta^{1},\mu^{0}\\}$

Where $\beta^{1}$ refers to the 1-dimensional Betti numbers (which can be
intuitively viewed as the number of loops formed by enclosing 1-simplices of
the filtration), and where $\mu^{0}$ refers to the mean distance between
critical 0-simplices (which can be intuitively viewed as a sparsity metric
between connected components of the filtration).

Entropy correlation We measure entropy of quantized latents with the standard
entropy formula [1]. We evaluate the entropy of quantized latents (for each
mini batch), not just the entropy of the codebook - such that the model can
learn data-specific regularization of the embeddings.

$E_{codebook}=-\sum_{i=1}^{n}(K_{p}*\log_{e}\left(K_{p}\right))_{i},\ \ \
where\ K_{p}=\dfrac{z_{e}(x)}{\sum_{i=1}^{n}(z_{e}(x))_{i}}$

Where $z_{e}(x)$ denotes a vector space of quantized latents. We further
evaluate it against $E(H)$ where $H$ is the input data.

In addition, we analyze the persistent entropy of the filtration, however we
do not include it in our loss calculation. Persistent entropy $E(F)$
definition is taken from the previously cited work [10]:

$E(F)=-\sum_{i=1}^{n}p_{i}\log\left(p_{i}\right)\text{ where
}p_{i}=\frac{\ell_{i}}{S_{L}},\ell_{i}=y_{i}-x_{i}\text{, and
}S_{L}=\sum_{i=1}^{n}\ell_{i}\text{. }$

Let $F$ be a (Vietoris-Rips simplicial) filtration constructed from the point
cloud $\mathcal{X}$ and the corresponding persistence diagram
$\operatorname{\mathcal{D}}(F)=\left\\{a_{i}=\left(x_{i},y_{i}\right)\mid
1\leq i\leq n\right\\}$ (being $x_{i}<y_{i}$ for all i), let
$L=\left\\{\ell_{i}=y_{i}-x_{i}\mid 1\leq i\leq n\right\\}$.

Regularization term We define the dynamical HC-VQ regularization loss term wrt
to the $E_{z}$ entropy, where $z$ refers to the point cloud of quantized
latents. The term is scaled by an arbitrary domain-specific hyperparameter
$\lambda$ for numerical stability:

$\mathcal{L}_{overall}:=\mathcal{L}+\mathcal{L}_{r}(\mathcal{S^{\mathcal{D}}},\lambda*\Delta
E_{z}/E_{input}*T_{\mathcal{S}})$

$\ where\ \Delta E_{z}\ :=\ \mu_{k}\\{E_{z}\\}$

We accumulate entropy count $E_{z}$ for each step (mini batch) and then
calculate a mean value as a measure of entropy over a step interval $k$. More
specifically, $k$ is a period hyperparameter referring to a number of training
steps - or, more generally, vector quantization attempts to average on. Higher
$k$ value produces smoother entropy estimations.

Target value of $S^{\mathcal{D}}$ is defined by two hyperparameters
$T_{\beta},T_{\mu}$ comprising the target homology signature
$T_{\mathcal{S}}$.

##  3 Implementation and Hyperparameters

A functioning implementation of HC-VQ module integrated to a VQ-VAE is made
available in a public git repo. [13] We use an embedding table
$X\in\mathbb{R}^{128\times 64}$. An embedding layer is incorporated at the
bottleneck dimension of a VQ-VAE with 2 convolutional and 2 ReLU layers at
each side of the autoencoder.

After quantizing the latents, we calculate step entropy $E_{z}$ and compare it
to the entropy of the source $E_{input}$ at each $k=200$.

HC-VQ is implemented with full support for backpropagation: construction of
persistence diagrams is differentiable; Betti numbers are counted using
approximate floating-point counting based on narrow gaussians.

Loss is calculated with the standard MSE function, and returned as part of the
overall VQ module loss. Learning rate is set to $0.0008$, VQ-VAE commitment
loss $\beta$ is set to 0.25.

The base VQ-VAE implementation is reused from a sample VAE autoencoder
collection repository.[14] Vietoris-Rips filtration is calculated with giotto-
ph software that supports calculation of gradients. We count Betti numbers
without thresholding of $\epsilon$, such that all the returned diagram
pairwise distance are counted. $k$-value - number of training steps for the
$E_{z}$ aggregation period - is set to 200.

##  4 Experiments

We test our HCVQ in the context of a sample VQ-VAE on three datasets with
varying complexity: CelebA face dataset, MNIST number dataset, and Fashion-
MNIST articles of clothing dataset.

We train two VQ-VAE models for 27000 steps each, one with HC-VQ term
deactivated and one with HC-VQ term activated (participating in overall loss
computation). Same dataseed is reused for producing predictable results of
stochastic or pseudorandom functions.

HC-VQ dry runs  The following observations were made during the most complex
(CelebA) dataset training. In $\mathcal{S^{\mathcal{D}}}$, $\mu^{0}$ (mean
$\epsilon$ between persistent pairings of critical simplices in dimension 0)
was most correlated to entropy $\Delta$s at each interval. $\mu^{0}$ was
increasing steadily as training went on:

Figure 1: $E_{z}$ entropy with no HCVQ Figure 2: $\mu^{0}$ with no HCVQ

Figure 1 presents an instance of diminished codebook utlization
($\approx(0,5000)$ step interval)

Comparisons to active HC-VQ term The following were CelebA training
observations with HCVQ loss term active. A set of hyperparameters
{$T_{\beta}:=100$, $T_{\mu}:=0.5$} influenced the $E_{z}$ entropy parameter
rather drastically:

Figure 3: $E_{z}$ entropy with HC-VQ, unstable $E>10$ values are clamped

By tracking the relaionship of reconstruction loss and entropy we can observe
some periods of model instability where it was struggling to fit the nudges of
the HC-VQ:

Figure 4: Reconstruction loss with HC-VQ

And a respective $\Delta E_{z}/E_{input}$ entropy loss metric:

Figure 5: HC-VQ $\Delta E_{z}/E_{input}$ $\mathcal{L}$

Persistent entropy indicates a more orderly topological structure with HC-VQ
enabled:

Figure 6: Persistent entropy comparison

A snapshot of final diagrams (which remained stable over last $k$-intervals)
indicates a more sparse positioning of connected simplices with HC-VQ enabled:

Figure 7: Dry-run: step 27000 persistent homology diagram Figure 8: HC-VQ
active: step 27000 persistent homology diagram

##  5 Conclusion

We found that HC-VQ term technique was able to efficiently increase codebook
utilisation (measured by $E_{z}$) during VQ-VAE training process compared to
dry runs. Heuristically, we observed sparse persistent homology and (stable)
high persistent entropy, strengthening the assumption that HC-VQ embedding
retained more features compared to VQ-VAE training with the same codebook
size.

The biggest drawback of HC-VQ would be numerical stability, which can be
mitigated by fitting an appropriate $\lambda$ scaling hyperparameter and
decreasing hyperparameters $T_{\beta},T_{\mu}$ (at the cost of decreased
learning speed).

## References

  * [1] P. Dhariwal, H. Jun, C. Payne, J. W. Kim, A. Radford, and I. Sutskever, “Jukebox: A generative model for music,” 2020. [Online]. Available: https://arxiv.org/abs/2005.00341
  * [2] A. v. d. Oord, O. Vinyals, and K. Kavukcuoglu, “Neural discrete representation learning,” 2017. [Online]. Available: https://arxiv.org/abs/1711.00937
  * [3] A. Razavi, A. v. d. Oord, and O. Vinyals, “Generating diverse high-fidelity images with vq-vae-2,” 2019. [Online]. Available: https://arxiv.org/abs/1906.00446
  * [4] A. Baevski, H. Zhou, A. Mohamed, and M. Auli, “wav2vec 2.0: A framework for self-supervised learning of speech representations,” 2020. [Online]. Available: https://arxiv.org/abs/2006.11477
  * [5] P. Chou, T. Lookabaugh, and R. Gray, “Entropy-constrained vector quantization,” _IEEE Transactions on Acoustics, Speech, and Signal Processing_ , vol. 37, no. 1, pp. 31–42, 1989.
  * [6] C. E. Shannon, _Coding Theorems for a Discrete Source With a Fidelity CriterionInstitute of Radio Engineers, International Convention Record, vol. 7, 1959._ , 1993, pp. 325–350.
  * [7] M. Moor, M. Horn, B. Rieck, and K. Borgwardt, “Topological autoencoders,” 2019\. [Online]. Available: https://arxiv.org/abs/1906.00722
  * [8] G. Montufar, N. Otter, and Y. G. Wang, “Can neural networks learn persistent homology features?” in _TDA & Beyond_, 2020. [Online]. Available: https://openreview.net/forum?id=pqpXM1Wjsxe
  * [9] H. Steck, “Autoencoders that don't overfit towards the identity,” in _Advances in Neural Information Processing Systems_ , H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, Eds., vol. 33. Curran Associates, Inc., 2020, pp. 19 598–19 608. [Online]. Available: https://proceedings.neurips.cc/paper/2020/file/e33d974aae13e4d877477d51d8bafdc4-Paper.pdf
  * [10] N. Atienza, R. González-Díaz, and M. Rucco, “Persistent entropy for separating topological features from noise in vietoris-rips complexes,” _CoRR_ , vol. abs/1701.07857, 2017. [Online]. Available: http://arxiv.org/abs/1701.07857
  * [11] D. R. Sheehy, “The persistent homology of distance functions under random projection,” in _Proceedings of the Thirtieth Annual Symposium on Computational Geometry_ , ser. SOCG’14. New York, NY, USA: Association for Computing Machinery, 2014, p. 328–334. [Online]. Available: https://doi.org/10.1145/2582112.2582126
  * [12] M. Lotz, “Persistent homology for low-complexity models,” 2017. [Online]. Available: https://arxiv.org/abs/1709.01037
  * [13] st4cks1defl0w, “HCVQ,” 11 2022. [Online]. Available: https://github.com/st4cks1defl0w/hcvq
  * [14] A. Subramanian, “Pytorch-vae,” https://github.com/AntixK/PyTorch-VAE, 2020\.