Training with a large number of classes

In machine learning we often face the issue of a very large number of classes in a classification problem. This causes a bottleneck in the computation. There's though a simple and effective way to deal with this. In areas like Natural Language Processing (NLP) a common task is to predict the next word in sequence (like in preditictive text on a smartphon or in learning word embeddings). For example, $u_\theta(c,x) \exp(w_c'x)$, where $w_c$ is a parameter vector for class $c$ and $x$ is the vector input.