Stabilitas (teori pemelajaran)

Stabilitas (bahasa Inggris: stability), dan dikenal juga sebagai stabilitas algoritmik atau algorithmic stability, adalah sebuah ide dalam teori pemelajaran komputasional yang menjelaskan bagaimana keluaran dari algoritma pemelajaran mesin dapat berubah seiring dengan dilakukannya perubahan kecil dalam masukannya. Suatu algoritma pemelajaran dikatakan stabil jika prediksi yang dihasilkan tidak banyak berubah jika terjadi sedikit perubahan pada data latihnya. Sebagai contoh, pertimbangkan sebuah algoritma pemelajaran mesin yang dilatih untuk mengenal huruf tulisan tangan dari alfabet dengan menggunakan 1000 contoh dan label yang diberikan adalah “A” sampai “Z” sebagai himpunan data latih. Maka satu cara untuk memodifikasi himpunan data latih ini adalah dengan membuang satu contoh, sehingga dengan itu tersisa 999 contoh huruf tulisan tangan dari alfabet beserta labelnya masing-masing. Dengan demikian, sebuah algoritma pemelajaran dikatakan stabil jika dapat menghasilkan klasifier yang mirip, baik dengan 1000 elemen maupun 999 elemen dari himpunan data latih.

Stabilitas ini dapat dipelajari untuk berbagai jenis masalah pemelajaran, mulai dari pemelajaran bahasa hingga masalah invers dalam bidang fisika dan teknik. Hal ini dapat terjadi karena stabilitas merupakan sifat dari suatu proses pemelajaran, bukan berdasarkan jenis informasi yang dipelajari. Studi terkait stabilitas menjadi penting dalam teori pemelajaran komputasi pada tahun 2000-an ketika terbukti ia memiliki hubungan dengan generalisasi. Hal tersebut menunjukkan bahwa untuk algoritma pemelajaran dengan jumlah kelas yang besar, terutama algoritma minimalisasi risiko empiris, jenis stabilitas tertentu dapat memastikan generalisasi yang baik.

 Sejarah 
Tujuan utama dalam mendesain sebuah sistem pemelajaran mesin adalah untuk menjamin bahwa algoritma pemelajaran dapat melakukan generalisasi, atau dapat menampilkan hasil prediksi secara akurat pada contoh baru setelah dilatih dalam jumlah contoh yang terbatas. Pada dekade 1990-an, dicapai tonggak sejarah dalam menentukan batas generalisasi pada algoritma pemelajaran terarah. Teknik tersebut di waktu itu digunakan untuk membuktikan bahwa generalisasi dapat menunjukkan bagaimana suatu algoritma bersifat konsisten , dengan menggunakan sifat konvergensi uniform dari kuantitas empiris. Teknik ini digunakan untuk mendapatkan batas generalisasi untuk kelas besar dalam algoritma minimalisasi risiko empiris (ERM). Algoritma ERM adalah suatu algoritma yang memilih solusi dari ruang hipotesis  sedemikian rupa untuk meminimalkan kesalahan empiris pada satu set latih .

Hasil umum yang dibuktikan oleh Vladimir Vapnik untuk algoritma klasifikasi biner ERM menyatakan bahwa untuk setiap fungsi target dan distribusi masukan, setiap ruang hipotesis  dengan dimensi VC , dan sebanyak  contoh latih, algoritmanya bersifat konsisten dan akan menghasilkan kesalahan latih yang paling banyak sebesar   (ditambah faktor logaritmik) dari kesalahan sebenarnya. Hasilnya kemudian diperluas ke algoritma hampir-ERM dengan kelas fungsi yang tidak memiliki minimalisasi yang unik.

Karya Vapnik, menggunakan apa yang dikenal sebagai teori VC, telah membangun sebuah hubungan antara generalisasi dari sebuah algoritma pemelajaran dan properti dari ruang hipotesis  dalam fungsi yang sedang dipelajari. Namun, hasil ini tidak dapat diterapkan pada algoritma dengan ruang hipotesis yang dimensi VC-nya takterbatas. Dengan kata lain, hasil ini tidak dapat diterapkan ketika informasi yang dipelajari mempunyai kompleksitas yang terlalu besar untuk diukur. Beberapa algoritma pemelajaran mesin yang paling sederhana—misalnya, untuk regresi—memiliki ruang hipotesis dengan dimensi VC yang tidak terbatas. Contoh lainnya adalah algoritma pemelajaran bahasa yang dapat menghasilkan kalimat dengan panjang yang berubah-ubah.

Analisis stabilitas dikembangkan pada tahun 2000-an untuk teori pemelajaran komputasi dan merupakan metode alternatif untuk memperoleh batasan generalisasi. Stabilitas suatu algoritma adalah properti dari proses pemelajaran, bukan properti langsung dari ruang hipotesis , dan dapat dinilai dalam algoritma yang memiliki ruang hipotesis dengan dimensi VC tidak terbatas atau tidak terdefinisi seperti tetangga terdekat. Algoritma pemelajaran yang stabil adalah algoritma yang fungsi pemelajarannya tidak banyak berubah ketika data latihnya sedikit dimodifikasi, misalnya dengan mengabaikan satu titik data. Ukuran kesalahan Leave one out digunakan dalam algoritma Cross Validation Leave One Out (CVloo) untuk mengevaluasi stabilitas algoritma pemelajaran sehubungan dengan fungsi kerugian. Dengan demikian, analisis stabilitas adalah penerapan analisis sensitivitas pada pemelajaran mesin.

 Ringkasan hasil klasik 

 Awal tahun 1900an - Stabilitas dalam teori pemelajaran pertama kali dijelaskan dalam istilah kontinuitas dari peta pemelajaran . Ketika ditelusuri istilah ini dipelopori hingga kepada Andrey Nikolayevich Tikhonov.
 1979 - Devroye dan Wagner mengamati bahwa perilaku leave-one-out dari suatu algoritma berhubungan dengan sensitivitasnya terhadap perubahan kecil dalam sampel.L. Devroye and Wagner, Distribution-free performance bounds for potential function rules, IEEE Trans. Inf. Theory 25(5) (1979) 601–604.
 1999 - Kearns dan Ron menemukan terkait hubungan antara dimensi VC terbatas dan stabilitas.M. Kearns and D. Ron, Algorithmic stability and sanity-check bounds for leave-one-out cross-validation, Neural Comput. 11(6) (1999) 1427–1453.
 2002 - Dalam sebuah makalah penting, Bousquet dan Elisseeff mengusulkan gagasan stabilitas hipotesis seragam atau uniform hypothesis stability dari suatu algoritma pemelajaran dan menunjukkan bahwa hal tersebut menyiratkan kesalahan generalisasi yang rendah. Stabilitas hipotesis seragam, bagaimanapun, adalah kondisi kuat yang tidak berlaku untuk kelas algoritma yang besar, termasuk algoritma ERM dengan ruang hipotesis hanya dua fungsi.O. Bousquet and A. Elisseeff. Stability and generalization. J. Mach. Learn. Res., 2:499–526, 2002.
 2002 - Kutin dan Niyogi memperluas hasil Bousquet dan Elisseeff dengan memberikan batasan generalisasi untuk beberapa bentuk stabilitas yang lebih lemah yang mereka sebut sebagai stabilitas hampir di semua tempat atau almost-everywhere-stability. Selanjutnya, mereka mengambil langkah awal dalam membangun hubungan antara stabilitas dan konsistensi dalam algoritma ERM dalam pengaturan Mungkin Kurang Lebih Benar (Probably Approximately Correct (PAC)).S. Kutin and P. Niyogi, Almost-everywhere algorithmic stability and generalization error, Technical Report TR-2002-03, University of Chicago (2002).
 2004 - Poggio dkk. membuktikan hubungan umum antara stabilitas dan konsistensi ERM. Mereka mengusulkan bentuk statistik dari stabilitas leave-one-out yang mereka sebut stabilitas CVEEEloo, dan menunjukkan bahwa itu a) cukup untuk generalisasi dalam kelas kerugian yang dibatasi, dan b) perlu dan cukup untuk konsistensi (dan dengan demikian generalisasi) dari algoritma ERM untuk fungsi kerugian tertentu seperti kerugian kuadrat, nilai absolut, dan kerugian klasifikasi biner.S. Mukherjee, P. Niyogi, T. Poggio, and R. M. Rifkin. Learning theory: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization. Adv. Comput. Math., 25(1-3):161–193, 2006.
 2010 - Shalev Shwartz dkk. memperhatikan masalah dengan hasil asli Vapnik karena hubungan kompleks antara ruang hipotesis dan kelas kerugian. Mereka mendiskusikan gagasan stabilitas yang mencakup kelas kerugian yang berbeda dan jenis pemelajaran yang berbeda, terarah dan tidak terarah.Shalev Shwartz, S., Shamir, O., Srebro, N., Sridharan, K., Learnability, Stability and Uniform Convergence, Journal of Machine Learning Research, 11(Oct):2635-2670, 2010.
 2016 - Moritz Hardt dkk. membuktikan stabilitas penurunan gradien dengan asumsi terhadap hipotesis tertentu dan berapa kali setiap instance digunakan untuk memperbarui model.Moritz Hardt, Benjamin Recht, Yoram Singer, Train faster, generalize better: Stability of stochastic gradient descent, ICML 2016.

 Definisi awal 
Kita mendefinisikan beberapa istilah yang terkait dengan rangkaian pelatihan algoritma pemelajaran, sehingga kita kemudian dapat mendefinisikan stabilitas dalam berbagai cara dan menyajikan teorema dari lapangan.

Sebuah algoritma pemelajaran mesin, juga dikenal sebagai peta pemelajaran , memetakan sebuah himpunan data latih, yang merupakan himpunan dari contoh yang berlabel , ke suatu fungsi  dari  ke , di mana  Dan  berada di ruang yang sama dengan contoh latih. Fungsinya  dipilih dari ruang hipotesis fungsi yang disebut  .

Himpunan data latih yang mana suatu algoritma dilatih didefinisikan sebagai

dan ukurannya  di dalam 

diambil iid dari distribusi yang tidak diketahui D.

Sedemikian sehingga peta pemelajaran  didefinisikan sebagai pemetaan dari  ke dalam , memetakan himpunan data latih  ke suatu fungsi  dari  ke  . Di sini, kita hanya mempertimbangkan algoritma deterministik di mana  simetris terhadap , yaitu tidak bergantung pada urutan elemen dalam data latih. Selanjutnya, kita asumsikan bahwa semua fungsi dapat diukur dan semua himpunan dapat dihitung.

Kesalahan empiris dari  adalah  .

Kesalahan sebenarnya dari  adalah 

Diberikan satu set pelatihan S berukuran m, kita akan membangun, untuk semua i = 1.... ,m, himpunan data latih yang dimodifikasi sebagai berikut:

 Dengan menghapus elemen ke-i

 Dengan mengganti elemen ke-i

 Definisi stabilitas 

 Stabilitas Hipotesis 
Sebuah algoritma  memiliki stabilitas hipotesis β sehubungan dengan fungsi kerugian V jika hal berikut berlaku:

 Stabilitas Hipotesis titik demi titik (Point-wise Hypothesis Stability) 
Sebuah algoritma  memiliki stabilitas hipotesis titik demi titik β sehubungan dengan fungsi kerugian V jika hal berikut ini berlaku:

 Stabilitas Kesalahan (Error stability) 
Sebuah algoritma  memiliki stabilitas kesalahan β sehubungan dengan fungsi kerugian V jika hal berikut berlaku:

 Stabilitas Seragam 
Sebuah algoritma  memiliki stabilitas seragam β terhadap fungsi kerugian V jika hal berikut berlaku:

Versi probabilistik dari stabilitas seragam β adalah:

Suatu algoritma dikatakan stabil jika nilainya  berkurang sebagai  .

 Stabilitas leave-one-out cross-validation (CVloo) 
Sebuah algoritma  memiliki stabilitas CVloo dinotasioan dengan β sehubungan dengan fungsi kerugian V jika hal berikut berlaku:

Definisi Stabilitas (CVloo) ekuivalen dengan stabilitas hipotesis Pointwise yang terlihat sebelumnya.

 Stabilitas kesalahan expected-leave-one-out (  ) 
Sebuah algoritma  memiliki stabilitas  jika untuk setiap n terdapat a  dan sebuah  sedemikian sehingga:

, dengan  Dan  akan menjadi nol untuk 

 Teorema klasik 
Dari Bousquet dan Elisseeff (02) :

Untuk algoritma pemelajaran simetris dengan kerugian yang terbatas, jika algoritma tersebut memiliki Stabilitas Seragam dengan definisi probabilistik di atas, maka algoritma tersebut berhasil menggeneralisasi.

Stabilitas Seragam adalah sebuah kondisi kuat yang tidak dipenuhi oleh semua algoritma, tetapi yang mengejutkan, dipenuhi oleh jumlah yang besar dan dengan kelas yang penting dalam algoritma regularisasi. Batasan generalisasi diberikan dalam artikel.

Dari Mukherjee dkk. (06) :

 Untuk algoritma pemelajaran simetris dengan kerugian terbatas, jika algoritma memiliki kedua stabilitas, yaitu Leave-one-out cross-validation  (CVloo) dan Expected-leave-one-out error  (  ) seperti yang didefinisikan di atas, maka algoritma tersebut berhasil menggeneralisasi.
 Tidak ada kondisi saja yang cukup untuk melakukan generalisasi. Namun, keduanya bersama-sama memastikan generalisasi (meskipun hal sebaliknya tidak benar).
 Khusus untuk algoritma ERM (katakanlah untuk kerugian kuadrat), Stabilitas Leave-one-out cross-validation (CVloo) diperlukan dan cukup untuk konsistensi dan generalisasi.

Ini merupakan hasil penting untuk landasan teori pemelajaran, karena menunjukkan bahwa dua sifat algoritma yang sebelumnya tidak berhubungan, stabilitas dan konsistensi, setara untuk ERM (dan fungsi kerugian tertentu). Batasan generalisasi diberikan dalam artikel.

 Algoritma yang stabil 

 Regresi linier Elisseeff, A. A study about algorithmic stability and
 their relation to generalization performances. Technical
 report. (2000)
 k-NN classifier dengan fungsi kerugian {0-1}.
 Klasifikasi Support Vector Machine (SVM) dengan kernel yang dibatasi dan regularisatornya merupakan norma dalam sebuah Reproducing Kernel Hilbert Space. Sebuah konstanta regularisasi yang besar  menghasilkan stabilitas yang baik.
 Soft margin SVM classification.
 Regresi teregularisasi Least Squares.
 Algoritma entropi relatif minimum untuk klasifikasi.
 Sebuah versi dalam bagging regularizers dengan nomor  jumlah regresi yang meningkat seiring dengan  .Rifkin, R. Everything Old is New Again: A fresh
 look at historical approaches in machine learning. Ph.D. Thesis, MIT, 2002
 Klasifikasi SVM multi-kelas.
 Semua algoritma pemelajaran dengan regularisasi Tikhonov memenuhi kriteria Stabilitas Seragam, sehingga dengan demikian, dapat menggeneralisasi.Rosasco, L. and Poggio, T. , 2009

 Referensi 

 Bacaan lebih lanjut 

S.Kutin and P.Niyogi.Almost-everywhere algorithmic stability and generalization error. In Proc. of UAI 18, 2002
S. Rakhlin, S. Mukherjee, and T. Poggio. Stability results in learning theory. Analysis and Applications, 3(4):397–419, 2005
V.N. Vapnik. The Nature of Statistical Learning Theory. Springer, 1995
Vapnik, V., Statistical Learning Theory. Wiley, New York, 1998
Poggio, T., Rifkin, R., Mukherjee, S. and Niyogi, P., "Learning Theory: general conditions for predictivity", Nature, Vol. 428, 419-422, 2004
Andre Elisseeff, Theodoros Evgeniou, Massimiliano Pontil, Stability of Randomized Learning Algorithms, Journal of Machine Learning Research 6, 55–79, 2010
Elisseeff, A. Pontil, M., Leave-one-out Error and Stability of Learning Algorithms with Applications, NATO SCIENCE SERIES SUB SERIES III COMPUTER AND SYSTEMS SCIENCES, 2003, VOL 190, pages 111-130
Shalev Shwartz, S., Shamir, O., Srebro, N., Sridharan, K.,  Learnability, Stability and Uniform Convergence, Journal of Machine Learning Research, 11(Oct):2635-2670, 2010

Kategori:Belajar
Kategori:Pemelajaran mesin