新的图模型及机器学习并行框架利器----GraphLab+Graphbuilder

Fth-Hokage

         在海量数据盛行的今天，大规模并行计算已经随处可见，尤其是MapReduce框架的出现，促进了并行计算在互联网海量数据处理中的广泛应用。而针对海量数据的机器学习对并行计算的性能、开发复杂度等提出了新的挑战。

        机器学习算法具有下面两个特点：数据依赖性强，运算过程各个机器之间要进行频繁的数据交换；流处理复杂，整个处理过程需要多次迭代，数据的处理条件分支多。

      而MapReduce是典型的SIMD模型，Map阶段集群的各台机器各自完成负载较重的计算过程，数据并行度高，适合完成类似矩阵运算、数据统计等数据独立性强的计算，而对于机器学习类算法并行性能不高。

      为解决机器学习的流处理，Google提出了Pregel框架，Pregel是严格的BSP模型，采用“计算-通信-同步”的模式完成机器学习的数据同步和算法迭代。Goolge曾称其80%的程序使用MapReduce完成，20%的程序使用Pregel实现。因而，Pregel是很成熟的机器学习流处理框架，但Google一直没有将Pregel的具体实现开源，外界对Pregel的模仿实现在性能和稳定性方面都未能达到工业级应用的标准。

     2010年，CMU的Select实验室提出了GraphLab框架，GraphLab是面向机器学习的流处理并行框架。同年， GraphLab基于最初的并行概念实现了1.0版本，在机器学习的流处理并行性能方面得到很大的提升，并引起业界的广泛关注，在2012年GraphLab升级到2.1版本，进一步优化了其并行模型，尤其对自然图的并行性能得到显著改进。
    目前，业界常见的针对迭代或图运算的框架有：
   
    GraphLab的软件架构：
     
    可以看出，他也包含一些常见的机器学习算法
  
    除了常规的机器学习算法，我们也不得不提到图运算(尤其是社交网络)——在数据挖掘与机器学习中也是无处不在：     
   
    然而原始的mapreduce框架针对这些问题显得很无力，正如我们上面所分析的那样，那么来看一种新的方案：
      
    图的并行计算模式：
        
   以这种方案来计算pagerank，性能对比如下：
      
   不知大家有什么不同的见解，不吐不快，哈哈，另外，哪位童靴要是有兴趣，可以研究一下   

chenwq

貌似确实PThreads比较多。

Fth-Hokage

tangzk 发表于 2013-1-8 18:41
确实，说起来Hadoop确不是为机器学习而生的，只是为了其当时的分布式大规模批量处理，如爬虫、索引和存储 ...

哈哈 新的收获 得亏了大家畅所欲言啊

tangzk

Fth-Hokage 发表于 2013-1-6 16:42
哈哈 这个见解真是一针见血
     当前大数据主要从三个层析展开：

确实，说起来Hadoop确不是为机器学习而生的，只是为了其当时的分布式大规模批量处理，如爬虫、索引和存储等，这些简单的数据流任务用MapReduce还是很适合，目前业界也都是这么干。
但是当涉及大规模网络通讯交互，甚至数据的迭代时，就需要更新的计算模型来支撑了，Pregel适用于图模型的处理，MPI类适合异构环境的并行集群计算，GPU类适合更高计算密集型的并行计算。
现在感觉机器学习见得多的还是用MPI+PThread做，据我所知有百度、淘宝等，不过存储依然是HDFS，另外80%的日常业务数据流处理任务还是用MapReduce。

chenwq

chenwq 发表于 2013-1-5 17:31
用过GraphLab一个月左右。就编程模型上而言，GraphLab是"think like a vertex"。而MapReduce是"think like  ...

GraphChi: Your Laptop Can Now Analyze Big Data
http://www.technologyreview.com/ ... &nld=2012-07-17

Fth-Hokage

chenwq 发表于 2013-1-6 11:46
"Big data is like teenage sex. If you do it, you do it bad, and most teenagers just talk about it. ...

     哈哈 这个见解真是一针见血
     当前大数据主要从三个层析展开：

     这三个层析的发展依次对应着云的 SaaS, PaaS, IaaS

      其中底层硬件基础架构主要由intel包揽：“英特尔的智能加速技术将使得基于英特尔的服务器平台，能获得优于竞争对手的表现。其次，大量的超线程已经在服务器上被广泛地应用，在集群系统当中使整个集群有更快的互联互通，超级互联架构能够也能使整个集成性能大幅度提高。英特尔最新的存储架构也是对今后可扩展性的存储架构提供了支撑。”

      对于中间层和最上层，林智仁 在百度做关于大数据 分类de 演讲时说:“当下诞生的分布式系统或框架--尤其hadoop，并不是为机器学习算法而诞生的，因此很多机器学习算法在这些框架上的并行化并不能达到最佳效果”“那么解决途径就是 1. 致力于新的更适合于机器学习的系统的研究  2.  设计新的能很好适应当前这些框架的算法”

      所以，目前除了intel能把重心放在底层外，业界其他很多机构都是重在 中间一层 的研发，我们看看典型的例子：google—pregel, CMU—GraphLab,  CRMI—BC-BSP, 华为新成立的诺亚方舟 实验室 其中一个重心也是“研发适合机器学习算法的分布式框架”，还有HaLoop, Graphbuilder, HTC DATA CENTEL LAB也在开发适应于大数据的并行框架

    当然 对于上层数据智能 了解的不太多 欢迎大家纠正，完善这几句 闲扯

chenwq

GraphLab实现的ALS (Alternating least squares), SGD (Stochastic Gradient Descent) , Bias SGD, Weighted-ALS, Sparse-ALS, 还有在Netflix Price里用到的SVD++。http://graphlab.org/toolkits/collaborative-filtering/

chenwq

tangzk 发表于 2013-1-6 13:27
GraphLab出品的这个大数据处理框架本年度值得关注，另外这个实验室的矩阵分解也做得相当拉风。

Tensor Factorization吗?他们用来做推荐。牛逼啊CMU

chenwq

xmubingo 发表于 2013-1-6 13:13
你骗我，你肯定看了在偷笑

哈哈。嗯。最早据说这话是在说agile

tangzk

GraphLab出品的这个大数据处理框架本年度值得关注，另外这个实验室的矩阵分解也做得相当拉风。