Shapley 값은 협동 게임 이론에서의 해 개념으로, 협력한 플레이어들 집단 간에 총 이득 또는 비용을 공정하게 분배하는 방법을 제공한다. 1951년에 이를 도입한 Lloyd Shapley의 이름을 따서 명명되었으며, 집단적 결과가 산출될 때 각 참여자가 받을 공로 또는 책임의 정도에 대한 질문에 답한다. 이 방법은 가능한 모든 연합에 걸쳐 각 플레이어의 평균 한계 기여도를 계산하여 효율성, 대칭성, 가산성, 그리고 더미 플레이어 속성이라는 네 가지 기본 속성을 충족하는 분배를 보장한다. 경제학에서의 기원을 넘어, Shapley 값은 해석 가능한 머신 러닝의 초석이 되었으며, 여기서는 복잡한 모델의 예측을 개별 입력 특성에 귀속시키는 데 사용된다.
핵심 아이디어는 플레이어가 다른 플레이어들의 각 가능한 부분 집합에 합류할 때 전체 결과가 어떻게 변하는지 평가한 다음, 이러한 변화를 모든 부분 집합과 모든 가능한 합류 순서에 대해 평균하는 것이다. 이 접근 방식은 플레이어 간의 상호 작용을 고려하여, 기여도가 이미 연합에 누가 있는지에 따라 달라질 수 있음을 인식한다. 네 가지 공리적 속성을 동시에 충족하는 유일한 분배 규칙이기 때문에, 협동 이득을 나누는 유일한 공정한 방법으로 종종 설명된다.
정의
연합 게임에서, 플레이어 집합 \(N\)은 연합 \(S \subseteq N\)을 형성할 수 있으며, 가치 함수 \(v(S)\)는 \(S\)의 구성원들이 협력하여 얻을 수 있는 총 보상을 할당한다. 플레이어 \(i\)에 대한 Shapley 값은 다음 공식으로 주어진다:
\[\varphi_i(v) = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|! (n - |S| - 1)!}{n!} (v(S \cup \{i\}) - v(S))\]
여기서 \(n\)은 총 플레이어 수이다. 항 \(v(S \cup \{i\}) - v(S)\)는 플레이어 \(i\)의 연합 \(S\)에 대한 한계 기여도이다. 조합 가중치 \(\frac{|S|! (n - |S| - 1)!}{n!}\)는 \(S\)의 플레이어들이 \(i\)보다 앞서고 나머지 플레이어들이 뒤따르는 순열의 수를 설명한다. 동등한 공식은 모든 \(n!\) 가능한 플레이어 순서에 대해 한계 기여도를 평균하는데, 여기서 \(P_i^R\)은 순서 \(R\)에서 \(i\)보다 앞서는 플레이어 집합을 나타낸다:
\[\varphi_i(v) = \frac{1}{n!} \sum_R \left[ v(P_i^R \cup \{i\}) - v(P_i^R) \right]\]
이 해석은 연합이 한 번에 한 플레이어씩 형성되고, 각 플레이어가 보상으로 자신의 한계 기여도를 받은 다음, 모든 가능한 형성 순서에 대해 평균하는 것을 상상한다.
공리적 속성
Shapley 값은 공정한 분배를 정의하는 것으로 널리 받아들여지는 네 가지 공리에 의해 독특하게 특징지어진다:
- 효율성: 모든 플레이어의 Shapley 값의 합은 대연합의 총 가치와 같다, \(\sum_{i \in N} \varphi_i(v) = v(N)\). 이는 가치가 손실되거나 생성되지 않음을 보장한다.
- 대칭성: 두 플레이어 \(i\)와 \(j\)가 모든 연합에 동일하게 기여한다면 (즉, 둘 중 하나를 포함하지 않는 모든 \(S\)에 대해 \(v(S \cup \{i\}) = v(S \cup \{j\})\)), 그들은 동일한 몫을 받는다.
- 가산성: 두 게임 \(v\)와 \(w\)에 대해, 결합된 게임 \(v+w\)의 Shapley 값은 개별 Shapley 값의 합이다, \(\varphi_i(v+w) = \varphi_i(v) + \varphi_i(w)\). 이 속성은 복잡한 문제의 분해를 지원한다.
- 더미 플레이어: 플레이어 \(i\)가 어떤 연합에도 가치를 더하지 않는다면 (즉, 모든 \(S\)에 대해 \(v(S \cup \{i\}) = v(S)\)), 그들의 Shapley 값은 0이다.
이러한 공리는 Shapley의 1951년 논문에서 공식화되었고 1953년 출판물에서 더욱 정제되었다. 이는 값이 임의적이지 않고 합리적인 공정성 기준에서 비롯됨을 보장한다.
경제 및 비즈니스에서의 응용
협동 게임 이론에서 Shapley 값은 다양한 경제적 환경에서 비용과 이익을 할당하는 데 사용되어 왔다. 예를 들어, 비즈니스 파트너십에서 파트너는 다양한 프로젝트 조합에 대한 한계 기여도를 기반으로 이익을 나누는 데 사용할 수 있다. 공동 벤처의 비용 할당, 예를 들어 공유 인프라 비용을 여러 사용자 간에 분담하는 데 적용되었다. 공급망 관리에서는 기업들이 최종 제품을 생산하기 위해 협력할 때 구성 요소의 공정한 가격을 결정하는 데 도움이 된다. 이 방법은 또한 가중 투표 시스템에서 각 유권자의 영향력을 측정하는 투표력 분석에도 사용되지만, 그 맥락에서는 밀접하게 관련된 Banzhaf 권력 지수가 때때로 선호된다.
머신 러닝에서의 Shapley 값
머신 러닝에서 Shapley 값은 특성 귀속으로 알려진 분야인 모델의 개별 예측을 설명하기 위해 적용되었다. 플레이어는 입력 특성이고, 가치 함수 \(v(S)\)는 부분 집합 \(S\)의 특성만 알려졌을 때의 모델 예측이며, 일반적으로 다른 특성을 주변화하여 계산한다. 특성의 Shapley 값은 다른 모든 특성과의 상호 작용을 고려하여 예측에 대한 평균 기여도를 측정한다. 이 접근 방식은 모델에 구애받지 않으므로 딥 러닝 네트워크, 신경망 앙상블, 대규모 언어 모델 시스템을 포함한 모든 예측 모델에 적용할 수 있다.
주요 실용 구현은 2017년 Scott Lundberg와 Su-In Lee가 도입한 SHAP(SHapley Additive exPlanations)이다. SHAP는 복잡한 모델에 대한 Shapley 값을 근사하는 효율적인 알고리즘을 제공하는데, 정확한 계산은 특성 수에 따라 지수적으로 증가하기 때문이다. 이 방법은 모델 해석 가능성을 위한 표준 도구가 되었으며, 데이터 과학자와 규제 기관이 모델이 특정 결정을 내린 이유를 이해하는 데 도움을 준다.
계산 과제 및 근사
정확한 Shapley 값은 \(2^n\)개의 부분 집합에 대한 합산을 요구하므로, 특성이 많은 모델에는 계산적으로 불가능하다. 30개의 특성을 가진 모델의 경우, 가능한 연합은 10억 개가 넘는다. 여러 근사 기법이 개발되었다:
- Monte Carlo 샘플링: 순열 또는 부분 집합을 무작위로 샘플링하고 한계 기여도를 평균한다. 이는 제어 가능한 분산으로 편향되지 않은 추정치를 제공한다.
- SHAP 및 TreeSHAP: 랜덤 포레스트 및 그래디언트 부스팅과 같은 트리 기반 모델의 경우, TreeSHAP는 트리 구조를 활용하여 다항식 시간 내에 정확한 Shapley 값을 계산한다.
- KernelSHAP: 가중 선형 회귀를 사용하여 Shapley 값을 근사하는 모델에 구애받지 않는 방법으로, 종종 블랙박스 모델에 사용된다.
- 그래디언트 기반 방법: 미분 가능한 모델의 경우, 그래디언트를 사용하여 근사를 계산할 수 있지만, 모든 공리를 정확히 충족하지는 않을 수 있다.
이러한 근사는 신용 점수, 의료 진단, 자연어 처리와 같은 실제 응용 분야에서 Shapley 값을 실용적으로 만들었다.
다른 귀속 방법과의 관계
Shapley 값은 종종 다른 특성 귀속 기법과 비교된다. 순열 중요도나 그래디언트 기반 돌출 맵과 같은 단순한 방법과 달리, Shapley 값은 특성 상호 작용을 고려하고 효율성 속성을 충족하여 귀속이 모델 출력의 합이 되도록 보장한다. 그러나 주변화할 때 특성이 독립적이라고 가정하므로, 특성이 고도로 상관되어 있으면 비현실적인 샘플이 생성될 수 있다. LIME(Local Interpretable Model-agnostic Explanations)과 같은 대안은 더 빠르지만 동일한 공리적 속성을 보장하지는 않는다. 협동 게임 이론에서 Shapley 값은 핵(nucleolus) 및 코어(core)를 포함한 여러 해 개념 중 하나이지만, 네 가지 공리를 동시에 충족하는 유일한 해이다.
확장 및 변형
다양한 맥락을 위해 Shapley 값의 여러 확장이 제안되었다. 가중 Shapley 값은 플레이어가 서로 다른 가중치를 가질 수 있게 하여 불평등한 협상력을 반영한다. Shapley-Shubik 권력 지수는 투표 게임에 값을 적용하여 플레이어가 결정적일 확률을 측정한다. 머신 러닝에서는 Shapley 상호 작용 지수와 같은 변형이 총 귀속을 주 효과와 특성 간 상호 작용 효과로 분해한다. 시계열 데이터의 경우 동적 Shapley 값은 시간적 의존성을 설명한다. 이러한 확장은 공정한 한계 기여도 평균이라는 핵심 아이디어를 유지하면서 특정 문제 구조에 적응한다.
한계 및 비판
이론적 매력에도 불구하고 Shapley 값에는 한계가 있다. 머신 러닝 응용에서 특성 독립성 가정은 특성이 상관되어 있을 때 오해의 소지가 있는 귀속을 생성할 수 있다. 근사를 사용하더라도 지수적 계산 비용은 매우 고차원 데이터에는 엄청날 수 있다. 또한 예측 모델의 가치 함수가 항상 잘 정의된 것은 아니며, 특성을 주변화하려면 특성 공간에 대한 분포가 필요한데, 이는 알려지지 않을 수 있다. 비평가들은 공리적 속성이 우아하지만 실제 시나리오에서 인간의 공정성 개념과 항상 일치하지는 않을 수 있다고 주장한다. 그럼에도 불구하고 Shapley 값은 게임 이론과 해석 가능한 AI 모두에서 기초 개념으로 남아 있으며, 이러한 문제를 해결하기 위한 활발한 연구가 진행 중이다.
역사적 배경
Lloyd Shapley는 RAND Corporation에 있을 때인 1951년에 이 값을 도입했고, 1953년에 공식적으로 출판했다. 그의 연구는 협동 게임 이론의 초기 아이디어, 특히 John von Neumann과 Oskar Morgenstern의 연구에 기반을 두었다. Shapley는 나중에 게임 이론에 대한 공헌으로 Alvin Roth와 함께 2012년 노벨 경제학상을 수상했다. 머신 러닝에서 Shapley 값의 채택은 AI 시스템이 더 복잡해짐에 따라 모델 해석 가능성에 대한 필요성에 의해 2010년대에 시작되었다. 오늘날 이는 데이터 과학자 도구 키트의 표준 도구이며 SHAP 및 scikit-learn과 같은 주요 라이브러리에 구현되어 있다.