Does hierarchical softmax of skip gram and CBOW only update output vectors on the path from the root to the actual output word?

Question

After reading word2vec Parameter Learning Explained by Xin Rong, I understand that in the hierarchical softmax model, there is no output vector representation for words, instead, each of the $V-1$ inner units has an output vector $\mathbf{v}^{'}_{n(w,j)}$. They can be updated by the following equation: $$\mathbf{v}^{'(new)}_{j}=\mathbf{v}^{'(old)}_{j}-\eta(\sigma(\mathbf{v}^{'T}_{j}\mathbf{h})-t_j)\cdot \mathbf{h}, (1)$$ which should be applied to $j=1,2,...,L(w)-1$ and $t_j = 1$ means the ground truth is to follow the left child; $t_j = 0$ means it should follow the right child. While in plain CBOW, output vectors should be updated using: $$\mathbf{v}^{'(new)}_{w_j}=\mathbf{v}^{'(old)}_{w_j}-\eta \cdot e_j \cdot \mathbf{h},\mbox{for } j=1,2,...,V,\mbox{ }(2) $$ where $e_j=y_j-t_j$ So equation (2) is: $$\mathbf{v}^{'(new)}_{w_j}=\mathbf{v}^{'(old)}_{w_j}-\eta \cdot \left(\frac{\exp(\mathbf{v}^{'T}_{w_j}\mathbf{v}_{w_I})}{\sum^{V}_{j^{,}=1}\exp(\mathbf{v}^{'T}_{w_j}\mathbf{v}_{w_I})}-t_j\right) \cdot \mathbf{h},\mbox{for } j=1,2,...,V,\mbox{ }(3)$$ Does this mean when training a CBOW hierarchical softmax model, given a training sample which consists of several context words $w_{I,1},...,w_{I,C}$ and a center word $w_{O}$, we do not have to update $V$ output vectors for every word in the vocabulary, instead we only have to update $L(w)-1$ output vectors on the path from the root to $w_{O}$ and leave all other output vectors unchanged?

For a detailed CBOW example as in the picture below,

given a training sample whose center word (or actual output word) $w_{O}$ is $w_{2}$, we only have to update:

• $\mathbf{v}^{'}_{n(w_{2},1)}$ and $t_j$ in equation(1) is 1 .
• $\mathbf{v}^{'}_{n(w_{2},2)}$ and $t_j$ in equation(1) is 1 .
• $\mathbf{v}^{'}_{n(w_{2},3)}$ and $t_j$ in equation(1) is 0 .

and all other output vectors stay unchanged?

If we want to train a hierarchical softmax skip-gram model which has multiple context words as output words, in our detailed example, we have context words $w_{2}$ and $w_{3}$ as actual output context words and according to Xin Rong:

When used for the skip-gram model, we need to repeat this update procedure for each of the C words in the output context.

So this means we need to update:

• $\mathbf{v}^{'}_{n(w_{2},1)}$ and $t_j$ in equation(1) is 1 .
• $\mathbf{v}^{'}_{n(w_{2},2)}$ and $t_j$ in equation(1) is 1 .
• $\mathbf{v}^{'}_{n(w_{2},3)}$ and $t_j$ in equation(1) is 0 .
• $\mathbf{v}^{'}_{n(w_{3},1)}$ and $t_j$ in equation(1) is 1 . In fact, $\mathbf{v}^{'}_{n(w_{3},1)}$ and $\mathbf{v}^{'}_{n(w_{2},1)}$ are the same one vector. So we update the same output vector twice.
• $\mathbf{v}^{'}_{n(w_{3},2)}$ and $t_j$ in equation(1) is 0 . In fact, $\mathbf{v}^{'}_{n(w_{3},2)}$ and $\mathbf{v}^{'}_{n(w_{2},2)}$ are the same one vector. So we update the same output vector twice.

and all other output vectors stay unchanged.

If I understand it correctly, for a training sample, in plain CBOW or skip gram, we have to update $V$ output vectors while in hierarchical softmax we only have to update $log(V)$ output vectors, that's why we improved the computational efficiency.

However, Learning Word Embedding claims that hierarchical softmax only helps reduce the complexity of the denominator estimation in equation (3).It means hierarchical softmax also has to update $log(V)$ output vectors for every word in the vocabulary, only from equation (1), we can see hierarchical softmax does not have to calculate the sum of all dot products between the input word vector and all other output word vectors. So for a training sample, the plain CBOW has complexity $O(V*V)$ ( although I think we can compute the denominator once and store it somewhere. so we don't have to compute the denominator for very word in the vocabulary. The denominator are the same for all words. we only need $O(V)$ ) and hierarchical softmax $O(V\log(V))$.

Which claim is right? I am really confused! Any hint helps!

Answer 1

For the sake of simplicity consider the case of CBOW with one-word context (this corresponds to section 1.1 in Rong's paper).

Let us consider a single training sample and assess the time complexity of the updates.

For naive softmax, one must compute all the $u_j={{v'}_{w_j}}^Th$ for $j\in \{1,\ldots,V\}$, this has complexity $O(NV)$ where $N$ is the size of the embeddings. Once this is done, store $\sum_{j=1}^V \exp(u_j)$ and all the $\exp(u_j)$ in memory. Then each of the $y_j$ can be computed in $O(1)$ time, yielding a complexity of $O(NV)+VO(1)=O(NV)$.

For hierarchical softmax, one merely needs to compute the $\sigma({{v'}_{w_j}}^Th)$ where $j$ ranges in $\{1,\ldots,L(w_j)-1\}$. One property of the tree at hand is $L(w_j) = O(\log V)$, hence a complexity of $O(N\log V)$.