Bài 41: Random Search và Bayesian Optimization sơ lược

Sau bài này, bạn sẽ:

• Hiểu vì sao Grid Search không scale khi search space lớn.
• Dùng được RandomizedSearchCV với loguniform, uniform, randint từ scipy.stats.
• Biết ý tưởng cốt lõi của Bayesian Optimization: surrogate model + acquisition function.
• Phân biệt được khi nào nên dùng Grid, Random, Bayesian, hay Successive Halving.
• Viết được vòng tune cơ bản với Optuna.

Bài 40 đã trình bày Grid Search: liệt kê tập giá trị cho mỗi hyperparameter, quét toàn bộ tích Descartes, đánh giá bằng cross-validation. Cách này phù hợp khi:

• Search space nhỏ (vài chục đến vài trăm tổ hợp).
• Mỗi fit nhanh (vài giây).
• Bạn muốn quét đủ để vẽ heatmap, phân tích landscape.

Nhưng Grid bộc lộ vài giới hạn ngay khi mở rộng:

• Combinatorial explosion: 5 hyperparameter × 5 giá trị/cái = 3 125 tổ hợp. Nhân với CV 5-fold = 15 625 fit. Mỗi fit 30 giây thì cần ~5 ngày.
• Phần lớn region không quan trọng: trong 3 125 tổ hợp, có thể chỉ vài chục tổ hợp nằm trong vùng cho score cao. Grid vẫn quét đều — phần lớn budget lãng phí.
• Discrete grid bỏ sót giá trị giữa: nếu grid là [0.01, 0.1, 1, 10, 100] mà tối ưu thật ở C=0.3, Grid sẽ không thấy.

Bài này giới thiệu 2 hướng thay thế: Random Search (sample ngẫu nhiên) và Bayesian Optimization (sample có học từ quá khứ).

Random Search hoán đổi 1 ý tưởng then chốt: thay vì khai báo tập giá trị rời rạc cho mỗi hyperparameter, bạn khai báo distribution mà từ đó sklearn sample ngẫu nhiên. Budget cố định bằng số lần sample (n_iter), không tăng exponential theo số hyperparameter.

Quy trình:

1. Với mỗi hyperparameter, định nghĩa distribution (uniform, log-uniform, integer uniform, list).
2. Lặp n_iter lần: sample 1 tổ hợp từ distribution → CV → ghi score.
3. Chọn tổ hợp có CV score cao nhất.

Bergstra & Bengio (2012, JMLR) chứng minh thực nghiệm: với cùng budget, Random Search thường tìm ra tổ hợp tốt nhanh hơn Grid Search khi search space ≥ 4-5 chiều. Paper này là tham chiếu kinh điển cho hyperparameter tuning, và là lý do Random Search trở thành default cho nhiều framework AutoML.

Một quan sát quan trọng từ Bergstra & Bengio: trong hầu hết bài toán, chỉ vài hyperparameter thật sự ảnh hưởng đến score; phần còn lại gần như không đổi. Với Random Forest, n_estimators và max_depth ảnh hưởng mạnh; min_samples_split ít hơn. Với XGBoost, learning_rate và max_depth dominate.

Khi đó:

• Grid Search: nếu quét 5 giá trị cho mỗi hyperparameter trong 5 chiều, mỗi giá trị của hyperparameter quan trọng được thử đúng 1 lần cho mỗi tổ hợp 4 chiều còn lại. Tức là chỉ có 5 giá trị unique cho hyperparameter quan trọng đó, dù chạy 3 125 fit.
• Random Search với 60 lần sample: hyperparameter quan trọng được thử ở 60 giá trị unique (gần như không trùng vì sample từ distribution liên tục). Cover vùng tốt nhanh hơn nhiều.

Nói cách khác: Grid phân bổ budget đều cho mọi hyperparameter, dù chúng quan trọng khác nhau. Random tự động "thử" mỗi hyperparameter ở nhiều giá trị unique, không bị penalty bởi chiều ít ảnh hưởng.

Trade-off: Random không đảm bảo cover đủ vùng (có vùng nhỏ nó miss); và không cho landscape heatmap đẹp như Grid. Với search space ≤ 2-3 chiều rời rạc, Grid vẫn ngang ngửa hoặc tốt hơn.

Class ở sklearn.model_selection.RandomizedSearchCV, API gần giống GridSearchCV — khác ở chỗ param_distributions nhận distribution thay cho list, và có thêm n_iter:

from sklearn.model_selection import RandomizedSearchCV
from sklearn.svm import SVC
from scipy.stats import loguniform, uniform

param_dist = {
    "C": loguniform(0.001, 1000),
    "kernel": ["linear", "rbf"],
    "gamma": loguniform(0.0001, 1),
}

search = RandomizedSearchCV(
    estimator=SVC(),
    param_distributions=param_dist,
    n_iter=50,
    cv=5,
    scoring="accuracy",
    n_jobs=-1,
    random_state=42,
)
search.fit(X_train, y_train)

print(search.best_params_)
print(search.best_score_)

Các attribute kết quả (best_params_, best_score_, best_estimator_, cv_results_, refit) giống hệt GridSearchCV — đây là drop-in replacement.

Vài điểm cần chú ý:

• n_iter: số lần sample tổ hợp. Tổng fit = n_iter × cv.
• random_state: bắt buộc set để reproducible. Cùng seed → cùng tập tổ hợp sample.
• param_distributions: có thể trộn distribution (cho continuous) và list (cho categorical). Sklearn tự nhận biết.
• Cũng kết hợp với Pipeline được, dùng cú pháp step__param giống Bài 40.

Random Search chỉ thực sự mạnh khi distribution chọn đúng kiểu giá trị. Ba helper hay dùng từ scipy.stats:

• loguniform(low, high): sample log-scale uniform giữa low và high. Dùng cho C, alpha, learning_rate, gamma — những giá trị trải nhiều bậc độ lớn. loguniform(0.001, 1000) sample đều theo log, nên cơ hội rơi vào 0.001-0.01 bằng vào 10-100.
• uniform(loc, scale): sample liên tục đều giữa loc và loc + scale. Dùng cho ratio: subsample, colsample_bytree, dropout. uniform(0.5, 0.5) nghĩa là sample đều trong [0.5, 1.0].
• randint(low, high): sample integer uniform trong [low, high) (không bao gồm high). Dùng cho n_estimators, max_depth, num_leaves.

List cũng dùng được — sklearn auto sample uniform từ list:

from scipy.stats import loguniform, uniform, randint

param_dist = {
    "n_estimators": randint(50, 500),         # 50, 51, ..., 499
    "max_depth": randint(3, 20),
    "learning_rate": loguniform(1e-4, 0.3),
    "subsample": uniform(0.5, 0.5),           # [0.5, 1.0]
    "colsample_bytree": uniform(0.5, 0.5),
    "max_features": ["sqrt", "log2", 0.5, 0.7, 1.0],
}

Nhầm phổ biến: dùng uniform cho C hay learning_rate. Vì giá trị trải log, sample uniform khiến phần lớn lần thử rơi vào vùng giá trị lớn — bỏ sót vùng nhỏ. Với những hyperparameter "trải log", luôn dùng loguniform.

n_iter là budget chính. Tradeoff:

• n_iter nhỏ (10-20): nhanh, nhưng dễ miss vùng tốt — đặc biệt khi search space ≥ 5 chiều.
• n_iter lớn (vài trăm): tiến gần Grid Search về cost, nhưng vẫn cover đa dạng hơn.

Quy tắc thực dụng: n_iter = 60-100 đủ cho hầu hết case 4-7 hyperparameter. Bergstra & Bengio chỉ ra với 60 lần sample, xác suất tổ hợp tốt rơi vào "top 5% của search space" là 1 - 0.95^60 ≈ 95%.

Quy tắc thứ 2: nếu mỗi fit rẻ (< 10 giây), tăng n_iter lên 200-500 để chắc; nếu mỗi fit đắt (vài phút trở lên), giới hạn 30-60 và chuyển hướng sang Bayesian.

Chiến lược 2 vòng:

1. Vòng 1: n_iter=60, distribution rộng. Khoanh vùng tốt.
2. Vòng 2: n_iter=60, distribution hẹp quanh best của vòng 1. Tinh chỉnh.

Random Search là stateless: lần sample thứ 50 không học được gì từ 49 lần trước. Bayesian Optimization sửa điều đó bằng cách build surrogate model — 1 model đơn giản dự đoán score = f(hyperparameter) dựa trên các observation đã có. Mỗi lần evaluate xong, surrogate được cập nhật, rồi quyết định điểm tiếp theo.

Hai thành phần:

• Surrogate model: dự đoán expected score và uncertainty tại mọi điểm trong search space. Phổ biến:
  • Gaussian Process (GP): ước lượng mean và variance của score tại mỗi điểm. Toán đẹp, nhưng scale O(n³) theo số observation — chậm khi quá vài trăm trial.
  • Tree-Parzen Estimator (TPE): ước lượng riêng 2 distribution — p(x | score tốt) và p(x | score xấu) — rồi chọn điểm có tỷ số p(good)/p(bad) cao. Scale tốt hơn GP.
• Acquisition function: hàm quyết định điểm nào nên thử tiếp theo, cân bằng exploit (chọn nơi surrogate dự đoán score cao) và explore (chọn nơi uncertainty cao). Vài lựa chọn:
  • Expected Improvement (EI): kỳ vọng score vượt best hiện tại — phổ biến nhất.
  • Upper Confidence Bound (UCB): mean + κ × std — tham số κ điều chỉnh explore vs exploit.
  • Probability of Improvement (PI): xác suất vượt best.

Vòng lặp Bayesian:

1. Sample vài điểm ngẫu nhiên ban đầu (warm-up), evaluate.
2. Fit surrogate trên các observation.
3. Optimize acquisition function → tìm điểm tiếp theo nên thử.
4. Evaluate điểm đó, thêm vào observation, quay về bước 2.
5. Lặp đến khi hết budget.

• Random Search: stateless, mỗi iteration độc lập → song song hoá dễ, không có overhead nội bộ.
• Bayesian Optimization: stateful, mỗi iteration phụ thuộc kết quả trước → khó song song tuyệt đối (vẫn có batch Bayesian); thêm overhead của surrogate.

Quy tắc chọn:

• Mỗi fit rẻ (< 30 giây): overhead surrogate gần bằng chính fit. Random Search đủ tốt và đơn giản hơn.
• Mỗi fit đắt (vài phút trở lên): mỗi điểm thử là 1 tài nguyên quý — Bayesian có lợi rõ vì chọn điểm thông minh hơn. Đây là tình huống điển hình của Deep Learning, large dataset.
• Search space liên tục, nhiều chiều: Bayesian (với TPE) thường thắng Random ở cùng budget khi budget < 100.
• Search space phần lớn categorical: lợi thế của Bayesian giảm; Random hoặc Successive Halving có thể tốt hơn.

Kết luận thực dụng: với ML cổ điển trên dataset cỡ vài chục nghìn sample, Random Search 60-100 iter là baseline mạnh. Với DL hoặc dataset to, dùng Optuna.

• scikit-optimize (skopt): cung cấp BayesSearchCV — drop-in replacement cho GridSearchCV / RandomizedSearchCV. Dùng GP làm surrogate. API quen thuộc với người dùng sklearn. Repo cập nhật chậm trong vài năm gần đây.
• Optuna: hiện là tool phổ biến cho hyperparameter tuning. Default surrogate là TPE; hỗ trợ pruning trial sớm (dừng các trial dở giữa chừng nếu score xấu hơn baseline), parallel async, multi-objective. API study.optimize(objective, n_trials=...) dễ tích hợp với mọi framework (sklearn, PyTorch, TensorFlow, XGBoost).
• Hyperopt: tool lâu đời, cũng dùng TPE. API fmin + space khai báo bằng hp.*. Vẫn được dùng nhưng phần lớn project mới chuyển sang Optuna.
• Ray Tune: framework distributed cho hyperparameter tuning. Tích hợp nhiều algorithm (Bayesian, ASHA, BOHB). Phù hợp khi tune trên cluster nhiều máy.

Với dự án ML cá nhân hoặc team nhỏ, Optuna là lựa chọn cân bằng giữa tính năng và độ phức tạp. Với hệ thống distributed, Ray Tune phù hợp hơn.

Mẫu chung của Optuna: định nghĩa hàm objective(trial) trả về score; trial.suggest_* sample hyperparameter; gọi study.optimize:

import optuna
from sklearn.svm import SVC
from sklearn.model_selection import cross_val_score
from sklearn.datasets import load_iris

X, y = load_iris(return_X_y=True)

def objective(trial):
    C = trial.suggest_float("C", 1e-3, 1e3, log=True)
    kernel = trial.suggest_categorical("kernel", ["linear", "rbf"])
    gamma = trial.suggest_float("gamma", 1e-4, 1.0, log=True)
    model = SVC(C=C, kernel=kernel, gamma=gamma)
    return cross_val_score(model, X, y, cv=5,
                           scoring="accuracy").mean()

study = optuna.create_study(direction="maximize")
study.optimize(objective, n_trials=100)

print(study.best_params)
print(study.best_value)

Các suggest_* hay dùng:

• trial.suggest_float(name, low, high, log=True): float, có thể log-scale.
• trial.suggest_int(name, low, high): integer.
• trial.suggest_categorical(name, choices): chọn từ list.

Optuna còn hỗ trợ pruning: trong DL, sau mỗi epoch gọi trial.report(score, epoch) rồi trial.should_prune() — nếu trial hiện tại tệ hơn baseline ở cùng epoch, dừng sớm để tiết kiệm thời gian. Đó là lý do Optuna phổ biến trong DL hyperparameter tuning.

Một hướng tiếp cận khác: phân bổ resource không đều. Resource ở đây là số sample dùng để train, hoặc n_estimators, hoặc số epoch.

Quy trình Successive Halving:

1. Sample nhiều tổ hợp (vd 64) với ít resource (vd 100 sample mỗi tổ hợp).
2. Đánh giá, giữ lại nửa tốt nhất (32 tổ hợp).
3. Tăng resource (vd 200 sample), đánh giá 32 tổ hợp đó.
4. Lặp: 16 → 8 → 4 → 1, mỗi vòng tăng resource gấp đôi.

Ý tưởng: tổ hợp tệ thường tệ ngay cả với ít data; không cần lãng phí full data để loại chúng. Tổ hợp hứa hẹn mới được full resource ở vòng cuối.

sklearn cung cấp HalvingGridSearchCV và HalvingRandomSearchCV ở module sklearn.model_selection (cần import thêm enable_halving_search_cv vì còn ở trạng thái experimental):

from sklearn.experimental import enable_halving_search_cv  # noqa
from sklearn.model_selection import HalvingRandomSearchCV
from scipy.stats import loguniform

search = HalvingRandomSearchCV(
    estimator=SVC(),
    param_distributions={"C": loguniform(1e-3, 1e3)},
    factor=2,             # giữ lại 1/factor mỗi vòng
    resource="n_samples", # dùng số sample làm resource
    cv=5,
    random_state=42,
)

Halving tỏ ra hiệu quả khi score "stable" với ít resource — nghĩa là tổ hợp tốt với 1000 sample cũng tốt với 10000. Nếu score thay đổi đột ngột theo resource (vd model cần đủ data mới convergent), Halving có thể loại nhầm tổ hợp tốt.

• Search nhỏ (≤ 100 tổ hợp), mỗi fit nhanh: GridSearchCV. Đơn giản, exhaustive, có thể visualize landscape.
• Search vừa-lớn (5-7 hyperparameter), mỗi fit nhanh-vừa: RandomizedSearchCV với n_iter=60-100. Baseline mạnh.
• Search lớn, mỗi fit đắt (Deep Learning, large dataset): Optuna với TPE. Có thể bật pruning để loại trial dở sớm.
• Cần loại trial dở sớm (mỗi epoch hoặc mỗi tăng resource): Optuna + pruner, hoặc HalvingRandomSearchCV.
• Distributed cluster nhiều máy: Ray Tune.
• Cần API quen thuộc sklearn: BayesSearchCV của scikit-optimize.

Không có "tool tốt nhất" — chọn theo budget, kích thước fit, và quen thuộc của team.

Recap nhanh — khi tune Random / Bayesian, ưu tiên distribution rộng cho những hyperparameter dưới đây:

• Linear / Logistic / Ridge / Lasso: C hoặc alpha — loguniform(1e-4, 1e2).
• Decision Tree: max_depth — randint(3, 20); min_samples_leaf — randint(1, 20).
• Random Forest: n_estimators — randint(100, 500); max_features — list ["sqrt", "log2", 0.5, 0.7]; max_depth.
• Gradient Boosting / XGBoost / LightGBM: n_estimators — randint(100, 1000); learning_rate — loguniform(1e-3, 0.3); max_depth — randint(3, 12); subsample, colsample_bytree — uniform(0.5, 0.5).
• SVM: C — loguniform(1e-3, 1e3); gamma — loguniform(1e-4, 1); kernel — list.
• Neural Network (Series 3): learning_rate — loguniform(1e-5, 1e-1); num_layers — randint(1, 5); hidden_size — randint(32, 512); dropout — uniform(0, 0.5); batch_size — list [32, 64, 128, 256].

Khi mở rộng tới NN, search space dễ vượt 10 chiều — Bayesian (Optuna) thường thắng rõ rệt vì mỗi train tốn nhiều phút.

• n_iter quá nhỏ: 10-15 iter không đủ cover search space ≥ 4 chiều. Tăng lên 50-100.
• Search range quá hẹp: loguniform(0.5, 2) chỉ trải 0.6 bậc độ lớn — gần như uniform. Đặt range rộng (vài bậc) cho vòng coarse, hẹp cho vòng fine.
• Quên random_state: kết quả không reproducible giữa các run. Set cả random_state của search và của CV splitter.
• Data leak qua preprocessing: vẫn áp dụng — bọc scaler/encoder trong Pipeline, đặt search ngoài Pipeline. Sai phổ biến: fit scaler trên toàn X_train trước khi truyền vào search.
• Dùng uniform cho hyperparameter log-scale: uniform(1e-3, 1e3) sẽ sample 99% giá trị ở vùng 1-1000, bỏ sót 0.001-1. Luôn dùng loguniform cho C, learning_rate, gamma, alpha.
• Tin tuyệt đối vào best_params từ 1 lần search: kết quả Random/Bayesian có variance theo seed. Chạy 2-3 lần với seed khác nhau, so sánh.
• Bayesian với search space rất nhỏ: overhead surrogate > lợi ích. Search space < 50 tổ hợp dùng Grid hoặc Random là đủ.

Ví dụ end-to-end với Random Forest trên Breast Cancer dataset:

import numpy as np
from scipy.stats import randint, uniform

from sklearn.datasets import load_breast_cancer
from sklearn.ensemble import RandomForestClassifier
from sklearn.model_selection import (
    train_test_split, RandomizedSearchCV,
)
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler

X, y = load_breast_cancer(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, stratify=y, random_state=42,
)

pipe = Pipeline([
    ("scaler", StandardScaler()),
    ("rf", RandomForestClassifier(random_state=42, n_jobs=-1)),
])

param_dist = {
    "rf__n_estimators": randint(100, 500),
    "rf__max_depth": randint(3, 20),
    "rf__max_features": ["sqrt", "log2", 0.5, 0.7],
    "rf__min_samples_leaf": randint(1, 10),
}

search = RandomizedSearchCV(
    pipe,
    param_distributions=param_dist,
    n_iter=60,
    cv=5,
    scoring="f1",
    n_jobs=-1,
    random_state=42,
    verbose=1,
)
search.fit(X_train, y_train)

print("Best params:", search.best_params_)
print(f"Best CV f1:  {search.best_score_:.4f}")
print(f"Test f1:     {search.score(X_test, y_test):.4f}")

Ghi nhận:

• Tổng fit = 60 × 5 = 300, cộng 1 refit cuối.
• scoring="f1" phù hợp khi 2 class lệch nhẹ (breast cancer ~63% positive).
• random_state=42 trong RandomizedSearchCV để tập 60 tổ hợp reproducible; random_state=42 trong RandomForestClassifier để mỗi fit reproducible.

Phiên bản Optuna tương đương (pseudo):

import optuna
from sklearn.model_selection import cross_val_score

def objective(trial):
    n_estimators = trial.suggest_int("n_estimators", 100, 500)
    max_depth = trial.suggest_int("max_depth", 3, 20)
    max_features = trial.suggest_categorical(
        "max_features", ["sqrt", "log2", 0.5, 0.7]
    )
    min_samples_leaf = trial.suggest_int("min_samples_leaf", 1, 10)

    pipe.set_params(
        rf__n_estimators=n_estimators,
        rf__max_depth=max_depth,
        rf__max_features=max_features,
        rf__min_samples_leaf=min_samples_leaf,
    )
    return cross_val_score(pipe, X_train, y_train, cv=5,
                           scoring="f1", n_jobs=-1).mean()

study = optuna.create_study(direction="maximize",
                            sampler=optuna.samplers.TPESampler(seed=42))
study.optimize(objective, n_trials=60)

print(study.best_params)
print(study.best_value)

Cùng budget 60 trial, Optuna với TPE thường ra best score ngang hoặc cao hơn Random nhẹ trên search space này — không phải lúc nào cũng vượt rõ rệt, vì search space chỉ 4 chiều và mỗi fit nhanh.

Bài 1. Trên Iris, Pipeline StandardScaler → SVC. RandomizedSearchCV với:

param_dist = {
    "svm__C": loguniform(1e-3, 1e3),
    "svm__kernel": ["linear", "rbf"],
    "svm__gamma": loguniform(1e-4, 1),
}

Chạy n_iter=50, cv=5, scoring="accuracy", random_state=42. In best params + CV score + test accuracy. So sánh tổng số fit với GridSearchCV ở Bài 40.

Bài 2. Trên Breast Cancer (cùng setup Bài 16), so sánh 3 cách:

1. GridSearchCV với grid hẹp (n_estimators ∈ {100, 300, 500}, max_depth ∈ {5, 10, 15}, max_features ∈ {"sqrt", "log2"}).
2. RandomizedSearchCV với n_iter=60.
3. Optuna với n_trials=60.

So sánh best CV score, test score, và wall-clock time. Cách nào nhanh nhất với score xấp xỉ?

Bài 3. Tune XGBoost trên dataset tuỳ chọn (vd California Housing). Search space:

param_dist = {
    "n_estimators": randint(100, 1000),
    "learning_rate": loguniform(1e-3, 0.3),
    "max_depth": randint(3, 12),
    "subsample": uniform(0.5, 0.5),
    "colsample_bytree": uniform(0.5, 0.5),
    "reg_lambda": loguniform(1e-3, 1e2),
}

RandomizedSearchCV n_iter=100, scoring "neg_root_mean_squared_error". So sánh RMSE test với XGBoost default. Mức cải thiện?

Bài 4. Lặp lại Bài 1 với random_state=42, 7, 123. Best params có giống nhau không? Variance của best score qua 3 seed là bao nhiêu? Bài học rút ra về tin tưởng kết quả 1 lần search?

Bài 42: Class Imbalance — SMOTE và class_weight — khi class trong dữ liệu lệch nặng (vd 95% âm, 5% dương trong fraud detection), model có xu hướng "lười" dự đoán toàn class đa số. Bài tiếp giới thiệu 2 hướng xử lý: cân lại dữ liệu bằng oversampling/SMOTE và cân lại loss bằng class_weight.