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

Вероятностные объяснения для линейных моделей

Основная информация

  • ID статьи: 2501.00154
  • Название: Probabilistic Explanations for Linear Models
  • Авторы: Bernardo Subercaseaux (Carnegie Mellon University), Marcelo Arenas (PUC Chile, IMFD Chile, RelationalAI), Kuldeep S. Meel (Georgia Institute of Technology, University of Toronto)
  • Классификация: cs.AI (Искусственный интеллект), cs.CC (Вычислительная сложность)
  • Дата публикации: 3 января 2025
  • Ссылка на статью: https://arxiv.org/abs/2501.00154

Аннотация

В данной работе исследуется проблема вычисления "достаточных причин" в формальной интерпретируемости ИИ (Formal XAI). Для заданной модели M и входного экземпляра x достаточная причина — это подмножество S признаков x такое, что для любого экземпляра z, совпадающего с x на признаках из S, выполняется M(x)=M(z). Для уменьшения размера достаточных причин авторы рассматривают вероятностную релаксацию: требуется, чтобы вероятность M(x)=M(z) для случайного экземпляра z, совпадающего с x на заданном наборе признаков, была не менее δ∈(0,1]. Вычисление малых δ-достаточных причин (δ-SRs) теоретически сложно, даже для "интерпретируемых" моделей, таких как деревья решений, существуют сильные результаты о неприближаемости. В работе предложена концепция (δ,ε)-SR, являющаяся простой релаксацией δ-SRs, и доказано, что такие объяснения могут быть эффективно вычислены на линейных моделях.

Исследовательский контекст и мотивация

  1. Основная проблема: Как обеспечить объяснения решений моделей машинного обучения с математическими гарантиями малого размера. Традиционные достаточные причины требуют 100% определённости, но это часто приводит к чрезмерно большим объяснениям, непригодным для понимания человеком.
  2. Значимость проблемы:
    • Miller (1956) показал, что объяснения с более чем 9 признаками могут быть слишком большими для человека
    • Эмпирические исследования показывают, что объяснения должны быть лаконичными (Narayanan et al., 2018; Lage et al., 2019)
    • В практических приложениях пользователи больше заботятся о размере объяснения, чем о малых различиях в вероятностных гарантиях
  3. Ограничения существующих методов:
    • Вычисление минимальных δ-SRs является NP-трудным даже для деревьев решений
    • Для линейных моделей точное вычисление вероятности #P-трудно
    • Существуют сильные результаты о неприближаемости: невозможно получить хорошие коэффициенты приближения за полиномиальное время
  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)} — частичные экземпляры, определённые первыми kk признаками с наивысшими оценками, то:

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. Оценка методом Монте-Карло

Использование неравенства Хёффдинга для оценки вероятности:

Для 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} можно вычислить (δ,ε)-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-трудно
  2. Проверка конкретных примеров:
    • Пример 2 показывает, что 0.999999-SR может быть в 251 раз меньше минимальной 1-SR
    • Пример 3 проверяет корректность стратегии жадного выбора

Теоретические находки

  1. Результаты разделения: Доказано фундаментальное преимущество линейных моделей перед деревьями решений
  2. Локальные vs глобальные оптимумы: Для линейных моделей локально минимальная δ-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)
  • Оптимальное объяснение из 2 признаков: {1,3}\{1,3\}, вероятность 7/8

Связанные работы

Вычисление достаточных причин

  1. Darwiche and Hirth (2020): Первая формализация концепции достаточных причин
  2. Barceló et al. (2020): Установление иерархии сложности для различных классов моделей
  3. Arenas et al. (2022): Доказательство сложности δ-SRs на деревьях решений

Вероятностные объяснения

  1. Wäldchen et al. (2021): Введение концепции δ-достаточных причин
  2. Izza et al. (2023): Исследование вычисления вероятностных абдуктивных объяснений
  3. Kozachinskiy (2023): Установление результатов неприближаемости для деревьев решений

Объяснение линейных моделей

  1. Marques-Silva et al. (2020): Исследование наивного Байеса и других линейных классификаторов
  2. Blanc et al. (2021): Малые объяснения относительно сложности сертификата

Заключение и обсуждение

Основные выводы

  1. Теоретический прорыв: Впервые доказана полиномиальная вычислимость вероятностных объяснений на линейных моделях
  2. Практическая ценность: Концепция (δ,ε)-SR повышает практичность при сохранении теоретических гарантий
  3. Разделение моделей: Установлено фундаментальное различие между линейными моделями и деревьями решений в сложности вычисления объяснений

Ограничения

  1. Практическая эффективность: Для высокомерных данных (например, n=500) вычисление при ε=0.1, δ=0.01 остаётся дорогостоящим
  2. Предположения о распределении: Алгоритм предполагает равномерное распределение; расширение на произведения распределений требует новых методов
  3. Типы признаков: Рассматриваются только бинарные признаки; практические приложения требуют работы с непрерывными и категориальными признаками

Направления будущих исследований

  1. Оптимизация алгоритмов: Снижение зависимости от 1/ε и 1/δ
  2. Расширение распределений: Работа с произведениями распределений и более общими распределениями признаков
  3. Типы признаков: Расширение на "обобщённые линейные классификаторы" со смешанными типами признаков
  4. Языки запросов: Разработка декларативного языка для запросов вероятностных объяснений

Глубокая оценка

Преимущества

  1. Значительный теоретический вклад:
    • Впервые установлена разрешимость вероятностных объяснений на линейных моделях
    • Предоставлен полный анализ сложности и разработка алгоритма
    • Доказаны важные результаты разделения
  2. Методологическая инновативность:
    • Концепция (δ,ε)-SR умело балансирует теорию и практику
    • Техника рандомизации эффективно избегает сложных экземпляров
    • Теоретическое обоснование жадной стратегии элегантно и глубоко
  3. Глубокий анализ:
    • Предоставлены детальные математические доказательства
    • Рассмотрены различные меры сложности
    • Установлены чёткие связи с соответствующими работами

Недостатки

  1. Ограничения практичности:
    • Алгоритм чувствителен к параметрам, неэффективен в высокомерных случаях
    • Применим только к линейным моделям с бинарными признаками
    • Предположение о равномерном распределении сильно в практике
  2. Недостаточная экспериментальная проверка:
    • Отсутствуют эксперименты на больших наборах данных
    • Нет сравнения с существующими эвристическими методами
    • Теоретические результаты требуют большей эмпирической поддержки
  3. Проблемы масштабируемости:
    • Значительные технические вызовы при расширении на более общие случаи
    • Неясна применимость к практическим ML pipeline

Влияние

  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.

Данная работа вносит значительный теоретический вклад в область формальной интерпретируемости ИИ, впервые доказав разрешимость вероятностных объяснений на линейных моделях и предоставив редкий позитивный результат в этой области. Хотя имеется место для улучшения в практичности, её теоретическая ценность и методологическая инновативность делают её важной работой в этой области.