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

罗维的博客

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

 
 
 
 
 

日志

 
 

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

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

  下载LOFTER 我的照片书  |

4 适用于稀疏矩阵的矩阵相乘算法

4.1 矩阵相乘的向量表达形式

       公式1还可以用向量的形式来表达,如公式2所示,其与公式1是等价的。

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

       A的列向量有n个,B的行向量也有n个,将A的某个列向量与B的对应行向量相乘,得到m*k的中间结果矩阵,将这n个中间结果矩阵相加,即得到结果矩阵C。公式2表面上看似抽象,但放到具体的业务中,其实有很强的物理意义。举个例子(就用第1节中的第2个例子):现有第1份数据是每个用户浏览的URL列表,每个URL带有权重分数,第2份数据是query到URL的搜索点击关系,每个URL也带有权重分数,用户规模、query规模、URL的规模均在数千万的规模,现在有个任务是给每个用户找出一批合适的query来描述。对这个问题,矩阵A的m是全部的user,n是全部的URL;矩阵B的n是全部的URL,k是全部的搜索query。公式2的意思就是说:对某个URL而言,将其对应的user向量与query向量进行相乘,得到一个user到query的中间结果矩阵C',维度是m*k。遍历全部的URL,将得到的各个中间结果矩阵C'相加即可得到矩阵C。通过这样一个解释能看到,作为索引项的URL其实是从user到query这种联系的桥梁。

       对于稀疏矩阵,某个URL对应的user向量和query向量有很多是零值,这些零值元素对计算出最终的矩阵C没有任何数值上的贡献。如果不是直接用公式2计算,而是建立URL到user和URL到query的倒排索引,并且只索引非零值。这样就可以进一步化简问题,也就引发出基于倒排索引的稀疏矩阵乘法。

4.2 单侧倒排索引的矩阵相乘法

       如果矩阵A和矩阵B中存在一个矩阵较小(比如矩阵的行数是十万这种量级,各行平均包含的非零值个数是数百这种量级),其倒排索引的空间开销小于MapReduce集群对节点的内存限制(不少公司的Hadoop集群要求各计算任务的节点内存开销在2G以内)。不失一般性,假设是矩阵A的倒排索引能被单节点加载,算法需要1轮MapReduce,且只需map阶段。Map阶段将矩阵A建立倒排索引,矩阵B按行切分将数据分配到不同的Map节点上,各节点每读入一条<x, y, v>,执行类似搜索引擎检索的流程,从倒排链中拉取出与其相关的全部的A中元素,并相应的计算出向量点积。

       当存在部分倒排链特别长时,可以将这些倒链再split成几个子倒链(计算精确无损),也可以设置一些cutoff值,比如倒链最大长度、倒链元素分数的最低阈值等(计算精度有损)。

4.3 双侧倒排索引的矩阵相乘法

       当矩阵A和矩阵B都较大,无论哪边的索引都超过MapReduce集群对节点的内存限制,那么就需要对两矩阵都建立倒排。如上文所说,当输入矩阵的某个<x, y>的v为0,因为零值元素对矩阵相乘的最终结果不会有分数上的贡献,所以不用将该项加入到索引中。在充分利用稀疏矩阵的这一特性后,我们可以设计出高效的矩阵相乘法。图3和图4是算法的2轮MapReduce的流程图。

       第一轮 Map阶段将矩阵A按列划分,矩阵B按行划分,即每读入一条<x, y, v>, 若来自矩阵 A, 则输出<y, 'A', x, v>;若来自矩阵B,则输出<x, 'B', y, v>。以第一个字段为分桶 key,前两个字段为排序 key。这样A的第i列和B的第i行会被发送到同一个reducer并放在一起,而且A的数据在前,B的数据在后。这样Reduce阶段就先输出i索引到A的数据,后输出同一个i索引到B的数据。

       第二轮Map阶段对每个i,对索引到A的数据集合和索引到B的数据集合求笛卡尔积,并把y1_y2组合作为key,其分数乘积v1*v2作为value发送给reducer,Reduce阶段只需要将第一轮输出中相同key的值求和。

       为了更方便的理解流程,下面对具体的例子(还是用第1节中的第2个例子)给出算法流程图,请见图5和图6。第1轮建立起关于URL的倒排索引,第2轮Map阶段对倒排索引的各项计算笛卡尔积,然后Reduce阶段对相同key进行求和。

图 3双侧倒排索引的矩阵相乘法的第1个MapReduce任务示意图

图 4 双侧倒排索引的矩阵相乘法的第2个MapReduce任务示意图

图 5 双侧倒排索引的矩阵相乘法的第2个MapReduce任务示意图(具体示例)

图 6双侧倒排索引的矩阵相乘法的第2个MapReduce任务示意图(具体示例)

       考虑到MapReduce集群对节点的内存限制,使用这种方法要注意各单项元素的倒排链不能太长,如果每个索引项需要的存储空间为100字节,那么可以估算倒排链长度的极限是10^7,也就是1000万。为稳定运行该流程,建议控制在数百万的量级。另外,在实际业务中,如果某元素的倒排链长度能到100万甚至更多,那一般来说此元素其实价值不大。比如,某URL能被100多万用户访问,这一方面说明此URL是高频URL,但另一方面也说明此URL的信息量不大,用此URL去架起user到query的桥梁的意义不大,从业务层面上看,这样的URL是可以被舍弃的。

4.4 双侧倒排索引的矩阵相乘法的工程实现trick

       分析双侧倒排索引的矩阵相乘法的流程,容易发现瓶颈会存在于第2轮MapReduce中,具体是map节点把进行笛卡尔积运算后的结果发送给reduce节点。假设关于矩阵A和关于矩阵B的倒排链的平均长度分别为p和q,那么单个索引项带来的笛卡尔积的计算复杂度为O(p*q),因为一共有n个索引项,所以总的计算复杂度为O(n*p*q),因为矩阵是稀疏的,所以这里p<<m, q<<k。比如m、n、k均为百万量级,但p和q是在一万这种量级,那么计算复杂度就在10^14的量级,虽然比原先的10^18的量级小了很多,但这个计算复杂度还是大,CPU开销和网络IO开销均是在O(n*p*q)量级。由此可见,笛卡尔积的计算是这个算法性能的关键点。

       O(n*p*q)量级的计算代价是精确计算、没有精度损失情况下的计算代价。不过一些实际业务是允许有精度损失的。比如对第1节中的第2个例子,当只需要对每个用户找到最合适的top N的query,那么可以对倒排链做些恰当的剪枝操作。剪枝策略主要是设置一些cutoff值,比如倒链最大长度、倒链元素分数的最低阈值等。

       在工程实现上,还要考虑数据倾斜的问题。在很多互联网业务中,数据均服从幂律分布。比如存在部分URL会对应到特别多的用户或者query,但这部分URL的数量在全部URL中的占比不大。为了缓和数据倾斜,可以在第1轮MapReduce的Reduce阶段加入长倒链切分成若干个短倒链的逻辑,并多加入一轮针对倒链数据的shuffle的MapReduce操作。这种方案并不会带来精度损失,但会提高后面算笛卡尔积的MapReduce任务的计算效率。在笔者负责的一项业务中,加入这个策略,算笛卡尔积的MapReduce任务的计算时间缩短为原先的1/3。

5. 总结

       对于稠密矩阵的矩阵相乘,视矩阵大小,来判断使用简单相乘法还是分块相乘法。

       对于稀疏矩阵的矩阵相乘,视矩阵大小,来判断使用单侧倒排索引的矩阵相乘法还是双侧倒排索引的矩阵相乘法。当然如果已有双侧倒排索引的矩阵相乘工具,那么无论矩阵大小,都可以直接使上。

       数据稀疏是个好特性,它给算法设计带来特别的考虑。矩阵相乘问题是在计算精度与计算效率上权衡的一个问题,如果实际业务允许一些精度损失,那么可以适当加些剪枝策略以提高计算效率。



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

历史上的今天

评论

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

页脚

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