PolySHAP: 상호작용을 고려한 다항 회귀를 이용한 KernelSHAP 확장

PolySHAP: Extending KernelSHAP with Interaction-Informed Polynomial Regression

샤플리 값은 설명 가능한 인공지능(XAI) 분야에서 핵심적인 게임 이론 도구로 부상했습니다. 그러나 모델이 $d$개의 특징을 가질 때, 정확한 샤플리 값을 계산하려면 $2^d$번의 게임 평가가 필요합니다. Lundberg와 Lee의 KernelSHAP 알고리즘은 이러한 지수적인 계산 비용을 피하는 주요 방법으로 자리 잡았습니다. KernelSHAP은 랜덤하게 선택된 특징 부분집합에 대한 소수의 게임 평가를 사용하여 선형 함수로 게임을 근사함으로써 샤플리 값을 근사합니다. 본 연구에서는 KernelSHAP을 확장하여, 특징 간의 비선형적인 상호작용을 포착할 수 있는 고차 다항식을 사용하여 게임을 근사합니다. 결과적으로 얻어진 PolySHAP 방법은 다양한 벤치마크 데이터셋에서 경험적으로 더 나은 샤플리 값 추정 결과를 제공하며, 이러한 추정치는 일관성을 갖는다는 것을 증명했습니다. 더 나아가, 본 연구는 KernelSHAP의 일반적인 개선 방법인 페어드 샘플링(반대 샘플링)과 본 연구의 접근 방식을 연결합니다. 페어드 샘플링은 2차 다항식을 전혀 사용하지 않고도, 2차 다항식 PolySHAP과 정확히 동일한 샤플리 값 근사값을 출력한다는 것을 증명했습니다. 현재까지 알려진 바로는, 이러한 결과는 페어드 샘플링 휴리스틱의 뛰어난 실제 성능에 대한 최초의 강력한 이론적 근거를 제공합니다.

Shapley values have emerged as a central game-theoretic tool in explainable AI (XAI). However, computing Shapley values exactly requires $2^d$ game evaluations for a model with $d$ features. Lundberg and Lee's KernelSHAP algorithm has emerged as a leading method for avoiding this exponential cost. KernelSHAP approximates Shapley values by approximating the game as a linear function, which is fit using a small number of game evaluations for random feature subsets. In this work, we extend KernelSHAP by approximating the game via higher degree polynomials, which capture non-linear interactions between features. Our resulting PolySHAP method yields empirically better Shapley value estimates for various benchmark datasets, and we prove that these estimates are consistent. Moreover, we connect our approach to paired sampling (antithetic sampling), a ubiquitous modification to KernelSHAP that improves empirical accuracy. We prove that paired sampling outputs exactly the same Shapley value approximations as second-order PolySHAP, without ever fitting a degree 2 polynomial. To the best of our knowledge, this finding provides the first strong theoretical justification for the excellent practical performance of the paired sampling heuristic.