Page 126 - 《软件学报》2020年第11期

3442 Journal of Software 软件学报 Vol.31, No.11, November 2020

然而,图不能完全等同于文本,子图间不具有文本中词之间的线性关系.SkipGram 模型中将出现在目标词
固定窗口内的词作为其上下文,这里,目标词与上下文中的词就具有线性关系.然而子图间并没有线性的上下文
关系,所有的子图是从图中以某一节点作为根节点提取的.考虑到以根节点 v 的子图 sg i 与以根节点 N v 的子图 sg j
存在一些相同特征,其中,N v 表示节点 v 的后继节点,因此,子图 sg i 相比其他子图与 sg j 是更有关系的.基于这一点,
我们将以后继节点 N v 为根节点的子图作为子图 sg i 的上下文 context(sg i ).子图的根节点是唯一的,将根节点邻接
节点子图作为其上下文,就好比文本中将邻近词作为目标词的上下文.关于子图上下文更多的信息,我们将在第
3.2 节讨论.
3.1 SubSkipGram模型
SubSkipGram 模型是计算在目标子图条件下,上下文子图概率的最大化.给定目标子图 sg i 以及目标子图上
下文 context(sg i ),SubSkipGram 模型是求以下对数似然最大化.
T
∑ log (P context (sg i ) | sg i ) (3)
i= 1
其中,概率 P(context(sg i )|sg i )是通过以下公式计算.
∏ ( Psg j | sg i ) (4)
sg ∈ (sg i )
j context
此外,概率 P(sg j |sg i )定义如下.
exp(v T sg ⋅ v′ sg )
i j (5)
∑ C k = 1 exp(v T sg i ⋅ v′ sg k )
其中, v sg k 和 v′ 是子图 sg k 的输入和输出向量,C 表示子图库中子图的数量.
sg
k
SubSkipGram 模型是神经语言 SkipGram 模型的延申.为了更好地理解上述式子,我们使用文本来解释.
SkipGram 模型通过给定一个目标词来预测其周围词即给定输入向量来更新其上下文向量,而更新的依据来自
公式(3),通过条件概率的最大化来反向更新其上下文向量.而公式(5)是用来计算上下文中的词出现的条件概
率,即:给定目标词,某一词出现在该目标词的上下文的概率.其中,概率是通过词向量来计算的.
3.2 子图分布式学习
本节中将介绍目标子图上下文的构造过程以及其更新方式,具体如下.
算法 2. SubSkipGram (,sg G DΦ d ,, ).
v
d
输入:Φ表示子图库中子图的向量矩阵,初始为 0; sg 表示根节点 v、深度为 d 的目标子图;D 表示最大提取
v
深度.
1. context(sg i )=∅
2. for each v′∈N v
3. for each θ∈{d−1,d,d+1} and 0≤θ≤D
( , , )v G θ
4. context (sg d ) = ∪ TreeWalk ′
v
5. for each sg ∈ context (sg d )
cont v
6. J Φ ( ) =− log ( Psg |Φ (sg d ))
cont v
J ∂
7. Φ Φ = α −
∂ Φ
d
算法 2 中,步骤 1~步骤 4 表示子图 sg 上下文 context (sg d ) 的构建过程:从根节点 v 的后继节点 N v 提取深度
v v
为{d−1,d+1}的子图作为上下文,正如前面所说,子图多添加一个节点以及一条边可变成另一个子图,深度为 d 的
d
目标子图 sg 不应只考虑邻接深度为 d 的子图作为其上下文,而深度{d−1,d+1}的子图也应考虑在内.步骤 5~步
v
骤 7 表示根据目标子图来更新其上下文子图,具体是通过梯度下降来实现的,其中,α表示学习率.