# Where the objective function of Skip-Gram Negative Sampling (SGNS) come from?

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

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).