CS224n Assignment 2

import numpy as np
import random

from utils.gradcheck import gradcheck_naive
from utils.utils import normalizeRows, softmax

Helper functions

def sigmoid(x):
    """
    Compute the sigmoid function for the input here.
    Arguments:
    x -- A scalar or numpy array.
    Return:
    s -- sigmoid(x)
    """

    ### YOUR CODE HERE
    s = 1./(1. + np.exp(-x))
    ### END YOUR CODE

    return s

def getNegativeSamples(outsideWordIdx, dataset, K):
    """ Samples K indexes which are not the outsideWordIdx """

    negSampleWordIndices = [None] * K
    for k in range(K):
        newidx = dataset.sampleTokenIdx()
        while newidx == outsideWordIdx:
            newidx = dataset.sampleTokenIdx()
        negSampleWordIndices[k] = newidx
    return negSampleWordIndices

Naive Softmax Loss And Its Gradient

In word2vec, the conditional probability distribution is given by taking vector dot-products and applying the softmax function:

$P(o\|c) = \frac{exp^{u_o^{T}v_c}}{\sum_{w\in v}exp^{u_w^{T}v_c}}$

$u_o$ is the ‘outside’ vector representing outside word o
$v_c$ is the ‘center’ vector representing center word c

The Cross Entropy Loss between the true (discrete) probability distribution p and another distribution q is:

$-\sum_i p_i log(q_i)$

So that the naive-softmax loss for word2vec given in following equation is the same as the cross-entropy loss between $y$ and $\hat{y}$:

$-\sum_{w \in Vocab} y_w log(\hat{y}_w) = -log(\hat{y}_o)$

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

$\frac{\partial L_i }{ \partial f_k } = p_k - \mathbb{1}(y_i = k)$

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


def naiveSoftmaxLossAndGradient(
    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)

    scores = np.matmul(outsideVectors, centerWordVec)   # (vocab_size,1)
    # print(scores.shape)
    probs = softmax(scores)                          # (vocab_size,1)  y_hat

    loss = -np.log(probs[outsideWordIdx])

    dscores = probs.copy()   # (vocab_size,1)
    dscores[outsideWordIdx] = dscores[outsideWordIdx] - 1   #  y_hat minus y
    gradCenterVec = np.matmul(outsideVectors.T, dscores)  # (embedding_dim,1)

    # print(dscores.shape) # (5,)
    # print(centerWordVec.shape) # (3,)
    # exit()

    gradOutsideVecs = np.outer(dscores, centerWordVec) # (vocab_size,embedding_dim)

    ### END YOUR CODE

    return loss, gradCenterVec, gradOutsideVecs

Negative Sampling Loss And Its Gradient

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:

$J_{neg-sample}(v_c,o,U) = -log(\sigma(u_o^{T}v_c)) - \sum_{k=1}^{k}log(\sigma(-u_k^{T},v_c))$

The sigmoid function and its gradient is as follows:

$\sigma(x) = \frac{1}{1+e^{-x}} \\\\ \rightarrow \hspace{0.3in} \frac{d\sigma(x)}{dx} = \frac{e^{-x}}{(1+e^{-x})^2} = \left( \frac{1 + e^{-x} - 1}{1 + e^{-x}} \right) \left( \frac{1}{1+e^{-x}} \right) = \left( 1 - \sigma(x) \right) \sigma(x)$

def negSamplingLossAndGradient(
    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 in range(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:

$J_{skip-gram} (v_c,w_{t−m},\cdots,w_{t+m}, U) = \sum_{-m \leq j \leq m, j \neq 0} J(v_c,w_{t+j},U)$

Here, $J(v_c,w_{t+j},U)$ represents an arbitrary loss term for the center word $c = w_t$ and outside word

def skipgram(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

    return loss, gradCenterVecs, gradOutsideVectors