猿辅导开源分布式机器学习库ytk-learn及分布式通信库ytk-mp4j

　　作者：猿辅导研究团队语音识别负责人夏龙，机器学习研发工程师吴凡

 

　　近期，猿辅导公司开源了两个机器学习项目——ytk-learn, ytk-mp4j，其中 ytk-mp4j 是一个高效的分布式通信库，基于该通信库我们实现了 ytk-learn 分布式机器学习库，该机器学习库目前在猿辅导很多应用场景中使用，比如，自适应学习、学生高考分预测、数据挖掘、课程推荐等。

 

 

 

​　　LR(Logistic Regression), GBDT(Gradient Boosting Decision Tree), FM(Factorization Machines), FFM(Field-aware Factorization Machines) 模型是广告点击率预测和推荐系统中广泛使用的模型，但是到目前为止几乎没有一个高效的机器学习开源项目集这几种常用模型于一身，而且很多机器学习开源项目只能在特定计算平台下使用，最重要的是不能高效的整合到线上生产环境中。ytk-learn 就是解决以上问题而产生的。

 

 

　　​ytk-learn 是基于Java的高效分布式机器学习库，实现大量的主流传统机器学习模型(GBDT, LR, FM, FFM等)和loss函数，支持单机多线程、多机集群及分布式计算环境。

 

​　　其中 GBDT/GBRT 的实现借鉴吸收了 XGBoost 和 LightGBM 的大部分有用特性，支持特征并行和数据并行，支持传统的精确算法和直方图近似算法，支持 level-wise 或者 leaf-wise 的建树方式，而且还实现了分布式带权分位数近似。在单机数据并行的场景中训练速度跟 XGBoost 相当，在非$2^n$台机器的分布式场景中比 LightGBM 速度更快，更稳定。

 

​　　传统的 GBDT/GBRT 在含有大量 Categorical 特征的场景中无法使用，我们实现了多种适用于大量 Categorical特征的 GBST(Gradient Boosting Soft Tree)模型，在猿辅导的点击率预测和推荐场景中效果明显好于LR、FM、FFM等模型。

 

　　​ytk-learn 实现了改进的 Hoag(Hyperparameter optimization with approximate gradient， ICML2016)算法，能够自动高效的进行超参数搜索。当目标函数是凸函数时，hoag 能快速得到最优超参数(kaggle 比赛利器)，效率明显高于传统的网格超参数搜索算法(grid search)，而且在非凸目标函数场景中也适用。

 

　　其他特性：

1. 简单易用，文档详细，只需要用户安装Java 8运行时环境即可，而且所有模型都有可运行的demo

2. 支持主流的操作系统：Linux，Windows，Mac OS，仅需安装Java8运行环境即可使用

3. 支持单机多线程，多机集群及分布式环境(Hadoop，Spark)，相比Hadoop Mahout, Spark MLlib效率高很多

4. 提供简单易用的在线预测代码，可以方便整合到线上生成环境

5. 支持多种目标函数和评估指标，支持L1，L2，L1+L2正则

6. 树模型支持样本采样，特征采样，提供初始预估值的训练

7. 支持特征预处理(归一化，缩放)，特征哈希，特征过滤，基于样本标签采样

8. 提供了读取数据时进行高效数据处理的python脚本

9. 训练模型支持checkpoint，继续训练

10. LR 支持 Laplace 近似，方便做 Exploitation&Exploration

11. 基于猿辅导的 ytk-mp4j 通信库，分布式训练效率非常高

 

 

 

​　　目前可以用于分布式机器学习的通信主要基于MPI和RPC，其中MPI是分布式高性能计算的标配，虽然效率非常高，但是对于开发分布式机器学习任务来说有很多缺点: 开发难度大、数据支持太底层、只能用C/C++, Fortran编写等等；RPC 方式来实现类似 allreduce 这种操作，在特征维度特别高的场景，通信效率太低。所以我们开发了一套易用且高效的机器学习分布式通信库。

 

 

​　　ytk-mp4j 是基于Java的高效分布式机器学习通信库，实现了类似 MPI Collective 通信中的大部分操作，包含gather, scatter, allgather, reduce-scatter, broadcast, reduce, allreduce，使用 ytk-mp4j 可以快速地把串行机器学习程序改造成支持多线程和多进程，ytk-learn 中所有涉及到分布式通信操作都是基于 ytk-mp4j 实现(表1中给出了部分例子)。

 

　　相比于MPI, ytk-mp4j 扩展实现了一些非常实用的特性：

1. 所有的通信操作都是基于最优算法实现[1,2]，性能非常高，同时支持多线程，多进程。同样的功能，在C/C++ 环境中，可能需要结合 MPI 和 OpenMP 才能实现

2. 不仅支持基本的数据类型(double, float, long, int, short, byte)，而且还支持Java String及任意普通Java对象(Java 对象只需要实现 Kryo的 Serializer 接口)

3. 不仅支持传统数组类型的 Collective 通信，而且还支持Java Map数据类型，使用Map数据类型，用户可以实现非常复杂的通信操作(例如：集合求交、求并，链表的连接等操作)

4. 支持数据压缩传输，在网络资源很紧张的情况下，可以节约大量的带宽

5. 纯Java代码实现，可以无缝集成到 Hadoop, Spark 等分布式计算平台，构建自己的分布式机器学习系统

6. 使用 Java的SDP(Sockets Direct Protocol)可以实现高效的RDMA(Remote Direct Memory Access)

 

ytk-mp4j 操作	ytk-learn 中使用场景
allreduce	Loss 求和，梯度求和，Hessian 求和，计算分位数，计算平均值，   计算评估指标(AUC, Confusion Matrix…)，统计样本数量、 特征出现次数等等
reduce-scatter	GBDT 高效梯度求和
allgather	L-BFGS 中计算Hv，GBDT 同步梯度

 

　　allreduce 操作是分布式机器学习中使用最多的通信操作，它对机群中所有的节点对应的数据进行归约操作，然后再分发给各个节点。下面给出了 ytk-mp4j 在多进程、多进程、数组，Map 下的 allreduce (归约操作为求和)示意图：

 

　　​表2给出了 ytk-mp4j 实现的Collective操作时间复杂度，其中  是网络连接延迟,  是传输1个字节需要的时间, 是需要传输的字节数量,  是进行1字节数据归约(reduction)操作需要的时间。可以看出，随着机器数量的增加，所有操作数据传输的时间是几乎不会增加的，只有连接和归约操作的时间会随机器数量增加，但在大数据通信时，连接和归约的时间占比很小。这个时间复杂度特性非常重要，它使得在特征维度、样本数量超过一定阈值的分布式机器学习训练任务中，训练加速比与机器数量接近线性关系。

 

　　下图是测试在 1Gigabit Ethernet 网络下，10亿维 double 数组，各种 Collective 通信操作在不同的机器数量下的通信性能(时间单位: ms)，从图中可以看出 ytk-mp4j 中的7种 Collective 操作的通信时间与机器数量的关系与理论值完全符合。