🤖 machine learning

Quotient DAGs for Off-Policy Evaluation:Forward-Flow Importance Sampling and Exact Slate Propensities

تقدم هذه الورقة إطار عمل (quotient-DAG) وخوارزمية (Forward-DP) للقضاء على تباين المتغيرات المزعجة وتمكين الحساب الدقيق لميول القوائم غير المرتبة (unordered slate propensities) من أجل تقييم فعال خارج السياسة في أنظمة التوصية ذات التوليد الذاتي (autoregressive recommendation systems).

المؤلفون الأصليون: Ziwen Xie, Shaowen Xiang, Hongyu He, Dianbo Liu

نُشر 2026-05-29

📖 4 دقيقة قراءة☕ قراءة في استراحة قهوة

CC BY 4.0

المؤلفون الأصليون: Ziwen Xie, Shaowen Xiang, Hongyu He, Dianbo Liu

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

تخيل أنك طاهٍ يحاول الحكم على مدى جودة وصفة جديدة (السياسة المستهدفة - Target Policy) ولكن لا يمكنك طهيها في مطبخك الخاص لأن ذلك مكلف أو محفوف بالمخاطر. بدلاً من ذلك، لديك دفتر ملاحظات مليء بوصفات طهيها طاهٍ آخر (سياسة السلوك - Behavior Policy) في الماضي. هدفك هو تقدير مدى لذة الوصفة الجديدة باستخدام دفتر الملاحظات القديم فقط. هذا هو جوهر مشكلة تقييم ما وراء السياسة (Off-Policy Evaluation - OPE).

المشكلة: حساب الأشياء الخاطئة

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

لكن هنا تكمن العقبة: في بعض الأحيان، لا يغير ترتيب إضافة المكونات في الواقع طعم الطبق النهائي.

السيناريو: تخيل "مجموعة" (slate) من العناصر (مثل قائمة تشغيل مكونة من 5 أغاني أو صينية تحتوي على 5 مقبلات). العميل يهتم فقط بـ أي 5 عناصر موجودة في الصينية، وليس بالترتيب الذي وضع بها الطاهي تلك العناصر.
الخطأ: يسجل الدفتر القديم الترتيب (الأغنية أ، ثم ب، ثم ج...). إذا حسبت درجتك بناءً على هذا الترتيب المحدد، فأنت تعامل "الترتيب" كأنه أمر مهم. ولكن بما أن العميل لا يهتم به، فأنت تضيف "ضجيجاً" (noise) إلى حساباتك.
النتيجة: هذا الضجيج يخلق حالة هائلة من الارتباك (التباين/variance). الأمر يشبه محاولة تخمين وزن حقيبة سفر عن طريق وزن كل جورب داخلها بشكل فردي، بدلاً من وزن الحقيبة ككل فقط. ستحصل على إجابات مختلفة كثيرة اعتماداً على كيفية عدّك للجوارب.

علاوة على ذلك، فإن حساب الاحتمالية "الحقيقية" للحصول على مجموعة معينة من 5 عناصر (مع تجاهل الترتيب) هو كابوس رياضي. إذا كان لديك 5 عناصر، فهناك 120 طريقة مختلفة (5 عاملي/factorial) يمكن بها اختيارها. القيام بهذا الحساب لكل مدخل في دفتر ملاحظاتك هو أمر مستحيل حاسوبياً.

الحل: "المخطط الموجه المقلوب" (خريطة التجميع)

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

التشبيه: تخيل شجرة ضخمة حيث يمثل كل فرع فيها ترتيباً مختلفاً لإضافة المكونات.
- الطريقة القديمة: تسير في كل فرع، وتقيس الوزن، وتحاول حساب المتوسط.
- الطريقة الجديدة (الرسم البيالي المقلوب - Quotient DAG): تدرك أن جميع الفروع التي تنتهي بنفس مجموعة المكونات هي في الواقع نفس "العقدة" في خريطتك. تقوم بدمج كل تلك الفروع في نقطة واحدة.
- الخريطة: هذا ينشئ "رسماً بيانياً موجهاً غير حلقي" (Directed Acyclic Graph - DAG) — وهي خريطة تهتم فقط بـ مجموعة العناصر المختارة حتى الآن، وليس بالترتيب.

الخدعة السحرية: أخذ عينات الأهمية للتدفق الأمامي

بمجرد الحصول على هذه الخريطة المبسطة، تحتاج إلى معرفة مدى احتمالية وصول الطاهي الجديد إلى "مجموعة" معينة مقارنة بالطاهي القديم.

الطريقة القديمة: سيتعين عليك جمع احتمالات الـ 120 ترتيباً مختلفاً للحصول على الإجابة.
الطريقة الجديدة (البرمجة الديناميكية الأمامية - Forward-DP): ابتكر المؤلفون طريقة تسمى Forward-DP (البرمجة الديناميكية الأمامية). فكر في هذا كآلة حاسبة ذكية تبني الإجابة خطوة بخطوة.
- تبدأ بصينية فارغة (احتمالية 1).
- تسأل: "إذا كان لدي عنصر واحد، فما هي فرصة إضافة عنصر ثانٍ؟"
- تسأل: "إذا كان لدي عنصران، فما هي فرصة إضافة عنصر ثالث؟"
- تستمر في بناء احتمالية المجموعة الكاملة دون الحاجة أبداً لسرد جميع الـ 120 ترتيباً.

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

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

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

الملخص

تقدم الورقة طريقة للتوقف عن الإفراط في تحليل "كيفية" (ترتيب الإجراءات) والتركيز على "ماذا" (المجموعة النهائية من العناصر). من خلال تجميع المسارات المتكافئة معاً واستخدام طريقة حساب ذكية وخطوة بخطوة (Forward-DP)، يمكننا تقييم الاستراتيجيات الجديدة بدقة وكفاءة أكبر بكثير، خاصة في مجالات مثل الرعاية الصحية أو محركات التوصية حيث يكون اختبار الأفكار الجديدة في الحياة الواقعية خطيراً جداً أو مكلفاً للغاية.

ملخص تقني: الرسوم البيانية الموجهة غير الحلقية (Quotient DAGs) للتقييم خارج السياسة (Off-Policy Evaluation)

بيان المشكلة

يقوم التقييم خارج السياسة (OPE) بتقدير أداء سياسة مستهدفة $\pi$ باستخدام بيانات تم جمعها بواسطة سياسة سلوكية $\beta$ . تعيد طريقة "أخذ العينات بالأهمية" (Importance Sampling - IS) القياسية وزن المسارات المسجلة عبر حاصل ضرب نسب احتمالية الإجراء من المستهدف إلى السلوك. ومع ذلك، غالبًا ما تتعامل هذه الطريقة مع تفاصيل عملية التوليد كأنها ذات معنى حتى عندما يتجاهل هدف التقييم تلك التفاصيل.

تظهر حالة رئيسية لهذه المشكلة في توصية القوائم (Slate Recommendation)، حيث تقوم المولدات الحديثة غالبًا ببناء القوائم (مجموعات من العناصر) بشكل تتابعي (Autoregressively)، مما يكشف عن احتمالات الخطوات لكل ترتيب محدد. ومع ذلك، فإن المكافأة والمقدرات اللاحقة تعتمد فقط على القائمة غير المرتبة. تعين طريقة IS للمسارات التقليدية نسبة احتمالية لمسار مرتب محدد، مما يخلق "فجوة احتمالية مشتركة" (Joint-Propensity Gap)؛ حيث يكشف المسجل عن احتمال ترتيب معين، بينما يتطلب المقدر الاحتمال الإجمالي للقائمة غير المرتبة. حساب هذا الاحتمال غير المرتب بدقة يتطلب عادةً الجمع عبر جميع الترتيبات الممكنة $K!$ ، وهو أمر مستعصٍ حاسوبيًا بالنسبة لأحجام القوائم المتوسطة. علاوة على ذلك، فإن التعامل مع الترتيب كعنصر ذي أهمية يُدخل تباينًا غير مرغوب فيه (Nuisance Variance) عندما تكون المكافأة ثابتة تجاه ترتيب التوليد.

المنهجية

يقدم البحث رؤية الرسم البياني الموجه غير الحلقي (Quotient-DAG) لمعالجة هذه المشكلات. الفكرة الجوهرية هي إجراء "قسمة" (Quotient) لشجرة الانتشار (Rollout Tree) عبر علاقة تكافؤ كافية لهدف التقييم.

الرسم البيئي الموجه غير الحلقي والتدفق الأمامي:
- يتم ضغط شجرة الانتشار عن طريق دمج بادئات التاريخ (History Prefixes) المتكافئة لهدف التقييم (على سبيل المثال: البادئات التي تحتوي على نفس مجموعة العناصر المختارة، بغض النظر عن ترتيبها).
- يشكل هذا رسمًا بيانيًا موجهًا غير حلقي (DAG) متعدد الطبقات، حيث تمثل العقد فئات التكافؤ (Quotient States).
- بدلاً من الوزن باستخدام نسبة مسار واحد محقق، تعين الطريقة أوزانًا باستخدام نسبة التدفق الأمامي $F_\pi(z)/F_\beta(z)$ ، حيث $F_\mu(z)$ هي الكتلة الاحتمالية التي تصل إلى العقدة $z$ تحت السياسة $\mu$ .
- تعمم هذه الطريقة الأساليب الموجودة: مثل IS لكل قرار (Per-decision IS)، وIS الهامشي (Marginalized IS)، وMIS ذو التجريد المعروف، وهي حالات خاصة تتوافق مع خيارات مختلفة لعلاقات التكافؤ.
أخذ العينات بالأهمية للتدفق الأمامي (FF-IS):
- بالنسبة لـ OPE العام ذي الأفق المحدود، يستبدل المقدر نسبة البادئة المأخوذة في PDIS بنسبة الاحتمال في القسمة (Quotient Likelihood Ratio).
- يُظهر التحليل النظري أنه بالنسبة للعوائد النهائية القابلة للقياس بالقسمة، فإن هذا الوزن يزيل عدم التطابق بين الهدف والسلوك داخل الفئة الواحدة، ويوفر تعبيرًا دقيقًا لفجوة التباين يحدد مقدار خفض التباين الناتج عن العناصر غير المرغوب فيها.
البرمجة الديناميكية الأمامية (Forward-DP) لتقييم القوائم:
- يخصص البحث هذا الإطار لـ توليد القوائم التتابعي تحت واجهة كافية للمجموعة (Set-Sufficient) (التعريف 1). تُعتبر السياسة "كافية للمجموعة" إذا كان احتمال اختيار العنصر التالي يعتمد فقط على السياق ومجموعة العناصر المختارة بالفعل، وليس على ترتيبها.
- تحت شرط كفاية المجموعة، تقابل قسمة التباديل رسمًا بيانيًا فرعيًا (Subset DAG)، حيث تمثل العقد مجموعات جزئية من الكتالوج، وتمثل الحواف إضافة عناصر غير مختارة.
- خوارزمية Forward-DP: تقوم خوارزمية البرمجة الديناميكية بحساب احتمال القائمة غير المرتبة الدقيق $F_\mu(S|x)$ $F_{μ} (S ∣ x)$ عن طريق الجمع عبر المجموعات الجزئية بدلاً من التباديل.
  - التعقيد: $O((M + K) \cdot 2^K)$ ، حيث $M$ هو حجم الكتالوج و $K$ هو حجم القائمة. وهذا يتجنب تعداد $K!$ .
  - الأمثلية: يثبت البحث أن أي خوارزمية حتمية تحسب الاحتمالات غير المرتبة بدقة للسياسات الكافية للمجموعات يجب أن تستعلم عن كل مجموعة جزئية صحيحة من القائمة في أسوأ الحالات، مما يثبت أن Forward-DP هي الخوارزمية المثلى للاستعلام (Query-optimal) حتى مع وجود ثوابت.

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

إطار نظري: رؤية موحدة للـ Quotient-DAG لـ OPE تشتق نسب الاحتمال الدقيقة كنسب تدفق أمامي على فضاء عينة أكثر خشونة.
ابتكار خوارزمي: خوارزمية Forward-DP، التي تحسب احتمالات القوائم غير المرتبة الدقيقة للوغاريتمات التتابعية المعتمدة على السياق والكافية للمجموعات، في وقت يتناسب طرديًا مع حجم الكتالوج وأسيًا مع حجم القائمة (قابلة للحل في زمن حدودي بالنسبة لـ $K$ ).
تقليل التباين: إثبات رسمي بأن وزن القسمة يزيل مكون التباين الناتج عن ترتيبات التوليد غير ذات الصلة (تباين الترتيب غير المرغوب فيه)، لا سيما عندما تكون المكافآت ثابتة تجاه تسلسل توليد القائمة.
اللبنات الأساسية لتقييم القوائم: تقديم Forward-DP كأداة أساسية تتيح التقييم الدقيق القائم على الاحتمالات واختيار النماذج لموصيات القوائم القائمة على المحولات (Transformers)، مما يسد الفجوة للمسجلات المعتمدة على السياق حيث لا تنطبق صيغ Plackett-Luce ذات الدرجات الثابتة.

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

قيم المؤلفون طريقتهم على اختبارات MDP ذات الأفق المحدود ومهام توصية القوائم:

نماذج MDP ذات الأفق المحدود (Sepsis & ICU-Sepsis):
- قلل FF-IS بشكل كبير من جذر متوسط مربع الخطأ (RMSE) مقارنة بـ Trajectory IS والأساليب المرجعية الأخرى (مثل DualDICE و GenDICE).
- في اختبار Sepsis، قلل FF-WIS من RMSE من 0.291 (في WIS) إلى 0.0568.
- تحققت هذه المكاسب باستخدام المسارات المسجلة فقط دون الحاجة لملائمة نموذج انتقال.
تجارب KuaiRec للقوائم:
- الكفاءة الحسابية: تحسب Forward-DP الاحتمالات الدقيقة بسرعة أكبر بمراحل من تعداد $K!$ . بالنسبة لـ $K=8$ ، استغرق التعداد حوالي 97,108 ثانية، بينما استغرقت Forward-DP حوالي 8.94 ثانية. بالنسبة لـ $K=12$ ، يصبح التعداد مستحيلاً، بينما تكتمل Forward-DP في حوالي 13.7 ثانية.
- التقييم خارج السياسة (OPE): تفوقت المقدرات التي تستخدم أوزان Forward-DP (مثل FF-OIS و FF-DR) باستمرار على نظيراتها الموزونة بالمسارات (OIS و DR) عبر جميع أحجام القوائم ( $K \in \{4, 6, 8\}$ ) من حيث RMSE.
- اختيار النماذج: في اختيار النماذج خارج السياسة بين الموصيات التتابعية (Transformer-based)، حققت المقدرات التي تستخدم Forward-DP (مثل Tree-DR و DP-OPCB-DR) دقة أعلى في Top-1، وارتباط Spearman أعلى، وندم (Regret) أقل مقارنة بالطرق القائمة على المسارات.

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

يزعم البحث أن الإطار المقترح يوفر عملية Rao–Blackwellization لـ per-decision IS. من خلال إجراء "القسمة" على شجرة الانتشار تحت علاقات تكافؤ كافية، تلغي الطريقة التباين غير المرغوب فيه المرتبط بتفاصيل التاريخ غير الضرورية (مثل ترتيب التوليد في توصية القوائم).

تحديدًا لتوصية القوائم، يؤكد البحث أن Forward-DP توفر اللبنة الأساسية المفقودة لـ OPE للمسجلات التتابعية المعتمدة على السياق. بخلاف الطرق السابقة التي تعتمد على افتراضات الدرجات الثابتة (حيث لا تتغير درجات العناصر مع القائمة الجزئية) أو تقريبات مونت كارلو، تتعامل Forward-DP مع الحالة التي يعتمد فيها Softmax العنصر التالي على القائمة الجزئية، حيث تحسب الاحتمال المشترك الدقيق دون الحاجة لتعداد عاملي. وهذا يتيح التقييم والاختيار الدقيق للنماذج القائمة على الاحتمالات لموصيات المحولات (Transformers) الحديثة.

أشار المؤلفون إلى القيود، بما في ذلك اشتراط فرضية "كفاية المجموعة" (والتي قد تتطلب توحيد المجموعة المختارة عند النشر) والنمو الأسي مع حجم القائمة $K$ ، لكنهم جادلوا بأن هذا عملي لأحجام القوائم النموذجية ( $K \le 10$ ) حيث يكون $K!$ مستعصيًا.