إثبات التقارب الموحد إذا كان VC Dimension محدود

Question

في الكتاب »فهم ماكينة التعلم: من النظرية إلى الخوارزميات«، كتبها بن ديفيد وشاليف - شوارتز، هناك دليل لا أفهمه. يثبت السياق أنه إذا كانت الفرضية الفصالة $ \ mathcal {h} $ لها بعد VC المحدود، ثم تتمتع بممتلكات التقارب الموحدة.

دليل على هذا التضمين ينطوي على LEMMA ل Sauer (فصوص الفرضية ذات البعد VC المحدود يحتوي على »حجم صغير فعال") ومظهر يفترض أن فرضيات الفرضية مع »حجم صغير فعال« استمتع بممتلكات التقارب الموحدة. يتضمن إثبات الآثار الفرعية الأخيرة هذا نظرية (نظرية 6.11 في الكتاب):

دع $ \ mathcal {h} $ يكون فئة الفم من الطبقات الثنائية عبر المجال $ \ mathcal {x } $ ودع $ \ Tau _ {\ mathcal {h}} $ تكون وظيفة النمو (من Lemma's Sauer). ثم، لجميع $ m \ in \ mathbb {n} $ ، لكل توزيع $ \ mathcal {D} $ < / span> Over $ \ mathcal {x} \ times \ {0، 1 \} $ وكل $ \ delta \ في (0، 1) $ : $$ \ forall H \ in \ mathcal {h}: \ mathbb {p} _ {s \ sim \ mathcal {d} ^ m} \ left [| l _ {\ mathcal {d}} (h) - l_s (h) | \ leq \ frac {4 + \ sqrt {\ log (\ tau _ {\ mathcal {h}} (2m))}} {\ delta \ sqrt {2m}} \ right] \ geq 1 - delta

في الدليل لهذا النظرية، يتم ذكرها، أنه يتبع على الفور من عدم المساواة $$ \ Mathbb {e} _ {s \ sim \ mathcal {d} ^ m} \ left [\ sup_ {h \ {h \ in \ mathcal {h}} | l _ {\ mathcal {d}} (h) - l_s (h) | \ right] \ leq \ frac {4 + \ sqrt {\ log (\ tau _ {\ mathcal {h}} (2m))}} {\ sqrt {2m}}، $ حقيقة أن متغير عشوائي $ \ theta:=sup_ {h \ in \ mathcal {h}} | L _ {\ mathcal {d} {d}} (h) - l_s (h) | $ غير مساواة غير ماركوف.

---

ومع ذلك، أفعل ليس ، انظر كيف يتبعه على الفور من هذه الحقائق. ما أنا في عداد المفقودين؟

Answer 1

دع $ x= | l_ \ mathcal {d} (h) - l_s (h) | $ .البيان المعني بتوقع التفوق من $ × $ يعني، على وجه الخصوص، أنه بالنسبة لبعض $ M $ $$ \ mathbb {e} [x] \ leq m. $ منذ $ x \ geq 0 $ ، لا يعني عدم المساواة markov ذلك $$ \ pr \ left [x \ geq \ frac {m} {\ delta} \ right] \ leq \ delta. $ وهذا يعني أن $$ \ pr \ left [x \ leq \ frac {m} {\ delta} \ right] \ GEQ \ pr \ left [x <\ frac {m} {\ delta} \ right]= 1 - \ pr \ left [x \ geq \ frac {m} {\ delta} \ right] \ geq 1 - \ delta.