1.大规模机器学习的挑战越来越丰富。丰富的数据资源为机器学习创造价值带来了越来越多的机会。机器学习在价值数千亿美元的应用中发挥着越来越重要的作用，例如计算广告和推荐系统，它创造的价值也越来越大。但不断增长的数据规模也给机器学习带来了诸多挑战。最大的挑战在于，海量的数据使得对计算资源的需求急剧增加。首先，经典的机器学习算法的计算量基本上与训练数据的数量或特征的数量成二次甚至三次关系[1]。也就是说，数据量或特征数量每增加一倍，计算量就会增加到四倍，甚至八倍。这样的计算量增加是非常恐怖的，即使使用可扩展的计算机集群，也很难满足这样的计算量增加。幸运的是，对于很多依赖凸优化方法的算法，可以采用随机梯度下降法，将计算量的增加降低到与数据量和特征数量成线性关系。然而，大规模机器学习在计算方面仍然存在三大难点。首先，由于几乎所有的机器学习算法都需要对数据进行多次扫描，无论是在什么平台上的海量数据，如果无法存储在内存中，都需要从磁盘存储系统中反复读取数据，这带来了巨大的IO开销。在很多情况下，IO开销占整个训练时间的90%以上。其次，即使有足够的资源来处理内存中的所有数据，对于分布式计算系统来说，在模型训练过程中更新模型也需要大量的网络通信开销。无论是同步更新还是异步更新，庞大的数据量和特征数量都足以让通信流量爆发，这是大规模机器学习的另一个瓶颈。第三，大规模的模型无法将整个模型存储在一个节点上，如何分布式管理模型也是一个比较大的挑战。图1目前主流的大数据处理技术都是基于MapReduce计算模型（包括Hadoop和Spark）。在MapReduce计算模式下，第一个问题只能通过增加内存和SSD存储来解决或缓解，但同时需要很高的成本。关于第二个和第三个问题，MapReduce模型的局限性使得这两个问题很难克服。ParameterServer[2]作为最新的大规模机器学习系统设计模式，主要解决第三个问题，即通过参数服务器和模型参数的分布式管理来支持超大规模模型。同时，模型更新过程中的通信方式可以采用异步更新方式，减少数据同步的开销，提高通信效率。但是在ParameterServer模式下，模型更新量的计算和模型的更新是分开的，其巨大的通信开销原则上是不可避免的。好在常见的大规模机器学习问题都是高维稀疏问题，很大程度上缓解了通信开销的问题，而且ParameterServer突破模型规模限制的优势是MapReduce模型无法替代的，所以ParameterServer已经成为最先进和公认的大规模机器学习模型。图2ParameterServer虽然解决了模型分布式管理的瓶颈，但是异步的通信方式和问题本身的稀疏性大大降低了通信压力。然而，机器学习算法本身对数据的多次扫描带来的计算和通信开销仍然是大规模机器学习效率的一大瓶颈。此外，另一大挑战是算法的参数调优。通常，机器学习算法依赖于一个或多个参数。对于同一个问题，不同的参数设置对模型的准确率影响很大。同样的参数设置在不同的问题上效果也是大不相同的。对于从事机器学习工作的人来说，调参一直是个头疼的问题。知乎上有个问题：“关于调参，为什么越做越有老中医看病的感觉？”[3]，关于机器学习调参的心得、体会、吐槽和小聪明有很多。对于大规模的机器学习问题，调参的难度显然更大：首先，训练和测试过程的时间和计算资源开销巨大。无论采用何种调参方式，多次实验都会带来很大的问题。时间和计算资源消耗。其次，大规模机器学习问题通常是数据快速变化的问题，例如计算广告和推荐系统。先前确定的参数也有随着数据变化而恶化的风险。目前大规模机器学习主要面临两个挑战：一是计算资源消耗比较大，训练时间长，二是调参困难，效率低.TalkingData在大规模机器学习的实践中也深受这两个问题的困扰，尤其是在公司前期硬件资源有限的情况下，这两个问题尤为突出。为了解决这个问题，我们做了很多努力和尝试。TalkingData最近开源的Fregata项目[4]就是我们在这方面的一些成果总结。2.Fregata的优势Fregata是TalkingData开源的大型机器学习算法库，基于Spark，目前支持Spark1.6.x，即将支持Spark2.0。Fregata目前包括三种算法：LogisticRegression、Softmax和RandomDecisionTrees。三种算法中，LogisticRegression和Softmax可视为一种广义线性参数法，其训练过程依赖于凸优化方法。我们提出了GreedyStepAveraging[5]优化方法，在SGD优化方法的基础上实现了学习率的自动调整，省去了参数调整的麻烦。大量实验证明了使用GSA优化方法的LogsticRegression和Softmax算法的收敛速度和稳定性都非常好，在不同数据规模、不同维度尺度和不同的问题上都能达到很好的精度和收敛速度稀疏性。基于GSA优化方法，我们在Spark上实现了并行的LogisticRegression和Softmax算法。我们测试了很多公共数据集和我们自己的数据，发现大部分数据都可以扫描一次收敛。这大大降低了IO开销和通信开销。其中，LogsiticRegression算法还有一个变体版本，支持多集特征交叉。不同的是维度交叉是在训练过程中完成的，这样就不需要在数据准备过程中预先交叉多组特征维度。通常这意味着随着数据层面数据量的膨胀，给数据存储和IO带来了很大的压力。而这种多组特征交集的需求在计算广告和推荐系统中是很常见的，所以我们专门做了支持。随机决策树[6][7]算法是一种高效的非参数学习方法，可以处理分类、多标签分类、回归和多目标回归。而且参数调整也比较简单。但是由于树结构本身比较复杂庞大，很难并行化。我们采用了一些HashTricks，使得二进制特征的数据一次扫描即可完成训练，而且训练过程中内存消耗非常小。总结起来，Fregata有两个优势。一是速度快，二是算法不需要或调整参数比较简单。这两个优点减少了计算资源的消耗，提高了效率。同时，他们也降低了对机器学习工程师的要求，提高了他们的工作效率。3.GSA算法介绍GSA算法是我们最近提出的一种梯度随机优化算法，是Fregata采用的核心优化方法。它是在随机梯度下降法（SGD）基础上的改进：保持了SGD易于实现、内存开销小、易于处理大规模训练样本等优点，同时省去了SGD手动调整学习率参数。事实上，近年来，已经有一些关于SGD算法步长选择的相关工作，如Adagrad、Adadelta、Adam等，但这些方法所声称的自适应步长策略实际上是将算法的敏感性转移到了其他参数的学习率，并没有从本质上解决参数调整的问题，而且它们还引入了额外的存储开销。与这些算法相比，GSA更轻量，易于实现和并行化，与SGD相比没有额外的内存开销，真正不依赖于任何参数。我们将GSA算法应用于Logistic回归和Softmax回归，在libsvm和SGD、Adadelta、SCSG（SVRG的变种）等目前流行的随机优化算法上，对16个不同类型和大小的数据集进行了对比实验。结果表明，参数调整后的GSA算法的最佳性能与不调整任何参数的其他算法相当。此外，GSA在计算速度和内存开销方面也比这些流行的方法具有一定的优势。GSA算法的核心原理很简单：在迭代的每一步对单个样本的损失函数做一次线搜索。具体来说，对于逻辑回归和softmax回归的交叉熵损失函数，我们推导出了一组近似公式，仅利用当前样本点的梯度信息来计算精确的线搜索步长。我们通过对使用该近似公式得到的步长取时间平均值来计算当前迭代步的学习率。这样有两个好处：基于精确线搜索得到的步长包含了当前迭代点到全局最小值的距离信息——接近收敛时步长比较小，反之亦然，从而保证收敛速度;另一方面aspectaveraging策略使得算法对离群点具有更强的鲁棒性，损失下降曲线不会剧烈晃动，为算法带来额外的稳定性。4.GSA算法在Spark上的并行化GSA算法是一种基本的优化方法，Spark上的算法并行化问题也需要考虑。机器学习算法的并行化有两种方式，一种是数据并行，一种是模型并行。但是Spark只能支持数据并行，因为模型并行会产生大量细粒度的节点间通信开销，Spark采用的BSP同步方式无法有效处理。数据并行模式下机器学习算法的并行化有三种方法，即梯度平均、模型平均和结果平均。梯度平均是在每个数据分片上计算当前的梯度更新量，然后对每个分片上的梯度更新量进行汇总平均来更新整体模型。模型平均是指每个分片训练自己的模型，然后将模型聚合平均得到一个整体模型。平均结果实际上是EnsembleLearning，由于模型的大小，这对于大规模问题不是一个好的选择。事实上，梯度平均是目前使用最广泛的方法。目前主要使用ParameterServer的各种实现来支持这种方式，SparkMLLib的算法实现也是采用这种方式。但是在Spark上使用梯度平均在效率上也有比较大的瓶颈，因为这种方法计算当前的梯度更新量依赖于当前最新的模型，这就带来了数据分片之间的频繁模型。同步开销，给MapReuce计算模型带来很大压力。模型平均一直被认为其收敛性在理论上是无法保证的，但最近Rosenblatt[8]等人证明了模型平均的收敛性。在大量的测试中，我们也发现一般的模型通常可以达到非常好的模型精度。考虑到模型平均计算方式更适合MapReduce计算模型，我们在Fregata中对GSA算法的并行方法采用模型平均法。在模型平均的并行方法中，每个数据分片在Map阶段训练自己的模型，最后通过Reduce操作对每个分片上的模型进行平均。扫描数据只需要一个模型同步。而且，在大量的实验中，该方法扫描一次数据后，模型的准确率可以达到很高的水平，经过更多的迭代，基本接近最佳结果。5、Fregata与MLLib的比较Fregata是一个基于Spark的机器学习算法库，因此与Spark内置的算法库MLLib具有很强的可比性。这里简单介绍一下三个数据集，以及两种算法（LogisticRegression和Softmax）的准确率和训练时间对比。我们使用的准确性指标是测试集的AUC。为了准确性和训练时间，每次扫描数据时都会记录算法。Fregata的算法不需要调参，所以我们只做了一个实验。对于MLLib上的算法，我们在各种参数组合（包括优化方法的选择）中进行网格搜索，选择测试集中AUC最高的参数集作为对比结果。Lookalike是基于Fregata平台的相对成熟的服务。它的目标是在种子人群的基础上进行人群放大，寻找潜在客户。我们把Lookalike看成一个二分类问题，所以可以用LogisticRegression算法来处理。训练模型时，以种子种群为正样本，其他为负样本。通常种子种群的数量并不多，所以Lookalike通常是一个正样本比例很小的classimblance问题。我们比较了FregataLR和MLLibLR在大规模数据集（4亿个样本，2000万个特征）上针对Lookalike问题进行模型训练的性能。从图4可以看出，Fregata的LR算法扫描一次数据就收敛到AUC的最高值（在测试集上）0.93。在这个数据样本和MLLib的LR算法中，即使我们通过调参选择最好的AUC结果，其AUC也只有0.55左右。模型的预测精度差异很大。此外，MLLib的训练时间（达到最高精度的时间）也比Fregata大6倍以上。在公开数据集eplison[9]（400,000个训练集，2,000个特征）上，FregataLR在收敛速度和模型效果上也比MLLibLR有更大的优势。从图5可以看出，在这个数据集上，FregataLR经过1次迭代就非常接近测试集上最好的结果，而MLLibLR需要5次迭代，最高准确率与FregataLR相差很大。MLLibLR的训练时间是FregataLR的5倍以上。另外，图6展示了FregataLR和MLLibLR在六个不同问题上的测试集AUC曲线。可以看出，FregataLR算法在不同问题上的收敛速度和稳定性比MLLibLR有更大的优势。FregataLR第一次迭代后，AUC已经基本收敛，即使和最高值还有一些差距，但已经很接近了。我们还在公开可用的数据集MNIST上测试了Softmax算法。从图7可以看出，FregataSoftmax在扫描一次数据后也非常接近测试集上最好的结果，而MLLibSoftmax需要扫描40多次数据才接近FregataSoftmax的结果扫描数据一次。比较两种算法达到各自最优结果所花费的时间，MLLibSoftmax是FregataSoftmax的50多倍。六。Fregata的使用介绍在上一节中，我们简单介绍了Fregata算法库涉及的一些技术原理和性能对比。让我们来看看如何使用Fregata。Fregata可以通过3种不同的方式获得。如果使用Maven管理项目，可以在pom.xml中加入如下代码，
