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 $H$ sedemikian rupa untuk meminimalkan kesalahan empiris pada satu set latih $S$.

Hasil umum yang dibuktikan oleh Vladimir Vapnik untuk algoritma klasifikasi biner ERM menyatakan bahwa untuk setiap fungsi target dan distribusi masukan, setiap ruang hipotesis $H$ dengan dimensi VC $d$, dan sebanyak $n$ contoh latih, algoritmanya bersifat konsisten dan akan menghasilkan kesalahan latih yang paling banyak sebesar $O\left({\sqrt {\frac {d}{n}}}\right)$ (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 $H$ 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 $H$, 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 $L$. 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.
• 1999 - Kearns dan Ron menemukan terkait hubungan antara dimensi VC terbatas dan stabilitas.
• 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.
• 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)).
• 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.
• 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.
• 2016 - Moritz Hardt dkk. membuktikan stabilitas penurunan gradien dengan asumsi terhadap hipotesis tertentu dan berapa kali setiap instance digunakan untuk memperbarui model.

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

Himpunan data latih yang mana suatu algoritma dilatih didefinisikan sebagai

$S=\{z_{1}=(x_{1},\ y_{1})\ ,..,\ z_{m}=(x_{m},\ y_{m})\}$

dan ukurannya $m$ di dalam $Z=X\times Y$

diambil iid dari distribusi yang tidak diketahui D.

Sedemikian sehingga peta pemelajaran $L$ didefinisikan sebagai pemetaan dari $Z_{m}$ ke dalam $H$, memetakan himpunan data latih $S$ ke suatu fungsi $f_{S}$ dari $X$ ke $Y$ . Di sini, kita hanya mempertimbangkan algoritma deterministik dimana $L$ simetris terhadap $S$, 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 $f$ adalah $I_{S}[f]={\frac {1}{n}}\sum V(f,z_{i})$ .

Kesalahan sebenarnya dari $f$ adalah $I[f]=\mathbb {E} _{z}V(f,z)$

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

$S^{|i}=\{z_{1},...,\ z_{i-1},\ z_{i+1},...,\ z_{m}\}$

• Dengan mengganti elemen ke-i

$S^{i}=\{z_{1},...,\ z_{i-1},\ z_{i}',\ z_{i+1},...,\ z_{m}\}$

Definisi stabilitas

Stabilitas Hipotesis

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

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

Stabilitas Hipotesis titik demi titik (Point-wise Hypothesis Stability)

Sebuah algoritma $L$ memiliki stabilitas hipotesis titik demi titik β sehubungan dengan fungsi kerugian V jika hal berikut ini berlaku:

$\forall i\in \ \{1,...,m\},\mathbb {E} _{S}[|V(f_{S},z_{i})-V(f_{S^{|i}},z_{i})|]\leq \beta .$

Stabilitas Kesalahan (Error stability)

Sebuah algoritma $L$ memiliki stabilitas kesalahan β sehubungan dengan fungsi kerugian V jika hal berikut berlaku:

$\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$

Stabilitas Seragam

Sebuah algoritma $L$ memiliki stabilitas seragam β terhadap fungsi kerugian V jika hal berikut berlaku:

$\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$

Versi probabilistik dari stabilitas seragam β adalah:

$\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 \}\geq 1-\delta$

Suatu algoritma dikatakan stabil jika nilainya $\beta$ berkurang sebagai $O({\frac {1}{m}})$ .

Stabilitas leave-one-out cross-validation (CVloo)

Sebuah algoritma $L$ memiliki stabilitas CVloo dinotasioan dengan β sehubungan dengan fungsi kerugian V jika hal berikut berlaku:

$\forall i\in \{1,...,m\},\mathbb {P} _{S}\{|V(f_{S},z_{i})-V(f_{S^{|i}},z_{i})|\leq \beta _{CV}\}\geq 1-\delta _{CV}$

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

Stabilitas kesalahan expected-leave-one-out ( $Eloo_{err}$ )

Sebuah algoritma $L$ memiliki stabilitas $Eloo_{err}$ jika untuk setiap n terdapat a $\beta _{EL}^{m}$ dan sebuah $\delta _{EL}^{m}$ sedemikian sehingga:

$\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}\}\geq 1-\delta _{EL}^{m}$, dengan $\beta _{EL}^{m}$ Dan $\delta _{EL}^{m}$ akan menjadi nol untuk $m,\rightarrow \infty$

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 ( $Eloo_{err}$ ) 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
• 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 $C$ 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 $k$ jumlah regresi yang meningkat seiring dengan $n$ .
• Klasifikasi SVM multi-kelas.
• Semua algoritma pemelajaran dengan regularisasi Tikhonov memenuhi kriteria Stabilitas Seragam, sehingga dengan demikian, dapat menggeneralisasi.

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