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

निर्णय वृक्षों के लिए कुशल और सही भविष्यसूचक समतुल्यता

मूल जानकारी

  • पेपर ID: 2509.17774
  • शीर्षक: निर्णय वृक्षों के लिए कुशल और सही भविष्यसूचक समतुल्यता
  • लेखक: João Marques-Silva (ICREA & University of Lleida), Alexey Ignatiev (Monash University)
  • वर्गीकरण: cs.AI cs.LG cs.LO
  • प्रकाशन समय/सम्मेलन: Journal of Machine Learning Research 23 (2025) 1-35
  • पेपर लिंक: https://arxiv.org/abs/2509.17774

सारांश

निर्णय वृक्षों के Rashomon समुच्चय का महत्वपूर्ण अनुप्रयोग मूल्य है। हाल के अनुसंधान से पता चलता है कि समान वर्गीकरण फलन की गणना करने वाले निर्णय वृक्ष (अर्थात् भविष्यसूचक समतुल्य निर्णय वृक्ष) Rashomon समुच्चय का एक बड़ा हिस्सा हो सकते हैं। यह अनावश्यकता अवांछनीय है, उदाहरण के लिए Rashomon समुच्चय पर आधारित विशेषता महत्व भविष्यसूचक समतुल्य निर्णय वृक्षों की उपस्थिति के कारण अनुपयुक्त हो जाता है। McTavish आदि ने हाल ही में निर्णय वृक्षों से संबंधित गणनात्मक समस्याओं को हल करने के लिए एक समाधान प्रस्तावित किया है, जिसमें भविष्यसूचक समतुल्य निर्णय वृक्षों का निर्धारण भी शामिल है। उनकी विधि प्रसिद्ध Quine-McCluskey (QM) विधि का उपयोग करके निर्णय वृक्ष का न्यूनतम DNF प्रतिनिधित्व प्राप्त करती है, जिसका उपयोग निर्णय वृक्षों की भविष्यसूचक समतुल्यता की तुलना के लिए किया जाता है। हालांकि, सूत्र न्यूनीकरण समस्या बहुपद पदानुक्रम के दूसरे स्तर के लिए कठिन है, और QM विधि सबसे खराब स्थिति में घातीय रनटाइम और स्पेस जटिलता प्रदर्शित कर सकती है। यह पेपर पहले साबित करता है कि ऐसे निर्णय वृक्ष मौजूद हैं जो QM विधि की सबसे खराब स्थिति की घातीय जटिलता को ट्रिगर करते हैं, दूसरा दिखाता है कि यदि दो महत्वपूर्ण बाधाओं को पूरा नहीं किया जाता है तो QM विधि भविष्यसूचक समतुल्यता का गलत निर्धारण कर सकती है, और अंत में साबित करता है कि न्यूनतम DNF प्रतिनिधित्व का उपयोग करने वाली सभी समस्याओं को निर्णय वृक्ष आकार के बहुपद समय में हल किया जा सकता है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या परिभाषा

यह पेपर निर्णय वृक्षों की भविष्यसूचक समतुल्यता निर्धारण की दक्षता और सही समस्या को हल करता है। भविष्यसूचक समतुल्य निर्णय वृक्ष वे हैं जो किसी भी इनपुट के लिए समान भविष्यसूचक परिणाम देते हैं।

समस्या का महत्व

  1. Rashomon समुच्चय अनुकूलन: मशीन लर्निंग में, Rashomon समुच्चय में कई समान प्रदर्शन वाले मॉडल होते हैं। भविष्यसूचक समतुल्य निर्णय वृक्ष इस समुच्चय में अनावश्यकता का कारण बनते हैं, जो विशेषता महत्व मूल्यांकन की सटीकता को प्रभावित करता है।
  2. व्याख्यात्मकता आवश्यकता: निर्णय वृक्षों को व्यापक रूप से व्याख्यात्मक मॉडल माना जाता है, लेकिन यहां तक कि इष्टतम निर्णय वृक्षों को भी औपचारिक व्याख्या की आवश्यकता होती है, विशेष रूप से उच्च जोखिम वाले अनुप्रयोग परिदृश्यों में।
  3. गणनात्मक दक्षता: मौजूदा विधियां बड़े पैमाने पर निर्णय वृक्षों को संभालते समय गंभीर गणनात्मक बाधाओं का सामना करती हैं।

मौजूदा विधि की सीमाएं

McTavish आदि द्वारा प्रस्तावित विधि Quine-McCluskey (QM) एल्गोरिथ्म पर आधारित है, जिसमें निम्नलिखित समस्याएं हैं:

  1. गणनात्मक जटिलता: QM विधि Σₚ²-कठिन समस्या को हल करती है, सबसे खराब स्थिति में घातीय समय और स्पेस की आवश्यकता होती है
  2. सही समस्या: विशिष्ट बाधाओं को पूरा न करने पर गलत परिणाम दे सकता है
  3. व्यावहारिक व्यवहार्यता: दर्जनों चर वाली समस्याओं के लिए QM विधि की विस्तारशीलता ज्ञात रूप से खराब है

मुख्य योगदान

  1. सैद्धांतिक विश्लेषण: साबित किया कि ऐसे निर्णय वृक्ष मौजूद हैं जो QM विधि की सबसे खराब स्थिति की घातीय जटिलता को ट्रिगर करते हैं
  2. सही समस्या विश्लेषण: भविष्यसूचक समतुल्यता निर्धारण में QM विधि की संभावित अशुद्धता को उजागर किया
  3. कुशल एल्गोरिथ्म: पूर्णता, संक्षिप्तता और भविष्यसूचक समतुल्यता निर्धारण समस्याओं को हल करने के लिए बहुपद समय एल्गोरिथ्म प्रस्तावित किया
  4. प्रायोगिक सत्यापन: QM की सबसे खराब स्थिति को ट्रिगर करने वाले निर्णय वृक्षों पर, नया एल्गोरिथ्म मौजूदा विधि से कई परिमाण तेज है
  5. सैद्धांतिक संबंध: भविष्यसूचक समतुल्यता और तार्किक व्याख्या, महत्व उपायों के बीच सैद्धांतिक संबंध स्थापित किया

विधि विवरण

कार्य परिभाषा

दो निर्णय वृक्षों 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 वर्ग c के लिए WAXp है
    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  # असमानता साबित नहीं की जा सकी, इसलिए समतुल्य

तकनीकी नवाचार बिंदु

  1. घातीय जटिलता से बचना: संभावित रूप से घातीय आकार के BCF प्रतिनिधित्व को उत्पन्न करने से बचते हुए निर्णय वृक्ष संरचना पर सीधे काम करना
  2. बहुपद समय गारंटी: सभी एल्गोरिथ्म की समय जटिलता निर्णय वृक्ष आकार की बहुपद है
  3. औपचारिक सही समस्या: एल्गोरिथ्म सही समस्या की गारंटी के लिए कठोर गणितीय प्रमाण प्रदान करता है
  4. समांतरकरणीय: भविष्यसूचक समतुल्यता एल्गोरिथ्म को समांतरित किया जा सकता है, जिससे दक्षता में और वृद्धि होती है

प्रायोगिक सेटअप

निर्मित परीक्षण मामले

पेपर प्रमेय 1 के प्रमाण पर आधारित विशेष निर्णय वृक्ष निर्माण का उपयोग करता है:

  • पैरामीटर r: वृक्ष की जटिलता को नियंत्रित करता है
  • नोड संख्या: 6r + 3 नोड्स
  • विशेषता संख्या: 2r + 1 विशेषताएं
  • BCF आकार: वर्ग 1 के लिए, 2^r प्रमुख निहितार्थ पदों का निचला सीमा

मूल्यांकन मेट्रिक्स

  1. रनटाइम: एल्गोरिथ्म निष्पादन समय (सेकंड)
  2. BCF आकार: Blake मानक रूप में प्रमुख निहितार्थ पदों की संख्या
  3. विस्तारशीलता: विभिन्न आकार के निर्णय वृक्षों को संभालने की क्षमता

तुलना विधियां

  • SymPy का QM कार्यान्वयन: McTavish आदि द्वारा उपयोग की जाने वाली बेंचमार्क विधि
  • स्वतंत्र BCF पीढ़ी: लेखकों द्वारा कार्यान्वित मानक QM प्रमुख निहितार्थ पद पीढ़ी चरण

कार्यान्वयन विवरण

  • प्लेटफॉर्म: Macbook M3 Pro प्रोसेसर
  • प्रोग्रामिंग भाषा: Python
  • टाइमआउट सेटिंग: QM विधि के लिए 150000 सेकंड टाइमआउट सीमा

प्रायोगिक परिणाम

मुख्य परिणाम

QM विधि की घातीय जटिलता सत्यापन

rSymPy समय(s)|BCF₀(T)||BCF₁(T)|BCF समय(s)
30.134220.01
40.575460.07
539.606940.84
62789.45719011.28
7>150000.008382161.25

नए एल्गोरिथ्म की विस्तारशीलता क्षमता

rDT नोड्सविशेषताएं|BCF₁(T)|एक AXpisWAXp?PE?
20012034012²⁰⁰1.71s0.005s3.7s
500300310012⁵⁰⁰26.98s0.032s57.1s
1000600320012¹⁰⁰⁰224.62s0.126s469.0s

मुख्य निष्कर्ष

  1. घातीय वृद्धि की पुष्टि: BCF₁(T) का आकार r के साथ घातीय रूप से बढ़ता है, जो सैद्धांतिक विश्लेषण को सत्यापित करता है
  2. विशाल प्रदर्शन अंतर: r=200 के मामले में, नया एल्गोरिथ्म 1203 नोड्स वाले निर्णय वृक्ष को केवल कुछ सेकंड में संभालता है, जबकि QM विधि 57 नोड्स पर टाइमआउट हो जाती है
  3. व्यावहारिक सत्यापन: नया एल्गोरिथ्म वास्तविक अनुप्रयोगों में हो सकने वाले बड़े पैमाने पर निर्णय वृक्षों को संभाल सकता है

संबंधित कार्य

Rashomon समुच्चय अनुसंधान

  • मूल अवधारणा: Breiman (2001) द्वारा पहली बार Rashomon समुच्चय अवधारणा प्रस्तावित
  • हाल का विकास: Fisher आदि, Semenova आदि द्वारा विशेषता महत्व पर काम
  • भविष्यसूचक समतुल्यता: McTavish आदि द्वारा निर्णय वृक्षों की भविष्यसूचक समतुल्यता का पहली बार व्यवस्थित अनुसंधान

तार्किक आधार व्याख्यात्मक AI

  • औपचारिक व्याख्या: Marques-Silva आदि द्वारा AXp और CXp पर काम
  • गणनात्मक जटिलता: कई अनुसंधान द्वारा व्याख्या गणना की जटिलता का प्रमाण
  • व्याख्यात्मकता उपाय: मशीन लर्निंग में Shapley मान और Banzhaf मान का अनुप्रयोग

बूलियन सूत्र न्यूनीकरण

  • शास्त्रीय विधि: Quine-McCluskey एल्गोरिथ्म का ऐतिहासिक विकास
  • जटिलता सिद्धांत: Σₚ²-कठिन जटिलता की स्थापना
  • व्यावहारिक सीमाएं: QM विधि की दक्षता 8 से अधिक चर वाली समस्याओं में तेजी से गिरती है

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. सैद्धांतिक योगदान: साबित किया कि QM विधि निर्णय वृक्षों पर वास्तव में घातीय जटिलता का सामना करती है
  2. एल्गोरिथ्म योगदान: बहुपद समय का विकल्प एल्गोरिथ्म प्रदान किया
  3. व्यावहारिक मूल्य: नया एल्गोरिथ्म वास्तविक अनुप्रयोगों में महत्वपूर्ण लाभ प्रदान करता है
  4. सैद्धांतिक संबंध: भविष्यसूचक समतुल्यता और कई XAI अवधारणाओं के बीच संबंध स्थापित किया

सीमाएं

  1. Python कार्यान्वयन: प्रयोग Python का उपयोग करते हैं जो प्रदर्शन मूल्यांकन के पूर्ण मूल्यों को प्रभावित कर सकता है
  2. विशेष निर्माण: प्रयोग मुख्य रूप से विशेष निर्मित निर्णय वृक्षों पर केंद्रित हैं
  3. समांतरकरण: भविष्यसूचक समतुल्यता एल्गोरिथ्म की समांतरकरण क्षमता बड़े पैमाने पर क्लस्टरों पर सत्यापित नहीं की गई है
  4. सामान्यता: वास्तविक डेटासेट पर अधिक सत्यापन की आवश्यकता है

भविष्य की दिशाएं

  1. स्पर्शोन्मुख इष्टतम एल्गोरिथ्म: सैद्धांतिक रूप से इष्टतम एल्गोरिथ्म की खोज
  2. अन्य मॉडल प्रकार: विधि को अन्य व्याख्यात्मक मॉडलों तक विस्तारित करना
  3. व्यावहारिक अनुप्रयोग: वास्तविक Rashomon समुच्चय अनुकूलन कार्यों में अनुप्रयोग
  4. समांतर कार्यान्वयन: बड़े पैमाने पर समांतर कार्यान्वयन का विकास

गहन मूल्यांकन

शक्तियां

  1. सैद्धांतिक कठोरता: पूर्ण गणितीय प्रमाण और जटिलता विश्लेषण प्रदान करता है
  2. उच्च व्यावहारिक मूल्य: मौजूदा विधि की मौलिक प्रदर्शन समस्या को हल करता है
  3. मजबूत नवाचार: पहली बार निर्णय वृक्षों पर QM विधि की समस्याओं का व्यवस्थित विश्लेषण
  4. पर्याप्त प्रयोग: सैद्धांतिक निर्माण सत्यापन और वास्तविक पैमाने पर परीक्षण दोनों
  5. स्पष्ट लेखन: अच्छी संरचना वाला पेपर, तकनीकी विवरण स्पष्ट रूप से वर्णित

कमियां

  1. प्रयोग की सीमा: मुख्य रूप से निर्मित परीक्षण मामलों पर सत्यापन, वास्तविक डेटासेट परिणामों की कमी
  2. कार्यान्वयन भाषा: Python सर्वोत्तम विकल्प नहीं हो सकता है, प्रदर्शन तुलना की विश्वसनीयता को प्रभावित करता है
  3. अनुप्रयोग सत्यापन: वास्तविक Rashomon समुच्चय अनुकूलन कार्यों में सत्यापन की कमी
  4. QM बाधा विश्लेषण: QM विधि सही समस्या बाधाओं की व्यावहारिक प्राप्यता का विश्लेषण पर्याप्त नहीं है

प्रभाव

  1. शैक्षणिक मूल्य: निर्णय वृक्ष अनुसंधान के लिए नए सैद्धांतिक उपकरण प्रदान करता है
  2. व्यावहारिक महत्व: Rashomon समुच्चय विश्लेषण के व्यावहारिक विधि को बदल सकता है
  3. पुनरुत्पादनीयता: एल्गोरिथ्म विवरण स्पष्ट है, पुनरुत्पादन में आसान
  4. विस्तारशीलता: विधि अन्य व्याख्यात्मक मॉडलों पर लागू हो सकती है

लागू परिदृश्य

  1. उच्च जोखिम अनुप्रयोग: व्याख्यात्मक AI की आवश्यकता वाले चिकित्सा, वित्त आदि क्षेत्र
  2. मॉडल चयन: कई समतुल्य मॉडलों में से चयन की आवश्यकता वाले परिदृश्य
  3. विशेषता महत्व विश्लेषण: विशेषता महत्व का सटीक मूल्यांकन आवश्यक अनुप्रयोग
  4. बड़े पैमाने पर निर्णय वृक्ष: जटिल निर्णय वृक्षों को संभालने वाले औद्योगिक अनुप्रयोग

संदर्भ

यह पेपर व्यापक संबंधित कार्यों का हवाला देता है, मुख्य रूप से:

  1. Rashomon समुच्चय: Breiman (2001), Xin et al. (2022), Fisher et al. (2019)
  2. तार्किक व्याख्यात्मक AI: Marques-Silva (2022), Darwiche (2023), Ignatiev et al. (2019)
  3. बूलियन फलन न्यूनीकरण: Quine (1952, 1955), McCluskey (1956), Umans (1998)
  4. निर्णय वृक्ष अनुकूलन: Bertsimas & Dunn (2017), Hu et al. (2019), Demirovic et al. (2022)

समग्र मूल्यांकन: यह सिद्धांत और व्यावहार के संयोजन वाला एक उच्च गुणवत्ता वाला पेपर है, जो न केवल मौजूदा विधि की मौलिक खामियों को उजागर करता है बल्कि व्यावहारिक समाधान भी प्रदान करता है। पेपर का सैद्धांतिक विश्लेषण कठोर है, प्रायोगिक सत्यापन पर्याप्त है, और निर्णय वृक्ष और व्याख्यात्मक AI क्षेत्र में महत्वपूर्ण योगदान देता है।