(진행중) SHAP (Shapley Additive exPlanations) 이해하기

SHAP에 대해서 좀 더 이해를 해보고자 블로그를 참고하는데, 블로그를 보고 정확히 이해하려니 매우 어렵지만 이해해보려고 한다...

 

게임 이론

게임이론이란 우리가 아는 게임을 말하는 것이 아닌 여러 주제가 서로 영향을 미치는 상황에서 서로가 어떤 의사결정이나 행동을 하는지에 대해 이론화한 것을 말한다.

 

즉, 의사결정자는 자신의 결정뿐 아니라 상대방의 결정이 무엇이 될 것인가에 대해서 관심을 가지게 될 수밖에 없고 이러한 상황의 문제를 다루는 의사결정학의 한 분야라고 한다.

 

게임 이론 분류

Shapley value

개념 및 예시

게임 이론의 개념을 기반으로 하며 예측에 대한 각 피처의 기여도를 계산하여 기계 학습 모델의 예측을 설명하는 데 사용할 수 있습니다.

Shap Value에 대한 간단한 이야기를 해보자.

 

M 명의 플레이어가 협력게임을 하고 있다고 가정을 하자.

F = {1,2,3,...M}

 

연합(coalitions) S은 F의 부분집합이 된다 ((S ⊆ F))

 

그래서 만약의 3명의 플레이어가 가정하면 연합들(coalitions)은 다음과 같다.

 

F 역시 coalition의 하나이고 이것을 grand coalition이라고 한다.

 

M 명의 플레이어가 있다면 $2^M$의 연합이 있다는 것을 추측할 수 있습니다.

이제 각 연합(coalition)을 실수(real number)로 매핑하는 함수 v를 정의합니다.

v is called a characteristic function.

따라서 각 연합 S에 대해 수량 v(S)는 실수이며 연합 S의 가치라고 합니다.

 

이는 해당 연합(coalition)의 플레이어가 함께 행동할 경우 얻을 수 있는 총 이득(total gain) 또는 집단적 보상(collective payoff)으로 간주됩니다. 빈 연합(empty coalition)에는 플레이어가 없기 때문에 다음과 같이 가정할 수 있습니다.

 

이제 M 플레이어와의 연합 게임에서 각 플레이어의 총 보상(total payoff)에 대한 기여도(contribution)가 무엇인지 알고 싶습니다.

즉, 플레이어들 사이에서 총 이득(total gain)을 나누는 가장 공정한 방법은 무엇입니까?

 

5명의 플레이가 있다고 가정하면 F= {1,2,3,4,5}로 됩니다.

 

플레이어를 empty set에 한 번에 하나씩 추가하여 F(grand coalition)를 구성하고 새로운 플레이어를 추가할 때마다 F의 새로운 연합을 구성한다고 가정합니다.

예를 들어, 먼저 empty set에 {1}을 추가하므로 현재 플레이어 세트는 F의 연합인 {1}입니다.

그런 다음 {2}를 추가하고 현재 세트는 연합 {1,2}이고 F={1, 2, 3, 4, 5}를 얻을 때까지 계속합니다.

각 플레이어가 현재 플레이어 세트에 추가되면 이전 연합의 총이득이 증가합니다.

예를 들어 {1,2}라는 set에서의 total gain은 v({1,2})인데, {3}을 추가하면 total gain은 v({1,2,3})으 된다고 볼 수 있다.

 

이제 현재 연합(coalition)에 대한 {3}의 기여도는 현재 연합({3} 포함)과 {3}을(를) 포함하지 않은 이전 연합의 가치 간의 차이라고 가정할 수 있습니다.

{3}을 추가한 후 {4} 및 {5}를 추가할 수 있으며 총이득도 변경됩니다.

그러나 {3}의 기여도에는 영향을 미치지 않으므로 이전 방정식은 여전히 ​​{3}의 기여도를 제공합니다

 

그러나 여기에는 문제가 있습니다. 플레이어 추가 순서도 중요합니다.

즉, 어떻게 추가하냐에 따라 기여도가 달라진다.

 

 

이 플레이어가 회사의 부서 직원이라고 가정합니다.

회사는 먼저 {1}을(를) 고용합니다. 그런 다음 기술이 부족하다는 것을 파악하고 {2}을(를) 고용합니다.

{2}을(를) 고용한 후 회사의 총이익은 $10000만큼 증가하며 이는 {1}에 추가될 때 {2}의 기여입니다.

 

Contribution of {2} = v({1,2}) - v({1}) = $10000

 

{3}을(를) 고용한 후 {3}의 기여도은 $2000에 불과합니다.

 

Contribution of {3} = v({1,2,3}) - v({1,2}) = $2000

 

또한 직원 {2} 및 {3}의 스킬 세트가 유사하다고 가정합니다.

 

이제 직원 {3}은(는) 자신이 더 일찍 고용되었더라면 {2}의 동일한 기여도를 갖게 되었을 것이라고 주장할 수 있습니다.

즉, {1}에 추가될 때 {3}의 기부금도 $10000가 될 수 있습니다.

 

Contribution of {3}  = v({1,3}) - v({1}) = $10000

결국 유사하다고 가정을 하면 기여도 3에 대해서의 영향력이 {2}와 같을 수 있게 된다.

 

따라서 각 플레이어의 기여도를 공정하게 평가하려면 대연합(grand coalition)을 형성하기 위해 추가되는 순서도 고려해야 합니다.

 

사실 플레이어 {i}의 기여도를 공정하게 평가하려면 F의 모든 순열을 형성하고 각 순열에서 {i}의 기여도를 계산한 다음 이러한 기여도의 평균을 취해야 합니다.

 

예를 들어

 

F = {1,2,3,4,5}의 순열 중에 하나가 [3,1,2,4,5]가 나온다고 하면, 

3의 기여도는 다음과 같다.

또 다른 permutation은 [4,5,2,3,1]이라고 하면,

특성 함수 v는 순열이 아니라 연합을 인수로 취한다는 점에 유의하는 것이 중요합니다.

연합은 집합이므로 요소의 순서는 중요하지 않지만 순열은 정렬된 요소 모음입니다.

 

[3,1,2,4,5]와 같은 순열에서 3은 첫 번째 플레이어이고 5는 팀에 추가된 마지막 플레이어입니다.

 

따라서 각 순열에 대해 요소의 순서는 총이득에 대한 기여도를 변경할 수 있지만 순열의 총 이득 또는 가치는 순서가 아닌 요소에만 의존합니다.

 

 

각 permutation P는 먼저 {i} 이전에 추가된 플레이어 연합의 가치를 계산해야 합니다.

 

그런 다음 S에 {i}를 추가하여 형성된 연합의 가치를 계산해야 하며 이 연합을 S U {i}라고 합니다. 이제 ϕᵢ로 표시된 플레이어 {i}의 기여도는 다음과 같습니다.

 

 

grand coalition F의 permutations의 총 수는 |F|!이다.

|F| 집합 F의 요소 수를 의미합니다.

그래서 우리는 {i}에 대한 기여의 평균을 얻기 위해 기여의 합계를 나눕니다.

 

위와 같은 식으로 조합을 전부다 계산하여 평가한다.

 

위에서 볼 수 있듯이 일부 순열은 연합 S 및 S U {i}가 동일하므로 동일한 기여도를 갖습니다.

 

따라서 방정식을 계산하는 더 쉬운 방법입니다. Eq 1은 기여도의 고유 값만 계산하고 반복 횟수를 곱한다는 것입니다.

그러기 위해서는 각 연합에서 얼마나 많은 순열을 형성할 수 있는지 파악해야 합니다.

 

F-{i}를 플레이어 {i}를 제외한 모든 플레이어의 집합이라고 하고 S는 F-{i}의 연합(S ⊆ F-{i}) 중 하나입니다.

예를 들어 F={1,2,3,4,5} 및 {i}={3}의 경우

S의 요소 수는 |S|로 표시되며 |S|! 이러한 요소로 순열이다.

예를 들어 S가 {1,2,}AUS |S|=2이다. 그럼 우리가 얻는 순열은 {1,2} 나 {2,1}이다.

S로부터 형성된 각 순열의 가치가 v(S) 임을 압니다.

이제 S에서 형성된 각 순열 끝에 플레이어 {i}를 추가합니다.

결과 순열의 가치는 모두 연합 S U {i}에 속하므로 v(S U {i})입니다.

집합 F는 F의 모든 요소를 ​​갖는 순열을 형성하기 위해 S U {i}의 끝에 추가될 수 있는 S U {i}의 요소를 제외한 나머지 요소 |F|-|S|-1개를 가집니다.

 

위의 수식으로 이해하면 헷갈리니 예시를 보자면, 

전에 예시를 이어서 하면 S={1,2}이고 3을 추가한다고 하면, 

S의 permutation은 2개이고, 나머지 조합을 따라서 다시 한번 permutation을 하면 F를 다음과 같이 구할 수 있다.

아래 그림처럼 계산되는 것을 볼 수 있다.

각 순열의 총이득에 대한 {i}의 기여도는 다음과 같습니다.

그리고 이러한 모든 순열의 총 이득에 대한 {i}의 총기여는 다음과 같습니다.

즉, 기여도가 나올 수 있는 경우를 다 곱한다고 보면 된다.

 

지금까지 우리는 F에서 하나의 가능한 연합 S의 순열을 다루고 총이익에 대한 {i}의 총기여도를 계산했습니다.

이제 F의 모든 순열에서 {i}의 기여도 합계를 얻기 위해 F-{i}의 다른 연합에 대해 동일한 절차를 반복할 수 있습니다.

 

 

마지막으로 |F|! 따라서 F의 모든 순열의 총이득에 대한 {i}의 평균 기여도는 이전 항을 |F|!로 나누어 얻을 수 있습니다.

 

 

여기서 ϕᵢ는 F의 모든 순열에서 {i}의 평균 기여도인 요소 {i}의 Shapley Value이라고 합니다.

 

이것은 F에 있는 모든 플레이어의 총 이득에 대한 플레이어 {i}의 수학적으로 공평한 몫입니다.

 

이전에 살펴본 것처럼 각 연합 S는 S! 를 만들 수 있습니다!

(|F|-|S|-1)! 순열. 순열의 총 수는 |F|! 이므로 다음과 같이 쓸 수 있습니다.

 

 

특성

shapley value는 다음과 같은 속성을 따른다.

1- Efficiency

모든 플레이어의 기여도 합계는 총이득을 제공해야 합니다.

 

1- Symmetry

i와 j가 i와 j를 포함하지 않는 모든 연합 S에 대해 v(S ∪ {i}) = v(S ∪ {j})인 경우 ϕᵢ=ϕⱼ.

가능한 모든 연합은 동일한 기여를 해야 합니다.

 

 

2- Dummy

i가 i를 포함하지 않는 모든 연합 S에 대해 v(S) = v(S ∪ {i})이면 ϕᵢ = 0입니다. 즉, 플레이어가 가능한 연합에 이득을 추가하지 않으면 기여도는 0입니다.

 

3- Additivity

u와 v가 게임의 두 가지 다른 특성 함수라고 가정합니다.

플레이어 i의 기여도를 각각 ϕᵢ(u) 및 ϕᵢ(v)라고 합니다(여기서 ϕᵢ(u)는 ϕᵢ이 u의 함수임을 의미합니다).

그러면 ϕᵢ(u + v) = ϕᵢ(u) + ϕᵢ(v)가 됩니다. 예를 들어 이 속성을 명확히 합시다.

직원 팀이 두 개의 다른 프로젝트에서 작업하고 각 프로젝트에 대한 직원의 총 보수와 기여도가 다르다고 가정합니다.

그런 다음 이러한 프로젝트를 결합하면 결합된 프로젝트에서 직원의 기여도는 각 프로젝트에 대한 기여도의 합계입니다.

 

Shapley values in machine learning

 

그러나 플레이어의 Shapley 값을 기계 학습 모델의 기능과 어떻게 연관시킬 수 있습니까?

아래 그림과 같이 N개의 행과 M개의 기능이 있는 데이터 세트가 있다고 가정합니다.

 

 

여기서 Xᵢ는 데이터 세트의 i번째 특징이고 xᵢ⁽ʲ⁾는 j번째 예에서 i번째 특징의 값이며 y⁽ʲ⁾는 j번째 행의 대상입니다.

특성 값은 M 요소가 있는 행 벡터로 표시되는 특성 벡터를 형성할 수 있습니다.

여기에 X₁=x₁, X₂=x₂,... X_M=x_M이 있습니다(선형 대수학에서 벡터는 일반적으로 열 벡터로 간주되지만 이 문서에서는 행 벡터라고 가정합니다).

특징 벡터는 데이터 세트의 j번째 행이 될 수도 있습니다. 이 경우 다음과 같이 작성할 수 있습니다.

 

 

이 함수는 x의 모든 요소에 적용됨을 의미하는 특징 벡터 x를 사용합니다. 예를 들어 선형 모델의 경우 다음이 있습니다.

따라서 각 x 값에 대해 모델 예측은 f(x)입니다. 앞서 언급했듯이 이 특징 벡터 x는 훈련 데이터 세트의 인스턴스 중 하나이거나 훈련 데이터 세트에 존재하지 않는 테스트 데이터 인스턴스 중 하나일 수 있습니다.

예를 들어, 이 선형 모델을 사용하여 교육 예제 중 하나의 대상을 예측할 수 있습니다.

 

따라서 f(x⁽ʲ⁾)는 데이터 세트의 j번째 행에 대한 모델 예측이며, f(x⁽ʲ⁾)와 y⁽ʲ⁾의 차이는 j에 대한 모델의 예측 오차입니다. 

 

기계 학습 모델이 연합 게임이고 M 기능이 이 게임의 M 플레이어라고 가정할 수 있습니다.

 

coalition game : machine learning model

M Player : M Feature

 

하지만 이 게임의 characteristic function은 무엇이어야 할까요?

첫 번째 추측은 f(x) 자체일 수 있습니다.

그러나 특성 함수는 방정식 1을 충족해야 합니다. 즉, 플레이어가 없을 때 총 이득은 0입니다.

 

기능(플레이어)이 없을 때 f(x)를 어떻게 평가할 수 있습니까? 기능이 게임의 일부가 아닌 경우 현재 값을 알 수 없으며 해당 기능의 값을 모른 채 모델의 대상을 예측하려고 합니다.

게임에 기능이 없다는 것은 기능의 현재 값을 알 수 없다는 의미입니다.

이 경우 예측을 위해 훈련 세트만 사용할 수 있습니다.

 

여기에서 훈련 예제 샘플(또는 모두)에 대한 f(x⁽ʲ⁾)의 평균을 최선의 추정치로 취할 수 있습니다.

따라서 특성이 없을 때의 예측은 다음과 같습니다.

여기서 NA는 사용할 수 없는 기능을 의미합니다(따라서 여기서는 f의 매개변수를 사용할 수 없음). 또한 교육 데이터 세트(k≤N)에서 k 데이터 인스턴스(특징 벡터)를 샘플링했습니다. 이제 우리는 대연정(grand coalition)에 대한 우리의 characteristic function을 다음과 같이 정의합니다.

 

 

 

그런 다음 이러한 기능에 대한 marginal value of f이 필요합니다.

 

예를 들어 F={X₁, X₂, X₃, X₄, X₅}이고 연합 S={X₁, X₂, X₅}인 경우 특성 X₃ 및 X₄의 현재 값을 알 수 없습니다. 그래서

여기서는 f로 표현되는 모델이 NA 값을 처리할 수 있다고 가정합니다. 따라서 이 연합의 가치는

 

 

이제 방정식 3과 방정식 10을 사용하여 기능 Xᵢ의 Shapley 값을 계산할 수 있습니다.

이 방정식에서 방정식 3과 일치하도록 ϕₓᵢ를 작성해야 합니다.

그러나 단순화를 위해 ϕᵢ을 사용합니다. 따라서 이 방정식에서 i는 i번째 특징(Xᵢ)을 나타냅니다.

 

 

즉, 모든 Feature의 Shapely 값의 합계는 Feature의 현재 값을 사용한 모델의 예측과 모든 교육 예제에 대한 모델의 평균 예측 간의 차이를 나타냅니다.

 

이걸 실제로 shap이라는 라이브러리에 대입해보면, 특정 행의 shap의 총합 더하기 예측값을 더하면 f(x)가 나온다는 뜻입니다.

 

SHAP Value을 논의하기 전에 SHAP와 같은 설명자 모델에 대한 수학적 설명이 필요합니다. f를 설명할 원래 모델로 정의하고 다음과 같이 정의합니다.

따라서 모델은 특징 벡터 x를 취하고 f(x)는 해당 특징 벡터에 대한 모델 예측입니다.

이 특징 벡터는 훈련 데이터 세트(x⁽ʲ⁾)의 인스턴스 중 하나이거나 훈련 데이터 세트에 존재하지 않는 테스트 특징 벡터일 수 있습니다.

이제 feature 벡터의 feature가 있는지 여부를 표시하기 위해 단순화된 입력 기능 세트를 생성합니다.

벡터 x'를 단순화된 특징 벡터라고 합니다.

각 x'ᵢ은 해당 특성 Xᵢ이 특성 벡터에서 관찰되는지(x'ᵢ =1) 또는 알 수 없는지(x'ᵢ = 0)를 나타내는 이진 변수입니다. 예를 들어, 특징 벡터가 왼쪽과 같다면 벡터 x'는 오른쪽처럼 됩니다.

 

x'를 x에 매핑하는 매핑 함수가 있다고 가정할 수 있습니다.(h(x))

설명자는 M 이진 변수를 사용하는 해석 가능한 모델 g입니다.

여기서 M은 방정식 13에서 단순화된 입력 기능의 수입니다.

행 벡터 z'는 사용 가능한 x 값의 연합을 나타냅니다. 따라서 x'의 0개 요소는 z'에서 항상 0이고 x'의 1개 요소는 z'에서 1 또는 0이 될 수 있습니다.

예를 들면 아래와 같습니다.

이 두 feature만 z'에 해당하는 1을 가지므로 간단히 연합 S={X₁, X₃}를 나타냅니다.

또한 x'는 대연합(grand coalition) F={X₁, X₂, X₃}를 나타내므로 x'도 연합 벡터(coalition vector)로 간주할 수 있다고 결론을 내릴 수 있습니다.

대연합 x'에 매우 가까운 연합 벡터 z'로 시작한다고 가정합니다.

이 연합에 대한 g의 예측은 단순히 g(z')입니다. 그러나 z'를 사용하여 f의 예측을 어떻게 얻을 수 있습니까? 문제는 f가 연합 벡터가 아닌 특징 벡터를 취한다는 것입니다.

따라서 z'에 해당하는 특성 값을 찾으려면 매핑 함수 h(x)가 필요합니다.

여기서 hₓ(z')는 z'에 있는 기능의 해당 값을 반환하고 다른 기능의 값은 NA가 됩니다.

 

 

f(z)인 f의 예측이 (g(z'))인 g의 예측에 매우 근접하여 g가 f가 예측을 위해 사용하는 동일한 프로세스를 모방하도록 합니다. 

 

(점점 매우 복잡...)

g를 기준으로 설명 방법을 분류할 수 있습니다.

추가 feature 속성 방법에는 이진 변수의 선형 함수인 설명자 모델이 있습니다.

여기서 ci는 일부 상수입니다. 나중에 볼 수 있듯이 SHAP는 이 메서드 클래스에 속합니다.

그래서 방정식 11을 z'로 표현하고자 합니다. x를 특징 벡터로 하고 x'를 단순화된 특징 벡터라고 합니다.

 

여기서 ϕᵢ(f, x)는 Shapley Value가 f와 x의 함수임을 강조합니다.

여기서 우리는 x'의 모든 가능한 연합 벡터(x의 모든 연합에 해당)를 고려합니다.

각 연합 벡터 z'에 대해 feature i의 기여도를 계산합니다. |z'| z'의 0이 아닌 항목 수(해당 연합의 크기) 및 |x'| 는 x'(대연정의 크기)에서 0이 아닌 항목의 수입니다.

예를 들어, 3이 세 번째 특성 x₃를 나타내는 경우 다음과 같이 작성할 수 있습니다.

예를 들면 다음과 같습니다.

 

아래의 수식에는 몇가지 특정이 있다고 합니다...

Property 1 (Local accuracy)

여기서 ϕ₀ =E[f(x)], ϕᵢ는 f의 Shapley 값입니다.

특징 벡터 x가 있고 단순화된 특징 벡터가 x'라고 가정하면 x = hₓ(x')가 됩니다.

그런 다음 이 속성을 기반으로 x'에 대한 g의 예측은 x에 대한 원래 모델 f의 예측과 일치합니다. 그래서 우리는 쓸 수 있습니다

 

 

 ϕ₀ =E[f(x)].

 

Property 2 (Missingness)

Property 3 (Consistency)

 

 

 

From Shapley values to SHAP values

Shapley 값은 견고한 이론적 기반과 흥미로운 속성을 가지고 있지만 실제로는 계산하기 쉽지 않습니다.

이를 계산하려면 방정식 18에서 fₓ(z') 또는 방정식 11에서 fₛ(xₛ)를 계산해야 합니다. 

따라서 fₓ(z') 또는 fₛ(xₛ)를 계산한다는 것은 z' 또는 S에 포함되지 않은 몇 가지 누락된 기능으로 f(x)를 계산해야 함을 의미합니다.

예를 들어, 선형 모형에서 f(x)를 계산하려면 xθ의 모든 값이 필요합니다. 그래서 우리는 f(x)의 결측값을 처리할 방법이 필요합니다. 앞에서 언급한 바와 같이, 각 연립 S에 대해 x의 누락된 요소는 S에 없는 피쳐의 값입니다. fₛ(xₛ)를 계산하기 위해, 우리는 다음과 같이 가정합니다.

여기서 E[f(x)|xₛ]는 S에 존재하는 특징에 따른 f(x)의 기대값입니다. 마찬가지로 다음과 같이 쓸 수 있습니다.

수학식 23 또는 수학식 24의 조건부 기대치를 사용하여 계산된 Shapley 값을 SHAP(SHapley Additive exPlanation) Value이라고 합니다.

따라서 방정식 11에서 SHAP 값을 얻으려면 다음과 같이 작성할 수 있습니다.

 

 

(내용은 정말 좋은 것 같은데... 이해하기가 벅차다...)

 

(계속...)

 

 

 

Reference

https://towardsdatascience.com/introduction-to-shap-values-and-their-application-in-machine-learning-8003718e6827

https://datanetworkanalysis.github.io/2019/12/23/shap1

http://dmqm.korea.ac.kr/activity/seminar/297