Amortized Linear-time Exact Shapley Value for Product-Kernel Methods

기술 요약: 곱 커널 방법에 대한 분할된 선형 시간 정확 샤플리 값

문제 제기
커널 방법은 유연성과 표현력 덕분에 머신러닝 및 통계 분야에서 널리 채택되고 있으나, 그 '블랙박스' 성격은 고위험 응용 분야에서의 채택을 저해합니다. 샤플리 값 기반 귀속 방법 (예: SHAP, RKHS-SHAP) 은 설명 가능성을 위한 원칙적인 프레임워크를 제공하지만, 특성 부분집합의 수가 지수적으로 증가 ($2^d$) 하기 때문에 샤플리 값의 정확한 계산은 일반적으로 계산 불가능합니다. 기존 접근법은 피할 수 없는 추정 오차를 수반하는 근사 (예: 몬테카를로 샘플링, 회귀 기반 추정기) 에 의존하며, 이 오차는 차원이 증가함에 따라 커집니다. 또한, 표준 가치 함수는 종종 주변 또는 조건부 분포로부터의 샘플링이나 밀도 추정을 필요로 하여 추가적인 계산 부담과 배경 데이터에 대한 의존성을 초래합니다.

방법론
본 논문은 특성 수에 대해 2 차 시간 ($O(d^2)$) 또는 특성당 분할된 선형 시간으로 곱 커널 방법 (예: 서포트 벡터 머신, 커널 릿지 회귀) 의 모든 $d$개 특성에 대한 정확한 샤플리 값을 계산하도록 설계된 PKeX-Shapley 알고리즘을 소개합니다.

이 방법론은 세 가지 핵심 구성 요소에 기반합니다:

1. 분포 무관 제거 연산자: 저자들은 커널 함수가 $k(x, x') = \prod_{j=1}^d k_j(x_j, x'_j)$로 인수분해되는 곱 커널을 사용하는 모델의 하위 클래스에 초점을 맞춥니다. 이들은 이 구조에 내재된 자연스러운 제거 연산자를 규명합니다: 특성 $j$를 제거하는 것은 해당 커널 인수 $k_j$를 곱셈 항등원 ($1$) 으로 대체하는 것에 해당합니다. 이 선택은 곱 구조를 유지하며 배경 분포가 필요 없고, 매개변수 없는 가치 함수를 유도합니다.

   • 샘플링이 필요한 개입적 또는 관찰적 가치 함수와 달리, 이 가치 함수는 함수적 분해를 통해 정의됩니다.
   • 연합 $S$에 대한 가치 함수는 $v_x(S) = \alpha^\top k_S(X_S, x_S) - f_\emptyset$으로 주어지며, 여기서 $f_\emptyset$은 한계 기여도에서 상쇄되는 상수 항입니다. 이 공식은 샘플링이나 밀도 추정이 필요하지 않습니다.

2. 함수적 분해: 제거 연산자를 활용하여 모델 $f(x)$를 특성 부분집합으로 인덱싱된 성분들의 합으로 고유하게 분해합니다: $f(x) = \sum_{S \subseteq D} f_S(x_S)$. 성분들은 부분집합 격자에서의 뫼비우스 반전을 통해 유도되며, 닫힌 형태를 가집니다: $f_S(x_S) = \sum_{i=1}^n \alpha_i \prod_{j \in S} (k_j(x_j, x^{(i)}_j) - 1)$.

3. 기본 대칭 다항식 (ESPs) 을 통한 재귀적 계산:

   • 단일 특성에 대한 샤플리 값은 한계 기여도의 가중 합으로 표현되며, 이는 커널 평가치의 **기본 대칭 다항식 (ESPs)**을 포함하는 항들로 인수분해됩니다.
   • 모든 특성에 대해 ESP 를 직접 계산하는 것은 비효율적입니다. 저자들은 뉴턴 항등식에 기반한 재귀적 공식을 유도합니다.
   • 모든 $d$개 샤플리 값을 공동으로 계산하기 위해, 접두사 - 접미사 구성을 사용합니다. 특성 집합의 접두사 (특성 $j$ 이전) 와 접미사 (특성 $j$ 이후) 에 대한 생성 다항식을 정의합니다. 이러한 다항식을 곱함으로써 $Z_{-j}$에 대한 ESP 를 복원합니다.
   • 이를 통해 모든 샤플리 값을 $O(d^2 n)$ 시간 ($n$은 샘플 수) 에 계산할 수 있습니다. 이 알고리즘은 요소별 덧셈과 곱셈에만 의존하여 수치적으로 안정적이며, 고차원에 적용될 때 다른 정확한 방법 (예: TreeSHAP) 에서 사용되는 다항식 보간 방법 (예: 체비셰프 또는 푸리에 보간) 과 관련된 수치적 불안정성을 피합니다.

통계적 불일치로 확장
이 프레임워크는 예측 모델링을 넘어 커널 기반 통계적 불일치로 확장됩니다. 구체적으로 다음과 같습니다:

• 최대 평균 불일치 (MMD): 분포 간 근접성을 측정하는 데 사용됩니다. 제거 연산자는 두 분포 간의 전체 불일치를 개별 변수에 할당하는 가치 함수를 생성합니다.
• 힐베르트 - 슈미트 독립성 기준 (HSIC): 확률 변수 간의 의존성을 측정하는 데 사용됩니다. 이 방법은 HSIC 의 함수적 분해를 제공하여 의존성을 특정 특성에 귀속시킬 수 있게 합니다.

결과
본 논문은 합성 및 실제 데이터셋에 대한 실험을 통해 PKeX-Shapley 를 검증합니다:

• 정확성 대 근사: 지역 설명에서 PKeX-Shapley(정확) 는 샘플링 기반 근사 (예: 커널 SHAP, RKHS-SHAP) 보다 현저히 우수합니다. 차원이 증가함에 따라 (예: $d=50$), 샘플링 기반 방법은 낮은 오차를 달성하기 위해 과도하게 큰 연합 크기가 필요하지만, PKeX-Shapley 는 차원에 관계없이 정확한 결과를 제공합니다.
• 특성 선택: HSIC 를 사용한 전역 민감도 분석에서 PKeX-Shapley 는 다항식 및 지수형 목적 함수를 가진 합성 회귀 작업에서 활성 특성을 효과적으로 식별하며, RKHS-SHAP, GEMFIX, BiSHAP 과 같은 기준 방법보다 우수하거나 이에 필적합니다.
• 계산 효율성: 이 알고리즘은 1,000 개 특성까지 수 초 내에 확장되지만, 브루트포스 계산은 약 20 개 특성으로 제한됩니다. 샘플링 기반 방법이 소수의 연합 샘플을 사용하더라도 이 알고리즘은 일관되게 더 빠릅니다.
• 수치적 안정성: 다양한 ESP 집계 전략 (2 차 재귀 대 FFT/체비셰프 보간) 을 비교한 실험은 보간 방법이 빠르지만 중간 차수 ($d \approx 50$) 에서 치명적인 수치적 불안정성을 겪음을 보여줍니다. 제안된 2 차 재귀는 $d=1000$까지 안정적으로 유지됩니다.

의의 및 주장
본 논문은 PKeX-Shapley 가 커널 방법에 대한 샤플리 값 계산의 두 가지 주요 과제를 해결한다고 주장합니다:

1. 근사 없는 정확성: 샘플링과 밀도 추정의 필요성을 제거하여 추정 오차를 제거하는 닫힌 형태, 매개변수 없는 가치 함수를 제공합니다.
2. 확장성: 정확한 계산을 위해 특성당 분할된 선형 시간 ($O(dn)$) 을 달성하여, 고차원 설정에서 브루트포스의 지수적 비용이나 샘플링 방법의 높은 분산보다 훨씬 개선되었습니다.

저자들은 이 방법이 곱 커널로 제한되지만, 이러한 구조적 제약이 계산 가능한 정확한 계산을 위해 필요하다고 강조합니다. MMD 와 HSIC 로의 프레임워크 확장은 휴리스틱 근사에 의존하지 않고 분포 차이와 의존성을 특정 변수에 귀속시킬 수 있는 해석 가능한 통계 분석을 위한 새로운 도구를 제공합니다. 저자들은 이 방법이 FANOVA GP 에 대한 방법과 동일한 방식으로 확률적 귀속 (예: 가우시안 프로세스의 샤플리 값 분산) 으로 자연스럽게 확장되지 않는다고 지적합니다. 이는 곱 커널의 경우 일반적으로 직교성이 성립하지 않기 때문입니다.