샤플리 값 추정의 새로운 방법: 홀(Odd) 추정기

An Odd Estimator for Shapley Values

샤플리 값은 머신러닝 분야에서 특징 중요도, 데이터 가치 평가, 인과 추론 등 다양한 분야에서 널리 사용되는 중요한 개념입니다. 하지만 샤플리 값의 정확한 계산은 일반적으로 어렵기 때문에 효율적인 근사 방법이 필요합니다. 기존의 효과적이고 널리 사용되는 추정 방법들은 쌍별 샘플링(paired sampling) 기법을 사용하여 추정 오류를 줄이는 것을 목표로 합니다. 하지만 이 기법이 성능 향상에 기여하는 이론적 원리는 명확하게 밝혀지지 않았습니다. 본 연구에서는 쌍별 샘플링의 작동 원리에 대한 간결하고 근본적인 설명을 제공합니다. 우리는 샤플리 값이 집합 함수의 홀(odd) 부분에만 의존하며, 쌍별 샘플링이 회귀 목표를 직교화하여 관련 없는 짝(even) 부분을 제거한다는 것을 증명합니다. 이러한 통찰력을 바탕으로, 우리는 새로운 일관된 추정기인 OddSHAP을 제안합니다. OddSHAP은 다항 회귀를 사용하여 홀 부분 공간에만 작용하며, 푸리에 기저를 활용하여 이 부분 공간을 분리하고, 프록시 모델을 사용하여 중요한 상호작용을 식별합니다. OddSHAP은 이러한 접근 방식을 통해 고차 근사의 조합적 복잡성을 극복합니다. 광범위한 성능 평가 결과, OddSHAP은 최첨단 수준의 추정 정확도를 달성하는 것으로 나타났습니다.

The Shapley value is a ubiquitous framework for attribution in machine learning, encompassing feature importance, data valuation, and causal inference. However, its exact computation is generally intractable, necessitating efficient approximation methods. While the most effective and popular estimators leverage the paired sampling heuristic to reduce estimation error, the theoretical mechanism driving this improvement has remained opaque. In this work, we provide an elegant and fundamental justification for paired sampling: we prove that the Shapley value depends exclusively on the odd component of the set function, and that paired sampling orthogonalizes the regression objective to filter out the irrelevant even component. Leveraging this insight, we propose OddSHAP, a novel consistent estimator that performs polynomial regression solely on the odd subspace. By utilizing the Fourier basis to isolate this subspace and employing a proxy model to identify high-impact interactions, OddSHAP overcomes the combinatorial explosion of higher-order approximations. Through an extensive benchmark evaluation, we find that OddSHAP achieves state-of-the-art estimation accuracy.