🔢 mathematics

Optimal training-conditional regret for online conformal prediction

تقترح هذه الورقة خوارزميات تنبؤ متوافق عبر الإنترنت ذات أمثلية "مينيمكس" لتدفقات البيانات غير المستقرة ذات الانزياح في التوزيع، وذلك باستخدام الكشف عن الانزياح لتحديث مجموعات المعايرة بشكل تكيفي والاستفادة من استقرار النموذج لتحقيق الندم التراكمي الأمثل المشروط بالتدريب.

المؤلفون الأصليون: Jiadong Liang, Zhimei Ren, Yuxin Chen

نُشر 2026-03-06

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

CC BY 4.0

المؤلفون الأصليون: Jiadong Liang, Zhimei Ren, Yuxin Chen

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

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

في عالم تعلم الآلة، يُسمى هذا التنبؤ المطابق (Conformal Prediction). وهو بمثابة شبكة أمان تخبرنا بمدى تأكد الكمبيوتر من إجابته. عادةً ما تعمل شبكات الأمان هذه بشكل رائع إذا ظل "الطقس" (البيانات) كما هو كل يوم.

ولكن ماذا يحدث عندما يتغير المناخ؟

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

إليك شرح لحلها، باستخدام تشبيهات من الحياة اليومية.

1. المشكلة: "الخريطة القديمة"

تخيل أنك تقود سيارة باستخدام نظام تحديد المواقع (GPS).

الطريقة القديمة: تم ضبط جهاز الـ GPS الخاص بك بناءً على خريطة من عام 2010. إذا تم افتتاح طريق سريع جديد اليوم، فإن جهاز الـ GPS لا يعلم بذلك، ويستمر في إخبارك باتخاذ الطريق القد، مما يجعلك تضل الطريق.
مقياس "الندم" (Regret): قدم المؤلفون طريقة جديدة لقياس الفشل. بدلاً من مجرد السؤال: "هل حصلت على الإجابة الصحيحة في المتوسط على مدار 10 سنوات؟" (وهو سؤال غامض للغاية)، هم يسألون: "في كل لحظة، ما مدى بُعد مستوى ثقتك عن الواقع؟"
- إذا قال جهاز الـ GPS "ثقة بنسبة 90%" ولكنك في الواقع تائه بنسبة 50% من الوقت، فهذا يعني وجود ندم عالٍ.
- إنهم يريدون تقليل هذا "الندم" قدر الإمكان، لضمان ألا تكون واثقاً جداً في اللحظات التي يجب أن تكون فيها غير متأكد.

2. السيناريوهان

يتناول المؤلفون نوعين من "تغيرات الطقس":

نقاط التغير المفاجئة (Change Points): تتغير البيانات فجأة. في دقيقة واحدة يكون الجو مشمساً، وفي الدقيقة التالية تهب عاصفة إعصارية.
الانجراف السلس (Smooth Drift): تتغير البيانات تدريجياً، مثل تحول الفصول من الصيف إلى الخريف.

3. الحل: "DriftOCP" (الملاح الذكي)

يقترح المؤلفون خوارزميتين رئيسيتين، اعتماداً على كيفية بناء "نموذج الطقس".

السيناريو (أ): النموذج المدرب مسبقاً (الخريطة الثابتة)

تخيل أن لديك خريطة رسمها خبير (نموذج مدرب مسبقاً) ولا يمكنك تغييرها. عليك فقط معرفة موقعك على تلك الخريطة.

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

السيناريو (ب): نموذج التعلم (السيارة ذاتية القيادة)

الآن، تخيل أن الخريطة ليست ثابتة. السيارة تتعلم القيادة أثناء سيرها، وتحدث خريطتها الخاصة في الوقت الفعلي. هذا أصعب لأن الخريطة تتغير بينما تحاول أنت معايرةها.

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

4. لماذا يهم هذا؟

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

هذه الورقة تبني منظم حرارة ذكياً يمكنه:

اكتشاف التغيير فوراً (كشف الانجراف - Drift Detection).
ضبط الإعدادات فوراً (المعايرة التكيفية - Adaptive Calibration).
الضمان بأنك لن تكون حاراً جداً أو بارداً جداً (الاستمثال الحد الأدنى الأقصى - Minimax Optimality).

الخلاصة الكبرى

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

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

إليك ملخص تقني مفصل لورقة "Optimal training-conditional regret for online conformal prediction" للباحثين Liang وRen وChen.

1. صياغة المشكلة

تتناول الورقة موضوع التنبؤ المطابق عبر الإنترنت (Online Conformal Prediction - OCP) في البيئات غير المستقرة حيث تتغير توزيعات البيانات بمرور الوقت.

الإعداد: تتدفق سلسلة بيانات متتالية $\{(X_t, Y_t)\}_{t=1}^T$ ناتجة عن عملية ديناميكية حيث يتغير التوزيع $D_t$ لـ $(X_t, Y_t)$ مع مرور الوقت. يجب على الخوارزمية بناء مجموعة تنبؤ $C_t(X_t)$ للاستجابة $Y_t$ باستخدام البيانات الماضية والميزة الحالية $X_t$ .
الهدف: تحقيق مستوى تغطية مستهدف $\alpha$ (أي $P(Y_t \in C_t(X_t)) \approx 1-\alpha$ ) عند كل خطوة زمنية $t$ .
الفجوة في الأعمال السابقة: تركز أدبيات OCP الحالية بشكل أساسي على:
1. الإعدادات العدائية (Adversarial settings): بافتراض عدم وجود بنية على $D_t$ .
2. التغطية الهامشية طويلة الأمد (Long-term marginal coverage): ضمان تقارب متوسط التغطية عبر الزمن إلى $1-\alpha$ .
- النقد: تسمح التغطية طويلة الأمد بحلول "فارغة" (على سبيل المثال، التنبؤ بالمجال بأكمله $\mathbb{R}$ باحتمالية $1-\alpha$ والمجموعة الفارغة $\emptyset$ باحتمالية $\alpha$ ) والتي تفشل في تقديم فترات معلوماتية في خطوات زمنية محددة. علاوة على ذلك، فإن مقاييس الندم العدائية غالبًا ما تفتقر إلى الارتباط المباشر بالصلاحية الإحصائية.
المقياس المقترح: قدم المؤلفون الندم التراكمي المشروط بالتدريب (Training-Conditional Cumulative Regret):
$\text{regret}_T = \sum_{t=1}^T \mathbb{E} \left[ \left| P(Y_t \in C_t(X_t) \mid \text{past data}, \text{internal randomness}) - (1-\alpha) \right| \right]$
يقيس هذا المقياس الانحراف في احتمال التغطية الشرطية عن الهدف عند كل خطوة، مجمعًا عبر الزمن. وهو يضمن أن الخوارزمية تمت معايرتها بناءً على البيانات الملحوظة حتى الآن، وليس فقط في المتوسط.

2. المنهجية

تقترح الورقة خوارزميتين متميزتين مصممتين لسيناريوهات مختلفة لتدريب دالة الدرجة (score function)، وكلاهما يستفيد من كشف الانحراف (drift detection) لتحديث مجموعات المعايرة بشكل تكيفي.

أ. السيناريو 1: الدرجات المدربة مسبقًا (DriftOCP)

السياق: درجات عدم التطابق (non-conformity scores) $s_t(\cdot, \cdot)$ مدربة مسبقًا على مجموعة بيانات مستقلة وتظل ثابتة أو تتطور بشكل مستقل عن التدفق عبر الإنترنت. هذا يحاكي طرق التحقق المطابق المنقسم (Split Conformal).
الخوارزمية (DriftOCP):
1. كشف الانحراف: تستخدم روتينًا فرعيًا DriftDetect يقوم بفحص نافذة زمنية $[t_0, t]$ بحثًا عن انحرافات ذات دلالة إحصائية في خطأ التغطية الكتلي التجريبي. وهي تتحقق مما إذا كان الانحراف التراكمي المعياري يتجاوز عتبة $\sigma$ .
2. تفكيك المراحل والجولات (Stage-Round Decomposition): يتم تقسيم الجدول الزمني إلى "مراحل" (يتم تحفيزها بواسطة كشف الانحراف) و"جولات" (أطوالها تزداد هندسيًا، $3^r$ ).
3. المعايرة التكيفية: ضمن مرحلة معينة، تفترض الخوارزمية الثبات. تقوم بتحديث عتبة المئيني $q$ باستخدام البيانات من الجولة السابقة. إذا تم اكتشاف انحراف، تبدأ مرحلة جديدة، ويتم إعادة تعيين مجموعة المعايرة.
أنواع الانحراف التي يتم التعامل معها:
- نقطة التغيير (Change-point): تحولات مفاجئة في التوزيع.
- الانحراف السلس (Smooth Drift): تطور مستمر في التوزيع (محدود بالتباين التراكمي).

ب. السيناريو 2: الدرجات المدربة تكيفيًا (DriftOCP-full)

السياق: يتم تدريب كل من النموذج التنبئي ودرجات عدم التطابق عبر الإنترنت باستخدام الملاحظات الماضية. يتطلب هذا طرق المطابقة الكاملة (Full Conformal) (باستخدام جميع البيانات للتدريب والمعايرة) لتجنب عدم كفاءة تقسيم البيانات.
التحدي: غالبًا ما تنتهك خوارزميات التعلم عبر الإنترنت (مثل SGD) تماثل التبديل (permutation symmetry) المطلوب لصلاحية المطابقة الكاملة الكلاسيكية.
الخوارزمية (DriftOCP-full):
1. افتراض الاستقرار: بدلاً من تماثل التبديل، يفترض المؤلفون أن خوارزمية التعلم مستقرة (التغييرات الصغيرة في بيانات التدريب تؤدي إلى تغييرات صغيرة في التنبؤات) وأن توزيع الاستجابة الشرطي مستمر ليبشيتز (Lipschitz continuous).
2. كشف الانحراف: يستخدم DriftDetect+ الذي يراقب تغطية مجموعات التنبؤ مباشرة (بدلاً من الدرجات فقط) لاكتشاف عدم الاستقرار.
3. بناء المطابقة الكاملة: في كل جولة، يتم تدريب النموذج على جميع البيانات السابقة للجولة الحالية، وتتكون مجموعة المعايرة من الجولة السابقة مباشرة.
الابتكار الرئيسي: يثبت المؤلفون أنه تحت افتراضات الاستقرار، يمكن لطرق المطابقة الكاملة تحقيق الصلاحية المشروطة بالتدريب حتى بدون تماثل التبديل.

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

مقياس أداء جديد: صياغة الندم التراكمي المشروط بالتدريب كمعيار لتقييم OCP تحت انحراف التوزيع، مع الحجج بأنها متفوقة على التغطية الهامشية طويلة الأمد أو الندم العدائي.
خوارزميات مثالية (Minimax-Optimal):
- للدرجات المدربة مسبقًا: تحقق DriftOCP حد ندم قدره $\tilde{O}(\sqrt{(N_{cp}+1)T})$ لنقاط التغيير و $\tilde{O}(\sqrt{T} + K_{ST}^{1/3}T^{2/3})$ للانحراف السلس (حيث $K_{ST}$ هو مسافة KS التراكمية).
- للدرجات المدربة تكيفيًا: تحقق DriftOCP-full حدودًا مماثلة (باستبدال مسافة KS بمسافة التباين الكلي) تحت افتراضات الاستقرار.
الحدود الدنيا للمينيمكس (Minimax Lower Bounds): اشتق المؤلفون حدودًا دنيا مطابقة لكلا الإعدادين.
- من المهم أنهم وضعوا حدًا أدنى لضبط المطابقة الكاملة المقيد بمجموعات التنبؤ ذات الـ $K$ -فاصلة، مما يظهر أن الخوارزميات المقترحة مثالية حتى العوامل اللوغاريتمية.
الضمانات النظرية للمطابقة الكاملة: إثبات ضمان تغطية جديد مشروط بالتدريب لطرق المطابقة الكاملة الدفعية باستخدام المتعلمين المستقرين (Proposition 4.1)، وهي نتيجة تمتد إلى ما وراء التبادلية وتماثل التبديل.
خالية من الأفق وفعالة: لا تتطلب الخوارزميات معرفة مسبقة بالأفق الزمني $T$ أو عدد نقاط الانحراف، وهي خفيفة حسابيًا (خطية في حجم النافذة).

4. النتائج

نظريًا:
- تتطابق حدود الندم مع الحدود الدنيا للمينيمكس، مما يثبت أن الخوارزميات مثالية من منظور المينيمكس.
- توضح الحدود صراحة المقايضة بين الأفق الزمني $T$ ، وحجم الانحراف (عدد نقاط التغيير أو التباين التراكمي)، وتعقيد مجموعات التنبؤ.
تجريبيًا:
- الدرجات المدربة مسبقًا: في تجارب مع تحولات التباين المفاجئة وانحرافات التحيز السلسة، تفوقت DriftOCP بشكل كبير على الاستدلال المطابق التكيفي (ACI). تعاني ACI من مقايضة حجم الخطوة (التكيف السريع مقابل الاستقرار)، بينما تتكيف DriftOCP بسرعة مع التحولات مع الحفاظ على الاستقرار خلال فترات الثبات.
- الدرجات المدربة تكيفيًا: عند استخدام SGD عبر الإنترنت لتحديثات النموذج، تنتج DriftOCP-full فترات تنبؤ أضيق مع تغطية مستقرة مقارنة بالنماذج المرجعية التي تستخدم نماذج مدربة مسبقًا ثابتة أو مناهج خالية من النماذج. لقد نجحت في التعامل مع النماذج الخطية المحددة جيدًا والخاطئة تحديدًا تحت تحولات المتوسط والتباين.

5. الأهمية

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