Dimensi VC persegi panjang

9

Buku "Pengantar Pembelajaran Mesin" oleh Ethem Alpaydın menyatakan bahwa dimensi VC dari sebuah persegi panjang sejajar sumbu adalah 4. Tetapi bagaimana sebuah persegi panjang menghancurkan satu set empat titik collinear dengan titik positif dan negatif alternatif?

Bisakah seseorang menjelaskan dan membuktikan dimensi VC dari sebuah persegi panjang?

kaz
sumber

Jawaban:

20

tl; dr: Anda salah mendefinisikan dimensi VC.

Dimensi VC persegi panjang adalah kardinalitas set poin maksimum yang dapat dihancurkan oleh persegi panjang.

Dimensi VC persegi panjang adalah 4 karena ada satu set 4 poin yang dapat dihancurkan oleh persegi panjang dan setiap set 5 titik tidak dapat dihancurkan oleh persegi panjang. Jadi, sementara memang benar bahwa persegi panjang tidak dapat menghancurkan satu set empat titik collinear dengan alternatif positif dan negatif, dimensi VC masih 4 karena ada satu konfigurasi 4 poin yang dapat dihancurkan.

neutralino
sumber
11

Dimensi VC suatu algoritma adalah jumlah titik maksimum sedemikian rupa

  • ada beberapa tata letak titik-titik sedemikian rupa

  • untuk semua pelabelan titik-titik itu, algoritma tidak membuat kesalahan

Dan memang, ada tata letak empat titik (seperti berlian) sedemikian rupa sehingga persegi panjang dapat membagi set poin positif dari yang lain. Bahwa ada tata letak empat titik di mana persegi panjang akan gagal tidak relevan.

Berikut ini Langgan dengan diagram .

Andy Jones
sumber
itu jawaban yang bagus dan Langgan sangat membantu, tapi saya masih penasaran tentang ketidakmungkinan 5 poin tidak bisa dihancurkan? Saya pikir ada tata letak juga di mana Anda dapat memisahkan positif dari negatif, misalnya sebagai bentuk bintang di mana tiga poin positif dan sisanya negatif atau sebaliknya. Apakah saya melewatkan sesuatu?
Kirk Walla
0

Anggap itu seperti pertandingan antara Anda dan lawan. Anda memilih lokasi poin dan lawan memberi label, bagaimanapun dia suka. Jika dia menang dengan menemukan label yang tidak dapat dihancurkan, maka dimensi VC lebih kecil dari jumlah poin tetapi jika Anda menang, dimensi VC sama atau lebih besar dari jumlah poin. Dalam pertanyaan Anda, Anda tidak dipaksa untuk memilih pengaturan itu, Anda dapat menemukan pengaturan poin yang lebih baik, yang memungkinkan Anda menang.

Ahmad
sumber
1
Ini semua benar, tetapi Anda belum benar-benar menjawab pertanyaan, yang berkaitan dengan dimensi VC dari persegi panjang yang disejajarkan dengan sumbu. Memperluas jawaban Anda untuk menunjukkan bagaimana itu berlaku untuk pertanyaan spesifik akan sangat bagus!
jbowman