기술 요약: 비대칭 샤플리 값(Asymmetric Shapley Values)을 넘어선 효율적 계산

문제 정의

본 논문은 설명 가능한 인공지로리(XAI)의 특성 기여도(feature attribution)와 관련된 계산 및 해석 가능성 문제를 다룬다. 샤플리 값(및 그 머신러닝 구현체인 SHAP)은 모델의 예측을 입력 특성들 사이로 배분하는 이론적으로 근거가 탄탄한 방법을 제공하지만, 다음과 같은 두 가지 주요 한계점을 가진다:

1. 계산적 불가능성(Computational Intractability): 정확한 샤플리 값을 계산하는 것은 특히 표현력이 풍부한 모델(예: 신경망)이나 기저 데이터 분포가 복잡한 경우(예: 나이브 베이즈 분포) #P-hard 문제가 된다.
2. 해석력 결핍(Interpretability Deficits): 표준 샤플리 값은 모든 특성을 대칭적으로 취급한다. 이는 인과 관계를 포착하지 못하며, 원인과 그 결정론적 효과에 동일한 중요도를 부여함으로써 실제 데이터 생성 과정을 왜곡할 수 있다.

두 번째 문제를 해결하기 위해, 주어진 인과 그래프(유향 비순환 그래프, DAG)를 준수하는 특성들의 순열(permutation)로 계산을 제한하는 비대칭 샤플리 값(ASV)이 제안되었다. 그러나 ASV의 계산 복잡성에 대한 연구는 충분히 이루어지지 않았다. 본 논문은 특정 맥락에서 인과적 제약 조건을 포함하는 것이 표준 샤플리 값보다 계산을 더 용이하게 만들 수 있는지 조사한다.

방법론

저자들은 인과 그래프의 구조와 기저 확률 분포(베이지안 네트워크로 모델링됨)를 활용하여 ASV를 정확하고 근사적으로 계산하기 위한 일련의 알고리즘을 제래한다.

1. 이론적 계산 가능성 분석

저자들은 나이브 베이즈 분포 하에서의 ASV에 관한 이론적 결과를 확립한다. 저자들은 특정 모델 군에서 나이브 베이즈 분포 하의 표준 샤플리 값을 계산하는 것은 난해하지만, 만약 ASV에 사용된 인과 그래프가 나이브 베이즈 네트워크 구조와 동일하다면 ASV를 계산하는 것은 다항 시간 내에 가능하다는 것을 증명한다. 이는 분포에 의한 인과적 제약이 다른 방식으로 문제를 어렵게 만드는 대칭성을 깨뜨릴 수 있음을 시사한다.

2. 동치류(Equivalence Classes)를 통한 정확한 계산

더 일반적인 인과 구조, 특히 **루트가 있는 유향 트리(rooted directed trees)**로 계산 가능성을 확장하기 위해, 저자들은 순열의 탐색 공간을 줄이는 방법을 도입한다:

• 동치류: 저자들은 인과 그래프의 위상 정렬(topological orderings) 집합에 대한 동치 관계를 정의한다. 두 정렬이 특성 $x$에 대해 동치라는 것은 $x$ 앞에 오는 특성들의 집합이 두 정렬에서 동일함을 의미한다.
• 알고리즘: 모든 위상 정렬을 반복하는 대신(이는 지수적일 수 있음), 알고리즘은 동치류($\Lambda_x^C$)의 집합과 각 클래스의 크기를 계산한다. 그 후, 각 동치류의 크기에 가중치를 둔 한계 기여도(marginal contributions)를 합산하여 ASV를 계산한다.
• 복잡도: 루트가 있는 유향 트리에서 동치류의 수는 $h \cdot l + 1$ (여기서 $h$는 깊이, $l$은 잎의 수)로 제한된다. 저자들은 이러한 클래스와 그 크기를 계산하기 위한 다항 시간 알고리즘을 제공한다.

3. 샘플링을 통한 근사 계산

정확한 계산이 불가능할 수 있는 임의의 인과 DAG를 위해, 저자들은 샘플링 기반의 근사 기법을 제안한다.

• 위상 정렬 샘플링: 이 방법은 위상 정렬을 균등하게 무작위로 샘플링하는 것에 의존한다. 저자들은 두 가지 접근 방식을 구현한다:
  1. 소스 노드(source nodes)를 올바르게 가중치 부여하기 위해 위상 정렬의 개수를 세는 폴리트리(polytrees)(두 노드 사이에 경로가 최대 하나인 그래프)를 위한 재귀적 카운팅 알고리즘.
  2. 일반적인 DAG를 위한 랜덤 워크 기반 알고리즘(Bubley & Dyer, 1999 기반).
• 오차 범위: 저자들은 위상 정렬 샘플러가 균등 분포와 $\epsilon_{samp}$만큼 가깝고, 특성 함수(기댓값 모델 값)가 $\epsilon_{\nu}$의 오차로 근사될 때, 결과적인 ASV 추정치가 $O(\epsilon_{samp} + \epsilon_{\nu})$의 가산 오차를 가짐을 공식화한다.

주요 결과

저자들은 실제 베이지안 네트워크(Cancer, Child)와 인공 구조(balanced trees, Naive Bayes, multiple paths)에서 제안된 방법들을 평가하였다.

1. 탐색 공간의 감소: 동치류 접근 방식은 모든 위상 정렬을 열거하는 것과 비교하여 계산 부담을 크게 줄였다. "Child" 네트워크의 경우, 위상 정렬의 수는 약 $7.41 \times 10^{11}$이었으나, 동치류의 수는 평균적으로 약 2003개에 불과했다.
2. 실행 시간 효율성:
   • 실용적인 그래프 크기에 대해 동치류를 계산하는 데 1초 미만이 소요되었다.
   • 정확한 알고리즘의 실행 시간은 동치류의 수와 강한 상관관계를 보였으며, 이를 통해 클래스 개수 사전 계산이 계산 비용의 예측 지표로 기능할 수 있음을 보여주었다.
   • 더 큰 그래프에서는 모든 위상 정렬을 열거하는 것이 불가능해졌으나, 동치류 방식은 여전히 실행 가능했다.
3. 샘플링 성능:
   • 폴리트리를 위한 커스텀 재귀 샘플링 알고리즘은 병렬 후보 생성 덕분에 샘플 수에 따라 비선형적으로 스케일링되며 효율적이었다.
   • 1,000개의 샘플을 사용했을 때 ASV 값에 대해 약 8%의 평균 상대 오차를 보였다. 오차는 실제 값이 큰 ASV 값에서는 더 낮았고, 매우 작은 실제 값에서는 더 높았다.

의의 및 주장

본 논문은 인과 구조가 관련이 있는 경우 ASV가 설명 가능성을 위한 실행 가능하고 잠재적으로 더 우수한 프레임워크임을 주장하며, 이는 표준 SHAP이 놓치는 의존성을 포착하기 때문이다. 본 논문의 주요 기여는 인과적 제약 조건이 특정 모델-분포 쌍(예: 나이브 베이즈 하의 결정 트리)에서 난해한 문제를 계산 가능한 문제로 변환할 수 있음을 입증한 것이다.

저자들은 ASV가 이러한 이론적, 실무적 이점을 제공하지만, 그 확장성은 인과 그래프의 토폴로지에 크게 의존한다고 강조한다:

• 루트가 있는 유향 트리 및 폴리트리의 경우, 동치류를 통한 정확한 계산이 가능하다.
• 밀집되거나 큰 DAG의 경우, 동치류의 수가 여전히 너무 커질 수 있으므로 샘플링 기반의 근사가 필요하다.

결론적으로, AS metal은 인과 그래프가 알려져 있고 그래프 구조가 효율적인 열거 또는 샘플링을 허용하는 경우, XAI를 위한 유망한 방향이다. 향후 연구로는 더 넓은 클래스의 그래프(예: 일반적인 폴리트리)로 정확한 알고리즘을 일반화하고 샘플링 메커니즘을 최적화하는 것이 제안된다.