السَّمْت

أساسيات تعلم الآلة1971متقدم9 دقيقة قراءة

حول التقارب المنتظم للتكرارات النسبية للأحداث نحو احتمالاتها

On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities

Vapnik, V. N. · Chervonenkis, A. Ya. — Theory of Probability and Its Applications

المشكلة

قانون الأعداد الكبيرة يخبرنا بأمر مطمئن: إذا كرّرت تجربة عشوائية مرات كافية، فإن نسبة حدوث أي حدث ستقترب من احتماله الحقيقي. لكن المشكلة أن خوارزميات التعلّم لا تختبر فرضية واحدة ثم تتوقف — بل تمشّط فئة كاملة من الفرضيات بحثاً عن الفرضية التي تحقّق أدنى خطأ على بيانات . وهنا يظهر السؤال الخطير: هل يبقى ضمان التقارب صامداً حين نبحث في فرضيات كثيرة بدلاً من واحدة؟ بدون إجابة واضحة على هذا السؤال، لا يوجد مبرّر رياضي يسمح لأي بأن يعمّم ما تعلّمه إلى بيانات جديدة لم يرها من قبل.

الإسهام

أثبت فابنيك وتشيرفونينكيس نتيجة محورية: التقارب المنتظم — أي أن التكرارات التجريبية تقترب من الاحتمالات الحقيقية لكل الأحداث في الفئة في آنٍ واحد — لا يحدث إلا إذا كانت الفئة تملك مقياس تعقيد تركيبي محدود سمّياه . والعكس صحيح أيضاً: إذا كان بُعد VC محدوداً فالتقارب المنتظم مضمون. كذلك أثبتا مبرهنة ساور–شيلاه التي تقول إن فئة بُعدها VC يساوي d لا تستطيع إنتاج أكثر من O(n^d) تصنيف مختلف على n نقطة، وهذا أقل بكثير من 2^n تصنيف ممكن نظرياً. هذا الانتقال من نمو أُسّي إلى نمو متعدد الحدود هو بالضبط ما يمنح أساساً رياضياً.

الأثر

هذه الورقة هي التي أسّست نظرية التعلم الإحصائي كحقل قائم بذاته. بُعد VC أصبح الأداة المركزية التي يُحلَّل بها ما إذا كانت تعلّم قادرة على التعميم أم لا. النتائج أفضت مباشرةً إلى نظرية التعلم شبه المؤكد تقريباً (PAC)، وإلى منهج تقليل المخاطر البنيوية، وإلى اختراع آلات المتجهات الداعمة. وكل حدود التعميم التي نستخدمها اليوم — من تعقيد ريدماخر إلى PAC-Bayes — تعود في جذورها الفكرية إلى هذه النتيجة.

تخيّل بطولة صيد على بحيرة. صيّاد واحد يرمي خيطه عشر مرات فيصطاد 6 سمكات — نسبة نجاح 60% تعكس على الأرجح طبيعة البحيرة فعلاً. الآن تخيّل أن 10,000 صيّاد نزلوا إلى البحيرة نفسها، كلٌّ منهم يجرّب موقعاً مختلفاً. الصيّاد الأفضل قد يخرج بنسبة 90%، لكن هذا الرقم يعكس كثرة المحاولات أكثر مما يعكس وفرة السمك.

نظرية VC تطرح السؤال التالي: كم موقعاً يمكنك تجربته قبل أن تفقد أفضل نسبة صيد أي دلالة حقيقية؟ الجواب يتوقف على مدى «تنوّع» المواقع — أي كم نمطاً مختلفاً جوهرياً من توزيع الأسماك تستطيع هذه المواقع إنتاجه. إن كانت المواقع محدودة وبسيطة، فنسبة الفائز تستحق الثقة. أما إن كانت قادرة على إنتاج أي نمط يخطر بالبال، فلا يمكن الوثوق بأي نتيجة.

الفجوة: فرضية واحدة تتقارب، لكن البحث في فرضيات كثيرة قد لا يتقارب

قانون الأعداد الكبيرة يمنحنا ضمانة واضحة: إذا أخذنا حدثاً واحداً AA وكرّرنا التجربة nn مرة، فإن نسبة حدوثه تقترب من احتماله الحقيقي P(A)P(A) كلما كبر nn. حتى الآن الأمر بسيط.

لكن خوارزمية التعلّم لا تقيّم فرضية بعينها — بل تمشّط فئة كاملة H\mathcal{H} من الفرضيات وتنتقي منها تلك ذات الأداء الأفضل على بيانات التدريب. الأمر أشبه بفحص آلاف الأحداث دفعةً واحدة ثم اختيار أفضلها. السؤال المحوري هنا: هل أسوأ فجوة بين التكرار المُلاحَظ والاحتمال الحقيقي — محسوبة عبر جميع فرضيات الفئة H\mathcal{H} — تتقلّص هي أيضاً نحو الصفر؟

sup⁡h∈H∣R^(h)−R(h)∣→P0\sup_{h \in \mathcal{H}} |\hat{R}(h) - R(h)| \xrightarrow{P} 0

هذا ما نسمّيه التقارب المنتظم، وهو شرط أقوى بكثير من النقطي لفرضية واحدة بمفردها.

افتح في المختبر
يساراً: فرضية واحدة — الخطأ التجريبي يقترب تدريجياً من الخطأ الحقيقي. يميناً: البحث في فرضيات كثيرة — أفضل خطأ تدريبي قد يكون أقل بكثير من الخطأ الحقيقي. جرّب زيادة حجم العينة لترى كيف يسدّ التقارب المنتظم هذه الفجوة.
تستيقظ التجربة عند وصولك…

التهشيم: هل يستطيع نموذجك تمثيل كل تصنيف ممكن؟

الفكرة المحورية هنا هندسية في جوهرها. لنفترض أن لدينا nn نقطة بيانات وفئة فرضيات H\mathcal{H} تضم مصنِّفات ثنائية، كل واحد منها يعطي كل نقطة تسمية: إما ++ أو −-. إجمالي التصنيفات الممكنة هو 2n2^n. إذا استطاعت H\mathcal{H} أن تُنتج جميع هذه التصنيفات الـ2n2^n على مجموعة معيّنة من nn نقطة، نقول إن H\mathcal{H} تُهشِّم تلك المجموعة.

ماذا يعني عملياً؟ يعني أن الفئة مرنة أكثر مما ينبغي بالنسبة لتلك النقاط — فهي قادرة على حفظ أي نمط كان، بما في ذلك الضوضاء العشوائية. تخيّل الأمر هكذا: إذا كان نموذجك قادراً على رسم أي صورة تريدها على nn نقطة بيانات، فهو لا يملك أي — لا يستطيع التمييز بين الإشارة المفيدة والضجيج. وبدون هذا التمييز، لا يمكن لأي خوارزمية أن تعمّم.

افتح في المختبر
جرّب كل التصنيفات الممكنة 2ⁿ. الخط المستقيم في بُعدين يستطيع تهشيم 3 نقاط لكنه يعجز عن تهشيم 4 — سيبقى دائماً تصنيف واحد على الأقل لا يستطيع تحقيقه.
تستيقظ التجربة عند وصولك…

بُعد VC: سقف التهشيم

بُعد VC لفئة فرضيات H\mathcal{H} هو حجم أكبر مجموعة نقاط تستطيع الفئة تهشيمها. بصيغة رياضية:

VCdim(H)=max⁡{n:∃ x1,…,xn that H shatters}\text{VCdim}(\mathcal{H}) = \max\{n : \exists\, x_1,\ldots,x_n \text{ that } \mathcal{H} \text{ shatters}\}

لكي تُثبت أن بُعد VC لفئة ما يساوي dd، تحتاج إلى إثبات شقَّين معاً: الأول أن هناك مجموعة من dd نقطة يمكن تهشيمها، والثاني أنه لا توجد أي مجموعة من d+1d+1 نقطة يمكن تهشيمها.

النقطة الجوهرية هنا أن بُعد VC يقيس التعقيد الفعلي لفئة الفرضيات، وليس عدد فيها. فئة تحوي عدداً لا نهائياً من الفرضيات قد يكون بُعدها VC صغيراً إذا كانت بنية تلك الفرضيات مقيَّدة. بعبارة أخرى، بُعد VC يقيس كم نمطاً من البيانات تستطيع الفئة حفظه، لا كم معاملاً تملكه.

افتح في المختبر
استكشف بُعد VC لفئات فرضيات مختلفة. بدّل بين الخطوط والدوائر والفواصل في أبعاد أعلى لترى كيف يتصاعد التعقيد.
تستيقظ التجربة عند وصولك…

دالة النمو: من الانفجار الأُسّي إلى الترويض المتعدد الحدود

ΠH(n)\Pi_{\mathcal{H}}(n) تحصي أقصى عدد من التصنيفات المتمايزة التي تستطيع الفئة H\mathcal{H} إنتاجها على أي مجموعة من nn نقطة:

ΠH(n)=max⁡x1,…,xn∣{(h(x1),…,h(xn)):h∈H}∣\Pi_{\mathcal{H}}(n) = \max_{x_1,\ldots,x_n} |\{(h(x_1),\ldots,h(x_n)) : h \in \mathcal{H}\}|

قبل عمل فابنيك وتشيرفونينكيس، كان الحد المعروف هو ΠH(n)≤2n\Pi_{\mathcal{H}}(n) \leq 2^n — نمو أُسّي متفجّر في nn. الإنجاز الذي حققاه هو إثبات أنه بمجرد أن يتجاوز nn بُعد VC البالغ dd، تنخفض دالة النمو من مسار أُسّي إلى مسار متعدد الحدود. وهذه هي مبرهنة ساور–شيلاه:

ΠH(n)≤∑i=0d(ni)≤(end)d\Pi_{\mathcal{H}}(n) \leq \sum_{i=0}^{d}\binom{n}{i} \leq \left(\frac{en}{d}\right)^d
مبرهنة ساور–شيلاه — السقف المتعدد الحدود — يمثّل بُعد VC عتبةً حاسمة في قدرة فئة النماذج على تمثيل أنماط التصنيف المختلفة. فقبل هذه العتبة تنمو القدرة على توليد تصنيفات متنوعة بسرعة كبيرة جداً، أما بعدها فيصبح النمو أكثر تقييداً ويتبع نمطاً متعدد الحدود بدلاً من النمو الأُسّي. وتُعدّ هذه الحقيقة من الركائز الأساسية في نظرية التعلّم الإحصائي، لأنها تمنع تعقيد النماذج من الازدياد بلا حدود وتجعل تقديم ضمانات حقيقية حول التعميم أمراً ممكناً.

تخيّل الأمر كأنه طريق يتفرّع عنده مسلك أبطأ. ما دام n≤dn \leq d، تسير دالة النمو بأقصى سرعة على المسار الأُسّي: ΠH(n)=2n\Pi_{\mathcal{H}}(n) = 2^n، أي أن الفئة قادرة على إنتاج كل تصنيف يمكن تخيّله. لكن عند n=d+1n = d+1، تأخذ دالة النمو المنعطف وتنتقل إلى المسار المتعدد الحدود O(nd)O(n^d)، ولا تعود إلى السرعة الأُسّية أبداً.

وهذا ليس تقديراً فضفاضاً، بل هو حدٌّ محكم: نقطة الانتقال تقع بالضبط عند n=dn = d، ودرجة كثير الحدود تساوي بالضبط بُعد VC.

افتح في المختبر
دالة النمو تساوي 2^n حتى n = d، ثم تنحني لتتبع منحنى متعدد الحدود. اسحب شريط بُعد VC لترى كيف تتحرّك نقطة الانحناء.
تستيقظ التجربة عند وصولك…

المبرهنة الرئيسية: بُعد VC محدود ⟺ تقارب منتظم

بعد أن قُيِّدت دالة النمو، أصبح بإمكان فابنيك وتشيرفونينكيس صياغة نتيجتهما المركزية — المبرهنة الأساسية لنظرية التعلم الإحصائي. وما يميّز هذه المبرهنة أنها تعطي شرطاً ضرورياً وكافياً معاً لقابلية التعلّم:

فئة الفرضيات H\mathcal{H} تمتلك خاصية التقارب المنتظم إذا وفقط إذا كان بُعد VC الخاص بها محدوداً.

ولتوضيح ما يترتب على ذلك عملياً: إذا كان VCdim(H)=d<∞\text{VCdim}(\mathcal{H}) = d < \infty، فلأي هامش خطأ ϵ>0\epsilon > 0 ومستوى ثقة δ>0\delta > 0، نحصل باحتمال لا يقلّ عن 1−δ1 - \delta على:

sup⁡h∈H∣R^(h)−R(h)∣≤dln⁡(n/d)+ln⁡(1/δ)n\sup_{h \in \mathcal{H}} |\hat{R}(h) - R(h)| \leq \sqrt{\frac{d \ln(n/d) + \ln(1/\delta)}{n}}
حدّ تعميم VC — يوضّح هذا الحد مدى التقارب المتوقع بين أداء النموذج على بيانات التدريب وأدائه على بيانات جديدة لم يرها من قبل. وتصغر الفجوة كلما ازداد عدد أمثلة التدريب، بينما تكبر كلما ازدادت قدرة فئة النماذج أو تعقيدها. أي إن تحسين التعميم يمكن تحقيقه إما بجمع مزيد من البيانات أو باستخدام نماذج أبسط ذات سعة تمثيلية أقل.

يمكنك قراءة هذا الحدّ على أنه صراع قوى متعاكسة. من جهة، بُعد VC يمثله dd ويدفع الحدّ نحو الأعلى — فكلما زادت مرونة النموذج زادت فرصة انحرافه. ومن الجهة المقابلة، حجم العينة nn يسحب الحدّ نحو الأسفل — المزيد من البيانات يكبح جماح التعقيد. النسبة d/n\sqrt{d/n} تحدّد ما يمكن تسميته «سعر الصرف»: لتقليص الحدّ إلى النصف، إما أن تُقلّل تعقيد النموذج إلى الربع أو تُضاعف البيانات أربع مرات. هذه العلاقة هي التي تُحدّد تعقيد العينة — أي كم مثالاً تحتاج لضمان تعميم موثوق.

افتح في المختبر
اضبط بُعد VC وحجم العينة لترى كيف يتغير حدّ التعميم. لاحظ كيف تتحكّم النسبة √(d/n) في الموازنة.
تستيقظ التجربة عند وصولك…

من النظرية إلى التطبيق: تقليل المخاطر التجريبية والبنيوية

حدّ VC يسمح لنا بتفكيك الخطأ الحقيقي لأي نموذج إلى عنصرين متنافسين:

R(h)≤R^(h)+Ω(d,n,δ)R(h) \leq \hat{R}(h) + \Omega(d, n, \delta)

العنصر الأول R^(h)\hat{R}(h) هو خطأ التدريب — وينخفض كلما ازداد تعقيد النموذج لأن سعته لمطابقة البيانات تزداد. العنصر الثاني Ω\Omega هو غرامة التعقيد — ويزداد بازدياد بُعد VC. هذا التنافس يُنتج منحنى على شكل حرف U: النماذج المبسَّطة أكثر من اللازم تعاني من فيظل خطأ تدريبها مرتفعاً، والنماذج المعقدة أكثر من اللازم تقع في فتزداد غرامة تعقيدها.

تقليل المخاطر التجريبية (ERM) يركّز على العنصر الأول فقط: اختر الفرضية ذات أقل خطأ تدريبي. نظرية VC تُثبت أن هذا المنهج سليم حين يكون بُعد VC محدوداً.

تقليل المخاطر البنيوية (SRM) — وهو ما طرحه فابنيك — يُقلّل المجموع بأكمله. الفكرة أن ترتّب فئات الفرضيات بشكل متداخل H1⊂H2⊂⋯\mathcal{H}_1 \subset \mathcal{H}_2 \subset \cdots بأبعاد VC متصاعدة، ثم تختار الفئة التي تحقق أفضل توازن بين جودة المطابقة وضبط التعقيد. هذه الفكرة بالذات هي التي ألهمت تصميم .

افتح في المختبر
منحنى U أثناء العمل. اسحب شريط التعقيد لترى كيف ينخفض خطأ التدريب بينما تزداد غرامة VC. النقطة المثلى هي التي تُقلّل المخاطر الكلية.
تستيقظ التجربة عند وصولك…

الفكرة ذاتها في شيفرة برمجية

حساب بُعد VC وحدّ التعميمpython

مبسَّط لإظهار الفكرة — ليس التنفيذ الحقيقي.

import numpy as np
from itertools import product

def is_shattered(points, classifier_factory):
    """تحقق مما إذا كانت مجموعة النقاط مُهشَّمة بفئة المصنِّفات."""
    n = len(points)
    for labeling in product([0, 1], repeat=n):  # كل التصنيفات 2^n الممكنة
        found = False
        for clf in classifier_factory():         # ابحث عن مصنِّف مطابق
            preds = [clf(p) for p in points]
            if tuple(preds) == labeling:
                found = True
                break
        if not found:
            return False                         # تصنيف واحد غير قابل للتحقيق = لا تهشيم
    return True

def sauer_bound(n, d):
    """مبرهنة ساور–شيلاه: أقصى عدد تصنيفات لبُعد VC يساوي d على n نقطة."""
    if n <= d:
        return 2 ** n                            # المنطقة الأُسّية
    return sum(
        np.math.comb(n, i) for i in range(d + 1) # المنطقة المتعددة الحدود
    )

def vc_bound(n, d, delta=0.05):
    """حدّ تعميم VC: أسوأ فجوة ممكنة بين خطأ التدريب والخطأ الحقيقي."""
    return np.sqrt((d * np.log(n / d) + np.log(1 / delta)) / n)

# مثال: الخطوط المستقيمة في بُعدين لها بُعد VC يساوي 3
d = 3
for n in [10, 100, 1000, 10_000]:
    print(f"n={n:>6}  حدّ ساور={sauer_bound(n,d):>12}  "
          f"من أصل 2^n={2**n:.1e}  "
          f"فجوة VC≤{vc_bound(n, d):.4f}")

لماذا غيّرت كل شيء

  1. 1971

    نظرية VC

    فابنيك وتشيرفونينكيس يُثبتان المبرهنة الأساسية — بُعد VC المحدود هو ما يُحدّد التقارب المنتظم. نُشرت في مجلة نظرية الاحتمالات وتطبيقاتها.

  2. 1974

    نظرية التعرّف على الأنماط

    فابنيك وتشيرفونينكيس يُصدران كتابهما الذي يوسّع النظرية لتشمل تقليل المخاطر البنيوية ويضع أُسس التعلم الإحصائي.

  3. 1984

    التعلم شبه المؤكد تقريباً (PAC)

    فاليانت يطرح إطار التعلم شبه المؤكد تقريباً (PAC). بُعد VC يتحوّل إلى الكمية المحورية في حدود تعقيد العينة ضمن هذا الإطار.

  4. 1992

    مبرهنة BEHW

    تُصاغ المبرهنة الأساسية لنظرية التعلم الحوسبي بشكلها النهائي: بُعد VC هو ما يُحدّد قابلية التعلم PAC في مسائل التصنيف الثنائي.

  5. 1995

    آلات المتجهات الداعمة

    فابنيك وكورتس يقدّمان آلات المتجهات الداعمة — تطبيق عملي مباشر لمبدأ تقليل المخاطر البنيوية. فكرة تعظيم الهامش تُحسّن حدّ VC بحكم تصميمها الهندسي.

  6. 2000

    ما بعد VC — ريدماخر وPAC-Bayes

    تعقيد ريدماخر وحدود PAC-Bayes تُطوّر نظرية التعميم بأدوات تعتمد على طبيعة البيانات والخوارزمية معاً، في امتداد طبيعي للإطار الفكري الذي رسمته نظرية VC.

نظرية VC لم تُضف مبرهنة جديدة فحسب — بل صاغت اللغة التي يفكّر بها مجال التعلّم الآلي حين يناقش التعميم. مفاهيم مثل والتهشيم وغرامات التعقيد أصبحت منسوجة في نسيج الحقل، حتى أن أي نقاش حول الإفراط في المطابقة أو اختيار النموذج أو يعود في أصله إلى هذه الورقة التي نُشرت عام 1971.

المرجعVapnik, V. N. and Chervonenkis, A. Ya.. On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities. Theory of Probability and Its Applications, 1971.

مصطلحات هذه الورقة