فهم بُعد فابنيك-تشيرفونينكيس
عدّ الفرضيات ينجح مع فئة منتهية وينهار فوراً مع الفئات المعتادة: فعلى المستقيم عدد لانهائي من المجالات، وفي المستوي عدد لانهائي من فوق-المستويات. غير أنّ الذي يهمّ في التعميم لم يكن العدّ قطّ. إنّما هو عدد السلوكيات المختلفة حقّاً التي تستطيع الفئة إظهارها على البيانات التي بين يديك، وهذا العدد منتهٍ وإن لم تكن الفئة كذلك.
تُشظّى مجموعة نقاط بعائلةٍ ما متى تحقّق كلّ إسناد للعناوين على تلك النقاط بعضوٍ من العائلة. والبُعد VC هو حجم أكبر مجموعة مشظّاة. والمُسوِّرات تستحقّ الانتباه: يجب أن تكون مجموعةٌ ما بهذا الحجم مشظّاة، وألّا تكون أيّ مجموعة أكبر بواحدة كذلك. ومن ثمّ فإثبات قيمة يحتاج حجّتين، مثالاً واستحالة، ولهذا يُبحث عن الرقم لا يُستذكر.
والمجالات على مستقيم تجعل التعريف ملموساً. نقطتان أمر يسير: يستطيع المجال أن يضمّهما، أو إحداهما، أو لا شيء. أمّا ثلاث نقاط فتهزمها: فضمّ الطرفين يفرض ضمّ الوسطى، فتصير العنونة (1، 0، 1) غير قابلة للتحقّق. سبع عنونات من ثماني ممكنة، والبُعد إذن 2، يحدّه نمط واحد مفقود. والمستطيلات الموازية للمحاور تشظّي نقاط المعيّن الأربع وتخفق عند خمس، لأنّ الأطراف في الاتّجاهات الأربعة تحاصر ما بقي.
والمكسب هو لِمّة ساور: فئةٌ بُعدها VC يساوي d تحقّق على الأكثر مجموع المعاملات الثنائية من C(n, 0) إلى C(n, d) من العنونات على n نقطة، أي كثير حدود بدل 2^n. ولمّا كانت حدود التعميم المنتظمة تحاسب على لوغاريتم عدد السلوكيات المتمايزة، صار ذلك الكثير حدود من رتبة d log n، وهو صغير بما يكفي كي تستمرّ الضمانة في الانضباط مع تراكم البيانات. وهكذا تكفّ السعة عن كونها عدّاً للفرضيات وتصير عدّاً للسلوكيات.
كيفية الحساب
VC(H) = max{ k : some S with |S| = k is shattered }, |H|_S ≤ Σ_{i≤d} C(n, i)
حيث
- H
- فئة الفرضيات: كلّ المجالات، أو كلّ المستطيلات، أو كلّ فوق-المستويات
- shattered
- مشظّاة: كلّ عنونة من عنونات S الـ2^k محقّقة بعضوٍ من H
- d
- البُعد VC للفئة H
- |H|_S
- عدد العنونات المتمايزة التي تستطيع H إنتاجها على عيّنة حجمها n
مثال على بُعد فابنيك-تشيرفونينكيس
العتبات على مستقيم بُعدها VC يساوي 1 والمجالات 2، وكلاهما وُجد بتعداد كلّ عنونة لكلّ مجموعة مرشّحة لا بالنظر. وعلى ثلاث نقاط تحقّق المجالات 7 من 8 عنونات، وتغيب بالضبط (1، 0، 1).
المستطيلات الموازية للمحاور تشظّي المعيّن (0,1) و(1,0) و(2,1) و(1,2) - فتتحقّق العنونات الستّ عشرة كلّها - وتخفق ما إن يُضاف المركز (1,1)، لأنّ مستطيلاً يضمّ الأطراف الأربعة يضمّ المركز أيضاً.
وعند البُعد VC = 2 يجري عدّ العنونات الممكنة 4 و7 و16 و56 و211 من أجل n تساوي 2 و3 و5 و10 و20، مقابل 4 و8 و32 و1024 و1,048,576 دون قيد. وعند n = 2 لا يزال الحدّ يسمح بكلّ شيء؛ وتنفتح الفجوة مباشرةً بعد ذلك.
الأسئلة الشائعة
هل البُعد VC الأعلى أسوأ؟
إنّه سعة أكبر، وهي تكلّف بيانات لا أن تكون سيّئة بذاتها. فالفئة الأصغر من أن تسع المسألة لا تستطيع تمثيل الحقيقة أصلاً. والبُعد يخبرك بما تدفعه، فهو يرافق مبادلة التحيّز والتباين لا يناقضها.
هل يضمن البُعد VC المنتهي أداءً جيّداً؟
يضمن أنّ خطأ التدريب يقترب من الخطأ الحقيقي مع تراكم البيانات، ولا يقول شيئاً عن صِغر أيٍّ منهما. فقد تعمّم فئةٌ تعميماً تامّاً وهي مخطئة على نحو منتظم، وذلك هو نصف «التحيّز» من المبادلة.
لماذا تعمّم الشبكات الحديثة مع سعة هائلة؟
حدود VC الكلاسيكية أسوأ-حالة على كلّ التوزيعات وكلّ العيّنات، وتصير خاوية عند هذه الأعداد من الوسائط. والتفسير سؤال بحثي نشط يشمل التنظيم الضمني الآتي من المحسِّن ومقاييس قائمة على الهامش، لا خللاً في التعريف.
الخلاصة
يجيب البُعد VC عن سؤال لا يطيقه العدّ: كم تستطيع فئةٌ فيها عدد لانهائي من الفرضيات أن تفعل فعلاً على البيانات الماثلة. وإثبات قيمةٍ يحتاج حجّتين، مثالاً يشظّي واستحالةً عند نقطة أزيد، ولهذا يُبحث عنه لا يُستذكر.