智客公社
标题:
万物皆可Embedding之Deepwalk算法解读
[打印本页]
作者:
liping1957
时间:
2019-8-27 18:51
标题:
万物皆可Embedding之Deepwalk算法解读
[attach]191604[/attach]
需求论文的冤家可当前台私信小编。
前言
自从
word representation
中的神奇算法
word2vec
出现之后,无论是学术界还是工业界都有这样一个共识——
万物皆可Embedding
,基于句子、文档表达的
word2vec、doc2vec
算法,基于物品序列的
item2vec
算法,基于图结构的
Graph Embedding
技术,无论是在引荐、广告还是反欺诈范畴,各互联网公司基于本身业务与Embedding结合的论文相继问世,本篇讲述的
Deepwalk
就是
Graph Embedding
技术中的代表,下图是graph embeddings技术的普通流程。
[attach]191605[/attach]
DeepWalk论文发表于2014年的KDD会议上,将embedding从item序列推行至图序列,它是一种用于学习网络中顶点的潜在表示的新方法。这些潜在表示将社会关系编码到延续的向量空间中,编码到向量空间后的社会关系,很容易运用到统计模型中。DeepWalk将
随机游走
得到的节点序列当做句子,从截断的随机游走序列中得到网络的部分信息,再经过部分信息来学习节点的潜在表示。
算法思绪
DeepWalk将一个图作为输入,并产生一个潜在表示(将图中的每个节点表示为一个向量)作为输入,如下图示例所示:
[attach]191606[/attach]
对于图结构来说,算法设计需求满足以下几个要求:
1、
顺应性
:社交网络是不断变化的,当网络发生变化不能对整个网络重新停止计算。
2、
社区看法
:节点的潜在表示对应着维度空间中的间隔,应该表示网络中对应的成员的相似度,以此保证网络的同质性。
3、
低维
:当被标记的成员很少时,低维的模型普通表现的更好,并且收敛和推理速度更快。
4、
延续性
:需求经过图的潜在表示来对延续空间中的部分社区成员停止建模。除了提供对社区成员资历的纤细视图之外,延续表示还可以使社区之间的决策界限平滑,从而完成更弱小的分类。
Deepwalk算法流程
1、展现用户行为序列
2、基于这些用户行为序列构建了物品相关图,图中的边是由用户行为产生的,比如为用户M先后购买了物品A和物品B,会产生了一条有向边由A指向B。其他的有向边也是异样的道理,假如有多个有A指向B的有向边,那么该条边的权重被加强。经过这样的方法将一切用户行为序列都转换成物品相关图中的边后,就得到全局的物品相关图。
3、
采用随机游走的方式随机选择起始点,产生部分物品序列
。
4、将这些物品序列当初句子停止word2vec建模,生成最终的物品Embedding向量。
图中的节点表示item,边表示item之间的交互,上边步骤中最重要的是第三步,如何随机游走产生部分物品序列。deepwalk中的游走是
完全随机
的,这一点需求留意。经过改变
Random Walk
策略才有了后面的
node2vec。
Random Walk
Random Walk从截断的随机游走序列中得到网络的部分信息,并以此来学习结点的向量表示。借助言语建模word2vec中的一个模型,skip-gram来学习结点的向量表示。将网络中的结点模拟为言语模型中的单词,而结点的序列(由随机游走得到)模拟为言语中的句子,作为skip-gram的输入。
当
图中结点的度
遵照
幂律分布
(
度数大的节点比较少,度数小的节点比较多
)时,短随机游走中
顶点出现的频率
也将遵照
幂律分布(
即出现频率低的结点多),又由于
自然言语中单词出现的频率遵照相似的分布
,因此以上
假设可行
。如下图作者针对YouTube的社交网络与Wikipedia的文章停止了研讨,得出二者幂率分布基本上相似。
[attach]191607[/attach]
优点:
1.并行性:同时停止多个随机游走
2.顺应性:当图变化后,不需求全局重新计算,可以迭代地更新学习模型,合适online learning。
算法完成
[attach]191608[/attach]
Deepwalk算法架构
该算法由两部分组成:一个随机游走生成器和一个更新程序。
[attach]191609[/attach]
SkipGram
SkipGram是一个言语模型,用于最大化句子中出如今窗口w内的单词之间的共现概率。它运用独立性假设,最后条件概率近似为:
[attach]191610[/attach]
对序列中的每个顶点,
计算条件概率
,即该结点出现的状况下序列中其他结点出现的概率的log值并借助
随机梯度下降算法
更新该结点的向量表示。
[attach]191611[/attach]
注:Φ(vj)为当前结点的向量表示。
并行性
[attach]191612[/attach]
上图显示了并行对DeepWalk的影响。图(a)当多个义务同时停止时,算法的速度变快。图(b)表明,并行运转下,DeepWalk的功能没有遭到影响。
实验效果展现
数据集
BlogCatalog
是博客作者的社交关系网络。标签代表作者提供的主题类别。
Flickr
是照片分享网站用户之间的联络网络。标签代表用户的兴味组,如“黑白照片”。
YouTube
是盛行的视频分享网站用户之间的社交网络。 这里的标签代表喜欢不同类型视频(例如动漫和摔跤)的观众群体。
[attach]191613[/attach]
对比算法
SpectralClusteringModularityEdgeClusterwvRNMajority
实验中经过
多标签分类义务
来评价算法的功能。从数据集中随机抽样标记节点的一部分(TR),并将其用作训练数据。 其他的节点被用作测试。 我们反复这个过程10次,并报告Macro-F1和Micro-F1的平均功能。对于一切的模型,运用由LibLinear完成的one-vs-rest逻辑回归扩展来前往最能够的标签。将DeepWalk中的参数设置为:γ=80,w=10,d =128。在SpectralClustering,Modularity,EdgeCluster中,将维度设置为500。
实验结果及分析
(1) BlogCatalog
[attach]191614[/attach]
在实验中,将BlogCatalog网络上的训练比率(TR)从10%提高到90%,粗体数字表示每列中最高的功能。
结果分析:
1、DeepWalk的功能一直优于EdgeCluster,Modularity和wvRN。DeepWalk在只要20%的节点被标记时的功能,比这些方法在90%的数据时被标记的状况下执行得更好。
2、SpectralClustering的功能更具竞争力,但是当Macro-F1(TR≤20%)和Micro-F1(TR≤60%)上的标记数据稀疏时,DeepWalk照旧表现优秀。
经过以上两点可以看出,算法的优势在于,只要小部分图表被标记时,具有弱小的功能。
(2) Flickr
[attach]191615[/attach]
在实验中,将Flickr网络上的训练比率(TR)从1%变为10%。 这相当于在整个网络中有大约800到8000个节点标记用于分类。 上表给出了实验结果,粗体数字表示每列中最高的功能。
结果分析:
1、对于Micro-F1,DeepWalk的功能至少要比其他算法高出3%。DeepWalk可以比其他算法少60%的训练数据。
2、在Macro-F1中表现也相当不错,SpectralClustering最接近它。
(3)YouTube
[attach]191616[/attach]
YouTube网络规模大,更接近理想世界网络。SpectralClustering和Modularity不能用于这种规模的网络。在实验中,训练比率(TR)从1%变化到10%,粗体数字表示每列中最高的功能。
结果分析:
从实验中可以看出,DeepWalk分明优于其他算法:DeepWalk可以扩展到大图,并且在这样一个稀疏标记的环境中执行得非常好。
参数敏感度实验
为了评价DeepWalk的参数变化如何影响其在分类义务上的功能,我们对两个多标签分类义务(Flickr和BlogCatalog)停止了实验。实验中固定窗口大小和步长(w = 10,t = 40),然后,改变嵌入维度(d),每个游走长度(γ),以及可用的训练数据量(TR),以确定它们对网络分类功能的影响。
[attach]191617[/attach]
图(a)显示了维度变化的影响。图(a1)和(a3)分析了维度和训练数据比例对功能的影响。图(a2)和(a4)展现了维数和随机游走长度对功能的影响。得到如下结论:
1、a1和a3显示模型的最佳维度取决于训练数据的数量。
2、经过a2和a4可以看出,在γ确定的状况下,不同维度下,算法的功能是相对波动的。当γ>=30时,算法的功能比较好。两个图在γ的不同值之间的相对差异是分歧的。
这些实验表明,算法可以生成各种大小的有用模型。模型的功能取决于
随机游走的数量
,而模型的
最优维度
取决于可用的训练样例。
图(b)显示了改变γ对功能的影响。结果对于不同的维度(图(b1),图(b3))和不同训练数据量(图(b2),图(b4))非常分歧。添加γ对结果有很大的影响,但是当γ>10时,这种影响迅速减慢。这些结果表明,当
随机游走的数量足够多
时,我们才可以学习结点的有意义的潜在表示。
读了这篇文章给大家留几个成绩:
(1)你觉得Deepwalk中的随机游走方式合理吗?
(2)来了一个新的item,怎样求它的embedding,需求重新训练吗?
总结
最近在重温embedding相关的论文,每一次看论文都有不同的感受,graph embedding曾经广泛运用在引荐、广告、风控反欺诈等范畴,值得我们好好读一读,有什么成绩可以和我交流。
欢迎回复、分享、收藏、点赞,更多的内容可以关注同名公众号
作者:
@Xizi_19Br4ttB
时间:
2019-8-27 18:59
分享了
作者:
a8159787
时间:
2019-8-27 19:00
embedding的本质是,应用低维子空间的稠密延续向量来逼近高维空间的稀疏团圆向量,它不应该比spectral clustering效果好,但是在计算效率上应该优越不少。随机游走是图论算法的数学基础,只需算法上运用合理,随机游走会发挥宏大的效果。前沿研讨中,应用随机游走改善spectral clustering是一个很重要的学术分支,国外著名大学的一票科研人员在努力于这方面的研讨。从文中的实验数据来看,好像某些算法的完成存在改进空间,算法完成没有表现出算法的优势。文章很值得好好研讨~~~
作者:
小嶋慶祐
时间:
2019-8-27 19:01
(1)不合理。(2)需求
作者:
寒晨月
时间:
2019-8-27 19:06
先mark
作者:
—Mercenary—
时间:
2019-8-27 19:11
分享了
作者:
天使旳指紋
时间:
2019-8-27 19:15
分享了
作者:
落叶式悲伤
时间:
2019-8-27 19:17
分享了
作者:
者行孙4
时间:
2019-8-27 19:27
分享了
作者:
金山岁月
时间:
2019-8-27 19:30
分享了
作者:
坤叔叔叔
时间:
2019-8-27 19:37
分享了
作者:
韓僅____atw
时间:
2019-8-28 17:11
众里寻他千百度,蓦然回首在这里!
作者:
bettermanzy
时间:
2019-8-29 14:24
沙发位出租,有意请联系电话:13888888888
作者:
Sex欲帝丶
时间:
2019-8-30 12:18
LZ敢整点更有创意的不?兄弟们等着围观捏~
欢迎光临 智客公社 (http://bbs.cnaiplus.com/)
Powered by Discuz! X3.4