本文是youtube在2008年提出的算法，现在回过头去看看它在当时是如何实现youtube的推荐系统的。
一、介绍
YouTube在2005成立，并很快成为用户发现和分享视频的流行网站。在Youtube视频库中有4500w视频，每分钟就有大量的视频上传。该巨大的视频库信息潜在包含了许多用户的视频兴趣。大量视频存在的缺点是，探索和发现新的、吸引人的视频是一项极具挑战的任务。推荐的标准方法已经被广泛应用于文本领域，比如：新闻组，网页新闻，但在视频领域并不简单。主要难点是，尽管通过计算机视觉技术可以打上少量可靠标签，但目前不存在任何比较好的机制对大部分视频内容打标签。更难的是，在YouTube视频上存在的标签相当少；它们只捕获了少量的内容信息。
为非文本内容提供有价值的信息，已经在一些上下文上做了探索。最接近的是Netflix challenge，它的系统会基于之前的评分推荐DVD给订阅者。Netflix有10w的DVD，Netflix的用户在这些视频上提供了大量显式的评分。相反的，在我们的任务上，视频的数目更大，评分很稀疏。我们解决该任务的方法是，利用大量用户在视频累积的观看（views）。通过学习观看模式，来创建一种有效的视频推荐系统，它不依赖于底层视频的分析。为了创建一个个性化的视频推荐页面，它不再仅仅只展示最新或最流行的视频，也会展示根据用户行为推荐出的视频。
在该节中，我们引入了一种主要数据源：co-view statistics。在第2节，我们介绍了吸附（adsorption）算法，并描述了许多相关研究。当我们具有一些标记过的对象，以及一个丰富的关于标记和未标记对象的图结构时，吸附（adsorption）算法会是一种非常通用的分类和学习框架。该算法在数学上非常健壮，它具有三种不同但等价的解释，在应用数学和机器学习领域有多种形式。在第3节，我们介绍了所使用的数据。该系统的评估本身就是一项挑战；每个系统在部署到线上生产环境前必须彻底审查。3.1节探索了在部署前使用历史数据来解释算法效果。实验结果在第4节，第5节则是结论。
1.1 视频的Co-View Graph
Youtube有大量用户们会观看多个视频。一个基础统计是，视频共同观看（co-view）数。在最简单的形式，对于任意的视频对（video pairs），co-view数据会给出那些观看了这两个视频的用户数。该统计会在所有视频上做计算，有许多方法将它们编码成一个图（graph）。在图1中，我们展示了“video-video co-view graph”，视频（相同用户最常看的视频）间会有一个连接。在图2中，我们展示了user-view graph，从中可以看到涉及到的co-views。
图1: video-video co-view graph. 每个视频是该图中的一个节点（vertex），它会与其它视频相连接，称为共同观看（co-viewed）。通常，只有与最少数目的观看量相连接才会被实例化
图2: User-Video Graph. 另一种表示co-view信息的方法是隐式地通过user-video二分图进行表示。co-view的数目通过检查在两个视频之间长度为2的路径来计算。
co-view信息提供了视频推荐的一个基础。一些基于item-based CF的简单系统，就是基于此构建。假设用户U观看了两个视频：J和K。从我们的co-view统计上看，我们可以知道，许多观看了视频J的其他用户也会观看视频L，M，N。相似的，许多观看了视频K的其他用户也观看了视频N, O, P, Q。因此，推荐给U的视频，会基于它的观看J和K，简单通过两个co-view的联集（union）得到：L, M, N, O, P, Q。为了对该推荐进行ranking，我们会考虑视频的观看数（它可以间接描述流行程度），每个视频的co-view数，或者推荐给U的每个视频的次数（注意：视频N会推荐两次），或结合其它的heuristics。
注意，还存在其它版本的co-view统计和图（graphs）可用于上述的情况。通过将co-view限制在只在相同web session中发生可以得到更强的相似度。这种方法可能会有用，人们会认为一个用户在一段时间内在相同的主题上可能会看多个视频（例如，观看多个关于如何以烟灰墨风格进行绘画的指导视频）。其它潜在的co-view变种包括：通过使用有向边来编码顺序信息（ordering information）。这些变种的缺点是，通常会为每个video/user产生一个更小的数据。如果给定大量的视频来计算co-view统计，我们尝试使用尽可能更宽泛的co-view定义。
2.吸附算法(ADSORPTION ALGORITHM)
我们将该算法族称为“吸附（adsorption）”的源自下面的这个问题：假设我们希望将图中的一个节点（node）根据其它节点上的标签（labels）作分类，应该如何去实现？最简单的答案是，在对应图上引入一个metric，通过采用最近邻的labels来分类label。我们可以选择许多种metrics（例如：最短路径、交换时间、电阻等），但对于大图（large graphs）来说，大多数的计算开销都很大。另外，像最短路径这种简单的方法在推荐系统的上下文中存在一定的不好（undesirable）的属性。基于user-video view graph，如果我们给用户u推荐一个他没有观看过的、并且在图中距离最近的视频v，那么我们会结束推荐这样的一个节点：它只通过高的度（high-degree）的节点到达（例如，如果用户u1和u2同时观看了一个流行的视频，尽管他们没有共同兴趣，我们将终止推荐由u2观看过的视频给u1，因为u1到其它视频的路径长度为3，这对于任意u1未观看过的视频都是最短可能的距离（distance））。更复杂的方法，比如往返距离（commute distance）可以避免该问题，但需要更昂贵的计算开销；再者，这些方法不会导致算法准许增量更新，另一个因素对于大型推荐系统很重要。
推荐视频通常与一个用户的观看过的视频构成co-view关系，然而可以通过发现带标签的节点进行抽取，它们离用户节点具有多个短路径（short paths）。这样做时，必须注意不要离开该节点太远，因为，如果连接一个用户到一个视频的路径很长，那么很大程度上会发生兴趣和相关度的漂移。
对于我们的推荐系统的迫切之处是，满足以下条件，那么一个视频v就与一个用户相关：
- (1) u和v在它们之间具有一个短路径
- (2) u和v在它们之间具有多个路径
- (3) u和v的路径应避免高度节点（high-degree nodes）的存在
2.1 基于平均的吸附算法（Adsorption via Averaging）
该算法具有以下的思想。在一个总的图中，一些节点具有标签（labels），这些带有标签（labels）的节点，会将标签（labels）传播给他们的邻居，接着，这些邻居会继续将标签（labels）传给他们的邻居，以此类推，直接所有节点都接收到他们的标签（labels）。这样，每个节点具有两个角色，传播标签（forwarding labels）和接收标签（collecting labels）。在“完全信息（full-information）”的模型中，我们假设每个节点会跟踪它们接受到的所有标签的历史————多久会接收到，在第几轮接收到，等等。这会允许每个节点做出一个知情选择：哪些标签希望保留（retain）。该算法的重要详情是，选择如何来维持一个概要：即保留该通知的基本部分，也能保障标签分配（label assignments）的一个稳定（或收敛）集合。
正式描述如下。我们给定一个图：$ G = (V,E,w) $，其中V表示顶点（节点）集合，E表示边的集合，$w: E \rightarrow R $表示在边上的一个非负权重。假设L表示标签集合，并假设在子集$ V_L \subseteq V $中，每个节点v携带着一个在标签集合上的概率分布$ L_v $。我们通常将$ V_L $看成是带标签节点的集合。为了更好地阐述，我们引入了一个预处理step，其中对于每个顶点$ v \in V_L $，我们创建了一个“shadow”顶点（$ \hat{v} $），它具有一个准确的外邻居（out-neighbor）v，通过一条权重为1的边$ (\hat{v}, v) $进行相连；更进一步，对于每个$ v \in V_L $，我们会重新分配（re-locate）从v到$\hat{v}$的权签分布$ L_v $，留下v不带label分布。给定$ \hat{V} $表示shadow顶点的集合，$ \hat{V} = \lbrace \hat{v} | v \in V_L \rbrace $。从现在开始，我们假设在算法的开始处，只有在$ \hat{V} $中的顶点具有非空的标签分布。
上述代码注释如下：
- (1) 在求和操作中，u和$ V \cup \hat{V} $中的所有顶点各不相同，它具有一个非空的label分布$L_u$。
- (2) 在该算法中，在一轮迭代中，如果没有任何节点的label分布发生变化，那就发生了收敛。实际上，我们会引入一个小的阈值，以便分布的变化幅度过小时就认为是收敛
- (3) 根据收敛，对于每个节点 $ v \in V \cup \hat{V} $，都会带着一个label分布，提供了从v到节点$ u \in V_L $的路径。
- (4) 在边$ (\hat{v}, v) $上每个节点$v \in V_L$的单位权重的选择是完全武断的，可以通过其它方法进行替换；这会是一个非常有意思的特性。
- (5) 机智的读者可能注意到，我们没有在每轮迭代中更新（update）label分布；而是，我们会从头到尾完全计算，基于在近邻上发布的分布。这说明整个算法是平等的，算法的无内存属性可以使得它更易于数学分析。
- (6) Adsorption算法是一个非常有效的迭代计算算法（类似于PageRank），其中，在每次迭代中，一个label分布会沿着每个边进行传递。这在MapReduce模型中很方便进行并行计算。
2.1.1 相关工作
我们的目标是，维持一个关于label的总览，这些labels可以从一个顶点可达（reachable），让我们记住，归一化阶段遵循近邻label分布的权重和计算对我们的算法来说是很重要的。在完成该step后，从多个近邻（or高权重近邻）处接收的标签（labels）趋向于具有更高的块（mass），因而该step将adsorption算法看成是一个传统ML分类器。实际上，该算法是一个关于标签传播算法的修改版本【 Zhu and Ghahrahmani】，Zhu的paper是第一篇使用图模型来设计半监督学习解决该问题。Zhu and Ghahrahmani也提到：它们的算法与【Szummer and Jaakkola】的随机游走算法不同；你可以看到，有一种非常不同的随机游走算法，它与adsorption算法完全一致。由Azran提出。
从一个科学的角度看，“重复平均(repeated averaging)”算法在数学的微分方程中具有一段很长的历史，特别是关于求边界值问题时。该邻域的一个原型问题是，给定边界温度，估计叠在2d网格上一个层流表面( laminar surface)上多个点的热度（heat）；最常见的算法是，对该网格近邻的值做重复平均，直到温度收敛。实际上，该算法的天然泛化性（）是可以通过一个专有图（arbitrary graph）来替代网格，其中有标签的节点与边界点对等。然而，总体上，一个图并不是一个连续结构，你必须处理多个由此引起的异常点。
2.2 基于随机游走的Adsorption算法
adsorption算法的无内存属性，可以产生一个紧密相关的解释。让我们从最后一轮“松开（unwind）”算法的执行，向后回退跟踪。
对于一个顶点$ v \in V $，$ N_v $表示在v的邻近集合上的概率分布，$ N_v(u) = w(u,v) / (\sum_{u} w(u,v)) $，也就是说，u的概率与边(u, v)的权重是成比例的。一个顶点v的标签分布，可以简单成看是一个关于它的近邻标签分布的凸组合（convex combination），也就是说，$ L_v = \sum_{u} N_v(u) L_u $；因此，如果我们根据概率$ N_v $随机选择v的一个内近邻（in-neighbor）u，根据分布$ L_u $抽样一个label，接着对于每个$ l \in L $的label， $ L_v(l) $与$ Exp_u[L_u(l)]$精确等价，其中指数（expectation）来自于根据$N_v$选择一个近邻u给出。将此扩展到距离为2的近邻上，很容易看到，对于每个标签$l \in L$，$ L_v(l)=Exp_{w} Exp_{u} [L_w(l)] $，其中，根据$N_v$选中v的一个内近邻u，根据$N_u$选中u的一个内近邻$w$。向外扩展得到：
\[L_v(l) = \sum_{w} \sum_{u} N_v(u) N_u(w) L_w(l)\]注意，$ N_v(u) $是在从v开始的随机游走并根据$N_v$选择一个近邻中的1个step内从v到达u的概率，相类似的，$N_u(w)$则是根据$N_u$从w到u选中一个近邻的概率。注意，这里Markov属性（无内存）的使用很重要，它基于随机游走，可以到达u，在选择w时使用的唯一信息是$N_u$，它只依赖于u，而不会依赖于随机游走的初始化。
最后，注意，如果随机游走到达了一个shadow顶点$\hat{z}$，其中$z \in V_L $，接着，不存在z的入边(in-edge)，因此随机游走会停止。这样，在$ \hat{V}$上的顶点是 Markov chain的“吸附状态（absorbing states）”，由随机游走定义。吸附算法（adsorption algorithm）等价于下面的变种，在图G的反向（reverse）、从$\hat{V}$到V的边进行随机游走。
在下面的表述中，算法从起点v进行随机游走，当到达一个吸附状态时为它输出一个label分布$L_v$。这样，每个节点的标签分布是一个随机变量，它们的期望（expectation）会为该顶点生成最终的label分布。为了为所有顶点获取label分布，该过程需要为每个顶点重复许多次，接着计算平均分布。很明显，该算法是一种非常低效的算法；因而，实际上，我们开发了该算法的在2.2节点的平均吸附算法的另一等价形式：它会是一个非常有效的实际，尤其适用于并行计算模型。
这里pick-neighbor(v, E, w) 会返回一个节点u，以便$ (u,v) \in E$，具有概率 $ w(u,v) / (\sum_u w(u,v))$
对比算法Adsorption-RW，在图上进行随机游走的固定分布（比如PageRank）的使用具有启发意义。像PageRank的情况，会考虑使用一个固定的Markov随机游走，因而给定了固定概率分布，对于图的每个节点，该游走的概率会访问这些节点。缺少任意的吸附节点（假设该游走是遍历的），在其上对该节点的初始化选择，随机游走的开始与对于在长期上到达任意特定节点的概率确定是完全无关的。因此，这些方法不会允许我们来衡量节点间的相互影响。相反的，在我们的情况下，带标签的节点处于随机游走的吸附状态；因此，该游走的起始点会决定着我们在任意吸附状态停止该游走的概率。这暗示着，我们可以使用这些概率作为节点间相互影响的衡量。
2.3 通过线性系统的Adsorption
该算法暴露的第三个角度，通过观看到：平均算法会自动隐含：在每每个节点v，标签集L的最终分布$ L_v $是一个在$ L_u $的凸组合，其中$ u \in V_L $ （传递给shadow $\hat{u} $）。
实际上，我们可以尝试去描述，将图中每个节点，根据它们的相似度（邻近程度、近邻重合数等），忽略掉是否有标签，作为一个关于其它节点的凸组合，这是一个非常见的问题，有许多潜在应用。实际上，这样做可以给出关于该图顶点到L1的一个embedding（因为，每个凸组合可以写看是一个unit L1 norm的n维向量，其中$ n = | V | $）；这在计算机科学上的研究是一个很热门的主题。由adsorption产生的embeddings不会捕获最短距离，但具有非常相关和有用的属性。embeddings的一个有用之外是，它们具有“连续（continuity）”的天然特性: 在L1上任意节点的图片(images)都是一个关于其它近邻图片的凸组合。据我们所知，这样的embeddings在文献中没有研究，对于特定的应用会非常有用。
通过将吸附算法转换成一个线性等式的系统，你可以更精准获得这样的embedding。进一步，线性等式系统具有一个唯一解，如果底层图是连接的。这产生了在图中进行标签传播问题的第三个算法。一旦我们将每个顶点表示成关于其于顶点的一个凸组合，我们可以获得任意节点的一个label分布，通过采用一个合适的在带label顶点上label分布的凸组合。
该线性系统的视角提供了另一个标签传播的天然算法(natural algorithmic)。另外，它提供了非常自然的思想来获取该算法的高效计算版本。例如，如果u和v不会有任何路径长度超过t，对于一些参数t，我们可以限制$ X_{uv} = 0$。它具有稀疏化（sparsifying）这些等式线性系统的效果，这可以帮助更有效地求解它。对于视频推荐算法，它也具有一个良好的语义解释：一用户观看了某一视频，如果在该视频半径为t的球体内没有其它用户观看它，就不推荐该视频给用户；这可以帮助控制那些在社群内流行但离该用户距离远的视频的传播，忽略掉它们有多流行。
该视角的另一个好处是，根据等式的线性系统，可以对标签分布进行增量更新，通过为相关的近邻快速更新信息，节点的加或减可以很快适应。
该节的结论，三种adsorption算法是等价的：
理论1: s Adsorption, Adsorption-RW, 和Adsorption-LS是等价的
2.4 注入概率与哑概率（Injection and Dummy Probabilities）
该算法的三种等价形式，导致许多有意思的变种。注意，等式的线性系统的视角，允许对于一个给定节点，我们可以限制哪个标签。我们指出，另一个有趣的变种可以通过采用另一解释来获取。
回顾“shadow”节点$\hat{v}$的概念，它为v扮演着“标签搬运工（label-bearer）”的角色。随着边$ (\hat{v}, v) $边权重的明智选择，（等价的，在逆向图中从v到$\hat{v}$的转移概率的选择）可以帮助我们精准控制随机游走的行为；它具有非常有用的应用。考虑到视频推荐的应用——假设我们从一个用户u开始一个随机游走，沿着边进行，到达一个视频节点v。现在，我们进入到吸附状态$ \hat{v} $的概率必须作为一个关于v的多个特征的函数来决定——它的流行度，新鲜度，社交兴趣，上传该视频用户的声望，等等。这样，该参数（我们称为“注入概率（einjection probability）”）通常在部署一个真实推荐系统时是一个重要的设计选择。相似的，在其它应用上，我们已经发现，该概率的选择在结果质量方面扮演着重要的角色。
下一个参数在控制算法的行为方面非常有用，是我们的等价理论的另一个新探索。考虑到在加权边图上的标准随机游走，我们可以考虑一个“跛行游走（hobbled walk）”，在每一step，有一些概率，我们称之为“abandonment probability” 或“dummy probability”，该算法会放弃随机游走，不会产生任意输出标签。例如，当随机游走访问一个高度节点（high-degree node）时相当有用。例如，在视频推荐上下文中，一个随机游走从一个用户节点u开始。假设在一些step后，随机游走到达了图中的节点z。如果z是一个高度（high-degree）的视频节点（相当流行的视频），再接另一个step将肯定会导致随机游走到那些与u相当不同的用户（因为流行的视频趋向于被没有共同兴趣的大部分用户观看）。相似的，如果z是一个高度（high-degree）的用户节点，再接另一step会导致用户u并不关心的视频（z可能具有很广泛的兴趣）。为了将该特征无缝集成到算法中，我们引入了“dummy” label的思想，在每个节点上修改label分布，来包含具有适当概率的”dummy” label。（通常受节点的度的影响）
我们的实验证实了，加了一个dummy label（相等的，放弃选择性的随机游走）确实是一个有用的特征。它可以以一个可计算的方式降低随机游走：在节点u上的一个标签l的影响，会沿着从带有标签l的节点到u的路径，以带标签节点数的指数方式减少。
3.实验
我们的实验的原始数据，从youtube.com上在92天内（从2007.7.1~2007.9.30）的用户观看视频中收集。我们从指定地理区域(语言、兴趣的主题基本相似）中选择了一个接近540w用户样本。对于每个选中的用户，我们收集了他们观看超过33%完成度的所有视频列表；该限制相当于用户实际上喜欢该视频。这产生了对420w视频的接近290w总观看数（一些可能是重复观看的）。所有数据以匿名的方式抽取，因而我们可以处理用户和视频的二分图（bipartite graph）（如图2所示）。
我们将数据分成两个集合：一个训练集，它包含了前46天的所有观看数据；一个测试集，它包含了其余天的所有观看数据。这里我们使用的这种方法，对应的metrics在第3.1节会讲。训练集被用于运行所有推荐算法，并基于它们的观看生成推荐；这些推荐的效果会与测试集对比进行衡量。考虑到，如果用户u没有在训练时间周期内观看视频v，但在测试时间周期内观看了视频v，我们就认为成功给用户u推荐了视频v。我们将对precision和recall进行measure（可以分别理解成：用户是否观看算法推荐的视频，以及算法是否推荐了所有用户要看的所有视频），这样的做法在信息检索应用上很常见。在我们处理评测准则的细节之前，我们很短暂地表述了所使和数据的一个总述。
首先，如果用户在训练周期和测试周期上同时没有观看行为，我们将这些用户抛弃掉。我们的评估机制允许为每个算法访问训练数据，限制该算法只基于该信息做出推荐。如果用户在两个周期内没有数据，那么没有方法来做出推荐或者为他做出评估。相似的，如果一个视频在训练周期内没被观看过，那么它不会被推荐，我们会移除这些视频。如果一个视频在训练周期中存在，在测试周期中不存在（可能被系统移除、下架），我们不会惩罚任何算法，因为这种case很容易在推荐系统的范围外进行处理，不会影响算法表现。在这些操作后，我们得到了约110w的用户以及130w的视频，约1250w的观看量。
假设，一个用户在训练期观看了视频集合$W_1$，在测试周期上视频集合为$W$，进一步假设，推荐算法从训练周期（对于所有的用户和视频来说）给定所有数据后，会给用户推荐一个视频的排名列表R。对于$ t = 1, …, |R| $，$R_t$包含了在R中前t个视频（以rank的顺序）。下面的定义在信息检索中的标准定义：
precision@t：
\[precision_t(W,R) = | W \cap R_t | / |R_t|\]recall@t：
\[recall_t(W,R) = | W \cap R_t | / |W|\]这样，对于每个在训练周期和测试周期上同时存在的用户u，t的合理值，我们获得了一个值对(value pair): ($p_{t}^{u}, r_{t}^{u})$ 。自然的，我们对跨所有用户进行平均来获取一个关于阈值为t的pair: $(p_t, r_t)$。这些值形成了in-depth分析的基础，包括ROC曲线（Receiver Operating Characteristic），Precision-Recall-Threshold 曲线以及top-rank质量评估。我们也通过每个推荐过程分析了视频集的覆盖率，见第4节。
3.1 推荐的事后检验（Backtesting Recommendations）
我们通过事后检验，指出涉及的微妙之处、注意事项、以及采纳该方法的合理之处，来停止临界分析我们的评测方法。
当没有提供排序(ranking)时，推荐系统的目标是诱使用户观看他们感兴趣的item，评估一个推荐算法的最简单方法是，在线上服务运行该系统，评估用户观看的推荐数目，或者对推荐结果进行人工标注进行评估。然而，这些方法都有一定的实际难点。在我们的研究中，有许多种参数设置和算法变种可以被探索；在真实服务上测试所有这些并不实际。使用足够多的用户来在一段长时间内运行每个变种，来获取统计上的不同之处，与确保在Youtube上的所有用户获得一个持久的、良好的体验相冲突。在该范围内（spectrum），人工标注不能有效地扩展，由于视频和算法变种的数量大。
一个最重要的挑战是，在允许上线部署前，评估推荐的有效性。为了评估推荐系统，我们使用在user-video观看上收集的历史日志数据。回顾之前的推荐系统训练，我们使用匿名的评估周期内的前46天数据。为了测试推荐，我们使用相似的后者数据中的一半的日志数据。
对于评估一个算法推荐好坏，一种看起来简单的方法是，对于由一个系统在时间T上做出的推荐，在[T, …, T+E]周期上有多少视频被一个用户实际观看过。然而，使用历史日志数据来测试一个推荐系统（不管是否是吸附算法，或基于任何其它技术）必须小心实施。其中的一些难点，如下所述：
- (1) 事后诸葛亮（Hindsight is not 20/20）: 如果一个用户做出的推荐，用户在评估期并没有观看，将它标记为不正确其实并不合理。如果推荐已经被展示，用户可能会观看它。实际上，没有被观看可以简单认为是它没有被用户发现。
- (2) 在评估期观看的视频数随用户的不同而不同：在评估一个推荐系统时，通常在特定设置中进行评测(evaluation)，例如：100个推荐。如果用户观看多于／少于推荐的视频的情况没有被正确处理，所有的评估可能都是悲观的。
- (3) 推荐在单个时间点上做出：在该评估中，每个推荐系统在评估周期的开始之处做出它们的推荐。在评估周期间的信息，比如：新趋势，在评估周期内被观看的视频，以及新的兴趣，不会被考虑进去。
- (4) 新视频：由于Youtube视频库的快速增长，许多视频在评估周期被上传，它们不会出现在训练集上
- (5) 新用户：会存在首次使用YouTube的新用户，在评估周期内观看了一个视频。这些用户不会有推荐。
这些case中最易于处理的是(4)新视频和(5)新用户。为了简化所有算法的评估，我们需要视频和用户在推荐的训练阶段和测试阶段youtube上存在，以便在评估时被统计。在部署时，该限制是不必要的；所有模型将会连续更新。注意，这种恒定的重训练（constant retraining）也可以处理问题(3)；新视频和新的流行的视频会被考虑到。尽管有这些不同，在单个时间内上的效果衡量提供了有价值的信息，最坏情况下会低估效果级别。
用户具有不同的观看视频数目，以多种方式被处理，如下例所示。用户U在评估周期上观看了两个视频；观看集W是{a, b}。假设推荐系统$R_1$被设计成推荐5个视频，它会推荐{a,c,b,e,f}。另一个系统$R_2$，会推荐{a,c,e,f,b}。我们尝试去评估推荐系统是否对用户U更好。
将推荐列表的size限制到至多$ |W|$直观上是吸引人的；如果用户观看了$ |W|$个视频，那么可能我们应使用$ |W|$个视频来测试我们的推荐。注意由于该size的限制，$R_1$和$R_2$具有相同的precision和recall（a正确，b不正确）。如果我们没有将推荐列表的size限制到$ |W|$个，两者在5个推荐上都会有相同的recall。然而，在立即推荐列表size上的效果也会有不同。因此，当为每个算法展示ROC曲线时，对比起R2,$R_1$对用户的展示更好，因为它会对U的第二个观看b比R2排序更高。由于这项对算法效果的理解，我们不会基于$|W|$来归一化推荐的size。
最终，我们需要处理问题（1）不会给出完美的答案—— 即使查看历史日日志，我们也不知道一个用户可能已经采取的动作会不会产生一个特别的推荐。不幸的是，没有方法来解决该问题；precision/recall的数值不能捕获任何系统的所有优点。尽管如此，他们提供了有意思的数据，可以相互做对比。他们衡量了哪个方法能更好捕获用户已知的动作————即使当该用户没有关于所有视频的完美信息。
总之，假设给定用户没有完全知道提供给他们的视频信息，事后检验（backtesting）提供了一种方法来对系统推荐的期望效果做排序。最重要的是，该排序（ranking）可以被实施，无需使用户服从多个评估测试以及相关潜在的不一致结果。
3.2 算法和变种测试
我们简单概述了youtube推荐的三种算法。而文献上到处都是推荐算法，例如，我们尝试去捕获许多推荐算法的基础理解力，并提出了一种典型的、易于分析的、功能上多样化的方法集合。
第一个最基础的算法称为GP：全局流行度（global popularity）。该算法首先在训练周期内通过流行度对所有视频做排序。当我们需要为一个用户u做出推荐时，我们以该流行度测量的顺序做处理，输出top个用户在训练周期内未观看过的视频。一个视频的整体流行度对于选择展示给用户视频来说是一个相当重要的信息。作为参考，它可以确保任何提出的算法很优雅地处理实际问题，对于大多数用户，许多它们观看过的视频可能简单地与全局流行的视频相对应。
第二个算法称为LP（局部流行度），会考虑这种情况：全局流行度对于许多用户的个性化程度不够。该算法背后的思想是另一个非常常见的item-based推荐，它基于co-views。对于每个视频v，会计算与视频z一起共同观看的列表C(v)，也就是说，用户观看了v也观看了z（在训练周期内）。再者，对于每个视频v，视频z与视频v被共同观看，会分配一个分数 c(v,z)，它给出了共同观看v和z的用户数。当对用户u进行推荐时，会查看用户u在训练周期上观看的所有视频集合W(u)，$ C(W(u)) \doteq {z \in C(v) | v \in W(u) } $ 为用户u共同观看的视频集合。对于每个 $ z \in C(W(u)) $，分配一个分数 $ c(u,z) \doteq \sum_{v \in W(u)} c(v,z) $; 通过总分对该集合做排序，输入排序后列表中top个未观看过的视频。这很容易实现，可以捕获在许多流行的推荐系统中存在的社会现象共性。(Amazon.com：用户买了X，也会买Y)
LP在一定程度上对用户是个性化的，它仍然有缺点：它趋向于喜欢一些流行的视频。例如，对于一个已经观看了某足球运动员视频的用户，会给他提供流行的足球视频，而非推荐用户更关心的关于该足球运员员的少量被观看的视频。
第三种算法会修正该问题：它不再将在视频v和z之间的co-view分数c(v,z)定义成用户共同观看v和z的数目，而是将c(v,z)定义成：
\[c(v,z) = \frac{|U(v) \cap U(z)|}{|U(v) \cup U(z) |}\]其中U(v)表示在训练周期内观看了v的用户集合。之前，我们将用户u和视频z的c(u,z)定义成 $ \sum_{v \in W(u)} c(v,z)$。我们称该算法为LR（局部稀有：local rare）。很容易看到该算法不会偏向于流行的视频，可以期望生成高度个性化的推荐。该得分公式是标准的Jaccard系数，一种衡量两个集合相似度的公式。
我们用相应的方法比较了adsorption算法的两个变种（带dummy node和不带dummy node）。我们使用“平均版本”的Map-reduce形式的adsorption算法变种，推荐集合可以很大地收敛。
Adsorption-N：在每个用户节点上，注入概率（injection probability）和空概率（ dummy probability）为0; 持续的随机游走概率（probability of continuing the random walk）为1。在每个视频节点上，注入概率是1/4, 空概率为0, 持续的随机游走概率为1/2.
Adsorption-D：在每个用户节点上，注入概率为0, 空概率为1/4, 持续的随机游走概率为3/4。在每个视频节点上，注入概率为1/4, 空概率为1/4, 持续的随机游走概率为1/2.
最终，我们指出，adsorption是如何在视频推荐上被使用的。使用该算法的一种方法是，在user-video的视图上运行该算法，使用label分布来为每个用户生成推荐；label将会是与该用户最相关的视频。另一个等价的方法是，对于每个用户，我们收集了他观看过的视频的分布，并对他们求平均。尽管这会产生相同的答案，它具有一个很重要的好处：我们可以使用该过程来对新用户做推荐（它们不在训练集内），即使他们只观看了一个视频。
由于空间的限制，我们没在对video-video co-view graph的使用做详细说明。然而，也使用该图做了一些完整实验；结果与下一节描述的user-view的view graph很接近。
4.期望结果
我们运行了每个算法来为每个视频节点生成一个相关视频列表，对于每个用户，会生成100个推荐，以确保算法不会推荐那些对于该用户已经在训练周期内观看过的视频。
4.1 Reference算法
我们通过ROC曲线（precision, recall） pairs来得到推荐视频的效果，对比三个reference算法。如图3所示。首先注意到，具有高precision和低recall值的点，对应于在算法输出的推荐结果上选择少量top（未观看过）的视频。而具有高recall值和低precision值的点（图的左手边）对应于从算法输出中选择一个大的推荐数。
图3: reference算法的ROC
第一个观察到的现象是，存在着YouTube用户社区观看的群体性视频（collective）和个体视频（individual）。考虑到YouTube相对比较年轻，如果大多数YouTube观看者都是随便的”一次性（one-off）/偶然（occasional）”的观看者，这并不令人吃惊。对于那些大多数简单模型（只预测最流行的）不会有提升。另外，我们的评估机制相当严格（跨两个46天的周期），做出成功的推荐在一定程度上是令人吃惊的。
precision值相当小。然而，该值具有一定欺诈性，有两个原因：第一，我们的评估是基于事后检验机制，它非常保守（真实用户当观看过一个推荐视频时可能会喜欢该推荐，但不能量化评估）；第二，在top-100上的precision为1%是相当动人的，这意味着在测试集上具有少量观看的用户，我们可以在100个推荐中成功产生至少一个想看的视频。考虑到观看频率的分布是一个典型的长尾分布（power-law），均值大约为5,大多数用户小于该均值，相当令人吃惊。
在top 1推荐中，GP算法达到了8.4%的precision以及3.2%的recall；在top 100的推荐上，10.6%的recall和precision为0.6%。 这种简单的heuristic的成功相当令人吃惊，为我们的算法设置了一个较强的baseline。
下一个有意思的现象是，我们观看到GP算法和LR算法ROC曲线交叉点，它可以达到较高的recall和较低的precision。这意味着当允许做出大量推荐时，LR可以为每个用户更好地裁减结果。如果我们喜欢做出一个少量的推荐，更好的推荐是GP；如果我们允许做出一个量大的推荐（一直），利用co-view统计更好。
最后，LP（它会有效结合两者）近乎一致地控制着这两个reference算法，提升很大。
4.2 Adsorption算法
我们来看下adsorption算法的效果。对于简单性，我们只限制在与LP的对比上，因为它是最好的reference算法。图4展示了两个adsorption变种算法、以及LP的ROC曲线：
图4: Adsorption算法的ROC
首先，我们注意到Adsorption-D和Adsorption-N几乎相同，前者具有微略更高的precision（更少的推荐），后者具有微略更高的recall（更多的推荐）。这与我们的直觉相一致：将一个随机游走做限制，让它与源节点更接近，以便更小概率发生主题漂移，从而获得更高的precision。相反的，一个限制更少的随机游走能到达更远的节点，会获得更高的recall。该通用规则的一个异常是在位置1上，其中Adsorption-N会比Adsorption-D具有更好的recall。然而，如图5所示，该图比一开始看起来更复杂。
图4的第二个结论是，在所有操作范围内，adsorption比最好的baseline效果更好。对比起LP，对于precision最大值的位置，我们观察到有17%的recall提升；对于recall最大值的位置，我们观察到有21%的precision提升。这些幅度上的增益对应于YouTube上成千上万的点击，非常有价值。
4.3 top-1效果
略.