Apa definisi dimensi VC yang tepat?

8

Saya mempelajari pembelajaran mesin dari kuliah Andrew Ng Stanford dan baru saja menemukan teori dimensi VC. Menurut ceramah dan apa yang saya mengerti, definisi dimensi VC dapat diberikan sebagai,

Jika Anda dapat menemukan satu set n poin, sehingga dapat dihancurkan oleh classifier (yaitu mengklasifikasikan semua kemungkinan 2n label dengan benar) dan Anda tidak dapat menemukan set n+1 poin yang dapat dihancurkan (yaitu untuk setiap set n+1 poin setidaknya ada satu urutan pelabelan sehingga classifier tidak dapat memisahkan semua poin dengan benar), maka dimensi VC adalah n.

Profesor juga mengambil contoh dan menjelaskan ini dengan baik. Yang mana:

Membiarkan,

H={set of linear classifiers in 2 Dimensions}

Kemudian 3 poin dapat dikelompokkan berdasarkan H benar dengan memisahkan bidang hyper seperti yang ditunjukkan pada gambar berikut.

masukkan deskripsi gambar di sini

Dan itulah mengapa dimensi VC Hadalah 3. Karena untuk setiap 4 poin dalam bidang 2D, classifier linier tidak dapat menghancurkan semua kombinasi poin. Sebagai contoh,

masukkan deskripsi gambar di sini

Untuk set poin ini, tidak ada hyper plane yang dapat ditarik untuk mengklasifikasikan set ini. Jadi dimensi VC adalah 3.

Saya mendapat ide sampai di sini. Tetapi bagaimana jika kita mengikuti jenis pola?

masukkan deskripsi gambar di sini

Atau pola di mana tiga titik bertepatan satu sama lain, Di sini juga kita tidak bisa menggambar bidang hiper memisahkan antara 3 titik. Tapi tetap saja pola ini tidak dipertimbangkan dalam definisi dimensi VC. Mengapa? Hal yang sama juga dibahas dalam ceramah yang saya tonton di sini pada pukul 16:24 tetapi profesor tidak menyebutkan alasan pasti di balik ini.

Contoh penjelasan intuitif apa pun akan dihargai. Terima kasih

Kaushal28
sumber

Jawaban:

9

Definisi dimensi VC adalah: jika ada satu set n poin yang dapat dihancurkan oleh classifier dan tidak ada set n + 1 poin yang dapat dihancurkan oleh classifier, maka dimensi VC dari classifier adalah n.

Definisi ini tidak mengatakan: jika set n poin dapat dihancurkan oleh classifier ...

Jika dimensi VC classifier adalah 3, itu tidak harus menghancurkan semua kemungkinan pengaturan 3 poin.

Jika dari semua pengaturan 3 poin Anda dapat menemukan setidaknya satu pengaturan seperti itu yang dapat dihancurkan oleh classifier, dan tidak dapat menemukan 4 poin yang dapat dihancurkan, maka dimensi VC adalah 3.

Vladislav Gladkikh
sumber
1
Maka dalam hal ini kita bisa mendapatkan setidaknya satu pola dari sejumlah titik yang dapat diklasifikasikan dengan garis lurus. Misalnya pikirkan 4 poin. Dua titik merah di sisi kiri dan dua titik biru di sisi kanan akan memungkinkan untuk diklasifikasi, dan dimensi VC adalah 4. Jadi mengapa tidak mempertimbangkan ini?
Kaushal28
Rahasia - ya. Shattered - no
Vladislav Gladkikh
Jadi apa arti dari menghancurkan susunan poin? Saya sangat bingung di sini. Terima kasih
Kaushal28
Pengaturan poin dapat hancur jika ada bagian dari pengaturan ini dapat diisolasi dan dimasukkan ke dalam satu kelas. Katakanlah, Anda ingin menguji apakah pengaturan tertentu (tidak semua pengaturan yang mungkin tetapi hanya satu pengaturan tertentu) dari n poin dapat dihancurkan oleh jenis pengklasifikasi tertentu. Maka Anda pertama kali menguji apakah ada titik tunggal yang dapat diisolasi. Kemudian, jika ada 2 poin yang dapat diisolasi, maka jika ada 3 poin, dll, hingga n-1 poin dari pengaturan tertentu. Lihat di sini en.wikipedia.org/wiki/Shattered_set
Vladislav Gladkikh
1
Gambar dengan 8 subplot adalah ilustrasi yang sangat bagus tentang apa yang menghancurkan. Di sini Anda memiliki 3 poin, 2 kelas, jadi 2 ^ 3 = 8 kemungkinan pelabelan dari 3 poin ini. Semua 8 pelabelan dapat dilakukan dan diisolasi dengan garis sehingga set ini dapat dihancurkan oleh garis. Angka dengan 4 titik: ia memiliki beberapa label yang dapat diisolasi dengan garis (katakanlah, dua kiri berwarna merah, dua kanan berwarna biru) tetapi juga memiliki label yang tidak dapat diisolasi dengan garis (seperti pada Gambar: atas dan biru bawah; kiri dan kanan kiri). Karena memiliki pelabelan yang tidak dapat diisolasi dengan garis, set ini tidak hancur.
Vladislav Gladkikh