CS 224n(2019) Assignment 2: word2vec[Coding]——Part 2

2019-05-20

Assignment 2的原始问题及完整代码已经上传GitHub仓库：https://github.com/moverzp/LearningProject/tree/master/CS%20224n%20(Winter%202019)

Written部分的解析详见CS 224n(2019) Assignment 2: word2vec[Written]
Part1完成作业要求的那部分代码，详见CS 224n(2019) Assignment 2: word2vec[Coding]——Part 1
Part2分析了作业之外的那代码部分，目的是搞清楚test和train的流程和原理，train的流程主要在run.py文件

1. gradcheck.py

该文件只定义了gradcheck_naive()一个函数，代码明细: https://github.com/moverzp/LearningProject/blob/master/CS%20224n%20(Winter%202019)/a2_solution/utils/gradcheck.py，本段只分析梯度校验的原理。

传入的参数：

f，function，传入一个参数，返回loss和grad
x，ndarray，检测梯度所在的点

返回的参数：无，只打印梯度校验是否通过。

我们先来看看导数的定义

$f'(x) = \mathop {\text {lim}}\limits_{\Delta x \rightarrow 0}\dfrac {f(x) - f(x + \Delta x)}{\Delta x}$

导数还分为左导数和右导数，如果把导数看做某点切线的斜率，那么左导数就是切线从左边不断逼近的斜率，右导数就是切线从右边不断逼近的斜率。如果左导数和右导数相等，那么就认为该函数在这一点连续且可导，比如 $f(x) = x^2$ ，处处连续且可导。如果左导数和右导数不相等，就说明函数在该点不可导，比如 $Relu(x) = \max(x, 0)$ ，在0这一点就是连续但不可导。

所以我们根据导数的基本定义可以验证求导函数是否正确。使用传入的函数f可以计算某点导数的实际值，使用导数的定义可以计算某点导数的理论值，如果相差不大，就认为传入的函数f确实可以正确计算导数。

该函数分别计算了左右导数 $f’_{-}(x)$ ， $f’_{+}(x)$ ， $\Delta x$ 取1e-4，然后对左右导数取了平均值，记为 $f’(x)$ ，使用函数f计算的实际导数记为 $grad(x)$ ，然后计算reldiff，

$reldiff = \dfrac {|f'(x) - grad(x)|}{\max (1, |f'(x)|, |grad(x)|)}$

如果feldiff大于1e-5，那么就判断梯度计算得不正确。

程序上有些小trick，这里提示一下

导数并不是一次计算完所有的维度进行判断，而是使用np.nditer()一个维度一个维度的计算并判断，只要一个维度不合理，就认为梯度计算错误
程序开始时使用random.getstate()保存了当前的随机数其实状态，后面需要复用，保证结果可以复现，避免随机数对结果的判断产生影响
本段一会说导数，一会说梯度，大家不要搞混了。导数是一个数，是标量；梯度是一个向量，是矢量，其方向上的方向导数最大，这个方向就是各个轴的偏导数组成的矢量的方向（有点绕口）。因此如果（偏）导数计算的有错误，就可以判断梯度计算一定有错误。

2. word2vec.py

2.1 naiveSoftmaxLossAndGradient()

这个函数在Part1部分解析过，详见CS 224n(2019) Assignment 2: word2vec[Coding]——Part 1。

该函数根据中心词和上下文词汇，计算softmax损失，损失函数对于对于中心词嵌入向量的梯度，损失函数对于上下文词嵌入矩阵的梯度。

2.2 skipgram()

该函数在Part1部分解析过，详见CS 224n(2019) Assignment 2: word2vec[Coding]——Part 1。

该方法计算了skipgram形式的loss以及loss对于中心词嵌入矩阵和上下文词嵌入矩阵的梯度。

2.3 word2vec_sgd_wrapper()

该函数就是根据传入的参数训练一个batch的模型，然后返回这个batch的平均损失和梯度。

传入的参数

word2vecModel
word2Ind
wordVectors
dateaset
windowSize，注意这个参数设定的是最大的窗口大小，在每一个batch的训练中，从[1, windowSize]中随机取一个值当做该次batch的窗口大小
word2vecLossAndGradient

返回的变量

loss，损失
grad，梯度

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

2.4 test_word2vec()

该函数主要有以下几个操作

生成dataset对象
使用np.random.randn()生成最初的10行3列词嵌入矩阵dummy_vectors
创建单词到索引的映射字典dummy_tokens
使用gradcheck_naive()校验naiveSoftmaxLossAndGradient()和negSamplingLossAndGradient()梯度计算是否正确。注意这里的lambda表达式，gradcheck_naive()检验的函数只接受一个 $x$ 值，而这两个待校验的函数都要传入一大堆参数，使用lambda表达式可以把其他的参数固定，这样gradcheck_naive()内部校验的时候只需要传入一个参数
打印naiveSoftmaxLossAndGradient()和negSamplingLossAndGradient()的计算结果。因为随机状态都被固定了，所以结果应该和预设的结果是一致的。如果不一致，那就是我们填充的代码出错了。

def test_word2vec():
    """ Test the two word2vec implementations, before running on Stanford Sentiment Treebank """
    dataset = type('dummy', (), {})() # 创建一个名为'dummy'，没有属性和方法的类的实例
    def dummySampleTokenIdx():
        """
        在[0, 4]之间随机取1个数。
        """
        return random.randint(0, 4)

    def getRandomContext(C):
        """
        Arguments:
        C -- 窗口的大小。
        Return:
        随机抽取的centerWord及对应的随机抽取的context。
        """
        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的sampleTokenIdx()方法
    dataset.getRandomContext = getRandomContext # 声明dataset的getRandomContext()方法

    random.seed(31415) # 设定随机数种子，保证每次的运行结果可复现
    np.random.seed(9265)
    dummy_vectors = normalizeRows(np.random.randn(10,3)) # 随机生成一个10行3列的矩阵，然后把每一行处理成单位向量，即L2范数等于1
    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]]
    """)

3. run.py

1) 检查Python的版本

# Check Python Version
import sys
assert sys.version_info[0] == 3
assert sys.version_info[1] >= 5

2) 初始化

固定随机数种子
载入数据集
定义嵌入的维度
定义窗口的大小

初始化词嵌入矩阵，

$V$ 和

$U$ 在axis=0的方向上拼接在一起，

$V$ 初始化为

$n\times d$ 的均匀分布矩阵，

$U$ 是零矩阵（个人认为这里使用随机正态矩阵初始化比较好）

# Reset the random seed to make sure that everyone gets the same results
random.seed(314)
dataset = StanfordSentiment()
tokens = dataset.tokens()
nWords = len(tokens)

# We are going to train 10-dimensional vectors for this assignment
dimVectors = 10

# Context size
C = 5

# Reset the random seed to make sure that everyone gets the same results
random.seed(31415)
np.random.seed(9265)

startTime=time.time()
wordVectors = np.concatenate(
    ((np.random.rand(nWords, dimVectors) - 0.5) /
       dimVectors, np.zeros((nWords, dimVectors))),
    axis=0)

3) 调用sgd()训练模型，即使用SGD降低损失函数

学习率0.3
迭代40000次
每隔固定的迭代次数(默认5000），保存训练参数和状态到文件
函数调用的顺序：sgd(), word2vec_sgd_wrapper(), skipgram(), negSamplingLossAndGradient()
使用 $\boldsymbol J_{\text {neg-sample}}$ 训练词嵌入矩阵，而不是 $\boldsymbol J_{\text {naive-softmax}}$ ，这样训练更快一些
训练完毕的矩阵 $V$ 就是我们想要的词嵌入矩阵

博主的Ubuntu 18.04，i7 8700 CPU，16G内存台式机一共训练了5156秒

wordVectors = sgd(
    lambda vec: word2vec_sgd_wrapper(skipgram, tokens, vec, dataset, C,
        negSamplingLossAndGradient),
    wordVectors, 0.3, 40000, None, True, PRINT_EVERY=10)
# Note that normalization is not called here. This is not a bug,
# normalizing during training loses the notion of length.

print("sanity check: cost at convergence should be around or below 10")
print("training took %d seconds" % (time.time() - startTime))

4) 可视化一些预设的单词

把单词转化为索引
按照索引取出词嵌入向量，结果是一个矩阵，记为temp
temp矩阵每个维度都减去该维度的平均值
计算temp矩阵的协方差矩阵，记为covariance
对covariance进行SVD分解
使用SVD分解的 $U$ 矩阵对temp进行降维（不是词嵌入的 $U$ 矩阵哦）
使用plt.text()画出降到二维的词向量

可以观察到训练的效果还不错

visualizeIdx = [tokens[word] for word in visualizeWords]
visualizeVecs = wordVectors[visualizeIdx, :]
temp = (visualizeVecs - np.mean(visualizeVecs, axis=0))
covariance = 1.0 / len(visualizeIdx) * temp.T.dot(temp)
U,S,V = np.linalg.svd(covariance)
coord = temp.dot(U[:,0:2])

for i in range(len(visualizeWords)):
    plt.text(coord[i,0], coord[i,1], visualizeWords[i],
        bbox=dict(facecolor='green', alpha=0.1))

plt.xlim((np.min(coord[:,0]), np.max(coord[:,0])))
plt.ylim((np.min(coord[:,1]), np.max(coord[:,1])))

plt.savefig('word_vectors.png')

word_vectors