Dimensão VC do conjunto de funções

Question

Deixe $ \ chi $ ser um espaço de instância e $ h \ in \ {0, 1 \} ^ \Chi $ uma classe com a dimensão vc finita.Para cada $ x \ em x $ Consideramos $ z_x \ colon h \ righttarrow {0, 1 \} $ st $ z_x (h)= h (x), \ forall h \ em h $ .

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

---

.

A única coisa que vem à mente quando vê isso é o Lema do Sauer, mas isso está relacionado à função de crescimento e não vejo como aplicá-lo aqui.Alguém tem alguma ideia de como se aproximar disso?

Answer 1

Este é um resultado clássico de Assouad ( Densité et dimensão ) sobre < em> dimensão dupla VC .

Deixe $ a $ ser uma matriz binária. A dimensão VC da $ a $ é o tamanho máximo de um conjunto $ s $ de colunas que são quebradas , isto é, todas as linhas possíveis aparecem quando restringimos $ a $ para as colunas na $ S $ . A dimensão dupla VC da $ a $ é a dimensão VC da $ a ^ t $ , a transposição de $ a $ .

Suponha que $ a ^ t $ tenha dimensão vc $ 2 ^ {d + 1} $ . Em seguida, há um conjunto $ s $ de $ 2 ^ {d + 1} $ linhas de $ a $ tal que, quando restringimos $ a $ para este conjunto de linhas, vemos todas as colunas possíveis. Se nós número as linhas usando números binários de comprimento $ D + 1 $ , então, em particular, vemos as seguintes colunas: para cada $ i $ , há uma coluna que contém a $ i $ 'th do índice de linha. Por exemplo, se $ D= 1 $ então vemos as seguintes colunas: $$ \ begin {matrix} 0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 e 0 \\ 0 & 1 e 1 \\ 1 & 0 e 0 \\ 1 & 0 e 1 \\ 1 e 1 e 0 \\ 1 e 1 e 1 \ fim {matrix} $$ Portanto, a dimensão VC da $ a $ é pelo menos $ D + 1 $ .

Se tomarmos $ D=mathrm {vc} (a) $ , então deduzimos $ \ mathrm { Vc} (a ^ t) <2 ^ {\ mathrm {vc} (a) +1} $ .