PolySHAP: 상호작용 정보를 반영한 다항 회귀를 이용한 KernelSHAP의 확장

PolySHAP: Extending KernelSHAP with Interaction-Informed Polynomial Regression

섀플리 값(Shapley values)은 설명 가능한 AI(XAI) 분야에서 핵심적인 게임 이론적 도구로 부상했다. 그러나 d개의 특성을 가진 모델에 대해 섀플리 값을 정확히 계산하려면 2^d번의 게임 평가가 필요하다. Lundberg와 Lee의 KernelSHAP 알고리즘은 이러한 지수적 비용을 피하기 위한 대표적인 방법으로 자리 잡았다. KernelSHAP은 무작위 특성 부분집합에 대한 적은 수의 게임 평가를 사용하여 적합(fit)된 선형 함수로 게임을 근사함으로써 섀플리 값을 추정한다. 본 연구에서는 특성 간의 비선형 상호작용을 포착하는 고차 다항식을 통해 게임을 근사함으로써 KernelSHAP을 확장한다. 그 결과물인 PolySHAP 방법은 다양한 벤치마크 데이터셋에서 경험적으로 더 우수한 섀플리 값 추정치를 산출하며, 우리는 이 추정치가 일치성(consistent)을 가짐을 증명한다. 또한, 우리는 우리의 접근 방식을 KernelSHAP의 경험적 정확도를 향상시키기 위해 널리 사용되는 변형인 쌍체 표본 추출(paired sampling, 또는 대칭 표본 추출)과 연결한다. 우리는 쌍체 표본 추출이 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.