Key-Value Retrieval Networks for Task-Oriented Dialogue

In plain words

Task-oriented assistants, such as the one in a car that books appointments or reports the weather, need to look facts up in a database. Earlier neural versions of these assistants either could not look facts up cleanly, or needed extra hand-built parts that track what the user wants so far. This paper keeps everything as one learned network that reads the conversation and writes the reply.

The new piece is a lookup step inside the reply writer. Each fact in the database is stored as a small (subject, relation, value) entry. While writing, the model scores these entries against its current state, as it would score words. A high-scoring entry raises its key word, which is then swapped back for the real value. The result is that the model can say the right fact, such as a time or a place, without a separate tracker that names the user's goal.

The authors also built a new dataset of in-car dialogues in three areas: calendar, weather and points of interest. The model does better than a hand-written rule system on the automatic and human scores reported here, and it does not reach human level.

TL;DR

• An LSTM encoder-decoder with encoder attention, plus a second attention over knowledge-base (KB) keys whose logits are added to the output vocabulary logits §2.1-§2.3.
• No explicit belief tracker or dialogue state: training is plain token-level cross-entropy §5.2.
• Author-reported test results: BLEU 13.2 and entity F1 48.0, against 6.6 and 43.8 for the rule-based model and 11.0 and 37.0 for Copy Net tab. 3.
• Use it as a reference for KB-key attention in a copy-style decoder. The paper does not release code (see Paper vs code), and some details that an implementation needs are not stated.

Problem

Neural task-oriented dialogue models of the time had two problems §1. They struggled to use knowledge-base contents while staying end-to-end trainable. They also usually needed belief trackers and dialogue-state annotation, which costs labelling effort and breaks differentiability §1 §2. Earlier systems that query a KB either emit well-formed API calls, which need intermediate supervision and break differentiability, or attend softly over the KB and feed the result into a reinforcement-learning policy with belief trackers §2.3. The paper also notes that the data for this area was scarce §4.

Method

Overview. The encoder is an LSTM over the tokens of the dialogue context, which ends with the current user turn §2.1 eq. 1. The decoder is an LSTM with attention over the encoder states, as in the standard attention sequence-to-sequence model §2.2 eq. 2-6. The KV retrieval step adds one logit per KB key to the output logits at each decoding step §2.3 eq. 7-9. The model uses one KB per dialogue, stored as normalized triples §2.3.

Steps.

1. Context encoding §2.1 eq. 1. Dialogue context tokens x_1,\dots,x_m (all turns up to the current user turn) are embedded with a trained embedding function and run through an LSTM. The paper writes h_i = \mathrm{LSTM}(\phi^{emb}(x_i), h_{i-1}).

2. Encoder attention in the decoder §2.2 eq. 2-4. At each decoding step t the decoder state \tilde h_t is scored against each encoder state h_i with a two-layer MLP using tanh at both layers (eq. 2). The scores are normalised with softmax (eq. 3) and the encoder states are summed with those weights into a context vector (eq. 4).

3. Vocabulary logits §2.2 eq. 5-6. The decoder state and the context vector are projected to output logits o_t with a learned matrix U, then softmaxed (eq. 5 and eq. 6).

4. KB entries as triples §2.3. Each KB entry is (subject, relation, object). A single row such as an event with a time, a date and a party is split into one triple per attribute. Every KB has at most 230 normalized triples §2.3.

5. KB keys and canonical tokens §2.3. The key of a triple is the sum of the word embeddings of its subject and relation (for example "meeting" and "time"). The value is replaced in the output vocabulary by a canonical token made from the subject and relation (for example "meeting_time"). The output vocabulary becomes |V| + n, where n counts the distinct canonical key entries §2.3.

6. KB logits §2.3 eq. 7-8. For each key k_j the KB attention score is a two-layer tanh MLP over [k_j, \tilde h_t] with a learned vector r (eq. 7). These scores are placed at the canonical-token positions of a sparse vector \bar v^t of length |V| + n and added to the output logits (eq. 8).

7. Output and decoding §2.3 eq. 9. The combined logits are softmaxed (eq. 9). At inference the argmax token is taken as the next input. If that token is a canonical token, it is converted to the real value by a lookup in the KB §2.3.

Equations (numbered by the order of the align lines in the LaTeX source; see Pitfalls):

h_i = \mathrm{LSTM}(\phi^{emb}(x_i), h_{i-1}) eq. 1

u_i^t = w^T \tanh(W_2 \tanh(W_1[h_i, \tilde h_t])) eq. 2

a_i^t = \mathrm{Softmax}(u_i^t) eq. 3

\tilde h_t' = \sum_{i=1}^{m} a_i^t h_i eq. 4

o_t = U[\tilde h_t, \tilde h_t'] eq. 5

y_t = \mathrm{Softmax}(o_t) eq. 6

u_j^t = r^T \tanh(W_2' \tanh(W_1'[k_j, \tilde h_t])) eq. 7

o_t = U[\tilde h_t, \tilde h_t'] + \bar v^t eq. 8

y_t = \mathrm{Softmax}(o_t) eq. 9

Pseudocode. One decoding step, then greedy decoding. Shapes are given for the sizes the paper uses where it states them (hidden and embedding size 200, §5.2).

# One decoding step of the KV retrieval net  [§2.2] [§2.3] [eq. 2-9]
# Input:  decoder_state (H,); encoder_states (m, H)
#         kb_keys (n_keys, E); kb_token_ids (n_keys,) into |V| + n
# Output: probs over the extended vocabulary, (|V| + n,)

def decode_step(decoder_state, encoder_states, kb_keys, kb_token_ids):
    # Score each encoder state against the decoder state  [§2.2] [eq. 2]
    enc_scores = encoder_attention_scores(encoder_states, decoder_state)
    # Normalise the encoder scores  [§2.2] [eq. 3]
    enc_weights = softmax(enc_scores)                     # (m,)
    # Weighted sum of encoder states  [§2.2] [eq. 4]
    enc_context = enc_weights @ encoder_states            # (H,)
    # Vocabulary logits  [§2.2] [eq. 5]
    logits = U @ concat(decoder_state, enc_context)       # (|V| + n,)
    # Score each KB key against the decoder state  [§2.3] [eq. 7]
    kb_scores = kb_attention_scores(kb_keys, decoder_state)   # (n_keys,)
    # Add KB scores at their canonical-token positions  [§2.3] [eq. 8]
    logits[kb_token_ids] += kb_scores
    # Normalise the extended logits  [§2.3] [eq. 9]
    return softmax(logits)


# Greedy decoding at inference  [§2.3]
# The stop rule and maximum length are not stated in the paper.
def greedy_decode(context, kb, max_len):
    tokens = []
    for step in range(max_len):
        probs = decode_step(...)
        token = argmax(probs)
        # Canonical KB tokens are looked up to their real value  [§2.3]
        if token is a KB token:
            token = kb.value_for(token)
        tokens.append(token)
    return tokens

Training objective §2.2 §5.2. Training predicts each output token so that the probability of the gold reply, conditioned on the input, is as high as possible. In practice this is token-level cross-entropy over the output vocabulary §5.2.

Hyperparameters

Results

Author-reported. Setup: the new in-car corpus of multi-turn dialogues in three domains (calendar scheduling, weather and points of interest), with one model trained on all domains jointly [abstract] §3. Test split of 304 dialogues tab. 2. Entity F1 is computed on canonicalized entity forms §5.4.1. Baselines are a rule-based system §5.3, Copy Net, a copy-augmented sequence-to-sequence model derived from the authors' earlier work §5.3, and an attention sequence-to-sequence model without KB attention §5.4.2 tab. 3.

Automatic evaluation tab. 3 (test set; bold marks the best model in the source):

Human evaluation, real-time chat tab. 4 (scale 1 to 5; 120 scenarios; the Turker judged the partner):

Human evaluation of system outputs on test dialogues tab. 5 (80 dialogues; scale 1 to 5):

The authors state the second human regime is less realistic because it starts from dialogue contexts sampled from the dataset §5.5.

Paper vs code

No official code.

The paper gives no code link in the abstract or the LaTeX source, and the arXiv metadata has no comments field. Its only external link is a footnote to the dataset page §1. Searches run for this card:

• The dataset blog page that the paper's footnote links (on the Stanford NLP site) could not be reached (connection refused), so it was not checked for a code link.
• GitHub repository search for kvret and for key-value retrieval dialogue returned no repository owned by an author or the Stanford NLP group.
• parkervg/kv-retrieval-net describes itself as an implementation of this paper. It is a third-party reimplementation, not an author repository, and was not used.
• A GitHub user search for "mihail eric" returned the account mihail911. The paper does not link it, and the first 19 of its repositories had no match. The rest of that list was not checked, so this is not confirmed as the authors' code.

No code was cloned, so there is no code_commit or code_license.

Pitfalls

• Equation numbers are inferred from the LaTeX source. The align environments number their lines in source order: eq. 1 is the encoder, eq. 2 to 6 the decoder and eq. 7 to 9 the KB block. The in-text references "(2)" for the attention logit and "(8)" for the combined output agree with this count. Check the numbers against the PDF before quoting them.
• Table numbers conflict. The text calls the dataset statistics table "Table 1" and the slot-type table "Table 2" §3.1. In the source the slot-type table comes first. This card cites the statistics table as tab. 2, the number its position in the source gives. Check the PDF.
• Percentages in the text are absolute points. The text says the model is 4.2% above the rule-based entity F1, which is 48.0 against 43.8 (4.2 points). It says 11% above Copy Net, which is 48.0 against 37.0 (11.0 points). It says the gap to human entity F1 is about 12.7%, which is 60.7 against 48.0 (12.7 points) §5.4.2.
• KB logits are not normalised over keys. Eq. 7 gives raw scores that go straight into the output logits in eq. 8. The paper does not state a softmax over KB keys, so their scale is learned only through r, W_1' and W_2'.
• Shape of U is not stated. Eq. 5 and eq. 8 use the same U, but the paper does not say whether U has |V| rows or |V| + n rows. The KB positions of the output vector need |V| + n entries.
• Canonical-key collisions are not addressed. Two triples with the same subject and relation share one canonical token. The paper does not say what happens to their values.
• Count of n is not given for the corpus. The paper defines n as the number of distinct canonical key entries §2.3 but does not report it.
• The no-encoder-attention variant has no equation. It is described in words only, as having no encoder context vector during decoding [fig. 2 caption]. Its exact form (dropping \tilde h_t' from eq. 5 and eq. 8) is inferred, not stated.
• Training input is not spelled out. The objective is a log-likelihood of the correct output §2.2, which implies teacher forcing. The paper does not say so explicitly.
• Surface realisation adds variance. Canonical forms are mapped back to surface forms by sampling from training and validation frequencies §5.1. Metrics use canonical forms, so entity F1 is unaffected, but BLEU depends on the sampled surface forms. The seed and any repeated samples are not stated.
• Random search is the only tuning stated. The number of trials, the final chosen values and whether reported numbers come from one run or an average are all not stated, and no variance is reported. Treat the 13.2 BLEU and 48.0 entity F1 as single-run author results.
• Human judgements are small and unsupported by agreement statistics. The real-time regime uses 120 scenarios. The test-output regime uses 80 dialogues. No inter-rater agreement or pay details are given §5.5. The "human" row is a second Turker, not a reference oracle.
• The dataset licence is unknown. The data is offered at the footnote URL §1, which could not be reached. The paper states no licence for it. The paper's CC BY 4.0 licence covers the text only. Do not redistribute the corpus without checking its terms.
• Author list differs between sources. arXiv metadata lists two authors. The LaTeX source lists four: Mihail Eric, Lakshmi Krishnan, Francois Charette and Christopher D. Manning [title block]. This card names all four, as attribution requires.
• Baseline differences. The Copy Net baseline does not use the entity-type input features of the original work, which the authors found worse on this data §5.3. Comparisons with the original Copy Net numbers are therefore not like for like.

Lineage

• Builds on: key-value memory networks for machine reading, which inspire the key-value structure of the KB §2.3. Attention over encoder states follows Bahdanau et al. and Luong et al. §2.2. Both are cited by name, not by arXiv id, because the wiki has no page for them.
• Compared against: a rule-based dialogue system; Copy Net, derived from the authors' earlier copy-augmented model §5.3; an attention sequence-to-sequence model without KB attention §5.4.2; and the KV retrieval net without encoder attention tab. 3.
• Contrasts with: end-to-end neural dialogue systems that use belief trackers or dialogue-state modules. The paper argues its model removes the need for them §1 §2.
• Superseded by: not known from content already in this wiki.