기술 요약: ShaplEIG

문제 정의

샤플리 값(Shapley values, SVs)은 해석 가능한 머신러닝에서 원칙적인 기여도 측정 도구로 사용되지만, 그 정확한 계산은 종종 난해합니다. 계산상의 부담은 두 가지 요인에서 발생합니다: 플레이어 수 $p$에 따른 연합(coalitions)의 지수적 증가($2^p$), 그리고 각 연합에 대한 가치 함수 $\nu$를 평가하는 데 드는 높은 비용입니다. 모델 재학습 기반의 특성 중요도, 데이터 가치 평가, 하이퍼파라미터 중요도와 같은 응용 분야에서 가치 함수 평가는 전체 모델의 재학습이나 값비싼 추론을 포함할 수 있으며, 이는 평가 예산을 심각하게 제한합니다.

Monte Carlo 샘플링 및 대리 모델 기반 접근 방식(예: Kernel SHAP, Regression MSR)을 포함한 기존의 근사 방법들은 일반적으로 고정된 비적응형 샘플링 분포에 의존합니다. 이는 특히 저예산 환경에서, 이전 관측치를 바탕으로 평가할 연합을 적응적으로 선택함으로써 근사 정확도를 개선할 수 있는지에 대한 의문을 제기합니다. 베이지안 실험 설계(Bayesian Experimental Design, BED)는 기대 정보 이득(Expected Information Gain, EIG)을 사용하는 순차적 설계를 위한 프레임워크를 제공하지만, 폐쇄형(closed-form) EIG 표현식의 부재와 고차원 이산 공간에 대한 EIG 추정의 계산적 난해함으로 인해 SV 추정에서의 채택은 제한적이었습니다.

방법론

저자들은 샤플리 값에 대한 정보 이득을 최대화하도록 연합을 적응적으로 선택하는 베이지안 실험 설계 접근 방식인 ShaplEIG를 제안합니다.

1. Hamming 커널을 이용한 가우시안 프로세스 대리 모델

ShaplEIG는 가우시안 프로세스(GP) 대리 모델을 사용하여 가치 함수 $\nu$를 모델링합니다. 연합의 이진 입력 공간(지표 벡터 $z \in \{0, 1\}^p$로 표현됨)을 처리하기 위해, 이 방법은 **해밍 거리 커널(Hamming distance kernel)**을 채택합니다. 이 커널은 학습 가능한 길이 척도 하이퍼파라미터 $\xi$를 가진 가중 해밍 거리에 기반하여 연합 간의 유사성을 정량화합니다. GP는 관측된 데이터셋 $D_t$가 주어졌을 때 모든 $2^p$개 연합에 대한 가치 함수의 사후 분포를 제공합니다.

2. 선형성을 통한 일관된 SV 추정

핵심적인 이론적 통찰은 샤플리 값이 가치 함수에 대해 선형적이라는 점입니다. SV $\phi$는 가치 함수 벡터 $\nu$의 선형 변환으로 표현될 수 있습니다: $\phi = A\nu$, 여기서 $A$는 샤플리 공식에서 유도된 알려진 행렬입니다. 결과적으로, GP 대리 모델 하에서 SV에 대한 사후 분포 또한 가우시안이며 폐쇄형으로 구할 수 있습니다:
$$\phi | D_t \sim \mathcal{N}_p(A\mu_{\nu|D_t}, A\Sigma_{\nu|D_t}A^\top)$$
저자들은 사후 평균 $\hat{\phi} = A\mu_{\nu|D_t}$로부터 SV 추정치를 추출합니다. 결정적으로, 노이즈가 없거나(또는 준노이즈 상태의) GP에 대해, 이 추정량은 **일관성(consistent)**을 갖습니다: 즉, 모든 $2^p$개의 연합이 평가되면 추정치는 실제 샤플리 값으로 정확히 수렴합니다.

3. 폐쇄형 기대 정보 이득 (Closed-Form EIG)

핵심 기여는 후보 연합 $z^{(i)}$에 대한 SV에 관한 EIG의 폐쇄형 표현식을 유도하는 것입니다. 순차적 선택을 SV가 선형적 목표인 베이지안 선형 역문제로 프레이밍함으로써, EIG는 오직 SV의 사후 공분산에만 의존함을 보여줍니다:
$$\text{EIG}^{(t)}_{\phi}(z^{(i)}) \propto -\log \det \left( A \Sigma_{\nu|\nu'(z^{(i)}), D_t} A^\top \right) + C$$
이는 EIG가 특정 결과 $y(x)$가 아닌 선택된 연합(실험 설계)에만 의존하므로, BED에서 일반적으로 요구되는 중첩 기대값(nested expectations) 계산을 피할 수 있게 합니다.

4. 기본 대칭 다항식을 통한 효율적 계산

EIG를 직접 계산하는 것은 $2^p \times 2^p$ 크기의 행렬 연산을 포함하며, 이는 지수적 복잡도로 이어집니다. 저자들은 해밍 커널의 곱셈 구조를 활용하여 복잡도를 다항 시간($O(p^4 + t^3)$)으로 줄이는 효율적인 계산 체계를 제래합니다.

• EIG에 필요한 항들(구체적으로 $A\Sigma_{\nu|D_t}e_i$ 및 $A\Sigma_{\nu|D_t}A^\top$)은 커널 평가의 가중 합으로 다시 작성됩니다.
• 이러한 합은 **스케일링된 기본 대칭 다항식(scaled elementary symmetric polynomials, ESPs)**과 동일한 것으로 식별됩니다.
• 동적 계획법(dynamic programming)과 접두사/접미사 테이블(prefix/suffix tables)을 사용하여 이 다항식들을 효율적으로 계산함으로써, 이 방법은 모든 연합을 명시적으로 열거하지 않고도 작동합니다.

5. 알고리즘

알고리즘은 탐욕적(greedy) 방식으로 진행됩니다:

1. 작은 설계(예: 레버리지 스코어 샘플링)로 초기화합니다.
2. GP 대리 모델을 적합시키고 하이퍼파라미터를 최적화합니다.
3. 효율적인 다항식 체계를 사용하여 모든 후보 연합에 대한 EIG를 계산합니다.
4. EIG가 최대인 연합을 선택하여 가치 함수를 평가하고 데이터셋을 업데이트합니다.
5. 예산이 소진될 때까지 반복합니다.

주요 기여

1. ShaplEIG 프레임워크: 해밍 커널을 가진 GP 대리 모델을 사용하고 EIG에 따라 연합을 적응적으로 선택하는, SV 추정을 위한 새로운 BED 기반 방법론을 도입했습니다.
2. 폐쇄형 EIG: SV가 가치 함수에 대해 선형적임을 활용하여, GP 대리 모델 하에서 EIG가 폐쇄형 표현을 가짐을 입증했습니다.
3. 다항 복잡도: 기본 대칭 다항식을 통해 EIG 계산을 플레이어 수($p$)에 대한 지수적 복잡도에서 다항 시간 복잡도로 줄이는 효율적인 계산 방식을 제안했습니다.
4. 일관된 추정: 모든 연합이 평가될 때 정확한 값으로 수렴하는 일관된 SV 추정량을 제공하며, 이는 추가적인 조정 단계가 필요한 일부 트리 기반 대리 모델 방식과 대조됩니다.

실험 결과

저자들은 소규모에서 중규모 게임($8 \le p \le 101$)을 포함하는 다양한 비용이 많이 드는 응용 분야에서 ShaplEIG를 평가했습니다:

• 태스크: 전역 특성 중요도(TabPFN), 데이터 가치 평가(Random Forest, Gradient Boosting), 하이퍼파라미터 중요도(XGBoost, LCBench), 로컬 설명(ResNet, ViT, Random Forest).
• 베이스라인: Kernel SHAP, Leverage SHAP, Permutation Sampling, 그리고 최신 기술인 Regression MSR(XGBoost와 결합됨)과 비교했습니다.
• 절제 연구(Ablations): 동일한 GP 대리 모델을 사용하되 서로 다른 선택 전략(Random, Uncertainty Sampling, Leverage Score Sampling)을 사용하는 변형들과 비교했습니다.

결과:

• 샘플 효율성: ShaplEIG는 대부분의 태스크에서 저예산 환경일 때 가장 우수한 전체 정확도(최저 평균 제곱 오차)를 일관되게 달성했습니다. 특히 플레이어 간 상호작용이 불균일한 비대칭 게임에서 경쟁 모델들을 엄격하게 압도하는 경우가 많았습니다.
• 절제 연구 통찰: 강력한 성능은 단순히 GP 대리 모델을 사용하는 것보다 EIG 기반의 선택 전략에 주로 기인합니다. 불확실성 샘플링(Uncertainty Sampling, US)은 무작위 샘플링보다 성능이 떨어지는 경우가 많았는데, 이는 주변 분산(marginal variance)을 최대화하는 것이 선형 변환된 SV에 대한 정보를 최대화하는 것과 같지 않음을 보여줍니다.
• 확장성: 더 큰 게임($p > 16$)에 대해서도, 하이퍼파라미터 재적합을 매 반복마다 수행하는 대신 스케줄에 따라 수행하더라도 효과가 유지됩니다.
• 계산 비용: EIG 계산은 효율적(수 초)이지만, 하이퍼파라미터 적합은 $p$가 클 때 병목 현상이 될 수 있습니다($p \approx 100$일 때 반복당 최대 25분). 저자들은 가치 함수 평가가 진정으로 비싼 경우에 ShaplEIG가 가장 적합하며, 이 오버헤드가 정당화된다고 언급했습니다.

의의 및 주장

본 논문은 ShaplEIG가 비용이 많이 드는 게임의 SV 추정을 위한 샘플 효율성을 개선하는 원칙적인 프레임워크를 제공한다고 주장합니다. 폐쇄형 EIG를 유도하고 다항 시간 복잡도의 효율적인 계산 체계를 구축함으로써, 저자들은 베이지안 실험 설계를 이 영역에 적용하는 데 있어 주요한 장벽을 극복했습니다.

저자들은 ShaplEIG가 반복적인 GP 최적화로 인한 계산 오버헤드를 발생시키지만, 평가 예산이 제한된 상황에서 추정 정확도 면에서 상당한 이득을 제공한다고 겸허히 밝힙니다. 매우 큰 게임이나 가치 함수가 상대적으로 덜 비싼 경우에는 이 오버헤드가 과도할 수 있음을 인정하며, 방법론의 적용 범위를 넓히기 위해 향에는 추가적인 계산 개선에 집중할 것을 제안합니다. 이 연구는 모든 시나리오의 SV 추정을 해결하려는 것이 아니라, 적응적 선택이 결정적인 '비싼 가치 함수' 환경을 구체적으로 타겟팅하고 있습니다.