新的图模型及机器学习并行框架利器----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

用过GraphLab一个月左右。就编程模型上而言，GraphLab是"think like a vertex"。而MapReduce是"think like a key"。可以这样理解吗？
另外，GraphChi，使用硬盘作为存储空间，可以单机做大规模计算。

chenwq

还有一个是上文所说不适用于非DAG吧。

GraphLab: A New Framework For Parallel Machine Learning: http://select.cs.cmu.edu/publica ... rin-hellerstein.pdf

貌似是他们用GraphLab做的实验，拿过两个KDD冠军还是best paper。

xmubingo

围观。。

chenwq

xmubingo 发表于 2013-1-5 20:46
围观。。

"Big data is like teenage sex. If you do it, you do it bad, and most teenagers just talk about it."
"Big data is like teenage sex: everyone talks about it, nobody really knows how to do it, everyone thinks everyone else is   doing it, so everyone claims they are doing it"

不理解。

xmubingo

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. ...

你骗我，你肯定看了在偷笑

tangzk

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

chenwq

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

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

chenwq

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

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

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/