梯度提升技術

梯度提升，亦稱作梯度增強，是一種用於迴歸和分類問題的機器學習技術。其產生的預測模型是弱預測模型的整合，如採用典型的決策樹作為弱預測模型，這時則為梯度提升樹。像其他提升方法一樣，它以分階段的方式構建模型，但它透過允許對任意可微分損失函式進行最佳化作為對一般提升方法的推廣。梯度提升技術源自於於1997年時將提升方法用於最佳化演算法的觀察。隨後於1999年時提出了顯式迴歸梯度增強演算法。Llew Mason、Jonathan Baxter、Peter Bartlett和Marcus Frean則針對梯度提升在一般的函式空間的運用進行研究，並於1999年在研討會發表之後，同年正式發表了論文。該論文介紹了將提升演算法看作“函式空間上的梯度下降迭代”演算法的觀點。也就是將其視為透過迭代地選擇指向負梯度方向的函式，來最佳化函式空間上的成本函式的演算法。這種將提升視為函式梯度的觀點，導致了提升演算法被運用於迴歸和分類之外的其他機器學習和統計領域的後續發展。非正式介紹.與其他增強方法一樣，梯度增強以迭代方式將弱的“學習器”組合為一個強學習器。最簡單的解釋是在最小二乘迴歸中，透過最小化均方誤差 formula_1 ，“教”模型formula_2預測實數值formula_3。在梯度提升的每個階段 formula_4, formula_5, 假設已經有一個不太完美的模型 formula_6 (最開始時只是一個預測輸出變數 h 可以完美預測當前不完美模型formula_6的殘差，即滿足，formula_11或者，等效地有，formula_12.因此，梯度提升透過擬合殘差 formula_13得到 h 。和其他提升方法的變體一樣, formula_14 透過糾正 formula_6的誤差變得更完美。 這個想法可以擴充套件到均方誤差損失之外的任意損失函式，甚至擴充套件到分類與排序問題，只要觀察到以下一點：模型的殘差 formula_13就是均方損失函式formula_17關於formula_18的負梯度。因此，梯度提升其實是一種 梯度下降演算法，可以代入除了均方損失之外的不同的損失函式，得到不同的梯度。演算法.在許多有監督學習問題中，一個輸出變數x透過聯合機率分佈formula_19描述 。給定訓練集formula_20，目的是在所有具有給定形式的函式formula_18中找到一個formula_22使某些指定損失函式formula_23的期望值達到最小：formula_24.梯度提升方法透過某一類formula_25中弱學習器formula_26帶權重和的形式來表示對實值變數y做出估計的formula_22:formula_28.根據經驗風險最小化原理，該方法試圖找到一個近似formula_22可以最大程度地減少訓練集上損失函式的平均值，即，最小化經驗風險。它是從一個由常數函式組成的模型formula_30開始 ，並以貪心的方式逐步擴充套件：formula_31,formula_32,上式formula_33是基學習器。不幸的是，通常在每個步驟中為任意損失函式h是計算上不可行的最佳化問題。因此，我們將方法侷限於問題的簡化版本。這個想法是對這個最小化問題應用梯度下降步驟。如果我們考慮連續情況，即formula_34是上的任意微分函式的集合formula_35 ，我們將根據以下方程式更新模型formula_36formula_37式子中，對於formula_38是關於函式formula_39求導，formula_40是步長。 但是在離散情況下，即formula_25如果是有限的，我們選擇最接近γ。請注意，這種方法是一種啟發式方法，因此不能給出給定問題的精確解決方案，而是一種近似方法。 在虛擬碼中，通用梯度增強方法是：Input: training set formula_42 a differentiable loss function formula_43 number of iterations M.Algorithm:梯度樹增強.梯度提升通常與固定大小的決策樹 一起用作基礎學習者。 對於這種特殊情況，Friedman提出了對梯度增強方法的改進，以提高每個基礎學習者的適應質量。第m步的通用梯度提升將適合決策樹formula_46偽殘留物。 讓formula_53是它的葉子數。 樹將輸入空間劃分為formula_53不相交的區域formula_55並預測每個區域的恆定值。 使用指標符號 ，輸出formula_46輸入x可以寫為和：formula_57這裡formula_58是該區域中預測的值formula_59。然後係數formula_58乘以一些值formula_40 ，使用線搜尋進行選擇，以最大程度地減少損失函式，並按以下方式更新模型：formula_62弗裡德曼建議修改此演算法，以便選擇一個單獨的最佳值formula_63每個樹的區域，而不是單個formula_40為整棵樹。 他稱修改後的演算法為“ TreeBoost”。 係數formula_58然後可以簡單地丟棄樹擬合過程中的資料，模型更新規則變為：formula_66樹木大小.formula_67 ，不允許變數之間進行互動。 用formula_69該模型可能包括多達兩個變數之間的相互作用的影響，依此類推。Hastie等人評論通常formula_70對於提升效果很好，結果對選擇formula_67在這個範圍內formula_68不足以用於許多應用程式，並且formula_73不太可能是必需的。正則化.過於緊密地擬合訓練集可能導致模型的泛化能力下降。 幾種所謂的正則化技術透過限制擬合過程來減少這種過度擬合的效果。一個自然的正則化引數是梯度提升迭代的次數M。M的增加會減少訓練集上的誤差，但將其設定得過高可能會導致過度擬合。 通常透過監視單獨的驗證資料集上的預測誤差來選擇M的最佳值。 除了控制M外，還使用其他幾種正則化技術。另一個正則化引數是樹的深度。 該值越高，模型越可能適合訓練資料。收縮率.梯度增強方法的一個重要部分是透過收縮排行正則化，它包括如下修改更新規則：formula_74哪裡引數 formula_75被稱為“學習率”。根據經驗發現，使用較小的學習率 。然而，這是以在訓練和查詢期間增加計算時間為代價的：較低的學習率需要更多的迭代。隨機梯度增強.引入梯度增強後不久，Friedman在Breiman的bootstrap聚合 觀察到，透過這種修改，梯度增強的精度有了顯著提高。子樣本大小是某個常數formula_78訓練集的大小。 什麼時候formula_79 ，該演算法是確定性的，並且與上述演算法相同。 較小的值formula_78將隨機性引入演算法中，並防止過度擬合 ，作為一種正則化 。 該演算法也變得更快，因為迴歸樹必須在每次迭代時都適合較小的資料集。弗裡德曼獲得了formula_81在中小型訓練集上可獲得良好的結果。 因此， formula_78通常將其設定為0.5，這意味著訓練集的一半用於構建每個基礎學習者。同樣，像在裝袋中一樣，子取樣允許透過評估那些在下一個基礎學習者的構建中未使用的觀察值的預測來定義預測效能改進的袋外誤差 。 預算外的估計有助於避免需要獨立的驗證資料集，但通常會低估實際效能的提高和最佳迭代次數。葉子中的觀察數.梯度樹增強實現通常還透過限制樹的終端節點中的最小觀察次數來使用正則化。透過忽略導致導致節點包含少於此訓練集例項數量的節點的任何拆分，在樹構建過程中使用它。施加此限制有助於減少葉子預測的差異。懲罰樹木的複雜性.用於梯度增強樹的另一種有用的正則化技術是懲罰學習模型的模型複雜性。 模型複雜度可以定義為學習樹中葉子的比例。 損失和模型複雜性的聯合最佳化對應於後修剪演算法，該演算法可刪除未能將損失降低閾值的分支。 其他種類的正規化，例如formula_83還可以新增對葉子值的懲罰以避免過度擬合 。用法.梯度提升可以用於學習排名 。 商業網路搜尋引擎Yahoo 和Yandex 在其機器學習的排名引擎中使用了梯度增強的變體。名字.該方法有多種名稱。弗裡德曼。R的一種流行的開源實現將其稱為“通用提升模型”。但是，使用BRT擴充套件這項工作的軟體包。 Salford Systems的商業實現使用名稱“ Multiple Additive Regression Trees”和TreeNet，兩者均為商標。