2025-11-15T14:04:11.886865

Probabilistic Explanations for Linear Models

Subercaseaux, Arenas, Meel
Formal XAI is an emerging field that focuses on providing explanations with mathematical guarantees for the decisions made by machine learning models. A significant amount of work in this area is centered on the computation of "sufficient reasons". Given a model $M$ and an input instance $\vec{x}$, a sufficient reason for the decision $M(\vec{x})$ is a subset $S$ of the features of $\vec{x}$ such that for any instance $\vec{z}$ that has the same values as $\vec{x}$ for every feature in $S$, it holds that $M(\vec{x}) = M(\vec{z})$. Intuitively, this means that the features in $S$ are sufficient to fully justify the classification of $\vec{x}$ by $M$. For sufficient reasons to be useful in practice, they should be as small as possible, and a natural way to reduce the size of sufficient reasons is to consider a probabilistic relaxation; the probability of $M(\vec{x}) = M(\vec{z})$ must be at least some value $δ\in (0,1]$, for a random instance $\vec{z}$ that coincides with $\vec{x}$ on the features in $S$. Computing small $δ$-sufficient reasons ($δ$-SRs) is known to be a theoretically hard problem; even over decision trees--traditionally deemed simple and interpretable models--strong inapproximability results make the efficient computation of small $δ$-SRs unlikely. We propose the notion of $(δ, ε)$-SR, a simple relaxation of $δ$-SRs, and show that this kind of explanation can be computed efficiently over linear models.
academic

شروح احتمالية للنماذج الخطية

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

  • معرّف الورقة: 2501.00154
  • العنوان: Probabilistic Explanations for Linear Models
  • المؤلفون: برناردو سوبيركاسيو (جامعة كارنيجي ميلون)، مارسيلو أرينا (جامعة بابلوفيا الكاثوليكية بتشيلي، IMFD تشيلي، RelationalAI)، كولديب إس. ميل (معهد جورجيا للتكنولوجيا، جامعة تورنتو)
  • التصنيف: cs.AI (الذكاء الاصطناعي)، cs.CC (التعقيد الحسابي)
  • تاريخ النشر: 3 يناير 2025
  • رابط الورقة: https://arxiv.org/abs/2501.00154

الملخص

تبحث هذه الورقة مشكلة حساب "الأسباب الكافية" في الذكاء الاصطناعي القابل للتفسير الرسمي (Formal XAI). بالنظر إلى نموذج M وعينة إدخال x، فإن السبب الكافي هو مجموعة فرعية S من الميزات بحيث أن أي عينة z متطابقة مع x على S لديها M(x)=M(z). لتقليل حجم الأسباب الكافية، يأخذ المؤلفون في الاعتبار تخفيفاً احتمالياً: يتطلب أن تكون احتمالية M(x)=M(z) عندما تتطابق عينة عشوائية z مع x على مجموعة الميزات على الأقل δ∈(0,1]. حساب الأسباب الكافية δ-الصغيرة (δ-SRs) صعب نظرياً، حتى بالنسبة للنماذج "القابلة للتفسير" مثل أشجار القرار. تقدم الورقة مفهوم (δ,ε)-SR، وهو تخفيف بسيط لـ δ-SRs، وتثبت أن هذه الشروح يمكن حسابها بكفاءة على النماذج الخطية.

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

  1. المشكلة الأساسية: كيفية توفير شروح صغيرة الحجم بضمانات رياضية لقرارات نماذج التعلم الآلي. تتطلب الأسباب الكافية التقليدية 100% من اليقين، لكن هذا غالباً ما يؤدي إلى شروح كبيرة جداً وغير مناسبة للفهم البشري.
  2. أهمية المشكلة:
    • أشار ميلر (1956) إلى أن الشروح التي تتجاوز 9 ميزات قد تكون كبيرة جداً على البشر
    • تشير الدراسات التجريبية إلى أن الشروح يجب أن تكون موجزة (Narayanan et al., 2018; Lage et al., 2019)
    • في التطبيقات العملية، يهتم المستخدمون بحجم الشرح أكثر من الاختلافات الطفيفة في الضمانات الاحتمالية
  3. قيود الطرق الموجودة:
    • حساب الحد الأدنى من δ-SRs هو NP-hard حتى بالنسبة لأشجار القرار
    • بالنسبة للنماذج الخطية، الحساب الدقيق للاحتمالية هو #P-hard
    • توجد نتائج قوية لعدم القابلية للتقريب: لا يمكن الحصول على نسب تقريب جيدة في الوقت متعدد الحدود
  4. الدافع البحثي:
    • حساسية المستخدمين لحجم الشرح أعلى من حساسيتهم للتغييرات الطفيفة في الضمانات الاحتمالية
    • الحاجة إلى إيجاد توازن بين القابلية النظرية للمعالجة والعملية
    • قد تسمح البنية الخاصة للنماذج الخطية بخوارزميات فعالة

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

  1. تقديم مفهوم (δ,ε)-الحد الأدنى من الأسباب الكافية: نسخة مخففة تسمح بتغيير الضمانات الاحتمالية ضمن النطاق δ-ε, δ+ε
  2. إثبات القابلية للمعالجة على النماذج الخطية: توفير خوارزمية زمن متعدد الحدود لحساب (δ,ε)-min-SR بوقت تشغيل Õ(n/ε²δ²)
  3. إنشاء نتائج فصل نظرية: إثبات أن هذه المشكلة تبقى صعبة على أشجار القرار، مما يبرز الخصوصية للنماذج الخطية
  4. إثبات التكافؤ الأمثل المحلي: بالنسبة للنماذج الخطية، كل δ-SR محلي أمثل هو δ-SR أمثل بالنسبة للمجموعة الفرعية
  5. تحليل فجوة التقريب: إثبات أن التغييرات الصغيرة في المعاملات الاحتمالية قد تؤدي إلى اختلافات أسية في حجم الشرح

شرح الطريقة

تعريف المهمة

الإدخال:

  • نموذج خطي L=(w,θ)\mathcal{L} = (\mathbf{w}, \theta)، حيث w∈Qn\mathbf{w} \in \mathbb{Q}^n، θ∈Q\theta \in \mathbb{Q}
  • عينة x∈{0,1}n\mathbf{x} \in \{0,1\}^n
  • عتبة احتمالية δ∈(0,1)\delta \in (0,1) وتسامح خطأ ε∈(0,1)\varepsilon \in (0,1)

الإخراج:

  • قيمة δ∗∈[δ−ε,δ+ε]\delta^* \in [\delta-\varepsilon, \delta+\varepsilon]
  • الحد الأدنى من δ∗\delta^*-السبب الكافي y\mathbf{y}

القيود:

  • L(x)=1\mathcal{L}(\mathbf{x}) = 1 إذا وفقط إذا x⋅w≥θ\mathbf{x} \cdot \mathbf{w} \geq \theta
  • عينة جزئية y⊑x\mathbf{y} \sqsubseteq \mathbf{x} تستخدم ⋆\star للإشارة إلى القيم غير المعروفة

معمارية النموذج

1. آلية تقييم الميزات

بالنسبة للنموذج الخطي L=(w,θ)\mathcal{L} = (\mathbf{w}, \theta) والعينة x\mathbf{x}، يُعرّف تقييم الميزة ii على النحو التالي:

si=wi⋅(2xi−1)⋅(2L(x)−1)s_i = w_i \cdot (2x_i - 1) \cdot (2\mathcal{L}(\mathbf{x}) - 1)

تشير إشارة التقييم إلى ما إذا كانت الميزة "تساعد" (+1) أم "تضر" (-1) التصنيف، والحجم يتناسب مع وزن الميزة.

2. اختيار الميزات الجشع

اللمة الأساسية: بالنسبة للنماذج الخطية، تحت التوزيع المنتظم، اختيار الميزات بترتيب تقييم تنازلي هو الأمثل.

بشكل محدد، إذا كانت y(0),…,y(n)\mathbf{y}^{(0)}, \ldots, \mathbf{y}^{(n)} عينات جزئية محددة بواسطة أفضل k ميزة بأعلى تقييم، إذاً:

Pr⁡z∼U(y(k+1))[L(z)=L(x)]≥Pr⁡z∼U(y(k))[L(z)=L(x)]\Pr_{z \sim U(\mathbf{y}^{(k+1)})}[\mathcal{L}(z) = \mathcal{L}(\mathbf{x})] \geq \Pr_{z \sim U(\mathbf{y}^{(k)})}[\mathcal{L}(z) = \mathcal{L}(\mathbf{x})]

3. تقدير مونت كارلو

استخدام عدم المساواة Hoeffding لتقدير الاحتمالية:

بالنسبة لـ m=log⁡2n2ε2δ2log⁡2log⁡nβm = \frac{\log 2n}{2\varepsilon^2\delta^2} \log\frac{2\log n}{\beta} عينة، لدينا:

Pr⁡[∣p^(m)−p∣≤εδ/log⁡n]≥1−β/log⁡n\Pr[|\hat{p}(m) - p| \leq \varepsilon\delta/\log n] \geq 1 - \beta/\log n

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

  1. عتبة احتمالية عشوائية: تختار الخوارزمية عشوائياً δ∗∼U([δ−ε,δ+ε])\delta^* \sim U([\delta-\varepsilon, \delta+\varepsilon])، مما يتجنب الحالات الصعبة
  2. استراتيجية البحث الثنائي: الاستفادة من رتابة الاحتمالية للبحث الفعال
  3. تخفيف الضمانات النظرية: الحصول على تعقيد زمن متعدد الحدود مع الحفاظ على العملية

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

وصف الخوارزمية

الخوارزمية 1: LinearMonteCarloExplainer

الإدخال: نموذج خطي L، عينة x، معاملات δ، ε، β
1. δ* ← عينة موحدة من [δ-ε, δ+ε]
2. حساب جميع تقييمات الميزات s_i
3. بناء سلسلة عينات جزئية y^(0), ..., y^(n)
4. تعيين عدد العينات m = (log 2n)/(2ε²δ²) log(2log n/β)
5. استخدام البحث الثنائي للعثور على الحد الأدنى k بحيث الاحتمالية المقدرة ≥ δ*
6. إرجاع (δ*, y^(k*))

التحليل النظري

النظرية الرئيسية: بالنظر إلى نموذج خطي L\mathcal{L} وإدخال x\mathbf{x}، يمكن حساب (δ,ε)(δ,\varepsilon)-min-SR بنجاح بوقت O~(nε2δ2)\tilde{O}(\frac{n}{\varepsilon^2\delta^2}) بواحتمالية 1−β1-\beta.

تحليل التعقيد

  • التعقيد الزمني: O(log⁡n⋅m⋅n)=O~(nε2δ2)O(\log n \cdot m \cdot n) = \tilde{O}(\frac{n}{\varepsilon^2\delta^2})
  • التعقيد المكاني: O(n)O(n)
  • احتمالية النجاح: 1−β1-\beta

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

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

  1. مقارنة القابلية للمعالجة:
    • النماذج الخطية: قابلة للحل في زمن متعدد الحدود
    • أشجار القرار: نتائج قوية لعدم القابلية للتقريب (ما لم يكن SAT قابلاً للحل في زمن شبه متعدد الحدود)
    • الشبكات العصبية: NPPP-hard
  2. التحقق من الأمثلة المحددة:
    • المثال 2 يوضح أن 0.999999-SR يمكن أن يكون أصغر 251 مرة من الحد الأدنى 1-SR
    • المثال 3 يتحقق من صحة استراتيجية الاختيار الجشع

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

  1. نتائج الفصل: إثبات الميزة الأساسية للنماذج الخطية مقارنة بأشجار القرار
  2. الأمثل المحلي مقابل العام: بالنسبة للنماذج الخطية، δ-SR المحلي الأمثل هو δ-SR الأمثل بالنسبة للمجموعة الفرعية
  3. فجوة التقريب: إثبات أن التغييرات الصغيرة في المعاملات الاحتمالية قد تؤدي إلى اختلافات Ω(n1/2−ϵ)\Omega(n^{1/2-\epsilon}) في حجم الشرح

تحليل الحالات

تحليل تفصيلي للمثال 3:

  • العينة: x=(1,0,0,1,1)\mathbf{x} = (1,0,0,1,1)
  • الأوزان: w=(5,1,−3,2,−1)\mathbf{w} = (5,1,-3,2,-1)، العتبة: θ=5\theta = 5
  • تقييمات الميزات: (5,−1,3,2,−1)(5,-1,3,2,-1)
  • أفضل شرح بميزتين: {1,3}\{1,3\}، الاحتمالية 7/8

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

حساب الأسباب الكافية

  1. Darwiche و Hirth (2020): أول من صاغ مفهوم الأسباب الكافية رسمياً
  2. Barceló وآخرون (2020): إنشاء تسلسل هرمي للتعقيد عبر فئات النماذج المختلفة
  3. Arenas وآخرون (2022): إثبات صعوبة δ-SRs على أشجار القرار

الشروح الاحتمالية

  1. Wäldchen وآخرون (2021): تقديم مفهوم δ-الأسباب الكافية
  2. Izza وآخرون (2023): دراسة حساب الشروح الاحتمالية البطنية
  3. Kozachinskiy (2023): إنشاء نتائج عدم القابلية للتقريب لأشجار القرار

شرح النماذج الخطية

  1. Marques-Silva وآخرون (2020): دراسة مصنفات خطية مثل Naive Bayes
  2. Blanc وآخرون (2021): شروح صغيرة بالنسبة لتعقيد الشهادة

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

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

  1. اختراق نظري: أول إثبات لقابلية الحساب في زمن متعدد الحدود للشروح الاحتمالية على النماذج الخطية
  2. القيمة العملية: مفهوم (δ,ε)(δ,\varepsilon)-SR يحسن العملية مع الحفاظ على الضمانات النظرية
  3. فصل النموذج: إنشاء فرق أساسي بين النماذج الخطية وأشجار القرار في تعقيد حساب الشروح

القيود

  1. الكفاءة العملية: بالنسبة للبيانات عالية الأبعاد (مثل n=500)، الحساب لا يزال مكلفاً عندما ε=0.1، δ=0.01
  2. افتراضات التوزيع: تفترض الخوارزمية توزيعاً منتظماً، التوسع إلى التوزيعات المنتجة يتطلب تقنيات جديدة
  3. أنواع الميزات: تأخذ في الاعتبار فقط الميزات الثنائية، التطبيقات العملية تتطلب التعامل مع الميزات المستمرة والفئوية

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

  1. تحسين الخوارزمية: تقليل الاعتماد على 1/ε و 1/δ
  2. توسيع التوزيع: التعامل مع التوزيعات المنتجة والتوزيعات الميزة الأكثر عمومية
  3. أنواع الميزات: التوسع إلى "المصنفات الخطية الممتدة" بأنواع ميزات مختلطة
  4. لغات الاستعلام: تصميم لغة استعلام شروح احتمالية إعلانية

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

المزايا

  1. مساهمة نظرية كبيرة:
    • أول إثبات لقابلية المعالجة للشروح الاحتمالية على النماذج الخطية
    • توفير تحليل تعقيد شامل وتصميم خوارزمية
    • إثبات نتائج فصل مهمة
  2. ابتكار الطريقة:
    • مفهوم (δ,ε)(δ,\varepsilon)-SR يوازن بذكاء بين النظرية والعملية
    • تقنية العشوائية تتجنب بفعالية الحالات الصعبة
    • إثبات استراتيجية الجشع أنيق وعميق
  3. تحليل متعمق:
    • توفير إثباتات رياضية مفصلة
    • النظر في مقاييس تعقيد متعددة
    • إنشاء روابط واضحة مع الأعمال ذات الصلة

أوجه القصور

  1. قيود العملية:
    • الخوارزمية حساسة للمعاملات، الكفاءة سيئة في الحالات عالية الأبعاد
    • تنطبق فقط على النماذج الخطية بميزات ثنائية
    • افتراض التوزيع المنتظم قوي جداً في الممارسة
  2. التحقق التجريبي غير كافٍ:
    • نقص التحقق التجريبي على مجموعات بيانات كبيرة
    • لا توجد مقارنة مع الطرق الاستكشافية الموجودة
    • النتائج النظرية تحتاج إلى دعم تجريبي أكثر
  3. مشاكل التوسع:
    • التحديات التقنية كبيرة للتوسع إلى إعدادات أكثر عمومية
    • وضوح التطبيق على خط أنابيب ML العملي غير واضح

التأثير

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

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

  1. التحكم المالي: شرح نماذج التقييم الخطية لقرارات القروض
  2. التشخيص الطبي: شرح تقييم المخاطر بناءً على الانحدار الخطي
  3. أنظمة التوصية: تحليل أهمية الميزات لنماذج التوصية الخطية
  4. الامتثال القانوني: شروح القرارات الآلية بضمانات رياضية

المراجع

  1. Darwiche, A. and Hirth, A. (2020). On the Reasons Behind Decisions. ECAI 2020.
  2. Barceló, P., Monet, M., Pérez, J., and Subercaseaux, B. (2020). Model interpretability through the lens of computational complexity. NeurIPS 2020.
  3. Wäldchen, S., MacDonald, J., Hauch, S., and Kutyniok, G. (2021). The computational complexity of understanding binary classifier decisions. JAIR.
  4. Arenas, M., Barceló, P., Romero Orth, M., and Subercaseaux, B. (2022). On computing probabilistic explanations for decision trees. NeurIPS 2022.
  5. Kozachinskiy, A. (2023). Inapproximability of sufficient reasons for decision trees. arXiv:2304.02781.

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