而且通常在單機(jī)上測(cè)的話比決策樹(shù)速度要快兩個(gè)數(shù)量級(jí)以上，通常跑的更精準(zhǔn)，而且更不容易o(hù)ver fitting，算是比較好的base line算法。但是也有一個(gè)問(wèn)題，因?yàn)闃?shù)結(jié)構(gòu)的算法，并行化是比較困難，單機(jī)上比較好實(shí)現(xiàn)。怎么在構(gòu)建的過(guò)程中同步樹(shù)的狀態(tài)，其實(shí)是非常麻煩的事情。
我們后來(lái)基于對(duì)隨機(jī)決策樹(shù)理論的研究，發(fā)現(xiàn)其實(shí)隨機(jī)決策樹(shù)起作用的不是因?yàn)橛昧藳Q策樹(shù)這個(gè)結(jié)構(gòu)。其實(shí)隨機(jī)決策樹(shù)起到的作用，僅僅是把數(shù)據(jù)隨機(jī)打散，每一個(gè)數(shù)據(jù)是不同的打散方式。我們想著用局部敏感哈希來(lái)代替樹(shù)的功能，就提出了隨機(jī)決策哈希的算法。這個(gè)文章發(fā)表在了2015年KDD的Bigmine Workshop上面。我們看看這兩個(gè)算法的精度跟傳統(tǒng)的算法的精度，后面三個(gè)分別是決策樹(shù)， SVM和Logistc Regression我們可以看到精度上面，這兩個(gè)都有比較大的優(yōu)勢(shì)。而且和傳統(tǒng)的算法相比，運(yùn)算時(shí)間也是有很大的優(yōu)勢(shì)。
我們嘗試過(guò)把隨機(jī)決策樹(shù)做并行化，但是發(fā)現(xiàn)只有在一種情況下可以做到比較好的并行。所有的數(shù)據(jù)的功能全部是二值的，這種情況下建空樹(shù)，所有的空樹(shù)要建成滿二叉樹(shù)的狀態(tài)，可以用寬度優(yōu)先的編碼方式，可以把每個(gè)節(jié)點(diǎn)編碼起來(lái)。中間的左右值節(jié)點(diǎn)有一個(gè)關(guān)系，可以通過(guò)運(yùn)算方式去回溯，這樣就使樹(shù)在實(shí)際應(yīng)用中不需要建立實(shí)體樹(shù)。在實(shí)際運(yùn)用過(guò)程中，運(yùn)用了一些哈希，在不建實(shí)體樹(shù)的情況下來(lái)保證隨機(jī)決策樹(shù)的算法，有一個(gè)小動(dòng)畫來(lái)解釋基本原理。
RDH的算法是非常好并行的，也不用去考慮太多其他因素。但是我們?yōu)榱诉M(jìn)一步提高速度，因?yàn)槲覀冏隽司植棵舾泄?，很多中間的過(guò)程就變成了binary的向量，可以用Bitmap表達(dá)，用Bitmap引擎來(lái)加速算法的運(yùn)算過(guò)程。我們測(cè)過(guò)在4到5億的數(shù)據(jù)集上，可以做到100秒以內(nèi)，在Spark上并行100秒以內(nèi)的訓(xùn)練過(guò)程，而且還包括了Spark本身的調(diào)度時(shí)間。
前面的方法都是非參數(shù)的方法，非參數(shù)的方法有很多的問(wèn)題，一是模型建出來(lái)會(huì)比較大，應(yīng)用起來(lái)沒(méi)有那么方便。二是可解釋性相對(duì)差一點(diǎn)，在很多實(shí)際應(yīng)用中，我們還是希望使用更簡(jiǎn)潔的參數(shù)模型，比如說(shuō)像Logistic Regression等算法。要求解這種方法，基本的方法是梯度下降，大規(guī)模的問(wèn)題用隨機(jī)梯度下降更多。我在這里簡(jiǎn)單列了一下Batch的梯度下降和隨機(jī)梯度下降的區(qū)別。隨機(jī)梯度下降最大的好處是把計(jì)算量降下來(lái)了：原來(lái)做批量隨機(jī)梯度下降的話，計(jì)算量跟數(shù)據(jù)量是呈幾次方的關(guān)系，但是在隨機(jī)梯度下面基本上呈線性關(guān)系。但是隨機(jī)梯度下降還是要進(jìn)行數(shù)據(jù)的多輪迭代，因?yàn)槊看沃贿^(guò)一個(gè)數(shù)據(jù)，過(guò)數(shù)據(jù)的次數(shù)就要更多一些。
另外，在實(shí)際應(yīng)用中，梯度下降方法的參數(shù)都比較難調(diào)，比如對(duì)于學(xué)習(xí)率的設(shè)置，對(duì)于不同問(wèn)題、不同數(shù)據(jù)是非常敏感的。如果再考慮到正則化系數(shù)，調(diào)參就變得更加復(fù)雜。
我們對(duì)SGD方法也做了很多的優(yōu)化，一是我們現(xiàn)在做到了可以無(wú)參數(shù)一次迭代收斂。主要原理是利用每一步的梯度信息，進(jìn)行動(dòng)態(tài)學(xué)習(xí)率改變，讓模型快速收斂。這個(gè)工作還有一些理論上的小問(wèn)題沒(méi)有完全解決，所以還沒(méi)有公布出來(lái)。隨著我們機(jī)器學(xué)習(xí)項(xiàng)目的開(kāi)源，我們也會(huì)把這個(gè)研究結(jié)果，包括算法和理論上的成果公布出來(lái)。
在大規(guī)模學(xué)習(xí)上要做稀疏正則化也是比較大的難題，我們這邊采用了一些比較實(shí)用的方法，根據(jù)內(nèi)存的容量動(dòng)態(tài)計(jì)算可以保存高維度的模型。這樣就使得在做稀疏正則化的時(shí)候不需要調(diào)參數(shù)，盡可能保證豐滿的模型，同時(shí)保證要高效地把模型訓(xùn)練出來(lái)。
在機(jī)器學(xué)習(xí)算法并行化方面，有三種可以考慮的方法：梯度平均，模型平均，還有結(jié)果平均。結(jié)果平均就是Ensemble，這里不討論。對(duì)于梯度平均而言是Spark Mllib，包括很多基于Parameter Server，用每一個(gè)數(shù)據(jù)或者每一個(gè)小批量的數(shù)據(jù)去產(chǎn)生一個(gè)對(duì)模型系數(shù)的更新量，然后把更新量匯集起來(lái)統(tǒng)一對(duì)模型進(jìn)行更新，然后再把模型發(fā)送到所有節(jié)點(diǎn)，這是一個(gè)梯度平均的過(guò)程。另外一種方法更簡(jiǎn)單一點(diǎn)，就是在每個(gè)數(shù)據(jù)分片上跑自己的模型，把所有數(shù)據(jù)分片的模型做平均。我們看過(guò)一些文獻(xiàn)，從理論上來(lái)說(shuō)梯度平均的收斂性、理論保證會(huì)比模型平均更好一點(diǎn)。但是我們?cè)趯?shí)際中做了大量的測(cè)試，至少現(xiàn)在我們的方法跟MLlib對(duì)比有壓倒性的優(yōu)勢(shì)。