نحن نحلل العلاقات السببية لمقاييس فكونتاكتي

مرحباً بالجميع ، اسمي Anver ، أعمل في فريق Core ML VK. تتمثل إحدى مهامنا في إنشاء وتحسين خوارزميات الترتيب لتغذية الأخبار. في هذه المقالة ، سأوضح لك كيف يمكنك استخدام تحليل السبب والنتيجة للمساعدة في جعل الخدمة أكثر تشويقًا للمستخدمين. دعنا نتحدث عن مزايا هذا النهج على تحليل الارتباط ، وسأقترح تعديلات على الخوارزميات الحالية.

ما هي المقاييس القصيرة والطويلة؟

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



لكن هناك نوع آخر من المقاييس. من المعتقد ، على سبيل المثال ، أن الوقت الذي يقضيه التطبيق ، أو عدد جلسات المستخدم ، يعكس موقفه بشكل أفضل تجاه الخدمة. سوف نسمي هذه المقاييس طويلة .



إن تحسين المقاييس الطويلة مباشرة من خلال خوارزميات الترتيب ليست مهمة تافهة. مع المقاييس القصيرة ، يكون هذا أسهل بكثير: نسبة النقر إلى الظهور ، على سبيل المثال ، مرتبطة بشكل مباشر بمدى تقديرنا لاحتمالية ظهورها. ولكن إذا عرفنا العلاقات السببية (أو السببية) بين المقاييس القصيرة والطويلة ، فيمكننا التركيز على تحسين المقاييس القصيرة فقط التي يجب أن تؤثر بشكل متوقع على المقاييس الطويلة. حاولت استخلاص مثل هذه الروابط السببية - وكتبت عنها في عملي ، والتي أكملتها كدبلومة في بكالوريوس العلوم (CT) في ITMO. أجرينا البحث في مختبر التعلم الآلي التابع لـ ITMO مع شركة VKontakte.

روابط إلى التعليمات البرمجية ومجموعة البيانات وصندوق الحماية

يمكنك العثور على جميع الكود هنا: AnverK .



لتحليل العلاقات بين المقاييس ، استخدمنا مجموعة بيانات تتضمن نتائج أكثر من 6000 اختبار أ / ب حقيقي أجراها فريق VK في أوقات مختلفة. مجموعة البيانات متاحة أيضًا في المستودع .



في وضع الحماية ، يمكنك معرفة كيفية استخدام الغلاف المقترح: على البيانات التركيبية .

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

التعامل مع الارتباطات الخاطئة

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





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



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

الخوارزميات الكلاسيكية لروابط الاستدلال

لقد درسنا عدة طرق للاستدلال السببي: PC (Peter and Clark) و FCI (الاستدلال السببي السريع) و FCI + (على غرار FCI من وجهة نظر نظرية ، ولكنه أسرع بكثير). يمكنك أن تقرأ عنها بالتفصيل في هذه المصادر:

• السببية (جي بيرل ، 2009) ،
• السببية والتنبؤ والبحث (P. Spirtes et al. ، 2000) ،
• تعلم النماذج السببية المتفرقة ليست صعبة NP (T. Claassen et al. ، 2013).

لكن من المهم أن نفهم أن الطريقة الأولى (PC) تفترض أننا نلاحظ جميع الكميات التي تؤثر على مقياسين أو أكثر - تسمى هذه الفرضية بالاكتفاء السببي. تأخذ الخوارزميتان الأخريان في الاعتبار أنه قد تكون هناك عوامل غير ملحوظة تؤثر على المقاييس المراقبة. أي ، في الحالة الثانية ، يعتبر التمثيل السببي أكثر طبيعية ويسمح بوجود عوامل غير ملحوظة$$$U_1, \dots U_k$:







يتم توفير جميع تطبيقات هذه الخوارزميات في مكتبة pcalg . إنه جميل ومرن ، ولكن مع "عيب" واحد - فهو مكتوب بلغة R (عند تطوير الوظائف الأكثر ثقلًا من الناحية الحسابية ، يتم استخدام حزمة RCPP). لذلك ، بالنسبة للطرق المذكورة أعلاه ، كتبت أغلفة في فئة CausalGraphBuilder ، مضيفة أمثلة على استخدامها.



سأصف عقود وظيفة استدلال الروابط ، أي الواجهة والنتيجة التي يمكن الحصول عليها من المخرجات. يمكنك اجتياز وظيفة اختبار للاستقلال الشرطي. هذا اختبار مثل هذا يعود$$$p_{value}$ تحت فرضية العدم أن الكميات $$$X$ و $$$Y$ مستقل بشكل مشروط عن مجموعة الكميات المعروفة $$$Z$... الافتراضي هو اختبار الارتباط الجزئي . اخترت الوظيفة بهذا الاختبار لأنها الوظيفة الافتراضية في pcalg ويتم تنفيذها في RCPP - وهذا يجعلها سريعة في الممارسة العملية. يمكنك أيضا نقل$$$p_{value}$، بدءًا من الرؤوس التي سيتم اعتبارها تابعة. بالنسبة لخوارزميات الكمبيوتر الشخصي و FCI ، يمكنك أيضًا تعيين عدد أنوية وحدة المعالجة المركزية ، إذا لم تكن بحاجة إلى كتابة سجل لعمليات المكتبة. لا يوجد مثل هذا الخيار لـ FCI + ، لكنني أوصي باستخدام هذه الخوارزمية المعينة - فهي تربح في السرعة. تحذير آخر: لا يدعم FCI + حاليًا خوارزمية توجيه الحافة المقترحة - النقطة موجودة في قيود مكتبة pcalg.



بناءً على نتائج عمل جميع الخوارزميات ، تم إنشاء PAG (الرسم البياني الجزئي للأسلاف) في شكل قائمة من الحواف. باستخدام خوارزمية الكمبيوتر الشخصي ، يجب تفسيره على أنه رسم بياني سببي بالمعنى الكلاسيكي (أو شبكة بايزي): حافة موجهة من$$$A$ في $$$B$، يعني التأثير $$$A$ على $$$B$... إذا كانت الحافة غير موجهة أو ثنائية الاتجاه ، فلا يمكننا توجيهها بشكل فريد ، مما يعني:

• أو البيانات المتاحة غير كافية لتحديد الاتجاه ،
• أو أنه مستحيل ، لأن الرسم البياني السببي الحقيقي ، باستخدام البيانات القابلة للملاحظة فقط ، يمكن إنشاؤه فقط حتى فئة التكافؤ.

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

تعديل خوارزمية اتجاه الحافة

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



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

قارن النماذج - 1: تقدير احتمالية رسم بياني

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



الأول هو تقدير احتمالية الرسم البياني:







هنا$$$PA_G(X)$ - العديد من الآباء في قمة الرأس $$$X$و $$$I(X, Y)$ - معلومات مشتركة عن الكميات $$$X$ و $$$Y$و و $$$H(X)$ هي إنتروبيا الكمية $$$X$... في الواقع ، لا يعتمد المصطلح الثاني على هيكل الرسم البياني ، لذلك ، كقاعدة عامة ، يتم اعتبار المصطلح الأول فقط. لكن يمكنك أن ترى أن الاحتمالية لا تقل مع إضافة حواف جديدة - يجب أن يؤخذ ذلك في الاعتبار عند المقارنة.



من المهم أن نفهم أن مثل هذا التقييم يعمل فقط لمقارنة شبكات Bayesian (ناتج خوارزمية الكمبيوتر الشخصي) ، لأنه في PAGs الحقيقية (إخراج خوارزميات FCI و FCI +) ، تحتوي الحواف المزدوجة على دلالات مختلفة تمامًا.



لذلك ، قارنت اتجاه الحواف مع الخوارزمية الخاصة بي والكمبيوتر الكلاسيكي: أتاح







الاتجاه المعدل للحواف زيادة كبيرة في الاحتمالية مقارنة بالخوارزمية الكلاسيكية. لكن من المهم الآن مقارنة عدد الحواف:







هناك عدد أقل منهم - وهذا متوقع. لذلك ، حتى مع وجود عدد أقل من الحواف ، من الممكن استعادة هيكل رسم بياني أكثر منطقية! هنا قد تجادل بأن الاحتمالية لا تقل مع عدد الحواف. النقطة المهمة هي أن الرسم البياني الناتج في الحالة العامة ليس رسم بياني فرعي للرسم البياني الذي تم الحصول عليه بواسطة خوارزمية الكمبيوتر الشخصي الكلاسيكية. قد تظهر الحواف المزدوجة بدلاً من الحواف المفردة ، وقد تغير الحواف المفردة اتجاهها. لذلك لا الحرف اليدوية!

مقارنة النماذج - 2: استخدام نهج التصنيف

دعنا ننتقل إلى الطريقة الثانية للمقارنة. سنستخدم خوارزمية الكمبيوتر الشخصي لإنشاء رسم بياني سببي واختيار رسم بياني دوري عشوائي منه. بعد ذلك ، سننشئ البيانات عند كل رأس كمجموعة خطية من القيم عند الرؤوس الأصلية مع المعاملات$$$\pm[0,2, 0,8]$مع إضافة الضوضاء الغوسية. أخذت فكرة هذا الجيل من مقالة "نحو اكتشاف سببي قوي ومتعدد الاستخدامات لتطبيقات الأعمال" (Borboudakis et al. ، 2016). تم إنشاء القمم التي ليس لها أبوين من التوزيع الطبيعي - باستخدام معلمات كما في مجموعة البيانات الخاصة بالرأس المقابل.



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



لأخذ التوجيهات في الاعتبار ، نقدم$$$TP_{misorient}$للحواف التي يتم عرضها بشكل صحيح ، ولكن بالاتجاه الخاطئ. بعد ذلك ، سننظر في الأمر على النحو التالي:

• $$$TP' = TP - TP_{misorient}$
• $$$FP' = FP + TP_{misorient}$

ثم يمكنك القراءة $$$F_1$- الحجم لكل من الهيكل العظمي ومراعاة الاتجاه (من الواضح أنه في هذه الحالة لن يكون أعلى من الهيكل العظمي). ومع ذلك ، في حالة خوارزمية الكمبيوتر الشخصي ، تضيف الحافة المزدوجة إلى$$$TP_{misorient}$ فقط $$$0.5$، لكن لا $$$1$، لأنه لا يزال يتم استنتاج أحد الجوانب الحقيقية (بدون الاكتفاء السببي ، سيكون هذا خطأ).



أخيرًا ، دعنا نقارن الخوارزميات:







الرسمان البيانيان الأولان عبارة عن مقارنة بين الهياكل العظمية لخوارزمية الكمبيوتر الشخصي: الخوارزمية الكلاسيكية وتوجيه الحافة الجديد. هناك حاجة إليها لإظهار الحد العلوي$$$F_1$-تدابير. يقوم الاثنان الآخران بمقارنة هذه الخوارزميات فيما يتعلق بالتوجيه. كما ترى ، لا يوجد ربح.

قارن النماذج - 3: قم بإيقاف تشغيل الكفاية السببية

الآن دعونا "نغلق" بعض المتغيرات في الرسم البياني الحقيقي وفي البيانات التركيبية بعد التوليد. سيؤدي هذا إلى إيقاف الاكتفاء السببي. لكن سيكون من الضروري مقارنة النتائج ليس بالرسم البياني الحقيقي ، ولكن مع النتيجة التي تم الحصول عليها على النحو التالي:

• سيتم رسم حواف والدي الرأس المخفي لأطفالها ،
• قم بتوصيل جميع أطفال الرأس المخفي بحافة مزدوجة.

سنقارن بالفعل خوارزميات FCI + (مع اتجاه الحافة المعدل ومع الخوارزمية الكلاسيكية):







والآن ، عندما لا يتم تحقيق الكفاية السببية ، تصبح نتيجة التوجه الجديد أفضل بكثير.



ظهرت ملاحظة مهمة أخرى - تقوم خوارزميات الكمبيوتر الشخصي و FCI ببناء هياكل عظمية متطابقة تقريبًا في الممارسة العملية. لذلك ، قارنت ناتجهم مع اتجاه الحواف التي اقترحتها في عملي.







اتضح أن الخوارزميات عمليا لا تختلف في الجودة. في هذه الحالة ، يعد الكمبيوتر الشخصي خطوة في خوارزمية بناء الهيكل العظمي داخل FCI. وبالتالي ، فإن استخدام خوارزمية توجيه الكمبيوتر ، كما هو الحال في خوارزمية FCI ، يعد حلاً جيدًا لزيادة سرعة استدلال الارتباط.

انتاج |

سوف ألخص بإيجاز ما تحدثنا عنه في هذا المقال:

1. كيف يمكن أن تنشأ مهمة اشتقاق الروابط السببية في شركة تكنولوجيا معلومات كبيرة.
2. ما هي الارتباطات الزائفة وكيف يمكن أن تتداخل مع اختيار الميزة.
3. ما هي خوارزميات روابط الاستدلال الموجودة والمستخدمة في أغلب الأحيان
4. ما الصعوبات التي يمكن أن تنشأ عند اشتقاق الرسوم البيانية السببية؟
5. ما هي مقارنة الرسوم البيانية السببية وكيفية التعامل معها.

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