ثنائيات على سحب النقاط

ماذا يبدو التحطيم

ضع n نقطة في مستوينا. اختر فئة فرضيات (المصنفات الخطية = الخطوط المستقيمة). احسب كم عدد الطرق المختلفة التي يمكن لفئتنا أن تسمي تلك النقاط n (±/− على كل جانب من الخط). اسم هذا العدد Π_H(n).

إذا كان Π_H(n) = 2ⁿ، فئتنا تحطم مجموعة النقاط تلك — يمكنها إنتاج كل تسمية ممكنة. إذا كان Π_H(n) < 2ⁿ، بعض التسميات لا يمكن أن تحدث.

ثلاث نقاط في موضع عام

المصنفات الخطية في ℝ² تحطم أي 3 نقاط غير خطية. 2³ = 8 تسميات؛ كل 8 قابلة للتحقق بخط ما. اختر أي 3 نقاط؛ لكل تسمية ±/±، ارسم خطاً يفصل الموجبة عن السالبة.

أربع نقاط ترفض التحطيم

ضع 4 نقاط عند زوايا مربع. حاول تسمية الزوج القطري كموجب والزوج المضاد القطري كسالب (تسمية XOR). لا يوجد خط مستقيم يفصلهما. إذاً Π_H(4) ≤ 14 < 16 = 2⁴.

بعد VC كأقصى حجم تحطيم

VC(خطي ℝ²) = 3. نستطيع أن نحطم 3 نقاط؛ لا نستطيع أن نحطم 4. بعد VC يعد سعة ثنائية الفرضيات لفئة الفرضيات الخاصة بنا.

الحدس الهندسي

أعلى VC = فئتنا ترسم حدود قرار أكثر تطوراً. الخطي (VC = d+1 في d البعد) يرسم الفرضيات. كثيرات الحدود ترسم منحنيات. الشبكات العصبية ترسم متنوعات مطوية بشدة. قابلية ثني أكثر = ثنائيات أكثر = VC أعلى = متطلب عينات أعلى.

عد الثنائيات

فكر في المصنفات الخطية في ℝ² (الخطوط). لدينا 5 نقاط موضوعة في موضع عام (لا 3 خطية، لا واحدة زائدة).

كتلة احتمالية على متنوعة الفرضيات

تصور PAC-Bayes

صور فضاء الفرضيات الخاص بنا كمتنوعة عالية الأبعاد. كل نقطة على هذه المتنوعة تتوافق مع تكوين وزن واحد لشبكة عصبية. الأولوية P تعين توزيع احتمالي على المتنوعة (غالباً غاوسي مركزي عند التهيئة). الاحتمالية الخلفية Q تركز كتلة احتمالية حيث بيانات التدريب قادت الأوزان الخاصة بنا.

اختلاف KL كمسافة هندسية

يقيس KL(Q‖P) مدى انجراف Q بعيداً عن P. القراءة الهندسية: مدى حركة سحابة الاحتمالية الخلفية من سحابة الأولوية، موزونة بمدى احتمالية كل منطقة احتمالية خلفية تحت أولويتنا.

KL صغير = Q تتداخل P بشدة. الاحتمالية الخلفية بالكاد تحركت. فجوة التعميم تبقى صغيرة.

KL كبير = Q مركزة في مناطق أعطتها P كتلة احتمالية قليلة. الاحتمالية الخلفية تحركت كثيراً. فجوة التعميم تنمو.

لماذا تهم هذه الهندسة

تخيل SGD كمسار بحث عبر متنوعة الفرضيات. المسار ينتهي في حوض خسارة تدريب منخفضة. يسأل PAC-Bayes: كم واسع هذا الحوض؟

حوض واسع = تكوينات وزن جارة كثيرة تحقق خسارة تدريب منخفضة أيضاً. يمكن للاحتمالية الخلفية Q أن تنتشر على منطقة واسعة و لا تزال تحقق خطراً منخفضاً. KL(Q‖P) يبقى مقيداً. فجوة التعميم صغيرة.

حوض ضيق = مجموعة رقيقة فقط من الأوزان تحقق خسارة منخفضة. يجب على الاحتمالية الخلفية أن تركز بحدة. KL ينمو. فجوة التعميم توسع.

هذا يتصل مباشرة بنقاش الحد الأدنى المسطح مقابل الحاد (Hochreiter & Schmidhuber 1997, Keskar et al 2017). الحد الأدنى المسطح يعمم بشكل أفضل لأنه يدعم احتمالايات خلفية أوسع مع KL أصغر.

قراءة عرض حوض

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

- النموذج A: حوض مسطح، الاحتمالية الخلفية تنتشر على منطقة مع KL(Q_A‖P) = 50 nats.

- النموذج B: حوض حاد، الاحتمالية الخلفية تركز مع KL(Q_B‖P) = 500 nats.

كلاهما مدرب على n = 10,000 مثال مع خطر تجريبي 0.05، δ = 0.05.

منحنى ينخفض حيث توقعت النظرية الارتفاع

منحنى U الكلاسيكي

ارسم سعة النموذج على المحور الأفقي. ارسم خطر الاختبار على المحور الرأسي. تتنبأ النظرية الكلاسيكية للانحياز-التباين:

- السعة المنخفضة: انحياز عالي، خطر اختبار عالي (نقص الملاءمة)

- السعة المتوسطة: انحياز منخفض + تباين منخفض، خطر اختبار منخفض (النقطة الحلوة)

- السعة العالية: انحياز منخفض، تباين عالي، خطر اختبار عالي (الإفراط في الملاءمة)

النتيجة: منحنى على شكل U. اختر السعة عند قاعنا.

ما لاحظه Belkin et al (2019)

ماضي عتبة الاستيفاء (السعة حيث يناسب النموذج بيانات التدريب بالضبط مع خطأ صفر)، ينخفض خطر الاختبار مرة أخرى. يقرأ المنحنى: انحدار → ذروة عند الاستيفاء → انحدار ثانٍ. انحدارات اثنان، منحنى واحد.

القراءة الهندسية للانحدار الثاني

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

ماضي عتبة الاستيفاء، حلول استيفاء كثيرة موجودة. لـ SGD حرية لاختيار واحد سلس (minimum-norm، curvature منخفض). الصورة الهندسية: متنوعة الحل تصبح أوسع وأكثر مسطحة. التحيز الضمني لـ SGD يختار حلول حميدة من هذه المتنوعة المسطحة. ينخفض خطر الاختبار.

لماذا تفتقد النظرية الكلاسيكية هذا

بعد VC يعد سعة مجموعة الحل لكن يتجاهل أي حل يتم اختياره. يفترض الحد الكلاسيكي أسوأ حالة empirical risk minimizer. الواقع: SGD بشكل موثوق يختار حلنا الأسطح والأملسة المستيفاة. بمجرد أننا نحسب الحلول التي اختارها SOLVER بدلاً من جميع الحلول، ينطقي الانحدار الثاني.

أخذ الهندسة للبيت

تهم السعة أقل من هندسة الحوض. الأحواض المسطحة الواسعة (بعد الاستيفاء) تعمم بشكل أفضل من الضيقة الحادة (عند الاستيفاء). تحاول النظرية الحديثة قيد التعميم بعرض الحوض، وليس بعدد المعاملات.

تحديد موقع الانحدارات الاثنان

على منحنى الانحدار المزدوج، ثلاثة مناطق تهم: (1) نظام تحت-معاملة، (2) ذروة استيفاء، (3) نظام فوق-معاملة.

سطح قانون الطاقة في فضاء المعاملات-الرموز

سطح ثلاثي الأبعاد

ارسم المعاملات N على محور أفقي واحد. ارسم الرموز D على محور أفقي ثانٍ. ارسم الخسارة L على المحور الرأسي. تنحت الخسارة التجريبية سطح قانون طاقة عبر هذا مستوى (N, D):

L(N, D) ≈ (Nc/N)^αN + (Dc/D)^αD + L∞

ينخفض السطح مع نمو N أو D. تتبع الانحدارات قوانين قوة log-linear (خطوط مستقيمة في رسم log-log). يبقى الخط المقارب L∞ موجب — خسارة غير قابلة للاختزال لا يمكن لنموذجنا تقليلها.

سلسلة جبل مثالية للحساب

اثبت إجمالي ميزانية الحساب C ∝ N × D (معاملات × رموز، تقريباً). قطع سطحنا على طول هذا القيد. قطع تتبع يقطع منحنى ثنائي الأبعاد من خلال السطح ثلاثي الأبعاد. قاع هذا المنحنى = نقطة مثالية للحساب.

احسبت Chinchilla (Hoffmann et al 2022) هذا القاع بشكل تحليلي: D_opt ≈ 20 × N. المنحنى على طول ميزانية الحساب = سلسلة جبل. المشي على طول سلسلة الجبل: حساب متساوٍ، خسارة متناقصة. المشي بعيداً عن سلسلة الجبل (معاملات أكثر من 20× الرموز، أو أقل): حساب مهدور.

القراءة الهندسية لـ GPT-3 مقابل Chinchilla

GPT-3: 175B معاملات، 300B رموز. يريد Chinchilla-مثالي 175B × 20 = 3500B رموز. يجلس GPT-3 بعيداً جداً عن سلسلة الجبل الحساب-مثالية في اتجاه الثقيل بالمعاملات. Chinchilla نفسها: 70B معاملات مدربة على 1400B رموز. 1400 / 70 = 20 — بالضبط على سلسلة الجبل. كسرت Chinchilla GPT-3 بأقل من نصف عدد معاملاتها بالجلوس على الأمثل الهندسي.

جدار البيانات كمستوى رأسي

ويب عامة ~10¹³ رموز قابلة للاستخدام. هذا يرسم كجدار رأسي في D = 10¹³ على مستوى المعاملات-الرموز. ماضي هذا الجدار، يتطلب التدريب مثالي الحساب N ≤ D / 20 = 5 × 10¹¹ معاملات. تجاوز الجدران N = 5 × 10¹¹ يعمل إما غير مدرب بالكامل (خارج سلسلة الجبل) أو يتطلب بيانات اصطناعية / متعددة الأنماط / RL لدفع الجدار للخارج.

المشي على سلسلة الجبل مثالية الحساب

نحن نجلس عند إحداثيات GPT-3: N = 175B معاملات، D = 300B رموز. وكيل الحساب C = N × D = 5.25 × 10²² معامل-رموز.

احتمالية خلفية بيتا تتقلص إلى إبرة

كثافة احتمالية على [0, 1]

Beta(α, β) هو كثافة احتمالية على الفترة الوحدة [0, 1]. متغير: ε = معدل الخطأ الحقيقي. الشكل: α يتحكم بالكتلة على جانب ε العالي؛ β يتحكم بالكتلة على جانب ε المنخفض.

Beta(1, 1): موحد — بلا معلومات، كثافة مسطحة على [0, 1].

Beta(α, β) مع α + β كبير: ذروة مركزة عند α / (α + β).

عرض ذروة Beta تتقلص بـ 1/√(α+β). إضافة 100 ملاحظة إلى أولويتنا تشد الذروة بعامل √100 = 10. إضافة 10000 ملاحظة تشد بـ √10000 = 100.

القراءة الهندسية لتشغيل تدقيق

ابدأ: Beta(1, 1) = مستطيل مسطح على [0, 1]. عدم يقين أقصى عن ε.

بعد 200 استعلام مع 8 تزييفات: Beta(9, 193). المتوسط = 9/202 ≈ 0.045. الكثافة الآن هضم حاد متمركز بالقرب من 0.045 مع عرض مميز σ ≈ 0.014.

بعد 2000 استعلام مع 80 تزييفات: Beta(81, 1921). المتوسط لا يزال ≈ 0.045، لكن العرض σ ≈ 0.0046. هضم ثلاث مرات أحد.

بعد 200,000 استعلام مع 8000 تزييفات: Beta(8001, 192,001). المتوسط ≈ 0.040، عرض σ ≈ 0.0004. الهضم يصبح إبرة.

تقارب هندسي نحو كتلة نقطة

مع n → ∞، الاحتمالية الخلفية البيتا تنهار إلى Dirac delta عند ε الحقيقي. الهندسة: مستطيل → هضم واسع → هضم ضيق → إبرة → نقطة. كل استعلام يشد توزيعنا بـ 1/√n.

لماذا هذا يتفوق على حدود PAC النظرية

تعطي حدود PAC النظرية تقدير ε STATIC استناداً إلى حجم فئة الفرضيات. تعطي الاحتمالية الخلفية البيتا تقدير ε DYNAMIC يشد مع كل ملاحظة، معايرة ضد توزيعك الحقيقي-العالمي. الحد النظري = ضمان تحت الافتراضات الحالة الأسوأ. التدقيق التجريبي = قياس الواقع الفعلي.

كم استعلام لتقليل الفترة الموثوقة إلى النصف؟

نحن حالياً نجلس عند Beta(9, 193) بعد 200 استعلام: متوسط ε ≈ 0.045، σ ≈ 0.014. نريد تقليل عرض الفترة الموثوقة إلى النصف إلى σ ≈ 0.007.