Early stopping (pemelajaran mesin)

Dalam pemelajaran mesin, ***early stopping*** (lit: penghentian dini) adalah salah satu bentuk regularisasi yang digunakan untuk menghindari *[[overfitting]]* ketika melatih model menggunakan metode iteratif, seperti penurunan gradien. Metode iteratif memperbarui model agar semakin cocok dengan data latih pada setiap iterasi. Metode ini dapat meningkatkan kinerja model pada data di luar data pelatihan (misalnya, data validasi) sampai batasan tertentu. Namun, ketika telah melampaui batasan tersebut, peningkatan kecocokan model terhadap data pelatihan akan mengorbankan kemampuan generalisasi model. Dengan menggunakan *early stopping,* jumlah iterasi yang dapat dijalankan sebelum model pemelajaran mulai mengalami *overfitting* dapat diketahui*.* Teknik ini juga telah digunakan dalam banyak metode pemelajaran mesin yang berbeda dengan landasan teoretis yang beragam.

## Latar belakang
Bagian ini menyajikan beberapa konsep dasar pemelajaran mesin yang diperlukan untuk memahami *early stopping.*

### ''Overfitting''

Algoritma pemelajaran mesin melatih model pada data pelatihan yang terbatas. Selama proses pelatihan ini, model dievaluasi berdasarkan seberapa baik model tersebut memprediksi pengamatan yang terdapat dalam set pelatihan. Namun, secara umum, tujuan pemelajaran mesin adalah untuk menghasilkan model yang digeneralisasi, yaitu memprediksi pengamatan yang belum pernah terlihat sebelumnya. *Overfitting* terjadi ketika suatu model memprediksi data dengan sangat baik dalam set pelatihan, sementara mengalami kesalahan generalisasi yang lebih besar.

### Regularisasi
Dalam konteks pemelajaran mesin, regularisasi merujuk pada proses memodifikasi algoritma pemelajaran untuk mencegah *overfitting*. Proses ini umumnya melibatkan penerapan semacam kendala kelancaran (*smoothness constraint*) pada model yang dipelajari. Kendala ini umumnya dapat diberlakukan secara eksplisit, misalnya dengan membatasi jumlah parameter dalam model, atau dengan menambah fungsi biaya seperti dalam regularisasi Tikhonov. Regularisasi Tikhonov, bersama dengan regresi komponen utama dan banyak skema regularisasi lainnya, termasuk dalam lingkup regularisasi spektral, yaitu regularisasi yang dicirikan oleh penerapan sebuah  filter. *Early stopping* juga termasuk dalam metode ini.

### Metode penurunan gradien (''gradient descent'')
Metode penurunan gradien merupakan metode optimasi orde pertama yang bersifat iteratif. Setiap iterasi memperbarui solusi perkiraan dari masalah optimasi dengan mengambil langkah ke arah negatif gradien dari fungsi objektif. Dengan memilih ukuran langkah (*step size*) yang tepat, metode ini dapat dibuat konvergen ke minimum lokal dari fungsi objektif. Dalam pemelajaran mesin, penurunan gradien digunakan dengan mendefinisikan *[[fungsi kerugian]]* (*loss function*) yang mencerminkan kesalahan model pada data pelatihan, lalu meminimalkan fungsi tersebut.

## ''Early stopping'' berdasarkan hasil analisis

### ''Early stopping'' dalam teori pembelajaran statistik
*Early stopping* dapat digunakan sebagai teknik regularisasi dalam masalah regresi non-parametrik yang sering ditemui dalam pemelajaran mesin. Untuk ruang masukan tertentu, X, ruang keluaran, Y, dan sampel yang diambil dari suatu distribusi probabilitas yang tidak diketahui, \rho, pada Z = X \times Y, tujuan dari masalah ini adalah untuk memperkirakan *fungsi regresi*, f_{\rho}, yang diberikan oleh

:  f_\rho(x) = \int_Y y \, d\rho(y\mid x),\, x \in X,

Dengan \rho(y\mid x) adalah distribusi kondisional pada x yang diinduksi oleh \rho  Salah satu pendekatan umum untuk memperkirakan fungsi regresi adalah menggunakan fungsi dari . Ruang ini dapat berdimensi takhingga sehingga mampu menghasilkan solusi yang *overfit* pada himpunan data pelatihan dengan ukuran berapapun. Oleh karena itu, regularisasi menjadi sangat penting dalam metode ini. Salah satu cara untuk melakukan regularisasi pada masalah regresi nonparametrik adalah dengan menerapkan *early stopping* yang lebih awal pada metode iteratif, seperti penurunan gradien.

Aturan *early stopping* yang diusulkan untuk masalah seperti ini didasarkan pada analisis batas atas kesalahan generalisasi yang bergantung pada jumlah iterasi. Aturan ini memberikan rekomendasi tentang seberapa banyak iterasi yang harus dijalankan, yan dapat dihitung sebelum proses penyelesaian dimulai.

#### Contoh: Kerugian kuadrat terkecil
(Diadaptasi dari Yao, Rosasco dan Caponnetto, 2007)

MisalX\subseteq\mathbb{R}^n dan Y=\mathbb{R}. Diberikan satu himpunan sampel

: \mathbf{z} = \left \{(x_i,y_i) \in X \times Y: i = 1, \dots, m\right\} \in Z^m,

diambil secara independen dari \rho, meminimalkan fungsi berikut.

: 
\mathcal{E}(f) = \int_{X\times Y} (f(x) - y)^2 \, d\rho


dengan f adalah anggota ruang Hilbert kernel reproduksi \mathcal{H}. Artinya, meminimalkan risiko ekspektasi untuk fungsi kerugian kuadrat terkecil. Karena \mathcal{E} bergantung pada ukuran probabilitas yang tidak diketahui \rho, maka \mathcal{E} tidak dapat digunakan dalam perhitungan. Seagai gantinya, pertimbangkan risiko empiris berikut. 

: 
\mathcal{E}_{\mathbf{z}}(f) = \frac{1}{m} \sum_{i=1}^m \left(f(x_i) - y_{i}\right)^2.


Misal,f_{t} dan f_t^{\mathbf{z}} adalah iterasi ke- *t* dari metode penurunan gradien yang diterapkan pada risiko ekspektasi dan risiko empiris yang keduanya diinisialisasi di titik asal, dan menggunakan ukuran langkah \gamma_{t}. Iterasi f_{t} lalu membentuk *iterasi populasi* yang konvergen ke f_{\rho}, tetapi tidak dapat digunakan dalam perhitungan, sementara f_t^{\mathbf{z}} membentuk *iterasi sampel* yang biasanya konvergen ke solusi *overfitting*.

Kita ingin mengontrol selisih antara risiko ekspektasi dari iterasi sampel dan risiko ekspektasi minimum, yaitu risiko ekspektasi dari fungsi regresi:

: \mathcal{E}(f_t^{\mathbf{z}}) - \mathcal{E}(f_\rho)

Selisih ini dapat ditulis ulang sebagai jumlah dari dua suku: selisih risiko ekspektasi antara iterasi sampel dan iterasi populasi, serta antara iterasi populasi dan fungsi regresi:

Persamaan ini menggambarkan tradeoff bias-varians, yang kemudian diselesaikan untuk memberikan aturan penghentian optimal yang mungkin bergantung pada distribusi probabilitas yang tidak diketahui. Aturan tersebut memiliki batas probabilistik terkait dengan kesalahan generalisasi. Untuk analisis yang mengarah pada aturan penghentian dini (*early stopping*) dan batas-batasnya, pembaca dapat merujuk ke artikel asli. Dalam praktiknya, metode berbasis data, misalnya validasi silang (*cross-validation*) dapat digunakan untuk memperoleh aturan penghentian adaptif.

### ''Early stopping'' dalam ''boosting''
*[[Boosting]]* mengacu pada keluarga algoritma yang terdiri atas sejumlah *weak learner* atau **pembelajar lemah** (yang hanya sedikit berkorelasi dengan proses atau distribusi yang mendasari data) dan digabungkan untuk menghasilkan *strong learner* (**pembelajar yang lebih kuat**). Telah dibuktikan, untuk beberapa algoritma *boosting* (termasuk AdaBoost ), bahwa regularisasi melalui *early stopping* dapat memberikan jaminan konsistensi, yaitu bahwa hasil algoritma menghampiri solusi sebenarnya ketika jumlah sampel mendekati tak terhingga.

#### L -''boosting''
Metode boosting memiliki hubungan erat dengan metode *gradient descent* yang dijelaskan di atas dapat dianggap sebagai metode boosting berdasarkan kerugian L_{2} =: Boosting *L *. 

## ''Early boosting'' berbasis validasi
Aturan *early stopping* ini bekerja dengan membagi set pelatihan asli menjadi satu data pelatihan baru dan satu data validasi. Kesalahan pada data validasi digunakan sebagai proksi untuk kesalahan generalisasi dalam menentukan kapan *overfitting* telah dimulai. Metode ini digunakan dalam pelatihan banyak algoritma pemelajaran mesin berbasis iteratif, termasuk jaringan saraf (berbasis *epoch*). Prechelt memberikan ringkasan berikut ini mengenai implementasi naif dari *early stopping* berbasis ''holdout'' sebagai berikut:

Validasi silang&nbsp;adalah alternatif yang dapat digunakan untuk masalah non-deret waktu. Validasi silang terdiri atas pemisahan data menjadi beberapa partisi yang masing-masing dibagi menjadi data pelatihan dan data validasi–alih-alih partisi tunggal yang hanya terdiri dari satu data pelatihan dan satu data validasi. Meskipun prosedur ini terlihat sederhana, dalam praktiknya menjadi lebih rumit karena kesalahan validasi bisa berfluktuasi selama pelatihan, yang menghasilkan beberapa titik minimum lokal. Komplikasi ini telah mendorong terciptanya berbagai aturan ad hoc untuk memutuskan kapan overfitting benar-benar dimulai.

## Lihat juga

* Overfitting, *early stopping*  adalah salah satu metode yang digunakan untuk mencegah *overfitting*
* Kesalahan generalisasi
* Regularisasi (matematika)
* Teori pembelajaran statistik
* Boosting (pemelajaran mesin)
* Validasi silang, khususnya menggunakan "set validasi"
* Jaringan saraf

## Referensi