  As the vocabulary size of modern word-based language models becomes ever
larger, many sampling-based training criteria are proposed and investigated.
The essence of these sampling methods is that the softmax-related traversal
over the entire vocabulary can be simplified, giving speedups compared to the
baseline. A problem we notice about the current landscape of such sampling
methods is the lack of a systematic comparison and some myths about preferring
one over another. In this work, we consider Monte Carlo sampling, importance
sampling, a novel method we call compensated partial summation, and noise
contrastive estimation. Linking back to the three traditional criteria, namely
mean squared error, binary cross-entropy, and cross-entropy, we derive the
theoretical solutions to the training problems. Contrary to some common belief,
we show that all these sampling methods can perform equally well, as long as we
correct for the intended class posterior probabilities. Experimental results in
language modeling and automatic speech recognition on Switchboard and
LibriSpeech support our claim, with all sampling-based methods showing similar
perplexities and word error rates while giving the expected speedups.
