#!/usr/bin/env python
# reference:
#           1. word2vec Parameter Learning Explained (https://arxiv.org/pdf/1411.2738.pdf)
#           2. word2vec Explained: Deriving Mikolov et al.s Negative-Sampling Word-Embedding Method
#               (https://arxiv.org/pdf/1402.3722.pdf)

import numpy as np
import random

from q1_softmax import softmax
from q2_gradcheck import gradcheck_naive
from q2_sigmoid import sigmoid, sigmoid_grad

def normalizeRows(x):
    """ Row normalization function

    Implement a function that normalizes each row of a matrix to have
    unit length.
    """

    ### YOUR CODE HERE
    # using l2 norm to normalize
    x = x / np.sqrt(np.sum(x * x, axis=-1, keepdims=True))
    ### END YOUR CODE

    return x


def test_normalize_rows():
    print("Testing normalizeRows...")
    x = normalizeRows(np.array([[3.0,4.0],[1, 2]]))
    print(x)
    ans = np.array([[0.6,0.8],[0.4472136,0.89442719]])
    assert np.allclose(x, ans, rtol=1e-05, atol=1e-06)
    print("")


def softmaxCostAndGradient(predicted, target, outputVectors, dataset):
    """ Softmax cost function for word2vec models

    Implement the cost and gradients for one predicted word vector
    and one target word vector as a building block for word2vec
    models, assuming the softmax prediction function and cross
    entropy loss.

    Arguments:
    predicted -- numpy ndarray, predicted word vector (\hat{v} in
                 the written component)
    target -- integer, the index of the target word
    outputVectors -- "output" vectors (as rows) for all tokens
    dataset -- needed for negative sampling, unused here.

    Return:
    cost -- cross entropy cost for the softmax word prediction
    gradPred -- the gradient with respect to the predicted word
           vector
    grad -- the gradient with respect to all the other word
           vectors

    We will not provide starter code for this function, but feel
    free to reference the code you previously wrote for this
    assignment!
    """

    ### YOUR CODE HERE
    scores = outputVectors.dot(predicted.T) # shape = (V, 1)
    y_hat = softmax(scores)
    cost = -scores[target] + np.log(np.sum(np.exp(scores)))
    one_hot_target = np.zeros_like(y_hat)
    one_hot_target[target] = 1
    grad = np.outer((y_hat - one_hot_target), predicted)
    gradPred = outputVectors.T.dot(y_hat - one_hot_target)
    
    '''
    final_predicted = predicted.dot(outputVectors.T)
    probability = softmax(final_predicted)
    cost = -np.log(probability[target])
    
    one_hot_target = np.zeros_like(probability)
    one_hot_target[target] += 1
    dlogits = probability - one_hot_target
    grad = np.outer(predicted, dlogits).T
    gradPred = outputVectors.T.dot(dlogits)
    '''
    ### END YOUR CODE

    return cost, gradPred, grad


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

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


def negSamplingCostAndGradient(predicted, target, outputVectors, dataset,
                               K=10):
    """ Negative sampling cost function for word2vec models

    Implement the cost and gradients for one predicted word vector
    and one target word vector as a building block for word2vec
    models, using the negative sampling technique. K is the sample
    size.

    Note: See test_word2vec below for dataset's initialization.

    Arguments/Return Specifications: same as softmaxCostAndGradient
    """

    # Sampling of indices is done for you. Do not modify this if you
    # wish to match the autograder and receive points!
    indices = [target]
    indices.extend(getNegativeSamples(target, dataset, K))

    ### YOUR CODE HERE
    grad = np.zeros_like(outputVectors)
    gradPred = np.zeros_like(predicted)
    cost = 0.0
    probability = 0.0
    for sample_idx in indices:
        similarity = outputVectors[sample_idx].dot(predicted.T)
        probability = sigmoid(similarity) # squash to 0 ~ 1
        if sample_idx == target: # positive sample
            #p = sigmoid(outputVectors[sample_idx].dot(predicted.T))
            cost += -np.log(sigmoid(similarity))
        else: # negative sample
            #p = sigmoid(-outputVectors[sample_idx].dot(predicted.T))
            cost += -np.log(sigmoid(-similarity)) # deduction from reference 2.
        
        if sample_idx == target:
            grad[sample_idx, :] += (probability - 1) * predicted
            gradPred += (probability - 1) * outputVectors[sample_idx]
        else:
            grad[sample_idx, :] += probability * predicted
            gradPred += probability * outputVectors[sample_idx]
    '''
    V, D = outputVectors.shape
    one_hot_target = np.zeros(V)
    one_hot_target[target] = 1
    cost = 0
    gradPred = np.zeros_like(predicted)
    grad = np.zeros_like(outputVectors)
    
    for idx in indices:
        context_vector = outputVectors[idx] # embedding vector (1, D)
        cosine_similarity = normalizeRows(predicted).dot(normalizeRows(context_vector).T)
        print('neg sample, consine_similarity={0}'.format(cosine_similarity))
        binary_class = sigmoid(cosine_similarity)
        print('neg sample, binary_class={0}'.format(binary_class))
        
        if idx == target:
            cost += binary_class - 1
        else:
            cost += binary_class
          
        dlogits = sigmoid_grad(cosine_similarity)
        #gradPred += dlogits * normalizeRows(context_vector)
        #grad += np.outer(one_hot_target, dlogits * normalizeRows(predicted))
        gradPred += dlogits
        grad += np.outer(one_hot_target, dlogits)
    '''
    ### END YOUR CODE

    return cost, gradPred, grad


def skipgram(currentWord, C, contextWords, tokens, inputVectors, outputVectors,
             dataset, word2vecCostAndGradient=softmaxCostAndGradient):
    """ Skip-gram model in word2vec

    Implement the skip-gram model in this function.

    Arguments:
    currentWord -- a string of the current center word
    C -- integer, context size
    contextWords -- list of no more than 2*C strings, the context words
    tokens -- a dictionary that maps words to their indices in
              the word vector list
    inputVectors -- "input" word vectors (as rows) for all tokens
    outputVectors -- "output" word vectors (as rows) for all tokens
    word2vecCostAndGradient -- the cost and gradient function for
                               a prediction vector given the target
                               word vectors, could be one of the two
                               cost functions you implemented above.

    Return:
    cost -- the cost function value for the skip-gram model
    grad -- the gradient with respect to the word vectors
    """
    
    cost = 0.0
    gradIn = np.zeros(inputVectors.shape)
    gradOut = np.zeros(outputVectors.shape)

    ### YOUR CODE HERE
    predicted = inputVectors[tokens[currentWord]]
    for cw in contextWords:
        per_cost, per_gradIn, per_gradOut = word2vecCostAndGradient(predicted, tokens[cw], outputVectors, dataset)
        cost += per_cost
        gradIn[tokens[currentWord]] += per_gradIn
        gradOut += per_gradOut
    '''
    predicted = inputVectors[tokens[currentWord]] # embedding vector
    one_hot_current = np.zeros(inputVectors.shape[0])
    one_hot_current[tokens[currentWord]] += 1
    for i in range(len(contextWords)):
        per_cost, gradPred, grad = word2vecCostAndGradient(predicted, tokens[contextWords[i]], outputVectors, dataset)
        cost += per_cost
        gradIn += np.outer(one_hot_current, gradPred)
        gradOut += grad
    '''
    ### END YOUR CODE

    return cost, gradIn, gradOut


def cbow(currentWord, C, contextWords, tokens, inputVectors, outputVectors,
         dataset, word2vecCostAndGradient=softmaxCostAndGradient):
    """CBOW model in word2vec

    Implement the continuous bag-of-words model in this function.

    Arguments/Return specifications: same as the skip-gram model

    Extra credit: Implementing CBOW is optional, but the gradient
    derivations are not. If you decide not to implement CBOW, remove
    the NotImplementedError.
    """

    cost = 0.0
    gradIn = np.zeros(inputVectors.shape)
    gradOut = np.zeros(outputVectors.shape)

    ### YOUR CODE HERE
    predicted = np.zeros(inputVectors.shape[1])
    for cw in contextWords:
        predicted += inputVectors[tokens[cw]]
    predicted /= C
    
    cost, sum_gradIn, gradOut = word2vecCostAndGradient(predicted, tokens[currentWord], outputVectors, dataset)
    # distribute sum_gradIn to each of context words
    for cw in contextWords: 
        gradIn[tokens[cw]] += sum_gradIn / C
    ### END YOUR CODE
    return cost, gradIn, gradOut


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

def word2vec_sgd_wrapper(word2vecModel, tokens, wordVectors, dataset, C,
                         word2vecCostAndGradient=softmaxCostAndGradient):
    batchsize = 50
    cost = 0.0
    grad = np.zeros(wordVectors.shape)
    N = wordVectors.shape[0]
    inputVectors = wordVectors[:N/2,:]
    outputVectors = wordVectors[N/2:,:]
    for i in range(batchsize):
        C1 = random.randint(1,C)
        centerword, context = dataset.getRandomContext(C1)

        if word2vecModel == skipgram:
            denom = 1
        else:
            denom = 1

        c, gin, gout = word2vecModel(
            centerword, C1, context, tokens, inputVectors, outputVectors,
            dataset, word2vecCostAndGradient)
        cost += c / batchsize / denom
        grad[:N//2, :] += gin / batchsize / denom
        grad[N//2:, :] += gout / batchsize / denom

    return cost, grad


def test_word2vec():
    """ Interface to the dataset for negative sampling """
    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 ====")
    gradcheck_naive(lambda vec: word2vec_sgd_wrapper(
        skipgram, dummy_tokens, vec, dataset, 5, softmaxCostAndGradient),
        dummy_vectors)
    gradcheck_naive(lambda vec: word2vec_sgd_wrapper(
        skipgram, dummy_tokens, vec, dataset, 5, negSamplingCostAndGradient),
        dummy_vectors)
    print("\n==== Gradient check for CBOW      ====")
    gradcheck_naive(lambda vec: word2vec_sgd_wrapper(
        cbow, dummy_tokens, vec, dataset, 5, softmaxCostAndGradient),
        dummy_vectors)
    gradcheck_naive(lambda vec: word2vec_sgd_wrapper(
        cbow, dummy_tokens, vec, dataset, 5, negSamplingCostAndGradient),
        dummy_vectors)

    print("\n=== Results ===")
    print(skipgram("c", 3, ["a", "b", "e", "d", "b", "c"],
        dummy_tokens, dummy_vectors[:5,:], dummy_vectors[5:,:], dataset))
    print(skipgram("c", 1, ["a", "b"],
        dummy_tokens, dummy_vectors[:5,:], dummy_vectors[5:,:], dataset,
        negSamplingCostAndGradient))
    print(cbow("a", 2, ["a", "b", "c", "a"],
        dummy_tokens, dummy_vectors[:5,:], dummy_vectors[5:,:], dataset))
    print(cbow("a", 2, ["a", "b", "a", "c"],
        dummy_tokens, dummy_vectors[:5,:], dummy_vectors[5:,:], dataset,
        negSamplingCostAndGradient))


if __name__ == "__main__":
    test_normalize_rows()
    test_word2vec()

23cba97bdcce12f3a866266927c342a4888dee76
<mask token>


def normalizeRows(x):
    """ Row normalization function

    Implement a function that normalizes each row of a matrix to have
    unit length.
    """
    x = x / np.sqrt(np.sum(x * x, axis=-1, keepdims=True))
    return x


def test_normalize_rows():
    print('Testing normalizeRows...')
    x = normalizeRows(np.array([[3.0, 4.0], [1, 2]]))
    print(x)
    ans = np.array([[0.6, 0.8], [0.4472136, 0.89442719]])
    assert np.allclose(x, ans, rtol=1e-05, atol=1e-06)
    print('')


<mask token>


def getNegativeSamples(target, dataset, K):
    """ Samples K indexes which are not the target """
    indices = [None] * K
    for k in range(K):
        newidx = dataset.sampleTokenIdx()
        while newidx == target:
            newidx = dataset.sampleTokenIdx()
        indices[k] = newidx
    return indices


def negSamplingCostAndGradient(predicted, target, outputVectors, dataset, K=10
    ):
    """ Negative sampling cost function for word2vec models

    Implement the cost and gradients for one predicted word vector
    and one target word vector as a building block for word2vec
    models, using the negative sampling technique. K is the sample
    size.

    Note: See test_word2vec below for dataset's initialization.

    Arguments/Return Specifications: same as softmaxCostAndGradient
    """
    indices = [target]
    indices.extend(getNegativeSamples(target, dataset, K))
    grad = np.zeros_like(outputVectors)
    gradPred = np.zeros_like(predicted)
    cost = 0.0
    probability = 0.0
    for sample_idx in indices:
        similarity = outputVectors[sample_idx].dot(predicted.T)
        probability = sigmoid(similarity)
        if sample_idx == target:
            cost += -np.log(sigmoid(similarity))
        else:
            cost += -np.log(sigmoid(-similarity))
        if sample_idx == target:
            grad[sample_idx, :] += (probability - 1) * predicted
            gradPred += (probability - 1) * outputVectors[sample_idx]
        else:
            grad[sample_idx, :] += probability * predicted
            gradPred += probability * outputVectors[sample_idx]
    """
    V, D = outputVectors.shape
    one_hot_target = np.zeros(V)
    one_hot_target[target] = 1
    cost = 0
    gradPred = np.zeros_like(predicted)
    grad = np.zeros_like(outputVectors)
    
    for idx in indices:
        context_vector = outputVectors[idx] # embedding vector (1, D)
        cosine_similarity = normalizeRows(predicted).dot(normalizeRows(context_vector).T)
        print('neg sample, consine_similarity={0}'.format(cosine_similarity))
        binary_class = sigmoid(cosine_similarity)
        print('neg sample, binary_class={0}'.format(binary_class))
        
        if idx == target:
            cost += binary_class - 1
        else:
            cost += binary_class
          
        dlogits = sigmoid_grad(cosine_similarity)
        #gradPred += dlogits * normalizeRows(context_vector)
        #grad += np.outer(one_hot_target, dlogits * normalizeRows(predicted))
        gradPred += dlogits
        grad += np.outer(one_hot_target, dlogits)
    """
    return cost, gradPred, grad


def skipgram(currentWord, C, contextWords, tokens, inputVectors,
    outputVectors, dataset, word2vecCostAndGradient=softmaxCostAndGradient):
    """ Skip-gram model in word2vec

    Implement the skip-gram model in this function.

    Arguments:
    currentWord -- a string of the current center word
    C -- integer, context size
    contextWords -- list of no more than 2*C strings, the context words
    tokens -- a dictionary that maps words to their indices in
              the word vector list
    inputVectors -- "input" word vectors (as rows) for all tokens
    outputVectors -- "output" word vectors (as rows) for all tokens
    word2vecCostAndGradient -- the cost and gradient function for
                               a prediction vector given the target
                               word vectors, could be one of the two
                               cost functions you implemented above.

    Return:
    cost -- the cost function value for the skip-gram model
    grad -- the gradient with respect to the word vectors
    """
    cost = 0.0
    gradIn = np.zeros(inputVectors.shape)
    gradOut = np.zeros(outputVectors.shape)
    predicted = inputVectors[tokens[currentWord]]
    for cw in contextWords:
        per_cost, per_gradIn, per_gradOut = word2vecCostAndGradient(predicted,
            tokens[cw], outputVectors, dataset)
        cost += per_cost
        gradIn[tokens[currentWord]] += per_gradIn
        gradOut += per_gradOut
    """
    predicted = inputVectors[tokens[currentWord]] # embedding vector
    one_hot_current = np.zeros(inputVectors.shape[0])
    one_hot_current[tokens[currentWord]] += 1
    for i in range(len(contextWords)):
        per_cost, gradPred, grad = word2vecCostAndGradient(predicted, tokens[contextWords[i]], outputVectors, dataset)
        cost += per_cost
        gradIn += np.outer(one_hot_current, gradPred)
        gradOut += grad
    """
    return cost, gradIn, gradOut


<mask token>


def word2vec_sgd_wrapper(word2vecModel, tokens, wordVectors, dataset, C,
    word2vecCostAndGradient=softmaxCostAndGradient):
    batchsize = 50
    cost = 0.0
    grad = np.zeros(wordVectors.shape)
    N = wordVectors.shape[0]
    inputVectors = wordVectors[:N / 2, :]
    outputVectors = wordVectors[N / 2:, :]
    for i in range(batchsize):
        C1 = random.randint(1, C)
        centerword, context = dataset.getRandomContext(C1)
        if word2vecModel == skipgram:
            denom = 1
        else:
            denom = 1
        c, gin, gout = word2vecModel(centerword, C1, context, tokens,
            inputVectors, outputVectors, dataset, word2vecCostAndGradient)
        cost += c / batchsize / denom
        grad[:N // 2, :] += gin / batchsize / denom
        grad[N // 2:, :] += gout / batchsize / denom
    return cost, grad


def test_word2vec():
    """ Interface to the dataset for negative sampling """
    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 ====')
    gradcheck_naive(lambda vec: word2vec_sgd_wrapper(skipgram, dummy_tokens,
        vec, dataset, 5, softmaxCostAndGradient), dummy_vectors)
    gradcheck_naive(lambda vec: word2vec_sgd_wrapper(skipgram, dummy_tokens,
        vec, dataset, 5, negSamplingCostAndGradient), dummy_vectors)
    print('\n==== Gradient check for CBOW      ====')
    gradcheck_naive(lambda vec: word2vec_sgd_wrapper(cbow, dummy_tokens,
        vec, dataset, 5, softmaxCostAndGradient), dummy_vectors)
    gradcheck_naive(lambda vec: word2vec_sgd_wrapper(cbow, dummy_tokens,
        vec, dataset, 5, negSamplingCostAndGradient), dummy_vectors)
    print('\n=== Results ===')
    print(skipgram('c', 3, ['a', 'b', 'e', 'd', 'b', 'c'], dummy_tokens,
        dummy_vectors[:5, :], dummy_vectors[5:, :], dataset))
    print(skipgram('c', 1, ['a', 'b'], dummy_tokens, dummy_vectors[:5, :],
        dummy_vectors[5:, :], dataset, negSamplingCostAndGradient))
    print(cbow('a', 2, ['a', 'b', 'c', 'a'], dummy_tokens, dummy_vectors[:5,
        :], dummy_vectors[5:, :], dataset))
    print(cbow('a', 2, ['a', 'b', 'a', 'c'], dummy_tokens, dummy_vectors[:5,
        :], dummy_vectors[5:, :], dataset, negSamplingCostAndGradient))


<mask token>

<mask token>


def normalizeRows(x):
    """ Row normalization function

    Implement a function that normalizes each row of a matrix to have
    unit length.
    """
    x = x / np.sqrt(np.sum(x * x, axis=-1, keepdims=True))
    return x


def test_normalize_rows():
    print('Testing normalizeRows...')
    x = normalizeRows(np.array([[3.0, 4.0], [1, 2]]))
    print(x)
    ans = np.array([[0.6, 0.8], [0.4472136, 0.89442719]])
    assert np.allclose(x, ans, rtol=1e-05, atol=1e-06)
    print('')


def softmaxCostAndGradient(predicted, target, outputVectors, dataset):
    """ Softmax cost function for word2vec models

    Implement the cost and gradients for one predicted word vector
    and one target word vector as a building block for word2vec
    models, assuming the softmax prediction function and cross
    entropy loss.

    Arguments:
    predicted -- numpy ndarray, predicted word vector (\\hat{v} in
                 the written component)
    target -- integer, the index of the target word
    outputVectors -- "output" vectors (as rows) for all tokens
    dataset -- needed for negative sampling, unused here.

    Return:
    cost -- cross entropy cost for the softmax word prediction
    gradPred -- the gradient with respect to the predicted word
           vector
    grad -- the gradient with respect to all the other word
           vectors

    We will not provide starter code for this function, but feel
    free to reference the code you previously wrote for this
    assignment!
    """
    scores = outputVectors.dot(predicted.T)
    y_hat = softmax(scores)
    cost = -scores[target] + np.log(np.sum(np.exp(scores)))
    one_hot_target = np.zeros_like(y_hat)
    one_hot_target[target] = 1
    grad = np.outer(y_hat - one_hot_target, predicted)
    gradPred = outputVectors.T.dot(y_hat - one_hot_target)
    """
    final_predicted = predicted.dot(outputVectors.T)
    probability = softmax(final_predicted)
    cost = -np.log(probability[target])
    
    one_hot_target = np.zeros_like(probability)
    one_hot_target[target] += 1
    dlogits = probability - one_hot_target
    grad = np.outer(predicted, dlogits).T
    gradPred = outputVectors.T.dot(dlogits)
    """
    return cost, gradPred, grad


def getNegativeSamples(target, dataset, K):
    """ Samples K indexes which are not the target """
    indices = [None] * K
    for k in range(K):
        newidx = dataset.sampleTokenIdx()
        while newidx == target:
            newidx = dataset.sampleTokenIdx()
        indices[k] = newidx
    return indices


def negSamplingCostAndGradient(predicted, target, outputVectors, dataset, K=10
    ):
    """ Negative sampling cost function for word2vec models

    Implement the cost and gradients for one predicted word vector
    and one target word vector as a building block for word2vec
    models, using the negative sampling technique. K is the sample
    size.

    Note: See test_word2vec below for dataset's initialization.

    Arguments/Return Specifications: same as softmaxCostAndGradient
    """
    indices = [target]
    indices.extend(getNegativeSamples(target, dataset, K))
    grad = np.zeros_like(outputVectors)
    gradPred = np.zeros_like(predicted)
    cost = 0.0
    probability = 0.0
    for sample_idx in indices:
        similarity = outputVectors[sample_idx].dot(predicted.T)
        probability = sigmoid(similarity)
        if sample_idx == target:
            cost += -np.log(sigmoid(similarity))
        else:
            cost += -np.log(sigmoid(-similarity))
        if sample_idx == target:
            grad[sample_idx, :] += (probability - 1) * predicted
            gradPred += (probability - 1) * outputVectors[sample_idx]
        else:
            grad[sample_idx, :] += probability * predicted
            gradPred += probability * outputVectors[sample_idx]
    """
    V, D = outputVectors.shape
    one_hot_target = np.zeros(V)
    one_hot_target[target] = 1
    cost = 0
    gradPred = np.zeros_like(predicted)
    grad = np.zeros_like(outputVectors)
    
    for idx in indices:
        context_vector = outputVectors[idx] # embedding vector (1, D)
        cosine_similarity = normalizeRows(predicted).dot(normalizeRows(context_vector).T)
        print('neg sample, consine_similarity={0}'.format(cosine_similarity))
        binary_class = sigmoid(cosine_similarity)
        print('neg sample, binary_class={0}'.format(binary_class))
        
        if idx == target:
            cost += binary_class - 1
        else:
            cost += binary_class
          
        dlogits = sigmoid_grad(cosine_similarity)
        #gradPred += dlogits * normalizeRows(context_vector)
        #grad += np.outer(one_hot_target, dlogits * normalizeRows(predicted))
        gradPred += dlogits
        grad += np.outer(one_hot_target, dlogits)
    """
    return cost, gradPred, grad


def skipgram(currentWord, C, contextWords, tokens, inputVectors,
    outputVectors, dataset, word2vecCostAndGradient=softmaxCostAndGradient):
    """ Skip-gram model in word2vec

    Implement the skip-gram model in this function.

    Arguments:
    currentWord -- a string of the current center word
    C -- integer, context size
    contextWords -- list of no more than 2*C strings, the context words
    tokens -- a dictionary that maps words to their indices in
              the word vector list
    inputVectors -- "input" word vectors (as rows) for all tokens
    outputVectors -- "output" word vectors (as rows) for all tokens
    word2vecCostAndGradient -- the cost and gradient function for
                               a prediction vector given the target
                               word vectors, could be one of the two
                               cost functions you implemented above.

    Return:
    cost -- the cost function value for the skip-gram model
    grad -- the gradient with respect to the word vectors
    """
    cost = 0.0
    gradIn = np.zeros(inputVectors.shape)
    gradOut = np.zeros(outputVectors.shape)
    predicted = inputVectors[tokens[currentWord]]
    for cw in contextWords:
        per_cost, per_gradIn, per_gradOut = word2vecCostAndGradient(predicted,
            tokens[cw], outputVectors, dataset)
        cost += per_cost
        gradIn[tokens[currentWord]] += per_gradIn
        gradOut += per_gradOut
    """
    predicted = inputVectors[tokens[currentWord]] # embedding vector
    one_hot_current = np.zeros(inputVectors.shape[0])
    one_hot_current[tokens[currentWord]] += 1
    for i in range(len(contextWords)):
        per_cost, gradPred, grad = word2vecCostAndGradient(predicted, tokens[contextWords[i]], outputVectors, dataset)
        cost += per_cost
        gradIn += np.outer(one_hot_current, gradPred)
        gradOut += grad
    """
    return cost, gradIn, gradOut


<mask token>


def word2vec_sgd_wrapper(word2vecModel, tokens, wordVectors, dataset, C,
    word2vecCostAndGradient=softmaxCostAndGradient):
    batchsize = 50
    cost = 0.0
    grad = np.zeros(wordVectors.shape)
    N = wordVectors.shape[0]
    inputVectors = wordVectors[:N / 2, :]
    outputVectors = wordVectors[N / 2:, :]
    for i in range(batchsize):
        C1 = random.randint(1, C)
        centerword, context = dataset.getRandomContext(C1)
        if word2vecModel == skipgram:
            denom = 1
        else:
            denom = 1
        c, gin, gout = word2vecModel(centerword, C1, context, tokens,
            inputVectors, outputVectors, dataset, word2vecCostAndGradient)
        cost += c / batchsize / denom
        grad[:N // 2, :] += gin / batchsize / denom
        grad[N // 2:, :] += gout / batchsize / denom
    return cost, grad


def test_word2vec():
    """ Interface to the dataset for negative sampling """
    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 ====')
    gradcheck_naive(lambda vec: word2vec_sgd_wrapper(skipgram, dummy_tokens,
        vec, dataset, 5, softmaxCostAndGradient), dummy_vectors)
    gradcheck_naive(lambda vec: word2vec_sgd_wrapper(skipgram, dummy_tokens,
        vec, dataset, 5, negSamplingCostAndGradient), dummy_vectors)
    print('\n==== Gradient check for CBOW      ====')
    gradcheck_naive(lambda vec: word2vec_sgd_wrapper(cbow, dummy_tokens,
        vec, dataset, 5, softmaxCostAndGradient), dummy_vectors)
    gradcheck_naive(lambda vec: word2vec_sgd_wrapper(cbow, dummy_tokens,
        vec, dataset, 5, negSamplingCostAndGradient), dummy_vectors)
    print('\n=== Results ===')
    print(skipgram('c', 3, ['a', 'b', 'e', 'd', 'b', 'c'], dummy_tokens,
        dummy_vectors[:5, :], dummy_vectors[5:, :], dataset))
    print(skipgram('c', 1, ['a', 'b'], dummy_tokens, dummy_vectors[:5, :],
        dummy_vectors[5:, :], dataset, negSamplingCostAndGradient))
    print(cbow('a', 2, ['a', 'b', 'c', 'a'], dummy_tokens, dummy_vectors[:5,
        :], dummy_vectors[5:, :], dataset))
    print(cbow('a', 2, ['a', 'b', 'a', 'c'], dummy_tokens, dummy_vectors[:5,
        :], dummy_vectors[5:, :], dataset, negSamplingCostAndGradient))


<mask token>

<mask token>


def normalizeRows(x):
    """ Row normalization function

    Implement a function that normalizes each row of a matrix to have
    unit length.
    """
    x = x / np.sqrt(np.sum(x * x, axis=-1, keepdims=True))
    return x


def test_normalize_rows():
    print('Testing normalizeRows...')
    x = normalizeRows(np.array([[3.0, 4.0], [1, 2]]))
    print(x)
    ans = np.array([[0.6, 0.8], [0.4472136, 0.89442719]])
    assert np.allclose(x, ans, rtol=1e-05, atol=1e-06)
    print('')


def softmaxCostAndGradient(predicted, target, outputVectors, dataset):
    """ Softmax cost function for word2vec models

    Implement the cost and gradients for one predicted word vector
    and one target word vector as a building block for word2vec
    models, assuming the softmax prediction function and cross
    entropy loss.

    Arguments:
    predicted -- numpy ndarray, predicted word vector (\\hat{v} in
                 the written component)
    target -- integer, the index of the target word
    outputVectors -- "output" vectors (as rows) for all tokens
    dataset -- needed for negative sampling, unused here.

    Return:
    cost -- cross entropy cost for the softmax word prediction
    gradPred -- the gradient with respect to the predicted word
           vector
    grad -- the gradient with respect to all the other word
           vectors

    We will not provide starter code for this function, but feel
    free to reference the code you previously wrote for this
    assignment!
    """
    scores = outputVectors.dot(predicted.T)
    y_hat = softmax(scores)
    cost = -scores[target] + np.log(np.sum(np.exp(scores)))
    one_hot_target = np.zeros_like(y_hat)
    one_hot_target[target] = 1
    grad = np.outer(y_hat - one_hot_target, predicted)
    gradPred = outputVectors.T.dot(y_hat - one_hot_target)
    """
    final_predicted = predicted.dot(outputVectors.T)
    probability = softmax(final_predicted)
    cost = -np.log(probability[target])
    
    one_hot_target = np.zeros_like(probability)
    one_hot_target[target] += 1
    dlogits = probability - one_hot_target
    grad = np.outer(predicted, dlogits).T
    gradPred = outputVectors.T.dot(dlogits)
    """
    return cost, gradPred, grad


def getNegativeSamples(target, dataset, K):
    """ Samples K indexes which are not the target """
    indices = [None] * K
    for k in range(K):
        newidx = dataset.sampleTokenIdx()
        while newidx == target:
            newidx = dataset.sampleTokenIdx()
        indices[k] = newidx
    return indices


def negSamplingCostAndGradient(predicted, target, outputVectors, dataset, K=10
    ):
    """ Negative sampling cost function for word2vec models

    Implement the cost and gradients for one predicted word vector
    and one target word vector as a building block for word2vec
    models, using the negative sampling technique. K is the sample
    size.

    Note: See test_word2vec below for dataset's initialization.

    Arguments/Return Specifications: same as softmaxCostAndGradient
    """
    indices = [target]
    indices.extend(getNegativeSamples(target, dataset, K))
    grad = np.zeros_like(outputVectors)
    gradPred = np.zeros_like(predicted)
    cost = 0.0
    probability = 0.0
    for sample_idx in indices:
        similarity = outputVectors[sample_idx].dot(predicted.T)
        probability = sigmoid(similarity)
        if sample_idx == target:
            cost += -np.log(sigmoid(similarity))
        else:
            cost += -np.log(sigmoid(-similarity))
        if sample_idx == target:
            grad[sample_idx, :] += (probability - 1) * predicted
            gradPred += (probability - 1) * outputVectors[sample_idx]
        else:
            grad[sample_idx, :] += probability * predicted
            gradPred += probability * outputVectors[sample_idx]
    """
    V, D = outputVectors.shape
    one_hot_target = np.zeros(V)
    one_hot_target[target] = 1
    cost = 0
    gradPred = np.zeros_like(predicted)
    grad = np.zeros_like(outputVectors)
    
    for idx in indices:
        context_vector = outputVectors[idx] # embedding vector (1, D)
        cosine_similarity = normalizeRows(predicted).dot(normalizeRows(context_vector).T)
        print('neg sample, consine_similarity={0}'.format(cosine_similarity))
        binary_class = sigmoid(cosine_similarity)
        print('neg sample, binary_class={0}'.format(binary_class))
        
        if idx == target:
            cost += binary_class - 1
        else:
            cost += binary_class
          
        dlogits = sigmoid_grad(cosine_similarity)
        #gradPred += dlogits * normalizeRows(context_vector)
        #grad += np.outer(one_hot_target, dlogits * normalizeRows(predicted))
        gradPred += dlogits
        grad += np.outer(one_hot_target, dlogits)
    """
    return cost, gradPred, grad


def skipgram(currentWord, C, contextWords, tokens, inputVectors,
    outputVectors, dataset, word2vecCostAndGradient=softmaxCostAndGradient):
    """ Skip-gram model in word2vec

    Implement the skip-gram model in this function.

    Arguments:
    currentWord -- a string of the current center word
    C -- integer, context size
    contextWords -- list of no more than 2*C strings, the context words
    tokens -- a dictionary that maps words to their indices in
              the word vector list
    inputVectors -- "input" word vectors (as rows) for all tokens
    outputVectors -- "output" word vectors (as rows) for all tokens
    word2vecCostAndGradient -- the cost and gradient function for
                               a prediction vector given the target
                               word vectors, could be one of the two
                               cost functions you implemented above.

    Return:
    cost -- the cost function value for the skip-gram model
    grad -- the gradient with respect to the word vectors
    """
    cost = 0.0
    gradIn = np.zeros(inputVectors.shape)
    gradOut = np.zeros(outputVectors.shape)
    predicted = inputVectors[tokens[currentWord]]
    for cw in contextWords:
        per_cost, per_gradIn, per_gradOut = word2vecCostAndGradient(predicted,
            tokens[cw], outputVectors, dataset)
        cost += per_cost
        gradIn[tokens[currentWord]] += per_gradIn
        gradOut += per_gradOut
    """
    predicted = inputVectors[tokens[currentWord]] # embedding vector
    one_hot_current = np.zeros(inputVectors.shape[0])
    one_hot_current[tokens[currentWord]] += 1
    for i in range(len(contextWords)):
        per_cost, gradPred, grad = word2vecCostAndGradient(predicted, tokens[contextWords[i]], outputVectors, dataset)
        cost += per_cost
        gradIn += np.outer(one_hot_current, gradPred)
        gradOut += grad
    """
    return cost, gradIn, gradOut


def cbow(currentWord, C, contextWords, tokens, inputVectors, outputVectors,
    dataset, word2vecCostAndGradient=softmaxCostAndGradient):
    """CBOW model in word2vec

    Implement the continuous bag-of-words model in this function.

    Arguments/Return specifications: same as the skip-gram model

    Extra credit: Implementing CBOW is optional, but the gradient
    derivations are not. If you decide not to implement CBOW, remove
    the NotImplementedError.
    """
    cost = 0.0
    gradIn = np.zeros(inputVectors.shape)
    gradOut = np.zeros(outputVectors.shape)
    predicted = np.zeros(inputVectors.shape[1])
    for cw in contextWords:
        predicted += inputVectors[tokens[cw]]
    predicted /= C
    cost, sum_gradIn, gradOut = word2vecCostAndGradient(predicted, tokens[
        currentWord], outputVectors, dataset)
    for cw in contextWords:
        gradIn[tokens[cw]] += sum_gradIn / C
    return cost, gradIn, gradOut


def word2vec_sgd_wrapper(word2vecModel, tokens, wordVectors, dataset, C,
    word2vecCostAndGradient=softmaxCostAndGradient):
    batchsize = 50
    cost = 0.0
    grad = np.zeros(wordVectors.shape)
    N = wordVectors.shape[0]
    inputVectors = wordVectors[:N / 2, :]
    outputVectors = wordVectors[N / 2:, :]
    for i in range(batchsize):
        C1 = random.randint(1, C)
        centerword, context = dataset.getRandomContext(C1)
        if word2vecModel == skipgram:
            denom = 1
        else:
            denom = 1
        c, gin, gout = word2vecModel(centerword, C1, context, tokens,
            inputVectors, outputVectors, dataset, word2vecCostAndGradient)
        cost += c / batchsize / denom
        grad[:N // 2, :] += gin / batchsize / denom
        grad[N // 2:, :] += gout / batchsize / denom
    return cost, grad


def test_word2vec():
    """ Interface to the dataset for negative sampling """
    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 ====')
    gradcheck_naive(lambda vec: word2vec_sgd_wrapper(skipgram, dummy_tokens,
        vec, dataset, 5, softmaxCostAndGradient), dummy_vectors)
    gradcheck_naive(lambda vec: word2vec_sgd_wrapper(skipgram, dummy_tokens,
        vec, dataset, 5, negSamplingCostAndGradient), dummy_vectors)
    print('\n==== Gradient check for CBOW      ====')
    gradcheck_naive(lambda vec: word2vec_sgd_wrapper(cbow, dummy_tokens,
        vec, dataset, 5, softmaxCostAndGradient), dummy_vectors)
    gradcheck_naive(lambda vec: word2vec_sgd_wrapper(cbow, dummy_tokens,
        vec, dataset, 5, negSamplingCostAndGradient), dummy_vectors)
    print('\n=== Results ===')
    print(skipgram('c', 3, ['a', 'b', 'e', 'd', 'b', 'c'], dummy_tokens,
        dummy_vectors[:5, :], dummy_vectors[5:, :], dataset))
    print(skipgram('c', 1, ['a', 'b'], dummy_tokens, dummy_vectors[:5, :],
        dummy_vectors[5:, :], dataset, negSamplingCostAndGradient))
    print(cbow('a', 2, ['a', 'b', 'c', 'a'], dummy_tokens, dummy_vectors[:5,
        :], dummy_vectors[5:, :], dataset))
    print(cbow('a', 2, ['a', 'b', 'a', 'c'], dummy_tokens, dummy_vectors[:5,
        :], dummy_vectors[5:, :], dataset, negSamplingCostAndGradient))


<mask token>

<mask token>


def normalizeRows(x):
    """ Row normalization function

    Implement a function that normalizes each row of a matrix to have
    unit length.
    """
    x = x / np.sqrt(np.sum(x * x, axis=-1, keepdims=True))
    return x


def test_normalize_rows():
    print('Testing normalizeRows...')
    x = normalizeRows(np.array([[3.0, 4.0], [1, 2]]))
    print(x)
    ans = np.array([[0.6, 0.8], [0.4472136, 0.89442719]])
    assert np.allclose(x, ans, rtol=1e-05, atol=1e-06)
    print('')


def softmaxCostAndGradient(predicted, target, outputVectors, dataset):
    """ Softmax cost function for word2vec models

    Implement the cost and gradients for one predicted word vector
    and one target word vector as a building block for word2vec
    models, assuming the softmax prediction function and cross
    entropy loss.

    Arguments:
    predicted -- numpy ndarray, predicted word vector (\\hat{v} in
                 the written component)
    target -- integer, the index of the target word
    outputVectors -- "output" vectors (as rows) for all tokens
    dataset -- needed for negative sampling, unused here.

    Return:
    cost -- cross entropy cost for the softmax word prediction
    gradPred -- the gradient with respect to the predicted word
           vector
    grad -- the gradient with respect to all the other word
           vectors

    We will not provide starter code for this function, but feel
    free to reference the code you previously wrote for this
    assignment!
    """
    scores = outputVectors.dot(predicted.T)
    y_hat = softmax(scores)
    cost = -scores[target] + np.log(np.sum(np.exp(scores)))
    one_hot_target = np.zeros_like(y_hat)
    one_hot_target[target] = 1
    grad = np.outer(y_hat - one_hot_target, predicted)
    gradPred = outputVectors.T.dot(y_hat - one_hot_target)
    """
    final_predicted = predicted.dot(outputVectors.T)
    probability = softmax(final_predicted)
    cost = -np.log(probability[target])
    
    one_hot_target = np.zeros_like(probability)
    one_hot_target[target] += 1
    dlogits = probability - one_hot_target
    grad = np.outer(predicted, dlogits).T
    gradPred = outputVectors.T.dot(dlogits)
    """
    return cost, gradPred, grad


def getNegativeSamples(target, dataset, K):
    """ Samples K indexes which are not the target """
    indices = [None] * K
    for k in range(K):
        newidx = dataset.sampleTokenIdx()
        while newidx == target:
            newidx = dataset.sampleTokenIdx()
        indices[k] = newidx
    return indices


def negSamplingCostAndGradient(predicted, target, outputVectors, dataset, K=10
    ):
    """ Negative sampling cost function for word2vec models

    Implement the cost and gradients for one predicted word vector
    and one target word vector as a building block for word2vec
    models, using the negative sampling technique. K is the sample
    size.

    Note: See test_word2vec below for dataset's initialization.

    Arguments/Return Specifications: same as softmaxCostAndGradient
    """
    indices = [target]
    indices.extend(getNegativeSamples(target, dataset, K))
    grad = np.zeros_like(outputVectors)
    gradPred = np.zeros_like(predicted)
    cost = 0.0
    probability = 0.0
    for sample_idx in indices:
        similarity = outputVectors[sample_idx].dot(predicted.T)
        probability = sigmoid(similarity)
        if sample_idx == target:
            cost += -np.log(sigmoid(similarity))
        else:
            cost += -np.log(sigmoid(-similarity))
        if sample_idx == target:
            grad[sample_idx, :] += (probability - 1) * predicted
            gradPred += (probability - 1) * outputVectors[sample_idx]
        else:
            grad[sample_idx, :] += probability * predicted
            gradPred += probability * outputVectors[sample_idx]
    """
    V, D = outputVectors.shape
    one_hot_target = np.zeros(V)
    one_hot_target[target] = 1
    cost = 0
    gradPred = np.zeros_like(predicted)
    grad = np.zeros_like(outputVectors)
    
    for idx in indices:
        context_vector = outputVectors[idx] # embedding vector (1, D)
        cosine_similarity = normalizeRows(predicted).dot(normalizeRows(context_vector).T)
        print('neg sample, consine_similarity={0}'.format(cosine_similarity))
        binary_class = sigmoid(cosine_similarity)
        print('neg sample, binary_class={0}'.format(binary_class))
        
        if idx == target:
            cost += binary_class - 1
        else:
            cost += binary_class
          
        dlogits = sigmoid_grad(cosine_similarity)
        #gradPred += dlogits * normalizeRows(context_vector)
        #grad += np.outer(one_hot_target, dlogits * normalizeRows(predicted))
        gradPred += dlogits
        grad += np.outer(one_hot_target, dlogits)
    """
    return cost, gradPred, grad


def skipgram(currentWord, C, contextWords, tokens, inputVectors,
    outputVectors, dataset, word2vecCostAndGradient=softmaxCostAndGradient):
    """ Skip-gram model in word2vec

    Implement the skip-gram model in this function.

    Arguments:
    currentWord -- a string of the current center word
    C -- integer, context size
    contextWords -- list of no more than 2*C strings, the context words
    tokens -- a dictionary that maps words to their indices in
              the word vector list
    inputVectors -- "input" word vectors (as rows) for all tokens
    outputVectors -- "output" word vectors (as rows) for all tokens
    word2vecCostAndGradient -- the cost and gradient function for
                               a prediction vector given the target
                               word vectors, could be one of the two
                               cost functions you implemented above.

    Return:
    cost -- the cost function value for the skip-gram model
    grad -- the gradient with respect to the word vectors
    """
    cost = 0.0
    gradIn = np.zeros(inputVectors.shape)
    gradOut = np.zeros(outputVectors.shape)
    predicted = inputVectors[tokens[currentWord]]
    for cw in contextWords:
        per_cost, per_gradIn, per_gradOut = word2vecCostAndGradient(predicted,
            tokens[cw], outputVectors, dataset)
        cost += per_cost
        gradIn[tokens[currentWord]] += per_gradIn
        gradOut += per_gradOut
    """
    predicted = inputVectors[tokens[currentWord]] # embedding vector
    one_hot_current = np.zeros(inputVectors.shape[0])
    one_hot_current[tokens[currentWord]] += 1
    for i in range(len(contextWords)):
        per_cost, gradPred, grad = word2vecCostAndGradient(predicted, tokens[contextWords[i]], outputVectors, dataset)
        cost += per_cost
        gradIn += np.outer(one_hot_current, gradPred)
        gradOut += grad
    """
    return cost, gradIn, gradOut


def cbow(currentWord, C, contextWords, tokens, inputVectors, outputVectors,
    dataset, word2vecCostAndGradient=softmaxCostAndGradient):
    """CBOW model in word2vec

    Implement the continuous bag-of-words model in this function.

    Arguments/Return specifications: same as the skip-gram model

    Extra credit: Implementing CBOW is optional, but the gradient
    derivations are not. If you decide not to implement CBOW, remove
    the NotImplementedError.
    """
    cost = 0.0
    gradIn = np.zeros(inputVectors.shape)
    gradOut = np.zeros(outputVectors.shape)
    predicted = np.zeros(inputVectors.shape[1])
    for cw in contextWords:
        predicted += inputVectors[tokens[cw]]
    predicted /= C
    cost, sum_gradIn, gradOut = word2vecCostAndGradient(predicted, tokens[
        currentWord], outputVectors, dataset)
    for cw in contextWords:
        gradIn[tokens[cw]] += sum_gradIn / C
    return cost, gradIn, gradOut


def word2vec_sgd_wrapper(word2vecModel, tokens, wordVectors, dataset, C,
    word2vecCostAndGradient=softmaxCostAndGradient):
    batchsize = 50
    cost = 0.0
    grad = np.zeros(wordVectors.shape)
    N = wordVectors.shape[0]
    inputVectors = wordVectors[:N / 2, :]
    outputVectors = wordVectors[N / 2:, :]
    for i in range(batchsize):
        C1 = random.randint(1, C)
        centerword, context = dataset.getRandomContext(C1)
        if word2vecModel == skipgram:
            denom = 1
        else:
            denom = 1
        c, gin, gout = word2vecModel(centerword, C1, context, tokens,
            inputVectors, outputVectors, dataset, word2vecCostAndGradient)
        cost += c / batchsize / denom
        grad[:N // 2, :] += gin / batchsize / denom
        grad[N // 2:, :] += gout / batchsize / denom
    return cost, grad


def test_word2vec():
    """ Interface to the dataset for negative sampling """
    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 ====')
    gradcheck_naive(lambda vec: word2vec_sgd_wrapper(skipgram, dummy_tokens,
        vec, dataset, 5, softmaxCostAndGradient), dummy_vectors)
    gradcheck_naive(lambda vec: word2vec_sgd_wrapper(skipgram, dummy_tokens,
        vec, dataset, 5, negSamplingCostAndGradient), dummy_vectors)
    print('\n==== Gradient check for CBOW      ====')
    gradcheck_naive(lambda vec: word2vec_sgd_wrapper(cbow, dummy_tokens,
        vec, dataset, 5, softmaxCostAndGradient), dummy_vectors)
    gradcheck_naive(lambda vec: word2vec_sgd_wrapper(cbow, dummy_tokens,
        vec, dataset, 5, negSamplingCostAndGradient), dummy_vectors)
    print('\n=== Results ===')
    print(skipgram('c', 3, ['a', 'b', 'e', 'd', 'b', 'c'], dummy_tokens,
        dummy_vectors[:5, :], dummy_vectors[5:, :], dataset))
    print(skipgram('c', 1, ['a', 'b'], dummy_tokens, dummy_vectors[:5, :],
        dummy_vectors[5:, :], dataset, negSamplingCostAndGradient))
    print(cbow('a', 2, ['a', 'b', 'c', 'a'], dummy_tokens, dummy_vectors[:5,
        :], dummy_vectors[5:, :], dataset))
    print(cbow('a', 2, ['a', 'b', 'a', 'c'], dummy_tokens, dummy_vectors[:5,
        :], dummy_vectors[5:, :], dataset, negSamplingCostAndGradient))


if __name__ == '__main__':
    test_normalize_rows()
    test_word2vec()

#!/usr/bin/env python
# reference:
#           1. word2vec Parameter Learning Explained (https://arxiv.org/pdf/1411.2738.pdf)
#           2. word2vec Explained: Deriving Mikolov et al.s Negative-Sampling Word-Embedding Method
#               (https://arxiv.org/pdf/1402.3722.pdf)

import numpy as np
import random

from q1_softmax import softmax
from q2_gradcheck import gradcheck_naive
from q2_sigmoid import sigmoid, sigmoid_grad

def normalizeRows(x):
    """ Row normalization function

    Implement a function that normalizes each row of a matrix to have
    unit length.
    """

    ### YOUR CODE HERE
    # using l2 norm to normalize
    x = x / np.sqrt(np.sum(x * x, axis=-1, keepdims=True))
    ### END YOUR CODE

    return x


def test_normalize_rows():
    print("Testing normalizeRows...")
    x = normalizeRows(np.array([[3.0,4.0],[1, 2]]))
    print(x)
    ans = np.array([[0.6,0.8],[0.4472136,0.89442719]])
    assert np.allclose(x, ans, rtol=1e-05, atol=1e-06)
    print("")


def softmaxCostAndGradient(predicted, target, outputVectors, dataset):
    """ Softmax cost function for word2vec models

    Implement the cost and gradients for one predicted word vector
    and one target word vector as a building block for word2vec
    models, assuming the softmax prediction function and cross
    entropy loss.

    Arguments:
    predicted -- numpy ndarray, predicted word vector (\hat{v} in
                 the written component)
    target -- integer, the index of the target word
    outputVectors -- "output" vectors (as rows) for all tokens
    dataset -- needed for negative sampling, unused here.

    Return:
    cost -- cross entropy cost for the softmax word prediction
    gradPred -- the gradient with respect to the predicted word
           vector
    grad -- the gradient with respect to all the other word
           vectors

    We will not provide starter code for this function, but feel
    free to reference the code you previously wrote for this
    assignment!
    """

    ### YOUR CODE HERE
    scores = outputVectors.dot(predicted.T) # shape = (V, 1)
    y_hat = softmax(scores)
    cost = -scores[target] + np.log(np.sum(np.exp(scores)))
    one_hot_target = np.zeros_like(y_hat)
    one_hot_target[target] = 1
    grad = np.outer((y_hat - one_hot_target), predicted)
    gradPred = outputVectors.T.dot(y_hat - one_hot_target)
    
    '''
    final_predicted = predicted.dot(outputVectors.T)
    probability = softmax(final_predicted)
    cost = -np.log(probability[target])
    
    one_hot_target = np.zeros_like(probability)
    one_hot_target[target] += 1
    dlogits = probability - one_hot_target
    grad = np.outer(predicted, dlogits).T
    gradPred = outputVectors.T.dot(dlogits)
    '''
    ### END YOUR CODE

    return cost, gradPred, grad


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

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


def negSamplingCostAndGradient(predicted, target, outputVectors, dataset,
                               K=10):
    """ Negative sampling cost function for word2vec models

    Implement the cost and gradients for one predicted word vector
    and one target word vector as a building block for word2vec
    models, using the negative sampling technique. K is the sample
    size.

    Note: See test_word2vec below for dataset's initialization.

    Arguments/Return Specifications: same as softmaxCostAndGradient
    """

    # Sampling of indices is done for you. Do not modify this if you
    # wish to match the autograder and receive points!
    indices = [target]
    indices.extend(getNegativeSamples(target, dataset, K))

    ### YOUR CODE HERE
    grad = np.zeros_like(outputVectors)
    gradPred = np.zeros_like(predicted)
    cost = 0.0
    probability = 0.0
    for sample_idx in indices:
        similarity = outputVectors[sample_idx].dot(predicted.T)
        probability = sigmoid(similarity) # squash to 0 ~ 1
        if sample_idx == target: # positive sample
            #p = sigmoid(outputVectors[sample_idx].dot(predicted.T))
            cost += -np.log(sigmoid(similarity))
        else: # negative sample
            #p = sigmoid(-outputVectors[sample_idx].dot(predicted.T))
            cost += -np.log(sigmoid(-similarity)) # deduction from reference 2.
        
        if sample_idx == target:
            grad[sample_idx, :] += (probability - 1) * predicted
            gradPred += (probability - 1) * outputVectors[sample_idx]
        else:
            grad[sample_idx, :] += probability * predicted
            gradPred += probability * outputVectors[sample_idx]
    '''
    V, D = outputVectors.shape
    one_hot_target = np.zeros(V)
    one_hot_target[target] = 1
    cost = 0
    gradPred = np.zeros_like(predicted)
    grad = np.zeros_like(outputVectors)
    
    for idx in indices:
        context_vector = outputVectors[idx] # embedding vector (1, D)
        cosine_similarity = normalizeRows(predicted).dot(normalizeRows(context_vector).T)
        print('neg sample, consine_similarity={0}'.format(cosine_similarity))
        binary_class = sigmoid(cosine_similarity)
        print('neg sample, binary_class={0}'.format(binary_class))
        
        if idx == target:
            cost += binary_class - 1
        else:
            cost += binary_class
          
        dlogits = sigmoid_grad(cosine_similarity)
        #gradPred += dlogits * normalizeRows(context_vector)
        #grad += np.outer(one_hot_target, dlogits * normalizeRows(predicted))
        gradPred += dlogits
        grad += np.outer(one_hot_target, dlogits)
    '''
    ### END YOUR CODE

    return cost, gradPred, grad


def skipgram(currentWord, C, contextWords, tokens, inputVectors, outputVectors,
             dataset, word2vecCostAndGradient=softmaxCostAndGradient):
    """ Skip-gram model in word2vec

    Implement the skip-gram model in this function.

    Arguments:
    currentWord -- a string of the current center word
    C -- integer, context size
    contextWords -- list of no more than 2*C strings, the context words
    tokens -- a dictionary that maps words to their indices in
              the word vector list
    inputVectors -- "input" word vectors (as rows) for all tokens
    outputVectors -- "output" word vectors (as rows) for all tokens
    word2vecCostAndGradient -- the cost and gradient function for
                               a prediction vector given the target
                               word vectors, could be one of the two
                               cost functions you implemented above.

    Return:
    cost -- the cost function value for the skip-gram model
    grad -- the gradient with respect to the word vectors
    """
    
    cost = 0.0
    gradIn = np.zeros(inputVectors.shape)
    gradOut = np.zeros(outputVectors.shape)

    ### YOUR CODE HERE
    predicted = inputVectors[tokens[currentWord]]
    for cw in contextWords:
        per_cost, per_gradIn, per_gradOut = word2vecCostAndGradient(predicted, tokens[cw], outputVectors, dataset)
        cost += per_cost
        gradIn[tokens[currentWord]] += per_gradIn
        gradOut += per_gradOut
    '''
    predicted = inputVectors[tokens[currentWord]] # embedding vector
    one_hot_current = np.zeros(inputVectors.shape[0])
    one_hot_current[tokens[currentWord]] += 1
    for i in range(len(contextWords)):
        per_cost, gradPred, grad = word2vecCostAndGradient(predicted, tokens[contextWords[i]], outputVectors, dataset)
        cost += per_cost
        gradIn += np.outer(one_hot_current, gradPred)
        gradOut += grad
    '''
    ### END YOUR CODE

    return cost, gradIn, gradOut


def cbow(currentWord, C, contextWords, tokens, inputVectors, outputVectors,
         dataset, word2vecCostAndGradient=softmaxCostAndGradient):
    """CBOW model in word2vec

    Implement the continuous bag-of-words model in this function.

    Arguments/Return specifications: same as the skip-gram model

    Extra credit: Implementing CBOW is optional, but the gradient
    derivations are not. If you decide not to implement CBOW, remove
    the NotImplementedError.
    """

    cost = 0.0
    gradIn = np.zeros(inputVectors.shape)
    gradOut = np.zeros(outputVectors.shape)

    ### YOUR CODE HERE
    predicted = np.zeros(inputVectors.shape[1])
    for cw in contextWords:
        predicted += inputVectors[tokens[cw]]
    predicted /= C
    
    cost, sum_gradIn, gradOut = word2vecCostAndGradient(predicted, tokens[currentWord], outputVectors, dataset)
    # distribute sum_gradIn to each of context words
    for cw in contextWords: 
        gradIn[tokens[cw]] += sum_gradIn / C
    ### END YOUR CODE
    return cost, gradIn, gradOut


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

def word2vec_sgd_wrapper(word2vecModel, tokens, wordVectors, dataset, C,
                         word2vecCostAndGradient=softmaxCostAndGradient):
    batchsize = 50
    cost = 0.0
    grad = np.zeros(wordVectors.shape)
    N = wordVectors.shape[0]
    inputVectors = wordVectors[:N/2,:]
    outputVectors = wordVectors[N/2:,:]
    for i in range(batchsize):
        C1 = random.randint(1,C)
        centerword, context = dataset.getRandomContext(C1)

        if word2vecModel == skipgram:
            denom = 1
        else:
            denom = 1

        c, gin, gout = word2vecModel(
            centerword, C1, context, tokens, inputVectors, outputVectors,
            dataset, word2vecCostAndGradient)
        cost += c / batchsize / denom
        grad[:N//2, :] += gin / batchsize / denom
        grad[N//2:, :] += gout / batchsize / denom

    return cost, grad


def test_word2vec():
    """ Interface to the dataset for negative sampling """
    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 ====")
    gradcheck_naive(lambda vec: word2vec_sgd_wrapper(
        skipgram, dummy_tokens, vec, dataset, 5, softmaxCostAndGradient),
        dummy_vectors)
    gradcheck_naive(lambda vec: word2vec_sgd_wrapper(
        skipgram, dummy_tokens, vec, dataset, 5, negSamplingCostAndGradient),
        dummy_vectors)
    print("\n==== Gradient check for CBOW      ====")
    gradcheck_naive(lambda vec: word2vec_sgd_wrapper(
        cbow, dummy_tokens, vec, dataset, 5, softmaxCostAndGradient),
        dummy_vectors)
    gradcheck_naive(lambda vec: word2vec_sgd_wrapper(
        cbow, dummy_tokens, vec, dataset, 5, negSamplingCostAndGradient),
        dummy_vectors)

    print("\n=== Results ===")
    print(skipgram("c", 3, ["a", "b", "e", "d", "b", "c"],
        dummy_tokens, dummy_vectors[:5,:], dummy_vectors[5:,:], dataset))
    print(skipgram("c", 1, ["a", "b"],
        dummy_tokens, dummy_vectors[:5,:], dummy_vectors[5:,:], dataset,
        negSamplingCostAndGradient))
    print(cbow("a", 2, ["a", "b", "c", "a"],
        dummy_tokens, dummy_vectors[:5,:], dummy_vectors[5:,:], dataset))
    print(cbow("a", 2, ["a", "b", "a", "c"],
        dummy_tokens, dummy_vectors[:5,:], dummy_vectors[5:,:], dataset,
        negSamplingCostAndGradient))


if __name__ == "__main__":
    test_normalize_rows()
    test_word2vec()
