Bài 38: Bias-Variance Tradeoff

Bài 37 mô tả hai triệu chứng đối lập:

• Overfit — train error thấp, test error cao. Model nhớ noise.
• Underfit — cả train và test error đều cao. Model quá đơn giản.

Cả hai là quan sát empirical. Bài này nhìn cùng hiện tượng dưới góc lý thuyết: expected test error có thể tách thành ba thành phần — bias², variance, và noise không khử được. Mỗi triệu chứng overfit/underfit tương ứng với một component chiếm ưu thế. Khi đã decompose được, ta biết phải vặn knob nào (complexity, regularization, data, ensemble) để xử lý.

Giả sử data sinh ra theo:

\[ y = f(\mathbf{x}) + \varepsilon, \quad \mathbb{E}[\varepsilon] = 0, \quad \operatorname{Var}(\varepsilon) = \sigma^2 \]

Trong đó \( f \) là hàm thật (không biết), \( \varepsilon \) là noise độc lập với \( \mathbf{x} \). Train một dataset \( D \) (sample từ phân phối chung) ra estimator \( \hat{f}_D \). Tại một điểm test cố định \( \mathbf{x}_0 \), expected squared error — lấy kỳ vọng theo cả train set \( D \) lẫn noise \( \varepsilon \) ở \( \mathbf{x}_0 \) — có decomposition:

\[ \mathbb{E}_{D, \varepsilon}\left[\left(y - \hat{f}_D(\mathbf{x}_0)\right)^2\right] = \underbrace{\bigl(\mathbb{E}_D[\hat{f}_D(\mathbf{x}_0)] - f(\mathbf{x}_0)\bigr)^2}_{\text{Bias}^2} + \underbrace{\operatorname{Var}_D\!\bigl(\hat{f}_D(\mathbf{x}_0)\bigr)}_{\text{Variance}} + \underbrace{\sigma^2}_{\text{Noise}} \]

Ba thành phần đại diện ba nguồn lỗi khác nhau:

• Bias² — chênh lệch giữa kỳ vọng dự đoán của model (trung bình qua nhiều train set) và giá trị thật \( f(\mathbf{x}_0) \). Sai số do giới hạn capacity của họ model.
• Variance — mức độ dao động của dự đoán quanh kỳ vọng của nó, khi thay đổi train set. Sai số do nhạy cảm với data ngẫu nhiên.
• Noise \( \sigma^2 \) — phương sai của \( \varepsilon \). Đây là irreducible error — không estimator nào khử được (vì \( \varepsilon \) độc lập với mọi \( \mathbf{x} \)).

Bias và variance là phần reducible — phụ thuộc lựa chọn model. Cả khoá học ML cổ điển xoay quanh tối ưu hai số này.

Chứng minh decomposition: triển khai \( (y - \hat{f})^2 \), cộng trừ \( \mathbb{E}_D[\hat{f}] \), dùng \( \mathbb{E}[\varepsilon] = 0 \) và độc lập của \( \varepsilon \) với \( \hat{f}_D \). Các cross-term triệt tiêu, còn đúng ba số hạng. Chi tiết có trong ESL Chương 7.3 hoặc ISL Chương 2.2.

Bias tại điểm \( \mathbf{x}_0 \):

\[ \operatorname{Bias}(\hat{f}_D(\mathbf{x}_0)) = \mathbb{E}_D[\hat{f}_D(\mathbf{x}_0)] - f(\mathbf{x}_0) \]

Có thể đọc: "trung bình qua mọi train set có thể, model dự đoán lệch bao nhiêu so với hàm thật". Bias cao khi:

• Họ model không chứa được \( f \). Ví dụ \( f \) là sin, ta fit linear — bất kể \( D \) thế nào, đường thẳng tốt nhất cũng không thể bằng sin.
• Capacity bị siết quá chặt bởi regularization mạnh — model bị "kéo" về 0 dù data nói khác.
• Feature thiếu — model không có đủ thông tin để mô tả \( f \).

Underfit chính là trường hợp bias chiếm ưu thế: dù trung bình hoá nhiều train set, dự đoán vẫn lệch xa hàm thật. Tăng số sample không cứu được bias — đó là structural error của họ model.

Một cách hình dung: bias là khoảng cách giữa tâm của đám mây dự đoán và mục tiêu. Bias cao = đám mây bắn lệch tâm, dù có chụm hay không.

Variance tại \( \mathbf{x}_0 \):

\[ \operatorname{Var}_D(\hat{f}_D(\mathbf{x}_0)) = \mathbb{E}_D\!\left[\bigl(\hat{f}_D(\mathbf{x}_0) - \mathbb{E}_D[\hat{f}_D(\mathbf{x}_0)]\bigr)^2\right] \]

Đo "đám mây dự đoán" phân tán quanh tâm của nó như thế nào khi train set thay đổi. Variance cao khi:

• Model có capacity rất cao (deep tree, polynomial bậc cao, KNN với \( k = 1 \), NN nhiều tham số) — fit được mọi train set tới sát noise.
• Train set nhỏ — mỗi resample khác nhau khá nhiều, predict cũng dao động mạnh.
• Không có regularization để kiềm hãm coefficient.

Overfit là trường hợp variance chiếm ưu thế: trên một train set cụ thể, model nhớ noise của riêng set đó; đổi sang train set khác, model sẽ nhớ noise khác — predict tại cùng \( \mathbf{x}_0 \) nhảy lung tung.

Đám mây dự đoán trong trường hợp variance cao: có thể trung bình ra đúng tâm (bias thấp), nhưng từng phát một thì văng xa.

Hai thành phần reducible đi ngược chiều khi vặn knob complexity của model:

• Tăng complexity (polynomial bậc cao hơn, tree sâu hơn, NN nhiều layer hơn, regularization yếu hơn) → bias giảm (model fit được hàm thật tốt hơn) → variance tăng (model nhạy với noise hơn).
• Giảm complexity → bias tăng → variance giảm.

Tổng expected error có dạng chữ U (theo complexity) trong góc nhìn cổ điển:

\[ \text{Total error}(c) = \operatorname{Bias}^2(c) + \operatorname{Var}(c) + \sigma^2 \]

Trong đó \( c \) là một thước đo complexity (degree, depth, số neuron, \( 1/\alpha \) của regularization, \( 1/k \) của KNN...). Bias² giảm đơn điệu theo \( c \), variance tăng đơn điệu theo \( c \), tổng có cực tiểu ở đâu đó giữa — chính là sweet spot mà cross-validation đi tìm.

Hai chú ý:

• \( \sigma^2 \) là sàn cứng. Test error giỏi nhất cũng không thấp hơn \( \sigma^2 \). Nếu đạt được \( \approx \sigma^2 \), model đã coi như tối ưu trên tập feature đang có.
• Sweet spot phụ thuộc cả lượng data. Tăng \( n \) làm cong variance dịch sang phải — model phức tạp hơn lúc này lại an toàn.

Cách hình dung kinh điển — bia phi tiêu. Tâm bia = \( f(\mathbf{x}_0) \). Mỗi train set sinh ra một estimator \( \hat{f}_D \), tương ứng một phát phi tiêu trúng vào bia. Bốn kịch bản:

• Low bias + low variance — phát rơi chụm, gần tâm. Đây là model tốt: trung bình đúng và ổn định.
• High bias + low variance — phát rơi chụm nhưng lệch tâm. Ví dụ linear cho data sin: mọi train set đều cho đường thẳng tương tự, tất cả cùng lệch.
• Low bias + high variance — phát phân tán quanh tâm. Ví dụ tree sâu không prune: trung bình hoá nhiều tree (chính là Random Forest) ra gần đúng, nhưng từng tree một thì văng xa.
• High bias + high variance — phát phân tán và lệch tâm. Kịch bản tệ nhất, thường gặp khi model vừa sai cấu trúc vừa quá nhạy với data.

Khi nhìn learning curve ở Bài 37, "khoảng cách train–test cao" tương ứng variance cao; "cả hai cao" tương ứng bias cao. Dartboard là visualization 2D tương đương của cùng decomposition.

Khi diagnose ra bias cao (train error cao, gần bằng test error, learning curve plateau sớm):

• Tăng model complexity — chuyển sang họ model có capacity lớn hơn. Linear → polynomial; shallow tree → deeper tree; small NN → wider/deeper NN.
• Thêm feature — tạo interaction term, polynomial feature, feature từ domain knowledge. Cùng họ model nhưng input giàu hơn → bias giảm vì model có đủ thông tin để biểu diễn \( f \).
• Giảm regularization — \( \alpha \) Ridge/Lasso nhỏ lại; cho phép tree mọc sâu hơn; nới max_depth, min_samples_leaf; tăng \( C \) trong LogisticRegression/SVM.
• Đổi sang model có inductive bias phù hợp hơn — vd data có cấu trúc spatial → CNN; sequential → RNN/Transformer; tabular → gradient boosting. Đây không phải "tăng capacity thuần", mà thay đổi cấu trúc giả định.

Lưu ý: thêm data thường không giảm bias. Bias là sai số có hệ thống của họ model — dù \( n \to \infty \), linear vẫn không fit nổi sin.

Khi diagnose ra variance cao (train error rất thấp, test error cao, learning curve còn dốc):

• Đơn giản hoá model — giảm degree, giảm depth, giảm số layer/neuron. Đánh đổi: bias tăng nhẹ.
• Thêm data — variance ~ \( 1/n \) trong nhiều estimator. Nếu khả thi, đây là cách "free lunch" nhất: giảm variance mà không phải tăng bias.
• Regularization — Ridge/Lasso (Bài 21), weight decay, dropout (NN). Thêm penalty kéo coefficient/weight về 0 → giảm dao động giữa các train set.
• Ensemble bằng bagging — trung bình hoá predict của nhiều model train trên bootstrap sample. Variance của trung bình giảm theo công thức \( \operatorname{Var}(\bar{X}) = \operatorname{Var}(X)/m \) (khi independent). Random Forest (Bài 29) là ví dụ điển hình.
• Early stopping trong gradient boosting/NN — dừng train trước khi nhớ noise.
• Data augmentation — tăng diversity của train set một cách synthetic; gián tiếp giống thêm data.

Nguyên tắc chung: giảm variance trả giá bằng bias (trừ khi thêm data thật hoặc augmentation hợp lệ). Lựa chọn cụ thể tuỳ điều kiện thực tế — data có sẵn không, compute có sẵn không.

Hai họ ensemble phổ biến đã gặp ở Bài 29 và Bài 30 thực ra giải hai bài toán đối ngẫu:

• Bagging (Random Forest) — base learner là tree sâu, capacity lớn → mỗi tree có bias thấp, variance cao. Trung bình \( m \) tree làm variance giảm còn ~ \( \operatorname{Var}/m \) (giảm thêm bằng feature subsampling để decorrelate), bias giữ nguyên xấp xỉ. Bagging chủ yếu giảm variance.
• Boosting (Gradient Boosting, XGBoost) — base learner là tree nông (depth 3–6), bias cao, variance thấp. Mỗi vòng boost fit phần residual chưa explain → giảm bias từng bước. Nếu boost quá nhiều vòng, variance có thể tăng — đó là lý do cần early stopping và shrinkage (learning rate < 1). Boosting chủ yếu giảm bias.

Hệ quả thực hành:

• Random Forest thường robust với hyperparameter, ít cần tune; vì hướng tới giảm variance, kết quả ổn định.
• Gradient Boosting nhạy hơn với learning rate, số rounds, max_depth — vì nó vừa giảm bias vừa có thể vô tình tăng variance.

Khi diagnose model thấy bias cao, boosting thường là lựa chọn đầu tiên; variance cao thì bagging hoặc tăng regularization.

Mỗi model có một (hoặc vài) knob điều khiển complexity. Vặn về phía nào ra bias cao / variance cao tổng kết như sau:

• Polynomial Regression (Bài 20) — degree. Thấp (1, 2) = high bias. Cao (10+) = high variance.
• Decision Tree (Bài 28) — max_depth, min_samples_leaf. Tree nông / leaf lớn = high bias. Tree sâu / leaf nhỏ = high variance.
• KNN (Bài 27) — n_neighbors \( k \). \( k \) lớn (đến mức smoothing toàn dataset) = high bias. \( k = 1 \) = high variance (model fit từng điểm).
• Ridge/Lasso (Bài 21) — alpha. \( \alpha \) lớn = high bias (coefficient co về 0). \( \alpha \to 0 \) = trở về OLS, variance cao nếu \( d \) lớn.
• Logistic Regression / SVM — C = 1/alpha. \( C \) nhỏ = high bias. \( C \) lớn = high variance.
• Neural Network — số layer, số neuron, dropout. Nhỏ = high bias. Lớn không regularize = high variance (trong góc cổ điển; xem mục 11 cho góc hiện đại).
• Gradient Boosting — số n_estimators, learning_rate, max_depth. Ít vòng + LR nhỏ + tree nông = high bias. Nhiều vòng + LR cao + tree sâu = high variance.

Cùng một dataset, vặn cùng một hướng trên các model khác nhau cho ra hiệu ứng tương tự. Đây là lý do bias-variance là khung chung — không chỉ áp dụng cho regression linear.

Khung bias-variance cổ điển dự đoán: complexity tăng quá ngưỡng, variance tăng vô hạn, test error tăng theo. Nhưng quan sát trong deep learning những năm gần đây mâu thuẫn với điều đó.

Belkin et al. 2019 (Reconciling modern machine learning practice and the classical bias–variance trade-off) đặt tên hiện tượng là double descent:

• Khi complexity tăng từ rất nhỏ đến interpolation threshold (số tham số ≈ số sample), test error đi theo chữ U cổ điển — đầu tiên giảm, sau đó tăng do variance bùng nổ.
• Khi complexity vượt qua interpolation threshold, test error giảm tiếp — descent lần hai. Một số trường hợp còn đạt thấp hơn cả minimum của chữ U.

Hiện tượng được observed empirically trong:

• Neural network rất lớn (overparameterized regime).
• Random feature models, kernel methods khi tăng số basis.
• Một số tree ensemble lớn.

Giải thích trực giác: ở regime overparameterized, optimizer ngầm chọn nghiệm "smoothest" trong số nhiều nghiệm interpolating — đó là implicit regularization của gradient descent. Variance không bùng nổ vì nghiệm vẫn smooth.

Hệ quả với khung lý thuyết bài này:

• Trong ML cổ điển (linear, tree, KNN, kernel với số sample > tham số), bias-variance cổ điển vẫn mô tả tốt hành vi. Cross-validation tìm sweet spot vẫn là cách chuẩn.
• Trong deep learning với model rất lớn, đừng quá tin rằng "phải" tìm sweet spot cổ điển — model lớn hơn có thể tốt hơn dù vượt qua threshold. Quyết định bằng test error thực nghiệm, không bằng "số tham số < số sample" như rule of thumb cũ.

Series Deep Learning sẽ chi tiết hơn về regime này. Hiện tại chỉ cần biết: khung cổ điển có giới hạn, áp dụng đúng phạm vi.

Không có công thức đóng cho complexity tối ưu — \( f \) thật không biết, \( \sigma^2 \) cũng không biết chính xác. Quy trình thực hành:

• Tách train / val / test (Bài 6) hoặc dùng cross-validation (Bài 39 ngay sau bài này) để estimate test error mà không nhìn vào test set thật.
• Quét hyperparameter điều khiển complexity trên thang log (vd \( \alpha \in [10^{-3}, 10^3] \), max_depth \( \in [1, 30] \)). Plot validation error theo hyperparameter — nhìn ra vùng underfit, vùng overfit, sweet spot.
• Tham số đáng tune nhất theo model: Ridge/Lasso → \( \alpha \); Tree/Forest → max_depth, min_samples_leaf, max_features; Boosting → learning_rate, n_estimators, max_depth; KNN → \( k \); SVM → \( C \), gamma.
• Empirical baseline theo họ model:

• Linear Regression default — thường high bias trên data phi tuyến.
• Decision Tree không prune — thường high variance.
• Random Forest default — bias trung bình, variance thấp.
• Gradient Boosting tune kỹ — thường có MSE thấp nhất trong họ tabular, cả bias và variance đều ổn nếu early stopping đúng.
• Deep NN đủ dữ liệu và regularize — low bias, low variance; thiếu data thì variance bùng.

Khi không chắc, chạy nhiều estimator song song (Linear / RF / GBM) với CV tune, so sánh — chiến lược này cost thấp và đưa ra picture rõ ràng.

Decompose empirical bằng bootstrap: sinh nhiều train set, train một model trên mỗi set, đo dự đoán tại các điểm test cố định, tính bias² và variance theo công thức ở mục 2.

import numpy as np
from sklearn.preprocessing import PolynomialFeatures
from sklearn.linear_model import LinearRegression
from sklearn.pipeline import make_pipeline

rng = np.random.default_rng(0)

def true_f(x):
    return np.sin(1.5 * np.pi * x)

def sample_data(n=30, sigma=0.3):
    x = rng.uniform(0, 1, size=n)
    y = true_f(x) + rng.normal(0, sigma, size=n)
    return x.reshape(-1, 1), y

# Test grid co dinh
x_test = np.linspace(0, 1, 200).reshape(-1, 1)
f_test = true_f(x_test.ravel())

def decompose(degree, n_trials=200, n_train=30, sigma=0.3):
    preds = np.zeros((n_trials, len(x_test)))
    for t in range(n_trials):
        X_tr, y_tr = sample_data(n=n_train, sigma=sigma)
        model = make_pipeline(
            PolynomialFeatures(degree, include_bias=False),
            LinearRegression(),
        )
        model.fit(X_tr, y_tr)
        preds[t] = model.predict(x_test)

    mean_pred = preds.mean(axis=0)
    bias2 = np.mean((mean_pred - f_test) ** 2)
    variance = np.mean(preds.var(axis=0))
    noise = sigma ** 2
    total = bias2 + variance + noise
    return bias2, variance, noise, total

print(f"{'deg':>3s}  {'bias2':>7s}  {'var':>7s}  {'noise':>7s}  {'total':>7s}")
for d in [1, 3, 9, 15]:
    b2, v, n, t = decompose(degree=d)
    print(f"{d:>3d}  {b2:>7.4f}  {v:>7.4f}  {n:>7.4f}  {t:>7.4f}")

Output điển hình (con số tuỳ seed):

deg    bias2      var    noise    total
  1   0.2316   0.0048   0.0900   0.3264
  3   0.0145   0.0211   0.0900   0.1256
  9   0.0098   0.0573   0.0900   0.1571
 15   0.0094   0.1284   0.0900   0.2278

Đọc kết quả:

• degree 1: bias² rất cao (linear không fit được sin), variance gần 0. Underfit.
• degree 3: bias² tụt mạnh, variance tăng nhẹ. Sweet spot trong grid này.
• degree 9 → 15: bias² gần bão hoà (đã đủ flexible), variance tăng theo lũy thừa. Overfit.
• Noise \( \sigma^2 = 0.09 \) — sàn cứng, không model nào ở đây xuống thấp hơn.

Pattern này khớp chính xác đường cong chữ U cổ điển mô tả ở mục 5.

Bài 1 — Decompose trên 3 model. Dùng data sinh từ true_f mục 13 (sin + noise). Train ba model trên cùng dataset cố định: LinearRegression, PolynomialFeatures(3) + LinearRegression, PolynomialFeatures(15) + LinearRegression. Bootstrap 200 train set với \( n = 30 \), decompose bias², variance, total. Model nào sweet spot? Bias² của linear cao gấp bao nhiêu lần bias² của poly-15?

Bài 2 — Variance giảm theo \( n \). Cố định degree=9. Chạy decompose với \( n_{\text{train}} \in \{30, 100, 300, 1000\} \). Plot variance theo \( n \). Có giảm theo dạng ~ \( 1/n \) không? Bias² có thay đổi không (lý thuyết: không phụ thuộc \( n \), chỉ phụ thuộc họ model)?

Bài 3 — Random Forest vs single Decision Tree. Trên cùng data sin + noise (\( n = 30 \), 1D, scale như mục 13), bootstrap 200 lần, mỗi lần train hai estimator: DecisionTreeRegressor() (default, không giới hạn depth) và RandomForestRegressor(n_estimators=100). Decompose bias² và variance cho cả hai. RF có thực sự giảm variance không? Bias² của RF có cao hơn không?

Bài 4 — Regularization và bias. Polynomial degree 15 trên data mục 13, nhưng thay LinearRegression bằng Ridge(alpha). Decompose với \( \alpha \in \{0, 0.001, 0.1, 10, 1000\} \). Quan sát: \( \alpha \) tăng → variance giảm, bias² tăng. Vẽ Bias²-Variance theo \( \alpha \), tìm sweet spot.

Bài 5 — KNN qua \( k \). Trên data mục 13, decompose KNeighborsRegressor(n_neighbors=k) với \( k \in \{1, 3, 7, 15, 25\} \). Confirm: \( k = 1 \) có variance cao nhất, \( k = 25 \) có bias cao nhất. So sánh sweet spot của KNN với sweet spot của polynomial ở Bài 1.

Gợi ý đáp án Bài 3: Decision Tree single thường có variance ~ 0.1–0.2 trên setup này, RF với 100 cây giảm xuống ~ 0.01–0.03. Bias² của RF tăng nhẹ (vài %) hoặc gần bằng — đúng dự đoán "bagging giảm variance, ít ảnh hưởng bias".

Bài 39: Cross-Validation — phương pháp chuẩn để estimate test error và chọn hyperparameter trong khung bias-variance vừa dựng. K-Fold, Stratified K-Fold, Leave-One-Out, và lý do vì sao một validation set duy nhất chưa đủ tin cậy khi tune.