VC Dimension of Circle, un caso speciale

Question

Ho letto che un cerchio può frantumare 3 punti nello spazio 2D, che in realtà è la VC Dimension of Circle.

Diciamo che abbiamo tre punti (5,2) (5,4) e (5,6). Come posso disegnare un cerchio dove (5,2) & (5,6) sono inclusi con fuori (5,4)? Non e possibile! Se non può andare in frantumi, allora come mai VC Dimension è 3 per un cerchio. O sbaglio nell'assumere che nella definizione di VC Dimension; un'ipotesi deve frantumare tutti i possibili scenari di tutti i possibili sottoinsiemi di spazio?

Cordiali saluti

Answer 1

La dimensione VC è il numero massimo di punti che può essere distrutto. {(5,2), (5,4), (5,6)} non possono essere distrutti dai cerchi, ma {(5,2), (5,4), (6,6)} possono essere frantumati dalle cerchie , quindi la dimensione VC è almeno 3. Dimostrando che è esattamente 3 è più difficile.

C'è un punto tecnico qui relativo alla risposta di Qnan. Se il classificatore del cerchio classifica sempre i punti all'interno del cerchio come 1 e quelli al di fuori del cerchio come 0, allora {(5,2), (5,4), (5,6)} non possono essere distrutti. D'altra parte, se il classificatore del cerchio può anche classificare i punti all'interno del cerchio come 0, allora {(5,2), (5,4), (5,6)} può essere frantumato come spiegato da Qnan.

QNAN, per quanto riguarda il tuo commento, se uno dice che n è il maggior numero di punti con la proprietà P, poi a dimostrare che n> = m, è sufficiente trovare qualsiasi collezione di m punti con proprietà P Se trovi uno o mille set di m punti che non hanno la proprietà P, allora questo non prova nulla di n. (A meno che non sia elencato ogni possibile insieme di punti di misura m.)

La dimensione VC è il numero massimo di punti che possono essere frantumati. Se la dimensione VC di un classificatore è 100, è comunque possibile trovare 3 punti che non possono essere distrutti dal classificatore. Potremmo definire la dimensione VCB il numero più grande n tale che tutti i gruppi di dimensioni n o inferiori possano essere frantumati. L'esempio originale di Asymptote mostra che la dimensione VCB dei classificatori circolari (supponendo 1 all'interno del cerchio e 0 all'esterno del cerchio) sul piano cartesiano è minore o uguale a 2 perché quei tre punti non possono essere frantumati; tuttavia, l'esempio di Asymptote non mostra che la dimensione VC è inferiore a 3 perché ci sono altri gruppi di punti di dimensione 3 che possono essere frantumati.

Answer 2

Il punto è che il cerchio può essere disegnato in modo tale che tutti i punti appartenenti a una classe siano all'interno, mentre il resto è all'esterno. Non importa quale classe sia, dal momento che lo scambio delle etichette richiede solo che il classificatore sia invertito.

Nel tuo caso, separare (5,2) e (5,6) da (5,4) è banalmente compreso includendo solo quest'ultimo nel cerchio. Per un classificatore, "dentro" e "fuori" non contano. Ciò che importa è che possono essere classificati con un errore 0.

EDIT rigor di termini, la dimensione VC è definito per classificatori con parametri, e ci sono più classificatori, il cui confine sarebbe descritto come un "circolo". Ad esempio, f(x)=(x-x0)*(x-x0) non può frantumare un insieme di tre punti su una riga, ma f(x)=a*(x-x0)*(x-x0) può, ed entrambi i classificatori hanno un limite circolare. La dimensione VC del secondo è in realtà 3, mentre quella del primo è 2.