百面機器學習｜第三章經(jīng)典算法知識點

前言

如果你能找到這里，真是我的幸運~這里是藍白絳的學習筆記，本集合主要針對《百面機器學習——算法工程師帶你去面試》這本書。主要記錄我認為重要的知識點，希望對大家有幫助。

第三章 經(jīng)典算法

0、寫在前面

這一章我看了之后的感覺是，需要和《統(tǒng)計學習方法》——李航的書配合著一起看。這一章總共20頁，講了三個經(jīng)典機器學習算法，而在統(tǒng)計學習方法中少則有50頁去講這三個算法。所以這本書叫做“算法工程師帶你去面試”是有道理的，主要是由面試問題引出的對算法知識的整理和延伸，需要在看過統(tǒng)計學習方法，有一定的基礎之后再去看這一部分。例如SVM的部分，雖然以一個非常有趣的故事開頭，讓人覺得原來SVM也不是很復雜嘛，但是后面的面試題引出的知識點，是需要先弄懂SVM算法的推導過程的。
這章同時也給統(tǒng)計學習方法做了非常非常好的補充，例如SVM的部分，給出的面試題是我從來沒有想過的，這樣的題會讓我們對算法原理有更近一步的認識；在邏輯回歸的部分，講了邏輯回歸和線性回歸的一些延伸知識；在決策樹的部分，利用一個例子將后剪枝的算法講得非常清楚，這個部分我在統(tǒng)計學習方法中沒有看懂，在這里就可以看得很明白。

1、支持向量機

  1. 在空間上線性可分的兩類點，分別向SVM超平面上做投影，這些點在超平面上的投影仍然是線性可分的嗎？
    答案是，對于任意線性可分的兩組點，它們在SVM分類超平面上的投影都是線性不可分的。
  2. 是否存在一組參數(shù)使SVM訓練誤差為0？
    答案是，一個使用高斯核(K(x,z)=e^{-||x-z||^2 / \gamma^2})訓練的SVM中，若訓練集中不存在兩個點在同一位置，則存在一組參數(shù)\{\alpha_1,...,\alpha_m,b\}以及參數(shù)\gamma使得該SVM的訓練誤差為0。
  3. 訓練誤差為0的SVM分類器一定存在嗎？
    答案是，一定存在。具體可以去看看這本書。
  4. 加入松弛變量的SVM的訓練誤差可以為0嗎？
    答案是，并不一定能得到訓練誤差為0的模型。如果使用SMO算法來訓練一個加入松弛變量的線性SVM模型，則我們的優(yōu)化目標改變了，并不再是使訓練誤差最小?？紤]帶松弛變量的SVM模型優(yōu)化的目標函數(shù)所包含的兩項為：C\sum_{i}^{m}\xi_i和\frac{1}{2}||w||^2。當我們的參數(shù)C選取較小的值時，后面的正則項將占據(jù)優(yōu)化的較大比重。這樣，一個帶有訓練誤差，但是參數(shù)較小的點將成為更優(yōu)的結(jié)果。當C取0時，w也取0時即可達到優(yōu)化目標。

2、邏輯回歸

  1. 邏輯回歸和線性回歸的異同：
  • 區(qū)別：最本質(zhì)的區(qū)別是，邏輯回歸處理的是分類問題，線性回歸處理的是回歸問題。邏輯回歸中，因變量取值是一個二元分布，模型學習得出的是E[y|x;\theta]，即給定自變量和超參數(shù)后，得到因變量的期望，并基于此期望來處理預測分類問題。而線性回歸中實際上求解的是y'=\theta^Tx，是對我們假設的真實關(guān)系y=\theta^Tx+\epsilon的一個近似，其中\epsilon代表誤差項，我們使用這個近似項來處理回歸問題。
    還有一個很大的區(qū)別是，邏輯回歸中的因變量是離散的，線性回歸中的因變量是連續(xù)的。并且在自變量x與超參數(shù)\theta確定的情況下，邏輯回歸可以看作廣義線性模型在因變量y服從二元分布時的一個特殊情況；而使用最小二乘法求解線性回歸時，我們認為因變量y服從正態(tài)分布。
  • 相同：兩者都使用了極大似然估計來對訓練樣本進行建模。線性回歸使用最小二乘法，實際上就是自變量x與超參數(shù)\theta確定，因變量y服從正態(tài)分布的假設下，使用極大似然估計的一個化簡；而邏輯回歸中通過對似然函數(shù)L(\theta)=\prod_{i=1}^{N}P(y_i|x_i;\theta)=\prod_{i=1}^{N}(\pi(x_i))^{y_i}(1-\pi(x_i))^{1-y_i}的學習，得到最佳參數(shù)\theta。
    在求解參數(shù)的過程中，都可以使用梯度下降的方法。
  1. 多項邏輯回歸：
  • 一個樣本只對應一個標簽時，可以假設每個樣本屬于不同標簽的概率服從幾何分布，使用多項邏輯回歸(Softmax Regression)來進行分類(存在一個Softmax)。
  • 一個樣本可能屬于多個標簽時，可以訓練k個二分類的邏輯回歸分類器，第i個分類器用以區(qū)分每個樣本是否可以歸為第i類。

3、決策樹

  1. 決策樹常用的啟發(fā)函數(shù)：
  • ID3：最大信息增益
    對于樣本集合D，類別數(shù)為K，數(shù)據(jù)集D的經(jīng)驗熵為H(D)=-\sum_{k=1}^{K}\frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|}其中C_k是樣本集合D屬于第k類的樣本子集，|C_k|表示該子集的元素個數(shù)，|D|表示樣本集合的元素個數(shù)。
    注：簡言之，數(shù)據(jù)集D的經(jīng)驗熵為，根據(jù)y的類別分的K個類的信息熵的和。
    然后計算某個特征A對于數(shù)據(jù)集D的經(jīng)驗條件熵H(D|A)為H(D|A)=\sum_{i=1}^{n}\frac{|D_i|}{|D|}H(D_i)=\sum_{i=1}^{n}\frac{|D_i|}{|D|}(-\sum_{k=1}^{K}\frac{|D_{ik}|}{|D_i|}log_2\frac{|D_{ik}|}{|D_i|})其中D_i表示D中特征A取第i個值的樣本子集，D_{ik}表示D_i中屬于第k類的樣本子集。
    注：簡言之，特征A對于數(shù)據(jù)集D的經(jīng)驗條件熵H(D|A)為，根據(jù)特征A分類之后，A的每個類分別求該小數(shù)據(jù)集的經(jīng)驗熵H(D_i)，再根據(jù)A每個類的占比對經(jīng)驗熵H(D_i)加權(quán)平均。
    于是信息增益g(D,A)可以表示為兩者之差，可得g(D,A)=H(D)-H(D|A)
    注：簡言之，信息增益就是根據(jù)特征A劃分之后，每個劃分D_i中y的類別是不是更集中了，也就是給定條件以后不確定性減少的程度。
  • C4.5：最大信息增益比
    特征A對于數(shù)據(jù)集D的信息增益比定義為g_R(D,A)=\frac{g(D,A)}{H_A(D)}其中H_A(D)=-\sum_{i=1}^{n}\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}，H_A(D)稱為數(shù)據(jù)集D關(guān)于A的取值熵。
  • CART樹：最大基尼指數(shù)(Gini)
    Gini描述的是數(shù)據(jù)的純度Gini(D)=1-\sum_{i=1}^{n}(\frac{C_k}{D})^2特征A的Gini指數(shù)定義為Gini(D|A)=\sum_{i=1}^{n}\frac{|D_i|}{|D|}Gini(D_i)
    注：Gini指數(shù)的計算方法是，選取特征A的某一個取值，如果特征A有三個取值1、2、3，那么選取A為1這個值，將2、3全看作非1，計算將數(shù)據(jù)集分成兩個部分之后，每個部分數(shù)據(jù)集的Gini指數(shù)的加權(quán)平均。數(shù)據(jù)集的Gini指數(shù)是1減根據(jù)y劃分的標簽占比平方和的差。
  1. 三種決策樹構(gòu)造準則的比較：
  • ID3采用信息增益作為評價指標，會傾向于取值較多的特征。因為，信息增益反映的是給定條件以后不確定性減少的程度。C4.5實際上是對ID3的優(yōu)化，通過引入信息增益比，一定程度上對取值比較多的特征進行懲罰，避免ID3出現(xiàn)過擬合的特征，提升決策樹的泛化能力。
  • 從樣本類型的角度，ID3只能處理離散型變量，而C4.5和CART樹都可以處理連續(xù)型變量。C4.5會排序找到切分點，將連續(xù)變量轉(zhuǎn)換為多個取值區(qū)間的離散型變量，CART每次會對特征進行二值劃分，適用于連續(xù)變量。
  • 從應用角度，ID3和C4.5只能用于分類，CART樹可以用于分類和回歸。
  • 從實現(xiàn)細節(jié)、優(yōu)化過程等角度，ID3對樣本特征缺失值比較敏感，而C4.5和CART樹都可以對缺失值進行不同方式的處理。
    ID3和C4.5可以產(chǎn)生多叉分支，且每個特征在層級之間不會復用。CART樹是二叉樹，每個特征可以被重復利用。
    ID3和C4.5通過剪枝來權(quán)衡樹的準確性和泛化性能，CART樹枝節(jié)利用全部數(shù)據(jù)發(fā)現(xiàn)所有可能的樹結(jié)構(gòu)進行對比。
  1. 前剪枝：在生成決策樹的過程中提前停止樹的增長。核心思想是在樹中節(jié)點進行擴展之前，先計算當前的劃分是否能帶來模型泛化性能的提升，如果不能則不再繼續(xù)生成子樹。
  • 前剪枝停止決策樹生長的幾種方法：
    (1) 當樹達到一定深度時停止生長。
    (2) 當?shù)竭_當前節(jié)點的樣本數(shù)量小于某個閾值時停止生長。
    (3) 計算每次分類對測試集的準確率提升，當小于某個閾值時停止生長。
  • 前剪枝的優(yōu)缺點：
    優(yōu)點：簡單高效，適合解決大規(guī)模問題。
    缺點：
    (1) 深度和閾值這些值很難準確估計，針對不同問題會有很大差別。
    (2) 前剪枝存在一定局限性，有欠擬合的風險，雖然當前的劃分會導致測試集準確率下降，可能在后面會有顯著上升。
  1. 后剪枝：在已生成的過擬合決策樹上進行剪枝。核心思想是讓算法生成一棵完全生長的決策樹，然后從底層向上計算是否剪枝。(剪枝是將子樹刪除，用一個葉子節(jié)點代替，節(jié)點類別按多數(shù)投票)如果剪枝之后準確率有提升，則剪枝。
  • 后剪枝的優(yōu)缺點：
    優(yōu)點：通常可以得到泛化能力更強的決策樹。
    缺點：時間開銷大。
  • 常用的后剪枝方法：
    (1) 錯誤率降低剪枝(Reduced Error Pruning，REP)
    (2) 悲觀剪枝(Pessimistic Error Pruning，PEP)
    (3)代價復雜度剪枝(Cost Complexity Pruning，CCP)
    (4)最小誤差剪枝(Minimum Error Pruning，MEP)
    (5)CVP(Critical Value Pruning)
    (6)OOP(Optimal Pruning)
  • 代價復雜度剪枝CCP的步驟。
    (1) 從完整決策樹T_0開始，生成一個子樹序列\{T_0,T_1,...,T_n\}，其中T_{i+1}由T_i生成，T_n為根節(jié)點。(也就是說計算剪枝之后誤差增加率，選最小的節(jié)點剪枝代替，一直剪枝，直到最后只剩下根節(jié)點，記錄下這個過程中所有的樹的樣子)
    (2)在子樹序列中，根據(jù)真實誤差選擇最佳的決策樹。CCP對于從子樹序列中選最優(yōu)樹有兩種方法：1.從子樹序列中選擇最佳決策樹。由于不是在所有可能的子樹中尋找，性能上會有一定不足。2.基于k折交叉驗證，將數(shù)據(jù)集分成k份，前k-1份用于生成決策樹，最后一份用于剪枝。重復進行N次，再從N個子樹中選擇最優(yōu)子樹。

小結(jié)

這一章的推導并不多，如果要看詳細的算法推導還是要看下《統(tǒng)計學習方法》。這章在講得非常通俗易懂的同時，對知識點也挖得很深，例如SVM，對統(tǒng)計學方法有很好的補充。這章讓我很深刻的就是“在空間上線性可分的兩類點，分別向SVM超平面上做投影，這些點在超平面上的投影仍然是線性可分的嗎？”這個問題，超出了我目前的知識范圍，還是要多熟悉原理才行。

結(jié)尾

如果您發(fā)現(xiàn)我的文章有任何錯誤，或?qū)ξ业奈恼掠惺裁春玫慕ㄗh，請聯(lián)系我！如果您喜歡我的文章，請點喜歡~*我是藍白絳，感謝你的閱讀！

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容