CS224N WINTER 2022（一）词向量（附Assignment1答案）
CS224N WINTER 2022（二）反向传播、神经网络、依存分析（附Assignment2答案）
CS224N WINTER 2022（三）RNN、语言模型、梯度消失与梯度爆炸（附Assignment3答案）
CS224N WINTER 2022（四）机器翻译、注意力机制、subword模型（附Assignment4答案）
CS224N WINTER 2022（五）Transformers详解（附Assignment5答案）

序言

文章目录

lecture 3 反向传播与神经网络

本节内容属于基础的机器学习与深度学习知识。

slides

[slides]

  1. 矩阵（向量）链式求导中的计算技巧：slides p.39

    假定一个神经网络的运算步骤如下所示：
    x ( input ) → z = W x + b → h = f ( z ) → s = u ⊤ h (3.1) x(\text{input})\rightarrow z=Wx+b\rightarrow h=f(z)\rightarrow s=u^\top h\tag{3.1} x(input)→z=Wx+b→h=f(z)→s=u⊤h(3.1)
    则计算网络参数 W W W与 b b b的参数时：
    ∂ s ∂ W = ∂ s ∂ h ∂ h ∂ z ∂ z ∂ W ∂ s ∂ b = ∂ s ∂ h ∂ h ∂ z ∂ z ∂ b (3.2) \frac{\partial s}{\partial W}=\frac{\partial s}{\partial h}\frac{\partial h}{\partial z}\frac{\partial z}{\partial W}\quad\frac{\partial s}{\partial b}=\frac{\partial s}{\partial h}\frac{\partial h}{\partial z}\frac{\partial z}{\partial b}\tag{3.2} ∂W∂s​=∂h∂s​∂z∂h​∂W∂z​∂b∂s​=∂h∂s​∂z∂h​∂b∂z​(3.2)
    可以定义局部误差信号（local error signal）：
    δ = ∂ s ∂ h ∂ h ∂ z = u ⊤ ∘ f ′ ( z ) (3.3) \delta=\frac{\partial s}{\partial h}\frac{\partial h}{\partial z}=u^\top\circ f'(z)\tag{3.3} δ=∂h∂s​∂z∂h​=u⊤∘f′(z)(3.3)
    则可以使得计算 ( 3.2 ) (3.2) (3.2)式的更加简单，事实上进一步计算可以发现：
    ∂ s ∂ W = ∂ s ∂ h ∂ h ∂ z ∂ z ∂ W = δ ∂ z ∂ W = δ ⊤ x ⊤ ∂ s ∂ b = ∂ s ∂ h ∂ h ∂ z ∂ z ∂ b = δ ∂ z ∂ b = δ (3.4) \begin{aligned} \frac{\partial s}{\partial W}&=\frac{\partial s}{\partial h}\frac{\partial h}{\partial z}\frac{\partial z}{\partial W}=\delta\frac{\partial z}{\partial W}=\delta^\top x^\top\\ \frac{\partial s}{\partial b}&=\frac{\partial s}{\partial h}\frac{\partial h}{\partial z}\frac{\partial z}{\partial b}=\delta\frac{\partial z}{\partial b}=\delta \end{aligned}\tag{3.4} ∂W∂s​∂b∂s​​=∂h∂s​∂z∂h​∂W∂z​=δ∂W∂z​=δ⊤x⊤=∂h∂s​∂z∂h​∂b∂z​=δ∂b∂z​=δ​(3.4)
    此时我们称 x x x是局部输入信号（local input signal）。

    这就是反向传播高效的原因，事实上只需要在神经网络的每条传播路径上存储两端节点变量的偏导值（如神经网络中节点 z z z指向节点 h h h，则存储 ∂ h / ∂ z \partial h/\partial z ∂h/∂z），即可快速计算任意两个节点变量之间的偏导值。

  2. 广义计算图中的反向传播（General Computation Graph）：slides p.77
    ∂ z ∂ x = ∑ i = 1 n ∂ z ∂ y i ∂ y i ∂ x (3.5) \frac{\partial z}{\partial x}=\sum_{i=1}^n\frac{\partial z}{\partial y_i}\frac{\partial y_i}{\partial x}\tag{3.5} ∂x∂z​=i=1∑n​∂yi​∂z​∂x∂yi​​(3.5)
    其中 { y 1 , y 2 , . . . , y n } \{y_1,y_2,...,y_n\} {y1​,y2​,...,yn​}是 x x x指向的所有节点。

notes

[notes]

  1. 神经网络中的常用技巧：notes p.8-18

    • 梯度检验：

      自动梯度计算一般使用的是数值近似的方法：
      f ′ ( x ) ≈ f ( x + ϵ ) − f ( x ) ϵ (3.6) f'(x)\approx \frac{f(x+\epsilon)-f(x)}{\epsilon}\tag{3.6} f′(x)≈ϵf(x+ϵ)−f(x)​(3.6)
      而非解析方法，因此总是存在一定的误差（特殊情况下可能就是错误的）。

      梯度检验是一种用来比较数值梯度值与解析梯度值之间差距的方法。下面是一个简单的demo：

      def eval_numerical_gradient(f, x):
	"""
	a naive implementation of numerical gradient of f at x
	- f should be a function that takes a single argument
	- x is the point (numpy array) to evaluate the gradient
	at
	"""
	fx = f(x) # evaluate function value at original point
	grad = np.zeros(x.shape)
	h = 0.00001
	
	# iterate over all indexes in x
	it = np.nditer(x, flags=['multi_index'], op_flags = ['readwrite'])
	
	while not it.finished:
		# evaluate function at x+h
		ix = it.multi_index
		old_value = x[ix]
		x[ix] = old_value + h                       # increment by h
		fxh_left = f(x)                             # evaluate f(x + h)
		x[ix] = old_value - h                       # decrement by h
		fxh_right = f(x)                            # evaluate f(x - h)
		x[ix] = old_value                           # restore to previous value (very important!)
		
		# compute the partial derivative
		grad[ix] = (fxh_left - fxh_right) / (2 * h) # the slope
		it.iternext()                               # step to next dimension
		
	return grad

    • 正则化：常用于处理模型过拟合的问题，一般是在损失函数中引入模型参数矩阵的 F F F范数（相当于是所有参数的二范数值）。

    • Dropout：常用于处理模型过拟合与降低模型复杂度。在反向传播中以一定概率剪除神经网络的传播路径。

    • 激活函数：Sigmoid，Tanh，Hard tanh，Soft sign，ReLU，Leaky ReLU

    • 数据预处理：减均值（中心化），正则化，白化（去除特征之间的相关性，如通过奇异值分解）。

    • 参数初始化：这个其实还是有讲究的，参数初始值的确对模型优化可能产生显著影响，有兴趣可以扒扒PyTorch中的参数初始化源码，是有很多不同的初始化方式的。如果我记得没错的话，PyTorch中绝大多数层的参数初始化用的都是本节中提到的这种方式：
      W ∼ Uniform ( − 6 n ( l ) + n ( l + 1 ) , 6 n ( l ) + n ( l + 1 ) ) (3.7) W\sim\text{Uniform}\left(-\sqrt{\frac{6}{n^{(l)}+n^{(l+1)}}},\sqrt{\frac{6}{n^{(l)}+n^{(l+1)}}}\right)\tag{3.7} W∼Uniform(−n(l)+n(l+1)6​ ​,n(l)+n(l+1)6​ ​)(3.7)
      其中 n ( l ) n^{(l)} n(l)是参数矩阵 W W W的fan-in值（输入节点数）， n ( l + 1 ) n^{(l+1)} n(l+1)是参数矩阵 W W W的fan-out值（输出节点数）。

      截距项一般初始化都是零。

    • 学习策略：学习率可以进行动态调整，有兴趣可以查看PyTorch中与lr_scheduler相关的内容。

    • 动量更新：梯度下降法一个变体。

      # Computes a standard momentum update
# on parameters x
v = mu*v - alpha*grad_x
x += v

    • 自适应优化方法（Adaptive Optimization Methods）：如经典的AdaGrad，Adam应该都属于这类方法。RMSProp是AdaGrad的一种变体。

      # Assume the gradient dx and parameter vector x
cache += dx**2
x += - learning_rate * dx / np.sqrt(cache + 1e-8)

# Update rule for RMS prop
cache = decay_rate * cache + (1 - decay_rate) * dx ** 2
x += - learning_rate * dx / (np.sqrt(cache) + eps)

# Update rule for Adam
m = beta1 * m + (1 - beta1) * dx
v = beta2 * v + (1 - beta2) * (dx ** 2)
x += - learning_rate * m / (np.sqrt(v) + eps)

suggested readings

  1. 矩阵运算相关（主要是求导）在神经网络中的应用。（matrix calculus notes）

  2. 各种多元函数、矩阵函数的求导方法汇总。（Review of differential calculus）

  3. 神经网络架构的基础知识，与slides及notes的内容有一定重合。（CS231n notes on network architectures）

  4. 反向传播重点讲解，包含一些代码示例。（CS231n notes on backprop）

  5. 从求导开始阐述反向传播的数学推导。（Derivatives, Backpropagation, and Vectorization）

  6. 1986年的一篇关于反向传播的老古董paper，反向传播首次提出？。（Learning Representations by Backpropagating Errors）

additional readings

  1. 一篇发布于2016年的反向传播博客。（Yes you should understand backprop）

  2. 本节唯一一篇属于paper的阅读内容，感觉更像是一部长篇教材，既讲了神经网络的基础知识，也讲了神经网络在若干自然语言处理任务中的应用，感觉写得很乱。不过也是2011年的内容，可能比较过时。（Natural Language Processing (Almost) from Scratch）

assignment2 参考答案

[code] [handout] [latex template]

Assignment2参考答案（written+coding）：囚生CYのGitHub Repository

1. written

  • ( a ) (a) (a) 根据定义可知：
    y w = { 1 if  w = o 0 otherwise ⇒ LHS = − ∑ w ∈ Vocab y w log ⁡ ( y ^ w ) = − y o log ⁡ ( y ^ o ) = − log ⁡ ( y ^ o ) = RHS (a2.1.1) y_w=\left\{\begin{aligned} &1&&\text{if }w=o\\ &0&&\text{otherwise} \end{aligned}\right.\Rightarrow \text{LHS}=-\sum_{w\in\text{Vocab}}y_w\log(\hat y_w)=-y_o\log(\hat y_o)=-\log(\hat y_o)=\text{RHS} \tag{a2.1.1} yw​={​10​​if w=ootherwise​⇒LHS=−w∈Vocab∑​yw​log(y^​w​)=−yo​log(y^​o​)=−log(y^​o​)=RHS(a2.1.1)

  • ( b ) (b) (b) 本问可参考[slides]中 29-31 \text{29-31} 29-31页的推导过程：
    ∂ J naive-softmax ( v c , o , U ) ∂ v c = − ∂ ∂ v c log ⁡ P ( O = o ∣ C = c ) = − ∂ ∂ v c log ⁡ exp ⁡ ( u o ⊤ v c ) ∑ w ∈ V exp ⁡ ( u w ⊤ v c ) = − ∂ ∂ v c log ⁡ exp ⁡ ( u o ⊤ v c ) + ∂ ∂ v c log ⁡ ( ∑ w ∈ V exp ⁡ ( u w ⊤ v c ) ) = − ∂ ∂ v c u o ⊤ v c + 1 ∑ w ∈ V exp ⁡ ( u w ⊤ v c ) ⋅ ∂ ∂ v c ∑ x ∈ V exp ⁡ ( u x ⊤ v c ) = − u o + 1 ∑ w ∈ V exp ⁡ ( u w ⊤ v c ) ⋅ ∑ x ∈ V ∂ ∂ v c exp ⁡ ( u x ⊤ v c ) = − u o + 1 ∑ w ∈ V exp ⁡ ( u w ⊤ v c ) ⋅ ∑ x ∈ V exp ⁡ ( u x ⊤ v c ) ∂ ∂ v c u x ⊤ v c = − u o + 1 ∑ w ∈ V exp ⁡ ( u w ⊤ v c ) ∑ x ∈ V exp ⁡ ( u x ⊤ v c ) u x = − u o + ∑ x ∈ V exp ⁡ ( u x ⊤ v c ) ∑ w ∈ V exp ⁡ ( u w ⊤ v c ) u x = − u o + ∑ x ∈ V P ( O = x ∣ C = c ) u x = − u o + ∑ x ∈ V y ^ x u x = − U ⊤ y + U ⊤ y ^ = U ⊤ ( y ^ − y ) (a2.1.2) \begin{aligned} \frac{\partial J_{\text{naive-softmax}}(v_c,o,U)}{\partial v_c}&=-\frac{\partial}{\partial v_c}\log P(O=o|C=c)\\ &=-\frac{\partial}{\partial v_c}\log\frac{\exp(u_o^\top v_c)}{\sum_{w\in V}\exp(u_w^\top v_c)}\\ &=-\frac{\partial}{\partial v_c}\log\exp(u_o^\top v_c)+\frac{\partial}{\partial v_c}\log\left(\sum_{w\in V}\exp(u_w^\top v_c)\right)\\ &=-\frac{\partial}{\partial v_c}u_o^\top v_c+\frac{1}{\sum_{w\in V}\exp(u_w^\top v_c)}\cdot\frac{\partial}{\partial v_c}\sum_{x\in V}\exp(u_x^\top v_c)\\ &=-u_o+\frac{1}{\sum_{w\in V}\exp(u_w^\top v_c)}\cdot\sum_{x\in V}\frac{\partial}{\partial v_c}\exp(u_x^\top v_c)\\ &=-u_o+\frac{1}{\sum_{w\in V}\exp(u_w^\top v_c)}\cdot\sum_{x\in V}\exp(u_x^\top v_c)\frac{\partial}{\partial v_c}u_x^\top v_c\\ &=-u_o+\frac{1}{\sum_{w\in V}\exp(u_w^\top v_c)}\sum_{x\in V}\exp(u_x^\top v_c)u_x\\ &=-u_o+\sum_{x\in V}\frac{\exp(u_x^\top v_c)}{\sum_{w\in V}\exp(u_w^\top v_c)}u_x\\ &=-u_o+\sum_{x\in V}P(O=x|C=c)u_x\\ &=-u_o+\sum_{x\in V}\hat y_xu_x\\ &=-U^\top y+U^\top \hat y\\ &=U^\top(\hat y-y) \end{aligned}\tag{a2.1.2} ∂vc​∂Jnaive-softmax​(vc​,o,U)​​=−∂vc​∂​logP(O=o∣C=c)=−∂vc​∂​log∑w∈V​exp(uw⊤​vc​)exp(uo⊤​vc​)​=−∂vc​∂​logexp(uo⊤​vc​)+∂vc​∂​log(w∈V∑​exp(uw⊤​vc​))=−∂vc​∂​uo⊤​vc​+∑w∈V​exp(uw⊤​vc​)1​⋅∂vc​∂​x∈V∑​exp(ux⊤​vc​)=−uo​+∑w∈V​exp(uw⊤​vc​)1​⋅x∈V∑​∂vc​∂​exp(ux⊤​vc​)=−uo​+∑w∈V​exp(uw⊤​vc​)1​⋅x∈V∑​exp(ux⊤​vc​)∂vc​∂​ux⊤​vc​=−uo​+∑w∈V​exp(uw⊤​vc​)1​x∈V∑​exp(ux⊤​vc​)ux​=−uo​+x∈V∑​∑w∈V​exp(uw⊤​vc​)exp(ux⊤​vc​)​ux​=−uo​+x∈V∑​P(O=x∣C=c)ux​=−uo​+x∈V∑​y^​x​ux​=−U⊤y+U⊤y^​=U⊤(y^​−y)​(a2.1.2)
    式 ( 1.2 ) (1.2) (1.2)沿用[notes]中的标记，即约定 U ∈ R ∣ V ∣ × n , y ∈ R ∣ V ∣ , y ^ ∈ R ∣ V ∣ U\in\R^{|V|\times n},y\in\R^{|V|},\hat y\in\R^{|V|} U∈R∣V∣×n,y∈R∣V∣,y^​∈R∣V∣，具体如下：
    U = [ u 0 u 1 . . . u ∣ V ∣ ] ⊤ y = [ 0 0 . . . 1 . . . 0 ] ⊤ y ^ = [ y ^ 0 y ^ 1 . . . y ^ o . . . y ^ ∣ V ∣ ] ⊤ (a2.1.3) \begin{aligned} U&=\left[\begin{matrix}u_0&u_1&...&u_{|V|}\end{matrix}\right]^\top\\ y&=\left[\begin{matrix}0&0&...&1&...&0\end{matrix}\right]^\top\\ \hat y&=\left[\begin{matrix}\hat y_0&\hat y_1&...&\hat y_o&...&\hat y_{|V|}\end{matrix}\right]^\top \end{aligned}\tag{a2.1.3} Uyy^​​=[u0​​u1​​...​u∣V∣​​]⊤=[0​0​...​1​...​0​]⊤=[y^​0​​y^​1​​...​y^​o​​...​y^​∣V∣​​]⊤​(a2.1.3)

    • ( 1 ) (1) (1) 当 y ^ = y \hat y=y y^​=y时，梯度为零；
    • ( 2 ) (2) (2) 我理解这个问题可能是想说梯度值实际刻画的是观测值与真实值之间误差，因此减去这个误差可以地得到更可靠的 v c v_c vc​

  • ( c ) (c) (c) 类似 ( b ) (b) (b)中的推导，我们有：
    ∂ J naive-softmax ( v c , o , U ) ∂ u w = − ∂ ∂ u w log ⁡ P ( O = o ∣ C = c ) = − ∂ ∂ u w log ⁡ exp ⁡ ( u o ⊤ v c ) ∑ w ∈ V exp ⁡ ( u w ⊤ v c ) = − ∂ ∂ u w log ⁡ exp ⁡ ( u o ⊤ v c ) + ∂ ∂ u w log ⁡ ( ∑ w ∈ V exp ⁡ ( u w ⊤ v c ) ) = − ∂ ∂ u w u o ⊤ v c + 1 ∑ w ∈ V exp ⁡ ( u w ⊤ v c ) ⋅ ∂ ∂ u w ∑ x ∈ V exp ⁡ ( u x ⊤ v c ) = − ∂ ∂ u w u o ⊤ v c + 1 ∑ w ∈ V exp ⁡ ( u w ⊤ v c ) ∂ ∂ u w exp ⁡ ( u w ⊤ v c ) = − ∂ ∂ u w u o ⊤ v c + exp ⁡ ( u w ⊤ v c ) ∑ w ∈ V exp ⁡ ( u w ⊤ v c ) v c = − ∂ ∂ u w u o ⊤ v c + P ( O = w ∣ C = c ) v c = − ∂ ∂ u w u o ⊤ v c + y ^ w v c = { ( y ^ w − 1 ) v c if  w = o y ^ w v c otherwise = ( y ^ w − y w ) v c (a2.1.4) \begin{aligned} \frac{\partial J_{\text{naive-softmax}}(v_c,o,U)}{\partial u_w}&=-\frac{\partial}{\partial u_w}\log P(O=o|C=c)\\ &=-\frac{\partial}{\partial u_w}\log\frac{\exp(u_o^\top v_c)}{\sum_{w\in V}\exp(u_w^\top v_c)}\\ &=-\frac{\partial}{\partial u_w}\log\exp(u_o^\top v_c)+\frac{\partial}{\partial u_w}\log\left(\sum_{w\in V}\exp(u_w^\top v_c)\right)\\ &=-\frac{\partial}{\partial u_w}u_o^\top v_c+\frac{1}{\sum_{w\in V}\exp(u_w^\top v_c)}\cdot\frac{\partial}{\partial u_w}\sum_{x\in V}\exp(u_x^\top v_c)\\ &=-\frac{\partial}{\partial u_w}u_o^\top v_c+\frac{1}{\sum_{w\in V}\exp(u_w^\top v_c)}\frac{\partial}{\partial u_w}\exp(u_w^\top v_c)\\ &=-\frac{\partial}{\partial u_w}u_o^\top v_c+\frac{\exp(u_w^\top v_c)}{\sum_{w\in V}\exp(u_w^\top v_c)}v_c\\ &=-\frac{\partial}{\partial u_w}u_o^\top v_c+P(O=w|C=c)v_c\\ &=-\frac{\partial}{\partial u_w}u_o^\top v_c+\hat y_wv_c\\ &=\left\{\begin{aligned} &(\hat y_w-1)v_c&&\text{if }w=o\\ &\hat y_wv_c&&\text{otherwise} \end{aligned}\right.\\ &=(\hat y_w-y_w)v_c \end{aligned}\tag{a2.1.4} ∂uw​∂Jnaive-softmax​(vc​,o,U)​​=−∂uw​∂​logP(O=o∣C=c)=−∂uw​∂​log∑w∈V​exp(uw⊤​vc​)exp(uo⊤​vc​)​=−∂uw​∂​logexp(uo⊤​vc​)+∂uw​∂​log(w∈V∑​exp(uw⊤​vc​))=−∂uw​∂​uo⊤​vc​+∑w∈V​exp(uw⊤​vc​)1​⋅∂uw​∂​x∈V∑​exp(ux⊤​vc​)=−∂uw​∂​uo⊤​vc​+∑w∈V​exp(uw⊤​vc​)1​∂uw​∂​exp(uw⊤​vc​)=−∂uw​∂​uo⊤​vc​+∑w∈V​exp(uw⊤​vc​)exp(uw⊤​vc​)​vc​=−∂uw​∂​uo⊤​vc​+P(O=w∣C=c)vc​=−∂uw​∂​uo⊤​vc​+y^​w​vc​={​(y^​w​−1)vc​y^​w​vc​​​if w=ootherwise​=(y^​w​−yw​)vc​​(a2.1.4)

  • ( d ) (d) (d) 根据 ( c ) (c) (c)中的结果，可得：
    ∂ J naive-softmax ( v c , o , U ) ∂ U = ( y ^ − y ) ⊤ v c (a2.1.5) \frac{\partial J_{\text{naive-softmax}}(v_c,o,U)}{\partial U}=(\hat y-y)^\top v_c\tag{a2.1.5} ∂U∂Jnaive-softmax​(vc​,o,U)​=(y^​−y)⊤vc​(a2.1.5)

  • ( e ) (e) (e) 将 ReLU \text{ReLU} ReLU激活函数写作分段形式分别求导：
    f ( x ) = { 0 if  x < 0 x if  x > 0 ⇒ f ′ ( x ) = { 0 if  x < 0 1 if  x > 0 (a2.1.6) f(x)=\left\{\begin{aligned} &0&&\text{if }x\lt 0\\ &x&&\text{if }x\gt 0 \end{aligned}\right.\Rightarrow f'(x)=\left\{\begin{aligned} &0&&\text{if }x\lt 0\\ &1&&\text{if }x\gt 0 \end{aligned}\right.\tag{a2.1.6} f(x)={​0x​​if x<0if x>0​⇒f′(x)={​01​​if x<0if x>0​(a2.1.6)

  • ( f ) (f) (f) 有如下推导：
    σ ′ ( x ) = e x ( e x + 1 ) − e 2 x ( e x + 1 ) 2 = e x ( e x + 1 ) 2 = σ ( x ) ( 1 − σ ( x ) ) (a2.1.7) \sigma'(x)=\frac{e^x(e^x+1)-e^{2x}}{(e^x+1)^2}=\frac{e^x}{(e^x+1)^2}=\sigma(x)(1-\sigma(x))\tag{a2.1.7} σ′(x)=(ex+1)2ex(ex+1)−e2x​=(ex+1)2ex​=σ(x)(1−σ(x))(a2.1.7)

  • ( g ) (g) (g) 关于负采样的内容可参考[notes]与[slides]的相关章节。

    • ( 1 ) (1) (1) 关于 v c v_c vc​的偏导有如下推导：
      ∂ J neg-sample ( v c , o , U ) ∂ v c = − ∂ ∂ v c log ⁡ σ ( u o ⊤ v c ) − ∑ s = 1 K ∂ ∂ v c log ⁡ σ ( − u w s ⊤ v c ) = − σ ( u o ⊤ v c ) ( 1 − σ ( u o ⊤ v c ) ) σ ( u o ⊤ v c ) ⋅ ∂ u o ⊤ v c ∂ v c − ∑ s = 1 K σ ( − u w s ⊤ v c ) ( 1 − σ ( − u w s ⊤ v c ) ) σ ( − u w s ⊤ v c ) ∂ − u w s ⊤ v c ∂ v c = ( σ ( u o ⊤ v c ) − 1 ) u o + ∑ s = 1 K ( 1 − σ ( − u w s ⊤ v c ) ) u w s (a2.1.8) \begin{aligned} \frac{\partial J_{\text{neg-sample}}(v_c,o,U)}{\partial v_c}&=-\frac{\partial}{\partial v_c}\log\sigma(u_o^\top v_c)-\sum_{s=1}^K\frac{\partial}{\partial v_c}\log \sigma(-u_{w_s}^\top v_c)\\ &=-\frac{\sigma(u_o^\top v_c)(1-\sigma(u_o^\top v_c))}{\sigma(u_o^\top v_c)}\cdot \frac{\partial u_o^\top v_c}{\partial v_c}-\sum_{s=1}^{K}\frac{\sigma(-u_{w_s}^\top v_c)(1-\sigma(-u_{w_s}^\top v_c))}{\sigma(-u_{w_s}^\top v_c)}\frac{\partial-u_{w_s}^\top v_c}{\partial v_c}\\ &=(\sigma(u_o^\top v_c)-1)u_o+\sum_{s=1}^K(1-\sigma(-u_{w_s}^\top v_c))u_{w_s} \end{aligned} \tag{a2.1.8} ∂vc​∂Jneg-sample​(vc​,o,U)​​=−∂vc​∂​logσ(uo⊤​vc​)−s=1∑K​∂vc​∂​logσ(−uws​⊤​vc​)=−σ(uo⊤​vc​)σ(uo⊤​vc​)(1−σ(uo⊤​vc​))​⋅∂vc​∂uo⊤​vc​​−s=1∑K​σ(−uws​⊤​vc​)σ(−uws​⊤​vc​)(1−σ(−uws​⊤​vc​))​∂vc​∂−uws​⊤​vc​​=(σ(uo⊤​vc​)−1)uo​+s=1∑K​(1−σ(−uws​⊤​vc​))uws​​​(a2.1.8)
      关于 u o u_o uo​的偏导有如下推导：
      ∂ J neg-sample ( v c , o , U ) ∂ u o = − ∂ ∂ u o log ⁡ σ ( u o ⊤ v c ) − ∑ s = 1 K ∂ ∂ u o log ⁡ σ ( − u w s ⊤ v c ) = − σ ( u o ⊤ v c ) ( 1 − σ ( u o ⊤ v c ) ) σ ( u o ⊤ v c ) ⋅ ∂ u o ⊤ v c ∂ u o = ( σ ( u o ⊤ v c ) − 1 ) v c (a2.1.9) \begin{aligned} \frac{\partial J_{\text{neg-sample}}(v_c,o,U)}{\partial u_o}&=-\frac{\partial}{\partial u_o}\log\sigma(u_o^\top v_c)-\sum_{s=1}^K\frac{\partial}{\partial u_o}\log \sigma(-u_{w_s}^\top v_c)\\ &=-\frac{\sigma(u_o^\top v_c)(1-\sigma(u_o^\top v_c))}{\sigma(u_o^\top v_c)}\cdot \frac{\partial u_o^\top v_c}{\partial u_o}\\ &=(\sigma(u_o^\top v_c)-1)v_c \end{aligned} \tag{a2.1.9} ∂uo​∂Jneg-sample​(vc​,o,U)​​=−∂uo​∂​logσ(uo⊤​vc​)−s=1∑K​∂uo​∂​logσ(−uws​⊤​vc​)=−σ(uo⊤​vc​)σ(uo⊤​vc​)(1−σ(uo⊤​vc​))​⋅∂uo​∂uo⊤​vc​​=(σ(uo⊤​vc​)−1)vc​​(a2.1.9)
      关于 u w s u_{w_s} uws​​的偏导有如下推导：
      ∂ J neg-sample ( v c , o , U ) ∂ u w s = − ∂ ∂ u w s log ⁡ σ ( u o ⊤ v c ) − ∑ k = 1 K ∂ ∂ u w s log ⁡ σ ( − u w k ⊤ v c ) = − ∑ k = 1 K σ ( − u w k ⊤ v c ) ( 1 − σ ( − u w k ⊤ v c ) ) σ ( − u w k ⊤ v c ) ∂ − u w k ⊤ v c ∂ u w s = ( 1 − σ ( − u w s ⊤ v c ) ) v c (a2.1.10) \begin{aligned} \frac{\partial J_{\text{neg-sample}}(v_c,o,U)}{\partial u_{w_s}}&=-\frac{\partial}{\partial u_{w_s}}\log\sigma(u_o^\top v_c)-\sum_{k=1}^K\frac{\partial}{\partial u_{w_s}}\log \sigma(-u_{w_k}^\top v_c)\\ &=-\sum_{k=1}^{K}\frac{\sigma(-u_{w_k}^\top v_c)(1-\sigma(-u_{w_k}^\top v_c))}{\sigma(-u_{w_k}^\top v_c)}\frac{\partial-u_{w_k}^\top v_c}{\partial u_{w_s}}\\ &=(1-\sigma(-u_{w_s}^\top v_c))v_c \end{aligned} \tag{a2.1.10} ∂uws​​∂Jneg-sample​(vc​,o,U)​​=−∂uws​​∂​logσ(uo⊤​vc​)−k=1∑K​∂uws​​∂​logσ(−uwk​⊤​vc​)=−k=1∑K​σ(−uwk​⊤​vc​)σ(−uwk​⊤​vc​)(1−σ(−uwk​⊤​vc​))​∂uws​​∂−uwk​⊤​vc​​=(1−σ(−uws​⊤​vc​))vc​​(a2.1.10)

    • ( 2 ) (2) (2) 观察 ( a 2.1.8 ) ( a 2.1.9 ) ( a 2.1.10 ) (a2.1.8)(a2.1.9)(a2.1.10) (a2.1.8)(a2.1.9)(a2.1.10)三个偏导解析式，显然可以重用的部分是：
      σ ( u o ⊤ v / c ) − 1  and  1 − σ ( − u w s ⊤ v c ) , s = 1 , 2 , . . . , K (a2.1.11) \sigma(u_o^\top v/_c)-1\text{ and }1-\sigma(-u_{w_s}^\top v_c),s=1,2,...,K\tag{a2.1.11} σ(uo⊤​v/c​)−1 and 1−σ(−uws​⊤​vc​),s=1,2,...,K(a2.1.11)
      写成要求的矩阵形式即为：
      σ ( U o , { w 1 , . . . , w K } ⊤ v c ) − 1 (a2.1.12) \sigma(U_{o,\{w_1,...,w_K\}}^\top v_c)-\textbf{1}\tag{a2.1.12} σ(Uo,{w1​,...,wK​}⊤​vc​)−1(a2.1.12)

    • ( 3 ) (3) (3) 从 ( b ) ( c ) (b)(c) (b)(c)的结果来看，同样有可以重用的部分（ y ^ − y \hat y-y y^​−y），但是 ( b ) (b) (b)的梯度需要计算矩阵与向量的乘法，耗时较长，而 ( g ) (g) (g)中的三个结果使用重用部分后本质上是标量与向量相乘的运算，自然要高效很多。

  • ( h ) (h) (h) 本问与 ( g ) (g) (g)的区别在于，负采样可能采样到重复的单词，因此结果与式 ( a 2.1.10 ) (a2.1.10) (a2.1.10)稍有区别：
    ∂ J neg-sample ( v c , o , U ) ∂ u w s = − ∂ ∂ u w s log ⁡ σ ( u o ⊤ v c ) − ∑ k = 1 K ∂ ∂ u w s log ⁡ σ ( − u w k ⊤ v c ) = − ∑ k = 1 K σ ( − u w k ⊤ v c ) ( 1 − σ ( − u w k ⊤ v c ) ) σ ( − u w k ⊤ v c ) ∂ − u w k ⊤ v c ∂ u w s = ∑ k = 1 K 1 w k = w s ( 1 − σ ( − u w s ⊤ v c ) ) v c (a2.1.13) \begin{aligned} \frac{\partial J_{\text{neg-sample}}(v_c,o,U)}{\partial u_{w_s}}&=-\frac{\partial}{\partial u_{w_s}}\log\sigma(u_o^\top v_c)-\sum_{k=1}^K\frac{\partial}{\partial u_{w_s}}\log \sigma(-u_{w_k}^\top v_c)\\ &=-\sum_{k=1}^{K}\frac{\sigma(-u_{w_k}^\top v_c)(1-\sigma(-u_{w_k}^\top v_c))}{\sigma(-u_{w_k}^\top v_c)}\frac{\partial-u_{w_k}^\top v_c}{\partial u_{w_s}}\\ &=\sum_{k=1}^K\textbf{1}_{w_k=w_s}(1-\sigma(-u_{w_s}^\top v_c))v_c \end{aligned} \tag{a2.1.13} ∂uws​​∂Jneg-sample​(vc​,o,U)​​=−∂uws​​∂​logσ(uo⊤​vc​)−k=1∑K​∂uws​​∂​logσ(−uwk​⊤​vc​)=−k=1∑K​σ(−uwk​⊤​vc​)σ(−uwk​⊤​vc​)(1−σ(−uwk​⊤​vc​))​∂uws​​∂−uwk​⊤​vc​​=k=1∑K​1wk​=ws​​(1−σ(−uws​⊤​vc​))vc​​(a2.1.13)
    其中 1 \textbf{1} 1为指示函数，若 w k = w s w_k=w_s wk​=ws​取值为一，否则取值为零。

  • ( i ) (i) (i) 在[notes]中可以查阅 skip-gram \text{skip-gram} skip-gram模型的目标函数：
    minimize J = − ∑ j = 0 , j ≠ m 2 m u c − m + j ⊤ v c + 2 m log ⁡ ∑ k = 1 ∣ V ∣ exp ⁡ ( u k ⊤ v c ) (a2.1.14) \text{minimize}\quad J=-\sum_{j=0,j\neq m}^{2m}u_{c-m+j}^\top v_c+2m\log\sum_{k=1}^{|V|}\exp(u_k^\top v_c)\tag{a2.1.14} minimizeJ=−j=0,j=m∑2m​uc−m+j⊤​vc​+2mlogk=1∑∣V∣​exp(uk⊤​vc​)(a2.1.14)
    则要求的三个偏导具有如下形式：
    ∂ J skip-gram ( v c , w t − m , . . . , w t + m , U ) ∂ U = ∑ − m ≤ j ≤ m , j ≠ 0 ∂ J ( v c , w t + j , U ) ∂ U ∂ J skip-gram ( v c , w t − m , . . . , w t + m , U ) ∂ v c = ∑ − m ≤ j ≤ m , j ≠ 0 ∂ J ( v c , w t + j , U ) ∂ v c ∂ J skip-gram ( v c , w t − m , . . . , w t + m , U ) ∂ v w = 0 (a2.1.15) \begin{aligned} &\frac{\partial J_{\text{skip-gram}}(v_c,w_{t-m},...,w_{t+m},U)}{\partial U}&&=\sum_{-m\le j\le m,j\neq0}\frac{\partial J(v_c,w_{t+j},U)}{\partial U}\\ &\frac{\partial J_{\text{skip-gram}}(v_c,w_{t-m},...,w_{t+m},U)}{\partial v_c}&&=\sum_{-m\le j\le m,j\neq0}\frac{\partial J(v_c,w_{t+j},U)}{\partial v_c}\\ &\frac{\partial J_{\text{skip-gram}}(v_c,w_{t-m},...,w_{t+m},U)}{\partial v_w}&&=0 \end{aligned}\tag{a2.1.15} ​∂U∂Jskip-gram​(vc​,wt−m​,...,wt+m​,U)​∂vc​∂Jskip-gram​(vc​,wt−m​,...,wt+m​,U)​∂vw​∂Jskip-gram​(vc​,wt−m​,...,wt+m​,U)​​​=−m≤j≤m,j=0∑​∂U∂J(vc​,wt+j​,U)​=−m≤j≤m,j=0∑​∂vc​∂J(vc​,wt+j​,U)​=0​(a2.1.15)

2. coding

  • ( a ) (a) (a) 这里第 ( 4 ) (4) (4)小问可能有点问题，始终无法通过测试，但是在往年的代码里是可以通过测试的，感觉或许是测试代码写得有些问题，因为只有 skip-gram \text{skip-gram} skip-gram的负采样损失函数这一项无法通过测试，其他都是正确的。

    • ( 1 ) (1) (1) 参考 written \text{written} written部分的 ( f ) (f) (f)
    • ( 2 ) (2) (2) 参考 written \text{written} written部分的 ( b ) ( c ) ( d ) (b)(c)(d) (b)(c)(d)
    • ( 3 ) (3) (3) 参考 written \text{written} written部分的 ( g ) (g) (g)
    • ( 4 ) (4) (4) 参考 written \text{written} written部分的 ( i ) (i) (i)

  • ( b ) (b) (b) 简单的梯度下降法实现。

  • ( c ) (c) (c) 需要事先下载数据集并解压到 utils \text{utils} utils目录下，运行得到的图片为：

    3.1

lecture 4 依存分析

slides

[slides] [slides (annotated)] 两份slides完全相同，后一份带标注（因为需要标注依存关系），本文以后一份为准。

  1. 依存分析的概念：slides p.24

    解析语句，将其中每个单词指向其所依赖的对象（通常句首添加ROOT标签，同样要为ROOT标注一个对象）。

    句法依存标注的基本规则：

    • ROOT有且仅有一个依赖对象；
    • 不要出现环，即 A A A指向 B B B， B B B又以任何路径指回到 A A A，原因是依存分析的目的之一是可以构建句法解析树。
    • 具体的一些句法依存关系与语义依存关系可以查看博客

    这里有提到一个projectivity的概念，不是很能搞得明白，有一个结论是CFG树必然是projective的。（在斯坦福句法解析包中，大部分的解析器都是PCFG解析器）

  2. 依存分析的方法：slides p.26

    • 动态规划：这是一个很老的思想，最早可以追溯到1986年。
    • 图算法：图算法的思想有点类似最大生成树，分词之间边的权重其实就是分词相互依存的概率，可以通过统计方法决定。
    • 基于规则的硬性约束
    • 基于转移的解析（transition-based parser）与基于确定性的解析（deterministic dependency parsing），这两个方法在推荐阅读部分有几篇相关的论文可供参考。

    一般来说，依存分析中，动词是句子的核心，会直接连在ROOT下面，然后扩展到全句其他词。

  3. 笔者拓展：

    这一节内容相对晦涩一些，笔者认为可能实践更为重要，因此记录一下近期斯坦福句法解析库的以备后用：

    1. 安装JDK；

    2. 从stanford-parser-4.2.0-models.jar处下载得到stanford-parser-4.2.0.zip（截至本文发布的版本号，之后可能会更新，可自行到https://nlp.stanford.edu/software/lex-parser.html#Download寻找下载链接）

    3. 接下来我们需要从stanford-parser-4.2.0.zip中找到几个文件：

      ① 根目录下的stanford-parser.jar；

      ② 根目录下的stanford-parser-4.2.0-models.jar；

      ③ 以中文解析为例，从stanford-parser-4.2.0-models.jar中解压得到chinesePCFG.ser.gz；

    4. 下面是生成句法树的demo：

      # -*- coding: utf-8 -*-
# @author: caoyang
# @email: caoyang@163.sufe.edu.cn

from nltk.parse.stanford import StanfordParser

def generate_parse_tree(tokens):		
	parser = StanfordParser('stanford-parser.jar',
							'stanford-parser-4.2.0-models.jar',
							model_path='chinesePCFG.ser.gz')
	parse_tree = list(parser.parse(tokens))
	return parse_tree

parse_tree = generate_parse_tree(tokens=['今天', '是', '一个', '好', '天气'])
print(parse_tree)	# [Tree('ROOT', [Tree('IP', [Tree('NP', [Tree('NT', ['今天'])]), Tree('VP', [Tree('VC', ['是']), Tree('NP', [Tree('QP', [Tree('CD', ['一个'])]), Tree('ADJP', [Tree('JJ', ['好'])]), Tree('NP', [Tree('NN', ['天气'])])])])])])]

    5. 注意道中文句法解析的输入必须是已经做好分词的结果，虽然斯坦福句法解析库也可以进行中文分词，但是相对来说jieba要更容易，也做得更好，因此可以考虑先用jieba分好词再输入进行解析得到句法树。

    6. 句法树可以进行可视化，使用stanford-parser-4.2.0.zip根目录下的lexparser-gui.bat即可。

    7. 句法树的叶子节点记录了每一个分词的词性，经过检查，笔者共发现有33种不同的词性：

      # Stanford中文词性标注集(对应句法树叶子节点上的标注, 共33个), 具体说明见https://blog.csdn.net/weixin_30642561/article/details/97772970
STANFORD_POS_TAG = [
	'AD', 'AS', 'BA', 'CC', 'CD', 'CS', 'DEC', 'DEG', 'DER', 'DEV', 'DT', 
	'ETC', 'FW', 'IJ', 'JJ', 'LB', 'LC', 'M', 'MSP', 'NN', 'NR', 'NT', 
	'OD', 'P', 'PN', 'PU', 'SB', 'SP', 'URL', 'VA', 'VC', 'VE', 'VV',
]

      此外非叶子节点标注的是句法成分，经过检查，笔者共发现28种不同的句法成分标记（与词性不重复）：

      # Stanford中文句法依存分析标注集(共33+28个, 前33个来自STANFORD_POS_TAG, 后28个对应句法树非叶节点上的标注)
STANFORD_SYNTACTIC_TAG = STANFORD_POS_TAG + [
	'ADJP', 'ADVP', 'CLP', 'CP', 'DFL', 'DNP', 'DP', 'DVP', 'FLR', 
	'FRAG', 'INC', 'INTJ', 'IP', 'LCP', 'LST', 'NP', 'PP', 'PRN', 'QP', 
	'ROOT', 'UCP', 'VCD', 'VCP', 'VNV', 'VP', 'VPT', 'VRD', 'VSB',
]

    8. 可直接从句法树中提取词性标注结果：

      # -*- coding: utf-8 -*-
# @author: caoyang
# @email: caoyang@163.sufe.edu.cn

import re

def generate_pos_tags_from_parse_tree(parse_tree, regex_compiler = re.compile('\([^\(\)]+\)', re.I)):
	if not isinstance(parse_tree, str):
		# 2022/03/09 19:48:50 只对字符串形式的树进行处理, 原数据结构不便于处理
		parse_tree = str(parse_tree)
	
	results = regex_compiler.findall(parse_tree)
	pos_tags = list(map(lambda result: tuple(result[1: -1].split(' ', 1)), results))
	return pos_tags

    9. 注意分词中的左右小括号会被改写为-LRB与-RRB-，以与句法树中的括号区分开，此外分词中\xa0会被视为空字符串，分词中的\u3000与单空格字符将不会被斯坦福句法解析库识别到，这些都是可能造成程序出现问题的小细节：

      # 2022/03/29 20:57:45 解析树会把原分词序列中的一些特殊符号分词改写为其他形式
# 2022/03/29 20:57:54 典型的如-LRB-表示左小括号, -RRB-表示右小括号
# 2022/03/29 20:57:54 其他的情况暂时没有发现, 但是我估计应该是没有其他了, 这两个是为了避免和句法树形式中的括号混淆
STANFORD_SPECIAL_SYMBOL_MAPPING = {'(': '-LRB-', ')': '-RRB-', '\xa0': ''}
STANFORD_IGNORED_SYMBOL = {'\u3000', ' '}

    10. 可以将解析得到的句法树转为networkx或dgl的图，下面是笔者实现的方法：

     # -*- coding: utf-8 -*-
 # @author: caoyang
 # @email: caoyang@163.sufe.edu.cn
 
 import networkx
 import dgl
 
 from networkx import DiGraph, draw
 
 def parse_tree_to_graph(parse_tree, display=False, return_type='networkx', ignore_text=False):
 	assert return_type in ['networkx', 'dgl'], f'Unknown param `return_type`: {return_type}'
 	if not isinstance(parse_tree, str):
 		# 2022/03/09 19:48:50 只对字符串形式的树进行处理, 原数据结构不便于处理
 		warnings.warn(f'句法解析树应为字符串, 而非{type(parse_tree)}')
 		parse_tree = str(parse_tree)
 	
 	graph = DiGraph()		# 2022/03/09 20:48:52 绘制句法树的有向图
 	current_index = 0		# 2022/03/09 20:48:52 记录已经解析到句法树字符串的位置
 	stack = []				# 2022/03/09 20:48:52 用于存储句法树节点的栈(包括句法树标签与文本)	
 	node_id = -1			# 2022/04/23 16:09:19 全局记录节点的id, 考虑将节点信息存储在node.data中
 	
 	# 2022/04/28 23:29:29 合并后的添加节点函数
 	def _add_node(_node_id, _text, _tag, _is_pos, _is_text):
 		_node_data = {
 			'node_id'	: _node_id,										# 2022/05/20 12:48:02 节点编号: 0, 1, 2, ...
 			'text'		: _text,										# 2022/05/20 12:48:02 文本分词内容, 若_is_text为False, 则为None
 			'tag_id'	: STANFORD_SYNTACTIC_TAG_INDEX.get(_tag, -1),	# 2022/05/20 12:48:02 句法树标签内容, 若_is_text为True, 则为None, 否则必然属于STANFORD_SYNTACTIC_TAG集合
 			'is_pos'	: _is_pos,										# 2022/05/20 12:48:02 记录是否是句法树叶子节点上的词性标注
 			'is_text'	: _is_text,										# 2022/05/20 12:48:02 记录是否是句法树叶子节点上的文本分词
 		}
 		graph.add_node(node_for_adding=_node_id, **_node_data)					# 添加新节点
 		if stack:																# 若栈不为空								
 			_stack_top_node_id = stack[-1]['node_id']							# 取栈顶节点的编号				
 			graph.add_edge(u_of_edge=_stack_top_node_id, v_of_edge=_node_id)	# 则栈顶节点(即当前分支节点)指向新节点
 		elif _is_text:
 			raise Exception('叶子节点文本内容找不到父节点标签')
 		if not _is_text:
 			stack.append(_node_data)											# 最后将新节点(非叶/非文本)添加到栈中
 			
 	while current_index < len(parse_tree):
 		# 左括号意味着新分支的开始
 		if parse_tree[current_index] == '(':
 			next_left_parenthese_index = parse_tree.find('(', current_index + 1)	# 寻找下一个左括号的位置
 			next_right_parenthese_index = parse_tree.find(')', current_index + 1)	# 寻找下一个右括号的位置
 			
 			if next_left_parenthese_index == -1 and next_right_parenthese_index == -1:
 				# 左括号后面一定还有括号
 				raise Exception('句法树括号位置不合规')
 			
 			if next_left_parenthese_index < next_right_parenthese_index and next_left_parenthese_index >= 0:
 				# 向右检索最先遇到左括号: 新节点出现
 				new_node = parse_tree[current_index + 1: next_left_parenthese_index].replace(' ', '')	# 向右搜索先遇到左括号: 发现新节点
 				
 				# 2022/05/20 13:00:30 新增断言
 				assert new_node in STANFORD_SYNTACTIC_TAG and new_node not in STANFORD_POS_TAG, f'Unknown syntactic tags: {new_node}'
 				
 				node_id += 1																			# 更新节点编号
 				_add_node(_node_id=node_id, _text=None, _tag=new_node, _is_pos=False, _is_text=False)	# 添加新节点
 				current_index = next_left_parenthese_index												# 将current_index刷新到新的左括号处
 			else:
 				# 向右检索最先遇到右括号: 此时到达叶子节点
 				leave_node = parse_tree[current_index + 1: next_right_parenthese_index]					# 向右搜索先遇到右括号: 此时意味着已经到达叶子节点
 				new_node, text = leave_node.split(' ', 1)												# 叶子节点由词性标注与对应的文本内容两部分构成
 				
 				# 2022/05/20 13:00:30 新增断言
 				assert new_node in STANFORD_POS_TAG, f'Unknown pos tags: {new_node}'
 				
 				node_id += 1																			# 更新节点编号
 				_add_node(_node_id=node_id, _text=None, _tag=new_node, _is_pos=True, _is_text=False)	# 添加叶子节点
 				if not ignore_text:
 					node_id += 1																		# 更新节点编号
 					_add_node(_node_id=node_id, _text=text, _tag=None, _is_pos=False, _is_text=True)	# 添加叶子节点上的文本内容
 				current_index = next_right_parenthese_index + 1											# 将current_index刷新到右括号的下一个位置
 				stack.pop(-1)																			# 弹出栈顶节点, 即叶子节点
 		
 		# 右括号意味着新分支的结束
 		elif parse_tree[current_index] == ')':	
 			stack.pop(-1)
 			current_index += 1
 		
 		# 空格则跳过
 		elif parse_tree[current_index] == ' ':
 			current_index += 1
 		
 		# 理论上不会出现其他情况, 除非字符串根本就不是一棵合法的句法树
 		else:
 			raise Exception(f'不合法的字符: {parse_tree[current_index]}')
 	
 	if display:
 		# 使用matplotlib将图绘制出来
 		draw(graph, with_labels=True)
 		plt.show()
 	
 	if return_type == 'networkx':
 		return graph
 	
 	elif return_type == 'dgl':
 		return dgl.from_networkx(graph, node_attrs=['node_id', 'tag_id',  'is_pos', 'is_text'])

notes

[notes]

  1. 有两种主要类型的句法树结构：成分结构（constituency structures）与依赖结构（dependency structure）

  2. 突然想到句法树的生成有点类似证明图的生成。

  3. 基于Transition的依存分析：notes p.2-3

    基于转换的依赖关系解析依赖于状态机，状态机定义所有可能的转移，用以创建从输入句子到依存关系树的映射。学习问题是根据状态机的过渡历史，建立一个能够预测下一个过渡的模型。句法分析问题是在给定先前归纳模型的情况下，为输入句子构造最佳的Transition序列。大多数基于Transition的系统不使用正式的语法。

    这里举了一个叫作Greedy Deterministic Transition-Based Parsing的例子（2003提出），Transition系统是一个状态机：

    • 状态：对于给定的句子 S = w 0 w 1 . . . w n S=w_0w_1...w_n S=w0​w1​...wn​，状态定义为三元组 c = ( σ , β , A ) c=(\sigma,\beta,A) c=(σ,β,A)

      ① σ \sigma σ是存储 S S S中单词 w i w_i wi​的栈（stack）；

      ② β \beta β是存储 A A A中单词 w i w_i wi​的缓存（buffer）；

      ③ A A A是一系列 ( w i , r , w j ) (w_i,r,w_j) (wi​,r,wj​)（称之为dependency arc）构成的集合，其中 r r r是预先定义好的一种依存关系。

    • 初始状态 c 0 = ( [ w 0 ] σ , [ w 1 , . . . , w n ] β , ∅ ) c_0=([w_0]_\sigma,[w_1,...,w_n]_{\beta},\emptyset) c0​=([w0​]σ​,[w1​,...,wn​]β​,∅)，其中 w 0 w_0 w0​就是ROOT，其他所有单词都在缓存中。

    • 终末状态为 ( σ , [ ] β , A ) (\sigma,[]_\beta,A) (σ,[]β​,A)

    • 然后每次转移的方式有三种：

      ① Shift：将缓存中的第一个单词移除，并置入栈顶；
      σ , w i ∣ β , A → σ ∣ w i , β , A (4.1) \sigma,w_i|\beta,A\rightarrow \sigma|w_i,\beta,A\tag{4.1} σ,wi​∣β,A→σ∣wi​,β,A(4.1)
      ② Left-Arc：添加一个依存关系组 ( w j , r , w i ) (w_j,r,w_i) (wj​,r,wi​)进入 A A A，其中 w i w_i wi​是栈顶的下一个单词， w j w_j wj​是栈顶单词，然后从栈中移除 w i w_i wi​；（先决条件：栈中至少包含两个单词，且 w i w_i wi​不能是ROOT）
      σ ∣ w i ∣ w j , β , A → σ ∣ w j , β , A ∪ { r ( w j , w i ) } (4.2) \sigma|w_i|w_j,\beta,A\rightarrow\sigma|w_j,\beta,A\cup\{r(w_j,w_i)\}\tag{4.2} σ∣wi​∣wj​,β,A→σ∣wj​,β,A∪{r(wj​,wi​)}(4.2)
      ③ Right-Arc：添加一个依存关系组 ( w i , r , w j ) (w_i,r,w_j) (wi​,r,wj​)进入 A A A，其中 w i w_i wi​是栈顶的下一个单词， w j w_j wj​是栈顶单词，然后从栈中移除 w j w_j wj​；（先决条件：栈中至少包含两个单词）
      σ ∣ w i ∣ w j , β , A → σ ∣ w j , β , A ∪ { r ( w i , w j ) } (4.3) \sigma|w_i|w_j,\beta,A\rightarrow\sigma|w_j,\beta,A\cup\{r(w_i,w_j)\}\tag{4.3} σ∣wi​∣wj​,β,A→σ∣wj​,β,A∪{r(wi​,wj​)}(4.3)

  4. 神经依存分析：notes p.3-5

    这个是非常流行的做法，推荐阅读部分也有两篇较新的paper是关于该主题的。

    以Greedy Deterministic Transition-Based Parsing为例，神经网络模型每次预测下一次的转移是哪一个（三分类），这个就有点强化学习的味道了，也就不难理解slides部分提到可以使用动态规划进行依存分析，不过似乎如何定义奖励是比较困难的事情。

    输入神经网络的特征来自单词的嵌入，各种句法标注标签的嵌入（词性，句法成分等）。

suggested readings

  1. 2004年的一篇老古董，讲的是Deterministic dependency parsing（与之对应的基于transition的解析方法）的内容，（Incrementality in Deterministic Dependency Parsing）
  2. 使用神经网络方法进行依存分析，使用的是基于transition的增量解析方法，2014年发表于EMNLP。（A Fast and Accurate Dependency Parser using Neural Networks）
  3. 这是一部著作，但是应该是需要付费下载的，暂时无法获取资源。（Dependency Parsing）
  4. 这也是一篇用神经网络方法进行依存分析，使用的也是基于transition的增量解析方法，2016年上传于ARXIV（Globally Normalized Transition-Based Neural Networks）
  5. 这篇应该Stanford Parser创始的paper，讲的是多语言句法解析的方法（Universal Stanford Dependencies: A cross-linguistic typology）
  6. 这是上一篇paper对应的网站，这是一个众筹数据的平台，好像也可以下载treebank的数据。（Universal Dependencies website）
  7. 教材中关于依存分析（Jurafsky & Martin Chapter 14）

此外在Stanford Parser主页上，每一种语言的解析器都有多篇论文可以参考。

pytorch tutorial session

[colab notebook]

笔者暂时无法下载colab代码，不过应该是一份PyTorch的入门demo，不是那么重要，自己查查API文档基本也够用了。

# 神经网络 # 深度学习 # 人工智能 # 自然语言处理 # 数学
Logo
技术共进，成长同行——讯飞AI开发者社区

技术共进，成长同行——讯飞AI开发者社区

更多推荐

大数据架构中的AI赋能：从数据平台到智能决策的演进

本文旨在深入探讨大数据架构与人工智能技术的融合演进过程，分析AI如何赋能大数据平台实现从数据存储到智能决策的跨越。我们将覆盖从基础数据平台建设到高级智能应用的全生命周期，重点关注技术架构演进和关键实现技术。文章将从大数据架构的基础概念开始，逐步引入AI赋能的技术路径，分析核心算法原理，展示实际应用案例，并探讨未来发展趋势。最后提供总结和思考题，帮助读者巩固所学知识。大数据架构：处理海量数据的系统设

avatar 讯飞AI开发者社区
cover

2025年数字化转型时代必备证！

avatar 讯飞AI开发者社区

Python先进技术全面发展无人有人监听探索器空间站研发开发重要性智能化系统化武器多样化太阳能利用回收利用可再生能源变形金刚机器人

概念解析：一个融合性未来科技平台您提出的这个概念，本质上是一个以人工智能为核心、以空间站为基地、以可再生能源为动力、具备多功能（科研、监听、防御/攻击、机器人技术）的智能化、系统化平台。· 系统集成：作为“胶水语言”，将平台上各种异构的、多样化的武器系统、传感器、能源模块、机器人控制系统无缝连接成一个系统化整体。—总结：整体研发的重要性研发这样一个高度融合的平台，其战略重要性是前所未有的：1. 技

avatar 讯飞AI开发者社区