Halving Search

Grid dan random search memperlakukan semua konfigurasi dengan martabat yang sama: masing-masing dievaluasi penuh, berapa pun biayanya. Successive halving menolak kesetaraan itu. Prinsipnya seperti turnamen eliminasi: semua kandidat mulai dengan anggaran kecil, yang tampak menjanjikan maju ke babak dengan anggaran lebih besar, dan sisanya tersingkir lebih dini tanpa pernah mencicipi data penuh. scikit-learn mengemas prinsip ini dalam HalvingGridSearchCV dan HalvingRandomSearchCV. Chapter ini membedah mekanisme turnamennya, mengaktifkannya dari modul eksperimental, lalu mengukur penghematannya secara programatik — anggaran baris yang diproses turun ke sekitar sepertiga dengan juara yang sama.

Mekanisme Turnamen Bertahap #

Pada HalvingGridSearchCV, seluruh kandidat grid dievaluasi di iterasi 0 dengan anggaran kecil: secara bawaan, resource adalah n_samples, jadi tiap kandidat hanya dievaluasi pada subcuplik berisi min_resources baris. Kandidat dengan skor terbaik lanjut — tepatnya ceil(jumlah_kandidat / factor) yang bertahan, sehingga dengan factor=3 sekitar sepertiga kandidat maju tiap babak. Babak berikutnya mengalikan anggaran dengan factor yang sama: 30 baris menjadi 90, lalu 270, dan seterusnya sampai anggaran menyentuh seluruh data latih atau tersisa satu kandidat.

Dua parameter mengendalikan bentuk turnamen. min_resources menetapkan titik awal — semakin kecil, semakin murah babak pembuka tetapi semakin bising penilaiannya. factor menetapkan kemajuan — factor=3 berarti anggaran naik tiga kali lipat dan kandidat yang lolos tinggal sepertiga. Resource juga tidak harus jumlah baris: parameter resource menerima "n_iterations" untuk estimator iteratif seperti gradient boosting (anggaran = jumlah putaran pelatihan), atau nama parameter estimator lain yang nilainya positif.

Parameter	Makna	Efek jika diperbesar
`factor`	Pengali anggaran tiap babak	Eliminasi lebih agresif, turnamen lebih pendek
`min_resources`	Anggaran babak pembuka	Babak awal lebih meyakinkan, biaya awal naik
`resource`	Jenis anggaran (`n_samples`, `n_iterations`)	Menyesuaikan sumber biaya ke jenis estimator
`max_candidates`	Batas jumlah kandidat babak awal	Menahan pertumbuhan kombinasi pada grid besar

Mengapa Ini Menghemat: Cerita dalam Angka #

Inti penghematannya bukan jumlah pemanggilan fit() — turnamen justru bisa sedikit lebih banyak memanggil fit() karena kandidat kuat dievaluasi berulang di beberapa babak. Penghematan sesungguhnya ada pada jumlah baris yang diproses: babak pembuka menilai 9 kandidat hanya dengan 30 baris per evaluasi, bukan 210 baris. Karena biaya pelatihan sebagian besar estimator sebanding jumlah baris latih, total “baris × panggilan” adalah proksi biaya yang jujur — dan di angka itu, halving memang unggul jauh.

Risikonya sejalan dengan logikanya: evaluasi pada 30 baris adalah estimasi yang bising, dan kandidat yang kuat di data penuh bisa saja tampak biasa di subcuplik kecil — tersingkir sebelum sempat membuktikan diri. Karena itu min_resources terlalu kecil berbahaya; naikkan titik awal kalau turnamen sering memilih juara yang berbeda dari grid penuh.

Aktivasi dari Modul Eksperimental #

Kelas-kelas halving belum dianggap API stabil, jadi scikit-learn menyimpannya di sklearn.experimental. Kodenya tetap berfungsi penuh, tetapi wajib mengimpor pengaktifnya sebelum bisa dipakai:

python
from sklearn.experimental import enable_halving_search_cv  # noqa: F401
from sklearn.model_selection import HalvingGridSearchCV

Tanpa baris impor pertama, pemanggilan HalvingGridSearchCV memicu ImportError. Keluarganya ada dua: HalvingGridSearchCV menjelajahi seluruh grid seperti GridSearchCV, sedangkan HalvingRandomSearchCV menggabungkan penyampelan acak Chapter Random Search dengan turnamen bertahap — cocok saat ruang pencariannya luas.

Contoh Kode: Turnamen vs Grid dengan Penghitung Biaya #

Skrip berikut membandingkan halving dan grid biasa pada grid dan lipatan yang persis sama. Biaya keduanya diukur lewat subclass RandomForestPenghitung yang menghitung setiap pemanggilan fit() beserta jumlah baris latihan yang diproses — pengukuran programatik, bukan perkiraan.

python

# HalvingGridSearchCV menyetel hyperparameter lewat turnamen bertahap:
# semua kandidat mulai dengan anggaran kecil, kandidat lemah tersingkir dini.
# Catatan: masih modul eksperimental -- impor enable_halving_search_cv WAJIB.

from sklearn.datasets import make_classification
from sklearn.experimental import enable_halving_search_cv  # noqa: F401
from sklearn.ensemble import RandomForestClassifier
from sklearn.model_selection import (GridSearchCV, HalvingGridSearchCV,
                                     StratifiedKFold, train_test_split)

X, y = make_classification(n_samples=300, n_features=6, n_informative=4,
                           n_redundant=0, n_clusters_per_class=1, random_state=42)
X_latih, X_uji, y_latih, y_uji = train_test_split(X, y, test_size=0.3,
                                                   stratify=y, random_state=42)
cv = StratifiedKFold(n_splits=3, shuffle=True, random_state=42)
param_grid = {"n_estimators": [20, 50, 100], "max_depth": [3, 5, None]}


class RandomForestPenghitung(RandomForestClassifier):
    """RandomForest yang ikut menghitung pemanggilan fit dan baris latihan."""

    n_fit = 0
    n_baris = 0

    def fit(self, X, y, **kwargs):
        type(self).n_fit += 1
        type(self).n_baris += X.shape[0]
        return super().fit(X, y, **kwargs)


# --- Turnamen: 9 kandidat mulai dari anggaran 30 baris ---
RandomForestPenghitung.n_fit = 0
RandomForestPenghitung.n_baris = 0
halving = HalvingGridSearchCV(
    RandomForestPenghitung(random_state=42, n_jobs=1), param_grid,
    factor=3, min_resources=30, cv=cv, random_state=42,
)
halving.fit(X_latih, y_latih)
fit_halving = RandomForestPenghitung.n_fit
baris_halving = RandomForestPenghitung.n_baris

print("== HalvingGridSearchCV (factor=3, min_resources=30) ==")
print(f"Jumlah iterasi       : {halving.n_iterations_}")
hasil = halving.cv_results_
for i in range(halving.n_iterations_):
    baris_iter = [j for j, it in enumerate(hasil["iter"]) if it == i]
    skor_terbaik = max(hasil["mean_test_score"][j] for j in baris_iter)
    print(f"  Iterasi {i}: {len(baris_iter)} kandidat, "
          f"anggaran {hasil['n_resources'][baris_iter[0]]} baris, "
          f"skor terbaik {skor_terbaik:.4f}")
print(f"best_params_ : {halving.best_params_}")
print(f"best_score_  : {halving.best_score_:.4f}")
print(f"Akurasi uji  : {halving.best_estimator_.score(X_uji, y_uji):.3f}")
print(f"Biaya        : {fit_halving} pemanggilan fit, "
      f"{baris_halving} baris latihan diproses")

# --- Pembanding: GridSearchCV pada grid dan cv yang persis sama ---
RandomForestPenghitung.n_fit = 0
RandomForestPenghitung.n_baris = 0
grid = GridSearchCV(RandomForestPenghitung(random_state=42, n_jobs=1),
                    param_grid, cv=cv)
grid.fit(X_latih, y_latih)
fit_grid = RandomForestPenghitung.n_fit
baris_grid = RandomForestPenghitung.n_baris

print("\n== GridSearchCV (grid dan cv yang sama) ==")
print(f"best_params_ : {grid.best_params_}")
print(f"best_score_  : {grid.best_score_:.4f}")
print(f"Akurasi uji  : {grid.best_estimator_.score(X_uji, y_uji):.3f}")
print(f"Biaya        : {fit_grid} pemanggilan fit, "
      f"{baris_grid} baris latihan diproses")

print("\n== Ringkasan efisiensi ==")
print(f"Juara sama            : {halving.best_params_ == grid.best_params_}")
print(f"Pemanggilan fit       : halving {fit_halving} vs grid {fit_grid}")
print(f"Baris latihan         : halving {baris_halving} vs grid {baris_grid} "
      f"({baris_halving / baris_grid:.1%} dari grid)")

Output yang Dihasilkan:

text
== HalvingGridSearchCV (factor=3, min_resources=30) ==
Jumlah iterasi       : 2
  Iterasi 0: 9 kandidat, anggaran 30 baris, skor terbaik 0.7333
  Iterasi 1: 3 kandidat, anggaran 90 baris, skor terbaik 0.9111
best_params_ : {'max_depth': 5, 'n_estimators': 100}
best_score_  : 0.9111
Akurasi uji  : 0.856
Biaya        : 37 pemanggilan fit, 1290 baris latihan diproses

== GridSearchCV (grid dan cv yang sama) ==
best_params_ : {'max_depth': 5, 'n_estimators': 100}
best_score_  : 0.9000
Akurasi uji  : 0.856
Biaya        : 28 pemanggilan fit, 3990 baris latihan diproses

== Ringkasan efisiensi ==
Juara sama            : True
Pemanggilan fit       : halving 37 vs grid 28
Baris latihan         : halving 1290 vs grid 3990 (32.3% dari grid)

Bedah baris-baris utamanya:

Baris 6 (impor eksperimental): enable_halving_search_cv diimpor lebih dulu; tanpa impor ini seluruh fitur halving tidak dapat diakses.
Baris 19–28 (RandomForestPenghitung): subclass kecil yang menimpa fit() untuk menambah dua penghitung kelas — jumlah pemanggilan dan total baris. Karena GridSearchCV meng-clone estimator, semua model yang dilatih tetap berkelas penghitung ini dan ikut tercatat.
Baris 34–37 (konstruksi turnamen): factor=3 dan min_resources=30 ditetapkan eksplisit; titik awal 30 baris dipilih agar babak pembuka cukup stabil pada dataset 210 baris latih ini.
Baris 45–50 (tabel babak): dari cv_results_, tiap iterasi diringkas — jumlah baris pada iter ke-i adalah jumlah kandidat yang dievaluasi babak itu (kolom n_resources mencatat anggarannya). Turnamen berlangsung dua babak: 9 kandidat pada 30 baris (skor terbaik 0,733), lalu 3 finalis pada 90 baris (skor terbaik 0,911).
Baris 57–64 (grid pembanding): GridSearchCV berjalan pada grid dan lipatan identik, dengan penghitung yang direset. Juaranya sama — max_depth=5, n_estimators=100 — dan akurasi data uji pun sama, 0,856.
Baris 73–77 (ringkasan efisiensi): pemanggilan fit() 37 lawan 28 — halving sedikit lebih banyak — tetapi baris latihan yang diproses 1.290 lawan 3.990, hanya 32,3% dari anggaran grid, dengan juara dan akurasi akhir yang setara.

Membaca cv_results_ Bentuk Turnamen #

Berbeda dari GridSearchCV yang satu baris per konfigurasi, cv_results_ pada halving berisi satu baris per kandidat per babak: konfigurasi yang sama muncul dua kali dengan skor pada anggaran 30 dan 90 baris. Kolom iter menandai babaknya, n_resources mencatat anggarannya, dan peringkat pada babak terakhir yang menentukan juara. Struktur ini juga memungkinkan inspeksi menarik: membandingkan skor kandidat yang sama antar babak adalah cara langsung melihat seberapa stabil peringkatnya saat data bertambah.

Turnamen mengotomatiskan alokasi anggaran, tetapi tetap menjawab pertanyaan “konfigurasi mana yang terbaik”. Ada pertanyaan yang lebih mendasar sebelum itu: hyperparameter mana yang benar-benar berpengaruh, dan di wilayah nilai mana efeknya berbalik? Pertanyaan itu dijawab bukan oleh pencarian, melainkan oleh kurva diagnostik — materi Chapter Kurva Validasi untuk Pemilihan Hyperparameter.

Referensi Resmi #

Tuning the hyper-parameters of an estimator — scikit-learn User Guide — bagian Searching for optimal parameters with successive halving.
HalvingGridSearchCV — scikit-learn API — kontrak factor, resource, min_resources, dan atribut n_candidates_/n_resources_.
HalvingRandomSearchCV — scikit-learn API — varian penyampelan acak dari turnamen bertahap.