기술 요약: 선형 설명자를 이용한 조건부 샤플리 값의 빠른 근사 추정

문제 정의

본 논문은 공변량 간의 의존성이 존재하는 선형 회귀 모델에서 **조건부 샤플리 값(conditional Shapley values)**을 추정할 때 발생하는 계산상의 병목 현상을 다룹니다. 샤플리 값은 특정 예측에 대한 특성 기여도를 게임 이론적으로 분해하여 제공하지만, 이를 조건부로 계산하려면 가능한 모든 특성 부분집합(coalitions)에 대한 기대 모델 출력을 추정해야 합니다.

$p$개의 예측 변수가 있는 모델의 경우, $2^p$개의 가능한 부분집합이 존재합니다. shapr R 패키지의 순차적(Sequential) 및 반복적(Iterative) 접근 방식과 같은 기존 방법들은 다음과 같은 상당한 문제에 직면합니다:

1. 순차적 추정(Sequential Estimation): $2^p$개의 별도 회귀 모델을 적합시켜야 하며, 이는 $p$가 증가함에 따라 계산적으로 불가능해집니다.
2. 반복적 추정(Iterative Estimation): 수렴 기준을 충족할 때까지 부분집합을 샘플링합니다. 적은 수의 부분집합만으로도 수렴하는 경우에는 더 빠를 수 있지만, 어려운 사례에서는 수렴을 위해 여전히 전체 $2^p$ 중 상당한 비율의 부분집합을 요구할 수 있으며, 이로 인해 순차적 방법과 유사하게 긴 실행 시간(수 시간)이 소요됩니다.
3. 특성 의존성(Feature Dependence): 한계 샤플리 값(marginal Shapley values)과 달리, 조건부 값은 공변량 간의 의존 구조를 고려해야 하므로 복잡한 조건부 기대치 계산이 필요합니다.

저자들은 수학적 구조의 희소성(sparsity)을 활용하여 모든 $2^p$ 서브모델의 계수를 동시에 신속하게 추정할 수 있는 방법을 개발하고자 합니다.

방법론

제안된 접근 방식은 제약 가우시안 마르코프 무작위장(Constrained Gaussian Markov Random Field, GMRF) 이론과 희소 행렬 대수를 활용하여, 모든 서브모델을 순차적이 아닌 공동으로 추정합니다. 저자들은 세 가지 별도의 알고리즘을 도출했습니다.

1. 대각 수정법 (Diagonal Correction Method, 근사 방식)

이 방법은 정밀 행렬($Q = X^T X$)을 수정하여 제약된 회귀를 근사합니다.

• 메커니즘: 특정 계수를 0으로 강제하는 제약(즉, 해당 특성이 서브모델에서 제외됨)을 적용하기 위해, 정밀 행렬의 해당 대각 요소에 큰 스칼라 값 $\kappa$를 더합니다.
• 이론적 기초: Woodbury 행렬 항등식에 기반하여, $\kappa A^T A$ (여기서 $A$는 제약 행렬)를 $Q$에 더하면 $\kappa \to \infty$일 때 조건부 공분산 행렬을 근사하게 됩니다.
• 구현: 모든 $2^p$ 모델을 위한 공동 제약 행렬 $A$를 구성합니다. 이 방법은 $(Q_F + \kappa A^T A)^{-1}m$ 선형 시스템을 해결하며, 여기서 $Q_F$는 전체 모델의 정밀 행렬이 $2^p$번 반복된 블록 대각 행렬입니다.
• 튜닝: 튜uning 파라미터 $\kappa$가 필요하며, 원래 정밀 행렬의 가장 큰 고윳값의 $10^5$배로 제안됩니다.

2. 투영법 (Projection Method, 근사 방식)

이 방법은 매개변수 공간을 투영하여 제약된 매개변수를 제거합니다.

• 메커니즘: 투영 행렬 $Z = I - A^T A$를 정밀 행렬에 적용합니다. 제약된 모델은 내재적 GMRF로 취급됩니다. 수치적 안정성(양의 정치성)을 보장하기 위해 투영된 정밀 행렬의 대각선에 작은 스칼라 $\epsilon$을 더합니다 ($Z Q F Z + \epsilon I$).
• 이론적 기초: $\epsilon \to 0^+$일 때, 솔루션은 정확한 제약 추정치로 수렴합니다.
• 구현: $Z(Z Q_F Z + \epsilon I)^{-1} Z m$ 시스템을 해결합니다.
• 튜닝: 작은 튜닝 파라미터 $\epsilon$ (예: $10^{-5}$)이 필요하며, 이는 $Q$의 가장 작은 고윳값보다 작지만 안정적인 촐레스키 분해(Cholesky decomposition)를 위해 충분히 커야 합니다.

3. 정확 변환법 (Exact Transformation Method, 정확 방식)

이 방법은 근사 오차나 튜닝 파라미터 없이 정확한 솔루션을 제공합니다.

• 메커니즘: 제약된 매개변수를 0으로 강제하는 대신, 0이 아닌 매개변수만을 포함하는 저차원 공간으로 문제를 변환합니다.
• 구현: 활성 매개변수만을 선택하는 매핑 행렬 $E$를 구성합니다. 시스템은 $(E Q_F E^T)^{-1} E m$으로 해결됩니다.
• 장점: 큰 페널티 항($\kappa$)이나 작은 정규화 항($\epsilon$)을 사용할 필요가 없어, 잠재적인 수치적 불안정성이나 근사 편향을 제거합니다.

세 방법 모두 효율적인 공동 추정을 위해 희소 행렬 대수(특히 촐레스키 분해)를 사용합니다. 공동 정밀 행렬은 모델들이 독립적이므로 매우 희소하며(블록 대각 구조), 비대각 성분의 0은 조건부 독립성을 나타냅니다.

주요 기여

1. 세 가지 새로운 알고리즘: 선형 회귀에서의 모든 서브모델의 공동 추정을 위해 두 가지 근사 방법(대각 수정, 투영)과 한 가지 정확한 방법(정확 변환)을 도입했습니다.
2. 수렴 증명: 저자들은 근사 방법들이 각각의 튜닝 파라미터($\kappa \to \infty$ 및 $\epsilon \to 0^+$)에 따라 실제 조건부 추정치로 수렴함을 보여주는 수학적 증명을 제공합니다.
3. 계산 효율성: 희소성과 공동 추정을 활용함으로써, 모든 $2^p$ 코알리션을 열거할 때도 계산 시간을 몇 시간 단위에서 초 또는 분 단위로 단축했습니다.
4. 실증적 검증: 새로운 방법들을 Adult Income, 시뮬레이션된 가우시안 데이터셋, WHO Life Expectancy 데이터셋의 세 가지 데이터셋을 통해 shapr 패키지(Sequential 및 Iterative 버전)와 비교하여 광범위한 수치 연구를 수행했습니다.

결과

수치 사례 연구를 통해 다음과 같은 결과가 도출되었습니다:

• 정확도: 새로운 방법들이 생성한 샤플리 값 추정치는 (전체 열거를 위한 ground truth로 사용된) shapr의 Sequential 방식과 거의 동일합니다.
  • Adult 데이터셋 ($p=11$)에서 새로운 방법들과 Sequential 방식 사이의 중앙 절대 오차(MedAE)는 $10^{-9}$ 수준이었습니다.
  • 시뮬레이션 데이터셋 ($p=21$)에서 MedAE는 $10^{-7}$에서 $10^{-5}$ 수준이었습니다.
  • WHO 데이터셋 ($p=16$)에서 MedAE는 $10^{-6}$ 수준이었습니다.
• 속도:
  • Adult 데이터셋: 새로운 방법들은 2.5~9초 만에 실행된 반면, shapr(Sequential 및 Iterative)는 17~19분이 소요되었습니다.
  • 시뮬레이션 데이터셋: 새로운 방법들은 약 210만 개의 모델($2^{21}$)을 추정하는 데 1.4~2.5분이 걸렸습니다. shapr Iterative 방식은 200개의 코알리션만 추정했으나 6.48초로 더 빨랐습니다.
  • WHO 데이터셋: 새로운 방법은 1.1~1.2분이 걸렸습니다. shapr Sequential 방식은 **131분(2.2시간)**이 걸렸고, Iterative 방식은 병렬 실행 시 16분, 직렬 실행 시 36분이 걸렸습니다.
• 확장성: 새로운 방법들은 시뮬레이션 연구에서 200만 개 이상의 서브모델을 몇 분 안에 성공적으로 추정했습니다. 확인된 주요 제한 사항은 표준 하드웨어에서 $p$가 약 21을 초과할 때의 메모리 제약(차원의 저주)이지만, 저자들은 더 많은 RAM이나 특화된 희소 행렬 패키지로 완화할 수 있다고 언급했습니다.

의의 및 주장

본 논문은 제안된 방법들이 정확도를 희생하지 않으면서 조건부 샤플리 값 추정을 위한 계산 효율성을 대폭 개선한다고 주장합니다.

• 전체 열거에서의 우월성: shapr의 Iterative 방법이 수렴을 위해 많은 수의 코알리션을 요구할 때(Adult 및 WHO 데이터셋에서 확인됨), 새로운 방법들은 동일하거나 더 나은 정확도를 유지하면서도 "상당히 빠릅니다."
• 포괄적 열거: 코알리션을 샘플링하는 반복적 접근 방식과 달리, 새로운 방법은 모든 $2^p$ 서브모델의 전체 열거를 제공하여 샘플링 분산으로 인한 정보 손실이 없습니다.
• 권장 사항: 저자들은 실무적 사용을 위해 **정확 변환법(Exact Transformation Method)**을 권장합니다. 세 방법 모두 유사한 결과를 내지만, 정확 변환법은 튜닝 파라미터가 없어 하이퍼파라미터 선택의 필요성과 근사 오차의 원인을 제거합니다.
• 미래 잠재력: 저자들은 이 방법론이 스플라인(예: rms 패키지)을 처리하도록 확장될 수 있으며, 병렬화(예: OpenMP)를 통해 실행 시간을 더욱 단축할 수 있다고 제안합니다.

결론적으로, 본 논문의 방법들은 이전에는 계산적으로 불가능했던 혼합형 공변량 유형을 가진 선형 모델에 대한 조건부 샤플리 값의 정확한 계산을 가능하게 합니다.