Dimensione VC del set di funzioni

Question

Let $ \ chi $ essere uno spazio di istanza e $ h \ in \ {0, 1 \} \ \ \ \CHI $ una classe con la dimensione VC finita.Per ogni $ x \ in x $ Consideriamo $ z_x \ colon h \ rayarrow \ {0, 1 \} $ st $ z_x (h)= h (x), \ forall h \ in h $ .

Let $ z={z_x: h \ raggi \ {0,1 \} \ mid x \ in \ chi \} $ . $ \ Mathit {vcdim} (z) <2 ^ {\ mathit {vcdim} (h) +1} $ ?

---

.

L'unica cosa che viene in mente quando vedi questo è il Lemma Sauer, ma è correlato alla funzione di crescita e non vedo come applicarlo qui.Chiunque abbia avuto idea su come avvicinarsi a questo?

Answer 1

Questo è un risultato classico di Assouad ( densité et dimension ) A proposito di < EM> Dimension Dual VC .

Let $ A $ Sii una matrice binaria. La dimensione VC di $ a $ è la dimensione massima di un set $ s $ di colonne che sono distrutte , cioè, tutte le righe possibili appaiono quando limitiamo $ a $ alle colonne in $ s $ . La Dual VC Dimension di $ A $ è la dimensione VC di $ a ^ T $ , la trasposizione di $ a $ .

Supponiamo che $ A ^ T $ ha la dimensione VC $ 2 ^ {d + 1} $ . Quindi c'è un set $ s $ di $ 2 ^ {d + 1} $ righe di $ A $ tale che quando limitiamo $ A $ a questo set di righe, vediamo tutte le colonne possibili. Se numeriamo le righe utilizzando numeri binari di lunghezza $ D + 1 $ , quindi in particolare vediamo le seguenti colonne: per ogni class class="container di matematica" > $ I $ , c'è una colonna che contiene la $ i $ 'il bit dell'edice della riga. Ad esempio, se $ d= 1 $ quindi vediamo le seguenti colonne: $$ \ Begin {matrix} 0 e 0 e 0 \\ 0 e 0 e 1 \\ 0 e 1 e 0 \\ 0 e 1 e 1 \\ 1 e 0 e 0 \\ 1 e 0 e 1 \\ 1 e 1 e 0 \\ 1 e 1 e 1 \ end {matrix} $$ Pertanto la dimensione VC della $ A $ è almeno $ d + 1 $ .

Se prendiamo $ d=mathrm {vc} (a) $ , quindi deduciamo $ \ mthrm { VC} (A ^ T) <2 ^ {\ MATARM {VC} (A) +1} $ .