기술 요약: 가짜 이름에 강한 데이터 귀속을 위한 몫 준가치

1. 문제 제기

데이터 Shapley 와 같은 데이터 가치 평가 방법은 기계 학습 파이프라인에 대한 훈련 데이터의 기여도를 배분하고 감사하기 위해 고안되었습니다. 그러나 이러한 방법들은 일반적으로 고정된 수동 기여자 집합을 가정합니다. 실제 데이터 시장에서는 기여자가 자신의 몫을 부풀리기 위해 귀속 메커니즘을 조작할 수 있는 전략적 행위자입니다.

이 논문은 가짜 이름 조작을 치명적인 실패 모드로 식별합니다. 단일 잠재 공급자는 다음과 같은 행위를 할 수 있습니다:

• 분할: 하나의 데이터셋을 여러 익명 정체성 (Sybil 공격) 으로 분할합니다.
• 복제: 고가치 예시를 복제하거나 거의 중복된 데이터 (패러프레이즈, 증강, 합성 변형) 를 생성합니다.
• 세탁: 평가자의 검증 세트를 악용하기 위해 합성 변형을 세탁합니다.

핵심 문제는 보고된 정체성에 대한 표준 Shapley 공정한 귀속이 인센티브 호환적이지 않다는 점입니다. 데이터 가치는 종종 비가산적이고 상호 보완적이기 때문에, 데이터셋을 여러 정체성으로 분할하면 공격자가 단일 정직한 정체성으로 받을 가치보다 Shapley 가치의 합을 증가시킬 수 있습니다.

2. 방법론

2.1 형식적 모델

저자들은 잠재 공급자($N$)와 제출된 정체성($m$)에 대한 메커니즘 설계 문제로 설정을 형식화했습니다.

• 데이터 가치 게임: 연합의 가치가 해당 연합의 페이로드 합집합으로 훈련된 학습자의 효용이 되는 단조 게임.
• 조작 클래스:
  • 가짜 이름 분할: 원래 데이터의 분할 또는 복제를 보유한 $k \ge 2$개의 정체성으로 하나의 정체성을 대체하는 것.
  • 변형 공격: 하나 이상의 정체성 하에 변환된 복사본 (중복, 패러프레이즈, 합성 데이터) 을 제출하는 것.
• 이득 지표: 정직한 보고와 비교하여 공격자가 정체성 구조를 조작함으로써 달성하는 가산적 또는 승법적 이득.

2.2 불가능성 결과

이 논문은 보고된 정체성에 대한 정확한 Shapley 공정한 귀속은 무제한 가짜 이름 증명성과 양립할 수 없다는 근본적인 불가능성 정리를 증명합니다.
이진수 값의 단조 게임 (예: 만장일치 게임) 에서조차, 공급자는 데이터를 여러 가명으로 분할함으로써 총 보상을 증가시킬 수 있습니다. 예를 들어, $v(\{A, B\}) = 1$인 2 인 만장일치 게임에서 공급자 $A$는 $1/2$을 받습니다. 만약 $A$가 $A_1, A_2$로 분할하여 가치에 세 명 ($A_1, A_2, B$) 이 모두 필요하게 된다면, 새로운 Shapley 가치는 각각 $1/3$이 되어 $A$에게는 총 $2/3$이 됩니다. 이러한 구조적 취약점은 일반 준가치 (Banzhaf, Beta-Shapley) 로도 확장되지만, 이득의 크기는 다양합니다.

2.2 몫 준가치 메커니즘

이를 해결하기 위해 저자들은 몫 준가치 (Quotient Semivalue) 메커니즘을 제안하며, 이는 전략적 단위를 원시 제출 정체성에서 증거 기반 귀속 클러스터로 전환합니다.

1. 증거 그래프 및 클러스터링:
   • 증거 함수 $e_\theta(u, u')$는 두 단위 (예시, 문서) 가 해시, 임베딩, 출처 등에 기반하여 동일한 귀속 객체로 간주하기에 충분히 유사한지 여부를 결정합니다.
   • 이는 연결된 구성 요소가 클러스터($C_1, \dots, C_K$)가 되는 그래프를 형성합니다.
2. 클러스터 대표 연산자 ($R_\theta$):
   • 클러스터 내 중복 (예: 가중치를 높이기 위해 예시 10 개를 제출) 을 통한 조작을 방지하기 위해, 고전적 대표 연산자는 각 클러스터를 고정된 고전적 훈련 단위 집합으로 매핑합니다.
   • 전략으로는 정확한 중복 축소, 클러스터당 단위 수 제한, 또는 가중치 정규화 합집합 등이 포함됩니다.
3. 몫 게임:
   • 플레이어가 정체성이 아닌 클러스터인 새로운 협력 게임이 구성됩니다.
   • 클러스터 연합의 가치는 그들의 고전적 대표자들의 합집합으로 훈련된 학습자의 효용입니다.
4. 준가치 계산 및 배분:
   • 준가치 (Shapley, Banzhaf 등) 가 몫 게임에 대해 계산됩니다.
   • 클러스터 내 배분: 클러스터에 대한 지불은 그 안에 있는 제출된 정체성들 사이에 분배됩니다. 이 메커니즘은 클러스터 내에서 정체성을 분할하는 것이 총 몫을 증가시키지 않도록 보장하기 위해 가짜 이름 중립적 배분 규칙 (예: 각 정체성이 기여한 고전적 단위 수에 비례하는 배분) 을 요구합니다.

3. 주요 기여

1. 형식적 모델: 잠재 공급자, 제출된 정체성, 변환 공격을 포함하는 데이터 공급자 조작에 대한 엄격한 프레임워크.
2. 불가능성 정리: 보고된 정체성에 대해 정확히 Shapley 공정하고 무제한적으로 가짜 이름 증명적인 메커니즘은 존재할 수 없다는 증명.
3. 몫 준가치 메커니즘: 고전적 대표 연산자를 갖춘 증거 기반 클러스터에 대해 준가치를 계산하는 구성적 해결책.
4. 이론적 보장:
   • 정확한 가짜 이름 증명성: "몫 안정적" 조작 (공격자가 정직한 클러스터를 탈출하거나 고전적 대표자를 변경할 수 없는 경우) 과 가짜 이름 중립적 배분 하에 달성됨.
   • 근사적 보장: 조작 이득과 공정성 손실에 대한 경계는 세 가지 측정 가능량인 탈출 클러스터 질량 (새로운 클러스터를 형성하는 변형), 가치 추정 오차, 클러스터링 거리 (대표자의 변화) 로 표현됨.
5. DataMarket-Gym: 정확한 중복, 거의 중복, 합성 세탁, Sybil 분할을 포함한 전략적 공급자 공격 하에서 귀속 메커니즘을 평가하기 위한 새로운 벤치마크.

4. 실험 결과

저자들은 합성 및 실제 데이터셋 (CIFAR-10, AG News, STL-10, IMDB) 에서 메커니즘을 평가했습니다.

• 합성 분류:
  • 원시 정체성에 대한 기준 Shapley 는 중복/Sybil 공격에서 1.74의 조작 이득을 보였습니다.
  • 예시 수준의 증거 (코사인 유사도 $\theta=0.99$) 를 사용한 몫 Shapley 는 이 이득을 0.96으로 줄여 공격을 효과적으로 무력화하고 정직한 수준에 근접하게 복귀시켰습니다.
  • 이 메커니즘은 준가치 선택 (Shapley, Banzhaf, Beta-Shapley) 에 대해 강건합니다.
• 임계값 민감도:
  • 코사인 임계값 $\theta$는 중요합니다. 임계값이 너무 낮으면 "거의 병합" (독립적인 공급자들이 그룹화됨) 을 초래하여 Sybil 이득을 증폭시킬 수 있습니다. 임계값이 너무 높으면 거의 중복된 데이터를 포착하지 못합니다.
  • 논문은 도메인별 임계값 반전을 식별합니다:
    • 이미지 도메인 (CIFAR-10) 에서는 높은 노름이 높은 쌍대 유사도로 이어지므로, 체인 공격을 방지하기 위해 더 엄격한 임계값 ($\theta \ge 0.90$) 이 필요합니다.
    • 텍스트 도메인 (AG News) 에서는 단위 정규화 임베딩이 낮은 쌍대 유사도를 가지므로, 엄격한 임계값이 거의 중복된 데이터를 연결하지 못하기 때문에 더 완만한 임계값 ($\theta \le 0.90$) 이 최적입니다.
  • 최적 임계값은 임베딩 통계 (쌍대 p90 및 체인-바닥 혼합 구성 요소 비율) 에서 예측 가능합니다.
• 실제 전이:
  • 이 메커니즘은 오라클 접근 없이 고정된 특징 파이프라인 (ResNet-18, MiniLM) 으로 전이되어 실제 실행 가능성을 확인했습니다.
  • 순수 분할 공격 (중첩이 없는 불연속 데이터) 은 유사성 증거만으로는 방어되지 않으며, 예시 수준이 아닌 출처 (예: 계정 연결, KYC) 가 필요합니다.

5. 중요성 및 주장

이 논문은 정체성이 내생적일 때 Shapley 공정한 데이터 귀속이 자동으로 인센티브 호환적이지 않다고 주장합니다. 이 연구의 중요성은 다음과 같습니다:

• 전략적 부담의 전환: 변경 가능한 정체성에서 증거 기반 클러스터로 귀속 단위를 이동시킴으로써 Shapley 스타일 공정성과 Sybil 저항성 사이의 통제된 절충을 가능하게 합니다.
• 조건부 가능성: 무제한 조작 하에서 정확한 Shapley 공정은 불가능하지만, 유사성과 출처 신호가 조작된 변형을 동일한 단위로 신뢰할 수 있게 축소할 수 있을 때 몫 메커니즘은 "통제된 절충"을 회복합니다.
• 실제 배포: 이 메커니즘은 "준가치 무관"이므로 다양한 가치 평가 백엔드 (Shapley, Banzhaf 등) 와 함께 배포될 수 있으며 추정기 노이즈에 강건합니다.
• 상호 보완성: 이 접근법은 데이터 콘텐츠가 변경 (복제, 패러프레이즈, 합성) 될 수 있을 때 귀속 단위 자체의 구성을 다루는 반면, "충실한 그룹 Shapley 가치" (고정된 데이터셋에 대한 쉘 회사 집합을 방어) 에 대한 기존 작업을 보완합니다.

저자들은 귀속 단위가 메커니즘 설계의 선택 사항이며, 몫 준가치가 공급자가 전략적인 데이터 시장을 위한 강력한 프레임워크를 제공한다고 결론지었습니다.