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 
jmpl| 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, , ruang keluaran, , dan sampel yang diambil dari suatu distribusi probabilitas yang tidak diketahui, , pada , tujuan dari masalah ini adalah untuk memperkirakan fungsi regresi, , yang diberikan oleh



Dengan  adalah distribusi kondisional pada  yang diinduksi oleh   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.Raskutti, G.; M.J. Wainwright; Bin Yu (2011). "Early stopping for non-parametric regression: An optimal data-dependent stopping rule". 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton). 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton). pp. 1318–1325. doi:10.1109/Allerton.2011.6120320.

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

Misal dan  Diberikan satu himpunan sampel



diambil secara independen dari , meminimalkan fungsi berikut.



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



Misal, dan  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 . Iterasi  lalu membentuk iterasi populasi yang konvergen ke , tetapi tidak dapat digunakan dalam perhitungan, sementara  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:



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  =: 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 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 

Kategori:Jaringan saraf tiruan