TreeSHAP-IQ 논문 리뷰(작성중)
| Venue | Link |
|---|---|
| AAAI 2024 | AAAI Proceedings |
논문이 해결하려는 문제
Muschalik et al. [9]의 Beyond TreeSHAP은 tree ensemble model의 prediction을 설명할 때, 단일 feature attribution을 넘어서 feature interaction까지 효율적으로 계산하는 방법을 제안한다. 논문에서 제안하는 알고리즘 이름은 TreeSHAP-IQ이다. 여기서 IQ는 Interaction Quantification을 뜻한다.
먼저 tree ensemble model이 무엇인지부터 정리하자. Decision tree는 입력 feature를 기준으로 데이터를 여러 번 나누고, 최종 leaf node에서 prediction을 내는 모델이다. Tree ensemble은 이런 tree를 여러 개 모아 prediction을 만드는 모델이다. 대표적으로 gradient boosting machine [4], XGBoost [3], LightGBM [6] 같은 모델이 있다. 이 모델들은 tabular data에서 여전히 강한 성능을 보이는 경우가 많다 [11].
문제는 성능이 좋은 tree ensemble이 항상 해석하기 쉬운 것은 아니라는 점이다. 얕은 decision tree 하나는 사람이 직접 따라갈 수 있다. 하지만 depth가 깊은 tree가 수백 개, 수천 개 모이면 모델이 왜 특정 prediction을 냈는지 바로 알기 어렵다. 그래서 XAI, 즉 explainable artificial intelligence에서는 다음 질문을 다룬다.
이 모델이 이 특정 입력 x에 대해 왜 이런 prediction을 냈는가?
이 질문은 global explanation이 아니라 local explanation이다. Global explanation은 모델 전체의 일반적인 동작을 설명하려는 것이다. 반면 local explanation은 특정 instance x 하나에 대한 prediction을 설명하려는 것이다. SHAP은 local explanation에서 가장 많이 쓰이는 방법 중 하나이다 [8].
SHAP이 하는 일
모델을 다음과 같이 쓰자.
f(x)
여기서 x는 여러 feature를 가진 입력이고, f(x)는 모델의 prediction이다. SHAP의 목표는 이 prediction을 baseline과 feature별 contribution으로 나누는 것이다.
f(x) = b_0 + \sum_{i \in N} \phi_i
여기서 N=\{1,\ldots,n\}은 feature들의 집합이고, b_0는 아무 feature도 모른다고 했을 때의 baseline prediction이다. \phi_i는 feature i가 prediction에 얼마나 기여했는지를 나타내는 값이다.
예를 들어 대출 부도 예측 모델을 생각해보자. 모델이 어떤 사람의 risk score를 높게 예측했다면, SHAP은 다음처럼 말해준다.
- income feature는 risk를 낮추는 방향으로 기여했다.
- credit history feature는 risk를 높이는 방향으로 기여했다.
- loan amount feature도 risk를 높이는 방향으로 기여했다.
이렇게 prediction을 feature별로 쪼개면 모델의 결과를 사람이 해석하기 쉬워진다.
SHAP의 이론적 기반은 Shapley value이다 [10]. Shapley value는 원래 cooperative game theory에서 나온 개념이다. 여러 player가 함께 얻은 payoff를 각 player에게 공정하게 나누려는 문제에서 출발한다. ML explanation에서는 player를 feature로 보고, payoff를 model prediction으로 본다.
Feature i의 Shapley value는 대략 다음 질문의 평균이다.
여러 feature subset에 feature i를 추가했을 때 prediction이 평균적으로 얼마나 바뀌는가?
수식으로 쓰면 다음과 같다.
\phi(f,i) = \sum_{T \subseteq N \setminus \{i\}} \frac{1}{n {n-1 \choose |T|}} \left[ f(T \cup \{i\}) - f(T) \right]
여기서 f(T)는 feature subset T만 알고 있다고 가정했을 때의 prediction이다. 즉, f(T \cup \{i\}) - f(T)는 이미 T라는 feature들을 알고 있는 상황에서 feature i를 추가로 알게 되었을 때 prediction이 얼마나 변하는지를 의미한다.
이 정의는 직관적이지만 계산이 어렵다. 모든 subset T를 봐야 하기 때문이다. Feature가 n개이면 subset은 대략 2^n개이다. 이런 지수적 증가는 feature 수가 조금만 커져도 빠르게 계산 부담을 만든다. TreeSHAP은 tree model의 구조를 이용해 이 계산을 polynomial time으로 줄인 방법이다 [7].
그런데 단일 feature만 보면 부족하다
Shapley value는 feature 하나하나의 contribution을 설명한다. 하지만 실제 모델에서는 feature 하나가 혼자 의미를 갖기보다, 다른 feature와 함께 의미를 갖는 경우가 많다.
예를 들어 housing price prediction을 생각해보자. Latitude만 보면 어떤 지역인지 애매할 수 있고, longitude만 봐도 마찬가지이다. 하지만 latitude와 longitude를 함께 보면 정확한 위치가 된다. 즉, 가격을 설명하는 것은 latitude 하나도 아니고 longitude 하나도 아니라, 두 feature의 interaction일 수 있다.
논문은 Figure 2에서 California housing dataset의 예를 보여준다. 일반 TreeSHAP에서는 longitude와 latitude가 각각 contribution을 갖는 것처럼 보인다. 하지만 TreeSHAP-IQ로 2차 interaction까지 보면, 중요한 설명은 latitude와 longitude의 interaction으로 옮겨간다. 즉, “위도 feature가 중요하다”보다 “위도와 경도의 조합, 즉 위치가 중요하다”가 더 정확한 설명이 된다.
이 차이는 실무적으로 중요하다. 단일 feature attribution만 보면 모델이 어떤 feature를 직접적으로 사용한다고 착각할 수 있다. 하지만 interaction attribution을 보면 모델이 feature의 조합을 통해 판단한다는 점을 더 잘 볼 수 있다.
Shapley interaction을 어떻게 정의할까?
Feature interaction을 설명하려면 feature 하나가 아니라 feature subset S \subseteq N을 본다. 예를 들어 S=\{i,j\}이면 feature i와 feature j의 pairwise interaction이고, S=\{i,j,k\}이면 세 feature의 third-order interaction이다.
이 논문이 주로 사용하는 index는 Shapley Interaction Index, 줄여서 SII이다 [5]. SII는 feature subset S를 여러 주변 context 안에서 켜고 끄며, 그 subset이 평균적으로 얼마나 interaction effect를 가지는지 측정한다. 다만 SII 자체는 설명해야 할 내용이 많아서 별도 글로 분리했다. 정의와 직관은 Shapley Interaction Index 정리에서 더 자세히 다룬다.
TreeSHAP-IQ 글에서는 다음 정도만 기억하면 된다.
- SII는 feature 하나가 아니라 feature subset S의 contribution을 본다.
- 계산에는 \delta_S(f,T)라는 discrete difference가 들어간다.
- n-SII는 maximum order s_0까지의 interaction score를 additive explanation으로 쓰기 위한 aggregation이다 [1].
TreeSHAP은 왜 빠른가?
일반적인 Shapley value 계산은 feature subset을 모두 고려해야 한다. 하지만 tree model에서는 계산 구조가 더 특수하다. Tree는 root에서 leaf까지 path를 따라 prediction을 만든다. 어떤 feature가 path에 등장하지 않는다면, 그 feature는 해당 leaf prediction에 영향을 주지 않는다.
TreeSHAP은 이 구조를 이용한다. Decision tree의 leaf node v마다 prediction rule R_v가 있다고 보자. Tree 전체 prediction은 leaf rule들의 합으로 볼 수 있다.
f(x) = \sum_{v \in L(T)} R_v(x)
여기서 L(T)는 tree의 leaf node 집합이다.
SHAP을 계산하려면 feature subset T만 알고 있을 때의 prediction f(x,T)가 필요하다. TreeSHAP에서는 feature가 unknown일 때 tree의 branch를 training data의 비율에 따라 따라간다. 예를 들어 어떤 split에서 왼쪽으로 간 training data가 70%, 오른쪽으로 간 training data가 30%였다면, 해당 split feature를 모를 때 prediction을 0.7과 0.3의 weight로 섞는다. 논문은 이 방식을 path dependent feature perturbation이라고 부른다 [7].
Linear TreeSHAP은 TreeSHAP 계산을 polynomial arithmetic으로 정리한다 [14]. 핵심 아이디어는 subset을 하나하나 나열하지 않고, subset들의 contribution을 polynomial coefficient에 저장하는 것이다.
Leaf node v에 대해 summary polynomial을 다음처럼 둔다.
G_v(y) = R_v^\emptyset \prod_{j \in F(R_v)} (q_{j,v} + y)
여기서 F(R_v)는 해당 leaf path에 등장하는 feature들의 집합이다. q_{j,v}는 feature j를 알게 되었을 때, unknown feature weight 기반 rule이 얼마나 바뀌는지를 나타내는 값이다. 처음 보면 기호가 복잡하지만, 직관은 단순하다.
Path에 등장하는 feature들의 가능한 subset contribution을 polynomial 하나에 압축해서 저장한다.
Polynomial을 전개하면 각 coefficient가 특정 크기의 feature subset contribution을 담는다. 그 다음 Shapley weight를 coefficient에 곱해 합치면 Shapley value가 나온다. 이렇게 하면 subset을 직접 모두 순회하지 않고 tree를 한 번 traversal하면서 계산할 수 있다.
TreeSHAP-IQ의 핵심 아이디어
TreeSHAP-IQ는 Linear TreeSHAP의 polynomial arithmetic을 interaction으로 확장한다. 단일 feature i에 대한 contribution이 아니라, feature subset S에 대한 interaction score를 계산해야 한다. 그러려면 두 가지가 필요하다.
- Interaction subset S의 discrete derivative 부분을 추적해야 한다.
- Summary polynomial에서 S에 해당하는 feature들을 나누어 Shapley interaction weight를 적용해야 한다.
논문은 이를 위해 두 종류의 polynomial을 추가한다.
첫 번째는 interaction polynomial이다.
H^{\mathrm{IP}}_{S,e}(y) = \prod_{j \in S} (p_{j,e} - y)
여기서 e는 tree의 edge이고, p_{j,e}는 edge e까지 내려왔을 때 feature j가 path에서 만든 효과를 나타낸다. 이 polynomial의 coefficient를 모두 더하면, discrete derivative에서 등장하는 alternating sum을 얻을 수 있다. 논문은 coefficient sum을 \kappa라고 둔다.
\kappa(H) = \text{coefficients of } H \text{의 합}
중요한 성질은 다음이다. 만약 S 안의 어떤 feature j가 아직 path에서 등장하지 않았다면 p_{j,e}=1이 되고, 이때 \kappa(H^{\mathrm{IP}}_{S,e})=0이 된다. 즉, interaction을 업데이트할 필요가 없다.
이 성질은 매우 자연스럽다. 어떤 interaction S=\{i,j\}를 계산하려면, 적어도 path에서 i와 j가 모두 의미 있게 등장해야 한다. 아직 j가 등장하지 않은 tree path에서 i와 j의 interaction을 계산하는 것은 불필요하다.
두 번째는 quotient polynomial이다.
H^{\mathrm{QP}}_{S,e}(y) = \prod_{j \in S} (p_{j,e} + y)
이 polynomial은 summary polynomial에서 interaction subset에 해당하는 부분을 나누는 역할을 한다. Linear TreeSHAP에서 feature 하나를 다룰 때 q_{i,v}+y로 나누던 것을, TreeSHAP-IQ에서는 subset S에 대해 \prod_{j \in S}(p_{j,e}+y)로 확장한다고 보면 된다.
논문의 main theorem은 SII를 edge 단위로 계산할 수 있음을 보인다. 정확한 식은 복잡하지만 구조만 보면 다음과 같다.
I_{\mathrm{SII}}(f,S) = \sum_{e \in E_S} \text{current edge contribution} - \text{ancestor correction}
여기서 E_S는 S에 속한 feature 중 하나로 split하는 edge들의 집합이다. Ancestor correction은 같은 feature가 path에서 여러 번 등장할 때 중복 계산을 막는 항이다. 단일 feature일 때는 이 식이 Linear TreeSHAP의 edge-based formula로 줄어든다.
따라서 TreeSHAP-IQ는 완전히 새로운 계산 원리를 만든다기보다, Linear TreeSHAP의 polynomial representation을 interaction subset S에 맞게 확장한다. 이 점이 논문의 핵심이다.
계산 복잡도
논문은 m개의 explanation point, leaf 수 \ell_T, maximum tree depth d_{\max}를 사용해 복잡도를 정리한다. Linear TreeSHAP의 computational complexity는 다음과 같다 [14].
O(m \cdot \ell_T \cdot d_{\max})
TreeSHAP-IQ가 order s=|S|인 모든 interaction을 계산할 때는, 현재 edge에서 만난 feature를 포함하는 interaction subset들을 업데이트해야 한다. 그 개수는 다음과 같다.
{n-1 \choose s-1}
그래서 computational complexity는 다음처럼 증가한다.
O\left( m \cdot \ell_T \cdot d_{\max} \cdot {n-1 \choose s-1} \right)
Storage complexity는 모든 order-s interaction score를 저장해야 하므로 다음 factor를 가진다.
{n \choose s}
논문은 storage complexity를 다음처럼 제시한다.
O\left( d_{\max}^2 \cdot {n \choose s} \right)
이 복잡도는 중요한 trade-off를 보여준다. TreeSHAP-IQ는 일반적인 brute-force 계산보다 훨씬 빠르지만, interaction order가 커지면 조합 수 자체가 커지는 문제는 남아 있다. 즉, any-order를 계산할 수 있다는 말이 모든 order를 항상 싸게 계산할 수 있다는 뜻은 아니다. 논문의 기여는 tree 구조를 이용해 가능한 한 효율적으로 정확한 interaction score를 계산하는 데 있다.
SII를 넘어서 CII까지
논문은 TreeSHAP-IQ가 SII에만 묶이지 않는다는 점도 보인다. SII, Shapley Taylor Interaction Index [12], Faithful Shapley Interaction Index [13] 같은 여러 interaction index는 더 넓은 class인 Cardinal Interaction Index, 즉 CII로 볼 수 있다.
CII는 대략 다음 형태를 가진다.
I_{\mathrm{CII}}(f,S) = \sum_{T \subseteq N \setminus S} w^{\mathrm{CII}}_s(|T|) \delta_S(f,T)
즉, 어떤 feature subset S의 discrete derivative를 여러 context T에 대해 weighted average한다. Index마다 다른 점은 weight w^{\mathrm{CII}}_s(|T|)이다.
TreeSHAP-IQ의 polynomial framework에서는 이 차이가 \psi라는 coefficient weighting function을 바꾸는 것으로 들어간다. 따라서 SII를 위한 계산 구조를 유지하면서, weight만 바꾸면 더 넓은 CII class에도 적용할 수 있다. 다만 FSI처럼 특정 order에 대해서만 명시적인 weighted-sum representation이 알려진 경우에는 적용 범위에 제한이 있다.
실험에서 보여준 것
논문은 TreeSHAP-IQ를 XGBoost, gradient-boosted trees, random forest, decision tree에 적용한다. Dataset은 German Credit, Bank, Adult, Bike, COMPAS, Titanic, California housing 등을 사용한다.
핵심 실험 결과는 두 가지이다.
첫째, TreeSHAP-IQ는 naive computation보다 큰 speed-up을 보인다. 논문 Table 1에 따르면 German Credit에서는 대략 10^4배, Bank와 Adult에서는 대략 10^3배, COMPAS에서는 대략 10^2배 정도의 speed-up을 보인다. California housing처럼 feature 수가 8개로 작을 때는 speed-up이 크지 않다. 이는 당연하다. Feature 수가 작으면 brute-force 방식의 조합 폭발도 상대적으로 약하기 때문이다.
둘째, interaction score가 실제 설명의 내용을 바꾼다. German Credit 예시에서는 credit amount가 단독으로 강한 feature라기보다 installment rate, duration과 interaction하면서 prediction에 영향을 준다. California housing 예시에서는 longitude와 latitude의 개별 효과보다 두 feature의 interaction이 실제 위치 정보를 설명한다. Bike regression 예시에서는 evening hour와 non-working day의 interaction이 prediction을 낮추고, hour와 temperature 관련 feature의 interaction은 prediction을 높인다.
이 결과들은 TreeSHAP-IQ가 단순히 더 많은 숫자를 계산하는 도구가 아니라, 해석의 단위를 feature에서 feature subset으로 확장한다는 점을 보여준다.
한계와 주의할 점
논문이 명확히 지적하는 한계는 absent feature를 어떻게 모델링하느냐에 따라 explanation이 달라진다는 점이다. Shapley 기반 explanation에서는 f(T), 즉 feature subset T만 알려졌을 때의 model output을 정의해야 한다. 하지만 실제 model은 보통 모든 feature를 입력으로 받도록 학습되어 있다. 따라서 어떤 feature가 없다고 할 때 이를 어떻게 처리할지 정해야 한다.
TreeSHAP-IQ는 기본적으로 path dependent feature perturbation을 사용한다. 이는 tree path에서 unknown split을 training data 비율로 따라가는 방식이다. 이 방식은 observational approach와 연결된다 [2]. 반면 interventional approach는 background dataset을 사용해 feature를 개입적으로 대체한다. TreeSHAP-IQ도 interventional 방식으로 계산할 수 있지만, 이 경우 background sample 수만큼 계산량이 증가한다. Interventional SHAP interaction을 더 효율적으로 계산하는 별도 연구도 있다 [15].
따라서 interaction score를 해석할 때는 다음을 구분해야 한다.
- 모델이 학습한 tree structure 안에서 path-dependent하게 본 explanation인가?
- feature distribution과 dependency를 어떻게 가정한 explanation인가?
- prediction을 정확히 분해하는 것이 중요한가, 아니면 feature 간 상호작용의 경향을 보는 것이 중요한가?
이 차이는 단순한 구현 디테일이 아니다. 같은 모델과 같은 입력이라도 absent feature를 다르게 정의하면 Shapley value와 interaction score가 달라질 수 있다.
정리
이 논문의 핵심은 다음 문장으로 요약할 수 있다.
TreeSHAP-IQ는 Linear TreeSHAP의 polynomial arithmetic을 확장해, tree ensemble에서 any-order Shapley interaction을 효율적으로 계산한다.
기존 TreeSHAP은 단일 feature attribution을 빠르게 계산했다. 하지만 단일 feature attribution은 feature들이 함께 의미를 갖는 상황을 놓칠 수 있다. TreeSHAP-IQ는 SII와 n-SII 같은 interaction score를 tree 구조에 맞게 계산함으로써, prediction explanation을 feature 단위에서 feature subset 단위로 확장한다.
개념적으로 중요한 부분은 세 가지이다.
- Shapley interaction은 feature subset S의 discrete derivative를 여러 context에서 평균낸 값이다.
- TreeSHAP-IQ는 summary polynomial, interaction polynomial, quotient polynomial을 사용해 subset enumeration을 피한다.
- Interaction order가 커질수록 조합 수는 여전히 커지므로, 실제 해석에서는 적절한 maximum order s_0를 선택해야 한다.
이 논문에서 가장 유용한 관점은 “feature importance”를 feature 하나의 점수로 끝내지 않는다는 점이다. 모델이 실제로 사용하는 신호가 feature의 조합이라면, 설명도 그 조합을 드러내야 한다. TreeSHAP-IQ는 tree ensemble이라는 중요한 모델 class에서 그 작업을 정확하고 효율적으로 수행하는 방법을 제시한다.