기술 요약: QuadraSHAP

문제 제기

Shapley 값은 협력 게임 이론에 기반한 특성 귀속을 제공하여 기계 학습 예측을 설명하는 데 필수적인 도구입니다. 그러나 정확한 계산은 일반적으로 계산이 불가능하며, $2^{d-1}$개의 지수적으로 많은 특성 연합 (coalition) 을 평가해야 합니다. 모델별 방법 (예: TreeSHAP, RKHS-SHAP) 은 구조적 특성을 활용하여 다항 시간 내에 계산을 달성하지만, 종종 수치적 안정성과 계산 효율성 사이의 지속적인 트레이드오프에 직면합니다.

구체적으로, 다항식 보간에 의존하는 방법 (예: Linear TreeSHAP) 은 Vandermonde 역행렬의 조건 불량 (ill-conditioning) 으로 인해 다항식 차수가 증가함에 따라 (나무 깊이 또는 특성 수에 의해 결정됨) 급격한 수치적 불안정성을 겪습니다. 반면, 대수적 재귀 방법 (예: 곱 커널 모델용) 은 안정성을 제공하지만 상당한 산술 비용을 초래합니다. 본 논문은 곱셈 구조를 보이는 광범위한 모델 클래스에 대해 동시에 정확한(또는 거의 정확한), 수치적으로 안정적인, 그리고 계산적으로 효율적인 방법이 필요하다는 점을 해결합니다.

방법론

본 논문은 **곱 게임 (product games)**에 대한 Shapley 값을 계산하는 방법인 QuadraSHAP을 소개합니다. 곱 게임은 연합 가치 $v(S)$가 각 플레이어 항의 곱으로 인수분해되는 협력 게임 ($v(S) = \prod_{j \in S} u_j$) 입니다. 이러한 구조는 트리 기반 모델과 곱 커널을 가진 커널 방법에서 자연스럽게 발생합니다.

1. 적분 표현

핵심 이론적 기여는 $2^{d-1}$개의 부분집합에 대한 가중 합으로 표현되던 곱 게임의 Shapley 값을 정확한 1 차원 적분으로 재구성하는 것입니다. Shapley 가중치의 Beta 함수 표현을 활용하여 저자들은 다음을 유도합니다:
$$\phi_i(v) = (u_i - 1) \int_0^1 \prod_{j \neq i} \left( (1-t) + t u_j \right) dt$$
이 변환은 부분집합 열거나 보간 기반 계수 복원을 필요로 하지 않습니다.

2. 가우스 - 르장드르 구적법

적분은 **가우스 - 르장드르 구적법 (Gauss–Legendre quadrature)**을 사용하여 평가됩니다.

• 정확성: 구적법 노드 수 $m_q$가 $m_q \ge \lceil d/2 \rceil$를 만족하면, 이 방법은 정확한 Shapley 값을 복원합니다.
• 근사: $m_q < \lceil d/2 \rceil$인 경우, 이 방법은 거의 정확한 근사치를 제공합니다. 오차는 베른슈타인 타원 매개변수 $\rho > 1$에 대해 $O(\rho^{-2m_q})$로 제한되며, $m_q$에 대해 기하급수적으로 감소하는 것으로 증명되었습니다. 실험적으로 수백 개의 노드만으로도 수천 개의 특성을 가진 경우에도 고정밀 추정이 가능하며, 이는 이론적 정확성 임계값보다 훨씬 낮습니다.

3. 수치적으로 안정적이고 효율적인 구현

실제 계산적 과제를 해결하기 위해 저자들은 구체적인 알고리즘 최적화를 제안합니다:

• 로그 공간 평가: 고차원에서의 오버플로우 및 언더플로우를 방지하기 위해, 곱셈은 명시적인 부호 추적을 통해 로그 공간에서 평가됩니다. 추정치는 다음과 같이 계산됩니다:
  $$\hat{\phi}_i(v) = (u_i - 1) \sum_{q=1}^{m_q} \omega_q \cdot \text{sgn}(P_q)\text{sgn}(T_{q,i}) \exp\left( \log|P_q| - \log|T_{q,i}| \right)$$
  여기서 $P_q$는 항들의 전체 곱이고 $T_{q,i}$는 특성 $i$에 대한 항입니다.
• 공유 계산: 각 특성마다 "leave-one-out" 곱을 다시 계산하는 대신, 전체 곱을 한 번 계산한 후 특성 $i$에 대한 특정 인자로 나누어 제거합니다. 이로 인해 복잡도가 $O(d^2 m_q)$에서 $O(d m_q)$로 감소합니다.
• 병렬화: 계산은 연관 스캔 원시 연산 (prefix sums) 을 활용하여 로그 공간 축산을 $O(\log d)$ 병렬 시간 내에 수행합니다.

주요 기여

1. 정확한 적분 공식화: 본 논문은 곱 게임에 대한 Shapley 값이 정확한 적분 표현을 허용함을 입증하여 가우스 - 르장드르 구적법의 사용을 가능하게 합니다.
2. 안정성과 효율성: QuadraSHAP 은 안정성 - 효율성 트레이드오프를 해결합니다. 보간 기반 방법 (Linear TreeSHAP 등) 의 수치적 불안정성을 피하면서도 곱 커널 모델에 대한 대수적 재귀 방법보다 훨씬 빠릅니다.
3. 이론적 보장: 이 방법은 $m_q \ge \lceil d/2 \rceil$에 대해 증명 가능한 정확성을 제공하고, 근사 영역에 대해서는 기하급수적 수렴 경계를 제공합니다.
4. 확장 가능한 알고리즘: 저자들은 $O(d m_q)$의 순차 작업과 $O(\log d)$의 병렬 시간을 가진 알고리즘을 유도하여, 이 방법을 수천 개의 특성을 가진 고차원 문제에 확장 가능하게 만듭니다.

실험 결과

저자들은 합성 및 실제 데이터셋에서 QuadraSHAP 을 최신 기준 (TreeSHAP, Linear TreeSHAP, FastTreeSHAP, shapiq, PKeX-Shapley) 과 비교 평가했습니다.

• 트리 앙상블:
  • 속도: QuadraSHAP 은 모든 테스트 구성에서 가장 빠른 수치적으로 안정적인 방법입니다. 대규모 앙상블 ($10^5$개의 잎) 에서 TreeSHAP 보다 35 배, FastTreeSHAP 보다 22.7 배 더 빠릅니다.
  • 안정성: 깊은 트리 영역 (깊이 최대 100) 에서 Linear TreeSHAP 및 TreeSHAP 과 같은 경쟁자들은 Shapley 효율성 공리의 치명적인 위반 (오차가 $10^{186}$ 이상) 을 보입니다. 반면 QuadraSHAP 은 부동소수점 한계 수준 ($\sim 10^{-13}$) 의 정밀도를 유지합니다.
• 곱 커널 방법:
  • 확장성: 곱 커널을 사용한 커널 릿지 회귀의 경우, QuadraSHAP 은 현재 정확한 기준 (PKeX-Shapley) 보다 한 자릿수 더 빠릅니다.
  • 고차원: PKeX-Shapley 는 특성 차원 $d \ge 2000$에서 시간 초과 (300 초 제한) 되는 반면, QuadraSHAP 은 몇 초 내에 설명을 완료합니다 (예: $d=5000$인 경우 7.6 초).
• 근사 품질: 실험은 근사 오차가 노드 수 $m_q$에 따라 기하급수적으로 감소함을 확인했습니다. $d=5000$인 경우, 정확성 임계값 (2500) 보다 훨씬 낮은 400 개의 노드만 사용하여 기계 정밀도에 가까운 정확도를 달성했습니다.

중요성 및 주장

본 논문은 QuadraSHAP 이 곱셈 구조를 가진 모델에 대한 특성 귀속을 위한 통합적이고 강력한 프레임워크를 제공한다고 주장합니다. 적분 표현과 가우스 - 르장드르 구적법을 활용함으로써 다음과 같은 성과를 달성합니다:

• 수치적 견고성: 보간 기반 방법이 실패하는 고차원 및 깊은 트리 환경에서도 안정적으로 유지됩니다.
• 계산적 우위: 정확성이나 제어된 근사를 유지하면서 기존 가장 빠른 방법의 속도와 일치하거나 능가합니다.
• 일반성: 이 공식은 트리 앙상블과 곱 커널 방법을 단일 계산 패러다임 아래 통합합니다.

저자들은 QuadraSHAP 을 이러한 특정 모델 클래스에 대한 가장 빠른 수치적으로 안정적인 방법으로 위치시키며, 복잡하고 고차원인 기계 학습 시스템의 설명 가능성에 대한 실용적인 해결책을 제시합니다.