Local vs. Global Interpretability: A Computational Complexity Perspective

• URL: http://arxiv.org/abs/2406.02981v2
• Date: Fri, 7 Jun 2024 08:44:52 GMT
• Title: Local vs. Global Interpretability: A Computational Complexity Perspective
• Authors: Shahaf Bassan, Guy Amir, Guy Katz,
• Abstract summary: We use computational complexity theory to assess local and global perspectives of interpreting ML models. Our findings offer insights into both the local and global interpretability of these models. We believe that our findings demonstrate how examining explainability through a computational complexity lens can help us develop a more rigorous grasp of the inherent interpretability of ML models.
• Score: 0.9558392439655016
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The local and global interpretability of various ML models has been studied extensively in recent years. However, despite significant progress in the field, many known results remain informal or lack sufficient mathematical rigor. We propose a framework for bridging this gap, by using computational complexity theory to assess local and global perspectives of interpreting ML models. We begin by proposing proofs for two novel insights that are essential for our analysis: (1) a duality between local and global forms of explanations; and (2) the inherent uniqueness of certain global explanation forms. We then use these insights to evaluate the complexity of computing explanations, across three model types representing the extremes of the interpretability spectrum: (1) linear models; (2) decision trees; and (3) neural networks. Our findings offer insights into both the local and global interpretability of these models. For instance, under standard complexity assumptions such as P != NP, we prove that selecting global sufficient subsets in linear models is computationally harder than selecting local subsets. Interestingly, with neural networks and decision trees, the opposite is true: it is harder to carry out this task locally than globally. We believe that our findings demonstrate how examining explainability through a computational complexity lens can help us develop a more rigorous grasp of the inherent interpretability of ML models.

Related papers

• GLEAMS: Bridging the Gap Between Local and Global Explanations [6.329021279685856]
  We propose GLEAMS, a novel method that partitions the input space and learns an interpretable model within each sub-region. We demonstrate GLEAMS' effectiveness on both synthetic and real-world data, highlighting its desirable properties and human-understandable insights.
  arXiv  Detail & Related papers  (2024-08-09T13:30:37Z)
• Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation [0.9558392439655016]
  The ability to interpret Machine Learning (ML) models is becoming increasingly essential. Recent work has demonstrated that it is possible to formally assess interpretability by studying the computational complexity of explaining the decisions of various models.
  arXiv  Detail & Related papers  (2024-08-07T17:20:52Z)
• Explaining Decisions in ML Models: a Parameterized Complexity Analysis [26.444020729887782]
  This paper presents a theoretical investigation into the parameterized complexity of explanation problems in various machine learning (ML) models. Contrary to the prevalent black-box perception, our study focuses on models with transparent internal mechanisms.
  arXiv  Detail & Related papers  (2024-07-22T16:37:48Z)
• SpaRC and SpaRP: Spatial Reasoning Characterization and Path Generation for Understanding Spatial Reasoning Capability of Large Language Models [70.01883340129204]
  spatial reasoning is a crucial component of both biological and artificial intelligence. We present a comprehensive study of the capability of current state-of-the-art large language models (LLMs) on spatial reasoning.
  arXiv  Detail & Related papers  (2024-06-07T01:06:34Z)
• Explaining Text Similarity in Transformer Models [52.571158418102584]
  Recent advances in explainable AI have made it possible to mitigate limitations by leveraging improved explanations for Transformers. We use BiLRP, an extension developed for computing second-order explanations in bilinear similarity models, to investigate which feature interactions drive similarity in NLP models. Our findings contribute to a deeper understanding of different semantic similarity tasks and models, highlighting how novel explainable AI methods enable in-depth analyses and corpus-level insights.
  arXiv  Detail & Related papers  (2024-05-10T17:11:31Z)
• Interpretability at Scale: Identifying Causal Mechanisms in Alpaca [62.65877150123775]
  We use Boundless DAS to efficiently search for interpretable causal structure in large language models while they follow instructions. Our findings mark a first step toward faithfully understanding the inner-workings of our ever-growing and most widely deployed language models.
  arXiv  Detail & Related papers  (2023-05-15T17:15:40Z)
• Structure Learning and Parameter Estimation for Graphical Models via Penalized Maximum Likelihood Methods [0.0]
  In the thesis, we consider two different types of PGMs: Bayesian networks (BNs) which are static, and continuous time Bayesian networks which, as the name suggests, have a temporal component. We are interested in recovering their true structure, which is the first step in learning any PGM.
  arXiv  Detail & Related papers  (2023-01-30T20:26:13Z)
• Interpretability in the Wild: a Circuit for Indirect Object Identification in GPT-2 small [68.879023473838]
  We present an explanation for how GPT-2 small performs a natural language task called indirect object identification (IOI) To our knowledge, this investigation is the largest end-to-end attempt at reverse-engineering a natural behavior "in the wild" in a language model.
  arXiv  Detail & Related papers  (2022-11-01T17:08:44Z)
• Optimistic MLE -- A Generic Model-based Algorithm for Partially Observable Sequential Decision Making [48.87943416098096]
  This paper introduces a simple efficient learning algorithms for general sequential decision making. We prove that OMLE learns near-optimal policies of an enormously rich class of sequential decision making problems.
  arXiv  Detail & Related papers  (2022-09-29T17:56:25Z)
• Partial Order in Chaos: Consensus on Feature Attributions in the Rashomon Set [50.67431815647126]
  Post-hoc global/local feature attribution methods are being progressively employed to understand machine learning models. We show that partial orders of local/global feature importance arise from this methodology. We show that every relation among features present in these partial orders also holds in the rankings provided by existing approaches.
  arXiv  Detail & Related papers  (2021-10-26T02:53:14Z)
• Unsupervised Learning of Global Factors in Deep Generative Models [6.362733059568703]
  We present a novel deep generative model based on non i.i.d. variational autoencoders. We show that the model performs domain alignment to find correlations and interpolate between different databases. We also study the ability of the global space to discriminate between groups of observations with non-trivial underlying structures.
  arXiv  Detail & Related papers  (2020-12-15T11:55:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.