Dimensi dan Kapasitas VC

Dimensi Vapnik-Chervonenkis mengukur kapasitas kelas model berdasarkan himpunan titik terbesar yang dapat dilabeli dengan semua cara yang mungkin, mengukur seberapa kompleks suatu pembelajar.

Definition

Dimensi Vapnik-Chervonenkis dari suatu kelas pengklasifikasi adalah jumlah titik terbesar yang dapat dilabeli oleh kelas tersebut dengan setiap cara yang mungkin; ini adalah ukuran kapasitas yang membatasi seberapa besar kelas tersebut dapat mengalami overfitting dan oleh karena itu seberapa banyak data yang dibutuhkan untuk belajar secara andal.

Scope

Topik ini mencakup ukuran kekayaan kelas hipotesis: gagasan tentang menghancurkan (shattering) sekumpulan titik, dimensi Vapnik-Chervonenkis sebagai ukuran himpunan yang hancur (shattered) terbesar, fungsi pertumbuhan, dan bagaimana ukuran kapasitas ini masuk ke dalam batas generalisasi. Ini menjelaskan mengapa kapasitas, bukan hanya jumlah parameter, yang mengatur kemampuan untuk menggeneralisasi.

Core questions

• Apa artinya bagi suatu kelas model untuk menghancurkan (shatter) sekumpulan titik?
• Bagaimana dimensi Vapnik-Chervonenkis didefinisikan dan dihitung?
• Mengapa kapasitas, bukan jumlah parameter, yang mengatur generalisasi?
• Bagaimana kapasitas masuk ke dalam batas-batas pada celah antara pelatihan dan kesalahan sebenarnya?

Key theories

Shattering dan kapasitas

Suatu kelas menghancurkan (shatters) sekumpulan titik jika ia dapat merealisasikan setiap pelabelan yang mungkin dari titik-titik tersebut; himpunan terbesar semacam itu mendefinisikan dimensi Vapnik-Chervonenkis, ukuran bebas distribusi tentang seberapa fleksibel kelas tersebut.

Kapasitas mengontrol konvergensi seragam

Kapasitas terbatas memastikan bahwa kesalahan empiris konvergen ke kesalahan sebenarnya secara seragam di seluruh kelas, sehingga pembelajar dengan dimensi Vapnik-Chervonenkis yang terbatas tidak dapat mengalami overfitting secara sewenang-wenang seiring bertambahnya data.

Kapasitas versus jumlah parameter

Kapasitas, bukan jumlah parameter mentah, yang menentukan generalisasi, sehingga dua model dengan jumlah parameter yang sama dapat sangat berbeda dalam seberapa banyak data yang mereka butuhkan.

Clinical relevance

Dimensi Vapnik-Chervonenkis menyediakan ukuran kapasitas sentral dari teori pembelajaran klasik dan membenarkan praktik pengendalian kompleksitas model; ini mendasari analisis berbasis margin dari support vector machines dan membingkai upaya berkelanjutan untuk memahami mengapa beberapa model berkapasitas sangat tinggi tetap dapat menggeneralisasi.

History

Vapnik dan Chervonenkis memperkenalkan dimensi yang menyandang nama mereka dalam karya dari akhir tahun 1960-an dan makalah tahun 1971 tentang konvergensi seragam, membangun teori kapasitas yang bebas distribusi. Konsep ini menjadi dasar bagi support vector machines dan untuk analisis generalisasi yang lebih luas.

Key figures

• Vladimir Vapnik
• Alexey Chervonenkis

Seminal works

• vapnik1971
• vapnik1995
• hastie2009

Frequently asked questions

Apa arti shattering?

Sekumpulan titik dihancurkan (shattered) oleh suatu kelas model jika, untuk setiap penugasan label yang mungkin pada titik-titik tersebut, beberapa model dalam kelas tersebut menghasilkan pelabelan yang persis sama. Ukuran himpunan yang dapat dihancurkan (shatterable) terbesar adalah dimensi Vapnik-Chervonenkis.

Apakah model dengan lebih banyak parameter selalu memiliki kapasitas yang lebih tinggi?

Belum tentu. Kapasitas diukur dengan dimensi Vapnik-Chervonenkis atau kuantitas terkait, yang dapat berbeda dari jumlah parameter. Ukuran kompleksitas yang tepat untuk generalisasi adalah kapasitas, bukan hanya berapa banyak parameter yang dimiliki suatu model.