Sequential Short-Text Classification with Recurrent and Convolutional Neural Networks

In plain words

Many short texts come in order: sentences in a document, or turns in a conversation. Most neural classifiers look at one text at a time and ignore what came just before it. This paper labels each utterance in a dialog with its "dialog act", a label for the role the utterance plays, and lets the classifier see the texts before it.

The model works in two steps. First, a small network turns each text into a fixed-size vector, using either a recurrent network that reads the words in order or a convolutional network that scans short word windows. Second, a small two-layer network reads that vector for the current text together with the vectors of a few earlier texts, and outputs a probability for each label.

Adding the earlier texts helped in the authors' experiments. Using history at the text-vector level helped more than using it at the label level. The authors report the best accuracy on three dialog datasets.

TL;DR

• Sequential short-text classification: label each text in a sequence using the text's own vector plus those of the few texts before it §1 §2.2.
• Text encoder: an LSTM (max pooling) or a CNN (n filters, height 3, max over time) §2.1 tab. 2.
• Result: author-reported best accuracies of 66.2 (DSTC 4, LSTM), 84.6 (MRDA, CNN) and 73.1 (SwDA, CNN) tab. 4.
• Relevant if you need dialog act labels or any ordered short-text classification. Expect to fill in the training details yourself: learning rate, batch size and epochs are not stated.

Problem

Most neural short-text classifiers handle each text in isolation, even when the texts occur in sequences such as sentences in a document or utterances in a dialog. Earlier sequential approaches were mostly non-neural: hidden Markov models, maximum entropy and naive Bayes §1. The paper targets dialog act prediction, which it describes as a label based on pragmatic, semantic and syntactic criteria §1. The datasets are sets of dialogs, each a sequence of utterances §3.1 tab. 1.

Method

Notation. A short text of length ℓ is a sequence of m-dimensional word vectors. Its encoder output is an n-dimensional vector s. The classifier has k output classes §2 §2.1.

Step 1: short-text vector (s). Use one of two encoders §2.1.

• RNN (LSTM) encoder §2.1.1. An LSTM reads the word vectors in order, with h_0 = c_0 = 0. Its gates are given by:

  i_t = \sigma(W_i x_t + U_i h_{t-1} + b_i) f_t = \sigma(W_f x_t + U_f h_{t-1} + b_f) \tilde{c}_t = \tanh(W_c x_t + U_c h_{t-1} + b_c) c_t = f_t \odot c_{t-1} + i_t \odot \tilde{c}_t o_t = \sigma(W_o x_t + U_o h_{t-1} + b_o) h_t = o_t \odot \tanh(c_t)

  §2.1.1, unnumbered display equations. The weights are W_j ∈ R^{n×m} and U_j ∈ R^{n×n}, with bias b_j ∈ R^n. Pooling over the hidden states h_{1:ℓ} gives s. The paper considers last, mean and max pooling; max is the chosen setting §2.1.1 tab. 2.

• CNN encoder §2.1.2. A filter W_f ∈ R^{h×m} slides over windows of h consecutive word vectors:

  c_t = \text{ReLU}(W_f \bullet X_{t:t+h-1} + b_f)

  §2.1.2, unnumbered display equation. n filters give features c_t ∈ R^n per window. Max pooling over the windows gives s ∈ R^n. The chosen filter height is h = 3 tab. 2 fig. 1.

Step 2: sequential classification (z_i). For the i-th text, the input is the window of vectors s_{i−d1−d2 : i}. Here d1 and d2 are the history sizes of the first and second layers §2.2.

• Layer 1 computes, for each j in [i−d2, i], a class representation y_j ∈ R^k §2.2:

  y_j = \tanh\left( \sum_{d=0}^{d_1} W_{-d}\, s_{j-d} + b_1 \right)

• Layer 2 combines those representations and applies a softmax, giving z_i ∈ R^k §2.2:

  z_i = \text{softmax}\left( \sum_{j=0}^{d_2} W_{-j}\, y_{i-j} + b_2 \right)

  The text names these matrices U_0, U_{−1}, U_{−2} ∈ R^{k×k} and writes W in the equation. See Pitfalls.

Figure 2 shows four history settings, (d1, d2) = (0, 0), (2, 0), (0, 2) and (1, 1). Setting (0, 0) is ordinary non-sequential classification fig. 2 §2.2. The prediction is the class with the highest z_i value, which is the standard reading of a softmax output but is not written in the paper.

Pseudocode. The encoder and classifier, in the notation of this card:

# Short-text encoder  [§2.1]
# Input:  word_vectors (T, m) for one short text
# Output: short_text_vector (n,)

def encode_lstm(word_vectors):
    # LSTM over the words, h_0 = c_0 = 0  [§2.1.1]
    hidden_states = lstm(word_vectors)             # (T, n)
    # Max pooling over time, the chosen setting  [§2.1.1] [tab. 2]
    return max_over_time(hidden_states)            # (n,)

def encode_cnn(word_vectors):
    # n filters of height h = 3, then ReLU  [§2.1.2] [tab. 2]
    windows = windows_of_height(word_vectors, 3)   # (T-2, 3, m)
    features = relu(convolve(windows))             # (T-2, n)
    # Max over positions  [§2.1.2]
    return max_over_time(features)                 # (n,)

# Sequential classifier  [§2.2] [fig. 2]
# Input:  s: short-text vectors (n,) of one dialog, indexed by utterance
#         i: index of the current utterance
#         d1, d2: history sizes
# Output: z_i: class probabilities (k,)

def classify(s, i, d1, d2):
    # Layer 1: class representation for each of the last d2+1 utterances
    # with the d1+1 short-text vectors ending at that utterance  [§2.2]
    for j in range(i - d2, i + 1):
        y[j] = tanh(
            sum(W[d] @ s[j - d] for d in range(d1 + 1)) + b1
        )                                          # (k,)
    # Layer 2: combine class representations, then softmax  [§2.2]
    logits = sum(U[j] @ y[i - j] for j in range(d2 + 1)) + b2
    return softmax(logits)                         # (k,)

Training. Minimise the negative log-likelihood of the correct dialog act for every utterance in the training set. Update all weights, biases and the word vectors with stochastic gradient descent, using the Adadelta update rule §3.2. Dropout is applied after the pooling layer. Early stopping uses the validation set, with patience of 10 epochs §3.2.

Hyperparameters

The paper varied one hyperparameter at a time, with the others fixed, to pick the table values §4 tab. 2.

Dataset statistics (copied from the paper) tab. 1:

Counts are dialogs, with utterances in parentheses. |C| is the number of classes and |V| the vocabulary size tab. 1. DSTC 4 and SwDA have only train and test splits as provided §3.1.

Results

Author-reported. Setup: three dialog act datasets, DSTC 4, MRDA and SwDA §3.1 tab. 1. The LSTM and CNN models are trained as in §3.2 tab. 2. Each accuracy is the test-set score of the run that scored best on the validation set tab. 4. Baselines are taken from other papers tab. 4.

Headline comparison tab. 4 (accuracy %):

The paper's caption notes that all five non-neural baselines but Naive Bayes use transcribed words and previously predicted dialog acts tab. 4. The interlabeler agreement row is a reference figure, not a method, and the paper gives it only for SwDA tab. 4.

Averages over five runs, with min and max, for each history setting tab. 3. Rows are d1, columns are d2. The best average per dataset and model is in bold in the source. Each cell is average (min, max):

The paper's conclusions from this grid §4 tab. 3:

• Sequential settings (d1 + d2 > 0) beat the non-sequential setting (0, 0) in the grid.
• The CNN is said to beat the LSTM on every dataset, by a small margin except on SwDA. The grid shows a tie on DSTC 4 (65.8 each at their best), and Table 4 reports LSTM ahead on DSTC 4 (66.2 vs 65.5). See Pitfalls.
• Raising d1 with d2 = 0 helps, and raising d2 with d1 = 0 helps less §4.
• Using history at both layers "does not help in most cases" §4.

Paper vs code

No official code. The paper's footnote links github.com/Franck-Dernoncourt/naacl2016 (by an author). It holds only a README with the train/validation/test splits for the three datasets. It has no model or training code, and no license is shown, so nothing from it is used here. Searched: the paper and its footnote (above); a GitHub repository search for the title ("sequential short-text classification") and for dialog act classification with the author name; and the author's GitHub repositories (about 17 listed). The two third-party matches for the title are reimplementations and were not used.

Pitfalls

• Validation split missing for two datasets. Early stopping uses a validation set §3.2, but DSTC 4 and SwDA are described as having only train and test splits §3.1. The paper does not say how a validation set was made for them. Reproduce with the author's split files or state your own choice.
• Headline numbers are single runs, grid numbers are averages. Table 4 reports the test score of the best-validation run tab. 4, while Table 3 reports averages over 5 runs tab. 3. The DSTC 4 LSTM headline (66.2) is higher than any average in the grid (max 65.8). Compare like with like.
• CNN vs LSTM claim. The grid caption says the CNN beats the LSTM on all datasets, but on DSTC 4 the averages are tied at 65.8, and Table 4 gives the LSTM the higher number (66.2 vs 65.5) tab. 3 tab. 4. Treat the claim as dataset-dependent.
• Stated gains do not match the grid cell by cell. The text gives 1.3 to 4.2 points for raising d1 with d2 = 0 §4. From the averages in Table 3, the gain from d1 = 0 to d1 = 2 at d2 = 0 is 1.3 (LSTM MRDA) to 4.4 (CNN SwDA), and the d1 = 1 gains are 0.4 to 2.9. Recompute from the table.
• Which (d1, d2) gives each headline number is not stated. The best setting may differ per dataset and per model. Choose it from validation data, not from the grid's test-set averages.
• Equation notation conflicts with the text. The second layer's text names U_0, U_{−1}, U_{−2} §2.2, but the equation writes W_{−j}. Implement a separate k×k matrix per lag, as the text says. The first layer is written with W_{−d} for d up to d1, so the text's three named matrices (W_0, W_{−1}, W_{−2}) only cover d1 ≤ 2, which is the grid range tab. 3.
• Context at the start of a dialog. For i − d1 − d2 < 0 the history does not exist. The paper does not say how it is filled (zeros, padding, or skipping the utterance). Also not stated: whether history can cross dialog boundaries.
• Sequence length handling. Not stated: maximum utterance length, truncation, and padding for the CNN or LSTM.
• Class representation uses the label space. Layer 1 maps each text vector to a k-dimensional vector before the second layer. The paper says history at the class level adds little and can propagate earlier mistakes §4. That explanation is the authors' hypothesis, not a tested result.
• Dropout placement. Dropout is applied after the pooling layer §3.2. The paper does not say whether dropout is also applied inside the LSTM or to the class representations.
• Table numbering in the source. The grid table sets \renewcommand\thetable{3} in the source. This card cites the comparison table as tab. 4 by LaTeX order. Check the printed number against the PDF.
• Cost not reported. Parameter counts, training time, and hardware are not stated. The history mechanism adds k×k and n×k weights per lag §2.2; the size of this overhead is not stated.
• Word-vector choice is per dataset. Different pretrained vectors per dataset §4 mean the results are not a clean comparison of the encoders alone.
• Comparisons are not controlled. The paper says text preprocessing and splits may differ across the baselines, and that many studies do not repeat runs §4. Only the authors' own rows have multi-run averages.

Lineage

• Builds on: the LSTM §2.1.1 (cites Hochreiter and Schmidhuber 1997) and the CNN text classifiers the introduction cites (Kim 2014 and others) §1. Neither has a card in this wiki.
• Compared against: SVM with rule features, naive Bayes, graphical models, HMMs, maximum entropy and memory-based learning, all listed in tab. 4 and §1.
• Superseded by: not stated in the paper, and no later work is cited here.