VC البعد من مجموعة الوظائف

Question

دع $ \ chi $ تكون مساحة مثيل و $ h \ in \ {0، 1 \} ^ \تشي $ فئة ذات VC-DIFSIOND.لكل $ x \ in x $ نحن نعتبر $ z_x \ colon h \ rightrow \ {0، 1 \} $ st $ z_x (h)= h (x)، \ forall h \ in h $ .

دع $ z={z_x: h \ charearrow \ {0،1 \} \ mile x \} $ .هو $ \ mathit {vcdim} (z) <2 ^ {\ mathit {vcdim} (h) +1} $ ؟

---

الشيء الوحيد الذي يتبادر إلى الذهن عند رؤية هذا هو Lemma Sauer، ولكن هذا يرتبط بوظيفة النمو ولا أرى كيفية تطبيقه هنا.أي شخص حصل على أي فكرة حول كيفية الاقتراب من هذا؟

Answer 1

هذه نتيجة كلاسيكية للأسلطة ( Densité et Dimension ) حول < EM> Dual VC Dimension .

دع $ $ تكون مصفوفة ثنائية. البعد VC من $ $ هو الحد الأقصى للحجم من مجموعة $ S $ من الأعمدة التي تحطمت ، أي أن جميع الصفوف الممكنة تظهر عندما تقصر $ $ إلى الأعمدة في $ S $ . البعد المزدوج VC من $ $ هو البعد VC من $ a ^ t $ ، يعادل $ $ .

لنفترض أن $ a ^ t $ لديه VC البعد $ 2 ^ ^ {d + 1} $ . ثم هناك مجموعة $ S $ $ 2 ^ ^ {d + 1} $ صفوف من $ $ بحيث يمكننا تقييد $ $ إلى هذه المجموعة من الصفوف، ونحن نرى كل الأعمدة الممكنة. إذا كنا نسئق الصفوف باستخدام الأرقام الثنائية من الطول $ D + 1 $ ، ثم نرى الأعمدة التالية: لكل $ i $ ، هناك عمود يحتوي على $ i $ 'th bit من مؤشر الصف. على سبيل المثال، إذا $ d= 1 $ ثم نرى الأعمدة التالية: $$ \ ابدأ {مصفوفة} 0 و 0 & 0 \\ 0 و 0 & 1 \\ 0 و 1 & 0 \\ 0 و 1 و 1 \\ 1 و 0 & 0 \\ 1 و 0 & 1 \\ 1 و 1 & 0 \\ 1 و 1 و 1 \ نهاية {matrix} $ لذلك البعد VC من $ $ هو على الأقل $ D + 1 $ .

إذا أخذنا $ d=mathrm {vc} (a) $ ، ثم نستنتج $ \ mathrm { VC} (a ^ t) <2 ^ {\ mathrm {vc} (a) +1} $ .