شجرة مرحلية (رياضيات)

الشجرة المرحلية هي نموذج احتمالي لعملية تتكون من سلسلة من الأحداث ذات القيم المنفصلة، ​​موصوفة بمخطط شجري (يُعرف أيضًا بشجرة الأحداث أو شجرة الاحتمالات). تُحدد الشجرة المرحلية علاقات التساوي على توزيعات الاحتمالات الشرطية لشجرة الأحداث. تُمثل هذه العلاقات بصريًا بلون الرؤوس لتشكيل نموذج بياني . كما أن للشجرة المرحلية تمثيلًا بصريًا أكثر إيجازًا يُسمى مخطط سلسلة الأحداث . ^{[ 1 ] [ 2 ]}

طُوِّرت الأشجار المرحلية ومخططات الأحداث المتسلسلة في الأصل كأداة لاستخلاص آراء الخبراء . غالبًا ما يفهم الناس الأمور من خلال القصص، ويشرح الخبراء عادةً مجالهم عبر تسلسلات الأحداث وآثارها المتتالية. ^{[ 3 ]} توفر الشجرة المرحلية ومخطط الأحداث المتسلسلة تمثيلًا مرئيًا لهذه التسلسلات من الأحداث، وتربطها بفئة من التوزيعات الاحتمالية لإنشاء نموذج احتمالي رسمي. عند توفر بيانات كافية، يمكن استخدام الأشجار المرحلية كأداة للتعلم الآلي للعثور على القصة التي تصف البيانات على أفضل وجه. وبهذه الطريقة، يمكن اكتشاف تفسيرات جديدة لتطور العملية. كما استُخدمت أيضًا في التحليل السببي ، ^{[ 4 ] [ 5 ] [ 6 ] [ 7 ]} ووُسِّعت لتشمل النماذج الديناميكية التي تتطور بمرور الوقت ^{، [ 8 ]} ولنمذجة البيانات المفقودة المُستنيرة . ^{[ 9 ]}

يبدأ بناء شجرة المراحل برسم شجرة الأحداث التي تصف جميع التطورات الممكنة للعملية. شجرة الأحداث هي عبارة عن شجرة متفرعة - رسم بياني لشجرة موجهة ذات جذر، حيث تتجه جميع الحواف بعيدًا عن رأس الجذر. يمثل الجذر بداية العملية، بينما تمثل أوراق الشجرة جميع نقاط النهاية الممكنة لها. تُسمى جميع الرؤوس غير الورقية، بما في ذلك الجذر، حالات ، وتمثل نقاطًا وسيطة في تطور العملية. تُسمى حواف الشجرة بمعرف الحدث الذي تُقابله. ^{[ 10 ]}

ترتبط كل حالة وحوافها الخارجة بتوزيع احتمالي، يُسمى احتمالات الانتقال ، والتي تصف احتمالات الحدث التالي بافتراض وصول العملية إلى تلك الحالة. تكفي احتمالات الانتقال لتحديد التوزيع الاحتمالي الكامل للعملية بشكل فريد. ^{[ 10 ]}

تُسمى شجرة الأحداث متوافقة مع x إذا أمكن ربطها بتسلسل من المتغيرات العشوائية المنفصلة (متغير واحد لكل طبقة من الشجرة) وكانت جميع التوليفات الممكنة لهذه المتغيرات ذات احتمالية غير صفرية. أما الأشجار غير المتوافقة مع x فتسمح بوجود أصفار هيكلية - عندما تحدث توليفات معينة من المتغيرات باحتمالية صفرية - أو بأن تعتمد القيم المحتملة للأحداث المستقبلية على الأحداث الماضية. ^{[ 11 ]}

مثال

لنفترض سيناريو مبسطًا لتجربة عشوائية مضبوطة لعلاج طبي جديد. يُشخَّص المرضى بأعراض خفيفة أو شديدة، ثم يُوزَّعون عشوائيًا إما على العلاج الجديد أو العلاج القياسي. تُحدَّد آثار العلاج، سواء كانت إيجابية أم سلبية. يمكن تمثيل هذه العملية بشجرة الأحداث المتوافقة مع x المعروضة على اليمين.

الشجرة المرحلية هي نموذج احتمالي يُقيّد نطاق التوزيعات الاحتمالية في شجرة الأحداث بتحديد علاقات التساوي بين احتمالات الانتقال بين المواقف المختلفة. تحديدًا، إذا كان موقفان في المرحلة نفسها ، فإنهما يشتركان في توزيع احتمالي انتقالي مشترك. ^{[ 1 ]} بعبارة أخرى، تُصنّف المواقف في مراحل وفقًا لاحتمالات انتقالها.

بشكل عام، يمكن لأي حالتين لهما نفس عدد الحواف الخارجة أن تكونا في نفس المرحلة. مع ذلك، غالبًا ما يكون تعريف المرحلة مقيدًا بحيث لا يمكن أن تكون في نفس المرحلة إلا الحالات التي لها نفس تسميات الحواف الخارجة، مع تساوي احتمالات الانتقال مع تسميات الحواف. تُسمى الشجرة المرحلية بالشجرة الطبقية إذا كانت الحالات الموجودة في نفس طبقة الشجرة فقط هي التي يمكن أن تكون في نفس المرحلة. ^{[ 11 ]}

تُوصَف مجموعة جميع المراحل في شجرة مُرَتَّبة بتقسيم لحالات الشجرة يُسمى "الترَتُّب" . يُعرَّف نموذج الشجرة المُرَتَّبة تعريفًا كاملًا بواسطة شجرة الأحداث والترَتُّب، ويُمثَّل بيانيًا بتلوين رؤوس شجرة الأحداث وفقًا لانتمائها إلى المرحلة. أي، تُخصَّص لكل مرحلة لون، وتُعطى جميع الحالات في المرحلة هذا اللون في الشجرة. عادةً ما تبقى المراحل الفردية - أي المراحل التي تحتوي على حالة واحدة فقط - بدون لون. ^{[ 10 ]}

مثال

بالعودة إلى المثال السابق، لنفترض أننا نفترض ما يلي:

1. تم إجراء التجربة بشكل عشوائي صحيح بحيث لا يعتمد احتمال حصول المريض على العلاج الجديد على أعراضه.
2. يتمتع العلاج الجديد والعلاج القياسي بنفس الفعالية بالنسبة لأولئك الذين يعانون من أعراض خفيفة.

يُمثل هذان الافتراضان في الشجرة المرحلية الموضحة على اليمين. وينعكس الافتراض الأول في الحالات${\displaystyle s_{1}}$و${\displaystyle s_{2}}$كلاهما ملون باللون الأحمر، بينما ينعكس الافتراض الثاني في المواقف${\displaystyle s_{3}}$و${\displaystyle s_{4}}$كلاهما ملون باللون الأخضر. المواقف${\displaystyle s_{5}}$و${\displaystyle s_{6}}$كلاهما غير ملونين، مما يعكس عدم وجود أي افتراضات حول توزيعات احتمالاتهما.

يُعدّ مخطط أحداث السلسلة تمثيلاً مرئياً أكثر إيجازاً لنموذج الشجرة المرحلية. تكون حالتان في نفس الموضع إذا كانتا في نفس المرحلة، وكان تطور العملية في المستقبل متطابقاً احتمالياً من كلتا الحالتين. بعبارة أخرى، تكون الأشجار الفرعية التي تبدأ من الحالتين متطابقة من حيث البنية والانتماء للمرحلة/اللون. يُنشأ مخطط أحداث السلسلة بدمج جميع الرؤوس الموجودة في نفس الموضع، بالإضافة إلى دمج جميع رؤوس الأوراق في رأس واحد نهائي . ^{[ 1 ] [ 10 ]}

مثال

بالعودة إلى المثال السابق، المواقف${\displaystyle s_{3}}$و${\displaystyle s_{4}}$تقع هذه الحالات في نفس الموضع، وبالتالي يمكن دمجها في مخطط أحداث السلسلة.${\displaystyle s_{1}}$و${\displaystyle s_{2}}$تقع هذه الرؤوس في نفس المرحلة، لكنها ليست في نفس الموضع لأن الأشجار الفرعية التي تبدأ من هذه الرؤوس لها ألوان مختلفة. لذا، لا يتم دمجها في مخطط أحداث السلسلة. يظهر مخطط أحداث السلسلة اللاحق على اليمين.

عند تقدير احتمالات الانتقال في شجرة الأحداث، لا يمكن استخدام سوى العينات التي تصل إلى الحالة ذات الصلة. مع ذلك، تتمتع الأشجار المرحلية بميزة طفيفة، إذ يمكن مشاركة العينات بين جميع الحالات في المرحلة نفسها، لأنها تُستخدم جميعها لتقدير التوزيع الاحتمالي نفسه. طالما أن افتراض التدرج المرحلي صحيح، ينتج عن ذلك أحجام عينات أكبر، وبالتالي تحسين تقدير احتمالات الانتقال. ^{[ 12 ]}

عندما لا تكون شجرة المراحل معروفة مسبقًا، يمكن تعلمها من البيانات. أي يتم اختيار نموذج شجرة المراحل الذي يمثل البيانات على أفضل وجه. وبهذه الطريقة، يمكن اكتشاف التساوي في احتمالات الانتقال. ^{[ 13 ]}

يتم اختيار النموذج عادةً من خلال دمج دالة تقييم مع خوارزمية بحث عن النموذج . تبحث خوارزمية البحث عن النموذج في مجموعة النماذج الممكنة للعثور على النموذج ذي أعلى درجة. من الخيارات الشائعة لدالة التقييم احتمالية النموذج اللاحقة ^{[ 14 ]} ومعيار المعلومات البايزي ، بينما تشمل خيارات خوارزمية البحث عن النموذج التجميع الهرمي التراكمي ^{[ 14 ]} وتسلق التل .

في كثير من الأحيان، عند اختيار نموذج الأشجار المرحلية، يُفترض أن شجرة الأحداث الأساسية ثابتة بناءً على معلومات خاصة بالمجال (مثل الترتيب الزمني أو السببي للمتغيرات). ويُعدّ عدم ثبات شجرة الأحداث وإدراجها في عملية اختيار النموذج امتدادًا لهذا الافتراض. يمكن أن تصف العديد من أشجار الأحداث المختلفة نفس مجموعة البيانات (على سبيل المثال، تغيير ترتيب المتغيرات في الأشجار المتوافقة)، ولكن كل شجرة تُنتج احتمالات انتقال مختلفة، وبالتالي فئات مختلفة من نماذج الأشجار المرحلية. ^{[ 15 ]} وللبحث في فضاء أشجار الأحداث الممكنة، يتوفر أسلوب البرمجة الديناميكية. ^{[ 16 ]}

تُعدّ الشبكات البايزية فئة من النماذج البيانية القادرة على ترميز علاقات الاستقلال الشرطي بين مجموعات الرؤوس. وبالمثل، يمكن استخدام مراحل الشجرة المُرَتّبة لترميز الاستقلال الشرطي. ^{[ 17 ]} في الواقع، يمكن اعتبار الأشجار المُرَتّبة المُتوافقة مع x امتدادًا للشبكات البايزية المنفصلة - إذ يمكن تمثيل كل شبكة بايزية منفصلة بشجرة مُرَتّبة مُتوافقة مع x. ^{[ 1 ]} مع ذلك، تستطيع الأشجار المُرَتّبة أيضًا تحديد استقلال شرطي خاص بالسياق لا يمكن تمثيله بواسطة شبكة بايزية قياسية. وبهذه الطريقة، تكون فئة نماذج الأشجار المُرَتّبة أوسع من فئة الشبكة البايزية القياسية. بالإضافة إلى ذلك، يمكن استخدام الأشجار المُرَتّبة غير المُتوافقة مع x للعمليات التي لا يمكن نمذجتها بواسطة الشبكات البايزية القياسية.

يتوفر برنامج لاختيار النموذج وتقدير الاحتمالية باستخدام الأشجار المرحلية في لغة R مع حزمة stagedtrees ^{[ 11 ]} وفي لغة Python مع حزمة cegpy. ^{[ 18 ]}

لقد طُبقت الأشجار المرحلية بنجاح في عدد من المجالات، بما في ذلك الطب وعلم الأوبئة، ^{[ 19 ] [ 20 ] [ 21 ]} والتحقيقات الجنائية، ^{[ 22 ] [ 23 ]} ومسارات الهجرة، ^{[ 24 ]} والنقل، ^{[ 25 ]} والقانون. ^{[ 26 ] [ 27 ] [ 28 ]}

من أبرز قيود نماذج الأشجار المرحلية محدودية أنواع البيانات التي يمكن استخدامها معها. تحديدًا، يجب أن تكون البيانات قابلة للتمثيل بشجرة أحداث، وهو ما لا يمكن تحقيقه إلا في فضاءات العينات المحدودة. عندما لا يكون لفضاء عينات البيانات حدٌّ أقصى ، كما في حالة احتواء البيانات على متغير مستمر، لا يمكن تمثيلها بشجرة أحداث، وبالتالي لا يمكن تطبيق نماذج الأشجار المرحلية مباشرةً. يتمثل الحل البسيط لهذه المشكلة في تقسيم أي متغيرات ذات فضاء عينات غير محدود إلى متغيرات منفصلة. ^{[ 2 ]}

من القيود الأخرى المشابهة لنماذج الأشجار المرحلية، كبر حجم فضاء العينة المحدود. قد يحدث هذا لأن الشجرة تحتوي على طبقات عديدة (سلاسل طويلة من الأحداث) أو عندما تحتوي المواقف على العديد من الحواف الخارجة (العديد من الأحداث المحتملة). على سبيل المثال، شجرة أحداث من${\displaystyle N}$المتغيرات الثنائية لها${\displaystyle 2^{N}}$المسارات من الجذر إلى الأوراق. يصبح التمثيل المرئي للشجرة المرحلية أكثر صعوبة في الفهم كلما ازداد حجمها، وبالتالي قد تُفقد إحدى أهم مزايا الأشجار المرحلية، وهي سهولة التفسير والتصور. تُحسّن مخططات أحداث السلسلة من هذا الأمر من خلال توفير تمثيل مرئي أكثر إيجازًا، ولكنها مع ذلك تُعاني في النهاية من المشكلة نفسها مع ازدياد حجم الشجرة. ^{[ 2 ]}

تبرز هذه المشكلة بشكل أكبر في اختيار النموذج. بالنسبة لشجرة أحداث من${\displaystyle N}$بالنسبة للمتغيرات الثنائية، فإن عدد نماذج الأشجار الطبقية المرحلية الممكنة هو${\textstyle \prod _{i=1}^{N}B(2^{N-1})}$^{[ 16 ]} حيث${\displaystyle B(m)}$هو${\displaystyle m}$رقم بيل . هذا يعني أن البحث الشامل عن النموذج غير ممكن حتى بالنسبة للأشجار متوسطة الحجم، مما يستلزم استخدام خوارزميات البحث عن النموذج. ^{[ 29 ]} علاوة على ذلك، قد تكون طرق اختيار النموذج غير مستقرة عندما يكون حجم العينة صغيرًا مقارنةً بحجم الشجرة.