أساسيات تعلم الآلة2016متوسط12 دقيقة قراءة

XGBoost: نظام قابل للتوسُّع لتعزيز الأشجار التدرُّجي

XGBoost: A Scalable Tree Boosting System

Chen, T. · Guestrin, C. — KDD

المشكلة

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

الإسهام

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

الأثر

أصبح XGBoost الخوارزمية المهيمنة على Kaggle وفي التطبيقات الصناعية . في عام 2015 وحده، استُخدم في 17 من أصل 29 حلاً فائزاً على Kaggle. ولا يزال نقطة البداية المعتادة لمهام البيانات المهيكلة — من التقييم الائتماني إلى التشخيص الطبي إلى التنبؤ بالنقرات الإعلانية. ألهم تصميمه LightGBM وCatBoost، وتمتد منظومته مفتوحة المصدر لتشمل Python وR وJulia وJava وSpark.

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

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

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

من شجرة ضعيفة واحدة إلى نموذج تجميعي قوي

شجرة القرار المنفردة سهلة التفسير لكنها هشّة: تقطّع فضاء السمات بحدود مستقيمة وتُخرج تنبؤاً ثابتاً في كل منطقة ناتجة (). إذا زدتَ عمقها حفظت الضوضاء؛ وإذا أبقيتها ضحلة فاتتها أنماط مهمة. هناك استراتيجيتان للتجميع تعالجان هذه المشكلة من زاويتين مختلفتين:

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

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

افتح في المختبر

بدّل بين التكييس والتعزيز لترى كيف يبني كلٌّ منهما نموذجه التجميعي. لاحظ كيف تركّز أشجار التعزيز تدريجياً على المناطق الأصعب.

تستيقظ التجربة عند وصولك…

دالة الهدف المنظَّمة: التحكّم في كل شجرة

ما يميّز XGBoost عن تطبيقات التعزيز التدرُّجي السابقة هو دالة الهدف المنظَّمة. أغلب تطبيقات التعزيز تكتفي بتقليل خسارة التنبؤ فحسب، لكن XGBoost يضيف عقوبة صريحة على تعقيد كل شجرة — تخيّلها كميزانية محدودة يجب على كل شجرة أن تنفقها بحكمة. عند إضافة الشجرة رقم $t$ ، تأخذ دالة الهدف الكاملة الشكل التالي:

\mathcal{L}^{(t)} = \sum_{i=1}^{n} l(y_i,\;\hat{y}_i^{(t-1)} + f_t(x_i)) \;+\; \Omega(f_t) \quad\text{where}\quad \Omega(f) = \gamma\,T + \tfrac{1}{2}\lambda \sum_{j=1}^{T} w_j^2

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

يعتمد XGBoost على تقريب تايلور من الدرجة الثانية لـدالة الخسارة حول التنبؤ الحالي. النتيجة تقريب تربيعي لا يحتاج سوى إحصائيتين لكل عيّنة : التدرُّج $g_i$ (المشتقة الأولى للخسارة) و**** $h_i$ (المشتقة الثانية). هذان الرقمان يلخّصان كل ما يحتاجه بانِي الشجرة من دالة الخسارة — وبالتالي يعمل XGBoost مع أي دالة خسارة قابلة للاشتقاق دون تغيير في البنية.

حين نجمّع العيّنات بحسب الورقة $j$ التي تقع فيها (لنسمِّ المجموعة $I_j$ )، نحصل مباشرةً على الوزن الأمثل لكل ورقة وعلى القيمة المثلى لدالة الهدف:

w_j^* = -\frac{\sum_{i \in I_j} g_i}{\sum_{i \in I_j} h_i + \lambda} \qquad \mathcal{L}^* = -\frac{1}{2}\sum_{j=1}^{T} \frac{\left(\sum_{i \in I_j} g_i\right)^2}{\sum_{i \in I_j} h_i + \lambda} + \gamma\,T

وزن الورقة الأمثل ودرجة البنية — بمجرد تحديد بنية الشجرة، يستطيع XGBoost حساب قيمة التنبؤ المثلى لكل ورقة بصيغة مغلقة مباشرة دون الحاجة لتحسين تكراري. كما يمنح كل بنية درجةً تعكس التوازن بين تحسين التنبؤ وتعقيد النموذج: البنى الأفضل تحقّق خفضاً أكبر في الخسارة، بينما تُعاقَب البنى المفرطة التعقيد. هذا يتيح لـ XGBoost المقارنة بين التقسيمات المرشّحة بكفاءة وبناء الأشجار بطريقة منهجية.

افتح في المختبر

عدّل قيمتَي γ وλ لترى كيف يؤثّر التنظيم على بنية الشجرة وأوزان أوراقها. كلّما زادت القيم، أصبحت الأشجار أبسط.

تستيقظ التجربة عند وصولك…

الانكماش والاختيار العشوائي للأعمدة: خطّا دفاع إضافيان

إلى جانب عقوبة $\Omega$ ، يستخدم XGBoost أسلوبين إضافيين مأخوذين من ممارسات راسخة:

الانكماش (أي η) يضرب إسهام كل شجرة جديدة بعامل بين 0 و1 قبل ضمّها إلى النموذج التجميعي. قيمة مثل η = 0.1 تعني أن كل شجرة لا تُسهم إلا بـ 10% من تنبّئها الكامل. الفكرة كأنّ المدرّب يقول «أثق في تصحيحك، لكن لنتمهّل» — هذا يترك مجالاً للأشجار اللاحقة ويحدّ كثيراً من ، لكنّه يتطلب عدداً أكبر من الأشجار.

يختار مجموعة فرعية عشوائية من عند بناء كل شجرة أو كل تقسيم. الفكرة مأخوذة من الغابة العشوائية وتحقّق هدفين: تقليل الارتباط بين الأشجار (فيقلّ التباين) وتسريع الحساب بتخطّي السمات غير المفيدة.

إيجاد أفضل تقسيم: الطريقة الدقيقة والتقريبية

جوهر أي بانٍ للأشجار هو خوارزمية إيجاد التقسيم: إذا كانت لدينا عقدة تضمّ مجموعة من العيّنات، فأيّ سمة وأيّ عتبة يُنتجان أفضل فصل؟ يوفّر XGBoost استراتيجيتين:

الدقيقة تفحص كل نقطة تقسيم ممكنة على كل سمة، وتحسب لكل مرشّح — أي مقدار التحسّن في درجة البنية. هذه الطريقة مثالية لكنها مكلفة حسابياً: تتطلّب فحص $O(n \cdot m)$ مرشّح لأجل $n$ عيّنة و $m$ سمة.

\text{Gain} = \frac{1}{2}\left[ \frac{\left(\sum_{i \in I_L} g_i\right)^2}{\sum_{i \in I_L} h_i + \lambda} + \frac{\left(\sum_{i \in I_R} g_i\right)^2}{\sum_{i \in I_R} h_i + \lambda} - \frac{\left(\sum_{i \in I} g_i\right)^2}{\sum_{i \in I} h_i + \lambda} \right] - \gamma

معادلة كسب التقسيم — تقيس هذه المعادلة جدوى تقسيم عقدة معيّنة. الفكرة هي مقارنة جودة العقدتين الناتجتين بجودة العقدة الأصلية: كلما كان الكسب أكبر دلّ ذلك على تحسّن حقيقي في التنبؤ. في المقابل، تفرض عقوبة التعقيد γ حدّاً أدنى للتحسين المطلوب، فإذا كان الكسب أصغر من هذا الحدّ يُرفض التقسيم ويُحافظ على بساطة الشجرة.

الخوارزمية التقريبية تستبدل البحث الشامل بفكرة أذكى: بدلاً من فحص كل قيمة، تقترح عتبات مرشّحة عند مئينات توزيع كل سمة وتقيّم تلك المرشّحات فقط. يستخدم XGBoost — وهو بنية بيانات متدفّقة تراعي أن بعض العيّنات أهم من غيرها (لأن الهسيان $h_i$ يعمل كوزن). النتيجة: ينخفض عدد المرشّحات من $n$ إلى ثابت صغير $k$ (نحو 33 مئيناً عادةً)، فتصبح الخوارزمية $O(k \cdot m)$ لكل عقدة — وهو تسريع كبير على البيانات الضخمة.

يمكن للطريقة التقريبية العمل في وضع شامل (اقتراح المرشّحات مرة واحدة قبل بناء الشجرة) أو وضع محلّي (إعادة الاقتراح عند كل تقسيم). الوضع المحلّي أدقّ لكنه أبطأ، وفي الواقع يكفي الوضع الشامل مع عدد كافٍ من المئينات للوصول إلى نتائج مطابقة للطريقة الدقيقة.

افتح في المختبر

قارن بين إيجاد التقسي الدقيق والتقريبي. حرّك شريط المئينات لترى كيف أن عدداً أقلّ من المرشّحات يكفي لإيجاد تقسيم قريب من الأمثل.

تستيقظ التجربة عند وصولك…

التعامل مع البيانات الناقصة: الخوارزمية الواعية بالتناثر

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

عند بناء تقسيم، تجرّب الخوارزمية إرسال جميع العيّنات ذات القيم المفقودة إلى الفرع الأيسر ثم إلى الأيمن، وتختار الاتجاه الذي يحقّق كسباً أعلى. يُحفظ هذا الاتجاه مع العقدة، فعند التنبؤ تتبع أي قيمة مفقودة جديدة المسار الذي كان أفضل تجريبياً أثناء التدريب.

من الناحية الهندسية هناك نقطة جوهرية: الخوارزمية الواعية بـ لا تمرّ إلا على المدخلات غير المفقودة. في البيانات المتناثرة (حيث قد تكون 90%+ من المدخلات أصفاراً أو غائبة)، لا تزور الخوارزمية إلا جزءاً صغيراً من البيانات — ما يجعل إيجاد التقسيم أسرع بخمسين ضعفاً مقارنةً بالطريقة التقليدية.

افتح في المختبر

انقر على الخلايا لإضافة قيم مفقودة أو إزالتها. شاهد كيف يتعلّم XGBoost تلقائياً إلى أيّ فرع يوجّه البيانات الناقصة عند كل تقسيم.

تستيقظ التجربة عند وصولك…

هندسة الأنظمة: الكتل والتخبئة والضغط

الإسهام الثاني للورقة — والذي لا يُقدَّر حقّ قدره غالباً — هو هندسة الأنظمة. لا قيمة لخوارزمية ذكية إن كانت أنماط الوصول إلى الذاكرة بطيئة. يخزّن XGBoost البيانات في بنية كتل مرتّبة عمودياً:

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

لكن هناك تفصيل مهم: القفز من الترتيب المرتّب إلى إحصائيات التدرُّج عبر مؤشّرات الصفوف يُسبّب إخفاقات في ذاكرة التخبئة على البيانات الكبيرة. يعالج XGBoost هذا بـجلب مسبق واعٍ بذاكرة التخبئة: خيط خلفي يحمّل قيم التدرُّج القادمة في ذاكرة المعالج السريعة قبل أن يحتاجها الخيط الرئيسي. على بيانات من 10 ملايين صف، يحقّق هذا الجلب المسبق وحده تسريعاً بمقدار الضعف.

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

افتح في المختبر

استكشف بنية كتل XGBoost. شاهد كيف يمكّن التخزين المرتّب عمودياً من البحث المتوازي عن التقسيمات ومن الجلب المسبق الواعي بذاكرة التخبئة.

تستيقظ التجربة عند وصولك…

مراحل عمل XGBoost الكاملة

لنتراجع خطوة ونرَ كيف تنتظم كل هذه المكوّنات في نظام واحد متماسك. على المستوى الأعلى، يبدأ XGBoost بتنبؤ أوّلي (عادةً المتوسط)، ثم يضيف أشجار قرار واحدة تلو الأخرى. كل شجرة تُبنى كالتالي:

حساب التدرُّج $g_i$ والهسيان $h_i$ لكل عيّنة بناءً على التنبؤ المجمّع الحالي.
إيجاد أفضل التقسيمات بالخوارزمية الدقيقة أو التقريبية، مع معالجة القيم المفقودة عبر الخوارزمية الواعية بالتناثر.
تعيين أوزان الأوراق المثلى بالصيغة المغلقة $w_j^*$ .
ضرب إسهام الشجرة بـمعدّل التعلّم η (الانكماش).
إضافة الشجرة المُقلَّصة إلى .

تتوقف العملية بعد عدد كافٍ من الجولات، أو حين يتوقف مقياس التحقق عن التحسّن (). النموذج النهائي هو مجموع كل الأشجار، والتنبؤ لعيّنة جديدة يعني تمريرها عبر كل شجرة وجمع قيم الأوراق.

افتح في المختبر

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

تستيقظ التجربة عند وصولك…

أهمية السمات: أيّ المدخلات تهم؟

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

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

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

افتح في المختبر

استكشف مقاييس أهمية السمات الثلاثة جنباً إلى جنب. انقر على سمة لترى أين استُخدمت عبر النموذج التجميعي.

تستيقظ التجربة عند وصولك…

لماذا هيمن XGBoost

في تجارب الورقة، طابق XGBoost المنافسين أو تفوّق عليهم باستمرار — التعزيز التدرُّجي في scikit-learn وgbm في R وSpark MLlib — بتسريع يصل إلى عشرة أضعاف مع دقة مكافئة. لكن السرعة وحدها لا تفسّر الهيمنة. نجح XGBoost بسبب تضافر عدّة عوامل:

حدّ من فرط التعلّم الذي كان يُضعف التعزيز التقليدي على البيانات الجدولية المشوّشة.
معالجة القيم المفقودة ألغت خطوة معالجة أوّلية مرهقة.
الخوارزمية التقريبية مكّنته من العمل على بيانات أكبر من أن تتعامل معها الطرق الدقيقة.
التصميم الواعي بذاكرة التخبئة جعله سريعاً حتى على جهاز واحد.
المنظومة مفتوحة المصدر — Python وR وJulia وJVM وSpark — لاقت الممارسين في بيئاتهم المعتادة.

النتيجة: بين 2015 و2017، استخدمت غالبية الفرق الفائزة على Kaggle خوارزمية XGBoost في مهام البيانات الجدولية. حتى اليوم، رغم ظهور منافسين أحدث مثل LightGBM وCatBoost، يظل XGBoost من أوّل الأدوات التي يلجأ إليها عالِم البيانات حين يواجه بيانات مهيكلة.

XGBoost في عشرة أسطر — تصنيف مع إيقاف مبكرpython

مبسَّط لإظهار الفكرة — ليس التنفيذ الحقيقي.

import xgboost as xgb
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split

# تحميل البيانات وتقسيمها
X, y = load_breast_cancer(return_X_y=True)
X_train, X_val, y_train, y_val = train_test_split(X, y, test_size=0.2)

# التدريب مع ضبط هيكلي + إيقاف مبكر
model = xgb.XGBClassifier(
    n_estimators=500, learning_rate=0.1,
    max_depth=4, reg_lambda=1.0, reg_alpha=0.1,
    subsample=0.8, colsample_bytree=0.8,
    early_stopping_rounds=20, eval_metric="logloss"
)
model.fit(X_train, y_train, eval_set=[(X_val, y_val)], verbose=False)
print(f"أفضل جولة: {model.best_iteration}، الدقة: {model.score(X_val, y_val):.3f}")

مسيرة تطوّر التعزيز التدرُّجي

لم يظهر XGBoost من فراغ، بل يستند إلى سلسلة طويلة من أساليب التجميع — بدءاً من AdaBoost مروراً بـالتعزيز التدرُّجي وصولاً إلى المعزّزات المسرَّعة بالمعالجات الرسومية اليوم. إليك كيف تراكمت الأفكار:

1995
AdaBoost
أثبت Freund وSchapire أن دمج عدّة مُصنِّفات ضعيفة — كلٌّ منها أفضل من التخمين العشوائي بقليل — في تصويت موزون يُنتج مُصنِّفاً قوياً. في كل جولة تُعاد ترجيح العيّنات بحيث تحصل الأخطاء على وزن أعلى.
2001
آلات التعزيز التدرُّجي (GBM)
عمّم Friedman فكرة التعزيز: بدلاً من إعادة ترجيح العيّنات، تُلائم كل شجرة جديدة التدرُّج السالب لأي دالة خسارة. بذلك أصبح التعزيز صالحاً للانحدار والترتيب وأي هدف قابل للاشتقاق.
2001
الغابة العشوائية
بديل Breiman القائم على التوازي: درّب أشجاراً عميقة كثيرة على عيّنات مسحوبة بالإعادة مع مجموعات فرعية عشوائية من السمات، ثم احسب متوسّطها. أقل عرضة لفرط التعلّم من التعزيز، لكنه أبطأ في التقاط الأنماط المعقّدة.
2014
إطلاق XGBoost
أطلق Chen وGuestrin نظام XGBoost مفتوح المصدر: دالة هدف منظَّمة، وتقسيمات واعية بالتناثر، وملخّص كمّيات موزون، وهندسة واعية بذاكرة التخبئة. استُخدم في 17 من 29 حلاً فائزاً على Kaggle عام 2015.
2017
LightGBM
ردّ Microsoft: إيجاد التقسيم عبر المدرّج التكراري ونموّ الشجرة ورقةً بورقة بدل مستوى بمستوى. أسرع بكثير على البيانات الضخمة مع دقة مماثلة.
2018
CatBoost
قدّمت Yandex التعزيز المرتّب لتقليل انزياح التنبؤ، مع دعم أصلي لترميز السمات الفئوية. يتميّز بأداء قوي دون ضبط كثير على بيانات تكثر فيها الأعمدة الفئوية.

المرجعChen, Guestrin. XGBoost: A Scalable Tree Boosting System. KDD, 2016.

مصطلحات هذه الورقة

إكس جي بوستXGBoost
مسودّة الكميّات الموزونةWeighted Quantile Sketch
اختيار الأعمدة العشوائيColumn Subsampling
الحوسبة خارج الذاكرةOut-of-Core Computation
كسب التقسيمSplit Gain