上一講：機器學習面試題精講（一）

4. GBDT

GBDT（Gradient Boosting Decision Tree）又叫 MART（Multiple Additive Regression Tree）。是一種迭代的決策樹演算法。

4.1 DT：回歸樹 Regression Decision Tree

GDBT 中的樹全部都是回歸樹，核心就是累加所有樹的結果作為最終結果。只有回歸樹的結果累加起來纔是有意義的，分類的結果加是沒有意義的。

GDBT 調整之後可以用於分類問題，但是內部還是回歸樹。

這部分和決策樹中的是一樣的，無非就是特徵選擇。回歸樹用的是最小化均方誤差，分類樹是用的是最小化基尼指數（CART）

4.2 GB：梯度迭代 Gradient Boosting

首先 Boosting 是一種集成方法。通過對弱分類器的組合得到強分類器，他是串列的，幾個弱分類器之間是依次訓練的。GBDT 的核心就在於，每一顆樹學習的是之前所有樹結論和的殘差。

Gradient 體現在：無論前面一顆樹的 cost function 是什麼，是均方差還是均差，只要它以誤差作為衡量標準，那麼殘差向量都是它的全局最優方向，這就是 Gradient。

4.3 Shrinkage

Shrinkage（縮減）是 GBDT 演算法的一個重要演進分支，目前大部分的源碼都是基於這個版本的。

核心思想在於：Shrinkage 認為每次走一小步來逼近結果的效果，要比每次邁一大步很快逼近結果的方式更容易防止過擬合。

也就是說，它不信任每次學習到的殘差，它認為每棵樹只學習到了真理的一小部分，累加的時候只累加一小部分，通過多學習幾棵樹來彌補不足。

具體的做法就是：仍然以殘差作為學習目標，但是對於殘差學習出來的結果，只累加一小部分（step* 殘差）逐步逼近目標，step 一般都比較小 0.01-0.001, 導致各個樹的殘差是漸變而不是陡變的。

本質上，Shrinkage 為每一顆樹設置了一個 weight，累加時要乘以這個 weight，但和 Gradient 沒有關係。

這個 weight 就是 step。跟 AdaBoost 一樣，Shrinkage 能減少過擬合也是經驗證明的，目前還沒有理論證明。

4.4 GBDT 適用範圍

• GBDT 可以適用於回歸問題（線性和非線性），相對於 logistic regression 僅能用於線性回歸，GBDT 適用面更廣；
• GBDT 也可用於二分類問題（設定閾值，大於為正，否則為負）和多分類問題。

4.5 GBDT 和隨機森林

相同點：

• 都是由多棵樹組成；
• 最終的結果都由多棵樹共同決定。

不同點：

• 組成隨機森林的可以是分類樹、回歸樹；組成 GBDT 只能是回歸樹；
• 組成隨機森林的樹可以並行生成（Bagging）；GBDT 只能串列生成（Boosting）；
• 對於最終的輸出結果而言，隨機森林使用多數投票或者簡單平均；而 GBDT 則是將所有結果累加起來，或者加權累加起來；
• 隨機森林對異常值不敏感，GBDT 對異常值非常敏感；
• 隨機森林對訓練集一視同仁權值一樣，GBDT 是基於權值的弱分類器的集成；
• 隨機森林通過減小模型的方差提高性能，GBDT 通過減少模型偏差提高性能。

TIPs：

1. GBDT 相比於決策樹有什麼優點

泛化性能更好！GBDT 的最大好處在於，每一步的殘差計算其實變相的增大了分錯樣本的權重，而已經分對的樣本則都趨向於 0。這樣後面就更加專註於那些分錯的樣本。

2. Gradient 體現在哪裡？

可以理解為殘差是全局最優的絕對方向，類似於求梯度。

3. re-sample

GBDT 也可以在使用殘差的同時引入 Bootstrap re-sampling，GBDT 多數實現版本中引入了這個選項，但是是否一定使用有不同的看法。

原因在於 re-sample 導致的隨機性，使得模型不可復現，對於評估提出一定的挑戰，比如很難確定性能的提升是由於 feature 的原因還是 sample 的隨機因素。

5. Logistic 回歸

5.1 LR 模型原理

首先必須給出 Logistic 分佈：

u 是位置參數，r 是形狀參數。對稱點是 (u,1/2)，r 越小，函數在 u 附近越陡峭。

然後，二分類 LR 模型，是參數化的 logistic 分佈，使用條件概率來表示：

然後，一個事件的幾率（odds）：指該事件發生與不發生的概率比值：

對數幾率：

那麼對於邏輯回歸而言，Y=1 的對數幾率就是：

最終，輸出 Y=1 的對數幾率是輸入 x 的線性函數表示的模型，這就是邏輯回歸模型。

5.2 參數估計

在統計學中，常常使用極大似然估計法來估計參數。即找到一組參數，使得在這組參數下，我們數據的似然度（概率）最大。

似然函數：

對數似然函數：

對應的損失函數：

5.3 最優化方法

邏輯回歸模型的參數估計中，最後就是對 J(W) 求最小值。這種不帶約束條件的最優化問題，常用梯度下降或牛頓法來解決。

使用梯度下降法求解邏輯回歸參數估計

求 J(W) 梯度：g(w):

更新 Wk：

$$W_{k+1} = W_k - lambda*g(W_k)$$

5.4 正則化

正則化為瞭解決過擬合問題。分為 L1 和 L2 正則化。主要通過修正損失函數，加入模型複雜性評估；

正則化是符合奧卡姆剃刀原理：在所有可能的模型中，能夠很好的解釋已知數據並且十分簡單的纔是最好的模型。

p 表示範數，p=1 和 p=2 分別應用 L1 和 L2 正則。

L1 正則化。向量中各元素絕對值之和。又叫做稀疏規則運算元（Lasso regularization）。關鍵在於能夠實現特徵的自動選擇，參數稀疏可以避免非必要的特徵引入的雜訊；

L2 正則化。使得每個元素都儘可能的小，但是都不為零。在回歸裡面，有人把他的回歸叫做嶺回歸（Ridge Regression），也有人叫他 「權值衰減」（weight decay）。

一句話總結就是：L1 會趨向於產生少量的特徵，而其他的特徵都是 0，而 L2 會選擇更多的特徵，這些特徵都會接近於 0.

5.5 邏輯回歸 vs 線性回歸

首先，邏輯回歸比線性回歸要好。

兩者都屬於廣義線性模型。

線性回歸優化目標函數用的最小二乘法，而邏輯回歸用的是最大似然估計。邏輯回歸只是在線性回歸的基礎上，將加權和通過 sigmoid 函數，映射到 0-1 範圍內空間。

線性回歸在整個實數範圍內進行預測，敏感度一致，而分類範圍，需要在 [0,1]。而邏輯回歸就是一種減小預測範圍，將預測值限定為 [0,1] 間的一種回歸模型。

邏輯曲線在 z=0 時，十分敏感，在 z>>0 或 z<<0 處，都不敏感，將預測值限定為 (0,1)。邏輯回歸的魯棒性比線性回歸要好。

5.6 邏輯回歸模型 vs 最大熵模型 MaxEnt

簡單粗暴的說：邏輯回歸跟最大熵模型沒有本質區別。邏輯回歸是最大熵對應為二類時的特殊情況，也就是說，當邏輯回歸擴展為多類別的時候，就是最大熵模型。

最大熵原理：學習概率模型的時候，在所有可能的概率模型（分佈）中，熵最大的模型是最好的模型。

6. SVM 支持向量機

註：面試中只要問到 SVM，最基本也是最難的問題就是：SVM 的對偶問題數學公式推導。

所以想學好機器學習，還是要塌下心來，不僅僅要把原理的核心思想掌握了，公式推導也要好好學習才行。

6.1 SVM 原理

簡單粗暴的說：SVM 的思路就是找到一個超平面將數據集進行正確的分類。對於在現有維度不可分的數據，利用核函數映射到高緯空間使其線性可分。

支持向量機 SVM 是一種二分類模型。它的基本模型是定義在特徵空間上的間隔最大的線性分類器，間隔最大使它有別於感知機。SVM 的學習策略是間隔最大化，可形式化為求解凸二次規劃問題。

SVM 分為：

• 線性可分支持向量機。當訓練數據線性可分時，通過硬間隔最大化，學習到的一個線性分類器；
• 線性支持向量機。當訓練數據近似線性可分時，通過軟間隔最大化，學習到的一個線性分類器；
• 非線性支持向量機。當訓練數據線性不可分，通過使用核技巧及軟間隔最大化，學習非線性支持向量機。

上圖中，X 表示負例，O 表示正例。此時的訓練數據可分，線性可分支持向量機對應著將兩類數據正確劃分並且間隔最大的直線。

6.1.1 支持向量與間隔

支持向量：在線性可分的情況下，訓練數據樣本集中的樣本點中與分離超平面距離最近的樣本點的實例稱為支持向量（support vector）。

函數間隔定義如下：

yi 表示目標值，取值為 +1、-1. 函數間隔雖然可以表示分類預測的準確性以及確信度。但是有個不好的性質：只要成倍的改變 W 和 B，雖然此時的超平面並沒有改變，但是函數間隔會變大。

所以我們想到了對超平面的法向量 W 施加一些約束，比如規範化，使得間隔確定，這就引出了幾何間隔：

支持向量學習的基本思想就是求解能夠正確劃分訓練數據集並且幾何間隔最大的分類超平面。

6.1.2 對偶問題

為了求解線性可分支持向量機的最優化問題：

將它作為原始最優化問題，應用拉格朗日對偶性，通過求解對偶問題得到原始問題的最優解，這就是線性可分支持向量機的對偶演算法。

本來的演算法也可以求解 SVM，但是之所以要用對偶問題來求解，優點是：

• 一是對偶問題往往更容易求解；
• 二是自然引入核函數，進而推廣到非線性分類問題。

說點題外話，這也是面試中會被問到的一個問題：原始問題既然可以求解，為什麼還要轉換為對偶問題。

答案就是上述這兩點。由於篇幅的願意，此處就不在展開數學公式的推導了，大家可以參考《機器學習》與《統計學習方法》。

6.1.3 核函數

對於在原始空間中不可分的問題，在高維空間中是線性可分的。

對於線性不可分的問題，使用核函數可以從原始空間映射到高緯空間，使得問題變得線性可分。核函數還可以使得在高維空間計算的內積在低維空間中通過一個函數來完成。

常用的核函數有：高斯核、線性核、多項式核。

6.1.4 軟間隔

線性可分問題的支持向量機學習方法，對現行不可分訓練數據是不適用的。所以講間隔函數修改為軟間隔，對於函數間隔，在其上加上一個鬆弛變數，使其滿足大於等於 1。約束條件變為：

6.2 優缺點

缺點：

• 時空開銷比較大，訓練時間長；
• 核函數的選取比較難，主要靠經驗。

優點：

• 在小訓練集上往往得到比較好的結果；
• 使用核函數避開了高緯空間的複雜性；
• 泛化能力強。

7. 利用 sklearn 進行實戰

使用 sklearn 用決策樹來進行鶯尾花數據集的劃分問題。代碼上沒有固定隨機種子，所以每次運行的結果會稍有不同。

數據集三維可視化：

在 Sepal length 和 Sepal width 二維上的可視化：

運行結果：

Decision Tree 可視化，也就是生成的決策樹：

推薦閱讀：