섀플리 값

통계 게임 개발 소프트웨어 마지막 수정: 2026-09-04 04:17:26

1. 개요[편집]

섀플리 값 Shapley value
제안	로이드 섀플리 (1953)
대상	이전가능효용 협조 게임 $(N, v)$
정의	모든 참여 순서에 대한 한계기여의 평균
유일성 근거	효율성 · 대칭성 · 더미 · 가법성
계산 비용	정의대로면 $O(2^n)$ — 간결한 게임에서도 #P-완전
기계학습 쪽 이름	SHAP

“누가 얼마나 기여했는가”는 원래 답이 없는 질문이다. 섀플리는 그 질문에 답을 만든 게 아니라, 답이 만족해야 할 조건 네 개를 적었더니 답이 하나로 정해졌다는 것을 보였다.

섀플리 값(Shapley value)은 협조 게임에서 대연합이 만들어 낸 총가치를 참여자들에게 나누는 배분 규칙으로, 네 가지 공정성 공리를 동시에 만족하는 유일한 배분이다. 로이드 섀플리가 1953년 논문 A Value for n-Person Games 에서 제시했고¹, 이후 비용 배분·투표력 지수·데이터 가치 평가를 거쳐 지금은 기계학습 모형 해석의 표준 도구 SHAP의 수학적 뼈대로 가장 널리 알려져 있다.

이 문서는 배분 규칙 자체와 그 계산을 다룬다. 기계학습 해석 도구로서의 사용법·비판·규제 맥락은 설명 가능한 인공지능 문서가 맡는다.

2. 협조 게임 — 무대 설정[편집]

게임 이론에서 흔히 다루는 내시 균형은 비협조 게임의 개념이다. 각자 전략을 고르고, 구속력 있는 약속은 없으며, 답은 “아무도 혼자 이탈할 유인이 없는 상태”다. 섀플리 값은 정반대 무대에 선다. 참여자들이 구속력 있게 뭉칠 수 있고, 뭉치면 얼마를 벌 수 있는지가 이미 주어져 있으며, 남은 질문은 오직 **“번 돈을 어떻게 나누는가”**뿐이다.

무대는 순서쌍 $(N, v)$ 다. $N = \{1,\dots,n\}$ 은 참여자 집합, 특성함수(characteristic function) $v : 2^N \to \mathbb{R}$ 는 부분집합(연합) $S$ 가 독자적으로 확보할 수 있는 가치를 준다. 규약으로 $v(\varnothing) = 0$ . 효용이 화폐처럼 자유롭게 이전된다고 보므로 이런 게임을 이전가능효용(TU) 게임이라 부른다.

핵심은 $v$ 가 부분집합의 함수라는 점이다. 개인의 능력이 아니라 “누가 누구와 함께 있느냐”가 가치를 결정하므로, 시너지와 중복이 모두 $v$ 안에 이미 들어 있다. 배분 규칙의 일이란 그 얽힌 시너지를 되풀어 개인에게 되돌리는 것이다.

장갑 게임을 예로 들자. 참여자 1은 왼쪽 장갑을, 참여자 2와 3은 각각 오른쪽 장갑을 한 짝씩 갖고 있다. 짝이 맞아야 팔리므로 $v(S)$ 는 $S$ 안에서 만들 수 있는 장갑 켤레 수다.

v(\{1,2\}) = v(\{1,3\}) = v(N) = 1, \qquad v(\{2,3\}) = v(\{i\}) = 0

직관은 이미 답을 안다 — 왼쪽 장갑은 희소하고 오른쪽 장갑은 남아돈다. 문제는 “희소하니까 더 받는다”를 숫자로 얼마나 더 주느냐이고, 여기서부터는 직관이 못 따라온다.

3. 정의 — 모든 순서에 대한 평균 한계기여[편집]

섀플리의 발상은 줄 세우기다. 참여자들이 무작위 순서로 방에 하나씩 들어온다고 하자. 각자가 들어오는 순간 방의 가치가 얼마나 올랐는지(= 한계기여)를 기록하고, 가능한 $n!$ 개 순서 전부에 대해 평균낸다. $\pi$ 를 순열, $P_i^\pi$ 를 순열 $\pi$ 에서 $i$ 보다 앞에 선 사람들의 집합이라 하면

\phi_i(v) \;=\; \frac{1}{n!} \sum_{\pi} \Big[\, v\big(P_i^\pi \cup \{i\}\big) - v\big(P_i^\pi\big) \Big]

이다. 같은 것을 순열 대신 부분집합으로 세면 익숙한 형태가 나온다. 앞선 집합이 정확히 $S$ 가 되는 순열이 $|S|!\,(n-|S|-1)!$ 개이므로

\phi_i(v) \;=\; \sum_{S \subseteq N \setminus \{i\}} \frac{|S|!\;(n-|S|-1)!}{n!}\Big[\, v\big(S \cup \{i\}\big) - v(S) \Big]

앞의 계수를 “이상한 가중치”로 외울 필요는 없다. 그것은 그저 순열의 비율이고, 결과적으로 연합 크기 $|S| = 0, 1, \dots, n-1$ 각 층에 정확히 같은 무게 $1/n$ 씩을 배정한다.

장갑 게임에 대입해 보자. 6개 순열을 다 적으면 참여자 1은 그중 4번(2·3 중 적어도 하나가 이미 방에 있을 때) 한계기여 1을 만들고, 참여자 2와 3은 각각 1번씩만 만든다.

\phi_1 = \tfrac{4}{6} = \tfrac{2}{3}, \qquad \phi_2 = \phi_3 = \tfrac{1}{6}

합은 정확히 $1 = v(N)$ 이다. 희소한 왼쪽 장갑이 전체의 3분의 2를 가져가는데, 이 숫자는 어디서 온 게 아니라 공리에서 강제된 값이다.

4. 네 공리와 유일성[편집]

섀플리 값이 특별한 유일한 이유는 다음 네 공리를 동시에 만족하는 배분 규칙이 오직 하나라는 정리다.

효율성(efficiency). $\sum_{i \in N} \phi_i(v) = v(N)$ . 총가치가 남김없이, 그리고 초과 없이 배분된다.
대칭성(symmetry). 모든 $S \subseteq N\setminus\{i,j\}$ 에 대해 $v(S \cup \{i\}) = v(S \cup \{j\})$ 이면 $\phi_i = \phi_j$ . 이름표는 배분에 영향을 주지 않는다.
더미(dummy/null player). 모든 $S$ 에 대해 $v(S \cup \{i\}) = v(S)$ 이면 $\phi_i = 0$ . 아무 데도 보태지 않는 사람은 못 받는다.
가법성(additivity). $\phi(v + w) = \phi(v) + \phi(w)$ . 두 게임을 따로 정산하든 합쳐서 정산하든 결과가 같다.

증명의 뼈대는 선형대수다. $N$ 위의 TU 게임 전체는 차원 $2^n - 1$ 의 벡터공간이고, 만장일치 게임

u_T(S) = \begin{cases} 1 & T \subseteq S \\ 0 & \text{그 외}\end{cases} \qquad (\varnothing \neq T \subseteq N)

들이 그 기저를 이룬다. 그런데 $c\,u_T$ 에서는 $T$ 밖의 사람이 전부 더미이므로 그들의 배당은 0, $T$ 안의 사람들은 서로 대칭이므로 배당이 같고, 효율성이 총합을 $c$ 로 묶으니 **각자 $c/|T|$ **로 값이 완전히 결정된다. 가법성이 이 결정을 기저 전체의 선형결합으로 확장한다. 공리를 만족하는 규칙이 존재한다면 유일해야 하고, 앞의 평균 한계기여 공식이 실제로 네 공리를 만족하므로 존재성도 끝난다.²

이 증명은 부산물로 섀플리 값의 가장 읽기 쉬운 해석을 준다. 임의의 게임을 $v = \sum_T \Delta_v(T)\,u_T$ 로 전개했을 때의 계수 $\Delta_v(T)$ 를 하사니 배당(Harsanyi dividend)이라 부르는데, 이는 연합 $T$ 가 자기 부분연합들이 이미 만든 것 너머로 새로 창출한 잉여다. 그러면

\phi_i(v) = \sum_{T \ni i} \frac{\Delta_v(T)}{|T|}

— 모든 연합이 만든 잉여를 그 연합 구성원끼리 똑같이 나눠 갖는다. 섀플리 값의 정체는 사실 이 한 줄이다.

가법성은 네 공리 중 유일하게 “공정성”이라기보다 회계 편의처럼 보여서 오래 미움을 받았다. 영(Young, 1985)이 이를 갈아 끼웠다 — 가법성 대신 한계성(marginality: 두 게임에서 $i$ 의 한계기여가 전부 같으면 배당도 같다)을 넣어도 효율성·대칭성과 함께 섀플리 값이 유일하게 나온다. “배당은 그 사람의 한계기여만 보고 정해져야 한다”는 훨씬 설득력 있는 요구가 같은 결론을 낳는다는 점이, 섀플리 값이 지금까지 살아남은 이유다.

5. 공정하지만 안정적이지는 않다 — 코어와의 관계[편집]

배분 규칙의 다른 계보가 코어(core)다. 코어는 공정성이 아니라 이탈 유인이 없는가를 묻는다.

\mathrm{Core}(v) = \Big\{ x \in \mathbb{R}^n \;:\; \sum_{i \in N} x_i = v(N), \;\; \sum_{i \in S} x_i \ge v(S)\ \ \forall S \subseteq N \Big\}

어떤 연합도 “우리끼리 나가면 더 번다”고 말할 수 없는 배분들의 집합이다. 코어는 비어 있을 수 있다 — 3인 다수결 게임(두 명만 모이면 1을 벌고, 혼자서는 0)이 대표적으로, 어떤 배분을 제시해도 손해 보는 둘이 뭉쳐 뒤집을 수 있다. 코어가 비지 않을 필요충분조건은 본다레바-섀플리 정리가 주는 균형성(balancedness)이고, 이는 코어를 찾는 선형계획법 문제에 쌍대성을 적용해 나온다.

여기서 섀플리 값의 성격이 드러난다. 섀플리 값은 코어 안에 있다는 보장이 없다. 위 장갑 게임의 코어는 계산해 보면 한 점 $(1, 0, 0)$ 뿐이다 — $x_1 + x_2 \ge 1$ 과 $x_1 + x_3 \ge 1$ 이 총합 1과 만나면 $x_2 = x_3 = 0$ 이 강제된다. 그런데 섀플리 값 $(2/3, 1/6, 1/6)$ 에서는 $\phi_1 + \phi_2 = 5/6 < 1$ 이므로 연합 $\{1,2\}$ 가 이 배분을 거부하고 이탈한다. 공정한 배분과 유지되는 배분은 다른 물건이다.

볼록 게임( $v(S \cup \{i\}) - v(S)$ 가 $S$ 에 대해 단조증가, 즉 초모듈러)에서는 사정이 좋아진다. 코어가 비지 않고, 코어의 꼭짓점이 $n!$ 개 순열의 한계기여 벡터들로 전부 주어지며, 섀플리 값은 그 벡터들의 평균이므로 코어의 무게중심이 된다(섀플리, 1971). 규모의 경제가 있는 비용 배분 문제가 대개 여기 속해서, 실무에서 섀플리 값이 통하는 이유의 절반은 이 정리다.
뉴클리올루스(슈마이들러, 1969)는 각 연합의 불만을 사전식으로 최소화하는 배분으로, 코어가 비지 않으면 항상 코어 안에 있다. 안정성이 중요하면 이쪽이다.
밴자프 지수는 한계기여를 순열이 아니라 부분집합에 균등 가중해 평균한다. 대칭성·더미·가법성은 만족하지만 효율성을 만족하지 않아 총합이 $v(N)$ 이 되지 않는다. 투표력 비교처럼 총합에 의미가 없는 맥락에서는 이 쪽을 쓰기도 한다.

6. 계산 — $2^n$ 이라는 벽[편집]

정의를 그대로 계산하려면 $v$ 를 $2^n$ 번 호출해야 한다. $n = 20$ 이면 백만, $n = 30$ 이면 십억. 게다가 특성함수 하나를 계산하는 데 모형 추론이나 시뮬레이션 한 번이 필요한 응용에서는 이 숫자에 다시 상수 수백이 곱해진다. 그리고 지름길을 기대하기도 어렵다 — 가중 다수결 게임처럼 특성함수가 몇 개의 숫자로 간결하게 주어지는 경우조차 섀플리 값 계산은 #P-완전이라는 것이 덩과 파파디미트리우(1994)의 결과다. 세는 문제의 어려움이라 NP-완전보다 나쁜 소식이다.

우회로는 세 갈래다.

6.1. 몬테카를로 순열 표집[편집]

정의가 이미 ” $n!$ 개 순열에 대한 평균”이므로, 순열을 무작위로 $m$ 개 뽑아 평균내면 곧바로 불편 추정량이 된다. 표준오차는 $\sigma_i/\sqrt{m}$ 이라 $n$ 과 무관하게 $O(\varepsilon^{-2})$ 표본이면 되고(카스트로 외, 2009), 한계기여의 범위가 $r$ 이면 회프딩 부등식으로 $m = O\big((r/\varepsilon)^2 \log(n/\delta)\big)$ 라는 명시적 보증도 나온다. 몬테카를로 방법의 표준 분산 감소 기법이 그대로 먹힌다.

층화. 참여자 $i$ 의 한계기여를 “앞에 몇 명 서 있었는가”로 층을 나눠 층별로 표본 수를 배분하면 분산이 크게 준다. 한계기여의 변동이 대개 위치에 강하게 의존하기 때문이다.
대조 순열. 순열 $\pi$ 를 뽑을 때 뒤집은 $\pi^{R}$ 을 짝지어 함께 쓰면 음의 상관이 생겨 분산이 준다.
순열 하나로 $n$ 명 전부. 순열 하나를 훑으면서 누적 가치를 갱신하면 $v$ 호출 $n+1$ 번으로 모든 참여자의 한계기여를 동시에 얻는다. 구현할 때 이걸 놓치면 비용이 $n$ 배가 된다.

6.2. 다중선형 확장[편집]

오언(1972)은 $v$ 를 초입방체 위의 매끄러운 함수로 늘렸다. 각자가 독립적으로 확률 $x_i$ 로 참여한다고 보고

f(x_1,\dots,x_n) = \sum_{S \subseteq N} \Big(\prod_{i \in S} x_i\Big) \Big(\prod_{j \notin S} (1 - x_j)\Big) v(S)

로 두면, 섀플리 값이 대각선 위 편미분의 적분으로 나온다.

\phi_i(v) = \int_0^1 \frac{\partial f}{\partial x_i}(t, t, \dots, t)\, dt

조합 합이 1차원 적분으로 바뀌므로 수치적분 격자점마다 이항 표집만 하면 되고, 연속적 참여를 다루는 아우만-섀플리 가격 이론도 이 확장 위에 서 있다. 이 형태가 특히 좋은 것은 구조가 있는 $v$ 에서 적분이 닫힌 형태로 풀릴 때다.

6.3. 구조를 이용한 정확 계산[편집]

$v$ 가 임의의 블랙박스가 아니면 다항 시간이 열린다.

게임 구조	방법	비용
가중 투표 게임	의석 합에 대한 동적 계획법·생성함수	쿼터에 대해 유사다항
그래프로 통신이 제한된 게임	미어슨 값 — 연결된 성분만 가치를 낸다	그래프 구조에 의존
결정 트리 앙상블	TreeSHAP — 트리를 타고 내려가며 동적계획	$O(TLD^2)$
활주로 비용 게임	정렬 후 구간별 균등분담 공식	$O(n \log n)$

첫 줄이 앞의 #P-완전 결과와 모순처럼 보이지만 아니다. 동적계획의 상태가 쿼터(가결선) 값이라 입력을 이진수로 적었을 때의 크기에 대해서는 지수적이다 — 배낭 문제와 정확히 같은 종류의 유사다항 알고리즘이고, 실제 의회처럼 쿼터가 작으면 그냥 계산된다.

마지막 줄이 고전이다. 공항 활주로 문제(리틀차일드·오언, 1973)에서 각 항공기는 자기 기종에 필요한 활주로 길이가 있고, 실제 활주로는 최장 요구 길이만큼 짓는다. 이 비용 게임의 섀플리 값은 활주로를 길이 구간으로 쪼개고 각 구간을 그 구간을 필요로 하는 항공기들끼리 균등분담하는 규칙과 정확히 일치한다. 지수적 정의에서 출발해 정렬 한 번짜리 규칙이 나오는 셈이고, 실제 공항 착륙료 산정에 쓰였다.

7. SHAP — 특징을 참여자로 세우기[편집]

런드버그와 리(2017)가 한 일은 무대를 갈아 끼운 것이다. 참여자 = 입력 특징, 연합의 가치 = 그 특징들만 알 때의 모형 출력. 그러면 예측값 $f(x)$ 와 기준값 $\mathbb{E}[f(X)]$ 의 차이가 효율성 공리에 의해 특징들에게 남김없이 배분된다.

f(x) - \mathbb{E}[f(X)] = \sum_{i=1}^{M} \phi_i

이 “덧셈으로 딱 떨어지는 설명”이 SHAP을 순식간에 표준으로 만들었다. 두 가지 계산 경로가 이 문서의 앞 절과 직결된다.

커널SHAP은 몬테카를로가 아니라 가중 최소제곱으로 간다. 부분집합 $S$ 를 뽑아 $\big(\mathbb{1}_S,\ v(S)\big)$ 쌍을 만들고, 여기에 섀플리 커널

\pi(S) = \frac{M-1}{\binom{M}{|S|}\,|S|\,(M - |S|)}

을 가중치로 얹어 선형회귀를 적합하면 회귀계수가 정확히 섀플리 값이 된다. 아주 작은 연합과 아주 큰 연합 쪽으로 가중치가 발산하듯 몰리는데, 특징 하나만 켜거나 하나만 끈 경우가 한계기여 정보를 가장 많이 담고 있기 때문이다. 같은 뼈대에서 가중치를 임의로 고르면 설명 가능한 인공지능 문서가 다루는 LIME이 되므로, 커널SHAP은 “LIME의 임의적 커널 폭을 공리로 대체한 것”으로 읽으면 정확하다.

트리SHAP은 결정 트리 앙상블에 한해 정확한 값을 다항 시간에 준다. 랜덤 포레스트와 그래디언트 부스팅이 지배하는 정형 데이터에서 SHAP이 사실상 기본값이 된 실질적 이유가 이것이다.

그런데 공리는 $v$ 를 정해 주지 않는다. 학습된 모형 $f$ 는 항상 전체 특징을 요구하므로 “없는 특징”을 적분해 없애야 하고, 여기서 갈래가 생긴다.

v_{\text{조건부}}(S) = \mathbb{E}\big[f(X) \mid X_S = x_S\big], \qquad v_{\text{주변}}(S) = \mathbb{E}\big[f(x_S,\, X_{\bar S})\big]

특징들이 독립이면 둘이 같지만, 상관이 있으면 답이 갈린다. 주변(개입) 방식은 상관 구조를 깨서 현실에 없는 조합에서 모형을 평가하고, 조건부 방식은 모형이 실제로 쓰지도 않는 특징에 0이 아닌 기여를 준다(쓰는 특징과 상관돼 있다는 이유만으로). 그래서 상관된 특징들 사이에서는 SHAP 값이 갈라지거나 임의로 나뉘어 보이는 현상이 흔하고, 이는 버그가 아니라 $v$ 선택이 공리 바깥에 있다는 사실의 귀결이다. 자세한 논쟁과 이를 겨냥한 우회 공격 사례는 설명 가능한 인공지능 문서에 있다.

한 가지는 몇 번을 반복해도 지나치지 않다. 섀플리 값은 인과가 아니다. 이 배분은 “이 모형이 무엇에 얼마나 의존하는가”에 대한 답이지 “이 세계에서 무엇을 바꾸면 결과가 바뀌는가”에 대한 답이 아니다. 후자는 인과 추론의 영역이고, 개입 없이 관측만으로 답할 수 있는 질문이 아니다.³

8. 다른 응용[편집]

투표력. 섀플리-슈빅 지수(1954)는 가중 투표 게임에 섀플리 값을 그대로 적용해, 의석수가 아니라 “무작위 순서로 찬성표가 쌓일 때 내가 가결선을 넘기는 결정타가 될 확률”로 권력을 잰다. 의석 비율과 권력 비율이 크게 어긋난다는 것이 이 지수의 반복되는 교훈이다.
비용 배분. 여러 부서가 공동 설비를 쓸 때의 요금, 공동 연구의 지분, 공유 인프라의 유지비. 규모의 경제가 있으면 게임이 볼록해지고 앞 절의 정리에 의해 섀플리 값이 코어 안에 들어가므로, “공정하면서 아무도 이탈하지 않는” 요금표가 나온다.
데이터 가치 평가. 학습 데이터 한 점(또는 한 제공자)을 참여자로, 검증 성능을 $v$ 로 두면 데이터의 기여를 배분할 수 있다(Data Shapley, 2019). 연합 학습에서 참여 기관에 보상을 나누는 문제가 정확히 이 형태라 활발히 쓰이는데, $v$ 한 번 계산이 재학습 한 번이라 계산 비용이 이 분야 연구의 절반을 차지한다.
민감도 해석. 입력을 참여자로 두고 출력 분산을 $v$ 로 삼으면 섀플리 효과가 나온다. 입력이 독립일 때 이 값은 소볼 지수의 1차 지수와 총 지수 사이에 놓이는데, 상호작용 몫을 관련 입력들에게 공평하게 쪼개 총합이 정확히 1이 되게 만들기 때문이다. 상관된 입력에서 소볼 분해가 먼저 무너지는 것과 달리 섀플리 효과는 여전히 정의되므로, 민감도 해석과 대리 모델 검토에서 실용적 가치가 있다.

9. 읽을 때 조심할 것[편집]

비용은 지수적이고, 보고되는 값은 거의 항상 근사다. 표본 수와 추정 오차를 함께 보고하지 않은 섀플리 값은 소수점 두 자리가 의미 없을 수 있다.
$v$ 를 명시하지 않은 섀플리 값은 해석할 수 없다. 같은 데이터, 같은 모형, 다른 라이브러리에서 다른 숫자가 나오는 이유의 대부분이 여기다.
효율성은 “합이 맞는다”이지 “옳다”가 아니다. 총합이 딱 떨어지는 표를 보면 정확해 보이지만, 그것은 공리가 강제한 회계 항등식일 뿐이다.
공정성과 안정성을 혼동하지 않는다. 게임이 볼록하지 않으면 섀플리 값 배분은 실제 협상에서 유지되지 않는다.
순위만 볼 거면 더 싼 도구를 먼저 재 본다. 순열 중요도처럼 훨씬 싼 방법이 같은 순위를 주는 경우가 흔하고, 그럴 때 섀플리 값의 추가 비용은 “덧셈으로 분해된다”는 성질에만 지불하는 것이다.⁴

10. 관련 문서[편집]

섀플리는 2012년 앨빈 로스와 함께 “안정적 배분과 시장 설계의 실제” 공로로 노벨 경제학상을 받았다. 그런데 수상 사유의 중심은 이 문서의 섀플리 값이 아니라 게일-섀플리 안정 결혼 알고리즘 쪽이었다. 정작 자기 이름이 가장 널리 불리는 업적으로는 상을 못 받은 셈인데, 그 이름이 60년 뒤 파이썬 패키지 이름(shap)으로 매일 수십만 번 임포트될 줄은 본인도 몰랐을 것이다. ↩
섀플리의 원 논문은 효율성과 더미를 하나로 묶은 운반자 공리(carrier axiom)를 썼다. ” $T$ 가 운반자이면, 즉 모든 $S$ 에 대해 $v(S) = v(S \cap T)$ 이면 $\sum_{i \in T} \phi_i = v(N)$ “이라는 형태다. 오늘날 교과서가 넷으로 쪼개 쓰는 이유는 셋이 더 멋있어서가 아니라, 어느 공리를 빼면 무엇이 깨지는지를 보여 주기 편해서다. ↩
이 경고를 매번 붙이는데도 현장 보고서의 SHAP 막대그래프에는 여전히 “이 변수를 줄이면 불량률이 내려갑니다”가 달린다. 모형이 상관을 학습했을 뿐인데 그것을 개입 지침으로 읽는 순간, 우리는 아이스크림 판매를 금지해 익사를 줄이려는 정책을 세우고 있는 것이다. ↩
그래도 그 성질에 값을 지불할 이유는 분명히 있다. 감사·규제 문서에서 “각 요인의 기여를 합하면 최종 점수가 됩니다”라는 한 줄이 만들어 주는 설득력은 순위 목록이 절대 주지 못한다. 다만 그 설득력이 수학적 유일성에서 오는 것이지 진실성에서 오는 것이 아니라는 점을 파는 쪽도 사는 쪽도 잊지 않는 것이 좋다. ↩