网站建设衡水,音乐网站开发编程语言,网络公司基础建设,广告制作公司名字Embedding技术概览#xff1a;对其它Embedding技术不熟悉#xff0c;可以看我的上一篇文章#xff1a;深度学习推荐系统中各类流行的Embedding方法#xff08;上#xff09;Graph Embedding简介Word2Vec和其衍生出的Item2Vec类模型是Embedding技术的基础性方法#xff0c… Embedding技术概览对其它Embedding技术不熟悉可以看我的上一篇文章深度学习推荐系统中各类流行的Embedding方法上Graph Embedding简介Word2Vec和其衍生出的Item2Vec类模型是Embedding技术的基础性方法二者都是建立在“序列”样本比如句子、用户行为序列的基础上的。在互联网场景下数据对象之间更多呈现的是图结构所以Item2Vec在处理大量的网络化数据时往往显得捉襟见肘在这样的背景下Graph Embedding成了新的研究方向并逐渐在深度学习推荐系统领域流行起来。Graph Embedding也是一种特征表示学习方式借鉴了Word2Vec的思路。在Graph中随机游走生成顶点序列构成训练集然后采用Skip-gram算法训练出低维稠密向量来表示顶点。之后再用学习出的向量解决下游问题比如分类或者连接预测问题等。可以看做是两阶段的学习任务第一阶段先做无监督训练生成表示向量第二阶段再做有监督学习解决下游问题。总之Graph Embedding是一种对图结构中的节点进行Embedding编码的方法。最终生成的节点Embedding向量一般包含图的结构信息及附近节点的局部相似性信息。不同Graph Embedding方法的原理不尽相同对于图信息的保留方式也有所区别下面就介绍几种主流的Graph Embedding方法和它们之间的区别与联系。DeepWalk-Graph早期影响力较大的Graph Embedding方法是于2014年提出的DeepWalk它的主要思想是在由物品组成的图结构上进行随机游走产生大量物品序列然后将这些物品序列作为训练样本输入Word2Vec进行训练得到物品的Embedding。因此DeepWalk可以被看作连接序列Embedding和Graph Embedding的过渡方法。论文《Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba》用上图所示的方法展现了DeepWalk的算法流程。DeepWalk算法的具体步骤如下图a是原始的用户行为序列。图b基于这些用户行为序列构建了物品关系图。可以看出物品A和B之间的边产生的原因是用户U1先后购买了物品A和物品B。如果后续产生了多条相同的有向边则有向边的权重被加强。在将所有用户行为序列都转换成物品关系图中的边之后全局的物品关系图就建立起来了。图c采用随机游走的方式随机选择起始点重新产生物品序列。将这些物品序列输入图d所示的Word2Vec模型中生成最终的物品Embedding向量。在上述DeepWalk的算法流程中唯一需要形式化定义的是随机游走的跳转概率也就是到达结点后下一步遍历的邻接点的概率。如果物品关系图是有向有权图那么从节点跳转到节点的概率定义如下式所示。其中是物品关系图中所有边的集合是节点所有的出边集合是节点到节点边的权重即DeepWalk的跳转概率就是跳转边的权重占所有相关出边权重之和的比例。如果物品关系图是无向无权图那么跳转概率将是上式的一个特例即权重将为常数1且应是节点所有“边”的集合而不是所有“出边”的集合。注意 在DeepWalk论文中作者只提出DeepWalk用于无向无权图。DeepWalk用于有向有权图的内容是阿里巴巴论文《Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba》中提出的Base Graph EmbeddingBGE模型其实该模型就是对DeepWalk模型的实践本文后边部分会讲解该模型。DeepWalk相关论文【1】Perozzi B, Alrfou R, Skiena S, et al. DeepWalk: online learning of social representations[C]. knowledge discovery and data mining, 2014: 701-710.【2】Wang J, Huang P, Zhao H, et al. Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba[C]. knowledge discovery and data mining, 2018: 839-848.LINE-DeepWalk的改进DeepWalk使用DFSDeep First Search深度优先搜索随机游走在图中进行节点采样使用Word2Vec在采样的序列上学习图中节点的向量表示。LINELarge-scale Information Network Embedding也是一种基于邻域相似假设的方法只不过与DeepWalk使用DFS构造邻域不同的是LINE可以看作是一种使用BFSBreath First Search广度优先搜索构造邻域的算法。在Graph Embedding各个方法中一个主要区别是对图中顶点之间的相似度的定义不同所以先看一下LINE对于相似度的定义。LINE定义图中节点之间的相似度现实世界的网络中相连接的节点之间存在一定的联系通常表现为比较相似或者在向量空间中距离接近。对于带权网络来说节点之间的权越大相似度会越高或者距离越接近这种关系称为一阶近邻。一阶近邻关系用于描述图中相邻顶点之间的局部相似度 形式化描述为若顶点、之间存在直连边则边权即为两个顶点的相似度若不存在直连边则一阶相似度为0。如下图所示6和7之间存在直连边且边权较大表现为图中顶点之间连线较粗则认为两者相似且一阶相似度较高而5和6之间不存在直连边则两者间一阶相似度为0。但是网络中的边往往比较稀疏仅仅依靠一阶近邻关系难以描述整个网络的结构。论文中定义了另外一种关系叫做二阶近邻。例如下图中的网络节点5和节点1,2,3,4相连节点6也和节点1,2,3,4相连虽然节点5和6之间没有直接联系但是节点5和6之间很可能存在某种相似性。举个例子在社交网络中如果两个人的朋友圈重叠度很高或许两个人之间具有相同的兴趣并有可能成为朋友在NLP中如果不同的词经常出现在同一个语境中那么两个词很可能意思相近。LINE通过捕捉网络中的一阶近邻关系和二阶近邻关系更加完整地描述网络。并且LINE适用于有向图、无向图、有权图、无权图。LINE算法模型1一阶近邻关系模型一阶近邻关系模型中定义了两个概率一个是联合概率如下公式所示其中 是图中节点的向量表示上式表示节点和之间的相似程度这是一个sigmoid函数。另外一个是经验概率如下公式所示其中是节点和之间的权重。优化目标为最小化下式其中是两个分布的距离目标是期望两个概率分布接近利用KL散度来计算相似性丢掉常数项之后得到下面公式一阶近邻关系模型的优化目标就是最小化。可以看到上面这些公式无法表达方向概念因此一阶近邻关系模型只能描述无向图。2二阶近邻关系模型二阶近邻关系描述的是节点与邻域的关系每个节点有两个向量一个是该顶点本身的表示向量一个是该顶点作为其他顶点的邻居时的表示向量因此论文中对每个节点定义了两个向量表示节点本身 是节点作为邻居的向量表示。针对每一个从节点到的有向边定义一个条件概率如下式其中是图中所有的节点数量这其实是一个函数。同样还有一个经验概率如下式其中是边的边权是从顶点出发指向邻居节点的所有边权之和是从节点出发指向邻居的所有边集合。同样需要最小化条件概率和经验概率之间的距离优化目标为其中为控制节点重要性的因子可以通过顶点的度数或者PageRank等方法估计得到。假设度比较高的节点权重较高令采用KL散度来计算距离略去常数项后得到公式直接优化上式计算复杂度很高每次迭代需要对所有的节点向量做优化论文中使用Word2Vec中的负采样方法得到二阶近邻的优化目标如下公式所示。从计算的过程可以看到二阶相似度模型可以描述有向图。(滑动查看完整公式)对比一阶近邻模型和二阶近邻模型的优化目标差别就在于二阶近邻模型对每个节点多引入了一个向量表示。实际使用的时候对一阶近邻模型和二阶近邻模型分别训练然后将两个向量拼接起来作为节点的向量表示。此外有一点需要说明在Graph Embedding方法中例如DeepWalk、Node2Vec、EGES都是采用随机游走的方式来生成序列再做训练而LINE直接用边来构造样本这也是他们的一点区别。LINE论文【1】Tang J, Qu M, Wang M, et al. Line: Large-scale information network embedding[C]//Proceedings of the 24th international conference on world wide web. 2015: 1067-1077.node2vec2016年斯坦福大学的研究人员在DeepWalk的基础上更进一步提出了node2vec模型它通过调整随机游走权重的方法使Graph Embedding的结果更倾向于体现网络的同质性homophily或结构性structural equivalence。node2vec的同质性和结构性具体的讲网络的“同质性”指的是距离相近节点的Embedding应尽量近似如下图所示节点与其相连的节点的Embedding表达应该是接近的这就是网络的“同质性”的体现。“结构性”指的是结构上相似的节点Embedding应尽量近似下图中节点和节点都是各自局域网络的中心节点结构上相似其Embedding的表达也应该近似这是“结构性”的体现。为了使Graph Embedding的结果能够表达网络的“结构性”在随机游走过程中需要让游走的过程更倾向于BFS因为BFS会更多地在当前节点的邻域中游走遍历相当于对当前节点周边的网络结构进行一次“微观扫描”。当前节点是“局部中心节点”还是“边缘节点”或是“连接性节点”其生成的序列包含的节点数量和顺序必然是不同的从而让最终的Embedding抓取到更多结构性信息。另外为了表达“同质性”需要让随机游走的过程更倾向于DFS因为DFS更有可能通过多次跳转游走到远方的节点上但无论怎样DFS的游走更大概率会在一个大的集团内部进行这就使得一个集团或者社区内部的节点的Embedding更为相似从而更多地表达网络的“同质性”。但是在不同的任务中需要关注的重点不同可能有些任务需要关注网络的homophily而有些任务比较关注网络的structural equivalence可能还有些任务两者兼而有之。在DeepWalk中使用DFS随机游走在图中进行节点采样使用Word2Vec在采样的序列学习图中节点的向量表示无法灵活地捕捉这两种关系。实际上对于这两种关系的偏好可以通过不同的序列采样方式来实现。有两种极端的方式一种是BFS如上图中红色箭头所示从u出发做随机游走但是每次都只采样顶点u的直接邻域这样生成的序列通过无监督训练之后特征向量表现出来的是structural equivalence特性。另外一种是DFS如上图中蓝色箭头所示从u出发越走越远学习得到的特征向量反应的是图中的homophily关系。node2vec算法那么在node2vec算法中是怎么控制BFS和DFS的倾向性呢主要是通过节点间的跳转概率。下图所示为node2vec算法从节点跳转到节点再从节点跳转到周围各点的跳转概率。假设从某顶点出发开始随机游走第步走到当前顶点要探索第步的顶点如下图所示。下面的公式表示从顶点到的跳转概率是图中边的集合表示顶点和之间的边表示从节点跳转到下一个节点的概率是归一化常数。带偏随机游走的最简单方法是基于下一个节点边权重进行采样即是权重之和。对于无权重的网络。最简单的方式就是按照这个转移概率进行随机游走但是无法控制BFS和DFS的倾向性。node2vec用两个参数和定义了一个二阶随机游走以控制随机游走的策略。假设当前随机游走经过边到达顶点现在要决定从节点跳转到下一个节点需要依据边上的跳转概率。设是顶点和之间的边权是修正系数定义如下上式中表示下一步顶点和顶点之间的最短距离只有3种情况如果又回到顶点那么如果和直接相邻那么其他情况。参数和共同控制着随机游走的倾向性。参数被称为返回参数return parameter控制着重新返回顶点的概率。如果那么下一步较小概率重新返回顶点如果那么下一步会更倾向于回到顶点node2vec就更注重表达网络的结构性。参数被称为进出参数in-out parameter如果那么下一步倾向于回到或者的临近顶点这接近于BFS的探索方式如果那么下一步倾向于走到离更远的顶点接近于DFS寻路方式node2vec就更加注重表达网络的同质性。因此可以通过设置和来控制游走网络的方式。所谓的二阶随机游走意思是说下一步去哪不仅跟当前顶点的转移概率有关还跟上一步顶点相关。在论文中试验部分作者对和的设置一般是2的指数比如。node2vec这种灵活表达同质性和结构性的特点也得到了实验的证实通过调整参数和产生了不同的Embedding结果。下图中的上半部分图片就是node2vec更注重同质性的体现可以看到距离相近的节点颜色更为接近下图中下半部分图片则更注重体现结构性其中结构特点相近的节点的颜色更为接近。node2vec在推荐系统中的思考node2vec所体现的网络的同质性和结构性在推荐系统中可以被很直观的解释。同质性相同的物品很可能是同品类、同属性或者经常被一同购买的商品而结构性相同的物品则是各品类的爆款、各品类的最佳凑单商品等拥有类似趋势或者结构性属性的商品。毫无疑问二者在推荐系统中都是非常重要的特征表达。由于node2vec的这种灵活性以及发掘不同图特征的能力甚至可以把不同node2vec生成的偏向“结构性”的Embedding结果和偏向“同质性”的Embedding结果共同输入后续的深度学习网络以保留物品的不同图特征信息。node2vec论文【1】Grover A, Leskovec J. node2vec: Scalable feature learning for networks[C]//Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. 2016: 855-864.EGES2018 年阿里巴巴公布了其在淘宝应用的Embedding方法 EGESEnhanced Graph Embedding with Side Information算法其基本思想是Embedding过程中引入带权重的补充信息Side Information从而解决冷启动的问题。淘宝平台推荐的三个问题可扩展性(scalability)已有的推荐算法(CF、Base-Content、DL)可以在小数据集上有不错效果但是对于10亿用户和20亿商品这样海量的数据集上效果差。稀疏性(sparsity)用户仅与小部分商品交互难以训练准确的推荐模型。冷启动(cold start)物品上新频繁然而这些商品并没有用户行为预测用户对这些商品的偏好是十分具有挑战性的。现在业界针对海量数据的推荐问题通用框架是分成两个阶段即matching 和 ranking。在matching阶段我们会生成一个候选集它的items会与用户接触过的每个item具有相似性接着在ranking阶段我们会训练一个深度神经网络模型它会为每个用户根据他的偏好对候选items进行排序。论文关注的问题在推荐系统的matching阶段也就是从商品池中召回候选商品的阶段核心的任务是计算所有item之间的相似度。为了达到这个目的论文提出根据用户历史行为构建一个item graph然后使用DeepWalk学习每个item的embedding即Base Graph EmbeddingBGE。BGE优于CF因为基于CF的方法只考虑了在用户行为历史上的items的共现率但是对于少量或者没有交互行为的item仍然难以得到准确的embedding。为了减轻该问题论文提出使用side information来增强embedding过程提出了Graph Embedding with Side information (GES)。例如属于相似类别或品牌的item的embedding应该相近。在这种方式下即使item只有少量交互或没有交互也可以得到准确的item embedding。在淘宝场景下side information包括category、brand、price等。不同的side information对于最终表示的贡献应该不同于是论文进一步提出一种加权机制用于学习Embedding with Side Information称为Enhanced Graph Embedding with Side information (EGES)。基于图的EmbeddingBGE该方案是 DeepWalk 算法的实践具体流程如下首先我们拥有上亿用户的行为数据不同的用户在每个 Session 中访问了一系列商品例如用户 u2 两次访问淘宝第一次查看了两个商品 B-E第二次产看了三个商品 D-E-F。然后通过用户的行为数据我们可以建立一个商品图Item Graph可以看出物品AB之间的边产生的原因就是因为用户U1先后购买了物品A和物品B所以产生了一条由A到B的有向边。如果后续产生了多条相同的有向边则有向边的权重被加强。在将所有用户行为序列都转换成物品相关图中的边之后全局的物品相关图就建立起来了。接着通过 Random Walk 对图进行采样重新获得商品序列。最后使用 Skip-gram 模型进行 Embedding 。Base Graph Embedding 与 DeepWalk 不同的是通过 user 的行为序列构建网络结构并将网络定义为有向有权图。 其中根据行为的时间间隔将一个 user 的行为序列分割为多个session。session分割可以参考Airbnb这篇论文《Real-time Personalization using Embeddings for Search Ranking at Airbnb》。使用Side Information的GEGES通过使用BGE我们能够将items映射到高维向量空间并考虑了CF没有考虑的用户序列关系。但是我们依然没有解决冷启动的问题。为了解决冷启动问题我们使用边信息 category, shop, price, etc赋值给不同的item。因为边信息相同的两个item理论而言会更接近。通过DeepWalk方案得到item的游走序列同时得到对应的边信息categorybrandprice序列。然后将所有序列放到Word2Vec模型中进行训练。针对每个 item将得到item_embeddingcategory_embeddingbrand_embeddingprice_embedding 等 embedding 信息。为了与之前的item embedding区分开在加入Side information之后我们称得到的embedding为商品的aggregated embeddings。商品v的aggregated embeddings为对上式做一个简单的解释针对每个 item将得到item_embeddingcategory_embeddingbrand_embeddingprice_embedding 等 embedding 信息。将这些 embedding 信息求均值来表示该 item的Embedding。需要注意的一点是item 和 side information例如category, brand, price等 的 Embedding 是通过 Word2Vec 算法一起训练得到的。 如果分开训练得到的item_embedding和category_embedding、brand_embedding、price_embedding不在一个向量空间中做运算无意义。即通过 DeepWalk 方案得到 item 的游走序列同时得到对应的{category, brand, price}序列。然后将所有序列数据放到Word2Vec模型中进行训练。增强型GESEGESGES中存在一个问题是针对每个item它把所有的side information embedding求和后做了平均没有考虑不同的side information 之间的权重EGES就是让不同类型的side information具有不同的权重提出来一个加权平均的方法来聚集这些边界embedding。因为每个item对其不同边信息的权重不一样所以就需要额外矩阵来表示每个item边信息的权重其大小为是item的个数是边信息的个数加1是还要考虑item自身Embedding的权重。为了简单起见我们用表示第个item、第个类型的side information的权重。表示第个item自身Embedding的权重。这样就可以获得加权平均的方法这里对权重项做了指数变换目的是为了保证每个边信息的贡献都能大于0。权重矩阵通过模型训练得到。EGES算法应用改进的Word2Vec算法Weighted Skip-Gram确定模型的参数。对上图中EGES算法简单说明如下上图的Sparse Features代表 item 和 side information 的ID信息Dense Embeddings 表示 item 和 side information 的 embedding 信息分别代表 item 和 side information 的 embedding 权重Sampled Softmax Classifier中的代表采样的负样本见论文中的Algorithm 2 Weighted Skip-Gram描述的第8行代表正样本某个item周边上下n个item均为正样本在模型中表示时不区分远近EGES并没有过于复杂的理论创新但给出了一个工程上的融合多种Embedding的方法降低了某类信息缺失造成的冷启动问题是实用性极强的Embedding方法。EGES论文【1】Wang J, Huang P, Zhao H, et al. Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba[C]. knowledge discovery and data mining, 2018: 839-848.总结时至今日Graph Embedding仍然是工业界和学术界研究和实践的热点除了本文介绍的DeepWalk、LINE、node2vec、EGES等主流方法SDNE、struct2vec等方法也是重要的Graph Embedding模型感兴趣的读者可以自己查找相关文献进一步学习。本文原创首发于公众号【Microstrong】想了解更多关于推荐系统、自然语言处理等方向的内容欢迎扫码关注公众号。关注公众号后点击【学习群】可以加入我们的交流群一起学习【Microstrong】持续产出推荐系统/NLP/机器学习/深度学习等相关技术干货和实践经验。关注公众号还可以了解Microstrong的成长之路和程序人生哟Microstrong近期文章深入理解XGBoostSelf-Attention与Transformer深入理解GBDT回归算法深入理解CatBoost深度学习推荐系统中各类流行的Embedding方法上深入浅出Word2Vec原理解析夕小瑶的卖萌屋关注星标小夕带你解锁AI秘籍订阅号主页下方「撩一下」有惊喜参考文献【1】《深度学习推荐系统》王喆编著。【2】【Graph Embedding】DeepWalk算法原理实现和应用 - 浅梦的文章 - 知乎 https://zhuanlan.zhihu.com/p/56380812【3】【论文笔记】DeepWalk - 陌上疏影凉的文章 - 知乎 https://zhuanlan.zhihu.com/p/45167021【4】【Graph Embedding】LINE算法原理实现和应用 - 浅梦的文章 - 知乎 https://zhuanlan.zhihu.com/p/56478167【5】Graph Embedding从DeepWalk到SDNE - 羽刻的文章 - 知乎 https://zhuanlan.zhihu.com/p/33732033【6】Graph Embedding之探索LINE - 张备的文章 - 知乎 https://zhuanlan.zhihu.com/p/74746503【7】【Graph Embedding】node2vec算法原理实现和应用 - 浅梦的文章 - 知乎 https://zhuanlan.zhihu.com/p/56542707【8】node2vec在工业界的应用-《当机器学习遇上复杂网络解析微信朋友圈 Lookalike 算法》地址https://mp.weixin.qq.com/s/EV-25t2lWT2JJMLhXsz4zQ【9】graph embedding之node2vec - 张备的文章 - 知乎 https://zhuanlan.zhihu.com/p/63631102【10】Graph Embedding在淘宝推荐系统中的应用 - 张备的文章 - 知乎 https://zhuanlan.zhihu.com/p/70198918【11】Graph Embedding - 阿里EGES算法 - 王多鱼的文章 - 知乎 https://zhuanlan.zhihu.com/p/69069878【12】Graph Embedding深度学习推荐系统的基本操作 - 顾鹏的文章 - 知乎 https://zhuanlan.zhihu.com/p/68247149【13】论文阅读:Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba地址https://blog.csdn.net/Super_Json/article/details/85537938
