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 teoritis yang beragam.

Latar belakang

Bagian ini menyajikan beberapa konsep dasar pemelajaran mesin yang diperlukan untuk memahami early stopping.

Overfitting

Gambar 1. Garis hijau melambangkan model yang terlalu pas dan garis hitam melambangkan model yang teregulasi. Walaupun garis hijau mengikuti data pelatihan dengan sangat baik, garis ini terlalu bergantung pada data latih tersebut dan cenderung memiliki tingkat kesalahan lebih tinggi pada data baru yang tak terlihat yang diilustrasikan dengan titik-titik bergaris hitam, dibandingkan dengan garis hitam.

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 permasalahan 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 <i>ruang Hilbert kernel reproducing</i>. 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)

Misal$X\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 resiko 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 resiko 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:

1. Pisahkan data pelatihan menjadi dua bagian: satu bagian untuk set pelatihan dan satu bagian untuk set validasi, misalnya dengan rasio 2:1.
2. Latih model hanya menggunakan data pada set pelatihan dan evaluasi pada data validasi, misalkan, seperti setelah setiap 5 epoch.
3. Hentikan proses pelatihan ketika galat pada data validasi lebih besar daripada saat terakhir kali diperiksa.
4. Gunakan bobot pada jaringan sebelumnya sebagai hasil dari pelatihan tersebut.
   — Lutz Prechelt, Early Stopping – But When?

Validasi silang 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