基于 Hierarchical Softmax 的 CBOW 模型

关注：如何构造 P(w | context(w)) ？

1. 网络结构

• 样本：(context(w),w)，假设 context(w) 由 w 的前后各 c 个词构成。
  

• 输入层：包含(context(w)) 中的 2c 个词向量:

  v(context(w)1)，v(context(w)2)，⋯，v(context(w)2c)∈Rm
  其中，m表示词向量的长度。

• 投影层：将输入层的 2c 个向量做累加求和，即：

  xw=∑i=12cv(context(w)i)∈Rm

• 输出层：对应一棵 Huffman 树，它以语料中出现过的词作为叶结点，叶结点的权重为词在语料中出现的次数。叶结点共 N=|D| 个，非叶子结点共 N−1 个。

2. 构造 P(w | context(w))

• 记号：

  • pw：从根节点到叶子结点 w 的路径。
  • lw：路径 pw 中包含的结点个数。
  • pw1，pw2，⋯，pwlw：表示路径 pw 的各个结点。
  • dw2，dw3，⋯，dwlw∈{0，1}：词语 w 对应的 Huffman 编码，也是 pw2，pw3，⋯，pwlw 对应的编码。
  • θw1，θw2，⋯，θwlw−1∈Rm：路径 pw 中非叶子结点对应的向量。

• 例子：
  

  • pw 为红色路径，lw=5。
  • pw1=38, pw2=23, pw3=9, pw4=4, pw5=3
  •   , dw2=1, dw3=0, dw4=0, dw5=1

• 如何使用 xw 和 Huffman 树定义 P(w | context(w)) ?

  • 从根节点出发，到达“足球”叶子结点，共有四个分支，每次分支视为进行了一次二分类。
  • word2vec 约定：Huffman 编码为 0 的结点为正类，编码为 1 的结点为负类，即
    Label(pwi)=1−dwi,i=2,3,⋯,lw
    在 Fuffman 树中，左边为负类，右边为正类。
  • 使用逻辑回归进行二分类，一个结点被分为正类的概率为
    σ(xTwθ)=11+e−xTwθ
    
    被分类为负类的概率为
    1−σ(xTwθ)
    
    上式中的 θ 即为每个非叶子结点的 θwi。

• 例子：
  第一次分类：P(dw2|xw,θw1)=1−σ(xTwθw1)
  第二次分类：P(dw3|xw,θw2)=σ(xTwθw2)
  第三次分类：P(dw4|xw,θw3)=σ(xTwθw3)
  第四次分类：P(dw5|xw,θw4)=1−σ(xTwθw4)

• 基本思路：对于词典 D 中的任何一个词 w，Huffman 树必定唯一存在一条从根节点到对应叶子节点的路径 pw，路径上存在 lw−1 个分支，把每个分支看成一次二分类，每次分类产生一个概率，把这些概率连乘即为所需的 P(w | context(w)) ，即
  
  P(w | context(w))=∏j=2lwP(dwj | xw,θwj−1)
  其中
  
  P(dwj | xw,θwj−1)={σ(xTwθwj−1),1−σ(xTwθwj−1),dwj=0（正类）dwj=1（负类）
  或者
  
  P(dwj | xw,θwj−1)=[σ(xTwθwj−1)]1−dwj×[1−σ(xTwθwj−1)]dwj,dwj∈{0,1}
  
  此处不需要进行归一化，输出的值本身具有概率意义。

3. 计算梯度

• 目标函数：
  L=∑w∈ClogP(w|context(w))

  =∑w∈Clog ∏lwj=2[σ(xTwθwj−1)]1−dwj×[1−σ(xTwθwj−1)]dwj

  =∑w∈C∑lwj=2(1−dwj)⋅log[σ(xTwθwj−1)] + dwj⋅log[1−σ(xTwθwj−1)]

  =∑w∈C∑lwj=2L(w,j)

• θ 参数（随机梯度上升）：

  • 每个结点的目标函数对各自结点的 θ 参数求导：
    
    L(w,j)=(1−dwj)⋅log[σ(xTwθwj−1)] + dwj⋅log[1−σ(xTwθwj−1)]
    
    
    δL(w,j)δθwj−1=(1−dwj)⋅[1−σ(xTwθwj−1)]xw−dwj⋅σ(xTwθwj−1)xw=[1−dwj−σ(xTwθwj−1)]⋅xw
  • 目标函数对 θ 参数求导：
    
    δLδθwj−1=δδθwj−1∑w∈C∑p=2lwL(w,p)
    
    
    =δδθwj−1∑w∈CL(w,j)
  • 每次更新使用一个点：
    
    θwj−1:=θwj−1+η⋅[1−dwj−σ(xTwθwj−1)]⋅xw
• xw 参数：
  
  • 
    
    δL(w,j)δ xw=[1−dwj−σ(xTwθwj−1)]⋅θwj−1(θwj−1和xw是对称的)
  • 
    
    δLδxw=δδxw∑w∈C∑p=2lwL(w,p)=∑w∈C∑j=2lwδδxwL(w,j)
• 更新词向量v(w^)
     我们的目标是求词典中各个词的词向量，xw 表示的是 Context(w) 中各词的词向量的累加：
  xw=∑i=12cContext(w)i=∑w^,  w^∈Context(w)
  
  所以，目标函数对词向量的导数为：
  
  δLδv(w^)=δLδxw×δxwδv(w^)=δLδxw
  
  随机梯度上升：
  
  v(w^):=v(w^)+η⋅∑j=2lwδδxwL(w,j), w^∈Context(w)