기술 요약: 텐서 네트워크를 통한 다루기 쉬운 샤플리 값 및 상호작용 (Tractable Shapley Values and Interactions via Tensor Networks)

문제 정의

샤플리 값(Shapley values)과 그 고차 일반화인 샤플리 상호작용 지수(Shapley Interaction Indices, SII)를 통해 머신러닝 예측을 설명하는 것은 의사결정 지원 및 해석 가능성을 위해 매우 중요합니다. 그러나 이를 계산하는 것은 $n$개의 특성을 가진 모델에 대해 전통적으로 $O(2^n)$의 연산량을 요구하므로 계산적으로 매우 부담스럽습니다. 기존 솔루션들은 다음과 같은 중대한 트레이드오프를 안고 있습니다:

• 구조적 가정: TreeSHAP이나 일반화 가법 모델(GAM)을 위한 방법들은 특정 아키텍처(예: 트리, 선형 모델)에 대해서만 정확합니다.
• 샘플링 기반 근사: KernelSHAP이나 SHAP-IQ와 같은 접근 방식은 과도한 샘플링에 의존하며, 정교한 분산 튜닝이 필요하고 대규모 계산 비용 없이 고차 상호작용으로 확장하는 데 어려움을 겪는 경우가 많습니다.
• 중재 추정(Amortized Estimation): 보조 모델을 훈련하는 방법들은 상당한 훈련 오버헤드를 발생시킬 수 있으며, 설명의 충실도(fidelity)에 대한 이론적 보장을 결여할 수 있습니다.

핵심 과제는 지수적인 열거(enumeration)나 과도한 샘플링 없이, 일반적인 예측기에 대해 샤플리 값과 상호작용을 정확하게(또는 제어된 오차 범위 내에서) 계산하는 것입니다.

방법론: TN-SHAP

저자들은 모든 연합(coalition)을 전수 조사하는 대신 **텐서 네트워크(Tensor Network, TN) 대리 모델(surrogate)**에 대한 몇 번의 평가 스킴을 사용하는 TN-SHAP을 제안합니다. 이 접근 방식은 복잡도를 $O(2^n)$에서 $O(n \cdot \text{poly}(\chi))$로 줄이기 위해 세 가지 핵심 통찰을 활용합니다. 여기서 $\chi$는 텐서 네트워크의 최대 본드 차원(maximal bond dimension)입니다.

1. 다선형 표현 및 계수 추출

이 방법은 예측 함수 $f$가 리프팅된 특성 공간(lifted feature space)에서 다선형 함수 $g$로 잘 근사될 수 있다고 가정합니다. 다선형 전개에서 $f(x) = \sum_{T \subseteq N} c_T \prod_{j \in T} x_j$이며, 연합 값은 텐서 계수의 선형 결합에 해당합니다. 결정적으로, 샤플리 값은 특정 연합 구성원이 아닌 크기별로 집계된 한계 기여도(size-aggregated marginal contributions)(즉, 크기가 $s$인 연합들의 기여도 합)에만 의존합니다.

2. 대각 선택자(Diagonal Selectors) 및 다항식 보간

TN-SHAP은 $2^n$개의 연합을 직접 쿼리하는 대신, 리프팅된 특성 $\tilde{x}_r = [\phi(x_r), 1]^\top$에 적용되는 대각 선택자 행렬(diagonal selector matrices) $S_r(t) = \text{Diag}(t, 1)$를 사용합니다.

• 특징들이 파라미터 $t$에 의해 스케일링된 지점에서 대리 함수 $g$를 평가함으로써, 이 방법은 모든 크기 $s$의 연합들을 결과 다항식 $P(t)$의 $t^s$ 계수로 집계합니다.
• 구체적으로, 타겟 특성 $i$에 대해, 다른 특성들의 모든 부분집합에 대한 한계 기여도를 격리하기 위해 프로브 함수(probe function) $G_i(t)$가 구축됩니다.
• 이를 통해 조합 최적화 문제를 다항식 보간(polynomial interpolation) 문제로 변환합니다. $n$개의 서로 다른 지점(예: 체비쇼프-가우스 노드)에서 $G_i(t)$를 평가함으로써, 시스템은 $\{m_s^{(i)}\}$라는 크기별 집계된 한계 기여도를 복구하기 위해 반데르몽드 선형 시스템(Vandermonde linear system)을 해결합니다.
• 샤플리 값은 이렇게 복구된 계수들의 가중치 합으로 계산됩니다.

3. 텐서 네트워크 대리 모델

규모 있는 데이터에서 다선형 맵의 평가를 용이하게 하기 위해, 계수 텐서를 본드 차원 $\chi$를 가진 텐서 네트워크(TN) (예: Tensor Train 또는 Hierarchical Tree)로 인수분해합니다.

• 특성 맵(Feature Maps): 비선형 실세계 데이터를 처리하기 위해, 스칼라 특성들은 TN에 들어가기 전 학습되거나 설계된 맵 $\phi_i: \mathbb{R} \to \mathbb{R}^{d_i-1}$를 통해 리프팅됩니다. 이는 원래 입력 공간에서의 비선형성을 모델링하면서도 리프팅된 공간에서의 다선형성을 유지합니다.
• 효율성: TN을 통한 각 순방향 패스(forward pass)의 비용은 $O(\text{poly}(\chi))$입니다. 보간을 위해 $O(n)$번의 평가만 필요하므로, $k$차 상호작용을 계산하기 위한 전체 복잡도는 $n$에 대한 다항 시간이 됩니다.

주요 기여

1. 통합 프로브-보간 스킴: $O(2^n)$ 쿼리를 피하고 $O(n)$의 구조화된 순방향 패스만을 사용하여 다선형 TN 대리 모델 상에서 샤플리 값 및 $k$-way 상호작용을 계산하는 정확한 알고리즘을 제공합니다.
2. 특성 맵 강화 대리 모델: 학습된 특성 리프트가 다선형 계산에 필요한 다선형성을 유지하면서도 비선형 모델에 대한 대리 모델의 충실도를 어떻게 개선하는지를 보여주는 프레임워크를 제시합니다.
3. 이론적 보장:
   • 정확성(Exactness): 이 방법은 적합된 다선형 대리 모델 상에서 샤플리 값을 정확하게 계산합니다.
   • 근사 오차(Approximation Error): 원본 모델에 대한 오차는 대리 모델의 최악의 연합 근사 오차($\epsilon$)에 의해 제한됩니다. 샤플리 값의 경우, $|\phi^g_i - \phi^f_i| \leq 2\epsilon$입니다.
   • 계산 가능성(Tractability): 지수 시간에서 다항 시간 $O(n \cdot \text{poly}(\chi) + n^2)$으로의 복잡도 감소를 입증했습니다.

실험 결과

저자들은 합성 다선형 함수와 MLP 교사(teacher) 모델을 사용한 실제 UCI 회귀 데이터셋(Concrete, Diabetes, Energy)에 대해 TN-SHAP을 평가했습니다.

• 합성 검증: 정확히 다선형인 함수들에 대해, TN-SHAP은 이론적 정확성을 달성하며 밀리초 단위의 실행 시간을 기록하여 KernelSHAP-IQ보다 수 차례 더 빠른 성능을 보였습니다 (예: $n=10$일 때 3.5ms vs 18.7ms; $n=50$일 때 19.7ms vs 447.3ms).
• 실제 데이터 정확도: MLP 교사를 사용한 UCI 데이터셋에서:
  • TN-SHAP은 유사한 정확도에서 KernelSHAP-IQ 대비 25~1000배의 벽 시계 시간(wall-clock) 단축을 달est했습니다.
  • 1차($k=1$) 기여도에 대해, TN-SHAP은 실제 정답과 거의 완벽한 코사인 유사도(0.994)를 달성했습니다.
  • 고차 상호작용($k=2, 3$)에서도 TN-SHAP은 샘플링 기반 베이스라인들이 분산 문제로 고전하거나 높은 충실도에 도달하기 위해 훨씬 더 많은 계산 시간이 필요한 상황에서도 경쟁력 있는 정확도를 유지했습니다.
• 순위 절제 실험(Rank Ablation): 실험 결과, 교사 모델의 랭크가 16일 때 학생(student) TN의 랭크 $r=5-6$만으로도 $R^2 > 0.99$ 수준에서 모든 상호작용 차수를 복구하기에 충분함을 보여주었습니다. 낮은 랭크는 고차 상호작용을 과소 적합(underfit)시켰습니다.
• 고차원 안정성: 고차원 합성 환경($D=50, 100$)에서 TN-SHAP은 선형 비용 쿼리 예산 하에서도 높은 대리 모델 충실도($R^2 > 0.95$)와 강력한 Top-$k$ 특성 복구 능력을 유지했습니다.

의의 및 주장

본 논문은 TN-SHAP이 샤플리 계산의 이론적 엄밀함과 실무적 효율성 사이의 간극을 메운다고 주장합니다. 텐서 네트워크의 대수적 구조와 다선형 함수의 효율성을 활용함으로써, 이 방법은 다음을 실현합니다:

• 지수적인 열거 문제를 적은 수의 구조화된 평가 문제로 전환합니다.
• LIME과 같이 제약이 없는 국소 대리 모델에서 흔히 발생하는 충실도 문제를 해결하는 구조적 보장(랭크 경계를 통한)을 제공합니다.
• 로컬 샤플리 설명과 글로벌 가법 구조(GAMs)를 통합합니다. 즉, $k$차 대리 모델을 적합하면 그에 대응하는 GAM 항과 일치하는 정확한 $k$-SII 계수를 얻게 됩니다.
• 샘플링 기반 방법, 특히 샘플링 분산이 높게 나타나는 고차 상호작용 계산에서 효율적인 대안을 제공합니다.

저자들은 이 방법의 성능이 TN 대리 모델의 적합 품질과 특성 맵의 선택에 달려 있다고 언급하지만, 실험 결과는 적절한 특성 리프트와 텐서 랭크만으로도 실제 복잡한 연합 구조를 포착하기에 충분하다는 것을 시사합니다.