| Machine Learning is one of the key technologies in IT Applications and manyother fields in all walks of life, among machine learning algorithms, linear regressionhas good performances on many simple regression and classification problem.However, in practice there is always not a simple linear relationship betweendependent and independent variables. Learning a nonlinear function by using anadditive model over nonlinear decision rules has been widely used and proved to beone of the most effective methods, such as gradient boosting decision tree (GBDT).Regularized greedy forest (RGF) is one of the best variants of GBDT, whichwere awarded with First Place Prize in a number of well-known competitions inKaggle. Unlike GBDT which simply treats the decision tree base learner as a blackbox and may have the problem of overfitting, RGF directly learns a decision forest viafully-corrective regularized greedy search:(1) RGF perform structured greedy searchdirectly over forest nodes taking advantage of the underlying forest structure;(2) RGFrepeatedly re-optimizes the coefficients of all the decision rules obtained so far;(3)RGF define regularizers that take advantage of individual tree structures. Throughthese improvements, RGF achieve better performances both on the predictionaccuracy and training time. However, it still takes a long time for RGF while doingthe training work of massive dataset, the use of parallel computing can efficientlysolve the problem.RGF mainly consumed time in the processing of greedy search and constructionof the decision forest, aiming at the structure of the RGF algorithm, this thesis proposes a parallel implementation based on Message Passing Interface (MPI) withgood scalability, which effectively integrate the computing ability of multiplecomputer nodes and do parallelization in three levels: Firstly, according to thecomplexity of each tree, we dynamically assign tasks of greedy search on multipletrees to parallel computing nodes and respectively get the optimal split, then weintegrate the results of all trees and get the global best split. Secondly, in theconstruction process of the decision forest, we grow multiple trees simultaneouslyusing parallel nodes. Thirdly, based on the number of parallel nodes and leaf nodes ofeach tree, search on different nodes of one tree are scheduled to parallel nodes. Lastly,in the process of the finding the best split for tree node, we divide the feature list todifferent processors for computing information gain.In this paper, we compare the experiment results of the original algorithm andour modified algorithm on different scale of datasets, it shows that the modifiedalgorithm reduces the training time significantly while guarantees the accuracy of theprediction model. Under the condition of10parallel cores, time consumption onlarger-scale dataset’s training can be reduced from10to15times. The parallelalgorithm in this paper can easily be extended, if there is more available computingresources, improvement on the speed will definitely be more apparent. |
