图表示学习 | 您所在的位置:网站首页 › 向量字母表示 › 图表示学习 |
Graph Embedding
先从Word Embedding来说,现在的NLP语言取得了巨大突破一大部分原因是将高度离散化的词语符号表示,转换为了低维的连续分布的表示。 eg: 我爱香蕉 我爱苹果 用onehot来表示: 我 0 [1,0,0,0] 爱 1 [0,1,0,0] 苹果 2 [0,0,1,0] 香蕉 3 [0,0,0,1] 但是这种方法不能够表现出相似性的关系,来就有了更聪明的方法,考虑将这些词语用高维空间中的向量表示,如果两个词向量之间的距离近,那么它们对应的词就具有越高的语义相似性,这种思想即word2vec。用word2vec可以变成: 我 [1,1,1]爱 [1,-1,1]苹果 [-1,1,0.5]雪梨 [-1,1,0.4]类比在图上也是一样,在图上,如果两个节点之间的路径短,那么这两个节点的相似性一定很高,也就是向量之间的距离短,考虑图G(V,E),在其基础上添加顶点的类别,则形成标注图(labeled graph)GL=(V,E,X,Y),其中X∈R(|v|*d)为顶点嵌入,Y∈R(|V|×|C|),d为特征维数,Y为标签集。 注意这种写法指X和Y均为矩阵,X一共有|V|行,每行对应一个顶点的特征向量,有d维;并且每个结点可能属于多个类别⊂C。(指multi-label classification,而不是multi-class每个样本只归属一类别)。 目标则是学习得到嵌入表示X,或者说映射Φ:V↦X,使得在低维的嵌入空间中,图结点有很好的分布式连续表达,能够很好保持图的邻接结构,即结点向量间的距离能够衡量原图中的邻接关系强弱。 下图来自deepwalk论文中的空手道数据集的deepwalk的实验结果。 将图中的节点当作词语,几个节点构成的路径当作句子。 Random walk随机游走的方式得到节点序列,就是从一个节点除法,走L步,得到的节点序列 ,其中从一个节点到相邻的节点之间是随机的饿过程。 w1,w2,…,wL 随机游走的好处: 可以实现并行计算 可以轻松应对动态网络,对于任意新加的点,不用再训练全图。 幂律分布与文本语言相似,图中,少量的节点拥有大量的连接,严重的分布不均匀。在论文中有说明: If the degree distribution of a connected graph follows a power law (i.e. scale-free), we observe that the frequency which vertices appear in the short random walks will also follow a power-law distribution. 图是符合幂律分布,他的子序列也符合幂律分布,因此可以尝试用语言模型来解决。 Skip-gram在word2vec中提到了两种LM,一种CBOW,输入为前后w个词,输出为中间词;而另外一种是skip-gram,输入中间词,输出前后w,skip-gram的计算量更少,deepWalk选择skip-gram;下图是窗口为2的情况; 论文中给出的伪代码: 总结一下: 1、每次随机选择一个起始点vi 2、从vi开始,做长为|Wvi|=t的随机游走。 3、依据得到的Wvi,做skip-gram。即对每一vj∈Wvi,每一uk∈Wvi[j−w:j+w],做梯度下降更新参数J ( Φ ) = − l o g P r ( u k ∣ Φ ( v j ) ) , Φ = Φ − α ∂ J / ∂ Φ J(Φ)=−logPr(uk∣Φ(vj)) , Φ=Φ−α∂J/∂Φ J(Φ)=−logPr(uk∣Φ(vj)),Φ=Φ−α∂J/∂Φ 其他的就是一些工程上的问题了,这里不再细致讨论。 |
CopyRight 2018-2019 实验室设备网 版权所有 |