word2vec.py

#!/usr/bin/env python

import numpy as np
import random

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


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
    assert np.ndim(x) < 2, "Can only handle scalar or 1-dimensional array"
    if np.ndim(x) == 0:
        # scalar
        s = 1./(1 + np.exp(-1*x))
    else:
        # s = np.array([1./(1+np.exp(-1*y)) for y in x])
        # https://stackoverflow.com/questions/42594695/how-to-apply-a-function-map-values-of-each-element-in-a-2d-numpy-array-matrix
        # ecerulm's answer suggests numpy exp is vectorized
        s = 1./(1+np.exp(-1*x))
    ### END YOUR CODE

    return s


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. 

    vocabSize = outsideVectors.shape[0]
    assert centerWordVec.shape[0] == outsideVectors.shape[1],\
        "mismatch of shapes: centerWordVec.shape: {} :: outsideVectors.shape: {}".format(centerWordVec.shape, outsideVectors.shape)

    """
    dimensionVector = outsideVectors.shape[1]  # Dimension of centerWordVec, each of the outsideVectors
    print("[Naive Softmax] vocabSize: {} :: dimensionVector: {}".format(vocabSize, dimensionVector))
    """

    # Create an array by computing dot product of v_c with each column of U.
    #  These are the components of the conditional probability.
    x_arr = outsideVectors.dot(centerWordVec)
    # Now compute the conditional probability of each of the words in the vocabulary as outside word given
    #   the center word vector v_c
    conditional_probability_arr = softmax(x=x_arr)
    # Compute the loss using the equation (2) in the assignment pdf
    loss = -1*np.log(conditional_probability_arr[outsideWordIdx])

    # Compute dJ / dv_c
    gradCenterVec = -1*outsideVectors[outsideWordIdx, :]

    """
    for i in range(vocabSize):
        gradCenterVec += conditional_probability_arr[i]*outsideVectors[i, :]
    """
    gradCenterVec += conditional_probability_arr.dot(outsideVectors)

    # Compute dJ / dU
    """
    gradOutsideVecs = np.zeros(outsideVectors.shape)

    for i in range(vocabSize):
        gradOutsideVecs[i, :] = conditional_probability_arr[i]*centerWordVec
    """
    gradOutsideVecs = np.outer(conditional_probability_arr, centerWordVec)

    gradOutsideVecs[outsideWordIdx, :] -= centerWordVec

    ### END YOUR CODE

    return loss, gradCenterVec, gradOutsideVecs


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


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  # KA - combines the two list into one list

    ### YOUR CODE HERE

    ### Please use your implementation of sigmoid in here.
    loss = -1*np.log(sigmoid(outsideVectors[outsideWordIdx, :].dot(centerWordVec)))
    """
    for k in negSampleWordIndices:
        loss -= np.log(sigmoid(-1*outsideVectors[k, :].dot(centerWordVec)))
    """
    loss -= np.sum(np.log(sigmoid(-1*outsideVectors[negSampleWordIndices, :].dot(centerWordVec))))

    # Compute dJ / dv_c
    gradCenterVec = -(1 - sigmoid(outsideVectors[outsideWordIdx, :].dot(centerWordVec))) * outsideVectors[outsideWordIdx, :]
    """
    for k in negSampleWordIndices:
        gradCenterVec += (1 - sigmoid(-1*outsideVectors[k, :].dot(centerWordVec))) * outsideVectors[k, :]
    """
    gradCenterVec += (1 - sigmoid(-1 * outsideVectors[negSampleWordIndices, :].dot(centerWordVec))).dot(outsideVectors[negSampleWordIndices, :])

    # Compute dJ / dU
    gradOutsideVecs = np.zeros(outsideVectors.shape)
    # 1st component: dJ / du_o
    gradOutsideVecs[outsideWordIdx, :] = -(1 - sigmoid(outsideVectors[outsideWordIdx, :].dot(centerWordVec))) * centerWordVec
    # 2nd component: sum over negative samples: dJ / du_k
    """
    for k in negSampleWordIndices:
        gradOutsideVecs[k, :] += (1 - sigmoid(-1 * outsideVectors[k, :].dot(centerWordVec))) * centerWordVec
    """
    countWordIndexDict = dict()
    for k in negSampleWordIndices:
        if k not in countWordIndexDict:
            countWordIndexDict[k] = 0
        countWordIndexDict[k] += 1

    # https://stackoverflow.com/questions/16819222/how-to-return-dictionary-keys-as-a-list-in-python
    # Jim Fasarakis Hilliard's answer
    # Note the difference between python 2 and python 3 for <dict>.keys()
    #   In python 2 its a list whereas in python 3 its dict_keys
    negSampleWordUniqueIndices = [*countWordIndexDict]
    negSampleWordCountVec = np.zeros(len(countWordIndexDict), dtype=int)
    for i in range(len(countWordIndexDict)):
        k = negSampleWordUniqueIndices[i]
        negSampleWordCountVec[i] = countWordIndexDict[k]

    gradOutsideVecs[negSampleWordUniqueIndices, :] = \
        np.outer(np.multiply((1 - sigmoid(-1 * outsideVectors[negSampleWordUniqueIndices, :].dot(centerWordVec))), negSampleWordCountVec), centerWordVec)

    ### END YOUR CODE

    return loss, gradCenterVec, gradOutsideVecs


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
    centerWordVec = centerWordVectors[word2Ind[currentCenterWord], :]
    # iterate over the context window
    for j in range(min(len(outsideWords), 2*windowSize)):
        # compute the loss and gradients for the current outside word
        cur_loss, cur_gradCenterVec, cur_gradOutsideVecs = word2vecLossAndGradient(centerWordVec=centerWordVec,
                                                                                   outsideWordIdx=word2Ind[outsideWords[j]],
                                                                                   outsideVectors=outsideVectors, dataset=dataset)

        loss += cur_loss
        gradCenterVecs[word2Ind[currentCenterWord], :] +=  cur_gradCenterVec
        gradOutsideVectors += cur_gradOutsideVecs

    ### END YOUR CODE

    return loss, gradCenterVecs, gradOutsideVectors

#############################################
# Testing functions below. DO NOT MODIFY!   #
#############################################

def word2vec_sgd_wrapper(word2vecModel, word2Ind, wordVectors, dataset, 
                         windowSize,
                         word2vecLossAndGradient=naiveSoftmaxLossAndGradient):
    batchsize = 50
    loss = 0.0
    grad = np.zeros(wordVectors.shape)
    N = wordVectors.shape[0]
    centerWordVectors = wordVectors[:int(N/2),:]
    outsideVectors = wordVectors[int(N/2):,:]
    for i in range(batchsize):
        windowSize1 = random.randint(1, windowSize)
        centerWord, context = dataset.getRandomContext(windowSize1)

        c, gin, gout = word2vecModel(
            centerWord, windowSize1, context, word2Ind, centerWordVectors,
            outsideVectors, dataset, word2vecLossAndGradient
        )
        loss += c / batchsize
        grad[:int(N/2), :] += gin / batchsize
        grad[int(N/2):, :] += gout / batchsize

    return loss, grad


def test_word2vec():
    """ Test the two word2vec implementations, before running on Stanford Sentiment Treebank """
    dataset = type('dummy', (), {})()
    def dummySampleTokenIdx():
        return random.randint(0, 4)

    def getRandomContext(C):
        tokens = ["a", "b", "c", "d", "e"]
        return tokens[random.randint(0,4)], \
            [tokens[random.randint(0,4)] for i in range(2*C)]
    dataset.sampleTokenIdx = dummySampleTokenIdx
    dataset.getRandomContext = getRandomContext

    random.seed(31415)
    np.random.seed(9265)
    dummy_vectors = normalizeRows(np.random.randn(10,3))
    dummy_tokens = dict([("a",0), ("b",1), ("c",2),("d",3),("e",4)])

    print("==== Gradient check for skip-gram with naiveSoftmaxLossAndGradient ====")
    gradcheck_naive(lambda vec: word2vec_sgd_wrapper(
        skipgram, dummy_tokens, vec, dataset, 5, naiveSoftmaxLossAndGradient),
        dummy_vectors, "naiveSoftmaxLossAndGradient Gradient")

    print("==== Gradient check for skip-gram with negSamplingLossAndGradient ====")
    gradcheck_naive(lambda vec: word2vec_sgd_wrapper(
        skipgram, dummy_tokens, vec, dataset, 5, negSamplingLossAndGradient),
        dummy_vectors, "negSamplingLossAndGradient Gradient")

    print("\n=== Results ===")
    print ("Skip-Gram with naiveSoftmaxLossAndGradient")

    print ("Your Result:")
    print("Loss: {}\nGradient wrt Center Vectors (dJ/dV):\n {}\nGradient wrt Outside Vectors (dJ/dU):\n {}\n".format(
            *skipgram("c", 3, ["a", "b", "e", "d", "b", "c"],
                dummy_tokens, dummy_vectors[:5,:], dummy_vectors[5:,:], dataset) 
        )
    )

    print ("Expected Result: Value should approximate these:")
    print("""Loss: 11.16610900153398
Gradient wrt Center Vectors (dJ/dV):
 [[ 0.          0.          0.        ]
 [ 0.          0.          0.        ]
 [-1.26947339 -1.36873189  2.45158957]
 [ 0.          0.          0.        ]
 [ 0.          0.          0.        ]]
Gradient wrt Outside Vectors (dJ/dU):
 [[-0.41045956  0.18834851  1.43272264]
 [ 0.38202831 -0.17530219 -1.33348241]
 [ 0.07009355 -0.03216399 -0.24466386]
 [ 0.09472154 -0.04346509 -0.33062865]
 [-0.13638384  0.06258276  0.47605228]]
    """)

    print ("Skip-Gram with negSamplingLossAndGradient")   
    print ("Your Result:")
    print("Loss: {}\nGradient wrt Center Vectors (dJ/dV):\n {}\n Gradient wrt Outside Vectors (dJ/dU):\n {}\n".format(
        *skipgram("c", 1, ["a", "b"], dummy_tokens, dummy_vectors[:5,:],
            dummy_vectors[5:,:], dataset, negSamplingLossAndGradient)
        )
    )
    print ("Expected Result: Value should approximate these:")
    print("""Loss: 16.15119285363322
Gradient wrt Center Vectors (dJ/dV):
 [[ 0.          0.          0.        ]
 [ 0.          0.          0.        ]
 [-4.54650789 -1.85942252  0.76397441]
 [ 0.          0.          0.        ]
 [ 0.          0.          0.        ]]
 Gradient wrt Outside Vectors (dJ/dU):
 [[-0.69148188  0.31730185  2.41364029]
 [-0.22716495  0.10423969  0.79292674]
 [-0.45528438  0.20891737  1.58918512]
 [-0.31602611  0.14501561  1.10309954]
 [-0.80620296  0.36994417  2.81407799]]
    """)

if __name__ == "__main__":
    test_word2vec()

"""
References:
    - https://docs.scipy.org/doc/numpy/reference/generated/numpy.isscalar.html
        - Suggests to use np.ndim(x) == 0 for scalar check.
"""