24.2.2 NLU component

The NLU (natural language understanding) component of dialogue systems must produce a semantic representation which is appropriate for the dialogue task. Many speech-based dialogue systems, since as far back as the GUS system (Bobrow et al., 1977), are based on the frame-and-slot semantics discussed in Chapter 15. A travel system, for example, which has the goal of helping a user find an appropriate flight, would have a frame with slots for information about the flight; thus a sentence like Show me morning flights from Boston to San Francisco on Tuesday might correspond to the following filled-out frame (from Miller et al. (1994)):

SHOW:

FLIGHTS:

ORIGIN:

CITY: Boston

DATE:

DAY-OF-WEEK: Tuesday

TIME:

PART-OF-DAY: morning

DEST:

CITY: San Francisco

How does the NLU component generate this semantic representation? Some dialogue systems use general-purpose unification grammars with semantic attachments, such as the Core Language Engine introduced in Ch. 18. A parser produces a sentence meaning, from which the slot-fillers are extracted (Lewin et al., 1999).

Other dialogue systems rely on simpler domain-specific semantic analyzers, such as semantic grammars. A semantic grammar is a CFG in which the actual node names in the parse tree correspond to the semantic entities which are being expressed, as in the following grammar fragments:

SHOW → show me | i want | can i see|...

DEPART_TIME_RANGE → (after|around|before) HOUR | morning | afternoon | evening

HOUR → one|two|three|four... | twelve (AMPM)

FLIGHTS → (a) flight | flights

AMPM → am | pm

ORIGIN → from CITY

DESTINATION → to CITY

CITY → Boston | San Francisco | Denver | Washington

These grammars take the form of context-free grammars or recursive transition networks (Issar and Ward, 1993; Ward and Issar, 1994), and hence can be parsed by any standard CFG parsing algorithm, such as the CKY or Earley algorithms introduced in Ch. 13. The result of the CFG or RTN parse is a hierarchical labeling of the input string with semantic node labels:

SHOW FLIGHTS ORIGIN DESTINATION DEPART_DATE DEPART_TIME to CITY

Show me flights from boston to san francisco on tuesday morning

Since semantic grammar nodes like ORIGIN correspond to the slots in the frame, the slot-fillers can be read almost directly off the resulting parse above. It remains only to put the fillers into some sort of canonical form (for example dates can be normalized into a DD:MM:YY form, times can be put into 24-hour time, etc).

The semantic grammar approach is very widely used, but is unable to deal with ambiguity, and requires hand-written grammars that can be expensive and slow to create.

Ambiguity can be addressed by adding probabilities to the grammar; one such probabilistic semantic grammar system is the TINA system (Seneff, 1995) shown in Fig. 24.6; note the mix of syntactic and semantic node names. The grammar rules in TINA are written by hand, but parse tree node probabilities are trained by a modified version of the SCFG method described in Ch. 14.

An alternative to semantic grammars that is probabilistic and also avoids hand-coding of grammars is the semantic HMM model of Pieraccini et al. (1991). The hidden states of this HMM are semantic slot labels, while the observed words are the fillers of the slots. Fig. 24.7 shows how a sequence of hidden states, corresponding to slot names, could be decoded from (or could generate) a sequence of observed words. Note that the model includes a hidden state called DUMMY which is used to generate words which do not fill any slots in the frame.

The goal of the HMM model is to compute the labeling of semantic roles $C = c_{1}, c_{2}, ..., c_{i}$ (C for ‘cases’ or ‘concepts’) that has the highest probability $P(C|W)$ given some words $W = w_{1}, w_{2}, ..., w_{n}$. As usual, we use Bayes Rule as follows:

$$ \begin{aligned}\underset{C}{\operatorname{argmax}}P(C|W)&=\underset{C}{\operatorname{argmax}}\frac{P(W|C)P(C)}{P(W)}\\&=\underset{C}{\operatorname{argmax}}P(W|C)P(C)\end{aligned} $$

$$ =\prod_{i=2}^{N}P(w_{i}|w_{i-1}...w_{1},C)P(w_{1}|C)\prod_{i=2}^{M}P(c_{i}|c_{i-1}...c_{1}) $$

The Pieraccini et al. (1991) model makes a simplification that the concepts (the hidden states) are generated by a Markov process (a concept $ M $-gram model), and that the observation probabilities for each state are generated by a state-dependent (concept-dependent) word $ N $-gram word model:

$$ \begin{aligned}P(w_{i}|w_{i-1},...,w_{1},C)&=P(w_{i}|w_{i-1},...,w_{i-N+1},c_{i})\\P(c_{i}|c_{i-1},...,c_{1})&=P(c_{i}|c_{i-1},...,c_{i-M+1})\end{aligned} $$

Based on this simplifying assumption, the final equations used in the HMM model are as follows:

$$ \underset{C}{\operatorname{argmax}}P(C|W)=\prod_{i=2}^{N}P(w_{i}|w_{i-1}...w_{i-N+1},c_{i})\prod_{i=2}^{M}P(c_{i}|c_{i-1}...c_{i-M+1}) $$

These probabilities can be trained on a labeled training corpus, in which each sentence is hand-labeled with the concepts/slot-names associated with each string of words. The best sequence of concepts for a sentence, and the alignment of concepts to word sequences, can be computed by the standard Viterbi decoding algorithm.

In summary, the resulting HMM model is a generative model with two components. The $ P(C) $ component represents the choice of what meaning to express; it assigns a prior over sequences of semantic slots, computed by a concept $ N $-gram. $ P(W|C) $ represents the choice of what words to use to express that meaning; the likelihood of a particular string of words being generated from a given slot. It is computed by a word N-gram conditioned on the semantic slot. This model is very similar to the HMM model for named entity detection we saw in Ch. 22. Technically, HMM models like this, in which each hidden state correspond to multiple output observations, are called semi-HMMs. In a classic HMM, by contrast, each hidden state corresponds to a single output observation.

Many other kinds of statistical models have been proposed for the semantic understanding component of dialogue systems. These include the Hidden Understanding

Model (HUM), which adds hierarchical structure to the HMM to combine the advantages of the semantic grammar and semantic HMM approaches (Miller et al., 1994, 1996, 2000), or the decision-list method of Rayner and Hockey (2003).