🤖 machine learning

Shapley Value Approximation Based on k-Additive Games

본 논문은 공정한 분할과 기계 학습 해석 가능성에 대한 정확한 계산에 내재된 지수적 계산 복잡성을 극복하기 위해 $k$ -가법적 대리 게임을 적합시켜 샤플리 값을 추정하는 새로운 근사 방법인 SVA $k_{\text{ADD}}$ 를 소개합니다.

원저자: Guilherme Dean Pelegrina, Patrick Kolpaczki, Eyke Hüllermeier

게시일 2026-05-13

📖 4 분 읽기☕ 가벼운 읽기

CC0 1.0

원저자: Guilherme Dean Pelegrina, Patrick Kolpaczki, Eyke Hüllermeier

원본 논문은 CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/)에 따라 공공 도메인에 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

"Shapley Value Approximation Based on k-Additive Games"라는 논문을 쉬운 언어와 일상적인 비유로 설명합니다.

큰 그림: 공평하게 파이 나누기

당신과 친구들이 레모네이드 가게를 운영한다고 상상해 보세요. 하루가 끝나고 수익이 생겼습니다. 큰 질문은 바로 이것입니다: 누가 돈을 얼마나 받아야 할까요?

레몬을 짜는 사람이 가장 많은 일을 했을까요?
간판을 들고 서 있는 사람이 가장 많은 고객을 끌어들였을까요?
설탕을 가져온 사람이 음료를 더 맛있게 만들었을까요?

기계 학습 (AI) 의 세계에서도 이는 동일한 문제입니다. AI 모델이 예측을 합니다 (질병을 진단하거나 이메일이 스팸인지 추측하는 것처럼). 우리는 알고 싶습니다: 어떤 특정 데이터 (특성) 가 그 예측을 담당했을까요?

"Shapley Value"는 로이드 샤플리 (Lloyd Shapley) 라는 게임 이론가가 고안한 수학적 공식입니다. 이는 공평함의 금표준입니다. 모든 가능한 플레이어 조합을 살펴봄으로써 각 "플레이어"(특성) 가 최종 결과에 얼마나 기여했는지 정확히 계산합니다.

문제: 수학이 너무 어렵습니다

여기 함정이 있습니다: Shapley Value 를 완벽하게 계산하려면 모든 가능한 팀 조합을 확인해야 합니다.

친구가 10 명이면 조합은 1,024 가지입니다.
친구가 20 명이면 조합은 100 만 개가 넘습니다.
친구가 50 명이면 그 숫자는 너무 커서 우주의 나이보다 더 오래 걸려도 계산할 수 없습니다.

현대 AI 모델은 종종 수백 또는 수천 개의 특성을 가지고 있기 때문에 정확한 Shapley Value 를 계산하는 것은 불가능합니다. 해변의 모래 알갱이 하나하나를 세어 해변의 가치를 공평하게 나누려는 것과 같습니다. 우리는 단축키가 필요하지만, 그 단축키는 신뢰할 수 있을 만큼 정확해야 합니다.

해결책: SVAkADD (스마트 대리 모델 방법)

이 논문의 저자들은 SVAkADD라는 새로운 방법을 제안합니다. 모든 모래 알갱이를 세려고 시도하는 대신, 실제 게임을 모방하지만 훨씬 쉽게 풀 수 있는 단순화된 모델(대리 모델) 을 구축합니다.

다음은 그들이 사용하는 창의적인 비유를 통해 설명하는 방법입니다:

1. "팀워크" 가정 (k-Additivity)

저자들은 모든 사람의 기여가 중요하지만, 복잡한 팀워크는 보통 특정 크기에서 멈춘다고 가정합니다.

1-Additive: 개인 노력만 중요합니다. (누구와 일하든 당신은 일을 잘합니다).
2-Additive: 짝이 중요합니다. (당신과 가장 친한 친구는 함께 일할 때 훌륭하지만, 세 명이 모이면 혼란스러울 수 있습니다).
3-Additive: 작은 그룹이 중요합니다. (세 사람은 잘 어울리지만, 열 명으로 구성된 위원회는 너무 지저분하여 독특한 "마법" 효과를 내기 어렵습니다).

이 논문에서는 이를 k-Additivity라고 부릅니다. 4 명, 5 명, 또는 10 명이 동시에 상호작용하는 경우는 매우 드물거나 무시할 수 있으므로 이를 무시할 수 있다고 가정합니다. 이로써 수학적으로 불가능한 문제가 관리 가능한 문제로 바뀝니다.

2. "맛보기 테스트" (샘플링)

모든 가능한 레모네이드 레시피 (연합) 를 테스트하는 대신, 연구자들은 레시피의 무작위 샘플을 취합니다.

그들은 몇 가지 특정 재료 조합을 섞습니다.
그 결과를 맛봅니다 (값을 계산합니다).
이 몇 가지 맛보기 테스트를 사용하여 단순화된 모델을 "적합"시킵니다.

3. "마법 공식" (최적화)

맛보기 테스트를 마치면, 그들은 단순화된 모델의 매개변수를 찾기 위해 특정 수학 퍼즐 (최적화 문제) 을 풉니다.

멋진 점: 저자들은 수학적으로 증명했습니다. 만약 맛보기 테스트에 올바른 "가중치"를 선택한다면, 이 단순화된 모델에서 얻은 답은 모든 조합을 테스트했을 때의 완벽한 Shapley Value 와 정확히 동일하다는 것입니다.
그들은 10 명 간의 복잡한 상호작용을 무시하고 있지만, 수학은 테스트한 시나리오에 대해 최종 "공평한 몫" 숫자가 올바르게 나온다는 것을 보장합니다.

다른 단축키보다 왜 더 나은가

다른 방법들은 무작위로 추측하고 평균을 내어 답을 추측하려 합니다 (주사위를 여러 번 굴리는 것처럼).

이 논문의 방법: 몇 가지 측정을 기반으로 청사진을 만드는 것과 같습니다. 청사진이 만들어지면 즉시 답을 읽어낼 수 있습니다.
결과: 이 논문은 그들의 방법이 무작위 추측 방법보다 훨씬 빠르게 수렴 (정확해짐) 한다고 보여줍니다. 신뢰할 수 있는 답을 얻기 위해 필요한 "맛보기 테스트"(샘플) 가 더 적습니다.

그들이 발견한 것 (결과)

연구자들은 실제 데이터 세트 (타이타닉 생존 예측, 와인 품질, 유방암 검출 등) 에서 이를 테스트했습니다.

속도 대 정확도: 그들은 상호작용이 3 명 그룹 (3-Additive) 에서 일어난다고 가정하는 것이 보통 "적정선"임을 발견했습니다. 이는 정확하기에는 충분히 복잡하면서도 빠르기에는 충분히 단순했습니다.
경쟁자 제압: 많은 테스트에서 그들의 방법 (SVAkADD) 은 동일한 계산 시간이나 데이터 샘플을 제공받을 때 현재 최상위 방법들 (KernelSHAP 등) 보다 더 정확했습니다.
특별한 규칙 불필요: 이 방법은 어떤 유형의 게임이나 AI 모델에서도 작동합니다. 데이터가 의료 기록, 주가, 스포츠 통계인지에 상관없이 작동합니다.

한 문장으로 요약

이 논문은 지나치게 복잡한 그룹 상호작용을 무시하는 단순화된 "팀워크 모델"을 구축함으로써 AI 특성 간에 공평하게 기여도를 나누는 새로운 방법을 제시하며, 모든 가능성을 확인하지 않고도 빠르고 정확하게 공평한 몫을 계산할 수 있게 합니다.

기술적 요약: k-Additive 게임을 기반으로 한 Shapley 값 근사

문제 제기

Shapley 값은 공정한 분할 문제의 표준 해법으로, 설명 가능한 AI(XAI) 에서 모델 성능에 대한 개별 특징이나 데이터 포인트의 기여도를 정량화하는 데 널리 채택되고 있습니다. 그러나 정확한 계산을 위해서는 $n$ 명의 플레이어에 대한 모든 $2^n$ 개의 가능한 연합 (coalition) 을 평가해야 하므로, 계산 복잡도가 지수적으로 증가합니다. 이로 인해 중간 규모의 특징을 가진 모델이나 복잡하고 자원을 많이 소모하는 모델을 평가할 때 정확한 계산은 불가능합니다. 따라서 근사 방법이 필요하지만, 기존 접근법들은 계산 효율성과 결과 중요도 점수의 정확도 사이의 균형을 맞추는 데 종종 어려움을 겪습니다.

방법론: SVAkADD

저자들은 구조화된 k-Additive 서브rogate 게임을 표본 추출된 연합 가치의 부분 집합에 적합시켜 Shapley 값을 근사하는 새로운 방법인 SVAkADD(k-Additivity 하의 Shapley 값 근사) 를 제안합니다.

핵심 개념: k-Additivity

SVAkADD 는 마진 기여도의 몬테카를로 표본 추출을 통해 Shapley 값을 직접 추정하는 대신, 기본 게임이 k-Additive 게임으로 근사될 수 있다고 가정합니다. 이러한 게임에서 크기 $k$ 를 초과하는 연합에 대한 상호작용 지수 (Shapley 상호작용) 는 0 이라고 가정합니다.

표현: 서브rogate 게임의 가치 함수 $\nu_k$ 는 모든 연합 $B$ 에 대한 Shapley 상호작용 지수 $I(B)$ 의 선형 변환으로 표현되며, 여기서 $|B| \leq k$ 입니다.
매개변수 축소: 이 가정은 게임을 정의하는 데 필요한 매개변수의 수를 $2^n$ 에서 다항식 수준 (예: $O(n^k)$ ) 으로 획기적으로 줄여 최적화를 실행 가능하게 만듭니다.

최적화 프레임워크

이 방법은 근사를 제약 조건이 있는 가중 최소 제곱 문제로 공식화합니다:

목적 함수: 원래 게임에서 관찰된 연합 가치 $\nu(A)$ 와 k-Additive 서브rogate 가 예측한 가치 $\nu_k(A)$ 사이의 가중치 제곱 오차를 최소화합니다.
제약 조건: 최적화는 효율성 공리를 강제하여, 서브rogate 의 Shapley 값의 합이 대연합의 가치와 공집합의 가치 차이 ( $\nu(N) - \nu(\emptyset)$ ) 와 같아지도록 보장합니다.
가중치: 저자들은 최소 제곱 문제에 대한 특정 가중치 $w^*_A = \binom{n-2}{|A|-1}^{-1}$ 를 분석적으로 유도했습니다. 모든 연합이 관찰되었다면, 이 특정 최적화를 해결하면 원래 게임이 진정으로 k-Additive 여부와 상관없이 정확한 Shapley 값이 도출됨을 증명했습니다.

알고리즘

SVAkADD 알고리즘은 다음과 같이 진행됩니다:

표본 추출: 결정론적으로 공집합 $\emptyset$ 과 대연합 $N$ 을 평가합니다. 그런 다음 유도된 가중치 $w^*_A$ 에 비례하는 확률 분포를 기반으로 멱집합 (공집합과 대연합 제외) 에서 $T-2$ 개의 추가 연합을 표본 추출합니다.
적합 (Fitting): 표본 추출된 데이터를 사용하여 제약 조건이 있는 가중 최소 제곱 문제를 풀어 $|B| \leq k$ 에 대한 상호작용 지수 $I(B)$ 를 추정합니다.
추출: 서브rogate 게임의 Shapley 값은 즉시 단일원 상호작용 지수 ( $I(\{i\})$ ) 로 얻어지며, 이는 원래 게임에 대한 추정치로 사용됩니다.

주요 기여

새로운 근사 방법: 직접적인 마진 기여도 표본 추출에 대한 구조화된 대안을 제공하는, 표본 추출된 데이터에 k-Additive 서브rogate 게임을 적합시키는 SVAkADD 의 도입.
이론적 건전성: $k=1, 2, 3$ 인 경우, 제안된 가중 최소 제곱 최적화가 모든 연합 집합이 관찰되었을 때 정확한 Shapley 값을 산출한다는 분석적 증명. 이는 k-Additivity 가 게임 구조에 대한 제한적인 가정이 아니라 근사를 위한 도구임을 입증합니다.
모델 및 도메인 중립성: 이 방법은 가치 함수의 특정 구조적 속성을 요구하지 않으므로, 기계 학습의 지역 및 글로벌 특징 설명을 포함한 모든 협력 게임에 적용 가능합니다.
실증적 평가: 다양한 데이터셋과 설명 유형 (글로벌, 지역, 비지도) 에 걸쳐 최첨단 베이스라인 (KernelSHAP, Stratified SVARM, Stratified sampling) 에 대한 포괄적인 비교.

실험 결과

저자들은 9 개에서 14 개까지의 특징을 가진 데이터셋에서 글로벌, 지역, 비지도 작업에 대해 SVAkADD 를 평가했습니다.

수렴: 이 방법은 경쟁력 있는 성능을 보여줍니다. 매우 낮은 표본 예산에서는 일부 베이스라인보다 오차가 높을 수 있지만, 예산이 증가함에 따라 특히 Adult 및 ImageNet 데이터셋의 지역 귀속 작업에서 정확한 Shapley 값으로 더 빠르게 수렴합니다.
$k$ 의 선택: 실험은 유연성과 수렴 속도 간의 트레이드오프를 강조합니다.
- 낮은 $k$ (1 또는 2) 는 복잡한 특징 상호작용을 모델링하기에 충분한 유연성이 부족하여 종종 느리게 수렴합니다.
- 높은 $k$ (3 또는 4) 는 일반적으로 훨씬 빠르게 수렴하며, 몇 개의 표본 이후에는 저차 모델보다 우수한 성능을 발휘합니다.
- 저자들은 오차 감소와 필요한 매개변수 수 사이의 좋은 균형을 제공하는 $k=3$ 을 선호하는 기본값으로 제안합니다.
비교: SVAkADD 는 일관되게 KernelSHAP 및 Stratified SVARM 과 경쟁하거나 능가하며, 특히 중간 규모의 표본 예산으로 고정밀도가 필요한 시나리오에서 두드러집니다.

중요성과 주장

이 논문은 SVAkADD 가 Shapley 값 근사를 위한 이론적으로 근거 있고 실용적으로 효과적인 접근법을 제공한다고 주장합니다. k-Additive 게임의 구조를 활용함으로써, 이 방법은 추정 문제를 다항식 시간 최적화로 변환하며 특정 가중치 조건 하에서 정확한 복원을 보장합니다.

저자들은 그들의 접근 방식이 모델 중립적이고 도메인 독립적이며, 모든 협력 게임 형식을 처리할 수 있음을 강조합니다. 그들은 단일 근사 방법이 모든 시나리오 (데이터셋, 작업, 예산에 따라 다름) 에서 우세하지는 않지만, SVAkADD 가 Shapley 상호작용의 이론적 속성을 활용하여 높은 정확도를 달성하는 견고한 대안을 제공한다고 결론지었습니다. 또한 이 논문은 $k \geq 2$ 일 때 이 방법이 개별 특징 중요도 이상의 추가적인 해석 가능성 (중복성 또는 보완성) 을 제공하는 상호작용 효과에 대한 추정치를 자연스럽게 제공한다고 지적합니다.