而且通常在单机上测的话比决策树速度要快两个数量级以上，通常跑的更精准，而且更不容易over fitting，算是比较好的base line算法。但是也有一个问题，因为树结构的算法，并行化是比较困难，单机上比较好实现。怎么在构建的过程中同步树的状态，其实是非常麻烦的事情。
我们后来基于对随机决策树理论的研究，发现其实随机决策树起作用的不是因为用了决策树这个结构。其实随机决策树起到的作用，仅仅是把数据随机打散，每一个数据是不同的打散方式。我们想着用局部敏感哈希来代替树的功能，就提出了随机决策哈希的算法。这个文章发表在了2015年KDD的Bigmine Workshop上面。我们看看这两个算法的精度跟传统的算法的精度，后面三个分别是决策树， SVM和Logistc Regression我们可以看到精度上面，这两个都有比较大的优势。而且和传统的算法相比，运算时间也是有很大的优势。
我们尝试过把随机决策树做并行化，但是发现只有在一种情况下可以做到比较好的并行。所有的数据的功能全部是二值的，这种情况下建空树，所有的空树要建成满二叉树的状态，可以用宽度优先的编码方式，可以把每个节点编码起来。中间的左右值节点有一个关系，可以通过运算方式去回溯，这样就使树在实际应用中不需要建立实体树。在实际运用过程中，运用了一些哈希，在不建实体树的情况下来保证随机决策树的算法，有一个小动画来解释基本原理。
RDH的算法是非常好并行的，也不用去考虑太多其他因素。但是我们为了进一步提高速度，因为我们做了局部敏感哈希，很多中间的过程就变成了binary的向量，可以用Bitmap表达，用Bitmap引擎来加速算法的运算过程。我们测过在4到5亿的数据集上，可以做到100秒以内，在Spark上并行100秒以内的训练过程，而且还包括了Spark本身的调度时间。
前面的方法都是非参数的方法，非参数的方法有很多的问题，一是模型建出来会比较大，应用起来没有那么方便。二是可解释性相对差一点，在很多实际应用中，我们还是希望使用更简洁的参数模型，比如说像Logistic Regression等算法。要求解这种方法，基本的方法是梯度下降，大规模的问题用随机梯度下降更多。我在这里简单列了一下Batch的梯度下降和随机梯度下降的区别。随机梯度下降最大的好处是把计算量降下来了：原来做批量随机梯度下降的话，计算量跟数据量是呈几次方的关系，但是在随机梯度下面基本上呈线性关系。但是随机梯度下降还是要进行数据的多轮迭代，因为每次只过一个数据，过数据的次数就要更多一些。
另外，在实际应用中，梯度下降方法的参数都比较难调，比如对于学习率的设置，对于不同问题、不同数据是非常敏感的。如果再考虑到正则化系数，调参就变得更加复杂。
我们对SGD方法也做了很多的优化，一是我们现在做到了可以无参数一次迭代收敛。主要原理是利用每一步的梯度信息，进行动态学习率改变，让模型快速收敛。这个工作还有一些理论上的小问题没有完全解决，所以还没有公布出来。随着我们机器学习项目的开源，我们也会把这个研究结果，包括算法和理论上的成果公布出来。
在大规模学习上要做稀疏正则化也是比较大的难题，我们这边采用了一些比较实用的方法，根据内存的容量动态计算可以保存高维度的模型。这样就使得在做稀疏正则化的时候不需要调参数，尽可能保证丰满的模型，同时保证要高效地把模型训练出来。
在机器学习算法并行化方面，有三种可以考虑的方法：梯度平均，模型平均，还有结果平均。结果平均就是Ensemble，这里不讨论。对于梯度平均而言是Spark Mllib，包括很多基于Parameter Server，用每一个数据或者每一个小批量的数据去产生一个对模型系数的更新量，然后把更新量汇集起来统一对模型进行更新，然后再把模型发送到所有节点，这是一个梯度平均的过程。另外一种方法更简单一点，就是在每个数据分片上跑自己的模型，把所有数据分片的模型做平均。我们看过一些文献，从理论上来说梯度平均的收敛性、理论保证会比模型平均更好一点。但是我们在实际中做了大量的测试，至少现在我们的方法跟MLlib对比有压倒性的优势。