Bagaimana cara menghitung dimensi-VC?

Saya sedang mempelajari pembelajaran mesin, dan saya ingin tahu bagaimana cara menghitung dimensi VC.

Sebagai contoh:

$h(x)=\begin{cases} 1 &\mbox{if } a\leq x \leq b \\ 0 & \mbox{else } \end{cases}$ , dengan parameter .$(a,b) ∈ R^2$

Apa dimensi VC-nya?

Dimensi VC adalah taksiran untuk kapabilitas pengklasifikasi biner. Jika Anda dapat menemukan satu set poin, sehingga dapat hancur oleh classifier (yaitu mengklasifikasikan semua kemungkinan pelabelan dengan benar) dan Anda tidak dapat menemukan setiap set poin yang dapat hancur (yaitu untuk mengatur setiap dari poin setidaknya ada satu urutan pelabelan sehingga classifier tidak dapat memisahkan semua poin dengan benar), maka dimensi VC adalah .$n$$2^n$$n+1$$n+1$$n$

Dalam kasus Anda, pertama pertimbangkan dua poin dan , sehingga . Lalu ada kemungkinan label$x_1$$x_2$$x_1 < x_2$$2^2=4$

1. $x_1:1$ ,$x_2:1$
2. $x_1:0$ ,$x_2:0$
3. $x_1:1$ ,$x_2:0$
4. $x_1:0$ ,$x_2:1$

Semua pelabelan dapat dicapai melalui pengklasifikasi dengan mengatur parameter sedemikian rupa$h$$a<b \in R$

1. $a<x_1<x_2<b$
2. $x_1<x_2<a<b$
3. $a<x_1<b<x_2$
4. $x_1<a<x_2<b$

masing-masing. (Sebenarnya, dapat diasumsikan wlog tetapi cukup untuk menemukan satu set yang dapat dihancurkan.)$x_1 < x_2$

Sekarang, pertimbangkan tiga sembarang (!) Poin , , dan wlog asumsikan , maka Anda tidak dapat mencapai pelabelan (1,0,1). Seperti dalam kasus 3 di atas, label : 1 dan : 0 menyiratkan . Yang menyiratkan > b dan karena itu label harus 0. Dengan demikian, classifier tidak dapat menghancurkan set tiga titik dan oleh karena itu dimensi VC adalah 2.$x_1$$x_2$$x_3$$x_1<x_2<x_3$$x_1$$x_2$$a<x_1<b<x_2$$x_3$$x_3$

-

Mungkin menjadi lebih jelas dengan classifier yang lebih berguna. Mari kita pertimbangkan hyperplanes (yaitu garis dalam 2D).

Sangat mudah untuk menemukan satu set tiga poin yang dapat diklasifikasikan dengan benar tidak peduli bagaimana mereka dilabeli:

Untuk semua kemungkinan label, kita dapat menemukan hyperplane yang memisahkannya dengan sempurna.$2^3=8$

Namun, kami tidak dapat menemukan set 4 poin sehingga kami dapat mengklasifikasikan semua kemungkinan label dengan benar. Alih-alih bukti formal, saya mencoba menyajikan argumen visual:$2^4=16$

Asumsikan untuk saat ini, bahwa 4 poin membentuk angka dengan 4 sisi. Maka tidak mungkin untuk menemukan hyperplane yang dapat memisahkan poin dengan benar jika kita memberi label pada sudut yang berlawanan dengan label yang sama:

Jika mereka tidak membentuk angka dengan 4 sisi, ada dua "kasus batas": Poin "luar" harus berupa segitiga atau semua membentuk garis lurus. Dalam kasus segitiga, mudah untuk melihat bahwa pelabelan di mana titik "dalam" (atau titik antara dua sudut) diberi label berbeda dari yang lain tidak dapat dicapai:

Dalam kasus segmen garis, ide yang sama berlaku. Jika titik akhir diberi label berbeda dari satu titik lainnya, mereka tidak dapat dipisahkan oleh hyperplane.

Karena kami membahas semua kemungkinan formasi 4 poin dalam 2D, kami dapat menyimpulkan bahwa tidak ada 4 poin yang dapat dihancurkan. Oleh karena itu, dimensi VC harus 3.

Dimensi VC dari classifier ditentukan dengan cara berikut:

VC = 1
found = False
while True:
    for point_distribution in all possible point distributions of VC+1 points:
        allcorrect = True
        for classdist in every way the classes could be assigned to the classes:
            adjust classifier
            if classifier can't classify everything correct:
                allcorrect = False
                break
        if allcorrect:
            VC += 1
            continue
    break

Jadi hanya ada satu cara untuk menempatkan tiga poin sehingga semua distribusi kelas yang mungkin di antara penempatan titik ini dapat diklasifikasikan dengan cara yang benar.

Jika Anda tidak menempatkan ketiga titik pada satu garis, persepsi itu benar. Tetapi tidak ada cara untuk mendapatkan persepsi mengklasifikasikan semua distribusi kelas yang memungkinkan dari 4 poin, tidak peduli bagaimana Anda menempatkan poin

Contoh anda

Fitur Anda ada di . Setiap classifier setidaknya memiliki dimensi 1.$\mathbb{R}$

VC-Dimensi 2: Dapat mengklasifikasikan keempat situasi dengan benar.

1. Poin: 0 dan 42
2. Distribusi:
   • class (0) = False, class (42) = False => mengklasifikasikan ini dengan benar$a = 1337, b=3141$
   • class (0) = False, class (42) = True => mengklasifikasikan ini dengan benar$a = 40, b = 1337$
   • class (0) = Benar, kelas (42) = Salah => mengklasifikasikan ini dengan benar$a = -1, b = 1$
   • class (0) = Benar, kelas (42) = Benar => mengklasifikasikan ini dengan benar.$a = -1, b = 1337$

VC-Dimensi 3: Tidak, itu tidak berhasil. Bayangkan kelas truedan falsediperintahkan seperti True False True. Klasifikasi Anda tidak dapat menangani hal itu. Karenanya ia memiliki Dimensi-VC 2.

Bukti

Jelas, poin hanya dapat dibedakan jika mereka memiliki nilai yang berbeda. Tanpa kehilangan umum, kita dapat mengasumsikan bahwa . Oleh karena itu, classifier harus dapat mengklasifikasikan$x_1, x_2, x_3 \in \mathbb{R}$$x_1 < x_2 < x_3$

class ( ) = Benar, kelas ( ) = Salah, kelas ( ) = Benar$x_1$$x_2$$x_3$

dengan benar untuk memiliki dimensi VC 3. Agar dapat diklasifikasikan sebagai Benar, . Agar Salah, diperlukan. Sebagai dan , itu harus . Jadi situasinya saat ini: Agar diklasifikasikan sebagai Benar, diperlukan. Tetapi kendala lain sudah diperlukan . Karenanya tidak mungkin untuk mengklasifikasikan semua distribusi kelas dari 3 poin dengan benar dengan classifier ini. Karenanya ia tidak memiliki VC dimensi 3. a ≤ x 1 ≤ b x 2 x 2 < $x_1$

$$a \leq x_1 \leq b$$ $x_2$ a ≤ x 1 x 1 < x 2 b < x 2 a ≤ x 1 ≤ b < x 2 < x 3 x 3 a ≤ x 3 ≤ b b < x $$x_2 < a \qquad\text{ or }\qquad b < x_2$$ $a \leq x_1$$x_1 < x_2$$b < x_2$ $$a \leq x_1 \leq b < x_2 < x_3$$ $x_3$ $$a \leq x_3 \leq b$$ $b < x_3$