轻量级大规模机器学习算法库 Fregata 开源：快速，无需调参

一. 大规模机器学习的挑战

随着互联网，移动互联网的兴起，可以获取的数据变得越来越多，也越来越丰富。数据资源的丰富，给机器学习带来了越来越多，越来越大创造价值的机会。 机器学习在计算广告，推荐系统这些价值上千亿美元的应用中起到的作用越来越大，创造的价值也越来越大。但是越来越大的数据规模也给机器学习带来了很多挑战。

最大的挑战就是庞大的数据量使得对计算资源的需求也急剧增长。首先经典的机器学习算法其计算量基本上都是与训练数据条数或者特征数量呈二次方甚至是三次方关系的 [1]。即是说数据量或者特征数每翻一倍，则计算量就要增加到原来的四倍，甚至是八倍。这样的计算量增长是十分可怕的，即使是采用可扩展的计算机集群一难以满足这样的计算量增长。好在对于很多依赖于凸优化方法的算法，可以采用随机梯度下降方法，将计算量的增长降到基本与数据量和特征数呈线性关系。但是，大规模机器学习在计算上依然有三个比较大的困难。

第一，因为几乎所有的机器学习算法都需要多次扫描数据，对于大规模数据无论在什么平台上，如果不能全部存储在内存中，就需要反复从磁盘存储系统中读取数据，带来巨大的 IO 开销。在很多情况下，IO 开销占到整个训练时间的 90% 以上。

第二，即使有足够的资源将所有数据都放到内存中处理，对于分布式的计算系统，模型训练过程中对模型更新需要大量的网络通信开销。无论是同步更新还是异步更新，庞大的数据量和特征数都足以使得通信量爆炸，这是大规模机器学习的另外一个瓶颈。

第三，大规模的模型使得无法在一个节点上存储整个模型，如何将模型进行分布式的管理也是一个比较大的挑战。

图 1

目前的主流大数据处理技术都是以 Map Reduce 计算模式为核心的（包括 Hadoop 和 Spark）。而Map Reduce计算模式下对第一个问题只能通过增加内存，SSD 存储来解决或者缓解，但同时也需要付出高昂的成本。对于第二，和第三个个问题，Map Reduce 模式的局限是很难克服这两个问题的。

而Parameter Server[2] 作为目前最新的大规模机器学习系统设计模式，主要解决的其实是第三个问题，通过参数服务器以及模型参数的分布式管理来实现对超大规模模型的支持。同时在模型更新过程中的通信模式可以采用异步更新模式，来减小数据同步的开销，提高通信效率，但是 Parameter Server 模式下模型的更新量计算和模型的更新是分离的，其庞大的通信开销在原理上就是不可避免的。幸运的是，常见的大规模机器学习问题，都是高维稀疏问题，在很大程度上缓解了通信开销的问题，而 Parameter Server 突破了模型规模限制的优点是 Map Reduce 模式无法取代的，所以 Parameter Server 成为了目前大规模机器学习最先进，最受认可的模式。

图 2

虽然 Parameter Server 解决了模型分布式管理的瓶颈，异步通信模式和问题本身的稀疏性大大降低了通信的压力。 但是机器学习算法本身对数据的多次扫描带来的计算和通信开销依然是大规模机器学习效率的很大瓶颈。

除此之外还有一个很大的挑战就是算法的调参工作， 一般机器学习算法都会依赖一个或者多个参数，对于同一问题，不同的参数设定对模型精度的影响是很大的，而同一参数设定在不同的问题上的效果也有很大的不同。对于从事机器学习工作的人来说，调参始终是一个令人的头疼的问题。知乎上有个问题是“调参这事儿，为什么越干越觉得像老中医看病？”[3]，里面有不少关于机器学习调参的经验，心得，吐槽和抖机灵。

对于大规模机器学习问题，调参的难度显然是更大的：

首先，一次训练和测试过程的时间和计算资源开销都是庞大的，不管采用什么调参方法，多次实验都会带来很大的时间和计算资源消耗。

其次，大规模机器学习问题通常都是数据变化很快的问题，如计算广告和推荐系统，之前确定好的参数在随着数据的变化，也有劣化的风险。

目前来说大规模机器学习存在的主要挑战是两个：第一是计算资源的消耗比较大，训练时间较长的问题，第二是调参比较困难，效率较低。TalkingData 在大规模机器学习的实践中也深受这两个问题的困然，特别是公司在早起阶段硬件资源十分有限，这两个问题特别突出。我们为了解决这个问题，做了很多努力和尝试。TalkingData 最近开源的 Fregata 项目 [4]，就是我们在这方面取得的一些成果的总结。

二. Fregata 的优点

Fregata 是 TalkingData 开源的大规模机器学习算法库，基于 Spark，目前支持 Spark 1.6.x, 很快会支持 Spark 2.0。目前 Fregata 包括了 Logistic Regression, Softmax, 和 Random Decision Trees 三中算法。

三种算法中 Logistic Regression, Softmax 可以看作一类广义线性的参数方法，其训练过程都依赖于凸优化方法。我们提出了 Greedy Step Averaging[5] 优化方法，在 SGD 优化方法基础上实现了学习率的自动调整，免去了调参的困扰，大量的实验证明采用 GSA 优化方法的 Logstic Regression 和 Softmax 算法的收敛速度和稳定性都是非常不错的，在不同数据规模，不同维度规模和不同稀疏度的问题上都能取得很好的精度和收敛速度。

基于 GSA 优化方法，我们在 Spark 上实现了并行的 Logistic Regression 和 Softmax 算法，我们测试了很多公开数据集和我们自己的数据，发现在绝大部分数据上都能够扫描一遍数据即收敛。这就大大降低了 IO 开销和通信开销。

其中 Logsitic Regression 算法还有一个支持多组特征交叉的变种版本，其不同点是在训练过程中完成维度交叉，这样就不需要在数据准备过程中将多组特征维度预先交叉准备好，通常这意味着数据量级上的数据量膨胀，给数据存储和 IO 带来极大压力。而这种多组特征交叉的需求在计算广告和推荐系统中又是非常常见的，因此我们对此做了特别的支持。

而 Random Decision Trees[6][7] 算法是高效的非参数学习方法，可以处理分类，多标签分类，回归和多目标回归等问题。而且调参相对也是比较简单的。但是由于树结构本身比较复杂而庞大，使得并行比较困难，我们采用了一些 Hash Trick 使得对于二值特征的数据可以做到扫描一遍即完成训练，并且在训练过程中对内存消耗很少。

总结起来，Fregata 的优点就两个，第一是速度快，第二是算法无需调参或者调参相对简单。这两个优点降低了减少了计算资源的消耗，提高了效率，同时也降低了对机器学习工程师的要求，提高了他们的工作效率。

三. GSA 算法介绍

GSA 算法是我们最近提出的梯度型随机优化算法, 是 Fregata 采用的核心优化方法。它是基于随机梯度下降法 (SGD) 的一种改进：保持了 SGD 易于实现，内存开销小，便于处理大规模训练样本的优势，同时免去了 SGD 不得不人为调整学习率参数的麻烦。

事实上，最近几年关于 SGD 算法的步长选取问题也有一些相关工作，像 Adagrad, Adadelta, Adam 等。但这些方法所声称的自适应步长策略其实是把算法对学习率的敏感转移到了其他参数上面，并未从本质上解决调参的问题，而且他们也引入了额外的存储开销。GSA 和这些算法相比更加轻量级，易于实现且易于并行，比起 SGD 没有额外的内存开销，而且真正做到了不依赖任何参数。

我们把 GSA 算法应用于 Logistic 回归和 Softmax 回归，对 libsvm 上 16 个不同类型规模不等的数据集，和 SGD，Adadelta，SCSG(SVRG 的变种) 这些目前流行的随机优化算法做了对比实验。结果显示，GSA 算法在无需调任何参数的情况下，和其他算法做参数调优后的最佳表现不相上下。此外，GSA 比起这些流行的方法在计算速度和内存开销方面也有一定的优势。

GSA 算法的核心原理非常简单：在迭代的每一步对单个样本的损失函数做线搜索。具体来说，我们对逻辑回归和 softmax 回归的交叉熵损失函数，推导出了一套仅用当前样本点的梯度信息来计算精确线搜索步长的近似公式。我们把利用这套近似公式得到的步长做时间平均来计算当前迭代步的学习率。这样做有两方面的好处：基于精确线搜索得到的步长包含了当前迭代点到全局极小的距离信息——接近收敛时步长比较小，反之则更大，因而保证收敛速度；另一方面平均策略使算法对离群点更鲁棒，损失下降曲线不至剧烈抖动，为算法带来了额外的稳定性。

四. GSA 算法 Spark 上的并行化实现

GSA 算法是基本的优化方法，在 Spark 上还需要考虑算法并行化的问题。机器学习算法的并行化有两种方式，一种是数据并行，另一种是模型并行。但是 Spark 只能支持数据并行，因为模型并行会产生大量细粒度的节点间通信开销，这是 Spark 采用的 BSP 同步模式无法高效处理的。

数据并行模式下进行机器学习算法的并行化又有三种方法，分别是梯度平均，模型平均，以及结果平均。梯度平均是在各个数据分片上计算当前的梯度更新量然后汇总平均各分片上的梯度更新量总体更新模型。模型平均是各分片训练自己的模型，然后再将模型汇总平均获得一个总体的模型。而结果平均实际上就是 Ensemble Learning， 在大规模问题上因为模型规模的问题，并不是一个好的选择。

实际上是目前采用得最多的是梯度平均，当前 Parameter Server 各种实现上主要还是用来支持这种方式，Spark MLLib 的算法实现也是采用的该方式。但是在 Spark 上采用梯度平均在效率上也有比较大的瓶颈，因该方法计算当前的梯度更新量是要依赖于当前的最新模型的，这就带来了在各数据分片之间频繁的模型同步开销，这对 Map Reuce 计算模式的压力是较大的。

模型平均一直被认为其收敛性在理论上是没有保证的，但是最近 Rosenblatt[8] 等人证明了模型平均的收敛性。而我们在大量的测试中，也发现模型平均通常能取得非常好的模型精度。考虑到模型平均的计算模式更适合 Map Reduce 计算模型，我们在 Fregata 中对于 GSA 算法的并行方法采用的就是模型平均方法。模型平均的并行方法中，每个数据分片在 Map 阶段训练自己的模型，最后通过 Reduce 操作对各个分片上的模型进行平均，扫描一次数据仅需要做一次模型同步。而且在大量的实验中，该方法在扫描一次数据后，模型的精度就可达到很高的水平，基本接近于更多次迭代后的最好结果。

五. Fregata 与 MLLib 对比

Fregata 是基于 Spark 的机器学习算法库，因此与 Spark 内置算法库 MLLib 具有很高的可比性。我们这里简要介绍了三个数据集，两种算法（Logistic Regression 和 Softmax）上的精度和训练时间对比。精度指标我们采用的是测试集的 AUC。对于精度和训练时间，算法每扫描完一次数据记录一次。

Fregata 的算法不需要调参，因此我们都只做了一次实验。而对于 MLLib 上的算法，我们在各种参数组合（包括优化方法的选择）中进行了网格搜索，选取了测试集 AUC 能达到最高的那组参数作为对比结果。

Lookalike 是一个基于 Fregata 平台运用比较成熟的服务，其目标在于根据种子人群进行人群放大以寻找潜在客户。我们将 Lookalike 作为二分类问题来处理，因此可以采用 Logistic Regression 算法来处理。在训练模型时以种子人群为正样本，其他为负样本，通常种子人群的数量不会很多，因此 Lookalike 通常是正样本比例非常少的 class imblance 问题。 在一个大规模数据集 (4 亿样本，2 千万个特征) 上的 Lookalike 问题的模型训练中，我们对比了 Fregata LR 和 MLLib LR 的性能。

从图 4 中可以看到 Fregata 的 LR 算法扫描一次数据即收敛达到 AUC（测试集上）的最高值 0.93。在这个数据样本中 而 MLLib 的 LR 算法，即使我们通过调参选取了最好的 AUC 结果，其 AUC 也仅为 0.55 左右。模型预测精度差别非常大。另外，MLLib 的训练时间（达到最高精度的时间）也是 Fregata 大的 6 倍以上。

在公开数据集 eplison[9] 上（40 万训练集，2000 特征）, Fregata LR 无论从收敛速度还是模型效果与 MLLib LR 相比也有较大的优势。从图 5 中可以看到，在这个数据集上 Fregata LR 在迭代一次以后就在测试集上非常接近最好的结果了，而 MLLib LR 需要 5 次迭代而且最高的精度比 Fregata LR 相差很大，而训练时间 MLLib LR 也是 Fregata LR 的 5 倍以上。

另外图 6 展示了 Fregata LR 与 MLLib LR 在 6 个不同问题上的测试集 AUC 曲线，可以看到 Fregata LR 算法在不同问题上收敛速度和稳定性相较于 MLLib LR 都是有较大的优势。Fregata LR 在第一次迭代后，AUC 就已经基本收敛，即使与最高值还有一些差距，但是也是非常接近了。

我们也在公开数据集 MNIST 上测试了 Softmax 算法。 从图 7 中可以看到， Fregata Softmax 也是一次扫描数据后在测试集上的 AUC 就非常接近最好的结果， 而 MLLib Softmax 需要扫描数据多达 40 多次以后才接近 Fregata Softmax 一次扫描数据的结果。对比两个算法在达到各自最优结果所花的时间，MLLib Softmax 是 Fregata Softmax 的 50 倍以上。

六. Fregata 的使用简介

前面简要介绍了 Fregata 算法库涉及到的一些技术原理和性能对比，我们再来看看 Fregata 的使用方式。可以通过 3 种不同的方式来获取 Fregata 如果使用 Maven 来管理工程，则可以通过添加如下代码在 pom.xml 中进行引入，

 
   <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 来管理工程，则可以通过如下代码在 build.sbt 中进行引入，

 
// 如果手动部署到本地 maven 仓库，请将下行注释打开
   // resolvers += Resolver.mavenLocal
   libraryDependencies += "com.talkingdata.fregata" % "core" % "0.0.1"
   libraryDependencies += "com.talkingdata.fregata" % "spark" % "0.0.1"

如果希望手动部署到本地 maven 仓库，可以通过在命令中执行如下命令来完成：

 
git clone https://github.com/TalkingData/Fregata.git
cd Fregata
mvn clean package install

接下来，让我们以 Logistic Regression 为例来看看如何快速使用 Fregata 完成分类任务：

1. 引入所需包

 
import fregata.spark.data.LibSvmReader
import fregata.spark.metrics.classification.{AreaUnderRoc, Accuracy}
import fregata.spark.model.classification.LogisticRegression
import org.apache.spark.{SparkConf, SparkContext}

2. 通过 Fregata 的 LibSvmReader 接口加载训练及测试数据集，训练及测试数据集为标准 LibSvm 格式，可参照 [10]

 
val (_, trainData)  = LibSvmReader.read(sc, trainPath, numFeatures.toInt)
   val (_, testData)  = LibSvmReader.read(sc, testPath, numFeatures.toInt)

3. 针对训练样本训练 Logsitic Regression 模型

 
val model = LogisticRegression.run(trainData)

4. 基于已经训练完毕的模型对测试样本进行预测

 
val pd = model.classPredict(testData)

5. 通过 Fregata 内置指标评价模型效果

 
val auc = AreaUnderRoc.of( pd.map{
     case ((x,l),(p,c)) =>
       p -> l
   })

在 Fregata 中，使用 breeze.linalg.Vector[Double] 来存储一个样本的特征，如果数据格式已经是 LibSvm，则只需通过 Fregata 内部的接口 LibSvmReader.read(…) 来加载即可。否则，可以采用如下的方法将代表实例的一组数据封装成 breeze.linalg.Vector[Double] 即可放入模型中进行训练及测试。

 
// indices  Array 类型，下标从 0 开始，保存不为 0 的数据下标
// values  Array 类型， 保存相应于 indices 中对应下标的数据值
// length  Int 类型，为样本总特征数
// label   Double 类型，为样本的标签。如果是测试数据，则不需该字段
sc.textFile(input).map{
val indicies  = ...
val values   = ...
val label    = ...
...
(new SparseVector(indices, values, length).asInstanceOf[Vector], asNum(label))
}

七. Freagata 的发展目标

Fregata 目前集成的算法还不多，未来还会继续扩充更多的高效的大规模机器学习算法。Fregata 项目追求的目标有 3 个：轻量级，高性能，易使用。

轻量级是指 Fregata 将尽可能在标准 Spark 版本上实现算法，不另外搭建计算系统，使得 Fregata 能够非常容易的在标准 Spark 版本上使用。虽然 Spark 有一些固有的限制，比如对模型规模的限制，但是作为目前大数据处理的基础工具，Fregata 对其的支持能够大大降低大规模机器学习的应用门槛。毕竟另外搭建一套专用大规模机器学习计算平台，并整合到整个大数据处理平台和流程中，其成本和复杂性也是不可忽视的。

高性能就是坚持高精度和高效率并举的目标，尽可能从算法上和工程实现上将算法的精度和效率推到极致，使得大规模机器学习算法从笨重的牛刀变成轻快的匕首。目前对 Fregata 一个比较大的限制就是模型规模的问题，这是基于 Spark 天生带来的劣势。未来会采用一些模型压缩的方法来缓解这个问题。

易使用也是 Fregata 追求的一个目标，其中最重要的一点就是降低调参的难度。目前的三个算法中有两个是免调参的，另一个也是相对来说调参比较友好的算法。降低了调参的难度，甚至是免去了调参的问题，将大大降低模型应用的难度和成本，提高工作效率。

另一方面我们也会考虑某些常用场景下的特殊需求，比如 LR 算法的特征交叉需求。虽然通用的 LR 算法效率已经很高，但是对于特征交叉这种常见需求，如果不把特征交叉这个过程耦合到算法中去，就需要预先将特征交叉好，这会带来巨大的 IO 开销。而算法实现了对特征交叉的支持，就规避了这个效率瓶颈。未来在集成更多的算法的同时，也会考虑各种常用的场景需要特殊处理的方式。

Fregata 项目名称的中文是军舰鸟，TalkingData 的开源项目命名都是用的鸟名，而军舰鸟是世界上飞得最快的鸟，最高时速达到 418km/ 小时，体重最大 1.5 公斤，而翼展能够达到 2.3 米，在全球分布也很广泛。我们希望 Fregata 项目能够像军舰鸟一样，体量轻盈，但是能够支持大规模，高效的机器学习，而且具有很强的适用性。目前 Fregata 还是只雏鸟, 期望未来能够成长为一只展翅翱翔的猛禽。

引用

1. 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.
2. https://www.zhihu.com/question/48282030
3. https://github.com/TalkingData/Fregata
4. http://arxiv.org/abs/1611.03608
5. http://www.ibm.com/developerworks/cn/analytics/library/ba-1603-random-decisiontree-algorithm-1/index.html
6. http://www.ibm.com/developerworks/cn/analytics/library/ba-1603-random-decisiontree-algorithm-2/index.html
7. Rosenblatt J D, Nadler B. On the optimality of averaging in distributed statistical learning[J]. Information and Inference, 2016: iaw013 MLA
8. https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/binary.html#epsilon
9. https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/

作者介绍

张夏天：TalkingData 首席数据科学家，12 年大规模机器学习和数据挖掘经验，对推荐系统、计算广告、大规模机器学习算法并行化、流式机器学习算法有很深的造诣；在国际顶级会议和期刊上发表论文 12 篇，申请专利 9 项；前 IBM CRL、腾讯、华为诺亚方舟实验室数据科学家；KDD2015、DSS2016 国际会议主题演讲；机器学习开源项目 Dice 创始人。

感谢杜小芳对本文的审校。

给InfoQ 中文站投稿或者参与内容翻译工作，请邮件至 editors@cn.infoq.com 。也欢迎大家通过新浪微博（ @InfoQ ， @丁晓昀），微信（微信号： InfoQChina ）关注我们。