📊 statistics

An Optimal Agnostic PAC Algorithm

تقدم هذه الورقة خوارزمية تعلم PAC غير متباينة (agnostic) للتصنيف الثنائي تحقق حداً مثالياً إحصائياً للمخاطر، مما يستقر بمرونة التعقيد العيني حتى الثوابت العالمية من خلال مطابقة الحدود الدنيا الراسخة.

المؤلفون الأصليون: Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy

نُشر 2026-08-07

📖 6 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

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

للإجابة على هذا، يستخدم العلماء مفهومًا يُسمى البعد الفيك-تشيرونكيس (VC dimension) (تسميةً لـ Vapnik وChervonis). فكر في البعد (VC) كأنه مقياس لمدى "الإرباك" أو "التعقيد" في عقل الروبوت. العقل البسيط الذي ينظر فقط إلى شكل الأذن لديه بُعد (VC) منخفض؛ أما العقل شديد التعقيد الذي ينظر إلى كل بكسل في الصورة، فلديه بُعد (VC) مرتفع. الهدف هو إيجاد "نقطة مثالية" حيث يتعلم الروبوت بسرعة كافية ليكون مفيدًا، دون أن يكون معقدًا جدًا بحيث يحفظ صور التدريب بدلًا من تعلم القواعد. لعقود من الزمن، حاول الرياضيون إيجاد الصيغة المثالية التي تخبرنا بالضبط مقدار "الخطأ الإضافي" الذي سيرتكبه الروبوت مقارنة بأفضل روبوت ممكن، بالنظر إلى عدد معين من الأمثلة ومستوى معين من التعقيد.

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

هذه الورقة البحثية، بعنوان "خوارزمية PAC التوافقية المثالية"، تجيب على هذا السؤال بـ "نعم" قاطعة. لقد صمم المؤلفون، ماركوس إنجيلوند ماثياسن، جيان كيان، ونيكيتا جيفوتوفسكي، خوارزمية تعلم محددة تحقق الحد الأمثل للمخاطرة (statistically optimal risk bound). باللغة البسيطة، يعني هذا أنهم وجدوا طريقة لتدريب مصنف يرتكب أقل عدد ممكن من الأخطاء، وقد أثبتوا رياضيًا أنه لا توجد طريقة أخرى يمكنها التفوق عليهم (باستثناء بعض الثوابت العالمية) لأي مستوى ثابت من الضجيج. لم يكتفوا بالتخمين؛ بل أثبتوا ذلك.

إليكم كيف فعلوا ذلك، باستخدام قصة عن مكتبة منظمة للغاية ولعبة ذكية تسمى "الاشتمال الواحد".

المشكلة: المكتبة المشوشة

تخيل مكتبة ضخمة حيث كل كتاب عبارة عن صورة، وكل كتاب له ملصق على كعب الكتاب يقول "قطة" أو "كلب". ومع ذلك، فإن أمين المكتبة مهمل بعض الشيء؛ فأحيانًا يضع ملصقًا خاطئًا على كتاب، أو يكون الكتاب تالفًا. تريد بناء نظام يمكنه النظر إلى كتاب جديد غير مصنف وتخمين ملصقه بشكل صحيح.

النظام "الأفضل الممكن" (لنسمّه الأوراكل/العراف) يعرف القواعد الحقيقية للكون. وحتى "الأوراكل" سيرتكب بعض الأخطاء لأن ملصقات أمين المكتبة تكون خاطئة أحيانًا. معدل الخطأ الأدنى هذا يسمى $L^*$ . هدفك هو بناء نظام يقترب من أداء "الأوراكل" قدر الإمكان، باستخدام عدد محدود من الكتب ( $n$ ) من المكتبة.

تثبت الورقة أن نظامهم الجديد، لنسمّه المُحسِّن (The Optimizer)، سيكون معدل خطئه ( $L(\hat{h})$ ) محكومًا بـ:
$L(\hat{h}) \le L^* + 7 \cdot 10^8 \left( \sqrt{\frac{L^*(d + \log(1/\delta))}{n}} + \frac{d + \log(1/\delta)}{n} \right)$
لا تدع الرياضيات تخيفك. الجزء الرئيسي هو حد الجذر التربيعي. تقول هذه الصيغة إن الأخطاء الإضافية التي ترتكبها (الـ "excess risk") تتقلص مع زيادة عدد الكتب ( $n$ )، وهي تتقلص بأسرع سرعة ممكنة تسمح بها قوانين الاحتمالات. الطرق السابقة كانت تحتوي على عوامل إضافية (مثل $\log(n)$ ) أبطأت من سرعتها، لكن "المُحسِّن" يستبعد تلك العوامل.

السر الخفي: المكعب والاتجاه

كيف فعلوا ذلك؟ استخدموا مزيجًا عبقريًا من فكرتين: رسم بياني للاشتمال الواحد (One-Inclusion Graph) و متوسط اللاحقة (Suffix Averaging).

1. رسم بياني للاشتمال الواحد (لعبة المكعب)
تخيل جميع الطرق الممكنة لتسمية الكتب في عينتك. إذا كان لديك $n$ من الكتب، فهناك $2^n$ من مجموعات الملصقات المحتملة. يمكنك تصور هذه المجموعات كأركان مكعب ضخم متعدد الأبعاد ("المكعب البولياني").

يتم توصيل ركنين بحافة إذا اختلفا في ملصق كتاب واحد بالضبط.
"الأوراكل" (أفضل قاعدة ممكنة) يعيش في مكان ما داخل هذا المكعب.
الهدف هو تحديد الاتجاه الذي يجب أن تشير إليه عندما تكون عند ركن ما، حتى تتحرك باتجاه "الأوراكل".

يستخدم المؤلفون تقنية تسمى التوجيه (orientation). تخيل أنك تقف على ركن من أركان هذا المكعب. عليك أن تقرر أي اتجاه تسلك. تقدم الورقة أداة رياضية جديدة تسمى التمهيدية 2.1 (Lemma 2.1)، وهي "عدم تماثل حواف يعتمد على الفئة". في مثال المكتبة الخاص بنا، هذه بمثابة قاعدة تقول: "عدد المسارات التي تحتاج إلى فحصها للعثور على الاتجاه الصحيح يعتمد على مدى بعدك عن الأوراكل ومدى تعقيد المكتبة".

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

2. متوسط اللاحقة (تصويت اللجنة)
بمجرد حصولهم على هذا التوجيه المثالي، يحتاجون لتحويله إلى متنبئ حقيقي. يستخدمون خدعة تسمى متوسط اللاحقة (suffix averaging).
تخيل أنك تبني فريقًا من الخبراء. أنت لا تسأل خبيرًا واحدًا فقط عن رأيه. بدلاً من ذلك، تسأل سلسلة من الخبراء الذين اطلعوا على كميات مختلفة قليًا من البيانات.

الخبير 1 قد رأى أول $k$ من الكتب.
الخبير 2 قد رأى أول $k+1$ من الكتب.
...
الخبير $m$ قد رأى أول $2k-1$ من الكتب.

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

3. اللمسة النهائية: العتبة (Thresholding)
النتيجة المتوسطة هي رقم بين -1 و 1 (أي "درجة"). للحصول على إجابة نهائية "قطة" أو "كلب"، نستخدم عتبة. يقومون باختبار بضعة نقاط قطع مختلفة على مجموعة منفصلة من كتب التحقق لاختيار النقطة التي تعمل بشكل أفضل. تضمن هذه الخطوة أن تكون النتيجة النهائية عبارة عن قاعدة بسيطة وحتمية (مصنف ثنائي) وليست مجرد احتمالية ضبابية.

لماذا يهم هذا؟

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

تظهر هذه الورقة أن بإمكانك الحصول على أفضل ما في العالمين. لقد صمموا متعلمًا:

لا يحتاج لمعرفة مستوى الضجيج: يعمل دون معرفة مدى تشوش البيانات ( $L^*$ ) أو مدى الثقة التي تريد تحقيقها ( $\delta$ ).
مثالي: يطابق الحد الأدنى النظري للسرعة (الذي يمثل حد السرعة للتعلم) الذي وضعه باحثون سابقون مثل ديفروي، جيروفي، ولوغوسي.
حتمي: لا يعتمد على الحظ؛ فهو يعطي نفس الإجابة في كل مرة تقوم فيها بتشغيله على نفس البيانات.

لقد استبعد المؤلفون صراحةً فكرة أننا بحاجة إلى عوامل "بوليلوغاريتمية" (تلك التباطؤات الإضافية) للحصول على نتائج مثالية في الحالة التوافقية (agnostic). لقد أثبتوا أن تلك العوامل غير ضرورية. كما أظهروا أنه بينما تعمل بعض الطرق السابقة (مثل التصويت بالأغلبية البسيطة) بشكل جيد للبيانات المثالية، إلا أنها تفشل في الحفاظ على السرعة المثالية عند إدخال الضجيج.

باختصار، تغلق هذه الورقة فصلاً طويلاً في تاريخ نظرية تعلم الآلة. إنها توفر الخوارزمية "المثالية" للتصنيف الثنائي في العالم الحقيقي، حيث لا تكون البيانات مثالية أبدًا. إنها تشبه العثور على خريطة تضمن لك الوصول إلى الكنز في أقل عدد ممكن من الخطوات، بغض النظر عن عدد الحفر الموجودة في الطريق. لم يكتفِ المؤلفون باقتراح أن هذا ممكن، بل بنوا الخريطة وأثبتوا أنها تعمل.

ملخص تقني: خوارزمية PAC مثالية ومستقلة عن الفرضيات

بيان المشكلة
تتناول الورقة البحثية المشكلة الجوهرية المتمثلة في تحديد حدود المخاطر الحادة في التعلم التقريبي الاحتمالي (PAC) المستقل عن الفرضيات (agnostic) للتصنيف الثنائي. لتكن $H \subseteq \{-1, +1\}^{\mathcal{X}}$ فئة فرضيات ذات بُعد VC يبلغ $d \geq 1$ . وبالنظر إلى عينة $S$ مستقلة ومتماثلة التوزيع (i.i.d.) بحجم $n$ من توزيع فوق $\mathcal{X} \times \{-1, +1\}$ ، فإن الهدف هو بناء متعلم يُخرج مصنفًا $\hat{h}$ بحيث تكون مخاطره $L(\hat{h})$ قريبة من المخاطر المثلى $L^* = \min_{h \in H} L(h)$ .

تاريخيًا، تم اشتقاق الحدود في هذا السياق عبر نظامين متميزين:

الحالة الواقعية ( $L^*=0$ ): يتم تحقيق معدلات مثالية قدرها $O(d/n)$ باستخدام حجج توافقية مثل مخطط الرسم البياني أحادي الاحتواء (Haussler, Littlestone, Warmuth) أو مخططات تجميع محددة.
الحالة المستقلة عن الفرضيات ( $L^* > 0$ ): تؤدي طرق العمليات التجريبية الكلاسيكية (chaining, covering) إلى معدلات مثالية قدرها $O(\sqrt{d/n})$ عندما تكون $L^*$ بعيدة عن الصفر.

السؤال المفتوح، الذي أثبتته الحدود الدنيا من Devroye, Györfi, and Lugosi، هو ما إذا كان بإمكان خوارزمية واحدة تحقيق المعدل الأمثل عبر الطيف الكامل لـ $L^*$ ، وتحديدًا مطابقة الحد:
$L(\hat{h}) \leq L^* + C \left( \sqrt{\frac{L^*(d + \log(1/\delta))}{n}} + \frac{d + \log(1/\delta)}{n} \right)$
كانت الحدود العليا السابقة إما تتضمن عوامل لوغاريتمية فرعية غير مثالية في حد المعدل السريع، أو تتطلب شروطًا محددة على $L^*$ (مثل $L^* \lesssim (d+\log(1/\delta))/n$ ) لتحقيق الأمثلية.

المنهجية
يبني المؤلفون متعلمًا حتميًا، غير دقيق عمومًا (improper learner)، يحقق الحد الأمثل دون معرفة مسبقة بـ $L^*$ أو معامل الثقة $\delta$ . تسير المنهجية عبر ثلاث مراحل رئيسية:

الآيزوبريمتري (Isoperimetry) للحواف المعتمد على الفئة (القسم 2):
الابتكار النظري الجوهري هو التمهيدية 2.1 (Lemma 2.1)، وهي متباينة آيزوبريمتري للحواف تعتمد على الفئة على المكعب البولياني. على عكس النتائج السابقة التي تحصر أعداد الحواف فقط بواسطة بُعد VC أو المسافة إلى أثر (trace)، تقدم هذه التمهيدية أوزانًا $w_{v,p}$ تحقق في آن واحد:

$w_{v,p} + w_{v \oplus p, p} = 1$ (تقسيم الحواف).
$\sum_{p \in D} w_{v,p} \leq \rho_F(v) + R_D(F)$ ، حيث $\rho_F(v)$ هي مسافة هامينج إلى الأثر $F$ و $R_D(F)$ هو عرض رادماخرر غير المعاير لإسقاط $F$ على الإحداثيات $D$ .

تسمح هذه المتباينة بوضع حد محلي لعدد الحواف المستحثة $|E_U|$ في رسم بياني فرعي، من خلال التحكم فيها عبر كل من المسافة إلى الأثر الأمثل وتعقيد الإسقاط.

التوجيه الأمثل "ترك واحد خارجًا" (Leave-One-Out) (القسم 2):
باستخدام مبرهنة زواج هول (Hall's Marriage Theorem)، يحول المؤلفون متباينة الآيزوبريمتري إلى توجيه حتمي $\sigma$ للمكعب البولياني الكامل. يضمن هذا التوجيه أنه لأي رأس $v$ ، يكون الدرجة الخارجة (out-degree) محدودة بـ:
$\text-out(v; \sigma) \leq \rho_F(v) + 120\sqrt{d \rho_F(v)} + 7202d$
يؤدي هذا إلى قاعدة "ترك واحد خارجًا" حيث يتم تحديد الخطأ المتوقع بواسطة المخاطر التجريبية المثلى بالإضافة إلى حد يتناسب مع $\sqrt{d L^*/n}$ و $d/n$ .
من "ترك واحد خارجًا" إلى حدود PAC (القسم 3):
لتحويل قاعدة "ترك واحد خارجًا" إلى ضمان PAC باحتمالية عالية، يستخدم المؤلفون عملية نزع عشوائية (derandomization) ومتوسط عبر خطوتين:

التماثل ومتوسط اللاحقة (Symmetrization and Suffix Averaging): يتم جعل قاعدة "ترك واحد خارجًا" الحتمية متماثلة عبر التباديل. يتم بناء متنبئ عشوائي $\hat{p}$ عن طريق متوسط هذه الدرجات المتماثلة عبر لاحقة من العينة (المؤشرات من $k$ إلى $2k-1$ ). تستخدم هذه الخطوة حجج مارتينجال العكسية والأمامية (التمهيديتان 3.1 و 3.2) والمكيفة من Aden-Ali et al. للتحكم في التباين وانحراف المخاطر الزائدة، مما يضمن أن الحد يسري بشكل موحد في $L^*$ .
العتبة وتقليل المخاطر التجريبية (Thresholding and ERM): يتم تحويل المتنبئ العشوائي $\hat{p}$ (الذي يأخذ قيمًا في $[-1, 1]$ ) إلى مصنف ثنائي حتمي. يتم ذلك من خلال النظر في فئة من الفرضيات ذات العتبات $T_{\hat{p}} = \{ x \mapsto 2\mathbb{1}[\hat{p}(x) \geq u] - 1 \}$ . ويتم اختيار مُقلل المخاطر التجريبية (ERM) من هذه الفئة باستخدام عينة تحقق مستقلة. ومن الأهمية بمكان أن الهيكل المتداخل لفئة العتبة يسمح بحد إنتروبي محلي دون تكبد عامل لوغاريتمي إضافي في حجم العينة، مما يحافظ على المعامل الأمثل لـ $L^*$ .

المساهمات والنتائج الرئيسية
تثبت الورقة النظرية 1 (Theorem 1)، مؤكدة وجود متعلم حتمي، لأي توزيع، وحجم عينة $n$ ، وثقة $\delta$ ، يُخرج مصنفًا $\hat{h}$ يحقق:
$L(\hat{h}) \leq L^* + 2 \cdot 10^8 \left( \sqrt{\frac{L^*(d + \log(48/\delta))}{n}} + \frac{d + \log(48/\delta)}{n} \right)$
بإحتمالية لا تقل عن $1-\delta$ . ويؤدي الاشتقاق النهائي في إثبات النظرية 1 إلى ثابت أكثر دقة يبلغ حوالي $3.1 \cdot 10^7$ .

الأمثلية: يطابق هذا الحد الحدود الدنيا لـ Devroye, Györfi, and Lugosi حتى الثوابت العالمية. إنها أول نتيجة تحقق المعدل الأمثل لكل $L^*$ ثابت، مما يردم الفجوة بين الأنظمة الواقعية والأنظمة المستقلة تمامًا عن الفرضيات دون عوامل لوغاريتمية فرعية غير مثالية.
الخصائص الخوارزمية: المتعلم حتمي، وغير دقيق عمومًا (outputting a classifier not necessarily in $H$ )، ولا يتطلب معرفة بـ $L^*$ أو $\delta$ .
الجدة التقنية: يعتمد الإثبات على متباينة الآيزوبريمتري الجديدة للحواف المعتمدة على الفئة (التمهيدية 2.1)، والتي تتحكم في أعداد الحواف المستحثة من خلال مزيج من أخطاء التقريب وعروض رادماخرر المسقطة، وهي تقنية متميزة عن النهج التوافقية أو عمليات العمليات التجريبية البحتة السابقة.

الأهمية
تدعي الورقة أنها حسمت تعقيد العينة لتعلم PAC المستقل عن الفرضيات حتى الثوابت العالمية. من خلال بناء خوارزمية تحقق حد المخاطرة الزائدة المينماكس (minimax excess risk) للتصنيف الثنائي عند كل $L^*$ ثابت، يحل المؤلفون مسألة مفتوحة منذ فترة طويلة تتعلق بوجود خوارزمية واحدة تكون مثالية عبر كامل طيف مستويات الضجيج. يوضح العمل أن المعدل الأمثل يمكن تحقيقه دون التضحية بالمعامل الرئيسي لـ $L^*$ ، وهو أمر كان يُعتقد سابقًا أنه صعب بسبب التوتر بين تقنيات التحليل الواقعي والتحليل المستقل عن الفرضيات.

المشكلة: المكتبة المشوشة

السر الخفي: المكعب والاتجاه

لماذا يهم هذا؟

ملخص تقني: خوارزمية PAC مثالية ومستقلة عن الفرضيات

أبحاث مشابهة