A Polynomial-Time Axiomatic Alternative to SHAP for Feature Attribution

이 논문은 SHAP 의 계산 복잡도 문제를 해결하기 위해 협력 게임 이론을 기반으로 효율성과 null-player 속성을 만족하는 다항 시간 폐형식 속성 할당 규칙인 ESENSC_rev2 를 제안하고, 이를 공리적으로 특징화하여 고차원 설명 가능성 환경에서 SHAP 을 대체할 수 있는 실용적 대안을 제시합니다.

핵심

이 논문은 인공지능 (AI) 이 내린 결정을 설명할 때 가장 많이 쓰이는 'SHAP'이라는 도구의 대안을 제안합니다. SHAP 은 매우 정확하지만, 데이터의 특징 (Feature) 이 많아질수록 계산 시간이 기하급수적으로 늘어나서 실제로 쓰기 어려운 단점이 있습니다.

이 논문은 **"SHAP 과 거의 똑같은 정확도를 내면서, 계산 속도는 훨씬 빠른 새로운 방법 (ESENSC_rev2)"**을 개발했다고 말합니다.

이 복잡한 내용을 일상적인 비유로 쉽게 설명해 드릴게요.

---

1. 배경: "누가 가장 공헌했을까?" (SHAP 의 문제)

상상해 보세요. 한 팀이 큰 프로젝트를 성공적으로 마쳤습니다. 이제 팀원들 (AI 의 특징들: 나이, 소득, 거주지 등) 이 그 성공에 얼마나 기여했는지 상금을 나누어 주려고 합니다.

• SHAP (기존 방법): 모든 가능한 팀 조합 (혼자 일했을 때, 둘이 일했을 때, 세 명이 일했을 때...) 을 하나하나 시뮬레이션해 보며 "누가 없으면 성과가 얼마나 떨어졌는지"를 정밀하게 계산합니다.
  • 문제점: 팀원 수가 10 명이면 조합이 1,024 가지, 20 명이면 100 만 가지가 넘습니다. 특징이 512 개라면? 우주 나이만큼의 시간이 걸려도 계산을 끝내지 못합니다. 너무 느립니다.

2. 새로운 해결책: "빠르고 똑똑한 상금 나누기" (ESENSC_rev2)

저자들은 "완벽한 시뮬레이션 대신, 공평한 원칙을 따르는 빠른 계산법"을 고안했습니다.

비유: "초보자의 기여 + 팀장의 기여"

이 새로운 방법은 두 가지 간단한 규칙을 섞어서 상금을 나눕니다.

1. 초보자의 기여 (ES): "네가 혼자서 할 수 있었던 일"을 기준으로 상금을 줍니다.
2. 팀장의 기여 (ENSC): "네가 팀에서 빠졌을 때 팀이 얼마나 손해를 봤는지"를 기준으로 상금을 줍니다.

이 두 가지를 50 대 50 으로 섞으면 대략적인 SHAP 값과 비슷해집니다. 하지만 여기서 한 가지 큰 문제가 있었습니다.

문제: "일도 안 한 사람도 돈을 받는다?"

기존의 빠른 방법들은 "일도 안 한 사람 (Null Player)"에게도 나머지 상금을 골고루 나눠주느라, 실제로는 기여도가 0 인 사람에게도 돈을 줘버리는 경우가 있었습니다.

• 예시: "이 사람은 아무런 영향을 주지 않았는데, 나머지 팀원들이 나눠먹다가 남은 돈을 이 사람에게도 줘버렸다." -> 이건 AI 설명에서는 말이 안 됩니다. (영향이 없는 특징은 점수 0 이어야 합니다.)

해결책: "ESENSC_rev2" (수정된 빠른 방법)

저자들은 이 문제를 해결하기 위해 **"영향이 없는 사람은 아예 상금 나누기에서 제외한다"**는 규칙을 추가했습니다.

• 결과: SHAP 과 거의 똑같은 정확도를 내면서도, 계산은 수천 배에서 수만 배 더 빠릅니다. 특징이 512 개가 되어도 순식간에 계산이 끝납니다.

3. 실험 결과: "빠르면서도 정확한가?"

저자들은 실제 데이터 (캘리포니아 주택 가격 예측 등) 와 복잡한 AI 모델 (신경망, XGBoost) 로 실험을 했습니다.

• 정확도: SHAP 과 비교했을 때 오차가 매우 작았습니다. (거의 SHAP 과 똑같다고 봐도 무방함)
• 속도: 특징이 늘어날수록 SHAP 은 계산이 불가능해지지만, 이 새로운 방법은 선형적으로만 느려져서 항상 빠르게 작동했습니다.
• 비교: 기존에 SHAP 을 빠르게 계산하려는 다른 방법들 (샘플링 기반) 보다 더 정확하면서도, 파라미터를 조절할 필요 없이 바로 계산할 수 있습니다.

4. 이론적 근거: "왜 이 방법이 맞을까?"

단순히 실험으로만 좋은 게 아니라, 수학적으로도 "이 방법이 유일하게 옳다"는 것을 증명했습니다.

• SHAP 은 "완벽한 공정성 (모든 조합을 고려)"을 요구합니다.
• 이 새로운 방법은 **"효율성 (빠름)"**과 **"영향 없는 사람은 0 점 (Null-player)"**이라는 두 가지 핵심 원칙을 지키면서, SHAP 과는 조금 다른 "제한된 공정성"을 따릅니다.
• 즉, **"완벽한 정답을 구하는 데 100 년 걸릴 바엔, 99.9% 정확한 답을 1 초 만에 구하는 게 현실적이다"**라는 철학을 수학적으로 증명해 보인 것입니다.

5. 결론: 왜 이 논문이 중요한가?

지금까지 AI 가 왜 그런 결정을 내렸는지 설명하려면 (XAI), SHAP 이 거의 유일한 표준이었습니다. 하지만 데이터가 커지면 SHAP 은 무너집니다.

이 논문은 **"SHAP 을 대체할 수 있는, 이론적으로도 탄탄하고 실제로도 매우 빠른 새로운 도구"**를 제시했습니다. 앞으로 AI 모델이 더 복잡해지고 데이터가 더 많아져도, 이 방법을 쓰면 빠르고 정확하게 "왜 AI 가 그렇게 판단했는지"를 설명할 수 있게 됩니다.

한 줄 요약:

"완벽하지만 느린 SHAP 대신, 거의 똑같이 정확하면서 천둥벌거숭이처럼 빠른 새로운 설명 방법을 개발했습니다."

기술 요약

논문 요약: SHAP 에 대한 다항 시간 (Polynomial-Time) 공리적 대안

1. 연구 배경 및 문제 제기 (Problem)

• SHAP 의 한계: 설명 가능한 인공지능 (XAI) 분야에서 가장 널리 사용되는 방법인 SHAP (Shapley Additive exPlanations) 은 협력 게임 이론의 샤플리 값 (Shapley value) 에 기반하고 있습니다. 그러나 정확한 샤플리 값 계산은 특성 (Feature) 의 수 $n$에 대해 지수적 복잡도 ($O(2^n)$) 를 가지므로, 고차원 데이터에서는 계산이 불가능하거나 매우 비효율적입니다.
• 기존 근사법의 문제: 기존에 개발된 SHAP 근사 알고리즘 (Permutation SHAP, Kernel SHAP 등) 은 계산 비용을 줄이지만, 정확도가 불안정할 수 있으며 하이퍼파라미터 튜닝이 필요하고, SHAP 이 지향하는 이론적 속성 (공리) 을 완전히 만족하지 못할 수 있습니다.
• XAI-TU 게임의 특수성: 기존 협력 게임 이론과 달리, XAI 환경에서는 특성들의 조합에 따라 coalition value(결합 가치) 가 양수와 음수가 공존할 수 있으며, 이는 전통적인 비례 분배 규칙이 직관적이지 않은 결과를 초래할 수 있음을 의미합니다.

2. 방법론 (Methodology)

저자들은 설명 가능한 AI 문제를 XAI-TU 게임 (Explainable-AI Transferable Utility Game) 으로 공식화하고, 샤플리 값 대신 계산 효율성이 높은 기존 게임 이론 해법들을 분석하여 새로운 가법적 특성 귀속 (Additive Feature Attribution, AFA) 규칙을 제안합니다.

• XAI-TU 게임 정의:

  • 플레이어: 특성 (Features)
  • 특성 함수 $v(S)$: 특성 집합 $S$가 알려진 상태에서의 모델 예측 기대값 (개입적 접근, $E[f(x_S, X_{N\setminus S})]$).
  • 귀속 목표: 전체 예측값과 베이스라인 예측값 ($v(N) - v(\emptyset)$) 의 차이를 각 특성에 분배.

• 주요 제안 규칙 (ESENSC_rev2):

  • Equal Surplus (ES) 및 ENSC 기반: 기존에 저비용으로 알려진 'Equal Surplus (ES)'와 'Egalitarian Nonseparable Contribution (ENSC)'의 50-50 혼합 규칙을 기반으로 합니다.
  • Null-player Property 수정: 기존 ES-ENSC 혼합 규칙은 기여도가 없는 특성 (Null player) 에도 잔여 잉여를 균등 분배하여 0 이 아닌 값을 부여하는 문제가 있었습니다. 저자들은 이를 수정하여, 기여도가 없는 특성에는 0 을 할당하고, 잉여는 기여도가 있는 특성들 사이에서만 재분배되도록 ESENSC_rev2 규칙을 설계했습니다.
  • 수식적 특징: $O(n)$ 수준의 특성 함수 평가 횟수만 필요로 하여 다항 시간 ($O(n)$) 에 계산 가능합니다.

• 비례 분배 (Proportional Allocation, PA) 계열 분석:

  • PA 계열 규칙은 계산이 빠르지만, XAI-TU 게임에서 양/음의 가치가 공존할 때 순서 반전 문제 (Order-reversal problem) 가 발생할 수 있음을 규명했습니다. 즉, 기여도가 큰 특성이 오히려 작은 할당을 받는 비직관적 상황이 발생할 수 있어, 이 계열의 규칙은 SHAP 을 대체하기 어렵다고 결론지었습니다.

• 공리적 특성화 (Axiomatization):

  • 제안된 규칙 (ESENSC_rev2) 이 다음 공리들을 만족하는 유일한 해임을 증명했습니다.
    1. 효율성 (Efficiency): 전체 할당 합이 총 잉여와 일치.
    2. Null-player 속성: 기여도가 없는 특성은 0 할당.
    3. 제한된 차분 한계성 (Restricted Differential Marginality): 샤플리 값의 완전한 차분 한계성보다 약화된 조건.
    4. 중간 무의미 게임 속성 (Intermediate Inessential Game): 최적과 최악의 관점의 중간값을 취하는 공리.
    5. 계산 복잡도 감소 (Reduction in Computational Complexity): 2 개에서 $n-2$ 개 크기의 coalition 값 계산을 불필요하게 함.

3. 주요 결과 (Results)

캘리포니아 주택 데이터셋을 기반으로 신경망 (Neural Network) 과 XGBoost 모델을 사용하여 실험을 수행했습니다.

• 계산 효율성:

  • 제안된 ESENSC_rev2는 특성 수가 증가함에 따라 계산 시간이 선형적으로 증가하는 반면, 정확한 SHAP 은 지수적으로 증가합니다.
  • 기존 SHAP 근사법 (Permutation SHAP, Kernel SHAP) 보다 계산 시간이 현저히 짧으며, 하이퍼파라미터 튜닝이 필요 없습니다.
  • 특성 수가 512 개로 늘어나는 고차원 환경에서도 여전히 계산이 가능했습니다.

• 정확도 (SHAP 과의 편차):

  • ESENSC_rev2는 정확한 SHAP 값과 매우 유사한 결과를 보여주며, 기존 근사법들 (특히 Kernel SHAP) 보다 SHAP 과의 편차가 작았습니다.
  • PA 계열 규칙 (PARPA 등) 은 계산은 빠르지만, SHAP 과의 편차가 크고 불안정하여 고차원 환경에서는 적합하지 않았습니다.

• 모델 일반성: 신경망과 XGBoost 모델 모두에서 일관된 성능 향상을 보였습니다.

4. 주요 기여 (Key Contributions)

1. XAI-TU 게임의 공식화: 설명 가능한 AI 문제를 전통적 협력 게임과 구별되는 구조적 특성 (양/음의 가치 공존 등) 을 가진 XAI-TU 게임으로 체계화했습니다.
2. 계산 효율적이고 이론적으로 타당한 AFA 개발: 샤플리 값의 지수적 복잡도 문제를 해결하면서 Null-player 속성을 만족하는 ESENSC_rev2 규칙을 제안했습니다.
3. 공리적 기반의 정당화: 제안된 규칙이 효율성, Null-player 속성, 그리고 계산 효율성을 반영하는 새로운 공리 집합에 의해 유일하게 결정됨을 증명했습니다. 이는 SHAP 을 근사하는 다항 시간 규칙에 대한 최초의 공리적 특성화입니다.
4. 실증적 검증: 다양한 모델과 고차원 데이터에서 제안된 방법이 SHAP 과 유사한 정확도를 유지하면서 계산 비용을 획기적으로 줄임을 입증했습니다.

5. 의의 및 결론 (Significance)

• 이론과 실용의 균형: 이 연구는 SHAP 의 강력한 이론적 기반 (공리) 을 유지하면서도, 실제 고차원 데이터 적용에 필요한 계산 효율성을 동시에 달성할 수 있는 방법을 제시했습니다.
• 실무 적용 가능성: 튜닝 파라미터가 필요 없고 계산 비용이 낮아 대규모 모델이나 실시간 설명이 필요한 환경에서 SHAP 기반 방법의 실용적인 대안이 될 수 있습니다.
• 향후 연구 방향: 비례 분배 규칙의 불안정성에 대한 추가 연구와, 다른 데이터 모달리티 (이미지, 텍스트 등) 로의 확장 가능성을 제시했습니다.

결론적으로, 이 논문은 ESENSC_rev2가 SHAP 을 대체할 수 있는 이론적으로 정립되고 계산적으로 효율적인 차세대 특성 귀속 방법임을 입증했습니다.