[논문리뷰/설명] SHAP: A Unified Approach to Interpreting Model Predictions

이전 포스팅에서 LIME에 대한 리뷰를 했었는데, 이번에 소개할 논문은 LIME에 뒤이어 "A unified approach to interpreting model predictions"라는 이름으로 "SHAP"이라는 획기적인 방법을 제시한 논문입니다.

 

포스팅하고 있는 현재 2021년 8월 기준 3994회(,,,)의 인용 수를 가지고 있는 엄청난 논문입니다. 논문을 쓰신 Scott M. Lundberg 선생님은 현재 마이크로소프트 리서치에서 근무 중이시고, Su-In Lee 선생님은 워싱턴대에서 교수로 재직 중이십니다. 이제 시작해보겠습니다!

 

논문 링크: https://arxiv.org/abs/1705.07874

A Unified Approach to Interpreting Model Predictions

 

 

 

 Introduction

 

본 논문에서는 예측모델의 설명에 대하여 다음 세 가지 방법을 제안합니다.

 

1. 어떤 예측에 대한 설명을 모델 자체로 보고 Explanation model로 정의하고, 설명 모델에 대한 새로운 분류인 additive feature attribution methods를 제안하여, 본 논문 이전에 제안된 6개 설명 방법론들이 이 분류에 포함되는 것을 보임.

 

2. 게임이론을 바탕으로 additive feature attribution methods에는 오직 하나의 해(a unique solution)만이 있음을 보이고, feature importance에 대한 새로운 측정법인 SHAP을 제안.

 

3. 사람의 직관과 잘 부합하는 SHAP 평가 방법을 제안.

 

 

 

 

 Additive Feature Attribution Methods

 

선형회귀분석이나 의사결정나무처럼 모델이 그 자체로 설명이 가능하다면 가장 좋겠지만, 복잡한 구조의 모델은 성능이 좋지만 그 자체로 설명이 매우 어렵습니다. 그렇기 때문에 복잡한 구조의 모델을 설명하기 위해서는 보다 단순한 모델이 필요하고, 이렇게 활용하는 단순한 모델을 Explanation model 이라 정의합니다.

 

본 논문은 설명 모델에 대한 새로운 분류인 additivie feature attribution methods를 제안합니다. 설명에 앞서 먼저 정의해야하는 notation들에 대해 살펴봅시다.

 

• $f$: 설명이 필요한 원래 모델
• $g$: $f$를 설명하기 위한 단순화된 Explanation model
• $x$: $f$에 들어가는 원래 input; $f(x)$는 input $x$에 대한 output
• $x'$: $g$의 input으로 들어가는 $x$의 단순화된 형태
• $h_x$: $x'$을 $x$로 매핑하는 함수; $x = h_x(x')$

 

되도록이면 국소적 설명 방법(local method)들은, 특정 metric 하에서 $x'$과 가까운 $z'$에 대해($z' \approx x'$), 설명 모델 $g$가 $g(z') \approx f(h_x (z'))$을 만족하도록 해야할 것입니다. $x$를 설명하기 위한 모델이 $g$이므로, $f(x) \approx g(x')$을 만족합니다. 따라서 $x'$과 가까운 $z'$들이 $g(z') \approx f(h_x (z'))$을 만족해야 $g$가 국소적으로 합리적인 설명 모델이라고 해석할 수 있는 것이죠. (이해를 위해 LIME 포스팅을 한 번 읽어보시길 권합니다)

 

이제 설명 모델의 새로운 분류인 additive feature attribution methods를 정의하고, 현재까지 제안된 6가지 설명 방법론들이 이 분류에 속하는 것을 보일 것입니다.

 

 

 

---

 

Definition 1. Additive feature attribution methods는 다음을 만족하는 이진 변수에 대한 선형 Explanation model $g$를 갖는다. $$g(z') = \phi_0 + \sum_{i=1}^{M} \phi_i z_{i}^{'}, \tag{1}$$ 단순화된 input의 feature 개수인 $M$에 대하여, $z' \in \left\{ 0, 1 \right\}^M$이고, $\phi_i \in \mathbb{R}$.

 

 

---

 

input의 feature 수를 줄이는 것뿐만 아니라, 0이 아닌 feature들의 값을 모두 1로 만든 벡터 $z'$이 설명 모델 $g$의 input이 되고, 이 $g$는 $M$개의 변수를 갖는 선형식으로 구성되어 있다는 뜻입니다. 결국 설명 방법론을 통해 추출한 Explanation model $g$를 통해 우리는 줄어든 변수 중에서 어떤 변수가 중요한지 판단할 수 있을 것입니다.

 

이어서 본 논문은 기존 6개의 설명 방법론(LIME, DeepLIFT, Layer-wise relevance propagation, Shapley values)이 이 additive feature attribution methods에 포함되는 것을 보입니다. 편의상 이번 포스팅에서는 "기존의 많은 설명 방법론들이 본 논문에서 제안한 분류에 포함된다" 는 정도로만 이해하고 넘어가겠습니다.

 

 

 

 

 Shapley Value

 

이번 포스팅에서 소개하는 SHAP은 SHapley Additive exPlanation을 줄인 것입니다. Shapley value가 무엇인지 잘 알고 넘어가야 SHAP이 방법으로서 갖는 의미를 잘 파악할 수 있습니다. 한 번 살펴봅시다.

 

Shapley regerssion value

다중공선성(multicollinearity)이 존재하는 선형 모델에서의 변수 중요도(feature importance)입니다. 다중공선성은 선형 모델에서 독립성 가정을 위배하는 성질이지만, Shapley regression value는 다중공선성이 있는 선형 모델에서도 사용할 수 있는 값이라고 언급하고 있습니다. 

 

Shapley regression value는 각 변수들이 학습에 포함되었을 때, 얼마나 모델의 성능에 영향을 미치는지에 따라 중요도(importance value)를 부여합니다. 중요도를 계산하는 방식은 다음과 같습니다.

 

$F$는 모든 변수의 집합, $S \subseteq F$, $x_S, f_S$는 S에 포함된 변수만 포함한 input, 학습모델일 때, Feature $i$의 중요도 $\phi_i$는, $$\phi_i = \sum_{S \subseteq F \setminus \left\{ i \right\}} \frac{|S|! (|F| - |S| - 1)!}{|F|!} \left[ f_{S \cup \left\{ i \right\}} (x_{S \cup \left\{ i \right\}}) - f_S(x_S) \right] \tag{4}$$

 

즉 $\phi_i$는, Feature $i$를 제외한 $F \setminus \left\{ i \right\}$의 모든 부분집합에 대해서, $i$를 추가 했을 때의 output 변화량의 평균을 측정한 값입니다. 

 

이제 Additive feature attribution methods가 어떻게 오직 하나의 해를 갖는지 살펴볼 것입니다.

 

 

 

 

 Simple Properties Uniquely Determine Addtitive Feature Attributions

 

Explanation model을 산출하는 과정은 게임이론과 상당히 흡사합니다. 게임이론은 다음과 같은 가정에서 기인합니다.

 

• 게임 내의 모든 플레이어들은 게임의 결과에 영향을 미칠 수 있다.
• Explanation model의 변수의 계수들은 예측 결과에 영향을 미칠 수 있다.
• Explanation model의 변수의 계수 = 게임 내의 모든 플레이어, 모델의 예측 결과 = 게임의 결과

 

이제 Explanation model을 산출하는 Additive feature attribution methods가 게임이론 문제의 하나인 것을 확인하실 수 있을 것입니다. 게임이론 문제가 오직 하나의 해를 갖기 위해서 만족해야 하는 네 가지 공리(axiom)가 있는데, 본 논문에서는 Additive feature attribution methods가 오직 하나의 해를 갖기 위해 가져야 할 조건들을 다음과 같이 제시합니다.

 

---

 

Property 1 (Local accuracy)

$$f(x) = g(x') = \phi_0 + \sum_{i=1}^{M} \phi_i x_{i}^{'}, \tag{5}$$

여기서 $x = h_x(x')$입니다.

 

원래 모델 $f$로부터 생성된 output인 $f(x)$를 설명하기 위한 $g$가 Local accuracy를 만족해야 한다는 것입니다.

 

Property 2 (Missingness)

$$x_{i}^{'} = 0 \Longrightarrow \phi_i = 0 \tag{6}$$

 

단순화된 input인 $x'$에서 Feature $i$에 해당하는 값이 0이라면 해당 변수의 영향력($\phi_i$)도 0이라는 것입니다.

 

Property 3 (Consistency)

$f_x(z') = f(h_x(z'))$이고, $z' \setminus i \Leftrightarrow z_{i}^{'} = 0$일 때, 모든 모델 $f, f'$, 모든 input $z' \in \left\{ 0, 1 \right\}^M$에 대하여, $$f_{i}^{'}(z') - f_{i}^{'}(z' \setminus i) \ge f_x(z') - f_x(z' \setminus i) \Longrightarrow \phi_i(f', x) \ge \phi_i(f, x) \tag{7}$$ 

Consistency는 만약 모델이 $f$에서 $f'$으로 바뀌었을 때, Feature $i$의 영향력이 더 커졌다면, $f'(x)$의 Explanation model의 Feature $i$에 대한 계수가 $f(x)$보다 더 크다는 뜻입니다.

 

---

 

그리고 이 세 가지 Property를 만족할 때, 다음과 같은 정리가 성립합니다.

 

Theorem 1  Property 1, 2, 3을 만족할 때, Additive feature attribution methods(Definition 1)를 통해 나온 Explanation model $g$는 오직 하나 존재한다. 

$$\phi_i(f, x) = \sum_{z' \subseteq x'} \frac{|z'|!(M - |z'| -1)!}{M!}[f_x(z') - f_x(z' \setminus i)] \tag{8}$$

여기서 $|z'|$은 $z'$에서 0이 아닌 원소의 개수이고, $z' \subseteq x'$은 모든 $z'$에 대하여, $z'$의 0이 아닌 원소들의 집합은 $x'$에서 0이 아닌 원소들의 집합의 부분집합이다.

 

---

 

Theorem 1의 (8)번 식이 Shapley value와 같은 형태의 식인 것을 통해, 결국 Local accuracy(Property 1), Consistency(Property 3)를 갖는 Additive feature attribution methods의 해는 Shapley value를 계수로 갖는 Explanation model이란 결론에 도달합니다. (Missingness(Property 2)는 단순히 게임이론 문제를 Additive feature attribution methods의 형태로 맞추기 위한 조작입니다)

 

Theorem 1이 어떻게 게임이론을 통해 증명되는지(게임이론이 오직 하나의 해를 갖기 위한 4가지 공리를 활용하여 Theorem 1을 어떻게 증명하는지)는 논문의 Supplement에서 살펴볼 수 있습니다. 본 포스팅에서는 증명은 생략하고, 지금까지의 내용을 정리해봅시다. 

 

• 기존의 설명 방법론들이 분류될 수 있는 Additive feature attribution methods 제안
• Shapley value 개념
• 게임이론부터 파생된 Property들을 만족하는 Additive feature attribution methods의 해는 오직 하나 존재한다.

 

 

 

 

 SHAP(SHapley Additive exPlanation) Values

 

SHAP value: A unified measure of feature importance

 

본 논문에서 제시하는 SHAP의 정의입니다. 이 값이 계산되는 방식은 다음과 같습니다.

 

• $z' \in \left\{ 0, 1 \right\}^M$과 $z'$의 non-zero index의 집합 $S$를 정의
• $f_x(z') = f(h_x(z')) = E[f(z) | z_S]$로 두고,
• Theorem 1의 (8)번 방정식의 해 산출

 

즉, 단순화된 $z'$으로부터 Shapley value를 구하면 되는 것인데, 이 과정은 $2^{|S|}$의 시간복잡도를 갖기 때문에 정확한 SHAP value를 찾는 것이 매우 어렵습니다. 하지만 본 논문에서는 additive feature attribution methods를 활용하여 근사치를 얻는 방법들을 소개하는데, 그 중 Kernel SHAP를 대표로 살펴보도록 하겠습니다.

 

---

Kernel SHAP (Linear LIME + Shapley values)

LIME은 다음과 같은 식을 사용하여 Explanation model $g$를 산출합니다. (이전 포스팅 참고)

$$\xi (x) = \operatorname{argmin}_{g \in G}\, \mathcal{L}(f, g, \pi_x) + \Omega(g), \tag{2}$$

이 식에서 손실함수로 쓰는 $L$, 인스턴스 간의 거리에 대한 커널인 $\pi$, 정규화(Regularization) 식인 $\Omega$를 무엇으로 설정하느냐에 따라 산출하는 Explanation model은 달라지게 됩니다.

 

그리고 Explanation model로 선형식을 쓰는 경우의 LIME은 본 논문에서 정의했던 Additive feature attribution methods에 속하기 때문에, 만약 Additiive feature attribution methods가 오직 하나의 해를 갖기 위한 조건인 Property 1~3을 따른다면, Theorem 1에 의해서 Explanation model의 각 변수들에 대한 계수는 Shapley value를 따르게 됩니다.

 

그렇다면 이제 필요한 작업은 Property 1~3을 만족하게 하는 $L, \pi, \Omega$를 결정하는 일입니다. 본 논문에서는 Theorem 2에서 이를 만족하는 "Shapley Kernel"을 제시합니다.

 

---

 

Theorem 2 (Shapley Kernel)  Definition 1 하에서, 다음을 만족하는 $L, \pi_{x'}, \Omega$는 (2)번 식이 Property 1~3을 만족하게 한다.

$$\Omega(g) = 0,$$

$$\pi_{x'}(z') = \frac{(M - 1)}{(M \text{ choose } |z'|)|z'|(M-|z'|)},$$

$$L(f, g, \pi_{x'}) = \sum_{z' \in Z} \left[ f(h_{x}^{-1} (z')) - g(z') \right]^2 \pi_{x'}(z')$$

$|z'|$은 $z'$에서 0이 아닌 원소들의 개수.

 

---

 

Theorem 2에서 제시하는 $L, \pi, \Omega$를 만족한다면, LIME을 수행했을 때 산출되는 선형 Explanation model의 계수들이 Shapley value와 일치한다는 것입니다. 이 정리는 LIME과 Shapley value를 연결했다는 점에서 매우 참신하고 유용한 접근법으로 볼 수 있습니다.

 

최종적으로 Kernel SHAP을 수행하는 과정은 다음과 같습니다.

 

• Theorem 2를 만족하는 $L, \pi, \Omega$ 정의
• LIME 수행, 선형 Explanation model 산출
• 모든 인스턴스 x에 대하여 LIME을 수행하고, 산출된 Explanation model들의 계수(Shapley value)들을 더하거나 평균을 취하여 모델의 Feature importance를 파악

 

 

 

 

 My Opinion

 

SHAP은 게임이론에 기반하여 보다 탄탄한 이론적 토대에서 설명 모델을 산출하는 방법을 소개합니다. 사실 Kernel SHAP은 시간이 오래 걸리는 방법론이고, 이후에 여러 단점들을 개선한 Tree SHAP 등의 방법론들이 발표되었다고 합니다. SHAP 계열 설명 방법론의 토대가 되는 논문을 살펴보았으니, 뒤에 등장한 다른 논문들도 살펴보고, 용도에 맞게 적절히 사용하면 모델을 설명하는 데에 큰 도움이 될 수 있을 것 같습니다.