ملخص تقني: استكشاف الاستكشاف في التحسين البايزي

بيان المشكلة

يُعد التحسين البايزي (Bayesian Optimization - BO) وسيلة قياسية لتعظيم الدوال "الصندوق الأسود" (black-box functions) من خلال بناء نماذج بديلة احتمالية (عادةً ما تكون عمليات غاوس - Gaussian Processes) بشكل متسلسل واختيار نقاط أخذ عينات جديدة عبر دالة استحواذ (Acquisition Function - AF). ويتمثل المكون الحاسم في أي خوارزمية تحسين بايزي ناجحة في قدرة دالة الاستحواذ على الموازنة بين الاستكشاف (البحث في المناطق غير المستكشفة لاكتشاف القيم المثلى العالمية) والاستغلال (تحسين البحث في المناطق الواعدة).

بينما يقر مجتمع التحسين البايزي على نطاق واسع بأن دوال الاستحواذ المختلفة تظهر درجات متفاوتة من التفضيل للاستكشاف، إلا أن هناك نقصاً كبيراً في المقاييس الكمية لتعريف هذه الخصائص ومقارنتها. تعاني المقاييس الحالية، مثل مسافة المركز الإجمالية (Total Center Distance - TCD) أو مسافة القمة (incumbent distance)، من عيوب ملحوية: فقد تفشل عندما تصيب العينة الأولية النقطة المثلى، أو لا تلتقط السلوك التذبذبي، أو تخلط بين المسافة من نقطة معينة والاستكشاف الحقيقي. علاوة على ذلك، فإن مقارنة دوال الاستحواذ من عائلات مختلفة (مثل Upper Confidence Bound مقابل الطرق القائمة على المعلومات) أمر صعب دون وجود مقياس عالمي. هذا الفجوة تعيق التحليل المنهجي والتصميم والاختيار لدوال الاستحواذ لمشكلات معينة في العالم الحقيقي.

المنهجية

لمعالجة نقص مقاييس الاستكشاف الكمية، يقترح المؤلفون نهجين مبتكرين يعتمدان على التوزيع المكاني للملاحظات المختارة أثناء عملية التحسين:

1. مسافة البائع المتجول للملاحظات (Observation Traveling Salesman Distance - OTSD)

تقيس OTSD الاستكشاف عن طريق حساب الحد الأدنى للمسافة الإقليدية المطلوبة لربط جميع نقاط الملاحظات في فضاء البحث، وتتم صياغتها كمسألة البائع المتجول (Traveling Salesman Problem - TSP).

• التعريف: بالنظر إلى مجموعة من $t$ من نقاط الملاحظة $X_t$، فإن OTSD هي إجمالي طول أقصر مسار يزور كل نقطة مرة واحدة بالضبط ويعود إلى نقطة البداية.
• التطبيع (Normalization): بما أن OTSD الخام تزداد بشكل رتيب مع عدد الملاحظات وتعتمد على الأبعاد، فقد قدم المؤلفون OTSD المطبّع (Normalized OTSD). ويتم اشتقاقه عن طريق قسمة OTSD الخام على حد أعلى نظري $\Psi(d, t)$، والذي يعتمد على البعد $d$ وعدد النقاط $t$. يسمح هذا التطبيع بالمقارنة عبر أبعاد المشكلات المختلفة وأعداد التكرارات المختلفة.
• الحساب: نظراً للطبيعة الصعبة (NP-hard) لمسألة TSP، استخدم المؤلفون خوارزمية استدراج (insertion heuristic) بتعقيد $O(dT^2)$، والتي تضمن طول مسار لا يتجاوز ضعف الطول الأمثل.

2. إنتروبيا الملاحظات (Observation Entropy - OE)

تقيس OE الاستكشاف عن طريق قياس مدى انتظام توزيع بيانات الملاحظات باستخدام نظرية المعلومات.

• التعريف: تعامل OE نقاط الملاحظة كعينات من متغير عشوائي وتقدر الإنتروبيا التفاضلية التجريبية. تشير قيم الإنتروبيا الأعلى إلى انتشار أكثر انتظاماً للنقاط، مما يعكس استكشافاً أكبر.
• التقدير: يستخدم المؤلفون مُقدّر كوزاتشينكو-ليونينكو (Kozachenko-Leonenko - KL) غير المعلمي، والذي يعتمد على مسافات أقرب جار. تم اختيار هذه الطريقة لكفاءتها في أخذ العينات وقابليتها للتطبيق في المساحات متوسطة الأبعاد ($d \le 50$).
• الخصائص: على عكس OTSD، فإن OE ليست رتيبة ويمكن أن تأخذ قيماً موجبة أو سالبة. يشير ارتفاع OE عبر التكرارات إلى أن دالة الاستحواذ تصبح أكثر استكشافاً، بينما يشير انخفاضها إلى التحول نحو الاستغلال.

المساهمات الرئيسية

1. مقاييس كمية مبتكرة: تقديم OTSD و OE كأول مقاييس كمية مخصصة لتوصيف سلوك الاستكشاف لدوال الاستحواذ بناءً على ملاحظاتها المختارة.
2. تصنيف تجريبي: إنشاء أول تصنيف تجريبي لاستكشاف دالة الاستحواذ. من خلال تطبيق OTSD و OE عبر اختبارات متنوعة، يضع المؤلفون ترتيباً جزئياً لدوال الاستحواذ (على سبيل المثال: البحث العشوائي $\succeq$ UCB (بـ $\beta$ مرتفع) $\succeq$ الطرق القائمة على المعلومات $\approx$ KG $\succeq$ EI $\succeq$ PI $\succeq$ UCB (بـ $\beta$ منخفض) $\succ$ الاختيار الحتمي).
3. تقييم شامل: تجارب مكثفة على اختبارات قياسية اصطناعية وواقعية (تتراوح من الأبعاد المنخفضة إلى العالية، $d=2$ إلى $d=180$) ومختلف متغيرات دالة الاستحواذ (بما في ذلك التقييمات المجمعة/Batched، مناطق الثقة/Trust Regions، وعينات RAASP).
4. الحدود النظرية: اشتقاق الحدود العليا والدنيا النظرية لقيم OTSD و OE الحقيقية، مما يوفر أساساً إحصائياً للمقدرات المقترحة.

النتائج

تؤكد التجارب فعالية OTSD و OE في التقاط سلوكيات الاستكشاف:

• الاتساق: تظهر OTSD و OE ارتباطاً قوياً عبر مشكلات الاختبار، مما يؤكد موثوقيتهما. نجح كلا المقياسين في التمييز بين الاستراتيجيات الاستكشافية المعروفة (مثل البحث العشوائي، و UCB مع $\beta$ مرتفع) والاستراتيجيات الاستغلالية (مثل PI، والاختيار الحتمي).
• تأثيرات الأبعاد: تكشف الدراسة أن الأبعاد تؤثر بشكل كبير على سلوك الاستكشاف. على سبيل المثال، يعد "أخذ عينات ثومبسون" (Thompson Sampling - TS) استكشافياً بدرجة متوسطة في الأبعاد المنخفضة، ولكنه يصبح استكشافياً بشكل مفرط في الأبعاد العالية، حيث يتجاوز غالباً البحث العشوائي في قيمة OTSD. وعلى العكس من ذلك، فإن "التحسين المتوقع" (Expected Improvement - EI) يكون أكثر استكشافاً من UCB في الأبعاد المنخفضة، ولكنه يصبح أقل استكشافاً في الأبعاد العالية.
• تأثير التقنيات:
  • التجميع (Batching): يزيد الاستكشاف (OTSD/OE أعلى) حيث تجبر أحجام الدفعات الأكبر على اختيار نقاط متنوعة.
  • مناطق الثقة (TRs) و RAASP: تقلل الاستكشاف باستمرار، مما يؤدي إلى سلوك أكثر استغلالاً.
• الارتباط بالأداء: تشير النتائج إلى أن أفضل الطرق أداءً لا تظهر مستويات استكشاف قصوى. بدلاً من ذلك، تحافظ على توازن بين الاستكشاف والاستغلال (EETO). الطرق ذات الاستكشاف المفرط (مثل TS في الأبعاد العالية) أو الاستغلال المفرط غالباً ما تعطي أداء تحسين أدنى.

الأهمية والادعاءات

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

• تشخيص سلوك دالة الاستحواذ: تحديد ما إذا كانت دالة الاستحواذ استكشافية للغاية (مثل TS في الأبعاد العالية) أو استغلالية للغاية لمشكلة معينة، مما قد يعمل كإشارة تحذير.
• بناء محافظ (Portfolios): اختيار دوال الاستحواذ المناسبة أو مجموعات منها (مثل إضافة RAASP إلى دالة استحواذ عالية الاستكشاف) بناءً على مستوى الاستكشاف المطلوب.
• الإيقاف المبكر: اكتشاف متى استنفدت دالة الاستحواذ القيم الصغرى المحلية (مما يشير إليه تغير اتجاهات OTSD/OE)، مما يوحي بأن عملية التحسين قد تكون جاهزة للانتهاء.

يؤكد المؤلفون أنه على الرغم من أن نتائجهم قوية تجريبياً، إلا أنها تقتصر على المجالات المستمرة ولا تأخذ حالياً في الاعتبار التأثيرات المحددة لمعلمات (hyperparameters) عملية غاوس (GP). يهدف العمل المستقبلي إلى توسيع هذه التصنيفات لتشمل المجالات غير الإقليدية واستقصاء تأثير معلمات النواة (kernel) والاحتمالية (likelihood).