(Explainable AI) Shapley Value에 대해 알아보자!

Shapley Value란 무엇인가?

게임이론(Game Theory)

Shapley Value를 알아보기 전 게임이론에 대해 간단하게 살펴보겠습니다. 흔히 말하는 컴퓨터 게임이라기보단 어떤 활동이나 행위를 할 때 서로 영향을 미치는 상황에서 어떤 의사결정이나 행동을 하는지(결국 자신의 최대 이익에 부합하는 행동 추구)에 대해 이론화한 것입니다.

참고로 게임이론 중 협력적(Cooperative) 게임 이론이 있는데, 이는 비협력적으로 게임을 했을 때 각 개인이 취하는 이득보다 협력적으로 게임을 했을 때 각 개인이 취하는 이득이 더 크다면 긍정적인 협동이 가장 최선의 선택지임을 가리킵니다.

(참고)
게임이론 종류
1. 협력 게임 vs 비협력 게임
2. 정보 제공 vs 정보 비제공
3. 전략형 게임 vs 전개형 게임
4. 제로섬 게임 vs 비제로섬 게임

Shapley Value란 쉽게 말해, 게임이론을 바탕으로 게임에서 각 플레이어의 기여도를 계산하는 것입니다. 데이터 분석 각도에서 보자면, 하나의 특성에 대한 중요도를 알기 위해 여러 특성들의 조합을 구성하고 해당 특성의 유무에 따른 평균적인 변화를 통해 얻어낸 값인거죠.

아래 그림을 통해 풀어서 설명드리겠습니다.

1) 정원이 있고, 2) 50평방 미터 크기의, 3) 2층에 위치하고, 4) 고양이는 출입할 수 없는 아파트 가격이 31만 유로입니다. 31만원이 우리가 예측하려는 집 값이었다면 1번 요소, 2번 요소, 3번 요소, 4번 요소 중 어느 요소가 가장 많은 영향을 끼쳤을지 알아보고 싶을 것입니다. 이렇게 어떤 특성이 결과값에 영향을 미친 정도를 표현하고자 하는 것이 Shapley Value입니다. 그렇다면 Shapley Value는 어떻게 구할 수 있을까요?

아래 그림을 보면 1번, 2번 조건은 동일하고 3번 조건만 차이가 있습니다. 고양이 출입을 허용하느냐, 불허하느냐에 따라 집값이 1만 유로 차이가 나네요. 이것이 바로 Shapley Value가 계산되는 과정입니다.

Shapley Value는 위와 같은 계산 과정을 모든 가능한 연합에 대해서 반복합니다. 이때 주의할 점은 단순히 예측값의 변화량이 Shapley Value가 되는 것이 아니라 모든 marginal contributions의 (가중) 평균이 되는 것입니다. 예를 들어, 위에서 총 특성 수는 3개(정원 여부, 집 크기, 층)이고, "고양이 출입 허용"이란 특성의 기여도를 본다고 합시다. 

집 크기나 층은 범위가 너무 넓기 때문에 여기선 각각 50m^2, 2층이라고 제한합니다.

이때 3개 특성으로 만들 수 있는 연합 수는 아래와 같이 총 8가지입니다. 모두 고양이 출입 허용 관련 변수가 없는 상태로 이때 나오는 집값에 대한 평균이 있을 것입니다. 해당 변수를 추가했을 때 나오는 예측값과 이 평균값과의 차이를 나타내는 분포가 Shapley Value를 알 수 있는 분포가 됩니다.

Shapley Value의 수식적 개념에 대해 선형 모델을 예로 들어 잠시 설명하고 넘어가도록 하겠습니다. 아래 수식은 특정 관측값에 따른 선형 모델의 예측 결과를 나타냅니다.

$\hat{f}(x)=\beta_0+\beta_1x_1+...+\beta_px_p$

<수식1>

익숙하신 분들은 아시겠지만 여기서 $x$는 관측치이고 $\beta$는 특성에 대한 가중치입니다. 즉 $x$가 1만큼 변할 때 $y$는 $\beta$만큼 변하는 것이죠. 예측값 $\hat{f}(x)$에서 $j$번째 특성의 기여도 $\phi_j$는 아래와 같습니다.

$\phi_j(\hat{f})=\beta_jx_j - E(\beta_jX_j)=\beta_jx_j - \beta_jE(X_j)$

<수식2>

여기서 $E(\beta_jX_j)$는 특성 $j$에 대한 평균 추정값을 가리키며, 기여도는 이것과 각 특성값의 차이가 됩니다. 즉 동일한 특성의 나머지 데이터들의 평균값과의 차이를 말하는 것이죠. 하나의 관측치에 대한 모든 특성의 기여도는 아래와 같이 계산할 수 있습니다.

$\sum_{j=1}^p \phi_j(\hat{f}) = \sum_{j=1}^p (\beta_jx_j - E(\beta_jX_j))$

$=(\beta_0 + \sum_{j=1}^p \beta_jx_j)) - (\beta_0 + \sum_{j=1}^pE(\beta_jX_j))$

$=\hat{f}(x) - E(\hat{f}(X))$

<수식3>

마지막 수식을 보면 결국 특정 데이터 $x$에서 평균 예측값을 뺀 것과 같습니다. 이제 Shapley Value의 진정한 수식은 아래와 같습니다.

<수식4>

$\phi_i$ : $i$ 데이터에 대한 Shapley Value
$F$ : 전체 집합
$S$ : 전체 집합에서 i 번째 데이터가 빠진 나머지의 모든 부분 집합
$f_{S∪i}​(x_{S∪i}​)$ : i 번째 데이터를 포함한 (=전체) 기여도
$f_S(x_S)$ : i 번째 데이터가 빠진 나머지 부분 집합의 기여도

위 수식에서 $f(S)$ 함수는 집합 S에 포함되지 않은 특성을 모두 marginalized한 집합 S의 특성값들에 대한 예측치입니다. 수식으로 표현하면 아래와 같은데요. 

$f(S) = \int_ {}^{} \hat{f} (x_1, ..., x_p)\, d\mathbb{P}_{x\notin S} - E_X(\hat{f}(X))$

<수식5>

(추가) 위의 수식 버전과 다르게 아래 유튜브 설명에 나오는 수식 버전이 직관적으로 이해가 될 수 있습니다.

 

수식으로만 확인하니 어떤 내용인지 눈에 들어오지 않습니다. 아래 그림을 통해 이해해봅시다.

위의 Tree 학습 모델에서 특성은 "나이(age)"와 "성별(gender)"만 있다고 가정합니다. 이때 하나의 관측치인 "Bobby"에 대해서 "나이" 특성의 Shapley Value를 계산해보겠습니다. 수식4에서 살펴봤듯이 $S$ 집합은 살펴보고자 하는 특성 $i$를 제외한 나머지 부분 집합을 가리킵니다.

$\phi_{Age}: i = Age, F \setminus i = \{\{\}, \{x_{gender}\}\}$

<수식6>

1번 과정에선 부분집합인 S가 비어있습니다. 특성이 없기 때문에 $f_{S\cup i}(x_{S\cup i})$는 본래 살펴보고자 했던 특성인 "나이" 이외의 데이터들을 대상으로 한 예측치의 평균입니다. 본래 살펴보고자 했던 특성은 "나이"였기 때문에 $f_S(x_S)$는 "나이" 역시 포함한 예측치의 평균입니다. 즉 나이라는 변수는 상관없어진 것이니 나이가 15세 이상인 데이터들의 예측치도 포함이 되는 겁니다.

반대로 2번은 S에 "성별"이 포함되었고, 이는 곧 "나이"에 이어 "성별" 역시 신경쓴다는 것입니다. 관측치인 "Bobby"는 남자기 때문에 $f_{S\cup i}(x_{S\cup i}) = 2$가 됩니다. 반대로 $f_S(x_S)$는 "성별", "나이" 모두 포함해야 하기 때문에 모든 데이터들의 예측치 평균이 됩니다.

위에서 $f(S)$ 함수는 집합 S에 포함되지 않은 특성을 모두 marginalized한 집합 S의 특성값들에 대한 예측치라고 했습니다. "marginalized" 라는 단어의 뜻은 직역을 하면 주변의, 지엽적인이라는 뜻입니다. S는 특성 $i$를 제외한 나머지 부분 집합이라고 했습니다. 수식6의 경우, "나이"를 제외하고 1) 특성이 없거나, 2) 성별 특성만 있는 집합입니다. 각 경우에 따라 "나이"라는 특성이 얼만큼의 기여를 하는가 측정하는 것을 "marginal contribution"이라 하고, 이들을 합해 평균내는 것이 결국엔 "나이"의 Shapley Value가 됩니다.

아래 그림은 $f_{S \cup i} (x_{S \cup i}) - f_{S}(x_s)$에 해당합니다. 주황색으로 색칠된 원이 특성 "나이"를 가리킵니다. 아래와 같은 조합들(marginal contribution (1), (2), (3)... (n))이 여러 개 나올 것이며, 이들을 모두 합쳐 평균낸 것이 Shapley Value가 되는 것이죠.

이렇게 모든 marginal contribution을 구해서 더하고 평균을 내는 이유는 각 연합에 포함된 특성 간의 관계가 모델 예측에 끼치는 순수한 영향력(Fair answer)을 판단하기 위해서입니다. 특성 간 관계가 강하면 실제 영향력보다 더 큰 영향력을 미친다고 결과가 나올 수 있기 때문입니다.

지금까지 설명한 Shapley Value는 다음의 4가지 성질(property)을 가지고 있습니다.

Efficiency
각 특성의 기여도 합은 x에 대한 예측치와 평균의 차이와 같다.
$\sum_{j=1}^p \phi_j = \hat{f}(x) - E_x(\hat{f}(X))$

Symmetry
두 개 특성값 $j$와 $k$는 모든 가능한 연합에 기여하는 바가 같다면 기여분이 같아야 한다.
$f(S \cup \{x_j\}) = f(S \cup \{x_k\})$
$\phi_j = \phi_k$

Dummy
예측치에 영향을 끼치지 않는 특성 $j$는 Shapley Value가 0이다.
$f(S \cup \{x_j\}) = f(S)$
$\phi_j = 0$

Additive
각 게임에서 얻은 함수값 $f$ 와 $f^+$를 더한 함수값에서 나오는 Shapley Value는 각 게임의 Shapley Value 값들을 합한 것과 같다.
$\phi_j + \phi_j^+$

---

Additive Feature Attribution Methods

Shapley Value는 Additive Feature Attribution이라는 일반화된 Method 중 하나라고 합니다. 이는 단순한 Explanation model을 이용하여 복잡한(?) Original model을 해석하는 사후검정(post-hoc) 기법이라고 합니다. 선형회귀모델의 가중치를 이용하여 특성의 영향력 및 중요도를 계산합니다.

Additive Feature Attribution을 수식으로 표현하면 아래와 같습니다.

$g(z')=\phi_0 + \sum_{i=1}^M \phi_iz'_i$

<수식7>

$g$: explanation model$(g(z')\approx f(h_x(z')))$
$f$: original prediction model
$z'\in 0, 1^M$: simplified input$(z'\approx x')$
$h_x$: mapping function$(x = h_x(x'))$
$\phi_i\in \mathbb{R}$: attribution value <-> $\phi_0$: null output(average output of the model)
$M$: simplified input feature 갯수

위에서 $h_x$라는 mapping function은 simplified input $x'$를 본래의 $x$로 변환해주는 함수입니다. simplified input이란 $z' \approx x'$라는 가정을 통해 $x'$가 아닌 $z' \in 0, 1^M$로 표현됩니다. Additive Feature Attribution은 본래 input $x$가 아닌 simplified input $z'$를 통해 $g(z') \approx f(h_x(z'))$를 만족하는 explanation model $g$를 만드는 방법입니다.

Additive Feature Attribution의 Methods로는 본 글에서 설명한 Shapley Value 이외에도 LIME(Local Interpretable Model-agnostic Explanations), DeepLift, Layer-Wise Relevance Propogation 등이 있다고 합니다.

Feature Attribution은 Local Accuracy, Missingness, Consistency 이 3가지 특징 모두를 만족해야 한다고 합니다.

Local Accuracy
input $x$에 대해 original 모델 $f$를 approximate 할 때, attribution value 합은 $f(x)$와 같다.
$f(x) = g(x') = \phi_0 + \sum_{i=1}^M \phi_ix'_i$
$The\ explanation\ model\ g(x')\ matches\ the\ original\ model\ f(x)\ when\ x=h_x(x'),\ where$
$\phi_0=f(h_x(0))\ represents\ the\ model\ output\ with\ all\ simplified\ inputs\ toggled\ off.$

Missingness
특성값이 0이면 attribution value 값도 0이다.
$x'_i = 0$ => $\phi_i = 0$
$f_x(S \cup i) = f_x(S)$

Consistency
모델이 변경되어 어떤 특성의 기여분이 증가하거나 동일하다면 해당 특성의 attribution value 역시 증가하거나 변하지 않는다.
$Let f_x(z') = f(h_x(z')) and\ z' \setminus i\ denote\ setting\ z'_i=0$
$For\ any\ two\ models\ f\ and\ f'$
$f'_x(z') - f'_x(z' \setminus i) \ge f_x(z') - f_x(z' \setminus i), for\ all\ inputs\ z' \in \{0, 1\}^M$
$\phi_i (f', x) \ge \phi_i (f, x)$

다음 시간엔 Shapley Value를 이용하여 Additive Feature Attribution을 만족하는 explanation model SHAP에 대해 알아보겠습니다. Lundberg에 따르면 위의 3가지 특징을 모두 만족하면서 Additive Feature Attribution을 만족하는 것은 오직 Shapley value라고 합니다.

참고
https://datanetworkanalysis.github.io/2019/12/23/shap1
https://velog.io/@tobigs_xai/2%EC%A3%BC%EC%B0%A8-SHAP-SHapley-Additive-exPlanation
https://daehani.tistory.com/entry/Shapley-value-SHAP-Tree-SHAP
KHU IAILab 유튜브 강의