Relative Keys: Putting Feature Explanation into Context

Shuai An, Yang Cao

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

Formal feature explanations strictly maintain perfect conformity but are intractable to compute, while heuristic methods are much faster but can lead to problematic explanations due to lack of conformity guarantees. We propose relative keys that have the best of both worlds. Relative keys associate feature explanations with a set of instances as context, and warrant perfect conformity over the context as formal explanations do, whilst being orders of magnitudes faster and working for complex blackbox models. Based on it, we develop CCE, a prototype that computes explanations with provably bounded conformity and succinctness, without accessing the models. We show that computing the most succinct relative keys is NP-complete and develop various algorithms for it under the batch and online models. Using 9 real-life datasets and 7 state-of-the-art explanation methods, we demonstrate that CCE explains cases where existing methods cannot, and provides more succinct explanations with perfect conformity for cases they can; moreover, it is 2 orders of magnitude faster.
Original languageEnglish
Article number8
Pages (from-to)1-28
Number of pages28
JournalProceedings of the ACM on Management of Data
Issue number1
Publication statusPublished - 26 Mar 2024
Event2024 SIGMOD/PODS International Conference on Management of Data - Santiago, Chile
Duration: 9 Jun 202415 Jun 2024


Dive into the research topics of 'Relative Keys: Putting Feature Explanation into Context'. Together they form a unique fingerprint.

Cite this