Local Shapley: Model-Induced Locality and Optimal Reuse in Data Valuation

Each language version is independently generated for its own context, not a direct translation.

이 논문은 **"데이터의 가치를 어떻게 공정하고 빠르게 평가할 것인가?"**라는 질문에 대한 혁신적인 해법을 제시합니다.

기존의 방법들은 너무 복잡하고 느려서 실제로 쓰기 힘들었는데, 이 연구는 **"모든 데이터가 모든 결과에 영향을 주는 것은 아니다"**라는 직관적인 사실을 발견하고, 이를 이용해 문제를 단순화했습니다.

이 내용을 일상적인 비유로 쉽게 설명해 드리겠습니다.

1. 문제 상황: "모든 사람을 다 불러와야 하는 파티" 🎉

데이터 과학자들은 AI 모델을 만들 때, "어떤 학습 데이터가 모델의 성능을 가장 잘 끌어올렸을까?"를 알고 싶어 합니다. 이를 **데이터 가치 평가 (Data Valuation)**라고 합니다.

기존 방식 (Shapley Value):
전통적인 방법 (Shapley 값) 은 모든 데이터 조합을 다 확인해야 합니다. 마치 100 명이 모인 파티에서 "누가 파티 분위기를 가장 잘 만들었는지"를 알기 위해, 100 명 중 1 명을 빼고 99 명만 모인 경우, 98 명만 모인 경우... 모든 조합을 일일이 시뮬레이션해야 하는 것과 같습니다.
- 문제점: 조합의 수가 기하급수적으로 늘어나서, 컴퓨터가 아무리 빨라도 계산하는 데 수백 년이 걸릴 수도 있습니다. (이론적으로 '불가능'에 가까운 계산량입니다.)

2. 핵심 발견: "모두가 중요한 게 아니다" (국소성) 🎯

이 논문은 현대 AI 모델들이 가진 중요한 특징을 발견했습니다.
"특정 질문 (테스트 데이터) 에 답할 때, 모든 학습 데이터가 다 관여하는 것은 아니다."

비유:
- K-NN(이웃 찾기) 모델: "이 사진이 고양이인가?"를 판단할 때, **가장 비슷한 5 개의 사진 (이웃)**만 보고 판단합니다. 나머지 9,995 장의 사진은 전혀 영향을 주지 않습니다.
- 의사결정나무: "이 사람이 대출을 받을 수 있을까?"를 판단할 때, 특정 규칙 (잎사귀) 에 걸린 몇몇 데이터만 중요합니다.
- 그래프 신경망 (GNN): "이 친구의 취미를 예측할 때"는 친구 관계망에서 바로 옆에 있는 친구들만 중요합니다.

즉, 모든 데이터를 다 볼 필요 없이, '영향을 미치는 작은 그룹 (Support Set)'만 보면 된다는 것입니다.

3. 해결책: "LSMR" (똑똑한 재사용 시스템) 🚀

저자들은 이 '작은 그룹'만 보는 아이디어를 바탕으로 LSMR이라는 새로운 알고리즘을 만들었습니다.

비유: "공통된 레시피 공유"
- 기존 방식: 각 사람마다 "내가 만든 요리가 얼마나 맛있었는지"를 확인하기 위해, 매번 새로운 재료를 사서 요리를 다시 해보는 바보 같은 짓을 반복합니다.
- LSMR 방식:
  1. 그룹화: "누가 어떤 재료 조합을 썼는지"를 먼저 파악합니다.
  2. 한 번만 요리하기: 같은 재료 조합 (예: 토마토 + 바질) 을 여러 사람이 필요로 하더라도, 한 번만 요리를 해서 그 맛을 기록합니다.
  3. 공유하기: 그 기록을 모든 사람이 공유합니다.
- 결과: 불필요한 요리 (모델 재학습) 를 99% 이상 줄이면서도, 정확한 맛 (데이터 가치) 을 알아냅니다.

4. LSMR-A: "대규모 파티를 위한 빠른 추정법" 🎲

만약 영향 받는 그룹이 너무 커서 모든 조합을 다 확인하기 힘들다면? LSMR-A라는 방법을 씁니다.

비유:
- 모든 조합을 다 확인하지 않고, 무작위로 몇 가지 조합을 뽑아서 맛을 본 뒤 전체적인 맛을 추정합니다.
- 하지만 기존 방식은 매번 새로운 재료를 사서 맛을 봤다면, LSMR-A 는 이미 맛본 재료를 다른 사람들과 공유해서 불필요한 쇼핑 (재학습) 을 아낍니다.
- 효과: 통계적으로 매우 정확하면서도, 계산 속도가 수천 배에서 수백만 배 빨라집니다.

5. 실험 결과: "기적 같은 속도 향상" ⚡

이론과 실험을 통해 다음과 같은 결과를 확인했습니다.

정확도 유지: 모든 데이터를 다 보는 것과 거의 똑같은 정확도로 데이터 가치를 평가합니다.
압도적인 속도: 기존 방법보다 수천 배에서 수백만 배 더 빠릅니다. (예: 1,000 만 번의 학습을 100 만 번으로 줄이는 게 아니라, 100 만 번을 1,000 번으로 줄임)
실용성: 이제 거대한 데이터를 가진 AI 모델에서도 "어떤 데이터가 중요한지"를 실시간에 가깝게 평가할 수 있게 되었습니다.

요약: 이 논문이 우리에게 주는 메시지

이 논문은 **"복잡한 문제를 해결할 때, 모든 것을 다 보려고 애쓰지 말고, 문제의 핵심 구조 (어떤 데이터가 실제로 영향을 미치는지) 를 먼저 파악하라"**고 말합니다.

마치 **"전 세계의 모든 책을 다 읽지 않아도, 필요한 책만 찾아 읽으면 지식을 얻을 수 있다"**는 것과 같습니다. 이 방식을 통해 데이터의 가치를 평가하는 일이 이제 현실적으로 가능해졌습니다.

Each language version is independently generated for its own context, not a direct translation.

1. 문제 정의 (Problem Definition)

데이터 가치 평가 (Data Valuation) 는 여러 당사자가 공동으로 모델 훈련에 참여할 때, 개별 데이터 항목이 모델 성능에 기여하는 정도를 공정하고 효율적으로 측정하는 문제입니다. Shapley 값은 협력 게임 이론에 기반하여 각 데이터 포인트의 한계 기여도를 계산하는 표준적인 방법론으로 널리 사용되지만, 다음과 같은 치명적인 한계가 있습니다.

계산 복잡도: Shapley 값의 정확한 계산은 모든 가능한 데이터 하위 집합 (coalition) 에 대한 재훈련을 필요로 하므로, 데이터 크기가 $N$ 일 때 $O(2^N)$ 의 지수적 복잡도를 가집니다. 이는 #P-hard 문제로 알려져 있어 대규모 데이터셋에서는 실용적이지 않습니다.
기존 방법의 한계: 기존 가속화 기법들 (몬테카를로 샘플링, 절단된 연합 평가, 영향 함수 기반 근사 등) 은 여전히 전역 (Global) 연합 공간을 가정합니다. 즉, 모든 훈련 데이터가 모든 테스트 인스턴스에 영향을 미칠 수 있다고 가정합니다.
현실과의 괴리: 현대 예측 모델 (KNN, 트리, GNN 등) 은 구조적 희소성 (Structural Sparsity) 을 가집니다. 즉, 특정 테스트 인스턴스에 대한 예측은 훈련 데이터의 소수 부분집합 (Support Set) 에만 의존합니다. 전역 공간을 고려하는 것은 불필요한 계산을 포함하는 과도하게 비관적인 가정입니다.

2. 방법론 (Methodology)

저자들은 모델 유도 국소성 (Model-Induced Locality) 개념을 도입하여 Shapley 계산 문제를 구조화된 데이터 처리 문제로 재정의했습니다.

2.1 모델 유도 국소성 및 Support Set

Support Set ( $N(t)$ ): 특정 테스트 인스턴스 $t$ 에 대한 예측을 결정하는 모델의 계산 경로 (예: KNN 의 이웃, 트리의 리프, GNN 의 수용 영역) 에 참여하는 훈련 데이터의 부분집합을 정의합니다.
국소 Shapley 값 (Local Shapley Value): 전체 데이터셋 $D$ $D$ 대신 $N(t)$ $N (t)$ 내에서만 Shapley 값을 계산합니다.
- 정확한 국소성: KNN 의 임계값 설정 등 모델이 엄격하게 국소적일 경우, 국소 Shapley 값은 전역 Shapley 값과 정확히 일치합니다.
- 근사 국소성: SVM, GNN 등 영향력이 점진적으로 감소하는 모델의 경우, 국소 영역 밖의 데이터가 미치는 영향은 이론적으로 상한 (Proposition 1) 이 보장되며, 이 오차는 국소 영역 밖의 상호작용 강도에 비례합니다.

2.2 최적 재사용 알고리즘: LSMR (Local Shapley via Model Reuse)

국소성을 적용하더라도 Support Set 내의 모든 부분집합을 나열하면 여전히 지수적 복잡도가 발생합니다. 저자들은 부분집합 중심 (Subset-Centric) 접근법을 통해 중복 계산을 제거합니다.

핵심 통찰: Shapley 계산의 본질적 복잡도는 전체 연합 수 ($2^N$) 가 아니라, 적어도 하나의 가치 평가에 영향을 미치는 '서로 다른 (Distinct)' 부분집합의 수에 의해 결정됩니다.
정보 이론적 하한: 어떤 정확한 알고리즘이라도 각 서로 다른 부분집합을 최소 한 번은 평가해야 함을 증명했습니다.
LSMR 알고리즘:
1. 이분 Support 매핑 그래프: 테스트 포인트와 훈련 데이터 간의 의존 관계를 그래프로 표현합니다.
2. 역 Support 인덱싱: 특정 부분집합 $S$ 가 유효한 모든 테스트 포인트를 식별합니다.
3. Pivot 기반 스케줄링: 각 부분집합 $S$ 에 대해 하나의 'Pivot(기준)' 테스트 포인트를 지정합니다. 해당 Pivot 에서만 모델을 훈련하고, 그 결과를 다른 모든 관련 테스트 포인트에 재사용합니다.
- 결과: 각 서로 다른 부분집합을 정확히 한 번만 훈련하여 재훈련 비용을 정보 이론적 하한까지 낮춥니다.

2.3 재사용 인식 몬테카를로 추정기: LSMR-A

Support Set 이 커서 정확한 나열이 불가능한 경우를 위해 몬테카를로 추정기를 확장했습니다.

Subset-Centric Sampling: 개별 플레이어 중심이 아닌 부분집합을 샘플링하여, 한 번 훈련된 부분집합의 결과를 모든 관련 테스트 포인트에 공유합니다.
Pivoted Sampling: 샘플링된 부분집합이 해당 Pivot 테스트 포인트에서 처리될 때만 훈련을 수행하고, 다른 경우엔 기존 결과를 재사용합니다.
통계적 보장:
- 편향 없음 (Unbiasedness): 기존 몬테카를로와 동일한 기대값을 가집니다.
- 지수적 집중 (Exponential Concentration): 샘플 수에 따라 오차가 지수적으로 감소합니다.
- 분산 감소: 불필요한 무작위성 (전체 데이터셋에서 샘플링되는 무관한 점들) 을 구조적으로 제거하여 분산을 줄입니다.

3. 주요 기여 (Key Contributions)

모델 유도 국소성 (Model-Induced Locality) 의 공식화: 예측 모델의 구조적 특성을 기반으로 Shapley 계산을 국소 영역으로 제한하는 이론적 프레임워크를 제시하고, 전역 Shapley 와의 오차 상한을 유도했습니다.
본질적 부분집합 복잡도 및 하한 증명: Shapley 계산의 복잡도가 전역 공간이 아닌 '서로 다른 영향력 있는 부분집합'의 수에 의해 결정됨을 증명하고, 재훈련 작업에 대한 정보 이론적 하한을 확립했습니다.
LSMR (정확한 알고리즘): Support 매핑과 Pivot 스케줄링을 통해 각 영향력 있는 부분집합을 한 번만 훈련하는 최적의 정확한 알고리즘을 제안했습니다.
LSMR-A (확장 알고리즘): 재사용을 고려한 몬테카를로 추정기를 개발하여, 샘플링 복잡도와 재훈련 복잡도를 분리하면서도 편향 없음과 낮은 분산을 보장합니다.

4. 실험 결과 (Results)

저자들은 Weighted KNN, RBF Kernel SVM, Decision Tree, Graph Neural Network (GNN) 등 4 가지 모델 계열과 다양한 데이터셋 (MNIST, Iris, Breast Cancer, Cora) 에서 실험을 수행했습니다.

근사 정확도 (Fidelity): 국소 Shapley 값은 전역 Shapley 값과 높은 상관관계 (Pearson $r$ : 0.53~0.84) 를 보였으며, 특히 KNN 과 같이 국소성이 명확한 모델에서는 거의 완벽하게 일치했습니다.
하류 작업 효율성 (Data Selection): Shapley 점수를 기반으로 데이터를 선별하여 모델 훈련 시, LSMR-A 는 전역 기반 방법들보다 더 적은 데이터로 동등하거나 더 높은 정확도를 달성했습니다.
계산 효율성 (Efficiency):
- 재훈련 횟수 감소: LSMR-A 는 전역 몬테카를로 (Global-MC) 대비 수천 배 (3 개 차수 이상) 의 재훈련 횟수 감소를 달성했습니다.
- 실행 시간: 대규모 데이터셋 (MNIST, $|D|=10,000$ ) 에서 LSMR-A 는 2 분 이내에 수렴하는 반면, 기존 방법들은 실행 불가능하거나 수일이 소요되었습니다.
- 확장성: 데이터셋 크기가 증가할수록 LSMR-A 의 재훈련 비용은 거의 일정하게 유지되는 반면, 기존 방법들은 지수적으로 증가했습니다.
모델 정렬 중요성: Support Set 을 평가 모델의 구조 (예: GNN 에 대해 GNN 기반 수용 영역) 와 일치시킬 때 가장 높은 정확도를 보였습니다. 구조적 불일치는 정확도를 급격히 떨어뜨렸습니다.

5. 의의 및 결론 (Significance)

이 논문은 데이터 가치 평가를 단순한 계산 최적화 문제를 넘어 구조화된 데이터 관리 문제로 재해석했습니다.

이론적 혁신: Shapley 계산의 병목이 '전체 연합 공간'이 아니라 '서로 다른 영향력 있는 부분집합'임을 규명하여, 재훈련 복잡도에 대한 새로운 하한을 제시했습니다.
실용적 가치: LSMR 및 LSMR-A 는 대규모 데이터셋과 복잡한 모델 (딥러닝, GNN 등) 에서도 Shapley 기반 데이터 가치 평가를 실용적으로 가능하게 합니다.
미래 전망: 이 프레임워크는 동적 환경이나 연동 학습 (Federated Learning) 과 같이 Support 구조가 진화하거나 분산된 환경으로 확장될 수 있는 기반을 마련했습니다.

결론적으로, 본 연구는 국소성 (Locality) 과 최적 재사용 (Optimal Reuse) 을 결합함으로써 Shapley 계산의 이론적 최적성과 실용적 확장성을 동시에 달성한 획기적인 접근법을 제시합니다.