Proxy-Based Approximation of Shapley and Banzhaf Interactions

기술적 요약: Shapley 및 Banzhaf 상호작용에 대한 프록시 기반 근사

문제 제기
현대 기계 학습 응용 분야는 모델 행동을 해석하기 위해 협력 게임 이론에 점점 더 의존하고 있으며, 특히 개별 특징에 대한 기여도를 귀속시키기 위해 Shapley 값과 Banzhaf 값을 사용합니다. 그러나 복잡하고 비선형적인 역학을 이해하는 것은 종종 단일 효과뿐만 아니라 고차 상호작용(특징의 부분집합) 을 분석하는 것을 요구합니다. 정확한 카디널 - 확률론적 상호작용 지수를 계산하는 것은 연합 공간 ($2^n$) 의 기하급수적 성장으로 인해 특징의 수가 많을 때 ($n$) 계산적으로 불가능합니다.

기존 추정기들은 속도와 정확도 사이에 치명적인 트레이드오프에 직면해 있습니다:

• 샘플링 기반 방법(예: SHAP-IQ, KernelSHAP-IQ) 은 종종 정확하지만, 방대한 수의 고차 항에 적합하기 위해 비현실적인 샘플 예산을 요구하며, 상호작용 차수에 따라 잘 확장되지 않는 높은 분산을 겪습니다.
• 프록시 기반 방법(예: ProxySPEX) 은 속도를 제공하지만 트리 대리 모델에서 푸리에 기반 추출에 의존합니다. 이 접근 방식은 트리 깊이에 대해 기하급수적인 복잡성을 겪으며 종종 정확도를 훼손하는 과감한 절단을 요구합니다. furthermore, 기존 프록시 방법들은 일반적으로 기본 가치 함수가 아닌 프록시의 상호작용을 반환하여 편향을 도입합니다.

방법론: ProxySHAP
저자들은 ProxySHAP을 제안합니다. 이는 트리 기반 프록시 모델의 샘플 효율성과 잔차 보정을 통한 일관성으로 가는 원칙적인 경로를 조화시키는 프레임워크입니다. 이 방법은 대상 상호작용 지수 $\phi^p_S(\nu)$를 두 구성 요소로 분해합니다:
$$\phi^p_S(\nu) = \underbrace{\phi^p_S(\hat{\nu}_T)}_{\text{정확한 프록시}} + \underbrace{\phi^p_S(\nu - \hat{\nu}_T)}_{\text{잔차}}$$

1. 프록시 피팅 (1 단계): XGBoost, LightGBM 과 같은 트리 기반 모델이나 상호작용 특징이 포함된 선형 모델을 샘플링된 연합에 대해 훈련하여 기본 가치 함수 $\nu$를 근사합니다.
2. 정확한 프록시 추출 (2 단계): 이전 방법들이 푸리에 계수를 추출하는 것과 달리, ProxySHAP 은 개입형 TreeSHAP 의 다항식 시간 일반화를 도입합니다. 이를 통해 트리 구조에서 직접 Shapley 와 Banzhaf 를 포함한 임의의 카디널 - 확률론적 상호작용 지수를 정확하게 계산할 수 있습니다.
   • 이 방법은 트리 리프에 의해 정의된 지시 게임의 Möbius 표현을 활용합니다.
   • 이는 푸리에 기반 추출의 기하급수적 $O(4^d)$ 복잡성 (여기서 $d$는 트리 깊이) 을 피하여 상호작용당 $O(n_{nodes})$ 실행 시간을 달성합니다.
3. 잔차 조정: 프록시가 $\nu$와 완벽하게 일치하지 않아 발생하는 편향을 보정하기 위해, 이 방법은 **최대 샘플 재사용 (MSR)**을 사용하여 잔차 게임 $(\nu - \hat{\nu}_T)$의 상호작용을 추정합니다.
   • 이 논문은 $k$차 상호작용에 대한 MSR 추정기의 분산이 $O(n^{k-1}/|T|)$로 스케일링된다는 이론적 분석을 제공합니다.
   • 따라서 저자들은 MSR 조정이 유익한 조건을 유도합니다: 주로 저차원 설정 ($n < 30$) 이거나 샘플링 예산 $|T|$가 $n^{k-1}$에 비해 충분히 큰 경우입니다. 대규모 게임의 고차 상호작용의 경우, 보정의 분산이 편향 감소보다 더 클 수 있습니다.

주요 기여

1. ProxySHAP 프레임워크: 트리 기반 프록시와 잔차 보정을 결합한 새로운 추정 전략으로, 고차 상호작용의 효율적이고 정확한 근사를 가능하게 합니다.
2. 이론적 발전:
   • 트리 앙상블에서 정확한 카디널 - 확률론적 상호작용 지수를 추출하기 위한 폐쇄형 다항식 시간 알고리즘 유도. 이는 이전 푸리에 기반 방법들의 기하급수적 깊이 의존성을 우회합니다.
   • 고차 상호작용에 대한 MSR 의 분산 증가에 대한 공식적 특성화. 잔차 조정이 성능을 향상시키거나 저하시키는 명시적 조건 ($n$, 예산, 상호작용 차수 $k$ 기준) 을 확립합니다.
3. 실증적 성능: 47 개 데이터셋 (표, 비전, 언어, 그래프, 비전 - 언어) 에 걸친 광범위한 벤치마킹은 ProxySHAP 이 새로운 최첨단 표준을 설정함을 보여줍니다. 이는 작은 예산 영역 (여기서 ProxySPEX 를 능가함) 과 큰 예산 영역 (여기서 KernelSHAP-IQ 를 능가함) 모두에서 가장 낮은 오차를 달성합니다.

결과

• 정확도: ProxySHAP 은 상대 평균 제곱 오차 (MSE) 측면에서 일관되게 베이스라인 (KernelSHAP-IQ, ProxySPEX, SHAP-IQ) 을 능가합니다. 수천 개의 특징을 가진 대규모 응용 (예: $n=1776$인 Bioresponse) 에서 ProxySHAP 은 다른 방법들이 계산적으로 불가능하거나 부정확해지는 상황에서도 효과적입니다.
• 효율성: 다항식 시간 추출 알고리즘은 푸리에 기반 추출에 비해 특히 트리 깊이가 증가함에 따라 10 배에서 1000 배에 이르는 속도 향상을 제공합니다.
• 하류 작업: SigLIP-2 비전 - 언어 모델 (FIxLIP 게임) 설명에 대한 특정 응용에서 ProxySHAP 은 선형 회귀 베이스라인과 ProxySPEX 에 비해 우월한 충실도 (삽입 - 삭제 곡선 아래 면적으로 측정) 를 보여주었습니다.
• 하이퍼파라미터 민감도: 이 연구는 프록시의 품질이 결정적임을 강조합니다. 하이퍼파라미터 최적화 (HPO) 는 성능을 크게 향상시키며, 비용과 정확도의 균형을 맞추기 위해 "HPO 기반" 기본 구성 (많은 수의 얕은 트리 사용) 이 제안됩니다.

중요성과 주장
이 논문은 ProxySHAP 이 상호작용 추정에서 속도와 정확도 사이의 오랜 트레이드오프를 해결한다고 주장합니다. 트리 프록시에 대한 정확한 추출 메커니즘과 잔차 보정을 위한 이론적으로 근거 있는 전략을 제공함으로써, 현대 AI 시스템의 복잡한 종속성을 확장 가능하게 정량화할 수 있게 합니다. 저자들은 그들의 방법이 특히 다음과 같은 경우에 가치가 있다고 강조합니다:

• 대규모 응용: 정확한 계산이 불가능한 수천 개의 특징을 가진 데이터셋 처리.
• 고차 상호작용: 비전 - 언어 모델과 같은 교차 모드 종속성 이해와 복잡한 특징 시너지에 중요한 쌍별 효과를 넘어선 상호작용에 대한 신뢰할 수 있는 추정 제공.
• 실제 배포: 다양한 예산 제약과 모델 유형에 걸쳐 견고하며 확장 가능한 C++ 구현을 지원하는 "최첨단" 추정기 제공.

저자들은 approximation 품질이 피팅된 프록시에 의존하며 (신중한 하이퍼파라미터 튜닝 필요) 잔차 보정의 분산이 매우 고차원 설정에서 고차 상호작용에 대한 유용성을 제한한다는 점을 겸손하게 지적합니다. 향후 작업은 더 유연하게 확장되는 대체 프록시 클래스와 잔차 추정기를 탐구하는 것이 제안됩니다.