以西瓜書為主線，以其他書籍作為參考進(jìn)行補(bǔ)充，例如《統(tǒng)計學(xué)習(xí)方法》，《PRML》等

第一章 緒論

1.2 基本術(shù)語

• 所有的可能的模型組合成為一個假設(shè)空間 H

• 預(yù)測分為兩類任務(wù)：

  • 分類任務(wù)： 預(yù)測的結(jié)果是離散值
    • 二分類任務(wù)，其中標(biāo)簽為(0/1 或者 +1/-1 代表 正例/負(fù)例)
    • 多分類任務(wù)，類別數(shù)目 k > 2
  • 回歸任務(wù)： 預(yù)測的結(jié)果是連續(xù)值

• 同時另一種任務(wù)是 聚類：事先不知道數(shù)據(jù)的規(guī)律，同時沒有標(biāo)簽，屬于無監(jiān)督學(xué)習(xí)

• 建立模型/學(xué)習(xí) 的目的

  • 找到一個從輸入空間 X -> 輸出 Y的函數(shù)映射
  • 使得學(xué)習(xí)到的模型能夠很好的擬合“新數(shù)據(jù)”，即具有很好的泛化能力

• 通常假設(shè)樣本數(shù)據(jù)服從獨立同分布（i.i.d），而服從的分布是未知的，我們需要做的就是找出這個分布規(guī)律

• 歸納偏好 可以理解為對不同特征的重視程度

• 任何一個有效的機(jī)器學(xué)習(xí)算法必有相應(yīng)的歸納偏好，因為能夠擬合有限數(shù)據(jù)的曲線并不唯一，因此需要設(shè)定歸納偏好，使得泛化能力得到保證

• 通常使用 奧卡姆剃刀 原則作為一般性的歸納偏好原則，但是很遺憾原則中 “簡單” 的含義針對不同的模型并不唯一，需要借助其他機(jī)制才能完成判斷

• NFL (No Free Lunch Theorem) 指出，必須結(jié)合具體的學(xué)習(xí)問題去討論算法的優(yōu)劣性

• 需要注意學(xué)習(xí)算法自身的偏好與問題是否匹配，不同的數(shù)據(jù)集有不同的“特點”，需要不同的“偏好”去擬合具體的數(shù)據(jù)集

第二章 模型評估與選擇

2.1 經(jīng)驗誤差與過擬合

• 誤差分為兩類：

  • 經(jīng)驗誤差： 數(shù)據(jù)集上的誤差
  • 泛化誤差： 新樣本上的誤差

• 過擬合的理解：

  • 學(xué)習(xí)到了數(shù)據(jù)集中不夠 general 的特性
  • 把訓(xùn)練集自身的某些特性當(dāng)做整體的特性
  • 過擬合是無法避免的

2.2 評估方法

• 模型選擇中存在兩個問題：
  • 泛化誤差我們無從知曉
  • 訓(xùn)練誤差不靠譜(存在過擬合的情況）

因此提出不同的評估方法

• 需要一個 “測試集” ，通過 “測試集” 上的測試誤差作為泛化誤差的估計

• 測試集盡量不在訓(xùn)練集中出現(xiàn)，即二者盡量互斥

測試集的劃分方法

1. 留出法

   將數(shù)據(jù)集劃分為兩個互斥的集合，同時保留類別比例(即進(jìn)行分層抽樣)

   一般采用確定分層比例后，在層的大小內(nèi)進(jìn)行若干次隨機(jī)劃分、重復(fù)進(jìn)行后取平均值作為最終結(jié)果

2. 交叉驗證法

   與留出法相似，將數(shù)據(jù)集A分為 k 個互斥的集合

       for i in k:
   
           將 A - k_i 作為訓(xùn)練集
           將 k_i 作為測試集
           記錄 測試誤差 err_i
   
       return 測試誤差的平均數(shù)
   

   • p次k折交叉驗證：通常重復(fù) p 次進(jìn)行，取 p 次結(jié)果的均值
   • 目的: 為了減少樣本劃分不同而引入的誤差

3. 留一法

   k 折交叉驗證法的特殊情況
   當(dāng) k = m , 此時稱為 留一法

4. 自助法

   在 數(shù)據(jù)集較小、很難劃分 訓(xùn)練集/ 測試集 的時候很有效

   但是，此方法產(chǎn)生的數(shù)據(jù)改變了出事數(shù)據(jù)集的分布，會引入估計偏差

   具體方法：
   假設(shè)數(shù)據(jù)集 D 有 m 個樣本

   1. 每次從數(shù)據(jù)集 D 中采出一個樣本，放入 D‘ 中，再將樣本放回 D
   2. 重復(fù)進(jìn)行 m 次采樣操作
   3. 用 D’ 作為訓(xùn)練集， D / D{`} 作為測試集

   可證明，測試集中度數(shù)據(jù)占 D 中的 1/3 ， 且均未出現(xiàn)過在 D‘ 中

   自助法在集成學(xué)習(xí)中的 Bagging 模型中還會用到（抽樣方法）

驗證集

• 我們將數(shù)據(jù)集劃分為訓(xùn)練集和驗證集，在驗證集上進(jìn)行模型選擇和調(diào)參

  注意?。?！
  在模型選擇調(diào)節(jié)完畢之后，還應(yīng)將整個數(shù)據(jù)集 D 再完整訓(xùn)練一遍！

2.3 性能度量

• 不同的性能度量導(dǎo)致不同的評判結(jié)果
• 不能僅僅依賴評判結(jié)果，不同的任務(wù)需求和數(shù)據(jù)需要不同的模型和性能度量

2.3.1 錯誤率與精度

分類任務(wù)中最常用的性能度量，可用于 二分類 及 多分類

2.3.2 查準(zhǔn)率、查全率與 F1

查準(zhǔn)率 也叫 準(zhǔn)確率（Precision）
查全率 也叫 召回率（Recall）

Precision 和 Recall 定義為：

{P} = TP \over {TP + FP}

{R} = TP \over {TP + FN}

• Precision 很高往往導(dǎo)致 Recall 較低，可以理解為謹(jǐn)小慎微，需要很大的確信度才會做決定
• Recall 很高往往導(dǎo)致 Precision 較低，可以理解為寧可錯殺一萬，也不會放過一個

P-R 曲線

1. 繪制具體步驟

   參考ROC曲線的繪制過程，將預(yù)測結(jié)果排序，依次將預(yù)測結(jié)果設(shè)置為閾值然后計算相應(yīng)的 Precision 和 Recall

2. 若分類器的 A 的 P-R 曲線完全被另一個分類器B “包住” ,則 B 的性能優(yōu)于 A

3. 平衡點（BEP）

   是當(dāng) Precision = Recall 時的取值，BEP 大的分類器更優(yōu)

F1 Score

比算術(shù)平均、幾何平均更加重視較小值

{F_1} = \frac {2 \times P \times R}{P + R}

Fβ Score

針對對于查準(zhǔn)率和查全率重視程度不一樣的情況
比算術(shù)平均、幾何平均更加重視較小值

{F_\beta} = \frac {(1 + {\beta}^2) \times P \times R}{({\beta}^2 \times P) + R}

macro F1 Score

亦稱 宏F1
直接計算，再求平均

{macro-P} = {1 \over n} \sum_{i=1}^{n}P_i

同理可得 macro-R，利用 macro-P、macro-R 和 F1 計算公式最后可得macro-F1

micro F1 Score
亦稱 微F1，同理macro-F1，記為micro-F1，先對 TP、TN、FP、FN 求平均，再計利用平均值計算F1 Score

2.3.3 ROC與AUC

• ROC - 受試者工作特征
• 橫軸： TPR ； 縱軸： FPR

• AUC - 曲線下面積
• 面積的大小代表預(yù)測的準(zhǔn)確性
• 繪制步驟
  • 對每個測試樣例進(jìn)行預(yù)測，得到預(yù)測結(jié)果
  • 對預(yù)測結(jié)果進(jìn)行排序
  • 將分類閾值一次設(shè)置為每一個預(yù)測值即將每個樣例設(shè)置為正例）
  • 設(shè)置好閾值之后，循環(huán)其他樣例，若樣例為真正例，則縱坐標(biāo)加1 \over m^+
  • AUC中坐標(biāo) x 代表 該點之前的反例所占比，因為每遇到一個反例橫坐標(biāo)擴(kuò)大一個百分點（1 \over m^-），同理，y 代表 該點之前的正例所占比
  • AUC的范圍是 [0.5, 1]

2.3.4 代價敏感錯誤率與代價曲線

敏感代價錯誤率

E(f;D;cost) = \frac{1}{m} (\sum_{x \in {D^+}}I(f(x_i)\not=y_i) \times cost_{01} + \sum_{x_i \in D^-}I(f(x_i)\not=y_i) \times cost_{10})

• 為了權(quán)衡不同類型的錯誤造成的代價
• 使用 代價矩陣(cost_{01}，cost_{10}...)刻畫不同的代價
• 使用 比值 刻畫代價之間的重要程度

2.4 比較檢驗

• 使用假設(shè)檢驗的方法，進(jìn)行誤差的假設(shè)檢驗
• 后期進(jìn)行二項檢驗、t檢驗的具體筆記

2.5 偏差與方差

• 針對回歸問題，期望泛化誤差可以分解為 偏差、方差、噪聲之和
• 分解結(jié)果：

E(f;D) = bias^2(x) + var(x) + \epsilon^2

• 具體分解過程見書 P45頁
• 偏差與方差的關(guān)系
  • 偏差與方差是 準(zhǔn) 與 確 的關(guān)系
  • 偏差 ：刻畫預(yù)測結(jié)果的 確 的程度，即算法本身的擬合能力
  • 方差 ：刻畫預(yù)測結(jié)果的 準(zhǔn) 的程度，也提現(xiàn)算法抗數(shù)據(jù)擾動的能力
  • 噪聲 ： 刻畫算法達(dá)到期望泛化誤差的下界，即學(xué)習(xí)問題本身的難度
  • 學(xué)習(xí)初期， 偏差 主導(dǎo)泛化錯誤率，體現(xiàn)為 欠擬合
  • 學(xué)習(xí)后期，欠擬合問題逐漸解決， 方差 主導(dǎo)泛化錯誤率，體現(xiàn)為 過擬合 ，在學(xué)習(xí)器學(xué)習(xí)過程中，會漸漸學(xué)習(xí)到數(shù)據(jù)中的 干擾數(shù)據(jù)，從而導(dǎo)致學(xué)習(xí)器的抗干擾能力下降，也即方差增加

偏差與方差的經(jīng)典關(guān)系圖：

image

• Min-Max規(guī)范化和z-score規(guī)范化的區(qū)別

第3章 線性模型

3.1 基本形式

• 試圖用 屬性 的 線性組合 進(jìn)行預(yù)測
• 基本形式：

f(x) = \omega^Tx + b = \omega_1x_1 + \omega_2x_2 + \cdots + \omega_dx_d + b

• \omega 代表了各屬性的 重要性， 因此線性模型具有很好的 可解釋性

3.2 線性回歸

回歸模型的變量通常是連續(xù)值，因此當(dāng)屬性是離散值時，可以進(jìn)行 連續(xù)化

• 當(dāng)屬性件存在 “序” 的關(guān)系，通過對離散值進(jìn)行排序，然后轉(zhuǎn)換為相應(yīng)大小的連續(xù)值
• 當(dāng)屬性間不存在 “序” 的關(guān)系，可以通過使用 OneHot 編碼方法進(jìn)行離散值的轉(zhuǎn)換
• 無序?qū)傩赃M(jìn)行連續(xù)化會不恰當(dāng)?shù)囊?“序” 的關(guān)系

損失函數(shù)：

• 使用 均方誤差(MSE) 進(jìn)行性能度量

MSE = \sum_{i=1}^{m}{(f(x_i) - y_i)}^2 = \sum_{i=1}^{m}{(\omega x_i + b - y_i)}^2

求解方法：

• 最小二乘法 - 找到一條直線使所有的樣本到直線的歐氏距離最小
• 最大似然估計 - 求出使所有出現(xiàn)的結(jié)果值的概率最大的概率模型參數(shù)

3.3 對數(shù)幾率回歸

也叫邏輯回歸（Logistic Regression），雖然叫回歸，但是其實是 分類 算法

起源

• 希望使用 線性模型 進(jìn)行 分類預(yù)測任務(wù)
• 因此輸出結(jié)果需要是 離散的 類別標(biāo)簽，二分類為例： y = {0,1}
• 但是線性模型的預(yù)測結(jié)果是連續(xù)值，因此我們需要找到一個函數(shù)將連續(xù)的結(jié)果值映射為離散的類別標(biāo)簽
• 因此，單位階躍函數(shù) 是理想的映射函數(shù)，但是單位階躍函數(shù)并不單調(diào)可微，這樣就引入了 對數(shù)幾率函數(shù) 作為替代函數(shù)
• 預(yù)測的結(jié)果其實是 對率幾率，定義如下：

\omega x^T + b = ln \frac {y}{1-y}

• 而 y 才是概率
• 去除 ln 有 幾率 的定義，反映 x 作為正例的相對可能性
• 直接對 分類可能性 建模，無需實現(xiàn)假設(shè)數(shù)據(jù)分布，避免假設(shè)分布不準(zhǔn)確引入的問題

3.4 線性判別分析

核心思想：

• 異類點的投影點盡可能的遠(yuǎn)離，同類點之間的協(xié)方差盡可能的小(即同類點之間盡可能的靠近)

優(yōu)化目標(biāo)

J = \frac{w^TS_bw}{w^TS_ww}

• 二維情況詳細(xì)推導(dǎo)可以參考 https://www.cnblogs.com/engineerLF/p/5393119.html
• 其中可以用“廣義瑞利商”的性質(zhì)得出最優(yōu)w ,詳細(xì)性質(zhì)推導(dǎo)見 https://www.cnblogs.com/pinard/p/6244265.html

最大化方法

• 添加負(fù)號，變?yōu)樽钚』瘑栴}
• 使用拉格朗日乘子法，

求解結(jié)果

• 在一般的實踐中，S_w^{-1} 使用SVD進(jìn)行奇異值分解，通過 S^{-1}_w = V{\Sigma}^{-1}U^T 得到 {S_w}^{-1}

KLDA

• 在LDA中引入核函數(shù)，應(yīng)對非線性可分問題，具體推導(dǎo)見西瓜書P137

3.5 多分類學(xué)習(xí)

• 三種拆分策略：

  • 一對一（OvO）
  • 一對其余（OvR）
  • 多對多（MvM）

• 一對一 將類別兩兩配對生成 \frac {N(N-2)}{2} 個分類器

• 一對其余 每次將一個類別視為正例，其余視為反例，因此一共會生成 N 個分類器

• 但是，一對一的 訓(xùn)練開銷 通常小于 一對其余，因為一對一只用到了兩個類的訓(xùn)練數(shù)據(jù)

多對多分類

• 常用糾錯輸出碼（ECOC）
• 常見編碼矩陣：二元碼，三元碼（加上停用類，不帶入計算）
• 將類別進(jìn)行隨機(jī)拆分，拆分為兩類：正例和反例，形成很多個二分類器
• 任意兩個分類器越 ”不相同“，訓(xùn)練結(jié)果越好，思想類似于 Bagging，訓(xùn)練多個高多樣性的分類器
• 最后這些分類器對同一個樣本預(yù)測，將預(yù)測結(jié)果分別計算編碼距離（海明距離 / 歐式距離），將編碼距離最小的類作為最終結(jié)果
• 同一個分類任務(wù)， ECOC編碼越長，分類器之間的相似性就會越小，因此容錯能力越好
• 同等長度的編碼， 任意兩個類別的編碼距離越大，容錯能力越好

3.6 類別不平衡問題

“再縮放” 思想

在對分類任務(wù)進(jìn)行預(yù)測時，y 是代表正例的概率，通常將閾值設(shè)置為 0.5，即 y > 0.5 ,將結(jié)果判定為正例，否則判定為負(fù)例

言外之意：

若 y > 0.5， 預(yù)測為正例， 即若 \frac{y}{1-y} > 1, 預(yù)測為正例

但是，注意這樣做的原因：
0.5 代表的其實是 觀測幾率, 即我們在數(shù)據(jù)集中能觀測到正例的幾率（我們 假設(shè) 兩個類別的數(shù)據(jù)集是一樣大的，因此觀測幾率是 0.5）所以當(dāng) y > 0.5 代表預(yù)測正例的概率大于觀測概率，當(dāng)然應(yīng)該判定為正例。

而現(xiàn)在，不同的類別對應(yīng)的數(shù)據(jù)量不同了，不再是 1 ： 1，我們的閾值就不應(yīng)該設(shè)置為 0.5， 而是應(yīng)該當(dāng)：

若 \frac {y}{1-y} > \frac{m^+}{m^-}，預(yù)測為正例， 解出 y ，就是我們新的閾值

欠采樣、過采樣思想

欠采樣

• 減少數(shù)據(jù)集的數(shù)目，使得所有類別的數(shù)據(jù)相同
• 代表算法： EasyEnsemble，即分割負(fù)例為不同的數(shù)據(jù)集，以供多個學(xué)習(xí)器使用，利用了集成的思想

過采樣

• 增加數(shù)據(jù)集的數(shù)目，使得所有類別的數(shù)據(jù)相同
• 需要注意增加數(shù)據(jù)集的方法，單純的 重復(fù)采樣 會導(dǎo)致嚴(yán)重的 過擬合
• 代表算法： SMOTE

3.7 相關(guān)思考

• 線性回歸推導(dǎo)中的最小二乘和極大似然的關(guān)系

  • 是因為極大似然中假設(shè) 誤差服從正態(tài)分布 所以才會有推導(dǎo)結(jié)果與最小二乘是一樣的，正態(tài)分布中剛好有二次項

  • 另一種說法是最小二乘選擇使用平方的原因是推導(dǎo)極大似然的推導(dǎo)結(jié)果就是最小二乘，所以說最小二乘是極大似然估計的結(jié)果

第4章 決策樹

4.1 決策樹模型與學(xué)習(xí)

優(yōu)點

• 模型具有可讀性，分類速度快

概念

• 損失函數(shù)使用 正則化的極大似然函數(shù)
• 學(xué)習(xí)的策略是 最小化損失函數(shù)
• 使用啟發(fā)式方法求解決策樹，求解的結(jié)果是次優(yōu)的
• 結(jié)點有兩種類型：內(nèi)部結(jié)點(非葉子結(jié)點）表示一個特征或?qū)傩裕?葉子結(jié)點代表一個類
• 還表示給定特征條件下的概率分布

決策樹的學(xué)習(xí)算法包括：

• 特征選擇（劃分選擇）
• 決策樹的生成，只考慮局部最優(yōu)
• 決策樹的剪枝，考慮全局最優(yōu)

注意兩種情況：

1. 當(dāng)屬性集為空或所有樣本在屬性集上的取值相同，將類別標(biāo)記為 D 中最多的類別，使用的是當(dāng)前結(jié)點的 后驗分布
2. 當(dāng)當(dāng)前結(jié)點包含的樣本集為空，同樣將類別標(biāo)記為 D 中最多的類別，但是是利用的當(dāng)前結(jié)點的 先驗分布

4.2 特征選擇（劃分選擇）

基于 信息熵 進(jìn)行特征選擇

• 表示隨機(jī)變量不確定性的度量

• 同時也可以從另一個角度理解： 表示了解一件事情所需要花費的信息代價（數(shù)學(xué)之美）

常用 3 種指標(biāo)選擇應(yīng)作為劃分的特征

• 信息增益
  • 對 可取數(shù)目較多 的特征(屬性)有所偏好
• 增益率
  • 對 可取數(shù)目較少 的特征(屬性)有所偏好

所以通常采用一種折中的方法： 先找出高于平均水平的 信息增益， 再找出其中 信息增益率 最大的特征(屬性)

• 基尼系數(shù)

4.3 決策樹的生成

常用的 3 種生成算法：

• ID3， 使用 信息增益 進(jìn)行特征選擇
• C4.5， 使用 增益率 進(jìn)行特征選擇
• CART， 使用 基尼系數(shù) 進(jìn)行特征選擇

ID3相當(dāng)于用極大似然法進(jìn)行概率模型的選擇 理解

決策樹模型的參數(shù)估計就是基于特征空間怎樣劃分使得樣本出現(xiàn)的概率最大,而尋找怎樣劃分的過程即求解概率模型參數(shù)的過程

4.4 CART 的生成

CART回歸樹的生成

對于回歸問題，CART 采用與決策樹相同的思想，還是 對輸入空間進(jìn)行劃分，每一個劃分R_m對應(yīng)一個固定的輸出值c_i，生成的回歸模型表示為：

f(x)=\sum_{m=1}^Mc_mI(x\in{R_m})

固定的輸出值 c_i 為劃分空間R_m中y_i的均值

CART回歸樹的損失函數(shù)

CART回歸樹采用 平方誤差 \sum_{x_i\in{R_m}}(y_i-f(x_i))^2

CART回歸樹的劃分

依次對劃分空間R_m中的每一個樣本進(jìn)行如下的操作：

• 依次將當(dāng)前樣本的每一個 特征/屬性 值，作為一個切分點s，而當(dāng)前變量就是切分變量j
• 使用當(dāng)前切分變量的切分點將當(dāng)前劃分空間R_m劃分為兩個子區(qū)域 R_1={x|{x^{(j)} \req s}}, R_2={x|{x^{(j)} > s}}
• 然后計算 R_1 和 R_2 的固定輸出值 c_{1i}, c_{2i}
• 計算c_{1i}, c_{2i} 下的平方誤差和 r_{js} = r_{js1} + r_{js2}

比較所有的r_{js}, 找到 最小的 r_{js}下的最優(yōu)切分變量 j，最優(yōu)切分點 s

再對劃分好的兩個子區(qū)域進(jìn)行上述劃分，直到滿足停止條件

CART分類樹的生成

CART分類樹使用 基尼系數(shù) 為劃分依據(jù)，剩下的生成方式與決策樹的生成方式一樣

算法停止的條件可以是：

• 結(jié)點中的樣本個數(shù)少于閾值
• 結(jié)點上的基尼指數(shù)小于閾值(基本屬于同一類)
• 或者沒有更多特征

CART分類樹的剪枝

4.5 決策樹的剪枝

剪枝策略

• 預(yù)剪枝
• 后剪枝

由 4.3 中 ID3相當(dāng)于用極大似然法進(jìn)行概率模型的選擇 的概念， 決策樹的剪枝也可以看做是正則化的極大似然估計，正則化項就是決策樹的葉結(jié)點個數(shù)

預(yù)剪枝

• 在劃分結(jié)點前估計，若劃分結(jié)點后不能提升泛化性能，則停止劃分
• 使用貪心的策略，有可能陷入局部最優(yōu)
• 帶來欠擬合的風(fēng)險

后剪枝

• 等決策樹完全生成好之后，再從下而上的進(jìn)行剪枝
• 剪枝策略：
  • 將結(jié)點的子樹替換為葉節(jié)點，觀察泛化性能是否提升，如果提升則將子樹替換為葉節(jié)點，否則不進(jìn)行剪枝
  • 根據(jù)奧卡姆剃刀原則，如果泛化性能不變依然應(yīng)該選擇剪枝，形成更簡單的決策樹
• 可以較好的防止過擬合，但是時間開銷很大

這里的泛化性能評估標(biāo)準(zhǔn)可以是 精度

4.6 連續(xù)與缺失值

4.6.1 連續(xù)值的處理

假設(shè)屬性 A 為連續(xù)值屬性， A 屬性共有 N 個不同的值

• 將這 N 個不同的值進(jìn)行排序
• 依次選取劃分點 t，大于劃分點 t 的記為 D_t^+, 同理，小于 t 的記為 D_t^-
• 這樣，可以將每一個取值都作為一次劃分點，然后計算 信息增益, 最后可以得到屬性 A 的信息增益
• 后續(xù)就跟離散值的做法一樣了

4.6.2 缺失值的處理

當(dāng)計算屬性 A 的信息增益時，如果發(fā)現(xiàn)有樣本有缺失值：

• 初始將所有樣本賦予 1 的 權(quán)值
• 計算 屬性a 上的三個概率（主要都是針對不含有缺失值的樣本）
  • 無缺失樣本所占總體數(shù)據(jù)比例
  • 無缺失樣本中第k類所占比例
  • 屬性 a 上無缺失樣本中取值為a^v所占比例
• 利用這三個概率計算每一個屬性 a 的信息增益

Gain(D,a) = \rho \times (Ent(D^n) - \sum_{v=1}^{V}{r_v}^~Ent({D_v}^n))

• 更新含有缺失值的樣本的權(quán)值，并劃入每一個結(jié)點
  • 將劃入的數(shù)據(jù)權(quán)值更新為 {r^n}_v * w_x, 相當(dāng)于將數(shù)據(jù)依概率進(jìn)行劃分
• 后續(xù)與普通的操作相同

注意：

• 更新權(quán)值相當(dāng)于以不同的概率將樣本劃分進(jìn)每一個結(jié)點
• 因為含有缺失值的樣本可能接下來還要參加其他屬性的信息增益的計算，而計算中會涉及權(quán)值，所以 權(quán)值 相當(dāng)于對帶有缺失值的樣本的 影響力

4.7 多變量決策樹

相當(dāng)于對特征進(jìn)行了一個線性的組合，之前的特征是單變量，組合之后單個結(jié)點相當(dāng)于一個 線性的分類器

4.8 習(xí)題思考

1. 以“最小訓(xùn)練誤差”作為劃分選擇的缺點

• 由于訓(xùn)練集總會與模型之間存在誤差，如果選擇最小誤差，則會很大程度的擬合為符合訓(xùn)練集的決策樹，從而導(dǎo)致嚴(yán)重的過擬合

2. 對比使用遞歸、棧（非遞歸）、隊列（非遞歸）三種結(jié)構(gòu)生成決策樹的優(yōu)缺點

• 缺點：

  • 使用遞歸的方法會保存大量的參數(shù)信息，而在參數(shù)中有大量的數(shù)據(jù)信息，從而會導(dǎo)致內(nèi)存溢出
  • 如果使用棧的結(jié)構(gòu)，不能完成以MaxNode的約束，會生成畸形的決策樹（只有一邊），只能完成以MaxDepth的約束
  • 如果使用隊列的結(jié)構(gòu)，只能完成BFS即以MaxNode的約束

• 優(yōu)點：

  • 使用遞歸的方法代碼更加簡潔，易讀
  • 使用棧的結(jié)構(gòu)有利于后剪枝
  • 使用隊列的結(jié)構(gòu)，由于入隊之前必須進(jìn)行劃分，如果是用預(yù)剪枝則會很方便，因為可以比較劃分與否的驗證集精度，而棧則做不到

當(dāng)數(shù)據(jù)屬性相對較多，屬性不同取值相對較少時，樹會比較寬，此時深度優(yōu)先所需內(nèi)存較小，反之寬度優(yōu)先較小。

第5章 神經(jīng)網(wǎng)絡(luò)

后續(xù)再寫

第6章 支持向量機(jī)

支持向量機(jī)內(nèi)容順序主要根據(jù)《統(tǒng)計學(xué)習(xí)方法》中的章節(jié)來安排，主要內(nèi)容也由《統(tǒng)計學(xué)習(xí)方法》展開，其中穿插入西瓜書的知識點

6.1 概念

• SVM是一種 二分類 模型
• 學(xué)習(xí)算法是 求解凸二次規(guī)劃的最優(yōu)化算法
• 模型分類三類
  • 線性可分支持向量機(jī)：當(dāng)數(shù)據(jù)集線性可分（硬間隔支持向量機(jī)）
  • 線性支持向量機(jī)：當(dāng)數(shù)據(jù)集近似線性可分（軟間隔支持向量機(jī)）
  • 非線性支持向量機(jī)：使用核技巧
• 核函數(shù)
  • 表示將輸入從輸入空間映射到特征空間得到的特征向量之間的內(nèi)積

6.2 線性可分支持向量機(jī)

• 輸入空間
  • 輸入的數(shù)據(jù)向量所在的空間
• 特征空間
  • 特征向量所在的空間

支持向量機(jī)的學(xué)習(xí)是在特征空間中進(jìn)行的，線性可分SVM將輸入空間中的輸入線性映射為特征空間中的特征向量，非線性可分SVM將輸入非線性映射為特征向量

• 算法思想
  • 利用間隔最大化求最優(yōu)分離超平面，解是唯一的
  • 能夠正確劃分訓(xùn)練數(shù)據(jù)集并且 幾何間隔 最大

學(xué)習(xí)到的分離超平面：

w^* * x + b^* = 0

最終的分離決策函數(shù)使用符號函數(shù)

6.2.1 函數(shù)間隔和幾何間隔

• 函數(shù)間隔

\hat{\gamma}_i = y_i(w*x_i+b)

其中 y_i 用來表示分類預(yù)測的正確性, w*x_i+b 用來表示分類的確信度（換言之就是點到分類超平面的距離）

定義超平面的函數(shù)間隔為數(shù)據(jù)集D中所有樣本的函數(shù)間隔中的最小值，即：

\hat{\gamma} = \min_{i=1,...,N}\hat{\gamma}_i

• 幾何間隔

由于成倍縮放w,b會導(dǎo)致函數(shù)間隔成倍縮放，所以 w 加上約束，如約束為：\Vert{w}\Vert = 1， 可以導(dǎo)出幾何間隔

• 函數(shù)間隔與幾何間隔的關(guān)系

\gamma = \frac{\hat{\gamma}}{\Vert{w}\Vert}

6.2.2 間隔最大化

• 直觀解釋
  • 使得分離有足夠的確信度 [ 使得（離分離超平面 最近 的數(shù)據(jù)點）離超平面 足夠遠(yuǎn) ]

可以得到求解式：

\max{\frac{\hat{\gamma}}{\Vert{w}\Vert}}_{w,b}

s.t. y_i(w*x_i+b) \geq \hat{\gamma}, i = i,2,...,N

令 \hat{\gamma} = 1,得到 線性可分支持向量機(jī)的最優(yōu)化問題(凸二次優(yōu)化問題), 具體推導(dǎo)見《方法》P97：

\min_{w,b} \frac{1}{2}{\Vert{w}\Vert}^2

s.t. y_i(w*x_x+b) - 1 \geq 0, i=1,2,...,N

6.2.3 學(xué)習(xí)的對偶算法

求解 線性可分支持向量機(jī)的最優(yōu)化問題 使用 拉格朗日對偶性，令原式為原始問題，通過求解對偶問題得到原始問題的最優(yōu)解

• 優(yōu)點
  • 對偶問題更容易求解
  • 自然引入核函數(shù)（在對偶式中出現(xiàn)了內(nèi)積）

推導(dǎo)過程見 《統(tǒng)計學(xué)習(xí)方法》 P103

其中幾個重要的點：

• 支持向量是 {\alpha_i}^* > 0 的點
• 對偶學(xué)習(xí)問題的KKT條件

image

• KKT的對偶互補(bǔ)條件

{\alpha}^* \geq 0

• 實際應(yīng)用中b的求解
  • 理論上使用任意一個數(shù)據(jù)x_j就能算出 b
  • 在實際應(yīng)用中，采用更加魯棒的做法:使用所有 支持向量 求解的平均值,S代表支持向量的集合

b = \frac{1}{S}\sum_{s\in{S}}(\frac{1}{y_s} - \sum_{i\in{S}}\alpha_iy_ix_i^Tx_s)

6.3 線性支持向量機(jī)與軟間隔最大化

6.3.1 線性支持向量機(jī)

• 引入

  • 大部分?jǐn)?shù)據(jù)并不滿足完全線性可分，存在一部分?jǐn)?shù)據(jù)非線性可分，因此對每一個數(shù)據(jù)引入一個松弛變量 \xi \geq 0,使得那些不滿足線性可分的數(shù)據(jù)點加上 \xi 變得線性可分

• 線性支持向量機(jī)的原始問題：

\min_{w,b,\xi} \frac{1}{2}{\Vert{w}\Vert}^2+C\sum_{i=1}^N{\xi}_i
s.t. y_i(w*x_i+b) \geq 1 - {\xi}_i, i = 1,2,...N
{\xi}_i \geq 0, i=1,2,...N

• 原始問題的對偶問題

  • 同線性可分的推導(dǎo)相同，先求\min_{w,b,{\xi}}(即分別對w,b,\xi求導(dǎo)，并令導(dǎo)數(shù)等于零，求出相應(yīng)的表達(dá)式，代回原式，得到\min_{w,b,{\xi}}L(w,b,\xi,\alpha,\mu))
  • 再求出\max_{\alpha}\min_{w,b,{\xi}}L(w,b,\xi,\alpha,\mu)

• 原始問題滿足的KKT條件

image

6.3.2 支持向量

• 若{\alpha_i}^* < C, 則\xi_i = 0,支持向量恰好落在間隔邊界上
• 若{\alpha_i}^* = C，0<\xi_i<1,則此時分類正確，x_i 在分類超平面與間隔邊界之間
• 若{\alpha_i}^* = C，\xi_i = 1，則 x_i 在分離超平面上
• 若{\alpha_i}^* = C，\xi_i > 1, 則 x_i 位于分類錯誤的一側(cè)

6.3.3 合頁損失函數(shù)

• 定義

image

• 原始問題也等價于含有合頁函數(shù)作為損失函數(shù)的目標(biāo)函數(shù)
• 也即將 \xi_i 換成了{[1-y_i(w*x_i+b)]}_+

{\sum_{i=1}^N}{[1 - y_i(w*x_i+b)]}_+ + \lambda{\Vert{w}\Vert}^2

• 相比感知機(jī)的損失函數(shù)和0-1損失函數(shù)，合頁損失函數(shù)有更高的要求

[圖片上傳失敗...(image-b1fd0d-1532507004505)]

6.4 支持向量回歸

• 思想
  • 不同于傳統(tǒng)回歸模型，SVR對偏差有一定的容忍，形成一個以容忍度/寬度2\epsilon為間隔帶，誤差不超過\epsilon的樣本都認(rèn)為預(yù)測正確
  • SVR也可以引入核函數(shù)
  • SVR引入了 \epsilon-不敏感損失

l_\epsilon(z) = \begin{cases} 0, & \text{if $|z| \leq \epsilon$} \\[2ex] |z| - \epsilon, & \text{otherwise} \end{cases}

• 原始問題
  • SVR考慮預(yù)測模型兩側(cè)的情況，所以約束條件分為兩個

f(x_i) - y_i \leq \epsilon + \xi_i, 上側(cè)

y_i - f(x_i) \leq \epsilon + \hat{\xi_i}, 下側(cè)

6.5 核函數(shù)

6.5.1 核技巧

非線性分類問題

• 對于不能線性分類的數(shù)據(jù)，也就不能用一個超平面將數(shù)據(jù)分開，但如果能用一個 超曲面 將數(shù)據(jù)集分開，那么這個問題就是一個非線性可分問題
• 注意：是 非線性的 但是是 可分的問題

求解思想

• 使用一個變換將原空間的數(shù)據(jù)映射到新空間，而這個新空間也就是 特征空間
• 在 新空間\特征空間 上用 線性分類的學(xué)習(xí)方法 學(xué)習(xí)分類模型

核函數(shù)定義

K(x,z) = \phi(x)*\phi(z)

其中，\phi{x} 為 映射函數(shù)

表示定理

• 對于一般的損失函數(shù)和正則化項，優(yōu)化問題都能表示為核函數(shù)的線性組合

h^*(x) = \sum_{i=1}^m\alpha_ik(x,x_i)

核函數(shù)在SVM中的應(yīng)用

• 將SVM對偶問題中的內(nèi)積 x_i*x_j 變換為特征空間中的內(nèi)積 \phi(x_i)*\phi(x_j)
• 當(dāng)映射函數(shù)是 非線性函數(shù) 時，學(xué)習(xí)到的核函數(shù)SVM是 非線性分類模型

使用核函數(shù)的支持向量機(jī)最優(yōu)化問題

6.6 習(xí)題思考

• 為什么高斯核會把原始維度映射到無窮多維？
  • 定義多項式核函數(shù) k(x,y) = {(x^Ty)}^p
  • 然后考慮高斯核函數(shù)k(x,y) = exp(-{\Vert{x-y}\Vert}^2)
  • 展開后得到： k(x,y) = exp(-{\Vert{x}\Vert}^2)exp(-{\Vert{y}\Vert}^2)exp(2xy)
  • 由泰勒展開公式：

指數(shù)函數(shù)： e^x = \sum_{n=0}^\infty{\frac{x^n}{n!}}

可以得到：

k(x,y) = exp(-{\Vert{x}\Vert}^2)exp(-{\Vert{y}\Vert}^2){\sum_{n=0}^\infty}{\frac{(2x^Ty)^n}{n!}}

可以看出，高斯核其實被展開為無窮項多項式核函數(shù)的和，而這其中也包括了無限維的多項式核，因此高斯核會把原始維度映射到無窮多維

第七章 貝葉斯分類器

7.1 貝葉斯決策論

概念

• 貝葉斯決策論是建立在 概率 和 損失 之上的,以概率為基石輔以損失函數(shù)

二者結(jié)合形成了在樣本上的 “條件風(fēng)險” 函數(shù)

R(c_i|x) = \sum_{j=1}^N\lambda_{ij}P(c_j|x)

\lambda_{ij} 是將真實標(biāo)記為 c_j 的標(biāo)記預(yù)測為 c_i 的損失，可以為任意的損失函數(shù)

P(c_i|x) 是 可從數(shù)據(jù)中獲得 樣本分類為 c_i 的 后驗概率

我們需要找到一個判定準(zhǔn)則 h , 來 最小化總體風(fēng)險, 即 使得預(yù)測結(jié)果類 c^* 是使得上面提到的損失最小的類 c

因此最優(yōu)的判定準(zhǔn)則為：

h(x^*) = \mathop{argmin}_{c\in{Y}}R(c|x)

現(xiàn)在，就我們就只需要考慮如何求得所有的 R(c|x), 當(dāng)損失函數(shù)是 0-1損失 時有：

R(c|x) = 1 - P(c|x)

注意！ 上式只在 損失函數(shù) 是 0-1損失 時成立！?。?/strong>

但是當(dāng) Z 是連續(xù)變量或者離散變量與連續(xù)變量的組合時，?法是完全相同的，只需把求和換成適當(dāng)?shù)?strong>積分即可（PRML）

• 為什么EM算法需要先給定一個先驗的參數(shù) \theta？

因為在求解最大化對數(shù)似然 log\sum_z{P(Y,Z|\theta)} 的過程中引入了一個 常數(shù)，而這個常數(shù)是一個已知了參數(shù) \theta 和Y的關(guān)于隱變量 z 的概率值，因為需要提前已知參數(shù) \theta 分布函數(shù)才是確定的，然后帶入 Y 才能利用分布函數(shù)求出當(dāng)前隱變量 z 的概率值

• 每次 M步 最大化的是什么？

最大化的是期望，而這個期望是對數(shù)似然的期望，其中對數(shù)似然的分布函數(shù)已經(jīng)是給定了的（其中分布函數(shù)是有關(guān)\theta的）

• 每次 E步 求的是什么？

求的是 M步最大化需要用到的提前給定的 對數(shù)似然的分布函數(shù)， 利用提前給的 \theta 進(jìn)行求解

8.2 算法步驟

• 輸入模型參數(shù)的初值 \theta^{(0)}
• E步： 利用已知的參數(shù)\theta^i 計算函數(shù) Q(\theta,\theta^{(i)}) = \sum_zlogP(Z|Y,\theta^{(i)})P(Y,Z|\theta)
  • 其中函數(shù) Q(\theta,\theta^{(i)}) 就代表對數(shù)似然的期望
  • 需要計算的就是 P(Z|Y,\theta^{(i)})
  • 其中含有 M步需要最大化的參數(shù)\theta
• M步： 最大化E步求出的 Q(\theta,\theta^{(i)}) 中的參數(shù) \theta
• 將 M步 求出的最大的 \theta 作為E步中已知的參數(shù)\theta^i，迭代進(jìn)行計算，直到參數(shù) \theta 收斂（變化很?。?/li>

8.3 算法是怎么來的 + 坐標(biāo)上升###

• 思想

  • 最大化觀測數(shù)據(jù)的對數(shù)似然函數(shù) logP(Y|\theta)
  • 找到一個對數(shù)似然函數(shù)的下界函數(shù) Q(\theta)
  • 找到下界函數(shù) Q(Z) 的最大值 \theta^*
  • 下界函數(shù)利用 Jensen不等式 得到（提示：log函數(shù)是一個凹函數(shù)）求得，其中需要引入一個使用 \theta^{(i)} 的先驗分布 Q(z^{(i)})

• 如何求得需要引入的先驗分布 Q(z^{(i)})？

  • 從 Jensen不等式入手，由于Jensen 表示： E[f(x)] \leq f[E(x)], 當(dāng)x為常數(shù)c的時候，左右式相等，此時取到等號
  • 此時求得 Q(z^{(i)}) = P(z^{(i)}|Y,\theta)

EM算法是一個迭代計算的算法，思想就是每次固定一個變量

• 首先固定住 \theta, 調(diào)整先驗分布函數(shù)Q(z^i)取到等號
• 然后固定住先驗分布函數(shù)Q(z^{(i)})，調(diào)整\theta，使先驗分布函數(shù)Q(z^{(i)})取得最大值，得到\theta^{new}
• 再固定住\theta，此時使用剛計算出的\theta^{new} ，調(diào)整先驗分布函數(shù)Q(z^i)取到等號....
• 直到對數(shù)似然函數(shù)收斂到最大值\theta^*

因此，EM算法可以看做利用 坐標(biāo)上升 進(jìn)行優(yōu)化的算法

image

第九章 集成學(xué)習(xí)

Boosting方法

主要關(guān)注 降低偏差

AdaBoost

核心思想

弱分類器的線性組合

組成元素

• 弱分類器 G_m(x)
• 弱分類器系數(shù) \alpha_m
• 第 m 輪中，第 i 個樣本的系數(shù) w_{m,i}
• 弱分類器在 加權(quán)數(shù)據(jù)集 上的分類誤差率 e_m，是被G_m(x)誤分類的樣本的權(quán)值之和

算法步驟

• 將樣本的權(quán)值先給定為均值，在此基礎(chǔ)上學(xué)習(xí)出基本分類器 G_1(x)
• 反復(fù)學(xué)習(xí)基分類器，執(zhí)行以下步驟：
  • 使用當(dāng)前權(quán)值分布的數(shù)據(jù)集學(xué)習(xí)得到基本分類器 G_m(x)
  • 計算基本分類器在當(dāng)前 加權(quán)數(shù)據(jù)集 上的分類誤差率 e_m
  • 根據(jù) e_m 調(diào)整基本分類器 G_m(x) 的系數(shù) \alpha_m，分類誤差率 越小 的基本分類器，其系數(shù) 越大，即在最終分類器中的作用越大
  • 根據(jù)基本分類器 G_m(x) 的系數(shù) \alpha_m，更新下一個基本分類器 G_{m+1}(x) 訓(xùn)練的數(shù)據(jù)集的權(quán)值分布 w_{m+1,i}

另一種解釋

AdaBoost 還可以看做是 前向分步加法算法 的特例，是由基本分類器組成的 加法模型， 損失函數(shù)是 指數(shù)函數(shù)

前向分步算法

• 學(xué)習(xí)的是 加法模型
• 從前向后，每次只學(xué)習(xí)一個基分類器及其系數(shù)

提升樹

以 分類樹 或 回歸樹 為 基分類器 的提升方法

對分類問題，采用 二叉分類樹，對回歸問題， 采用 二叉回歸樹

采用 加法模型 + 前向分布算法 + 決策樹為基函數(shù) 且基函數(shù)為決策樹樁（最簡單的決策樹）

之所以采用二叉樹，是因為二叉樹是所謂的 決策樹樁, 足夠簡單，同時也能避免 過擬合

提升樹算法

不同問題的提升樹算法區(qū)別在于： 損失函數(shù)不同

• 分類問題： 指數(shù)損失函數(shù)
• 回歸問題：平方誤差損失函數(shù)
• 一般決策問題： 一般損失函數(shù)

分類問題提升樹

分類問題提升樹與Adaboost差別不大

其中，對于二分類問題，與 AdaBoost 算法步驟相同，只不過將基分類器固定為 二叉分類樹，即二分類問題的提升樹算法是 AdaBoost算法的特殊情況

回歸問題提升樹

回歸問題提升樹采用 前向分步算法 + 平方損失函數(shù)，學(xué)習(xí)方法就是不斷地擬合 殘差

• 計算當(dāng)前殘差 r_{mi} = y_i - f_{m-1}(x_i)
• 訓(xùn)練一個擬合當(dāng)前殘差 r_{mi} 的回歸樹 f_{m}
• 將學(xué)習(xí)到的回歸樹與之前的回歸樹進(jìn)行加和，求得最終的回歸提升樹

梯度提升樹（Gradient Boosing Decision Tree）####

核心思想

• 在 提升樹 的基礎(chǔ)上加入了 梯度 的概念,利用 負(fù)梯度在當(dāng)前模型的值 作為回歸問題提升樹中的殘差的 近似值

GBDT基分類器的選擇

• 服從 低方差和高偏差，算法框架服從 boosting框架 即可

• 由于是 擬合殘差(連續(xù)值)，所以GBDT中的基分類器選擇的基本都是 CART回歸樹

算法步驟

大部分在提升樹中的步驟不變，加入了 用損失函數(shù)的負(fù)梯度作為殘差的近似值

• 使用 原始數(shù)據(jù)集作為訓(xùn)練集, 利用 CART回歸樹 訓(xùn)練出第一個回歸樹 f_0(x)
• 計算損失函數(shù)的 負(fù)梯度 當(dāng)回歸樹 f_{m-1} 下的值 r_{mi}, 后面有舉例怎么計算
• 對 r_{mi} 擬合一顆 CART回歸樹 f_r(x), 擬合的過程參考:CART回歸樹的生成
• 更新 f_m(x) 為 f_{m-1}(x) 與 f_r(x) 的和
• 重復(fù)執(zhí)行以上步驟，直到達(dá)到停止條件

計算負(fù)梯度的例子

對于 平方損失函數(shù)，它就是殘差，對于一般損失函數(shù)，它是殘差的近似值

image

logloss的推導(dǎo)如下：

image

不同的問題下選擇的損失函數(shù)不同，后面會看到，例如多分類問題下的GBDT選擇的就是logloss

GBDT的各種擴(kuò)展

對于不同的問題GBDT采用不同的處理方法，而這些方法的不同之處只在于 損失函數(shù)的不同

同時，應(yīng)該注意，不同的損失函數(shù)下，算法的初始化方法也不同！?。。?/strong>