- Decomposing probabilities hierarchically, building nested categories of words in a tree-like structure over large vocabulary sets $\mathbb{V}$
- Instead of needing the amount of computations to be proportional $|\mathbb{V}|$, ( and to the number of hidden units $n_h$)
- In a balanced tree, the tree has a depth of $O(log|\mathbb{V}|)$
- The probability of choosing a word is equal to the product of the probabilities of choosing the branch leading to that word at every node on a path from the root of the tree to the leaf containing the word
- To predict the conditional probabilities that are needed for each node, often a logistic regression model is used, providing the same context $C$ as input. Since the correct output is encoded in the training set, you can use supervised learning to train the models, typically done using a cross-entropy loss corresponding to maximizing the log-likelihood of the correct sequence of decisions.
- Because the output log-likelihood can be efficiently computed, its gradients may also be efficiently computed (both with respect to the outer parameters as well as the hidden layer activations)
- It is often possible to optimize the tree structure to minimize the expected number of computations, however, it is usually not practical to do so, since the computation of outer probabilities is only one part of the total computation in the model.
- Instead of optimizing a tree with branching factor of 2, it is simpler to define a tree with a depth of 2 and a branching factor of $\sqrt{|\mathbb{V}|}$, i.e. defining a set of mutually exclusive word classes, capturing most of the benefit of the hierarchical strategy
- Question remains of how to best define the word classes, or the hierarchy in general. One could use discrete optimization to approximately optimize the partition of words
- Computing the probability of all $|\mathbb{V}|$ words will remain expensive, and the tree structure does not provide an exact solution to selecting the most likely word in a given context
- Produces computational benefits at both training time and test time, but tends to give worse results than sampling-based methods, potentially due to a poor choice of word classes.

Hierarchical Softmax

The key idea of noise constractive estimation is to learn the feature of data distribution by learning from a dichotomy problem of selecting the data points from the original dataset from a mixed dataset made up of noises and the original datasets.

Noise Contractive Estimation

Multiple approaches have been used to deal with the cost of high-dimensional output layers over large vocabulary sets, including:
- Use of a Short Vocabulary List
- Hierarchical Softmax
- Importance Sampling
- Ranking Loss
- Noise-Contrastive Estimation

University of Michigan - Ann Arbor

For natural language applications, we often want to use words as the fundamental unit of the output. However, because vocabularies can be very large (up to hundreds of thousands of words), this can be computationally expensive. Both the high memory cost and the high computational cost, which occur at training and testing time, make the standard way to approach this type of distribution have many difficulties.

High Dimensional Outputs

Goodfellow, I., Bengio, Y., & Courville, A. (2016). $\mathit{Deep \ Learning.}$ MIT Press. Retrieved from [www.deeplearningbook.org](https://www.deeplearningbook.org) 

Learn Before

Related

Learn After