📊 statistics

An Odd Estimator for Shapley Values

이 논문은 쌍 샘플링(paired sampling)이 집합 함수의 무관한 짝수 성분을 걸러낸다는 것을 이론적으로 증명함으로써, 홀수 부분 공간(odd subspace)에 대해서만 효율적인 다항 회귀를 가능하게 하여 최첨단 정확도를 달성하는 새로운 샤플리 값 추정치인 OddSHAP을 소개한다.

원저자: Fabian Fumagalli, Landon Butler, Justin Singh Kang, Kannan Ramchandran, R. Teal Witter

게시일 2026-06-01

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Fabian Fumagalli, Landon Butler, Justin Singh Kang, Kannan Ramchandran, R. Teal Witter

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

당신이 자율주행 자동차나 의료 진단 도구와 같이 복잡한 기계를 가지고 있고, 그 기계가 어떤 결정을 내렸다고 가정해 봅시다. 당신은 알고 싶습니다: 입력값의 어떤 구체적인 부분(특징)들이 그 결정에 책임을 지고 있는가?

머신러닝의 세계에서 '샤플리 값(Shapley value)'은 이 질문에 답하기 위해 사용되는 황금 표준 수학 도구입니다. 이는 결정에 대한 '공로'를 모든 입력 특징들 사이에 공정하게 배분합니다. 하지만 샤플리의 값을 정확하게 계산하는 것은 마치 해변의 모든 모래알 하나하나가 전체 무게에 얼마나 기여했는지 확인하기 위해 모래알을 세는 것과 같습니다. 수학적으로는 가능하지만, 너무 많은 조합을 확인해야 하기 때문에 복잡한 문제에서는 계산적으로 불가능합니다.

이 논문은 이 값들을 추정하는 더 똑똑하고 새로운 방법인 OddSHAP을 소개합니다. 여기서는 이를 쉬운 비유를 통해 설명합니다.

1. 문제점: "너무 많은 조합"의 함정

특정 특징이 얼마나 중요한지 파악하려면, 보통 모든 가능한 특징의 조합(특징을 켜거나 끄는 방식)을 테스트해야 합니다.

기존 방식: 당신이 재료의 조합을 통해 수프의 맛을 추측하려고 한다고 상상해 보세요. 만약 재료가 100개라면, 그 조합의 수는 천문학적입니다. 그 모든 것을 다 맛볼 수는 없습니다.
현재 가장 좋은 방식: 과학자들은 '쌍 샘플링(paired sampling)'이라는 기술을 사용합니다. 무작위로 만든 수프 한 그릇을 맛보는 대신, 그 수프와 정확히 반대되는 것(추가된 것은 빼고, 빠진 것은 채운 것)을 함께 맛봅니다. 이는 노이즈를 상쇄하는 데 도움이 되지만, 지금까지는 왜 이 방법이 그렇게 잘 작동하는지 아무도 알지 못했습니다.

2. 거대한 발견: "홀수(Odd)"의 비밀

저자들은 근본적인 수학적 규칙을 발견했습니다: 샤플리 값은 이야기의 "홀수(odd)" 부분에만 관심을 가집니다.

가치 함수(기계의 로직)를 하나의 노래라고 생각해 봅시다. 이 노래에는 두 가지 유형의 음표가 있습니다.

짝수 음표(Even Notes): 이들은 대칭적입니다. 노래를 뒤집어도 똑같이 들립니다. 수학적으로 말하면, 이들은 샤플리 값을 계산할 때 서로 상쇄되는 패턴들입니다. 이들은 이 특정 계산에 있어서 "무관한 노이즈"입니다.
홀수 음표(Odd Notes): 이들은 비대칭적입니다. 뒤집으면 변합니다. 이것들이 실제로 샤플리 값에 영향을 주는 유일한 음표들입니다.

비유: 당신이 저울 위에 서 있는 특정 사람의 무게를 측정하려는데, 저울이 그 사람을 둘러싼 거대하고 대칭적인 안개 구름의 무게도 함께 재고 있다고 상상해 보세요. 안개는 무겁지만, 완벽하게 균형 잡혀(even) 있기 때문에 왼쪽이나 오른쪽 중 어느 한쪽으로 더 치우치게 만들지 않습니다. "OddSHAP"의 통찰은 우리가 그냥 안개를 무시하고 오직 사람에게만 집중하면 된다는 사실을 깨닫는 것입니다.

3. 해결책: OddSHAP

저자들은 이 "홀수 대 짝수"의 통찰을 사용하여 시간을 절약하고 정확도를 높이는 새로운 추정기인 OddSHAP을 구축했습니다.

작동 원리: 전체 노래(전체 기계 로직)를 배우려고 노력하는 대신, OddSHAP은 영리한 샘플링 기술(쌍 샘플링)을 사용하여 "짝수" 음표를 자동으로 걸러냅니다. 그런 다음 오직 "홀수" 음표만을 사용하여 모델을 구축합니다.
대리 모델(Proxy) 기법: 모든 홀수 음표를 일일이 확인하지 않고 가장 중요한 홀수 음표를 찾기 위해, OddSHAP은 정찰병 역할을 하는 "대리 모델"(빠르고 단순한 결정 트리)을 사용합니다. 이 정찰병은 빠르게 영향력이 큰 몇몇 상호작용(가장 큰 소리를 내는 "홀수" 음표)을 식별하고 나머지는 무시합니다.
결과: 이는 훨씬 작은 수학 문제를 푸는 것과 같습니다. 마치 퍼즐 조각의 고유한 모양을 가진 조각들만 보고, 그림을 맞추는 데 도움이 되지 않는 수천 개의 동일한 사각형 조각들은 무시하며 퍼즐을 푸는 것과 같습니다.

4. 왜 더 나은가?

이 논문은 다양한 데이터셋(집값 예측, 암 진단, 텍text 분석 등)을 사용하여 이 방법을 기존의 최고 수준의 방법들과 비교 테스트했습니다.

정확도: 충분한 데이터(큰 "예산")가 주어졌을 때, OddSHAP은 사용 가능한 방법 중 가장 정확합니다. 특히 이미지 인식 등에 사용되는 복잡한 딥러닝 모델에 대해 이전의 최고 방법들을 능가합니다.
효율성: "조합 폭발"을 피합니다. 다른 방법들이 너무 많은 조합을 계산하느라 쩔쩔매는 동안, OddSHAP은 관련 있는 조합으로 바로 직행합니다.
미스터리의 해명: 또한 이 논문은 왜 기존의 "쌍 샘플링" 기술이 그렇게 잘 작동했는지 마침내 설명합니다. 쌍 샘-플링을 하는 것이 의도치 않게 OddSHAP이 의도적으로 수행하는 것과 똑같은 일을 하고 있었음이 밝혀졌습니다. 즉, 수학적으로 "짝수" 노이즈를 상쇄하여 유용한 "홀수" 신호만을 남기는 작업을 수행했던 것입니다.

요요약

OddSHAP은 AI의 결정을 설명하기 위한 새로운 도구입니다. 이 도구는 어떤 결정이 내려졌는지 이해하기 위해 모든 가능한 시나리오를 분석할 필요가 없다는 점을 깨달았습니다. 오직 결과에 실제로 영향을 미치는 특정한 비대칭적 패턴만을 분석하면 됩니다. 대칭적인 "노이즈"를 무시함으로써, 이전보다 더 빠르고 정확하게 답을 계산합니다.

제한 사항에 대한 참고: 논문은 이 방법이 복잡한 딥러닝 모델에는 매우 뛰어나지만, "노이즈"가 자연적으로 매우 낮은 단순한 트리 기반 모델(표준 결정 트리 등)을 다룰 때는 일부 오래된 경직된 방법들보다 효율성이 약간 떨어질 수 있다고 언급합니다. 그러나 AI가 가장 신비로운 영역인 광범하고 복잡한 문제들에 있어서, OddSHAP은 새로운 최첨단(state-of-the-art) 기술입니다.

기술 요약: 샤플리 값을 위한 기묘한 추정량 (An Odd Estimator for Shapley Values)

문제 정의

샤플리 값(Shapley value)은 특징 중요도, 데이터 가치 평가, 인과 추론 등에 사용되는 머신러닝의 표준적인 기여도 산출 프레임워크이다. 그러나 정확한 계산은 평가에 필요한 조합의 수가 지수적( $2^d$ )으로 증가하기 때문에 일반적으로 다루기 불가능하다(intractable). 근사 방법들이 존재하지만, 가장 효과적인 추정량들은 종종 "쌍 샘플링(paired sampling)"(연합 $S$ 와 그 보집합 $S^c$ 를 함께 샘플링하는 방식)에 의존한다. 이는 경험적으로 정확도를 개선하는 휴리스틱이지만, 특히 고차 상호작용(higher-order interactions)과 관련하여 왜 이것이 작동하는지에 대한 엄밀한 이론적 근거가 부족하다. 또한, 기존의 고차 다항 회귀 방법들(예: PolySHAP)은 다항식 기저의 크기에 따라 계산 비용이 이차적으로 증가하는 확장성 병목 현상에 직면해 있어, 고차원 설정에서의 적용이 제한적이다.

방법론

저자들은 샤플리 값의 근본적인 구조적 특성인, 가치 함수 $f$ 의 **홀수 성분(odd component)**에만 의존한다는 점을 활용하는 새로운 추정량인 OddSHAP을 제안한다.

이론적 기초

홀-짝 분해 (Odd-Even Decomposition): 임의의 집합 함수 $f$ 는 홀수 성분( $f_{odd}$ )과 짝수 성분( $f_{even}$ )으로 유일하게 분해될 수 있다. 여기서 $f_{odd}(S) = -f_{odd}(S^c)$ 이고 $f_{even}(S) = f_{even}(S^c)$ 이다.
샤플리 값의 성질: 저자들은 모든 플레이어 $i$ 에 대해 $\phi_i(f) = \phi_i(f_{odd})$ 임을 증명한다. 즉, 짝수 성분은 샤플리 값에 기여하지 않는다.
쌍 샘플링의 메커즘: 본 논문은 쌍 샘플링에 대한 최초의 일반적인 이론적 정당성을 제공한다. 대칭적인 가중치를 가진 쌍 $(S, S^c)$ 를 샘플링함으로써, 가중 최소 제곱 회귀 문제는 홀수 성분과 짝수 성분에 대한 독립적인 최적화 문제로 직교화(orthogonalize)(디커플링)된다. 짝수 성분은 무관하므로, 쌍 샘플링은 샤플리 값에 필요한 신호를 효과적으로 격리한다. 이는 차수가 $k$ (홀수 $k$ )인 적합(fit)이 차수 $k+1$ 인 적합과 동일하다는 추측을 해결한다.

알고리즘 설계: OddSHAP

모든 고차 항을 적합시키는 데 따르는 조합 폭발을 피하면서 이 통찰을 활용하기 위해, OddSHAP은 단일성 기저(unanimity basis) 대신 **푸리에 기저(Fourier basis)**에서 작동한다.

푸리에 기저의 장점: 푸리에 기저에서 기저 함수 $\chi_T$ 는 카디널리티 $|T|$ 가 홀수일 때만 홀수이다. 이는 단일성 기저와 달리 홀수 항과 짝수 항의 깔끔한 분리를 가능하게 한다.
2단계 프로세스:
1. 상호작용 스크리닝 (Interaction Screening): 샘플링된 연합들에 대해 그래디언트 부스팅 트리(GBT) 프록시 모델을 적합시킨다. ProxySPEX와 같은 방법을 사용하여, 알고리즘은 희소한(sparse) 고영향력 홀수 차수 푸리에 계수를 추출한다. 이를 통해 가능한 모든 상호작용을 적합시켜야 하는 부담을 피한다.
2. 홀수 회귀 (Odd Regression): 빈 집합과 전체 집합에 대한 가치 함수와 일치하도록 제약 조건을 두면서, 선택된 홀수 차수 푸리에 항(및 선형 항)에 대해서만 가중 최소 제곱 회귀를 수행한다.
효율성: 회귀를 홀수 부분 공간으로 제한하고 프록시를 사용하여 항을 선택함으로써, OddSHAP은 고정 차수 다항 방법의 $O(d^k)$ 스케일링을 우회하여 샘플링 예산에 대한 다항 시간 복잡도를 달ら한다.

주요 기여

쌍 샘플링의 이론적 통합: 본 논문은 쌍 샘플링이 회귀 목적 함수를 홀수 및 짝수 성분으로 암묵적으로 디커플링한다는 것을 증명함으로써, 낮은 차수의 상호작용에 국한되었던 기존의 발견을 넘어 그 경험적 성공에 대한 엄밀한 이론적 메커니즘을 제공한다.
OddSHAP 추정량: 희소한 선택된 홀수 차수 푸리에 기저 함수(및 선형 항)만을 사용하여 다항 회귀를 수행하는 일관된 추정량이다. 이는 무관한 짝수 성분을 필터링하고 프록시 모델을 통해 고영향력 상호작용을 식별한다.
최첨단 성능 (State-of-the-Art Performance): 광범에한 벤치마크를 통해 OddSHAP이 샘플링 예산 $m$ 이 상호작용을 탐지하기에 충분할 때( $m > \eta \cdot d$ ), 기존 방법들(RegressionMSR, LeverageSHAP, PolySHAP 포함)보다 우수한 추정 정확도를 달성함을 입증하였다.

실험 결과

저자들은 $d=14$ (DistilBERT)부터 $d=101$ (Crime 데이터셋)까지 딥러닝(이미지 및 텍텍스트)과 정형 데이터 영역을 아우르는 8개의 가치 함수에 대해 OddSHAP을 평가하였다.

정확도: OddSHAP은 특히 상호작용을 탐지하기 위한 샘플링 예산 $m$ 이 충분할 때( $m > \eta \cdot d$ ), 낮은 평균 제곱 오차(MSE)와 최고의 평균 순위를 일관되게 기록하며 가장 우수한 성능을 보였다.
FFD와의 비교: OddSHAP은 고차 상호작용이 중요한 딥러닝 아키텍처(ViT, DistilBERT)에서 FFD-RD(Fixed-Budget Fractional Factorial Design)보다 뛰어난 성능을 보였다. 반대로, 고차 상호작용이 빠르게 감소하는 트리 기반 정형 데이터셋에서는 FFD-RD가 약간 더 나은 성능을 보여, 도메인별 트레이드오프를 입증했다.
절제 연구 (Ablation Studies):
- 쌍(Paired) vs 비쌍(Non-Paired): 쌍 샘플링이 비쌍 샘플링보다 일관되게 우수한 성능을 보였다.
- 홀수(Odd) vs 모든 상호작용(All Interactions): 쌍 샘플링 하에서 짝수 상호작용을 포함하는 것은 이득이 없었으며, 수학적으로 상쇄되는 항들이 상호작용 예산을 소모함으로써 오히려 성능을 저하시켰다.
- 희소성 (Sparsity): 홀수 상호작용의 수를 적절히 포함(회귀 변수 인자 $\eta$ 에 의해 제어)하면 선형 베이스라인에 비해 오차가 크게 감소했으나, 너무 많은 상호작용을 포함할 경우 과적합이 발생했다.

의의 및 주장

본 논문은 OddSHAP이 다양한 상호작용 구조에 걸쳐 견고하게 적응하는 **유연한 예산 프레임워크(flexible-budget framework)**를 제공한다고 주장한다. 이 논문의 주요 의의는 다음과 같다:

열린 추측의 해결: 단순한 경험적 관찰을 넘어 구조적 증명을 통해 왜 쌍 샘플링이 작동하는지에 대한 근본적인 이론적 메커니즘을 제공한다.
확장성: 모델을 홀수 부분 공간으로 제한함으로써, 과도한 조합 비용을 발생시키지 않으면서도 고차 근사의 표현력을 유지한다.
강건성: 고차 상호작용이 무시할 수 없는 수준인 복잡한 딥러닝 도메인에서도 효과적으로 작동하는 동시에, 희소한 정형 도메인에서도 경쟁력을 유지한다.

저자들은 알고리즘의 실행 시간이 선택된 상호작용에 대한 이차 회귀 비용으로 인해 예산에 따라 삼차적으로 스케일링된다는 점과, 쌍 샘플링이 독립적인 샘플의 유효 수를 줄여 분산을 키울 수 있다는 점 등 한계점을 언급하였다. 그러나 그들은 이 방법이 모델 불가지론적(model-agnostic) 설정에서 샤플리 값 추정을 위한 최첨단 접근법임을 결론지었다.