一. 大规模机器学习的挑战
随着互联网，移动互联网的兴起，可以获取的数据变得越来越多，也越来越丰富。数据资源的丰富，给机器学习带来了越来越多，越来越大创造价值的机会。 机器学习在计算广告，推荐系统这些价值上千亿美元的应用中起到的作用越来越大，创造的价值也越来越大。但是越来越大的数据规模也给机器学习带来了很多挑战。
最大的挑战就是庞大的数据量使得对计算资源的需求也急剧增长。首先经典的机器学习算法其计算量基本上都是与训练数据条数或者特征数量呈二次方甚至是三次方关系的[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算法介绍
#p#分页标题#e#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操作对各个分片上的模型进行平均，扫描一次数据仅需要做一次模型同步。而且在大量的实验中，中国直播网 ，该方法在扫描一次数据后，模型的精度就可达到很高的水平，基本接近于更多次迭代后的最好结果。
特别声明：本文为中国直播网直播号作者或机构上传并发布，仅代表该作者或机构观点，不代表中国直播网的观点或立场，中国直播网仅提供信息发布平台。
版权声明：版权归著作权人，转载仅限于传递更多信息，如来源标注错误侵害了您的权利，请来邮件通知删除，一起成长谢谢
欢迎加入：直播号，开启无限创作！一个敢纰漏真实事件，说真话的创作分享平台，一个原则：只要真实，不怕事大，有线索就报料吧！申请直播号请用电脑访问https://zbh.zhibotv.com.cn。
