陳天奇xgb論文
算法部分：
提升樹方面：
1.受正則貪心森林(RGF)的啟發(fā)在損失中引入了l2正則項和葉節(jié)點個數(shù)來控制模型的復(fù)雜度從而防止過擬合吏口。(RGF中的正則項會隨著節(jié)點變深而加大懲罰力度與xgb不同)其中xgb的正則項權(quán)重對應(yīng)參數(shù)中的lambda，節(jié)點數(shù)權(quán)重對應(yīng)gamma成艘。
2.xgb在損失優(yōu)化時的原理：通過對損失函數(shù)進行二階展開憋他，將以前的多次迭代結(jié)果和當(dāng)前樹區(qū)分開诗良，從而在一次迭代中只需優(yōu)化與當(dāng)前樹相關(guān)的損失部分嚷兔。并且將損失簡化為了二次函數(shù)，來簡化計算趾娃。每次構(gòu)建樹時，選取使損失減少最多的點作為分裂點缔御。
3.權(quán)值收縮和列采樣：權(quán)值收縮率可理解為學(xué)習(xí)時的步長抬闷，每生成一個樹就在樹的前面乘上一個收縮系數(shù)eta 列采樣：（在隨機森林中使用）是指在生成一棵樹進行節(jié)點分裂時選取隨機特征集合來進行分裂，最后得到的最優(yōu)分割點來自于該隨機特征集合耕突。
分裂查找算法：
1.精確貪心算法：遍歷每個特征以及特征中所有的分裂點笤成，從而精確的找出使loss減少最多的分裂點。O(n2)的復(fù)雜度（代碼中通過EnumerateSplit函數(shù)進行遍歷再利用ComputeSplitscore獲取評分）
2.近似分裂算法：利用分位點對原來對特征進行分桶眷茁，對分位點進行評估找出使loss減少最多的點炕泳。O(n)的復(fù)雜度。這種分法有兩種實現(xiàn)方式上祈，一種是global分割培遵，在開始時就把所有特征中的待選點分桶。另一種是loacl分割登刺，在每次進行分割時都要進行分桶籽腕。gloabl算法需要分出更多的侯選點，來保證精度塘砸，而local算法不用节仿。
3.加權(quán)分位圖：在對損失函數(shù)式進行變形之后發(fā)現(xiàn)，特征點關(guān)于損失函數(shù)的二階梯度的值可以被單獨提出來作為系數(shù)掉蔬，（我目前的理解是這樣可以看作增益以hi為單位進行增長所以用hi作為權(quán)重）廊宪。
4.稀疏感知分裂查找：由于應(yīng)用中的特征有比較強的稀疏性，對于那些缺省值女轿。在進行分裂時直接將為缺省值的點單獨拿出來箭启，最后統(tǒng)一分在一邊，這樣就不再對缺省點進行遍歷分裂從而提高了算法的效率蛉迹，具體是放在左分支還是右分支要計算增益來決定傅寡。
系統(tǒng)設(shè)計部分：
1.可并行學(xué)習(xí)的特征塊：在進行訓(xùn)練之前先將特征值排序并存儲在block中，以減少排序的耗時北救。在尋找分裂點時在不同的block中對不同的特征進行并行計算荐操。對于貪婪分裂法，一個block就對應(yīng)一個特征中的所有數(shù)據(jù)珍策。對于分布式計算托启，可將某列數(shù)據(jù)分成多個塊分別存儲在不同的地方，并且可以通過不同的機器對某列進行線性掃描攘宙。
2.緩存感知訪問：由于需要對特征所對應(yīng)的梯度值進行順序訪問屯耸，但是梯度是按照example的index存儲的，因而不是連續(xù)的內(nèi)存訪問這樣會導(dǎo)致緩存的命中率低從而降速蹭劈。在精確貪婪分割中xgboost中采用了預(yù)取的方式疗绣，在每個線程中設(shè)置了緩沖，小批量地把相應(yīng)的梯度數(shù)據(jù)放在緩沖當(dāng)中這樣就把不連續(xù)的數(shù)據(jù)變成了連續(xù)數(shù)據(jù)（這部分的實現(xiàn)在分裂查找的代碼中有體現(xiàn)）铺韧。在近似分裂方法中通過選取合適的block size從而找到存取和運行效率之間的平衡多矮。
3.塊的核外計算：在數(shù)據(jù)量大的情況下，需要在運算的同時對磁盤數(shù)據(jù)進行讀取哈打，為了加快讀取速度采用了壓縮算法對數(shù)據(jù)進行壓縮工窍，在讀取時用專門對線程進行解壓。另一種方式是用多個磁盤進行數(shù)據(jù)預(yù)取前酿，并將他們存入內(nèi)存中對緩沖區(qū)患雏。