No.40期
单词共现矩阵应用
Mr. 王:这个算法的优势在于,它的 key 空间相比前面的词对要小得多,这意味着它能够更好地利用 combiner。
但是这种做法实现起来相对会困难一些,而且这个算法里面潜在的对象是非常大的。我们为每一个词申请的数组,是造成潜在对象非常大的首要原因。
下面我们看看如何进一步应用所求出来的单词共现矩阵。在自然语言处理中,我们经常需要通过共现矩阵求出两个单词间的相对频率。其表达式是这样的:
小可:这个 count(A,B) 就是词 A 和词 B 的共现计数吧?
Mr. 王:没错。现在需要思考的是,如何利用 MapReduce 来解决这个问题。首先来看看条带法。
对于条带法,我们只要使用共现矩阵关于 A 的那个数组就可以了。扫描一遍,就知道 A出现了多少次,在扫描第二遍时,就可以根据 count(A,B) 一一求出对于任意一个 B, f ( | B A)的值。
小可:那么对于词对法,又是怎么做的呢?
Mr. 王:对于词对法,要考虑的问题就比较多了。我们要对词 A 额外设计一个词对为(a,*)。
(a,*)这个量保存的是 a 出现的总频数,也就是 count(A)。为了完成上面的工作,我们在设计 MapReduce 时,要额外考虑以下几个方面。
Mapper 需要额外传递一个 (a,*) 用于求 count(a),还要保证它必须先于其他所有的 (a,b) 先抵达 Reducer,这样计算才能有效地继续进行下去。
必须要保证所有的同一个词 a 都会传递给同一个 Reducer。
还要在涉及不同的 key-value 对的 Reducer 中保存相应的状态。
小可:各种方法在处理问题时还是各有利弊啊。
Mr. 王:在计算机科学中非常流行的一个词汇叫作 Trade-off。 Trade-off,简而言之,就是在有限的计算资源制约下,资源之间的互相置换和平衡。常见的例子有空间换时间和时间换空间等。
小可:都是怎么解释的呢?
Mr. 王:比如我们要解决一个问题,当希望利用较小的内存空间去解决时,就需要花费较多的时间;当希望节省时间时,可能就要占用较大的内存空间。我们要寻找一种时间和空间都能接受的方法,这个过程就是 Trade-off。
在 MapReduce 的设计中,也涉及很多 Trade-off 的问题。比如键值对的数量控制,创建对象的数量越多,开销就越大,同时也会对排序和洗牌的效率造成一些影响。
而如果减小键值对的数量,单个键值对的大小可能就会变得比较大,这意味着在传输过程中,同样会造成通信比较耗时的问题。
另外,对于本地聚合问题,也是很值得思考的。对于不同的问题, combiner的设计会产生很大的效率变化。当然,我们也可以尝试去设计 In-Mapper 和 combiner 共存的MapReduce 程序。
还有就是联系我们之前研究过的磁盘算法。
在算法执行过程中产生的大量中间结果,是存到内存中还是磁盘上,或者是在整个机架、机群的网络中传输,都会产生非常不同的效果,这是一个好的 MapReduce 使用者或者说程序员不得不深入考究的问题。
好了,今天听了这么多,你也很累了吧,我们的课就上到这里,下次再见。
小可:好的,王老师再见。