TreeSHAP: Consistent Individualized Feature Attribution for Tree Ensembles

Digest (CISELQ)

Context: 트리 앙상블(XGBoost, LightGBM, Random Forest)은 실무에서 가장 널리 사용되는 모델이지만, 기존 feature importance(gain, split count, permutation)는 일관성(consistency)을 만족하지 않아 같은 feature가 모델 기여도를 증가시켜도 importance 점수가 감소하는 역설이 존재한다.
Issue: 게임 이론의 Shapley value는 유일한 consistent & locally accurate attribution을 제공하지만, 계산 복잡도가 O(2^M)으로 feature 수 M에 지수적이어서 실제 트리 앙상블에 적용 불가능했다.
Solution: 트리 구조를 활용하여 각 트리 경로에서 Shapley value를 다항 시간 O(TLD^2) (T=트리 수, L=최대 리프 수, D=최대 깊이)에 정확히 계산하는 TreeSHAP 알고리즘을 제안한다.
Evidence: XGBoost/LightGBM에 구현하여 수천 배의 속도 향상을 달성하고, 사용자 연구에서 인간 직관과 더 높은 일치도, supervised clustering에서 우월한 성능을 보였다.
Limit: Path-dependent(training distribution) 근사는 독립성 가정을 요구하며, interventional 버전은 background dataset 크기에 비례하는 추가 비용이 필요하다.
Question: Feature 간 상관이 강한 실세계 데이터에서 path-dependent vs interventional TreeSHAP의 해석 차이를 어떻게 조율할 것인가?

섹션별 요약

Introduction

기존 tree-based feature attribution 방법(Saabas, gain-based, permutation)이 inconsistency 문제를 겪음을 보이고, Shapley value 기반 SHAP이 유일한 해결책이지만 계산량이 문제였음을 지적한다. 저자들은 (1) 트리 앙상블용 exact polynomial SHAP 알고리즘, (2) SHAP interaction values, (3) supervised clustering, (4) 새로운 시각화를 기여로 제시한다.

Methods

트리의 각 리프가 도달 경로상 feature 조건을 나타낸다는 구조적 특성을 이용하여, 각 feature가 “present/absent”일 때의 conditional expectation E[f(x)|x_S]를 동적 프로그래밍으로 계산한다. Algorithm 1은 O(TL 2^M)의 naive 버전이며, Algorithm 2는 각 경로에 대해 “extending/unwinding”으로 Shapley weight를 O(D^2) 내에 누적하여 전체 O(TLD^2)을 달성한다. SHAP interaction value는 Shapley interaction index를 트리상에서 O(TLD^2 M)로 계산한다.

Results (+table)

평가 항목	Baseline	TreeSHAP
계산 복잡도	O(TL 2^M)	O(TL D^2)
Consistency	불만족 (gain, Saabas)	만족
Local accuracy	불만족	만족
User study agreement	낮음	높음
Supervised clustering (NHANES)	baseline	개선

Discussion

Shapley value가 유일한 consistent local attribution임을 보이므로, 해석 방법 선택의 이론적 불확실성을 제거한다. 실무적으로 XGBoost/LightGBM에 통합되어 대규모 데이터에서도 실시간 설명이 가능하다. Interaction value는 “main effect”와 “pairwise interaction”을 분리하여, 단일 feature 설명의 한계를 넘는다.

Insights

Tree 구조는 Shapley value의 조합 폭발을 DP로 접을 수 있는 특수 구조다.
“Consistency”는 모델이 변할 때 feature importance의 단조성을 보장하는 필수 속성이며, 기존 gain-based 측도는 이를 위반한다.
Supervised clustering(feature attribution 공간에서의 클러스터링)은 raw feature 기반보다 outcome-relevant subgroup을 더 잘 포착한다.

Discussion Points

Interventional vs path-dependent TreeSHAP: causal 해석에는 전자, 데이터 분포 충실성에는 후자가 적합.
Feature correlation이 강할 때 attribution 분배의 모호성.
Global importance = mean(|SHAP|)의 정당성과 한계.

메타데이터

항목	값
저자	Scott M. Lundberg, Gabriel G. Erion, Su-In Lee
발표	arXiv preprint (2018)
분야	XAI / Interpretable ML / Theory
핵심 알고리즘	TreeSHAP (Algorithm 1/2), SHAP Interaction Values
전제 이론	Shapley value (Shapley 1953), SHAP (Lundberg & Lee 2017)
구현	XGBoost, LightGBM, CatBoost, scikit-learn(GBT) 내장

왜 이 연구를 하는가?

실제 산업과 의료에서 XGBoost/LightGBM이 표준 모델로 사용되지만, “왜 이 예측이 나왔는가”에 대한 설명은 gain, split count, Saabas 같은 inconsistent한 방식에 의존하고 있었다. 이들은 동일 모델에서도 방법에 따라 순위가 뒤집히며, 심지어 feature 영향이 커져도 importance가 감소할 수 있다. Shapley value는 axiomatic하게 유일한 해답이지만 지수 복잡도로 인해 실무 적용이 불가능했다. 따라서 트리 앙상블의 구조적 특수성을 활용한 효율적 exact 계산 알고리즘이 필요했고, 이를 해결하면 수십억 예측을 실시간으로 설명할 수 있는 인프라가 만들어진다.

방법 (Method)

flowchart TD
    A[입력: 학습된 트리 앙상블 f, 인스턴스 x] --> B{각 트리 t에 대해}
    B --> C[리프 경로 상의 feature 집합 S_path 추출]
    C --> D[노드별 cover 기반 E_f_x_S 계산]
    D --> E[Algorithm 2: extend/unwind로<br/>Shapley weight DP]
    E --> F[feature j의 기여 phi_j 누적]
    F --> G{모든 트리 합산}
    G --> H[phi_j x = sum_t phi_j_t x]
    H --> I[Local explanation 출력]
    I --> J[Global = mean_i phi_j x_i<br/>Interaction = SHAP interaction index]

복잡도: naive O(TL 2^M) → 제안 O(TL D^2). Interaction 버전은 O(TL D^2 M).

발견

실험/분석	주요 결과
실행 시간 벤치마크	기존 모델 독립적 SHAP 대비 수천~수만 배 속도 향상
Consistency 검증	gain/Saabas는 consistency 위반 사례 존재, TreeSHAP는 항상 만족
사용자 연구	인간 직관 대비 설명 일치도 유의미하게 증가
Supervised clustering (NHANES I 생존 데이터)	raw-feature 기반 대비 임상적으로 의미 있는 subgroup 분리
SHAP dependence plot	partial dependence plot보다 interaction 가시화 우수
의료 데이터 적용	개별 환자 risk 분해로 임상 해석 가능성 제공

이론적 의의

Uniqueness: Efficiency, symmetry, dummy, additivity를 만족하는 유일한 attribution이 Shapley value임을 재확인하고, 이를 트리 앙상블에 정확히 적용할 수 있음을 증명했다.
Tractability bridge: Exponential 조합 공간을 tree path 구조로 축약하는 것은 이후 GraphSHAP, FastSHAP 등 구조 활용 attribution 연구의 출발점이 되었다.
Interaction decomposition: f(x) = phi_0 + sum phi_i + sum_{i<j} Phi_{ij}로 예측을 main + pairwise interaction으로 직교 분해하는 이론적 틀을 제시했다.
Explainable AI의 표준화: XGBoost/LightGBM에 내장됨으로써 SHAP이 사실상 tabular ML 해석의 de facto standard가 되었다.

재현성 및 신뢰도 평가

항목	평가	근거
알고리즘 명시	A	Algorithm 1/2 의사코드 제공
코드 공개	A	`shap` 패키지(오픈소스) + XGBoost/LightGBM 내장
실험 재현성	A	공개 데이터(NHANES, UCI) + 결정론적 알고리즘
이론 증명	A	Shapley axiom 기반, 복잡도 증명 포함
한계 기술	B	Interventional vs path-dependent 구분이 후속 연구에서 더 명확화됨
종합	A	이론·구현·공개 모두 상위 수준

원자적 인사이트

Tree path = Shapley coalition structure: 트리의 리프 경로가 자연스럽게 “present features”의 집합을 정의하므로, Shapley value 계산에서 지수적 coalition 열거를 경로별 DP로 축약할 수 있다. 이는 “모델 구조가 attribution 계산 복잡도를 결정한다”는 원리의 대표 사례다.
Consistency는 axiom이지 metric이 아니다: gain이나 permutation importance를 “더 잘 조정”해서 고칠 수 없고, Shapley axiom을 만족하는 attribution만이 수학적으로 일관성을 보장한다. 따라서 방법 선택은 경험적 비교가 아닌 공리적 유일성 논증으로 결정된다.
Local → Global 자연 확장: mean(|phi_j|)로 global importance를 얻는 구조는 instance-level 설명과 dataset-level 설명을 동일한 단위로 연결하는 드문 장점을 제공한다.

핵심 용어 정리

Shapley value (phi_i): 협력 게임에서 i번째 플레이어의 공정한 기여 분배. f(x) = phi_0 + sum_i phi_i를 만족.
Local accuracy (Efficiency): 개별 예측에 대한 attribution 합이 예측값과 baseline의 차이와 같아야 한다는 공리.
Consistency (Monotonicity): 모델이 변해 feature의 기여가 커지면 attribution도 감소하지 않아야 한다는 공리.
Path-dependent TreeSHAP: 학습 데이터 분포 기반 조건부 기대값 사용(트리의 cover 가중치).
Interventional TreeSHAP: background dataset을 샘플링하여 do-calculus 의미의 개입적 기대값 사용.
SHAP interaction value (Phi_{ij}): Shapley interaction index를 트리상에서 계산한 pairwise interaction 기여.
Supervised clustering: raw feature가 아닌 SHAP 값 공간에서 수행하는 클러스터링으로, outcome-relevant subgroup 식별에 유리.

XAI SHAP TreeSHAP ShapleyValues TreeEnsembles FeatureAttribution Interpretability Theory

Juhyeon's Blog

탐색기

TreeSHAP- Consistent Individualized Feature Attribution for Tree Ensembles