Axiomatic Foundations of Counterfactual Explanations

기술 요약: 반사실적 설명의 공리적 기초

문제 정의
본 논문은 설명 가능한 인공지능(XAI) 문헌의 결정적인 공백을 다룬다. 반사실적 설명(“왜 아닌가?”라는 질문에 답하는 것)은 자율 시스템에 대한 신뢰를 높이기 위한 매력적인 방법으로 부상했으나, 기존 연구는 다음과 같은 두 가지 주요 한계점을 갖는다:

1. 체계적 분류의 부재: 기존 연구의 대부분은 단일 유형의 국소적(local) 반사실(개별 인스턴스에 맞춤화된 것)에 집중하며, 대안적인 유형들을 체계적으로 연구하지 못하고 있다.
2. 전역적(Global) 설명의 소홀: 개별 예측이 아닌 모델의 전반적인 추론 과정을 설명하고자 하는 전역적 반사실에 대한 관심이 부족하다.
   결과적으로, 국소적 반사실과 전역적 반사실 사이의 이론적 트레이드오프, 그리고 "근접성(closeness)" 또는 "타당성(validity)"의 서로 다른 정의들 사이의 관계는 여전히 제대로 이해되지 않고 있다.

방법론
저자들은 반사실적 설명기를 체계적으로 정의, 비교 및 특성화하기 위해 **공리적 프레임워크(axiomatic framework)**를 제안한다. 이론 과학에서 흔나히 쓰이는 이 접근법은 명확하게 진술된 공리(기초적인 속성) 세트를 기반으로 체계를 구축하여 표현 정리(representation theorems)를 도출한다.

• 공식 설정: 프레임워크는 분류 이론 $T = \langle F, dom, C \rangle$ (특징, 도메인, 클래스)와 분류기 $\kappa$ 위에서 작동한다. 쿼리는 $Q = \langle T, \kappa, x \rangle$로 정의된다.
• 공리: 논문은 세 가지 범주로 그룹화된 9개의 공리를 도입한다:
  • 일반 속성: 성공(Success, 비어 있지 않은 출력), 비자명성(Non-Triviality, 빈 집합이 아님), 동등성(Equivalence, 동일 클래스 $\to$ 동일 설명), 실현 가능성(Feasibility, 설명은 인스턴스의 부분집합임).
  • 필요한 이유(Necessary Reasons) 속성: 핵심성(Coreness, 설명은 핵심 리터럴만을 포함함), 회의적 타당성(Sceptical Validity, 설명을 제거하면 클래스 변화가 보장됨).
  • 충분한 이유(Sufficient Reasons) 속성: 참신성(Novelty, 설명은 원래 인스턴스의 리터럴을 포함하지 않음), 강한 타당성(Strong Validity, 설명의 존재가 클래스 변화를 보장함), 약한 타당성(Weak Validity, 값을 설명으로 교체하면 다른 클래스가 됨).
• 분석: 저자들은 이 공리들을 사용하여 불가능성 정리(특정 조합이 서로 양립할 수 없음을 보여줌)와 표현 정리(공리 부분 집합과 설명 모델 군 사이의 일대일 대응 관계를 확립함)를 증명한다.

주요 기여
본 논문은 여섯 가지 주요 기여를 한다:

1. 공리적 프레임워크: 반사실적 설명기를 정의하기 위해 9개의 공리에 기반한 프레임워크를 도입한다.
2. 불가능성 정리: 단일 설명기가 특정 공리 조합을 동시에 만족할 수 없음을 증명한다 (예: Success, Non-Triviality, Coreness는 양립 불가능함).
3. 호환 가능한 집합의 특성화: 호환 가능한 모든 공리 집합을 완전히 특성화한다.
4. 표현 정리: 특정 공리 부분 집합과 다섯 가지의 뚜리한 설명 모델 군 사이의 일대일 대응 관계를 확립하여, 다섯 가지 근본적으로 다른 유형의 반사실을 밝혀낸다:
   • 전역적 필요한 이유 (GNR): 한 클래스를 다른 모든 클래스와 구별하는 특징-값 조합 (Coreness, Non-Triviality 만족).
   • 국소적 회의적 필요한 이유 (SNR): 인스턴스를 다른 결정(decision)을 가진 모든 다른 인스턴스로부터 구별하는 인스턴스의 부분 집합 (Feasibility, Sceptical Validity 만족).
   • 전역적 충분한 이유 (GSR): 존재 시 다른 클래스를 보장하는 특징-값 조합 (Strong Validity 만족).
   • 국소적 회의적 충분한 이유 (SSR): 인스턴스에 없던 새로운 특징 값을 통해 다른 결정을 보장하는 것 (Novelty, Strong Validity 만족).
   • 국소적 낙관적 충분한 이유 (CSR): 다른 결정을 가진 어떤 인스턴스와 인스턴스를 구별하는 특징-값 조합 (Novelty, Weak Validity 만족).
5. 기존 연구의 분류학: 기존 설명기들을 이 분류 체계 내에서 공식적으로 특성화한다. 논문은 거의 모든 기존 국소적 설명기가 낙관적 충분한 이유 (CSR) 군에 속한다는 것을 발견했다. 선행 연구[2]에서 제안된 전역적 설명기는 **전역적 필요한 이유 (GNR)**에 해당한다. 이 분석은 이전에 인식되지 않았던 세 가지 유형(SNR, GSR, SSR)을 드러낸다.
6. 복잡도 분석: 이러한 설명을 생성하는 계산 복잡도를 분석하며, 결정 문제(설명이 유효한지 확인)와 탐색 문제(설명을 생성)를 구분한다.

결과

• 분류: 다섯 가지 유형의 반사실은 두 가지 근본적인 형태, 즉 필요한 이유(결정을 바꾸기 위해 반드시 결여되어야 하는 것)와 충분한 이유(결정을 바꾸기 위해 반드시 존재해야 하는 것)로 나뉜다.
• 존재성 및 압축성(Compactness):
  • 필요한 이유(GNR, SNR)와 회의적 충분한 이유(SSR)는 모든 쿼리에 대해 존재가 보장되지 않는다.
  • 낙관적 충분한 이유(CSR)와 전역적 충분한 이유(GSR)는 존재가 보장된다.
  • 필요한 이유는 압축적이다 (최소한의 리터럴 세트를 통해 전체 변화 범위를 전달함). 반면 충분한 이유는 비압축적이다 (모든 가능한 변화를 열거함).
• 인간의 선호도: 논문은 필요한 이유가 존재하는 경우, 흔히 매우 많고 장황한 충분한 이유에 비해 짧고 간결한 설명을 원하는 인간의 선호에 더 잘 부합한다고 주장한다.
• 복잡도:
  • 불리언(Boolean) 분류기의 경우, 설명의 유효성을 결정하는 문제($DECIDEEXP$)는 CSR, SNR 및 희소성(sparsity) 기반 설명기의 경우 $O(n)$이지만, GNR, GSR, SSR 및 카디널리티/거리 기반 설명기의 경우 co-NP-complete이다.
  • 설명을 찾는 문제($FINDEXP$)는 대부분의 군(GNR, CSR, SNR, GSR 포함)에서 NP-hard이지만, 대부분의 경우 최대 $n$번의 SAT 오라클 호출로 해결 가능하다.

의의
본 논문은 반사실적 설명에 대한 최초의 공리적 프레임워크를 제공한다고 주장한다. 그 의의는 다음과 같다:

1. 이론적 엄밀성: 경험적 평가를 넘어, 만족하는 공리에 기반하여 설명기를 객관적이고 원칙적으로 비교할 수 있는 토대를 마련했다.
2. 통합 및 발견: 기존의 국소적 설명기를 CSR 군으로 통합하는 동시에, 이전에 인식되지 않았던 세 가지 새로운 유형(SNR, GSR, SSR)을 공식적으로 정의하고 식별했다.
3. 모델 불가지론적 일반성: 이 프레임워크는 다양한 설정과 분류기 유형에 적용 가능하다.
4. 향후 연구를 위한 토대: 가능한 설명기의 공간을 특성화함으로써, 특정 반사실 유형 내에서 특정 바람직한 속성(예: 실행 가능성, 공정성, 다양성)을 만족하는 설명기를 설계할 수 있는 길을 열어준다.

저자들은 필요한 이유가 이론적으로는 매력적이지만, 존재성 측면에서는 충분한 이유가 더 견고하다고 결론짓는다. 이 프레임워크는 이러한 트레이드오프를 체계적으로 탐색할 수 있는 필수적인 도구를 제공한다.