四. 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倍以上。