0
$\begingroup$

In the paper of "Neural Word Embedding as Implicit Matrix Factorization", there is an objective function for Skip-Gram Negative Sampling. I wanted to know where this formula come from

enter image description here

$\endgroup$
1

1 Answer 1

1
$\begingroup$

The original w2v paper [1] shows the loss function for each pair of target and context words $(w, c)$. The model is a binary classifier that learns to classify "positive samples" from "negative samples". Each observed $(w,c)$ pair is a positive sample. For each of those, $k$ random context words $c_N$ are sampled from a distribution $P_D(c)$ (e.g. uniformly), giving $k$ negative sample pairs $(w,c_N)$. Overall, the model learns to differentiate context words that $w$ co-occurs with from those it doesn't.

The model has one vector (or word embedding) $\overrightarrow{w}$ for each target word $w$ and another $\overrightarrow{c}$ for each context word $c$. Any given word, e.g. "cat", will at various times be considered a target word and at others a context word, and so have 2 embeddings.

The model predicts a word pair $w$, $c$ as being a positive sample by Prob$[(w,c)$ +ve$]=\sigma(\overrightarrow{w}\!\cdot\!\overrightarrow{c})$, i.e. the dot product of their embeddings in a sigmoid function. By implication, the probability that $w$, $c$ are a negative sample is $\ 1\!-\! \sigma(\overrightarrow{w}\cdot\overrightarrow{c}) = \sigma(-\overrightarrow{w}\cdot\overrightarrow{c})$.

The loss function is maximised for all positive and negative samples as in standard logistic regression. $\#(w,c)$ is the number of times the word pair $(w,c)$ occurs. For each occurrence $\sigma(\overrightarrow{w}\cdot\overrightarrow{c})$ is maximised (towards 1). For each of the corresponding negative samples $(w, c_N)$, $\sigma(-\overrightarrow{w}\cdot\overrightarrow{c_N})$ is maximised, or equivalently $\sigma(\overrightarrow{w}\cdot\overrightarrow{c_N})$ is minimised (towards 0). $k$ appears since there are $k$ negative samples drawn for each positive sample. The expectation $\mathbb{E}_{c_N\sim P_N}[...]$ appears because each negative sample is drawn from $P_N$. The expectation can instead be written as a weighted sum over all possible context words (as Levy & Goldberg do in their paper).

[1] Mikolov, T., Sutskever, I., Chen, K., Corrado, G., and Dean, J. (2013). Distributed Representations of Words and Phrases and their Compositionality. In Advances in Neural Information Processing Systems.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.