2025-11-12T13:34:14.831387

Efficient & Correct Predictive Equivalence for Decision Trees

Marques-Silva, Ignatiev

The Rashomon set of decision trees (DTs) finds importance uses. Recent work showed that DTs computing the same classification function, i.e. predictive equivalent DTs, can represent a significant fraction of the Rashomon set. Such redundancy is undesirable. For example, feature importance based on the Rashomon set becomes inaccurate due the existence of predictive equivalent DTs, i.e. DTs with the same prediction for every possible input. In recent work, McTavish et al. proposed solutions for several computational problems related with DTs, including that of deciding predictive equivalent DTs. The approach of McTavish et al. consists of applying the well-known method of Quine-McCluskey (QM) for obtaining minimum-size DNF (disjunctive normal form) representations of DTs, which are then used for comparing DTs for predictive equivalence. Furthermore, the minimum-size DNF representation was also applied to computing explanations for the predictions made by DTs, and to finding predictions in the presence of missing data. However, the problem of formula minimization is hard for the second level of the polynomial hierarchy, and the QM method may exhibit worst-case exponential running time and space. This paper first demonstrates that there exist decision trees that trigger the worst-case exponential running time and space of the QM method. Second, the paper shows that the QM method may incorrectly decide predictive equivalence, if two key constraints are not respected, and one may be difficult to formally guarantee. Third, the paper shows that any of the problems to which the smallest DNF representation has been applied to can be solved in polynomial time, in the size of the DT. The experiments confirm that, for DTs for which the worst-case of the QM method is triggered, the algorithms proposed in this paper are orders of magnitude faster than the ones proposed by McTavish et al.

academic

الكفاءة والصحة في التكافؤ التنبؤي لأشجار القرار

المعلومات الأساسية

معرّف الورقة: 2509.17774
العنوان: الكفاءة والصحة في التكافؤ التنبؤي لأشجار القرار
المؤلفون: João Marques-Silva (ICREA & جامعة Lleida)، Alexey Ignatiev (جامعة Monash)
التصنيف: cs.AI cs.LG cs.LO
وقت النشر/المؤتمر: مجلة أبحاث التعلم الآلي 23 (2025) 1-35
رابط الورقة: https://arxiv.org/abs/2509.17774

الملخص

تتمتع مجموعات Rashomon لأشجار القرار بقيمة تطبيقية مهمة. أظهرت الأبحاث الحديثة أن أشجار القرار التي تحسب نفس دالة التصنيف (أي أشجار القرار المتكافئة تنبؤياً) قد تشكل جزءاً كبيراً من مجموعة Rashomon. هذا التكرار غير مرغوب فيه، على سبيل المثال، أهمية الميزات المستندة إلى مجموعة Rashomon تصبح غير دقيقة بسبب وجود أشجار القرار المتكافئة تنبؤياً. اقترح McTavish وآخرون مؤخراً حلاً لحل المشاكل الحسابية المتعلقة بأشجار القرار، بما في ذلك تحديد أشجار القرار المتكافئة تنبؤياً. تستخدم طريقتهم طريقة Quine-McCluskey (QM) الشهيرة للحصول على تمثيل DNF الأدنى لشجرة القرار، والذي يُستخدم بعد ذلك لمقارنة التكافؤ التنبؤي لأشجار القرار. ومع ذلك، فإن مشكلة تقليل الصيغة صعبة على الطبقة الثانية من التسلسل الهرمي متعدد الحدود، وقد تُظهر طريقة QM تعقيداً زمنياً ومكانياً أسياً في أسوأ الحالات. تثبت هذه الورقة أولاً وجود أشجار قرار تُثير التعقيد الأسي الأسوأ لطريقة QM، وتوضح ثانياً أن طريقة QM قد تحكم بشكل خاطئ على التكافؤ التنبؤي إذا لم تُستوفَ قيدان رئيسيان، وأخيراً تثبت أن جميع المشاكل التي تطبق تمثيل DNF الأدنى يمكن حلها في الوقت متعدد الحدود لحجم شجرة القرار.

الخلفية البحثية والدافع

تعريف المشكلة

المشكلة الأساسية التي تعالجها هذه الورقة هي كفاءة وصحة تحديد التكافؤ التنبؤي لأشجار القرار. أشجار القرار المتكافئة تنبؤياً هي أشجار قرار مختلفة تنتج نفس نتائج التنبؤ لأي إدخال.

أهمية المشكلة

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

قيود الطرق الموجودة

الطريقة المقترحة من قبل McTavish وآخرين بناءً على خوارزمية Quine-McCluskey (QM) لديها المشاكل التالية:

التعقيد الحسابي: تحل طريقة QM مشكلة Σₚ²-hard، وتتطلب وقتاً ومساحة أسية في أسوأ الحالات
مشاكل الصحة: قد تنتج نتائج خاطئة عند عدم استيفاء قيود محددة
الجدوى العملية: من المعروف أن طريقة QM لديها قابلية توسع سيئة للمشاكل التي تحتوي على عشرات المتغيرات

المساهمات الأساسية

التحليل النظري: إثبات وجود أشجار قرار يمكنها تفعيل التعقيد الأسي الأسوأ لطريقة QM
تحليل الصحة: الكشف عن مشاكل عدم الصحة المحتملة في طريقة QM في تحديد التكافؤ التنبؤي
خوارزمية فعالة: اقتراح خوارزمية وقت متعدد الحدود لحل مشاكل الاكتمال والإيجاز والتكافؤ التنبؤي
التحقق التجريبي: على أشجار القرار التي تفعل أسوأ حالات QM، الخوارزمية الجديدة أسرع بعدة رتب من حيث الحجم من الطرق الموجودة
الروابط النظرية: إنشاء روابط نظرية بين التكافؤ التنبؤي والتفسيرات المنطقية وتدابير الأهمية

شرح الطريقة

تعريف المهمة

بالنظر إلى شجري قرار T₁ و T₂، تحديد ما إذا كانا متكافئين تنبؤياً، أي:

∀(x ∈ F). (κₜ₁(x) = κₜ₂(x))

حيث F هي مساحة الميزات، و κ هي دالة التصنيف.

إطار العمل التقني الأساسي

1. طريقة التفسير الضعيف الاستقرائي (WAXp)

تقترح الورقة خوارزمية وقت متعدد الحدود بناءً على WAXp:

الخوارزمية 1: فحص اتساق المسار

def ConsistentPath(A, P, T):
    # فحص اتساق التعيين الجزئي A مع مسار الشجرة P
    for each feature i:
        combine literals from A and P for feature i
        if inconsistent: return False
    return True

الخوارزمية 2: تحديد WAXp

def IsWAXp(A, c, T):
    # تحديد ما إذا كان التعيين الجزئي A هو WAXp للفئة c
    for each path P in T:
        if Class(P) != c and ConsistentPath(A, P, T):
            return False  # A متسق مع مسار فئة أخرى
    return True

2. خوارزمية تحديد التكافؤ التنبؤي

الخوارزمية 5: تحديد التكافؤ التنبؤي

def PredictivelyEquivalent(T1, T2):
    for P1 in Paths(T1):
        c1 = Class(P1)
        A1 = Literals(P1)  # إنشاء تعيين جزئي
        for P2 in Paths(T2):
            c2 = Class(P2)
            if c1 != c2 and ConsistentPath(A1, P2, T2):
                return False  # اكتشاف دليل عدم التكافؤ
    return True  # لا يمكن إثبات عدم التكافؤ، لذلك متكافئ

نقاط الابتكار التقني

تجنب التعقيد الأسي: العمل مباشرة على هيكل شجرة القرار، تجنب إنشاء تمثيل BCF الذي قد يكون بحجم أسي
ضمان الوقت متعدد الحدود: جميع الخوارزميات لها تعقيد زمني متعدد الحدود لحجم شجرة القرار
صحة رسمية: توفير إثبات رياضي صارم يضمن صحة الخوارزمية
قابلية التوازي: يمكن توازي خوارزمية التكافؤ التنبؤي لزيادة الكفاءة

إعداد التجربة

حالات الاختبار المُنشأة

استخدمت الورقة أشجار قرار خاصة مبنية على أساس النظرية 1:

المعامل r: التحكم في تعقيد الشجرة
عدد العقد: 6r + 3 عقدة
عدد الميزات: 2r + 1 ميزة
حجم BCF: للفئة 1، الحد الأدنى هو 2^r من الحدود الأساسية

مؤشرات التقييم

وقت التشغيل: وقت تنفيذ الخوارزمية (بالثواني)
حجم BCF: عدد الحدود الأساسية في نموذج Blake القياسي
قابلية التوسع: القدرة على معالجة أشجار القرار بأحجام مختلفة

طرق المقارنة

تطبيق QM من SymPy: طريقة الأساس المستخدمة من قبل McTavish وآخرين
إنشاء BCF المستقل: خطوة إنشاء الحدود الأساسية QM القياسية المطبقة من قبل المؤلفين

تفاصيل التطبيق

المنصة: معالج Macbook M3 Pro
لغة البرمجة: Python
حد المهلة الزمنية: تم تعيين حد المهلة الزمنية لطريقة QM على 150000 ثانية

نتائج التجربة

النتائج الرئيسية

التحقق من التعقيد الأسي لطريقة QM

r	وقت SymPy (ثانية)	\|BCF₀(T)\|	\|BCF₁(T)\|	وقت BCF (ثانية)
3	0.13	4	22	0.01
4	0.57	5	46	0.07
5	39.60	6	94	0.84
6	2789.45	7	190	11.28
7	>150000.00	8	382	161.25

الأداء الموسع للخوارزمية الجديدة

r	عدد عقد DT	عدد الميزات	\|BCF₁(T)\|	AXp واحد	isWAXp?	PE?
200	1203	401	2²⁰⁰	1.71s	0.005s	3.7s
500	3003	1001	2⁵⁰⁰	26.98s	0.032s	57.1s
1000	6003	2001	2¹⁰⁰⁰	224.62s	0.126s	469.0s

الاكتشافات الرئيسية

تأكيد النمو الأسي: يزداد حجم BCF₁(T) بشكل أسي مع r، مما يتحقق من التحليل النظري
فجوة الأداء الضخمة: بالنسبة لحالة r=200، تحتاج الخوارزمية الجديدة فقط إلى بضع ثوانٍ لمعالجة شجرة قرار بـ 1203 عقدة، بينما تتجاوز طريقة QM المهلة الزمنية عند 57 عقدة
التحقق من الجدوى العملية: يمكن للخوارزمية الجديدة معالجة أشجار القرار الكبيرة التي قد تظهر في التطبيقات الفعلية

الأعمال ذات الصلة

أبحاث مجموعة Rashomon

المفاهيم الأساسية: قدم Breiman (2001) مفهوم مجموعة Rashomon لأول مرة
التطورات الحديثة: أعمال Fisher وآخرين، Semenova وآخرين في مجال أهمية الميزات
التكافؤ التنبؤي: أول دراسة منهجية لـ McTavish وآخرين للتكافؤ التنبؤي لأشجار القرار

الذكاء الاصطناعي القابل للتفسير ذو الأساس المنطقي

التفسيرات الرسمية: أعمال Marques-Silva وآخرين في AXp و CXp
التعقيد الحسابي: أبحاث متعددة تثبت تعقيد حساب التفسيرات
تدابير القابلية للتفسير: تطبيق قيم Shapley و Banzhaf في التعلم الآلي

تقليل الصيغ البوليانية

الطرق الكلاسيكية: التطور التاريخي لخوارزمية Quine-McCluskey
نظرية التعقيد: إنشاء تعقيد Σₚ²-hard
القيود العملية: من المعروف أن طريقة QM تنخفض كفاءتها بشكل حاد عندما يتجاوز عدد المتغيرات 8

الخلاصة والمناقشة

الاستنتاجات الرئيسية

المساهمة النظرية: إثبات أن طريقة QM تواجه بالفعل تعقيداً أسياً على أشجار القرار
المساهمة الخوارزمية: توفير خوارزمية بديلة بوقت متعدد الحدود
القيمة العملية: الخوارزمية الجديدة لها مزايا كبيرة في التطبيقات العملية
الروابط النظرية: إنشاء روابط بين التكافؤ التنبؤي ومفاهيم XAI متعددة

القيود

تطبيق Python: قد يؤثر استخدام Python على القيم المطلقة لتقييم الأداء
البناء الخاص: تركز التجارب بشكل أساسي على أشجار القرار المُنشأة خصيصاً
التوازي: لم يتم التحقق من إمكانات التوازي لخوارزمية التكافؤ التنبؤي على مجموعات كبيرة
العمومية: تحتاج إلى مزيد من التحقق على مجموعات البيانات الفعلية

الاتجاهات المستقبلية

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

التقييم المتعمق

المزايا

الصرامة النظرية: توفير إثبات رياضي كامل وتحليل التعقيد
القيمة العملية العالية: حل المشكلة الأساسية في الأداء للطرق الموجودة
الابتكار القوي: أول تحليل منهجي لمشاكل طريقة QM على أشجار القرار
التجارب الكافية: التحقق من الحالات النظرية المُنشأة والاختبارات على نطاق عملي
الكتابة الواضحة: هيكل الورقة جيد، وتفاصيل تقنية موضحة بوضوح

أوجه القصور

نطاق التجارب: التحقق بشكل أساسي على حالات اختبار مُنشأة، يفتقد نتائج مجموعات البيانات الفعلية
لغة التطبيق: استخدام Python قد لا يكون الخيار الأفضل، مما يؤثر على قوة مقارنة الأداء
التحقق من التطبيق: يفتقد التحقق في مهام تحسين مجموعة Rashomon الفعلية
تحليل قيود QM: تحليل غير كافٍ لقابلية الوصول العملية لقيود صحة طريقة QM

التأثير

القيمة الأكاديمية: توفير أدوات نظرية جديدة لأبحاث أشجار القرار
الأهمية العملية: قد تغير طريقة ممارسة تحليل مجموعة Rashomon
القابلية للتكرار: وصف الخوارزمية واضح، سهل التكرار
القابلية للتوسع: قد تنطبق الطريقة على نماذج قابلة للتفسير أخرى

السيناريوهات المناسبة

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

المراجع

تستشهد هذه الورقة بمجموعة واسعة من الأعمال ذات الصلة، تشمل بشكل أساسي:

مجموعة Rashomon: Breiman (2001)، Xin وآخرون (2022)، Fisher وآخرون (2019)
الذكاء الاصطناعي القابل للتفسير المنطقي: Marques-Silva (2022)، Darwiche (2023)، Ignatiev وآخرون (2019)
تقليل الدوال البوليانية: Quine (1952، 1955)، McCluskey (1956)، Umans (1998)
تحسين أشجار القرار: Bertsimas & Dunn (2017)، Hu وآخرون (2019)، Demirovic وآخرون (2022)

التقييم الشامل: هذه ورقة عالية الجودة تجمع بين النظرية والممارسة، لا تكشف فقط عن العيوب الأساسية في الطرق الموجودة بل توفر أيضاً حلاً عملياً. التحليل النظري للورقة صارم، والتحقق التجريبي كافٍ، وتتمتع بمساهمات مهمة في مجالات أشجار القرار والذكاء الاصطناعي القابل للتفسير.