VC البعد من فئة الطبقات متعددة الحدود من الدرجة $ N $

Question

جئت عبر هذا العبارة في الصفحة 85 من الكتاب "فهم التعلم الآلي: من النظرية إلى الخوارزميات" < / a>

الفكرة العامة هي كما يلي:

فكر في مشكلة في الفصل الدراسي الثنائي مع مجال المثيل يجري $ x=mathbb r $ .

مقابل كل $ n \ in \ mathbb n $ دع $ h_n $ يكون فئة متعدد الحدود Classi ers imers $ n $ ؛ وهي $ h_n $ هي مجموعة من جميع classi fi ers من النموذج $ h (x)=operatorname {sign} ( P (x)) $ ، حيث $ p \ colon \ mathbb r \ to \ mathbb r $ هو متعدد الحدود من درجة $ n $ .

أثبت أن البعد VC من $ h_n $ هو $ n + 1 $ .

Answer 1

الفكرة هي أن متعدد الحدود من الدرجة $ N $ لديه على الأكثر $ n $ جذور، وهكذا يمكن تغيير العلامات على معظم $ n $ times. لذلك لا يوجد عدد متعدد الحدود من الدرجة $ N $ يمكن أن تشكل نمطا بديلا + - + -... أو - + + + ... من الطول $ n + 2 $ . هذا يدل على أن البعد VC على الأكثر $ n + 1 $ .

من ناحية أخرى، لأي مجموعة من $ n + 1 $ pairs $ (x_1، y_1)، \ LDOTS، (x_ {n + 1}، y_ {n + 1}) $ ، هناك كثير الحدود من الدرجة $ n $ والتي تتوافق عليها، قدمها صيغة الاستيفاء لاجرانج. باستخدام $ y_i=pm 1 $ ، يمكنك بسهولة إظهار أن أي مجموعة مجموعة من $ n +1 $ نقاط تحطمت. وبالتالي، فإن البعد VC هو بالضبط $ n + 1 $ .