게임 이론의 협력 게임 상금을 공정하게 분배하는 방법 중 하나인 Shapley value를 확장하여 black box machine learning 모델을 해석하는 데 활용한 SHAP (SHapley value Additive exPlanation)에 대하여 다루겠습니다. 이번 블로그에서는 SHAP의 근간인 Shapley value를 먼저 살펴보도록 하겠습니다.
Shapley value?
Shapley value는 협력 게임 이론 (cooperative or coaltitional game theory)의 solution 중 하나로 게임에 참여한 플레이어들에게 총보상을 공정하게 분배하는 하나의 분포를 의미합니다.
여기에서 협력 게임과 하나의 분포의 의미는 다음과 같습니다.
협력 게임 (Cooperative game theory)
협력 게임은 동일한 목표를 달성하기 위해 게임에 참여한 플레이어가 경쟁이 없이 함께 협력하여 참여한 게임을 의미합니다.
분포 (Distribution)
협력 게임에서는 참여한 플레이어가 협력하여 집단의 총보상을 얻습니다. 이때 플레이어 개개인의 기여도를 계산하여 나타낸 것을 분포라고 합니다.
Formulation of Shapley value
1) Players & Coliation
n명의 플레이어가 참여한 게임의 플레이어의 집합을 $N=\{1, 2, \cdots, n\}$로 정의합니다. $S$를 $N$의 부분 집합, 즉, $S\subset N$으로 정의하고 $S$를 coliation이라고 부릅니다. 정의에 따라 $2^n$의 협력체를 구성할 수 있습니다. 플레이어들은 협력체에 참여할 수도, 아닐 수도 있습니다. 예컨데, 아무도 참여하지 않는 경우 $S=\emptyset$이 됩니다.
2) Characteristic function
플레이어 집합 $N$에 대하여 모든 협력체의 집합은 $S\in\mathcal{P}(N)$ ($\mathcal{P}$: power set)으로 정의할 수 있습니다. 어떤 협력체 $S$가 얻은 총보상을 나타내는 함수를 charateristic function $v$로 정의하고, $$v: \mathcal{P}(N)\rightarrow \mathbb{R}$$로 나타낼 수 있습니다. (이는 가치 함수라고 불리기도 합니다.) 여기에서 $v(\emptyset)=0$를 가정합니다. 즉, 아무도 참여하지 않은 게임의 총보상은 0을 가정하며, 이는 매우 합리적입니다.
3) Distribution
Distribution, $\varphi$는 characteristic function $v$와 플레이어 집합 $N$에 대하여 $n$명의 플레이어에게 총상금을 분배하는 함수입니다. $$\varphi(v, N)=\left[\varphi_{1}(v, N), \cdots, \varphi_{n}(v, N)\right]^{\top}\in\mathbb{R}^{n}$$
4) Fair distribution
아래 5개의 조건을 만족하는 분배를 공정 분배(fair distribution)라고 합니다.
① Efficiency, 효율성
모든 플레이어의 개별 보상의 합은 총 보상과 같다.$$\sum_{i\in N}\varphi_{i}(v)=v(N)$$이 경우 효율성이 있다고 한다.
② Symmetry, 대칭성
서로 다른 플레이어 $i$, $j$와 모든 협력체 $S\subset N-\{i, j\}$에 대하여, $$v(S\cup\{i\})=v(S\cup\{j\})$$를 만족할 때, $$\varphi_{i}(v)=\varphi_{j}(v)$$가 만족할 경우 대칭성이 있다고 한다.
③ Linearity, 선형성
Characteristic function $v$, $w$에 대하여 아래를 만족하면 선형성이 있다고 한다. $$\varphi_{i}(v+w) = \varphi_{i}(v)+\varphi_{i}(w)\text{ and }\varphi_{i}(av)=a\varphi_{i}(v), \forall i\in N, a\in\mathbb{R}$$
④ Dummy or Null, 위장
게임에 기여하지 않은 player의 보상은 0이다. $$v(S)=v(S\cup\{i\}), v(S\cup\{i\})-v(S)=v_{i}(S)=0,\forall S\subset N-\{i\}\Rightarrow \varphi_{i}(v)=0$$
⑤ Monotonicity, 단조성
동일 player에 대하여 다른 방식으로 총보상을 얻고 크기가 다를 때, 각 총보상의 분배의 대소 관계 결과도 일치해야 한다.$$v_{i}(S)\ge w_{i}(S)\Rightarrow \varphi_{i}(v)\ge\varphi_{i}(w),$$ 여기에서 $v_{i}(S)=v(S\cup\{i\})-v(S)$를 의미합니다.
5) Shapley value
Shapley value는 fair distribution의 solution 중 하나입니다. $R$을 $|N|=n$명의 player의 순서로, $P_{i}^{R}$은 $R$의 순서에서 $i$ 앞에 배치된 player의 순서로 정의하겠습니다. 예를 들어, 5명의 player가 있다면, $R=\{1,3,2,5,4\}$가 순서중 하나라면 $P_{2}^{R}=\{1,3\}$을 의미합니다. Shapley value는 아래와 같습니다. $$\varphi_{i}(v)=\frac{1}{|N|!}\sum_{R}\left[v(P_{i}^{R}\cup \{i\})-v(P_{i}^{R})\right]$$즉, $|N|!$의 순서 순열에 대하여 $i$의 모든 기여도를 계산한 뒤 산술평균을 구한 것과 같습니다. 보통 Shapley value에 대한 정의를 찾아보면 위와 같이 정의된 case는 많이 없습니다. 만약 $P_{i}^{R}\in S$, $S\subset N-\{i\}$라면, $v(P_{i}^{R}\cup\{i\})-v(P_{i}^{R})\in v(S\cup\{i\})-v(S)$를 만족합니다. 그러면 우리는 player의 배치를 이렇게 생각할 수 있습니다.$$\left[S, \{i\}, N-S-{i}\right]$$ 즉 $i$ player를 제외한 $S$ coalition의 player와 나머지 player ($N-S-\{i\}$)의 순서로 배치 됩니다. 각 집합을 섞는다고 생각해보면, $|S|!\times 1 \times (|N|-|S|-1)!$의 경우의 수가 생깁니다. 그러면 우리는 Shapley value를 아래와 같이 다시 정의할 수 있습니다.$$\varphi_{i}(v)=\sum_{S\subset N-\{i\}}\frac{|S|!(|N|-|S|-1)!}{|N|!}\left[v(S\cup \{i\})-v(S)\right]$$ 정의된 Shapley value는 위 다섯 가지 성질을 만족하며 이는 증명가능합니다. (이번 블로그에서는 증명 과정은 생략하겠습니다.)
Shapley value example
Wikipedia에 있는 example을 그대로 들고 왔습니다. 위에서 설명한 Shapley value를 계산해 보겠습니다.
Glove game은 각 플레이어들이 왼쪽 또는 오른쪽 장갑 중 하나만 가지고 있을때, 협력하여 왼쪽, 오른쪽 짝을 맞추면 보상을 얻는 게임입니다. 3명의 players가 참여합니다. 즉, $N=\{1,2,3\}$입니다. 이때 1, 2 player는 왼쪽 장갑을, 3 player는 오른쪽 장갑을 가지고 있습니다. 이에 따라 characteristic function을 다음과 같이 정의하겠습니다. $$v(S)=\left\{\begin{align*}1&\text{, }S\in\left\{\{1,3\},\{2, 3\}, \{1,2,3\}\right\}\\0&\text{, otherwise.}\end{align*}\right.$$ Player 1의 Shapley value는 아래와 같이 계산할 수 있습니다. 위에서 정의한 순서에 따라서 1st, 2nd definition으로 정의했습니다.
Player 2, 3도 위와 같은 방식으로 계산할 수 있습니다.
감사합니다 :)
References
- https://zephyrus1111.tistory.com/271
- Wikipedia contributors. "Shapley value." Wikipedia, The Free Encyclopedia. Wikipedia, The Free Encyclopedia, 11 Jun. 2023. Web. 19 Jun. 2023.
댓글