大图中如何快速计算PPR

博客引流

终于写完了花了快一周累拖延症的无奈
然后发现知识点好多害啪
回想一下现在ML领域逐渐走向交叉态势不应该再拘泥于一个小方向
还是要多学习
关键词: PPR TopPPR Chernoff bound Alias Method Multi-armed Bandit
本文预计需要20-30min

首先我们应该对什么是PageRank有了一定概念没有的话请点👈

$PR(u) =\alpha \sum\limits_{v \in N_{in}(u)}^N \dfrac{1}{N_{out}(v)}PR(v) + (1-\alpha) \dfrac{1}{n}$

$\vec{PR}^{l \cdot T}=\alpha ^l\vec{PR}^{0\cdot T}P^l+\dfrac{1-\alpha}{n}\vec{1}^T(\alpha^{l-1}\cdot P^{l-1}+\cdot \cdot \cdot+\alpha P + I)$

PageRank相当于站在上帝视角进行评价所有节点的重要程度值

必须遍历所有网络上的节点才能进行计算

实际上我们并不知道互联网有多大也没法从全局的视角评价所有节点

当然也是为了更个性化的评价

于是就有学者提出PPR

跟我念 PPAP PPAP PPR

PPR = Personal Page Rank value

以个人节点出发计算PageRank值

$PPR_s(u) =\alpha \sum\limits_{v \in N_{in}(u)}^N \dfrac{1}{N_{out}(v)}PPR_s(v) + (1-\alpha) \dfrac{1}{n}$

PPR的公式和PR的没什么区别只是PPR的值都是基于某一个节点s 这样的话就对PPR的研究就可以分为两个维度

给定一个Source S, 返回所有节点关于s的PPR值
给定一个Source S, 返回Top-K节点关于s的PPR值
- 当然最笨的办法就是先把所有节点的值都算一遍然后再排序当然想效率高一点一般不这么做
- 对于这种问题如果PPR值比较小，那么对它的估计误差就不是特别重要（当然不能误差到Top-K）
- 很显然这个问题在实际生产过程中更具有价值

在计算PPR的时候还是需要进行递归计算的

递归就需要停止边界

$|\tilde{\pi}(s,t)-\pi(s,t)|\le\epsilon\pi(s,t)$
$\pi(s,t)\le\delta$ (一般而言 $\delta = O(1/n)$ )
举个栗子, 在选Top-3的时候

$\pi(s,v_1)=0.45 ,\pi(s,v_2)=0.2, \pi(s,v_3)=0.18, \pi(s,v_4)=0.17, \epsilon=0.1, \delta=0.01$

在 $\tilde{\pi}(s,v_1)=0.45,\tilde{\pi}(s,v_2)=0.2, \tilde{\pi}(s,v_4)=0.18$ 时，有

$|\tilde{\pi}(s,v_4)-\pi(s,v_4)|\le0.1\pi(s,v_4), |\pi(s,v_4)-\pi(s,v_3)|\le0.1\pi(s,v_3)$ 分别为收敛性和相似性

不再care top-K后面的排序和值是否是对的

PPR的有极强的工业应用场景 ~~(就是给的钱多)~~

比如说鹅厂王者荣耀的好友推荐就是基于PPR的 ~~(一般人我不跟他说)~~

A厂主营业务TB的『千人千面』算法

还比如说实体消歧 ~~(消除歧义我第一次听见这个名词的时候也是一脸懵逼的)~~

还有社交网络的关系查询羡慕这么好找工作的实验室

当然PPR复杂度较高所有有一些对它的近似估计算法下面就来大致介绍一下👇

Monte Carlo Method

[Andersen et al. 2007]

那什么是蒙特卡洛简单来说蒙特卡洛就是一类随机算法

一般把蒙特卡洛和拉斯维加斯放在一起比较

蒙特卡罗算法：采样越多，越近似最优解
拉斯维加斯算法：采样越多，越有机会找到最优解

举个很经典的🌰

蒙特卡洛就是: 从100个🍎s中挑最大的，拿一个在手上，再随机挑一个，选二者最大的，除非遍历到最后一个，否则只能给出一个近似最优解
拉斯维加斯就是: 从100把🔑中找到能开门的钥匙，不能保证一定找得到解，但找到了肯定是最优解

那么这里的MC算法就是以随机游走的概率估计PPR值 ~~(其实相同的方法我们在PageRank的计算中也提到过)~~

那么这样的估计就是一个无偏估计每次Random walk都是对所有点的无偏估计！

可以感觉出来Random walk越多估计的就越准

对固定一个点每次Random Walk的结果之间都是独立的

那么就可以利用Chernoff bound(切尔诺夫界限) ~~你可以把它理解为一个大数定理一样的东西~~

对任意 ${x_i}\in[0,1](i\in[1,n_x])$ , 均值为 $\mu$ 的随机变量, 有 $Pr\left\{|\sum\limits_{i=1}^{n_x}x_i-n_x\mu|\ge n_x\epsilon\right\}\le exp(-\dfrac{n_x\dot{}\epsilon^2}{2\epsilon/3+2\mu})$

假设Random walk的次数 $\ge O(\dfrac{\ln{n}}{\epsilon^2})$

那么达到停止条件 $|\tilde{\pi}(s,t)-\pi(s,t)|\le \epsilon$ 的概率至少 $1-\dfrac{1}{n}$

则带入Chernoff bound得到 $exp(-\dfrac{n_x\dot{}\epsilon^2}{2\epsilon/3+2\mu})< O(\dfrac{1}{n})=\delta$

则推出Random walk实验次数 $n>-\dfrac{c}{\epsilon^2}\log{\delta}=O(\log{n})$

然后这个过程也算是一个PAC过程

PAC =Probably Approximately Correct

达到0误差是非常困难而且没有必要的所以需要争取误差比较小 $\le \epsilon$ 得到近似正确的概率比较大 $\ge 1-\delta$

Forward Search

[FOCS’06]

每个node包含

Reserve: $\pi_f(s,v)$ 随机游走到v，且停在v
Residue: 随机当前游走到v，不停
- 在递归过程中 $r_f(s,v)$ 代表着未分配的概率值

举个🌰 ，如图每个节点转移出去的概率为 $1-\alpha$ , 留在节点的概率为 $\alpha$ , 则

image

第一个节点没分配的时候 $\pi_f(s,s)=\alpha$ , $r_f(s,s)=1-\alpha$
当分配到第二轮的时候 $\pi_f(s,s)=\alpha$ , $r_f(s,s)=0$ , $r_f(s,v_i)=(1-\alpha)/3$

则有 $\pi(s,t)=\pi_f(s,t)+\sum\limits_{v\in V}r_f(s,v)\dot{}\pi(v,t)$

当 $r_f(s,t)$ 很小的时候，运算就没必要再进行下去了

其时间复杂度为 $O(\dfrac{1}{r_{max}})$

Backward Search

[WAW’07]

有Forward 很容易想到是不是有Backward

此时 $\pi_b(v,t), r_b(v,t)$ 的定义和Forward基本一致

Reserve: $\pi_b(v,t)$ 从v出发，运行到t, 且停在t
Residue: $r_b(v,t)$ 从v出发, 当前走到t，不停

image

同样可以推出

\pi(s,t)=\pi_b(s,t)+\sum\limits_{v\in V}r_b(v,t)\dot{}\pi(s,v)

当然可以吧Forward Backward结合在一起通过并行加快计算效率

FORA

[Wang et.al, KDD’17]

由上述可知

Forward 精确解代价太高可以较早的停止，但尾项不能保证近似解
MC 可以保证得到的是近似解但效率低下

就有学者把这两者结合在一起

在计算较大 $\pi_f$ 时使用Forward 当Forward进入停止迭代尾项的时候使用MC进行计算以提高精度

[图片上传中...(image-7117dd-1541592244992)]

MC那么精确那为啥不一开始就用MC呢

Forward的cost大概在MC的 $1-\alpha$ 倍左右, 举个栗子还是Forward那张图

$Cost_f=(1-\alpha)w/\alpha+d_out$
$Cost_M=w/\alpha$

这在数据量较大的情况下差距还是比较可观的

image

Alias Method

现在插播一个算法

Alias Method 是一种大图中经常会用到的带权采样算法

一开始看见这个算法名字的时候觉得很眼熟

然后我同学提醒我~/.zshrc中有 ~~(尴尬不失礼貌的微笑)~~

直译过来就是别名采样算法 ~~(别问我采样怎么译出来的)~~

考虑一个问题:一个随机事件包含四种情况, 每种情况发生的概率分别为: $\dfrac{1}{2}$ , $\dfrac{1}{3}$ , $\dfrac{1}{12}$ , $\dfrac{1}{12}$ , 问怎么产生符合这个概率的采样方法

一个很简单的思路就是产生一个 $x\in[0,1]$ 的随机数然后根据x检索到详情的具体情况, 这样就转变为搜索问题, 用BST可以达到 $O(\log{n})$ 的复杂度

那有没有复杂度更好的算法呢？（我觉得 $O(\log{n})$ 挺好的了 ~~尴尬不失礼貌的微笑~~）

Naïve Alias Method

把所有情况排成一列掷两次骰子第一次决定列第二次决定采样是否成功

如图，先掷一次骰子, 先确定是四种情况中的哪一种，如果是A，则100%采样A; 如果是B, 则 $\dfrac{2}{3}$ 概率为B， $\dfrac{1}{3}$ 概率重试

![image](http://upload-images.jianshu.io/upload_images/14621057-673aa5336aba61d2.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

我们来考虑下复杂度, 最好的情况，一次就结束 $O(1)$ ，不好的情况一直一直迭代下去，平均复杂度 $O(n)$

Alias Method

回顾刚才的过程可以发现我们在重试的过程中可能会出现反复重试的情况这样消耗太多有没有什么办法能减少重试次数呢

如果我们能保证第二次掷骰子🎲的时候不是当前类就是其他类那么就不需要重试了吧

想法很好究竟如何来实现呢给出了下图的一个方法

image

通过拼接来实现保证第二次掷骰子的时候不是A就是B

但要注意这个拼接是有条件的:

满足一块中只能最多两个拼接而成
第 $i$ 块必须包含第 $i$ 块的一部分

当然就会产生一个疑问到底是不是都会存在这种拼接

事实上可以证明Alias 拼接的存在性具体参考👉

为什么突然提到ALias采样算法?

回想一下FORA算法第二步MC算法是在第一步达到停止条件之后的随机游动

在随机游走模拟初始化的时候就需要使用判别采样的类别

考虑下FORA的时间复杂度

MC: $O(\dfrac{n\ln{n}}{\epsilon^2})$

则Radom Walk: $O(r_{sum}\dfrac{n\ln{n}}{\epsilon^2})=O(mr_{max}\dfrac{n\ln{n}}{\epsilon^2})$ , 其中 $r_{sum}=\sum\limits_{v\in V}r(s,v)\le \sum\limits_{v\in V}d_{out}(v)r_{max}=mr_{max}$

则Total: $O(\dfrac{1}{r_{max}}+mr_{max}\dfrac{n\ln{n}}{\epsilon^2})$

令 $r_{max}=\epsilon \sqrt{\dfrac{1}{nm\ln{n}}}$

则: $O(Total)=O(\dfrac{1}{\epsilon}\sqrt{mn\ln{n}})$

Top-K single source PPR

事实上在很场景下我们并不关心所有的PPR值

大部分时候只对Top-K感兴趣

如何精准的估计前K个或者说第K个 PPR值成了关键问题

解决Top-K的一个简单的想法就是利用迭代

给定初始值 $\delta = \dfrac{1}{k}$
Run FORA
Test solution
- 通过上下限来评估PPR值
- 如果没满足精度，则 $\delta /= 2$ , 重复第二步
- 如果满足精度则输出

Multi-armed Bandit

然后再插播一个问题？(还是算法) ~~傻傻分不清~~🙉

假如说你进到一个赌场有n台老虎机🎰 看起来这n台老虎机没啥区别
但事实上每台老虎机都有自己的概率分布那么如何制定策略尝试从而在最小的代价下获得最大的利益

这就是多臂老虎机MAB问题

image

其实这是一个在Reinforcement learning, RL领域很火的问题

也拥有极强的应用场景

推荐系统中 EE(Exploit-Explore)和冷启动是两个经典的问题

EE直译就是利用与探索，到底是应该利用目前为数不多的数据进行分析还是应该再做探索拿到很多的信息

冷启动，主要针对的是用户第一次进入系统，在对用户一无所知的情况下，如何更有效的进行推荐

解决这两个问题的一个有效途径就是MAB算法

A/B test

最简单的一种思路就是每台老虎机🎰尝试n次记录回报值哪台老虎机平均回报最大就选哪台

A/B test的核心就是控制变量

每台老虎机在相同条件下尝试相同的次数n
然后根据这 $n×m$ 的结果，对老虎机收益进行估计

但很显然这样的算法要达到一定精准度需要较大的代价

$\epsilon$ -Greedy

直译就是贪婪算法 ~~(很贪婪了)~~

这个算法有点像前面说的Naïve Alias Method, 通过随机结果估计样本情况

指定一个 $\epsilon \in (0, 1)$
每轮结束的时候，以概率 $\epsilon$ 决定探索, 在所有老虎机中选一个作为下一个尝试项
以概率 $1-\epsilon$ 决定利用, 选择当前获取的样本中最好的老虎机作为下一个尝试项

这是一个online过程，随着尝试次数n的增大，所得到的结果就越接近真实值

且随着 $\epsilon$ 值的增大，收敛速度越快 (越激进越有可能发现真理所以同学们要保持对这个世界的怀疑)

但 $\epsilon$ -Greedy 忽略了可能已经表征出来的特征从始至终的都是随机筛选可能会花费过多的时间才能收敛

当然 $\epsilon$ -Greedy 也有很多变种

比如说一开始尝试概率高之后概率慢慢减小
通过预筛选先框定小范围再进行 $\epsilon$ -Greedy

SoftMax

大致思路就是根据现有的信息进行估计选择最可能的情况

根据之前的情况计算每一台老虎机的 $p_k=\dfrac{e^{\bar\mu_k/k}}{\sum e^{\bar\mu_k/k}}$ 值
选择 $p_k$ 值最大的作为下一阶段选择的老虎机

好像和前面的没啥区别都是根据现有的信息来估计分布

实际上 SoftMax的最大特点就是通过一个变量T，Temperature来控制估计范围的力度

T-温度，直观的感受，随着时间的增大，T随之减小那么在分母的T导致现有的样本权值变高越来越占主导地位

另外SoftMax也有一些变体，比如说 $p_k=(1-\gamma)\dfrac{w_k(t)}{\sum \limits_{j=1}^K w_j(t)}+\dfrac{\gamma}{K}$ , 其中 $w_j(t+1)=w_j(t)exp(\gamma \dfrac{r_j(t)}{p_j(t)K})$

UCB

虽然SoftMax已经有一种感觉越多估计越可用但它没有考虑到置信区间的问题 UCB则从置信区间出发

UCB = Upper Confidence Bound

先对每一个老虎机都进行一次测试
计算 $p_k=\bar{\mu}_k(t-1)+\sqrt{\dfrac{2\ln{t-1}}{T_{j,t-1}}}$ , 其中 $T_{j,t-1}$ 为截止到第t轮j这台老虎机试验次数
选择 $p_k$ 值最大的作为下一阶段选择的老虎机

和SoftMax相比只是 $p_k$ 计算方法略有区别然后还多了一次预操作处理

仔细观察 $p_k$ 式子，其中包含了试验次数

随着试验次数的增大后面那项值越小，均值占得比重越大; 而试验次数较小的时候，后项值较大，均值占比较小

从而减少因为采样次数较少造成的错误估计

本质上后一项是均值的标准差

那么为何叫做上置信区间算法呢？其实这个式子是从置信区间推出来的

根据上置信区间公式可得 $P(\bar{\mu}\ge\epsilon)\le exp(-n\epsilon^2/2)$ , 令右侧= $\delta$ , 则有 $P(\bar{\mu}\ge\sqrt{\dfrac{2}{n}\log{\dfrac{1}{\delta})}}\le \delta$

则其均值估计就为 $\bar{\mu}_i(t-1)+\sqrt{\dfrac{2}{T_i(t-1)}\log{\dfrac{1}{\delta}}}$

当然 UCB还有很多改进版本在这就提出一个最朴素的思想

Thompson sampling

之前UCB是从置信度的角度出发考虑问题

而Thompson sampling则是站在贝叶斯的角度通过维护一个beta概率分布用先验估计后验

对每台老虎机维护一个tuple(winner, lose), 里面存放着历史成功、失败数，其中winner，lose为beta分布的参数
每轮，每台老虎机的beta分布随机产生一个值 $p_k$
选择 $p_k$ 值最大的作为下一阶段选择的老虎机

相对而言Thompson sampling的计算量会更小

实际使用效果也和UCB不相上下基本上是目前使用比较多的一个算法

Top-K arm indentification

刚才我们分析都是选择收益最大的老虎机

实际上我们的需求不一定有那么强可能只需要知道一个Top-K的集合就行了

比如说我们这个问题只需要知道Top-K的PPR值

Naïve Solution

选择实验结果的第i大老虎机 $\epsilon$ 范围内的老虎机

image

MC solution

好我们回到前面讲的Top-K single source PPR

想必很多人已经忘记我们这片blog的主题了 ~~(连我自己也觉得我就是在讲🎰)~~

好跟我念 PPAP PPAP PPR 好回到我们的Top-K PPR

利用Chernoff bound估计所有点的UB LB且所有点的 $UB-LB$ 均相等

则带入Top-K single source PPR 根据停止条件 UB LB进行MC迭代

然后根据前面说的banbit算法估计前k个PPR

image

TopPPR algorithm

[Wei et.al., SIGMOD 18]

MC的实际精度表现的比较低，于是又学者考虑把FORA 和Backward结合在一起

利用Backward search改善精度，得到了TopPPR algorithm

image

$\pi(s,t)=\pi_f(s,t)+\sum\limits_{u\in V}r_f(s,u)\pi_b(u,t)+\sum\limits_{u,v\in V}r_f(s,u)\pi(u,v)r_b(v,t)$

但问题是Backward必须知道目标点对Top-K而言就是需要给出一个候选集

于是我们大致把候选集分为三个集合 一定是Top-K的 可能是 不可能是

反复迭代通过Empirical Bernstein不等式计算置信区间

注意在迭代过程中每个点的采样次数不同 UB LB的差也不同

image

回顾下刚才的UB-LB算法可以发现在第k大PPR附近的点很容易被误采样进样本中

好到这里大致把PPR的图搜索算法讲完了

另外PPR的矩阵计算最近几年也得到不错的成果

虽然目前工业界主流采用图搜索算法 (毕竟复杂度 $1-\alpha$ 倍)

Reference

最后编辑于：2018.11.07 20:45:30

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 219,427评论 6赞 508
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 93,551评论 3赞 395
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 165,747评论 0赞 356
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,939评论 1赞 295
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,955评论 6赞 392
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,737评论 1赞 305
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,448评论 3赞 420
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,352评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,834评论 1赞 317
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,992评论 3赞 338
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 40,133评论 1赞 351
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,815评论 5赞 346
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,477评论 3赞 331
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 32,022评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 33,147评论 1赞 272
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,398评论 3赞 373
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 45,077评论 2赞 355

大图中如何快速计算PPR

Monte Carlo Method

Forward Search

Backward Search

FORA

Alias Method

Naïve Alias Method

Alias Method

Top-K single source PPR

Multi-armed Bandit

A/B test

-Greedy

SoftMax

UCB

Thompson sampling

Top-K arm indentification

Naïve Solution

MC solution

TopPPR algorithm

Reference

推荐阅读更多精彩内容

$\epsilon$ -Greedy