level would differentiate between two classes, and in total the hierarchical softmax would take logarithmic time. [@Morin:2005]

We used a two-level hierarchy, because it is simple to implement, and it does not require a hierarchical clustering of the vocabulary. The first level performs a softmax between $\sqrt{N}$ word classes and the second level performs a softmax between $\sqrt{N}$ words inside the correct class:

$$\label{eq:hierarchical-softmax}
\begin{split}
&P(w_t \mid w_0 \ldots w_{t-1}) = \\
&P(c(w_t) \mid w_0 \ldots w_{t-1}) P(w_t \mid w_0 \ldots w_{t-1}, c(w_t))
\end{split}$$

This already reduces the time complexity of the output layer to the square root of the vocabulary size.

The clustering affects the performance of the resulting model, but it is not clear what kind of clustering is optimal for this kind of models. In earlier work, clusterings have been created from word frequencies [@Mikolov:2011:ICASSP], by clustering distributed word representations [@Mnih:2009], and using expert knowledge [@Morin:2005].

Ideally all class sizes would be equal, as the matrix product that produces the preactivations can be computed efficiently on a GPU when the weight matrix is dense. We use the same word classes in the hierarchical softmax layer that we use in class-based models, but we force equal class sizes; 