FQTree: Fine-grained Quantization and Hardware Generation of Boosted Decision Trees
تقدم هذه الورقة FQTree، وهي خوارزمية تدريب واعية بالكمية دقيقة التفاصيل مدمجة مع إطار عمل توليد الأجهزة QXXGB، والتي تعمل على تحسين أشجار القرار المعززة للنشر على مصفوفات البوابات المنطقية القابلة للبرمجة (FPGA) عن طريق تقليل استخدام جداول البحث والتبديل (LUT) بنسبة 26-57% مع الحفاظ على الدقة أو تحسينها.
المؤلفون الأصليون:Zhiqiang Que, Chang Sun, Haiyang Wang, Dinesh Pamunuwa, Roshan Weerasekera, Qijia Tang, Bakhtiar Zadeh, Wayne Luk, Maria Spiropulu
تخيل أنك تحاول تعليم روبوت كيفية اتخاذ القرارات، مثل حكم في لعبة فيديو أو حارس أمن في ملهى ليلي. أنت لا تريد للروبوت أن يكون مفكراً بطيئاً وثقيلاً؛ بل تريده أن يكون فائق السرعة، يتخذ قرارات في أجزاء من الثانية دون تعثر. هذا هو عالم "أشجار القرار المعززة" (Boosted Decision Trees - BDTs). فكر في الـ BDT ليس كدماغ واحد ضخم، بل كفريق من العديد من صانعي القرارات الصغار والبسطاء. كل واحد منهم يطرح سؤالاً بسيطاً مثل: "هل درجة الحرارة فوق 20 درجة؟" أو "هل السرعة فوق 50 ميلاً في الساعة؟". وبناءً على الإجابة، يسلم الفريق الشعلة إلى الشخص التالي في الصف. وبحلول نهاية الصف، يكون الفريق بأكمله قد جمع آراءهم لاتخاذ قرار نهائي. تشتهر هذه الفرق بقدرتها العالية على رصد الأنماط في البيانات الفوضوية، ولكن لديها مشكلة: فهي غالباً ما تكون ثقيلة وبطيئة جداً بالنسبة للرقائق الصغيرة فائقة السرعة (التي تسمى FPGAs) التي تشغل الأنظمة التي تعمل في الوقت الفعلي مثل السيارات ذاتية القيادة أو تجارب فيزياء الجسيمات.
التحدي الكبير هو أن فرق اتخاذ القرار هذه تُدرب عادةً باستخدام أرقام "عائمة" (مثل 3.14159...)، وهي أرقام دقيقة ولكنها تستهلك مساحة وطاقة كبيرة لتخزينها. ولجعلها تعمل على رقائق صغيرة، يحاول المهندسون عادةً حشر هذه الأرقام في صناديق أصغر وأبسط (مثل الأعداد الصحيحة). لكن الأمر يشبه محاولة وضع هلام (جيلي) ضخم ومتذبذب في صندوق صغير وصلب: إذا حاولت ضغطه فقط بعد أن تماسك الهلام بالفعل، فإنه سينكسر، ويبدأ الروبوت في ارتكاب أخطاء غبية. كانت الطريقة القديمة هي التخمين للوصول إلى الحجم المناسب للصندوق للجميع، وهو ما كان يهدر المساحة أو يفسد ذكاء الروبوت في كثير من الأحيان.
تقدم هذه الورقة طريقة جديدة ذكية تسمى FQTree (شجرة التكميم دقيقة التفاصيل) وأداة مرافقة تسمى QXGB تغير طريقة بناء فرق اتخاذ القرار هذه. فبدلاً من تدريب الفريق باستخدام أرقام عائمة كبيرة ثم محاولة حشرها في صندوق لاحقاً، تقوم FQTree بتعليم الفريق التفكير في صناديق صغيرة وبسيطة أثناء عملية التعلم. الأمر يشبه تدريب لاعبة جمباز على أداء حركات فوق عارضة توازن ضيقة منذ اليوم الأول، بدلاً من تركها تتدرب على أرضية واسعة ثم إجبارها على الانتقال إلى العارضة قبيل المسابقة مباشرة.
السر يكمكمن في أن FTree تدرك أن ليس كل أعضاء فريق اتخاذ القرار متساوين في الأهمية. فالأعضاء الأوائل، الذين يتخذون القرارات الكبيرة والواضحة، يحتاجون إلى دقة عالية جداً. أما الأعضاء اللاحقون، الذين يقومون فقط بتعديلات طفيفة لإصلاح الأخطاء الصغيرة، فلا يحتاجون إلى نفس القدر من الدقة. تقوم FQTree تلقائياً بتحديد مقدار "مساحة الدماغ" التي يحتاجها كل عضو. فهي تمنح المفكرين الكبار المزيد من البتات (المزيد من التفاصيل) والمفكرين الصغار عدداً أقل من البتات (تفاصيل أقل)، مما يوفر مساحة هائلة. كما تستخدم خدعة تسمى "طي الانحياز" (bias folding)، وهي تشبه إزاحة جميع الأرقام لتصبح كلها موجبة، مما يسمح للأجهزة بالتخلي عن بت الإشارة (sign bit) لتصبح أكثر بساطة.
بمجرد تدريب الفريق بهذه الطريقة الفعالة، يعمل إطار عمل QXGB كمترجم سحري؛ حيث يأخذ الفريق المدرب ويبني فوراً مخططاً هندسياً مخصصاً للرقاقة، دون الحاجة لمهندس بشري لإعادة رسم الدوائر لكل تصميم جديد. والنتائج مبهرة: في ثلاثة اختبارات مختلفة (واحد للتعرف على الأرقام المكتوبة بخط اليد، وواحد لرصد جسيمات النفاثات في الفيزياء، وآخر للعثور على المتسللين إلى الشبكات)، استخدمت هذه الطريقة مساحة أجهزة (تحديداً جداول البحث أو LUTs) أقل بنسبة تتراوح بين 26% إلى 57% من أفضل الطرق الحالية، مع الحفاظ على دقة عالية أو حتى جعلها أفضل. وفي بعض الحالات، جعلت القرارات أسرع بمرتين. إنه فوز للطرفين: الروبوت يصبح أصغر، وأسرع، ولا يزال بنفس الذكاء.
ملخص تقني: FQTree – التكميم دقيق الحبيبات وتوليد الأجهزة لشرائح اتخاذ القرار المعززة
بيان المشكلة
تُستخدم أشجار اتخاذ القرار المعززة (BDTs) على نطاق واسع في التطبيقات ذات زمن الاستجابة الحرج نظرًا لأدائها التنبؤي وحجمها المدمج، مما يجعلها مناسبة للنشر على مصفوفات البوابات المنطقية القابلة للبرمجة ميدانيًا (FPGA). ومع ذلك، يظل التنفيذ الفعال للأجهزة أمرًا صعبًا. تعتمد تصميمات BDT الحالية الموجهة لـ FPGA عادةً على تمثيلات نقطة ثابتة موحدة أو مضبوطة يدويًا عبر النموذج بأكمده. يفشل هذا النهج في مراعاة الأدوار الرقمية غير المتجانسة لمكونات BDT المختلفة (الميزات المدخلة، عتبات الانقسام، قيم الأوراق، ومنطق التراكم)، مما يؤدي غالبًا إلى تكاليف أجهزة غير ضرورية أو تدهور يمكن تجنبه في الدقة.
علاوة على ذلك، غالبًا ما يكون التكميم بعد التدريب (PTQ) المباشر غير فعال بالنسبة لـ BDTs. فخلافًا للشبكات العصبية حيث يؤدي التكميم إلى اضطراب حسابي مستمر، يمكن أن يتسبب تكميم BDT في تغييرات مسار منفصلة؛ إذ قد تؤدي الاضطرابات الطفيفة في الميزات أو العتبات إلى قلب قرارات الفروع، مما يغير تمامًا الورقة المختارة. تتطلب هذه الحساسية نهج "التدريب الواعي بالتكميم" (QAT) الذي يعرض النموذج لآثار التكميم أثناء عملية التحسين، مما يسمح للمعلمات الرقمية بالتكيف مع الدقة المنخفضة مع الحفاظ على الجودة التنبؤية.
المنهجية
خوارزمية FQTree
يقترح المؤلفون FQTree، وهي خوارزمية QAT دقيقة الحبيبات ومدركة للأجهزة لـ BDTs. بخلاف PTQ، تدمج FQTree التكميم مباشرة في حلقة التدريب.
التعزيز مع التكميم: خلال عملية التعزيز المرحلية، يتم تكميم كل شجرة تم ضبطها حديثًا فورًا قبل استخدامها في مراحل التدريب اللاحقة. يضمن هذا أن الأشجار اللاحقة تتكيف مع الأخطاء المتبقية لـ المجموعة المكممة بالفعل، مما يعوض عن كل من بقايا المهمة والتشويه الناتج عن التكميم.
مخطط تكميم قيمة الورقة: الابتكار الأساسي هو استراتيجية تكميم قيم الأوراق الموجهة للأجهزة. بدلاً من الدقة الموحدة، تخصص FQTree الدقة بناءً على مقدار قيم الأوراق:
الخطوة العالمية والإزاحة على مستوى الشجرة: تُستخدم خطوة تكميم عالمية (s) عبر المجموعة، مدمجة مع عامل إزاحة على مستوى الشجرة (f(v)).
تمثيل الأعداد الصحيحة غير السالبة: يحول المخطط قيم الأوراق إلى أعداد صحيحة مدمجة غير سالبة. يتم قص القيم السالبة إلى الصفر، ويتم تطبيق إزاحة لإزالة بت الإشارة، مما يبسط مسار البيانات.
طي الانحياز: يتم طي الإزاحة (offset) التي تمت إزالتها أثناء إعادة التأسيس في حد انحياز (bias) على مستوى الشجرة أو مستوى الفئة، والذي يُضاف مرة واحدة فقط بعد التراكم، بدلاً من حمله عبر كل مسار شجرة.
عرض البت الديناميكي: يتم تحديد عرض البت لكل شجرة (bt) من خلال النطاق الديناميكي لقيم الأعداد الصحيحة المكممة الخاصة بها (⌈log2(max(vint′)+1)⌉). الأشجار المبكرة، التي تساهم بشكل أكبر في التنبؤ النهائي، تحصل طبيعيًا على عدد أكبر من البتات، بينما تستخدم الأشجار التصحيحية اللاحقة بتات أقل.
تكميم الميزة/العتبة: يتم تطبيق التكميم الموحد القياسي على الميزات والعتبات، مع محاذاة دقتها طبيعيًا في الأجهزة عبر الطرح ذي الإشارة.
إطار عمل QXGB
لسد الفجوة بين التدريب والنشر، يقدم المؤلفون QXGB (XGBoost المكمم)، وهو إطار عمل قائم على المترجم للتوليد التلقائي للأجهزة.
تمثيل تدفق البيانات: يتم خفض BDT المكمم المدرب إلى تمثيل وسيط (IR) موسع لـ "مجموعة تعليمات الحساب الموزعة" (DAIS). تم توسيع هذا الـ IR بـ تعليمات MUX صريحة لالتقاط التوجيه الشرطي لعقد القرار، مما يعامل استدلال BDT كـ "نواة تدفق بيانات" عديمة الحالة.
التوليد التلقائي: يتتبع المترجم رسميًا مخطط الحساب ويولد كود RTL أو HLS قابل للتصنيع. يدعم هذا التدفق المحاكاة المطابقة للبيانات ويسمح بالاستكشاف المنهجي للمقايضة بين الدقة وزمن الاستجابة والموارد دون إعادة تصميم يدوي.
المساهمات الرئيسية
خوارزمية FQTree: نهج QAT دقيق الحبيبات يتميز بصياغة تكميم قيم الأوراق الموجهة للأجهزة والتي تستخدم خطوة عالمية، وإزاحة على مستوى الشجرة، وطي الانحياز لتمكين تمثيلات الأعداد الصحيحة المدمجة وغير السالبة.
إطار عمل QXGB: تدفق قابل للتوسع وقائم على المترجم لتوليد تطبيقات BDT فعالة ومنخفضة زمن الاستجابة على FPGA لكل من HLS وRTL، مما يقلل زمن الاستجابة واستخدام الموارد.
تقييم شامل: إثبات أن الطريقة تقلل من استخدام جداول البحث (LUT) بنسبة 26-57% مقارنة بتصميمات BDT الرائدة الموجهة لـ FPGA مع مطابقة أو تحسين الدقة.
النتائج التجريبية
تم تقييم الطريقة على ثلاث مجموعات بيانات: JSC (تصنيف البنية التحتية للنفاث في الفيزياء عالية الطاقة)، MNIST (تصنيف الأرقام المكتوبة يدويًا)، و NID (كشف اختراق الشبكة).
مجموعة بيانات JSC: حققت FQTree دقة 75.7% باستخدام 1,652 LUT ودورتين (4.0 نانو ثانية). مقارنة بـ TreeLUT (دقة 75.6%، 2,234 LUT، 3 دورات)، حسنت FQTree الدقة مع تقليل استخدام LUT بنسبة ~26% وعمق خط الأنابيب. عند نقطة تكلفة أقل، حققت FQTree دقة 74.8% مع 548 LUT فقط (أقل بنسبة 31% من TreeLUT) وزمن استجابة دورة واحدة.
مجموعة بيانات MNIST: وصلت أعلى تهيئة دقة إلى 97.7% باستخدام 8,147 LUT ودورتين، متفوقة على أفضل نتيجة سابقة (POLYBiNN، 97.2%) مع زمن استجابة واستخدام موارد أقل بكثير. عند النقاط المتوسطة، حققت FQTree دقة 96.7% باستخدام 2,744 LUT، مما يمثل انخفاضًا بنسبة ~39% في LUT مقارنة بـ TreeLUT لدقة مماثلة.
مجموعة بيانات NID: حققت FQTree دقة 93.1% باستخدام 157 LUT فقط ودورة واحدة، وهو انخفاض بنسبة ~55% في LUT مقارنة بـ TreeLUT (دقة 92.7%، 345 LUT).
خط الأساس PTQ: عند مقارنتها بخط أساس التكميم بعد التدريب باستخدام نفس المكمم، قدمت FQTree باستمرار مقايضات أفضل بين الدقة والموارد، مما يؤكد أن المكاسب تنبع من كل من تصميم المكمم وعملية تحسين QAT.
الأهمية والادعاءات
يزعم البحث تقديم أول سير عمل موحد لنشر BDTs على FPGA يجمع بين تكميم قيم الأوراق الموجه للأجهزة، والتدريب الواعي بالتكميم، والتوليد التلقائي للأجهزة.
يؤكد المؤلفون أن نهجهم يعالج التحديات المحددة لـ BDTs، حيث يؤثر التكميم على قرارات التوجيه، وليس فقط الدقة الحسابية. من خلال دمج التحكم دقيق الحبيبات في التدريب وأتمتة توليد الأجهزة عبر إطار عمل QXGB، تمكن الطريقة من الاستكشاف المنهجي للمقايضة بين الدقة وزمن الاستجابة والموارد. تظهر النتائج أن FQTree يمكنها تحديد عمليات تنفيذ مدمجة وعالية الجودة تتفوق بشكل كبير على التصميمات الحالية الرائدة من حيث كفاءة الأجهزة (استخدام LUT) مع الحفاظ على الدقة أو تحسينها.