기술 요약: 검증된 SHAP (VERISHAP)

문제 정의

Shapley Additive Explanations(SHAP) 은 머신러닝 모델의 예측을 입력 특징에 귀속시키는 표준적인 사후 설명 가능성 방법입니다. 그러나 신경망에 대한 정확한 SHAP 값을 계산하는 것은 특징 부분집합에 대한 지수적 탐색 공간 ($2^n$) 으로 인해 계산적으로 처리 불가능한 것으로 널리 간주됩니다. 트리 기반 모델과 가법 모델에서는 정확한 계산이 가능하지만, 일반적인 신경망에 대해서는 #P-난해 (NP-hard) 입니다. 따라서 기존 문헌은 통계적 추정기 (예: KERNELSHAP, FASTSHAP, LEVERAGESHAP) 에 의존합니다. 이러한 추정기들은 두 가지 근본적인 한계에 직면해 있습니다:

1. 부정확성: 이들은 고도로 비선형인 모델이나 강한 특징 상호작용이 있는 시나리오에서 신뢰할 수 없는 근사치를 제공합니다.
2. 진실값 (Ground Truth) 부재: 신경망에 대한 정확한 SHAP 값 계산은 비용이 너무 많이 들어 계산 불가능하므로, 추정기들은 보통 정확한 계산이 가능한 장난감 크기 (toy-sized) 모델에서 평가됩니다. 이러한 설정은 종종 실제 세계의 고차원 신경망으로 일반화되지 못합니다.

방법론: 검증된 SHAP (VERISHAP)

본 논문은 신경망에 대한 정확한 SHAP 값과 증명 가능한 경계를 계산하기 위해 최신 신경망 검증 기술을 활용한 최초의 알고리즘인 VERISHAP을 소개합니다. 이 접근법은 이산적이고 확률적이며 합산이 많은 SHAP 의 특성에 맞춰 분기 - 한정 (branch-and-bound) 검증 기법을 적용합니다.

핵심 알고리즘

VERISHAP 은 특징 공간 (특징 $i$에 대한 모든 연합 $S_i$의 집합) 을 재귀적으로 분할하기 위해 점진적인 분기 - 한정 전략을 사용합니다.

1. 분할: 알고리즘은 포함되는 특징 집합 ($I$) 과 제외되는 특징 집합 ($E$) 을 기반으로 분기 $B$를 정의합니다. 하나의 분기는 $I$에 속한 특징이 존재하고 $E$에 속한 특징이 부재하는 연합의 부분집합을 나타냅니다.
2. 전파를 통한 경계 설정: 각 분기에 대해 알고리즘은 한계 기여도 $\Delta_i(S) = v(S \cup \{i\}) - v(S)$에 대한 하한과 상한을 계산합니다.
   • 이산 집합에 연속 경계 전파 (예: CROWN, IBP) 를 적용하기 위해, 알고리즘은 불리언 특징 마스크 $m \in \{0, 1\}^n$을 연속 영역 $[0, 1]^n$으로 완화합니다.
   • 선형 경계 전파 (LBP)(구체적으로 CROWN-IBP) 를 사용하여 완화된 영역에서의 가치 함수 $v(S)$에 대한 엄격한 경계를 유도합니다.
3. 집계: 전체 SHAP 값 경계는 모든 분기의 가중 경계를 합산하여 계산됩니다:
   $$\phi_i^{(t)} = \sum_{B \in \mathcal{B}^{(t)}} \Lambda_B \Delta_i^B \leq \phi_i \leq \sum_{B \in \mathcal{B}^{(t)}} \Lambda_B \Delta_i^B = \bar{\phi}_i^{(t)}$$
   여기서 $\Lambda_B$는 분기 $B$ 내 연합에 대한 SHAP 가중치의 폐쇄형 합으로, 조합론적으로 유도됩니다.
4. 정제: 알고리즘은 분할할 분기 (MAXDIAM 등의 전략 사용) 와 분할할 특징 (SMEARS 등의 전략 사용) 을 반복적으로 선택하여 경계를 정제하며, 값이 정확히 수렴하거나 원하는 정밀도에 도달할 때까지 이를 반복합니다.

주요 이론적 속성

• 종료: 분할이 결국 단일 연합을 분리하므로, 알고리즘은 유한한 횟수의 반복 (최대 $2^{n-1}$) 후 정확한 SHAP 값으로 종료됨이 보장됩니다.
• 선형 모델의 조기 종료: 선형 모델의 경우, 한계 기여도가 일정하고 LBP 가 선형 조합에 대해 근사 오차를 도입하지 않으므로 알고리즘은 첫 번째 반복에서 종료됩니다.
• 조각별 선형성: ReLU 활성화 신경망의 경우, 분할이 네트워크가 선형적으로 동작하는 영역으로 탐색을 제한할 경우 알고리즘은 조기 종료할 수 있습니다.

주요 기여

1. 신경망을 위한 최초의 정확한 SHAP: VERISHAP 은 일반적인 신경망에 대한 정확한 SHAP 값을 계산하는 최초의 알고리즘이며, 이전의 정확한 방법들보다 수백만 배 더 큰 탐색 공간으로 확장 가능합니다.
2. 증명 가능한 경계: 이 방법은 SHAP 값에 대해 임의로 엄격한 하한과 상한을 제공하여, 완전한 수렴 전에도 신뢰할 수 있는 설명적 통찰을 가능하게 합니다.
3. 진실값 기준: 이전에는 달성할 수 없었던 더 크고 현실적인 탐색 공간에서 통계적 SHAP 추정기를 평가하기 위한 원칙적인 프레임워크를 확립합니다.
4. 검증을 통한 효율성: 신경망을 근사 선형 영역으로 분해하는 것을 활용함으로써, 많은 실제 사례에서 모든 $2^n$개의 연합을 열거하는 것을 피합니다.

실험 결과

저자들은 VERISHAP 을 표형 (UCI 데이터셋) 및 비전 (MNIST, FashionMNIST, CIFAR10, GTSRB) 벤치마크에서 평가했습니다.

• EXACTSHAP 대비 확장성: VERISHAP 은 최첨단 정확한 방법인 EXACTSHAP 보다 훨씬 뛰어난 성능을 발휘합니다. EXACTSHAP 은 $2^{20}$보다 큰 탐색 공간에서 GPU 메모리가 고갈되는 반면, VERISHAP 은 $2^{25}$ ($\approx 3 \times 10^7$개 연합) 까지의 인스턴스에 대해 정확한 값을 계산하고 $2^{60}$ ($\approx 10^{18}$개 연합) 까지의 공간에 대해 엄격한 경계를 제공합니다.
• 추정기와의 비교: 통계적 추정기 (KERNELSHAP, TREEMSR, LEVERAGESHAP) 와 비교했을 때, VERISHAP 은 추정기들이 메모리 제약 내에서 동일한 정확도를 달성하지 못하는 경우가 많음을 보여줍니다. 또한 VERISHAP 은 추정기 성능이 데이터셋에 따라 크게 달라짐을 드러냅니다 (예: TREEMSR 은 트리 기반 모델에 비해 신경망에서 변동성이 큰 성능을 보입니다).
• 아키텍처 다양성: 이 알고리즘은 ReLU, tanh, Swish 활성화 함수를 가진 완전 연결 네트워크는 물론 ResNet 을 포함한 다양한 아키텍처에 대해 정확한 SHAP 값을 성공적으로 계산합니다.
• 수렴: 실험 (예: MNIST) 에서 경계는 정확한 값이 계산되기 훨씬 전 (종종 수 초 내) 에도 유익한 정보 (귀속 패턴 드러냄) 를 제공하며, 정확한 계산은 수십 초가 소요될 수 있습니다.

중요성과 주장

본 논문은 신경망에 대한 정확한 SHAP 계산의 확장성을 위한 첫걸음으로서 VERISHAP 을 위치시킵니다. 그 중요성은 세 가지 영역에 있습니다:

1. 확장성: 신경망 검증을 활용함으로써 이론적 계산 불가능성과 실제 적용 사이의 간극을 메웁니다.
2. 신뢰성: 통계적 근사치에 내재된 불확실성을 해결하기 위해 증명 가능한 보장을 갖춘 '진실값' 설명을 얻을 수 있는 방법을 제공합니다.
3. 평가 프레임워크: 장난감 모델을 넘어 더 큰 탐색 공간에서 SHAP 추정기를 평가하고 개선하기 위한 엄격한 벤치마크를 제공합니다.

저자들은 정확한 SHAP 계산이 여전히 #P-난해이며 VERISHAP 이 특정 복잡한 네트워크에서는 여전히 느릴 수 있음을 인정합니다. 그러나 증명 가능한 경계를 계산할 수 있는 능력과 신경망 검증의 지속적인 개선 가능성은 신뢰할 수 있는 AI 설명 가능성에 대한 기초적인 발전이라고 주장합니다.