Dimension Independent Similarity Computation (DISCO) — — 一篇技术博文的典范

话说很久没有看到好的技术文章了，一方面国内的高产的同学们，喜欢高屋建瓴，这个以微博上的各种“分析师”为首，之前是云计算，现在是Big Data，基本上都是扯淡，除了吼两嗓子让大家发现自己真不懂之外，没有什么价值，另一方面就是写得过细，比如一个MapReduce的WordCount的教程，基本上就是白开水。如同swordsp同学所说的“技术博文的典范”的文章基本看不到，好在老外同学们还是有不少好文章的，比如今天翻译的这篇DISCO，是最近几个月看过的难得的好文，这也是我其实非常喜欢Twitter的Data和Machine Learning部分的原因，简单快捷，容易实践，对于小公司非常值得效仿，如果不是目前的工作实在有趣，我觉得我会想方设法加入Twitter的。

看了这篇和之前翻译过的基于Hadoop的系统背后的数学，我觉得可以总结一下我眼中好的技术博文的三个特点：

• 写别人没写过的内容
• 谈一个具体但又足够通用的问题域，Big Data这样的Title太大，WordCount又太小
• 别堆Code，看Code我们去GitHub而不是你的Blog，需要图/算法过程让大家简单易懂

两篇文章首先都是新的别人没写过的内容，其次选题够实践够具体，Hadoop那篇文章是讲Overhead Cost计算的，这篇文章是讲MR计算相似度算法优化复杂度的，既不是大而无当只能看看，但是又没有细节到一个过于简单的Case，没有任何代码，一篇文章几个公式和几个图把Overhead对系统影响的曲线画出来，一篇文章几个算法伪代码外加复杂度优化的实际数据出来，非常漂亮，看得人赏心悦目啊。唯一DISCO这篇有个缺陷是p和epsilon如何选取文章里没写要去看引用的paper。

我对自己未来技术文章的期望就是一年能有个两三篇这样水准的，如果写得出来，觉得一是写作(单指技术文章)过关了，还有就是也说明对于特定领域的确有insight和自己的东西了。

最后是这篇过于DISCO算法blog的中文翻译，越来越觉得自己翻译成中文是让我仔细看一个东西的最佳途径。

Dimension Independent Similarity Computation (DISCO)

MapReduce是一种用于处理大数据集的编程模型，典型地用于在普通电脑组成的集群上进行分布式计算。当你有大量的处理能力在手的时候，会很容易倾向于通过暴力求解的方法来解决问题。但是，我们常常可以将MapReduce和聪明的采样技术组合起来以提升它的效率。

让我们来考虑一个寻找所有的D组指标向量(0/1的条目), 每个向量的维度为N的数据对之间的相似度的问题。我们特别专注于所有D组向量对在R^N空间下的cosine相似度的问题。进一步地，我们假设所有的维度，都是L稀疏的，即每个维度最多在所有的点中，只有L个非0值。例如，典型的在Twitter的用户键计算两两相似度的数据可能是这样的：

D = 10M (1000万个向量/用户)
N = 1B (10亿个维度)
L = 1000（每个维度下只有至多1000个用户有值）

由于维度是稀疏的，所以将数据点按维度来存储是非常自然的想法。为了计算cosine相似度，我们可以很容易地将每个维度，通过下面的Mapper和Reducer的组合喂到MapReduce程序中去。

其中 #(w) 统计了点w中包含的维度数量，#(w1, w2)统计了w1和w2中均出现的维度的数量，也就是w1和w2之间的点积。上面的步骤计算了所有的点积，并最终通过cosine的归一化因子来计算。

有两个主要的复杂度衡量指标:”shuffle size”以及”reduce-key complexity”来简短地定义MapReduce(Ashish Goel and Kamesh Munagala 2012).

很容易可以知道，上述的mapper会输出O(NL²)数量级的数据，这在我们给出的示例参数下来处理是没有可行性的。mapper端输出的内容叫做“shuffle size”，因为这是需要通过网络shuffle到正确的reducer的数据。

进一步地，reduce到单个key的条目数的最大值是 #(w1, w2)，也就是最多是N。这就是说，上面这种模式的”reduce-key complexity”是N。

我们可以激进地将shuffle size和reduce-key complexity的复杂度通过一些聪明的采样方式来缩小:

注： p和epsilon是过采样参数

在这个case中，reducer的删除是期望值为cosine相似度的随机变量。我们需要两个证明来确认这种模式的有效性。首先，这个期望值是真正正确的，并且由高概率来保障的，其次，shuffle size大大缩小了。

我们在(Reza Bosagh-Zadeh and Ashish Goel 2012)中证明了这两个断言。特别的，除了正确性之外，我们证明了上述模式的shuffle size只有O(DL log(D)/epsilon)，也就是独立于维度N，就像这种算法的名称中所说的那样。

这意味着你只要有足够的mapper来读入你的数据，你可以使用DISCO采样的方式来使得shuffle size是容易处理的。进一步地，每个reduce的key最多只会得到O(log(D)/epsilon)个value，这使得reduce-key complexity也是易于处理的。

在Twitter中，我们通过DISCO采样模式来计算相似的用户。通过把每个tweets当作一个维度，其中出现的单词作为signal，我们同样可以使用这个模式来计算高度相似的单词对。我们进一步地通过经验来验证了这个假设，并且观察到shuffle size的大幅度减少，详细内容在这篇论文中。

最后，这个采样模式可以用于实现很多其他的相似度算法。对于Jaccard相似度，我们改进了著名的MinHash模式在Map-Reduce上的实现。

Posted by 
Reza Zadeh (@Reza_Zadeh) and Ashish Goel (@ashishgoel) — Personalization & Recommendation Systems Group and Revenue Group

Bosagh-Zadeh, Reza and Goel, Ashish (2012), Dimension Independent Similarity Computation, arXiv:1206.2082

Goel, Ashish and Munagala, Kamesh (2012), Complexity Measures for Map-Reduce, and Comparison to Parallel Computing, http://www.stanford.edu/~ashishg/papers/mapreducecomplexity.pdf