一个CM通信

实践

它可能工作

由泰勒Mcmullen
ACM通信，2015年11月，第58卷第11期，第50-54页
10.1145 / 2814332
评论

概率算法的存在是为了解决不可能或不现实的问题(太昂贵或太耗时，等等)而精确解决。在理想的情况下，你永远不需要使用概率算法。对于不熟悉它们的程序员来说，这个想法可能会非常伤脑筋:“我怎么知道它真的能工作?如果这是莫名其妙的错误呢?我如何调试它?也许我们应该把这个问题抛在一边，或者买更多的服务器……”

然而，对于那些深刻理解概率论或至少在大规模生产环境中使用和观察过概率算法行为的人来说，这些算法不仅可以接受，而且还值得寻找使用它们的机会。这是因为它们可以帮助解决问题，创建成本更低、更可预测的系统，并可以做其他方法无法做到的事情。

世界是概率的，至少它太复杂了，我们无法100%准确地建模。网络，尤其是互联网，也是概率性的。一个特定的数据包是否会到达它需要去的地方，这不是我们能完全知道的事情。要知道它从世界的一端到达另一端会经过多少个网络，它会走哪条路，就更不确定了。跨异步/有损网络运行的系统必然是概率的。不管你喜不喜欢，概率就在我们身边。

不确定性是不熟悉概率算法的开发人员遇到的核心问题，导致他们相信算法可能工作得很差或无法调试。然而，这种想法是不正确的。概率算法包含了随机性的元素(它们也被称为随机算法)，这是可量化的。它可以被分析，从而对算法的行为做出强有力的预测。事实上，算法的行为几乎没有不确定性。

本文讨论了两种类型的概率算法:一种是通过a显式引入随机性的算法rand ()调用，以及那些将输入数据转换为均匀分布以实现类似效果的函数。我将讨论属于这些类的具体算法，包括LogLog(及其更知名的后继者HyperLogLog)和双峰多播，以及它们试图解决的问题。

在第三种概率算法中，随机性是数据的固有属性。这适用于GPS跟踪、自动驾驶汽车、传感器网络和导弹制导系统等问题。例如，传感器网络常常试图对整个网络做出一个陈述，尽管只有部分数据。就自动驾驶汽车和导弹制导系统而言，数据是不断变化的。当程序处理完数据时，当前状态已经发生了变化。所以这已经是错误的，必须考虑到这一点。本文不讨论这类算法，但是要获得关于这类问题集和解决它们的算法的更多信息，阅读卡尔曼滤波器是有帮助的¹¹以及一般的估计算法。

回到顶部

Count-Distinct

计数不同的问题涉及计算流中可能包含重复项的唯一项的数量。更正式地说:查找多集的基数。许多问题都属于这一类。例如:在过去的一个小时内有多少个ip连接到服务器?在一个巨大的文本语料库中有多少不同的单词?一天有多少不同的用户访问了一个流行的网站?甚至，通过HTTP代理请求了多少个惟一的url ?

这个问题的天真解决办法很容易。您可以很容易地在头脑中编写代码，然后才看到前面的句子的结尾。下面是一些演示解决方案的Python代码:

与许多问题一样，计数清晰的困难伴随着规模。计算1000甚至100万的独立用户、ip、url或单词可能很容易，也很便宜，但如果是1亿呢?还不算太糟。如果在数千台服务器上每台服务器有1亿元呢?现在开始变得有趣了。

现在的问题是:在1,000台服务器上执行独立计数(每台服务器可能有多达1亿个唯一项)，并找到它们的结果的并集的基数。换句话说:分布式计数-区分。让我们考虑一个朴素解。

每个服务器都可以保留一组“可见”项，就像前面的代码示例一样。当每个集合完成其独立的与计数不同的运行时，它将“已看到的”集合的全部内容发送到中央服务器，然后中央服务器可以接受所有集合的并集并返回组合集的基数。

同样，幼稚的解决方案简单明了，但代价高昂。如果每个服务器都能看到1亿个独特的条目，那么“可见”列表的大小将非常大。就url而言，平均长度约为76个字符。这将使每个服务器大约有7.6GB的数据。即使每个url都可以被散列为64位整数，其大小也将是800MB。这更容易管理，但如果有数千个服务器呢?这些服务器中的每一个都将其“已看到”列表发送到中央服务器。在只有1000台服务器的情况下，要转储到combined_cardinality函数。

如果您需要经常进行这种分布式计数区分，那么您要么需要安装其中一个“大数据”系统(并雇佣一个团队来运行它)，要么寻找不同的解决方案。

输入HyperLogLog。该算法采用概率的方法来解决计数不同的问题。它的核心是基于两个观察结果:第一，在随机数的二进制表示中设置任何特定位的概率是50%;第二，两个独立事件的概率，一个而且B，两者都是* P P (A) (B)．因此，如果该随机数中任意一个特定位被设置的概率为50%，那么任意两个特定位被设置的概率为25%，任意三个具体位设置为12.5%。你懂的。

概率论101的另一点需要记住的是在事件发生之前的预期试验次数是1 / P(事件)．因此,如果P(一个特定的位集)是50%，那么它的预期试验次数是2。对于两个特定的比特，期望是4;三、八;等等。

输入值通常不是均匀分布的随机数，因此需要一种方法将输入值转换为类似于均匀分布的值——换句话说，就是哈希函数。注意:在哈希函数的某些应用中，分布对系统的正确性并不重要。但是HyperLogLog对此非常敏感。如果哈希函数输出的某些比特明显比其他比特更有可能被设置或不设置，那么它就完全抛弃了作为算法基础的数学。(我在MurmurHash3上取得了很好的成功。¹³要了解您喜欢的哈希函数是如何堆叠的，请查看smhash，¹⁵这在寻找哈希函数缺陷方面做得很好。)

---

一个特定的数据包是否会到达它需要去的地方，这不是我们能完全知道的事情。要知道它从世界的一端到达另一端会经过多少个网络，它会走哪条路，就更不确定了。

---

那么，第一步是获取输入项并将其哈希到一组位。然后计算所设置的前导位数，并记录最大到目前为止已设置的前导位数。这将提供所处理的唯一项目数量的粗略估计。看到一个前导位集的概率是50%，所以您可以“期望”唯一项的数量是两个。如果设置了三个前导位，那么，平均而言，您将看到8个独特的项。

改进估计的方法和HyperLogLogis背后的独特想法，将传入的项目根据它们的尾随位划分为一系列“桶”。记住每个桶的集合位的最大前导数:通过像这样将传入的项划分到桶中，您可以开发出对总基数的更准确的估计。如果你有米桶和n唯一的物品，那么平均每个桶将看到n / m独特的物品。因此，取这些桶的平均值提供了一个合理的估计log2 (n / m),您可以很容易地从中生成一个估计。

此外，HyperLogLog还有一个很好的特性，它允许您使用相同数量的桶的独立HyperLogLog实例，以及每个对应桶的最大值，并最终得到一个HyperLogLog联盟之前的两个hyperloglog。

这是HyperLogLog算法工作原理的一个粗略草图。HyperLogLog引入的主要变化是使用谐波平均值而不是算术平均值。(欲了解更多信息，请阅读原文LogLog⁶和HyperLogLog⁸论文)。

考虑分布式计数离散问题的简单实现。假设您有1000个服务器，每个服务器有1亿个独特的条目。在算法的每次运行过程中，中央服务器将需要处理800GB的数据。这也意味着需要800GB的数据穿越网络。HyperLogLog如何改变这种情况?

根据原始论文作者所做的分析，在为桶使用大约1.5KB的空间时，您可以预期精确度约为2%。每个服务器保存自己的1.5KB HyperLogLog，然后将其发送到中央服务器。对于1,000台服务器，中心服务器在每次运行分布式计数时处理大约1.5MB的数据。换句话说，您只处理了原始解中处理的数据的0.0002%。

这完全改变了这个问题的经济学意义。突然之间，你可以运行很多这样的程序，并且运行得更频繁。你不需要一个大数据系统;你甚至不需要更多的服务器——所有的成本在你的估计中有2%的偏差。

回到顶部

近邻搜索

最近邻搜索问题涉及到在一个集合中寻找相似的项目，例如，书籍、音乐、产品、照片和视频。这实际上是一个双重问题:什么会类似的意思是，你如何找到彼此相似的物品?

这个问题的前半部分被称为特征提取。它定义了被比较的项目是什么。例如，如果你要一个字符一个字符地比较两本书，那么这个字符及其位置就是你的特征。实际上，这并不是非常有用。相反，您可以选择提取每个惟一单词的相对计数，并将其用作本书的特征集。想象下面这句话是一本书:

一个人仍然是他将要停止成为的样子，也已经成为了他将要成为的样子。一个为死而生，一个为生而死。
让·保罗·萨特

从这本“书”中提取每一个单词的计数将会产生一个“单词袋”，以这样的方式可视化:

{已经:1，和:1，是:1，成为:1，停止:1，死亡:1，死亡:1，去:2，是:3，生活:1，生活:1，一:7，仍然:1，到:3，什么:2}

这只是做特征提取的一种方法。你可以选择提取成对的单词:

{already_what: 1, and_already: 1, be_and: 1, become_one: 1, quese_to: 1, death_one: 1，…｝

然而，在所有情况下，特征提取的输出都可以表示为向量。一本有10,000个独特单词的书可以表示为10,000维空间中的一个向量。

这可能看起来很奇怪，但以这种方式表示特征允许一些巧妙的操作。举个例子，如果你把每本书看作是n在-维空间中，你可以通过计算欧氏距离来衡量相似度⁷他们之间。你也可以测量向量之间的夹角。余弦相似度^3.这种方法很有效。

测量相似度的方法有很多，但它们都受到一个潜在问题的困扰:维度的诅咒。⁴简而言之，维度的诅咒是在试图处理非常高维空间中的数据时发生的一组现象，因为空间的体积随每个维度呈指数增长。问题是计算欧氏距离或两个向量的余弦相似度所需的工作量随着维数的增加而增加。对多维向量进行计算非常耗时。

进入另一个概率算法:LSH(位置敏感哈希)。LSH背后的思想基本上与传统的哈希相反。在传统的散列中，两个相似但不相同的输入值需要有非常不同的输出。在LSH中，两个相似的输入应该有相似的输出，但数据量要小得多。在实践中，我使用LSH将百万维向量转换为512位散列，它工作得很好。

显然，如果高维向量被缩小到一个小的“签名”，那么数据就会丢失。这就是概率部分的作用。

生成LSH有许多不同的方法。下面的例子是一种比较简单的方法。

假设我们有一个书籍文本的语料库。我们已经提取了包含10万个条目的词汇表。因此，每本书的特征向量将有100,000个维度。假设我们已经决定创建一个256位的LSH函数。现在我们生成256个完全随机的100000维向量。这些随机向量是LSH函数的基础。

LSH函数计算输入向量和每个提前生成的随机向量的点积。对于每个随机向量，如果点积是正的，我们记录1位。如果是负数，我们记录一个0位。我们最终得到一个256位的输出散列。

最好的方法是用随机向量有效地“分割”向量空间。通过回答输入向量是否大于或小于它们中的每一个，我们可以近似它在该空间中的“角度”。因此，这个LSH函数实际上所做的是生成一个散列，可以用来近似任意两个散列之间的余弦相似度。两本书的余弦相似度与它们哈希之间的汉明距离成正比。

回到顶部

可靠的广播

跨高延迟损耗网络(如Internet)在大量对等点之间可靠地广播消息是一个困难的问题。事实上，这正是我们在“快速”必须解决的问题，以便创建我们的“即时净化”系统。通常情况下，当遇到这个问题时，工程师会尝试用一个集中的、单一的真相来源来解决它。然后，该系统要么向所有服务器推送更新，要么由所有服务器提取更新。然而，依赖于真理的单一来源，也会使它成为失败的单一来源。如果集中式系统消失了，或者所有服务器或服务器的一个子集无法访问，那么系统的可靠性就完了。

有没有其他的解决方案?乍一看，这个问题似乎是可以解决的原子广播。⁵然而，原子广播的原则之一是总秩序的性质。换句话说，如果您有两个消息，A和B，每个服务器总是以相同的顺序看到它们。虽然该属性对某些应用程序很有用，但它引入了head-of-line阻塞问题。¹⁰如果消息A出现在消息B之前，但是消息A被延迟到达服务器，那么每个服务器都必须等待接收B，直到该服务器接收到A。在我们的特定应用程序中，顺序是不相关的，并且由行首阻塞造成的潜在额外延迟是不可接受的。

我们一直在寻找替代方案，最终决定采用一种名为“双峰多播”的算法，这是一种多相协议，可以在服务器网络上可靠地、有概率地分发消息。第一个阶段包括不可靠地从一个对等点向所有其他对等点广播消息。这种广播的机制不是特别重要——例如，如果有IP多播，你可以使用它。重要的是要尽可能快地将消息发送到所有服务器，即使在此过程中它们有可能丢失。

这个算法的第二阶段是流言协议⁹用于anti-entropy。每隔一段时间，每个服务器在网络中随机地独立选择另一个服务器。它向所选服务器发送当前状态的摘要，本质上是该服务器到此为止所看到的所有内容的摘要版本。该摘要的具体格式不是协议规定的部分，但其思想是以这样一种方式发送摘要，即当服务器收到摘要时，它可以确定错过了哪些消息。然后，它将返回尚未收到的消息列表，而发起八卦的服务器将重新发送这些消息。

该系统具有概率性，因为服务器随机选择与哪些其他服务器进行八卦。有可能他们选择的闲聊对象在某个回合中错过了与他们相同的消息。在这种情况下，他们不会立即恢复丢失的消息。尽管丢失的信息在系统中传播的方式是随机的，但它很容易被理解，并遵循一个经典的“流行病”模式。一条丢失的信息通过网络传播的速度和概率可以通过改变八卦的频率和服务器记住旧信息的时间长度来调整。

这个系统的版本是我们净化系统的核心，它被调到了这样一个程度:永久丢失信息的可能性是微乎其微的——大约是10³¹²%。按照目前的清理速度，我们预计每3×10会由于算法中的随机性而丢失一条消息³⁰⁰年。换句话说，只要你知道这个概率是多少，“高概率”就完全足够了。

许多很难精确解决的问题用概率算法变得相当可行。一致性哈希²经常应用于负载均衡和分布式数据库中。Mincut算法¹²可应用于网络路由问题。布鲁姆过滤器¹存在于许多数据库和网络应用中。快速排序¹⁴实际上是现今使用的标准排序算法。即使是基本的普通哈希表实际上也是概率的。程序员的日常工作充满了概率算法和数据结构。它们往往不被注意到，因为它们很有效。

事实上，概率算法就在我们身边。它们可以帮助解决困难问题，而不需要依靠一架架的机器。它们可以帮助解决实际上无法解决的问题。对于那些设计和构建大型系统的人来说，概率算法应该是最重要的。

相关文章
在queue.acm.org

变形:翻译系统生物学的未来转变
萨曼莎·克莱因伯格和巴德·米什拉
http://queue.acm.org/detail.cfm?id=1629775

电脑游戏中的人工智能
亚历山大Nareyek
http://queue.acm.org/detail.cfm?id=971593

Hazy:让构建和维护大数据分析变得更容易
阿伦·库马尔，牛峰，克里斯托弗Ré，
http://queue.acm.org/detail.cfm?id=2431055

回到顶部

进一步的阅读

这些文章更全面地解释了生成位置敏感散列的技术:

安多尼和因迪克。
2008.逼近最优哈希算法在高维逼近最近邻。Commun。ACM 51， 1 (2008)， 117-122;http://people.csail.mit.edu/indyk/p117-andoni.pdf．

安多尼，A，因迪克，P.帕特拉斯库，M。
关于降维方法的最优性。计算机科学基础, 2006, 449 - 458;http://people.csail.mit.edu/mip/papers/eps2n/eps2n.pdf

安多尼，A.，因迪克，P.阮，H.L.， Razenshteyn，我。
超越位置敏感哈希，2013;http://arxiv.org/pdf/1306.1547.pdf．

Datar, M.， Indyk, P.， Immorlica, N.， mirorkni, V.S.
基于p稳定分布的位置敏感哈希算法，2004;http://www.cs.princeton.edu/courses/archive/spring05/cos598E/bib/p253-datar.pdf．

乔治亚州的Gionis，印第安纳州的Indyk, R州的Motwani。
基于哈希的高维相似度搜索。二十五次会议的会议记录^th超大数据库国际会议, 1999;518 - 529;http://www.cs.princeton.edu/courses/archive/spring13/cos598C/Gionis.pdf．

因迪克，P.莫特瓦尼，R。
近似最近的邻居:为了消除维度的诅咒。STOC98学报》, 604 - 613;http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.38.249&rep=rep1&type=pdf．

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2015 ACM, Inc.

---

没有发现记录