기술 요약: Quadrature-TreeSHAP

문제 정의

트리 앙상블 모델 (예: XGBoost, Random Forests) 에 대한 설명 가능성은 Shapley 값에 크게 의존합니다. Path-Dependent SHAP 은 효율성으로 인해 표준 접근법이지만, 기존 방법들은 깊이 의존적 실행 시간, 수치적 안정성, 그리고 고차 상호작용 지원과 관련하여 상당한 트레이드오프에 직면해 있습니다.

현재 최첨단 방법들은 다음과 같은 특정 한계를 보입니다:

• TreeSHAP 및 GPUTreeSHAP는 $O(MTLD^2)$의 시간 복잡도로 작동합니다 (여기서 $M$은 샘플, $T$는 트리, $L$은 리프, $D$는 깊이).
• FastTreeSHAP v2 및 Woodelf는 복잡도를 $O(MTLD)$로 줄이지만, 깊이에 대해 지수적으로 증가하는 전처리 단계를 도입하여 깊은 트리에서는 실용적이지 않습니다.
• Linear TreeSHAP은 $O(MTND)$를 달성하지만, 단항식 기저 (monomial basis) 에서의 연산으로 인해 수치적 불안정성을 겪습니다.
• TreeGrad-Shap은 기울기 형식을 통해 안정성을 개선하지만 1 차 귀속 (attributions) 으로 제한됩니다.
• TreeSHAP-IQ는 고차 상호작용으로 확장되지만, 복잡도가 $O(MTLD \binom{F-1}{s-1})$로, 특성 수 ($F$) 와 상호작용 차수 ($s$) 가 증가함에 따라 성능이 크게 저하됩니다.

방법론

저자들은 Gauss–Legendre 구적법과 가중 Banzhaf 상호작용 다항식을 기반으로 한 Path-Dependent TreeSHAP 의 재형식화인 Quadrature-TreeSHAP을 제안합니다.

1. 이론적 기반

이 방법은 Shapley 값과 가중 Banzhaf 값 사이의 관계를 활용합니다.

• 가중 Banzhaf 다항식: 결정 트리 리프 $v$에 대해, 포함 확률 $p$에서 특성 부분집합 $S$에 대한 Path-Dependent 가중 Banzhaf 상호작용 값은 다항식 $B^{(S)}_{p,v}$로 표현됩니다. 이 다항식은 리프의 경로 구조와 엣지 가중치에서 유도됩니다.
• 적분 복원: Shapley 상호작용 값은 참여 확률 $p \in [0, 1]$에 대해 이러한 Banzhaf 다항식을 적분하여 복원됩니다:
  $$SII^{(S)}(f_v) = \int_0^1 B^{(S)}_p(f_v) \, dp$$
• 구적법 근사: 기호적 적분 대신 저자들은 Gauss–Legendre 구적법을 사용하여 이 적분을 평가합니다. 적분은 고정된 노드 $t_m$에서 평가된 다항식의 가중 합으로 근사됩니다:
  $$SII^{(S)}_v \approx \sum_{m=1}^n w_m B^{(S)}_{t_m, v}$$

2. 알고리즘 구현

• 고정점 형식: 알고리즘은 트리의 단일 깊이 우선 탐색 (DFS) 을 수행합니다. 탐색 중에는 다항식을 기호적으로 확장하는 대신 고정된 Gauss–Legendre 노드 집합(일반적으로 8 개) 에서 경로 다항식의 값을 전파합니다.
• 복잡도 감소:
  • 이론적으로 차수-$s$ 상호작용에 대한 피적분 함수의 차수는 최대 $d-s$입니다 (여기서 $d$는 경로상의 최대 고유 특성 수).
  • 실제로 저자들은 8 개의 고정 구적점이 매우 깊은 트리에서도 기계 정밀도 (float32) 에 도달하기에 충분함을 입증했습니다.
  • 이는 내부 계산에서 트리 깊이 $d$에 대한 의존성을 제거하여, 1 차의 경우 유효 복잡도를 $O(MTN \lceil d/2 \rceil)$에서 $O(MTN)$으로, 차수-$s$상호작용의 경우$O(MTN d^s)$에서$O(MTN d^{s-1})$로 감소시킵니다.
• 하드웨어 가속: 계산이 모든 경로에 대해 동일한 고정된 점 집합을 평가하는 것을 포함하므로 연산이 규칙적입니다. 이는 GPUTreeSHAP 이 필요로 하는 bin-packing 및 스케줄링 오버헤드를 제거하면서 CPU 에서 효율적인 SIMD(단일 명령어 다중 데이터) 실행과 GPU 에서 SIMT(단일 명령어 다중 스레드) 실행을 가능하게 합니다.

주요 기여

1. 임의 차수 상호작용 알고리즘: 이 논문은 TreeSHAP-IQ 의 최첨단 복잡도를 $O(MTLD \binom{F-1}{s-1})$에서 $O(MTN d^s)$로 개선하는 임의 차수 Shapley 상호작용 값을 계산하는 알고리즘을 제시합니다. 이는 특성 수가 트리 깊이보다 많을 때 ($F > D \ge d$) 상당한 이득을 제공합니다.
2. 구적법 기반 재형식화: 저자들은 8 개의 Gauss–Legendre 점이 Shapley 값 및 상호작용에 대해 기계 정밀도에 도달하기에 충분함을 이론적 및 실증적으로 분석하여, 실제로 실행 시간을 트리 깊이에서 실질적으로 분리했습니다.
3. 수치적 안정성: 단항식 기저에서 계수를 확장하는 대신 유계 양수 노드에서 요약 다항식을 평가함으로써, 이 방법은 치명적인 상쇄 (catastrophic cancellation) 를 피합니다. 저자들은 Quadrature-TreeSHAP 이 특히 깊은 앙상블에 대해 TreeSHAP 보다 수치적으로 더 안정적이라고 주장합니다.
4. 하드웨어 효율적 구현: 이 방법은 CPU 용 C++ 로 구현되었으며 GPU 용으로 XGBoost 에 통합되었습니다. 벡터화 (CPU 는 4 점, GPU 는 32 점) 를 활용하여 기존 구현 대비 상당한 속도 향상을 달성했습니다.
5. 오픈 소스 통합: 구현은 오픈 소스로 공개되었으며 XGBoost 라이브러리에 통합되어 (TreeSHAP 백엔드 교체), 표준 API 호출 (pred_contribs=True 및 pred_interactions=True) 을 통해 접근 가능합니다.

실험 결과

저자들은 소규모, 대규모, 희소 영역에 걸쳐 12 개의 XGBoost 벤치마크 앙상블 (Adult, CalHousing, CovType, Fashion-MNIST) 에서 Quadrature-TreeSHAP 을 평가했습니다.

• 1 차 (Shapley 값):
  • CPU: TreeSHAP 보다 1.06 배에서 10.59 배 빠름 (중앙값 3.84 배).
  • GPU: GPUTreeSHAP 보다 1.84 배에서 6.95 배 빠름.
• 2 차 (쌍별 상호작용):
  • CPU: TreeSHAP 보다 3.80 배에서 58.11 배 빠름 (중앙값 12.86 배).
  • GPU: GPUTreeSHAP 보다 최대 6.65 배 빠름 (다만 GPUTreeSHAP 은 특정 작은 깊이 작업 부하에서 여전히 경쟁력이 있음).
• 고차 상호작용 (Python 벤치마크):
  • 3 차 상호작용에 대해 TreeSHAP-IQ 와 비교했을 때, Quadrature-TreeSHAP 은 18.73 배에서 26.49 배 빨랐습니다.
  • CovType-희소 데이터셋에서 TreeSHAP-IQ 대비 속도 향상은 상호작용 차수가 증가함에 따라 커져, 6 차에서 1209.37 배에 달했습니다.
• 수치적 안정성:
  • 깊이가 증가하는 Fashion-MNIST-희소 벤치마크에서 TreeSHAP 은 깊이 32 를 넘어가면 불안정해졌습니다. Quadrature-TreeSHAP 은 6–8 개의 점으로 높은 정확도를 유지하며 안정적으로 작동했습니다.

의의

이 논문은 Quadrature-TreeSHAP 이 Path-Dependent SHAP 에 대한 수치적으로 안정적이고, 하드웨어 효율적이며, 상호작용을 인지하는 재형식화를 제공한다고 주장합니다. 기호적 다항식 연산에서 고정점 구적법으로 전환함으로써, 이 방법은 깊이 의존성과 수치적 안정성 사이의 트레이드오프를 해결합니다. 이는 이전 방법들의 지수적 복잡성이나 불안정성으로 인해 이전에 방해받았던 깊은 트리에서의 고차 상호작용 효율적 계산을 가능하게 합니다. XGBoost 에의 통합은 라이브러리 사용자 및 광범위한 shap 패키지 사용자에게 즉각적인 실용적 유용성을 보장합니다.