Approximate Shapley value estimation using sampling without replacement and variance estimation via the new Symmetric bootstrap and the Doubled half bootstrap

기술 요약: 샘플링 없는 복원 추출을 이용한 근사 샤플리 값 추정 및 새로운 부트스트랩 분산 추정기

1. 문제 정의

고전적인 KernelSHAP 프레임워크(Lundberg and Lee, 2017)는 모든 $2^p$ 개의 부분 집합에 대해 기여 함수를 평가하는 대신, 부분 집합의 하위 집합을 샘플링함으로써 샤플리 값 추정의 계산 비용을 줄이는 것을 목표로 합니다. 그러나 기존 구현 방식은 일반적으로 복원 추출(with replacement) 방식으로 부분 집합을 샘플링합니다. 이 접근 방식은 다음과 같은 구체적인 통계적 문제를 야기합니다:

1. 샘플링 비효율성: 복원 추출을 통한 샘플링은 쿠폰 수집가 문제(Coupon Collector's Problem)의 가중 버전으로 이어지며, 특히 가중치가 낮은 부분 집합의 경우 샘플 크기가 커짐에 따라 고유한 부분 집합을 얻는 것이 점점 더 어려워집니다.
2. 분산 추정의 한계: 전통적인 부트스트랩 방법은 독립 항등 분포(i.i.d.) 샘플을 가정합니다. 유한 모집단(모든 가능한 부분 집합의 집합)으로부터 비복원 추출을 할 때 이 가정은 위배됩니다. 결과적으로 표준 부트스트랩 기술은 샤플리 값의 분산을 정확하게 추정하지 못할 수 있으며, 모든 부분 집합이 평가될 경우 분산이 이론적으로 0에 수렴해야 한다는 유한 모집단 제약을 반영하지 못합니다.

본 논문은 **비복원 추출(without replacement)**을 사용하는 프레임워크를 활용하고, 근사된 샤플리 값의 분산을 정확하게 추정하기 위해 유한 모집단 이론과 호환되는 새로운 부트스트랩 방법론을 도입하는 문제를 다룹니다.

2. 방법론

2.1 월레니우스 분포(Wallenius' Distribution)를 이용한 비복원 추출

제안된 알고리즘은 KernelSHAP 절차를 수정하여 비복원 방식으로 부분 집합을 샘플링합니다. 이 과정은 두 가지 주요 단계로 구성됩니다:

1. 층화(Stratification): 부분 집합들을 포함하는 특징(feature)의 수(크기)에 따라 그룹화합니다.
2. 샘플 크기 결정: 부분 집합을 확률적으로 하나씩 샘플링하는 대신, 알고리즘은 **월레니우스의 비중 중앙 과대 기하 분포(Wallenius' noncentral hypergeometric distribution)**를 사용하여 각 그룹에서 추출될 기대 부분 집합 수를 계산합니다. 이 분포는 항목들이 서로 다른 가중치를 가진 편향된 비복원 샘플링을 모델링합니다.
   • 알고리즘은 이 분포의 기대값을 사용하여 각 층(stratum)에서 샘플링할 부분 집합의 수를 결정하며, 이를 가장 가까운 정수로 반올림합니다.
   • 수량이 결정되면, 각 그룹 내에서 비복원 추출 방식으로 부분 집합을 샘플링합니다.
   • 페어링 전략(Pairing Strategy): 분산을 더욱 줄이기 위해, 본 방법은 페어링 전략(Kroese et al., 2013)을 사용합니다. 만약 부분 집합 $S$가 샘플링되면, 그 여집합인 $S^c$도 계산에 포함되어 쌍을 이루는 그룹 간의 특징 합이 일정하게 유지되도록 합니다.

2.2 부트스트랩 방법을 통한 분산 추정

본 논문은 새로운 샘플링 설계 하에서 샤플리 값의 표준 편차를 추정하기 위한 세 가지 접근 방식을 평가합니다:

1. 유효하지 않은 직관적 방법(Invalid Intuitive Method): 가중 최소 제곱법(weighted least squares)에 직접 적용된 표준 Horvitz-Thompson 분산 추정기입니다. 저자는 이 방법이 페어링 전략에 의해 도입된 특정 의존성과 KernelSHAP 맥락에서의 $Z^T W Z$ 행렬 구조를 고려하지 못하기 때문에 유효하지 않음을 입증합니다.
2. 이중 절반 부트스트랩(Doubled Half Bootstrap; Antal and Tillé, 2014): 단위가 베르누이 샘플링을 통해 선택되고, 선택되지 않은 단위들이 무작위로 두 번 선택되는 유한 모집단에서의 알려진 방법입니다. 비교를 위해 이 방법이 구현되었습니다.
3. 대칭 부트스트랩(Symmetric Bootstrap; 새로운 기여): 이 문맥에 특화되어 개발된 새로운 부트스트랩 방법입니다.
   • 메커니즘: 각 부트스트랩 샘플에서 원래 샘플의 모든 단위는 0번, 1번, 또는 2번 나타날 수 있습니다.
   • 대칭성: 이 방법은 0번 나타나는 총 단위의 수가 2번 나타나는 총 단위의 수와 같음을 보장합니다.
   • 확률: 단위 $k$가 $S_k$번 나타날 확률은 다음과 같이 정의됩니다:
     • $Pr(S_k = 0) = Pr(S_k = 2) = \frac{1}{2}(1 - \frac{n}{N})$
     • $Pr(S_k = 1) = \frac{n}{N}$
   • 특성: 이러한 구성은 기대값 $E(S_k) = 1$과 분산 $Var(S_k) = 1 - \frac{n}{N}$을 보장하여, 유한 모집단 샘플링에서의 유효한 분산 추정을 위한 필수 조건(Horvitz-Thompson 일치성)을 충족합니다.
   • 정수 처리: "0" 또는 "2"의 발생 기대값이 정수가 아닌 경우, 인접한 정수 값 사이를 교차하도록 베르누이 확률 변수를 도입하여 절차가 완전히 자동화된 상태를 유지하도록 합니다.

2.3 계산 구현

기여 함수 $v(S)$는 샘플링된 부분 집합들에 대한 회귀 분석을 통해 추정됩니다. 구현은 선형 모델을 효율적으로 처리하기 위해 희소 행렬(sparse matrices)과 Cholesky 분해(Matrix 패키지)를 활용하며, 단일 코어에서 몇 분 내에 65,000개의 선형 모델에 대한 평균을 추정할 수 있습니다 (Aanes, 2025).

3. 주요 기여

1. 샘플링 프레임워크: 월레니우스의 비중 중앙 과대 기하 분포를 KernelSHAP 프레임워크에 통합하여, 복원 추출 샘플링에 내재된 쿠폰 수집가 문제의 비효율성을 피하고 효율적인 비복원 추출을 가능하게 했습니다.
2. 대칭 부트스트랩: 유한 모집단 샘플링을 위해 특화된, 계산적으로 효율적인 새로운 부트스트랩 방법을 도입했습니다. 이는 이 문맥에서 편향되지 않은 분산 추정을 위한 필요한 모멘트 조건(평균 및 분산)을 충족합니다.
3. 분산 추정 분석: 새로운 샘플링 설계에 대한 분산 추정기들을 엄격하게 비교하여, 표준 부트스트랩이 이 특정 설계에는 부적절하며 새로운 대칭 부트스트랩이 기존의 Doubled half 부트스트랩(Antal and Tillé, 2014)보다 우수하거나 대등한 성능을 보임을 입증했습니다.

4. 결과

새로운 방법과 복원 추출을 사용하는 최신 상태의 shapr R-패키지(버전 1.0.7)를 비교하기 위해 Kaggle의 "Life Expectancy" 데이터셋을 사용한 두 가지 시뮬레이션 연구가 수행되었습니다.

• 소규모 시뮬레이션 연구 (5개 특징, 16개 부분 집합):
  • 새로운 샘플링 방법은 shapr과 유사한 표준 편차를 가진 샤플리 값 추정치를 생성했습니다.
  • Antal-Tillé 부트스트랩은 성능이 저조하여, 빈번하게 완전 계수(full-rank)가 아닌 행렬($Z^T W Z$)을 생성하고 부정확한 분산 추정치를 냈습니다.
  • 대칭 부트스트랩은 Antal-Tillé보다 훨씬 나은 성능을 보였으나, 가끔 실제 값(모든 부분 집합을 재샘플링한 결과)에 비해 약간 "자유로운(liberal, 작게 측정된)" 표준 편차를 생성했습니다.
• 대규모 시뮬레이션 연구 (16개 특징, 402개 부분 집합):
  • 대칭 부트스트랩과 Antal-Tillé 방법은 구별할 수 없을 정도로 동일한 표준 편차 추정치를 생성했습니다.
  • 두 새로운 부트스트랩 방법 모두 여러 변수에 대해 표준 편차를 과소 추정하는 경 경향이 있는 shapr의 내장 부트스트랩 절차보다 약간 더 나은 성능을 보였습니다.
  • 새로운 샘플링 알고리즘(비복원 추출)은 샤플리 값 추정 자체의 정확도 측면에서 shapr 방식(복원 추출)과 유사한 성능을 보였습니다.

5. 의의 및 결론

본 논문은 월레니우스 분포를 통한 비복원 추출과 새로운 대칭 부트스트랩을 결가한 제안된 알고리즘이 기존의 KernelSHAP 구현들에 대한 강력한 대안이 될 수 있다고 결론짓습니다.

• 성능: 제안된 방법은 점 추정치(point estimates) 측면에서 개선된 KernelSHAP 방법인 shapr 패키지와 "유사한" 성능을 보입니다.
• 분산 추정: 대칭 부트스트랩은 "매우 계산 속도가 빠르고 이해하기 쉬운" 방법으로 강조되었으며, 특히 대규모 시뮬레이션 연구에서 우수한 성능을 보였습니다. 이는 비복원 추출을 사용하는 유한 모집단에서의 "가이드가 될 만한" 부트스트랩 방법에 대한 문헌상의 공백을 메워줍니다.
• 한계: 저자는 소규모 연구에서 대칭 부트스트랩이 특정 변수에 대해 표준 편차를 약간 너무 작게(liberal) 생성하는 경우가 있었으나, 가장 큰 표준 편차는 일관되게 포착했다는 점을 겸허히 언급했습니다.
• 적용 가능성: 이 방법은 기여 함수가 선형 또는 일반화 선형 모델(예측이 변환된 척도 상에서 선형인 경우)을 통해 추정되는 시나리오를 위해 설계되었으며, 빠른 계산 기술을 활용합니다.

본 연구는 유한 모집단 이론이 샤플리 값 추정에 성공적으로 적용되어 샘플링 효율성을 높이고, 전통적인 i.i.d. 부트스트랩 가정의 이론적 한계를 극복하여 유효한 분산 추정을 제공할 수 있음을 확립했습니다.