For the backpropagation, lets introduce the intermediate variable \(p\), which is a vector of the (normalized) probabilities. The loss for one example is: \[p_k = \frac{e^{f_k}}{ \sum_j e^{f_j} } \hspace{1in} L_i =-\log\left(p_{y_i}\right)\]
We now wish to understand how the computed scores inside \(f\) should change to decrease the loss \(L_i\) that this example contributes to the full objective. In other words, we want to derive the gradient \(\frac{\partial L_i}{\partial f_k}\). The loss \(L_i\) is computed from \(p\) which in turn depends on \(f\).
Notice how elegant and simple this expression is. Suppose the probabilities we computed were p = [0.2, 0.3, 0.5], and that the correct class was the middle one (with probability 0.3). According to this derivation the gradient on the scores would be df = [0.2, -0.7, 0.5].
defnaiveSoftmaxLossAndGradient( centerWordVec, outsideWordIdx, outsideVectors, dataset ): """ Naive Softmax loss & gradient function for word2vec models Implement the naive softmax loss and gradients between a center word's embedding and an outside word's embedding. This will be the building block for our word2vec models. Arguments: centerWordVec -- numpy ndarray, center word's embedding (v_c in the pdf handout) outsideWordIdx -- integer, the index of the outside word (o of u_o in the pdf handout) outsideVectors -- outside vectors (rows of matrix) for all words in vocab (U in the pdf handout) dataset -- needed for negative sampling, unused here. Return: loss -- naive softmax loss gradCenterVec -- the gradient with respect to the center word vector (dJ / dv_c in the pdf handout) gradOutsideVecs -- the gradient with respect to all the outside word vectors (dJ / dU) """
### YOUR CODE HERE
### Please use the provided softmax function (imported earlier in this file) ### This numerically stable implementation helps you avoid issues pertaining ### to integer overflow. # centerWordVec: (embedding_dim,1) # outsideVectors: (vocab_size,embedding_dim)
Now we shall consider the Negative Sampling loss, which is an alternative to the Naive Softmax loss. Assume that K negative samples (words) are drawn from the vocabulary. For simplicity of notation we shall refer to them as \(w_1,w_2,\cdots,w_k\) and their outside vectors as \(u_1,\cdots,u_k\). Note that \(o \in {w_1, \cdots, w_k}\). For a center word c and an outside word o, the negative sampling loss function is given by:
defnegSamplingLossAndGradient( centerWordVec, outsideWordIdx, outsideVectors, dataset, K=10 ): """ Negative sampling loss function for word2vec models Implement the negative sampling loss and gradients for a centerWordVec and a outsideWordIdx word vector as a building block for word2vec models. K is the number of negative samples to take. Note: The same word may be negatively sampled multiple times. For example if an outside word is sampled twice, you shall have to double count the gradient with respect to this word. Thrice if it was sampled three times, and so forth. Arguments/Return Specifications: same as naiveSoftmaxLossAndGradient """
# Negative sampling of words is done for you. Do not modify this if you # wish to match the autograder and receive points! negSampleWordIndices = getNegativeSamples(outsideWordIdx, dataset, K) indices = [outsideWordIdx] + negSampleWordIndices
### YOUR CODE HERE
### Please use your implementation of sigmoid in here. gradCenterVec = np.zeros(centerWordVec.shape) gradOutsideVecs = np.zeros(outsideVectors.shape) loss = 0.0
u_o = outsideVectors[outsideWordIdx] z = sigmoid(np.dot(u_o,centerWordVec)) loss -= np.log(z) gradCenterVec += u_o*(z-1) gradOutsideVecs[outsideWordIdx] = centerWordVec*(z-1)
for i inrange(K): neg_id = indices[i+1] u_k = outsideVectors[neg_id] z = sigmoid(-np.dot(u_k,centerWordVec)) loss -= np.log(z) gradCenterVec += u_k*(1-z) gradOutsideVecs[neg_id] += centerWordVec*(1-z) ### END YOUR CODE
return loss, gradCenterVec, gradOutsideVecs
SkipGram
Suppose the center word is \(c = w_t\) and the context window is \([w_{t-m},\cdots,w_{t-1},\cdots, w_{t}, \cdots, w_{t+1}, \cdots,w_{t+m} ]\), where m is the context window size. Recall that for the skip-gram version of word2vec, the total loss for the context window is:
defskipgram(currentCenterWord, windowSize, outsideWords, word2Ind, centerWordVectors, outsideVectors, dataset, word2vecLossAndGradient=naiveSoftmaxLossAndGradient): """ Skip-gram model in word2vec Implement the skip-gram model in this function. Arguments: currentCenterWord -- a string of the current center word windowSize -- integer, context window size outsideWords -- list of no more than 2*windowSize strings, the outside words word2Ind -- a dictionary that maps words to their indices in the word vector list centerWordVectors -- center word vectors (as rows) for all words in vocab (V in pdf handout) outsideVectors -- outside word vectors (as rows) for all words in vocab (U in pdf handout) word2vecLossAndGradient -- the loss and gradient function for a prediction vector given the outsideWordIdx word vectors, could be one of the two loss functions you implemented above. Return: loss -- the loss function value for the skip-gram model (J in the pdf handout) gradCenterVecs -- the gradient with respect to the center word vectors (dJ / dV in the pdf handout) gradOutsideVectors -- the gradient with respect to the outside word vectors (dJ / dU in the pdf handout) """
loss = 0.0 gradCenterVecs = np.zeros(centerWordVectors.shape) gradOutsideVectors = np.zeros(outsideVectors.shape)
### YOUR CODE HERE center_id = word2Ind[currentCenterWord] centerWordVec = centerWordVectors[center_id] for word in outsideWords: outside_id = word2Ind[word] loss_mini, gradCenter_mini, gradOutside_mini= \ word2vecLossAndGradient(centerWordVec=centerWordVec, outsideWordIdx=outside_id,outsideVectors=outsideVectors,dataset=dataset) loss += loss_mini # print(gradCenterVecs[center_id].shape, gradCenter_mini.shape) # exit() gradCenterVecs[center_id] += gradCenter_mini gradOutsideVectors += gradOutside_mini ### END YOUR CODE