기술 요약: NASH - SHapley 정보성 구성요소의 비선형 집계

문제 제기

데이터 선택은 크기 제약 하에서 모델 유틸리티 (예: 검증 정확도 $u_V$) 를 최적화하기 위해 고품질 훈련 데이터 하위 집합을 식별하는 것을 목표로 합니다. 데이터 Shapley 와 그 일반화 (세미값) 는 데이터 상호작용을 고려하기 위해 협력 게임 이론에 이론적으로 근거하고 있지만, 최근 실증 연구들은 이들이 실제 환경에서는 종종 비효과적으로 작동함을 보여줍니다. 구체적으로, 검증 정확도와 같은 복잡한 유틸리티 함수에 대해 계산된 Shapley 값을 기준으로 상위 $m$개의 데이터 포인트를 선택하는 경우, 무작위 선택보다 나을 뿐만 아니라 오히려 더 나쁜 하위 집합을 산출할 수 있습니다.

본 논문은 이러한 실패의 두 가지 주요 원인을 식별합니다:

1. Shapley 정보성 부재: 복잡한 유틸리티 함수는 검증 세트 내의 여러 다른 "역할" (예: 다른 클래스 또는 하위 집단) 을 포함합니다. 단일 데이터 포인트에 대한 하나의 Shapley 값은 이러한 역할 전반에 걸쳐 해당 데이터의 고유한 강점을 포착하지 못합니다. 결과적으로 서로 다른 강점을 가진 데이터가 동일한 Shapley 점수를 받아, 서로 다른 유틸리티 기여도에도 불구하고 상호 교환 가능한 취급을 받게 됩니다.
2. 부적절한 집계: 진정한 목표 (예: 검증 정확도) 는 이러한 역할 전반의 성능을 비선형적으로 집계합니다. 그러나 표준 상위 $m$개 휴리스틱은 Shapley 값을 합산하는 선형 집계에 의존하는데, 이는 한 데이터 포인트의 기여도가 이미 선택된 다른 데이터에 따라 달라지는 시너지 상호작용 (예: 과소 대표된 역할을 커버하는 데이터 포인트는 더 가치 있음) 을 포착하지 못합니다.

방법론: NASH 프레임워크

저자들은 NASH(SHapley 정보성 구성요소의 비선형 집계) 를 제안합니다. 이는 복잡한 유틸리티 함수를 Shapley 값이 효과적인 단순한 구성요소로 분해한 후, 이를 비선형적으로 집계하는 프레임워크입니다.

1. Shapley 정보성과 분해

본 논문은 Shapley 값의 합이 하위 집합의 실제 유틸리티를 나타내는 속성으로 Shapley 정보성을 형식화합니다. 저자들은 임의의 유틸리티 함수는 일반적으로 Shapley 정보성을 갖지 않는다고 증명합니다. 그러나 그들은 더 단순한 유틸리티 함수, 구체적으로 단일 검증 데이터에 대한 예측 정확도($u_v$) 가 "일관된 플레이어" 가정 (특정 검증 포인트에 대해 데이터가 일관되게 좋거나 나쁨) 하에서 Shapley 정보성을 갖는다고 증명합니다.

NASH 는 집계된 검증 정확도 $u_V$에 대한 Shapley 값을 계산하는 대신, 각 검증 데이터 $v \in V$에 대해 개별 구성요소 $u_v$로 $u_V$를 분해합니다. 그리고 이러한 단순한 구성요소에 대해 Shapley 값 $\phi_i(u_v)$를 계산합니다. 주목할 점은 $u_V$가 단순히 $u_v$들의 평균이므로, 집계된 $u_V$에 대한 Shapley 값을 계산하는 것과 비교하여 이러한 벡터를 계산하는 데 추가적인 실행 시간 비용이 발생하지 않는다는 것입니다.

2. 비선형 집계

이러한 정보성 구성요소로부터 복잡한 목표를 재구성하기 위해 NASH 는 선형 합계 (결함이 있는 상위 $m$개 Shapley 휴리스틱을 복원함) 를 피합니다. 대신 비선형 집계 목표를 최적화합니다:
$$\max_{M \subseteq N, |M|=m} \sum_{v \in V} F_T(\hat{u}_v(M))$$
여기서 $\hat{u}_v(M) = \sum_{i \in M} \phi_i(u_v)$는 구성요소 $v$에 대한 Shapley 값의 합이며, $F_T$는 학습 곡선에서 영감을 받은 누적 분포 함수 (CDF) (예: 지수 법칙) 입니다. 이 비선형 함수는 선택 과정이 이미 잘 예측된 포인트에서 높은 점수를 누적하는 대신, poorly predicted 검증 포인트 (미해결된 역할) 에 대한 "임계값을 넘기"를 돕는 데이터를 우선시하도록 보장합니다.

3. 최적화

NASH 목표는 그리디 알고리즘을 사용하여 최적화됩니다. 저자들은 Shapley 값이 음이 아닐 때 목표 함수가 단조 서브모듈러임을 보여 $(1 - 1/e)$ 근사성을 보장합니다. 음수 값 (노이즈가 있는 데이터에서 발생) 이 있더라도, 해를 끼치는 데이터 (서브모듈러성을 위반하게 만드는 데이터) 가 자연스럽게 우선순위가 낮아지기 때문에 그리디 알고리즘은 경험적으로 잘 작동합니다. 이 알고리즘은 무거운 작업 (Shapley 근사) 을 기존 방법과 공유하므로 추가적인 실행 시간 비용은 최소화됩니다.

주요 기여

1. 이론적 분석: 본 논문은 Shapley 정보성 속성을 형식화하여 복잡한 ML 유틸리티 함수 (예: 검증 정확도) 가 이를 만족하지 못해 데이터 Shapley 의 일관되지 않은 성능을 초래하는 이유를 설명합니다.
2. 검증 가능한 정보성 구성요소: 저자들은 합리적인 가정 하에서 단일 검증 데이터 포인트에 대한 예측 정확도가 Shapley 정보성 구성요소로 작용함을 식별하고 증명합니다.
3. NASH 프레임워크: 복잡한 목표를 Shapley 정보성 구성요소로 분해하고 이를 비선형적으로 집계하여 고품질 하위 집합을 선택하는 새로운 데이터 선택 프레임워크입니다.
4. 실증적 검증: 표준 데이터셋 (로지스틱 회귀, KNN) 과 대규모 언어 모델 파인튜닝 (BERT, Llama-2) 을 통한 광범위한 실험은 NASH 가 순수한 데이터 Shapley, 기타 세미값, 그리고 무작위 선택보다 일관되게 우월한 성능을 보임을 입증합니다.

결과

• 일반 데이터 선택: 주입된 노이즈가 없는 환경 (동질적 품질) 에서 순수한 데이터 Shapley 는 종종 무작위 선택보다 나을 바가 없습니다. NASH 는 이러한 시나리오에서 성능을 크게 향상시켜 다양한 선택 비율에 걸쳐 베이스라인을 일관되게 능가합니다.
• 이질적 품질 데이터셋: 라벨 노이즈가 있는 환경에서는 순수한 데이터 Shapley 가 개선되지만 (나쁜 데이터를 식별할 수 있으므로), NASH 는 여전히 일관되게 더 나은 성능을 보입니다. 이는 NASH 의 이점 (역할 상호작용 처리) 이 노이즈 필터링 능력과 구별되며 상호 보완적임을 시사합니다.
• 호환성: NASH 는 다양한 세미값 (예: Beta Shapley, Data Banzhaf) 과 효율적인 근사 방법 (예: MC 샘플링, FreeShap) 과 호환되며, 이들의 선택 성능을 일관되게 향상시킵니다.
• 강건성: 이 방법은 집계 함수의 하이퍼파라미터 $\lambda$ 선택에 강건하며, 다양한 유틸리티 함수 (예: 검증 손실, MSE) 와 효과적으로 작동합니다.

의의

본 논문은 NASH 가 데이터 Shapley/세미값이 제한된 데이터셋이나 특정 환경 (예: 주입된 노이즈가 있는 경우) 에서만 효과적이라는 제약을 대폭 제거한다고 주장합니다. Shapley 기반 선택을 다양한 데이터셋과 모델 규모에 걸쳐 일관되게 신뢰할 수 있고 강건하게 만드는 프레임워크를 제공함으로써, NASH 는 원칙적인 데이터 가치 평가 방법의 광범위한 채택을 가능하게 합니다. 이러한 발전은 기초 모델에 대한 근사 효율성 및 데이터 선택 개선에 대한 향후 연구를 지원하며, Shapley 값의 이론적 이점 (단시적이지 않은 상호작용과 형평성) 이 실제로 실현되도록 보장합니다.