Dimensión VC del conjunto de funciones.

Question

Permitir $ \ chi $ ser un espacio de instancia y $ h \ in \ {0, 1 \} ^ \chi $ una clase con la dimensión VC finita.Para cada $ x \ en x $ consideramos $ z_x \ colon h \ rudowarrow \ {0, 1 \} $ st $ z_x (h)= h (x), \ forall h \ in h $ .

Let $ z={z_x: h \ rudotrow \ {0,1 \ \ \ \ {0,1 \} \ {0,1 \ \ \ \ \ \ in \ chi \ \ \ sport> $ .Es $ \ mathit {vcdim} (z) <2 ^ {\ mathit {vcdim} (h) +1} $ ?

---

Lo único que viene a la mente al ver esto es el Lemma Sauer, pero eso está relacionado con la función de crecimiento y no veo cómo aplicarla aquí.¿Alguien tiene alguna idea de cómo abordar esto?

Answer 1

Este es un resultado clásico de Ssouad ( Densité et Dimension ) sobre < em> dimensión de doble vc .

Let $ A $ Sea una matriz binaria. La dimensión de VC de $ A $ es el tamaño máximo de un conjunto $ s $ de columnas que son destrozadas , es decir, todas las filas posibles aparecen cuando restringimos $ A $ a las columnas en $ s $ . La dimensión de doble VC de $ a $ es la dimensión de VC de $ a ^ t $ , la transposición de $ a $ .

Supongamos que $ a ^ t $ tiene vc dimension $ 2 ^ {D + 1} $ . Luego hay un conjunto $ s $ de $ 2 ^ {D + 1} $ filas de $ A $ de modo que cuando restringimos $ a $ a este conjunto de filas, vemos todas las columnas posibles. Si numéramos las filas utilizando números binarios de longitud $ d + 1 $ , entonces, en particular, vemos las siguientes columnas: para cada $ i $ , hay una columna que contiene el $ i $ 'th bit del índice de fila. Por ejemplo, si $ d= 1 $ luego vemos las siguientes columnas: $$ \ comienzan {matrix} 0 y 0 y 0 \\ 0 y 0 y 1 \\ 0 y 1 y 0 \\ 0 y 1 y 1 \\ 1 y 0 y 0 \\ 1 y 0 y 1 \\ 1 y 1 y 0 \\ 1 y 1 y 1 \ End {matrix} $$ Por lo tanto, la dimensión de VC de $ a $ es al menos $ d + 1 $ .

Si tomamos $ d=mathrm {vc} (a) $ , luego deducimos $ \ mathrm { Vc} (a ^ t) <2 ^ {\ mathrm {vc} (a) +1} $ .