TL, DR: Tampaknya, bertentangan dengan saran yang sering diulang, validasi silang tinggalkan-satu-keluar (LOO-CV) - yaitu,lipat CV dengan(jumlah lipatan) sama dengan(angka pengamatan pelatihan) - menghasilkan perkiraan kesalahan generalisasi yang merupakanvariabel terkecil untuk setiap, bukan variabel terbanyak, dengan asumsikondisi stabilitas tertentubaik pada model / algoritma, dataset, atau keduanya (saya tidak yakin yang mana benar karena saya tidak begitu mengerti kondisi stabilitas ini).K N $K$$K$$N$$K$

• Dapatkah seseorang dengan jelas menjelaskan apa sebenarnya kondisi stabilitas ini?
• Benarkah regresi linier adalah salah satu dari algoritma "stabil", yang secara tidak langsung menyatakan bahwa dalam konteks itu, LOO-CV adalah pilihan terbaik dari CV sejauh menyangkut bias dan varian estimasi kesalahan generalisasi?

Kebijaksanaan konvensional adalah bahwa pilihan dalam -fold CV mengikuti bias-variance tradeoff, nilai-nilai lebih rendah (mendekati 2) mengarah pada perkiraan kesalahan generalisasi yang memiliki bias lebih pesimistis, tetapi varians yang lebih rendah, sedangkan varians yang lebih rendah, sedangkan nilai yang lebih tinggi dari (mendekati ) menyebabkan perkiraan yang kurang bias, tetapi dengan varians yang lebih besar. Penjelasan konvensional untuk fenomena peningkatan varians dengan ini mungkin diberikan paling menonjol dalam The Elements of Statistics Learning (Bagian 7.10.1):K K K N $K$$K$$K$$K$$N$$K$

Dengan K = N, penduga cross-validation kira-kira tidak bias untuk kesalahan prediksi yang sebenarnya (diharapkan), tetapi dapat memiliki varians yang tinggi karena N "set pelatihan" sangat mirip satu sama lain.

Implikasinya adalah bahwa kesalahan validasi lebih tinggi berkorelasi sehingga jumlah mereka lebih bervariasi. Alur penalaran ini telah diulangi dalam banyak jawaban di situs ini (misalnya, di sini , di sini , di sini , di sini , di sini , di sini , dan di sini ) serta di berbagai blog dan lain-lain. Tetapi analisis terperinci hampir tidak pernah diberikan, sebagai gantinya hanya intuisi atau sketsa singkat tentang seperti apa analisis itu nantinya.$N$

Namun seseorang dapat menemukan pernyataan kontradiktif, biasanya mengutip kondisi "stabilitas" tertentu yang saya tidak benar-benar mengerti. Sebagai contoh, jawaban kontradiktif ini mengutip beberapa paragraf dari makalah 2015 yang mengatakan, antara lain, "Untuk model / prosedur pemodelan dengan ketidakstabilan rendah , LOO sering memiliki variabilitas terkecil" (penekanan ditambahkan). Makalah ini (bagian 5.2) tampaknya setuju bahwa LOO mewakili pilihan variabel paling sedikit dari selama model / algoritma "stabil." Bahkan mengambil sikap lain tentang masalah ini, ada juga makalah ini (Corollary 2), yang mengatakan "Variansi fold cross validation [...] tidak bergantung padak $K$$k$$k$, "lagi mengutip kondisi" stabilitas "tertentu.

Penjelasan tentang mengapa LOO mungkin adalah -Fold variabel yang paling variabel cukup intuitif, tetapi ada kontra-intuisi. Estimasi CV akhir dari mean squared error (MSE) adalah rata-rata estimasi MSE di setiap lipatan. Jadi, ketika meningkat hingga , estimasi CV adalah rata-rata dari meningkatnya jumlah variabel acak. Dan kita tahu bahwa varians dari rata-rata berkurang dengan jumlah variabel yang dirata-rata. Jadi agar LOO menjadi yang paling variabel CV ganda, itu harus benar bahwa peningkatan varians karena meningkatnya hubungan antara perkiraan MSE melebihi penurunan varians karena jumlah yang lebih besar dari lipatan yang rata-rata lebihK N $K$$K$$N$$K$. Dan sama sekali tidak jelas bahwa ini benar.

Setelah benar-benar bingung memikirkan semua ini, saya memutuskan untuk menjalankan sedikit simulasi untuk kasus regresi linier. Aku simulasi 10.000 dataset dengan = 50 dan 3 prediktor berkorelasi, setiap kali memperkirakan kesalahan generalisasi menggunakan ganda CV dengan = 2, 5, 10, atau 50 = . Kode R di sini. Berikut adalah rata-rata dan variasi hasil estimasi CV di seluruh 10.000 dataset (dalam unit UMK):K K $N$$K$$K$$N$

         k = 2 k = 5 k = 10 k = n = 50
mean     1.187 1.108  1.094      1.087
variance 0.094 0.058  0.053      0.051

Hasil ini menunjukkan pola yang diharapkan bahwa nilai-nilai yang lebih tinggi mengarah ke bias yang kurang pesimistis, tetapi juga muncul untuk mengkonfirmasi bahwa varians estimasi CV adalah terendah, bukan tertinggi, dalam kasus LOO.$K$

Jadi tampak bahwa regresi linier adalah salah satu kasus "stabil" yang disebutkan dalam makalah di atas, di mana peningkatan dikaitkan dengan penurunan daripada peningkatan varians dalam perkiraan CV. Tapi yang masih saya tidak mengerti adalah:$K$

• Apa tepatnya kondisi "stabilitas" ini? Apakah ini berlaku untuk model / algoritma, kumpulan data, atau keduanya sampai batas tertentu?
• Adakah cara intuitif untuk memikirkan stabilitas ini?
• Apa contoh lain dari model / algoritma atau dataset yang stabil dan tidak stabil?
• Apakah relatif aman untuk mengasumsikan bahwa sebagian besar model / algoritma atau kumpulan data "stabil" dan oleh karena itu umumnya harus dipilih setinggi layak secara komputasi?$K$

Jawaban ini menindaklanjuti jawaban saya di Bias dan varians dalam validasi lintas-keluar-keluar vs K-fold yang membahas mengapa LOOCV tidak selalu mengarah ke varian yang lebih tinggi. Mengikuti pendekatan yang sama, saya akan mencoba untuk menyoroti kasus di mana LOOCV memang mengarah ke varian yang lebih tinggi di hadapan pencilan dan "model tidak stabil".

Stabilitas algoritma (teori pembelajaran)

Topik stabilitas algoritmik adalah yang terbaru dan beberapa klasik, hasil yang berpengaruh telah dibuktikan dalam 20 tahun terakhir. Berikut adalah beberapa makalah yang sering dikutip

• Heuristik ketidakstabilan dan stabilisasi dalam pemilihan model (1996): Leo Breiman
• Stabilitas algoritma dan batas kewarasan untuk LOOCV (1997): Kearns, Ron
• Stabilitas dan Generalisasi (2002): Bousquet, Elisseef
• Validasi Lintas dan Stabilitas Mean-Square (2011) Kale, Kumar, Vassilvitskii
• Hampir di mana-mana stabilitas algoritmik dan kesalahan generalisasi (2012): Kutin, Niyogi
• Beberapa catatan tentang topik: University of Arizona

Halaman terbaik untuk mendapatkan pemahaman tentu saja halaman wikipedia yang menyediakan ringkasan yang sangat baik yang ditulis oleh pengguna yang mungkin sangat berpengetahuan.

Definisi stabilitas yang intuitif

Secara intuitif, algoritma stabil adalah salah satu yang prediksinya tidak banyak berubah ketika data pelatihan sedikit dimodifikasi.

Secara formal, ada setengah lusin versi stabilitas, dihubungkan bersama oleh kondisi teknis dan hierarki, lihat grafik ini dari sini misalnya:

Namun tujuannya sederhana, kami ingin mendapatkan batasan ketat pada kesalahan generalisasi dari algoritma pembelajaran tertentu, ketika algoritma memenuhi kriteria stabilitas. Seperti yang diharapkan, semakin ketat kriteria stabilitas, semakin ketat batas yang terkait.

Notasi

Notasi berikut berasal dari artikel wikipedia, yang dengan sendirinya menyalin kertas Bousquet dan Elisseef:

• Set pelatihan diambil iid dari distribusi yang tidak diketahui D$S = \{ z_1 = (x_1,y_1), ..., z_m = (x_m, y_m)\}$
• Fungsi kerugian dari hipotesis sehubungan dengan contoh didefinisikan sebagaif z V ( f , z $V$$f$$z$$V(f,z)$
• Kami memodifikasi set pelatihan dengan menghapus elemen ke- :S | i = { z 1 , . . . , Z i - 1 , z i + 1 , . . . , z m$i$$S^{|i} = \{ z_1,...,z_{i-1}, z_{i+1},...,z_m\}$
• Atau dengan mengganti elemen ke- :S i = { z 1 , . . . , z i - 1 , $i$$S^{i} = \{ z_1,...,z_{i-1}, z_i^{'}, z_{i+1},...,z_m\}$

Definisi formal

Mungkin gagasan stabilitas terkuat yang diharapkan dapat dipatuhi oleh algoritma pembelajaran yang menarik adalah stabilitas seragam :

Stabilitas seragam Suatu algoritma memiliki stabilitas seragam dengan menghormati fungsi kehilangan jika yang berikut ini berlaku:$\beta$$V$

Dianggap sebagai fungsi , istilah dapat ditulis sebagai . Kami mengatakan algoritma ini stabil ketika berkurang sebagai . Bentuk stabilitas yang sedikit lebih lemah adalah:$m$$\beta$$\beta_m$$\beta_m$$\frac{1}{m}$

Stabilitas hipotesis

Jika satu titik dihapus, perbedaan dalam hasil algoritma pembelajaran diukur dengan perbedaan absolut rata-rata kerugian ( norma ). Secara intuitif: perubahan kecil pada sampel hanya dapat menyebabkan algoritme pindah ke hipotesis terdekat.$L_1$

Keuntungan dari bentuk-bentuk stabilitas ini adalah mereka memberikan batasan untuk bias dan varian dari algoritma stabil. Secara khusus, Bousquet membuktikan batas-batas ini untuk stabilitas Seragam dan Hipotesis pada tahun 2002. Sejak itu, banyak pekerjaan telah dilakukan untuk mencoba melonggarkan kondisi stabilitas dan menggeneralisasi batas, misalnya pada tahun 2011, Kale, Kumar, Vassilvitskii berpendapat bahwa stabilitas persegi berarti memberikan batas varians kuantitatif pengurangan varians yang lebih baik.

Beberapa contoh algoritma stabil

Algoritme berikut telah terbukti stabil dan telah membuktikan batas generalisasi:

• Regresi kuadrat terkecil teregulasi (dengan tepat sebelumnya)
• Klasifikasi KNN dengan fungsi kerugian 0-1
• SVM dengan kernel terikat dan konstanta regularisasi besar
• SVM margin lunak
• Algoritma entropi relatif minimum untuk klasifikasi
• Versi pengatur pengantongan

Simulasi eksperimental

Mengulangi percobaan dari utas sebelumnya ( lihat di sini ), kami sekarang memperkenalkan rasio pencilan tertentu dalam kumpulan data. Khususnya:

• 97% dari data memiliki noise yang seragam$[-.5,.5]$
• 3% dari data dengan noise seragam$[-20,20]$

Karena model polinomial orde tidak diatur, itu akan sangat dipengaruhi oleh kehadiran beberapa outlier untuk set data kecil. Untuk dataset yang lebih besar, atau ketika ada lebih banyak outlier, efeknya lebih kecil karena mereka cenderung membatalkan. Lihat di bawah untuk dua model untuk 60 dan 200 titik data.$3$

Melakukan simulasi seperti sebelumnya dan memplot rata-rata MSE yang dihasilkan dan varian MSE memberikan hasil yang sangat mirip dengan Eksperimen 2 dari kertas Bengio & Grandvalet 2004 .

Sisi Kiri : tidak ada pencilan. Sisi Kanan : 3% pencilan.

(lihat kertas tertaut untuk penjelasan tentang gambar terakhir)

Penjelasan

Mengutip jawaban Yves Grandvalet di utas lainnya:

Secara intuitif, [dalam situasi algoritma yang tidak stabil], cuti-keluar-keluar mungkin buta terhadap ketidakstabilan yang ada, tetapi mungkin tidak dipicu oleh perubahan satu titik dalam data pelatihan, yang membuatnya sangat bervariasi terhadap realisasi perlengkapan latihan.

Dalam praktiknya cukup sulit untuk mensimulasikan peningkatan varian karena LOOCV. Ini membutuhkan kombinasi ketidakstabilan tertentu, beberapa outlier tetapi tidak terlalu banyak, dan sejumlah besar iterasi. Mungkin ini diharapkan karena regresi linier telah terbukti cukup stabil. Eksperimen yang menarik adalah mengulangi ini untuk data dimensi yang lebih tinggi dan algoritma yang lebih tidak stabil (misalnya pohon keputusan)

Saya akan memberikan jawaban saya dalam konteks paragraf yang Anda kutip:

Dengan K = N, penduga cross-validation kira-kira tidak bias untuk kesalahan prediksi yang sebenarnya (diharapkan), tetapi dapat memiliki varians yang tinggi karena N "set pelatihan" sangat mirip satu sama lain.

Estimator CV dari kesalahan prediksi yang sebenarnya (diharapkan) didasarkan pada contoh himpunan pelatihan, jadi di sini, ekspektasinya melebihi sampel himpunan pelatihan, ketika saya memahaminya dengan benar.

Jadi, apa yang ayat ini tentang "varians tinggi" kemudian katakan adalah bahwa ada perbedaan "tinggi" antara kesalahan yang diharapkan dan kesalahan yang diperkirakan oleh CV (yang di sini, rata-rata di atas lipatan).

Ini masuk akal karena model ini cocok untuk satu set pelatihan tertentu dan karena semua lipatan pelatihan sangat mirip dalam waktu keluar satu kali. Namun, sementara lipatan pelatihan sangat mirip dalam putaran CV, estimasi mungkin berbeda banyak jika kita menukar sampel pelatihan untuk CV. Dalam k-fold CV, karena kami "mendiversifikasi" lipatan pelatihan, kami memiliki pengaruh rata-rata, dan di seluruh lipatan k, liputannya kemudian lebih sedikit bervariasi.

Atau dengan kata lain, penaksir CV cuti-keluar-keluar pada dasarnya hampir seperti metode penahan jika Anda tidak memutar lipatan dan mendasarkan perkiraan kesalahan Anda pada satu set validasi. Sekali lagi, lebih dari contoh pelatihan, akan ada varians yang tinggi dibandingkan dengan perkiraan dari k-fold, di mana Anda rata-rata lebih dari lipatan dengan sudah melatih model yang agak beragam dalam putaran k-fold (dengan kata lain, jika Anda menukar set pelatihan, perkiraan dari kesalahan melalui k-fold mungkin tidak akan terlalu bervariasi).

EDIT:

Ketika saya membaca beberapa jawaban di sini di cross-divalidasi dan internet secara umum, saya pikir tampaknya ada beberapa kebingungan penduga mana yang kita maksud. Saya pikir beberapa orang merujuk pada model yang memiliki varian tinggi (dengan ML bicara untuk kerugian memiliki komponen varian dominan) vs varian tinggi penduga k-fold CV. Dan, rangkaian jawaban lain merujuk pada varians sebagai varians sampel mengenai lipatan ketika seseorang mengatakan "k-fold memiliki varian tinggi". Jadi, saya sarankan untuk lebih spesifik, karena jawabannya berbeda.

Kami telah melalui ini sebelumnya - Anda terlalu matematis tentang kuda mati. Lihat karya klasik Ron Kohavi (Stanford-Univ) di CV dan dilema bias-varians di sini . Setelah selesai membaca ini, Anda tidak ingin melakukan LOOCV, dan kemungkinan akan tertarik dengan CV 10 kali lipat dan / atau CV bootstrap-bias.

Anda juga harus berpikir tentang dataset besar, yang LOOCV terlalu mahal secara komputasi. Saat ini, LOOCV sebenarnya bukan pilihan dalam alur kerja / jalur pipa kebanyakan grup.

Apa tepatnya kondisi "stabilitas" ini? Apakah ini berlaku untuk model / algoritma, kumpulan data, atau keduanya sampai batas tertentu?

Di alam semesta semua fungsi biaya dan alam semesta semua set fitur, saya tidak akan berasumsi ada keseluruhan indeks "stabilitas", karena itu tidak akan dapat diterima, dan akan terlalu rentan untuk mogok di bawah seperangkat besar tak terhingga banyaknya kondisi. Pada dasarnya, sesuai ketika parameter df dan / atau # sangat besar sehingga dibutuhkan lebih banyak data pelatihan. Bias juga akan lebih besar untuk , karena lebih banyak data digunakan, dan varians akan menjadi nol secara artifisial, karena dataset pelatihan terlalu mirip satu sama lain. Anda juga akan belajar lebih banyak noise dalam data saat . k = n k = $k=n$$k=n$$k=n$

LREG sebagai penggolong akan bekerja ketika data dipisahkan secara linear, tetapi rata-rata biasnya akan terlalu tinggi, karena banyak dataset tidak dapat dipisahkan secara linear.

Adakah cara intuitif untuk memikirkan stabilitas ini?

Tidak dalam pandangan saya - karena tidak ada aturan umum tentang stabilitas.

Apa contoh lain dari model / algoritma atau dataset yang stabil dan tidak stabil?

Ini bersifat terbuka dan terlalu luas, karena sejumlah besar tanggapan yang tidak terbatas dapat dibuat-buat, yang tidak akan membantu.

Apakah relatif aman untuk mengasumsikan bahwa sebagian besar model / algoritma atau kumpulan data "stabil" dan oleh karena itu umumnya harus dipilih setinggi layak secara komputasi?$K$

Tidak. Tidak. Hanya mengandalkan mengasumsikan bahwa Anda mempercayai data tersebut. Contohnya adalah Hutan Acak, yang benar-benar tidak ada . Sementara sekitar 37% dari data akan digunakan untuk pengujian (rata-rata, 37% objek tidak dipilih saat pengambilan sampel dengan penggantian), misalnya ada 5.000 set data berbeda (bootstraps) yang masing-masing dibagi menjadi pelatihan / pengujian secara berbeda. Contoh Anda diambil dari makalah yang diasumsikan bahwa setiap dataset yang digunakan adalah realisasi data yang sebenarnya - yang merupakan asumsi yang keliru. $k$$k$

Dengan adanya bootstrap, aturan stabilitas di sekitar dapat diterima, karena sampel data yang digunakan untuk pendekatan CV langsung yang melibatkan bukanlah realisasi sebenarnya dari semesta dari semua data dari mana sampel diperoleh. $k$$k$