VC-Dimension von Funktionen

Question

$ \ chi $ Seien Sie ein Instanzraum und $ h \ in \ {0, 1 \} ^ \Chi $ Eine Klasse mit endlicher VC-Dimension.Für jeden $ x \ in x $ berücksichtigen wir $ z_x \ colon h \ rightarrow \ {0, 1 \} $ st $ Z_X (H)= H (X), \ Vorall H \ in H $ .

$ Z={Z_X: H \ Rightarrow \ {0,1 \ \ \ \ mid x \ in \ chi \} $ .Ist $ \ mathit {vcdim} (z) <2 ^ {\ Mathit {vcdim} (h) +1} $ ?

---

Das einzige, was in den Sinn kommt, wenn Sie dies sehen, ist das Sauer Lemma, aber das ist mit der Wachstumsfunktion verbunden, und ich sehe nicht, wie Sie es hier anwenden.Jeder hat eine Idee, wie man sich annähern kann?

Answer 1

Dies ist ein klassisches Ergebnis von Assouad ( densité et maße ) über < EM> Dual VC-Dimension .

Lassen Sie $ A $ eine binäre Matrix sein. Die VC-Dimension von $ A $ ist die maximale Größe eines Set $ s $ von Säulen, die zerschlagen sind , das heißt, alle möglichen Zeilen werden angezeigt, wenn wir $ A $ an die Spalten in $ S $ einschränken. Die Dual-VC-Dimension von $ A $ ist die VC-Dimension von $ A ^ T $ , der Transponierung von $ A $ .

Angenommen, der $ A ^ T $ hat vc dimension $ 2 ^ {d + 1} $ . Dann gibt es einen Set $ s $ von $ 2 ^ {d + 1} $ Zeilen von $ A $ so, dass, wenn wir $ A $ an diesen Zeilensatz einschränken, alle möglichen Spalten sehen. Wenn wir die Zeilen mit binären Nummern der Länge $ d + 1 $ , dann sehen wir insbesondere die folgenden Spalten an: Für jeden $ i $ , es gibt eine Spalte, die den $ i $ 'ter Bit des Zeilenindex enthält. Wenn zum Beispiel $ d= 1 $ dann die folgenden Spalten sehen: $$ \ begin {matrix} 0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \\ 100 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \ end {matrix} $$ Daher ist die VC-Dimension von $ A $ zumindest $ d + 1 $ .

Wenn wir $ d=mathrm {vc} (a) $ nehmen, dufen wir dann $ \ mathrm { Vc} (a ^ t) <2 ^ {\ mathrm {vc} (a) +1} $ .