NTU 機器學習作業：Decision Stump 實作與多維擴展

問題背景

本文記錄 NTU 機器學習課程（林軒田教授）第 16~20 題的實作過程。核心任務為實作 Decision Stump（決策樹桩），並在一維與九維資料集上驗證 E_in 與 E_out。

一維 Decision Stump（Q16~18）

假設函數

h(x) = s * sign(x - θ)，其中 s ∈ {+1, -1}，θ 為閾值。

演算法流程

1. 生成 20 筆 [-1, 1] 均勻分布樣本，排序。
2. 依 f(x) = sign(x) 標記，並以 20% 機率翻轉標籤。
3. 枚舉所有相鄰樣本中點作為候選 θ，分別計算 s = +1 與 s = -1 的 E_in，取最小者。
4. 重複 5000 次實驗，統計平均 E_in 與理論 E_out。

關鍵程式碼片段

double getMinErrIn(vector<double>& inputVec, vector<int>& outputVec, Hypothesis &hypo, double &bestThres) {
    double minErrIn = 1.0;
    for (int i = 0; i < SAMPLE_SIZE - 1; ++i) {
        hypo.threshold = (inputVec[i] + inputVec[i+1]) / 2.0;
        double curErrIn = calErrInSample(inputVec, outputVec, hypo);
        if (curErrIn < minErrIn) { minErrIn = curErrIn; bestThres = hypo.threshold; }
    }
    return minErrIn;
}

實驗結果

多維擴展（Q19~20）

將 Decision Stump 推廣至 9 維：對每一維獨立執行一維演算法，選擇 E_in 最小的維度，並在測試集上計算對應的 E_out。

核心邏輯

void decisionStump(vector<record>& trainingSet, vector<record>& testSet, vector<Hypothesis>& hypo) {
    double minErrIn = 1.1; int minErrInDem;
    for (int dem = 0; dem < DEMENSION; ++dem) {
        vector<singleDemensionRecord> singleDemensionVec;
        getInputByDemension(trainingSet, singleDemensionVec, dem+1);
        // 對該維度跑一維 decision stump
        hypo[dem].coef = 1;
        double minErrInPositive = getMinErrIn(singleDemensionVec, hypo, dem+1, bestThresPositive);
        hypo[dem].coef = -1;
        double minErrInNegtive = getMinErrIn(singleDemensionVec, hypo, dem+1, bestThresNegtive);
        // 取較佳 s 與 θ
        // ...
        if (minErrIn > curMinErrIn) { minErrIn = curMinErrIn; minErrInDem = dem+1; }
    }
    // 在測試集上計算 minErrInDem 維度的 E_out
    vector<singleDemensionRecord> singleDemensionTestVec;
    getInputByDemension(testSet, singleDemensionTestVec, minErrInDem);
    cout << "min E-out = " << calErr(singleDemensionTestVec, hypo, minErrInDem) << endl;
}

測試結果

心得

Decision Stump 是 Boosting（如 AdaBoost）的基礎弱分類器。一維時僅需枚舉閾值；多維時獨立處理各維度再取最優。實作細節包括：樣本排序、閾值取中點、正負 s 皆嘗試、理論 E_out 公式驗證。