Pixie: A System for Recommending 3+ Billion Items to 200+ Million Users in Real-Time
概述
这一片论文和上一篇介绍Youtube推荐架构的论文很像，也是结合了工程和算法实现的文章。这一篇主要介绍了来自Pinterest的新推荐架构Pixie（这名字读起来像是在喊我一样……尴尬），Pixie走了一条和Youtube截然不同的推荐路线。其以Random Walk算法为主扩展和升级实现了Pixie。
不同于之前介绍的绝大部分算法都是端到端的有明确的训练目标的模型，本文中的Pixie Random Walk算法并没有直接对某个目标进行建模。从原理上讲这是一种类似协同过滤的方法，通过隐含的聚类发现方法来寻找和目标内容最为接近的内容。由于没有训练学习的过程，因此从架构角度来看可以相对容易的做到实时更新以及非常快速的在线预测。
从我的个人感觉来说我会觉得这个方法非常适合支撑极大规模的内容推荐，但是相应的在泛化、长尾召回等方面会存在先天的劣势。当然如果这个结果的输出作为一个召回的结果来看待会是一个性价比很高的方案。
方法
传统Random Walk
Random Walk算法在之前的文章中已经介绍过了，这里简单说一下传统Random walk在推荐系统里如何直接应用。
一般来说Random Walk算法用以捕捉图结构的信息，譬如Twitter - Who to follow功能就是通过这个方法来进行计算的，其使用了单台机器存储了所有用户的关系网络然后在这个图上运行SALSA算法来计算推荐的关注人。SALSA算法我不是很了解，这里留个TODO后续学习之后补充上。
TODO: SALSA介绍
Random Walk用于推荐的基本算法如下：首选确定一个节点或者一组节点，可以是用户的行为历史也可以是用户的当前行为。基于这样一组节点随机选择和该节点相连接的节点进行遍历得到一组新的节点，再基于这些节点随机选择相连接的节点进行遍历。重复以上过程直到满足收敛条件（最大迭代次数、最大遍历节点数、收敛参数等等），计算所有被遍历到的节点被遍历的次数，从高到低排序就得到了推荐内容的列表。
Pixie Random Walk
Pixie Random Walk是Pixie系统中核心的算法，其在Random Walk基础之上做了诸多优化使得性能和效果都得到了显著提升，具体的：
Biasing the Pixie Random Walk
这个方法旨在通过用户个人信息来调整图谱结构，使得对于每一个用户图谱的内容都是不同的进而做到了更好的个性化。因此在算法中随机选择相连接节点这个过程被调整为按照用户个人的偏好来选择节点。文中没有详细的说明其使用了什么方法来计算用户的偏好，但是大体上看是通过用户的主题偏好、语言等特征对边进行打分从而进行过滤/加权采样。
Multiple Query Pins with Weights
当起始的节点不止一个的时候，有两个问题就需要去考虑了：每个节点是等权的吗？每个节点的遍历长度是一样的吗？如果这两个答案都是否那么就不能用简单暴力的方法来解决了。原文中给出了一个这样的解决方案。假定每个起始节点的权重是$w_q$其中$q \in Q$，$Q$是全部起始节点集合。那么考虑到对于一个出度很高的节点其遍历长度应该是更长的，所以每个起始节点的遍历长度如下：
\[s_q = |E(q)| \cdot (C - \log |E(q)|)\] \[N_q = w_qN\frac {s_q} {\sum_{r}^{Q} s_r}\]其中\(\|E(q)\|\)表示节点\(q\)的出度，\(C = max_{p \in Q}\|E(q)\|\)，\(N\)表示总体遍历次数，\(N_q\)就是节点\(q\)的遍历次数。
Multi-hit Booster
接上个问题，如果起始节点是多个节点并且权重不同，那么在计算最终的每个节点的遍历计数的时候来自不同起始节点的遍历权重是一样的吗？直观的看应该是不一样的，因此本文提出了一个Boost方法来计算最终每个被遍历到的节点的分数：
\[V[p] = (\sum_{q}^{Q}\sqrt{V_q[p]})^2\]其中$p$表示一个被遍历到的节点，$V[p]$表示最终节点的得分，$V_q[p]$表示节点在$q$起始的遍历路径中的得分，如果遍历节点为只有一个那么得分不变。
Early Stopping
这个方法就是解决上文中提到的收敛条件。从每个起始的节点$q$出发遍历图$N_q$次是可以计算出需要推荐的节点的，但是有没有可能在不损失或者轻微损失效果的情况下加快遍历速度尼？如果图的规模非常大或者连接非常稠密这一问题就变得很重要。那么这篇文章也提出了一个非常简单的方法，其目标就是如果遍历的节点中被访问次数最多的一些节点已经不太可能发生变化（也就是头部的节点基本固定了）那么遍历就可以停止了。而实现的方案做了进一步的简化也就是当$n_q$个节点一共被遍历$n_v$次之后，遍历就可以停止了。
Graph Pruning
通过以上几个优化Pixie实际上已经获得了远超过过去推荐系统的效果，但是其仍然有巨大的优化空间那就是以上的优化只考虑了图中的连接关系，那么是否有可能把节点本身的信息加入到计算中继续提高效果？
如果能通过计算节点之间内容的相关程度进而过滤掉大量的不靠谱的节点连接关系以及连接过于分散的节点（我在行文中尽量避免涉及到具体的Pinterest中的产品概念，这里我继续用通用的解释），也就是一类节点可能和各种各样的节点相连接（譬如Cool Awesome这样的Tag就是可能会连接到各种各样的内容上但是这种连接本身意义有限）而连接本身并没有太强的意义，那么Random Walk采样这样的连接就会影响最终的效果。
同时减少连接量（或者说剪枝）也非常有利于提升系统的性能、减少资源的占用一举两得。本文中介绍了一种剪枝的方法得到了非常好的效果和性能的提升。
- 首先计算每个节点的语义向量，文中提出用LDA模型计算节点的描述信息的方法计算向量。
- 计算与节点$p$相连的所有节点的向量的熵，如果熵值非常的高那么说明节点$p$的连接发散程度太高，将该节点以及与该节点相连的所有边全部删除。
- 计算相连的节点之间的向量的cosine相似度，删除那些相似度非常低的边。
经过以上优化，Pixie的图的规模从70亿节点超过1000亿条边减少到30亿节点170亿条边而推荐相关度提升了58%。
实现
Pixie的具体实现在文中有简短的介绍，总体来说有如下特点：
- 为了提高性能主要服务都是C++编写的
- 自定义了一套图存储结构用以高效的存储图数据
- 实现了一套高性能HashTable作为Random Walk时的计数器
- 图生成时首先经过一系列Hadoop MapReduce任务计算得到全部的节点和边的关系
- 使用了一台内存在T级别的机器加载Hadoop生成的节点和边的关系运行图剪枝等算法，最后生成一个二进制的文件保存图内容
- 在线服务加载二进制图文件到内存中，采用多线程的方式执行请求
- 以上图计算、更新的过程每天执行一次
以上实现总的来说……亮点不是很多，高性能图存储、HashTable等等都有很多重量级的开源项目，压缩算法也有非常棒的开源实现：
- 超级HashTable：HighwayHash
- 超级压缩解压算法：Snappy
不得不说在工程方面，Google依然是很多公司的祖师爷级别。
总结
这篇文章总的来说中规中矩，没有特别多新颖的方法但是工程实现稳扎稳打，其无论是算法还是工程实现都有很多可以参考借鉴的内容。
当然我认为一个优秀的推荐系统仅有以上的功能是不足够的，而且其更新的周期仍然有很大的优化空间（譬如实时图更新？）。