cs224n学习笔记L2:word vectors and word senses
cs224n学习笔记L1:自然语言处理简介
目的：课堂结束后能够读懂词嵌入的论文。
二、 词向量计算方法 2.1 回顾word2vec计算对一个中心词，与窗口内的context词出现的概率：
P(o∣c)=exp(uoTvc)∑w∈Vexp(uwvc)(2.1)P(o|c) = \frac{exp(u_o^T v_c)}{\sum_{w \in V}exp(u_wv_c)} \tag{2.1}P(o∣c)=∑w∈Vexp(uwvc)exp(uoTvc)(2.1)
通过极大似然方法最大化整个文本出现的概率：
L(θ)=∏t=1T∏−m≤j≤m，j≠0P(wt+j∣wt,θ)L(\theta) = \prod_{t=1}^T\prod_{-m \le j \le m， j\ne0}P(w_{t+j}|w_t,\theta)L(θ)=t=1∏T−m≤j≤m，j=0∏P(wt+j∣wt,θ)
损失函数：
J(θ)=−1TlogL(θ)=−1T∑t=1T∑−m≤j≤m，j≠0logP(wt+j∣wt,θ)(2.2)J(\theta)=-\frac1TlogL(\theta)=-\frac1T\sum_{t=1}^T\sum_{-m \le j \le m， j\ne0}logP(w_{t+j}|w_t,\theta) \tag{2.2}J(θ)=−T1logL(θ)=−T1t=1∑T−m≤j≤m，j=0∑logP(wt+j∣wt,θ)(2.2)
假设vocabulary包含m个词，每个词向量长度为n, 对于每一个词，作为中心词(center)和非中心词(outside)时分别使用v和u两个向量表示。在计算完成后将两个向量平均作为最终词向量表示。
Um×n(outside)=[u1u2⋮um]U_{m \times n}(outside) = \left[ \begin{matrix}
u_1 \\
u_2 \\
\vdots \\
u_m
\end{matrix} \right] Um×n(outside)=⎣⎢⎢⎢⎡u1u2⋮um⎦⎥⎥⎥⎤
Vm×n(center)=[v1v2⋮vm] V_{m \times n} (center)= \left[ \begin{matrix}
v_1 \\
v_2 \\
\vdots \\
v_m
\end{matrix} \right]Vm×n(center)=⎣⎢⎢⎢⎡v1v2⋮vm⎦⎥⎥⎥⎤
对每一个词作为中心词时，计算概率分布。这里假定第4个词作为中心词时，有
Dm×1=Um×n⋅v4T=[d1d2⋮dm]D_{m \times 1} = U_{m \times n} \cdot v_4^T = \left[ \begin{matrix}
d_1 \\
d_2 \\
\vdots \\
d_m
\end{matrix}\right]Dm×1=Um×n⋅v4T=⎣⎢⎢⎢⎡d1d2⋮dm⎦⎥⎥⎥⎤
其中，d为与m个outside词的点积，由于两个向量的点乘可以表示其相似度，进一步可用于表示其出现的概率大小，从而得到概率表示：
Pm×1=softmax(Dm×1)=[p1p2⋮pm]P_{m \times 1} = softmax(D_{m \times 1}) = \left[ \begin{matrix}
p_1 \\
p_2 \\
\vdots \\
p_m
\end{matrix}\right]Pm×1=softmax(Dm×1)=⎣⎢⎢⎢⎡p1p2⋮pm⎦⎥⎥⎥⎤
这里原理就很明显了，我们接下来需要做的，就是通过优化问题来更新矩阵U和V，从而使词向量模型需对出现在同一个context中的词赋予较大的概率。
通过以上计算过程可以知道，如果两个词出现在一个context的次数越频繁，那么他们的词向量就会越接近，这样一来像the这样的高频词，就会使它前后的词向量高度集中，从而导致一些问题。
三、优化基础 3.1 梯度下降 梯度是指多元函数在某个点上升最快的方向，那么梯度的反方向当然就是下降最快的方向。从而得到直观的优化公式：θnew=θold−α∇θJ(θ)\theta_{new} = \theta_{old} - \alpha \nabla_{\theta}J(\theta)θnew=θold−α∇θJ(θ)
此处∇thetaJ(θ)\nabla_{theta}J(\theta)∇thetaJ(θ)为损失函数的梯度，α\alphaα为学习率或步长，是一个超参数。以上是对整个问题的矩阵表示，但在计算过程中，需要一个个的更新参数，所以有对单个参数θj\theta_jθj表示版本：
θjnew=θjold−α∂∂θjoldJ(θ) \theta _ { j } ^ { n e w } = \theta _ { j } ^ { o l d } - \alpha \frac { \partial } { \partial \theta _ { j } ^ { o l d } } J ( \theta ) θjnew=θjold−α∂θjold∂J(θ)
在高等数学（同济）中关于梯度的定义如下，及梯度是各个自变量的偏导组成的向量。
3.2 随机(stochastic)梯度下降（SGD）
3.1中提到的梯度下降，为了计算出参数的梯度，需要代入整个数据集，这样一次更新计算量非常大，因此提出随机梯度下降方法，即每一个更新都是从数据及中随机抽样部分数据（batch), 在词向量计算中对每一个window数据计算一次更新。
四、word vector优化过程 4.1 SGD引起的稀疏数据由于使用一个窗口更新一次，由于∇θJt(θ)\nabla_{\theta}J_t(\theta)∇θJt(θ)是各个词向量的偏导组成的向量，如果这个词没有出现，其偏导也就为0，因此梯度将非常稀疏。
对应方案：使用稀疏矩阵或者将词hash映射到具体向量，如果是分布式计算，必须避免大量的中间数据在节点之间的传送
4.2 两种词向量建模方案 Skip-gram(SG)：给定中心词预测窗口context(outsides) Continous Bag of Words(CBOW)：给定窗口context预测中心词 4.3 训练效率提升方案 负采样。目前为止仍然以更简单但是计算量大的传统softmax为主要方案, 即公式2.1中的分母（正则项）。 由于经典方案正则化计算量太大，因此我们在作业二中使用负采样方案。其主要思想为：训练一个logistics regression分类器， 判断一个词语对是否来自于同一个context。 损失函数：最大化如下函数：
在作业二中，使用的损失函数为：
Jneg−sample(o,vc,U)=−log(σ(uo⊤vc))−∑k=1,k∼P(w)Klog(σ(−uk⊤vc)) J _ { n e g - s a m p l e } \left( \boldsymbol { o } , \boldsymbol { v } _ { c } , \boldsymbol { U } \right) = - \log \left( \sigma \left( \boldsymbol { u } _ { o } ^ { \top } \boldsymbol { v } _ { c } \right) \right) - \sum _ {k = 1 , k \sim P(w) } ^ { K } \log \left( \sigma \left( - \boldsymbol { u } _ { k } ^ { \top } \boldsymbol { v } _ { c } \right) \right) Jneg−sample(o,vc,U)=−log(σ(uo⊤vc))−k=1,k∼P(w)∑Klog(σ(−uk⊤vc))
这里的P(w)P(w)P(w)为采样的概率分布，为了平衡高频词和低频次的影响，取P(w)=U(w)3/4ZP(w) = \frac{U(w)^{3/4}}{Z}P(w)=ZU(w)3/4, 这里U(w)U(w)U(w)为unigram分布，及按词频比例作为其概率分布，指数部分取3/4可以平滑词频的影响，分母Z表示正则化，将指数操作后（和不为1）的数值重新变为概率(和为1)。 4.4 统计共现(co-occurence)词对 存在问题：存储共现矩阵稀疏（O(n2)O(n^2)O(n2)内存） 解决办法：奇异值分解降维。可以使用numpy库中的np.lilalg.svd()函数。 五、验证及其他 5.1 两种验证方法 类比 训练完整的下游任务 5.2 其他
课程还介绍了很多词向量的其他细节、例如一词多义、词向量训练参数介绍及各种模型性能对比等，课程后半截听得有点迷糊，这里就不给出完整笔记了，如果以后需要冲刷再来补上。
六、作业 6.1 手写推导部分
感悟：当遇到矩阵或向量求导的时候，要每个元素拆开单独计算，第4小题比较典型。
一行文字说明下面两个公式等价，即交叉熵损失与naive-softmax。
Jcross−entropy=−∑ywlog(y^w)=−log(y^o)J_{cross-entropy}=- \sum y _ { w } \log \left( \hat { y } _ { w } \right) = - \log \left( \hat { y } _ { o } \right)Jcross−entropy=−∑ywlog(y^w)=−log(y^o)
Jnaive−softmax(vc,o,U)=−logP(O=o∣C=c)J_{naive-softmax}\left( \boldsymbol { v } _ { c } , o , \boldsymbol { U } \right) = - \log P ( O = o | C = c )Jnaive−softmax(vc,o,U)=−logP(O=o∣C=c)
答：由于ywy_wyw为0-1概率分布，因此Jcross−entropy=−∑ywlog(y^w)=−∑(0,1)⋅log(y^w)=−log(y^w1y^w2…y^wT)=−logP(O=o∣C=c)J_{cross-entropy} \\
=- \sum y _ { w } \log \left( \hat { y } _ { w } \right) \\
= - \sum (0,1) \cdot \log \left( \hat { y } _ { w } \right) \\
= - \log \left( \hat { y } _ { w1 } \hat { y } _ { w2 } \dots \hat { y } _ { wT } \right) \\
=- \log P( O = o | C = c )Jcross−entropy=−∑ywlog(y^w)=−∑(0,1)⋅log(y^w)=−log(y^w1y^w2…y^wT)=−logP(O=o∣C=c)
we know this deravatives:(这里第一种解法利用了softmax+交叉熵求导的一般规律，可以推导证明)
解法一：∵J=CE(y,y^)y^=softmax(θ) ∴∂J∂θ=(y^−y)T \because J = CE(y, \hat{y}) \\ \hat{y} = softmax(\theta)\ \\ \therefore \frac{\partial J}{\partial \theta} = (\hat{y} - y)^T ∵J=CE(y,y^)y^=softmax(θ) ∴∂θ∂J=(y^−y)T
yyy is a column vector in the above equation. So, we can use chain rules to solve the deravitive:
∂J∂vc=∂J∂θ∂θ∂vc =(y^−y)∂UTvc∂vc =UT(y^−y)T\begin{aligned} \frac{\partial J}{\partial v_c} &= \frac{\partial J}{\partial \theta} \frac{\partial \theta}{\partial v_c} \ &= (\hat{y} - y) \frac{\partial U^Tv_c}{\partial v_c} \ &= U^T(\hat{y} - y)^T \end{aligned}∂vc∂J=∂θ∂J∂vc∂θ =(y^−y)∂vc∂UTvc =UT(y^−y)T
解法二：
∂J(vc,o,U)∂vc=−∂(uoTvc)∂vc+∂(log(∑wexp(uwTvc)))∂vc=−uo+1∑wexp(uwTvc)∂(∑wexp(uwTvc))∂vc=−uo+∑wexp(uwTvc)uw∑wexp(uwTvc)=−uo+∑wp(O=w∣C=c)uw=−youo+∑wy^wuw(单个uo)=−UTy+UTy^(全体u，这里限定O=o所以U实际代表一行）=UT(y^−y)\begin{aligned}
\frac{\partial J\left(v_{c}, o, U\right)}{\partial v_{c}} &=-\frac{\partial\left(u_{o}^{T} v_{c}\right)}{\partial v_{c}}+\frac{\partial\left(\log \left(\sum_{w} \exp \left(u_{w}^{T} v_{c}\right)\right)\right)}{\partial v_{c}} \\
&=-u_{o}+\frac{1}{\sum_{w} \exp \left(u_{w}^{T} v_{c}\right)} \frac{\partial\left(\sum_{w} \exp \left(u_{w}^{T} v_{c}\right)\right)}{\partial v_{c}} \\
&=-u_{o}+\sum_{w} \frac{\exp \left(u_{w}^{T} v_{c}\right) u_{w}}{\sum_{w} \exp \left(u_{w}^{T} v_{c}\right)} \\
&=-u_{o}+\sum_{w} p(O=w | C=c) u_{w} \\
&=-y_ou_o+\sum_w\hat y_wu_w (单个u_o)\\
&=-U^T\boldsymbol{y} + U^T\boldsymbol{\hat y}(全体u，这里限定O=o所以U实际代表一行） \\
&=U^{T}(\hat{y}-y)
\end{aligned}∂vc∂J(vc,o,U)=−∂vc∂(uoTvc)+∂vc∂(log(∑wexp(uwTvc)))=−uo+∑wexp(uwTvc)1∂vc∂(∑wexp(uwTvc))=−uo+w∑∑wexp(uwTvc)exp(uwTvc)uw=−uo+w∑p(O=w∣C=c)uw=−youo+w∑y^wuw(单个uo)=−UTy+UTy^(全体u，这里限定O=o所以U实际代表一行）=UT(y^−y)
similar to the equation above. ∂J∂vc=∂J∂θ∂θ∂U =(y^−y)∂UTvc∂U =vc(y^−y)T\begin{aligned} \frac{\partial J}{\partial v_c} &= \frac{\partial J}{\partial \theta} \frac{\partial \theta}{\partial U} \ &= (\hat{y} - y) \frac{\partial U^Tv_c}{\partial U} \ &= v_c(\hat{y} - y)^T \end{aligned}∂vc∂J=∂θ∂J∂U∂θ =(y^−y)∂U∂UTvc =vc(y^−y)T
xxx为一个向量，求sigmod函数对x的偏导，结果可以用σ(x)表示\sigma(x)表示σ(x)表示。
σ(x)=11+e−x=ex1+ex\sigma(x)= \frac{1}{1+e^{-x}}=\frac{e^x}{1+e^x}σ(x)=1+e−x1=1+exex
答：sigmod(x)=11+e−xsigmod(x) = \frac{1}{1+e^{-x}}sigmod(x)=1+e−x1, 由于x为一个向量x=(x1,x2,…,xn)x=(x_1, x_2, \dots, x_n)x=(x1,x2,…,xn)，而求导实际上是针对单个变量, 由于σ(x)\sigma(x)σ(x)是x的函数，所以求导结果应该是一个矩阵：
∂σ(xi)∂xi=e−xi(1+e−xi)2=(1+e−xi)−1(1+e−xi)2=σ(x)(1−σ(x))∂σ(xi)∂xj=0∴∂σ(x)∂x=[σ′(x1)0…00σ′(x2)…0⋮⋮⋱⋮00…σ′(xn)]\begin{aligned}
\frac{\partial \sigma(x_i)}{\partial x_i} & = \frac{e^{-x_i}}{(1+e^{-x_i})^2} =\frac{(1+e^{-x_i})-1}{(1+e^{-x_i})^2} = \sigma(x)(1-\sigma(x))\\
\frac{\partial \sigma(x_i)}{\partial x_j} & = 0 \\
\therefore \frac{\partial \sigma(x)}{\partial x} &=
\left[\begin{matrix}
\sigma'(x_1) & 0 & \ldots &0 \\
0 & \sigma'(x_2) & \ldots &0 \\
\vdots & \vdots & \ddots& \vdots\\
0 &0 & \ldots & \sigma'(x_n)\\
\end{matrix} \right]
\end{aligned} ∂xi∂σ(xi)∂xj∂σ(xi)∴∂x∂σ(x)=(1+e−xi)2e−xi=(1+e−xi)2(1+e−xi)−1=σ(x)(1−σ(x))=0=⎣⎢⎢⎢⎡σ′(x1)0⋮00σ′(x2)⋮0……⋱…00⋮σ′(xn)⎦⎥⎥⎥⎤
sigmod 函数有一些特性： (1) σ(−x)=1−σ(x)\sigma(-x) = 1-\sigma(x)σ(−x)=1−σ(x) (2) σ′(x)=σ(x)(1−σ(x))\sigma'(x) = \sigma(x)(1-\sigma(x))σ′(x)=σ(x)(1−σ(x))
题目描述如图
答：根据第四题有(1)∂J∂vc=−σ′(uoTvc)uoσ(uoTvv)+∑k=1Kσ′(−ukTvc)ukσ(−ukTvc)=(σ(uoTvc)−1)uo+∑k=1K(1−σ(−ukTvc))uk=(σ(uoTvc)−1)uo+∑k=1Kσ(ukTvc)uk(2)∂J∂uo=(σ(uoTvc)−1)vc(o∉K)(3)∂J∂uk=σ(ukTvc)vc\begin{aligned} (1) \frac{\partial J}{\partial v_c} & = -\frac{\sigma'(u_o^Tv_c)u_o}{\sigma(u_o^Tv_v)} + \sum_{k=1}^K \frac{\sigma'(-u_k^Tv_c)u_k}{\sigma(-u_k^Tv_c)} \\ &=(\sigma(u_o^Tv_c)-1)u_o+\sum_{k=1}^K(1-\sigma(-u_k^Tv_c))u_k \\ & =(\sigma(u_o^Tv_c)-1)u_o+\sum_{k=1}^K\sigma(u_k^Tv_c)u_k \\ (2)\frac{\partial J}{\partial u_o} &= (\sigma(u_o^Tv_c)-1)v_c (o \notin K)\\ (3)\frac{\partial J}{\partial u_k} &=\sigma(u_k^Tv_c)v_c \end{aligned}(1)∂vc∂J(2)∂uo∂J(3)∂uk∂J=−σ(uoTvv)σ′(uoTvc)uo+k=1∑Kσ(−ukTvc)σ′(−ukTvc)uk=(σ(uoTvc)−1)uo+k=1∑K(1−σ(−ukTvc))uk=(σ(uoTvc)−1)uo+k=1∑Kσ(ukTvc)uk=(σ(uoTvc)−1)vc(o∈/K)=σ(ukTvc)vc
从偏导可以看出，梯度更新时，使用负采样计算的参数量远远小于naive-softmax。 6.2 代码
github链接
实现word2vec, 实际上是在课程代码框架下填充部分代码。
这次课程完成时间比较长，当然收货也比较大，复习了一遍高数，终于勉强搞懂了矩阵向量求导，算是推公式入门选手了吧。
作者：geek_hch
