当机器学习遇上复杂网络：解析微信朋友圈 Lookalike 算法
每天在微信朋友圈，用户都会或多或少地收到一些广告推送。有的十分精准，有的却未必。机器学习是人工智能的一个重要分支，也是未来技术趋势里的重要角色。那么，微信是怎么做的呢？
本文整理自腾讯机器学习高级研究员易玲玲在ArchSummit 北京 2016的演讲。回复关键词「机器」，下载完整版PPT。
Lookalike是做什么的
基本上所有的互联网公司都有其广告投放平台，这是给广告主投放广告的一个页面。广告主可以通过广告提交页面提交自己的广告需求，后台会给广告主圈定一部分潜在用户，这个就是我们称为Lookalike的模块。
一般的Lookalike会怎么来做呢？它会有两种做法：第一种就是显性的定位，广告主根据用户的标签直接定位，比如说通过年龄、性别、地域这样的标签来直接圈定一部分用户进行投放。这个时候我们的技术支持就是后台的用户画像的挖掘。这其实是广告主对自己产品的理解，圈出目标用户。
这种人工定义的方法，可能不够精准，或者可能通过年龄和地域指定的用户量很大，需要做精准筛选，这个时候，需要lookalike的第二种做法，通过一个机器学习的模型，来定位广告主的潜在用户。
这个问题怎么转化成一个机器学习的模型呢？学习样本是什么? 优化目标是什么？此时，广告主提交一批客户名单，我们称之为种子用户，它作为机器学习的正样本。负样本我们会从非种子用户，或者是说平台会积累历史的一些相似的广告作为负样本，这个问题就转化为一个二分类的模型，正负样本组成学习的样本，训练模型之后，利用模型结构对活跃用户进行打分，最后得到广告主需要的目标人群。
回顾一下这个流程，广告主会提供他已有的客户名单作为种子用户，这是机器学习的正样本，然后会从活跃用户里面（非种子用户）或者历史我们已经积累了相似的广告负反馈的用户，作为负样本，训练一个二分类的模型，利用模型结果对这个用户进行打分排序，取出广告主需要的目标数据的用户。
对于特征和模型算法，不同的公司各有差异：特征取决于公司有哪些数据；在模型算法上，Facebook 和Google对外公布的说法就是一个预测模型，Yahoo发表过几篇论文，详细介绍过它的算法，比如LR，Linear SVM，GBDT都有尝试，论文里面提到的是GBDT的效果比较好。下图列出了不同公司的做法，供大家参考。
微信社交Lookalike是怎么做的
微信朋友圈的广告怎么进行潜在用户的定位呢？显然，我们也可以把它转化成二分类的预估模型来做。然而有没有一个更好的思路呢？我们可以从微信朋友圈广告这个问题本身先做一些探索分析。
微信朋友圈的广告和其他的广告平台差异点在哪里？下图是微信朋友圈的广告形式，比如万科投广告，我们会以他的公众号在用户的朋友圈里出现。
如果我和我的朋友同时收到这个广告的时候，它会形成用户之间的互动。大家也可以回想一下，大家有没有因为某个好朋友对一个广告进行了点赞或者评论，而引起你对这个广告的关注呢？其实很多时候都会的。
我们再看看数据，大家可以看下面的数据图表，这个横轴是与广告进行互动的好友个数，纵轴是用户对广告的关注率（包括查看，点赞或者评论），我们发现这个关注率会随着好友数的增加而上升。这个数据拐点差不多是3到5个好友。我们再深入思考一下这个数据背后的原因，为什么会出现这种数据的相关性？因为我和好友有相同爱好？因为朋友评论了广告我才关注？
实际上，这两个方面就是社交关系数据的两个核心价值，也就是社交同质性和社交影响力。这正是网络科学研究界的学者给出来的比较严谨的定义。
同质性说得更容易理解一点，就是相似性，我们跟好友可能会有兴趣的相似，或者我们同一个行业我们有行业背景的相似，我们才会形成好友。比如拿广告投放来说，广告主给了我客户名单即种子用户，是不是我种子用户的好友也会喜欢这个广告？
另一个维度就是影响力，影响力说的是我的行为会受到好友的影响。那这个点投放到朋友圈广告上，我可以看到朋友对广告的反馈，会受到他的影响。
所以说做朋友圈广告，我们重点会挖掘这两个价值，就是社交同质性和社交影响力。
讲到这里，再回到我们的问题，怎么给广告主挖掘潜在用户？ 基于广告主给出的客户名单，是不是可以做一个这样的尝试：找这批广告主的好友作为潜在用户，一就是社交相似性，二在微信朋友圈这样一个投放平台，同用户之间的行为会因为社会影响而形成传播，即微信社交Lookalike的基本思想。
那么，另一个问题又来了。 社交同质性、影响力如何量化？当种子用户的好友非常多的时候，如何对好友进行排序选择？家人排前面？闺蜜排前面？还是同学、同事排在前面？人工规则强依赖于业务经验，那我们能不能利用机器学习的方法对社交相似度进行量化呢？
我们通过历史投放的广告采集到学习样本，比如说我的好友有400多个，对于有一部分好友我跟他历史上有同时曝光到一些广告，这些好友我可以计算出我跟他的广告相似度，就等于共同点击的广告数除以共同曝光的广告数。而剩余的好友，历史上没有共同曝光过广告。那我们有其他领域的数据，比如说我跟他的亲密关系，浏览或者阅读文章等兴趣相同点，能否通过这些社交的行为数据，预测到我跟他在广告上的喜好度？
回看我们的网络数据，比如我们的好友关系网络，文章阅读转发网络等等特征工程，我们怎么从网络数据做这个特征工程？
机器学习的输入一般是向量或者说矩阵，图结构特征表达，可不可以用一个降维的方法把图里面的节点表达成一个隐空间的向量，在NLP也会把词表达成一个向量，这是14年谷歌发布的一个Wodrd2Vec的算法包， 将一个单词embedding为一个项目，这个是结果。
如何把图结构切入一个向量？从Wodrd2Vec到node2vec，词里面单词的词频分布，它是幂律的，有些常用词出现的频率非常高，尾巴上的词出现的频率比较低。
实际上在一个社交网络的节点也是这样的，我们经常会存在一些大的节点，他会有非常多的好友，有的人好友就达不到那么多。所以说其实在社交网络里面的一个节点的分布也是幂律分布。如何把Wodrd2Vec迁移到node2vec，这个时候就要产生一个节点的序列，它对应到了自然语言处理的一条句子，图结构里面的节点相当于NLP的一个单词。
所以在图网络上按照一个搜索的方法生成节点序列，这个节点的序列可以对应到自然语言的一个句子，后面我们通过Wodrd2Vec的框架，将节点embedding为一个向量。所以对于做network embedding的时候，这个生成节点序列的搜索策略非常重要。最简单的一个方法，就是随机游走，随机游走一方面生成节点序列，另一方面也是对图的一种采样，降低了计算量。
我们说社交数据最重要的特征就是社交的同质性。所以说我们在network embedding的时候，把社交同质性这个特征保留下来。我们结合网络的社团性质对随机游走的算法进行调整， 比如说A节点走到C，再走到E的时候，它再往下走，这边就相当于它会走到另外一个社团。它设置了一个节点P和Q，P大的时候它是往回走，因为社交网络的特征会形成这样的社团性。
比如说我们的一个社交网络，我的同学会形成一个社团，设计这个P往回走，就更容易走到我这个群体。当P越大，它会越能体现同质性。Q越大的时候，它其实能够体现这种结构的相似性，不同的节点有不同的作用。比如说F节点和E节点它是连接这两个社团的桥接点。当Q大的时候，它体现的是网络结构的相似性。这时候我们怎么选P和Q？这个可以根据实际任务进行半监督的学习。
再回顾一下刚才我们说的Node2vec的流程，首先通过有偏随机游走，生成一个节点序列，后面是word2vec的算法框架得到这个节点的向量表达。其中的参数调优，根据我们保留的同质性，或者根据实际的任务进行调参。
给大家看一下node2vec的结果，先给大家看这个算法的输出。这里有一个简单的图，做embedding之后的结果，1和2的节点向量是一样的，它会是重叠的一个向量，3、4、5、6也是一个重合的节点，它表达的是什么呢？为什么1和2完全重叠？其实1和2的网络环境是一模一样的，这个embedding的结果表达是是节点的社交网络环境，也就是我们说的拓扑特征。
我们做node2vec还会有其他什么好处呢？以好友沟通网络为例，我有120个好友，实际上我沟通网络并不会跟那么多好友经常聊天，也就是说这个数据非常稀疏，在node2vec的输出结果上再计算亲密度，其实我跟所有好友的亲密度都是可以计算出来的。第一个带来的好处就是解决数据的稀疏性的问题。另外，这个结果具有稳定性。
对于沟通网络，比如说，我跟一些好友沟通可能是事务性的，不能表达亲密度的。比如一些客户，或者服务中介等，因为我跟他没有形成社交圈，在做embedding的时候， 产生序列的邻居共现次数比小，embedding出来的结果就是这些人员在亲密度排序上会排在后面，而相对来说，真实关系紧密的，比如亲人，闺蜜，同学，同事会比较稳定的排在前面。
对社交相似性的学习框架，大家可以看下面的图。 我们建立一个回归的model。现在做的是SVR模型。输入好友网络，沟通网络、文章的转发阅读网络等等，进行embedding得到特征向量表达，通过SVR模型，学习到这些特征和广告相似度的函数关系。这个函数关系计算出好友相似度，可以对好友进行排序。
我们看一下算法的效果。我们评估算法的效果，最直接的就是说我有多个算法，广告主需要100万的用户，我这几个算法都给出100万用户，然后看一下这100万的用户点击量是怎么样的，我们叫Lift值。其他的算法跟它进行对比，看一下它的效果有没有提升。那我们的算法相比直接的二分类模型有2倍-3倍的lift。
写在最后
本次主要介绍了社交Lookalike的探索性的分析，社交的同质性和影响力，并重点分享了社交同质性量化问题。后面我们希望把Lookalike系统做成一个动态的，比如我为某个好友点赞，下面我需要推送的人是我的好友，我能影响到那些好友。把这个社交影响力进行量化，并且结合到广告投放里面去。假如说用户能够形成主动传播广告，这样的话它是一个非常好的局面，相当于用户自助的对广告进行口碑的传播。