Approximation-Free Differentiable Oblique Decision Trees

ملخص تقني: أشجار القرار المائلة القابلة للتفاضل بدون تقريب

بيان المشكلة
تحظى أشجار القرار (DTs) بتقدير كبير في المجالات الحساسة للسلامة (مثل التشخيص الطبي) نظراً لقابليتها للتفسير وفعاليتها في التعامل مع البيانات الجدولية. ومع ذلك، فإن تدريب أشجار القرار "المائلة" (Oblique DTs) الدقيقة (حيث تكون التقسيمات عبارة عن تركيبات خطية من الميزات بدلاً من كونها محاذية للمحاور) يمثل تحدياً حوسبياً بسبب الطبيعة غير الحتمية (NP-hard) لمساحة البحث. وبينما تتيح الأساليب القابلة للتفاضل الحديثة التدريب القائم على التدرج، إلا أنها تعتمد على تقريبات تخل بسلامة عملية التعلم:

1. الأشجار الناعمة (Soft DTs): تستخدم حدوداً احتمالية "ناعمة" (مثل تنشيطات Sigmoid) لجعل الأشجار قابلة للتفاضل، ولكن تحويل هذه الحدود إلى قرارات "صلبة" غالباً ما يؤدي إلى تدهور الدقة.
2. المقدرات ذات المرور المباشر (Straight-Through Estimators - STE): تُستخدم في طرق مثل DGT وICCT لتقريب التدرجات عبر القرارات الصلبة غير القابلة للتفاضل، مما يخلق عدم تطابق دلالي بين مرحلة التمرير الأمامي (التقييم) ومرحلة التمرير الخلفي (التحسين). في مهام الانحدار (Regression)، يؤدي هذا التباين إلى تحديثات تدرج متحيزة، وعدم استقرار هيكلي، وعدم استغلال كامل لعقد الأوراق، حيث يتم تحديث المعلمات الداخلية بناءً على جميع المنظمات بينما يتم اختيار واحد فقط منها.

المنهجية: DTSemNet
يقترح المؤلفون DTSemNet، وهو بنية شبكة عصبية جديدة توفر تمثيلاً مكافئاً دلالياً وقابلاً للعكس لأشجار القرار المائلة الصلبة. بخلاف الأعمال السابقة، تتيح DTSemNet التدريب من البداية إلى النهاية باستخدام خوارزمية التدرج النزولي القياسية دون الحاجة إلى تقريبات.

• البنية: تقوم DTSemNet بترميز شجرة قرار بم $m$ من العقد الداخلية و $n$ من الأوراق في شبكة عصبية باستخدام تنشيطات ReLU والعمليات الخطية.
  • العقد الداخلية: تمثل بطبقات خطية تحسب $\langle A_i, x \rangle + b_i$.
  • التفرع: تستخدم تنشيطات ReLU للفصل بين النتائج الموجبة ($\top$) والسالبة ($\bot$)، مما يضمن تفعيل فرع واحد بالضبط لأي مدخل (باستثناء الحدود ذات القياس الصفري).
  • الأوراق: تقوم طبقة خطية ذات أوزان ثابتة بتجميع الفروع المفعلة لإنتاج الـ (logits) لكل ورقة.
• التكافؤ الدلالي: يثبت النظرية 1 أن أي مدخل $x$، فإن الورقة المختارة بواسطة شجرة القرار الصلبة هي نفسها الورقة ذات أعلى قيمة logit في شبكة DTSemNet. وبالتالي، فإن دالة التقييم (التمرير الأمامي) ودالة التحسين (التمرير الخلفي) متطابقتان دلالياً.

استراتيجية الانحدار: Top-k الملدن (Annealed Top-k)
بينما يتوافق التصنيف طبيعياً مع هذه الصيغة (عبر argmax)، يتطلب الانحدار تحسيناً مشتركاً لمسارات التوجيه (العقد الداخلية) ومنظمات الأوراق. حدد المؤلفون أن استخدام مقدر واحد (STE) كما في عملهم السابق في المؤتمرات يسبب عدم استقرار لأن العقد الداخلية تُحدث بناءً على جميع المنظمات بينما يتم تحديث منظم واحد فقط في كل خطوة.

لحل هذه المشكلة، قدمت الورقة طريقة Annealed Top-k:

1. الآلية: بدلاً من اختيار Top-1 الصلب أثناء التدريب، يستخدم النموذج في البداية مختار Top-$k$ (حيث $k \ge 2$) مقترناً بـ Softmax مدرج الحرارة (temperature-scaled)، مما يسمح للنموذج بتوجيه المدخلات إلى عدة خبراء (أوراق) في وقت واحد، مما يوفر تدرجات غنية بالمعلومات.
2. التلدين (Annealing): يتم تقليل قيمة $k$ تدريجياً من $k \ge 2$ إلى $k=1$ عبر دورات التدريب.
3. الفوائد:
   • اتساق التدرج: على عكس STE، تشترك عمليات التمرير الأمامي والخلفي في نفس الدلالات عند كل خطوة $k$.
   • تحديثات متوازنة: يتم تحديث معلمات العقد الداخلية بناءً على أفضل $k$ من المنظمات المختارة فقط، مما يمنع التأثير المزعزع للاوراق البعيدة غير المختارة.
   • الاستكشاف: يتم تحديث عدة منظمات لعينة واحدة، مما يسمح للنموذج بالتكيف إذا تغير قرار التوجيه لاحقاً في التدريب.
4. الضبط الدقيق (Fine-tuning): بمجرد الوصول إلى $k=1$، يتم تجميد العقد الداخلية، ويتم ضبط منظمات الأوراق باستخدام عينات معززة لمنع الإفراط في التخصيص (overfitting).

المساهمات الرئيسية

1. بنية DTSemNet: ترميز قابل للتفاضل لأشجار القرار المائلة، مكافئ دلالياً للشجرة الصلبة، مما يسمح بتدريب دقيق عبر التدرج دون تقريب لمهام التصنيف.
2. Annealed Top-k للانحدار: إجراء تدريب مبتكر يلغي التقريب والتحيز المتأصل في طرق STE لمهام الانحدار، مما يضمن تحسيناً مشتركاً مستقراً ودقيقاً لمعلمات التوجيه ومعلمات الأوراق.
3. سياسات التعلم المعزز البرمجية: إثبات DTSemNet كسياسة برمجية في التعلم المعزز (RL)، لتحل محل الشبكات العصبية القياسية في كل من فضاءات العمل المنفصلة والمستمرة.

النتائج التجريبية
قيم المؤلفون DTSemNet مقابل أحدث الطرق (TAO, DGT, CRO-DT, CART, ICCT, VIPER) عبر اختبارات التصنيف، والانحدار، والتعلم المعزز.

• التصنيف: حققت DTSemNet أفضل أداء على جميع مجموعات البيانات المختبرة، بما في ذلك الأشجار الموجزة والكثيفة. تفوقت بشكل ملحوظ على الطرق غير القائمة على التدرج (مثل TAO, CRO-DT) والتقريبات القائمة على التدرج (مثل DGT)، حيث قللت خطأ التصنيف بنسبة تصل إلى 10% في الاختبارات الصعبة مثل Optical Recognition. كانت أوقات التدريب مقاربة لـ DGT وأسرع بكثير من طرق البحث العالمي.
• الانحدار: تفوقت DTSemNet باستخدام Top-k على جميع المنافسين في معظم مجموعات البيانات. حققت تحسناً متوسطاً في RMSE بنسبة 3% عن TAO-Linear وتفوقت بشكل كبير على DTSemNet-STE (التي استخدمت STE). أكدت دراسات الاستئصال (Ablation studies) أن Top-k تؤدي إلى استخدام أكثر توازناً للأوراق وتطور أكثر استقراراً للأوزان مقارنة بـ STE، التي تميل إلى عدم استغلال الأوراق بشكل كافٍ.
• التعلم المعزز:
  • الأفعال المنفصلة (Discrete Actions): طابقت DTSemNet أداء الشبكات العصبية أو تجاوزته، وتفوقت بشكل كبير على السياسات الأخرى القائمة على أشجار القرار (DGT, ICCT, VIPER) في بيئات مثل LunarLander وZerglings.
  • الأفعال المستمرة (Continuous Actions): باستخدام استراتيجية Top-k الملدنة مع خوارزمية SAC، تفوقت DTSemNet على نماذج الشبكات العصبية الأساسية وDTs القائمة على STE في مهام Continuous LunarLander وBipedalWalker، مما يثبت أن التدريب الخالي من التقريب ينتج سياسات متفوقة حتى في التحكم المستمر.

الأهمية والادعاءات
تدعي الورقة أن DTSemNet هي أول بنية تحقق التدريب الخالي من التقريب لأشجار القرار المائلة في كل من مهام التصنيف والانحدار. من خلال إزالة عدم التطابق الدلالي بين التقييم والتحسين، تتغلب على عدم الاستقرار والتحيز في أساليب STE. يرى المؤلفون أن هذا يجسّر الفجوة بين قابلية التفسير للنماذج الرمزية (DTs) وقابلية التوسع للتدريب القائم على التدرج، مما يجعل النماذج عالية الأداء والقابلة للتفسير صالحة للتطبيقات الحساسة للسلامة وبيئات التعلم المعزز المعقدة.

القيود والعمل المستقبلي
يقر المؤلفون بأن DTSemNet، كشجرة قرار، ليست مناسبة للمدخلات عالية الأبعاد مثل الصور، حيث تواجه صعوبة في التعامل مع الأشكال المعقدة. سيركز العمل المستقبلي على تطوير طرق قابلة للتفاضل لنمو الأشجار التكيفي وتقليمها، والابتعاد عن استخدام ارتفاعات الأشجار الثابتة كمعاملات فائقة (hyperparameters).