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 & 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

সারসংক্ষেপ

সিদ্ধান্ত গাছের রাশোমন সংগ্রহের গুরুত্বপূর্ণ প্রয়োগ মূল্য রয়েছে। সাম্প্রতিক গবেষণা দেখায় যে একই শ্রেণীবিভাগ ফাংশন সম্পাদনকারী সিদ্ধান্ত গাছগুলি (অর্থাৎ পূর্বাভাসমূলক সমতুল্য সিদ্ধান্ত গাছ) রাশোমন সংগ্রহের একটি বড় অংশ গঠন করতে পারে। এই অপ্রয়োজনীয়তা অনাকাঙ্ক্ষিত, উদাহরণস্বরূপ রাশোমন সংগ্রহের উপর ভিত্তি করে বৈশিষ্ট্য গুরুত্ব পূর্বাভাসমূলক সমতুল্য সিদ্ধান্ত গাছের উপস্থিতির কারণে অনির্ভুল হয়ে ওঠে। ম্যাকটাভিশ এবং অন্যরা সম্প্রতি সিদ্ধান্ত গাছ সম্পর্কিত গণনামূলক সমস্যা সমাধানের জন্য একটি পদ্ধতি প্রস্তাব করেছেন, যার মধ্যে পূর্বাভাসমূলক সমতুল্য সিদ্ধান্ত গাছ নির্ধারণ অন্তর্ভুক্ত। তাদের পদ্ধতি বিখ্যাত কুইন-ম্যাককলাস্কি (QM) পদ্ধতি ব্যবহার করে সিদ্ধান্ত গাছের ন্যূনতম DNF প্রতিনিধিত্ব পেতে, যা পরে সিদ্ধান্ত গাছের পূর্বাভাসমূলক সমতুল্যতা তুলনা করতে ব্যবহৃত হয়। তবে সূত্র ন্যূনতমকরণ সমস্যা বহুপদী শ্রেণীবিভাগের দ্বিতীয় স্তরের জন্য কঠিন, এবং QM পদ্ধতি সর্বোচ্চ ক্ষেত্রে সূচকীয় চলমান সময় এবং স্থান জটিলতা প্রদর্শন করতে পারে। এই পত্রটি প্রথমে প্রমাণ করে যে QM পদ্ধতির সর্বোচ্চ ক্ষেত্রে সূচকীয় জটিলতা ট্রিগার করে এমন সিদ্ধান্ত গাছ বিদ্যমান, দ্বিতীয়ত দেখায় যে দুটি মূল সীমাবদ্ধতা পূরণ না হলে QM পদ্ধতি পূর্বাভাসমূলক সমতুল্যতা ভুলভাবে বিচার করতে পারে, এবং অবশেষে প্রমাণ করে যে সমস্ত প্রয়োগকৃত ন্যূনতম DNF প্রতিনিধিত্ব সমস্যা সিদ্ধান্ত গাছ আকারের বহুপদী সময়ে সমাধান করা যায়।

গবেষণা পটভূমি এবং প্রেরণা

সমস্যা সংজ্ঞা

এই পত্রটি যে মূল সমস্যাটি সমাধান করে তা হল সিদ্ধান্ত গাছ পূর্বাভাসমূলক সমতুল্যতা বিচার এর দক্ষতা এবং সঠিকতার সমস্যা। পূর্বাভাসমূলক সমতুল্য সিদ্ধান্ত গাছগুলি হল বিভিন্ন সিদ্ধান্ত গাছ যা যেকোনো ইনপুটের জন্য একই পূর্বাভাস ফলাফল উৎপাদন করে।

সমস্যার গুরুত্ব

রাশোমন সংগ্রহ অপ্টিমাইজেশন: মেশিন লার্নিংয়ে, রাশোমন সংগ্রহে একাধিক কর্মক্ষমতা-সমান মডেল রয়েছে। পূর্বাভাসমূলক সমতুল্য সিদ্ধান্ত গাছগুলি সেই সংগ্রহে অপ্রয়োজনীয়তা সৃষ্টি করে, বৈশিষ্ট্য গুরুত্ব মূল্যায়নের নির্ভুলতা প্রভাবিত করে।
ব্যাখ্যাযোগ্যতার প্রয়োজনীয়তা: সিদ্ধান্ত গাছগুলি ব্যাপকভাবে ব্যাখ্যাযোগ্য মডেল হিসাবে স্বীকৃত, তবে সর্বোত্তম সিদ্ধান্ত গাছগুলিও আনুষ্ঠানিক ব্যাখ্যার প্রয়োজন, বিশেষত উচ্চ-ঝুঁকি প্রয়োগের পরিস্থিতিতে।
গণনামূলক দক্ষতা: বিদ্যমান পদ্ধতিগুলি বড় আকারের সিদ্ধান্ত গাছ পরিচালনা করার সময় গুরুতর গণনামূলক বাধার সম্মুখীন হয়।

বিদ্যমান পদ্ধতির সীমাবদ্ধতা

ম্যাকটাভিশ এবং অন্যদের দ্বারা প্রস্তাবিত পদ্ধতি কুইন-ম্যাককলাস্কি (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 শ্রেণী 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  # অসমতুল্যতা প্রমাণ করতে পারে না, তাই সমতুল্য

প্রযুক্তিগত উদ্ভাবন পয়েন্ট

সূচকীয় জটিলতা এড়ানো: সরাসরি সিদ্ধান্ত গাছ কাঠামোতে কাজ করুন, সম্ভাব্য সূচকীয় আকারের BCF প্রতিনিধিত্ব উৎপাদন এড়ান
বহুপদী সময় গ্যারান্টি: সমস্ত অ্যালগরিদমের সময় জটিলতা সিদ্ধান্ত গাছ আকারের বহুপদী
আনুষ্ঠানিক সঠিকতা: অ্যালগরিদম সঠিকতা নিশ্চিত করার জন্য কঠোর গাণিতিক প্রমাণ প্রদান করুন
সমান্তরালযোগ্য: পূর্বাভাসমূলক সমতুল্যতা অ্যালগরিদম সমান্তরালযোগ্য, আরও দক্ষতা উন্নত করুন

পরীক্ষামূলক সেটআপ

নির্মিত পরীক্ষার ক্ষেত্রে

পত্রটি উপপাদ্য 1 প্রমাণের উপর ভিত্তি করে বিশেষ সিদ্ধান্ত গাছ নির্মাণ ব্যবহার করে:

প্যারামিটার r: গাছের জটিলতা নিয়ন্ত্রণ করুন
নোড সংখ্যা: 6r + 3 নোড
বৈশিষ্ট্য সংখ্যা: 2r + 1 বৈশিষ্ট্য
BCF আকার: শ্রেণী 1 এর জন্য, 2^r প্রধান অন্তর্ভুক্তির নিম্ন সীমা

মূল্যায়ন মেট্রিক্স

চলমান সময়: অ্যালগরিদম সম্পাদন সময় (সেকেন্ড)
BCF আকার: Blake স্ট্যান্ডার্ড ফর্মে প্রধান অন্তর্ভুক্তির সংখ্যা
স্কেলেবিলিটি: বিভিন্ন আকারের সিদ্ধান্ত গাছ পরিচালনা করার ক্ষমতা

তুলনা পদ্ধতি

SymPy এর QM বাস্তবায়ন: ম্যাকটাভিশ এবং অন্যরা ব্যবহৃত বেঞ্চমার্ক পদ্ধতি
স্বাধীন BCF প্রজন্ম: লেখক দ্বারা বাস্তবায়িত মান QM প্রধান অন্তর্ভুক্তি প্রজন্ম পদক্ষেপ

বাস্তবায়ন বিবরণ

প্ল্যাটফর্ম: Macbook M3 Pro প্রসেসর
প্রোগ্রামিং ভাষা: Python
সময়সীমা সেটিং: QM পদ্ধতি 150000 সেকেন্ড সময়সীমা সেট করুন

পরীক্ষামূলক ফলাফল

প্রধান ফলাফল

QM পদ্ধতির সূচকীয় জটিলতা যাচাইকরণ

r	SymPy সময়(s)	\|BCF₀(T)\|	\|BCF₁(T)\|	BCF সময়(s)
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 নোডে সময়সীমা অতিক্রম করে
ব্যবহারিক সম্ভাব্যতা যাচাইকরণ: নতুন অ্যালগরিদম বাস্তব প্রয়োগে ঘটতে পারে এমন বড় আকারের সিদ্ধান্ত গাছ পরিচালনা করতে পারে

উপসংহার এবং আলোচনা

প্রধান উপসংহার

তাত্ত্বিক অবদান: প্রমাণ করে যে QM পদ্ধতি সিদ্ধান্ত গাছে সূচকীয় জটিলতার সম্মুখীন হয়
অ্যালগরিদম অবদান: বহুপদী সময়ের বিকল্প অ্যালগরিদম প্রদান করে
ব্যবহারিক মূল্য: নতুন অ্যালগরিদম বাস্তব প্রয়োগে উল্লেখযোগ্য সুবিধা রয়েছে
তাত্ত্বিক সংযোগ: পূর্বাভাসমূলক সমতুল্যতা এবং একাধিক XAI ধারণার মধ্যে সংযোগ স্থাপন করে

সীমাবদ্ধতা

Python বাস্তবায়ন: পরীক্ষা Python ব্যবহার করে কর্মক্ষমতা মূল্যায়নের পরম মূল্য প্রভাবিত করতে পারে
বিশেষ নির্মাণ: পরীক্ষা প্রধানত বিশেষভাবে নির্মিত সিদ্ধান্ত গাছে ফোকাস করে
সমান্তরালকরণ: পূর্বাভাসমূলক সমতুল্যতা অ্যালগরিদমের সমান্তরালকরণ সম্ভাবনা বড় ক্লাস্টারে যাচাই করা হয়নি
সাধারণতা: বাস্তব ডেটাসেটে আরও যাচাইকরণ প্রয়োজন

ভবিষ্যত দিকনির্দেশনা

অ্যাসিম্পটোটিকভাবে সর্বোত্তম অ্যালগরিদম: তাত্ত্বিকভাবে সর্বোত্তম অ্যালগরিদম খুঁজে বের করুন
অন্যান্য মডেল প্রকার: পদ্ধতি অন্যান্য ব্যাখ্যাযোগ্য মডেলে প্রসারিত করুন
বাস্তব প্রয়োগ: বাস্তব রাশোমন সংগ্রহ অপ্টিমাইজেশনে প্রয়োগ
সমান্তরাল বাস্তবায়ন: বড় আকারের সমান্তরাল বাস্তবায়ন উন্নয়ন

গভীর মূল্যায়ন

সুবিধা

তাত্ত্বিক কঠোরতা: সম্পূর্ণ গাণিতিক প্রমাণ এবং জটিলতা বিশ্লেষণ প্রদান করে
উচ্চ ব্যবহারিক মূল্য: বিদ্যমান পদ্ধতির মৌলিক কর্মক্ষমতা সমস্যা সমাধান করে
শক্তিশালী উদ্ভাবন: প্রথমবার সিদ্ধান্ত গাছে QM পদ্ধতির সমস্যা পদ্ধতিগতভাবে বিশ্লেষণ করে
পর্যাপ্ত পরীক্ষা: তাত্ত্বিক নির্মাণের যাচাইকরণ এবং বাস্তব আকারের পরীক্ষা উভয়ই রয়েছে
স্পষ্ট লেখা: পত্রটি ভালভাবে কাঠামোগত, প্রযুক্তিগত বিবরণ স্পষ্টভাবে বর্ণিত

অপূর্ণতা

পরীক্ষার পরিসীমা: প্রধানত নির্মিত পরীক্ষার ক্ষেত্রে যাচাই, বাস্তব ডেটাসেট ফলাফল অনুপস্থিত
বাস্তবায়ন ভাষা: Python সর্বোত্তম পছন্দ নাও হতে পারে, কর্মক্ষমতা তুলনার প্রভাবশীলতা প্রভাবিত করে
প্রয়োগ যাচাইকরণ: বাস্তব রাশোমন সংগ্রহ অপ্টিমাইজেশন কাজে যাচাইকরণ অনুপস্থিত
QM সীমাবদ্ধতা বিশ্লেষণ: QM পদ্ধতির সঠিকতা সীমাবদ্ধতার ব্যবহারিক অর্জনযোগ্যতা বিশ্লেষণ যথেষ্ট গভীর নয়

প্রভাব

একাডেমিক মূল্য: সিদ্ধান্ত গাছ গবেষণার জন্য নতুন তাত্ত্বিক সরঞ্জাম প্রদান করে
ব্যবহারিক তাৎপর্য: রাশোমন সংগ্রহ বিশ্লেষণের ব্যবহারিক পদ্ধতি পরিবর্তন করতে পারে
পুনরুৎপাদনযোগ্যতা: অ্যালগরিদম বর্ণনা স্পষ্ট, পুনরুৎপাদন করা সহজ
সম্প্রসারণযোগ্যতা: পদ্ধতি অন্যান্য ব্যাখ্যাযোগ্য মডেলে প্রযোজ্য হতে পারে

প্রযোজ্য পরিস্থিতি

উচ্চ-ঝুঁকি প্রয়োগ: ব্যাখ্যাযোগ্য AI প্রয়োজনীয় চিকিৎসা, আর্থিক এবং অন্যান্য ক্ষেত্র
মডেল নির্বাচন: একাধিক সমতুল্য মডেল থেকে নির্বাচন করার প্রয়োজনীয় পরিস্থিতি
বৈশিষ্ট্য গুরুত্ব বিশ্লেষণ: বৈশিষ্ট্য গুরুত্ব সঠিকভাবে মূল্যায়নের প্রয়োজনীয় প্রয়োগ
বড় আকারের সিদ্ধান্ত গাছ: জটিল সিদ্ধান্ত গাছ পরিচালনার শিল্প প্রয়োগ

সংদর্ভ

এই পত্রটি ব্যাপক সম্পর্কিত কাজ উদ্ধৃত করে, প্রধানত অন্তর্ভুক্ত:

রাশোমন সংগ্রহ: Breiman (2001), Xin et al. (2022), Fisher et al. (2019)
যুক্তিগত ব্যাখ্যাযোগ্যতা AI: Marques-Silva (2022), Darwiche (2023), Ignatiev et al. (2019)
বুলিয়ান ফাংশন ন্যূনতমকরণ: Quine (1952, 1955), McCluskey (1956), Umans (1998)
সিদ্ধান্ত গাছ অপ্টিমাইজেশন: Bertsimas & Dunn (2017), Hu et al. (2019), Demirovic et al. (2022)

সামগ্রিক মূল্যায়ন: এটি একটি উচ্চ মানের তাত্ত্বিক এবং ব্যবহারিক সমন্বিত পত্র, যা শুধুমাত্র বিদ্যমান পদ্ধতির মৌলিক ত্রুটি প্রকাশ করে না বরং ব্যবহারিক সমাধানও প্রদান করে। পত্রটির তাত্ত্বিক বিশ্লেষণ কঠোর, পরীক্ষামূলক যাচাইকরণ পর্যাপ্ত, এবং সিদ্ধান্ত গাছ এবং ব্যাখ্যাযোগ্য AI ক্ষেত্রে গুরুত্বপূর্ণ অবদান রয়েছে।