Shapley value는 협력 게임에서 참여자의 기여도를 계산한다

요약

• 게임이론에서 나온 개념으로, 협력 게임에서 참가자들 간의 공정한 이익 분배 방식을 정의
• feature 수가 늘어나면 계산량이 O(N²)까지 증가하므로 근사 방법이 필요

본문

Shapley Value

• 1953년 로이드 샤플리가 협력 게임 상황에서 참가자들 간의 공정한 이익 분배 방식을 정의하기 위해 제안했음
• 협력 게임에서는 여러 참가자들이 힘을 합쳐 어떤 가치를 창출함, 결과로 나온 전체 가치를 각 참가자에게 어떻게 나누어줄지 정하는 문제
  • 여러 기업이 공동 투자해 수익
  • 팀 프로젝트에서 결과물이 나온다.
• 게임에 참여한 모든 플레이어가 기여한 감소량을 모든 적용 순서의 평균으로 계산하는 방법
• 예를 들어 A, B, C 가 있고 A, B, C를 배치하는 모든 경우의 6가지에 대해 각 단계에서 증감량을 평균내어 각 플레이어의 할당량을 정한다.

근사 기여도

• feature 수가 늘어날 수록 계산량이 O(N ^ 2)까지 늘어남
• 이를 해결하기 위해 3가지 근사적으로 shapley value를 구하는 방식이 있음
  1. 순열 샘플링 (Permutaion sampling)
     • 피처들의 순서를 랜덤하게 섞고, 특정 피처가 포함/미포함에 따를 성능 차이를 계산함
     • 순열을 반복하면 shapley 값에 근사함
  2. 몬테카를로 추정 (Monte Carlo Approximation)
     • 전체 순열중 일부를 무작위로 뽑아 shapley 값을 추정함
  3. 특정 모델 구조 (TreeSharp)
     • 의사 결정 기반 모델에서 조합을 효율적으로 계산할 수 있는 수학적 방법(TreeSharp)이 존재함

참고