أساسيات تعلم الآلة2017متوسط9 دقيقة قراءة
LightGBM: تعزيز تدرُّجي فائق الكفاءة لأشجار القرار
LightGBM: A Highly Efficient Gradient Boosting Decision Tree
Ke, G. · Meng, Q. · Finley, T. · Wang, T. · Chen, W. · Ma, W. · Ye, Q. · Liu, T.-Y. — NeurIPS
المشكلة
أشجار القرار المُعزَّزة بالتدرُّج من أنجح الخوارزميات في التعامل مع البيانات الجدولية، لكنّ التطبيقات الموجودة مثل XGBoost تصل إلى حدودها مع البيانات الضخمة. السبب بسيط: لكل سمة، تحتاج الخوارزمية أن تمرّ على كل صفّ في البيانات لإيجاد أفضل نقطة . حين يصبح عدد الصفوف بالملايين والسمات بالآلاف، يتحوّل هذا البحث الشامل إلى عبء حقيقي يستهلك ساعات من وذاكرة هائلة.
الإسهام
يُقدّم LightGBM ابتكارين أساسيين: الأول هو أخذ العيّنات أحادي الجانب بناءً على التدرُّج (GOSS)، حيث يحتفظ بكل العيّنات ذات التدرُّجات الكبيرة ويأخذ عيّنة عشوائية فقط من البقية — فيُوجِّه الحساب نحو البيانات الأكثر أهمية. الثاني هو تجميع السمات الحصرية (EFB)، الذي يكتشف السمات المتفرقة التي لا تنشط معاً ويدمجها في سمة واحدة، فتنخفض الأبعاد دون خسارة معلومات. وحين نضيف إلى ذلك بحث التقسيم وتنمية الأشجار ورقة بورقة، يُحقّق LightGBM تسريعاً يصل إلى 20 ضعفاً مع دقة شبه مطابقة.
الأثر
أصبح LightGBM الخيار الأول للعاملين في التعلّم الآلي حين يتعاملون مع بيانات جدولية ضخمة. يقف وراء الحلول الفائزة في معظم مسابقات Kaggle على البيانات المُهيكلة، ويُستخدم على نطاق واسع في الصناعة للترتيب والتوصية وكشف الاحتيال والتنبؤ بمعدلات النقر. ومع XGBoost وCatBoost يُشكّل ثلاثي التعزيز الحديث، وأثّرت أفكاره — خصوصاً المُدرَّج التكراري وأخذ العيّنات بالتدرُّج — في أُطُر التعزيز التي جاءت بعده.
تخيّل مدير مدرسة يبحث عن معلّمين بدلاء. الطريقة القديمة (كما في XGBoost) تفرض مقابلة كل مُرشّح لأجل كل مادة، حتى لو كانت الوظيفة مشغولة أصلاً. النتيجة: أسابيع من المقابلات بلا داعٍ.
LightGBM يتعامل مع الأمر بذكاء أكبر: أولاً، بدلاً من تقييم كل مرشح بدقة مُفرطة، يُصنّف المتقاربين في مجموعات سريعة — هذا هو مبدأ المُدرَّج التكراري. ثانياً، يُركّز وقت المقابلات على مَن أساؤوا في اختبار الفرز، لأنهم يكشفون أكثر عن نقاط الضعف الحقيقية — وهذه فكرة أخذ العيّنات بالتدرُّج (GOSS). ثالثاً، يُلاحظ أنّ وظيفتَي «معلم إسبانية» و«معلم فرنسية» لا تكونان شاغرتين في الوقت نفسه أبداً، فيدمجهما في وظيفة واحدة «معلم لغات» — وهذا هو تجميع السمات الحصرية (EFB).
المحصلة: نفس جودة التعيينات، في وقت أقصر بكثير.
عنق الزجاجة: مسح كل صف لأجل كل تقسيم
الفكرة الأساسية في أنك تبني من واحدة تلو الأخرى. كل شجرة جديدة تتعلّم من أخطاء الأشجار التي سبقتها — وتحديداً من المتبقية. المشكلة أنّ كل في الشجرة تحتاج فحص كل نقطة تقسيم ممكنة لكل ، أي مسح البيانات بالكامل لكل قرار تقسيم.
XGBoost يحلّ هذا بخوارزمية الترتيب المسبق: يُرتّب قيم كل سمة ثم يمرّ عليها قيمةً قيمةً لحساب . النتيجة دقيقة، لكنّ التكلفة تبلغ لكل عقدة — والنموذج الواحد قد يحتوي على آلاف العقد موزّعة على مئات الأشجار.
حين يصل إلى الملايين و إلى الآلاف، يتحوّل زمن التدريب إلى عائق حقيقي لا يمكن تجاهله.
الحل الأول: بحث التقسيم بالمُدرَّج التكراري
بدلاً من فحص كل قيمة على حدة لكل سمة، يأخذ LightGBM القيم المتصلة ويضعها في عدد ثابت من السلال — عادة 255 سلّة. هذا هو مبدأ المُدرَّج التكراري: لكل سلّة يُخزَّن عدد العيّنات ومجموع التدرُّجات. بناء هذا المُدرَّج يُكلّف ، لكنّ البحث عن أفضل تقسيم بعدها يُكلّف فقط بدلاً من .
الفكرة أشبه بتصحيح الامتحانات: بدلاً من ترتيب درجة كل طالب بدقة، تضعهم في تقديرات (ممتاز، جيد جداً، جيد، مقبول، ضعيف). تخسر قليلاً من الدقة، لكنك ترى فوراً أين يقع أفضل خطّ فاصل بين المجموعات. ومع 255 سلّة، الخسارة في الدقة لا تكاد تُذكر.
وهناك حيلة ذكية أخرى: طرح المُدرَّجات. إذا كنت تعرف مُدرَّج العقدة الأم، يكفي أن تطرح مُدرَّج أحد الابنين من مُدرَّج الأم للحصول على مُدرَّج الابن الآخر. بهذا تنخفض تكلفة بناء المُدرَّجات إلى النصف.
نموّ أذكى: ورقة بورقة أم طبقة بطبقة؟
معظم أُطُر — بما فيها الوضع الافتراضي لـ XGBoost — تُنمّي الأشجار طبقة بطبقة: تُقسّم كل العقد في المستوى الحالي قبل النزول إلى مستوى أعمق، فتنتج أشجاراً متوازنة. الطريقة آمنة، لكنها تهدر تقسيمات على عقد لا تُضيف شيئاً يُذكر لتقليل .
LightGBM يتّبع نهجاً مختلفاً: ينمو ورقة بورقة. في كل خطوة يبحث في الشجرة بأكملها عن الورقة التي سيُحقّق تقسيمها أكبر تخفيض في دالة الخسارة، ويُقسّمها هي فقط. النتيجة أشجار غير متناظرة وأعمق، لكنها تتقارب أسرع — تصل إلى الخسارة المطلوبة بتقسيمات أقل.
الثمن المحتمل هو : الشجرة قد تنمو عميقاً جداً في جانب واحد فتحفظ الضوضاء بدلاً من الأنماط الحقيقية. لذلك يتحكّم LightGBM بهذا عبر مُعامِلَي max_depth وnum_leaves. فكّر في num_leaves كميزانية: الشجرة تستطيع إنفاق تقسيماتها أينما كان المكسب أعلى، لكنها لا تتجاوز الميزانية.
أخذ العيّنات بالتدرُّج (GOSS): ركّز على ما يهمّ
ليست كل نقاط البيانات متساوية في أهميتها لعملية التعلّم. العيّنات ذات التدرُّجات الكبيرة هي التي يُخطئ فيها النموذج أكثر من غيرها — وبالتالي تحمل أكبر قدر من المعلومات لتحسين الشجرة التالية. في المقابل، العيّنات ذات التدرُّجات الصغيرة يتنبأ بها النموذج جيداً أصلاً، فإسهامها في التحسين محدود.
GOSS يستثمر هذه الملاحظة: يحتفظ بـجميع العيّنات ذات التدرُّج الكبير (أعلى نسبة من البيانات) ويأخذ عيّنة عشوائية فقط من البقية (نسبة ). ولكي لا يتحيّز النموذج بسبب هذا ، تُضرب العيّنات المختارة ذات التدرُّج الصغير بعامل لتعويض التمثيل الناقص.
المحصّلة: المُدرَّج التكراري يُبنى من مجموعة أصغر بكثير من البيانات، لكن توزيع مكسب المعلومات يبقى محفوظاً تقريبياً. مع الإعدادات المعتادة (، ) تُبنى الشجرة من 30% فقط من البيانات، فتحصل على تسريع يقارب الضعف فوق ما يُوفّره المُدرَّج وحده.
تجميع السمات الحصرية (EFB): اختصار السمات المتفرقة
البيانات الحقيقية — خصوصاً بعد — تكون في الغالب شديدة : معظم قيم السمات أصفار. وكثير من هذه السمات متبادلة الحصرية، بمعنى أنها نادراً ما تحمل قيماً غير صفرية في الوقت نفسه. مثلاً، لو رمّزت بيانات نصية أحادياً، فعمود «تفاحة» وعمود «برتقالة» لن يساويا 1 معاً في الصف نفسه أبداً.
ما يفعله EFB هو اكتشاف هذه السمات المتبادلة الحصرية ودمجها في سمة حُزمة واحدة. الآلية بسيطة: لو كانت السمة A تتراوح بين 0–10 والسمة B بين 0–20، تُخزَّن قيم A كما هي بينما تُزاح قيم B بمقدار 10. بعد ذلك تستطيع الشجرة التقسيم على الحُزمة بدلاً من سمتين مستقلتين، فينخفض عدد السمات الفعلي انخفاضاً كبيراً.
إيجاد التجميع الأمثل مسألة صعبة حسابياً — تُختزل إلى — لذا يستخدم EFB خوارزمية جشعة: يبني رسماً بيانياً للتعارضات تربط فيه الأضلاع بين السمات التي ليست متبادلة الحصرية، ثم يُوزّع السمات على حُزم بأسلوب جشع مع السماح بنسبة تعارض صغيرة.
المسار الكامل: كيف يتدرّب LightGBM خطوة بخطوة
في كل جولة من جولات التعزيز، يمرّ LightGBM بالخطوات التالية:
- حساب التدرُّجات لجميع العيّنات بناءً على تنبؤات النموذج الحالي.
- أخذ العيّنات بالتدرُّج (GOSS) — الاحتفاظ بكل العيّنات ذات التدرُّج الكبير، وسحب عيّنة عشوائية من البقية.
- تجميع السمات الحصرية (EFB) — دمج السمات المتبادلة الحصرية (يُنفَّذ مرة واحدة عند بداية التدريب).
- بناء المُدرَّجات التكرارية لكل سمة أو حُزمة على البيانات المُختارة.
- إيجاد أفضل التقسيمات بمسح سلال المُدرَّج بدلاً من القيم الخام.
- تنمية الشجرة ورقة بورقة — في كل خطوة تُقسَّم الورقة ذات أعلى مكسب.
- إضافة الشجرة الجديدة إلى التجميعة مع تقليص بواسطة .
الخطوتان 4 و5 هما مصدر التوفير الأساسي من المُدرَّج التكراري. الخطوة 2 تُقلّص البيانات الداخلة إلى الخطوة 4، والخطوة 3 تُقلّص عدد السمات. وحين تتراكم هذه التحسينات معاً، تصل إلى تسريع بمقدار 20 ضعفاً.
الفكرة في شيفرة برمجية
مبسَّط لإظهار الفكرة — ليس التنفيذ الحقيقي.
import numpy as np
def build_histogram(feature_bins, gradients, hessians, n_bins=255):
"""بناء مُدرَّج تكراري للتدرُّجات ومشتقات هسه لسمة واحدة."""
grad_hist = np.zeros(n_bins)
hess_hist = np.zeros(n_bins)
for i in range(len(feature_bins)):
b = feature_bins[i]
grad_hist[b] += gradients[i]
hess_hist[b] += hessians[i]
return grad_hist, hess_hist
def find_best_split(grad_hist, hess_hist, reg_lambda=1.0):
"""مسح سلال المُدرَّج للعثور على التقسيم ذي أعلى مكسب."""
G_total = grad_hist.sum()
H_total = hess_hist.sum()
best_gain, best_bin = -np.inf, -1
G_left, H_left = 0.0, 0.0
for b in range(len(grad_hist) - 1):
G_left += grad_hist[b]
H_left += hess_hist[b]
G_right = G_total - G_left
H_right = H_total - H_left
gain = 0.5 * (
G_left**2 / (H_left + reg_lambda)
+ G_right**2 / (H_right + reg_lambda)
- G_total**2 / (H_total + reg_lambda)
)
if gain > best_gain:
best_gain, best_bin = gain, b
return best_bin, best_gain
# الفكرة الجوهرية: نمسح 255 سلّة فقط وليس ملايين الصفوف.
# من هنا يأتي التسريع.التجارب: السرعة والدقة
اختبرت الورقة LightGBM على خمس مجموعات بيانات عامة تتراوح بين نصف مليون و10 ملايين عيّنة. مقارنةً بخوارزمية الترتيب المسبق في XGBoost، حقّق LightGBM تسريعاً يتراوح بين 6 أضعاف و21 ضعفاً مع الحفاظ على شبه مطابقة — مقاسة بـ في مهام التصنيف وNDCG@10 في مهام الترتيب.
لو فصّلنا إسهام كل تقنية: GOSS وحده يُوفّر تسريعاً يقارب الضعف بالتدريب على 10–20% فقط من البيانات. EFB يُضيف تسريعاً يتناسب مع درجة تفرُّق السمات — مع السمات المُرمَّزة أحادياً يمكنه تقليص عدد السمات الفعلي بمقدار رتبة حجمية كاملة. أما المُدرَّج التكراري فهو الأساس الذي تُبنى عليه التقنيتان معاً.
لماذا غيَّر LightGBM قواعد اللعبة
2014
إطلاق XGBoost
أطلق تشن وغِسترين XGBoost الذي نشر فكرة التعزيز التدرُّجي مع التنظيم، وسرعان ما أصبح الخوارزمية المهيمنة في مسابقات Kaggle.
2017
LightGBM (هذه الورقة)
قدّمت مايكروسوفت تقنيات أخذ العيّنات بالتدرُّج وتجميع السمات الحصرية والنمو ورقة بورقة، محقّقةً تسريعاً بعشرين ضعفاً مع دقة شبه مطابقة.
2018
CatBoost
أطلقت Yandex خوارزمية CatBoost التي تدعم التعزيز المُرتَّب والتعامل المباشر مع السمات الفئوية، مُكمِّلةً بذلك ثلاثي التعزيز الحديث.
2020
SHAP لتفسير النماذج
طوّر لُندبرغ خوارزمية TreeSHAP لحساب قيم SHAP على تجميعات الأشجار بدقة وكفاءة. أدمجها LightGBM بشكل أصيل، فأصبح تفسير النماذج ميزة مدمجة من الدرجة الأولى.
2022
هيمنة على البيانات الجدولية
أكّدت دراسات متعددة أنّ التعزيز التدرُّجي (XGBoost وLightGBM وCatBoost) لا يزال يتفوّق على التعلّم العميق في معظم المهام الجدولية، خصوصاً مع مجموعات البيانات متوسطة الحجم.
المرجعKe, Meng, Finley, Wang, Chen, Ma, Ye, Liu. LightGBM: A Highly Efficient Gradient Boosting Decision Tree. NeurIPS, 2017.
مصطلحات هذه الورقة
- تعزيز التدرجGradient Boosting
- شجرة القرار الإحصائيةDecision Tree
- المُدرَّج التكراريHistogram
- أهمية السماتFeature Importance
- فرط التخصيصOverfitting
- معدل التعلمLearning Rate
- النماذج التجميعية الهجينةEnsemble
- التجميع المتتالي التراكمي للنماذجBoosting
- إكس جي بوستXGBoost
- لايت جي بي إمLightGBM
- استخلاص السماتFeature Extraction
- التناثر البنيوي للمصفوفاتSparsity