探索算法中的主观性

让我们通过研究一个互联网时代最具标志性的算法：PageRank 来探讨算法设计中的主观性。

PageRank 的不动点方程版本，带有随机矩阵 W(G)，非零元素 i,j 仅在 (i,j) 是 G 中的边时存在，随机种子向量 s，以及介于 0 到 1 之间的系数 alpha。

首先，简要介绍 PageRank 算法的公式。该算法以一个有向网络的世界模型开始；这是因为它是由 Sergey Brin 和 Larry Page 发明的，用于对万维网上的页面进行排名。网络的 PageRank 在施加混合过程模型后才有良好的定义。标准的 PageRank 算法使用简单的启发式，每个链接被遍历的概率相同，混合过程可以很容易用随机漫步来解释。被称为 PageRank 的向量是随机漫步的平稳分布，假设这些随机漫步从特定的种子向量开始，而任何特定的随机漫步以概率 alpha 结束并开始新的随机漫步，这个概率也被称为传送率。如果使用额外的链接元数据来赋予链接不同的权重，最终的排名可能会显著不同。

算法分解：图 G 编码了一组节点和边的关系及潜在的元数据，启发式 h 将该数据映射为混合过程 W(G) 的权重，而度量则是唯一定义图 G 中节点排名的向量的映射。

改变种子向量也会显著改变算法的结果；标准的 PageRank 算法使用对所有节点的均匀分布作为种子向量。当使用单个节点或节点的子集作为种子时，该算法被称为个性化 PageRank。结果可以解释为每个节点相对于种子的相对重要性，这种情况下通常被称为 个性化向量。我们引入了主观性的第一个概念。即使我们都同意一种用于将权重施加于混合过程的启发式，我们也可以通过承认网络中的位置意味着独特的视角，从而得出不同的排名，因此得出一份独特的排名。我将使用一个简单的参考实例来演示这一影响，一个循环图。这个有向循环图具有均匀的标准 PageRank，因为它是对称的。

均匀种子和 alpha=0.1 的有向循环的标准 PageRank

当将种子从均匀分布更改为节点 3 的个性化向量时，对称性被打破，循环的方向立即显现。

节点 3 的个性化 PageRank，alpha = 0.1

所以对于这个情况来说还比较基础，选择个性化向量提供了上下文相关的排名，但这还没有触及基于混合过程的排名算法家族的表面，算法设计师所做的越多主观选择（有意或无意）就会影响度量的结果。

为了检视这些问题，让我们将对底层网络的解释从超链接和网页扩展到更为一般的 归因网络。在本文中，归因网络是指任何有向图，其中一个链接将信用（或信誉）从源分配到目的地。这种网络的例子包括学术引用、软件依赖关系和类似 Twitter 的社交网络（关注分配信誉）。在引入这种形式时，我们进一步给我们的算法参数化，允许我们的混合过程在有向边上流动，上下流用不同的权重。

使用学术引用作为参考例子，这种假设承认引用知名参考文献确实为我的论文带来了信誉，尽管它带来的信誉程度不同。我们不需要边向下游流动比向上游流动更具重量，但这是一种良好的惯例。

为什么我们需要一个惯例？

因为这是一种 主观选择，这种选择的动机在于：当作品 A 引用作品 B 时，A 增加了对 B 的信誉，而 B 被引用对 A 本身的信誉并不多。现在，让我们看看，当赋予上下游信用时，个性化 PageRank 在我们的循环图中会发生什么，但是向上流的权重是向下流权重的二分之一。

节点 3 的个性化 PageRank，向上权重为向下权重的 1/2，alpha=0.1

节点 1 和 2 由于拥有来自节点 3 的最近向上链接获得了更多的权重，但有些违背直觉的是，像 17 和 18 这样离得更远的节点的排名失去了很多优势。这是因为排名算法是随机向量，即它的总和保持不变。在给予上游节点信用时，与种子节点紧邻的节点通过短循环获得了重要性，而进一步下游的节点则相应损失。这里一个重要的消息是，即使是对一个简单算法的存心良好的修改也能产生意想不到且不良的后果。

考虑到这一点，我想提出一些没有“正确答案”的简单参考案例。为了讨论的目的，假设链接代表学术引用，在绘图时，我将保留信用以半权重向上流动的假设。

信用应该如何分配在一系列依赖的论文中？

（如通过 20 个节点的折线图表示）

如果我们简单地采取没有个性化的标准 PageRank 算法，就会出现很奇怪的事情。该算法考虑到倒数第二个（节点 18），而不考虑最后一个（节点 19），这被解释为第一篇论文是最重要的。

标准 PageRank，均匀种子和向上权重为向下权重的 1/2，alpha=0.1

为什么会出现这种情况？数学上说，节点 19 因为它位于边界上，未获得任何上游信用而处于劣势。大多数人会直观地更愿意把节点 19 视为重要节点，但其他人可能会辩称，在没有节点 18 的证实时，我们无法充分理解节点 19 的工作。在实践中，早期的一篇论文往往鲜为人知，直到其他人开始在其基础上进行研究。那么谁能说节点 19 应该比节点 18 更重要呢？

假设我们希望纠正对根节点的这种看法。我可以通过简单的算法修改做到这一点：引入自循环，权重等于下游引用。

标准 PageRank，均匀种子，自循环权重等于下游权重，向上权重为下游权重的 1/2，alpha=0.1

自循环让算法变得更好吗？这取决于你问谁。这些算法在本质上是“客观”的，因为它们反映了在相同图上混合过程的数学性质。如果仔细观察，自循环的引入也提高了节点 0 的得分。在没有自循环的混合模型中，边缘节点处于劣势，而自循环则对其有所偏袒。

线图参考例子中的另一个显著特点是 PageRank 的衰减速度。均匀的种子向量将某种基础水平的信用注入到每个节点中，而混合过程则允许这种信用在整个网络中扩散；系数 alpha 可以看作是这种信用注入的速率：较大的 alpha 将使解决方案更接近均匀 PageRank，而较小的 alpha 将允许信用扩散得更远，导致更多积累在某些节点，因而在最大和最小值之间形成更大的差距。这是我设置 alpha = 0.001 时的情况。

均匀种子，自循环权重等于下游权重，向上权重是下游权重的 1/2，alpha=0.001 的标准 PageRank

如果节点 0 被视为一个重要发现，而社区更感兴趣的是先前工作如何应得了信用以便实现这一发现时，这种情况下需要个性化 PageRank，但并未指明是否要保留自循环、向上链接或如何设定 alpha。我将展示带有自循环和对向上链接为半权重的结果，但承认这个选择是随意的。

个性化 PageRank，节点 0 作为种子，自循环权重等于下游权重，向上权重为下游的 1/2，alpha=0.01

鉴于我们正在使用个性化 PageRank，得分对 alpha 的选择非常敏感，因此我计算了一系列 alpha 值的结果。

有向线图上的个性化 PageRank，边按降序排列，自循环权重为 1，向上权重为 1/2，种子为节点 0

突出的情况是，减少 alpha 将信用从最直接的依赖转移到早期的依赖。如果一个人相信基础性的工作是最重要的，那么就需要一个较小的 alpha。另一方面，如果有人认为导致发现的最新工作获得更多信用，则需要一个较大的 alpha。就我个人而言，我喜欢 alpha = 0.03 的结果，因为它为基础性的结果积累价值，同时仍然为更接近发现的工作赋予权重。

然而这并不是我直接计划的事情。我们一旦改变网络，“感觉合适”的 alpha 或者为特定图优化的 alpha 不一定在另一个图中保持该特征。让我们再审查几个参考案例。

如何在星形图中分配信用？

如人所料，信用累积在共享依赖项上。

均匀种子，自循环权重等于下游权重，向上权重为下游权重的 1/2，alpha=0.1 的标准 PageRank

值得注意的是，改变 alpha 几乎对这个参考案例毫无影响。

均匀种子，自循环权重等于下游权重，向上权重为下游权重的 1/2，alpha 参数调整的标准 PageRank

当星型的方向发生翻转，并且以一篇论文引用大量未连接的引用时，情况就变得更加有趣。现在重点放在上游权重的相对强度上。当在下面的例子中，上游权重较小时，边缘节点的信用超过中心节点。

均匀种子，自循环权重等于下游权重，向上权重为下游权重的 0.001，alpha=0.1 的标准 PageRank

然而，随着上游权重的增加，情况发生了逆转，中心节点获得了大部分信用，因为它得到了所有引用的信誉，而没有其他链接来累积信用。

均匀种子，自循环权重等于下游权重，向上权重为下游权重的 0.1，alpha=0.1 的标准 PageRank

这种重要性的翻转可以通过对上游权重的相对值进行一系列实验来检验（相对于赋予下游边和自循环的权重为 1）。

均匀种子，自循环权重等于下游权重，alpha=.1，含上游权重的参数调整的标准 PageRank

此改变发生得比预期的要快得多；引用所有其他节点的中心节点的影响超过了外围节点，即使上游权重不足 1%。这提醒我们，上游权重的一个重要事实是；如果它们的数量级与下游权重相近，一位希望提升自己的排名的贡献者可能会夸大引用，而不当提升自己。 然而也应注意，此参考案例超敏感于上游权重。我们应该审查一个依赖关系分布更广的参考案例。

如何在树形图中分配信用？

在这个参考案例中，网络是深度为 4 的有向二叉树。有向树图具有我们线图和星形图的特性。与线图相同，没有自循环的情况下，根节点实际获得的信用比其直接前驱节点少。

均匀种子，向上权重为下游权重的 1/2，自循环权重为 0，alpha=0.1 的标准 PageRank

与线图相同，包括权重等于下游链条的自循环可以纠正这种情况。

均匀种子，向上权重为下游权重的 1/2，自循环权重等于下游权重，alpha=0.1 的标准 PageRank

正如星形图的情况一样，调换引用的方向以形成扇出，而不是聚合，突显了上游权重的效果。

均匀种子，向上权重为下游权重的 1/2，自循环权重等于下游权重，alpha=0.1 的标准 PageRank

与星形图的情况不同，没有任何入链的节点并未累积很多信用。但仍存在一个有趣的现象：倒数第二层每个节点累积的信用最多。进一步探索每个层中的信用累积情况，可以清楚地看到深度 4 的最后一层仍然积累了最多的信用，但分布在更多的节点上。

均匀种子，向上权重为下游权重的 1/2，自循环权重等于下游权重，alpha=0.1 的标准 PageRank

再一次，这不是我们想要的归因算法的表现并不明确。选择上游权重的强度会显著影响这些信用的分布。

均匀种子，自循环权重等于下游权重，alpha=.1，带有上游权重参数调整的标准 PageRank

类似于星形网络的情况，更大的上游权重会将信用传递给没有入链的节点，但与星形网络不同的是，这些权重必须相当大，PageRank才显著上升。

现在，让我们重复在线图上进行的实验；假设没有任何引用的节点被视为一个新的突破，并且我们希望分配信用给之前的工作。我们上面的个性化 PageRank 分析结果会向我们显示。

种子为节点 0，权重与下游权重相等的自循环，向上权重为下游权重 1/2 的 PageRank，alpha=0.01

结果表明，价值仍然在最后两层中累积，倒数第二层每个节点的影响最大，而最后一层则捕获了最大的总影响。

个性化 PageRank，均匀种子，以及向上权重为下游权重的 1/2，自循环权重等于下游权重，alpha=0.1

这些结果同样对参数的选择非常依赖。当上游权重逐渐降低时，下游权重的降低会将重要性转移到距离依赖图较远的节点。调整 alpha 参数时，较小的 alpha 会将信用向下迁移到依赖图中更远的位置。

个性化 PageRank，种子节点为 0 ，自循环权重与下游权重相等。左：alpha=0.01，带有上游权重的参数调整。右：向上权重为下游权重的 1/2，alpha 更改参数调整。

这两个参数对于中间层节点有显著不同的影响；减少上游权重会对倒数第二层的节点产生显著不利影响，而改变 alpha 对这些节点的信用几乎没有影响。

我将以我最喜欢的实验之一结束。这当一群攻击者向网络贡献虚假内容，并开始在彼此之间建立相互关联的引用时，会发生什么？

在这个例子中，我的项目由节点 7 到 13 的贡献构成，而我的攻击者则提交了节点 0 到 6 的贡献并且与整个项目有一个链接，以及他们自己贡献之间大量的内部链接。

均匀种子，向上权重为下游权重的 1/2，自循环权重等于下游权重，alpha=0.1 的标准 PageRank

起初看起来情况并不太好。由于缺乏来自合法工作小组到虚假工作小组的链接，合法工作的 PageRank 较高，但并不足以对抗这种攻击。

这就是种子向量可以作为信任锚定的一种方式。在一些活动可能被伪造以人为地提升某些贡献的信用的环境下，避免使用均匀种子以防奖励 Sybil 攻击者，而是利用人类的知识来确定由人工验证的内容构成的种子。

假设不使用均匀种子，而是重复实验，将节点 9 和 13 设置为可信的种子。那么结果则大相径庭。

个性化 PageRank，以 9 和 13 为种子，向上权重为下游权重的 1/2，自循环权重等于下游权重，alpha=0.1

有人可能会争辩说，这些可信种子的选择是随意的和主观的！我会说当然是这样，但提出这个论点的人往往未能认识到，算法在我们让人类专家决定可信种子之前，已经包含了多少主观性。

谁来决定在链接上信用如何以及程度地向上流动？谁来决定是否存在自循环及其强度？谁决定 alpha 参数应该是什么？所有这些都是主观选择，它们对信用分配有非平凡的影响，而且一旦付诸实践，这种措施也会对寻求信用或补偿其贡献的参与者产生同样非平凡的影响。

明确来说，这并不是关于 PageRank 算法的声明，而是关于算法的声明，特别是用于将复杂的人类努力简化为量化框，以便我们进行比较的算法。没有绝对的客观价值测度。每个度量都是在主观选择的基础上具有客观性的。我们每天都在做这些主观价值判断，这并没有错，但是当涉及到将主观价值判断编码到代码中时，并且隐含或显式地将其强加给他人时，作为算法设计师我们有责任对这些主观选择及其可能对他人产生的影响保持警惕。

• 原文链接： medium.com/sourcecred/ex...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～