Ch3 Classification & Model Overfitting

Model Overfitting

  • 分類誤差 :
    • Training Errors
    • Test Errors
    • Generalization Errors (推論錯誤) : 模型對來自相同分佈隨機選擇記錄的預期誤差
  • Model Underfitting : Training & Test Errors 都很大 → 模型太簡單
  • Model Overfitting : Training Errors 很小 & Test Errors 很大 → 模型太複雜
    • 會讓 Decision Tree 變過於複雜
    • 形成原因 :
      1. Trainng Data 太少 → Under-representative (無代表性) → 當 Node 數↑，Overfitting 越嚴重
        • 解法 : 增加 Training Data 比例
      2. Multiple Comparison Procedure : 誤將不相關的 Component 加進 Mode l中，e.g. noise
  • Model Selection :
    • 目的 : 避免讓 Model 過於複雜 → 防止 Overfitting
    • 需要估計 Genralization Errors :
      1. 使用 Validation Set (驗證資料集) :
        • Def : 估計 Genralization Error
        • 跟 Test Data Set 不同
        • 缺點 : Training Data 變少
      2. 考量 Model Complexity : Occam’s Razor 理論
        • 兩個類似的 Generalization Error，會選較簡單的 Model
        • 在評估一 Model 時，要考量其 Complexity
          • $\color{blue}{\text{Gen. Error} = \text{Train Error}+\alpha \times \text{Complexity}}$
        • Resubstitution Estimate(重新替代估計) : 為 Opimistic Error Estimate(樂觀誤差估計)，用 Training Error 當作 Gen. Error 的樂觀估計值
        • Pessimistic Error Estimate(悲觀誤差估計) : Leaf Node 數越多，Gen. Error 越高
          • $err_{gen}(T)=err(T)+\Omega \times \frac{k}{N_{train}}$
          • $k$ : Leaf Node 數、$N_{train}$ : Train Data 數
        • Minimum Description Length(MDL)
      3. 估計 Statistical Bounds
  • Pre-Pruning (預剪枝) :
    • Def : 在長成 tree 前暫停 Algorithm
    • 暫停條件 :
      • 所有 Instance 屬於同一 Class 時
      • 所有 Attribute value 皆相同時
      • Node 的良好度量低於 Threshold 時
      • 擴展當前 Node 不能提升 Improve measure 時
  • Post-Pruning (後剪枝) :
    • Def : 先把 tree 構造完畢，再由下往上剪
    • Subtree Replacement :
      • 若修剪後 Gen. Error 提升，則將子樹用一 Leaf Node 取代
      • Leaf Node 的 Class Label 由子樹中大多數的 instances 所決定
    • Subtree Raising :
      • 由最常使用的 branch 來取代子樹
  • Model Evaluation :
    • Def : 估計 Classifier 作用於 Test Data Set 中的成效
    • Holdout (最終驗證用) : $k$% Training、$(100-k)$% Testing，並反轉與重複
    • Cross Validation (交叉驗證) :
      • Def : 將資料切割成 $k$ 個 Disjoint Subsets
      • $k$-fold ($k$折驗證) : $(k-1)$ 個 Partition 當 Training、$1$ 個 Partition 當 Testing
        • $k$ 值會影響 Training Data 數量
      • Leave-one-out (留一驗證) : 當 $k$ 為樣本數時的 $k$-fold