#skip-gram

Question 1: Single choice

mediumAI-checkedText Representation & Embeddings

Skip-gram with a full softmax uses the gradient $\partial \log P(w_o \mid w_c)/\partial \mathbf{v}_c = \mathbf{u}_o - \sum_{j \in \mathcal{V}} P(w_j \mid w_c)\,\mathbf{u}_j$ . With vocabulary $\mathcal{V}$ and $d$ -dimensional vectors, what does one such gradient cost, and why is that a problem?

$O(|\mathcal{V}|\,d)$ : every word's vector enters the sum, which is slow for huge vocabularies1
$O(d)$ : only the vectors of the center word and the context word are involved2
$O(|\mathcal{V}|^2 d)$ : every pair of words in the vocabulary has to be compared with each other3
$O(d\log|\mathcal{V}|)$ : the softmax is evaluated along a path in a binary tree4

Timed test