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稀疏的,即每个维度最多在所有的点中,只有10个非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^2)数量级的数据,这在我们给出的示例参数下来处理是几乎不显示的。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

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>