Online Conformal Prediction Beyond Feedback

صياغة المشكلة: التنبؤ الموحد عبر الإنترنت لما وراء التغذية الراجعة

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

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

المنهجية: التنبؤ الموحد عبر الإنترنت مع الاستعلامات (OCPQ)

يقترح المؤلفون التنبؤ الموحد عبر الإنترنت مع الاستعلامات (OCPQ)، وهي طريقة مصممة لهذا البروتوكول "ما وراء التغذية الراجعة". يتبع النهج خطوتين رئيسيتين:

1. الاختزال إلى المراقبة الجزئية: يتم اختزال المشكلة إلى لعبة مراقبة جزئية منتهية. تتكون "أذرع" اللعبة من مجموعة منتهية من عتبات التنبؤ $M \subset [0, 1]$ وإجراء استعلام منفصل.

   • إجراء التنبؤ: اختيار عتبة $m \in M$ يولد مجموعة تنبؤ $\Gamma_C(x_t, m)$ بناءً على مصنف صندوق أسود $C$. هذا الإجراء لا ينتج عنه أي ملاحظة (تغذية راجعة منعدمة $\perp$) ولا مكافأة مباشرة.
   • إجراء الاستعلام: اختيار إجراء الاستعلام يكشف الملصق الحقيقي $y_t$ ولكنه لا ينتج مجموعة تنبؤ ولا يعطي أي مكافأة.
   • هيكل المكافأة: تحدد الخوارزمية دالة مكافأة مساعدة $R(m, t)$. إذا كان الملصق الحقيقي مغطى بواسطة مجموعة التنبؤ ($y_t \in \Gamma_C(x_t, m)$)، فإن المكافأة هي $1 - m(1-\beta)$، حيث $\beta$ هو معامل يحدد من قبل المستخدم للتحكم في المقايضة بين التغطية والكفاءة. إذا لم يكن الملصق مغطى، فإن المكافأة هي 0. إجراء الاستعلام يعطي دائماً 0 مكافأة. هذا الهيكل يحفز المتعلم على اختيار عتبات ضيقة (صغيرة $m$) مع الحفاظ على التغطية.

2. تصميم الخوارزمية: تكيف OCPQ المتنبئ ذو الوزن الأسي الفعال في الملصقات لـ Cesa-Bianchi وLugosi وStoltz (2004).

   • في كل جولة $t$، تقوم الخوارزمية بإجراء استعلام باحتمالية ثابتة $\epsilon$.
   • إذا تم إجراء استعلام، يتم ملاحظة الملصق الحقيقي $y_t$. تقوم الخوارزمية بعد ذلك بتحديث تقديرات المكافأة التراكمية $\hat{Z}_{m,t}$ لجميع العتبات $m \in M$ باستخدام مخطط وزن الاحتمال العكسي، مما يعيد بناء المكافأة التي كانت ستُحصل لو تم اتخاذ قرار التنبؤ.
   • إذا لم يتم إجراء استعلام، تقوم الخوارزمية بأخذ عينة من عتبة $m_t$ من توزيع موزون أسياً بناءً على التقديرات الحالية $\hat{Z}_{m,t}$ وتخرج مجموعة التنبؤ المقابلة. لا يتم استقبال أي تغذية راجعة.

النتائج النظرية

تضع الورقة ضمانات للأفق المحدود لـ OCPQ تحت تدفق بيانات عدائي غافل (oblivious adversarial) بطول $T$:

• الندم (Regret): الندم المتوقع بالنسبة لأفضل عتبة ثابتة في الماضي هو $O(T^{2/3})$. وتحديداً، مع $\epsilon = T^{-1/3}$ و $\eta = T^{-2/3}\sqrt{\ln|M|}$، يكون الندم محدوداً بـ $T^{2/3}(2\sqrt{\ln|M|} + 1)$. يشير المؤلفون إلى أن هذا المعدل مثالي تقاربياً لهذه الفئة من ألعاب المراقبة الجزئية.
• التغطية: معدل التغطية المتوقع $p_{cover}$ يحقق:
  $$E[p_{cover}] \ge \beta - O(T^{-1/3})$$
  هذا يضمن أن التغطية تقترب من الهدف المحدد من قبل المستخدم $\beta$ مع زيادة $T$.
• معدل الاستعلام: تقوم الخوارزمية بالاستعلام عن الملصق في جزء $T^{-1/3}$ فقط من الجولات المتوقعة.
• حدود الاحتمالية العالية: تشتق الورقة أيضاً حدود الاحتمالية العالية لكل من الندم والتغطية، مما يثبت أن تباين أداء الخوارزمية يتم التحكم فيه ولا يظهر سلوكاً مرضياً.

النتائج التجريبية

أُجريت تجارب على مجموعات بيانات واقعية للتحقق من النهج:

• انزياح التوزيع: تم اختبار OCPQ على معايير قياسية (MNIST, CIF-10, CIFAR-100) حيث اختلف توزيع التدريب عن توزيع الاختبار (على سبيل المثال، من MNIST إلى USPS، أو من MNIST إلى MNIST-C). أظهرت النتائج أنه يمكن التحكم في المقايضة بين التغطية والكفاءة عبر المعامل $\beta$. وقد تجاوزت التغطية التجريبية باستمرار الحد الأدنى النظري.
• مراقبة سلامة النماذج اللغوية الكبيرة (LLM): تم تطبيق الطريقة لمراقبة سلامة مطالبات النماذج اللغوية الكبيرة باستخدام مجموعة بيانات WildGuardMix، والتي تتضمن مطالبات عادية ومطالبات تمت إعادة كتابتها بشكل عدائي. انخفضت دقة المصنف الأساسي بشكل كبير في المطالبات العدائية، ومع ذلك حافظت OCPQ على التغطية فوق الحد النظري مع الحفاظ على مجموعات تنبؤ غنية بالمعلومات.
• المقارنة: عند مقارنتها بـ Adaptive Conformal Inference (ACI)، التي تفترض وجود تغذية راجعة كاملة، حققت OCPQ حدود تغطية وكفاءة مماثلة رغم استخدامها لمعلومات أقل بكثير (الاستعلام في حوالي 5% فقط من الجولات).

الأهمية والمساهمات

تدعي الورقة المساهمات التالية:

1. بروتوكول جديد: صياغة OCP في إعداد "ما وراء التغذية الراجعة" حيث لا يتم تقييم التنبؤات المنشورة أبداً، وهو سيناريو شائع في تطبيقات السلامة الحرجة حيث تتوفر الملصقات فقط للاستعلامات الممتنعة.
2. الاختزال الخوارزمي: اختزال هذه المشكلة إلى لعبة مراقبة جزئية وتكييف تقنيات التعلم العدائي الفعالة في الملصقات لحلها، وتحديداً تعديل المتنبئ ليعامل الاستعلامات كأفعال متميزة تحل محل التنبؤات بدلاً من اتباعها.
3. الضمانات النظرية: توفير ضمانات الندم والتغطية المتوقعة لـ OCP في هذا الإعداد، مما يوضح أن التقييم الكمي الصالح لعدم اليقين ممكن مع إجراء $O(T^{-1/3})$ فقط من استعلامات الملصقات.
4. الفعالية العملية: تثبت التجارب أن الإشراف المتناثر (الاستعلامات العشوائية) كافٍ للحفاظ على مفاهيم التغطية والكفاءة المفيدة، حتى تحت انزياحات التوزيع العدائية، دون الحاجة إلى تغذية راجعة من مجموعات التنبؤ المنشورة.

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