Deep learning - Probability and Information theories VI

Deep learning - Probability and Information theories VI

Application:Decision tree(決策樹) and random forest(隨機森林)

  • 廣泛使用的一種歸納推理演算法
  • 對於干擾直相當敏感

Impurity measure(亂度的測量)

argmaxj,v(Impurity(Xparent)Impurity(Xleft,Xright))

亂度為熵的非正式定義

  • 給定一組標記過的樣本資料組
    • X={(x(i),y(i))}Ni=1
    • x 為一個向量, jth 維度該樣本的一個特徵(Attribute)
      • 向量元素 xj 代表著一個該資料對應該特徵的一個狀態(State of j-th attribute)
    • yx 經過一個隨機變數 X 所對應的一個標記狀態
      • 由於隨機變數 X 是人決定的,所以可以將這個對應稱為一種標記
  • 欲經一樹狀函數 f規則),將樣本的特徵狀態 x(i) 可以映射到人為標記狀態 y(i) (Label)
    • f(x(i))=y(i)
1556032997160
  • Xparent 為決策樹裡其中一個父節點
    • 代表一組子樣本資料
      • XparentX
  • XleftXright 為對應於上述父節點的左右子節點
    • 代表一組子樣本資料
      • XleftXXrightX
      • Xleft+Xright=Xparent
  • Impurity(Xparent)=H[YEmpirical(Xparent)]

    • 「父節點的亂度」為 YEmpirical(Xparent)
    • PY(y)=Xparenty
  • Impurity(Xleft,Xright)=i=left,right|X(i)||Xparent|H[YEmpirical(X(i))]

    • |X(i)| 為該樣本資料組的數量
    • 「子節點的亂度」為左右子點對 YEmpirical(X(i)) 的熵,並依比對父點的資料量比例加總
      • 「子節點的亂度」≦「父節點的亂度」
      • 目標是找到一種父節點的資料分類方法,將「子節點的亂度」最小化
  • Impurity(Xparent)Impurity(Xleft,Xright) 稱作「資訊獲利」(Information gain)

    • 越大代表「子節點的亂度」越小
    • 資料分類方法的一種效能評鑑
  • (j,v) :斷點

    • x 還沒判斷的特徵空間中找到 jth 維度,選擇一個定值 v

    • 節點中的資料必須符合 Rule 的規則

    • 將父節點 Xparent={(x(i),y(i))Rule} 分支為兩個節點

      • Xleft={(x(i),y(i))Rule{x(i)j<v}}
      • Xright={(x(i),y(i))Rule{x(i)jv}}
1556075449719

Decision tree

Training a decision tree

  1. 建構一根節點 {(x(i),y(i))Rule=}
    • 節點中的資料必須符合 Rule 的規則
    • 最開始不設定規則 $$,所以此點資料等於 X
  2. 往下分支兩個子節點 XleftXright
    • argmaxj,v(Impurity(Xparent)Impurity(Xleft,Xright)) 為依據,找到符合的 Rule
    • 對其子節點遞迴此步驟,直到該節點的亂度等於 0(Pure),也就是其節點的人為標記狀態全部相等

Random forests

隨機森林為多個決策樹所構成

  • 決策樹模型可能會被訓練得非常高
    • 越高的節點其 Rule 會越嚴格
    • 訓練資料樣本可以判斷很好,但是在測試資料樣本最壞可能完全無法利用
    • 解決此問題讓決策樹可以更廣泛應用(Generalizability)
      • 剪枝(Pruning):限制決策樹的高度,但可能葉節點中的標記狀態不會全部相等
      • 隨機森林:多棵剪枝過的決策樹之集成
  • 機器學習中的「集成」(Ensemble)
    • 一般機器學習演算法只使用單一模型來學習,可能在該樣本之外會無法利用
    • 結合多個弱機器學習以建構一個強穩的模型,避免過適現象(Overfit)的發生

Training a random forest

  1. 取得一個自助樣本(Bootstrap sample)
    • 自助樣本:在原始的訓練資料集中隨機挑選 M 個樣本(挑選過可以重新再挑選)
  2. 使用自助養本,訓練過程中
    1. 隨機挑選 K 個特徵
    2. 在該範圍找到最好的斷點 (j,v) 來分支
  3. 重複第一第二步得到 T 個決策樹
  • T 個決策樹以多數決(Majority vote)來判斷測試資料樣本
    • 每個決策樹對樣本有不同的見解,取其多數以判斷
  • 隨機森林的訓練與決策樹的訓練有些許的不同
    • 第一步與第二之一步
1556079393095
1556079400721