Lihat sumber 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 [[Pengolahan bahasa alami|pemelajaran bahasa]] hingga [[Masalah terbalik|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 [[Pemelajaran mesin|generalisasi]].<ref>Olivier Bousquet. [https://jmlr.org/papers/v2/bousquet02a.html Stability and Generalization]. ''Journal of Machine Learning Research''. 2002. Vol. 2 (Mar). hlm. 499–526.</ref> Hal tersebut menunjukkan bahwa untuk algoritma pemelajaran dengan jumlah kelas yang besar, terutama algoritma [[Minimalkan risiko secara empiris|minimalisasi risiko empiris]], jenis stabilitas tertentu dapat memastikan generalisasi yang baik.

== Sejarah ==
Tujuan utama dalam mendesain sebuah [[Pemelajaran mesin|sistem pemelajaran mesin]] adalah untuk menjamin bahwa algoritma pemelajaran dapat melakukan [[Pemelajaran mesin|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 [[Pemelajaran terarah|algoritma pemelajaran terarah]]. Teknik tersebut di waktu itu digunakan untuk membuktikan bahwa generalisasi dapat menunjukkan bagaimana suatu algoritma bersifat [[:en:Consistent estimator|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 <math>H</math> sedemikian rupa untuk meminimalkan kesalahan empiris pada satu set latih <math>S</math>.

Hasil umum yang dibuktikan oleh [[Vladimir Vapnik]] untuk algoritma klasifikasi biner ERM menyatakan bahwa untuk setiap fungsi target dan distribusi masukan, setiap ruang hipotesis <math>H</math> dengan [[dimensi VC]] <math>d</math>, dan sebanyak <math>n</math> contoh latih, algoritmanya bersifat konsisten dan akan menghasilkan kesalahan latih yang paling banyak sebesar  <math>O\left(\sqrt{\frac{d}{n}}\right)</math> (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 <math>H</math> 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 <math>H</math>, 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 ''[[Tinggalkan satu kesalahan|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 <math>L</math>. 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.<ref>L. Devroye and Wagner, Distribution-free performance bounds for potential function rules, IEEE Trans. Inf. Theory 25(5) (1979) 601–604.</ref>
* '''1999''' - Kearns dan Ron menemukan terkait hubungan antara dimensi VC terbatas dan stabilitas.<ref>M. Kearns and D. Ron, Algorithmic stability and sanity-check bounds for leave-one-out cross-validation, Neural Comput. 11(6) (1999) 1427–1453.</ref>
* '''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.<ref>O. Bousquet and A. Elisseeff. Stability and generalization. J. Mach. Learn. Res., 2:499–526, 2002.</ref>
* '''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)).<ref>S. Kutin and P. Niyogi, Almost-everywhere algorithmic stability and generalization error, Technical Report TR-2002-03, University of Chicago (2002).</ref>
* '''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.<ref>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.</ref>
* '''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.<ref>Shalev Shwartz, S., Shamir, O., Srebro, N., Sridharan, K., Learnability, Stability and Uniform Convergence, Journal of Machine Learning Research, 11(Oct):2635-2670, 2010.</ref>
* '''2016''' - Moritz Hardt dkk. membuktikan stabilitas [[penurunan gradien]] dengan asumsi terhadap hipotesis tertentu dan berapa kali setiap ''instance'' digunakan untuk memperbarui model.<ref>Moritz Hardt, Benjamin Recht, Yoram Singer, Train faster, generalize better: Stability of stochastic gradient descent, ICML 2016.</ref>

== 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 <math>L</math>, memetakan sebuah himpunan data latih, yang merupakan himpunan dari contoh yang berlabel <math>(x,y)</math>, ke suatu fungsi <math>f</math> dari <math>X</math> ke <math>Y</math>, di mana <math>X</math> Dan <math>Y</math> berada di ruang yang sama dengan contoh latih. Fungsinya <math>f</math> dipilih dari ruang hipotesis fungsi yang disebut <math>H</math> .

Himpunan data latih yang mana suatu algoritma dilatih didefinisikan sebagai

<math>S = \{z_1 = (x_1,\ y_1)\ ,..,\ z_m = (x_m,\ y_m)\}</math>

dan ukurannya <math>m</math> di dalam <math>Z = X \times Y</math>

diambil iid dari distribusi yang tidak diketahui D.

Sedemikian sehingga peta pemelajaran <math>L</math> didefinisikan sebagai pemetaan dari <math>Z_m</math> ke dalam <math>H</math>, memetakan himpunan data latih <math>S</math> ke suatu fungsi <math>f_S</math> dari <math>X</math> ke <math>Y</math> . Di sini, kita hanya mempertimbangkan algoritma deterministik di mana <math>L</math> simetris terhadap <math>S</math>, 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 <math>f</math> adalah <math>I_S[f] = \frac{1}{n}\sum V(f,z_i)</math> .

Kesalahan sebenarnya dari <math>f</math> adalah <math>I[f] = \mathbb{E}_z V(f,z)</math>

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

<math>S^{|i} = \{z_1 ,...,\ z_{i-1},\ z_{i+1},...,\ z_m\}</math>

* Dengan mengganti elemen ke-i

<math>S^i = \{z_1 ,...,\ z_{i-1},\ z_i',\ z_{i+1},...,\ z_m\}</math>

== Definisi stabilitas ==
=== Stabilitas Hipotesis ===
Sebuah algoritma <math>L</math> memiliki stabilitas hipotesis β sehubungan dengan fungsi kerugian V jika hal berikut berlaku:

<math>\forall i\in \{1,...,m\}, \mathbb{E}_{S,z} [|V(f_S,z)-V(f_{S^{|i}},z)|]\leq\beta.</math>

=== Stabilitas Hipotesis titik demi titik (P''oint-wise Hypothesis Stability'') ===
Sebuah algoritma <math>L</math> memiliki stabilitas hipotesis titik demi titik β sehubungan dengan fungsi kerugian V jika hal berikut ini berlaku:

<math>\forall i\in\ \{1,...,m\}, \mathbb{E}_{S} [|V(f_S,z_i)-V(f_{S^{|i}},z_i)|]\leq\beta.</math>

=== Stabilitas Kesalahan (''Error stability'') ===
Sebuah algoritma <math>L</math> memiliki stabilitas kesalahan β sehubungan dengan fungsi kerugian V jika hal berikut berlaku:

<math>\forall S\in Z^m, \forall i\in\{1,...,m\}, |\mathbb{E}_z[V(f_S,z)]-\mathbb{E}_z[V(f_{S^{|i}},z)]|\leq\beta</math>

=== Stabilitas Seragam ===
Sebuah algoritma <math>L</math> memiliki stabilitas seragam β terhadap fungsi kerugian V jika hal berikut berlaku:

<math>\forall S\in Z^m, \forall i\in\{1,...,m\}, \sup_{z\in Z}|V(f_S,z)-V(f_{S^{|i}},z)|\leq\beta</math>

Versi probabilistik dari stabilitas seragam β adalah:

<math>\forall S\in Z^m, \forall i\in\{1,...,m\}, \mathbb{P}_S\{\sup_{z\in Z}|V(f_S,z)-V(f_{S^{|i}},z)|\leq\beta\}\geq1-\delta</math>

Suatu algoritma dikatakan '''stabil''' jika nilainya <math>\beta</math> berkurang sebagai <math>O(\frac{1}{m})</math> .

=== ''Stabilitas leave-one-out cross-validation'' (CVloo) ===
Sebuah algoritma <math>L</math> memiliki stabilitas CVloo dinotasioan dengan β sehubungan dengan fungsi kerugian V jika hal berikut berlaku:

<math>\forall i\in\{1,...,m\}, \mathbb{P}_S\{ |V(f_S,z_i) - V(f_{S^{|i}},z_i)|\leq\beta_{CV}\}\geq1 - \delta_{CV}</math>

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

=== Stabilitas kesalahan ''expected-leave-one-out'' ( Eloo_err ) ===
Sebuah algoritma <math>L</math> memiliki stabilitas <math>Eloo_{err}</math> jika untuk setiap n terdapat a <math>\beta_{EL}^m</math> dan sebuah <math>\delta_{EL}^m</math> sedemikian sehingga:

<math>\forall i\in\{1,...,m\}, \mathbb{P}_S\{|I[f_S]-\frac{1}{m}\sum_{i=1}^m V(f_{S^{|i}},z_i)|\leq\beta_{EL}^m\}\geq1-\delta_{EL}^m</math>, dengan <math>\beta_{EL}^m</math> Dan <math>\delta_{EL}^m</math> akan menjadi nol untuk <math>m,\rightarrow\infty</math>

== 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''  ( <math>Eloo_{err}</math> ) 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 linear|Regresi linier]] <ref>Elisseeff, A. A study about algorithmic stability and their relation to generalization performances. Technical report. (2000)</ref>
* ''k-NN classifier'' dengan fungsi kerugian {0-1}.<ref>L. Devroye and Wagner, Distribution-free performance bounds for potential function rules, IEEE Trans. Inf. Theory 25(5) (1979) 601–604.</ref>
* Klasifikasi [[Support-vector machine|Support Vector Machine]] (SVM) dengan kernel yang dibatasi dan regularisatornya merupakan norma dalam sebuah ''Reproducing Kernel Hilbert Space''. Sebuah konstanta regularisasi yang besar <math>C</math> menghasilkan stabilitas yang baik.<ref>O. Bousquet and A. Elisseeff. Stability and generalization. J. Mach. Learn. Res., 2:499–526, 2002.</ref>
* ''Soft margin SVM classification''.<ref>O. Bousquet and A. Elisseeff. Stability and generalization. J. Mach. Learn. Res., 2:499–526, 2002.</ref>
* Regresi [[Regularisasi (pemelajaran mesin)|teregularisasi]] ''Least Squares''.<ref>O. Bousquet and A. Elisseeff. Stability and generalization. J. Mach. Learn. Res., 2:499–526, 2002.</ref>
* Algoritma [[entropi]] relatif minimum untuk klasifikasi.<ref>O. Bousquet and A. Elisseeff. Stability and generalization. J. Mach. Learn. Res., 2:499–526, 2002.</ref>
* Sebuah versi dalam [[Bootstrap aggregating|bagging]] ''regularizers'' dengan nomor <math>k</math> jumlah regresi yang meningkat seiring dengan <math>n</math> .<ref>Rifkin, R. Everything Old is New Again: A fresh look at historical approaches in machine learning. Ph.D. Thesis, MIT, 2002</ref>
* Klasifikasi SVM multi-kelas.<ref>Rifkin, R. Everything Old is New Again: A fresh look at historical approaches in machine learning. Ph.D. Thesis, MIT, 2002</ref>
* Semua algoritma pemelajaran dengan regularisasi Tikhonov memenuhi kriteria Stabilitas Seragam, sehingga dengan demikian, dapat menggeneralisasi.<ref>Rosasco, L. and Poggio, T. [https://web.archive.org/web/20231126033102/http://www.mit.edu/~9.520/spring09/Classes/class10_stability.pdf], 2009</ref>

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

== Referensi ==
<references />

== Sumber dan atribusi ==

Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Stabilitas+%28teori+pemelajaran%29&oldid=29220455 Wikipedia bahasa Indonesia], revisi 29220455 (2026-05-12T15:55:24Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

<!-- WIKI_UNISSULA_PRESENTATION_V4 -->