A Neural Probabilistic Language Model

Modelling the joint distribution of many discrete variables needs huge numbers of parameters: 10 consecutive words over a 100,000-word vocabulary have potentially \(100000^{10} - 1 = 10^{50} - 1\) free parameters. Test word sequences are likely to differ from all training sequences, and discrete spaces offer no obvious smoothness to generalize with.

By “gluing” very short overlapping pieces of length 1, 2, … up to \(n\) seen in training: backing off or interpolating to shorter contexts when a combination is unseen (Katz 1987; Jelinek and Mercer 1980).

They ignore context beyond 1 or 2 words, and they ignore similarity between words: having seen “The cat is walking in the bedroom” should make “A dog was running in a room” almost as likely, since dog/cat, the/a, room/bedroom play similar roles.

(1) Associate each vocabulary word with a distributed, real-valued feature vector in \(\mathbb{R}^m\); (2) express the joint probability of word sequences in terms of these vectors; (3) learn the word vectors and the probability function’s parameters simultaneously.

Similar words get similar feature vectors, and the probability function is smooth in those features, so a small change in features changes probabilities only slightly. Each training sentence thus raises the probability of a combinatorial number of “neighbouring” sentences.

Class-based models (e.g. Brown et al. 1992) assign each word a discrete class, a hard or soft partition of the vocabulary. The neural model represents similarity with a continuous learned feature vector per word, so words can be similar along many dimensions.

LSI learns vectors from co-occurrence in documents; here the vectors are learned to represent the distribution of word sequences compactly, jointly with the model. Fixed vectors from principal components of co-occurrence counts did not work well; joint learning did.

Into a mapping \(C\) from each word \(i\) to a feature vector \(C(i) \in \mathbb{R}^m\) (a \(|V| \times m\) matrix of free parameters, shared across all context positions), and a function \(g\) mapping the context’s feature vectors to a distribution over the next word: \(f(i, w_{t-1}, \ldots, w_{t-n+1}) = g(i, C(w_{t-1}), \ldots, C(w_{t-n+1}))\).

Concatenate the context word vectors \(x = (C(w_{t-1}), \ldots, C(w_{t-n+1}))\); compute \(y = b + Wx + U \tanh(d + Hx)\), where \(W\) are optional direct connections (or zero); then \(\hat P(w_t \mid \ldots) = e^{y_{w_t}} / \sum_i e^{y_i}\) (softmax).

\(\theta = (b, d, W, U, H, C)\), dominated by \(|V|(nm + h)\): linear in vocabulary size and in the order \(n\), not exponential as for n-gram tables. More sharing (time-delay or recurrent networks) could make it sublinear in \(n\).

By stochastic gradient ascent on the penalized log-likelihood \(L = \frac{1}{T} \sum_t \log f(w_t, \ldots, w_{t-n+1}; \theta) + R(\theta)\), with weight decay on weights and \(C\) but not biases. Only the feature vectors of words in the current input window need updating after each example.

Mixing the probability predictions (fixed weight 0.5, a learned weight, or weights conditioned on context frequency) always reduced perplexity, suggesting the two models make their errors (low probability on the observed word) in different places.

An n-gram probability is a normalized relative frequency looked up directly, but the neural model must compute the output activations for every word in the vocabulary to normalize the softmax; the output layer is the main bottleneck.

Locking parameter writes left processors mostly waiting, so they let processors write asynchronously; occasionally an update is overwritten, adding a little noise that didn’t visibly slow training.

Across the output units, where almost all computation happens (about 99.7% for the AP News network): each CPU computes and updates a block of outputs, duplicating the cheap input and hidden computations. CPUs share only the softmax normalizer and gradients on the hidden and feature layers, via MPI Allreduce; communication was 1/15 of total time.

Each CPU finds the maximum \(q_i\) of its \(y_j\); an extra Allreduce shares the overall maximum \(Q\), and \(p_j = e^{y_j - Q}\) is computed, so no exponential overflows and at least one \(p_j\) is non-zero; then the sum of \(p_j\) is shared to normalize.

The Brown corpus (about 1.18M words: 800k train, 200k validation, 181k test; words with frequency ≤ 3 merged, \(|V| = 16{,}383\)) and AP News 1995–96 (about 14M training words, \(|V| = 17{,}964\) after lowercasing and mapping rare words, numbers and proper nouns to special symbols).

A deleted-interpolation trigram with mixture weights conditioned on context frequency bins (trained by EM on validation data), modified Kneser-Ney back-off n-grams, and class-based n-grams, with order and number of classes chosen on validation data.

On Brown: best MLP (mixed with the trigram) 252 vs 312 for the best n-gram (class-based, 500 classes), about 24% better, and 33% better than the interpolated trigram (336). On AP News: 109 vs 117 for the best Kneser-Ney model, about 8%.

The network benefited from more context (4 instead of 2 context words helped it, not the n-grams); hidden units helped; mixing with the trigram always helped. Without direct connections training took twice as long (20 vs 10 epochs) but generalized slightly better, perhaps as a tighter bottleneck.

The output word also gets a feature vector: the network reads \(x = (C(w_t), C(w_{t-1}), \ldots, C(w_{t-n+1}))\) and outputs an energy \(E = v \cdot \tanh(d + Hx) + \sum_{i=0}^{n-1} b_{w_{t-i}}\), low for likely sequences; normalizing \(e^{-E}\) over \(w_t\) gives the conditional probability. Hidden units act like products-of-experts experts.

Initialize a new word’s feature vector as the probability-weighted average of the vectors of words that could occur in the context, \(C(j) \leftarrow \sum_{i \in V} C(i)\, \hat P(i \mid w_{t-n+1}^{t-1})\), then add it to the vocabulary and renormalize.

Tree-structured (hierarchical) output to cut computation by a factor of about \(|V|/\log|V|\); computing gradients for only a subset of output words (e.g. importance sampling); recurrent networks for longer context; and multiple vectors per word for polysemy.

Each training sentence informs the model about a combinatorial number of other sentences through learned distributed representations. Compact, smooth representations replace tables of conditional probabilities, and computation and memory scale linearly, not exponentially, with the number of conditioning variables.