SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism

이 논문은 **텐서 네트워크 (Tensor Networks, TNs)**를 사용하여 SHAP(Shapley Additive Explanations) 설명을 계산하는 문제의 계산 복잡성을 분석하고, 특정 구조 하에서 이 계산이 효율적으로 가능함을 증명하는 이론적 연구입니다. 기존에 SHAP 계산이 신경망과 같은 복잡한 블랙박스 모델에서는 NP-난해 (NP-hard) 임이 알려져 있었으나, 본 연구는 텐서 네트워크의 구조적 특성을 활용하여 이 한계를 극복하고 병렬 계산을 통한 다항 로그 시간 (poly-logarithmic time) 해결 가능성을 제시합니다.

다음은 논문의 주요 내용을 기술적으로 요약한 것입니다.

1. 문제 정의 (Problem)

• SHAP 계산의 비효율성: SHAP은 모델 예측에 대한 공정한 특징 기여도를 제공하는 표준적인 설명 방법이지만, 일반적인 신경망과 같은 표현력이 높은 모델에서는 SHAP 값을 정확히 계산하는 것이 NP-난해 (NP-hard) 또는 #P-난해 (#P-hard) 임이 알려져 있습니다.
• 기존 접근법의 한계: 기존 연구들은 주로 결정 트리 (Decision Trees) 와 같은 단순한 모델에 국한되거나, 근사치 (KernelSHAP 등) 를 사용하여 계산 비용을 줄이는 데 초점을 맞추었습니다.
• 연구 목표: 보다 표현력이 풍부한 모델 클래스인 **텐서 네트워크 (TNs)**에 대해 SHAP 계산의 정확한 복잡성을 분석하고, 특정 하위 클래스 (Tensor Trains) 에서는 효율적인 정확한 계산이 가능한지 규명하는 것입니다.

2. 방법론 (Methodology)

2.1. 텐서 네트워크 기반 SHAP 프레임워크

저자들은 SHAP 값을 계산하기 위한 일반적인 텐서화된 프레임워크를 제안했습니다.

• 마진 SHAP 텐서 (Marginal SHAP Tensor): SHAP 공식을 텐서 연산으로 재정의하여, 모델 $M$과 데이터 분포 $P$를 텐서 네트워크로 표현합니다.
• 구축 알고리즘:
  1. 수정된 가중 연합 텐서 (Modified Weighted Coalitional Tensor, $\tilde{W}$): SHAP 가중치를 인코딩하는 텐서를 생성합니다.
  2. 마진 가치 텐서 (Marginal Value Tensor, $V_{(M,P)}$): 모델과 분포 텐서의 합성곱을 통해 생성합니다.
  3. 합성곱 (Contraction): 위 두 텐서를 특정 인덱스 간에 합성곱하여 최종 SHAP 행렬을 얻습니다.
• 일반 TN 의 복잡성: 임의의 구조를 가진 일반 텐서 네트워크에 대해서는 SHAP 계산이 #P-난해임을 증명했습니다.

2.2. 텐서 트레인 (Tensor Trains, TT) 구조의 활용

• TT 구조의 특성: 텐서 트레인은 고차 텐서를 1 차원 체인 형태의 3 차 텐서 코어 (cores) 로 분해하는 구조로, 계산 효율성이 뛰어납니다.
• 병렬 계산 가능성: TT 구조를 가진 모델과 분포에 대해서는 SHAP 계산이 NC (Nick's Class) 복잡도 클래스에 속함을 증명했습니다. 이는 다항 로그 시간 (poly-logarithmic time) 내에 병렬 프로세서를 사용하여 해결 가능함을 의미합니다.
• 구체적 알고리즘: TT 합성곱 연산은 병렬 스캔 (parallel scan) 전략을 사용하여 로그 깊이의 회로로 구현할 수 있습니다.

2.3. 파라미터화 복잡도 분석 (Binarized Neural Networks)

• 이진 신경망 (BNN) 분석: BNN 을 텐서 네트워크로 매핑하여 구조적 파라미터 (깊이, 너비, 희소성) 가 SHAP 계산 난이도에 미치는 영향을 분석했습니다.
  • 깊이 (Depth): 깊이가 고정되어 있어도 SHAP 계산은 여전히 NP-난해입니다.
  • 너비 (Width): 네트워크의 너비가 고정되면 계산이 XP (slice-wise Polynomial) 클래스에 속하며, 다항 시간이 가능합니다.
  • 너비 + 희소성 (Width + Sparsity): 너비와 희소성 (reified cardinality) 이 모두 고정되면 **FPT (Fixed-Parameter Tractable)**가 되어, 네트워크 크기에 관계없이 효율적으로 계산 가능합니다.

3. 주요 기여 (Key Contributions)

1. 일반 TN 을 위한 정확한 SHAP 알고리즘: 임의 구조의 텐서 네트워크에 대해 정확하고 검증 가능한 SHAP 설명을 생성하는 최초의 알고리즘을 제시했습니다.
2. TT 를 위한 NC 복잡도 증명: 텐서 트레인 (TT) 모델에서 SHAP 계산이 다항 로그 시간에 병렬 계산 가능함을 증명했습니다. 이는 기존에 알려진 SHAP 계산 가능 모델 (예: 트리 기반 모델) 보다 훨씬 표현력이 높은 모델 클래스에 대한 확장입니다.
3. 다른 ML 모델에 대한 복잡도 개선: TT 로의 환원 (reduction) 을 통해 결정 트리, 트리 앙상블, 선형 RNN, 선형 모델 등에 대한 SHAP 계산 복잡도가 기존 연구보다 강화됨을 보였습니다. 즉, 이 모델들도 병렬화를 통해 다항 로그 시간에 계산 가능해지며, 더 복잡한 특징 의존성을 가진 분포 하에서도 적용 가능합니다.
4. BNN 에 대한 세밀한 복잡도 분석: 신경망의 SHAP 계산 난이도가 '깊이'가 아닌 **'너비 (Width)'**에 의해 결정된다는 중요한 통찰을 제공했습니다. 특히 너비와 희소성이 제한된 BNN 은 효율적으로 해석 가능함을 증명했습니다.

4. 결과 (Results)

• 이론적 결과:
  • 일반 TN: SHAP 계산은 #P-난해.
  • TT 모델: SHAP 계산은 NC2 에 속함 (병렬 다항 로그 시간).
  • BNN: 깊이 고정 시 NP-난해, 너비 고정 시 XP, 너비 + 희소성 고정 시 FPT.
• 실용적 의미:
  • 기존에 해석이 불가능하거나 근사치만 사용되던 복잡한 모델 (선형 RNN, 트리 앙상블 등) 에 대해 정확한 SHAP을 병렬 하드웨어를 통해 빠르게 계산할 수 있는 이론적 토대를 마련했습니다.
  • 신경망 설계 시 SHAP 해석 가능성을 고려하여 너비를 제한하거나 희소성을 도입하는 것이 계산적 효율성을 높이는 핵심 전략임을 시사합니다.

5. 의의 및 중요성 (Significance)

• 해석 가능성 (XAI) 의 이론적 확장: SHAP 계산의 복잡성 한계를 텐서 네트워크라는 수학적 도구를 통해 확장하고, 어떤 조건에서 해석이 '정확하게' 그리고 '효율적으로' 가능한지 명확히 정의했습니다.
• 병렬 컴퓨팅의 가능성 제시: SHAP 계산이 단순히 순차적인 연산이 아니라, 병렬 처리를 통해 극도로 가속화될 수 있음을 이론적으로 증명하여 대규모 모델에 대한 실시간 설명 가능성의 길을 열었습니다.
• 모델 설계에 대한 통찰: 신경망의 '깊이'보다 '너비'가 해석 가능성의 병목 현상임을 지적함으로써, 향후 해석 가능한 AI 모델 설계 시 구조적 제약 (너비 제한, 희소화) 을 고려해야 함을 강조합니다.

요약하자면, 이 논문은 텐서 네트워크를 매개체로 하여 SHAP 계산의 복잡성을 재정의하고, 텐서 트레인 구조와 병렬 계산을 통해 기존에 불가능했던 복잡한 모델들의 정확한 해석을 가능하게 하는 이론적 돌파구를 제시했습니다.