text: #!/usr/bin/env python
  
  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.
      """
  
      x_sum = np.sqrt((x * x).sum(axis=1))
      x = x / x_sum[:, None]
  
      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(v_c, target, U, 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
      u_v -- "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
      z = np.dot(U, v_c)
      y_hat = softmax(z)
  
      #  Calculate the cost:
      cost = -np.log(y_hat[target])
  
      #  Gradients
      z = y_hat.copy()
      z[target] -= 1.0
  
      # grad for u
      grad = np.outer(z, v_c)
  
      # grad for v
      gradPred = np.dot(U.T, z)
  
      return cost, gradPred, grad
  
  
  def getNegativeSamples(target, dataset, K):
      """ Samples K indexes which are not the target """
  
      indices = [None] * K
      for k in xrange(K):
          newidx = dataset.sampleTokenIdx()
          while newidx == target:
              newidx = dataset.sampleTokenIdx()
          indices[k] = newidx
      return indices
  
  
  def negSamplingCostAndGradient(v_c, target, U, 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))
  
      grad = np.zeros(U.shape)
      gradPred = np.zeros(v_c.shape)
  
      # positive samples
      z = sigmoid(np.dot(U[target], v_c))
      cost = -np.log(z)
      grad[target] += v_c * (z - 1.0)
      gradPred += U[target] * (z - 1.0)
  
      # negative sample
      for k in xrange(K):
          sample_index = indices[k + 1]
          z = sigmoid(np.dot(U[sample_index], v_c))
          cost -= np.log(1.0 - z)
          grad[sample_index] += v_c * z
          gradPred += U[sample_index] * z
  
      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)
  
      current_index = tokens[currentWord]
      v_c = inputVectors[current_index]
  
      for win_word in contextWords:
          wv_index = tokens[win_word]
          win_cost, win_grad_in, win_grad_out = \
              word2vecCostAndGradient(v_c, wv_index, outputVectors, dataset)
          cost += win_cost
          gradIn[current_index] += win_grad_in
          gradOut += win_grad_out
  
      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)
  
      win_indices = [tokens[word] for word in contextWords]
      win_vectors = inputVectors[win_indices]
      win_sum_vector = win_vectors.sum(axis=0)
      current_index = tokens[currentWord]
  
      cost, grad_win, gradOut = word2vecCostAndGradient(win_sum_vector, current_index, outputVectors, dataset)
      for i in win_indices:
          gradIn[i] += grad_win
  
      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 xrange(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 xrange(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()
  