机器心灵专栏
作者： asjdxh(tzdkj )、瘦铃)翼升)等
千人千面模块上线，所有淘宝店今后都可能会有隐形智能指南。 建议重新升级算法。
电商时代，消费者对推荐系统不再陌生。 “突然回头看”，就会明白喜欢的商品在首页很显眼的地方。
现在，我不仅向你推荐电子商务网站的主页，还向你热情推荐。 即使进入淘宝商店的店铺，也很有可能会得到推荐算法的服务。
这是阿里商店事业部推出的智能店铺“千人千面”模块。
阿里事业部相关人士表示，单纯基于算法的商品推荐，未必符合商家的利益。 如果公司想卖的商品没有被推荐，市场营销被算法拖累，商家就会经常抱怨。 所谓“千人千面”，首先是让商家拿出想推的商品集，算法是从指定的候补集向进入某家商店的消费者进行个性化推荐。 这样，算法可以用于商家的营销服务，也可以用于商家决定的营销计划“ljdgb”。
但是，要做到这一点并不容易。
行业推荐系统通常由匹配和排名两部分组成。 在Matching部分，根据网民的浏览、追加购买、收藏等行为数据，从巨大的商品池中找出小的候选集。 Ranking是运用综合用户档案、喜好、商品特征等信息训练而成的评分排名模型。
但是，阿里电子商务交易所目前拥有百万级的活跃店铺，单个用户在单个特定店铺内的行为记录非常缺乏，很难用传统方法有效地进行匹配。
对此，阿里商店事业部提出了可扩展性强的Graph Embedding (图嵌入)方法，并将其创新性地应用于商品的embedding中。 可以在非常小的存储空间中计算任意两个商品的相似度。 即使你从来没有涉足过这家店，算法也可以根据你以前在另一家的浏览记录，从店里选择喜欢的商品，排在你前面。
模块投入使用后，商家商品点击率提高了30%，成交量提高了60%。
从学术上讲，这种Graph Embedding方法可以学习能够描述图中节点间高阶、不对称相似度的低维Embedding向量，从理论上解释基于该机器学习的方法与预定义的传统节点间相似度的关系，相关论文则是
接下来是针对这篇论文的中文讲义。 完整的论文PDF可以点击阅读原文进行下载。
工业界的推荐系统通常由Matching和Ranking两部分组成，Matching部分基于所有网民的浏览、购买、收藏等行为数据，利用协同过滤等算法，如基于商品的ItemCF Ranking是运用综合用户的个人资料、喜好、商品特征等附加信息训练而成的评分排名模型。
对于我们的推荐场景，也就是店铺私域内千人千面的推荐模块来说，与公网推荐的重要区别在于，推荐的目标仅限于极少数商家指定的商品集。
传统Matching这个部门面临的挑战是，由于阿里电子商务运营商目前拥有百万级的活动店铺，单个用户在单个店铺内的行为记录非常稀疏。 大多数情况下，用户最近首次访问某店铺的主页时，由于店内的行为信息(足迹商品等)不足，难以有效利用店内的ItemCF进行推荐。
ItemCF的核心问题之一是有效测量和计算item和item之间的相似度parencite{recsurvey05}。 对于全网推荐的APP场景，由于商品数量过多，通常会离线计算各item的前k个相似的item listparencite{itemcftopk}，用于在线评分的推荐方案。
但是，如果直接使用网络topk item相似度的数据，则每个商品与他相似的商品数量可能其实很多，但由于topk的限制(通常不到200 )，只有极少数店铺的商品可以召回。 也就是说，基于网络top-k的商品相似度在该店推荐下的召回能力比较有限。
当然，也可以用同样的方法只计算每个店铺内部的i2i数据进行推荐。 这样的缺点是用户完全无法覆盖店内没有足迹的情况。
因此，为了提高类似商品的召回，覆盖用户没有店内足迹的状况，使用图嵌入算法APP，根据用户的浏览记录制作商品嵌入——，将商品嵌入低维空间，保存作为商品间结构特征的商品相似度， 由此，可以用稳定的小成本在线计算任意两个商品之间的相似度。
“旺铺智能版智能模块”面向中小企业，是企业可以运营的个性化商品装饰模块。 在通过商家侧算法提供面向场景的选项的同时，允许商家调整算法商品池或完全手动创建商品池； 在消费者方面，个性化算法根据商家设置的商品池实时投放访问者。 产品设计在一定程度上满足了商家的确定需求的基础上，通过个性化算法提高了成交转换。
我们研究Graph Embedding的最初目的是为单步模块的千人千面场景提供覆盖率高的Match的支持。 由于用户在店铺内的行为稀少，所以传统的基于I2I的match的覆盖率很低。 可以用Embedding计算
任意两个商品之间的 Match 分数，极大改善覆盖率问题。我们提出一种高可扩展性的 Graph Embedding 方法，该方法可学习到能够可描述图中节点间高阶的、非对称相似度的低维 Embedding 向量。同时我们提供理论上的解释，来阐述这种基于机器学习的方法和基于预定义的传统节点 I2I 相似度的关系。
1.背景介绍 & 相关工作
图是一种抽象程度高、表达能力强的数据结构，它通过对节点和边的定义来描述实体和实体之间的关联关系。常用的图有社交关系网络，通信网络，商品网络，知识图谱等等。
而如何衡量图中节点之间的相似度，对于朋友推荐、商品推荐、以及常见的分类聚类问题来说都是一个很重要的前置步骤。Graph Embedding 可以理解成是一种降维技术，它可以将图中的节点映射到一个低维空间里，我们只需要通过计算低维向量之间的关系，就可以得到原来节点之间的关联关系。
尽管传统 Embedding 技术被研究了很久，但他们的复杂度往往都在 N^2 级别以上，难以适应大规模数据。最近的一系列可扩展性较强的 Graph Embedding 工作主要是从 DeepWalk【6】开始，后面有 Line【7】，Node2vec【2】等等。DeepWalk 在原图中做了一些路径采样，然后将路径当作一个句子，路径中的点当作单词，之后就采用 word2vec 中提出的 Skip-Gram with Negative-Sampling【5】方式进行训练，得到每一个节点的 embedding 向量。Line 只针对边进行采样。Node2vec 可以调节参数来进行 BFS 或者 DFS 的抽样。
然而图中的路径采样在概率上有着非常严重的非对称性，之前的这些方法并没有注意到这件事，也没有从理论上来思考为什么这么干不太科学。
例如在有向图（图 1）中，对于 A 来说，可能并不关心 C，而对于 C 来说，A 很可能是他的兴趣点。即使在无向图中（图 2），也有同样的现象。这样的节点非对称性关系是由于节点周围的图结构不同造成的。而从 C 出发的路径 C->B->A 和从 A 出发的路径 A->B->C 有着完全不相同的概率（0.5，0.08）。因此我们不能认为 C->B->A 这条路径的产生会带来一个（A->C）的正样本。
图 1 有向图中的非对称性
图 2 无向图中的非对称性
2.我们的工作
我们的工作所做的改进其实非常简单，首先为了有能力表达非对称性相似度，我们为每个节点引入了两种 Embedding 向量，分别是 Source 向量和 Target 向量，如图一所示。我们将对于 A 来说 B 的相似度记为 sim(A，B)，并使用 Source(A) 与 Target(B) 的点积来表示，图一中我们可以从 Embedding 中算出 sim(A，C)<sim(C, A)。
图 3 节点的两种 Embedding 身份
其次我们遵循了一种标准的、用来估计 Rooted PageRank【3】的蒙特卡洛随机游走的方法【1】【8】来进行正例的采样。
节点 u 对于节点 v 的 Rooted PageRank（PPR）值代表了从 v 出发落在 u 点的概率。我们认为以这种方式生成图中节点对的正样例是更加自然、合理、有说法的。
这类游走方法都是基于常见的 Random Ｗalk with Restart，即从一个点出发以（1-alpha）的概率选择邻居进行跳转，另外 alpha 的概率跳转回自己。那么现有的几种方法稍有一些区别：
例如 Monte 拉长的保温杯 End Point 只保留首次跳转之前的节点，Monte 拉长的保温杯 Full Path 保留路径上的所有节点，将路径的后缀也当作有效的采样【1】。因为这两条路径对于起始点来说可以看作是相互独立的。在最新的工作中也有对前缀路径进行重用的【8】，就不再此展开。值得注意的是，后两种的采样效率相对于 1 来说要更高，尽管这三种方法都在各自的文章中被证明是正确且有 Bound 的。
我们遵循这类游走方法，企图给图中的节点对创造一些正样本。对于每一个被标记为正例的样本（A, B）我们会根据目标函数更新 A 的 source 向量和 B 的 target 向量。并且随机采样其他的节点作为负样本。
我们定义给定节点 u，可以预测到节点 v 的概率
利用 Skip-Gram with Negative-Sampling【5】，近似等价于优化
K 是负采样数，P_D（n）在图中可用均匀分布替代。则总的目标函数如下：
下面我们来解释一个有趣的现象，我们非对称的点积最终会是以学习出两点之间的 PPR 的对数为目标。
这里，类似于 Levy【4】的证明，当维数充分大时，可看作互相独立的变量。于是另下式为 0：
得到：
由于|V|, k 均为常数，我们可以看出 x 只跟 Rooted PageRank 的模拟值 Sim_u(v) 呈对数关系。通过以上证明，论证了该方法可以保持非对称的、高阶相似度的说法，因为 Rooted PageRank 就是一种非对称的、高阶的相似度度量。
3.小数据集上的实验
Link Prediction Task（AUC）：Embedding 方法相对于传统 Pre-defined i2i 指标来说，在 AUC 上很占便宜。因为传统指标大多基于 2 跳以内的关系，包括阿里内部使用的 Swing。这样就有很多正例的结果是 0——完全无法和负例分开，AUC 不高。可以看出我们的方法（APP）在比现有的方法要好一些。
下表是为了体现非对称性的优势，而在负样本中加大了单向边的比例，即 A->B 有边，B->A 无边。可以看出我们与之前的方法在 LinkPrediction 任务上有显著提升。
Node Recommendation：
值得注意的是，在寻找 topk 的这个问题当中，我们发现之前的 Embedding 方法似乎并没有传统指标靠谱。但我们的方法可以比较好的反应 Topk 的相似关系。
4.在模块千人千面中的实践
为了缓解用户在店铺内部行为的稀疏性，我们将用户 Session 中的全网点商品击序列转化成一个全网商品点击转换图。之后应用我们的 Graph Embedding 方法得到商品向量。该向量可以用来计算用户点击行为所产生的商品之间的相似度。下图是我们与传统 topk i2i 方法在真实场景中的点击率比较。
我们的这项工作目前还只是作为 Match 打分的基础算法，我们正在尝试进一步融合一些外部信息，如商品文本属性、类目信息等，提高长尾商品的结构化 Embedding 质量。
参考文献：
1.Fogaras, D.; R´acz, B.; Csalog´any, K.; and Sarl´os, T. 2005. Towards scaling fully personalized pagerank: Algorithms, lower bounds, and experiments. Internet Mathematics 2(3):333–358.
2.Grover, A., and Leskovec, J. 2016. node2vec: Scalable feature learning for networks. In International Conference on Knowledge Discovery and Data Mining. ACM.
3.Haveliwala, T. H. 2002. Topic-sensitive pagerank. In Proceedings of the 11th international conference on World Wide Web, 517–526. ACM.
4.Levy, O., and Goldberg, Y. 2014. Neural word embedding as implicit matrix factorization. In Advances in neural information processing systems, 2177–2185.
5.Mikolov, T.; Sutskever, I.; Chen, K.; Corrado, G. S.; and Dean, J. 2013. Distributed representations of words and phrases and their compositionality. In Advances in neural information processing systems, 3111–3119.
6.Perozzi, B.; Al-Rfou, R.; and Skiena, S. 2014. Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, 701–710. ACM.
7.Tang, J.; Qu, M.;Wang, M.; Zhang, M.; Yan, J.; and Mei, Q. 2015. Line: Large-scale information network embedding. In Proceedings of the 24th International Conference on World Wide Web, 1067–1077. ACM.
8.Liu, Q.; Li, Z.; Lui, J.; and Cheng, J. 2016. Powerwalk: Scalable personalized pagerank via random walks with vertex-centric decomposition. In Proceedings of the 25th ACM International on Conference on Information and Knowledge Management, 195–204. ACM.