Strategies for Training Large Vocabulary Neural Language Models

1 Introduction

• The study focuses on efficient handling of large output vocabularies rather than architecture or context representation, using a feed-forward neural model similar to Bengio et al. (2003).Source: §1 · p. 1
• Training slows as vocabulary grows because probability normalization and gradient computation become costlier, infrequent words require more data, and larger datasets often support higher-capacity models needing more iterations.Source: §1 · p. 1
• The paper compares softmax, hierarchical softmax, target sampling, noise contrastive estimation, self-normalization, and differentiated softmax, and extends self-normalization as a likelihood estimator.Differentiated softmax assigns more capacity to frequent words and is reported as faster and more accurate than softmax.Source: §1 · pp. 1–2
• The evaluation uses Penn Treebank, Gigaword, and Billion Word, benchmarks that differ in training-data amount and vocabulary size, under a one-week training budget.Source: §1 · p. 2
• On Billion Word, hierarchical softmax performs best, although it is less accurate than softmax on Penn Treebank; differentiated softmax trains better models within the time budget.The results illustrate that conclusions from small datasets do not always generalize to larger settings.Source: §1 · p. 2
• Neural models benefit less from more training data because their higher training complexity exceeds the time budget in some cases, while Kneser-Ney remains competitive on rare words.The rare-word finding runs counter to the common belief that neural models are better on infrequent words.Source: §1 · p. 2

2.1 Softmax Neural Language Model

• Classical softmax computes activations for every output word, making the vocabulary-sized output layer the dominant network cost and a GPU bottleneck at large dimensions.The paper focuses on algorithmic alternatives to sharding this computation across GPUs.Source: §2.1 · p. 3

2.2 Hierarchical Softmax

• A balanced hierarchical softmax tree reduces output scoring from O(V) to O(log V) by multiplying probabilities along each word’s path from root to leaf.The experiments also compare frequency-based, random, and embedding-based clustering strategies.Source: §2.2 · p. 3

2.3 Differentiated Softmax

• Differentiated softmax assigns different output-embedding dimensions by word-frequency partition, reducing output-layer complexity and providing speed-ups and accuracy gains in training and inference.Its partition-specific embeddings are paired with separate hidden-layer features; frequent words can receive more parameters than rare words.Source: §2.3 · pp. 3–4

2.4 Target Sampling

• Target sampling approximates softmax normalization with a subset of output classes, but changing the sampled weight matrix between mini-batches is computationally costly.The method includes positive examples in the mini-batch and uniformly samples a cross-validated subset of other words.Source: §2.4 · p. 4

2.5 Noise Contrastive Estimation

• Noise contrastive estimation trains a data-versus-noise classifier rather than directly maximizing training likelihood, and unnormalized scores can remove vocabulary-size dependence during training.The softmax normalization is reintroduced at test time to obtain a proper distribution.Source: §2.5 · pp. 4–5

2.6 Infrequent Normalization

• Infrequent normalization down-samples partition-function computations, and the paper extends it to a non-squared log-partition term that is an unbiased negative-log-likelihood estimator when α = 1.A smaller sampling rate computes the partition function on a smaller fraction of training data.Source: §2.6 · p. 5

2.7 Other Methods

• Locality-sensitive hashing can approximate the output dot product, but re-indexing embeddings adds training overhead and larger test batches erode its speed-ups.Source: §2.7 · p. 5

Datasets

• Penn Treebank uses 1 million tokens and a 10,000-word vocabulary, billionW has close to a billion tokens and about 800,000 words, and Gigaword has 5 billion tokens with a 100,000-word vocabulary.Gigaword uses a time-based split because it has no standard train/test split or vocabulary.Source: §3 · p. 5

Evaluation

• Performance is measured by test perplexity, with sentence-boundary context and end-of-sentence scoring for PTB and billionW but not for Gigaword.Gigaword contexts cross sentence boundaries, and its evaluation omits end-of-sentence markers.Source: §3 · pp. 5–6

Model and baseline

• The baseline is an unpruned 5-gram interpolated Kneser-Ney model; neural models use 6-grams on PTB and 11-grams on billionW and Gigaword, trained by SGD to maximize log-likelihood.The Kneser-Ney models are trained with KenLM.Source: §3 · p. 6

Validation

• Validation data selects model dimensions and method-specific settings, including clustering, distractor counts, noise/data ratios, and infrequent-normalization regularization.Learning rate and mini-batch size are also chosen to maximize validation accuracy.Source: §3 · p. 6

Training Time

• Training is limited to 24 hours for PTB and 168 hours for billionW and Gigaword; the best validation-perplexity model within each budget is evaluated on test data.The authors describe the time limit as a trade-off between exploring settings comprehensively and achieving accuracy.Source: §3 · p. 6

4.1 Softmax

• Hierarchical softmax processes the most training examples per time period, while D-Softmax scores nearly twice as many tokens per second at test time when all output words must be scored.In that all-word test-time scenario, D-Softmax's complexity is similar to softmax.Source: §4 · pp. 6–7, Table 3 · p. 7

4 Results

• Across benchmarks, softmax's competitiveness falls as vocabulary grows; hierarchical softmax shifts from poor on PTB to best on billionW, while D-Softmax performs very well across datasets.Table 2 reports test perplexity for individual models and their interpolations with Kneser-Ney.Source: §4 · p. 6, Table 2 · p. 7, §4.3 · p. 8

4.2 Target Sampling

• More than 30% distractors gives the best Gigaword target-sampling accuracy, while 50% is the best billionW setting; overall, target sampling is not much better than softmax.The authors suggest independently sampled distractors may miss words the model considers likely in context.Source: §4.2 · pp. 7–8, Figure 5 · p. 8

4.3 Hierarchical Softmax

• K-means clustering performs best among the tested strategies, while informative context-similar clusters help learning and random clustering performs worst.The comparison covers four clustering strategies on billionW and Gigaword.Source: §4.3 · p. 8, Table 4 · p. 8

4.4 Differentiated Softmax

• D-Softmax is best on Gigaword, second on billionW after HSM, and among PTB's indistinguishable best; its low-dimensional rare-word representations speed test-time scoring but hurt rare-word accuracy.The variable-capacity scheme gives frequent words larger embeddings and rare words smaller ones.Source: §4.4 · p. 8

4.5 Noise Contrastive Estimation

• NCE required decoupling noise-sample count from the data/noise ratio; it beats softmax only on billionW and is not among the best methods for minimizing perplexity.Similar NCE losses can correspond to very different validation entropies.Source: §4.5 · pp. 8–9

4.6 Infrequent Normalization

• Weaknorm variants beat softmax on billionW and match it on PTB and Gigaword; WeaknormSQ evaluates the partition on 10% of examples but still requires post-training normalization.WeaknormSQ is sensitive to regularization strength; the non-squared Weaknorm with strength 1 gives an unbiased estimator of data likelihood.Source: §4.6 · p. 9

5.1 Model Capacity

• 512 hidden units yielded the best validation performance within the allocated time, while D-Softmax captured most of the benefit of a larger softmax model.A longer training horizon could let a 1024-unit softmax model perform better; D-Softmax allocates more capacity to frequent words at the expense of rarer words.Source: §5.1 · p. 9

5.2 Effect of Initialization

• PCA initialization of both input and output representations outperformed random initialization, and initial conditions still affected validation perplexity after a week.For hierarchical softmax, random initialization of the output matrix could reach performance comparable to PCA initialization after a week.Source: §5.2 · p. 10

5.3 Training Set Size

• 96 perplexity came from adapting a Billion Word softmax model to Penn Treebank, while Gigaword softmax improved little with more than 500M tokens in one week.The authors say benefiting from the full Gigaword training set would require a higher training budget, faster hardware, or parallelization.Source: §5.3 · pp. 10–11, Figure 9 · p. 10

5.4 Rare Words

• Kneser-Ney was competitive on rare words while neural models were on par or better on frequent words; hierarchical softmax was best among neural strategies on rare words.D-Softmax excelled on frequent words but performed poorly on rare ones; hierarchical softmax was fast and made more updates, observing rare-word occurrences several times.Source: §5.4 · p. 11, Table 5 · p. 11

• The paper presents a comprehensive analysis of strategies for training large-vocabulary neural language models, where computing the partition function over the full vocabulary is a challenge.Source: §6 · p. 11
• The paper extends self-normalization to estimate likelihood properly and introduces differentiated softmax, which reduces computation by assigning less capacity to rare words.Source: §6 · p. 11
• Differentiated softmax and hierarchical softmax were the best strategies for large vocabularies, while target sampling and noise contrastive estimation did not outperform softmax in this setting.Source: §6 · p. 11
• Neural models were better at modeling frequent words but less effective for rare words than Kneser-Ney, and combining the two was very effective.Source: §6 · p. 11
• The authors identify training with combined normalized and unnormalized objectives, parallel training, and better rare-word modeling as promising directions for further work.Source: §6 · p. 11