Dimensi Vapnik-Chervonenkis: mengapa empat titik pada garis tidak dapat dihancurkan oleh persegi panjang?

8

Jadi saya membaca "Pengantar Pembelajaran Mesin" edisi ke-2, oleh Bishop, et. semua. Pada halaman 27 mereka membahas Dimensi Vapnik-Chervonenkis yang,

"Jumlah maksimum poin yang dapat dihancurkan oleh H [kelas hipotesis] disebut Vapnik-Chervonenkis (VC) Dimensi H, dilambangkan VC (H) dan mengukur kapasitas H."

Sedangkan "penghancur" menunjukkan hipotesis untuk sekumpulan titik data N sehingga memisahkan contoh positif dari negatif. Dalam contoh seperti itu dikatakan bahwa "H menghancurkan N poin".h∈H

Sejauh ini saya pikir saya mengerti ini. Namun, penulis kehilangan saya dengan yang berikut:

"Misalnya, empat titik pada sebuah garis tidak dapat dihancurkan oleh segi empat."

Pasti ada beberapa konsep di sini saya tidak sepenuhnya mengerti, karena saya tidak bisa mengerti mengapa ini terjadi. Adakah yang bisa menjelaskan hal ini kepada saya?

machine-learning vc-dimension BrotherJack
sumber
2
Panggil empat poin secara berurutan. Tidak ada kotak yang berisi dan tetapi tidak termasuk dan . p,q,r,sprqs
JeffE
Ya, tetapi ada persegi panjang yang bisa berisi dan , tidak termasuk dan ; atau mengandung dan dan mengecualikan dan . Apakah Anda mengatakan bahwa masing-masing kombinasi harus memungkinkan untuk poin yang akan hancur, dan jika demikian MENGAPA INI BUKAN JAWABAN: P? pqrsqrps
BrotherJack

Jawaban:

10

Definisi "satu set dapat hancur oleh empat persegi panjang" adalah bahwa untuk setiap subset dari , ada persegi panjang yang berisi tepat bahwa bagian dan tidak termasuk sisa . Ekuivalen, setiap label poin positif dan negatif konsisten dengan setidaknya satu hipotesis di .PPPH

Sekarang perhatikan empat titik sepanjang garis di pesawat. Karena tidak ada persegi panjang yang berisi dan tetapi tidak termasuk dan , keempat titik ini tidak dapat dihancurkan oleh persegi panjang.p,q,r,sprqs

JeffE
sumber
Itu dia. Jauh lebih baik memiliki ini sebagai jawaban, bukan?
BrotherJack