注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

罗维的博客

{ 关注机器学习、计算广告、自然语言处理、大规模数据处理等 }

 
 
 
 
 

日志

 
 

使用MapReduce实现大规模稀疏矩阵相乘(上)  

2015-11-14 16:26:16|  分类: 算法设计 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1. 引言

       在DT时代,挖掘海量数据并从中提炼出有价值的信息是各大互联网公司的重要目标之一。在拥有海量数据后,各种各样的数据挖掘任务就出现了,大规模稀疏矩阵相乘就是其中一项常见的计算任务。在文本处理或者说自然语言处理中,稀疏矩阵是常见的数据表达形式,对大规模稀疏矩阵做乘法的业务需求也是很常见,比如:

  1. 现有大量的object(比如数千万甚至更大的规模),已通过某种特征抽取算法建立起每个object的稀疏特征向量,这里object可以是query、word、URL、host、APP、商品、用户等,现在有个任务是对每个object找出与其相似的object。在个性化推荐领域中经常碰到这类问题。
  2. 现有第1份数据是每个用户浏览的URL列表,每个URL带有权重分数,第2份数据是query到URL的搜索点击关系,每个URL也带有权重分数,用户规模、query规模、URL的规模均在数千万的规模,现在有个任务是给每个用户找出一批合适的query来描述。
  3. 现有第1份数据是每个用户浏览的商品ID列表,每个商品ID带有权重分数,第2份数据是query到商品ID的搜索点击关系,每个商品ID也带有权重分数,用户规模、query规模、商品ID的规模均在数千万的规模,现在有个任务是给每个用户找出一批合适的query来描述。(这里,query也可以变成是商品的核心词)
  4. 已有一份词典D,其对每个query列举了与其相似query和相似性分数,左侧query的规模在数千万的规模。但是其中有些query的相似query列表较短,如果需要扩展列表,一种办法是通过把相似的query拿到字典D中再查询一次,以丰富query的相似query列表内容。

       上述例子还只是大规模稀疏矩阵相乘任务的冰山一角,还有更多的业务场景需要用到它。既然需要大规模稀疏矩阵相乘的任务很多,那么有必要对该任务研发出一套scalable的通用分布式计算工具。笔者刚好在最近的一些工作中碰到了这类需求,就基于MapReduce开发了一套工具以支持团队需求。

       下文就针对单机不能处理,需要用到分布式计算平台(比如MapReduce)的大规模矩阵相乘问题,列举研发此工具的一些经验教训。先简单介绍适用于稠密矩阵的矩阵相乘算法,然后介绍适用于稀疏矩阵的矩阵相乘算法,继而介绍工程实现上的一些trick,最后简单做个总结。笔者了解的东西不多,欢迎各位读者批评指正。

2. 矩阵相乘的形式化定义

       将一个m*n的矩阵A和一个n*k的矩阵B相乘得到m*k的矩阵C,数学公式如下:

                                   C[x][y] = sigma( A[x][i] * B[i][y] ), i={0,1, …, n-1} (1)

       下面考虑的是A和B都是大矩阵的情形,即单机计算时间很长甚至是单机无法加载数据,这时只能依靠分布式计算平台(比如MapReduce)。从公式1可以看出,A和B的每个元素都被用于计算C中不止一个元素的值,整个计算复杂度是O(m*n*k),如果m、n、k均为百万量级,那么计算复杂度就在10^18的量级,这样的计算规模是相当大的。当今主流CPU的每秒处理速度在10^9量级,所以靠暴力求解法并不合适。研发一款实用的大矩阵相乘工具是很有必要的,要考虑计算精度、计算速度、shuffle数据量和数据倾斜等情况。

3. 适用于稠密矩阵的矩阵相乘算法

3.1 简单相乘法

图 1 简单相乘法的MapReduce流程图

       简单相乘法可谓是最朴素的MapReduce上矩阵相乘算法,用此方法作为算法比较的基础。简单相乘法依据公式(1)来实现矩阵乘法,图1是其算法流程图。图中,Map输出的第一个"|"表示分桶 key的位置,第二个"|"表示排序 key的位置。它只需要一轮MapReduce。

       Map阶段每读入一条数据<x, y, v>,需要输出若干条数据。若它来自于矩阵A,则需要输出k条数据,需输出<x, i, y, v>, i={0, 1, …, k-1},补充说明,x = {0, 1, …, m-1}, y = {0, 1, …, n-1};若它来自矩阵B,则需要输出m条数据,需输出<i, y, x, v>, i={0, 1, …, m-1},补充说明,x = {0, 1, …, n-1}, y = {0, 1, …, k-1}。前两个字段为分桶key,前三个字段为排序key。Reduce 阶段的输入是<x, y, z, v>,当且仅当前后两条输入数据的x, y, z均相同时,说明 A 中存在A[x][z],B中存在B[z][y],应该把它们俩的值相乘累加到C[x][y]。由于是按x, y分桶并按x, y, z排序,所有能贡献到C[x][y]的数据都分配到这个reducer并排列在一起,因此当目前读取的x, y与上一个不同时,若上一个x, y累加的sum不为0,则输出<x, y, sum>。

       矩阵A和矩阵B中的每个元素要发送多次,总的网络传输数据量,也就是shuffle数据量,是O(m*n*k)。对大规模矩阵,m, n, k都是较大的数(比如这3个数均在数百万的量级,则传输规模在10^18量级),这种情形下的网络传输量会特别大。当矩阵稀疏时,大部分 A发送的数据找不到与 B 发送的x, y, z相同且非零的数据,反之亦然,因此有很多网络传输是浪费的。可见这个算法对于稀疏矩阵乘法并不高效。

3.2 分块相乘法

图 2 分块相乘法的MapReduce流程图

       分块相乘法,也就是在线性代数或者矩阵论教材上所说的分块矩阵相乘法,该方法有点类似于递归思路,即把原问题的求解先分解为多个子问题的求解,然后在做某种恰当的归并操作。分块相乘法有多种具体实现,这里举一种代表性的实现方案,很多方法可以视为该方法的变种。图2是一种实现方案。图中,Map输出的第一个"|"表示分桶 key的位置,第二个"|"表示排序 key的位置。它也只需要一轮MapReduce。

       借用数学中的一个概念,向上取整的公式RoundedUp(x),表示不小于x的整数中最小的一个。下文为了表达简洁,用R1(x/y)表示RoundedUp(x/y),用R2(x/y)表示RoundedUp(x/y) - 1。

       将矩阵A和矩阵B都分成大小为d*d的块。这样矩阵A的行被分成了R1(m/d)块,列被分成了R1(n/d)块,子块的行下标取值范围为{0, 1, …, R2(m/d)},列下标取值范围为{0, 1, …, R2(n/d)}。矩阵B的行被分成了R1(n/d)块,列被分成了R1(k/d)块,子块行下标取值范围为{0, 1, …, R2(n/d)},列下标取值范围为{0, 1, …, R2(k/d)}。Map阶段每读入一条数据<x, y, v>,需要输出若干条数据。若它来自于矩阵A,则需要输出R1(k/d)条数据,需输出<x/d, i, y/d, ‘A’, x%d, y%d, v>, i = {0, 1, …, R2(k/d)},补充说明,x = {0, 1, …, m-1}, y = {0, 1, …, n-1};若它来自矩阵B,则需要输出R1(m/d)条数据,需输出<i, y/d, x/d, ‘B’, x%d, y%d, v>, i = {0, 1, …, R2(m/d)},补充说明,x = {0, 1, …, n-1}, y = {0, 1, …, k-1}。前两个字段为分桶key,前三个字段为排序key。Reduce 阶段的输入是<x, y, src, x_index, y_index, v>,其中src表示来源,取值’A’或者’B’,<’A’, x_index, y_index, v>的list构成来自矩阵A的子块,<’B’, x_index, y_index, v>的list构成来自矩阵B的子块。当且仅当前后两条输入数据的x, y, z均相同时,说明 A 中存在子块A[x][z],B中存在子块B[z][y],应该把它们两矩阵相乘的结果累加到子块C[x][y]。由于是按x, y分桶并按x, y, z排序,所有能贡献到C[x][y]的数据都分配到这个reducer并排列在一起,因此当目前读取的x, y与上一个不同时,则输出<x, y, sum_matrix_multiplication>。

       用分块相乘法进行矩阵相乘最大的优点是每条数据只会被发送R1(k/d)或者R1(m/d)次,大大降低了网络通信。在设置d的大小时有一个限制,在本地相乘的2个子块占用的空间O(d^2)不会超过机器的内存限制。

       此方法有诸多变种,可以总结为2类思路,一类是子块大小不设置成d*d这种方块矩阵,而是灵活的依据矩阵A和矩阵B的大小规模来配置;一类是优化算法,提高计算性能。对稀疏矩阵,有可能划分出两个为空的子块进行相乘,此时传输这两个块的开销仍是不必要的。虽然有方法对此进行优化,但由于矩阵稀疏,还会碰到两个不为空的子块相乘,结果为空的情形,此时传输这两个块的开销仍是浪费的。



本文为原创,转载请注明来源:罗维的博客,谢谢!^^
  评论这张
 
阅读(542)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017