Fregata: 轻量级大规模机器学习算法库 Chief Data Scientist, TalkingData
大纲 大规模机器学习的挑战 Fregata 的优点 GSA 算法介绍 GSA 算法在 Spark 上的并行化与 MLLib 的对比如何使用 Fregata Fregata 的发展目标
大规模机器学习两个挑战 计算瓶颈 调参困难
经典算法的计算瓶颈 计算复杂度随数据规模超线性增长 Cheng T. Chu, Sang K. Kim, Yi A. Lin, Yuanyuan Yu, Gary R. Bradski, Andrew Y. Ng, Kunle Olukotun, Map-Reduce for Machine Learning on Multicore, NIPS, 2006.
梯度下降法 随机梯度下降法
三大计算瓶颈 IO 开销 通信开销 模型规模
Map Reduce IO 开销 : 可通过内存 /SSD 加速来缓解 通信开销 : 无法解决 模型规模 : 无法解决
Parameter Server IO 开销 : 可通过内存 /SSD 加速来缓解 通信开销 : 通过异步更新部分缓解 模型规模 : 分布式管理, 解除了模型规模限制
调参困难 参数搜索空间大 对经验依赖比较大
大纲 大规模机器学习的挑战 Fregata 的优点 GSA 算法介绍 GSA 算法在 Spark 上的并行化与 MLLib 的对比如何使用 Fregata Fregata 的发展目标
Fregata 项目 https://github.com/talkingdata/fregata
Fregata 项目 基于 Spark, 目前支持 1.6 目前实现了四种算法 Logistic Regression Combine Features Logistic Regression Softmax Random Decision Trees
Fregata 项目的特点 速度快 只需要扫描一遍数据 调参容易 LR 和 Softmax 算法不需要调参 RDT 调参容易
大纲 大规模机器学习的挑战 Fregata 的优点 GSA 算法介绍 GSA 算法在 Spark 上的并行化与 MLLib 的对比如何使用 Fregata Fregata 的发展目标
https://arxiv.org/abs/1611.03608 Greedy Step Averaging 优化方法
GSA 优点 SGD 方法需要调学习率 衍生方法 Adadelta, ADMM, SVRG 同样存在着调参的问题, 有些还需要付出更大的存储代价 GSA 方法不需要调参
GSA 算法流程图
Greedy Step 方法
Averaging 策略
Logistic Regression & Softmax via GSA Logistic Regression 学习率公式 Softmax 学习率公式
GSA LR & Softmax 实验 数据
GSA LR & Softmax 实验 对比算法和总体结果 对比算法 SGD, Adadelta, SCSG
GSA LR & Softmax 实验 GSA vs SGD
GSA LR & Softmax 实验 GSA vs Adadelta
GSA LR & Softmax 实验 GSA vs SCSG
大纲 大规模机器学习的挑战 Fregata 的优点 GSA 算法介绍 GSA 算法在 Spark 上的并行化与 MLLib 的对比如何使用 Fregata Fregata 的发展目标
大规模机器学习并行化方法 梯度平均 模型平均 n w t = w t 1 η n i=0 n Q i (w t 1 ) w t = 1 n i=0 w t 1,i 结果平均 m y j = 1 m k=0 y j,k
模型平均的收敛性 当 N 个样本均匀分配给 m 台机器训练出 m 个 p 维的模型,n=N/m 时, 对线性模型且当 n>>p 时逼近效果是比较好的, 当 p 很大时, 误差和 m 呈线性关系 对非线性模型, 误差包含二阶项, 可能会很大 Rosenblatt J D, Nadler B. On the optimality of averaging in distributed statistical learning[j]. Information and Inference, 2016: iaw013 MLA
大纲 大规模机器学习的挑战 Fregata 的优点 GSA 算法介绍 GSA 算法在 Spark 上的并行化与 MLLib 的对比如何使用 Fregata Fregata 的发展目标
LR 实验结果 1
LR 实验结果 2 Lookalike 300million X 20 million dataset 0.01% postive class instances Epsilon 400000X 2000 dataset
Softmax 实验结果 - MNIST
大纲 大规模机器学习的挑战 Fregata 的优点 GSA 算法介绍 GSA 算法在 Spark 上的并行化与 MLLib 的对比如何使用 Fregata Fregata 的发展目标
Maven 配置 <dependency> <groupid>com.talkingdata.fregata</groupid> <artifactid>core</artifactid> <version>0.0.1</version> </dependency> <dependency> <groupid>com.talkingdata.fregata</groupid> <artifactid>spark</artifactid> <version>0.0.1</version> </dependency> SBT 配置 librarydependencies += "com.talkingdata.fregata" % "core" % "0.0.1" librarydependencies += "com.talkingdata.fregata" % "spark" % "0.0.1"
LR 算法示例 import fregata.spark.data.libsvmreader import fregata.spark.metrics.classification.{areaunderroc, Accuracy} import fregata.spark.model.classification.logisticregression import org.apache.spark.{sparkconf, SparkContext} // 加载数据 val (_, traindata) = LibSvmReader.read(sc, trainpath, numfeatures.toint) val (_, testdata) = LibSvmReader.read(sc, testpath, numfeatures.toint) // 训练模型 val model = LogisticRegression.run(trainData) val pd = model.classpredict(testdata) // 测试 AUC 指标 val auc = AreaUnderRoc.of( pd.map{ case ((x,l),(p,c)) => p -> l })
大纲 大规模机器学习的挑战 Fregata 的优点 GSA 算法介绍 GSA 算法在 Spark 上的并行化与 MLLib 的对比如何使用 Fregata Fregata 的发展目标
Fregata 的目标 轻量级 高性能 易使用
邮箱 :xiatian.zhang@gmail.com 微博 : _ 机器学习