🤖 AI

ExplAIner: A Declarative Query Language for Explaining Classification Models

이 논문은 불리언 분류 모델을 위한 다양한 설명 개념들을 통합하는 선언적 쿼리 언어인 ExplAIner를 소개하며, 이의 평가가 유한한 횟수의 SAT 솔버 호출을 통해 계산 가능하다는 점과 최적화 지향적 파편인 Opt-FOIL이 다항식 번의 호출로 최소 설명을 계산할 수 있게 한다는 점을 입증한다.

원저자: Marcelo Arenas, Pablo Barceló, Diego Bustamante, Jose Caraball, María Alejandra Schild, Bernardo Subercaseaux

게시일 2026-07-08

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Marcelo Arenas, Pablo Barceló, Diego Bustamante, Jose Caraball, María Alejandra Schild, Bernardo Subercaseaux

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신은 아주 똑똑하지만 신비로운, 결정을 내리는 로봇을 상상해 보세요. 아마도 이 로봇은 누가 대출을 받을 수 있는지, 혹은 의료 스캔 결과가 의심스러운지 등을 결정할 것입니다. 당신이 로봇에게 "왜 이 특정 사람에게 '예'라고 했나요?"라고 묻습니다.

로봇은 단순히 간단한 이유를 대지 않습니다. 그 안에는 블랙박스가 들어 있습니다. 이를 이해하기 위해 연구자들은 수십 가지의 서로 다른 질문을 던지는 방법을 고안했습니다: "가장 작은 이유는 무엇인가?", "만약 한 가지를 바꾼다면 어떻게 될까?", "어떤 특징들이 절대적으로 필요했는가?"

이 논문은 이러한 다양한 질문 방식이 너무 무질서하다고 주장합니다. 이는 마치 정말로 하나의 유니버설 키링(universal keyring)이 필요한데, 천 개의 자물쇠에 천 개의 서로 다른 열쇠를 가지고 있는 것과 같습니다. 저자들은 어떤 질문을 하더라도 동일한 규칙을 사용하여 질문할 수 있는 보편적인 언어(쿼리 언어)를 만들고자 하며, 컴퓨터가 이 질문들에 답하는 것이 정확히 얼마나 어려운지 알고 싶어 합니다.

다음은 일상적인 비유를 사용한 그들의 여정에 대한 설명입니다:

1. 오래된 도구: FOIL ("고장 난 손전등")

연구자들은 먼저 FOIL이라는 기존 도구를 살펴보았습니다. FOIL을 로봇의 블랙박스 내부를 들여다보는 데 사용하는 손전등이라고 생각해보세요.

문제점: 이 손전등은 너무 약합니다. "가장 작은" 또는 "최선의" 이유(예: 필요한 특징의 최소 개수를 찾는 것)를 찾아내지 못합니다. 이는 마치 큰 바위들만 보여주는 손전등으로 모래더미 속에서 가장 작은 조약돌을 찾으려는 것과 같습니다.
위험성: 더 심각하게, 이 손전등은 나쁜 의미로 너무 강력합니다. 특정 질문을 던지면 컴퓨터의 두뇌가 폭발해 버립니다. 수학적으로 볼 때, 결정 트리(decision tree)와 같은 단순한 모델에 대해서도 어떤 질문들은 컴퓨터가 불가능한 숫자의 가능성을 확인해야 함을 보여줍니다. 이는 계산기에 해변의 모든 모래알을 세라고 시키는 것과 같습니다. 시간이 너무 오래 걸립니다.

2. 새로운 도구: ExplAIner ("스마트하고 층이 나뉜 지도")

이를 해결하기 위해 저자들은 ExplAIner라는 새로운 언어를 구축했습니다. 이것을 로봇의 의사결정 과정을 보여주는 고도의 기술이 집약된, 층이 나뉜 지도로 상상해 보세요.

레이어 1 (원자 레이어 - Atomic Layer): 이것은 기본적인 지형입니다. 정보의 조각들을 비교하는 법을 압니다(예: "이 조각은 누락된 부분이 3개이고, 저것은 5개이다"). 저자들은 이 레이어가 읽기 쉽다는 것을 증증했습니다. 컴퓨터는 이를 즉시 처리할 수 있습니다.
레이어 2 (정량화 레이어 - Quantified Layer): 이 레이어는 로봇의 행동에 대해 질문합니다. "만약 내가 이 누락된 부분들을 채운다면, 로봇은 항상 '예'라고 할 것인가?" 또는 "그것은 항상 '아니오'라고 할 것인가?" 이 레이어는 조금 더 어렵지만, 여전히 관리 가능한 수준입니다(이는 NP라는 범주에 속하며, 이는 어렵긴 하지만 탐색을 통해 해결 가능하다는 뜻입니다).
레이어 3 (전체 ExplAIner): 이것은 이 모든 것을 결합하는 최상위 레이어입니다. 당신은 "최소한이면서 동시에 특징 X를 포함하는 이유가 존재하는가?"와 같은 복잡한 질문을 던질 수 있습니다.
마법: 저자들은 이러한 복잡한 질문에도 불구하고 컴퓨터가 미쳐 날뛰지 않을 것임을 증명했습니다. 컴퓨터는 "조력자"(SAT solver, 즉 초스마트 퍼즐 해결사)에게 고정된 횟수만큼 질문함으로써 답을 찾을 수 있습니다. 이는 마치 사서가 도서관이 아무리 커지더라도 딱 세 번의 질문만으로 도서관의 어떤 책이든 찾아낼 수 있는 것과 같습니다.

3. 최적화 도구: Opt-FOIL ("효율적인 요리사")

함정이 하나 있습니다. 질문을 던지는 것(이유가 존재하는지 확인하는 것)이 반드시 답을 쉽게 찾는 것(실제 이유를 찾아내는 것)을 의미하지는 않습니다. 이는 완벽한 케이크 레시피가 있다는 것은 알지만, 주방을 다 태워 먹지 않고 어떻게 구워야 할지는 모르는 것과 같습니다.

이를 해결하기 위해 그들은 이 언어의 특수한 하위 집합인 Opt-FOIL을 만들었습니다.

개념: 이것은 단순히 아무 케이크나 찾는 것이 아니라, 맛은 좋으면서도 가장 작은 케이크, 혹은 설탕이 가장 적게 들어간 케이크를 찾는 요리사와 같습니다.
결과: 저자들은 이러한 "최선의" 질문들에 대해 컴퓨터가 실제로 효율적으로 답을 찾을 수 있음을 증명했습니다. 컴퓨터는 문제의 크기에 따라 합리적으로 증가하는 횟수만큼 "조력자"(퍼즐 해결사)에게 질문함으로써 이를 수행할 수 있습니다. 이는 요리사가 주방을 태우지 않고도 완벽한 케이크를 보장하는 단계별 가이드를 가지고 있는 것과 같습니다.

4. 이것이 왜 중요한가 ( "유니버설 키링")

핵론은 저자들이 AI를 설명하기 위한 표준화된 프레임워크를 만들었다는 것입니다.

통일성: 모든 종류의 설명(귀납적, 대조적, 특징 기반 설명 등)을 위해 매번 새로운 컴퓨터 프로그램을 작성하는 대신, 이 새로운 언어로 쿼리를 작성하기만 하면 됩니다.
안전성: 이 쿼리들이 컴퓨터를 다운시키지 않을 것임을 수학적으로 증명했습니다. 이 쿼리들은 "안전 구역" 내에 머물며, 이는 이미 업계에서 사용되는 강력한 도구들(SAT solver)을 사용하여 해결될 수 있음을 의미합니다.
유연성: 다양한 유형의 설명을 혼합하고 조합할 수 있습니다. 가장 작은 이유, 가장 큰 이유, 또는 특정 특징(예: 성별)을 무시하는 이유 등을 모두 동일한 규칙을 사용하여 물을 수 있습니다.

요약 비유

AI 모델을 잠겨 있는 보물 상자라고 상상해 보세요.

FOIL은 가끔 맞지 않는 열쇠였습니다(가장 작은 이유를 찾지 못함) 또한 가끔은 문을 부술 정도로 너무 세게 잠겨버렸습니다(계산하기에 너무 복잡함).
ExplAIner는 마스터 키링입니다. 서로 다른 잠금장치에 맞는 다양한 열쇠를 가지고 있지만, 그 열씨들은 모두 동일한 메커니즘에 맞습니다. 저자들은 이 키들을 사용하는 것이 잠금장치를 망가뜨리지 않을 것임을 증명했습니다.
Opt-FOIL은 이 키링에 달린 특수 도구로, 상자를 열 뿐만 아니라 자동으로 가장 작은 열쇠 구멍이나 가장 가치 있는 보석을 빠르고 효율적으로 찾아냅니다.

이 논문은 이것이 내일 당장 질병을 치료하거나 주식 시장을 예측할 것이라고 주장하는 것이 아닙니다. 단지 이렇게 말하는 것입니다: "우리는 AI 모델에 '왜?'라고 물을 수 있는 더 나은, 더 안전하고, 더 조직적인 방법을 만들었으며, 우리의 새로운 방식이 컴퓨터를 망가뜨리지 않고 작동한다는 것을 수학적으로 증명했습니다."

기술 요약: ExplAIner: 분류 모델 설명을 위한 선언적 쿼리 언어

1. 문제 정의

설명 가능한 AI(XAI) 분야는 다양한 설명 개념, 점수 및 쿼리(예: 귀추적, 대조적, 특징 필수성, 반사실적 설명)의 확산을 초래했습니다. 데이터 관리 관점에서 이러한 다양성은 통일된 프레임워크가 결여되어 있습니다. 기존의 접근 방식은 각 설명 작업마다 별도의 알고리즘을 설계해야 하는 경우가 많습니다. 본 논문은 이러한 설명 개념들을 통일적으로 지정, 결합 및 분석하기 위해 선언적 쿼리 언어가 필요하다고 주장합니다.

그러나 기존의 기초적인 언어들은 두 가지 결정적인 한계에 직면해 있습니다:

표현력(Expressiveness): 이들은 중심적인 최적성 기반 설명 개념(예: 최소 귀추적 설명)을 포착하는 데 실패하는 경우가 많습니다.
복잡도(Complexity): 이들의 평가 문제는 다항 계층(PH)의 높은 수준에 도달하여 난해해질 수 있으며, 이는 표준 SAT 기반 엔진을 사용한 구현을 불가능하게 만듭니다.

핵심 과제는 광범위한 설명 쿼리 군을 포착할 수 있는 충분한 표현력과, 제어된 평가 복잡도(구체적으로, SAT 솔버를 통한 트랙터빌리티(tractability), 즉 NP 상의 불리언 계층에 대응함) 사이의 균형을 맞추는 논리를 설계하는 것입니다.

2. 방법론 및 프레임워크

저자들은 불리언 모델(함수 $M: \{0, 1\}^n \to \{0, 1\}$ )을 쿼리가 평가되는 구조체로 취급하여 이를 설명하기 위한 프레임워크를 개발합니다. 방법론은 세 단계로 진행됩니다.

2.1 FOIL 분석

본 논문은 모델을 부분 인스턴스에 대한 양의 인스턴스와 포함 관계( $\subseteq$ )에 접근할 수 있는 블랙박스로 취급하는 모델 불가지론적 논리인 FOIL(First-Order Interpretability Logic)을 먼저 재검토합니다.

표현력의 한로: 저자들은 FOIL이 의사결정 트리(decision trees) 환경에서 최소 귀추적 설명(mAXp) 쿼리를 표현할 수 없음을 증명합니다. 이는 포함 관계만을 기반으로 할 때, FOIL이 최소 설명이 존재하는 모델과 존재하지 않는 모델을 구분할 수 없음을 Ehrenfeucht-Fraïssé 게임을 통해 보여줌으로써 입증되었습니다.
복잡도의 한계: 의사결정 트리 상에서의 FOIL 평가 문제가 다항 계층의 모든 단계( $\Sigma^P_k$ -hard)에 대해 어렵다는 것이 밝혀졌습니다. 이는 FOIL이 NP 오라클에 대한 다항 횟수의 호출만으로는 평가될 수 없음을 의미하며, 따라서 실용적인 SAT 기반 평가에 부적합함을 시사합니다.

2.2 ExplAIner 도입

이러한 한계를 해결하기 위해, 저자들은 확장된 어휘를 가진 계층적 1차 논리인 ExplAIner를 도입합니다.

어휘 확장: ExplAIner는 정의된 특징의 수(카디널리티)를 기준으로 부분 인스턴스를 비교하는 이항 관계 $\preceq$ 를 추가합니다. 저자들은 $\subseteq$ 와 $\preceq$ 가 독립적이며, 의사결정 트리 위에서 어느 하나가 다른 하나로 정의될 수 없음을 증명합니다.
계층적 구조:
1. 원자 계층(Atomic Layer): $\{\subseteq, \preceq\}$ 에 대한 공식입니다. 이는 모델이 아닌 부분 인스턴스의 구조에만 의존합니다. 평가는 P(다항 시간) 내에 있으며, 유효성 검사는 Presburger 산술로의 환원을 통해 결정 가능합니다.
2. 양화 계층(Quantified Layer): 원자 계층에 AllPos 및 AllNeg 술어(부분 인스턴스의 모든 완성이 양 또는 음으로 분류되는지 확인)와 가드된 양화사(guarded quantifiers)를 확장합니다. 가드된 양화사는 보편 양화(universal quantification)를 정확히 하나의 특징이 정의된 부분 인스턴스로 제한합니다. 만약 AllPos와 AllNeg가 특정 모델 클래스에 대해 트랙터블(P 내에 존재)하다면, 이 계층의 평가는 NP에 속합니다.
3. 전체 ExplAIner 계층(Full ExplAIner Layer): 양화 계층의 공식들에 대한 불리언 조합을 허용합니다. 이 계층은 NP 상의 불리언 계층(BH) 전체를 포착합니다.

2.3 Opt-FOIL 도입

평가(인스턴스가 설명인지 확인하는 것)와 계산(설명을 찾는 것)이 다르다는 점을 인식하여, 저자들은 Opt-FOIL을 정의합니다.

메커니즘: Opt-FOIL은 정의 가능한 엄격한 부분 순서(strict partial orders)에 대한 최소화 연산자(min)가 추가된 ExplAIner의 파편(fragment)입니다.
구문(Syntax): 공식 $\Psi = \min[\varphi, \rho]$ 는 논리적 명세 $\varphi$ 를 만족하면서 $\rho$ 라는 엄격한 부분 순서에 대해 최소인 인스턴스 $x$ 를 계산합니다.
구문 결정 가능성: 논문은 주어진 원자 공식이 엄격한 부분 순서를 정의하는지 검증하는 알고리즘(Presburger 산술 기반)을 제공하여, Opt-FOIL이 결정 가능한 구문을 가짐을 보장합니다.

3. 주요 기여 및 결과

3.1 FOIL의 한계

정리 3.1: 어떤 FOIL 공식도 의사결정 트리 상에서 최소 귀추적 설명 쿼리를 정의할 수 없습니다.
정리 3.4: 다항 계층의 모든 단계 $k$ 에 대하여, 의사결정 트리 상에서 평가가 $\Sigma^P_k$ -hard인 고정된 FOIL 공식이 존재합니다.

3.2 ExplAIner의 표현력 및 복잡도

표현력: ExplAIner는 다음과 같은 광범위한 설명 개념을 성공적으로 인코딩합니다:
- 약한/귀추적/최소 귀추적 설명 (wAXp, AXp, mAXp).
- 약한/대조적/최대 대조적 설명 (wCXp, CXp, mCXp).
- 최소 변경 필요량 (MCR) 및 최대 허용 변경량 (MCA).
- 필수적 및 관련 특징 (NF, RF).
복잡도 경계:
- 원자 계층: 평가는 P에 속합니다.
- 양화 계층: 만약 AllPos와 AllNeg가 P에 있다면, 평가는 NP에 속합니다. 의사결정 트리 상에서 NP-완전인 쿼리들이 이 계층에 존재합니다.
- 전체 계층: 만약 AllPos와 AllNeg가 P에 있다면, 평가는 **불리언 계층(BH)**에 속합니다. 모든 $BH_k$ 단계에 대하여, 의사결정 트리 상에서 $BH_k$ -hard인 ExplAIner 쿼리가 존재합니다.
- 적용 가능성: 이러한 경계는 의사결정 트리, 결정론적 분해 가능 부정 정규형(d-DNNF) 회로, 2CNF, Horn CNF에 대해 유효합니다.

3.3 Opt-FOIL의 계산적 보장

정리 5.3: 만약 AllPos와 AllNeg가 P에 있다면, 임의의 Opt-FOIL 공식의 계산 문제는 FPNP(다항 횟수의 NP 오라클 호출을 사용하는 다항 시간 함수)에 속합니다.
알고리즘: 계산은 엄격한 부분 순서 내의 경로를 구축하는 과정을 포함합니다. 이러한 경로의 길이는 다항적으로 제한되므로(보조정리 5.5), 알고리즘은 다항 횟수의 SAT 솔러 호출과 함께 종료됩니다.
엄격한 포함 관계: 다항 계층이 붕괴하지 않는다고 가정할 때, Opt-FOIL은 ExplAIner에 엄격히 포함되며, ExplAIner는 (확장된 술어를 가진) FOIL에 엄격히 포함됩니다. 이는 Opt-FOIL이 계산적 트랙터빌리티를 얻기 위해 일부 표현력(예: 특정 비최적성 쿼리)을 희생했음을 확인시켜 줍니다.

4. 의의 및 주장

본 논문은 ExplAIner와 Opt-FOIL이 형식적 XAI를 위한 원칙적이고 선언적인 토대를 제공한다고 주장합니다.

통일성: 이들은 다양한 설명 개념을 지정할 수 있는 단일 언어를 제공하여, 기준의 결합(예: 여러 인스턴스에 대한 공통 설명 찾기)을 가능하게 합니다.
트랙터빌리티: 논리를 평가가 BH 내에 있고 계산이 FPNP 내에 있는 계층으로 제한함으로써, 프레임워크는 현대적인 SAT 솔버의 능력과 일치하도록 설계되었습니다. 이는 형식적 XAI가 의사결정 트리나 d-DNNF 회로와 같은 모델에 대한 SAT 인코딩에 의존하는 경우가 많기 때문에 매우 중요합니다.
관심사의 분리: 프레임워크는 설명 쿼리의 논리적 명세와 평가의 표현 의존적 복잡성을 분리합니다. 이를 통해 동일한 쿼리 언어를 효율적인 일관성 검사(AllPos/AllNeg)를 지원하는 다양한 모델 클래스(트리, 회로 등)에 적용할 수 있습니다.

저자들은 FOIL이 기초적인 이론적 도구로서 기능하지만, 높은 복잡도와 최적성에 관한 제한된 표현력 때문에 실제 구현에는 부적합하다고 결론짓습니다. ExplAIner와 Opt-FOIL은 이러한 문제를 해결하여 불리언 모델에 대한 설명을 효율적으로 지정하고 계산할 수 있게 합니다.