机器学习和生物信息学实验室联盟

标题: 新的图模型及机器学习并行框架利器----GraphLab+Graphbuilder [打印本页]

作者: Fth-Hokage 时间: 2013-1-5 16:21
标题: 新的图模型及机器学习并行框架利器----GraphLab+Graphbuilder
本帖最后由 Fth-Hokage 于 2013-1-5 16:38 编辑

      在海量数据盛行的今天，大规模并行计算已经随处可见，尤其是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版本，进一步优化了其并行模型，尤其对自然图的并行性能得到显著改进。
目前，业界常见的针对迭代或图运算的框架有：
[attach]1215[/attach]
GraphLab的软件架构：
[attach]1206[/attach]
可以看出，他也包含一些常见的机器学习算法

除了常规的机器学习算法，我们也不得不提到图运算(尤其是社交网络)——在数据挖掘与机器学习中也是无处不在：
[attach]1210[/attach]
然而原始的mapreduce框架针对这些问题显得很无力，正如我们上面所分析的那样，那么来看一种新的方案：
[attach]1212[/attach]
图的并行计算模式：
[attach]1209[/attach]
以这种方案来计算pagerank，性能对比如下：
[attach]1208[/attach]
不知大家有什么不同的见解，不吐不快，哈哈，另外，哪位童靴要是有兴趣，可以研究一下

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

作者: chenwq 时间: 2013-1-5 19:10
本帖最后由 chenwq 于 2013-1-5 19:12 编辑

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

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

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

作者: xmubingo 时间: 2013-1-5 20:46
围观。。

作者: chenwq 时间: 2013-1-6 11:46

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 时间: 2013-1-6 13:13

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 时间: 2013-1-6 13:27
GraphLab出品的这个大数据处理框架本年度值得关注，另外这个实验室的矩阵分解也做得相当拉风。

作者: chenwq 时间: 2013-1-6 14:29

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

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

作者: chenwq 时间: 2013-1-6 14:38

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

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

作者: chenwq 时间: 2013-1-6 14:41
GraphLab实现的ALS (Alternating least squares), SGD (Stochastic Gradient Descent) , Bias SGD, Weighted-ALS, Sparse-ALS, 还有在Netflix Price里用到的SVD++。http://graphlab.org/toolkits/collaborative-filtering/

作者: Fth-Hokage 时间: 2013-1-6 16:42

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

   哈哈这个见解真是一针见血
   当前大数据主要从三个层析展开：
[attach]1216[/attach]
   这三个层析的发展依次对应着云的 SaaS, PaaS, IaaS

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

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

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

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

作者: chenwq 时间: 2013-1-8 10:16

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

作者: tangzk 时间: 2013-1-8 18:41

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

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

作者: Fth-Hokage 时间: 2013-1-9 10:24

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

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

作者: chenwq 时间: 2013-1-21 12:33
貌似确实PThreads比较多。

欢迎光临机器学习和生物信息学实验室联盟 (http://123.57.240.48/)