CS224d－Day 3:
word2vec 有两个模型，CBOW 和 Skip-Gram，今天先讲 Skip-Gram 的算法和实现。
Skip-Gram 能达到什么效果？
比如词库里有这么一句话 ‘The cat jumped over the puddle’， 如果给我们 ‘jumped’时，我们可以推出它周围的词： "The", "cat", "over", "the", "puddle"。这就是 skip gram 做的事情：
Skip-gram 算法如下
其中，word i 对应的 one-hot vector 是 x，W^1 是 input vector matrix，它的第 i 列是 word i 的 input vector，用 u^i 表示，W^2 是 output vector matrix，它的第 i 行是 word i 的 output vector，用 v^i 表示，也就是对于每个词，都有两个向量表示，而这两个 W 也正是我们要求的。
我们的目标是要让下面的条件概率达到最大：也就是在给定 word i 的前提下，使它周围的词语是窗口长为2C内的上下文的概率达到最大。
为了求这两个参数矩阵，我们要使下面这个 cost function J 达到最小：
其中这个概率的计算用到了 softmax 函数来求得。
所以这个模型就变为，对 J 求参数的偏导，再用梯度下降方法更新梯度，最后让 cost 达到最小。
下面这个公式是 J 对 input vector 的偏导，每次更新 W^1 的相应行：
下面这个公式是 J 对 output vector 的偏导，每次更新 W^2：
要把上面的算法实现，代码如下：
def test_word2vec():
dataset = type('dummy', (), {})() #create a dynamic object and then add attributes to it
def dummySampleTokenIdx(): #generate 1 integer between (0,4)
return random.randint(0, 4)
def getRandomContext(C): #getRandomContext(3) = ('d', ['d', 'd', 'd', 'e', 'a', 'd'])
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 #add two methods to dataset
dataset.getRandomContext = getRandomContext
random.seed(31415)
np.random.seed(9265) #can be called again to re-seed the generator
#in this test, this wordvectors matrix is randomly generated,
#but in real training, this matrix is a well trained data
dummy_vectors = normalizeRows(np.random.randn(10,3)) #generate matrix in shape=(10,3),
dummy_tokens = dict([("a",0), ("b",1), ("c",2), ("d",3), ("e",4)]) #{'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), dummy_vectors) #vec is dummy_vectors
print "\n=== Results ==="
print skipgram("c", 3, ["a", "b", "e", "d", "b", "c"], dummy_tokens, dummy_vectors[:5, :], dummy_vectors[5:, :], dataset)
if __name__ == "__main__":
test_word2vec()
这个函数里定义了：
dummy_vectors－就是要求的两个 W，只不过合成一个矩阵形式了，初始化是随机生成
dummy_tokens－一个字典，用来表示词窗里的单词和位置
然后调用了 gradcheck_naive－这个函数就是用来检验，目标函数自己求出来的导数和从分析学的角度计算出来的导数是否差不多，误差不大的话就通过 check，否则就是没有通过。
所以可以先直接看下面这个函数， word2vec_sgd_wrapper(skipgram, dummy_tokens, vec, dataset, 5), 其中 vec＝dummy_vectors：
def word2vec_sgd_wrapper(word2vecModel, tokens, wordVectors, dataset, C, word2vecCostAndGradient = softmaxCostAndGradient):
batchsize = 50
cost = 0.0
grad = np.zeros(wordVectors.shape) #each element in wordVectors has a gradient
N = wordVectors.shape[0]
inputVectors = wordVectors[:N/2, :]
outputVectors = wordVectors[N/2:, :]
for i in xrange(batchsize): #train word2vecModel for 50 times
C1 = random.randint(1, C)
centerword, context = dataset.getRandomContext(C1) #randomly choose 1 word, and generate a context of it
if word2vecModel = skipgram:
denom = 1
else:
denom = 1
c, gin, gout = word2vecModel(centerword, C1, context, tokens, inputVectors, outputVectors, dataset, word2vecCostAndGradient)
cost += c / batchsize / denom #calculate the average
grad[:N/2, :] += gin / batchsize / denom
grad[N/2:, :] += gout / batchsize / denom
return cost, grad
这个函数主要是做了 batchsize = 50 次的迭代，每一次，都随机选取一个 center word，并随机生成一个长度为 2*C1 的上下文，其中 C1 也是随机的：centerword, context = dataset.getRandomContext(C1)
每一次都由 word2vecModel 求出一组 cost 和 gradient，最后50次后求平均值做为结果。
那么接下来看 word2vecModel(centerword, C1, context, tokens, inputVectors, outputVectors, dataset, word2vecCostAndGradient) 这个函数：
其中 word2vecModel 我们先看 skipgram 模型，
word2vecCostAndGradient 先看 softmax 计算的，其实 模型可以有 skipgram 和 cbow 两种选择，word2vecCostAndGradient 可以有 softmax 和 negative sampling 两种选择，所以 word2vec 一共4种组合形式，今天先写 skipgram＋softmax 的，把一个弄明白，其他的就好理解了：
def skipgram(currentWord, C, contextWords, tokens, inputVectors, outputVectors,
dataset, word2vecCostAndGradient = softmaxCostAndGradient):
""" Skip-gram model in word2vec """
currentI = tokens[currentWord] #the order of this center word in the whole vocabulary
predicted = inputVectors[currentI, :] #turn this word to vector representation
cost = 0.0
gradIn = np.zeros(inputVectors.shape)
gradOut = np.zeros(outputVectors.shape)
for cwd in contextWords: #contextWords is of 2C length
idx = tokens[cwd]
cc, gp, gg = word2vecCostAndGradient(predicted, idx, outputVectors, dataset)
cost += cc #final cost/gradient is the 'sum' of result calculated by each word in context
gradOut += gg
gradIn[currentI, :] += gp
return cost, gradIn, gradOut
在上面这个 skipgram 函数里，向量 predicted 就是 center word 的 input vector 的表示，contextWords 就是随机生成的 长度为 2*C1 的上下文，在文章开头我们提到了，目标是要让 J 达到最大，所以需要对 v_c 和 u_w 求偏导，并且求出最小的 cost，由上面的形式，有一个求和的过程，所以我们可以对 上下文 中的每一个词先分别求，然后加起来得到最终结果，那 skipgram 这个函数主要是求和，求导在 word2vecCostAndGradient(predicted, idx, outputVectors, dataset) 这个函数里，这个我们用的是 softmax 求 cost 和 gradient：
def softmaxCostAndGradient(predicted, target, outputVectors, dataset):
""" Softmax cost function for word2vec models """
probabilities = softmax(predicted.dot(outputVectors.T))
cost = -np.log(probabilities[target])
delta = probabilities
delta[target] -= 1
N = delta.shape[0] #delta.shape = (5,)
D = predicted.shape[0] #predicted.shape = (3,)
grad = delta.reshape((N, 1)) * predicted.reshape((1, D))
gradPred = (delta.reshape((1, N)).dot(outputVectors)).flatten()
return cost, gradPred, grad
在上面的函数里，probabilities = softmax(predicted.dot(outputVectors.T)) 就是
grad = delta.reshape((N, 1)) * predicted.reshape((1, D))就是
gradPred = (delta.reshape((1, N)).dot(outputVectors)).flatten()就是
ok，Skip-Gram 和 softmax gradient 的结合就写完了，之后再看到 几行简略的算法描述，应该自己也能写出完整的代码了。
下一次要写用 SGD 求 word2vec 模型的参数，本来这一次想直接写情感分析的实战项目的，但是发现 word2vec 值得单独拿出来写一下，因为这个算法才是应用的核心，应用的项目多数都是分类问题，而 word2vec 训练出来的词向量才是分类训练的重要原料。
上面的完整代码可以在这里找到
