أشجار القرار والتجميعات

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

ويتبيّن أن هذا الضعف الأخير قابل للإصلاح على نحوٍ يجعل الأشجار عمودَ بعض أقوى الطرق العامة المتاحة.

أ. كيف تتنبّأ الشجرة

تطرح الشجرة سلسلة أسئلة نعم/لا عن المتنبّئات. تختبر كل عقدة داخلية متنبّئاً واحداً مقابل عتبة واحدة؛ وتحمل كل ورقة تنبّؤاً - متوسط استجابات التدريب في تلك المنطقة في الانحدار، والفئة الأكثر تكراراً في التصنيف.

والتنبّؤ يعني السير من الجذر إلى ورقة. لا يُحسب شيء؛ بل تتّبع الفروع فحسب. ولهذا تُقدَّم الأشجار بوصفها قابلة للتفسير: فالمسار هو التفسير.

ب. إنماء الشجرة

إيجاد التقسيم الأمثل غير ممكن حسابياً، ولذلك تُنمّى الأشجار بإجراء جشِع يُسمّى القسمة الثنائية العَودية.

في كل خطوة، انظر في كل متنبّئ $X_j$ وكل نقطة قطع ممكنة $s$، بحيث تُقسَم المنطقة الحالية إلى $\{X_j < s\}$ و$\{X_j \ge s\}$. اختر الزوج $(j, s)$ الذي يحسّن المعيار أكثر من غيره، نفّذ القسمة، ثم كرّر مستقلاً داخل كل منطقة جديدة.

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

وفي الانحدار يكون المعيار RSS مجموعةً على المنطقتين الابنتين:

$$\sum_{i \in R_1}(y_i - \hat y_{R_1})^2 + \sum_{i \in R_2}(y_i - \hat y_{R_2})^2 .$$

ج. معايير القسمة في التصنيف

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

البديلان المعياريان، لمنطقة نِسَب فئاتها $\hat p_{mk}$:

$$G = \sum_{k=1}^{K}\hat p_{mk}\big(1 - \hat p_{mk}\big) \qquad\text{(Gini index)},$$ $$D = -\sum_{k=1}^{K}\hat p_{mk}\log \hat p_{mk} \qquad\text{(cross-entropy)} .$$

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

يستعمل الشكل عشرين مشاهدة، عشراً من كل فئة، وهي عيّنة غير عيّنة النقاط العشر المحسوبة أدناه. اسحب عتبة القطع: يبقى معدّل الخطأ في التصنيف عند 0.2000 على العتبات الخمس الوسطى، بينما يتحرّك مؤشّر جيني.

د. حساب قسمة واحدة يدوياً

عشر مشاهدات، خمس في كل فئة. ترسل قسمة مرشّحة 6 مشاهدات إلى اليسار (4 من الفئة 1 و2 من الفئة 0) و4 إلى اليمين (1 من الفئة 1 و3 من الفئة 0).

ولفئتين، $G = 2p(1-p)$ حيث $p$ نسبة الفئة 1.

العقدة الأم. $p = 5/10 = 0.5$، ومن ثم

$$G_{\text{parent}} = 2(0.5)(0.5) = 0.5 ,$$

وهو الأقصى الممكن لفئتين - عقدة مختلطة تماماً.

الابن الأيسر. $p = 4/6 = 0.6667$:

$$G_L = 2\left(\tfrac{4}{6}\right)\left(\tfrac{2}{6}\right) = 2 \times \tfrac{8}{36} = 0.4444 .$$

الابن الأيمن. $p = 1/4 = 0.25$:

$$G_R = 2(0.25)(0.75) = 0.375 .$$

مرجّحين بحجم المنطقة، لأن قيمة القسمة تتوقّف على عدد المشاهدات التي تمسّها:

$$G_{\text{split}} = \frac{6}{10}(0.4444) + \frac{4}{10}(0.375) = 0.2667 + 0.15 = 0.4167 .$$

التحسّن:

$$\Delta G = 0.5 - 0.4167 = 0.0833 .$$

وتحسب خوارزمية إنماء الشجرة هذا بالضبط لكل زوج $(j, s)$ وتأخذ أكبر $\Delta G$.

هـ. لماذا الشجرة الواحدة غير موثوقة

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

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

و. التعبئة: إذهاب التباين بالمتوسّط

إن كان لطريقة تباين مرتفع، فخذ متوسط نسخ كثيرة منها. فلـ$B$ ملاءمة مستقلة تباين كلٍّ منها $\sigma^2$، يكون تباين المتوسط $\sigma^2/B$.

ولا نملك سوى مجموعة بيانات واحدة، ولذا تصنع التعبئة (التجميع بالتمهيد الذاتي) مجموعات كثيرة: اسحب $B$ عيّنة تمهيد ذاتي - بسحب $n$ مشاهدة مع الإرجاع - وأنمِ على كلٍّ منها شجرة عميقة غير مشذّبة، ثم خذ متوسط التنبّؤات (أو صوّت بالأغلبية).

والأشجار العميقة هي الصواب هنا تماماً. فلكلٍّ منها تحيّز منخفض وتباين مرتفع، ويهاجم المتوسّط التباينَ تاركاً التحيّز المنخفض سليماً.

وتأتي التعبئة أيضاً بمجموعة تحقّق مجانية. فكل عيّنة تمهيد تُسقط نحو ثلث المشاهدات - إذ إن احتمال إغفال مشاهدة بعينها هو $(1 - 1/n)^n \to e^{-1} \approx 0.368$. والتنبّؤ بكل مشاهدة باستخدام الأشجار التي لم ترَها فقط يعطي تقدير الخطأ خارج الحقيبة، بلا كلفة حسابية إضافية.

ز. الغابات العشوائية: فكّ ارتباط الأشجار

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

وتضيف الغابات العشوائية إعاقة متعمّدة واحدة: عند كل قسمة، لا يُنظَر أصلاً إلا في مجموعة جزئية عشوائية من $m$ متنبّئاً، وعادةً $m \approx \sqrt{p}$ في التصنيف. فلا تستطيع معظم القسمات استخدام المتنبّئ المهيمن إطلاقاً، فتحين نوبة المتنبّئات الأخرى، وتصبح الأشجار مختلفة حقاً، ويغدو المتوسط أنجع بكثير.

وهي فكرة لافتة: تُجعَل كل شجرة على حدة أسوأ عن قصد، فيصير التجميع أفضل بسبب ذلك.

ح. ما الذي تتنازل عنه

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

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

الخلاصات الأساسية

• تقسّم الأشجار فضاء المتنبّئات وتتنبّأ بثابت لكل منطقة، وتُنمّى بـالقسمة الثنائية العَودية الجشِعة.
• يتفوّق جيني والإنتروبيا المتقاطعة على معدّل الخطأ في التصنيف كمعايير قسمة، لأنهما يستجيبان لتغيّرات النقاء التي لا تقلب الأغلبية.
• قسمتنا المحلولة: جيني الأم $0.5$، والابنان $0.4444$ و$0.375$، والمرجّح $0.4167$، والمكسب $0.0833$.
• الأشجار المفردة منخفضة التحيّز مرتفعة التباين - غير مستقرة أمام تغيّرات صغيرة في البيانات.
• تأخذ التعبئة متوسط أشجار عميقة على عيّنات تمهيد، مع خطأ خارج الحقيبة مجاناً؛ وتقيّد الغابات العشوائية إضافةً إلى ذلك كل قسمة بـ$m \approx \sqrt p$ متنبّئاً لفكّ ارتباط الأشجار.
• يشتري التجميع الدقةَ بقابلية التفسير.

ما التالي

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