Distributed Representations of Words and Phrases and their Compositionality

2.1 Hierarchical Softmax

1. How does the hierarchical softmax work in Skip-gram?
   Words are leaves of a binary tree; each inner node has a vector \(v'_n\), and \(p(w \mid w_I)\) is the product, along the path from the root to \(w\), of \(\sigma(\pm v'^\top_n v_{w_I})\) for going left or right. It costs about \(\log_2 W\) instead of \(W\) per word, and the probabilities sum to 1.
   • Mikolov et al., 2013, Distributed Representations of Words and Phrases and their Compositionality (Advances in Neural Information Processing Systems 26 (NIPS 2013)), §2.1
2. Why did Mikolov et al. use a Huffman tree for the hierarchical softmax?
   It gives frequent words short codes (short paths), so training is fast. The tree’s structure considerably affects both speed and accuracy.
   • Mikolov et al., 2013, Distributed Representations of Words and Phrases and their Compositionality (Advances in Neural Information Processing Systems 26 (NIPS 2013)), §2.1